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 David E. Muller entwickelt.

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 {\displaystyle 2^{6}=64} Codewörtern wurden Grauwerte eines Bildpunktes kodiert. Mehr dazu im nachfolgenden Beispiel 3 zur NASA Raumsonde Mariner 9.

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

X = F 2 d = { x 1 , … , x 2 d } {\displaystyle X=\mathbb {F} _{2}^{d}=\{x_{1},\ldots ,x_{2^{d}}\}} .

F n {\displaystyle \mathbb {F} _{n}} ist eine Teilmenge der nichtnegativen ganzen Zahlen

F n = { a ∈ N 0 | a < n } {\displaystyle \mathbb {F} _{n}=\{a\in \mathbb {N} _{0}\;|\;a<n\}} .

Wir definieren im n-dimensionalen Raum F 2 n {\displaystyle \mathbb {F} _{2}^{n}} die Indikatorvektoren :

I A ∈ F 2 n {\displaystyle \mathbb {I} _{A}\in \mathbb {F} _{2}^{n}}

auf Untermengen A ⊂ X {\displaystyle A\subset X} durch:

( I A ) i = { 1  wenn  x i ∈ A 0  sonst {\displaystyle \left(\mathbb {I} _{A}\right)_{i}={\begin{cases}1&{\mbox{ wenn }}x_{i}\in A\\0&{\mbox{ sonst}}\\\end{cases}}}

und – ebenfalls in F 2 n {\displaystyle \mathbb {F} _{2}^{n}} – die binäre Operation:

w ∧ z = ( w 1 × z 1 , … , w n × z n ) {\displaystyle w\wedge z=(w_{1}\times z_{1},\ldots ,w_{n}\times z_{n})}

die als Keil-Produkt bezeichnet wird.

F 2 d {\displaystyle \mathbb {F} _{2}^{d}} ist ein d {\displaystyle d} -dimensionaler Vektorraum über F 2 {\displaystyle \mathbb {F} _{2}} , deshalb ist es möglich zu schreiben:

( F 2 ) d = { ( y 1 , … , y d ) | y i ∈ F 2 } {\displaystyle (\mathbb {F} _{2})^{d}=\{(y_{1},\ldots ,y_{d})\;|\;y_{i}\in \mathbb {F} _{2}\}}

Wir definieren im n {\displaystyle n} -dimensionalen Raum F 2 n {\displaystyle \mathbb {F} _{2}^{n}} die folgenden Vektoren der Länge n {\displaystyle n}

v 0 = ( 1 , 1 , … , 1 ) {\displaystyle v_{0}=(1,1,\ldots ,1)} und

v i = I H i {\displaystyle v_{i}=\mathbb {I} _{H_{i}}} ,

wobei H i {\displaystyle H_{i}} Hyperebenen in ( F 2 ) d {\displaystyle (\mathbb {F} _{2})^{d}} (mit Dimension d − 1 {\displaystyle d-1} ) sind:

H i = { y ∈ ( F 2 ) d ∣ y i = 0 } {\displaystyle H_{i}=\{y\in (\mathbb {F} _{2})^{d}\mid y_{i}=0\}}

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

Es gelten die folgenden Eigenschaften

1. Die Menge aller möglichen Keil-Produkte von bis zu d der v i {\displaystyle v_{i}} bilden eine Basis von F 2 n {\displaystyle \mathbb {F} _{2}^{n}} .
2. Der RM(d, r)-Code hat den Rang: ∑ s = 0 r ( d s ) {\displaystyle \sum _{s=0}^{r}{d \choose s}}
3. Es gilt R M ( d , r ) = R M ( d − 1 , r ) | R M ( d − 1 , r − 1 ) {\displaystyle RM(d,r)=RM(d-1,r)|RM(d-1,r-1)} , wobei | {\displaystyle |} das Bar-Product zweier Codes bezeichnet
4. RM(d, r) hat die minimale Hamming-Distanz 2 d − r {\displaystyle 2^{d-r}} .

Sei d = 3 {\displaystyle d=3} . Dann n = 8 {\displaystyle n=8} , und

X = F 2 3 = { ( 0 , 0 , 0 ) , ( 0 , 0 , 1 ) , … , ( 1 , 1 , 1 ) } . {\displaystyle X=\mathbb {F} _{2}^{3}=\{(0,0,0),(0,0,1),\ldots ,(1,1,1)\}.}

und

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 ) {\displaystyle {\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

{ v 0 , v 1 , v 2 , v 3 } {\displaystyle \{v_{0},v_{1},v_{2},v_{3}\}}

oder genauer durch die Zeilen der Matrix

( 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 ) {\displaystyle {\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}}}

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

{ v 0 , v 1 , v 2 , v 3 , v 1 ∧ v 2 , v 1 ∧ v 3 , v 2 ∧ v 3 } {\displaystyle \{v_{0},v_{1},v_{2},v_{3},v_{1}\wedge v_{2},v_{1}\wedge v_{3},v_{2}\wedge v_{3}\}}

oder genauer durch die Zeilen der Matrix

( 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 ) {\displaystyle {\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}}}

Bei der NASA Raumsonde Mariner 9 aus dem Jahre 1971 wurde ein Reed-Muller-Code (1, 5) mit fehlender Kontrollmatrix genutzt, der einen Spezialfall allgemeiner Reed-Muller Codes darstellt. Dieser Code war schlussendlich 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 {\displaystyle 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 kommt 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,01 % reduziert werden.

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

Die Konstruktion von H 32 {\displaystyle H_{32}} erfolgt rekursiv aus der Hadamard-Matrix

H 1 = ( 1 ) {\displaystyle H_{1}={\begin{pmatrix}1\end{pmatrix}}}

und der Erzeugungsregel

H 2 n = ( H n H n H n − H n ) {\displaystyle H_{2n}={\begin{pmatrix}H_{n}&H_{n}\\H_{n}&-H_{n}\end{pmatrix}}}

Diese Konstruktion nach Sylvester erzeugt die sogenannten Walsh Matrizen

H 1 = ( 1 ) , H 2 = ( 1 1 1 − 1 ) , H 4 = ( 1 1 1 1 1 − 1 1 − 1 1 1 − 1 − 1 1 − 1 − 1 1 ) , … {\displaystyle H_{1}={\begin{pmatrix}1\end{pmatrix}},H_{2}={\begin{pmatrix}1&1\\1&-1\end{pmatrix}},H_{4}={\begin{pmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{pmatrix}},\ldots }

die normalisierte Hadamard-Matrizen vom Grad 2 k {\displaystyle 2^{k}} darstellen.

Wenn man nun die Hadamard-Matrix H 32 {\displaystyle H_{32}} als Bitmuster interpretiert (bei dem eine 1 für die Binärziffer 1, und eine − 1 {\displaystyle -1} für die Binärziffer 0 steht), dann erhält man 32 Codewörter mit 32 Bit Länge. Jedes dieser Codewörter weist zu jedem anderen Codewort einen Hamming-Abstand von 16 oder 32 auf. Durch Kombination der Hadamard-Matrix H 32 {\displaystyle H_{32}} mit der dazu inversen Hadamard-Matrix − H 32 {\displaystyle -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 {\displaystyle H_{32}} und − H 32 {\displaystyle -H_{32}} definiert dabei einen Hadamard-Code, mit dem sich 2 6 = 64 {\displaystyle 2^{6}=64} Werte kodieren lassen, indem ein Wert n {\displaystyle n} der n {\displaystyle 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.

Die Klasse der Reed-Muller-Codes kann man auch mit einer Menge von Abbildungen identifizieren. Betrachte hierzu die Menge

V = { f  Abbildung ∣ f : F 2 m → F 2 } {\displaystyle V=\{f{\text{ Abbildung}}\mid f\colon \mathbb {F} _{2}^{m}\rightarrow \mathbb {F} _{2}\}} .

Eine Abbildung f ∈ V {\displaystyle f\in V} wird durch ihre 2 m {\displaystyle {2^{m}}} Bilder eindeutig bestimmt, sofern deren Reihenfolge bekannt ist. Daher kann man f {\displaystyle f} auch durch den zugehörigen Bildvektor ( f ( 0 ) , f ( 1 ) , … , f ( 2 m − 1 ) ) ∈ F 2 2 m {\displaystyle (f(0),f(1),\dots ,f(2^{m}-1))\in \mathbb {F} _{2}^{2^{m}}} darstellen, wobei die Argumente 0 , 1 , … , 2 m − 1 {\displaystyle 0,1,\dots ,2^{m}-1} die 2 {\displaystyle 2} -adische Entwicklung der Elemente aus dem Definitionsbereich F 2 m {\displaystyle \mathbb {F} _{2}^{m}} sind. Auf V {\displaystyle V} kann man eine komponentenweise Addition und Multiplikation gemäß den Rechenoperationen in F 2 {\displaystyle \mathbb {F} _{2}} definieren. Genau genommen gibt es einen Ringisomorphismus zwischen der Menge der Abbildungen V {\displaystyle V} und der Menge der Bildvektoren F 2 2 m {\displaystyle \mathbb {F} _{2}^{2^{m}}} , weshalb man eine Abbildung auch mit seinem Bildvektor identifizieren kann: f = ( f ( 0 ) , f ( 1 ) , … , f ( 2 m − 1 ) ) {\displaystyle f=(f(0),f(1),\dots ,f(2^{m}-1))} . In V {\displaystyle V} liegen spezielle Abbildungen, die sogenannten Koordinatenfunktionen Z i , i ∈ { 1 … 2 m } {\displaystyle Z_{i},\;i\in \{1\dots 2^{m}\}} .

Diese sind wie folgt definiert:

Z i ( v ) := v i {\displaystyle Z_{i}(v):=v_{i}} für v = ( v 1 , … , v m ) ∈ F 2 m {\displaystyle v=(v_{1},\dots ,v_{m})\in \mathbb {F} _{2}^{m}} .

In der oben eingeführten Vektordarstellung lassen sich die Koordinatenfunktionen auch schreiben als

Z i = ( 0 , … , 0 ⏟ 2 i − 1 -mal , 1 , … , 1 ⏟ 2 i − 1 -mal , 0 , … , 0 ⏟ 2 i − 1 -mal , … ) ∈ F 2 2 m {\displaystyle Z_{i}=(\underbrace {0,\dots ,0} _{2^{i-1}{\text{-mal}}},\underbrace {1,\dots ,1} _{2^{i-1}{\text{-mal}}},\underbrace {0,\dots ,0} _{2^{i-1}{\text{-mal}}},\dots )\in \mathbb {F} _{2}^{2^{m}}} .

Nun gilt:

1. Das System der Monome Z i 1 ⋅ ⋯ ⋅ Z i k {\displaystyle Z_{i_{1}}\cdot \dots \cdot Z_{i_{k}}} ( 1 ≤ i 1 < ⋯ < i k ≤ m , k = 0 , … , m {\displaystyle 1\leq i_{1}<\dots <i_{k}\leq m,k=0,\dots ,m} ) ist eine Basis von V {\displaystyle V} .
2. Die Teilmenge { f : F 2 m → F 2  Abbildung ∣ grad ⁡ ( f ) ≤ r } ⊆ V {\displaystyle \{f\colon \mathbb {F} _{2}^{m}\rightarrow \mathbb {F} _{2}{\text{ Abbildung}}\mid \operatorname {grad} (f)\leq r\}\subseteq V} entspricht dem Reed-Muller-Code RM(r, m). Hierbei ist grad ⁡ ( f ) {\displaystyle \operatorname {grad} (f)} der höchste Monomgrad der Koordinatenfunktionen, als deren Summe f {\displaystyle f} gemäß 1. geschrieben werden kann.

Die Idee ist wie folgt: Jedes Codewort des Reed-Muller-Codes RM(r,m) kann gemäß der obigen alternativen Charakterisierung als Funktion f {\displaystyle f} aus V {\displaystyle V} aufgefasst werden – mit Basisdarstellung in entgegengesetzten Koordinatenfunktionen, d. h. mit eindeutig bestimmten Koeffizienten m I  mit  I ⊆ M {\displaystyle m_{I}{\text{ mit }}I\subseteq M} wobei M = { 1 , … , m } {\displaystyle M=\{1,\dots ,m\}} die Menge der Koordinatenfunktionen-Indizes ist. Die Funktion f {\displaystyle f} wird als Bildvektor ( f ( 0 ) , f ( 1 ) , … , f ( 2 m − 1 ) ) {\displaystyle (f(0),f(1),\dots ,f(2^{m}-1))} durch den gestörten Kanal geschickt. Der Empfänger dekodiert das mit Fehler e {\displaystyle e} behaftete Codewort g = f + e {\displaystyle g=f+e} , indem er sukzessive die Koeffizienten m I {\displaystyle m_{I}} rekonstruiert. Dabei beginnt er mit den Koeffizienten, die zum Monom höchsten Grades r {\displaystyle r} gehören. Hierzu berechnet er das Skalarprodukt von g {\displaystyle g} mit den s.g. charakteristischen Funktionen des Monoms. Dies sind alle Abbildungen vom Grad m − r {\displaystyle m-r} , wobei die erzeugenden Koordinatenfunktionen auch entgegengesetzt vorkommen können. Der Wert, der mehrheitlich durch die Skalarprodukte berechnet wird, ist der ursprüngliche Monomkoeffizient. Das Verfahren wird mit den Monomen vom Grad r − 1 , r − 2 , … , 0 {\displaystyle r-1,r-2,\dots ,0} wiederholt und man erhält hierdurch schließlich f {\displaystyle f} – vorausgesetzt der Fehler e {\displaystyle e} ist nicht zu groß.

Codierungs- und Decodierungsprozess mittels Reed-Muller-Codes im Überblick:

1. Nachricht n {\displaystyle n} wird in Codewort c {\displaystyle c} übersetzt.
2. Codewort c {\displaystyle c} kann mit Abbildung f {\displaystyle f} identifiziert werden.
3. Abbildung f {\displaystyle f} kann auch als Bildvektor ( f ( 0 ) , f ( 1 ) , … , f ( 2 m − 1 ) ) {\displaystyle (f(0),f(1),\dots ,f(2^{m}-1))} dargestellt werden.
4. Übermittle anstelle der Monomkoeffizienten von f {\displaystyle f} den zugehörigen Bildvektor. Dies liefert Redundanz, die die gewünschte Fehlerkorrektur ermöglicht.
5. Sende den Bildvektor durch den gestörten Kanal. Es ergibt sich g = f + e {\displaystyle g=f+e} mit Fehlervektor e {\displaystyle e} .
6. Empfange den Bildvektor g {\displaystyle g} und gewinne durch Skalarmultiplikationen mit den Koordinatenfunktionen Z i {\displaystyle Z_{i}} die ursprünglichen Monomkoeffizienten.
7. Durch die Monomkoeffizienten berechnet man die/das ursprüngliche Abbildung/Codewort f = c {\displaystyle f=c} und damit n {\displaystyle n} .

• Rekursive Codes mit der Plotkin-Konstruktion (PDF; 1,7 MB) 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 {\displaystyle 2^{5}=32} Werten angegeben und erläutert wird.)