Hamming-code: voorbeelden van foutcorrectie

Wat is een fout?

Verzonden gegevens kunnen tijdens de communicatie beschadigd raken. Het wordt waarschijnlijk beïnvloed door externe ruis of andere fysieke storingen. In een dergelijke situatie kunnen de invoergegevens niet hetzelfde zijn als de uitvoergegevens. Deze mismatch staat bekend als 'Fout'.

De gegevensfouten kunnen leiden tot het verlies van belangrijke of beveiligde gegevens. De meeste gegevensoverdracht in digitale systemen zal plaatsvinden in de vorm van 'Bitoverdracht'. Zelfs een klein beetje verandering kan de prestaties van het hele systeem beïnvloeden. Als in een gegevensreeks 1 wordt gewijzigd in 0 of 0 wordt gewijzigd in 1, wordt dit 'Bitfout' genoemd.

In deze Hamming-code-tutorial leer je:

Soorten fouten

Er zijn hoofdzakelijk drie soorten bitfouten die optreden bij gegevensoverdracht van de zender naar de ontvanger.

  • Enkele bit fouten
  • Meerdere bitfouten
  • Burst-fouten

Enkele bit fouten

De wijziging die in één bit in de gehele gegevensreeks wordt aangebracht, staat bekend als 'Single bit error'. Het optreden van een enkele bitfout is echter niet zo gebruikelijk. Bovendien treedt deze fout alleen op in een parallel communicatiesysteem omdat de gegevens bitsgewijze in een enkele lijn worden overgedragen. Daarom is er meer kans dat een enkele lijn luidruchtig kan zijn.

Meerdere bitfouten

Als er in gegevensreeksen een verandering is in twee of meer bits van een gegevensreeks van een zender naar ontvanger, staat dit bekend als 'Multiple bit errors'.

Dit type fout komt meestal voor in zowel seriële als parallelle datacommunicatienetwerken.

Burst-fouten

De verandering van de set bits in de gegevensreeks staat bekend als 'Burst-fout'. Dit type gegevensfout wordt berekend vanaf de eerste bitwijziging tot de laatste bitwijziging.

Wat is foutdetectie en -correctie?

In een digitaal communicatiesysteem worden fouten van het ene communicatiesysteem naar het andere overgedragen. Als deze fouten niet worden gedetecteerd en gecorrigeerd, gaan de gegevens verloren. Voor effectieve communicatie moeten systeemgegevens met hoge nauwkeurigheid worden overgedragen. Dit zal worden gedaan door eerst de fouten te identificeren en deze te corrigeren.

Foutdetectie is een methode om de fouten te detecteren die aanwezig zijn in de gegevens die worden verzonden van een zender naar een ontvanger in een datacommunicatiesysteem.

Hier kunt u redundantiecodes gebruiken om deze fouten te vinden, door gegevens toe te voegen wanneer deze door de bron worden verzonden. Deze codes worden 'Foutdetectiecodes' genoemd.

Drie soorten foutdetectiecodes zijn:

  • Pariteitscontrole
  • Cyclische redundantiecontrole (CRC)
  • Longitudinale redundantiecontrole (LRC)

Pariteitscontrole:

  • Het wordt ook wel een pariteitscontrole genoemd.
  • Het heeft een kosteneffectief mechanisme voor foutdetectie.
  • Bij deze techniek staat de redundante bit bekend als een pariteitsbit. Het wordt voor elke data-eenheid toegevoegd. Het totale aantal enen in de eenheid moet even worden, wat bekend staat als een pariteitsbit.

Longitudinale redundantiecontrole

Bij deze foutdetectietechniek wordt een blok bits georganiseerd in tabelvorm. De LRC-methode helpt u bij het berekenen van de pariteitsbit voor elke kolom. De set van deze pariteit wordt ook meegestuurd met de originele data. Het pariteitsblok helpt u om de redundantie te controleren.

Cyclische redundantiecontrole

Cyclische redundantiecontrole is een reeks redundantie die aan het einde van de unit moet worden toegevoegd. Daarom moet de resulterende data-eenheid deelbaar worden door een tweede, vooraf bepaald binair getal.

Op de bestemming moeten de binnenkomende gegevens door hetzelfde getal worden gedeeld. In het geval dat er geen rest is, wordt aangenomen dat de data-eenheid correct is en wordt geaccepteerd. Anders geeft het aan dat de data-eenheid beschadigd is tijdens verzending en daarom moet worden afgewezen.

Wat is een Hamming-code?

Hamming-code is een voeringcode die nuttig is voor foutdetectie tot twee directe bitfouten. Het is in staat tot single-bit fouten.

In Hamming-code codeert de bron het bericht door redundante bits aan het bericht toe te voegen. Deze redundante bits worden meestal ingevoegd en gegenereerd op bepaalde posities in het bericht om het foutdetectie- en correctieproces te bewerkstelligen.

Geschiedenis van Hamming-code

  • Hamming-code is een techniek die door R.W.Hamming is ontwikkeld om fouten te detecteren.
  • Hamming-code moet worden toegepast op gegevenseenheden van elke lengte en maakt gebruik van de relatie tussen gegevens en redundantiebits.
  • Hij werkte aan het probleem van de foutcorrectiemethode en ontwikkelde een steeds krachtigere reeks algoritmen, de Hamming-code.
  • In 1950 publiceerde hij de Hamming-code, die tegenwoordig veel wordt gebruikt in toepassingen zoals ECC-geheugen.

Toepassing van Hamming-code:

Hier zijn enkele veelvoorkomende toepassingen van het gebruik van Hemming-code:

  • Satellieten
  • Computer geheugen
  • Modems
  • PlasmaCAM
  • Open connectoren
  • Afschermingsdraad
  • Geïntegreerde processor

Voordelen van Hamming-code:

  • De Hamming-codemethode is effectief op netwerken waar de gegevensstromen worden gegeven voor de single-bit-fouten.
  • Hamming-code biedt niet alleen de detectie van een bitfout, maar helpt u ook bij het inspringen van bits die een fout bevatten, zodat deze kan worden gecorrigeerd.
  • Het gebruiksgemak van hamming-codes maakt ze het beste geschikt voor gebruik in computergeheugen en voor het corrigeren van enkele fouten.

Nadelen van Hamming-code

  • Single-bit foutdetectie en correctiecode. Als er echter meerdere bits gegrond zijn, kan de uitkomst resulteren in een ander bit dat correct moet worden gewijzigd. Dit kan ertoe leiden dat de gegevens nog meer fouten bevatten.
  • Hamming-code-algoritme kan alleen problemen met enkele bits oplossen.

Proces van het coderen van een bericht met Hamming Code

Het proces dat door de afzender wordt gebruikt om het bericht te coderen, omvat de volgende drie stappen:

  • Berekening van het totale aantal overtollige bits.
  • Controle van de positie van de overtollige bits.
  • Ten slotte, het berekenen van de waarden van deze overtollige bits.

Wanneer de bovenstaande redundante bits zijn ingebed in het bericht, wordt het naar de gebruiker verzonden.

Stap 1) Berekening van het totale aantal redundante bits.

Stel dat het bericht het volgende bevat:

  • N - aantal databits
  • P - aantal redundante bits die eraan worden toegevoegd zodat np tenminste (n + p + 1) verschillende toestanden kan aangeven.

Hier geeft (n + p) de locatie van een fout in elk van de (n + p) bitposities weer en één extra status geeft geen fout aan. Omdat p-bits 2 . kunnen aangevenPstaten, 2Pmoet minimaal gelijk zijn aan (n + p + 1).

Stap 2) Het plaatsen van de overtollige bits in hun juiste positie.

De p redundante bits moeten op bitposities met machten van 2 worden geplaatst. Bijvoorbeeld 1, 2, 4, 8, 16, enz. Ze worden p genoemd1(op positie 1), p2(op positie 2), p3(op positie 4), enz.

Stap 3) Berekening van de waarden van de redundante bit.

De overtollige bits moeten pariteitsbits zijn, waardoor het aantal enen even of oneven is.

De twee soorten pariteit zijn ?

  • Het totale aantal bits in het bericht dat even is gemaakt, wordt even pariteit genoemd.
  • Het totale aantal bits in het bericht dat oneven wordt gemaakt, wordt oneven pariteit genoemd.

Hier moet alle overtollige bit, p1, worden berekend als de pariteit. Het moet alle bitposities dekken waarvan de binaire weergave een 1 op de 1e positie moet bevatten, exclusief de positie van p1.

P1 is het pariteitsbit voor alle databits in posities waarvan de binaire representatie een 1 bevat op de minder belangrijke positie, exclusief 1 Like (3, 5, 7, 9, .... )

P2 is het pariteitsbit voor alle databits in posities waarvan de binaire weergave 1 bevat op de positie 2 van rechts, niet inclusief 2 Like (3, 6, 7, 10, 11,...)

P3 is de pariteitsbit voor elk bit in posities waarvan de binaire weergave een 1 bevat op de positie 3 van rechts, niet inclusief 4 Like (5-7, 12-15,... )

Proces van het decoderen van een bericht in Hamming-code

Ontvanger ontvangt inkomende berichten die herberekeningen nodig hebben om fouten te vinden en te corrigeren.

Het herberekeningsproces gebeurt in de volgende stappen:

  • Tellen van het aantal overtollige bits.
  • Correcte positionering van alle overtollige bits.
  • Pariteitscontrole

Stap 1) Het aantal overtollige bits tellen

U kunt dezelfde formule gebruiken voor het coderen, het aantal overtollige bits

2P? n + p + 1

Hier is het aantal databits en p is het aantal overtollige bits.

Stap 2) Alle overbodige bits correct plaatsen

Hier is p een redundante bit die zich op bitposities van machten van 2 bevindt, bijvoorbeeld 1, 2, 4, 8, enz.

Stap 3) Pariteitscontrole

Pariteitsbits moeten worden berekend op basis van databits en de redundante bits.

p1 = pariteit (1, 3, 5, 7, 9, 11…)

p2 = pariteit (2, 3, 6, 7, 10, 11... )

p3 = pariteit (4-7, 12-15, 20-23... )

Samenvatting

  • Verzonden gegevens kunnen beschadigd raken tijdens communicatie
  • Drie soorten bitfouten zijn 1) Enkele bitfouten 2) Meerdere bitfouten 3) Burstbitfouten
  • De wijziging die in één bit in de gehele gegevensreeks wordt aangebracht, staat bekend als 'Single bit error'.
  • Als er in gegevensreeksen een verandering is in twee of meer bits van een gegevensreeks van een zender naar ontvanger, staat dit bekend als 'Multiple bit errors'.
  • De verandering van de set bits in de gegevensreeks staat bekend als 'Burst-fout'.
  • Foutdetectie is een methode om de fouten te detecteren die aanwezig zijn in de gegevens die van een zender naar een ontvanger in een datacommunicatiesysteem worden verzonden
  • Er zijn drie soorten foutdetectiecodes: 1) Pariteitscontrole 2) Cyclische redundantiecontrole (CRC) 3) Longitudinale redundantiecontrole (LRC)
  • Hamming-code is een voeringcode die nuttig is voor foutdetectie tot twee directe bitfouten. Het is in staat tot single-bit fouten.
  • Hamming-code is een techniek die door R.W.Hamming is ontwikkeld om fouten te detecteren.
  • Veelvoorkomende toepassingen voor het gebruik van Hemming-code zijn satellieten, computergeheugen, modems, ingebouwde processors, enz.
  • Het grootste voordeel van de hamming-codemethode is effectief op netwerken waar de gegevensstromen worden gegeven voor de single-bit-fouten.
  • Het grootste nadeel van de hamming-codemethode is dat deze alleen problemen met enkele bits kan oplossen.
  • We kunnen het proces van het coderen en decoderen van het bericht uitvoeren met behulp van hamming-code.