Tag archieven: Hamming code

Fouten verbeterende codes( deel 2)

Geplaatst op door

In een vorig artikel bespraken we Hamming-codes. De Hamming (7,4) code codeert een 4-bits boodschap p_1p_2p_3p_4 naar een 7-bits codewoord p_1p_2p_3p_4p_5p_6p_7, door drie even pariteitsbits toe te voegen:

    \[p_5=p_1+p_2+p_4\]

    \[p_6=p_1+p_3+p_4\]

    \[p_7=p_2+p_3+p_4\]

De vergelijkingen dienen modulo 2 bekeken te worden.

Dit zijn de 16 mogelijke codewoorden. Om 0100 te zenden, stuur je het codewoord 0100101 door. Als er 1 transmissiefout op zit en je ontvangt 0101101, dan kan de ontvanger de fout vinden door het dichts bijzijnde codewoord te gebruiken. Inderdaad, 0100101 is het enige codewoord dat in slechts 1 positie verschilt van 0101101.

Neem nu even de eerste zes bits van een codewoord  en verdeel ze als p_1p_2,p_3p_4 en p_5p_6. Gebruik nu het eindige veld met 4 elementen, gedefinieerd door volgende bewerkingen:

Neem nu terug  het codewoord 0100101. De punten (1,p_1p_2)=(1,1), (2,p_3p_4)=(2,0) en (3,p_5p_6)=(3,2) blijken alle drie op de rechte y=2x+3 te  liggen. Reken na met bovenstaande bewerkingstabellen. Deze eigenschap kan gebruikt worden bij het decoderen. Veronderstel dat het ontvangen  codewoord 0101101 is. Met de zes eerste bits vormen we, zoals hierboven beschreven drie punten A(1,1),B(2,1) en C(3,1). De rechte door A en B bevat C niet.Omdat de Hamming code 1 fout kan detecteren, veronderstellen we dat 1 van de punten fout is. De oorspronkelijke rechte is dus ofwel AB:y=1, AC:y=2x+3 of BC:y=3x. Dan zouden de zes eerste bits van het originele codewoord 010101,010010 of 110110 moeten zijn. Onder deze drie mogelijkheden voldoet enkel 010010 aan p_7=p_2+p_3+p_4 mod 2. Bijgevolg decoderen we de ontvangen boodschap 0101101 als 0100101 en was de oorspronkelijke boodschap 0100.

Deze proceduren lijkt erg complex. Ze kan echter veralgemeend worden om meer fouten verbeterende codes te construeren, door gebruik te maken van veeltermen in plaats van rechten.

Het idee om dergelijke veetermen te gebruiken werd het eerst naar voren gebracht door Reed en Solomon in 1960.

Foutenverbeterende codes

Geplaatst op door

Stel, je wilt de  boodschap HELLO doorgeven van de ene computer aan de andere. Dat kan bijvoorbeeld door gebruik te maken van een tabel die de boodschap omzet in binaire tekens. De ontvanger kan de boodschap dan decoderen met dezelfde tabel. Een voorbeeld van zo een tabel is de ASCII-tabel:

Maar er kunnen  fouten  bij het verzenden optreden; zo kan de letter H = 0100 1000 ontvangen worden als 01001010, wat de letter J geeft!

Een manier om te weten of er een fout is opgetreden, is het toevoegen van een extra bit aan de boodschap, het zogenaamde pariteitsbit. Voor een even pariteit code zorgen we ervoor dat het aantal 1-en altijd even is.

Zo wordt H = 0100 1000 0 ( de laatste nul is het pariteitsbit dat ervoor zorgt dat het totaal aantal enen even is). Als je nu 0100 1010 0 ontvangt, weet je dat er een fout in de verzending zit omdat er een oneven aantal enen staat. We spreken van een fout ontdekkende code : we weten dat er minstens 1 foute bit in de boodschap zit, maar we kunnen die niet verbeteren omdat we niet weten waar de fout zit

Het was de Amerikaanse wiskundige Richard Hamming (1915-1998) die een oplossing vond voor dit probleem.

Om een 4 bits rij d_1d_2d_3d_4 te coderen gebruikte hij 3 cirkels:

Hij plaatste de gegeven bits zoals hierboven gegeven en voegde er dan de even pariteitsbits p_1,p_2 en p_3 aan toe. Voor 1001 wordt de code dan 1001001. Als er nu een fout zit in het verzenden en er wordt 1011001 ontvangen, dan kan je door de pariteit te controleren in de drie cirkels zien dat de fout zit in de blauwe en rode,  maar niet in de groene cirkel. Dus bit d_3 was fout en de verzonden boodschap was dan 1001!

Dit is fouten verbeterende code. men noemt het de (7,4) Hamming code. De notatie (7,4) betekent dat elke 4 bits informatie gecodeerd worden als een 7 bit rijtje.