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

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

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

Abstract
Related Papers

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

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

[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 and 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 and Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015
[5]	Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187
[6]	Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[7]	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
[8]	Cristian Dobre. Mathematical properties of the regular -representation of matrix $$-algebras with applications to semidefinite programming. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 367-378. doi: 10.3934/naco.2013.3.367
[9]	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
[10]	René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial and 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 and 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 and 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 and 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

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Christine Bachoc Gilles Zémor
on Google Scholar
Christine Bachoc Gilles Zémor

[Back to Top]