Obsah
Hammingovy kódy se používají k vložení informací o opravě chyb do datových toků. Kódy jsou navrženy tak, aby byla chyba nejen detekována, ale také opravena. Přidání informací o opravě chyb zvyšuje množství dat, ale také zvyšuje spolehlivost komunikace přes média s vysokou mírou chyb.
Hammingovo kódování může být komplikované, ale lze ho provést velmi rychle pomocí aritmetických triků na bitové úrovni. To umožňuje vytvoření užitečného a vysokorychlostního systému pro korekci chyb, který bude použit ve vestavěných aplikacích.
Krok 1
Vytvořte datové slovo. Jakýkoli bit s pozicí, která je mocninou dvou (první, druhá, čtvrtá atd.), Musí být rezervován pro paritní informace. Použijte tak dlouho, jak je to nutné, aby slovo mělo původní data a paritní bity.
Příklad:
1 1 0 1 0 0 1 0 se stává _ _ 1 _ 1 0 1 _ 0 0 1 0
Původní bity zůstávají ve stejném pořadí, ale byly rozloženy pro vložení paritních bitů.
Krok 2
Vypočítejte první paritní bit. Počínaje prvním bitem se bit načte, poté se bit přeskočí a postup se opakuje až do konce. Mezitím se spočítá počet nalezených. Paritní bity se v tomto procesu nepočítají.
Pokud je počet jednotek sudý, nastavte první bit na nulu. Jinak jej nastavte na jednu.
Příklad:
Bity 1, 3, 5, 7, 9 a 11 z _ _ 1 _ 1 0 1 _ 0 0 1 0, _11101, obsahují čtyři. Je to sudé, takže první bit je nastaven na nulu: 0 _ 1 _ 1 0 1 _ 0 0 1 0
Krok 3
Vypočítejte zbývající paritní bity. Počínaje druhým bitem se načtou dva bity, poté se dva bity přeskočí a postup se opakuje až do konce. Čtvrtý bit čte čtyři bity, přeskočí další čtyři, počínaje bitem čtyři. Stejný vzor následují všechny paritní bity, dokud nejsou všechny vypočítány.
Příklad:
Bit 2: 0 _ 1 _ 1 0 1 _ 0 0 1 0 kontroluje _1, 01, 01, které obsahují tři, takže bit 2 je nastaven na jednu. Bit 4: _ 0 1 1 1 0 1 _ 0 0 1 0 kontroluje _101, 0, který obsahuje dva, takže bit 4 je nastaven na nulu. Bit 8: 0 1 1 0 1 0 1 _ 0 0 1 0 kontroluje _0010, který obsahuje pouze jeden, takže bit 8 je nastaven na jeden.
Slovo je proto kódováno jako 011010110010.
Krok 4
Potvrďte slovo. Pokud je slovo poškozené, paritní bity se neshodují s tím, co se očekává. Chcete-li potvrdit, že slovo není poškozeno, jednoduše vypočítejte paritní bity pomocí kroků dva a tři. Pokud bity nejsou stejné, zaznamenejte jejich polohy.
Krok 5
Opravte špatný bit. Pokud najdete nesprávné paritní bity, jednoduše přidejte pozice bitů. Hodnota součtu je poloha nesprávného bitu. Změňte bitovou hodnotu v této poloze.
Například pokud jsou nesprávné paritní bity jedna a čtyři, změnou hodnoty pátého bitu chybu opravíte.