Hammingin raja

Koodausteoriassa Hamming-raja määrittelee mahdollisten arvojen rajat mielivaltaisen lohkokoodin parametreille . Tunnetaan myös pallomaisena pakkausrajana . Koodeja, jotka saavuttavat Hamming-rajan, kutsutaan täydellisiksi tai tiiviiksi pakatuiksi koodeiksi .

Sanamuoto

Olkoon -ary lohkon pituuskoodin suurin mahdollinen kardinaliteetti ja pienin etäisyys ( -ary lohkon pituuskoodi on osajoukko sanoja , joiden aakkoset koostuvat elementeistä). $A_q(n,\;d)$ $q$ $C$ $n$ $d$ $q$ $n$ $\mathcal{A}_q^n$ $\mathcal{A}_q$ $q$

Sitten

A_q(n,\;d)\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k},

missä

t=\left\lfloor\frac{d-1}{2}\right\rfloor.

Todiste

Määritelmän mukaan jos koodisanan lähetys tapahtui ennen virheitä, niin minimietäisyyden rajoittaman dekoodauksen avulla pystymme tunnistamaan lähetetyn koodisanan tarkasti . $d$ $t=\left\lfloor\frac{d-1}{2}\right\rfloor$

Tarkastellaan tietyn koodisanan ympäryspalloa , jonka säde on . Koska tämä koodi pystyy korjaamaan virheet, mikään pallo ei leikkaa minkään muun kanssa ja sisältää $c\in C$ $t$ $c$ $t=\left\lfloor\frac{d-1}{2}\right\rfloor$

\sum_{k=0}^t \binom{n}{k}(q-1)^k

sanoja, koska voimme sallia (tai vähemmän) merkkien (kaikista sanan merkeistä) ottaa yhden mahdollisista arvoista, jotka poikkeavat tietyn sanan vastaavan merkin arvosta (muista, että itse koodi on -ic ).

t

n

(q-1)

q

Antaa tarkoittaa sanojen määrää . Yhdistämällä palloja kaikkien koodisanojen ympärille huomaamme, että tuloksena oleva joukko sisältyy sanaan . Koska pallot ovat epäyhtenäisiä, voimme summata kunkin niistä elementit ja saada $M$ $C$ $\mathcal{A}_q^n$

M\times\sum_{k=0}^t\binom{n}{k}(q-1)^k\leqslant|\mathcal{A}_q^n|=q^n,

mistä tahansa koodista $C$

M\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k},

ja siksi,

A_q(n,\;d)\leqslant\frac{q^n}{\displaystyle\sum_{k=0}^t\binom{n}{k}(q-1)^k}.

Täydelliset koodit

Koodeja, jotka saavuttavat Hamming-rajan, kutsutaan täydellisiksi koodeiksi . Seuraavan tyyppisiä täydellisiä koodeja on löydetty: Hamming -koodit ja Golay-koodit . On myös triviaaleja täydellisiä koodeja: parittoman pituisia binäärikoodeja, koodeja, joissa on yksi koodisana, ja koodeja, jotka sisältävät koko joukon . $F_q^n$

Titvainen ja Van Lint osoittivat, että millä tahansa ei-triviaalilla täydellisellä koodilla on Hamming- tai Golay-koodin parametrit [1] [2] .

Muistiinpanot

↑ Tietavainen A., Perko A. Ei ole olemassa tuntemattomia täydellisiä binäärikoodeja. Annales Universitatis Turkuensis . Ser. A, I 148, 3-10[6], 1971.
↑ Lint van JH Olemattomuuslauseet täydellisiin virheenkorjauskoodeihin. — Algebran ja lukuteorian tietokoneet . — Voi. IV [6], 1971.

Kirjallisuus