key: cord-0047191-1ff2a0kh
authors: Bouyuklieva, Stefka; Bouyukliev, Iliya
title: Classification of Linear Codes by Extending Their Residuals
date: 2020-06-06
journal: Mathematical Software - ICMS 2020
DOI: 10.1007/978-3-030-52200-1_17
sha: c97cc7938ca8b0567cef7938b754a3020166cfe9
doc_id: 47191
cord_uid: 1ff2a0kh

An approach for classification of linear codes with given parameters starting from their proper residual codes or subcodes is presented. The base of the algorithm is the concept of canonical augmentation which is important for parallel implementations. The algorithms are implemented in the programs LengthExtension and DimExtension of the package QextNewEdition. As an application, the nonexistence of binary [41, 14, 14] codes is proved.

The paper is a contribution to the problem of classifying linear codes with given parameters over finite fields with q elements. Many authors have considered this problem before [2, 3, 5, 10] , and it is known to be very hard. The structure of the codes for classification is very important in the generation process. We discuss an algorithm that solves the following problem: Find all inequivalent codes with given parameters if the set of all residual codes with respect to a codeword with a given weight is given. The extension of the generator matrix of a given residual code can be done row by row or column by column. We consider in more details the problem how to generate only inequivalent codes and obtain all of needed codes. To do this, we use the concept of canonical augmentation [10, 12] . This concept is very important for parallel implementations. We also mention the dual problem namely the classification of linear codes by extending their proper subcodes.

The algorithms presented in this paper are implemented in the programs LengthExtension and DimExtension of the package QextNewEdition.

Restrictions on the dual distance, minimum distance, etc. can be applied. The program will be available on the webpage http://www.moi.math.bas.bg/moiuser/ ∼ data/Software/QextNewEdition

Let q be a prime power and F q the finite field with q elements, F * q = F q \ {0}. A linear code of length n, dimension k, and minimum distance d over F q is called an [n, k, d] q code. Two linear codes of the same length and dimension are equivalent if one can be obtained from the other by a sequence of the following transformations: (1) a permutation of the coordinate positions of all codewords;

(2) a multiplication of a coordinate of all codewords with a nonzero element from F q ; (3) a field automorphism. A sequence of the transformations given above that maps a code C to itself is called an automorphism of C. The set of all automorphisms of C forms a group, called the automophism group of the code and denoted by Aut(C). The action of Aut(C) on the code partitions the set of its codewords into orbits.

The defined equivalence relation in the set of all linear [n, k, d] q codes partitions this set into equivalence classes. We choose a canonical representative of each equivalence class. If C is a linear [n, k, d] q code, we call the canonical representative of its equivalence class the canonical form of C and denote it by ρ(C). If two codes C 1 and C 2 are equivalent they have the same canonical form, or ρ(C 1 ) = ρ(C 2 ).

Let C be an [n, k, d] q code and let c be a codeword of weight w. Then the residual code of C with respect to c, denoted Res(C; c), is the code of length n − w punctured on the set of coordinates on which c is nonzero. If only the weight w of c is of importance, we will denote it by Res(C; w). The next result gives a lower bound for the minimum distance of residual codes. Theorem 1. [8] Let C be an [n, k, d] code over F q and let c be a codeword of weight w < qd/(q − 1).

We need also the following theorem Theorem 2. Let C be an [n, k, d] code over F q and x, y ∈ C be codewords of the same weight w < qd/(q−1) such that y = φ(x) for an automorphism φ ∈ Aut(C). Then the residual codes Res(C; x) and Res(C; y) are equivalent.

Without loss of generality we can take x = (00 · · · 0 11 · · · 1 w ). Then the sup-

Hence the restriction of φ on the first n − w coordinates maps Res(C; x) to Res(C; y).

To see the connection to the dual code, we use a theorem that gives the relation between a punctured of a code C and a shortened of its dual code C ⊥ . A code C can be punctured on a coordinate set T of size t. We denote the resulting code by C T . Consider the set C(T ) of codewords whose i-th coordinate is 0 if i ∈ T . C(T ) is a subcode of C. Shortening C(T ) on T gives a code of length n − t called shortened code of C on T and denoted by C T . If we take T to be the support of the codeword c ∈ C of weight w, then C T is the residual code of Res(C; c) with respect to c. Theorem 3 ([9, Theorem 1.5.7]). Let C be an [n, k, d] code and T be a set of t coordinates. Then:

As a corollary we obtain

Since Res(C; c) ⊥ is a shortened code of C ⊥ , its minimum distance is at least d ⊥ . Therefore we consider all [n − w, k − 1, d ≥ d − w + w/q ] q codes with dual distance ≥ d ⊥ as residual codes and then extend them to the linear [n, k, d] q codes with dual distance ≥ d ⊥ .

We developed a second algorithm which extends all possible [n−w, k−w+1, ≥ d] shortened codes to the [n, k, d] codes provided that their dual codes contain codewords of weight w, w < qd ⊥ /(q − 1). The theoretical base of this algorithm is the following corollary.

(see Theorem 3 and Corollary 1).

We are looking for all inequivalent linear codes with length n, dimension k, minimum distance d and dual distance at least d ⊥ ≥ 2. We propose two algorithms depending on the input codes.

The input in the first algorithm is a set of all inequivalent linear [n−w, k−1, ≥ d ] q codes with dual distance ≥ d ⊥ where d > d − w + w/q . These codes are all possible residual codes of [n, k, d] q linear codes with dual distance at least d ⊥ with respect to a codeword of weight w.

Without loss of generality, we can consider the generator matrices in the form 00 · · · 0 11 · · · 1 G res G 1

where G res is a (k−1)×(n−w) matrix that generates the residual code Res(C; x), x = (00 · · · 0, 11 · · · 1) ∈ C, wt(x) = w. We construct the matrix G 1 row by row in the same way as it is in the program qext l of the package Q-Extension [3] . The main question is which of the constructed in this way codes to take in our set of representatives of the equivalence classes. To do this, we use canonical augmentation [10, 12] . The presentation that follows differs from the original McKay's paper [12] but the idea is the same. First, we find the canonical form and the automorphism group of the constructed [n, k, d] code C. The orbits are ordered in the way described in [1] and this ordering depends on the canonical form ρ(C) and the automorphism group Aut(C). Then we check if the vector x is in the first orbit in the set of all codewords of weight w in C. If not, we reject it (it can be obtained by another residual code), if yes we say that this code passes the parent test. Finally, we check for equivalence the codes obtained from the same residual code that have passed the parent test. A pseudocode is presented in Algorithm 1.

Proof. We have to prove that (1) any [n, k, d] q code with the needed dual distance is equivalent to a code in the set M , and (2) the codes in M are not equivalent.

(1) Let C be an [n, k, d] q code with dual distance ≥ d ⊥ . The set of all codewords of weight w is partitioned into orbits under the action of Aut(C). These orbits are ordered depending on the canonical form ρ(C) (see [1] for details). Take a codeword x in the first orbit and the residual code Res(C; x). There is a code B ∼ = Res(C; x) in the set R. If φ maps Res (C; x) into B, we can extend the map φ to φ : C → C , C = φ(C). If x = φ(x), then B = Res(C , x ) and the code C passes the parent test (the codeword x ∈ C belongs to the first orbit in the partition of the set of all codewords of weight w in C since ρ(C) = ρ(C )). Hence there is a code that is equivalent to C, has a residual code in the set R and passes the parent test. (2) If C 1 ∼ = C 2 are two codes with the needed parameters, x i ∈ C i , i = 1, 2 are vectors of weight w, and both codes pass the parent test, then their residuals Res(C 1 , x 1 ) and Res(C 2 , x 2 ) are also equivalent (see Theorem 2).

We use the presented algorithms implemented in the programs LengthExtension and DimExtension to obtain a systematic classification of linear codes with specific properties and parameters over fields with 2, 3 and 4 elements.

Besides specifying the parameters such as length (n), dimension (k) and minimum distance (d), many other constraints can be considered. We give two examples, both over the filed F 2 , but the first one uses the program LengthExtension and the second one DimExtension. All calculations have been done on 2 × Intel Xeon E5-2620 V4, 32 thread computer. and weight enumerator W (y) = 1 + 99y 20 + 90y 22 + 15y 24 + 45y 28 + 6y 30 . Its automorphism group is isomorphic to (C 15 : C 4 )×S 3 , where C 15 : C 4 is the semidirect product of the cyclic groups of orders 15 and 4, and S 3 is the symmetric group (calculated by GAP Computer Algebra System [6] ). The group acts transitively on the coordinates and has order 360. The code is not self-orthogonal.

The following proposition allows one to reduce the number of cases that need to be considered for an exhaustive search for a certain class of codes. Proposition 1. If binary linear [n, k, 2d] codes exist then at least one of these codes is even.

Proof. Let C be a binary linear [n, k, 2d] code. Suppose that C contains codewords of odd weight. If C * is the punctured code of C on the right-most coordinate then C * is an [n − 1, k, d * ] code where d * = 2d − 1 or 2d. Then we extend C * with one coordinate by adding an overall parity check. The [7] indicates that the existence of [40, 13, 14] binary codes is also unknown. If a code with these parameters exists, its dual distance can be 5 or 6. If C is a [40, 13, 14] binary even code with dual distance 5, it contains an even [35, 9, 14] shortened code with dual distance ≥ 3. By the program DimExtension, we obtain that these codes cannot be extended to [40, 13, 14] binary codes. This means that if a [40, 13, 14] binary even code exists, its dual distance is 6. Then this code contains a shortened code with parameters [34, 8, 14] and dual distance ≥ 3. There are 10 607 917 inequivalent [34, 8, 14] codes with needed dual distance. We were not able to extend all these codes for a reasonable time and therefore we have no result for the codes with parameters [40, 13, 14] .

About the code equivalence

Computer classification of linear codes

Some new results for optimal ternary linear codes

Classification of the extremal formally self-dual even codes of length 30

Classification and nonexistence results for linear codes with prescribed minimum distances

GAP -Groups, Algorithms, and Programming

Bounds on the minimum distance of linear codes and quantum codes

Optimal ternary linear codes

Fundamentals of Error-Correcting Codes

Classification Algorithms for Codes and Designs

Isomorph-free exhaustive generation

We are greatly indebted to the unknown referees for their useful suggestions.

The second algorithm extends all [n−w, k−w+1, ≥ d] codes to the [n, k, ≥ d] codes with dual distance d ⊥ whose dual codes contain codewords of weight w. The generator matrices of the considered codes have the form ⎛ w) matrices, respectively. We fill out the matrix A row by row in a similar way as it is done in [4] . The dual code C ⊥ has a generation matrix 11 · · · 1 00 · · · 0 G 1 G 2 where G 2 generates the residual code of C ⊥ with respect to the codewords (11 · · · 100 · · · 0) of weight w and it is the dual code of C 0 . To take only inequivalent codes, we apply Algorithm 1 to the dual codes.