Research ArticleOpen AccessGoogle Scholar indexed
A Novel Decoder Based on Parallel Genetic Algorithms for Linear Block Codes
Department of Industrial and Production Engineering, Moulay Ismail University, National High School of Arts and Trades, Meknès, Morocco
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
Department of Industrial and Production Engineering, Moulay Ismail University, National High School of Arts and Trades, Meknès, Morocco
- 1 Department of Industrial and Production Engineering, Moulay Ismail University, National High School of Arts and Trades, Meknès, Morocco
- 2 Department of Communication Networks, National High School of Comptuer Science and System Analysis, Rabat, Morocco
- 3 Department of Industrial and Production Engineering, Moulay Ismail University, National High School of Arts and Trades, Meknès, Morocco
- 4 Department of Industrial and Production Engineering, Moulay Ismail University, National High School of Arts and Trades, Meknès, Morocco
International Journal of Communications, Network and System Sciences·Volume 06 (2013)·Pages 66–76·Published 29 January 2013·DOI10.4236/ijcns.2013.61008
Copy link · social · email
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 ﹣ 5 with only 4 processors.
KeywordsChannel CodingLinear Block CodesMeta-HeuristicsParallel Genetic AlgorithmsParallel Decoding AlgorithmsTime ComplexityFlat Fading ChannelAWGN
- R. W. Hamming, “Error Detecting and Error Correcting Codes,” Bell System Technical Journal, Vol. 29, No. 2, 1950, pp. 47-160.
- C. E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal, Vol. 27, 1948, pp. 379-423, pp. 623-656.
- S. Roman, “Introduction to Coding and Information Theory,” Spring Verlag, New York, 1996.
- 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
- 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
- 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.
- 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
- 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
- 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.
- 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.
- 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.
- 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.