Co je Hammingův zákon?

Hammingův kód je metoda pro detekci a opravu chyb v binárním přenosu. Děje se tak zahrnutím dalších binárních číslic do sekvence, která se používá pro kontrolu, jakož i algoritmu, který poskytuje detekční logiku. Takový kód je schopen najít dvě chyby v libovolném sledu bitů a opravit jeden bit, který může být nesprávný. Nejběžněji uváděný Hammingův kód je známý jako Hamming (7,4), kde čtyři označují původní počet počátečních bitů a sedm představuje celkový počet bitů v sekvenci poté, co byly zahrnuty další kontrolní bity.

Tato technika získala jméno od svého tvůrce, Richarda Hamminga, který metodu publikoval v roce 1950. Způsob, jakým Hammingův kód funguje, je převzetím řetězce bitů a vložením dalších kontrolních bitů, označovaných jako paritní bity, do sekvence. Kontrolní bity jsou vždy injektovány do pozice, která je mocna dvou, takže jakýkoli počet bitů může být ověřen zahrnutím dalších paritních bitů. To může pokračovat, dokud poslední paritní bit přidaný do sekvence není v poloze, která je výkonem dvou, který je menší nebo roven konečné poloze v sekvenci.

Když jsou všechny paritní bity na místě, zbývající pozice jsou skutečné datové bity. V případě čtyřbitového příkladu by tedy bitové pozice jedna, dvě a čtyři byly paritní bity, zatímco pozice tři, pět, šest a sedm jsou data. Jakmile je tato posloupnost zavedena, logika Hammingova kódu funguje.

V Hammingově kódu se každý z paritních bitů, které byly přidány do sekvence, používá ke kontrole některých bitových pozic, ke kterým jsou blízko, včetně sebe samých. Paritní bit na pozici jedna kontroluje každou další bitovou pozici, což je v podstatě každá lichá pozice v sekvenci. Druhý paritní bit v pozici dva kontroluje pozice dvě a tři, poté přeskočí dvě pozice, zkontroluje další dvě pozice, přeskočí další dvě a tak dále. Pokud je v pozici čtyři paritní bit, jedná podobně jako v tom, že kontroluje pozice čtyři až sedm, poté přeskočí čtyři pozice, zkontroluje další čtyři a dále. Každý paritní bit v sekvenci pokračuje tímto způsobem po celou sekvenci.

Proces, kterým Hammingův kód detekuje a opravuje chybu, je spočítání bitů v kontrolní sekvenci pro každou kontrolu parity, z nichž každý musí vycházet sudé číslo. V případě sedmibitového příkladu se pro první kontrolu parity sčítají bity jedna, tři, pět a sedm. Pokud je součet sudé číslo, parita se odhlásí, ale pokud je součet lichý, dojde k chybě. Protože se kontroly parity překrývají, objeví se dvě takové chyby. Když se dvě paritní bitové pozice, které nedokáží přijít s sudými součty, sečtou, odhalí bit, který je třeba opravit.

V příkladu sedmibitového Hammingova kódu zvažte, že bit na pozici číslo pět je nesprávný. Součet bitů v pozicích jedna, tři, pět a sedm vyjde jako liché číslo, stejně jako součet bitů v pozicích čtyři až sedm. To znamená, že paritní kontroly kontrolních bitů v pozicích jedna a čtyři selhaly. Když se sčítají jedna a čtyři, součet je pět, což je pozice pro nesprávný bit v přenosu, který je třeba opravit.