Hammingkod: Definition, principer och exempel på felkorrigerande koder

Hammingkod: Lär dig definition, principer och konkreta exempel på felkorrigerande koder — hur paritetsbitar upptäcker och korrigerar bitfel i digital kommunikation.

En hammingkod är en felkorrigerande blockkod. Koden är uppkallad efter Richard Hamming som utvecklade den på 1950-talet. På den tiden arbetade Hamming med maskiner som hade reläer och använde hålkort för att läsa av data. Eftersom de användes flitigt hade hålkorten ofta fel som behövde rättas av anställda.

Hammingkoder används för digital signalbehandling och telekommunikation. Hammingkoder genereras enligt vissa regler. Hammingkoder använder flera paritetsbitar. En paritetsbit talar om huruvida en grupp av bitar är jämn eller udda. I en hammingkod täcks varje databit av flera paritetsbitar. Detta gör det möjligt att upptäcka fel, och i vissa fall även att korrigera dem. En hammingkod använder redundans. Om det finns tre paritetsbitar per kodord måste kodordet ha en längd på 7 ( 2 k - 1 {\displaystyle 2^{k}-1} , för k som antalet paritetsbitar). Detta ger 4 bitar användardata per kodord, i exemplet. Vanligtvis skrivs detta som (N,n), där den första siffran är den totala längden på ett kodord och den andra är antalet bitar för användardata. Exemplet ovan är (7,4).

Den kortaste möjliga Hammingkoden är (3,1), 2 paritetsbitar används för en databit. Denna kod har två giltiga värden 000 och 111 - Koderna 001, 010 och 100 är överföringsfel och kommer att tilldelas det giltiga kodordet 000. De andra möjligheterna 011, 101 och 110 ändras till 111.

Principer och egenskaper

Hammingkoder är utformade för att rätta enkla bitfel (single-error correction, SEC) och ofta också upptäcka, men inte rätta, dubbelbitfel. Den grundläggande egenskapen är att kodens minsta Hamming-avstånd är 3, vilket innebär att två giltiga kodord skiljer sig i minst tre bitar. Det gör att ett enda bitfel ger ett avstånd 1 från ett giltigt kodord och kan identifieras och korrigeras.

Paritetsbitarna skapar redundans. Genom att låta varje databit ingå i flera paritetsgrupper kan avkodaren med hjälp av ett så kallat syndrom avgöra vilken bit som är felaktig och sedan vända den.

Konstruktion: hur många paritetsbitar behövs?

För att en Hammingkod med r paritetsbitar och m databitars ska kunna representera alla möjliga fel (inklusive ”ingen fel”) måste följande villkor uppfyllas:

• 2^r ≥ m + r + 1

Här står 2^r för antalet möjliga syndromvärden, m+r är totala antal bitar i kodordet och +1 räknar med fallet "ingen fel". För (7,4) är r = 3 och m = 4: 2^3 = 8 ≥ 4 + 3 + 1 = 8, alltså räcker tre paritetsbitar för fyra databitar.

Placering av paritetsbitar

Paritetsbitar placeras i positioner som är potenser av två: 1, 2, 4, 8, ... (räknat från 1). Övriga positioner innehåller databitarnas värden. Varje paritetsbit kontrollerar en grupp av bitar där positionens binära representation har en etta i den bitpositionen. Exempel (7,4):

• p1 i position 1 kontrollerar bitar 1,3,5,7
• p2 i position 2 kontrollerar bitar 2,3,6,7
• p4 i position 4 kontrollerar bitar 4,5,6,7

Kodning och avkodning — exempel med (7,4)

Anta att vi ska koda databitsekvensen 1 0 1 1 (i ordningen d1 d2 d3 d4). I Hamming(7,4) placeras dessa i positionerna 3, 5, 6 och 7:

• pos 1 = p1 (paritet)
• pos 2 = p2 (paritet)
• pos 3 = d1 = 1
• pos 4 = p4 (paritet)
• pos 5 = d2 = 0
• pos 6 = d3 = 1
• pos 7 = d4 = 1

Beräkna pariteterna så att varje paritetsgrupp får jämn paritet (exempelvis):

• p1 täcker 1,3,5,7 ⇒ p1 ⊕ d1 ⊕ d2 ⊕ d4 = 0 ⇒ p1 ⊕ 1 ⊕ 0 ⊕ 1 = 0 ⇒ p1 = 0
• p2 täcker 2,3,6,7 ⇒ p2 ⊕ d1 ⊕ d3 ⊕ d4 = 0 ⇒ p2 ⊕ 1 ⊕ 1 ⊕ 1 = 0 ⇒ p2 = 1
• p4 täcker 4,5,6,7 ⇒ p4 ⊕ d2 ⊕ d3 ⊕ d4 = 0 ⇒ p4 ⊕ 0 ⊕ 1 ⊕ 1 = 0 ⇒ p4 = 0

Det kodade ordet blir då: 0 1 1 0 0 1 1 (position 1 till 7).

Om ett fel uppstår under överföring — till exempel att biten i position 5 flippar från 0 till 1 — kan mottagaren beräkna pariteterna på nytt och jämföra med de mottagna paritetsbitarna. Skillnaden bildar ett syndrom: ett binärt tal vars värde motsvarar den bitposition som är felaktig. I vårt exempel ger syndromet värdet 5, mottagaren vet alltså att position 5 är fel och vänder den tillbaka (från 1 till 0).

Begränsningar och varianter

• Standard Hammingkoder kan rätta ett enkelt bitfel och upptäcka (men inte alltid korrekt klassificera) tvåbitfel.
• En vanlig variant är extended Hamming code (SECDED — single error correction, double error detection) där en extra global paritetsbit läggs till för att upptäcka dubbelbitfel. Den utökade koden får då Hamming-avstånd 4 och kan både korrigera ett fel och upptäcka tvåfel.
• Hammingkoder är effektiva för miljöer med låga felhastigheter och används fortfarande i minnessystem, inbyggda system och viss telekommunikation.

Ytterligare kommentarer

Hammingkoder är exempel på perfekta koder i den meningen att alla möjliga vektorers utrymme täcks av kluster runt kodorden utan överlappning (för enkelt felrättande), givet rätt relation mellan paritets- och databitantal. De är också pedagogiskt viktiga för att förstå grundläggande idéer inom felkorrigering: redundans, paritet, syndromberäkning och positionskodning.

Frågor och svar

F: Vad är en Hamming-kod?

F: Hur fungerar en Hamming-kod?

F: Vem uppfann Hammingkoden?

F: Vad använde Richard Hamming sin uppfinning till?

F: Vad skrivs som (N,n) när man talar om en Hamming-kod?

F: Vad är den kortaste möjliga hammingkoden?

Sök med bokstav