Evolutionary strategies for the design of binary linear codes

DOI10.1007/978-3-031-30035-6_8arXiv2211.11551OpenAlexW4361798394MaRDI QIDQ6149095FDOQ6149095

Authors: Claude Carlet, Luca Mariot, Luca Manzoni, Stjepan Picek 

Publication date: 12 January 2024

Published in: Evolutionary Computation in Combinatorial Optimization (Search for Journal in Brave)

Abstract: The design of binary error-correcting codes is a challenging optimization problem with several applications in telecommunications and storage, which has also been addressed with metaheuristic techniques and evolutionary algorithms. Still, all these efforts 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. To that end, 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 evolved codes start to drop, with the extreme case of $(16,8,5)$ codes which all turn out to be equivalent to MAGMA's BKLC.

Full work available at URL: https://arxiv.org/abs/2211.11551

zbMATH Keywords

Boolean functionserror-correcting codesevolutionary strategiesalgebraic normal formvariation operators

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Combinatorial optimization (90C27)

Cites Work

• Reducibility among combinatorial problems
• Handbook of finite fields
• Fundamentals of Error-Correcting Codes
• Coding for Errors and Erasures in Random Network Coding
• Exploring semi-bent Boolean functions arising from cellular automata
• Boolean functions for cryptography and coding theory
• Evolutionary Computation in Combinatorial Optimization
• The design of (almost) disjunct matrices by evolutionary algorithms
• Expressing the minimum distance, weight distribution and covering radius of codes by means of the algebraic and numerical normal forms of their indicators

This page was built for publication: Evolutionary strategies for the design of binary linear codes

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