Johnson bound

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 be a q-ary code of length , i.e. a subset of . Let be the minimum distance of , i.e.

where is the Hamming distance between and .

Let be the set of all q-ary codes with length and minimum distance and let denote the set of codes in such that every element has exactly nonzero entries.

Denote by the number of elements in . Then, we define to be the largest size of a code with length and minimum distance :

Similarly, we define to be the largest size of a code in :

Theorem 1 (Johnson bound for ):

If ,

If ,

Theorem 2 (Johnson bound for ):

(i) If

(ii) If , then define the variable as follows. If is even, then define through the relation ; if is odd, define through the relation . Let . Then,

where is the floor function.

Remark: Plugging the bound of Theorem 2 into the bound of Theorem 1 produces a numerical upper bound on .

See also[edit]