Hamming-code: foutdetectie en -correctie met voorbeelden

Wat is een fout?

Verzonden gegevens kunnen tijdens de communicatie beschadigd raken. Het wordt waarschijnlijk beïnvloed door externe geluiden of andere fysieke storingen. In een dergelijke situatie kunnen de invoergegevens niet hetzelfde zijn als de uitvoergegevens. Deze discrepantie staat bekend als ‘fout’.

De gegevensfouten kunnen resulteren in het verlies van belangrijke of beveiligde gegevens. Het grootste deel van de 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 een ‘bitfout’ genoemd.

Soorten fouten

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

• Enkele bitfouten
• Meerdere bitfouten
• Burst-fouten

Enkele bitfouten

De verandering die in één bit in de gehele datareeks wordt gemaakt, staat bekend als "Single bit error". Het voorkomen van een single-bit error komt echter niet zo vaak voor. Bovendien treedt deze fout alleen op in een parallel communicatiesysteem, omdat data bitsgewijs in één lijn wordt overgedragen. Daarom is de kans groter dat één lijn ruis bevat.

Meerdere bitfouten

Als er in de datareeks een verandering optreedt in twee of meer bits van een datareeks van een zender naar een ontvanger, staat dit bekend als 'meerdere bitfouten'.

Dit type fout komt vooral 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 datafout wordt berekend vanaf de eerste bitverandering tot de laatste bitverandering.

Wat is foutdetectie en foutcorrectie?

Bij digitale communicatiesystemen 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 gebeurt door eerst de fouten te identificeren en deze vervolgens te corrigeren.

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

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

Er zijn drie soorten foutdetectiecodes:

• Pariteitscontrole
• Cyclic Redundancy Check (CRC)
• Longitudinale redundantiecontrole (LRC)

Pariteitscontrole

• Het wordt ook wel een pariteitscontrole genoemd.
• Het heeft een kosteneffectief mechanisme voor foutdetectie.
• Bij deze techniek staat het redundante bit bekend als een pariteitsbit. Het wordt voor elke data-eenheid toegevoegd. Het totale aantal enen in de eenheid moet gelijk 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 gegevens. Het pariteitsblok helpt u de redundantie te controleren.

Cyclische redundantiecontrole

Cyclische redundantiecontrole is een reeks redundantie die aan het einde van de eenheid 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 worden gedeeld door hetzelfde getal. Als er geen rest is, wordt aangenomen dat de data-eenheid correct is en wordt deze geaccepteerd. Anders geeft dit aan dat de data-eenheid tijdens de transmissie is beschadigd en daarom moet deze worden afgewezen.

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

Geschiedenis van de Hamming-code

• Hamming-code is een techniek die door RWHamming is ontwikkeld om fouten te detecteren.
• Hamming-code moet worden toegepast op data-eenheden van elke lengte en gebruikt de relatie tussen data en redundantiebits.
• Hij werkte aan het probleem van de foutcorrectiemethode en ontwikkelde een steeds krachtiger arsenaal aan algoritmen, de zogenaamde Hamming-code.
• In 1950 publiceerde hij de Hamming Code, die tegenwoordig veel wordt gebruikt in toepassingen als ECC-geheugen.

Toepassing van Hamming-code

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

• satellieten
• Computer geheugen
• modems
• PlasmaCAM
• Open connectoren
• Afschermingsdraad
• Embedded Processor

Voordelen van Hamming-code

• De Hamming-codemethode is effectief op netwerken waar de datastromen worden gegeven voor de enkelbitsfouten.
• Hamming-code zorgt niet alleen voor de detectie van een bitfout, maar helpt u ook om bits met fouten te laten inspringen, zodat deze kunnen worden gecorrigeerd.
• Het gebruiksgemak van hamming-codes maakt ze het meest geschikt voor gebruik in computergeheugen en correctie van enkele fouten.

Nadelen van Hamming-code

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

Hoe een bericht te coderen in Hamming Code

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

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

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

Stap 1) Berekening van het totale aantal redundante bits.

Laten we aannemen dat het bericht het volgende bevat:

• n– aantal databits
• p – aantal redundante bits die eraan worden toegevoegd zodat np minimaal (n + p + 1) verschillende toestanden kan aangeven.

Hier geeft (n + p) de locatie weer van een fout in elk van de (n + p) bitposities en geeft één extra toestand aan dat er geen fout is. Zoals p bits 2 kunnen aangeven^p staten, 2^p moet minimaal gelijk zijn aan (n + p + 1).

Stap 2) Het plaatsen van de redundante bits op de 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 genoemd.₁ (op positie 1), p₂ (op positie 2), p₃ (op positie 4), enz.

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

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

De twee soorten pariteit zijn?

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

Hier moet alle redundante bit, p1, worden berekend als de pariteit. Het moet alle bitposities bestrijken waarvan de binaire weergave een 1 op de eerste positie moet bevatten, met uitzondering van de positie van p1.

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

P2 is de pariteitsbit voor alle databits op posities waarvan de binaire representatie 1 omvat op positie 2 van rechts, exclusief 2 Like (3, 6, 7, 10, 11, ...)

P3 is de pariteitsbit voor elke bit op posities waarvan de binaire representatie een 1 bevat op de positie 3 van rechts, exclusief 4 zoals (5-7, 12-15,…)

Een bericht decoderen in Hamming-code

De ontvanger ontvangt inkomende berichten die herberekeningen vereisen om fouten te vinden en te corrigeren.

Het herberekeningsproces verloopt in de volgende stappen:

• Het tellen van het aantal redundante bits.
• Correcte positionering van alle redundante bits.
• Pariteitscontrole

Stap 1) Het tellen van het aantal redundante bits

U kunt dezelfde formule gebruiken voor het coderen van het aantal redundante bits

2^p ? n+p+1

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

Stap 2) Het correct plaatsen van alle overtollige bits

Hier is p een redundant bit dat zich bevindt op bitposities met machten van 2, 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 tijdens de communicatie beschadigd raken
• Er zijn drie soorten bitfouten: 1) Enkele bitfouten 2) Meervoudige bitfouten 3) Burstbitfouten
• De wijziging die in één bit in de gehele gegevensreeks wordt aangebracht, staat bekend als 'Single bit error'.
• Als er in de datareeks een verandering optreedt in twee of meer bits van een datareeks van een zender naar een ontvanger, staat dit bekend als 'meerdere bitfouten'.
• De verandering van de set bits in de gegevensreeks staat bekend als "Burst-fout".
• Foutdetectie is een methode voor het detecteren van de fouten die aanwezig zijn in de gegevens die van een zender naar een ontvanger worden verzonden in een datacommunicatiesysteem
• Er zijn drie soorten foutdetectiecodes: 1) Pariteitscontrole 2) Cyclische redundantiecontrole (CRC) 3) Longitudinale redundantiecontrole (LRC)
• Hamming-code is een linercode die nuttig is voor foutdetectie tot twee onmiddellijke bitfouten. Het is in staat tot fouten van één bit.
• Hamming-code is een techniek die door RWHamming is ontwikkeld om fouten te detecteren.
• Veel voorkomende toepassingen van het gebruik van Hamming-code zijn satellietcomputergeheugen, modems, ingebouwde processor, enz.
• Het grootste voordeel van de hamming-codemethode is effectief op netwerken waar de datastromen worden gegeven voor de enkelbitsfouten.
• 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.