Hamming-kode: Definition og forklaring af fejlkorrigerende blokkoder
Hamming-kode: Klart forklaret — forstå fejlkorrigerende blokkoder, paritetsbits, redundans og (7,4)-eksempel for pålidelig digital kommunikation.
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}
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.
Spørgsmål og svar
Spørgsmål: Hvad er en Hamming-kode?
Svar: En Hamming-kode er en fejlkorrigerende blokkode, som blev udviklet af Richard Hamming i 1950'erne. Den anvendes til digital signalbehandling og telekommunikation til at opdage og korrigere fejl.
Sp: Hvordan fungerer en Hamming-kode?
Svar: En Hamming-kode anvender flere paritetsbits til at dække hver databit, hvilket gør det muligt at opdage fejl og i visse tilfælde også at rette dem. Den anvender også redundans, hvilket betyder, at den samlede længde af et kodeord skal være lig med 2^k - 1, hvor k er antallet af paritetsbits.
Spørgsmål: Hvem opfandt Hamming-koden?
Svar: Hamming-koden blev opfundet af Richard Hamming i 1950'erne.
Spørgsmål: Hvad brugte Richard Hamming sin opfindelse til?
Svar: På det tidspunkt, hvor han udviklede den, brugte Richard Hamming sin opfindelse til at hjælpe med at korrigere fejl på hulkort, der blev meget brugt i maskiner med relæer. I dag bruges den hovedsagelig til digital signalbehandling og telekommunikation.
Spørgsmål: Hvad skrives som (N,n), når man taler om en hamming-kode?
A: Når man taler om en hamming-kode, henviser (N,n) til den samlede længde af et kodeord (det første tal) og antallet af bits til brugerdata (det andet tal). F.eks. betyder (7,4), at der er i alt 7 bits, hvoraf 4 er brugerdatabits.
Spørgsmål: Hvad er den kortest mulige hamming-kode?
Svar: Den kortest mulige hamming-kode er (3,1), hvilket betyder, at der er 3 bits i alt, hvoraf 1 er en brugerdatabit.
Søge