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. Let d be the minimum distance of C, i.e. 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: Similarly, we define A_q(n,d,w) to be the largest size of a code in C_q(n,d,w): Theorem 1 (Johnson bound for A_q(n,d)): If d=2t+1, If d=2t+2, ** Theorem 2 (Johnson bound for A_q(n,d,w)):** (i) If d > 2w, (ii) If d \leq 2w, then define the variable e as follows. If d is even, then define e through the relation d=2e; if d is odd, define e through the relation d = 2e - 1. Let q^* = q - 1. 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 A_q(n,d).