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

• 作者: Ahmed Azouaoui Mohamed Askali Mostafa Belkasmi Sa?d Nouh
• 来源期刊: 通讯、网络与系统学国际期刊(英文)
• 学科: 数学
• 关键词: Minimum Distance ERROR Impulse Method Heuristic Methods Genetic Algorithms NP-HARDNESS Linear ERROR CORRECTING CODES BCH CODES QR CODES Double CIRCULANT CODES
• 年，卷（期）: 2012,（11）
• 页码范围: 774-784
• 页数: 11页
• 分类号: O1

摘要

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.