Metaheuristic Algorithms for Decoding Binary Linear Codes

Authors: Hassan Berbia, Faissal Elbouanani, Rahal Romadi, Mostafa Belkasmi

Abstract:

This paper introduces two decoders for binary linear codes based on Metaheuristics. The first one uses a genetic algorithm and the second is based on a combination genetic algorithm with a feed forward neural network. The decoder based on the genetic algorithms (DAG) applied to BCH and convolutional codes give good performances compared to Chase-2 and Viterbi algorithm respectively and reach the performances of the OSD-3 for some Residue Quadratic (RQ) codes. This algorithm is less complex for linear block codes of large block length; furthermore their performances can be improved by tuning the decoder-s parameters, in particular the number of individuals by population and the number of generations. In the second algorithm, the search space, in contrast to DAG which was limited to the code word space, now covers the whole binary vector space. It tries to elude a great number of coding operations by using a neural network. This reduces greatly the complexity of the decoder while maintaining comparable performances.

Keywords: Block code, decoding, methaheuristic, genetic algorithm, neural network

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1081129

References:

[1] G. C. Clarck, J.B. Cain , "Error-Correction Coding for Digital Communications", New York Plenum, 1981
[2] G.D. Forney, Jr., "Generalized Minimum Distance Decoding", IEEE Transactions on Information Theory, vol. IT-12, pp. 125-131, April 1966
[3] Ja-Ling Wu, Yuen-Hsien Tseng, and Yuh-Ming Huang, "Neural Networks Decoders for Linear Block Codes", International Journal of Computational Engineering Science, vol.3, No.3, pp.235-255, 2002
[4] M.P.C. Fossorier and S. lin, "Soft decision decoding of linear block codes based on ordered statistics", IEEE Trans. information theory Vol. 41, pp. 1379-1396, sep. 1995.
[5] H. Morelos-Zaragoza, "The Art of Error Correcting Coding", Second Edition Robert , John Wiley & Sons, Ltd. ISBN: 0-470-01558-6, 2006
[6] F. El Bouanani, H. Berbia, M. Belkasmi, H. Ben-azza, "Comparaison des d'ecodeurs de Chase, l-OSD et ceux bas'es sur les algorithmes g'en'etiques", GRETSI 2007, Troyes, French 11-14, September 2007
[7] H. Berbia, F.El Bouanani, M.Belkasmi, F.Ayoub, R.Romadi, "Optimisation des performances d-un dcodeur a base d-algorithmes g'en'etiques", Wotic07, Rabat 5-6 July 2007, Maroc
[8] M. Belkasmi, H. Berbia, F. El Bouanani, "Iterative decoding of product block codes based on genetic algorithms", SCC 2008, 14-16 January 2008, Ulm Germany
[9] Y. S. Han, C. R. P. Hartmann, and C.-C. Chen, "Efficient maximumlikelihood soft-decision decoding of linear block codes using algorithm A*", Technical Report SU-CIS-91-42, School of Computer and Information Science, Syracuse University, Syracuse, NY 13244, December 1991
[10] J. Holland, "Adaptation in Natural and Artificial Systems", University of Michigan Press 1975.
[11] H.S. Maini, K. G. Mehrotra,C. Mohan, S. Ranka, "Genetic Algorithms for Soft Decision Decoding of Linear Block Codes", Journal of Evolutionary Computation, Vol.2, No.2, pp.145-164, Nov.1994
[12] A.G. Scandura,A.L.Daipra,L.Arnone,L.Passoni,J.C. Moreira, "AGenetic Algorithm Based Decoder for Low Density Parity Check Codes" Latn American Applied Research 2006
[13] D. E. Goldberg, "Genetic Algorithms in search, Optimization, and machine learning", Addison-Wesly, Reading M.A, 1989.
[14] G. Cybencko ,"Approximation by superpositions of a sigmo¨ıdal function," Mathematics of Control, signals and systems, 2, pp. 303-314, 1989.
[15] M.T. Mitchell ,"Machine learning," New York: The McGraw-Hill Companies, 1997.
[16] H. Berbia, M. Belkasmi, F. El Bouanani, F. Ayoub, "On the decoding of convolutional codes using genetic algorithms", Intern. Conf. on Computer and Commun. Engineering ICCCE-2008, pp 667-671, Malaysia, 2008
[17] H. Berbia, F.El Bouanani, M.Belkasmi, F.Ayoub, R.Romadi, "An Enhanced Genetic Algorithm Based Decoder for Linear Codes," ICTTA-08 , Damascus, Syria, 2008