Hammingkod

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 

Datasäkerhet