A Novel Decoder Based on Parallel Genetic Algorithms for Linear Block Codes

Abdeslam Ahmadi, Faissal El Bouanani, Hussain Ben-Azza, Youssef Benghabrit

Department of Communication Networks, National High School of Comptuer Science and System Analysis, Rabat, Morocco.
Department of Industrial and Production Engineering, Moulay Ismail University, National High School of Arts and Trades, Meknès, Morocco.

DOI: 10.4236/ijcns.2013.61008                

Abstract

Genetic algorithms offer very good performances for solving large optimization problems, especially in the domain of error-correcting codes. However, they have a major drawback related to the time complexity and memory occupation when running on a uniprocessor computer. This paper proposes a parallel decoder for linear block codes, using parallel genetic algorithms (PGA). The good performance and time complexity are confirmed by theoretical study and by simulations on BCH(63,30,14) codes over both AWGN and flat Rayleigh fading channels. The simulation results show that the coding gain between parallel and single genetic algorithm is about 0.7 dB at BER = 10﹣⁵ with only 4 processors.

Keywords

Channel Coding; Linear Block Codes; Meta-Heuristics; Parallel Genetic Algorithms; Parallel Decoding Algorithms; Time Complexity; Flat Fading Channel; AWGN

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	R. W. Hamming, “Error Detecting and Error Correcting Codes,” Bell System Technical Journal, Vol. 29, No. 2, 1950, pp. 47-160.
[2]	C. E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal, Vol. 27, 1948, pp. 379-423, pp. 623-656.
[3]	S. Roman, “Introduction to Coding and Information Theory,” Spring Verlag, New York, 1996.
[4]	C. Berrou and A. Glavieux, “Near Optimum Error Correcting Coding and Decoding: Turbo Codes,” IEEE Transactions on Communications, Vol. 44, No. 10, 1996, pp. 1261-1271. doi:10.1109/26.539767
[5]	D. J. C. Mackay and R. M. Neal, “Good Codes Based on Very Sparse Matrices,” 5th IMA Conference on Cryptography and Coding. Lecture Notes in Computer Science number 1025, October 1995, Springer, Berlin, pp. 100-111. doi:10.1007/3-540-60693-9_13
[6]	Y. S. Han, C. R. P. Hartmann and C.-C. Chen, “Efficient Maximum Likelihood Soft-Decision Decoding of Linear Block Codes Using Algorithm A*,” Technical Report SU-CIS-91-42, Syracuse University, Syracuse, 1991.
[7]	H. S. Maini, K. G. Mehrotra, C. Mohan and S. Ranka, “Genetic Algorithms for Soft Decision Decoding of Linear Block Codes,” Journal of Evolutionary Computation, Vol. 2, No. 2, 1994, pp. 145-164. doi:10.1162/evco.1994.2.2.145
[8]	J. L. Wu, Y. H. Tseng and Y. M. Huang, “Neural Networks Decoders for Linear Block Codes,” International Journal of Computational Engineering Science, Vol. 3, No. 3, 2002, pp. 235-255. doi:10.1142/S1465876302000629
[9]	F. El Bouanani, H. Berbia, M. Belkasmi and H. Ben-Azza, “Comparison between the Decoders of Chase, OSD and Those Based on Genetic Algorithms,” 21 Colloquium of GRETSI (Group of Study and Signal and Pictures Processing), Troyes, 11-14 September 2007, pp. 1153-1156.
[10]	M. Belkasmi, H. Berbia and F. El Bouanani, “Iterative Decoding of Product Block Codes Based on the Genetic Algorithms,” 7th International ITG Conference on Source and Channel Coding (SCC’08), Ulm, 14-16 January 2008, pp. 1-6.
[11]	A. Ahmadi, F. El Bouanani, H. Ben-Azza and Y. Benghabrit, “Reduced Complexity Iterative Decoding of 3D-Product Block Codes Based on Genetic Algorithms,” Journal of Electrical and Computer Engineering, Vol. 2012, 2012, Article ID: 609650.
[12]	R. Pyndiah, A. Glavieux, A. Picart and S. Jacq, “Near Optimum Decoding of Product Codes,” IEEE Proceedings of Global Telecommunications Conference, San Francisco, 28 November-2 December 1994, Vol. 1, pp. 339-343.
[13]	P. A. Martin, D. P. Taylor and M. P. C. Fossorier, “Soft-Input Soft-Output List-Based Decoding Algorithm,” IEEE Transactions on Communications, Vol. 52, No. 2, 2004, pp. 252-264.
[14]	S. Lin and D. Costello, “Error Control Coding: Fundamentals and Applications,” Prentice-Hall, Upper Saddle River, 1983.
[15]	A. Tanenbaum, “Computer Architecture,” Dunod, Paris, 2001.
[16]	J. H. Holland, “Adaptation in Natural and Artificial Systems,” University of Michigan Press, Ann Arbor, 1975.
[17]	D. E. Goldberg, “Genetic Algorithms in Search, Optimization, and Machine Learning,” Addison-Wesley, Boston, 1989.
[18]	E. Alba and M. Tomassini, “Parallelism and Evolutionary Algorithms,” IEEE Transactions on Evolutionary Computation, Vol. 6, No. 5, 2002, pp. 443-462.
[19]	E. Alba and J. M. Troya. “A Survey of Parallel Distributed Genetic Algorithms,” Complexity, Vol. 4, No. 4, 1999, pp. 31-52. doi:10.1002/(SICI)1099-0526(199903/04)4:4<31::AID-CPLX5>3.0.CO;2-4
[20]	T. Starkweather, D. Whitley and K. Mathias, “Optimization Using Distributed Genetic Algorithm,” Springer Verlag, New York, 1991, pp. 176-185. doi:10.1007/BFb0029750
[21]	V. S. Gordon and D. Whitley, “A Machine-Independent Analysis of Parallel Genetic Algorithms,” Complex Systems, Vol. 8, 1994, pp. 181-214.