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.
Definition Let C {\displaystyle C} be a q-ary code of length n {\displaystyle n} , i.e. a subset of F q n {\displaystyle \mathbb {F} _{q}^{n}} . Let d {\displaystyle d} be the minimum distance of C {\displaystyle C} , i.e.
d = min x , y ∈ C , x ≠ y d ( x , y ) , {\displaystyle d=\min _{x,y\in C,x\neq y}d(x,y),}
where d ( x , y ) {\displaystyle d(x,y)} is the Hamming distance between x {\displaystyle x} and y {\displaystyle y} . Let C q ( n , d ) {\displaystyle C_{q}(n,d)} be the set of all q-ary codes with length n {\displaystyle n} and minimum distance d {\displaystyle d} and let C q ( n , d , w ) {\displaystyle C_{q}(n,d,w)} denote the set of codes in C q ( n , d ) {\displaystyle C_{q}(n,d)} such that every element has exactly w {\displaystyle w} nonzero entries. Denote by | C | {\displaystyle |C|} the number of elements in C {\displaystyle C} . Then, we define A q ( n , d ) {\displaystyle A_{q}(n,d)} to be the largest size of a code with length n {\displaystyle n} and minimum distance d {\displaystyle d} :
A q ( n , d ) = max C ∈ C q ( n , d ) | C | . {\displaystyle A_{q}(n,d)=\max _{C\in C_{q}(n,d)}|C|.}
Similarly, we define A q ( n , d , w ) {\displaystyle A_{q}(n,d,w)} to be the largest size of a code in C q ( n , d , w ) {\displaystyle C_{q}(n,d,w)} :
A q ( n , d , w ) = max C ∈ C q ( n , d , w ) | C | . {\displaystyle A_{q}(n,d,w)=\max _{C\in C_{q}(n,d,w)}|C|.}
Theorem 1 (Johnson bound for A q ( n , d ) {\displaystyle A_{q}(n,d)} ): If d = 2 t + 1 {\displaystyle d=2t+1} ,
… excerpt ends here. Continue reading the full article.
