Johnson bound explained

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 be a q-ary code of length n , i.e. a subset of F ^{n} _{q} . Let d be the minimum distance of C , i.e.d = min _{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 \in 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 \in C _{q(n,d,w)}} |C|.

Theorem 1 (Johnson bound for

A _{q(n,d)} ):

If

d =2 t +1 ,A _{q(n,d)} \leq (q ^{n})/(\sum ^{t} _{i =0} {n \choose i) (q -1 ) ^{i} + ({n \choose t +1)/((q -1 )) ^{t+1} - {d \choose t} A _{q(n,d,d)}{A} _{q(n,d,t+1)}} }.

If

d =2 t +2 ,A _{q(n,d)} \leq (q ^{n})/(\sum ^{t} _{i =0} {n \choose i) (q -1 ) ^{i} + ({n \choose 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 \leq 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)} \leq \left\lfloor (n q ^{*})/(w) \left\lfloor ((n -1 )q ^{*})/(w -1) \left\lfloor … \left\lfloor ((n - w + e)q ^{*})/(e) \right\rfloor … \right\rfloor \right\rfloor \right\rfloor

where

\lfloor ~~ \rfloor 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)} .

See also

• Elias Bassalygo bound
• Gilbert–Varshamov bound
• Griesmer bound
• Hamming bound
• Plotkin bound
• Singleton bound

References

• Selmer Martin . Johnson . Selmer Martin Johnson . A new upper bound for error-correcting codes . . 203–207 . April 1962.
• Book: William Cary . Huffman . Vera S. . Pless . Vera Pless . Fundamentals of Error-Correcting Codes . registration . . 2003 . 978-0-521-78280-7.