Genetic algorithms with permutation-based representation for computing the distance of linear codes

arXiv2002.12330MaRDI QIDQ6335722

Author name not available (Why is that?)

Publication date: 27 February 2020

Abstract: Finding the minimum distance of linear codes is an NP-hard problem. Traditionally, this computation has been addressed by means of the design of algorithms that find, by a clever exhaustive search, a linear combination of some generating matrix rows that provides a codeword with minimum weight. Therefore, as the dimension of the code or the size of the underlying finite field increase, so it does exponentially the run time. In this work, we prove that, given a generating matrix, there exists a column permutation which leads to a reduced row echelon form containing a row whose weight is the code distance. This result enables the use of permutations as representation scheme, in contrast to the usual discrete representation, which makes the search of the optimum polynomial time dependent from the base field. In particular, we have implemented genetic and CHC algorithms using this representation as a proof of concept. Experimental results have been carried out employing codes over fields with two and eight elements, which suggests that evolutionary algorithms with our proposed permutation encoding are competitive with regard to existing methods in the literature. As a by-product, we have found and amended some inaccuracies in the MAGMA Computational Algebra System concerning the stored distances of some linear codes.

This page was built for publication: Genetic algorithms with permutation-based representation for computing the distance of linear codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6335722)