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