8 Johnson Bound
8.1 Overview
This chapter proves the binary Johnson bound: for a binary code \(C\) of length \(n\) with minimum distance \(d\), if every codeword has weight at most \(w \le J_2(n,d)\) where
then \(|C| \le 2n\).
The proof reduces to a Rankin bound from geometry: a set of unit vectors in \(\mathbb {R}^n\) with pairwise non-positive inner products has size at most \(2n\). Codewords are embedded via a shifted \(\{ \pm 1\} \) map so that the distance and weight constraints force the inner-product condition.
8.2 Basic definitions
A binary codeword of length \(n\) is a function \(\mathrm{Fin}\, n \to \mathrm{Bool}\).
The Hamming weight \(\mathrm{wt}(x) = |\{ i : x_i = 1\} |\); the Hamming distance \(\mathrm{hdist}(x,y) = \mathrm{wt}(x \oplus y)\).
A code \(C \subseteq \{ 0,1\} ^n\) is \((n,d,w)\)-admissible if every pair of distinct codewords has Hamming distance \(\ge d\) and every codeword has weight \(\le w\).
8.3 Embedding and inner-product bounds
Map \(x \in \{ 0,1\} ^n\) to the vector \(\hat{x}^\alpha _i = (-1)^{x_i} - \alpha \) (with \(\alpha \ge 0\)), viewed in \(\mathbb {R}^n\).
\(\langle \hat{x},\hat{y}\rangle = n - 2\, \mathrm{hdist}(x,y)\).
For \(\alpha \ge 0\), \(\mathrm{hdist}(x,y) \ge d\), and \(\mathrm{wt}(x),\mathrm{wt}(y) \le w\),
If \(n \gt 0\), \(1 \le d\), \(2d \le n\), and \(w \le J_2(n,d)\), then \((n - 2d) + \alpha ^2 n + 2\alpha (2w - n) \le 0\) for the choice \(\alpha = \alpha (n,d)\).
8.4 Rankin bound
In a finite inner-product space, if a set \(S\) of unit vectors has pairwise non-positive inner products, then one can project away one vector and reduce to a smaller set in the orthogonal complement with the same property.
A set of unit vectors in an \(n\)-dimensional real inner product space with pairwise non-positive inner products has size at most \(2n\).
A finite set of unit vectors in \(\mathbb {R}^n\) with pairwise non-positive inner products has cardinality at most \(2n\).
8.5 Johnson bound
Let \(C \subseteq \{ 0,1\} ^n\) be a code with minimum distance \(\ge d\) and all weights \(\le w\). For any \(\alpha \ge 0\) with \((n-2d) + \alpha ^2 n + 2\alpha (2w-n) \le 0\),
If \(n \gt 0\), \(1 \le d\), \(2d \le n\), and all codewords of \(C\) have weight \(\le w \le J_2(n,d)\) and minimum distance \(\ge d\), then \(|C| \le 2n\).
Every \((n,d,w)\)-admissible code \(C\) with \(w \le J_2(n,d)\) satisfies \(|C| \le 2n\).
\(A_0(n,d,w)\) is the maximum size of an \((n,d,w)\)-admissible code.
If \(n \gt 0\), \(1 \le d\), \(2d \le n\), and \(w \le J_2(n,d)\), then