Approaching the Minimum Distance Problem by Algebraic Swarm-Based Optimizations

Year 2021, , 129 - 134, 30.06.2021

Serap Şahinkaya , Deniz Üstün

https://doi.org/10.47000/tjmcs.825565

Abstract

Finding the minimum distance of linear codes is one of the main problems in coding theory. The importance of the minimum distance comes from its error-correcting and error-detecting capability of the handled codes.
It was proven that this problem is an NP-hard that is the solution of this problem can be guessed and verified in polynomial time but no particular rule is followed to make the guess and some meta-heuristic approaches in the literature have been used to solve this problem.
In this paper, swarm-based optimization techniques, bat and firefly, are applied to the minimum distance problem by integrating the algebraic operator to the handled algorithms.

Keywords

Minimum distance, minimum-weight codeword, BCH codes, optimization, heuristic, bat algorithm, firefly algorithm

References

• [1] Ajitha Shenoy, K.B., Biswas, S., Kurur, P.P., Efficacy of the metropolis algorithm for the minimum-weight codeword problem using codeword and generator search spaces, IEEE Trans Evolut Comput., 24(4)(2020).
• [2] Arora, S., Singh, S., A conceptual comparison of firefly algorithm, bat algorithm and cuckoo search, 2013 International Conference on Control, Computing, Communication and Materials (ICCCCM), Allahabad, (2013), 1–4.
• [3] Augot, D., Charpin, P., Sendrier, N., Studying the locator polynomial of minimum weight codewords of BCH codes, IEEE Trans. Info. Theory, 38(1992), 960–973.
• [4] Bland, J.A., Local search optimisation applied to the minimum distance problem, Adv. Eng. Informat., 21(2007), 391–397.
• [5] Bouzkraoui, H., Azouaoui, A., Hadi, Y., New ant colony optimization for searching the minimum distance for linear codes, International Conference on Advanced Communication Technologies and Networking, (2018). doi: 10.1109/COMMNET.2018.8360246
• [6] Gomez-Torrecillas, J., Lobillo, F.J., Navarro, G., Minimum distance computation of linear codes via genetic algorithms with permutation encoding, ACM Communications in Computer Algebra, 52(3)(2018), 71–74.
• [7] Cuellar, M.P., Gomez-Torrecillas, J., Lobillo, F.J., Navarro, G., Genetic algorithms with permutation-based representation for computing the distance of linear codes, arXiv:2002.12330.
• [8] Hogben, L., Handbook of Linear Algebra. Boca Raton, FL, USA: Champman and Hall, 2007.
• [9] MacWilliams, F.J., Sloane, N.J.A., The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1993.
• [10] Ling, S., Xing, C., Coding Theory: A First Course, Cambridge University Press, 2004.
• [11] Santucci, V., Baioletti, M., Milani, A., Algebraic differential evolution algorithm for the permutation flowshop scheduling problem with total flowtime criterion, in IEEE Transactions on Evolutionary Computation, 20(5)(2016), 682–694.
• [12] Shannon, C.E., A mathematical theory of communication, Bell System Technical Journal, 27(1948), 379–423.
• [13] Wolpert, D.H., Macready, W.G, No free lunch theorems for optimization. IEEE Trans Evolut Comput, 1(1997), 67–82.
• [14] Vardy, A., The intractability of computing the minimum distance of a code, IEEE Transactions on Information Theory, 43(6)(1997), 1757–1766.
• [15] Yang, X.S., A New Metaheuristic Bat-Inspired Algorithm, Nature inspired cooperative strategies for optimization, Studies in Computational Intelligence, 43(284), Springer, Berlin, Heidelberg, 2010.