Vad är en Hamming Code?

En Hamming-kod är en metod för att upptäcka och korrigera fel i en binär överföring. Det gör det genom att inkludera ytterligare binära siffror i sekvensen som används för att kontrollera, liksom en algoritm som tillhandahåller detekteringslogiken. En sådan kod kan hitta två fel i vilken bit som helst och reparera en bit som kan vara felaktig. Den vanligaste Hamming-koden är känd som Hamming (7,4), där de fyra indikerar det ursprungliga antalet startbitar och de sju representerar det totala antalet bitar i sekvensen efter att ytterligare kontrollbitar har inkluderats.

Tekniken fick sitt namn från sin skapare, Richard Hamming, som publicerade metoden 1950. Hur Hamming-koden fungerar är genom att ta en sträng bitar och infoga ytterligare kontrollbitar, kallad paritetsbitar, i sekvensen. Kontrollbitarna injiceras alltid i en position med en effekt på två, så att alla antal bitar kan verifieras genom att inkludera ytterligare paritetsbitar. Detta kan fortsätta tills den sista paritetsbiten som läggs till i sekvensen är i en position som är en effekt av två som är mindre än eller lika med slutpositionen i sekvensen.

Med alla paritetsbitar på plats är de återstående positionerna de faktiska databitarna. Med tanke på fyra-bitsexemplet skulle då bitpositioner en, två och fyra vara paritetsbitarna, medan positionerna tre, fem, sex och sju är data. När denna sekvens har fastställts fungerar Hamming-kodens logik.

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 en kontrollerar varannan bitposition, vilket i huvudsak är varje udda numrerade position i sekvensen. Den andra paritetsbiten, i position två, kontrollerar positioner två och tre, hoppar sedan över två positioner, kontrollerar ytterligare två positioner, hoppar över två till och så vidare. Om det finns en paritetsbit i position fyra, fungerar den på liknande sätt genom att den kontrollerar positioner fyra till sju, hoppar sedan över fyra positioner, kontrollerar fyra till och med. Varje paritetsbit i sekvensen fortsätter på detta sätt genom 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 med ett jämnt tal. Med tanke på det sju bitars exemplet, för den första paritetskontrollen, läggs bitarna ett, tre, fem och sju till. Om summan är ett jämnt antal, kontrollerar pariteten, men om summan är udda, finns det ett fel. Eftersom paritetskontrollerna överlappar visas två sådana fel. När bitpositionerna med två pariteter som inte lyckas komma med jämna totaler läggs samman kommer det att avslöja den bit som måste korrigeras.

I det sju-bitars Hamming-kodexemplet, tänk på 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 positionerna fyra till sju. Detta indikerar att paritetskontroller för kontrollbitarna i position ett och fyra misslyckades. När en och fyra läggs samman är summan fem, vilket är positionen för den felaktiga biten i transmissionen som måste korrigeras.