Hammingkod är en typ av felrättande kod, av typen blockkodning, som skapades av Richard Hamming och publicerades i april 1950 i Bell System Technical Journal. Hammingkoden är speciell eftersom den är en så kallad perfekt kod, det vill säga att den ger bästa förhållandet mellan kodord och kontrollbitar för den valda längden och där ordet har hammingavståndet tre.

Hammingkoden är ofta hamming(7,4) eftersom ett kodord på 4 bitar kompletteras med tre kontrollbitar så att man kan rätta ett enkelt bitfel.

Lägger man sedan till en extra paritetsbit till ordet, vilken räknar om det är ett jämnt eller udda antal ettor, kan man även detektera om det är två fel. Då kan man dock inte rätta det utan bara meddela att det är två fel. Skulle det bli tre fel så visar koden det som om det är ett fel och rättar fel, men sannolikheten för tre fel är så liten att man bortser från det. Denna kod kallas då hamming(8,4).

Principer För att skriva i hammingkod följer man följande struktur: Alla bitar i kodordet som är i basen två är kontrollbitar, det vill säga 1, 2, 4, 8, 16... De resterande bitarna är databitar, det vill säga 3, 5, 6, 7, 9, 10... kontrollbitarna kontrollerar pariteten hos speciella bitar i kodordet utifrån sin egen position, det vill säga den räknar om det finns ett jämnt eller udda antal ettor. Ett udda antal ger pariteten 1 medan jämnt antal ger paritetet 0. Bestäm vad som är minst signifikanta siffra (LSB) innan du börjar koda, och var säker på att mottagaren vet om det också, det vill säga om du börjar från höger eller vänster. Position 1 kontrollerar varannan bit, med början på bit ett: 1, 3, 5, 7... Position 2 kontrollerar två bitar och hoppar över två: 2, 3, 6, 7, 10, 11... Position 4 kontrollerar fyra bitar och hoppar över fyra: 4-7, 12-15... Position 8 kontrollerar åtta bitar och hoppar över åtta: 8-15, 24-31...

Denna generella regel kan visualiseras i en tabell:

{| class="wikitable" style="text-align:center;" |- !colspan="2"| Bit position ! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10 !! 11 !! 12 !! 13 !! 14 !! 15 !! 16 !! 17 !! 18 !! 19 !! 20 |rowspan="7"| ... |- !colspan="2"| Encoded data bits !style="background-color: #90FF90;"| p1 !style="background-color: #90FF90;"| p2 !! d1 !style="background-color: #90FF90;"| p4 !! d2 !! d3 !! d4 !style="background-color: #90FF90;"| p8 !! d5 !! d6 !! d7 !! d8 !! d9 !! d10 !! d11 !style="background-color: #90FF90;"| p16 !! d12 !! d13 !! d14 !! d15 |- !rowspan="5"|Paritybitcoverage !style="background-color: #90FF90;"| p1 | X || || X || || X || || X || || X || || X || || X || || X || || X || || X || |- !style="background-color: #90FF90;"| p2 | || X || X || || || X || X || || || X || X || || || X || X || || || X || X || |- !style="background-color: #90FF90;"| p4 | || || || X || X || X || X || || || || || X || X || X || X || || || || || X |- !style="background-color: #90FF90;"| p8 | || || || || || || || X || X || X || X || X || X || X || X || || || || || |- !style="background-color: #90FF90;"| p16 | || || || || || || || || || || || || || || || X || X || X || X || X

Exempel kodord: 1001110 Läsning sker i dessa exempel med början från höger som då är LSB. Skriv upp ordet så att kontrollbitarna kommer på sin position: 100?111?0?? Börja med position 1: kontrollera varannan. Det finns då tre ettor, vilket ger paritetet 1: 100?111?0?1 Fortsätt med position 2: kontrollera enligt ovan. Det finns även här tre ettor, vilket ger paritet 1: 100?111?011 Fortsätt med position 4: kontrollera enligt ovan. Det finns även här tre ettor, vilket ger paritet 1: 100?1111011 Avsluta med position 8: kontrollera enligt ovan. Det finns här en etta, vilket ger paritet 1: 10011111011 Kodordet med kontrollbitar blir då: 10011111011 vilket är det som mottagaren skall få fram. För att kontrollera att bitarna är rätt så kodar denne om ordet, och jämför de nya kontrollbitarna med de gamla. De felaktiga visar då var felet sitter.

Modulo-2 räkning

Man kan även lösa det med modulo-2-räkning. Genom att göra på det sättet är det lättare att hitta felen. Detta görs på följande sätt: Skriv upp ordet som i exemplet ovanför: 100?111?0?? Räkna vilka positioner som har ettor. I detta fallet är det: 5, 6, 7, 11 Skriv talen binärt och addera dem (det vill säga jämnt antal ettor ger svaret 0 och udda antal ettor ger svaret 1): 11=1011 07=0111 06=0110 05=0101 kontrollbitar=1111

Man ser om det är ett jämnt eller udda antal ettor i kolumnerna. Ordet blir då samma som i exemplet ovan: 10011111011

Avkodning och felrättning Man kan avkoda och upptäcka var felet sitter om det bara är ett fel som har uppstått. Eftersom sannolikheten för att det är flera fel på en så liten kodsekvens fungerar det bra. För att avkoda ordet och se om det är rätt skriver man upp alla bitars position med paritet med binära siffror, precis som ovan, och räknar ut vad svaret blir. Blir det 0000 är det rätt kodat, men skulle det bli ettor i svaret så visar det var felet sitter: 11=1011 08=1000 07=0111 06=0110 05=0101 04=0100 02=0010 01=0001 kontroll=0000

Vid ett bitfel på position 6 så ändras den siffran från en etta till en nolla. Då blir talet som mottages följande: 10011011011. Vid kontrollen får man följande uträkning: 11=1011 08=1000 07=0111 05=0101 04=0100 02=0010 01=0001 kontroll=0110

vilket är den binära siffran för position 6. Då vet avkodaren att den siffran som står där skall bytas ut mot den andra möjliga siffran vilket i detta fallet är en etta.

Referenser

Kategori:Datasäkerhet