On Delsarte's Linear Programming Bounds for Binary Codes

We prove two results about the value of Delsarte 's linear program for binary codes. Our main result is a new lower bound on the value of the program, which, in particular, is nearly tight for low rate codes. We also give an easy proof of a (known) upper bound, which coincides with the best known bound for a wide range of parameters.

Authors

• Michael Navon
• Alex Samorodnitsky

Keywords

• Linear programming
• Binary codes
• Error correction codes
• Binary sequences
• Vectors
• Upper bound
• Linear code
• Communication channels
• Random variables
• Application software
• Binary Code
• Value Of Programs
• Normal Function
• Lower Bound
• Minimum Distance
• Dimensional Vector
• Space Of Functions
• Polynomial Of Degree
• Fourier Analysis
• Forward Error Correction
• Ball Of Radius
• Symmetric Function
• Orthogonal Polynomials
• Polytope
• Noisy Channels
• Point Interval
• Technical Lemma
• Programming Solution
• Hamming Weight
• Linear Programming Approach