Hvad er en Hamming-kode?

En Hamming-kode er en metode til at detektere og korrigere fejl i en binær transmission. Det gør det ved at inkludere yderligere binære cifre i den sekvens, der bruges til kontrol, samt en algoritme, der giver detektionslogikken. En sådan kode er i stand til at finde to fejl i en hvilken som helst bitsekvens og reparere en bit, der kan være forkert. Den mest almindeligt omtalte Hamming-kode er kendt som Hamming (7,4), hvor de fire angiver det oprindelige antal startbits og de syv repræsenterer det samlede antal bit i sekvensen, efter at de ekstra kontrolbits er inkluderet.

Teknikken fik sit navn fra sin skaber, Richard Hamming, der udgav metoden i 1950. Måten Hamming-koden fungerer er ved at tage en streng bits og indsætte yderligere kontrolbits, der kaldes paritetsbits, i sekvensen. Kontrolbitene indsprøjtes altid i en position med en styrke på to, så ethvert antal bits kan verificeres ved at inkludere yderligere paritetsbits. Dette kan fortsætte, indtil den sidste paritetsbit, der er tilføjet til sekvensen, er i en position, der er en styrke på to, som er mindre end eller lig med den endelige position i sekvensen.

Når alle paritetsbits er på plads, er de resterende positioner de faktiske databits. I betragtning af eksemplet med fire bit vil bitpositioner en, to og fire være paritetsbitene, mens positionerne tre, fem, seks og syv er dataene. Når denne sekvens er etableret, fungerer logikken i Hamming-koden.

I en Hamming-kode bruges hver af paritetstykkerne, der er føjet til sekvensen, til at kontrollere nogle af bitpositionerne, de er tæt på, inklusive sig selv. Paritetsbiten i position én kontrollerer hver anden bitposition, hvilket i det væsentlige er hver ulige nummerplacering i sekvensen. Den anden paritetsbit, i position to, kontrollerer positioner to og tre, springer derefter over to positioner, kontrollerer yderligere to positioner, springer over to mere, og så videre. Hvis der er en paritetsbit i position fire, fungerer den på samme måde, at den kontrollerer positioner fire til syv, og springer derefter over fire positioner, kontrollerer fire mere og videre. Hver paritetsbit i sekvensen fortsætter på denne måde gennem hele sekvensen.

Den proces, hvorpå en Hamming-kode registrerer og korrigerer en fejl, er ved at tilføje bitene i kontrol-sekvensen for hver paritetskontrol, som hver skal komme ud et jævnt tal. I syv-bit-eksemplet tilføjes bits en, tre, fem og syv til den første paritetskontrol. Hvis det samlede antal er et jævnt tal, kontrolleres pariteten, men hvis det samlede antal er ulige, er der en fejl. Da paritetskontrollerne overlapper hinanden, vises to sådanne fejl. Når de to-paritet bitpositioner, der ikke klarer at nå frem til jævne totaler, tilføjes sammen, afslører det den bit, der skal rettes.

I eksemplet med syv bit Hamming-kode skal du overveje, at bit i position nummer fem er forkert. Summen af ​​bitene i positionerne en, tre, fem og syv vil komme ud som et ulige antal, ligesom summen af ​​bitene i positioner fire til syv. Dette indikerer, at paritetskontrol af kontrolbitene i position en og fire mislykkedes. Når en og fire tilføjes sammen, er det samlede antal fem, hvilket er positionen for den forkerte bit i transmissionen, der skal rettes.