Efficient Information Set Decoding Based on Genetic Algorithms

Ahmed Azouaoui, Idriss Chana, Mostafa Belkasmi

SIME Lab., ENSIAS, Mohammed V-Souissi University, Rabat, Morocco.

DOI: 10.4236/ijcns.2012.57052                

Abstract

In this paper, we describe a hard-decision decoding technique based on Genetic Algorithms (HDGA), which is applicable to the general case of error correcting codes where the only known structure is given by the generating matrix G. Then we present a new soft-decision decoding based on HDGA and the Chase algorithm (SDGA). The performance of some binary and non-binary Linear Block Codes are given for HDGA and SDGA over Gaussian and Rayleigh channels. The performances show that the HDGA decoder has the same performances as the Berlekamp-Massey Algorithm (BMA) in various transmission channels. On the other hand, the performances of SDGA are equivalent to soft-decision decoding using Chase algorithm and BMA (Chase-BMA). The complexity of decoders proposed is also discussed and compared to those of other decoders.

Keywords

Genetic Algorithms (GA); Error Correcting Codes; RS Codes; Information Set Decoding; Chase Algorithm

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	G. C. Clarck and J. B. Cain, “Error-Correction Coding for Digital Communications,” Plenum, New York, 1981.
[2]	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, Syracuse University, Syracuse, 1991.
[3]	A. C. M. Cardoso and D. S. Arantes, “Genetic Decoding of Linear Block Codes,” Congress on Evolutionary Computation, Washington DC, 1999.
[4]	I. Shakeel, “GA-Based Soft-Decision Decoding of Block Codes,” IEEE 17th International Conference on Telecommunications, Doha, 4-7 April 2010, pp. 13-17.
[5]	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
[6]	L. Hebbes, R. Malyan and A. Lenaghan, “Genetic Algorithms for Turbo Codes,” IEEE EUROCON, Belgrade, 21-24 November 2005.
[7]	N. Durand, J.-M Alliot and B. Bartolomé, “Turbo Codes Optimization Using Genetic Algorithms,” IEEE Congress on Evolutionary Computation, Vol. 2, 1999, pp. 119-125.
[8]	P. Praveenkumar, R. Amirtharajan, K. Thenmozhi and J. B. B. Rayappan, “Regulated OFDM-Role of ECC and ANN: A Review,” Journal of Applied Sciences, Vol. 12, 2012, pp. 301-314. doi:10.3923/jas.2012.301.314
[9]	R. Sujan, et al., “Adaptive ‘soft’ Sliding Block Decoding of Convolutional Code Using the Artificial Neural Network,” Transactions on Emerging Telecommunications Technologies, 2012.
[10]	J. W. H. Kao, S. M. Berber and A. Bigdeli, “A General Rate K/N Convolutional Decoder Based on Neural Networks with Stopping Criterion,” Advances in Artificial Intelligence, Vol. 2009, 2009, Article ID: 356120. doi:10.1155/2009/356120
[11]	J. Orth and S. Houghten, “Optimizing the Salmon Algorithm for the Construction of DNA Error-Correcting Codes,” IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, Paris, 11-15 April 2011, pp. 1-7.
[12]	A. Azouaoui, M. Askali and M. Belkasmi, “A Genetic Algorithm to Search of Good Double-Circulant Codes,” International Conference on Multimedia Computing and Systems (ICMCS), Ouarzazate, 7-9 April 2011, pp. 1-5.
[13]	A. Azouaoui, M. Belkasmi and A. Farchane, “Efficient Dual Domain Decoding of Linear Block Codes Using Genetic Algorithms,” Journal of Electrical and Computer Engineering, Vol. 2012, 2012, Article ID: 503834. doi:10.1155/2012/503834
[14]	A. Azouaoui and Dr. M. Belkasmi, “A Soft Decoding of Linear Block Codes by Genetic Algorithms,” International Conference on Intelligent Computational Systems (ICICS’2012), Dubai, 7-8 January 2012.
[15]	D. Chase, “A Class of Algorithms for Decoding Block Codes with Channel Measurement,” IEEE Transactions on Information Theory, Vol. 18, 1972, pp. 170-181. doi:10.1109/TIT.1972.1054746