Reed-Müller-Code - Reed–Muller code

Reed-Müller-Code RM(r,m)
Benannt nach	Irving S. Reed und David E. Muller
Einstufung
Typ	Linearer Blockcode
Blocklänge	${\displaystyle 2^{m}}$
Nachrichtenlänge	${\displaystyle k=\sum_{i=0}^{r}{\binom {m}{i}}}$
Rate	${\displaystyle k/2^{m}}$
Distanz	${\displaystyle 2^{mr}}$
Alphabetgröße	${\displaystyle 2}$
Notation	${\displaystyle [2^{m},k,2^{mr}]_{2}}$-Code
v T e

Reed-Muller-Codes sind fehlerkorrigierende Codes , die in drahtlosen Kommunikationsanwendungen verwendet werden, insbesondere in der Weltraumkommunikation. Darüber hinaus stützt sich der vorgeschlagene 5G-Standard auf die eng verwandten Polarcodes zur Fehlerkorrektur im Kontrollkanal. Aufgrund ihrer günstigen theoretischen und mathematischen Eigenschaften wurden Reed-Muller-Codes auch in der theoretischen Informatik intensiv untersucht .

Reed-Muller-Codes verallgemeinern die Reed-Solomon-Codes und den Walsh-Hadamard-Code . Reed-Muller-Codes sind lineare Blockcodes , die lokal testbar , lokal decodierbar und listendecodierbar sind . Diese Eigenschaften machen sie besonders nützlich beim Entwurf von probabilistisch überprüfbaren Beweisen .

Herkömmliche Reed-Muller-Codes sind Binärcodes, was bedeutet, dass Nachrichten und Codewörter Binärzeichenfolgen sind. Wenn r und m ganze Zahlen mit 0 ≤ r ≤ m sind , wird der Reed-Muller-Code mit den Parametern r und m als RM( r ,  m ) bezeichnet. Wenn er aufgefordert wird, eine aus k Bits bestehende Nachricht zu codieren , wobei gilt, erzeugt der RM( r ,  m )-Code ein Codewort, das aus 2 ^m Bits besteht. ${\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}$

Reed-Muller-Codes sind nach David E. Muller , der die Codes 1954 entdeckte, und Irving S. Reed , der den ersten effizienten Decodierungsalgorithmus vorschlug, benannt.

Beschreibung mit Polynomen niederen Grades

Reed-Muller-Codes können auf verschiedene (aber letztendlich äquivalente) Arten beschrieben werden. Die auf Polynomen niederen Grades basierende Beschreibung ist recht elegant und besonders geeignet für ihre Anwendung als lokal testbare Codes und lokal decodierbare Codes .

Encoder

Ein Blockcode kann eine oder mehrere Codierungsfunktionen haben , die Nachrichten Codewörtern zuordnen . Der Reed-Muller-Code RM( r , m ) hat Nachrichtenlänge und Blocklänge . Eine Möglichkeit, eine Codierung für diesen Code zu definieren, basiert auf der Auswertung von multilinearen Polynomen mit m Variablen und dem Gesamtgrad r . Jedes multilineare Polynom über dem endlichen Körper mit zwei Elementen kann wie folgt geschrieben werden: ${\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$${\textstyle x\in\{0,1\}^{k}}$${\textstyle C(x)\in\{0,1\}^{n}}$ ${\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}$ ${\displaystyle \textstyle n=2^{m}}$

Dies sind die Variablen des Polynoms und die Werte sind die Koeffizienten des Polynoms. Da es genau Koeffizienten gibt, besteht die Nachricht aus Werten, die als diese Koeffizienten verwendet werden können. Auf diese Weise führt jede Nachricht zu einem eindeutigen Polynom in m Variablen. Zur Bildung des Codewortes wertet der Encoder an allen Auswertepunkten aus und interpretiert dort die Summe als Addition modulo zwei, um ein Bit zu erhalten . Das heißt, die Kodierungsfunktion wird definiert über${\textstyle Z_{1},\dots,Z_{m}}$${\textstyle c_{S}\in \{0,1\}}$${\textstyle k}$${\textstyle x\in\{0,1\}^{k}}$${\textstyle k}$${\textstyle x}$${\textstyle p_{x}}$${\textstyle C(x)}$${\textstyle p_{x}}$${\textstyle a\in\{0,1\}^{m}}$${\textstyle (p_{x}(a){\bmod {2}})\in \{0,1\}}$

$${\displaystyle C(x)=\left(p_{x}(a){\bmod {2}}\right)_{a\in \{0,1\}^{m}}\,.}$$

Die Tatsache, dass das Codewort zur eindeutigen Rekonstruktion ausreicht, folgt aus der

Lagrange-Interpolation , die besagt, dass die Koeffizienten eines Polynoms eindeutig bestimmt sind, wenn genügend viele Bewertungspunkte gegeben sind. Da und gilt für alle Nachrichten , ist die Funktion eine lineare Abbildung . Somit ist der Reed-Muller-Code ein linearer Code . ${\displaystyle C(x)}$${\displaystyle x}$${\displaystyle C(0)=0}$${\displaystyle C(x+y)=C(x)+C(y){\bmod {2}}}$${\displaystyle x,y\in\{0,1\}^{k}}$${\displaystyle C}$

Beispiel

Für den Code RM( 2 , 4 ) lauten die Parameter wie folgt:

${\textstyle {\begin{ausgerichtet}r&=2\\m&=4\\k&=\textstyle {\binom {4}{2}}+{\binom {4}{1}}+{\binom {4 }{0}}=6+4+1=11\\n&=2^{m}=16\\\end{ausgerichtet}}}$

Sei die soeben definierte Codierungsfunktion. Um den String x = 1 1010 010101 der Länge 11 zu codieren, konstruiert der Encoder zunächst das Polynom in 4 Variablen:${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$${\textstyle p_{x}}$

$${\displaystyle {\begin{aligned}p_{x}(Z_{1},Z_{2},Z_{3},Z_{4})&=1+(1\cdot Z_{1}+0\cdot Z_{2}+1\cdot Z_{3}+0\cdot Z_{4})+(0\cdot Z_{1}Z_{2}+1\cdot Z_{1}Z_{3}+0\cdot Z_{1}Z_{4}+1\cdot Z_{2}Z_{3}+0\cdot Z_{2}Z_{4}+1\cdot Z_{3}Z_{4})\\&=1 +Z_{1}+Z_{3}+Z_{1}Z_{3}+Z_{2}Z_{3}+Z_{3}Z_{4}\end{ausgerichtet}}}$$

Dann wertet es dieses Polynom an allen 16 Bewertungspunkten aus:

$${\displaystyle p_{x}(0000)=1,\;p_{x}(0001)=1,\;p_{x}(0010)=1,\;p_{x}(0011)=1,\ ;p_{x}(0100)=1,\;p_{x}(0101)=0,\;p_{x}(0110)=1,\;p_{x}(0111)=0,\;p_ {x}(1000)=0,\;p_{x}(1001)=1,\;p_{x}(1010)=0,\;p_{x}(1011)=1,\;p_{x }(1100)=0,\;p_{x}(1101)=0,\;p_{x}(1110)=0,\;p_{x}(1111)=0\,.}$$

Als Ergebnis gilt C(1 1010 010101) = 1111 1010 0101 0000.

Decoder

Wie bereits erwähnt, kann die Lagrange-Interpolation verwendet werden, um die Nachricht effizient aus einem Codewort wiederzugewinnen. Ein Decoder muss jedoch auch dann funktionieren, wenn das Codewort an einigen Stellen beschädigt wurde, das heißt, wenn sich das empfangene Wort von einem beliebigen Codewort unterscheidet. In diesem Fall kann ein lokales Dekodierungsverfahren helfen.

Verallgemeinerung auf größere Alphabete durch Polynome niederen Grades

Unter Verwendung von Polynomen niederen Grades über einem endlichen Körper der Größe ist es möglich, die Definition von Reed-Muller-Codes auf Alphabete der Größe auszudehnen . Seien und positive ganze Zahlen, wobei als größer als gedacht werden sollte . Um eine Nachricht der Breite zu codieren , wird die Nachricht wiederum als ein -variates Polynom höchstens Gesamtgrades und mit dem Koeffizienten von interpretiert . Ein solches Polynom hat tatsächlich Koeffizienten. Die Reed-Muller-Codierung von ist die Liste aller Auswertungen von over all . Somit ist die Blocklänge . ${\displaystyle\mathbb{F}}$${\displaystyle q}$${\displaystyle q}$${\displaystyle m}$${\displaystyle d}$${\displaystyle m}$${\displaystyle d}$${\textstyle x\in\mathbb{F}^{k}}$${\displaystyle k=\textstyle {\binom {m+d}{m}}}$${\displaystyle m}$${\displaystyle p_{x}}$${\displaystyle d}$${\displaystyle\mathbb{F}}$${\displaystyle \textstyle {\binom {m+d}{m}}}$${\displaystyle x}$${\displaystyle p_{x}(a)}$${\displaystyle a\in\mathbb{F}^{m}}$${\displaystyle n=q^{m}}$

Beschreibung anhand einer Generatormatrix

Eine Generatormatrix für einen Reed-Muller-Code RM( r , m ) der Länge N = 2 ^m kann wie folgt konstruiert werden. Schreiben wir die Menge aller m -dimensionalen binären Vektoren als:

${\displaystyle X=\mathbb{F}_{2}^{m}=\{x_{1},\ldots ,x_{N}\}.}$

Wir definieren im N -dimensionalen Raum die

Indikatorvektoren${\displaystyle \mathbb{F} _{2}^{N}}$

${\displaystyle \mathbb{I}_{A}\in\mathbb{F}_{2}^{N}}$

auf Teilmengen von: ${\displaystyle A\subset X}$

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

zusammen mit, auch in , der binären Operation ${\displaystyle \mathbb{F} _{2}^{N}}$

${\displaystyle w\wedge z=(w_{1}\cdot z_{1},\ldots,w_{N}\cdot z_{N}),}$

als Keilprodukt bezeichnet (nicht zu verwechseln mit dem in der äußeren Algebra definierten Keilprodukt ). Hier und sind Punkte in ( N- dimensionale binäre Vektoren), und die Operation ist die übliche Multiplikation im Körper . ${\displaystyle w=(w_{1},w_{2},\ldots,w_{N})}$${\displaystyle z=(z_{1},z_{2},\ldots,z_{N})}$${\displaystyle \mathbb{F} _{2}^{N}}$${\displaystyle \cdot}$${\displaystyle \mathbb{F}_{2}}$

${\displaystyle \mathbb{F}_{2}^{m}}$ist ein m- dimensionaler Vektorraum über dem Körper , also kann man schreiben ${\displaystyle \mathbb{F}_{2}}$

${\displaystyle (\mathbb{F}_{2})^{m}=\{(y_{m},\ldots,y_{1})\mid y_{i}\in\mathbb{F}_{ 2}\}.}$

Wir definieren im N- dimensionalen Raum die folgenden Vektoren mit Länge und ${\displaystyle \mathbb{F} _{2}^{N}}$${\displaystyle N:v_{0}=(1,1,\ldots,1)}$

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

wobei 1 ≤ i ≤ m , und die H _i sind Hyperebene in (mit der Dimension m - 1 ): ${\displaystyle (\mathbb{F}_{2})^{m}}$

${\displaystyle H_{i}=\{y\in (\mathbb{F}_{2})^{m}\mid y_{i}=0\}.}$

Die Generatormatrix

Der Reed-Muller- RM( r , m ) -Code der Ordnung r und der Länge N  = 2 ^m ist der Code, der von v ₀ und den Keilprodukten von bis zu r der v _i , 1 ≤ i ≤ m (wobei gemäß Konvention a Keilprodukt von weniger als einem Vektor ist die Identität für die Operation). Mit anderen Worten, wir können eine Generatormatrix für den RM( r , m ) -Code aufbauen , indem wir Vektoren und ihre Keilprodukt-Permutationen bis zu r gleichzeitig als Zeilen der Generatormatrix verwenden, wobei 1 i _k ≤ m ist . ${\displaystyle {v_{0},v_{1},\ldots ,v_{n},\ldots ,(v_{i_{1}}\wedge v_{i_{2}}),\ldots (v_{i_ {1}}\wedge v_{i_{2}}\ldots \wedge v_{i_{r}})}}$

Beispiel 1

Sei m = 3. Dann ist N = 8, und

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

und

${\displaystyle {\begin{ausgerichtet}v_{0}&=(1,1,1,1,1,1,1)\\[2pt]v_{1}&=(1,0,1, 0,1,0,1,0)\\[2pt]v_{2}&=(1,1,0,0,1,1,0,0)\\[2pt]v_{3}&=( 1,1,1,1,0,0,0,0).\end{ausgerichtet}}}$

Der RM(1,3)-Code wird von der Menge erzeugt

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

oder expliziter durch die Zeilen der Matrix:

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

Beispiel 2

Der RM(2,3)-Code wird von der Menge generiert:

${\displaystyle \{v_{0},v_{1},v_{2},v_{3},v_{1}\wedge v_{2},v_{1}\wedge v_{3},v_{2 }\keil v_{3}\}}$

oder expliziter durch die Zeilen der Matrix:

${\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\\01&0\\1&1&1&1&0&0&0&0\\1&0&0&0&1&0&0&0\\01&0\\1&1&1&1&0&0&0&0\\1&0&0&0&1&0&0&0\\01&0&1$

Eigenschaften

Es gelten folgende Eigenschaften:

1. Die Menge aller möglichen Keilprodukte bis m der v _i bilden eine Basis für .${\displaystyle \mathbb{F} _{2}^{N}}$
2. Der RM ( r , m ) Code hat Rang

   ${\displaystyle \sum _{s=0}^{r}{m \wähle s}.}$

3. RM ( r , m ) = RM ( r , m − 1) | RM ( r − 1, m − 1) wobei '|' bezeichnet das Strichprodukt zweier Codes.
4. RM ( r , m ) hat ein minimales Hamming-Gewicht 2 ^{m − r} .

Nachweisen

RM-Codes decodieren

RM( r , m )-Codes können unter Verwendung einer Majoritätslogik-Decodierung decodiert werden . Die Grundidee der Majoritätslogik-Decodierung besteht darin, für jedes empfangene Codewortelement mehrere Prüfsummen zu bilden. Da jede der verschiedenen Prüfsummen alle den gleichen Wert haben muss (dh den Wert des Nachrichtenwort-Elementgewichts), können wir eine Mehrheitslogik-Decodierung verwenden, um den Wert des Nachrichtenwort-Elements zu entschlüsseln. Sobald jede Ordnung des Polynoms decodiert ist, wird das empfangene Wort entsprechend modifiziert, indem die entsprechenden Codewörter, gewichtet durch die decodierten Nachrichtenbeiträge, bis zur gegenwärtigen Stufe entfernt werden. Für einen RM-Code r- ter Ordnung müssen wir also iterativ r+1 decodieren, bevor wir das letzte empfangene Codewort erreichen. Außerdem werden die Werte der Nachrichtenbits durch dieses Schema berechnet; schließlich können wir das Codewort berechnen, indem wir das (gerade decodierte) Nachrichtenwort mit der Generatormatrix multiplizieren.

Ein Hinweis darauf, ob die Decodierung erfolgreich war, besteht darin, am Ende der ( r  + 1)-Stufen-Decodierung durch die Majoritätslogik-Decodierung ein vollständig aus Nullen modifiziertes empfangenes Wort zu haben . Diese Technik wurde von Irving S. Reed vorgeschlagen und ist allgemeiner, wenn sie auf andere endliche Geometriecodes angewendet wird.

Beschreibung mit rekursiver Konstruktion

Ein Reed-Muller-Code RM( r,m ) existiert für beliebige ganze Zahlen und . RM( m , m ) ist als Universumscode ( ) definiert . RM(−1,m) ist als trivialer Code ( ) definiert. Die restlichen RM-Codes können aus diesen elementaren Codes unter Verwendung der Längenverdopplungskonstruktion konstruiert werden ${\displaystyle m\geq 0}$${\displaystyle 0\leq r\leq m}$${\displaystyle 2^{m},2^{m},1}$${\displaystyle 2^{m},0,\infty}$

$( r,m-1),\mathbf{v}\in\mathrm{RM} (r-1,m-1)\}.}$

Aus dieser Konstruktion ist RM( r,m ) ein binärer linearer Blockcode ( n , k , d ) mit Länge n  = 2 ^m , Dimension und Mindestabstand für . Der duale Code zu RM( r,m ) ist RM( m – r– 1, m ). Dies zeigt, dass Wiederholungs- und SPC-Codes dual sind, biorthogonale und erweiterte Hamming-Codes dual sind und dass Codes mit k  =  n /2 selbstdual sind. ${\displaystyle k(r,m)=k(r,m-1)+k(r-1,m-1)}$${\displaystyle d=2^{mr}}$${\displaystyle r\geq 0}$

Sonderfälle von Reed-Müller-Codes

Tabelle aller RM(r,m)-Codes für m≤5

Alle RM( r ,  m ) -Codes mit und Alphabetgröße 2 werden hier angezeigt, annotiert mit der standardmäßigen [n,k,d] -Codierungstheorie-Notation für Blockcodes . Der Code RM( r ,  m ) ist ein -Code, das heißt, er ist ein linearer Code über einem binären Alphabet , hat Blocklänge , Nachrichtenlänge (oder Dimension) k und minimalen Abstand . ${\displaystyle m\leq 5}$${\displaystyle \textstyle [2^{m},k,2^{mr}]_{2}}$ ${\displaystyle \textstyle 2^{m}}$ ${\displaystyle \textstyle 2^{mr}}$

						RM ( m, m ) ( 2 m , 2 m , 1)	Universumscodes
					RM(5,5) (32,32,1)
				RM(4,4) (16,16,1)		RM( m  − 1,  m ) (2 m , 2 m − 1, 2)	SPC- Codes
			RM(3,3) (8,8,1)		RM(4,5) (32,31,2)
		RM(2,2) (4,4,1)		RM(3,4) (16,15,2)		RM( m  − 2, m ) (2 m , 2 m − m −1, 4)	ext. Hamming-Codes
	RM(1,1) (2,2,1)		RM(2,3) (8,7,2)		RM(3,5) (32,26,4)
RM(0,0) (1,1,1)		RM(1,2) (4,3,2)		RM(2,4) (16,11,4)
	RM(0,1) (2,1,2)		RM(1,3) (8,4,4)		RM(2,5) (32,16,8)		Selbst-Doppelcodes
RM(−1,0) (1,0, ) ${\displaystyle\infty}$		RM(0,2) (4,1,4)		RM(1,4) (16,5,8)
	RM(−1,1) (2,0, ) ${\displaystyle\infty}$		RM(0,3) (8,1,8)		RM(1,5) (32,6,16)
		RM(−1,2) (4,0, ) ${\displaystyle\infty}$		RM(0,4) (16,1,16)		RM(1, m ) (2 m , m +1, 2 m –1 )	Durchstochen Hadamard - Codes
			RM(−1,3) (8,0, ) ${\displaystyle\infty}$		RM(0,5) (32,1,32)
				RM(−1,4) (16,0, ) ${\displaystyle\infty}$		RM(0, m ) (2 m , 1, 2 m )	Wiederholungscodes
					RM(−1,5) (32,0, ) ${\displaystyle\infty}$
						RM(−1, m ) (2 m , 0, ∞)	triviale Codes

Eigenschaften von RM(r,m)-Codes für r≤1 oder r≥m-1

• RM(0,  m ) -Codes sind Wiederholungscodes der Länge N  = 2 ^m , Geschwindigkeit und Mindestabstand .${\displaystyle {R={\tfrac {1}{N}}}}$${\displaystyle d_{\min}=N}$
• RM(1,  m ) -Codes sind Paritätsprüfcodes der Länge N  = 2 ^m , der Rate und des minimalen Abstands .${\displaystyle R={\tfrac {m+1}{N}}}$${\displaystyle d_{\min}={\tfrac {N}{2}}}$
• RM( m  − 1,  m ) Codes sind einzelne Paritätsprüfcodes der Länge N  = 2 ^m , Rate und Mindestabstand .${\displaystyle R={\tfrac {N-1}{N}}}$${\displaystyle d_{\min}=2}$
• RM( m  − 2,  m ) Codes sind die Familie der erweiterten Hamming-Codes der Länge N  = 2 ^m mit minimalem Abstand .${\displaystyle d_{\min}=4}$

Verweise

Weiterlesen

• Shu Lin; Daniel Costello (2005). Fehlerkontrollcodierung (2 Aufl.). Pearson. ISBN 978-0-13-017973-9. Kapitel 4.
• JH van Lint (1992). Einführung in die Codierungstheorie . GTM . 86 (2 Aufl.). Springer-Verlag . ISBN 978-3-540-54894-2. Kapitel 4.5.

Externe Links

• MIT OpenCourseWare , 6.451 Prinzipien der digitalen Kommunikation II, Vorlesungsnotizen Abschnitt 6.4
• GPL Matlab-Implementierung von RM-Codes
• Source GPL Matlab-Implementierung von RM-Codes
• Weiss, E. (September 1962). "Verallgemeinerte Reed-Muller-Codes" . Information und Kontrolle . 5 (3): 213–222. doi : 10.1016/s0019-9958(62)90555-7 . ISSN  0019-9958 .