Optimal One-Error-Correcting Binary Codes and their Extensions
Classification
The optimal one-error-correcting binary codes are known up to length
15. For lengths 4,…,11, the codes were classified by
Östergård, Baicheva and Kolev
[6]. Some of the shorter cases also appeared in
earlier publications
[10, 1, 5]. Codes
of lengths 12 and 13 were classified by Krotov, Östergård
and Pottonen [4] and the codes of lengths
14 and 15 by Östergård and
Pottonen [7].
For a general reference on combinatorial classification, and a catalogue of the codes of lengths up to 11 (12 for d=4), see the monograph by Kaski and Östergård [3].
For length 12≤n≤15, any (n, 2n-4, 3) code is an
orthogonal array of strength t = n−8 as is its extension [2], see also [4, 8].
All these codes are made available on this page.
The files contain one code per line, and a code is given as a list of codewords in hexadecimal format, separated by single space characters.
The largest files are compressed.
- the 2 (4,2,3) codes and their extensions: the 2 (5,2,4) codes
- the unique (5,4,3) code and its extension: the unique (6,4,4) code
- the unique (6,8,3) code and its extension: the unique (7,8,4) code
- the unique (7,16,3) code and its extension: the unique (8,16,4) code
- the 5 (8,20,3) codes and their extensions: the 3 (9,20,4) codes
- the unique (9,40,3) code and its extensions: the unique (10,40,4) code
- the 562 (10,72,3) codes and their extensions: the 96 (11,72,4) codes
- the 7398 (11,144,3) codes and their extensions: the 1041 (12,144,4) codes
- the 237610 (12,256,3) codes (39MB) and their extensions: the 27375 (13,256,4) codes (3MB)
- the 117832 (13,512,3) codes (42MB) and their extensions: the 17513 (14,512,4) codes (5MB)
- the 38408 (14,1024,3) codes (33MB) and their extensions: the 5983 (15,1024,4) codes (5MB)
- the 5983 (15,2048,3) codes (13MB) and their extensions: the 2165 (16,2048,4) codes (4BM)
Some specific codes
Östergård and Pottonen [9] discovered 2 (13,512,3) codes that are not double-shortened (15,2048,3) codes.
It turns out that they are only such codes [4], and furthermore they
have the same extension. It also turns out that
there are 10 (12, 256, 3) codes that
do have the same property, and they have 3 different extensions [4].
Bibliography
- T. Baicheva and E. Kolev, Binary codes of length eight, minimum distance three and twenty codewords, in Proc. 2nd International Workshop on Optimal Codes and Related Topics (Sozopol, Bulgaria, June 9–15, 1998), Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, Sofia, 1998, pp. 5–8.
- M. R. Best and A. E. Brouwer, The triple shortened binary Hamming code is optimal, Discrete Mathematics 17 (1977), 235–245, doi:10.1016/0012-365X(77)90158-3.
- P. Kaski and P. R. J. Östergård,
Classification Algorithms for Codes and Designs, Springer, 2006,
doi:10.1007/3-540-28991-7.
- D. S. Krotov, P. R. J. Östergård, and O. Pottonen,
On Optimal Binary One-Error-Correcting Codes of Lengths 2m-4 and 2m-3, IEEE Transactions on Information theory 57 (2011), 6771–6779, doi:10.1109/TIT.2011.2147758. Preprint at arXiv:1104.4013.
- S. Litsyn and A. Vardy, The uniqueness of the Best code, IEEE Transactions on Information Theory 40 (1994), 1693–1698,
doi:10.1109/18.333896.
- P. R. J. Östergård, T. Baicheva, and E. Kolev,
Optimal binary one-error-correcting codes of length
10 have 72 codewords, IEEE Transactions on Information
Theory 45 (1999), 1229–1231, doi:10.1109/18.761273. See also this page.
- P. R. J. Östergård and O. Pottonen,
The Perfect Binary One-Error-Correcting Codes of Length 15: Part
I—Classification, IEEE Transations on Information Theory 55 (2009),
4657–4660,
doi:10.1109/TIT.2009.2027525. Preprint at
arXiv:0806.2513.
- P. R. J. Östergård, O. Pottonen and K. T. Phelps,The Perfect Binary One-Error-Correcting Codes of Length 15:
Part II—Properties, IEEE Transations on Information Theory, 56 (2010), 2571–2582,
doi:10.1109/TIT.2010.2046197. Preprint at
arXiv:0903.2749.
- P. R. J. Östergård and O. Pottonen,
Two Optimal One-Error-Correcting Codes of Length 13 That Are Not Doubly Shortened Perfect Codes, Designs, Codes and Cryptography 59 (2011), 281–285,
doi:10.1007/s10623-010-9450-4. Preprint at
arXiv:0909.2526.
- S. K. Zaremba, Covering problems concerning abelian groups, Journal of the London Mathematical Society 27 (1952), 242–246, doi:10.1112/jlms/s1-27.2.242.