Reed-Muller-code

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een Reed-Muller-code is een lineaire foutcorrigerende code gebruikt bij (tele-)communicatie.

Constructie[bewerken]

De generator-matrix van een Reed-Muller-code met lengte n = 2d wordt opgebouwd als volgt. Beschouw eerst de vectorruimte met dimensie d over het eindig lichaam . Deze vectorruimte bevat elementen.

We definiëren nu in de n-dimensionale ruimte over de 'indicator-vectoren':

op deelverzamelingen door:

en we definiëren in de volgende binaire bewerking 'puntproduct':


is een d-dimensionale vectorruimte over , en is dus te schrijven als



We definiëren nu de volgende vectoren ter lengte n : en

waarbij Hi hypervlakken in zijn (van dimensie 2d-1):

De Reed-Muller RM(d,r)-code van de orde r en lengte n=2d is de lineaire code die wordt gegenereerd door v0 en de puntproducten van tot en met r van de vectoren .

Voorbeeld 1[bewerken]

Zij d=3. Dan is derhalve n=8, en

en

De RM(3,1)-code wordt gegenereerd door de verzameling

of, meer expliciet geformuleerd, door de rijen van de matrix:

De dimensie van de code is 4, dus de code bestaat uit 16 codewoorden.

Voorbeeld 2[bewerken]

De RM(3,2)-code wordt gegenereerd door de verzameling

ofwel door de volgende matrix:

Eigenschappen[bewerken]

Er geldt:

1 De verzameling van alle mogelijke puntproducten tot en met d van de vectoren vormt een basis van .

En Reed-Muller-codes hebben onder meer de volgende eigenschappen:

2 De RM(d,r)-code heeft dimensie:

3 Er geldt RM(d,r) = RM(d-1,r) | RM(d-1,r-1) waarbij '|' voor twee lineaire codes is gedefinieerd als

4 RM(d,r) heeft minimum Hammingafstand 2d-r.