TITLE:
On the Computing of the Minimum Distance of Linear Block Codes by Heuristic Methods
AUTHORS:
Mohamed Askali, Ahmed Azouaoui, Saïd Nouh, Mostafa Belkasmi
KEYWORDS:
Minimum Distance; Error Impulse Method; Heuristic Methods; Genetic Algorithms; NP-Hardness; Linear Error Correcting Codes; BCH Codes; QR Codes; Double Circulant Codes
JOURNAL NAME:
International Journal of Communications, Network and System Sciences,
Vol.5 No.11,
November
26,
2012
ABSTRACT: 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.