Source-linked AI summary
Construction of Large Constant Dimension Codes With a Prescribed Minimum Distance
Axel Kohnert, Sascha Kurz
TL;DR
The paper addresses construction of constant dimension codes with prescribed minimum subspace distance. It uses automorphism-constrained Diophantine systems and reports competitive codes, including new constructions with improved code sizes.
Problem
The problem is to construct constant dimension subspace codes with a prescribed minimum subspace distance and many codewords.
Method
The paper constructs codes by solving Diophantine systems derived from incidence matrices, restricting the search to codes with prescribed automorphism groups such as Singer cycles.
Results
For v = 6, the direct approach produced a code of cardinality n = 74, improving earlier examples by 3; for v = 7, a construction produced 304 three-dimensional subspaces.
Takeaways & Limitations
The approach constructs competitive constant dimension codes, improves lower bounds for Aq(v, d, k) in some cases, and is especially effective for v ≥8.
Takeaways & Limitations
Constructing condensed incidence matrices remains difficult for arbitrary groups and larger parameters, and a restricted subgroup search did not find codes of size 304.
Abstract
from arXiv · showhide
In this paper we construct constant dimension space codes with prescribed minimum distance. There is an increased interest in space codes since a paper by Koetter and Kschischang were they gave an application in network coding. There is also a connection to the theory of designs over finite fields. We will modify a method of Braun, Kerber and Laue which they used for the construction of designs over finite fields to do the construction of space codes. Using this approach we found many new constant dimension spaces codes with a larger number of codewords than previously known codes. We will finally give a table of the best found constant dimension space codes.
1 Introduction
The paper frames constant dimension codes as subspace-code packing problems with prescribed minimum distance, motivated by network coding and connections to finite-field designs.
- Subspace Codes: A subspace code is a collection of subspaces over GF(q), and it is constant dimension when all codewords have the same dimension.The framework uses the lattice of all subspaces of GF(q)^v.
- Subspace Codes: The optimal code problem fixes a lattice and minimum distance, then maximizes the number of subspaces whose pairwise distances meet that threshold.This is presented as problem (P1).
- Connections: Subspace-code optimization is the q-analogue of Hamming-graph packing, replacing words with subspaces in the lattice of GF(q)^v.The paper relates the two problems through the Hasse diagram and the field-with-one-element viewpoint.
- q-Analogues of Designs: A q-analogue of a t-(v,k,λ) design uses k-dimensional subspaces so every t-dimensional subspace occurs in exactly λ q-blocks.The paper defines these as finite-field counterparts of classical designs.
- q-Analogues of Designs: A q-analogue of a Steiner system yields a constant dimension code with minimum distance 2(k−t+1), because distinct blocks intersect in dimension at most t−1.The converse construction identifies two blocks whose distance attains this value.
- Connections: The paper adapts methods for q-analogue designs to construct constant dimension codes while searching only for the weaker conditions of the optimal code problem.This avoids requiring the stronger Steiner-system property, whose existence is severely restricted.
2 Construction of Constant Dimension Codes
The construction converts prescribed-distance code selection into a binary Diophantine system based on incidence between candidate k-spaces and forbidden lower-dimensional subspaces.
- Incidence formulation: For constant dimension k, the subspace distance is 2k−2dim(V∩W), so target distances are even and bounded by 2k.A code of minimum distance 2d must avoid common subspaces of dimension k−d+1.
- Incidence formulation: The incidence matrix M has rows for (k−d+1)-spaces and columns for k-spaces, recording containment between them.Its entries are 1 when a row space is contained in a column space and 0 otherwise.
- Diophantine system: A code with m codewords and minimum distance at least 2d exists exactly when a binary vector selects k-spaces while every row of M sums to at most one.The selected vector is the characteristic vector of the code.
- Diophantine system: The system generalizes the Diophantine formulation used to search for q-analogue Steiner systems.The code-selection problem relaxes exact design conditions to distance constraints.
- Computational size: The formulation becomes computationally large because the number of subspaces is governed by q-binomial coefficients.Even the q-analogue of the Fano plane for q=2 produces a matrix with 11811 columns and 2667 rows.
3 Constant Dimension Codes with prescribed Automorphisms
The construction reduces constant-dimension code searches by prescribing automorphisms, compressing the associated incidence system into orbit-based variables and constraints. The resulting optimization formulations yield a 304-word code in GF(2)^7 with dimension 3 and minimum distance 4, while larger instances remain computationally difficult.
- Automorphism reduction: Prescribing automorphisms reduces the system size to orbit variables on k-spaces and orbit constraints on (k−d+1)-spaces.The number of variables and constraints becomes the number of corresponding group orbits.
- Optimization formulations: The construction begins with a Diophantine linear system and can be reformulated as binary linear optimization or a weighted graph problem.The optimization formulation provides feasible-solution lower bounds and upper bounds during the search, while the graph formulation corresponds to maximum-weight clique.
- Matrix reduction: Columns violating the at-most-one condition are removed, followed by deletion of zero and duplicate rows to further reduce the condensed matrix.These reductions preserve the search for a (0/1)-solution satisfying the system's constraints.
- Example: In GF(2)^7, the chosen automorphism group gives 567 orbit variables and 129 orbit constraints, reduced by presolving to 477 variables and 126 constraints.The reduced system has 3306 nonzero coefficients.
- Example: 304 codewords were obtained with constant dimension 3 and minimum distance 4, exceeding previously known codes with 289 and 294 codewords.The code was formed from 16 selected orbits after the software found a feasible (0/1)-solution.
- Computational boundary: For larger parameters, rapidly growing numbers of subspaces make computing all required group orbits and the condensed matrix difficult.The paper introduces a method for special cases to obtain a similar matrix.
4 Using Singer Cycles
The paper uses Singer subgroup orbits to represent and combine k-dimensional subspaces, then tests their distance distributions through a reduced Diophantine system. This yields constant dimension codes with prescribed minimum distance and Singer-subgroup automorphisms.
- Orbit construction: Singer subgroup orbits provide a structured way to construct k-dimensional subspace codes with prescribed intersection properties.The subgroup acts transitively on one-dimensional subspaces, allowing orbit members to be generated by incrementing their labels modulo the Singer cycle length.
- Orbit construction: A k-space is represented by the labels of its contained one-dimensional subspaces, and its distance distribution is the multiset of pairwise label distances.All spaces in one Singer orbit share the same distance distribution, which is used to distinguish the different orbits.
- Single-orbit criterion: A Singer orbit is a code of minimum distance 2(k −1) exactly when its distance distribution has no repeated numbers.This condition ensures that any two code spaces intersect in at most one one-dimensional subspace.
- Multiple-orbit construction: Combining several Singer orbits requires checking that their distance distributions do not create intersections larger than one dimension.The matrix S records orbit distance distributions by possible distance values and supports this compatibility test.
5 Results
The authors construct binary constant dimension codes with prescribed minimum distance using Singer-cycle symmetries and a more general condensed-matrix approach. The resulting codes improve known bounds in some cases and are competitive for v ≥8, while subgroup searches can be computationally unsuccessful.
- The study restricts its main construction to q = 2, k = 3, and minimum subspace distance dS = 4.
- Singer-cycle constructions produce code sizes that improve lower bounds on Aq(v, d, k) for v ≥9, with results optimal for the Singer cycle when 6 ≤v ≤8.For v = 9, a code size n = 12 is theoretically possible, but the corresponding binary linear program was not solved to optimality.
- For v = 6, the general incidence-matrix approach yields a code of cardinality n = 74, improving earlier examples by 3, against an upper bound of 93.The instance contains 1395 binary variables, 651 constraints, and 9765 nonzero entries.
- For v = 7, a suitable automorphism group produces 304 three-dimensional subspaces of GF(2)^7 whose pairwise intersections have dimension at most one.The construction required trying several groups before selecting the specific group described in the results.
- Restricted subgroup searches near translated solutions did not find codes of size 304 for subgroups of the group of order 21.Solutions for a group G can be translated to subgroups because moving to a subgroup can split orbits.
- The authors conclude that the approach constructs good codes for prescribed minimum distance and that prescribing a Singer cycle reduces computational effort; the resulting codes are competitive for v ≥8.For v = 6 and v = 7, the discovered codes motivate further calculation of condensed matrices for other groups.