Plotkin raja

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 9. heinäkuuta 2014 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Plotkin -raja - koodausteoriassa määrittää pituuden ja minimietäisyyden binäärikoodin tehorajan . Se on nimetty amerikkalaisen matemaatikon Morris Plotkinin (1907-2003) mukaan. $n$ $d$

Sanamuoto

Antaa olla binäärikoodi pituus tai toisin sanoen osajoukko . Olkoon koodin minimietäisyys , ts. $C$ $n$ $\mathbb{F}_2^n$ $d$ $C$

d=\min_{\begin{smallmatrix}x,\;y\in C,\\x\neq y\end{smallmatrix}}d(x,\;y),

missä on Hamming-etäisyys välillä ja . Lauseke ilmaisee suurinta mahdollista koodisanojen määrää pituuden ja vähimmäisetäisyyden binäärikoodissa . Plotkinin rajoitus antaa tälle lausekkeelle ylärajan. $d(x,\;y)$ $x$ $y$ $A_2(n,\;d)$ $n$ $d$

Lause (Plotkin-sidottu):

1. Jos on parillinen luku , niin $d$ $2d>n$

A_2(n,\;d)\leqslant 2\left\lfloor\frac{d}{2d-n}\right\rfloor.

2. Jos on pariton luku ja , sitten $d$ $2d+1>n$

A_2(n,\;d)\leqslant 2\left\lfloor\frac{d+1}{2d+1-n}\right\rfloor.

3. Jos on parillinen luku, niin $d$

A_2(2d,\;d)\leqslant 4d.

4. Jos on pariton luku, niin $d$

A_2(2d+1,\;d)\leqslant 4d+4,

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

Todiste ensimmäisestä osasta

Antaa olla Hamming - etäisyys ja , Ja on valta . Etsitään arvon raja kahdella eri tavalla. $d(x,\;y)$ $x$ $y$ $M$ $C$ $\sum_{x,\;y\in C}d(x,\;y)$

Toisaalta on olemassa erilaisia vaihtoehtoja, joista valita , ja jokaiselle niistä on vaihtoehtoja, joista valita . Määritelmän mukaan kaikille ja siksi $M$ $x$ $M-1$ $y$ $d(x,\;y)\geqslant d$ $x$ $y$

\sum_{x,\;y\in C}d(x,\;y)\geqslant M(M-1)d.

Toisaalta määritämme dimensioiden matriisin , jonka rivit ovat koodielementtejä . Jos on nollien määrä matriisin sarakkeessa , niin sarake sisältää ykkösiä. Mikä tahansa nolla ja yksi samassa sarakkeessa lisäävät täsmälleen (koska ) kokonaissummaan , mikä tarkoittaa $A$ $M\ kertaa n$ $C$ $si}$ $i$ $A$ $i$ $M-s_i$ $2$ $d(x,\;y)=d(y,\;x)$ $\sum_{x,\;y\in C}d(x,\;y)$

\sum_{x,\;y\in C}d(x,\;y)=\sum_{i=1}^n 2s_i(M-s_i).

Parille tasa-arvon oikealla puolella oleva arvo saavuttaa maksimiarvon klo , mikä tarkoittaa $M$ $s_i=M/2$

\sum_{x,\;y\in C}d(x,\;y)\leqslant\frac{1}{2}nM^2.

Yhdistämällä lausekkeen ala- ja ylärajat yhdeksi epäyhtälöksi saadaan $\sum_{x,\;y\in C}d(x,\;y)$

M(M-1)d\leqslant\frac{1}{2}nM^2,

joka on vastaava ehdolla $2d>n$

M\leqslant\frac{2d}{2d-n}.

Koska on siis parillinen luku $M$

M\leqslant 2\left\lfloor\frac{d}{2d-n}\right\rfloor.

Toisaalta, jos pariton, niin saavuttaa maksimin klo , josta se seuraa sitä $M$ $\sum_{i=1}^n 2s_i(M-s_i)$ $s_i=\frac{M\pm1}{2}$

\sum_{x,\;y\in C}d(x,\;y)\leqslant\frac{1}{2}n(M^2-1).

Yhdistämällä lausekkeen ala- ja ylärajat yhdeksi epäyhtälöksi saadaan $\sum_{x,\;y\in C}d(x,\;y)$

M(M-1)d\leqslant\frac{1}{2}n(M^2-1),

joka on vastaava ehdolla $2d>n$

M\leqslant\frac{2d}{2d-n}-1.

Koska on siis kokonaisluku $M$

M\leqslant\left\lfloor\frac{2d}{2d-n}-1\right\rfloor=\left\lfloor\frac{2d}{2d-n}\right\rfloor-1\leqslant 2\left\ lfloor\frac{d}{2d-n}\right\rfloor,

joka täydentää ensimmäisen osan todistuksen.

Todiste toisesta osasta

Jotta saataisiin tarvittava epäyhtälö, meidän on todistettava seuraava lemma.

Lemma 1

A(n,\;2r-1)=A(n+1,\;2r).

Todiste lemasta

Olkoon se -koodi. Lisäämällä pariteettitarkistukseen saamme -koodin, mikä viittaa siihen $C$ $(n,\;M,\;2r-1)$ $C$ $(n+1,\;M,\;2r)$

A_2(n,\;2r-1)\leqslant A_2(n+1,\;2r).

Päinvastaisessa suunnassa yhden koordinaatin heittäminen ulos tietyssä -koodissa johtaa -koodiin, joten $(n+1,\;M,\;2r)$ $(n,\;M,\;d\geqslant 2r-1)$

A_2(n,\;2r-1)\geqslant A_2(n+1,\;2r).

Vaadittu tulos seuraa todistuksen ensimmäisestä osasta ja Lemmasta 1.

Todiste kolmannesta osasta

Todistamme jälleen ensin seuraavan apuväitteen.

Lemma 2

A_2(n,\;d)\leqslant 2A_2(n-1,\;d).

Todiste lemasta

Tietyssä -koodissa jaamme kaikki koodisanat kahteen luokkaan, jaamme yhdelle luokalle nollalla alkavat sanat ja toiselle ne, jotka alkavat yhdellä. Yksi näistä luokista sisältää vähintään puolet koodisanoista, mikä tarkoittaa $(n,\;M,\;d)$

A_2(n-1,\;d)\geqslant\frac{A_2(n,\;d)}{2}.

Todistuksen ensimmäisestä osasta ja Lemmasta 2 seuraa, että

A_2(4r,\;2r)\leqslant 2A_2(4r-1,\;2r)\leqslant 8r.

Haluttu tulos saadaan korvaamalla . $d = 2r$

Todiste neljännestä osasta

Lemma 1 viittaa siihen

A_2(2d+1,\;d)=A_2(2d+2,\;d+1).

Koska ja ovat parillisia lukuja, voimme käyttää todistuksen kolmannen osan tulosta: $2p+2$ $d+1$

A_2(2d+2,\;d+1)=A_2(2(d+1),\;d+1)\leqslant 4(d+1)=4d+4,

joka täydentää koko lauseen todistuksen.

Codes Achieving the Plotkin Bound

Jos on olemassa kaikkien mahdollisten kertalukujen Hadamard-matriiseja (mitä ei kuitenkaan ole vielä todistettu), niin yhtäläisyydet pätevät lauseen kaikissa osissa. Siten Plotkinin rajoitus on täsmällinen siinä mielessä, että on olemassa koodeja , jotka saavuttavat tämän rajoituksen [1] .

Muistiinpanot

↑ Levenshtein V. I. Hadamard-matriisien soveltaminen yhteen koodaustehtävään. — Kybernetiikan ongelmat . - 5:123-136 [2A], 1961.

Kirjallisuus

Plotkin M. Binäärikoodit tietyllä vähimmäisetäisyydellä. — Kyberneettinen kokoelma . - Moskova, 7:60-73 [2], 1963.
FJ MacWilliams ja NJA Sloane. Virheenkorjauskoodien teoria . - Amsterdam, Alankomaat, Pohjois-Hollanti, § 2.2, 1977.