Hamming gräns

I kodningsteori definierar Hamming-gränsen gränserna för möjliga värden för parametrarna för en godtycklig blockkod . Även känd som den sfäriska packningsgränsen . Koder som når Hamming-gränsen kallas perfekta eller tätpackade koder .

Formulering

Låt beteckna den maximala möjliga kardinaliteten av -är blocklängdskod och minsta avstånd ( -ary blocklängdskod är en undergrupp av ord med alfabet som består av element). $A_q(n,\;d)$ $q$ $C$ $n$ $d$ $q$ $n$ $\mathcal{A}_q^n$ $\mathcal{A}_q$ $q$

Sedan

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

var

t=\vänster\lgolv\frac{d-1}{2}\höger\rgolv.

Bevis

Per definition , om överföringen av kodordet skedde före fel, kommer vi med hjälp av avkodning begränsad av minimiavståndet att kunna känna igen det överförda kodordet exakt . $d$ $t=\vänster\lgolv\frac{d-1}{2}\höger\rgolv$

För ett givet kodord , överväg en sfär med radie runt . På grund av det faktum att denna kod kan korrigera fel, skär ingen sfär med någon annan och innehåller $c\in C$ $t$ $c$ $t=\vänster\lgolv\frac{d-1}{2}\höger\rgolv$

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

ord, eftersom vi kan tillåta (eller färre) tecken (av alla tecken i ett ord) att anta ett av de möjliga värdena som skiljer sig från värdet för motsvarande tecken i ett givet ord (kom ihåg att koden i sig är -ic ).

t

n

(q-1)

q

Låt beteckna antalet ord i . Genom att slå samman sfärer runt alla kodord märker vi att den resulterande uppsättningen finns i . Eftersom sfärerna är osammanhängande kan vi summera elementen i var och en av dem och få $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,

varifrån för eventuell kod $C$

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

och därför,

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

Perfekta koder

Koder som når Hamming-gränsen kallas perfekta koder . Följande typer av perfekta koder har upptäckts: Hamming -koder och Golay-koder . Det finns också triviala perfekta koder: binära koder med udda längd, koder med ett kodord och koder som inkluderar hela uppsättningen . $F_q^n$

Det bevisades av Titvainen och Van Lint att varje icke-trivial perfekt kod har parametrarna för en Hamming -kod eller en Golay-kod [1] [2] .

Anteckningar

↑ Tietavainen A., Perko A. Det finns inga okända perfekta binära koder. Annales Universitatis Turkuensis . Ser. A, I 148, 3-10[6], 1971.
↑ Lint van JH Nonexistence-satser för perfekta felkorrigerande koder. — Datorer i algebra och talteori . — Vol. IV [6], 1971.

Litteratur