Metaheuristic Algorithms for Decoding Binary Linear Codes

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.

Authors:

• Hassan Berbia
• Faissal Elbouanani
• Rahal Romadi
• Mostafa Belkasmi

Keywords:

• Block code
• decoding
• methaheuristic
• genetic algorithm
• neural network

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