Inhoud
Hamming-codes worden gebruikt om foutcorrectie-informatie in gegevensstromen in te voegen. De codes zijn zo ontworpen dat een fout niet alleen wordt gedetecteerd, maar ook wordt gecorrigeerd. Door foutcorrectie-informatie toe te voegen, neemt de hoeveelheid gegevens toe, maar wordt ook de betrouwbaarheid van communicatie over media met hoge foutpercentages vergroot.
Hamming-codering kan ingewikkeld zijn om te implementeren, maar het kan heel snel worden gedaan met behulp van rekenkundige trucs op bitniveau. Dit maakt het mogelijk om een nuttig en snel foutcorrectiesysteem te creëren dat kan worden gebruikt in embedded applicaties.
Stap 1
Maak het datawoord. Elke bit met een positie met een macht van twee (eerste, tweede, vierde, etc.) moet worden gereserveerd voor pariteitsinformatie. Gebruik zo lang als nodig is om het woord de originele gegevens en pariteitsbits te laten hebben.
Voorbeeld:
1 1 0 1 0 0 1 0 wordt _ _ 1 _ 1 0 1 _ 0 0 1 0
De originele bits blijven in dezelfde volgorde, maar werden uitgespreid om de pariteitsbits in te voegen.
Stap 2
Bereken het eerste pariteitsbit. Beginnend met het eerste bit, wordt een bit gelezen en vervolgens wordt een bit overgeslagen en wordt de procedure herhaald tot het einde. Ondertussen wordt het aantal gevonden exemplaren geteld. Pariteitsbits tellen niet mee in dit proces.
Als het aantal enen even is, stelt u de eerste bit in op nul. Stel het anders in op één.
Voorbeeld:
Bits 1, 3, 5, 7, 9 en 11 van _ _ 1 _ 1 0 1 _ 0 0 1 0, _11101, bevatten vier enen. Dit is zelfs, dus het eerste bit wordt op nul gezet: 0 _ 1 _ 1 0 1 _ 0 0 1 0
Stap 3
Bereken de resterende pariteitsbits. Beginnend met het tweede bit, worden twee bits gelezen en vervolgens worden twee bits overgeslagen en wordt de procedure herhaald tot het einde. De vierde bit leest vier bits, slaat er nog eens vier over, te beginnen met bit vier. Hetzelfde patroon wordt gevolgd door alle pariteitsbits, totdat ze allemaal berekend zijn.
Voorbeeld:
Bit 2: 0 _ 1 _ 1 0 1 _ 0 0 1 0 controleert _1, 01, 01, die drie enen bevatten, dus bit 2 is ingesteld op één. Bit 4: _ 0 1 1 1 0 1 _ 0 0 1 0 controleert _101, 0, die twee enen bevat, dus bit 4 wordt op nul gezet. Bit 8: 0 1 1 0 1 0 1 _ 0 0 1 0 controleert _0010, die er slechts één bevat, dus bit 8 is ingesteld op één.
Het woord is daarom gecodeerd als 011010110010.
Stap 4
Bevestig het woord. Als een woord beschadigd is, zullen de pariteitsbits niet overeenkomen met wat wordt verwacht. Om te bevestigen dat het woord niet beschadigd is, berekent u gewoon de pariteitsbits met behulp van stap twee en drie. Als de bits niet hetzelfde zijn, noteert u hun posities.
Stap 5
Corrigeer het verkeerde bit. Als u onjuiste pariteitsbits vindt, voegt u gewoon de posities van de bits toe. De somwaarde is de positie van de verkeerde bit. Verander de bitwaarde in deze positie.
Als de onjuiste pariteitsbits bijvoorbeeld één en vier zijn, wordt de fout gecorrigeerd door de waarde van de vijfde bit te wijzigen.