Reed-Muller-Code

Die Reed-Muller Codes sind eine Familie von linearen, fehlerkorrigierenden Codes, die im Bereich der Kanalcodierung zur gesicherten Datenübertragung und Datenspeicherung Verwendung finden. Diese Klasse von Codes wurden von Irving S. Reed und D. E. Muller entwickelt.

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 bei Mariner 9 ein RM-Code (1, 5) ohne Kontrollmatrix als Hadamard-Code (32, 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$ Codewörtern wurden Grauwerte eines Bildpunktes kodiert. Mehr dazu im nachfolgenden Beispiel 3 zur NASA Raumsonde Mariner 9.

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

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.

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}

Beispiel 3: NASA Raumsonde Mariner 9

Bei der NASA Raumsonde Mariner 9 aus dem Jahre 1971 wurde ein Reed-Muller-Code (1, 5) mit fehlernder Kontrollmatrix genutzt, der einen Spezialfall allgemeiner Reed-Muller Codes darstellt. Dieser Code war schlußendlich ein Hadamard-Code mit den Parametern (32, 6, 16). Mit diesem RM-Code (32, 6, 16) wurden 32 Bit lange Codewörter übertragen, die $2^6=64$ Werte kodierten, wobei die Codewörter untereinander einen Hamming-Abstand von 16 aufwiesen. Diese Parameter wurden aufgrund der Kanalcharakteristik, der Bildauflösung und der Aufnahme- und Übertragungszeiten gewählt, die eine Wortlänge von reichlich 30 Bit sinnvoll machten.

Aufgrund der großen Entfernung zwischen Mars und Erde, und den damals im Vergleich zu heute unfortschrittlichen Übertragungsgeräten, lag die angenommene Bit-Fehlerwahrscheinlichkeit bei 5 %. Daraus ergibt sich aufgrund der Kodierung von einem Grauwert in 6 Bit ohne zusätzliche Fehlerkorrekturmechanismen eine Grauwert-Fehlerwahrscheinlichkeit von 26 %. Das heißt ca. ein Viertel eines übertragenen Bildes kommen fehlerhaft beim Empfänger an. Durch den Einsatz des RM-Code (32, 6, 16) konnte bei gleicher Bit-Fehlerwahrscheinlichkeit von 5 % die Grauwert-Fehlerwahrscheinlichkeit auf 0.001 % reduziert werden.

Konstruktion

Der verwendete RM-Code (32, 6, 16) basiert auf einer Hadamard-Matrix $H\_\{32\}$.

Die Konstruktion von $H\_\{32\}$ erfolgt rekursiv aus der Hadamard-Matrix

$H\_1\; =\; \backslash begin\{pmatrix\}\; 1\; \backslash end\{pmatrix\}$

und der Erzeugungsregel

Diese Konstruktion nach Sylvester erzeugt die sogenannten Walsh Matrizen

die normalisierte Hadamard-Matrizen vom Grad $2^k$ darstellen.

Wenn man nun die Hadamard-Matrix $H\_\{32\}$ als Bitmuster interpretiert (bei dem eine 1 für die Binärziffer 1, und eine $-1$ für die Binärziffer 0 steht), dann erhält man 32 Codewörter mit 32 Bit Länge. Jedes dieser Codewörter weisst zu jedem anderen Codewort einen Hamming-Abstand von 16 oder 32 auf. Durch Kombination der Hadamard-Matrix $H\_\{32\}$ mit der dazu inversen Hadamard-Matrix $-H\_\{32\}$ erhält man 64 Codewörter mit 32 Bit Länge, bei denen jedes Codewort zu jedem anderen Codewort einen Hamming-Abstand von 16 aufweist. Diese Kombination von $H\_\{32\}$ und $-H\_\{32\}$ definiert dabei einen Hadamard-Code, mit dem sich $2^6=64$ Werte kodieren lassen, indem ein Wert n der n-ten Zeile des Codes entspricht. Die nebenstehende Abbildung zeigt den vollständigen Hadamard-Code für RMC (32, 6, 16), wobei die Farbe Schwarz für die Binärziffer 1 und die Farbe Weiß für die Binärziffer 0 steht.

Weblinks

Rekursive Codes mit der Plotkin-Konstruktion Dissertation zur Konstruktion und Decodierung von Reed-Muller Codes und deren Untercodes (Achtung: Angabe über den RM-Code (32, 6, 16) der Mariner 9 Mission sind nicht korrekt, da nur eine Mächtigkeit des Codes von $2^5=32$ Werten angegeben und erläutert wird.)

Erläuterungen zu Hadamard-Codes und der Mariner 9 Mission