Institute of Information Science - University of Miskolc

A redundancia növelésével automatikus hibajavítás is végezhető. Ha m adatbitünk van, akkor ehhez rendeljünk r darab redundáns paritásbitet, így a teljes bithossz n:

$$ n = m + r. $$

Ha adott két kódszó, pl: 00101110 és 00111110 és ezek 1 bitben térnek el egymástól, akkor a kódszavak Hamming távolsága 1.

Ez egy érdekes távolság fajta, mert nem függ attól, hogy a hányadik bit különbözik, és attól sem, hogy ezen a helyen bináris vagy tízes számrendszerbeli szám áll. Tehát pl. 45635263 és 45615263 két szónak is 1 a Hamming távolsága, hiába a hibás helyen még 8-féle más szimbólum is állhatna!

Ennek az a jelentősége, hogy ha két kódszó távolsága d, akkor d darab egyszeres bithibának kell lennie ahhoz, hogy az egyik kódszó a másikba alakulhasson.

Például az 11110001 és a 00110000 Hamming távolsága 3, mert 3 egyszeres bithiba szükséges ahhoz, hogy az egyik a másikba alakulhasson.

d egyszeres bithiba felismeréséhez \(d + 1\) távolságú kódolás kell, mert ebben az esetben d egyszeres bithiba semmiféleképpen nem alakíthat át egy érvényes kódszót egy másik érvényes kódszóvá.

Az egyszeres bithibák javításához a Hamming-kódokban szükséges paritásbitek számát a következőképpen lehet meghatározni:

Ha a kódolt üzenet m adatbitet tartalmaz, akkor legalább r paritásbit szükséges, ahol r olyan, hogy teljesüljön az egyenlőtlenség:

$$ 2^r \geq m + r + 1. $$ $$ 2^r \geq n + 1. $$

Ez azt jelenti, hogy az r paritásbitnek képesnek kell lennie megkülönböztetni a \(m+r+1\) különböző állapotot (beleértve a hibamentes állapotot és az összes lehetséges hibás bitpozíciót).