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

Affiliation(s)

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

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

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.

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.

Cite this paper

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.

M. Askali, A. Azouaoui, S. Nouh and M. Belkasmi, "On the Computing of the Minimum Distance of Linear Block Codes by Heuristic Methods,"

References

[1] H. Chen, N. S. Flann and D. W. Watson, “Parallel Genetic Simulated Annealing: A Massively Parallel SIMD Algorithm,” IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 2, 1998, pp. 126-136. doi:10.1109/71.663870

[2] C. Cotta, E. Alba and J. M. Troya, “Utilising Dynastically Optimal Forma Recombination in Hybrid Genetic Algorithms,” In: A. Eiben, T. BAack, M. Schoenauer and H. Schwefel, Eds., Parallel Problem Solving from Nature, Springer-Verlag, Berlin, 1998, pp. 305-314.

[3] J. M. Daida, S. J. Ross and B. C. Hannan, “Biological Symbiosis as a Metaphor for Computational Hybridization,” In: L. Eshelman, Ed., Proceedings of the 6th International Conference on Genetic Algorithms, Pittsburgh, 15-19 July 1995, pp. 328-335.

[4] K. Dontas and K. De Jong, “Discovery of Maximal Distance Codes Using Genetic Algorithms,” Proceedings of the 2nd International IEEE Conference on Tools for Artificial Intelligence, IEEE Computer Society Press, Los Alamitos, 1990, pp. 905-811.

[5] M. Askali, S. Nouh and M. Belkasmi, “An Efficient Method to Find the Minimum Distance of Linear Block Codes,” IEEE International Conference on Multimedia Computing and Systems Proceeding, Tangier, 10-12 May 2012, pp. 185-188.

[6] D. Coppersmith and G. Seroussi, “On the Minimum Distance of Some Quadratic Residue Codes,” IEEE Transactions on Information Theory, Vol. 30, No. 2, 1984, pp. 407-411. doi:10.1109/TIT.1984.1056861

[7] N. Boston, “The Minimum Distance of the [137, 69] Quadratic Residue Code,” IEEE Transactions on Information Theory, Vol. 45, No. 1, 1999, p. 282. doi:10.1109/18.746813

[8] D. Kuhlmann, “The Minimum Distance of the [83, 42] Quadratic Residue Code,” IEEE Transactions on Information Theory, Vol. 45, No. 1, 1999, p. 282. doi:10.1109/18.746814

[9] Markus Grassl, “On the Minimum Distance of Some Quadratic Residue Codes,” Proceedings IEEE International Symposium on Information Theory, Sorrento, 25-30 June 2000.

[10] W.-K. Su, P.-Y. Shih, T.-C. Lin and T.-K. Truong, “On the Minimum Weights of Binary Extended Quadratic Residue Codes,” Proceedings of the 11th International Conference on Advanced Communication Technology, Vol. 3, IEEE Press, Piscataway, 2009.

[11] A. Azouaoui, M. Askali and M. Belkasmi, “A Genetic Algorithm to Search of Good Double-Circulant Codes,” IEEE International Conference on Multimedia Computing and Systems Proceeding, Ouarzazate, 7-9 April 2011, pp. 829-833.

[12] J. Wallis and K. Houghten, “A Comparative Study of Search Techniques Applied to the Minumum Distance of BCH Codes,” Conference on Artificial Intelligence and Soft Computing, Banff, 17-19 July 2002.

[13] S. Nouh and M. Belkasmi, “Genetic Algorithms for Finding the Weight Enumerator of Binary Linear Block Codes,” International Journal of Applied Research on Information Technology and Computing, Vol. 2, No. 3, 2011, pp. 557-568.

[14] R. Garello, P. Pierleoni and S. Benedetto, “Computing the Free Distance of Turbo Codes and Serially Concatenated Codes With Interleavers: Algorithms and Applications,” IEEE Journal on Selected Areas in Communications, Vol. 19, No. 5, 2001, pp. 800-812. doi:10.1109/49.924864

[15] C. Berrou, S. Vaton, M. Jezequel and C. Douillard, “Computing the Minimum Distance of Linear Codes by the Error Impulse Method,” Proceedings of IEEE Globecom, Taipei, 17-21 November 2002, pp. 10-14.

[16] R. Garello and A. Vila, “The All-Zero Iterative Decoding Algorithm for Turbo Code Minimum Distance Computation,” IEEE International Conference on Communications, Paris, 20-24 June 2004, pp. 361-364.

[17] S. Crozier, P. Guinand and A. Hunt, “Computing the Minimum Distance of Turbo-Codes Using Iterative Decoding Techniques,” Proceedings of 22nd Biennial Symposium on Communications, Kingston, Ontario, 31 May-3 June 2004, pp. 306-308.

[18] 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, No. 4, 2012, pp. 301-314. doi:10.3923/jas.2012.301.314

[19] R. Sujan, et al., “Adaptive ‘SOFT’ Sliding Block Decoding of Convolutional Code Using the Artificial Neural Net-Work,” Transactions on Emerging Telecommunications Technologies, Vol. 23, No. 7, 2012, pp. 672-677. doi:10.1002/ett.2523

[20] 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

[21] K. Dontas and K. Dejong, “Discovery of Maximal Distance Codes Using Genetic Algorithms,” Proceedings of the 2nd International IEEE Conference on Tools for Artificial Intelligence, Herndon, 6-9 November 1990.

[22] D. Coley, “An Introduction to Genetic Algorithms for Scientists and Engineers,” World Scientific, Singapore City, 1999.

[23] X. Y. Hu, M. P. C. Fossorier and E. Eleftheriou, “On the Computation of the Minimum Distance of Low-Density Parity-Check Codes,” IEEE International Conference on Communications, Paris, 20-24 June 2004, pp. 767-771.

[24] R. Garello and A. Vila, “The All-Zero Iterative Decoding Algorithm for Turbo Code Minimum Distance Computation,” IEEE International Conference on Communications, Paris, 20-24 June 2004, pp. 361-364.

[25] M. Zhang and F. Ma, “Simulated Annealing Approach to the Minimum Distance of Error-Correcting Codes,” International Journal of Electronics, Vol. 76, No. 3, 1994, pp. 377-384.

[26] C. Tjhai, M. Tomlinson, R. Horan, M. Ahmed and M. Ambroze, “Some Results on the Weight Distributions of the Binary Double Circulant Codes Based on Primes,” Proceedings of 10th IEEE International Conference on Communication Systems, Singapore City, 30 October-1 November 2006.

[27] M. Grassl, IAKS, “Fakultat fur Informatik,” Universitat Karlsruhe, Karlsruhe, 2006.

[28] F. J. McWilliams and N. J. A. Saloane, “The Theory of Error-Correcting Codes,” North Holland, Amsterdam, 1977.

[29] V. Pless, et al., “Handbook of Coding Theory,” North Holland, Amsterdam, 1998.

[30] I. Krasikov and S. Litsyn, “An Improved Upper Bound on the Minimum Distance of Doubly-Even Self-Dual Codes,” IEEE-IT, Vol. 46, No. 1, 2000, pp. 274-278. doi:10.1109/18.817527

[1] H. Chen, N. S. Flann and D. W. Watson, “Parallel Genetic Simulated Annealing: A Massively Parallel SIMD Algorithm,” IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 2, 1998, pp. 126-136. doi:10.1109/71.663870

[2] C. Cotta, E. Alba and J. M. Troya, “Utilising Dynastically Optimal Forma Recombination in Hybrid Genetic Algorithms,” In: A. Eiben, T. BAack, M. Schoenauer and H. Schwefel, Eds., Parallel Problem Solving from Nature, Springer-Verlag, Berlin, 1998, pp. 305-314.

[3] J. M. Daida, S. J. Ross and B. C. Hannan, “Biological Symbiosis as a Metaphor for Computational Hybridization,” In: L. Eshelman, Ed., Proceedings of the 6th International Conference on Genetic Algorithms, Pittsburgh, 15-19 July 1995, pp. 328-335.

[4] K. Dontas and K. De Jong, “Discovery of Maximal Distance Codes Using Genetic Algorithms,” Proceedings of the 2nd International IEEE Conference on Tools for Artificial Intelligence, IEEE Computer Society Press, Los Alamitos, 1990, pp. 905-811.

[5] M. Askali, S. Nouh and M. Belkasmi, “An Efficient Method to Find the Minimum Distance of Linear Block Codes,” IEEE International Conference on Multimedia Computing and Systems Proceeding, Tangier, 10-12 May 2012, pp. 185-188.

[6] D. Coppersmith and G. Seroussi, “On the Minimum Distance of Some Quadratic Residue Codes,” IEEE Transactions on Information Theory, Vol. 30, No. 2, 1984, pp. 407-411. doi:10.1109/TIT.1984.1056861

[7] N. Boston, “The Minimum Distance of the [137, 69] Quadratic Residue Code,” IEEE Transactions on Information Theory, Vol. 45, No. 1, 1999, p. 282. doi:10.1109/18.746813

[8] D. Kuhlmann, “The Minimum Distance of the [83, 42] Quadratic Residue Code,” IEEE Transactions on Information Theory, Vol. 45, No. 1, 1999, p. 282. doi:10.1109/18.746814

[9] Markus Grassl, “On the Minimum Distance of Some Quadratic Residue Codes,” Proceedings IEEE International Symposium on Information Theory, Sorrento, 25-30 June 2000.

[10] W.-K. Su, P.-Y. Shih, T.-C. Lin and T.-K. Truong, “On the Minimum Weights of Binary Extended Quadratic Residue Codes,” Proceedings of the 11th International Conference on Advanced Communication Technology, Vol. 3, IEEE Press, Piscataway, 2009.

[11] A. Azouaoui, M. Askali and M. Belkasmi, “A Genetic Algorithm to Search of Good Double-Circulant Codes,” IEEE International Conference on Multimedia Computing and Systems Proceeding, Ouarzazate, 7-9 April 2011, pp. 829-833.

[12] J. Wallis and K. Houghten, “A Comparative Study of Search Techniques Applied to the Minumum Distance of BCH Codes,” Conference on Artificial Intelligence and Soft Computing, Banff, 17-19 July 2002.

[13] S. Nouh and M. Belkasmi, “Genetic Algorithms for Finding the Weight Enumerator of Binary Linear Block Codes,” International Journal of Applied Research on Information Technology and Computing, Vol. 2, No. 3, 2011, pp. 557-568.

[14] R. Garello, P. Pierleoni and S. Benedetto, “Computing the Free Distance of Turbo Codes and Serially Concatenated Codes With Interleavers: Algorithms and Applications,” IEEE Journal on Selected Areas in Communications, Vol. 19, No. 5, 2001, pp. 800-812. doi:10.1109/49.924864

[15] C. Berrou, S. Vaton, M. Jezequel and C. Douillard, “Computing the Minimum Distance of Linear Codes by the Error Impulse Method,” Proceedings of IEEE Globecom, Taipei, 17-21 November 2002, pp. 10-14.

[16] R. Garello and A. Vila, “The All-Zero Iterative Decoding Algorithm for Turbo Code Minimum Distance Computation,” IEEE International Conference on Communications, Paris, 20-24 June 2004, pp. 361-364.

[17] S. Crozier, P. Guinand and A. Hunt, “Computing the Minimum Distance of Turbo-Codes Using Iterative Decoding Techniques,” Proceedings of 22nd Biennial Symposium on Communications, Kingston, Ontario, 31 May-3 June 2004, pp. 306-308.

[18] 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, No. 4, 2012, pp. 301-314. doi:10.3923/jas.2012.301.314

[19] R. Sujan, et al., “Adaptive ‘SOFT’ Sliding Block Decoding of Convolutional Code Using the Artificial Neural Net-Work,” Transactions on Emerging Telecommunications Technologies, Vol. 23, No. 7, 2012, pp. 672-677. doi:10.1002/ett.2523

[20] 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

[21] K. Dontas and K. Dejong, “Discovery of Maximal Distance Codes Using Genetic Algorithms,” Proceedings of the 2nd International IEEE Conference on Tools for Artificial Intelligence, Herndon, 6-9 November 1990.

[22] D. Coley, “An Introduction to Genetic Algorithms for Scientists and Engineers,” World Scientific, Singapore City, 1999.

[23] X. Y. Hu, M. P. C. Fossorier and E. Eleftheriou, “On the Computation of the Minimum Distance of Low-Density Parity-Check Codes,” IEEE International Conference on Communications, Paris, 20-24 June 2004, pp. 767-771.

[24] R. Garello and A. Vila, “The All-Zero Iterative Decoding Algorithm for Turbo Code Minimum Distance Computation,” IEEE International Conference on Communications, Paris, 20-24 June 2004, pp. 361-364.

[25] M. Zhang and F. Ma, “Simulated Annealing Approach to the Minimum Distance of Error-Correcting Codes,” International Journal of Electronics, Vol. 76, No. 3, 1994, pp. 377-384.

[26] C. Tjhai, M. Tomlinson, R. Horan, M. Ahmed and M. Ambroze, “Some Results on the Weight Distributions of the Binary Double Circulant Codes Based on Primes,” Proceedings of 10th IEEE International Conference on Communication Systems, Singapore City, 30 October-1 November 2006.

[27] M. Grassl, IAKS, “Fakultat fur Informatik,” Universitat Karlsruhe, Karlsruhe, 2006.

[28] F. J. McWilliams and N. J. A. Saloane, “The Theory of Error-Correcting Codes,” North Holland, Amsterdam, 1977.

[29] V. Pless, et al., “Handbook of Coding Theory,” North Holland, Amsterdam, 1998.

[30] I. Krasikov and S. Litsyn, “An Improved Upper Bound on the Minimum Distance of Doubly-Even Self-Dual Codes,” IEEE-IT, Vol. 46, No. 1, 2000, pp. 274-278. doi:10.1109/18.817527