On the Computing of the Minimum Distance of Linear Block Codes by Heuristic Methods

作     者：Mohamed Askali Ahmed Azouaoui Said Nouh Mostafa Belkasmi 

作者机构：SIME LabNational School of Computer Science and Systems Analysis(ENSIAS)Mohammed V-Souisi UniversityRabatMorocco 

出 版 物：《International Journal of Communications, Network and System Sciences》 (通讯、网络与系统学国际期刊（英文）)

年 卷 期：2012年第5卷第11期

页      面：774-784页

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

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

摘      要：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.