En Hamming-kode er en fejlkorrigerende blokkode, opkaldt efter Richard Hamming, som udviklede den i 1950'erne. På det tidspunkt arbejdede Hamming med maskiner, der havde relæer og brugte hulkort til at læse data. Fordi kortene blev håndteret ofte, opstod der perforerings- og aflæsningsfejl, hvilket motiverede udviklingen af metoder til automatisk fejlrettelse.

Grundidé og anvendelse

Hamming-koder anvendes fortsat inden for digital signalbehandling og telekommunikation, hvor man gerne vil sikre korrekt overførsel af bits uden at skulle genkalde hele pakken ved fejl. Hovedidéen er at tilføje få ekstra bit (paritetsbits) til brugerdata, så man kan opdage og rette enkelte fejl i et kodeord.

Paritetsbits og kodeordslængde

En Hamming-kode bruger flere paritetsbits, hvor hver paritetsbit angiver, om en bestemt gruppe af bits har lige eller ulige antal 1'er (jf. lige eller ulige paritet). Hver databit dækkes af flere paritetsbits, hvilket muliggør entydig lokalisering af en enkeltfejl.

For k paritetsbits kan man maksimalt have en kodeordslængde på

2 k - 1 {\displaystyle 2^{k}-1}{\displaystyle 2^{k}-1}

Dette svarer til, at et perfekt Hamming-kodeord har N = 2^k − 1 bits i alt, og antallet af brugerdata (informationsbits) bliver N − k = 2^k − 1 − k. En anden måde at udtrykke kravet på er 2^k ≥ N + 1, som sikrer, at alle mulige syndromer (mønstre af paritetskontrol) kan pege på enten ingen fejl eller en bestemt enkeltbit-position.

Notation og eksempel

Man skriver ofte en Hamming-kode som (N,n), hvor N er den samlede længde af et kodeord, og n er antallet af bits til brugerdata. For eksempel er Hamming-(7,4) en kode med 7 bits i alt og 4 data-bits, dvs. 3 paritetsbits.

Den kortest mulige Hamming-kode er (3,1) med k = 2 paritetsbits og ét data-bit. Med lige paritet (som i standardeksemplet) bliver de to gyldige kodeord:

  • 000 for data 0
  • 111 for data 1

Hvis der under transmission opstår en enkeltbit-fejl (f.eks. 000 → 001, 010 eller 100), vil dekoderen kunne genkende mønsteret og rette det tilbage til det korrekte gyldige kodeord (000). På samme måde rettes fejl i nærheden af 111 (f.eks. 011, 101, 110) tilbage til 111.

Fejlfindingsmekanisme (syndrom)

Ved modtagelse af et kodeord beregnes pariteterne igen og sammenlignes med de modtagne paritetsbits. Forskellen danner et binært mønster kaldet et syndrom. Syndromet svarer i Hamming-koder direkte til positionen af en evt. enkelt fejlet bit (hvis syndromet er 0, er der ingen fejl). Dette gør det muligt både at opdage og rette en enkelt bitfejl.

Egenskaber

  • Hamming-koder har Hamming-afstand 3, hvilket betyder, at mindst tre bits skal ændres for at skifte fra ét gyldigt kodeord til et andet. Det er grunden til, at de kan rette én enkeltbitfejl.
  • Standard Hamming-koder kan typisk rette enkelt-bit-fejl og opdage (men ikke korrekt rette) nogle typer flertalsfejl. Med et ekstra overordnet paritetsbit (f.eks. udvidet Hamming(8,4)) kan man også opdage todelt fejlsituationer (dvs. opdage dobbeltfejl), men stadig kun rette enkeltfejl.
  • Hamming-koder er "perfekte" i den forstand, at hele kodeordrummet dækkes uden overlap for de fejlmønstre, de er designet til at håndtere (enkeltfejl).

Praktiske bemærkninger

  • Hamming-koder er enkle at implementere i hardware og bruges i systemer, hvor enkeltfejl er langt mere sandsynlige end flertalsfejl.
  • I moderne systemer kombineres Hamming-koder ofte med andre mekanismer (f.eks. checksums, længere fejlkorrigerende koder eller retransmission) for at opnå højere pålidelighed, afhængigt af kanalens fejlkarakteristik.

Hamming-koder udgør et fundamentalt koncept i fejlkorrigerende koder og bruges ofte som indføringseksempel på, hvordan paritet og redundans kan give både fejlopdagelse og -korrektion i digitale systemer.