Hamming-code

Hamming werkte in de jaren 40 bij Bell Labs aan de Bell Model V computer, een elektromechanische met relais uitgevoerde kolos met een cyclustijd van enkele seconden. De invoer van gegevens vond plaats via ponskaarten, waarbij altijd leesfouten optraden. Tijdens werkdagen 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 bekendstaat als de Hamming-code, die momenteel in bepaalde situaties nog steeds toegepast wordt.

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.

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.

Tijdens de jaren 40 gebruikte Bell ook een iets meer geavanceerde code, die bekendstond 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.

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.

 

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-letters 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 zo veel 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:

1. alle bitposities die tweemacht zijn worden gebruikt als pariteitsbits (bitposities 1, 2, 4, 8, 16, 32, 64 etc.)
2. alle overige bitposities worden gebruikt voor de te coderen data (bitposities 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17 etc.)
3. 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 respectievelijk niet worden meegenomen in het berekenen van het pariteitsbit.
   • Pariteit bit 1: bit 1 (de pariteit bit zelf), 3, 5, 7, 9, etc.
   • Pariteit bit 2: bit 2 (de pariteit bit zelf), 3, 6, 7, 10,11, etc.
   • Pariteit bit 4: bit 4 (de pariteit bit zelf), 5, 6, 7, 12,13,14,15, etc.
   • Pariteit bit 8: bit 8 (de pariteit bit zelf), 9, 10, 11, 12,13,14,15, etc.
   • enzovoorts

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

	p1	p2	d1	p3	d2	d3	d4	p4	d5	d6	d7
datawoord (zonder pariteit):			0		1	1	0		1	0	1
p1	1		0		1		0		1		1
p2		0	0			1	0			0	1
p3				0	1	1	0
p4								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)

	p1	p2	d1	p3	d2	d3	d4	p4	d5	d6	d7	Pariteitscheck	Pariteitsbit
Ontvangen woord:	1	0	0	0	1	1	0	0	1	0	0	1
p1	1		0		1		0		1		0	Detectie	1
p2		0	0			1	0			0	0	Detectie	1
p3				0	1	1	0					Correct	0
p4								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.

	p4	p3	p2	p1
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.

Tegenwoordig 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-code (7,4) 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.

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 Hamming-code (7,4) gebruiken we twee matrices, namelijk

${\displaystyle 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}}}$  (coderen)

en

${\displaystyle 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: ${\displaystyle H_{e}}$  is de getransponeerde van de generatormatrix G, dus

${\displaystyle \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 ${\displaystyle H_{e}}$  aangehouden, dus de getransponeerde notatie ten opzichte van de notatie met G.

${\displaystyle 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

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

Stel dat we deze databits willen versturen. We vermenigvuldigen de matrix ${\displaystyle H_{e}}$  met p, uiteraard rekenend modulo 2:

${\displaystyle 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 ${\displaystyle H_{d}}$ , om na te gaan of er een fout is opgetreden. Dit levert op (wederom modulo 2 rekenend):

${\displaystyle 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

${\displaystyle \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 ${\displaystyle \mathbf {r} +\mathbf {e} _{i}}$  komt overeen met een enkelvoudige bitfout op plaats i.

Als we deze vector vermenigvuldigen met ${\displaystyle H_{d}}$ :

${\displaystyle 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 ${\displaystyle H_{d}}$  en r gelijk aan nul. Dus

${\displaystyle H_{d}\mathbf {r} +H_{d}\mathbf {e} _{i}=\mathbf {0} +H_{d}\mathbf {e} _{i}=H_{d}\mathbf {e} _{i}}$ 

Het product van ${\displaystyle H_{d}}$  met eenheidsvector nummer i zal de kolom zijn van ${\displaystyle H_{d}}$  die staat op de bitpositie waar de fout is opgetreden. De kolommen van ${\displaystyle 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 ${\displaystyle \mathbf {s} }$ , dan heeft het dus zin om ${\displaystyle H_{d}\mathbf {s} }$  om te zetten in een binair getal; bijvoorbeeld (1, 0, 1) is een kolom van ${\displaystyle 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

${\displaystyle \mathbf {s} =\mathbf {r} +\mathbf {e} _{2}={\begin{pmatrix}1\\1\\1\\1\\0\\1\\0\end{pmatrix}}}$ 

Dan is

${\displaystyle 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 ${\displaystyle H_{d}}$  met ${\displaystyle \mathbf {s} }$  ongelijk is aan nul in geval van bitfouten. Immers, in het geval van twee bitfouten, is het ontvangen woord ${\displaystyle \mathbf {s} =\mathbf {r} +\mathbf {e} _{i}+\mathbf {e} _{j}}$  en is ${\displaystyle H_{d}\mathbf {s} }$  gelijk aan de som van twee kolommen van ${\displaystyle 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

• Lee-code
• Coderingstheorie
• Lineaire code