Hva er Hamming Code: Historie, arbeid og dets applikasjoner

Prøv Instrumentet Vårt For Å Eliminere Problemer





I digitale systemer sendes data for kommunikasjon kan bli ødelagt på grunn av ekstern støy og andre fysiske feil. Hvis de overførte dataene ikke samsvarer med de gitte inndataene, kalles det en ‘feil’. Datafeilene kan slette vitale data i digitale systemer. Overføring av data vil være i form av biter (0 og 1) i digitale systemer. Hvis noen av bitene endres, kan hele systemets ytelse påvirkes. Hvis biten '1' endres til biten '0' eller omvendt, kalles den bitfeil. Det er forskjellige typer feil som single bit-feil, flere feil og burst-feil. I denne artikkelen diskuterer vi feilretting og gjenkjenning og hamming-kode.

Hva er feilregistrering og korrigering?

Ved digital kommunikasjon vil dataene gå tapt hvis det er en feil i overføringen av informasjon fra ett system / nettverk til et annet system / nettverk. Så det er viktig å finne og rette feil. Noen feil gjenkjenning og korreksjonsmetoder brukes til å oppdage og rette feilene for effektiv kommunikasjon. Hvis disse metodene brukes, kan dataene overføres med høyere nøyaktighet.




Feildeteksjon er definert som metoden som brukes til å oppdage feilene som overføres fra sender / sender til mottaker i digitale systemer. Redundanskoder legges til dataene under overføringen for å finne feilene. Disse kalles feiloppdagende koder.

Feilkorreksjon er korreksjon av data som overføres fra sender til mottaker. Feilretting kan gjøres i to typer.



Bakover feilkorrigering

I denne typen feilretting ber mottakeren avsenderen om å overføre dataene på nytt hvis mottakeren oppdager feilen.

Videresend feilretting

hvis dataene mottatt av mottakeren finner feilen, utfører den feilkorrigerende koder for å korrigere og gjenopprette dataene automatisk.


Hvis det er 'm' antall databiter og 'r' antall overflødige biter, vil kombinasjonene av informasjon være 2r.

2r> = m + r + 1

Typer feilregistreringskoder

Feilene i de mottatte dataene kan oppdages ved hjelp av tre typer feilregistreringskoder. Det er paritetskontroll, syklisk redundanskontroll (CRC) og langsiktig redundanskontroll.

Paritetskontroll

Den overflødige biten som kalles paritetsbit, blir lagt til for å gjøre antall biter jevne eller odde i tilfelle jevn paritet eller odde paritet. Mottakeren teller antall biter (1) i en ramme for å legge til paritetsbiten. Dette kalles paritetskontroll. Hvis antallet av 1-er i en ramme er jevnt, brukes jevn paritet ved å legge til biten '1'med nullverdi. På samme måte er antall nr. 1 oddetall, og oddetallpariteten brukes ved å legge til biten med verdien '1'.

Feiloppdagelse

feilregistrering

Derfor brukes den til å sikre at rammen / datoen mottatt av mottakeren fra kilden ikke blir ødelagt. I denne typen feilregistrering skal antallet av 1 være jevnt i den mottatte rammen. Det er veldig rimeligere blant alle typer feilregistrering.

Longitudinal Redundancy Check (LRC)

når settet / bitblokken er organisert, kan LRC-metoden brukes til å sjekke paritetsbiten i hver ramme. Det hjelper å sende settet med paritetsbiter sammen med originaldataene og sjekker redundansen.

Syklisk redundanssjekk

hans type brukes til å oppdage data / ramme mottatt fra kilden er gyldig eller ikke. Det involverer i den binære delingen av dataene som skal sendes og bruker polynomer (for å generere divisor). Før overføringen , blir en delingsoperasjon utført av avsenderen på dataene / bitene / rammen for å beregne resten.

Syklisk redundans-sjekk

syklisk redundans-sjekk

Under overføring av faktiske data fra avsenderen legger den til resten på slutten av de faktiske dataene. Kombinasjonen av faktiske data og resten kalles et kodeord. Dataene overføres i form av kodeord. I denne prosessen, hvis dataene er ødelagt, vil dataene bli avvist av mottakeren, ellers vil de bli akseptert.

Hva er Hamming Code?

Hamming-kode er definert som, en lineær kode som brukes i feiloppdagelsesprosessen opp til 2-mellomliggende feil. Den er også i stand til å oppdage enkeltbitfeil. I denne metoden blir de overflødige bitene lagt til dataene / meldingen av avsenderen for å kode dataene. For å gjøre feildeteksjon og -korreksjon, blir disse overflødige bitene lagt til i bestemte posisjoner for feilkorreksjonsprosessen.

Hamming-kode

hamming-kode

Hamming Codes historie

I 1950 oppfant Richard W. hamming Hamming-koder for å oppdage og rette feilene i data. Etter utviklingen av datamaskiner med høyere pålitelighet introduserte han hammingkoder for 1-feilkorrigeringskoder, og senere utvidet han opptil 2-feilregistreringskoder. Hamming-koder opprettes fordi paritetskontroll ikke kan oppdage og korrigere feil i dataene. Hamming-kodene settes inn i hvilken som helst blokklengde av data mellom faktiske data og redundansbiter. Han utviklet en rekke algoritmer for å jobbe med problemene med feilrettingmetoder, og disse kodene er mye brukt i ECC-minne.

Prosess med å kode en melding ved hjelp av Hamming-kode

Prosessen med å kode en melding ved hjelp av en hammingkode av avsenderen inkluderer tre trinn.

Trinn 1: Det første trinnet er å beregne antall overflødige biter i en melding

  • For eksempel, hvis en melding inneholder ‘n’ antall biter og ‘p’ antall overflødige biter blir lagt til meldingen, indikerer ‘np’ (n + p + 1) forskjellige tilstander.
  • Hvor (n + p) representerer plasseringen av en feil i hver bitposisjon
  • 1 (ekstra tilstand) representerer ingen feil.
  • Siden ‘p’ indikerer 2 ^ p (2p) tilstander, som er lik (n + p + 1) tilstander.

Steg 2: Plasser de overflødige bitene i nøyaktig / riktig posisjon

'p' biter settes inn i bitposisjonene som er kraften til 2 som 1, 2, 4, 8, 16, etc. Disse bitposisjonene er indikert som p1 (posisjon 1), p2 (posisjon 2), p3 (posisjon 4) osv.

Trinn 3: Beregn verdiene til overflødige biter

  • Her brukes paritetsbiter for å beregne verdiene til overflødige biter.
  • Paritetsbiter kan gjøre antallet av 1-er i en melding til enten jevn eller merkelig.
  • Hvis det totale antallet av 1-er i en melding er jevnt, brukes jevn paritet
  • Hvis totalt antall av 1-er i en melding er oddetall, brukes odd-paritet.

Prosess for dekryptering av en melding i Hamming Code

Prosessen med å dekryptere en melding mottatt fra avsenderen av mottakeren ved hjelp av hamming-koden inkluderer følgende trinn. Denne prosessen er bare omberegning for å oppdage og rette feilene i en melding.

Trinn 1: Telle antallet overflødige biter

Formelen for å kode meldingen ved hjelp av overflødige biter er,

2p≥ n + p + 1

Steg 2: korriger posisjonene til alle overflødige biter

‘P’ antall overflødige biter er plassert i litt kraftposisjoner på 2 som 1,2,4,8,16,32 etc

Trinn 3: paritetskontroll (odd paritet og til og med paritet)

Paritetsbiter beregnes ut fra antall 1-er i databiter og overflødige biter.

For eksempel

Pariteten til p1 ville være 1, 3, 5, 7, 9, 11, ...

Pariteten til p2 ville være 2, 3, 6, 7, 10, 11, ...

Pariteten til p3 vil være 4-7, 12-15, 20-23, ...

Fordeler med Hamming Code

Den største fordelen med å bruke en hammingkode er kostnadseffektiv hvis en datastrøm inneholder enkeltbitfeil.

  • Det kan gi feilregistrering og indikerer også bit som inneholder en feil for korreksjon.
  • Hamming-koder er veldig enkle og best å bruke i dataminnet og feilkorrigering og gjenkjenning av en bit.

Ulemper ved Hamming Code

  • Det er bare best for feilkorrigering og gjenkjenning av en bit. Hvis det oppstår feil med flere biter, kan hele ødelegges.
  • Hamming-kodealgoritmen kan bare løse enkeltbittfeil.

Anvendelser av Hamming-koder

Hamming-koder brukes i,

  • Databehandling
  • Telekommunikasjon
  • Datakomprimering
  • Løse gåter og turbokoder
  • Satellitter
  • Plasma CAM
  • Skjermede ledninger
  • Modemer
  • Dataminne
  • Åpne kontaktene
  • Innebygde systemer og prosessor

Vanlige spørsmål

1). Kan Hamming-koden oppdage 2-bits feil?

Hamming-koder kan oppdage og korrigere opptil 2-bits feil i en datastrøm

2). Hvordan fikser du Hamming-koden?

Hamming-koder plasseres i hvilken som helst datalengde mellom de faktiske dataene og overflødige biter. Disse kodene er steder med en minimumsavstand på 3 bits

3). Hva er paritetskoden?

Paritetskode eller paritetsbit legger til litt i den mottatte rammen (data inneholder 1 og 0) for å gjøre totalt antall bit (1) like eller odd.

4). Hva er Hamming-avstanden mellom dataene?

Hammingsavstanden mellom de to forskjellige datastrømmene med samme lengde er ikke 1 av.

Hammingsavstanden mellom to datastrenger av samme lengde kan beregnes ved hjelp av XOR-operasjonen.

For eksempel a = 11011001

b = 10011101

Hamming avstand kan beregnes som,

11011001 ⊕ 10011101 = 01000100 (antall 1-bits er 2)

Hammingsavstanden angir antall 1-er i den resulterende datastrømmen

Så, d (11011001, 10011101) = 2

Tilsvarende er 010 ⊕ 011 = 001, d (010, 011) = 1.

5). Er Hamming-kode syklisk?

Ja, hamming-koder tilsvarer sykliske koder som kan brukes som feiloppdagende koder.

Dermed handler alt om feilretting og gjenkjenning, typer feilregistrering, hamming koder prosessen med å kryptere og dekryptere meldingen ved hjelp av hammingkoder, applikasjoner av hammingkoder, fordeler og ulemper ved Hamming-koder. Her er et spørsmål til deg, ‘Hva er bruken av feilregistrering og korrigering?’