Source-linked AI summary
Constraint-Preserving Genetic Algorithms for Embedding Linear Codes into Self-Orthogonal Codes
Haeun Lim, Junmin An, Jon-Lark Kim
TL;DR
The paper addresses the difficulty of searching the large space of self-orthogonal embeddings for optimal codes. It develops a constraint-preserving genetic algorithm and reports 66 new optimal codes, plus 135 further codes reaching the best minimum distance found so far.
Problem
Searching all self-orthogonal embeddings for optimal codes is generally infeasible, especially for codes with large dimensions.
Method
The paper encodes embeddings as sequences of orthogonal-group generators so genetic operations preserve self-orthogonality while fitness prioritizes minimum distance and minimum-weight codewords.
Results
66 new optimal self-orthogonal codes meet the upper bound, while 135 further codes attain the best minimum distance obtained so far.
Takeaways & Limitations
The constraint-preserving representation yields valid embeddings throughout the genetic search and supports construction of new optimal and best-known self-orthogonal codes.
Takeaways & Limitations
The bound-based optimality conclusion depends on the residual-parameter condition: if no even code exists with those parameters, equality with the bound cannot hold.
Abstract
from arXiv · showhide
In this paper, we aim to construct binary optimal self-orthogonal codes using shortest self-orthogonal embedding methods. For this purpose, we design a heuristic framework based on a genetic algorithm. We explore the search space of shortest self-orthogonal embeddings using a fitness function based on the minimum distance and the number of minimum-weight codewords. We construct \emph{constraint-preserving} crossover and mutation operations so that every chromosome yields a valid self-orthogonal embedding, while high-fitness structural features, such as favorable subsequences of orthogonal generators, are propagated across generations. We also analyze the time and storage complexity of the algorithm, and validate our design through an ablation study on guided crossover and a comparison with random search under an equal time budget. Using this method, we obtain $66$ new binary optimal self-orthogonal codes that meet the upper bound, together with $135$ further self-orthogonal codes attaining the best minimum distance found so far.
1 Introduction
Self-orthogonal codes are important in coding theory, but finding optimal constructions is difficult. The paper addresses the intractable search for shortest self-orthogonal embeddings with a constraint-preserving genetic algorithm.
- Self-orthogonal codes support important coding-theoretic constructions, including unimodular lattices and quantum error-correcting codes.
- Embedding methods construct self-orthogonal codes by adding columns to a generator matrix while seeking the minimum number of appended columns.
- Large-dimensional embedding spaces are nearly impossible to search exhaustively, motivating a heuristic genetic algorithm.
- The proposed algorithm encodes chromosomes with orthogonal-group generators so crossover and mutation preserve valid self-orthogonal embeddings.
- 66 new optimal self-orthogonal codes and 135 further codes attaining the best minimum distance found so far were obtained over F2.
2 Preliminaries
The preliminaries define binary linear and self-orthogonal codes, minimum distance, residual codes, and the genetic-algorithm components used later. Genetic operators must preserve feasibility when chromosomes encode structurally constrained solutions.
- Coding theory: A binary linear [n, k] code is a k-dimensional subspace of F2^n represented by a k × n generator matrix.
- Coding theory: A code is self-orthogonal when C ⊆ C⊥, equivalently when its generator matrix satisfies GGT = O.
- Coding theory: For linear codes, minimum distance equals the smallest Hamming weight among nonzero codewords.
- Coding theory: A residual code is formed by puncturing all coordinates where a minimum-weight codeword has ones, producing length n − d and dimension k − 1.
- Genetic algorithms: Genetic algorithms evolve chromosome populations through fitness-based selection, crossover, mutation, and often elitism to search large optimization spaces.
- Genetic algorithms: When chromosomes represent constrained solutions, crossover and mutation must be designed to preserve structural feasibility.
3 Problem Formulation and a Constraint-Preserving Genetic Algorithm
The paper formulates shortest self-orthogonal embedding as a constrained search over orthogonal transformations and uses a genetic algorithm whose representations and operators remain feasible. Its fitness prioritizes minimum distance, then minimum-weight codeword count and chromosome length, while complexity analysis motivates avoiding exhaustive enumeration.
- 3.1 Shortest self-orthogonal embeddings and the feasibility condition: A self-orthogonal embedding appends m columns to an [n, k] binary code, with the shortest length determined by n + k − ℓ or n + k − ℓ + 1.Here ℓ is the dimension of the code hull; the first expression applies to odd-like codes and the second to even codes.
- 3.1 Shortest self-orthogonal embeddings and the feasibility condition: Duplicating the generator matrix as [G(C) | G(C)] always yields a self-orthogonal embedding, but shortest embeddings seek the minimum number of appended columns.The construction establishes existence, while the hull-based theorem characterizes the shortest achievable length.
- 3.1 Shortest self-orthogonal embeddings and the feasibility condition: Every shortest embedding can be generated by varying the appended block B, subject over F2 to the feasibility condition B B^T = A A^T.The generator matrix has the form [G(C) | A], and the condition follows from self-orthogonality.
- 3.2 A constraint-preserving genetic algorithm: For m ≥ 5, orthogonal transformations are generated using permutation matrices and weight-4 transvections, enabling systematic traversal of shortest embeddings.The paper uses sequences of weight-4 vectors to represent products of transvections in the orthogonal group.
- 3.2 A constraint-preserving genetic algorithm: Chromosomes are finite sequences of weight-4 vectors, and each chromosome induces an orthogonal matrix Dχ, so genetic candidates remain valid shortest embeddings.The induced matrix is used to transform the appended block and define the candidate code.
- 3.2 A constraint-preserving genetic algorithm: Fitness is lexicographic: maximize minimum distance, minimize the number of minimum-weight codewords, then minimize chromosome length.The final component only breaks ties and discourages unnecessarily long representations.
- 3.2 A constraint-preserving genetic algorithm: Random crossover exchanges chromosome subsequences at independently selected cut points, while the resulting sequences remain composed of valid transvection generators.The paper introduces two crossover types and uses generator-based representations to preserve structural feasibility.
- 3.3 Complexity: Fitness evaluation dominates runtime; over P candidates, G generations, and up to D local-search steps, the algorithm performs a bounded number of evaluations rather than enumerating the orthogonal group.Exhaustive search scales as 2^Θ(m^2), whereas the proposed evaluation cost is governed by 2^k with per-candidate cost O(2^r).
4 Numerical results
The study derives upper bounds, applies a genetic algorithm to shortest self-orthogonal embeddings, and evaluates the resulting codes, runtime, guided crossover, and random-search comparisons. Across 469 base codes, the method yields 66 bound-attaining optimal codes and 135 codes two below the bound.
- Bounds: Upper bounds for binary self-orthogonal codes are derived by combining Grassl’s table, residual-code criteria, and nonexistence results.The bounds cover 20 ≤ n ≤ 256 and 9 ≤ k ≤ 15, with known values handled separately for k = 9 and k = 10.
- Method: The genetic algorithm searches shortest embeddings of MAGMA BKLC base codes using constraint-preserving representations and operators.The experiments include 469 base codes with m ≥ 5 appended columns; chromosomes encode orthogonal-group generators, and fitness prioritizes minimum distance before minimum-weight codeword count.
- Results: 201 distinct self-orthogonal codes remain after removing codes indistinguishable by both [n, k] and automorphism-group order.Among 469 base codes, the method reaches the bound for 73 and falls short by 2 for 151 before deduplication.
- Results: 66 new optimal self-orthogonal codes meet the upper bound, while 135 further codes attain the best minimum distance found so far with gap = 2.All reported codes in the two result tables are obtained by the genetic algorithm.
- Ablation: Guided crossover reaches all 66 bound-attaining codes, whereas random crossover misses 2 even with 20 additional generations.For gap-2 codes, the configurations are nearly tied at 132 versus 133 out of 135, and their total wall-clock times differ by less than 4%.
- Random-search comparison: Under equal time budgets, the genetic algorithm finds all 66 optimal codes and 198 of 201 codes within gap ≤2, outperforming both random baselines.Random + LS(8) finds 57 optimal codes and Pure random finds 49; the genetic algorithm is never outperformed on an individual case.
5 Conclusion
The paper develops a constraint-preserving genetic algorithm for shortest self-orthogonal embeddings and uses it to construct new high-distance binary self-orthogonal codes.
- The method reformulates shortest self-orthogonal embedding as finding a feasible block satisfying BBT = AAT.All shortest embeddings arise through the action of orthogonal group O(m, 2).
- Chromosomes encode weight-four transvections, so crossover, mutation, and local search automatically preserve self-orthogonality.This representation is based on O(m, 2) being generated by weight-four transvections for m ≥5.
- 66 new optimal self-orthogonal codes and 135 further best-known-distance codes were found for dimensions 9 ≤k ≤15.The previous computational searches cited in the conclusion were limited to dimensions up to 8.
- An ablation study and equal-time comparison with random search support the genetic algorithm and, specifically, guided crossover.
Appendix
The appendix presents upper bounds on minimum distances for binary self-orthogonal codes across specified lengths and dimensions.
- The bounds apply to self-orthogonal codes over F2 with dimensions 9 ≤k ≤15 and lengths 20 ≤n ≤256.
- Table 7 gives upper bounds on minimum distance for binary self-orthogonal [n, k] codes.The table covers dimensions 9 ≤k ≤15 and lengths 20 ≤n ≤256.