Source-linked AI summary
New binary optimal LCD codes using heuristic embedding
Haeun Lim, Junmin An, Jon-Lark Kim
TL;DR
The paper addresses the difficulty of constructing optimal binary LCD codes when shortest-embedding search spaces are too large for exhaustive enumeration. It applies greedy search to structured shortest LCD embeddings and reports 14 previously unknown optimal codes among 19 found, while noting local-optimum and dimensional-scope limitations.
Problem
Shortest LCD embeddings are parameterized by matrices that create search spaces too large for exhaustive enumeration, motivating more efficient construction methods.
Method
The paper applies greedy search to shortest LCD embeddings, using row operations on the invertible block and entry flips on the arbitrary block as local moves.
Results
14 of the 19 optimal LCD codes found for dimensions 6 ≤k ≤8 and lengths 55 to 225 were previously unknown.
Takeaways & Limitations
The method produced 14 new optimal LCD codes, including codes whose parameters determine exact dLCD(n, k) values.
Takeaways & Limitations
Greedy search may become trapped in a local optimum, and no codes attaining the corresponding bounds were obtained for dimensions k = 9 and k = 10.
Abstract
from arXiv · showhide
In this paper, we investigate the construction of binary optimal LCD codes through short LCD embeddings. For this purpose, we design heuristic frameworks based on a greedy algorithm. We explore the search spaces of LCD embeddings using the fact that an invertible matrix together with an arbitrary matrix yields an LCD embedding. We therefore use elementary row operations on the invertible block and single entry-flips on the arbitrary block as local moves in a greedy algorithm. Using this method, we have found $14$ optimal new LCD codes with dimensions 7 and 8 for lengths from 55 to 201.
1 Introduction
Optimal LCD codes are a central coding-theory problem, with prior binary results concentrated at smaller dimensions and lengths. The paper applies heuristic search to shortest LCD embeddings to expand these constructions.
- Optimal LCD codes remain a fundamental construction problem because researchers seek the largest possible minimum distances.
- Prior work established complete or partial binary results mainly for dimensions up to six and lengths up to 50.Exact values were determined for lengths n ≤12, while partial results covered various dimensions for n ≤50 and dimensions three through six.
- Shortest LCD embeddings construct LCD codes by appending columns to a generator matrix, extending earlier self-orthogonal embedding methods.
- Exhaustive enumeration is impractical because shortest LCD embeddings are parameterized by an arbitrary invertible matrix and an arbitrary matrix.
- A greedy algorithm searches these embeddings using elementary row operations and single-entry flips as local moves.
- The method produced 19 optimal LCD codes for dimensions 6 ≤k ≤8 and lengths 55 to 225, including 14 previously unknown codes.
2 Preliminaries
The preliminaries define binary linear and LCD codes, shortest LCD embeddings, and the greedy-search framework. Shortest embeddings have a constrained invertible block but an arbitrary companion block, creating a structured search space.
- Linear codes: A binary linear [n, k] code is a k-dimensional subspace of F2^n represented by a generator matrix.
- LCD codes: An LCD code has trivial hull, equivalently its generator matrix G satisfies that GGT is invertible.
- Distance optimality: A code is distance-optimal when its minimum distance equals d(n, k), the largest minimum distance among all linear [n, k] codes.
- LCD embeddings: An LCD embedding is an LCD code obtained by adding coordinates so that puncturing those coordinates recovers the original code.
- Shortest LCD embeddings: A shortest LCD embedding has minimum possible length, namely n + ℓ when the original code's hull dimension is ℓ.
- Shortest LCD embeddings: Every shortest LCD embedding is obtained by choosing an invertible matrix D and an arbitrary matrix B.
- Greedy algorithm: Greedy search repeatedly accepts improving neighboring solutions, but may terminate at a local optimum rather than a globally optimal solution.
- Greedy algorithm: A multi-start strategy reduces dependence on one initial solution by repeating greedy search from different starting points.
3 Methods
The methods derive upper bounds for binary LCD codes and search shortest LCD embeddings with greedy local moves. Fitness prioritizes minimum distance, then the number of minimum-weight codewords, across lengths 51 ≤n ≤256 and dimensions 6 ≤k ≤10.
- Bounds: The bounds combine Grassl-table bounds with recursive bounds from smaller lengths and dimensions.
- Bounds: Upper bounds on dLCD(n, k) are derived for binary LCD codes with 51 ≤n ≤256 and 6 ≤k ≤10.
- Bounds: The recursion improves the general linear-code bound by one for binary LCD [51, 8] codes, giving dLCD(51, 8) ≤23 instead of 24.
- Search objective: The search seeks shortest LCD embeddings with the largest possible minimum distance for target parameters 51 ≤n ≤256 and 6 ≤k ≤10.
- Local moves: The invertible block D is modified by row-addition and row-swap operations, while the arbitrary block B is modified by entry flips.
- Search procedures: Two experiments use either joint random local moves or alternating block-coordinate updates, with restarts after local optima.
- Fitness: Fitness is lexicographic: larger minimum distance is preferred, followed by fewer minimum-weight codewords when distances tie.
4 Numerical results
The experiments produced LCD codes that attained the bound or fell short by one to seven units, including 14 new optimal codes in dimensions 7 and 8. These results determine exact dLCD(n, k) values for the corresponding parameters.
- Experimental setup: 1019 base codes were processed, with redundant parameter sets reduced to representatives having the largest minimum distance.The resulting representative set contained 756 codes.
- New optimal codes: 14 new optimal LCD codes were obtained with dimensions 7 and 8, spanning lengths from 55 to 201.The listed parameters include nine dimension-7 codes and five dimension-8 codes.
- Comparison with prior codes: Among the 19 bound-attaining codes, five were equivalent to codes in prior databases or studies, while the remaining 14 had no equivalent codes found in previous studies.Those remaining 14 codes attain the upper bound and therefore determine exact dLCD(n, k) values for their parameters.
- New optimal codes: The new optimal parameter sets include [55, 7, 25], [85, 7, 40], [201, 8, 98], and other codes listed in Theorem 4.1.The theorem identifies the complete set of 14 new binary optimal LCD-code parameters.
- Result interpretation: The tables report the largest minimum distance found across four runs for each parameter set, with an asterisk marking attainment of the upper bound.Here, n is the length after applying a shortest LCD embedding, and “Our result” is compared with the bound on dLCD(n, k).
5 Conclusion
The paper applies a greedy algorithm to shortest LCD embeddings to construct optimal LCD codes, obtaining 19 codes and 14 new ones, while dimensions 9 and 10 remain unresolved.
- 19 optimal LCD codes were constructed for lengths 51 ≤ n ≤ 256 and dimensions 6 ≤ k ≤ 8, including 14 new codes.The method uses elementary row operations on invertible matrices and entry flips on arbitrary matrices as local moves.
- No codes attaining the corresponding bounds were obtained for dimensions k = 9 and k = 10, leaving these dimensions for future work.