In applied mathematics, the Johnson bound (named after Selmer Martin Johnson) is a limit on the size of error-correcting codes, as used in coding theory for data transmission or communications.
Let C be a q-ary code of length n , i.e. a subset of F q n . Let d be the minimum distance of C , i.e.
d = min x , y ∈ C , x ≠ y d ( x , y ) , where d ( x , y ) is the Hamming distance between x and y .
Let C q ( n , d ) be the set of all q-ary codes with length n and minimum distance d and let C q ( n , d , w ) denote the set of codes in C q ( n , d ) such that every element has exactly w nonzero entries.
Denote by | C | the number of elements in C . Then, we define A q ( n , d ) to be the largest size of a code with length n and minimum distance d :
A q ( n , d ) = max C ∈ C q ( n , d ) | C | . Similarly, we define A q ( n , d , w ) to be the largest size of a code in C q ( n , d , w ) :
A q ( n , d , w ) = max C ∈ C q ( n , d , w ) | C | . Theorem 1 (Johnson bound for A q ( n , d ) ):
If d = 2 t + 1 ,
A q ( n , d ) ≤ q n ∑ i = 0 t ( n i ) ( q − 1 ) i + ( n t + 1 ) ( q − 1 ) t + 1 − ( d t ) A q ( n , d , d ) A q ( n , d , t + 1 ) . If d = 2 t ,
A q ( n , d ) ≤ q n ∑ i = 0 t ( n i ) ( q − 1 ) i + ( n t + 1 ) ( q − 1 ) t + 1 A q ( n , d , t + 1 ) . Theorem 2 (Johnson bound for A q ( n , d , w ) ):
(i) If d > 2 w ,
A q ( n , d , w ) = 1. (ii) If d ≤ 2 w , then define the variable e as follows. If d is even, then define e through the relation d = 2 e ; if d is odd, define e through the relation d = 2 e − 1 . Let q ∗ = q − 1 . Then,
A q ( n , d , w ) ≤ ⌊ n q ∗ w ⌊ ( n − 1 ) q ∗ w − 1 ⌊ ⋯ ⌊ ( n − w + e ) q ∗ e ⌋ ⋯ ⌋ ⌋ ⌋ where ⌊ ⌋ is the floor function.
Remark: Plugging the bound of Theorem 2 into the bound of Theorem 1 produces a numerical upper bound on A q ( n , d ) .
