Limita Hamming

În teoria codificării, granița Hamming definește limitele valorilor posibile pentru parametrii unui cod de bloc arbitrar . Cunoscută și sub denumirea de graniță sferică de ambalare . Codurile care ajung la limita Hamming se numesc coduri perfecte sau compacte .

Formulare

Să notăm cardinalitatea maximă posibilă a codului de lungime a blocului -ary și a distanței minime ( codul de lungime a blocului -ary este un subset de cuvinte cu alfabet format din elemente). $A_q(n,\;d)$ $q$ $C$ $n$ $d$ $q$ $n$ $\mathcal{A}_q^n$ $\mathcal{A}_q$ $q$

Apoi

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

Unde

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

Dovada

Prin definiție , dacă transmiterea cuvântului de cod a avut loc înainte de erori, atunci cu ajutorul decodării limitate de distanța minimă , vom putea recunoaște cu exactitate cuvântul de cod transmis . $d$ $t=\left\lfloor\frac{d-1}{2}\right\rfloor$

Pentru un anumit cuvânt de cod , luați în considerare o sferă de rază în jur . Datorită faptului că acest cod este capabil să corecteze erorile, nicio sferă nu se intersectează cu alta și conține $c\în C$ $t$ $c$ $t=\left\lfloor\frac{d-1}{2}\right\rfloor$

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

cuvinte, deoarece putem permite (sau mai puțin) caractere (dintre toate caracterele dintr-un cuvânt) să ia una dintre valorile posibile diferite de valoarea caracterului corespunzător unui cuvânt dat (reamintim că codul în sine este -ic ).

t

n

(q-1)

q

Să notăm numărul de cuvinte în . Prin gruparea sferelor în jurul tuturor cuvintelor de cod , observăm că setul rezultat este conținut în . Deoarece sferele sunt disjunctive, putem însumați elementele fiecăreia dintre ele și obținem $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,

de unde pentru orice cod $C$

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

prin urmare,

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

Codurile perfecte

Codurile care ajung la limita Hamming sunt numite coduri perfecte . Au fost descoperite următoarele tipuri de coduri perfecte: coduri Hamming și coduri Golay . Există, de asemenea, coduri perfecte banale : coduri binare de lungime impară, coduri cu un singur cuvânt de cod și coduri care includ întregul set . $F_q^n$

S-a dovedit de Titvainen și Van Lint că orice cod perfect non-trivial are parametrii unui cod Hamming sau a unui cod Golay [1] [2] .

Note

↑ Tietavainen A., Perko A. Nu există coduri binare perfecte necunoscute. Annales Universitatis Turkuensis . Ser. A, I 148, 3-10[6], 1971.
↑ Lint van JH Teoreme de inexistență pentru coduri perfecte de corectare a erorilor. — Calculatoare în algebră și teoria numerelor . — Vol. IV [6], 1971.

Literatură