Hammingkod

Hammingkod är en typ av felrättande kod, av typen blockkodning[1], som skapades av Richard Hamming och publicerades i april 1950 i Bell System Technical Journal.[2] 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[3].

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.[4]

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.[5] 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:[6]

  1. Alla bitar i kodordet som är i basen två är kontrollbitar, det vill säga 1, 2, 4, 8, 16...
  2. De resterande bitarna är databitar, det vill säga 3, 5, 6, 7, 9, 10...
  3. 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.
  4. 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:

Bit position1234567891011121314151617181920...
Encoded data bitsp1p2d1p4d2d3d4p8d5d6d7d8d9d10d11p16d12d13d14d15
Parity
bit
coverage		p1XXXXXXXXXX
p2XXXXXXXXXX
p4XXXXXXXXX
p8XXXXXXXX
p16XXXXX

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.[6]

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:[4]

  • 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

  1. ^ ”Introduktion till Viterbialgoritmen i enlighet med IEEE 802.11a”. Linköpings universitet. http://liu.diva-portal.org/smash/get/diva2:22173/FULLTEXT01. Läst 4 februari 2013. 
  2. ^ ”Richard Wesley Hamming”. Richard Wesley Hamming. School of Mathematics and Statistics University of St Andrews, Scotland. http://www-history.mcs.st-andrews.ac.uk/Biographies/Hamming.html. Läst 20 december 2012. 
  3. ^ ”se lemma 12”. Introduction to Coding Theory. Carnegie Mellon’s School of Computer Science. http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes1.pdf. Läst 21 december 2012. 
  4. ^ [a b] Wallander, Per (2001). 17 lektioner i TELEKOMMUNIKATION. Per Wallander Antenn AB. sid. 176-77. ISBN 91-86296-10-8 
  5. ^ ”Introduktion till feldetekterande och felkorrigerande koder”. Introduktion till feldetekterande och felkorrigerande koder. Högskolan Karlskrona Ronneby. http://www.fukt.bsnet.se/~mr_a/arbeten/errordetection.pdf. Läst 21 december 2012. 
  6. ^ [a b] ”Calculating the Hamming Code”. Calculating the Hamming Code. School of Computing and Information Science, Florida International University. http://users.cs.fiu.edu/~downeyt/cop3402/hamming.html. Läst 21 december 2012.