American Institute of Mathematical Sciences

Advanced
November  2010, 4(4): 547-565. doi: 10.3934/amc.2010.4.547

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, France, France

Received  February 2010 Revised  July 2010 Published  November 2010

We apply Schrijver's semidefinite programming method to obtain improved upper bounds on generalized distances and list decoding radii of binary codes.
Keywords: Binary codes, pseudo-distances., semidefinite programming.
Mathematics Subject Classification: 94B65, 90C2.
Citation: Christine Bachoc, Gilles Zémor. Bounds for binary codes relative to pseudo-distances of $k$ points. Advances in Mathematics of Communications, 2010, 4 (4) : 547-565. doi: 10.3934/amc.2010.4.547
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.  Google Scholar

[2]

L. A. Bassalygo, Supports of a code, in "Proc. AAECC 11,'' (1995), 1-3. Google Scholar

[3]

C. Bachoc, Semidefinite programming, harmonic analysis and coding theory, Lecture notes of a CIMPA course, 2009, arXiv:0909.4767 Google Scholar

[4]

C. Bachoc, D. Gijswijt, A. Schrijver and F. Vallentin, Invariant semidefinite programs,, preprint, ().   Google Scholar

[5]

V. M. Blinovskii, Bounds for codes in the case of list decoding of finite volume, Problems of Information Transmission, 22 (1986), 7-19. Google Scholar

[6]

V. M. Blinovskii, Generalization of Plotkin bound to the case of multiple packing, in "ISIT 2009''. Google Scholar

[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.  Google Scholar

[8]

J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups,'' Springer-Verlag, 1988.  Google Scholar

[9]

P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., (1973), vi+97.  Google Scholar

[10]

P. Delsarte, Hahn polynomials, discrete harmonics and $t$-designs, SIAM J. Appl. Math., 34 (1978), 157-166. doi: 10.1137/0134012.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

L. H. Ozarow and A. D. Wyner, Wire-tap channel II, in "Advances in cryptology (Paris, 1984),'' Springer, Berlin, (1985), 33-50.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

F. Vallentin, Lecture notes: Semidefinite programs and harmonic analysis,, preprint, ().   Google Scholar

[18]

F. Vallentin, Symmetry in semidefinite programs, Linear Algebra and Appl., 430 (2009), 360-369. doi: 10.1016/j.laa.2008.07.025.  Google Scholar

[19]

V. K. Wei, Generalized Hamming weights for linear codes, IEEE Trans. Inform. Theory, IT-37 (1991), 1412-1418. doi: 10.1109/18.133259.  Google Scholar

[20]

G. Zémor, Threshold effects in codes, in "Algebraic coding (Paris, 1993),''  Google Scholar

[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.  Google Scholar

show all references

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

[2]

L. A. Bassalygo, Supports of a code, in "Proc. AAECC 11,'' (1995), 1-3. Google Scholar

[3]

C. Bachoc, Semidefinite programming, harmonic analysis and coding theory, Lecture notes of a CIMPA course, 2009, arXiv:0909.4767 Google Scholar

[4]

C. Bachoc, D. Gijswijt, A. Schrijver and F. Vallentin, Invariant semidefinite programs,, preprint, ().   Google Scholar

[5]

V. M. Blinovskii, Bounds for codes in the case of list decoding of finite volume, Problems of Information Transmission, 22 (1986), 7-19. Google Scholar

[6]

V. M. Blinovskii, Generalization of Plotkin bound to the case of multiple packing, in "ISIT 2009''. Google Scholar

[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.  Google Scholar

[8]

J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups,'' Springer-Verlag, 1988.  Google Scholar

[9]

P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., (1973), vi+97.  Google Scholar

[10]

P. Delsarte, Hahn polynomials, discrete harmonics and $t$-designs, SIAM J. Appl. Math., 34 (1978), 157-166. doi: 10.1137/0134012.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

L. H. Ozarow and A. D. Wyner, Wire-tap channel II, in "Advances in cryptology (Paris, 1984),'' Springer, Berlin, (1985), 33-50.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

F. Vallentin, Lecture notes: Semidefinite programs and harmonic analysis,, preprint, ().   Google Scholar

[18]

F. Vallentin, Symmetry in semidefinite programs, Linear Algebra and Appl., 430 (2009), 360-369. doi: 10.1016/j.laa.2008.07.025.  Google Scholar

[19]

V. K. Wei, Generalized Hamming weights for linear codes, IEEE Trans. Inform. Theory, IT-37 (1991), 1412-1418. doi: 10.1109/18.133259.  Google Scholar

[20]

G. Zémor, Threshold effects in codes, in "Algebraic coding (Paris, 1993),''  Google Scholar

[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.  Google Scholar

[1]

Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 613-630. doi: 10.3934/amc.2020034
[2]

Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127
[3]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881
[4]

Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015
[5]

Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187
[6]

Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225
[7]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[8]

Joaquim Borges, Ivan Yu. Mogilnykh, Josep Rifà, Faina I. Solov'eva. Structural properties of binary propelinear codes. Advances in Mathematics of Communications, 2012, 6 (3) : 329-346. doi: 10.3934/amc.2012.6.329
[9]

Cristian Dobre. Mathematical properties of the regular *-representation of matrix $*$-algebras with applications to semidefinite programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 367-378. doi: 10.3934/naco.2013.3.367
[10]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363
[11]

Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323
[12]

Rafael Arce-Nazario, Francis N. Castro, Jose Ortiz-Ubarri. On the covering radius of some binary cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 329-338. doi: 10.3934/amc.2017025
[13]

Stefka Bouyuklieva, Anton Malevich, Wolfgang Willems. On the performance of binary extremal self-dual codes. Advances in Mathematics of Communications, 2011, 5 (2) : 267-274. doi: 10.3934/amc.2011.5.267
[14]

Daniel Heinlein, Sascha Kurz. Binary subspace codes in small ambient spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 817-839. doi: 10.3934/amc.2018048
[15]

Steven T. Dougherty, Esengül Saltürk, Steve Szabo. Codes over local rings of order 16 and binary codes. Advances in Mathematics of Communications, 2016, 10 (2) : 379-391. doi: 10.3934/amc.2016012
[16]

Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[17]

Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651
[18]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117
[19]

Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2020, 14 (2) : 333-357. doi: 10.3934/amc.2020024
[20]

Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the existence of extended perfect binary codes with trivial symmetry group. Advances in Mathematics of Communications, 2009, 3 (3) : 295-309. doi: 10.3934/amc.2009.3.295

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (62)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences