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 \mathbb{F}_2 = GF(2). Deze vectorruimte bevat 2^d elementen.

\mathbb{F}_2^d = \{ x_1, \ldots, x_{2^d} \}

We definiëren nu in de n-dimensionale ruimte over \mathbb{F}_2 de 'indicator-vectoren':

\mathbb{I}_A \in \mathbb{F}_2^n

op deelverzamelingen  A \subset \mathbb{F}_2^d door:

\left( \mathbb{I}_A \right)_i = \begin{cases} 1 & \mbox{ als } x_i \in A \\ 0 & \mbox{ elders} \\ \end{cases}

en we definiëren in ( \mathbb{F}_2 ) ^ n de volgende binaire bewerking 'puntproduct':

 w \wedge z = (w_1 \times z_1, \ldots , w_n \times z_n )


\mathbb{F}_2^d is een d-dimensionale vectorruimte over \mathbb{F}_2, en is dus te schrijven als

(\mathbb{F}_2)^d = \{ (y_1, \ldots , y_d) | y_i \in \mathbb{F}_2 \}

We definiëren nu de volgende vectoren ter lengte n : v_0 = (1,1,1,1,1,1,1,1) en

 v_i = \mathbb{I}_{ H_i }

waarbij Hi hypervlakken in (\mathbb{F}_2)^d zijn (van dimensie 2d-1):

H_i = \{ y \in ( \mathbb{F}_2 ) ^d \mid y_i = 0 \}

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 v_i.

Voorbeeld 1[bewerken]

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

 \mathbb{F}_2^3 = \{ (0,0,0), (0,0,1),  \ldots, (1,1,1) \}.

en


\begin{matrix}
v_0 & = & (1,1,1,1,1,1,1,1) \\
v_1 & = & (1,0,1,0,1,0,1,0) \\
v_2 & = & (1,1,0,0,1,1,0,0) \\
v_3 & = & (1,1,1,1,0,0,0,0) \\
\end{matrix}

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

 \{ v_0, v_1, v_2, v_3 \}

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


\begin{pmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
\end{pmatrix}

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

 \{ v_0, v_1, v_2, v_3, v_1 \wedge v_2, v_1 \wedge v_3, v_2 \wedge v_3 \}

ofwel door de volgende matrix:


\begin{pmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
\end{pmatrix}

Eigenschappen[bewerken]

Er geldt:

1 De verzameling van alle mogelijke puntproducten tot en met d van de vectoren v_i vormt een basis van \mathbb{F}_2^n.

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

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

 \sum_{s=0}^r {d \choose s}

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

C_1 | C_2 = \{ (c_1|c_1+c_2) \mid c_1 \in C_1, c_2 \in C_2 \}

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