Hamming határ

A kódoláselméletben a Hamming-határ határozza meg egy tetszőleges blokkkód paramétereinek lehetséges értékeinek határait . Más néven gömb alakú csomagolási határ . Azokat a kódokat, amelyek elérik a Hamming-határt, tökéletes vagy szorosan csomagolt kódoknak nevezzük .

Megfogalmazás

Jelölje az -ary blokkhossz kód és a minimális távolság maximális lehetséges számosságát ( -ary blokkhossz kód a szavak egy részhalmaza , ábécé elemekből áll ). $A_q(n;\;d)$ $q$ $C$ $n$ $d$ $q$ $n$ $\mathcal{A}_q^n$ $\mathcal{A}_q$ $q$

Akkor

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

ahol

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

Bizonyítás

Értelemszerűen , ha a kódszó továbbítása hibák előtt történt , akkor a minimális távolsággal korlátozott dekódolás segítségével pontosan felismerjük a továbbított kódszót . $d$ $t=\left\lfloor\frac{d-1}{2}\right\rfloor$

Egy adott kódszóhoz tekintsünk egy sugarú gömböt a körül . Tekintettel arra, hogy ez a kód képes a hibák kijavítására, egyetlen gömb sem metszi egymást, és nem tartalmaz $c\in C$ $t$ $c$ $t=\left\lfloor\frac{d-1}{2}\right\rfloor$

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

szavakat, mivel megengedhetjük (vagy kevesebb) karakternek (egy szó összes karakteréből), hogy az adott szó megfelelő karakterének értékétől eltérő lehetséges értékek egyikét vegye fel (emlékezzünk rá, hogy maga a kód -ic ) ).

t

n

(q-1)

q

Legyen jelölje a szavak számát . Ha az összes kódszó köré gömböket egyesítünk , akkor észrevesszük, hogy az eredményül kapott halmaz a . Mivel a gömbök diszjunktak, így mindegyik elemét összegezhetjük, és megkaphatjuk $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,

honnan bármilyen kódra $C$

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

és ezért,

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

Tökéletes kódok

A Hamming-határt elérő kódokat tökéletes kódoknak nevezzük . A tökéletes kódok következő típusait fedezték fel: Hamming kódok és Golay kódok . Vannak triviális tökéletes kódok is: páratlan hosszúságú bináris kódok, egy kódszót tartalmazó kódok és olyan kódok, amelyek a teljes készletet tartalmazzák . $F_q^n$

Titvainen és Van Lint bebizonyította, hogy minden nem triviális tökéletes kód rendelkezik egy Hamming- vagy egy Golay-kód paramétereivel [1] [2] .

Jegyzetek

↑ Tietavainen A., Perko A. Nincsenek ismeretlen tökéletes bináris kódok. Annales Universitatis Turkuensis . Ser. A, I 148, 3-10[6], 1971.
↑ Lint van JH Nemlétezési tételek a tökéletes hibajavító kódokhoz. — Számítógépek az algebrában és a számelméletben . — Vol. IV [6], 1971.

Irodalom