Johnson bound

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.

be a q-ary code of length

, i.e. a subset of

be the minimum distance of

is the Hamming distance between

be the set of all q-ary codes with length

and minimum distance

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

, Theorem 2 (Johnson bound for

(ii) If

, then define the variable

is even, then define

through the relation

is odd, define

is the floor function.

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