Hamming-code

Van Wikipedia

In de telecommunicatie is een Hamming-code een foutcorrigerende code, genoemd naar de uitvinder, Richard Hamming. Hamming-codes zijn lineaire codes, en zij kunnen 1 of 2 bitfouten detecteren, of 1 bitfout corrigeren. Dit in tegenstelling tot het gebruik van een enkelvoudige pariteitscontrole (met 1 partiteitsbit), die een even aantal bitfouten niet detecteert, en die geen hulp kan bieden voor het corrigeren van gevonden bitfouten.

Inhoud

1 Geschiedenis
2 Codes die vooraf gingen aan de Hamming-code
3 Hamming-codes
4 Voorbeeld aan de hand van de (11,7) Hamming code
5 Hamming (7,4) code
6 Een toelichting met vectorrekening
7 Zie ook

[bewerk] Geschiedenis

Hamming werkte in de jaren '40 bij Bell Labs aan de Bell Model V computer, een elektromechanisch met relais uitgevoerde kolos met een cyclustijd van enkele seconden. De invoer van gegevens vond plaats via ponskaarten, waar altijd leesfouten bij optraden. Tijdens weekdagen zorgde een speciale code ervoor dat fouten werden gedetecteerd en via lichtsignalen de operators werden gewaarschuwd, zodat die het probleem konden verhelpen. Buiten kantooruren en tijdens weekends, wanneer er geen operators aanwezig waren, ging de machine eenvoudigweg door met de volgende taak.

Hamming werkte tijdens weekends, en werd steeds gefrustreerder over het opnieuw moeten starten van zijn programma's vanwege de onbetrouwbaarheid van de kaartlezer. Gedurende een aantal jaren werkte hij aan het vraagstuk van foutcorrectie, waarbij hij een set krachtige algoritmes ontwikkelde. In 1950 publiceerde hij wat nu bekend staat als de Hamming-code, die momenteel in bepaalde situaties nog steeds toegepast wordt.

[bewerk] Codes die vooraf gingen aan de Hamming-code

Een aantal eenvoudige foutdetecterende codes was reeds eerder in gebruik, maar deze waren bij gelijke redundantie veel minder effectief dan Hamming-codes. Enkele worden hier kort beschreven.

[bewerk] Pariteitsbit

Er wordt een enkel bit toegevoegd aan een codewoord dat aangeeft of er in dat woord een even dan wel een oneven aantal bits de waarde 1 heeft. Een enkelvoudige bitfout op het transmissiepad verandert de pariteit, waardoor de fout gedetecteerd wordt. Een even aantal bitfouten wordt hierdoor echter niet opgemerkt. Daarnaast is het zo dat bij detectie van een bitfout er niet duidelijk is welk bit fout is ontvangen; de enig mogelijke correctiemethode is het uitvoeren van een hertransmissie.

[bewerk] 'Twee van vijf' code

Tijdens de jaren '40 gebruikte Bell ook een iets meer geavanceerde code, die bekend stond als two-of-five. Deze code had de eigenschap dat elk 5-bits codewoord exact twee enen bevatte. Tegenwoordig noemen we dit een constant gewicht code. Als de input van de computer een woord ontving met niet exact twee enen, dan vond foutdetectie plaats. Ook bij deze code kan het echter voorkomen dat 2 bitfouten in 1 woord niet worden gedetecteerd.

[bewerk] Repetitiecode

Een andere code herhaalde simpelweg ieder databit een aantal malen. Bijvoorbeeld als het te verzenden databit een 1 was, verzond een n=3 repetitiecode het woord "111". Als de drie ontvangen bits niet identiek waren, was er foutdetectie. De foutcorrectie werkt hierbij als volgt: bij ontvangst van 000, 001, 010 of 100 wordt het gedecodeerde databit een 0, terwijl ontvangst van 111, 110, 101, of 011 resulteert in decodering als 1, alsof de ontvangen bits 'democratisch' aangeven wat het originele bit is. Dit is een elementair voorbeeld van een foutcorrigerende code.

Uiteraard kunnen zulke codes niet alle mogelijke fouten op correcte wijze corrigeren. Bovendien is de repetitiecode zeer inefficiënt.

[bewerk] Hamming-codes

Wanneer er meer foutcorrigerende bits worden toegevoegd aan een boodschap, en als deze bits zo worden gerangschikt dat verschillende 'foute' bits verschillende effecten opleveren, dan worden foutieve bits identificeerbaar. In een 7-bit boodschap zijn er zeven enkelvoudige bitfouten mogelijk, dus drie redundante bits zijn in beginsel voldoende om niet alleen aan te geven dat er een fout is opgetreden, maar ook (bij een enkelvoudige bitfout) welk bit foutief is.

Hamming bestudeerde de bestaande codes, inclusief two-of-five, en zocht naar generalisaties. Bijvoorbeeld bij gebruik van een pariteitsbit wordt aan elk datawoord een enkel bit toegevoegd; uitgaande van ASCII woorden die bestaan uit 7 bits, omschreef Hamming dit als een (8,7) code, met in totaal acht bits, waarvan er 7 databits zijn. De repetitiecode in het voorbeeld zou op deze wijze een (3,1) code genoemd worden. De information rate is het tweede getal gedeeld door het eerste, voor onze repetitiecode 1/3.

Hamming onderzocht ook de problemen die ontstaan bij twee of meer bitfouten, en ontwikkelde het concept van de Hammingafstand. De pariteitscode heeft een afstand 2, want iedere tweevoudige bitfout wordt niet opgemerkt. De (3,1) repetitiecode heeft afstand 3, want van een legaal codewoord (000 of 111) moeten er drie bits worden veranderd om een ander legaal codewoord te verkrijgen.

Hamming was geïnteresseerd in twee problemen; hij wilde zowel de afstand zoveel mogelijk verhogen (en daarmee het foutcorrigerend vermogen), als de information rate (gemiddelde informatie-inhoud van een transmissie-bit) zo groot mogelijk krijgen. Tijdens de jaren '40 ontwikkelde hij diverse codes die een grote verbetering waren ten opzichte van reeds bestaande codes. Al zijn systemen hadden als eigenschap dat de pariteitsbits zowel elkaar 'controleerden' als de databits.

Het algoritme van de (gegeneraliseerde) Hamming-code is simpel:

alle bitposities die tweemacht zijn worden gebruikt als pariteitsbits (bitposities 1, 2, 4, 8, 16, 32, 64, etc.)
alle overige bitposities worden gebruikt voor de te coderen data (bitposities 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.)
ieder pariteitsbit berekent de pariteit voor een aantal bits uit het codewoord. De positie van het pariteitsbit bepaalt de rij van de bits die wel resp. niet worden meegenomen in het berekenen van het pariteitsbit.
- pos. 1: check 0 bits, skip 1 bit, check 1 bit, skip 1 bit, check 1 bit, etc.
- pos. 2: check 1 bit, skip 2 bits, check 2 bits, skip 2 bits, check 2 bits, etc.
- pos. 4: check 3 bits, skip 4 bits, check 4 bits, skip 4 bits, check 4 bits, etc.
- pos. 8: check 7 bits, skip 8 bits, check 8 bits, skip 8 bits, check 8 bits, etc.
- pos. 16: check 15 bits, skip 16 bits, check 16 bits, skip 16 bits, check 16 bits, etc.
- pos. 32: check 31 bits, skip 32 bits, check 32 bits, skip 32 bits, check 32 bits, etc.
- enzovoorts

[bewerk] Voorbeeld aan de hand van de (11,7) Hamming code

Beschouw het 7-bit datawoord "0110101". Zie de tabellen ter illustratie van hoe Hamming-codes worden ontworpen en gebruikt om een fout te detecteren. Met d wordt een databit aangegeven, en met p een pariteitsbit.

Eerst worden de databits in de correcte bitpositie geplaatst en vervolgens worden de pariteitsbits berekend, steeds uitgaande van even pariteit.

*Berekening van Hamming-code pariteitsbits*
	p₁	p₂	d₁	p₃	d₂	d₃	d₄	p₄	d₅	d₆	d₇
datawoord (zonder pariteit):			0		1	1	0		1	0	1
p₁	1		0		1		0		1		1
p₂		0	0			1	0			0	1
p₃				0	1	1	0
p₄								0	1	0	1
codewoord (met pariteit):	1	0	0	0	1	1	0	0	1	0	1

Het codewoord (met pariteitsbits) is "10001100101".

Neem nu aan dat het laatste bit foutief wordt ontvangen. Ons ontvangen woord is "10001100100"; en nu zetten we ieder pariteitsbit op 1 indien de pariteitscontrole een foutdetectie oplevert.

*Controle van pariteitsbits* (veranderd bit gemarkeerd)
	p₁	p₂	d₁	p₃	d₂	d₃	d₄	p₄	d₅	d₆	d₇	Pariteitscheck	Pariteitsbit
Ontvangen woord:	1	0	0	0	1	1	0	0	1	0	0	1
p₁	1		0		1		0		1		0	Detectie	1
p₂		0	0			1	0			0	0	Detectie	1
p₃				0	1	1	0					Correct	0
p₄								0	1	0	0	Detectie	1

De laatste stap is het bepalen van de waarde van de pariteitsbits (het bit met de laagste waarde gaat het verste naar rechts). De decimale waarde van de pariteitsbits is 11, waaruit volgt dat het elfde bit in het ontvangen woord (incl. pariteitsbits) foutief is, en dus dient te worden geïnverteerd.

	p₄	p₃	p₂	p₁
binair	1	0	1	1
decimaal	8		2	1	Σ = 11

Inverteren van het elfde bit verandert 10001100100 terug naar 10001100101. Verwijderen van de Hamming pariteitsbits levert het oorspronkelijke datawoord 0110101 op.

Omdat de pariteitsbits elkaar niet checken, is bij foutdetectie voor één enkel pariteitsbit, de oorzaak dat het pariteitsbit zelf fout is, en niet een van de erdoor gecontroleerde databits.

Neem nu aan dat twee bits veranderen, op de posities x en y. Als x en y binair geschreven op positie 2^k dezelfde bitwaarde hebben, dan zal het pariteitsbit op die positie niet van waarde veranderen omdat beide bitfouten worden 'gecheckt'. Echter, er moeten pariteitsbits zijn die van waarde veranderen, omdat x en y niet op iedere positie dezelfde bitwaarde hebben. Hieruit volgt dat de Hamming-code alle dubbele bitfouten detecteert.

[bewerk] Hamming (7,4) code

Nu (2005) wordt met Hamming-code een specifieke (7,4) code aangeduid, die door Hamming werd geïntroduceerd in 1950. De Hamming-code voegt drie checkbits toe aan iedere vier databits van de te verzenden boodschap. Hamming's (7,4) code kan iedere enkelvoudige bitfout corrigeren, en alle dubbele bitfouten detecteren. Voor in de praktijk voorkomende kanalen zou gebruik van de Hamming-code een foutvrij informatietransport realiseren.

[bewerk] Een toelichting met vectorrekening

Een Hamming-code is een voorbeeld van een lineaire code. Hamming codes maken gebruik van vermenigvuldiging van matrices en vormen een uitbreiding op het concept 'pariteit'. Bijvoorbeeld voor de (7,4) Hamming-code, gebruiken we twee matrices, namelijk

$H_e := \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ \end{pmatrix}$ (encoderen)

$H_d := \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix}$ (decoderen)

Opmerking:

H e

is de getransponeerde van de generatormatrix G, dus

$\mathbf{G} = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{pmatrix}$

In het huidige voorbeeld wordt de notatie met

H e

aangehouden, dus de getransponeerde notatie ten opzichte van de notatie met G.

H d

is de parity check matrix die correspondeert met G (zie lineaire code).

We gebruiken 'blokken' van vier databits (vandaar de 4 in de naam), en berekenen drie redundante checkbits (vandaar de 7 in de naam, want 4+3=7). Om de data te versturen, beschouwen we het blok te versturen databits als een vector, bijvoorbeeld bij de databits "1011" is het de vector

$\mathbf{p}=\begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}$

Stel dat we deze databits willen versturen. We vermenigvuldigen de matrix $H e$ met p, uiteraard rekenend modulo 2:

$H_e\mathbf{p} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ \end{pmatrix}\begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}= \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}=\mathbf{r}$

De ontvanger zal de ontvangen r vermenigvuldigen met $H d$ , om na te gaan of er een fout is opgetreden. Dit levert op (wederom modulo 2 rekenend):

$H_d\mathbf{r} = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix}\begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}$

In dit geval is de uitkomst de nulvector, dus de ontvanger kan concluderen dat er geen bitfouten zijn opgetreden.

Neem nu aan dat er een enkelvoudige bitfout is opgetreden. We kunnen het ontvangen woord schrijven als

$\mathbf{r}+\mathbf{e}_i$

modulo 2, waarbij e_i eenheidsvector nummer i is: een vector gevuld met nullen maar met een 1 op positie i. Dus $\mathbf{r}+\mathbf{e}_i$ komt overeen met een enkelvoudige bitfout op plaats i.

Als we deze vector vermenigvuldigen met $H d$ :

$H_d(\mathbf{r}+\mathbf{e}_i) = H_d\mathbf{r} + H_d\mathbf{e}_i$

Omdat r het ontvangen codewoord is indien er geen bitfouten zijn, is het product van $H d$ en r gelijk aan nul. Dus

$H_d\mathbf{r} + H_d\mathbf{e}_i = \mathbf{0} + H_d\mathbf{e}_i = H_d\mathbf{e}_i$

Het product van $H d$ met eenheidsvector nummer i zal de kolom zijn van $H d$ die staat op de bitpositie waar de fout is opgetreden. De kolommen van $H d$ verschillen allen van elkaar en staan in een speciale volgorde: als we iedere kolom opvatten als een binair geschreven geheel getal, dan staan de kolommen exact in oplopende volgorde met stapgrootte 1.

Als we uitgaan van het ontvangen woord $\mathbf{s}$ , dan heeft het dus zin om $H_d\mathbf{s}$ om te zetten in een binair getal; bijvoorbeeld (1, 0, 1) is een kolom van $H d$ en correspondeert met plaats 5. Als er sprake is van een enkelvoudige bitfout, weten we dan waar de fout is opgetreden, en kunnen deze corrigeren.

Stel bijvoorbeeld dat

$\mathbf{s} = \mathbf{r}+\mathbf{e}_2 = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix}$

Dan is

$H_d\mathbf{s} = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix}\begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}$

wat overeenkomt met kolom 2 (decimale vertaling van het binaire "010"); er is dus een fout opgetreden in plaats 2, en deze kan nu worden gecorrigeerd.

Het is niet moeilijk om aan te tonen dat uitsluitend enkelvoudige bitfouten op deze wijze kunnen worden gecorrigeerd. Echter, Hamming-codes kunnen ook worden gebruikt om zowel enkelvoudige als dubbele bitfouten te detecteren, door op te merken dat het product van $H d$ met $\mathbf{s}$ ongelijk is aan nul ingeval van bitfouten. Immers, in het geval van twee bitfouten, is het ontvangen woord $\mathbf{s} = \mathbf{r}+\mathbf{e}_i+\mathbf{e}_j$ en is $H_d\mathbf{s}$ gelijk aan de som van twee kolommen van $H d$ ; dit zal nooit de nulvector zijn, want alle kolommen zijn verschillend. Twee bitfouten worden dus altijd gedetecteerd.

Tegelijkertijd enkelvoudige bitfouten corrigeren en dubbele bitfouten detecteren is niet mogelijk. De keuze is dus tussen:

correctie van enkelvoudige bitfouten
detectie van zowel enkelvoudige als dubbele bitfouten

[bewerk] Zie ook

Categorieën: Discrete wiskunde | Lineaire algebra | Code