Hamming-code

In de coderingstheorie is een Hamming-code een foutcorrigerende code, genoemd naar de uitvinder, Richard Hamming. Hamming-codes zijn lineaire codes en maken gebruik van pariteitsbits. Zij kunnen detecteren dat 1 of 2 bits in een codewoord zijn geïnverteerd of 1 bit dat is geïnverteerd in het ontvangen codewoord corrigeren. Dat is meer dan bij codes met een enkel pariteitsbit, die een even aantal bitfouten niet detecteren en die geen hulp bieden voor het corrigeren van gevonden bitfouten.

Geschiedenis

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 aantal krachtige algoritmes ontwikkelde. Hij publiceerde in 1950 wat nu bekendstaat als de Hamming-code, die momenteel in bepaalde situaties nog steeds wordt toegepast.

Voorafgaande codes

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.

Pariteitsbit

Er wordt een enkel pariteitsbit toegevoegd aan een codewoord dat aangeeft of er in dat woord een even dan wel een oneven aantal bits de waarde 1 heeft. Een enkele bitfout op het transmissiepad verandert de pariteit, waardoor de fout wordt gedetecteerd, maar een even aantal bitfouten wordt hierdoor niet opgemerkt. Daarnaast is het zo dat bij detectie van een bitfout er niet duidelijk is welk bit fout is ontvangen. De enige mogelijke correctiemethode is het codewoord opnieuw sturen.

'Twee van vijf'-code

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 codewoord van vijf bit exact twee enen bevatte. Tegenwoordig noemen we dit een constant gewicht code. Als de invoer van de computer een woord ontving met niet exact twee enen, dan vond foutdetectie plaats. Het kan bij deze code desondanks voorkomen dat 2 bitfouten in 1 woord niet worden gedetecteerd.

Repetitiecode

Een andere code herhaalde ieder databit een aantal keer. Bijvoorbeeld als het te verzenden databit een 1 was, verzond een $n$ =3 repetitiecode het woord 111. Als de drie ontvangen bits niet hetzelfde waren, was er dus een fout opgetreden. De foutcorrectie werkt hierbij als volgt: bij ontvangst van 000, 001, 010 of 100 wordt het ontvangen 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.

Dergelijke codes kunnen uiteraard niet alle mogelijke fouten op correcte wijze corrigeren. Bovendien is de repetitiecode inefficiënt.

Werking

De vier databits, drie pariteitsbits en welke pariteitsbits bij welke databits horen in de (7,4) Hammingcode

Wanneer er meer foutcorrigerende bits aan een codewoord of boodschap worden toegevoegd 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 wanneer bekend is dat er een bit verkeerd is, welk bit dat is.

Hamming bestudeerde de bestaande codes, inclusief two-of-five, en zocht naar generalisaties. Bijvoorbeeld bij gebruik van een pariteitsbit wordt aan elk codewoord 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 worden genoemd. De information rate is het aantal mogelijke codewoorden gedeeld door het aantal bits in de code, voor onze repetitiecode 1/3.

Hamming onderzocht ook de problemen die ontstaan bij twee of meer bitfouten en definieerde de Hammingafstand. De code met een extra pariteitsbit heeft de afstand 2. De (3,1)-repetitiecode heeft afstand 3, want tussen de twee codewoorden 000 en 111 moeten er drie bits worden veranderd om het andere codewoord te krijgen.

Hamming was geïnteresseerd in twee problemen. Hij wilde zowel de afstand en daarmee het fout corrigerende vermogen zo veel mogelijk verhogen, als de information rate zo groot mogelijk maken. Tijdens de jaren 40 ontwikkelde hij diverse codes die een grote verbetering waren ten opzichte van reeds bestaande codes. Al zijn codes hadden de eigenschap dat zij behalve de codewoorden ook de pariteitsbits daarin controleerden.

Het algoritme van de Hamming-code is als volgt:

Alle bitposities die tweemacht zijn worden als pariteitsbits gebruikt, dat zijn de bitposities 1, 2, 4, 8, 16, 32, 64 enzovoort.
Alle overige bitposities worden voor het te coderen bericht gebruikt, dat zijn de bitposities 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17 enzovoort.
Het aantal bits achter elkaar dat steeds door een pariteitsbit wordt gecontroleerd, maar ook het aantal bits die daarna niet worden gecontroleerd, komt met de positie van dat pariteitsbit overeen.
Ieder pariteitsbit berekent de pariteit voor een aantal bits uit het codewoord. De positie van het pariteitsbit bepaalt de rij van de bits die al dan niet worden meegenomen in het berekenen van het pariteitsbit. Het pariteitsbit hoort per definitie bij de rij waarvan het de pariteit bepaalt.
- Pariteit bit 1: bit 1, 3, 5, 7, 9 enz.
- Pariteit bit 2: bit 2, 3, 6, 7, 10, 11, enz.
- Pariteit bit 4: bit 4, 5, 6, 7, 12, 13, 14, 15, enz.
- Pariteit bit 8: bit 8, 9, 10, 11, 12, 13, 14, 15, enz.
- enzovoorts

(11,7)-Hammingcode

Beschouw het 7 bit-codewoord 0110101. Zie de tabellen hieronder hoe Hamming-codes worden ontworpen en gebruikt om een fout te detecteren. Er komen in het woord dat wordt verzonden 7 gegevensbits voor, maar er worden met de vier pariteitsbits daarbij 11 bits verzonden. 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.

	p₁	p₂	d₁	p₃	d₂	d₃	d₄	p₄	d₅	d₆	d₇
codewoord zonder controle:			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 controle:	1	0	0	0	1	1	0	0	1	0	1

Het codewoord waar voor de controle de nodige pariteitsbits aan zijn toegevoegd is 10001100101. Neem nu aan dat het laatste bit verkeerd wordt ontvangen, dus dat 10001100100 wordt ontvangen. Zet indien de pariteitscontrole een fout oplevert het pariteitsbit op 1 .

	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	fout	1
p₂		0	0			1	0			0	0	fout	1
p₃				0	1	1	0					correct	0
p₄								0	1	0	0	fout	1

Het verkeerde bit is hierin gemarkeerd, maar de ontvanger moet nu nog berekenen welk bit dat is. De laatste stap daartoe is het bepalen van de waarde van de pariteitsbits. De decimale waarde van de pariteitsbits is 11, waaruit volgt dat het elfde bit in het ontvangen woord inclusief de pariteitsbits fout is, dus moet worden veranderd.

	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 codewoord 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'. Er moeten toch 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 in 1950 werd geïntroduceerd. 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.

Matrixvermenigvuldiging

Een Hamming-code is een voorbeeld van een lineaire code. Hamming-codes maken gebruik van de matrixvermenigvuldiging. Bijvoorbeeld, voor de Hamming-code (7,4) gebruiken we twee matrices, namelijk

\mathbf {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

\mathbf {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:

\mathbf {H} _{e}

is de getransponeerde van de generatormatrix

\mathbf {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

\mathbf {H} _{e}

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

\mathbf {G}

.

\mathbf {H} _{d}

is de parity check matrix die correspondeert met

\mathbf {G}

.

We gebruiken 'blokken' van vier databits en berekenen drie redundante checkbits. 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 $\mathbf {H} _{e}$ met p, uiteraard rekenend modulo 2:

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

\mathbf {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 $\mathbf {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 $\mathbf {H} _{d}$ :

\mathbf {H} _{d}(\mathbf {r} +\mathbf {e} _{i})=\mathbf {H} _{d}\mathbf {r} +\mathbf {H} _{d}\mathbf {e} _{i}

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

\mathbf {H} _{d}\mathbf {r} +\mathbf {H} _{d}\mathbf {e} _{i}=\mathbf {0} +\mathbf {H} _{d}\mathbf {e} _{i}=\mathbf {H} _{d}\mathbf {e} _{i}

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

\mathbf {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, de 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 $\mathbf {H} _{d}$ met $\mathbf {s}$ ongelijk is aan nul in geval 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 $\mathbf {H} _{d}\mathbf {s}$ gelijk aan de som van twee kolommen van $\mathbf {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

Een Lee-code is een uitbreiding van de Hamming-code voor die gevallen waarin het verzonden signaal geen binair signaal is.