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, 2^n-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

1. 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.
2. 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.
3. P. Kaski and P. R. J. Östergård, Classification Algorithms for Codes and Designs, Springer, 2006, doi:10.1007/3-540-28991-7.
4. D. S. Krotov, P. R. J. Östergård, and O. Pottonen, On Optimal Binary One-Error-Correcting Codes of Lengths 2^m-4 and 2^m-3, IEEE Transactions on Information theory 57 (2011), 6771–6779, doi:10.1109/TIT.2011.2147758. Preprint at arXiv:1104.4013.
5. 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.
6. 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.
7. 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.
8. 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.
9. 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.
10. 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.