★ Aan de slag 50 (verdiepen)

De bovengenoemde methode van hertransmissie vereist dat er een interactie plaatsvindt tussen zender en ontvanger.
Dit is een voorbeeld van een protocol.
Maar in sommige situaties is een dergelijke interactie met de ontvanger niet mogelijk, bijvoorbeeld aan situaties waarbij gegevens opgeslagen worden, in het geheugen (RAM), op een harde schijf of op een DVD.

Een alternatieve methode is dan om foutherstellende codes toe te passen: daarmee kun je niet alleen nagaan dat er iets is misgegaan bij de communicatie (of opslag), maar je weet precies welk bit beschadigd is.
Dit kun je dan herstellen. Een voorbeeld van een dergelijke foutherstellende code is de Hammingcode.

Een veel gebruikte vorm is de (4-7) Hamming code, waarbij er door het toevoegen van 4 bits in een 7-bits woord een fout gecorrigeerd worden.

Stel je wilt de volgende bitreeks verzenden: 1010101

In de onderstaande tabel wordt op de plaatsen die geen tweemacht zijn de bitreeks ingevuld.

positie

1

2

3

4

5

6

7

8

9

10

11

bitreeks

 

 

1

 

0

1

0

 

1

0

1


Op de posities van de tweemachten (1, 2, 4 en 8) komen de 4 extra bits voor het herstellen van de fout te staan.

Per bit dat verzonden wordt bepalen we de controlebits.

Het eerste bit staat op positie 3: 1.

We herschrijven drie als som van machten van 2: 20 + 21 ofwel 1 + 2

In een matrix vullen we onder 1 en 2 het bit van positie 3 in: 1

positie

1

2

3

4

5

6

7

8

9

10

11

  3

1

1

 

 

 

 

 

 

 

 

 


Het volgende bit staat op positie 5: 0.

We herschrijven vijf als som van machten van 2: 20 + 22 ofwel 1 + 4

In een matrix vullen we onder 1 en 4 het bit van positie 5 in: 0

positie

1

2

3

4

5

6

7

8

9

10

11

  3

1

1

 

 

 

 

 

 

 

 

 

  5

0

 

 

0

 

 

 

 

 

 

 


Op dezelfde manier worden de controlebits van alle te versturen bits in de matrix gezet.

positie

1

2

3

4

5

6

7

8

9

10

11

3

1

1

 

 

 

 

 

 

 

 

 

5

0

 

 

0

 

 

 

 

 

 

 

6

 

1

 

1

 

 

 

 

 

 

 

7

0

0

 

0

 

 

 

 

 

 

 

9

1

 

 

 

 

 

 

1

 

 

 

10

 

0

 

 

 

 

 

0

 

 

 

11

1

1

 

 

 

 

 

1

 

 

 


Voor elke kolom van de matrix wordt het pariteitsbit bepaald.

positie

1

2

3

4

5

6

7

8

9

10

11

3

1

1

 

 

 

 

 

 

 

 

 

5

0

 

 

0

 

 

 

 

 

 

 

6

 

1

 

1

 

 

 

 

 

 

 

7

0

0

 

0

 

 

 

 

 

 

 

9

1

 

 

 

 

 

 

1

 

 

 

10

 

0

 

 

 

 

 

0

 

 

 

11

1

1

 

 

 

 

 

1

 

 

 

pariteitsbit

1

1

 

1

 

 

 

0

 

 

 


De bitreeks die verzonden moet worden is

positie

1

2

3

4

5

6

7

8

9

10

11

bitreeks

1

1

1

1

0

1

0

0

1

0

1

 

 

 


Hoe werkt nu de herstellende code?

Stel de ontvanger ontvangt niet 11110100101, maar 11111100101. Een bit is verkeerd aangekomen.

De ontvanger haalt uit de bitreeks de zeven bits die het eigenlijke woord moeten voorstellen. Die stonden op de posities 3, 5, 6, 7, 9, 10 en 11.
De ontvanger vindt 1 1 1 0 1 0 1

Om de gevonden data te corrigeren bouwt de ontvanger ook de matrix op:

positie

1

2

3

4

5

6

7

8

9

10

11

3

1

1

 

 

 

 

 

 

 

 

 

5

1

 

 

1

 

 

 

 

 

 

 

6

 

1

 

1

 

 

 

 

 

 

 

7

0

0

 

0

 

 

 

 

 

 

 

9

1

 

 

 

 

 

 

1

 

 

 

10

 

0

 

 

 

 

 

0

 

 

 

11

1

1

 

 

 

 

 

1

 

 

 


Van elke kolom wordt ook het pariteitsbit bepaald.

positie

1

2

3

4

5

6

7

8

9

10

11

3

1

1

 

 

 

 

 

 

 

 

 

5

1

 

 

1

 

 

 

 

 

 

 

6

 

1

 

1

 

 

 

 

 

 

 

7

0

0

 

0

 

 

 

 

 

 

 

9

1

 

 

 

 

 

 

1

 

 

 

10

 

0

 

 

 

 

 

0

 

 

 

11

1

1

 

 

 

 

 

1

 

 

 

pariteitsbit

0

1

 

0

 

 

 

0

 

 

 


Als we de zeven andere bits hierbij invullen is het resultaat: 0 1 1 0 1 1 0 0 1 0 1

Dat verschilt met de bitreeks, die de ontvanger had ontvangen: 1 1 1 1 1 1 0 0 1 0 1

Om de fout te herstellen kijken we naar de vier pariteitsbits.
We zien dat bit 1 en bit 4 verschillen.
Dat betekent dat bit 5 (1+4) verkeerd is aangekomen.

We kunnen het woord nu herstellen:

1 1 1 1 1 1 0 0 1 0 1    →     1 1 1 1 0 1 0 0 1 0 1

Dit resulteert in de oorspronkelijke 7 databits: 1010101.

Dergelijke foutherstellende codes vormden één van de belangrijke innovaties van de CD.
Hierdoor is het mogelijk om een CD met krassen in veel gevallen zonder verlies van kwaliteit af te spelen.