Johnson bound

From HandWiki
Revision as of 21:42, 6 February 2024 by StanislovAI (talk | contribs) (fix)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 [math]\displaystyle{ C }[/math] be a q-ary code of length [math]\displaystyle{ n }[/math], i.e. a subset of [math]\displaystyle{ \mathbb{F}_q^n }[/math]. Let [math]\displaystyle{ d }[/math] be the minimum distance of [math]\displaystyle{ C }[/math], i.e.

[math]\displaystyle{ d = \min_{x,y \in C, x \neq y} d(x,y), }[/math]

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

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

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

[math]\displaystyle{ A_q(n,d) = \max_{C \in C_q(n,d)} |C|. }[/math]

Similarly, we define [math]\displaystyle{ A_q(n,d,w) }[/math] to be the largest size of a code in [math]\displaystyle{ C_q(n,d,w) }[/math]:

[math]\displaystyle{ A_q(n,d,w) = \max_{C \in C_q(n,d,w)} |C|. }[/math]

Theorem 1 (Johnson bound for [math]\displaystyle{ A_q(n,d) }[/math]):

If [math]\displaystyle{ d=2t+1 }[/math],

[math]\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)} }. }[/math]

If [math]\displaystyle{ d=2t+2 }[/math],

[math]\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)} }. }[/math]

Theorem 2 (Johnson bound for [math]\displaystyle{ A_q(n,d,w) }[/math]):

(i) If [math]\displaystyle{ d \gt 2w, }[/math]

[math]\displaystyle{ A_q(n,d,w) = 1. }[/math]

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

[math]\displaystyle{ A_q(n,d,w) \leq \left\lfloor \frac{n q^*}{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 }[/math]

where [math]\displaystyle{ \lfloor ~~ \rfloor }[/math] is the floor function.

Remark: Plugging the bound of Theorem 2 into the bound of Theorem 1 produces a numerical upper bound on [math]\displaystyle{ A_q(n,d) }[/math].

See also

References