Optimal One-Error-Correcting Binary Codes and their Extensions


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.

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].


  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 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.
  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.