On Non-Linear Finite State Digital Channel Coding
Abstract
Abstract. A discrete-time digital channel coding, in which the encoder and decoder are both time-invariant finite state machines, is investigated. The channel is assumed to be memoryless. Two measures of performance are considered: the probability of error and the minimum free distance. Greater emphasis is placed on the minimum free distance since it is easier to evaluate than the probability of error criterion, and for small channel crossover probability it is a very good indicator of system performance; it is defined as the Hamming distance between two possible output sequences that correspond to distinct state sequences of the same length that are identical at both the start and finish. An algorithm to calculate the distance between such possible output sequences was developed; it also identifies all such pain of output sequence. Another algorithm, based on the finite state machine properties of the encoder, was found to generate the finite state decoder. Finally, after having found the pairs of encoder-decoder finite state machines, we simulated the communication system.
Sari. Suatu kode saluran digital dengan waktu tercacah yang mempunyai pasangan encoder-decoder berupa mesin berkeadaan terhingga dan invarian waktu akan diteliti. Saluran dianggap tanpa daya ingat. Digunakan dua buah ukuran kinerja yaitu probabilitas kesalahan dan jarak bebas minimum. Penggunaan jarak bebas minimum lebih ditekankan karena lebih mudah dievaluasi dibandingkan probabilitas kesalahan. Untuk probabilitas kesalahan saluran yang kecil, jarak itu merupakan indikator yang sangat baik bagi kinerja sistem; ia didefinisikan sebagai jarak Hamming minimum antara dua buah kemungkinan sekuen keluaran yang berupa sekuen keadaan yang unik dengan panjang dan keadaan yang sama, baik di awal maupun di akhir sekuen. Sebuah algoritma untuk menghitung jarak antara sekuen keluaran yang sedemikian itu telah pula dikembangkan; algoritma tersebut juga mampu mengidentifikasi semua pasangan sekuen keluaran itu. Sebuah algoritma lainnya, didasarkan pada sifat-sifat encoder sebagai mesin dengan keadaan berhingga, yang mampu menyusun decoder dengan keadaan berhingga, telah pula ditemukan. Akhirnya, setelah menemukan berbagai pasangan encoder-decoder yang berupa mesin dengan keadaan berhingga, sistem komunikasi digital disimulasikan.
References
Elias, P., Coding for Noisy Channels, IRE Conv. Rec., Part 4, pp. 37-47, 1955.
Viterbi, A.J., Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm, IEEE Trans. Theory, vol.IT-13, no. 2, pp. 260-269, April 1967.
......., Convolutional Codes and Their Performance in Communications Systems, IEEE Trans. on Commun. Technl., vol. COM-19, no. 5, October 1971.
Forney, G. D., Jr., The Viterbi Algorithm, Proc. IEEE, vol. 61, no. 3, pp. 268-278, March 1973.
......., Convolutional Codes I: Algebraic Structure, IEEE Trans. Inform. Theory, vol.IT-16, no. 6, pp.720-738, November 1970.
......., Convolutional Codes II: Maximum Likelihood Decoding, Inform. and Control, vol. 25, no. 3, pp. 222-266, July 1974.
Larsen, K. J., Short Convolutional Codes with Maximum Free Distance for Rate 1/2, 1/3, and 1/4, IEEE Trans. Inform. Theory, vol. IT- 9, no. 3, pp. 371-372, May 1973.
Paaske, E., Short Binary Convolutional Codes with Maximal Free Distance for Rate 2/3 and 3/4, IEEE Trans. Inform. Theory, vol. IT-20, no. 5, pp. 683-689, September 1974.
Johanneson, R. and E. Paaske, Further Results on Binary Convolutional Codes with an Optimum Distance Profile, IEEE Trans. Inform. Theory, vol.lT-24, no. 2, pp. 264-268, March 1978.
Costello, D. J., Jr., Free Distance Bounds for Convolutional Codes, IEEE Trans. Inform. Theory, vol.IT-20, no. 3, May 1974.
Bahl, L. R., et. al, An Efficient Algorithm for Computing Free Distance, IEEE Trans. Inform. Theory, vol. IT-18, no. 3, pp. 437-439, May 1972.
Lanen, K. J., Comments on 'An Efficient Algorithm for Computing Free Distance', IEEE Trans. Inform. Theory, vol IT-19, no. 4, pp. 577-579, July 1973.
Gaarder, N. T. and D. Slepian, On Optimal Finite State Digital Transmission Systems, IEEE Trans. Inform. Theory, vol. IT-28, no. 2, pp. 167- 186, March 1982.
Wiseman, J. A., A construction of Nonlinear Codes Which Betters of Equals Known Results for Certain Parameters, Inform. and Control, no. 48, pp.70-79, 1981.
Lin, S. and D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications. New Jersey: Prentice Hall, 1983.
Petenon, W. W. and E. J. Weldon, Jr., Error Correcting Codes. Cambridge: The MIT Press, 1972.
Viterbi, A. J. and J. K. Omura, Principles of Digital Communication and Coding. New York: McGraw-Hil, 1979.
Wozencraft, J. M. and I. M. Jacobs, Principles of Communication Engineenng. New York: John Wiley and Sons, 1965.
Kohavi, Z., Switching and Finite Automata Theory. New York: McGraw-Hill, 1970.
Booth, T.L., Sequential Machines and Automata Theory. New York: Wiley, 1967.
Deo, N., Graph Teory with Applications to Engineering and Computer Science. New Jersey: Prentice Hall, 1974.
Maurer, H. H., Dota Structures and Progamming Techniques. New Jersey: Prentice Hall, 1977.
Ellis, M. R., A Structured Approach to Fortran 77 Programming. London: Addison-Wesley, 1982.
