Innhold
Hamming-koder brukes til å sette inn informasjon om feilretting i datastrømmer. Kodene er utformet slik at en feil ikke bare blir oppdaget, men også rettet. Å legge til feilkorreksjonsinformasjon øker datamengden, men det øker også påliteligheten av kommunikasjon over media med høye feilrater.
Hamming-koding kan være komplisert å implementere, men det kan gjøres veldig raskt ved hjelp av bitnivå-aritmetiske triks. Dette gjør det mulig å lage et nyttig og hurtigkorrigeringssystem for høyhastighet, som kan brukes i innebygde applikasjoner.
Trinn 1
Lag dataordet. Enhver bit med en posisjon som er en styrke på to (første, andre, fjerde osv.) Må reserveres for paritetsinformasjon. Bruk så lenge det er nødvendig for at ordet skal ha de originale dataene og paritetsbitene.
Eksempel:
1 1 0 1 0 0 1 0 blir _ _ 1 _ 1 0 1 _ 0 0 1 0
De opprinnelige bitene forblir i samme rekkefølge, men ble spredt for å sette inn paritetsbitene.
Steg 2
Beregn den første paritetsbiten. Fra og med den første biten leses litt og deretter hoppes det litt over og prosedyren gjentas til slutten. I mellomtiden telles antall funnet. Paritetsbiter teller ikke i denne prosessen.
Hvis antallet er jevnt, setter du den første biten til null. Ellers setter du den til en.
Eksempel:
Bitt 1, 3, 5, 7, 9 og 11 i _ _ 1 _ 1 0 1 _ 0 0 1 0, _11101, inneholder fire. Dette er jevnt, så den første biten er satt til null: 0 _ 1 _ 1 0 1 _ 0 0 1 0
Trinn 3
Beregn gjenværende paritetsbiter. Fra og med den andre biten leses to biter og deretter hoppes over to biter og prosedyren gjentas til slutten. Den fjerde biten leser fire biter, hopper over ytterligere fire, og begynner med bit fire. Det samme mønsteret følges av alle paritetsbiter, til de alle blir beregnet.
Eksempel:
Bit 2: 0 _ 1 _ 1 0 1 _ 0 0 1 0 sjekker _1, 01, 01, som inneholder tre, så bit 2 er satt til en. Bit 4: _ 0 1 1 1 0 1 _ 0 0 1 0 sjekker _101, 0, som inneholder to, så bit 4 er satt til null. Bit 8: 0 1 1 0 1 0 1 _ 0 0 1 0 sjekker _0010, som bare inneholder en, så bit 8 er satt til en.
Ordet er derfor kodet som 011010110010.
Trinn 4
Bekreft ordet. Hvis et ord er ødelagt, vil paritetsbitene ikke matche det som forventes. For å bekrefte at ordet ikke er ødelagt, er det bare å beregne paritetsbitene ved hjelp av trinn to og tre. Hvis bitene ikke er de samme, registrerer du posisjonene.
Trinn 5
Korriger feil bit. Hvis du finner feil paritetsbiter, legger du bare til bitenes posisjon. Summen er posisjonen til feil bit. Endre bitverdien i denne posisjonen.
For eksempel, hvis feil paritetsbiter er ett og fire, vil feilen korrigeres ved å endre verdien til den femte biten.