On the minimum average distance of binary codes: Linear programming approach
\textit{R. Ahlswede} and \textit{G. Katona} [Discrete Math. 17, 1-22 (1977; Zbl 0368.05001)] posed the following problem: For given \(n\) and \(M\) with \(1 \leq M \leq 2^n\), determine the minimum average Hamming distance \(\beta (n,M)\) of binary codes with length \(n\) and size \(M\). In graph-theoretic terms, this is the minimum average distance between \(M\) vertices of an \(n\)-cube. In the current paper, linear programming is used to obtain new lower bounds, which are used to determine \(\beta (n,M)\) for several families of parameters, including \(M \in \{2^{n-2}, 2^{n-2}\pm 1, 2^{n-1}\pm 2,2^{n-1}+2^{n-2}, 2^{n-1}+2^{n-2}\pm 1,2^n-2\}\). An upper bound is obtained as well, based on combining codes of size \(2^{k_i}\) and length \(k_i\) (that is, cubes), where \(M = 2^{k_1}+2^{k_2}+\cdots\) and \(k_1 > k_2 > \cdots\). This gives optimal codes -- that is, codes attaining \(\beta (n,M)\) -- in many cases but not always, since if \(M \leq n+1\) and \(M\) is large enough, then one can take the all-zero word and \(M-1\) words of weight 1 to get better codes.
- Lower bounds on the minimum average distance of binary codes
- On the average Hamming distance for binary codes
- On the minimum average distance of binary constant weight codes
- Further results on the asymptotic behaviour of minimum average Hamming distance for binary codes
- The linear programming bound for binary linear codes
- An ``average distance inequality for large subsets of the cube
- Bounds for binary codes of length less than 25
- Coding for write-efficient memory
- Contributions to the geometry of Hamming spaces
- scientific article; zbMATH DE number 4074964 (Why is no real title available?)
- scientific article; zbMATH DE number 3543912 (Why is no real title available?)
- scientific article; zbMATH DE number 1286502 (Why is no real title available?)
- On the average Hamming distance for binary codes
- On the expectation and variance of Hamming distance between two i. i. d. random vectors
- On the Hamming distance between two i.i.d. random n-tuples over a finite set
- The asymptotic behaviour of diameters in the average
- Sets of binary sequences with small total Hamming distances
- On the variance of average distance of subsets in the Hamming space
- Further results on the asymptotic behaviour of minimum average Hamming distance for binary codes
- Average distance and minimum average distance of binary constant weight code and its properties
- Minimum distance computation of linear codes via genetic algorithms with permutation encoding
- Optimal Binary Coding of Ordered Numbers
- Common Information, Noise Stability, and Their Extensions
- STOLARSKY'S INVARIANCE PRINCIPLE FOR FINITE METRIC SPACES
- On the \(\Phi \)-stability and related conjectures
- Minimum possible block length of a linear binary code for some distances
- On the minimum average distance of binary constant weight codes
- Lower bounds on the minimum average distance of binary codes
This page was built for publication: On the minimum average distance of binary codes: Linear programming approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5939230)
