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.  doi: 10.1109/18.761280.  Google Scholar

[2]

L. A. Bassalygo, Supports of a code,, in, (1995), 1.   Google Scholar

[3]

C. Bachoc, Semidefinite programming, harmonic analysis and coding theory,, Lecture notes of a CIMPA course, (2009).   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.   Google Scholar

[6]

V. M. Blinovskii, Generalization of Plotkin bound to the case of multiple packing,, in, (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.  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).   Google Scholar

[10]

P. Delsarte, Hahn polynomials, discrete harmonics and $t$-designs,, SIAM J. Appl. Math., 34 (1978), 157.  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.  doi: 10.1109/TIT.2003.815776.  Google Scholar

[12]

V. I. Levenshtein, Universal bounds for codes and designs,, in, (1998), 499.   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.  doi: 10.1109/TIT.1977.1055688.  Google Scholar

[14]

L. H. Ozarow and A. D. Wyner, Wire-tap channel II,, in, (1985), 33.   Google Scholar

[15]

A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming,, IEEE Trans. Inform. Theory, IT-51 (2005), 2859.  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.  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.  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.  doi: 10.1109/18.133259.  Google Scholar

[20]

G. Zémor, Threshold effects in codes,, in, (1993).   Google Scholar

[21]

G. Zémor and G. Cohen, The threshold probability of a code,, IEEE Trans. Inform. Theory, IT-41 (1995), 469.  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.  doi: 10.1109/18.761280.  Google Scholar

[2]

L. A. Bassalygo, Supports of a code,, in, (1995), 1.   Google Scholar

[3]

C. Bachoc, Semidefinite programming, harmonic analysis and coding theory,, Lecture notes of a CIMPA course, (2009).   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.   Google Scholar

[6]

V. M. Blinovskii, Generalization of Plotkin bound to the case of multiple packing,, in, (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.  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).   Google Scholar

[10]

P. Delsarte, Hahn polynomials, discrete harmonics and $t$-designs,, SIAM J. Appl. Math., 34 (1978), 157.  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.  doi: 10.1109/TIT.2003.815776.  Google Scholar

[12]

V. I. Levenshtein, Universal bounds for codes and designs,, in, (1998), 499.   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.  doi: 10.1109/TIT.1977.1055688.  Google Scholar

[14]

L. H. Ozarow and A. D. Wyner, Wire-tap channel II,, in, (1985), 33.   Google Scholar

[15]

A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming,, IEEE Trans. Inform. Theory, IT-51 (2005), 2859.  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.  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.  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.  doi: 10.1109/18.133259.  Google Scholar

[20]

G. Zémor, Threshold effects in codes,, in, (1993).   Google Scholar

[21]

G. Zémor and G. Cohen, The threshold probability of a code,, IEEE Trans. Inform. Theory, IT-41 (1995), 469.  doi: 10.1109/18.370148.  Google Scholar

[1]

Akbar Mahmoodi Rishakani, Seyed Mojtaba Dehnavi, Mohmmadreza Mirzaee Shamsabad, Nasour Bagheri. Cryptographic properties of cyclic binary matrices. Advances in Mathematics of Communications, 2021, 15 (2) : 311-327. doi: 10.3934/amc.2020068
[2]

Vo Van Au, Hossein Jafari, Zakia Hammouch, Nguyen Huy Tuan. On a final value problem for a nonlinear fractional pseudo-parabolic equation. Electronic Research Archive, 2021, 29 (1) : 1709-1734. doi: 10.3934/era.2020088
[3]

Nguyen Huy Tuan, Vo Van Au, Runzhang Xu. Semilinear Caputo time-fractional pseudo-parabolic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020282
[4]

Nguyen Anh Tuan, Donal O'Regan, Dumitru Baleanu, Nguyen H. Tuan. On time fractional pseudo-parabolic equations with nonlocal integral conditions. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020109
[5]

Stanislav Nikolaevich Antontsev, Serik Ersultanovich Aitzhanov, Guzel Rashitkhuzhakyzy Ashurova. An inverse problem for the pseudo-parabolic equation with p-Laplacian. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021005
[6]

Andrea Giorgini, Roger Temam, Xuan-Truong Vu. The Navier-Stokes-Cahn-Hilliard equations for mildly compressible binary fluid mixtures. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 337-366. doi: 10.3934/dcdsb.2020141
[7]

Yuyuan Ouyang, Trevor Squires. Some worst-case datasets of deterministic first-order methods for solving binary logistic regression. Inverse Problems & Imaging, 2021, 15 (1) : 63-77. doi: 10.3934/ipi.2020047
[8]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054
[9]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[10]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[11]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012
[12]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136
[13]

Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020124
[14]

Liang Huang, Jiao Chen. The boundedness of multi-linear and multi-parameter pseudo-differential operators. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020291
[15]

Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162
[16]

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013
[17]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118
[18]

Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129
[19]

Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044
[20]

San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038

2019 Impact Factor: 0.734

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences