Hva er en Hamming-kode?

En Hamming-kode er en metode for å oppdage og rette feil i en binær overføring. Det gjør det ved å inkludere flere binære sifre i sekvensen som brukes til å sjekke, samt en algoritme som gir deteksjonslogikken. En slik kode er i stand til å finne to feil i en hvilken som helst bitsekvens og reparere en bit som kan være feil. Den mest refererte Hamming-koden er kjent som Hamming (7,4), der de fire indikerer det opprinnelige antall startbiter og de syv representerer det totale antall biter i sekvensen etter at de ekstra kontrollbits er inkludert.

Teknikken fikk navnet sitt fra sin skaper, Richard Hamming, som publiserte metoden i 1950. Slik Hamming-koden fungerer er ved å ta en streng med biter og sette inn flere kontrollbiter, referert til som paritetsbiter, i sekvensen. Kontrollbitene blir alltid injisert i en stilling som har en styrke på to, så et hvilket som helst antall biter kan verifiseres ved å inkludere flere paritetsbiter. Dette kan fortsette til den siste paritetsbiten som er lagt til i sekvensen er i en posisjon som er en kraft av to som er mindre enn eller lik den endelige posisjonen i sekvensen.

Med alle paritetsbitene på plass, er de gjenværende posisjonene de faktiske databitene. Gitt firbitseksemplet, da vil bitposisjoner en, to og fire være paritetsbitene, mens posisjonene tre, fem, seks og syv er dataene. Når denne sekvensen er etablert, fungerer logikken til Hamming-koden.

I en Hamming-kode brukes hver av paritetsbitene som er lagt til sekvensen for å sjekke noen av bitposisjonene de er i nærheten av, inkludert seg selv. Paritetsbiten i posisjon en sjekker annenhver bitposisjon, som i det vesentlige er hver odde-nummererte posisjon i sekvensen. Den andre paritetsbiten, i posisjon to, sjekker posisjoner to og tre, hopper deretter over to posisjoner, sjekker ytterligere to posisjoner, hopper over to til, og så videre. Hvis det er en paritetsbit i posisjon fire, fungerer den på samme måte at den kontrollerer posisjoner fire til syv, og hopper deretter over fire posisjoner, kontrollerer fire flere og videre. Hver paritetsbit i sekvensen fortsetter på denne måten gjennom hele sekvensen.

Prosessen som en Hamming-kode oppdager og korrigerer en feil er ved å legge sammen bitene i sjekkesekvensen for hver paritetskontroll, som hver må komme ut et jevnt tall. Gitt syv-bit-eksemplet, for den første paritetskontrollen, blir bitene en, tre, fem og syv lagt opp. Hvis totalen er et jevnt tall, sjekker pariteten, men hvis totalen er merkelig, er det en feil. Siden paritetskontrollene overlapper hverandre, vil to slike feil vises. Når bitparisjonsposisjonene som ikke klarer å oppnå jevne totaler legges sammen, vil det avsløre biten som må korrigeres.

I eksemplet med syvbits Hamming-kode må du vurdere at biten i posisjon nummer fem er feil. Summen av bitene i posisjonene en, tre, fem og syv vil komme ut som et oddetall, og summen av bitene i posisjonene fire til syv. Dette indikerer at paritetskontroller for sjekkbitene i posisjon en og fire mislyktes. Når en og fire er lagt sammen, er totalen fem, som er plasseringen for den feil biten i transmisjonen som må korrigeres.