1. Complete title:
Evolutionary Strategies for the Design of Binary Linear Codes
---------------------
2. Authors' names, addresses, e-mails and phone numbers:
Claude Carlet
University of Bergen, Bergen, Norway and Université Paris 8, Département de mathématiques, 2 rue de la liberté, 93526 Saint-Denis, Cedex, France
claude.carlet@gmail.com
+33 630 389 528
Luca Mariot
Semantics, Cybersecurity and Services Group, University of Twente, Drienerlolaan 5, 7522 NB Enschede, The Netherlands
l.mariot@utwente.nl
+31 623 952 460
Luca Manzoni
Department of Mathematics and Geosciences, University of Trieste, Via Valerio 12/1, Trieste, Italy
lmanzoni@units.it
+39 040 558 2674
Stjepan Picek
Digital Security Group, Radboud University, PO Box 9010, Nijmegen, The Netherlands
stjepan.picek@ru.nl
+385 9822 6407
---------------------
3. Corresponding author
Luca Mariot
---------------------
4. Abstract
The design of binary error-correcting codes is a challenging
optimization problem with several applications in telecommunications
and storage, which has been addressed with metaheuristic techniques
such as evolutionary algorithms. Still, all these efforts are focused
on optimizing the minimum distance of unrestricted binary codes, i.e.,
with no constraints on their linearity, which is a desirable property
for efficient implementations. In this paper, we present an
Evolutionary Strategy (ES) algorithm that explores only the subset of
linear codes of a fixed length and dimension. We represent the
candidate solutions as binary matrices and devise variation operators
that preserve their ranks. Our experiments show that up to length
n=14, our ES always converges to an optimal solution with a full
success rate, and the evolved codes are all inequivalent to the
Best-Known Linear Code (BKLC) given by MAGMA. On the other hand, for
larger lengths, both the success rate of the ES as well as the
diversity of the codes start to drop, with the extreme case of
(16,8,5) codes which all turn out to be equivalent to MAGMA's BKLC.
---------------------
5. Relevant criteria
B, C, D, G
---------------------
6. Criteria statement
(B) Our results show that Evolutionary Strategies (ES) are able to
construct binary linear codes with optimal minimum distance, with full
success rate in almost all considered problem instances. The only
exception is the largest instance of length n=16, where anyway at
least one tested ES variant achieves a very high success rate
(92%). The optimality of the minimum distance is theoretically
guaranteed, since for the considered lengths and dimensions the
theoretical lower and upper bounds coincide. Other optimal linear
codes for the considered parameters have been constructed in the
literature: nowadays, the standard way to obtain them is through the
Best Known Linear Code (BKLC) provided by the MAGMA computer algebra
system. Most of these codes returned by MAGMA come from the
computational search effort published in 2006 in [1]. Since our ES
approach is able to obtain error correcting codes with the same
optimal distance for the considered problem instances, we think that
our work fully qualifies for the criterion (B).
(C) There exist several tables with the optimal minimum distances
achievable by binary codes, depending on their length and
dimension. In the last decade, the tables maintained by Grassl [2]
became the standard reference for this problem, since they constitute
the most comprehensive database for error-correcting codes publicly
available. Through this database, it is quite easy to check if a
particular code obtained by some construction meets the lower or upper
bounds known in the literature, and therefore to establish if the code
is optimal. Further, one can check for each combination of optimal
parameters what is the corresponding code construction provided by
MAGMA. In our work, we use the optimal minimum distance as a parameter
that defines the problem instance solved by ES. The values of the
optimal minimum distance were taken from the database [2], and in all
those cases the lower and upper bounds coincide. Since ES almost
always converge to an optimal solution, we can conclude that our
results are equal to the results that were placed in the database [2]
maintained by an expert of the field, and used as a reference by
researchers in that field. Thus, we deem our work to be completely
fitting for criterion (C).
(D) Researchers working in coding theory are always interested in
finding new constructions of optimal linear codes, even if previous
examples already exist. This is especially true if the new
construction yields codes that are inequivalent to previously known
ones. Inequivalence is defined in terms of code isomorphism, and can
be easily checked through the IsIsomorphic function in MAGMA. In our
work, we compared all codes evolved by our ES algorithm against the
Best Known Linear Code (BKLC) provided by MAGMA for the corresponding
parameters, and checked for isomorphism (see Table 3 in the paper for
a summary of the results). Interestingly, for three instances out of
the five considered ones, all codes generated by the simplest ES
variant are inequivalent to MAGMA's BKLC. For the fourth instance (15,
7, 5) the simplest ES variant is still able to find inequivalent codes
in 72% of the cases. Finally, for the largest instance (16, 8, 5), all
ES variants produce optimal codes that are equivalent to MAGMA's
BKLC. We believe this stark difference to be very interesting for the
coding theory community, since it might indicate that the (16, 8, 5)
instance is characterized by a single optimal code up to
isomorphism. So far, there have been no results in this direction, and
we think that for this reason our work qualifies also for criterion
(D), since this experimental findings are independent of the fact that
they were created through ES.
(G) Finding an optimal linear error correcting code is recognized to
be a hard combinatorial optimization problem. As a matter of fact,
except for very small instances where all possible codes of a given
length and dimension can be exhaustively generated and checked for the
optimality of their distance, in general one needs to resort either to
algebraic constructions or heuristic techniques. Algebraic
constructions can be considered as the state-of-the-art method for
this problem, since most of the optimal codes reported in the database
[2] have been generated in this way. However, the problem with
algebraic constructions is that they always yield the same classes of
codes, up to isomorphism. Indeed, finding optimal codes that are
inequivalent to the known ones in the literature can be regarded as a
very difficult problem. Before our work, heuristic techniques were
nowhere near to match algebraic cosntructions, not for the optimality
of the distance but rather on the linearity of the resulting codes. As
a matter of fact, our work is the first one to produce a heuristic
construction of binary codes that are linear, with a prescribed
dimension. Moreover, as we remarked above for criterion (D), our ES is
often able to find codes that are inequivalent to those obtained by
algebraic constructions in terms of isomorphism. Hence, we think that
our results qualify for criterion (G) as well.
---------------------
7. Full citation
Carlet C., Mariot L., Manzoni L., Picek S. (2023) Evolutionary
Strategies for the Design of Binary Linear Codes. In: Pérez Cáceres
L., Stutzle T. (eds.) Evolutionary Computation in Combinatorial
Optimization. EvoCOP 2023. Lecture Notes in Computer Science,
vol. 13987, pp. 114-129. Springer, Cham
@inproceedings{cmmp-evocop2023,
author = {Claude Carlet and
Luca Mariot and
Luca Manzoni and
Stjepan Picek},
editor = {Leslie P{\'{e}}rez C{\'{a}}ceres and
Thomas St{\"{u}}tzle},
title = {Evolutionary Strategies for the Design of Binary Linear Codes},
booktitle = {Evolutionary Computation in Combinatorial Optimization - 23rd European
Conference, EvoCOP 2023, Held as Part of EvoStar 2023, Brno, Czech
Republic, April 12-14, 2023, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {13987},
pages = {114--129},
publisher = {Springer},
year = {2023}
doi = {10.1007/978-3-031-30035-6\_8}
}
8. Prize statement
Any prize money, if any, is to be divided equally among the co-authors.
---------------------
9. Best statement
We believe that our work is the best entry for two reasons. The first
one concerns the techniques developed in the paper: as we mention in
its introduction, several works in the existing literature addressed
the design of binary error correcting codes via evolutionary
algorithms. However, none of them considered the linearity constraint
of the evolved codes, which is often very important for practical
applications, in order to achieve low-cost implementation using
feedback shift registers and similar devices. Our work is the first
one to propose an evolutionary algorithm (specifically ES) that
searches directly in the space of linear codes, using innovative
genetic operators which preserve the dimension of the linear mapping
encoded by an individual in the population. Thus, we think that this
part already represents a significant improvement over existing works
that construct error correcting codes with heuristic techniques. The
second reason concerns instead the obtained results: as we discussed
above in the criteria statements, ES turned out to yield many optimal
linear codes that are also new. The optimality of such codes can be
easily checked using the code tables in [2]. The "novelty" aspect of
these codes is that many of them are inequivalent to the best linear
codes known so far, as verified through MAGMA. Such inequivalent codes
could be in turn studied to see whether they yield new algebraic
constructions. The same interest applies also for the largest
instance, where all codes actually turned out to be equivalent to
MAGMA's BKLC: far from considering it a setback, we believe that these
results could be very useful to shed light on the mathematical
structure of the space of (16, 8, 5) linear codes, since they seem to
indicate that there is only a single optimal code up to
isomorphism. All in all, we think that the results presented in this
paper indicate that ES (and evolutionary algorithms in general)
represent an interesting tool to perform experimental mathematics.
---------------------
10. Methods used
ES (Evolutionary Strategies)
---------------------
11. Publication date
31 March 2023
---------------------
References
[1] Grassl, Markus. Searching for linear codes with large minimum distance. Discovering Mathematics with Magma: Reducing the Abstract to the Concrete. Springer Berlin Heidelberg, 2006.
[2] Grassl, Markus. Code Tables: Bounds on the parameters of various types of codes. URL: http://www.codetables.de/