Die Reed-Muller Codes sind eine Familie von linearen fehlerkorrigierenden Codes, die in der Kommunikationstechnik Verwendung finden.

Praxis

---

Der binäre Reed-Muller-Code wurde von der NASA in den Mariner Expeditionen (1969 bis 1976) zum Mars benutzt, um die vom Mars gemachten Fotos an die Erde zu senden. Im Speziellen wurde ein RM-Code mit den Parametern 6, 16 verwendet, das bedeutet, dass sechs Informationsbits in 32 Bit langen Wörtern kodiert waren und das Minimalgewicht der Wörter mindestens 16 betrug, was eine Fehlerkorrektur von 7 Bits ermöglichte. Mit den $2^6=64$ Codeworten wurden die Helligkeiten eines Bildpunktes kodiert.

Konstruktion

---

Im Folgenden wird beschrieben, wie man eine Erzeugermatrix eines Reed-Muller-Codes der Länge n = 2^d konstruiert.

$X\; =\; \backslash mathbb\{F\}\_2^d\; =\; \backslash \{\; x\_1,\; \backslash ldots,\; x\_\{2^d\}\; \backslash \}$

Wir definieren im n-dimensionalen Raum $\backslash mathbb\{F\}\_2^n$ die Indikatorvektoren :

$\backslash mathbb\{I\}\_A\; \backslash in\; \backslash mathbb\{F\}\_2^n$

auf Untermengen $A\; \backslash subset\; X$ durch:

und - ebenfalls in $\backslash mathbb\{F\}\_2^n$ - die binäre Operation:

$w\; \backslash wedge\; z\; =\; (w\_1\; \backslash times\; z\_1,\; \backslash ldots\; ,\; w\_n\; \backslash times\; z\_n\; )$

die als Keil-Produkt bezeichnet wird.

$\backslash mathbb\{F\}\_2^d$ ist ein d-dimensionaler Vektorraum über $\backslash mathbb\{F\}\_2$, deshalb ist es möglich zu schreiben:

$(\backslash mathbb\{F\}\_2)^d\; =\; \backslash \{\; (y\_1,\; \backslash ldots\; ,\; y\_d)\; |\; y\_i\; \backslash in\; \backslash mathbb\{F\}\_2\; \backslash \}$

Wir definieren im n-dimensionalen Raum $\backslash mathbb\{F\}\_2^n$ die folgenden Vektoren der Länge n: $v\_0\; =\; (1,1,1,1,1,1,1,1)$ und

$v\_i\; =\; \backslash mathbb\{I\}\_\{\; H\_i\; \}$

wobei H_i Hyperebenen in $(\backslash mathbb\{F\}\_2)^d$ (mit Dimension 2^d-1) sind:

$H\_i\; =\; \backslash \{\; y\; \backslash in\; (\; \backslash mathbb\{F\}\_2\; )\; ^d\; \backslash mid\; y\_i\; =\; 0\; \backslash \}$

Der Reed-Muller RM(d, r)-Code der Ordnung r und der Länge n=2^d ist derjenige Code, der durch v₀ und dem Keil-Produkt von bis zu r der $v\_i$ erzeugt wird (wobei nach Vereinbarung ein Keil-Produkt von weniger als einem Vektor gleich der Identität für diesen Operator ist).

Beispiel 1

---

Sei d=3. Dann n=8, und

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

und

$$

\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}

Der RM(3,1)-Code wird erzeugt durch die Menge

$\backslash \{\; v\_0,\; v\_1,\; v\_2,\; v\_3\; \backslash \}$

oder genauer durch die Zeilen der 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}

Beispiel 2

---

Der RM(3,2)-Code wird erzeugt durch die Menge

$\backslash \{\; v\_0,\; v\_1,\; v\_2,\; v\_3,\; v\_1\; \backslash wedge\; v\_2,\; v\_1\; \backslash wedge\; v\_3,\; v\_2\; \backslash wedge\; v\_3\; \backslash \}$

oder genauer durch die Zeilen der 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}

Eigenschaften

---

Es gelten die folgenden Eigenschaften

1. Die Menge aller möglichen Keil-Produkte von bis zu d der $v\_i$ bilden eine Basis von $\backslash mathbb\{F\}\_2^n$.
2. Der RM(d, r)-Code hat den Rang: $\backslash sum\_\{s=0\}^r\; \{d\; \backslash choose\; s\}$
3. RM(d, r) = RM(d-1,r) | RM(d-1,r-1) wobei '|' das Balkenprodukt zweier Codes bezeichnet
4. RM(d, r) hat die minimale Hamming-Distanz 2^d-r.

Kodierungstheorie | Diskrete Mathematik

Code de Reed-Müller | Reed-Muller-code | Reed-Muller code