Hamming CodeFejlfinding og -korrektion med eksempler

Af: Bryce Leo Bryce Leo
Hours Opdateret

⚡ Smart opsummering

Hamming-kode er en lineær fejlkorrigerende kode, der tilføjer redundante paritetsbits ved potens-af-to positioner, hvilket giver en modtager mulighed for at detektere op til to-bit fejl og automatisk rette enhver enkelt-bit fejl under datatransmission.

  • 🧭 Formål: Hamming-kode registrerer og korrigerer transmissionsfejl ved at indlejre paritetsbits, der præcist bestemmer positionen af ​​en beskadiget bit.
  • 🔢 Redundante bits: Antallet af paritetsbits (p) opfylder reglen 2^p ≥ n + p + 1, hvor n er antallet af databits.
  • 📍 Placering: Paritetsbits optager potensen af ​​to positioner - 1, 2, 4 og 8 - mens databits udfylder de resterende positioner.
  • 🧮 Hamming(7,4): En almindelig form koder fire databits til syv i alt bits ved hjælp af tre paritetsbits.
  • 🧯 Begrænsning: Standard Hamming-kode korrigerer kun enkeltbitfejl; en ekstra samlet paritetsbit tilføjer dobbeltfejldetektion (SECDED).
  • 🤖 AI assistance: Maskinlæringsdekodere hjælper med at markere støjende kanaler og fejlmønstre, som faste koder alene kan overse.
Læs mere

Fejldetektion og -korrektion i Hamming-kode med paritetsbits

Hvad er en fejl?

TransmitIndlæste data kan blive beskadiget under kommunikation. De vil sandsynligvis blive påvirket af ekstern støj eller andre fysiske fejl. I en sådan situation kan inputdataene ikke være de samme som outputdataene. Denne uoverensstemmelse kaldes en "fejl".

Datafejl kan forårsage tab af vigtige eller sikre data. Det meste af dataoverførslen i digitale systemer sker i form af "bitoverførsel", og selv en lille ændring af en enkelt bit kan påvirke hele systemets ydeevne. Hvis et 1-tal i en datasekvens ændres til et 0, eller et 0 ændres til et 1-tal, kaldes det en "bitfejl".

Typer af fejl

Der er primært tre typer bitfejl, der opstår, når data transmitfra afsender til modtager. Diagrammet nedenfor illustrerer, hvordan hver type påvirker en datasekvens:

Diagram, der sammenligner enkeltbit-, flerbit- og burstfejl i en binær datasekvens

  • Enkelt bit fejl
  • Flere bitfejl
  • Burst fejl

Enkelt bit fejl

En ændring af én bit i hele datasekvensen kaldes en "single-bit error". Forekomsten af ​​en single-bit error er ikke så almindelig. Det forekommer oftest i et parallelt kommunikationssystem, fordi data overføres bitvis på separate linjer, så der er større chance for, at én linje bliver støjende, mens de andre forbliver rene.

Flere bitfejl

Når to eller flere bits i en datasekvens ændrer sig mellem transmitter og modtageren, er det kendt som en "multiple-bit-fejl".

Denne type fejl forekommer i både serielle og parallelle datakommunikationsnetværk.

Burst fejl

En ændring i et sæt af fortløbende bits i en datasekvens er kendt som en "burst-fejl". Længden af ​​en burst-fejl måles fra den første ændrede bit til den sidst ændrede bit.

Hvad er fejldetektion og fejlkorrektion?

I et digitalt kommunikationssystem kan der opstå fejl, når data flyttes fra én enhed til en anden. Hvis disse fejl ikke opdages og rettes, går dataene tabt. For effektiv kommunikation skal data overføres med høj nøjagtighed, hvilket opnås ved først at identificere fejlene og derefter rette dem.

Fejlregistrering er en metode til at finde fejl i data transmitted fra en transmitter til en modtager i en datakommunikation system.

Redundanskoder bruges til at finde disse fejl ved at tilføje ekstra bits til dataene, når de er transmitfra kilden. Disse ekstra bits kaldes "fejldetekteringskoder". De tre mest almindelige typer fejldetekteringskode er:

  • Paritetskontrol
  • Cyclic Redundancy Check (CRC)
  • Longitudinalt redundanstjek (LRC)

Paritetskontrol

  • Det er også kendt som et paritetstjek.
  • Det giver en omkostningseffektiv mekanisme til fejldetektion.
  • I denne teknik kaldes den redundante bit, der tilføjes til hver dataenhed, en paritetsbit. Den indstilles således, at det samlede antal 1'ere i enheden bliver lige (lige paritet) eller ulige (ulige paritet).

Longitudinel redundanskontrol

I denne fejldetekteringsteknik organiseres en blok af bits i en tabel. LRC-metoden beregner en paritetsbit for hver kolonne, og dette sæt af paritetsbits sendes sammen med de originale data. Blokken af ​​paritetsbits hjælper modtageren med at kontrollere for redundans og detektere fejl.

Cyclisk Redundans Check

Cyklisk redundanskontrol tilføjer en sekvens af redundante bits til slutningen af ​​dataenheden, så den resulterende dataenhed bliver nøjagtig delelig med et andet, forudbestemt binært tal.

Ved destinationen divideres de indgående data med det samme tal. Hvis der ikke er nogen rest, antages dataenheden at være korrekt og accepteres. Ellers indikerer det, at dataenheden blev beskadiget under transmissionen, og den skal afvises.

Hvad er en Hamming Code?

Hamming-kode er en lineær kode, der er nyttig til at detektere op til to umiddelbare bitfejl og korrigere enkeltbitfejl. Fejlkorrektion af denne art opererer typisk på datalinklaget, hvor data indrammer og kontrollerer deres integritet mellem tilstødende noder.

I Hamming-kode koder kilden beskeden ved at tilføje redundante bits. Disse redundante bits indsættes og genereres på bestemte positioner i beskeden for at udføre fejldetektion og -korrektion.

Hammings historie Code

  • Hamming-kode er en teknik udviklet af RW Hamming til at detektere og rette fejl.
  • Den kan anvendes på dataenheder af enhver længde og bruger forholdet mellem databits og redundansbits.
  • Hamming arbejdede med problemet med fejlkorrektion og udviklede en stadig mere kraftfuld række af algoritmer.
  • I 1950 udgav han Hamming-koden, som stadig er meget anvendt i dag i applikationer som ECC-hukommelse.

Anvendelser af Hamming Code

Her er nogle almindelige anvendelser af Hamming-kode:

  • Satellitter
  • Computerhukommelse (ECC RAM)
  • Modemer
  • PlasmaCAM
  • Åbn stik
  • Skærmet ledning
  • Indlejrede processorer

RELATEREDE ARTIKLER

Fordele ved Hamming Code

  • Hamming-kode er effektiv på netværk, hvor datastrømme er udsat for enkeltbitfejl.
  • Den registrerer ikke kun en bitfejl, men hjælper dig også med at identificere den bit, der indeholder fejlen, så den kan rettes.
  • Hamming-kodernes brugervenlighed gør dem velegnede til computerhukommelse og korrektion af enkeltfejl.

Ulemper ved Hamming Code

  • Det er en enkeltbit-fejldetektions- og korrektionskode. Hvis flere bits viser sig at være fejlagtige, kan resultatet vende en anden bit, der faktisk var korrekt, hvilket yderligere ødelægger dataene.
  • Hamming-kodealgoritmen kan kun løse problemer med én bit.

Sådan koder du en besked i Hamming Code

Den proces, som afsenderen bruger til at kode beskeden, involverer følgende tre trin:

  • Beregn det samlede antal redundante bits.
  • Bestem placeringen af ​​de redundante bits.
  • Beregn værdien af ​​hver redundant bit.

Når de redundante bits er integreret i beskeden, sendes det komplette kodeord til modtageren.

Trin 1) Beregn det samlede antal redundante bits.

Antag at beskeden indeholder n databits og p redundante bits, tilføjet således at 2p kan angive mindst (n + p + 1) forskellige tilstande.

Her tager (n + p) højde for placeringen af ​​en fejl i hver af (n + p) bitpositionerne, og én ekstra tilstand indikerer ingen fejl. Fordi p paritetsbits kan indikere 2p stater, 2p skal være mindst lig med (n + p + 1).

Trin 2) Placer de redundante bits i deres korrekte positioner.

De p redundante bits er placeret på bitpositioner, der er potenser af 2 - for eksempel 1, 2, 4, 8 og 16. De kaldes p1 (i position 1), s2 (i position 2), s3 (på position 4) og så videre.

Trin 3) Beregn værdien af ​​hver redundant bit.

Hver redundant bit er en paritetsbit, der gør antallet af 1'ere i sin gruppe enten lige eller ulige. De to typer paritet er:

  • Lige paritet: Det samlede antal 1'ere i de dækkede positioner gøres lige.
  • Ulige paritet: Det samlede antal 1-ere i de dækkede positioner gøres ulige.

Hver paritetsbit dækker et specifikt sæt positioner, bestemt af den binære repræsentation af positionsnumrene:

  • p1 kontrollerer alle positioner, hvis binære værdi har et 1 i den mindst betydende bit — positionerne 1, 3, 5, 7, 9, 11 osv.
  • p2 kontrollerer alle positioner, hvis binære værdi har et 1 i den anden bit fra højre — positionerne 2, 3, 6, 7, 10, 11 osv.
  • p3 kontrollerer alle positioner, hvis binære værdi har et 1 i den tredje bit fra højre — positionerne 4 til 7, 12 til 15 osv.

Udarbejdet eksempel (7,4): Overvej de fire databits 1011Tre paritetsbits er nødvendige (23 = 8 ≥ 4 + 3 + 1), hvilket giver et syv-bit kodeord opstillet som p1 p2 d1 p3 d2 d3 d4Placering af dataene giver positionerne 3, 5, 6, 7 = 1, 0, 1, 1. Ved brug af lige paritet: p1 dækker positionerne 1, 3, 5, 7 (bit 1, 0, 1 → p1 = 0); p2 dækker 2, 3, 6, 7 (bit 1, 1, 1 → p2 = 1); p3 dækker 4, 5, 6, 7 (bit 0, 1, 1 → p3 = 0). Den transmitted-kodeordet er derfor 0110011.

Sådan afkoder du en besked i Hamming Code

Modtageren tager den indgående besked og udfører genberegninger for at finde og rette fejl. Genberegningsprocessen bruger følgende trin:

  • Tæl antallet af redundante bits.
  • Placer alle de redundante bits korrekt.
  • Udfør paritetskontrollen.

Trin 1) Tæl antallet af redundante bits. Brug den samme formel som til kodning: 2p ≥ n + p + 1, hvor n er antallet af databits og p er antallet af redundante bits.

Trin 2) Placer alle de redundante bits korrekt. Hver redundante bit sidder på en bitposition, der er en potens af 2 - for eksempel 1, 2, 4 og 8.

Trin 3) Udfør paritetskontrollen. Paritetsbittene genberegnes ud fra databittene og de modtagne redundante bits:

  • p1 = paritet(1, 3, 5, 7, 9, 11, …)
  • p2 = paritet(2, 3, 6, 7, 10, 11, …)
  • p3 = paritet(4–7, 12–15, 20–23, …)

De genberegnede paritetsbits danner tilsammen et binært tal. Hvis dette tal er nul, er der ingen fejl; ellers angiver dets værdi den nøjagtige position af den enkelte beskadigede bit, som derefter vendes for at rette meddelelsen.

Ofte Stillede Spørgsmål

Hamming-afstand er antallet af bitpositioner, hvor to binære strenge af samme længde adskiller sig. I fejlkorrigerende koder bestemmer den minimale Hamming-afstand mellem gyldige kodeord, hvor mange fejl der kan detekteres eller korrigeres. Standard Hamming-kode har en minimumsafstand på tre.

Hamming(7,4) koder fire databits ind i et syv-bit kodeord ved at tilføje tre paritetsbits. Den korrigerer enhver enkelt-bit fejl og detekterer to-bit fejl. Notationen (n, k) angiver den samlede kodeordlængde n og antallet af databits k.

En enkelt paritetsbit registrerer kun et ulige antal bitfejl og kan ikke lokalisere eller rette dem. Hamming-kode bruger flere paritetsbits i potens af to positioner, så den præcist identificerer den fejlbehæftede bit og retter den automatisk.

Grundlæggende Hamming-kode korrigerer en-bit fejl, men kan fejlkorrigere to-bit fejl. Tilføjelse af én samlet paritetsbit, der dækker hele kodeordet, skaber SECDED (single error correction, double error detection), hvilket hæver minimumsafstanden til fire og pålideligt detekterer dobbelt-bit fejl.

Fejldetektion og -korrektion forekommer hovedsageligt på datalinklaget i OSI model, som indrammer data og kontrollerer deres integritet mellem tilstødende noder. Transportlagsprotokoller tilføjer end-to-end-kontroller, mens det fysiske medie introducerer den støj, som disse koder beskytter imod.

Hamming-kode er en lineær blokkode. Den behandler en blok af databits med fast størrelse på én gang og tilføjer paritetsbits, i modsætning til konvolutionskoder, der koder en kontinuerlig bitstrøm ved hjælp af hukommelsen fra tidligere bits. Dette gør Hamming-kode enkel og hurtig.

Maskinlæringsmodeller lærer støjmønstrene i en kanal og forudsiger sandsynlige bitfejl, hvilket forbedrer afkodningsnøjagtigheden ud over faste ordninger. AI-drevne dekodere til LDPC og polarkoder understøtter nu moderne 5G- og lagringssystemer, hvor klassisk Hamming-kode alene er utilstrækkelig.

GitHub Copilot kan scaffolde encoder- og dekoderfunktioner, generere paritetsbitmasker og udarbejde enhedstests fra en kort kommentar. Bekræft bitpositionsmatematikken og paritetsgruppenpings omhyggeligt, fordi off-by-one-indeksering er en hyppig kilde til fejl i genereret kode.

Opsummer dette indlæg med: