Erik Agrell’s tables of binary block codes

Purpose

This website forms an electronic supplement to [1] and [2]. It contains tables of bounds on the size of binary unrestricted codes, constant-weight codes, doubly-bounded-weight codes, and doubly-constant-weight codes.

The site is maintained as an online resource for the best known upper bounds for these classes of binary block codes. Hence, we would like to hear of any progress that is made, such as improved bounds or corrections. Tables of lower bounds are available elsewhere; see the links below.

Table history

• Aug. 10, 2000: The web version of the tables in [1] was published at www.chl.chalmers.se.
• Mar. 2, 2001: The web version of the table in [2] was published at www.s2.chalmers.se.
• 2001–2005: Updates based on [7] and [8].
• 2008: The site moved to webfiles.portal.chalmers.se.
• Jan. 5, 2015: The site moved to codes.se/bounds. Some corrections (references, links, values, and syntax).
• Jan. 5, 2015: Updates based on [8], [10], [11], and [12].

Tables

• Bounds on A(n,d), the maximum size of an (n,d) unrestricted binary code.
• Bounds on A(n,d,w), the maximum size of an (n,d,w) constant-weight binary code.
• Bounds on T´(w₁,n₁,w₂,n₂,d), the maximum size of a (w₁,n₁,w₂,n₂,d) doubly-bounded-weight binary code.
• Bounds on T(w₁,n₁,w₂,n₂,d), the maximum size of a (w₁,n₁,w₂,n₂,d) doubly-constant-weight binary code.

For definitions of these four classes of binary codes and their parameters, see [1].

[B] A. E. Brouwer: Upper and lower bounds for unrestricted binary, ternary, and quaternary codes. The tables constitute online versions of [4] and are regularly updated (2014).

[G] M. Grassl: Code Tables—Bounds on the parameters of various types of codes

[J] D. B. Jaffe: Upper and lower bounds for binary linear codes.

[LRS] S. Litsyn, E. M. Rains, and N. J. A. Sloane: Extensive tables of lower bounds for unrestricted binary codes. This is an online version of [6], updated until 1999.

[RS] E. M. Rains, and N. J. A. Sloane: Lower bounds for constant-weight binary codes, with upper bounds where they are known to coincide with the lower bounds. These tables, which unfortunately do not seem to be online anymore (2014), were an electronic supplement to [5].

References

[1] E. Agrell, A. Vardy, and K. Zeger, “Upper bounds for constant-weight codes,” IEEE Transactions on Information Theory, vol. 46, no. 7, pp. 2373–2395, Nov. 2000.

[2] E. Agrell, A. Vardy, and K. Zeger, “A table of upper bounds for binary codes,” IEEE Transactions on Information Theory, vol. 47, no. 7, pp. 3004–3006, Nov. 2001. Correction

[3] M. R. Best, A. E. Brouwer, F. J. MacWilliams, A. M. Odlyzko, and N. J. A. Sloane, “Bounds for binary codes of length less than 25,” IEEE Transactions on Information Theory, vol. IT-24, no. 1, pp. 81–93, January 1978.

[4] A. E. Brouwer, “Bounds on the size of linear codes,” in Handbook of Coding Theory (V. S. Pless and W. C. Huffman, eds.), vol. 1, pp. 295–461, Amsterdam, The Netherlands: Elsevier, 1998.

[5] A. E. Brouwer, J. B. Shearer, N. J. A. Sloane, and W. D. Smith, “A new table of constant weight codes,” IEEE Transactions on Information Theory, vol. 36, no. 6, pp. 1334–1380, Nov. 1990.

[6] S. Litsyn, “An updated table of the best binary codes known,” in Handbook of Coding Theory (V. S. Pless and W. C. Huffman, eds.), vol. 1, pp. 463–498, Amsterdam, The Netherlands: Elsevier, 1998.

[7] B. Mounits, T. Etzion, and S. Litsyn, “Improved upper bounds on sizes of codes,” IEEE Transactions on Information Theory, vol. 48, no. 4, pp. 880–886, Apr. 2002.

[8] A. Schrijver, “New code upper bounds from the Terwilliger algebra and semidefinite programming”, IEEE Transactions on Information Theory, vol. 51, no. 8, pp. 2859–2866, Aug. 2005.

[9] D. Smith, A. Sakhnovich, S. Perkins, D. Knight, and L. Hughes, “Application of coding theory to the design of frequency hopping lists,” Tech. report UG-M-02-1, Div. of Math. and Stat., Univ. of Glamorgan, Wales, U.K., Feb. 2002.

[10] P. R. J. Östergård, “Classification of binary constant weight codes”, IEEE Transactions on Information Theory, vol. 56, no. 8, pp. 3779–3785, Aug. 2010.

[11] P. R. J. Östergård, “On the size of optimal three-error-correcting binary codes of length 16”, IEEE Transactions on Information Theory, vol. 57, no. 10, pp. 6824–6826, Oct. 2011.

[12] D. C. Gijswijt, H. D. Mittelmann, and A. Schrijver, “Semidefinite code bounds based on quadruple distances”, IEEE Transactions on Information Theory, vol. 58, no. 5, pp. 2697–2705, May 2012.