Bounds for binary codes relative to pseudo-distances of $k$ points

Christine Bachoc; Gilles Zémor

doi:10.3934/amc.2010.4.547

Article Contents

2010, Volume 4, Issue 4: 547-565. Doi: 10.3934/amc.2010.4.547

This issue Previous Article Input-state-output representations and constructions of finite support 2D convolutional codes Next Article On $q$-ary linear completely regular codes with $\rho=2$ and antipodal dual

Bounds for binary codes relative to pseudo-distances of $k$ points

Christine Bachoc^1, and
Gilles Zémor^1,

1.
Université Bordeaux I, Institut de Mathématiques, 351, cours de la Libération, 33405 Talence

Received: January 31, 2010

Revised: June 30, 2010

Published: October 2010

Abstract Related Papers Cited by

Abstract

We apply Schrijver's semidefinite programming method to obtain improved upper bounds on generalized distances and list decoding radii of binary codes.

Keywords:

Mathematics Subject Classification: 94B65, 90C22.

Citation:

Related Papers

Cited by

References

[1]	A. Ashikhmin, A. Barg and S. Litsyn, New upper bounds on generalized weights, IEEE Trans. Inform. Theory, IT-45 (1999), 1258-1263.doi: 10.1109/18.761280.
[2]	L. A. Bassalygo, Supports of a code, in "Proc. AAECC 11,'' (1995), 1-3.
[3]	C. Bachoc, Semidefinite programming, harmonic analysis and coding theory, Lecture notes of a CIMPA course, 2009, arXiv:0909.4767
[4]	C. Bachoc, D. Gijswijt, A. Schrijver and F. Vallentin, Invariant semidefinite programs, preprint, arXiv:1007.2905
[5]	V. M. Blinovskii, Bounds for codes in the case of list decoding of finite volume, Problems of Information Transmission, 22 (1986), 7-19.
[6]	V. M. Blinovskii, Generalization of Plotkin bound to the case of multiple packing, in "ISIT 2009''.
[7]	G. Cohen, S. Litsyn and G. Zémor, Upper bounds on generalized Hamming distances, IEEE Trans. Inform. Theory, 40 (1994), 2090-2092.doi: 10.1109/18.340487.
[8]	J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups,'' Springer-Verlag, 1988.
[9]	P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., (1973), vi+97.
[10]	P. Delsarte, Hahn polynomials, discrete harmonics and $t$-designs, SIAM J. Appl. Math., 34 (1978), 157-166.doi: 10.1137/0134012.
[11]	V. Guruswami, List decoding from erasures: bounds and code constructions, IEEE Trans. Inform. Theory, IT-49 (2003), 2826-2833.doi: 10.1109/TIT.2003.815776.
[12]	V. I. Levenshtein, Universal bounds for codes and designs, in "Handbook of Coding Theory'' (eds. V. Pless and W.C. Huffmann), North-Holland, Amsterdam, (1998), 499-648.
[13]	R. J. McEliece, E. R. Rodemich, H. Rumsey and L. Welch, New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities, IEEE Trans. Inform. Theory, IT-23 (1977), 157-166.doi: 10.1109/TIT.1977.1055688.
[14]	L. H. Ozarow and A. D. Wyner, Wire-tap channel II, in "Advances in cryptology (Paris, 1984),'' Springer, Berlin, (1985), 33-50.
[15]	A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory, IT-51 (2005), 2859-2866.doi: 10.1109/TIT.2005.851748.
[16]	M. Sudan, Decoding of Reed Solomon codes beyond the error-correction bound, Journal of Complexity, 13 (1997), 180-193.doi: 10.1006/jcom.1997.0439.
[17]	F. Vallentin, Lecture notes: Semidefinite programs and harmonic analysis, preprint, arXiv:0809.2017
[18]	F. Vallentin, Symmetry in semidefinite programs, Linear Algebra and Appl., 430 (2009), 360-369.doi: 10.1016/j.laa.2008.07.025.
[19]	V. K. Wei, Generalized Hamming weights for linear codes, IEEE Trans. Inform. Theory, IT-37 (1991), 1412-1418.doi: 10.1109/18.133259.
[20]	G. Zémor, Threshold effects in codes, in "Algebraic coding (Paris, 1993),''
[21]	G. Zémor and G. Cohen, The threshold probability of a code, IEEE Trans. Inform. Theory, IT-41 (1995), 469-477.doi: 10.1109/18.370148.