Evolutionary Strategies for the Design of Binary Linear Codes

Claude Carlet; Luca Mariot; Luca Manzoni; Stjepan Picek

doi:10.1007/978-3-031-30035-6_8

Evolutionary Strategies for the Design of Binary Linear Codes

Claude Carlet, Luca Mariot^*, Luca Manzoni, Stjepan Picek

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

80 Downloads (Pure)

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.

Original language	English
Title of host publication	Evolutionary Computation in Combinatorial Optimization - 23rd European Conference, EvoCOP 2023, Held as Part of EvoStar 2023, Proceedings
Editors	Leslie Pérez Cáceres, Thomas Stützle
Publisher	Springer
Pages	114-129
Number of pages	16
ISBN (Print)	9783031300349
DOIs	https://doi.org/10.1007/978-3-031-30035-6_8
Publication status	Published - 31 Mar 2023
Event	23rd European Conference on Evolutionary Computation in Combinatorial Optimisation, EvoCOP 2023 - Brno, Czech Republic Duration: 12 Apr 2023 → 14 Apr 2023 Conference number: 23

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13987 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd European Conference on Evolutionary Computation in Combinatorial Optimisation, EvoCOP 2023
Abbreviated title	EvoCOP 2023
Country/Territory	Czech Republic
City	Brno
Period	12/04/23 → 14/04/23
Other	Held as part of EvoStar 2023

Keywords

2024 OA procedure
Boolean functions
Error-correcting codes
Evolutionary strategies
Variation operators
Algebraic normal form

Access to Document

10.1007/978-3-031-30035-6_8

978-3-031-30035-6_8Final published version, 1.13 MBLicence: Taverne

Cite this

Carlet, C., Mariot, L., Manzoni, L., & Picek, S. (2023). Evolutionary Strategies for the Design of Binary Linear Codes. In L. Pérez Cáceres, & T. Stützle (Eds.), Evolutionary Computation in Combinatorial Optimization - 23rd European Conference, EvoCOP 2023, Held as Part of EvoStar 2023, Proceedings (pp. 114-129). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13987 LNCS). Springer. https://doi.org/10.1007/978-3-031-30035-6_8

Carlet, Claude ; Mariot, Luca ; Manzoni, Luca et al. / Evolutionary Strategies for the Design of Binary Linear Codes. Evolutionary Computation in Combinatorial Optimization - 23rd European Conference, EvoCOP 2023, Held as Part of EvoStar 2023, Proceedings. editor / Leslie Pérez Cáceres ; Thomas Stützle. Springer, 2023. pp. 114-129 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f84f5b642a8e470ca5e2b8f2a95f96fd,

title = "Evolutionary Strategies for the Design of Binary Linear Codes",

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{\textquoteright}s BKLC.",

keywords = "2024 OA procedure, Boolean functions, Error-correcting codes, Evolutionary strategies, Variation operators, Algebraic normal form",

author = "Claude Carlet and Luca Mariot and Luca Manzoni and Stjepan Picek",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 23rd European Conference on Evolutionary Computation in Combinatorial Optimisation, EvoCOP 2023, EvoCOP 2023 ; Conference date: 12-04-2023 Through 14-04-2023",

year = "2023",

month = mar,

day = "31",

doi = "10.1007/978-3-031-30035-6_8",

language = "English",

isbn = "9783031300349",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "114--129",

editor = "{P{\'e}rez C{\'a}ceres}, Leslie and Thomas St{\"u}tzle",

booktitle = "Evolutionary Computation in Combinatorial Optimization - 23rd European Conference, EvoCOP 2023, Held as Part of EvoStar 2023, Proceedings",

address = "Germany",

}

Carlet, C, Mariot, L, Manzoni, L & Picek, S 2023, Evolutionary Strategies for the Design of Binary Linear Codes. in L Pérez Cáceres & T Stützle (eds), Evolutionary Computation in Combinatorial Optimization - 23rd European Conference, EvoCOP 2023, Held as Part of EvoStar 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13987 LNCS, Springer, pp. 114-129, 23rd European Conference on Evolutionary Computation in Combinatorial Optimisation, EvoCOP 2023, Brno, Czech Republic, 12/04/23. https://doi.org/10.1007/978-3-031-30035-6_8

Evolutionary Strategies for the Design of Binary Linear Codes. / Carlet, Claude; Mariot, Luca; Manzoni, Luca et al.
Evolutionary Computation in Combinatorial Optimization - 23rd European Conference, EvoCOP 2023, Held as Part of EvoStar 2023, Proceedings. ed. / Leslie Pérez Cáceres; Thomas Stützle. Springer, 2023. p. 114-129 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13987 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Evolutionary Strategies for the Design of Binary Linear Codes

AU - Carlet, Claude

AU - Mariot, Luca

AU - Manzoni, Luca

AU - Picek, Stjepan

N1 - Conference code: 23

PY - 2023/3/31

Y1 - 2023/3/31

N2 - 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.

AB - 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.

KW - 2024 OA procedure

KW - Boolean functions

KW - Error-correcting codes

KW - Evolutionary strategies

KW - Variation operators

KW - Algebraic normal form

UR - http://www.scopus.com/inward/record.url?scp=85152555687&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-30035-6_8

DO - 10.1007/978-3-031-30035-6_8

M3 - Conference contribution

AN - SCOPUS:85152555687

SN - 9783031300349

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 114

EP - 129

BT - Evolutionary Computation in Combinatorial Optimization - 23rd European Conference, EvoCOP 2023, Held as Part of EvoStar 2023, Proceedings

A2 - Pérez Cáceres, Leslie

A2 - Stützle, Thomas

PB - Springer

T2 - 23rd European Conference on Evolutionary Computation in Combinatorial Optimisation, EvoCOP 2023

Y2 - 12 April 2023 through 14 April 2023

ER -

Carlet C, Mariot L, Manzoni L, Picek S. Evolutionary Strategies for the Design of Binary Linear Codes. In Pérez Cáceres L, Stützle T, editors, Evolutionary Computation in Combinatorial Optimization - 23rd European Conference, EvoCOP 2023, Held as Part of EvoStar 2023, Proceedings. Springer. 2023. p. 114-129. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-30035-6_8

Evolutionary Strategies for the Design of Binary Linear Codes

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Evolutionary Strategies for the Design of Binary Linear Codes

Cite this