Misplaced Pages

Johnson bound

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Second 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.

Definition

Let C {\displaystyle C} be a q-ary code of length n {\displaystyle n} , i.e. a subset of F q n {\displaystyle \mathbb {F} _{q}^{n}} . Let d {\displaystyle d} be the minimum distance of C {\displaystyle C} , i.e.

d = min x , y ∈ C , x ≠ y d ( x , y ) , {\displaystyle d=\min _{x,y\in C,x\neq y}d(x,y),}

where d ( x , y ) {\displaystyle d(x,y)} is the Hamming distance between x {\displaystyle x} and y {\displaystyle y} .

Let C q ( n , d ) {\displaystyle C_{q}(n,d)} be the set of all q-ary codes with length n {\displaystyle n} and minimum distance d {\displaystyle d} and let C q ( n , d , w ) {\displaystyle C_{q}(n,d,w)} denote the set of codes in C q ( n , d ) {\displaystyle C_{q}(n,d)} such that every element has exactly w {\displaystyle w} nonzero entries.

Denote by | C | {\displaystyle |C|} the number of elements in C {\displaystyle C} . Then, we define A q ( n , d ) {\displaystyle A_{q}(n,d)} to be the largest size of a code with length n {\displaystyle n} and minimum distance d {\displaystyle d} :

A q ( n , d ) = max C ∈ C q ( n , d ) | C | . {\displaystyle A_{q}(n,d)=\max _{C\in C_{q}(n,d)}|C|.}

Similarly, we define A q ( n , d , w ) {\displaystyle A_{q}(n,d,w)} to be the largest size of a code in C q ( n , d , w ) {\displaystyle C_{q}(n,d,w)} :

A q ( n , d , w ) = max C ∈ C q ( n , d , w ) | C | . {\displaystyle A_{q}(n,d,w)=\max _{C\in C_{q}(n,d,w)}|C|.}

Theorem 1 (Johnson bound for A q ( n , d ) {\displaystyle A_{q}(n,d)} ):

If d = 2 t + 1 {\displaystyle d=2t+1} ,

A q ( n , d ) ≤ q n ∑ i = 0 t ( n i ) ( q − 1 ) i + ( n t + 1 ) ( q − 1 ) t + 1 − ( d t ) A q ( n , d , d ) A q ( n , d , t + 1 ) . {\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{i=0}^{t}{n \choose i}(q-1)^{i}+{\frac {{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 {\displaystyle d=2t+2} ,

A q ( n , d ) ≤ q n ∑ i = 0 t ( n i ) ( q − 1 ) i + ( n t + 1 ) ( q − 1 ) t + 1 A q ( n , d , t + 1 ) . {\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{i=0}^{t}{n \choose i}(q-1)^{i}+{\frac {{n \choose t+1}(q-1)^{t+1}}{A_{q}(n,d,t+1)}}}}.}

Theorem 2 (Johnson bound for A q ( n , d , w ) {\displaystyle A_{q}(n,d,w)} ):

(i) If d > 2 w , {\displaystyle d>2w,}

A q ( n , d , w ) = 1. {\displaystyle A_{q}(n,d,w)=1.}

(ii) If d ≤ 2 w {\displaystyle d\leq 2w} , then define the variable e {\displaystyle e} as follows. If d {\displaystyle d} is even, then define e {\displaystyle e} through the relation d = 2 e {\displaystyle d=2e} ; if d {\displaystyle d} is odd, define e {\displaystyle e} through the relation d = 2 e − 1 {\displaystyle d=2e-1} . Let q ∗ = q − 1 {\displaystyle q^{*}=q-1} . Then,

A q ( n , d , w ) ≤ ⌊ n q ∗ w ⌊ ( n − 1 ) q ∗ w − 1 ⌊ ⋯ ⌊ ( n − w + e ) q ∗ e ⌋ ⋯ ⌋ ⌋ ⌋ {\displaystyle A_{q}(n,d,w)\leq \left\lfloor {\frac {nq^{*}}{w}}\left\lfloor {\frac {(n-1)q^{*}}{w-1}}\left\lfloor \cdots \left\lfloor {\frac {(n-w+e)q^{*}}{e}}\right\rfloor \cdots \right\rfloor \right\rfloor \right\rfloor }

where ⌊     ⌋ {\displaystyle \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 ) {\displaystyle A_{q}(n,d)} .

See also

References

Category: