Granița Johnson

Limita Johnson definește limita de putere a codului de lungime și distanța minimă . $n$ $d$

Formulare

Fie al -lea cod de lungime peste câmpul sau, cu alte cuvinte, submulțimea lui . Fie distanța minimă de cod , adică $C$ $q$ $n$ $\mathbb{F} = \mathrm{GF}(q)$ ${\mathbb {F}}_{q}^{n}$ $d$ $C$

d = \min_{x,y \in C, \; x \neq y} \mathsf{d}(x,y)

unde este distanța Hamming dintre cuvintele cod și . $\mathsf{d}(x,y)$ $X$ $y$

Fie mulțimea tuturor codurilor --lea de lungime și distanță minimă și fie denota submulțimea tuturor codurilor de echilibru în , cu alte cuvinte, toate codurile a căror greutate a tuturor cuvintelor de cod este egală cu . $C_q(n,d)$ $q$ $n$ $d$ $C_q(n,d,w)$ $C_q(n,d)$ $w$

Să notăm prin numărul de cuvinte de cod în , și prin — cardinalitatea maximă a codului de lungime și distanța minimă , i.e. $|C|$ $C$ $A_q(n,d)$ $n$ $d$

A_q(n,d) = \max_{C \in C_q(n,d)} |C|.

În mod similar, definim puterea maximă a codului în : $A_q(n,d,w)$ $C_q(n,d,w)$

A_q(n,d,w) = \max_{C \in C_q(n,d,w)} |C|.

Teorema 1 (Johnson legat pentru ): $A_q(n,d)$

La $d=2t+1$

A_q(n,d) \leq \frac{q^n}{\sum_{i=0}^t {n \choose i} (q-1)^i + \frac{{n \choose t+1} - {d \alege t} A_q(n,d,d)}{A(n,d,t+1)}(q - 1)^{t + 1} }.

Notă: pentru a găsi limita superioară pentru valorile pare , puteți utiliza următoarea egalitate $A_q(n,d)$ $d=2t$

A_q(n,2t) = A_q(n-1,2t-1).

Teorema 2 (Johnson legat pentru ): $A_q(n,d,w)$

La $d > 2w$

A_q(n,d,w) = 1.

Când lăsați , și de asemenea , atunci $d\leq 2w$ $t = \lceil \frac{d}{2}\rceil$ $q^* = q - 1$

A_q(n,d,w) \leq \lfloor \frac{nq^*}{w} \lfloor \frac{(n-1)q^*}{w-1} \lfloor \cdots \lfloor \frac{ (n-w+t)q^*}{t} \rfloor \cdots \rfloor \rfloor,

unde operatorul denotă partea întreagă a unui număr . $\lfloor ~~ \rfloor$

Notă: Înlocuind limita teoremei 2 în teorema 1, obținem o limită superioară pentru . $A_q(n,d)$

Demonstrarea primei teoreme

Fie un cod de lungime , putere cu distanță minimă , care conține un vector zero. Se notează prin mulțimea de vectori care sunt la distanță de cod , adică $C$ $n$ $M = A_q(n, d)$ $d=2t+1$ $Si}$ $i$ $C$

S_i = \left\lbrace u \in F^n: \forall v \in C\ d(u, v) \geq i \wedge \exists w \in C\ d(w, u) = i \right\rbrace .

Astfel, . Apoi , deoarece dacă ar exista un vector situat la o distanță sau mai mare de cod , atunci l-am putea adăuga și obține un cod cu o putere și mai mare. Deoarece mulțimile nu se intersectează, aceasta implică limita împachetării sferice . Pentru a obține limita dorită, estimăm puterea . $S_0 = C$ $S_0 \cup S_1 \cup \dots \cup S_{d - 1} = F^n$ $d$ $C$ $C$ $S_0, S_1, S_2, \dots, S_t$ $S_{t + 1}$

Să alegem un cuvânt de cod arbitrar și prin schimbarea corespunzătoare a codului îl vom transfera la originea coordonatelor. Cuvintele de cod de greutate formează un cod de echilibru cu o distanță minimă de cel puțin și, prin urmare, numărul de cuvinte de cod de greutate nu depășește . $P$ $d=2t+1$ $2t+1$ $d$ $A_q(n, 2t + 1, 2t + 1) = A_q(n, d, d)$

Se notează prin mulțimea vectorilor de greutate . Orice vector de la aparține fie , fie . Fiecare cuvânt de cod de greutate corespunde vectorilor de greutate care se află la o distanță de . $W_{t + 1}$ $F^{n}$ $t+1$ $W_{t + 1}$ $Sf$ $S_{t + 1}$ $Q$ $d$ ${ d \alegeți t }$ $t+1$ $Q$ $t$

Toți acești vectori sunt diferiți și aparțin mulțimii . Prin urmare, $W_{t + 1} \cap S_t$

|W_{t + 1} \cap S_{t+1}| = |W_{t + 1}| - |W_{t + 1} \cap S_t| \geq {n \choose t + 1}(q - 1)^{t + 1} - {d \choose t}(q - 1)^{t + 1} A_q(n, d, d).

Vectorul din mulțime se află la o distanță de cel mult de cuvintele cod. Într-adevăr, să mutăm originea într-un punct și să calculăm câte cuvinte de cod pot fi la o distanță și să aibă o distanță Hamming între ele . Acestea, prin definiție, nu ar trebui să fie mai mult . Prin urmare, vectorii din mulțime pot fi numărați de cele mai multe ori, adică fiecărui cuvânt de cod îi corespunde cel puțin $R$ $W_{t + 1} \cap S_{t+1}$ $t+1$ $A_q(n,d,t+1)$ $R$ $R$ $t+1$ $d$ $A_q(n,d,t+1)$ $W_{t + 1} \cap S_{t+1}$ $A_q(n,d,t+1)$ $P$

\frac{{n \alegeți t+1} - {d \alegeți t} A_q(n,d,d)}{A(n,d,t+1)}(q - 1)^{t + 1}

diferiți vectori la distanță de . $t+1$ $P$

Literatură

S. Johnson, A new upper bound for error correcting codes, IRE Transactions on Information Theory , 203–207, aprilie 1962.
FJ MacWilliams și NJA Sloane, Theory of Error-Correcting Codes , Amsterdam, Țările de Jos, Olanda de Nord, § 17.2, § 17.3, 1977.
W. C. Huffman, V. Pless, Fundamentals of Error-Correcting Codes , Cambridge University Press, 2003.

Granița Johnson

Formulare

Demonstrarea primei teoreme

Literatură

Vezi și