Hamming-kode: Eksempler på feilretting

Innholdsfortegnelse:

Anonim

Hva er en feil?

Overførte data kan bli ødelagt under kommunikasjonen. Det vil sannsynligvis bli påvirket av ekstern støy eller andre fysiske feil. I en slik situasjon kan ikke inngangsdataene være de samme som utdataene. Denne uoverensstemmelsen er kjent som "Feil".

Datafeilene kan føre til tap av viktige eller sikre data. Det meste av dataoverføringen i digitale systemer vil være i form av 'Bitoverføring.' Selv en liten endring kan påvirke ytelsen til hele systemet. I en datasekvens, hvis 1 endres til 0 eller 0 endres til 1, kalles det "Bitfeil."

I denne Hamming-kodenopplæringen vil du lære:

  • Hva er en feil?
  • Typer feil
  • Hva er feilregistrering og korrigering?
  • Hva er en Hamming-kode?
  • Historien om Hamming-koden
  • Anvendelse av Hemming-kode:
  • Fordeler med Hamming-kode
  • Ulemper ved Hamming-kode
  • Prosess med å kode en melding ved hjelp av Hamming Code
  • Prosess for dekryptering av en melding i Hamming-kode

Typer feil

Det er hovedsakelig tre typer bitfeil som oppstår i dataoverføring fra avsender til mottaker.

  • Enkeltbitfeil
  • Flere bitfeil
  • Burst-feil

Enkeltbitfeil

Endringen som er gjort i en bit i hele datasekvensen er kjent som "Single bit error". Forekomsten av enkeltbitfeil er imidlertid ikke så vanlig. Videre oppstår denne feilen bare i et parallelt kommunikasjonssystem fordi data overføres bitvis i en enkelt linje. Derfor er det flere sjanser for at en enkelt linje kan være støyende.

Flere bitfeil

I datasekvens, hvis det er en endring i to eller flere biter av en datasekvens til en sender til mottaker, er den kjent som "Multiple bit-feil."

Denne typen feil forekommer hovedsakelig i både serielle og parallelle datakommunikasjonsnettverk.

Burst Feil

Endringen av settet med bits i datasekvensen er kjent som "Burst error". Denne typen datafeil beregnes fra første bitendring til siste bitendring.

Hva er feilregistrering og korrigering?

I digital kommunikasjon vil feil overføres fra ett kommunikasjonssystem til et annet. Hvis disse feilene ikke blir oppdaget og korrigert, vil dataene gå tapt. For effektiv kommunikasjon bør systemdata overføres med høy nøyaktighet. Dette vil bli gjort ved først å identifisere feilene og korrigere dem.

Feildeteksjon er en metode for å oppdage feilene som er tilstede i dataene som overføres fra en sender til mottakeren i et datakommunikasjonssystem.

Her kan du bruke redundanskoder for å finne disse feilene, ved å legge til dataene når de overføres fra kilden. Disse kodene kalles "Error detecting codes".

Tre typer feilkoder er:

  • Paritetskontroll
  • Syklisk redundanssjekk (CRC)
  • Longitudinal Redundancy Check (LRC)

Paritetskontroll:

  • Det er også kjent som en paritetskontroll.
  • Den har en kostnadseffektiv mekanisme for feildeteksjon.
  • I denne teknikken er den overflødige biten kjent som en paritetsbit. Den er lagt til for hver dataenhet. Totalt antall 1s i enheten skal bli jevnt, noe som er kjent som en paritetsbit.

Longitudinal Redundancy Check

I denne feildeteksjonsteknikken er en blokk med biter organisert i tabellformat. LRC-metoden hjelper deg med å beregne paritetsbiten for hver kolonne. Settet for denne pariteten sendes også sammen med de originale dataene. Paritetsblokken hjelper deg med å kontrollere overflødigheten.

Syklisk redundanssjekk

Syklisk redundanskontroll er en sekvens med overflødig som må legges til på slutten av enheten. Derfor bør den resulterende dataenheten deles med et andre, forhåndsbestemt binært tall.

På destinasjonen må innkommende data deles med samme nummer. I tilfelle hvis det ikke er noen rest, antas dataenheten å være korrekt og aksepteres. Ellers indikerer det at dataenheten er skadet i overføring, og derfor må den avvises.

Hva er en Hamming-kode?

Hamming-kode er en linjekode som er nyttig for feilregistrering opptil to umiddelbare bitfeil. Den er i stand til enkeltbitfeil.

I Hamming-kode koder kilden meldingen ved å legge til overflødige biter i meldingen. Disse overflødige bitene blir hovedsakelig satt inn og generert på bestemte posisjoner i meldingen for å oppnå feiloppdagelse og korrigeringsprosess.

Historien om Hamming-koden

  • Hamming-kode er en teknikk som RWHamming bygger for å oppdage feil.
  • Hamming-kode skal brukes på dataenheter av hvilken som helst lengde og bruker forholdet mellom data og redundansbiter.
  • Han jobbet med problemet med feilkorrigeringsmetoden og utviklet et stadig kraftigere utvalg av algoritmer kalt Hamming-kode.
  • I 1950 ga han ut Hamming Code, som i dag er mye brukt i applikasjoner som ECC-minne.

Påføring av Hamming-kode

Her er noen vanlige bruksområder for bruk av Hemming-kode:

  • Satellitter
  • Dataminne
  • Modemer
  • PlasmaCAM
  • Åpne kontaktene
  • Skjermledning
  • Innebygd prosessor

Fordeler med Hamming-kode

  • Hamming-kodemetoden er effektiv i nettverk der datastrømmene er gitt for enkeltbitfeil.
  • Hamming-kode gir ikke bare påvisning av en bitfeil, men hjelper deg også med å innrykke bit som inneholder feil, slik at den kan korrigeres.
  • Den enkle bruken av hammingkoder gjør det best egnet for bruk i dataminne og rettelse av en feil.

Ulemper ved Hamming-kode

  • Enkel-bit feilregistrering og korreksjonskode. Imidlertid, hvis flere biter er grunnlagt feil, kan resultatet resultere i en annen bit som bør være riktig for å bli endret. Dette kan føre til at dataene blir ytterligere feil.
  • Hamming-kodealgoritme kan bare løse problemer med enkeltbiter.

Prosess med å kode en melding ved hjelp av Hamming Code

Prosessen som avsenderen bruker for å kode meldingen inkluderer følgende tre trinn:

  • Beregning av totalt antall overflødige biter.
  • Kontrollerer posisjonen til de overflødige bitene.
  • Til slutt beregner du verdiene til disse overflødige bitene.

Når de ovennevnte overflødige bitene er innebygd i meldingen, sendes den til brukeren.

Trinn 1) Beregning av totalt antall overflødige biter.

La oss anta at meldingen inneholder:

  • n - antall databiter
  • p - antall overflødige biter som legges til den slik at np kan indikere minst (n + p + 1) forskjellige tilstander.

Her viser (n + p) plasseringen av en feil i hver av (n + p) bitposisjoner, og en ekstra tilstand indikerer ingen feil. Da p-biter kan indikere 2 p- tilstander, må 2 p være minst lik (n + p + 1).

Trinn 2) Plasser de overflødige bitene i riktig posisjon.

De overflødige p-bitene skal plasseres i bitposisjoner med krefter på 2. For eksempel 1, 2, 4, 8, 16, etc. De blir referert til som p 1 (i posisjon 1), p 2 (i posisjon 2) , p 3 (i posisjon 4) osv.

Trinn 3) Beregning av verdiene til den overflødige biten.

De overflødige bitene skal være paritetsbiter som gjør antall 1s enten like eller odde.

De to typene paritet er -

  • Totalt antall biter i meldingen blir jevnt, kalles jevn paritet.
  • Det totale antallet biter i meldingen blir merkelig, kalles odd paritet.

Her må all overflødig bit, p1, beregnes som paritet. Den skal dekke alle bitposisjonene hvis binære representasjon skal inkludere en 1 i første posisjon unntatt posisjonen til p1.

P1 er paritetsbiten for hver databit i posisjoner hvis binære representasjon inkluderer en 1 i den mindre viktige posisjonen som ikke inkluderer 1 Like (3, 5, 7, 9,

…. )

P2 er paritetsbit for hver databit i posisjoner hvis binære representasjon inkluderer 1 i posisjon 2 fra høyre, ikke inkludert 2 Like (3, 6, 7, 10, 11,

...)

P3 er paritetsbit for hver bit i posisjoner hvis binære representasjon inkluderer en 1 i posisjon 3 fra høyre ikke inkluderer 4 Like (5-7, 12-15,

...)

Prosess for dekryptering av en melding i Hamming-kode

Mottaker får innkommende meldinger som krever å utføre omberegninger for å finne og rette feil.

Omberegningsprosessen ble utført i følgende trinn:

  • Teller antall overflødige biter.
  • Korrekt plassering av alle overflødige biter.
  • Paritetskontroll

Trinn 1) Teller antall overflødige biter

Du kan bruke samme formel for koding, antall overflødige biter

2 p ≥ n + p + 1

Her er antall databiter og p antall overflødige biter.

Trinn 2) Korrekt posisjonering av alle overflødige biter

Her er p en overflødig bit som er lokalisert i bitposisjoner av krefter på 2, for eksempel 1, 2, 4, 8, etc.

Trinn 3) Paritetskontroll

Paritetsbiter må beregnes basert på databiter og de overflødige bitene.

p1 = paritet (1, 3, 5, 7, 9, 11

...)

p2 = paritet (2, 3, 6, 7, 10, 11

...)

p3 = paritet (4-7, 12-15, 20-23

...)

Sammendrag

  • Overførte data kan bli ødelagt under kommunikasjonen
  • Tre typer bitfeil er 1) Enkeltbitfeil 2) Multiple bitfeil 3) Burst Bit-feil
  • Endringen som er gjort i en bit i hele datasekvensen er kjent som "Single bit error."
  • I datasekvens, hvis det er en endring i to eller flere biter av en datasekvens til en sender til mottaker, er den kjent som "Multiple bit-feil."
  • Endringen av settet med bits i datasekvensen er kjent som "Burst error".
  • Feildeteksjon er en metode for å oppdage feilene som er tilstede i dataene som overføres fra en sender til mottaker i et datakommunikasjonssystem
  • Tre typer feildeteksjonskoder er 1) Paritetskontroll 2) Syklisk redundanskontroll (CRC) 3) Longitudinal Redundancy Check (LRC)
  • Hamming-kode er en linjekode som er nyttig for feilregistrering opptil to umiddelbare bitfeil. Den er i stand til enkeltbitfeil.
  • Hamming-kode er en teknikk som RWHamming bygger for å oppdage feil.
  • Vanlige bruksområder for bruk av Hemming-kode er satellittminne, modemer, innebygd prosessor, etc.
  • Den største fordelen med hamming code-metoden er effektiv i nettverk der datastrømmene er gitt for single-bit-feilene.
  • Den største ulempen med hamming code-metoden er at den bare kan løse problemer med enkeltbiter.
  • Vi kan utføre prosessen med å kryptere og dekode meldingen ved hjelp av hamming-kode.