Vad är en Hamming -kod?

En Hamming -kod är en metod för att upptäcka och korrigera fel i en binär växellåda. Det gör det genom att inkludera ytterligare binära siffror i sekvensen som används för kontroll, liksom en algoritm som ger detekteringslogiken. En sådan kod kan hitta två fel i någon sekvens av bitar och reparera en bit som kan vara felaktig. The most commonly referenced Hamming code is known as the Hamming(7,4), where the four indicates the original number of starting bits and the seven represents the total number of bits in the sequence after the additional checking bits have been included.

The technique got its name from its creator, Richard Hamming, who published the method in 1950. The way the Hamming code works is by taking a string of bits and inserting additional checking bitar, kallade paritetsbitar, i sekvensen. Kontrollbitarna injiceras alltid i en position som är en kraft på två, så valfritt antal bitar kan verifieras av incuding ytterligare paritetsbitar. Detta kan fortsätta tills den sista paritetsbiten som läggs till i sekvensen är i en position som är en kraft på två som är mindre än eller lika med den slutliga positionen i sekvensen.

Med alla paritetsbitar på plats är de återstående positionerna de faktiska databitarna. Med tanke på det fyra-bitars exemplet, skulle bitpositioner ett, två och fyra vara paritetsbitarna, medan positionerna tre, fem, sex och sju är uppgifterna. När denna sekvens har etablerats går logiken för Hamming -koden till jobbet.

I en Hamming -kod används var och en av paritetsbitarna som har lagts till i sekvensen för att kontrollera några av bitpositionerna de är nära, inklusive sig själva. Paritetsbiten i position One kontrollerar varannan bitposition, som i huvudsak är alla udda numrerade positioner i sekvensen. Den andra paritetsbiten, i position två, kontrollerar positionerna två och treE, hoppar sedan över två positioner, kontrollerar ytterligare två positioner, hoppar över två till, och så vidare. Om det finns en paritetsbit i läge fyra, fungerar den på samma sätt genom att den kontrollerar positioner fyra till sju, hoppar sedan över fyra positioner, kontrollerar fyra till och framåt. Varje paritetsbit i sekvensen fortsätter på detta sätt under hela sekvensen.

Processen genom vilken en Hamming -kod upptäcker och korrigerar ett fel är genom att lägga till bitarna i kontrollsekvensen för varje paritetskontroll, som var och en måste komma ut ett jämnt nummer. Med tanke på det sju-bitars exemplet, för den första paritetskontrollen, läggs bitar en, tre, fem och sju till. Om summan är ett jämnt antal, checkar pariteten ut, men om det totala är udda, finns det ett fel. Sedan paritetskontrollerna överlappar varandra kommer två sådana fel att dyka upp. När tvåparitetsbitpositionerna som inte kommer med till och med totaler läggs samman kommer det att avslöja den bit som måste korrigeras.

I exemplet på sju-bitars Hamming Code, nackdelarider att biten i position nummer fem är felaktig. Summan av bitarna i positioner en, tre, fem och sju kommer ut som ett udda nummer, liksom summan av bitarna i positioner fyra till sju. Detta indikerar att paritetskontroller för kontrollbitarna i position en och fyra misslyckades. När en och fyra läggs samman är det totala fem, vilket är positionen för felaktig bit i överföringen som måste korrigeras.