Johnsonin raja

Johnsonin raja määrittelee pituuskoodin tehorajan ja minimietäisyyden . $n$ $d$

Sanamuoto

Antaa olla -th pituinen koodi kentän päällä tai toisin sanoen :n osajoukko . Olkoon koodin minimietäisyys , ts . $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)

missä on Hamming- etäisyys koodisanojen ja . $\mathsf{d}(x,y)$ $x$ $y$

Antaa olla joukko kaikista -th koodit pituus ja pienin etäisyys , ja anna merkitsee osajoukko kaikkien tasapainokoodit , toisin sanoen kaikki koodit, joiden paino kaikki koodisanat on yhtä suuri . $C_q(n,d)$ $q$ $n$ $d$ $C_q(n,d,w)$ $C_q(n,d)$ $w$

Merkitään koodisanojen lukumäärällä , ja — pituuskoodin maksimikardinaliteetti ja pienin etäisyys , ts. $|C|$ $C$ $A_q(n,d)$ $n$ $d$

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

Samoin määrittelemme koodin maksimitehoksi : $A_q(n,d,w)$ $C_q(n,d,w)$

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

Lause 1 (Johnson matkalla kohti ): $A_q(n,d)$

klo $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 \choose t} A_q(n,d,d)}{A(n,d,t+1)}(q - 1)^{t + 1} }.

Huomaa: löytääksesi ylärajan parillisille arvoille , voit käyttää seuraavaa yhtälöä $A_q(n,d)$ $d = 2t$

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

Lause 2 (Johnson matkalla kohti ): $A_q(n,d,w)$

klo $d > 2w$

A_q(n,d,w) = 1.

Kun anna , ja myös silloin $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,

jossa operaattori merkitsee luvun kokonaislukuosaa . $\lfloor ~~ \rfloor$

Huomautus: Korvaamalla Lauseen 2 rajan lauseeseen 1, saadaan yläraja . $A_q(n,d)$

Ensimmäisen lauseen todistus

Antaa olla koodi pituus , teho vähimmäisetäisyys , joka sisältää nollavektorin. Merkitään joukolla vektoreita, jotka ovat etäisyyden päässä koodista , eli $C$ $n$ $M = A_q(n, d)$ $d=2t+1$ $Si}$ $i$ $C$

S_i = \vasen\lsulku u \in F^n: \forall v \in C\ d(u, v) \geq i \wedge \exists w \in C\ d(w, u) = i \oikea\rhakasulku .

Siten ,. Sitten , koska jos vektori sijaitsisi etäisyydellä tai kauempana koodista , voisimme lisätä sen koodiin ja saada vielä suuremman tehon koodin. Koska joukot eivät leikkaa toisiaan, tämä merkitsee pallomaisen pakkauksen rajaa . Halutun rajan saamiseksi arvioimme tehon . $S_0 = C$ $S_0 \kuppi S_1 \kuppi \pisteet \kuppi S_{d - 1} = F^n$ $d$ $C$ $C$ $S_0, S_1, S_2, \pisteet, S_t$ $S_{t + 1}$

Valitaan mielivaltainen koodisana ja siirretään koodia sopivalla siirrolla koordinaattien alkupisteeseen. Painokoodisanat muodostavat tasapainokoodin , jonka vähimmäisetäisyys on vähintään , ja siksi painokoodisanojen määrä ei ylitä . $P$ $d=2t+1$ $2t+1$ $d$ $A_q(n, 2t + 1, 2t + 1) = A_q(n, d, d)$

Merkitään painovektorijoukolla . _ Mikä tahansa vektori kohteesta kuuluu joko , tai . Jokainen painokoodisana vastaa painovektoreita , jotka ovat etäisyyden päässä . $W_{t + 1}$ $F^{n}$ $t+1$ $W_{t + 1}$ $S_t$ $S_{t + 1}$ $K$ $d$ ${ d \valitse t }$ $t+1$ $K$ $t$

Kaikki nämä vektorit ovat erilaisia ja kuuluvat joukkoon . Näin ollen $W_{t + 1} \cap S_t$

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

Vektori joukosta on enintään koodisanojen etäisyydellä. Todellakin, siirretään origo johonkin pisteeseen ja lasketaan kuinka monta koodisanaa voi olla etäisyyden päässä ja niiden välillä voi olla Hamming-etäisyys . Niitä ei määritelmän mukaan pitäisi olla enemmän . Siksi vektorit joukosta voidaan laskea korkeintaan , eli jokainen koodisana vastaa vähintään $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 \choose t+1} - {d \choose t} A_q(n,d,d)}{A(n,d,t+1)}(q - 1)^{t + 1}

eri vektoreita etäisyyden päässä kohteesta . $t+1$ $P$

Kirjallisuus

S. Johnson, Virheenkorjauskoodien uusi yläraja, IRE Transactions on Information Theory , 203–207, huhtikuu 1962.
FJ MacWilliams ja NJA Sloane, Theory of Error-Correcting Codes , Amsterdam, Alankomaat, Pohjois-Hollanti, § 17.2, § 17.3, 1977.
W. C. Huffman, V. Pless, Fundamentals of Error-Correcting Codes , Cambridge University Press, 2003.

Johnsonin raja

Sanamuoto

Ensimmäisen lauseen todistus

Kirjallisuus

Katso myös