Mathematics Research Institute


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

F. Javier Lobillo (Universidad de Granada)

Fecha: 05/05/2020 16:00
Lugar: Webex (número de reunión 844 055 777)


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 opens the possibility to use a permutation representation in metaheuristics to find the minimum distance of an arbitrary linear code, as an alternative to the classic discrete representation. The proposed model is polynomial time-dependent with respect to the dimension of the code and the size of the base finite field. It can be concluded from our experiments that usual limitations of discrete representation, such as high selective pressure, are palliated by means of the new representation. Our approach is able to find true minimum distances of general linear codes of medium size, and it is the first work, as far as we know, to address the problem for codes over finite fields with more than two elements using metaheuristics. Comparison with the existing methods in the literature suggests that our proposal is accurate, efficient and able to outperform previous approaches for BCH and EQR binary codes. As a by-product, we have been able to find some inaccuracies in the list of best known linear codes over the field with eight elements in the Magma Computational Algebra System.

El seminario tendrá lugar en Webex:
Número de reunión: 844 055 777

Para participar y recibir la contraseña de la reunión se necesita registro: