Author(s)

Mohamed Askali, Ahmed Azouaoui, Saïd Nouh, Mostafa Belkasmi

SIME Lab, National School of Computer Science and Systems Analysis (ENSIAS), Mohammed V-Souisi University, Rabat, Morocco.

The evaluation of the minimum distance of linear block codes remains an open problem in coding theory, and it is not easy to determine its true value by classical methods, for this reason the problem has been solved in the literature with heuristic techniques such as genetic algorithms and local search algorithms. In this paper we propose two approaches to attack the hardness of this problem. The first approach is based on genetic algorithms and it yield to good results comparing to another work based also on genetic algorithms. The second approach is based on a new randomized algorithm which we call "Multiple Impulse Method (MIM)", where the principle is to search codewords locally around the all-zero codeword perturbed by a minimum level of noise, anticipating that the resultant nearest nonzero codewords will most likely contain the minimum Hamming-weight codeword whose Hamming weight is equal to the minimum distance of the linear code.

Minimum Distance; Error Impulse Method; Heuristic Methods; Genetic Algorithms; NP-Hardness; Linear Error Correcting Codes; BCH Codes; QR Codes; Double Circulant Codes

M. Askali, A. Azouaoui, S. Nouh and M. Belkasmi, "On the Computing of the Minimum Distance of Linear Block Codes by Heuristic Methods," International Journal of Communications, Network and System Sciences, Vol. 5 No. 11, 2012, pp. 774-784. doi: 10.4236/ijcns.2012.511081.