Perfect and Related Codes

Citation Author(s):
Sobolev Institute of Mathematics
Submitted by:
Denis Krotov
Last updated:
Mon, 05/16/2022 - 07:40
Data Format:
0 ratings - Please login to submit your rating.


This dataset is devoted to 1-perfect codes. Currently, it is mainly focused on the concatenated ternary perfect codes, but there is also an additional content, see (3) below, (1-2) This dataset contains all inequivalent concatenated ternary 1-perfect codes of length 13. Additionally, it contains some components necessary to obtain such concatenated codes, namely, collections of disjoint ternary distance-3 Reed-Muller-like codes of length 9, see p.(1) below. (3) Independently, check matrices of all (equivalent) binary Hamming codes of length 15 are collected in one file and all 232 inequivalent pairs of disjoint such codes are kept in another file.

In details, the dataset keeps:

(1) Inequivalent collections of (from 1 to 9) ternary $(9,3^6,3)_3$ codes that are subsets of the all-parity-check $(9,3^8,2)_3$ code. The equivalence is understood in the sense of the automorphisms of the Hamming graph $H(9,3)$. There are 4 equivalence classes of such codes; 141 equivalence classes of pairs of disjoint codes; 10956 equivalence classes of triples; 118388 classes for 4 disjoint codes; 501915 for 5; 945965 for 6; 755066 for 7; 314833 for 8; 65436 equivalence classes of partitions of the all-parity-check $(9,3^6,3)_3$ code into 9 distance-3 codes. Such partitions, in combination with partitions of the Hamming space $H(4,3)$ into 9 1-perfect codes (the two inequivalent partitions of $H(4,3)$ can also be found in the file in this dataset), can be used to construct 1-perfect ternary codes of length 13 by concatenation, see [Romanov, A. M. On Non-Full-Rank Perfect Codes Over Finite Fields. Des. Codes Cryptography, 2019, 87, 995-1003].

(2) All 93241327 inequivalent concatenated 1-perfect $(13,3^{10},3)_3$ codes (one code of rank 10, the Hamming code, 1164330 codes of rank 11, and 92076996 codes of rank 12). Each such code is the concatenation of one of the partitions of the all-parity-check $(9,3^8,2)_3$ code into $9$ codes, see p.(1), and one of the two inequivalent partitions of $H(4,3)$ into $1$-perfect codes (partition "A" consists of the translations of the same Hamming code, partition "B" is the other one). The $i$th code of a partition of length $9$ is concatenated with the $p(i)$th code of the partition "A" or "B" of length $4$, where $p$ is a permutation of $(0,1,2,3,4,5,6,7,8)$, and the resulting code is the union over all $i=0,1,2,3,4,5,6,7,8$.

(3) The file allHamming15.txt in the archive contains the check matrices of all 64864800 binary Hamming codes of length 15 ( equivalently 64864800 projective geometries PG(3,GF(2)), or linear STS(15) ). The file Hamming_pairs.txt in the same archive keeps all 232 ordered pairs of disjoint binary Hamming codes of length 15 (one code is linear, the other is a translation of a linear code).


(1) Each text file in the dataset archived in keeps collections of disjoint $(9,3^6,3)_3$ codes, coded in the following manner (the file names are coded with equivalence classes of the corresponding codes, from 0 to 3; some files are empty, for example, "n00123", because two codes from equivalence class 0, one code from class 1, one code from class 2, and one code from class 3 cannot be packed in a disjoint manner). Each line corresponds to one representative of such a collection. If the number of codes is M, then the line contains M records like "N T PPPPPPPPP". "N" denotes the number of a code in the list of seven permutably inequivalent codes (note that "permutably equivalent" is not the same as "equivalent"; only first 4 are inequivalent in the sense of $Aut(H(9,3))$, the last 3 are equivaleng to the code number 3). "T" is the number of a translation vector in the list 0: 000000000, 1: 120000000, 2: 102000000, 3: 100200000, 4: 100020000, 5: 100002000, 6: 100000200, 7: 100000020, 8: 100000002, and "PPPPPPPPP" is a coordinate permutation. To reconstruct the corresponding code, one should take the code number "N" from, apply the coordinate permutation "PPPPPPPPP" in the following manner: $$(x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8) \to (x_{P^{-1}(0)},x_{P^{-1}(1)},x_{P^{-1}(2)},x_{P^{-1}(3)},x_{P^{-1}(4)},x_{P^{-1}(5)},x_{P^{-1}(6)},x_{P^{-1}(7)},x_{P^{-1}(8)}),$$ and add the translation vector number "T" to all codewords.  After M records about the codes, each line contains: (ii) the record "-A", where A is the order of the automorphism group of the collection of codes; (iii) the record "+R", where 6+R is the rank of the collection, that is, the dimension of the union of the (non-translated) codes (the minimum rank is 6 and the maximum is 8=9-1 because of the all-parity check, so R is 0, 1, ro 2); (iv) the record "~" or "|", where "~" means that the collection can be continued to a collection of M+1 codes and "|" means that no $(9,3^6,3)_3$ code (satisfying the all-parity check) can be added to the complement (this can only happen when M is 6 or 9).

(2) The file "concat13" (arxived to concat13.xz; the original file is 1.7GiB) contains the list of all inequivalent concatenated ternary 1-perfect codes of length 13 in the following form. Each length-9 partition in the form described in p.(1) (the order of records is (i), (iii), (ii), and the last record contains generators of the group of permutations of 9 codes induced by the automorphism group of the partition) is followed by the list of concatenated codes obtained with this partitions. The records for each code are the following:

(i) "A" or "B" indicate the partition of $H(4,3)$ into 1-perfect codes.

(ii) The next 8 numbers show the permutation $p$ of the codes of the partition.

(iii) The record "+R" means that the rank of the code is 10+R (10, 11, or 12).

(iv) The record ":K" means that the dimension of the kernel of the code is K (the kernel is the set of all periods of the code, that is, the translations that send the code to itself).

(v) The record "/S" means that the code can be represented as a concatenated code in S different ways (partitions 9+4 of coordinates); for the rank-10 Hamming code this number is 13; for rank-12 codes it is 1; for rank-11 codes it is from 1 to 4.

(vi) The record "-A*K" means that the order of the automorphism group of the code is A*K, while A is the number of authomorphisms that keep the coordinate partition 9+4, i.e., the current concatenation structure (if (iv) is "/1", then K necessarily equals 1).

If the record (v) is "/1" or "/13", then there are no more records, because this guarantees that an equivalent code cannot be obtained by concatenation in another way (in particular, from a different partition).

If the record (v) is "/2", "/3", or "/4", then such codes were checked for isomorphism, and one more record is given:

(vii) This record contains a symbol "n" or "o" and some number. "n" means that the code is new, and it is not equivalent to any of the codes above, and the following number is its unique number (among the codes with symbol "n" in the record). "o" means that the code is not new and it is equivalent to one of the codes above, namely, the one with symbol "n" followed by the same number.

So (ATTENTION!!!), some lines of the database correspond to equivalent codes; to read only inequivalent codes, one should ignore the lines with symbol "o".

Additional material: (3) The file contains the database file (to reduce the size, the xz-compression was applied) with 64864800 check matrices of [15,11,3] different Hamming codes, the database file with the 232 inequivalent pairs of disjoint Hamming codes, the file readme.txt with instructions and some scripts.