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.

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: