Links und Funktionen
Sprachumschaltung

Navigationspfad
You are here: Home / Teaching / Winter 2016/17 / Lecture notes - WS 2016 / Reed-Muller-Code


Inhaltsbereich

Reed-Muller-Code

Lecture Note (in German) on the Reed-Muller Code. Will not be given in the lecture.

Plain Text icon skript6.txt — Plain Text, 9 KB (10193 bytes)

File contents

Reed-Muller Code
----------------

Plotkin Konstruktion
--------------------

Satz (Plotkin Konstruktion): Sei C1 ein (n,k1,d1)-Code und C2 ein
(n,k2,d2)-Code ueber GF(2). 

Dann ist

C1~C2 := {(x1,x1+x2) | x1:C1, x2:C2} 

ein (2n,k1*k2,d)-Code mit d=min(2*d1, d2). Sind C1, C2 linear, so auch C1~C2. 

Beweis: Die Parameter 2n, k1*k2 sind klar, weil alpha(x1,x2)=(x1,x1+x2)
injektiv ist. Ist C1~C2=0, so ist d1=d2=0. Sei also 0=/=(x1,x1+x2):C1~C2. 

Ist x2=0, so ist wt(x)=2*wt(x1) >= 2*d1. (wt = Gewicht = Anzahl der
Einsen).	 


Ist x2=/=0, so gilt wt(x) = wt(x1)+wt(x1+x2). In x2 werden durch die
Addition von x1 maximal soviele 1en "gekillt", wie ohnedies in der
ersten Komponente wieder dazu kommen. Deshalb ist hier
wt(x)>=wt(x2)>=d2. Beispiel: x1=1100, x2=1101. (x1,x1+x2)=11000001. []



Definition des Reed-Muller Code
-------------------------------

Fuer r<=m ist der (binaere) Reed-Muller Code r-ter Ordnung RM(r,m) definiert durch: 

RM(0,m) = 2^m-fache Wiederholung von {0,1} = {0^2^m,1^2^m}
RM(m,m) = {0,1}^2^m
RM(r,m) = RM(r,m-1) ~ RM(r-1,m-1)

Satz: RM(r,m) ist ein [2^m,sum_{i=0}^r.binom(m,i)]-Code mit Minimalabstand 
2^{m-r}. 

Erinnerung: (n,k,d)-Code: Laenge n, |C|=k, Minimalabstand d
            [n,k]-Code: Linear. Laenge n, dim(C)=k, also |C|=2^k. 
            [n,k,d]-Code: [n,k]-Code mit Minimalabstand d. 

Beweis des Satzes: Durch Induktion ueber m unter Verwendung der
Plotkinkonstruktion. 


Beispiel: RM(1,2) = RM(1,1)~RM(0,1) = {00,01,10,11}~{00,11} = 
        {0000,0011,
         0101,0110,
         1010,1001,
         1111,1100}

         RM(1,3) = RM(1,2)~RM(0,2) = RM(1,2) ~ {0000,1111} = 
          {00000000,00001111,00110011,00111100,
	   01010101,01011010,01100110,01101001,  
           10101010,10100101,10011001,10010110,
	   11111111,11110000,11001100,11000011}

          RM(2,3) = RM(2,2)~RM(1,2) = 
          {00000000,00001111,00010001,00011110,...

          RM(1,5) ist ein [32,6]-Code mit Minimalabstand 16. Es gibt
          also 64 Codewoerter der Laenge 32, die sich jeweils an 16
          Positionen unterscheiden. Er wurde bei Mars Expeditionen in
          den Jahren 1969-1972 verwendet, um Bilder zu codieren.



Polynomfunktionen
-----------------

Definition: Eine Boolesche Funktion f:{0,1}^n -> {0,1} ist
Polynomfunktion vom Grad d, wenn es ein Polynom P in n
Variablen {x1..xn} ueber GF(2)={0,1} und vom Grad hoechstens d 
gibt, sodass P(v1..vn)=f(v1..vn)
fuer alle v1..vn : {0,1}. 

NB: "Grad" bedeutet hier immer "summarischer Grad". Also hat
z.B. x*y+y den Grad zwei. 

NB: Ueber GF(2) sind Polynome und Polynomfunktionen nicht dasselbe,
denn fuer alle v:{0,1} gilt v*v=v, aber die Polynome x^2 und x sind
verschieden. Der Grund fuer diese Festlegung ist, dass man Polynome
oft auch in Erweiterungen des Koeffizientenkoerpers, hier GF(2),
auswerten moechte. In diesem Kapitel benoetigen wir das aber nicht, und
dementsprechend sind alle Polynome, die wir betrachten, multilinear,
in dem Sinne, dass jede Variable nur in der ersten Potenz vorkommt.

Satz: Jede n-stellige Boolesche Funktion ist Polynomfunktion vom Grad
n. 

Beweis: Die NAND Funktion ist Polynomfunktion vom Grad 2 vermoege
1+xy. Durch Komposition lassen sich daraus alle booleschen Funktionen
repraesentieren. Indem man modulo x^2-x reduziert (also jede hoehere
Potenz einer Variablen durch die erste ersetzt) erhaelt man ein
Polynom vom Grad n. 

Satz: Die Polynomfunktionen vom Grad d bilden einen GF(2) Vektorraum
der Dimension sum_{i=0}^d binom(n,i). 

Beweis: Es gibt binom(n,i) Monome vom Grad exakt i. 

Sei f eine m-stellige Polynomfunktion. Die Wertetabelle von f ist der
{0,1}-Vektor der Laenge 2^m welcher an der Position j:{1..2^m} den
Eintrag f(bin(j)), wobei bin(j):{0,1}^m die Binaerdarstellung von j
ist.

Satz: RM(r,m) besteht gerade aus den Wertetabellen der
m-stelligen Polynomfunktionen vom Grad r. 

Beweis: Durch Induktion ueber r (Uebung). 

Beispiel: 00110011 : RM(1,3) entspricht der Polynomfunktion
f(x1,x2,x3)=x2

10101010 : RM(1,3) entspricht der Polynomfkt g(x1,x2,x3)=1+x1. 

00010001 : RM(2,3) entspricht der Polynomfkt h(x1,x2,x3)=x1*x2

Umgekehrt entspricht f(x1,x2,x3)=x1+x3+1 dem Codewort
10011001:RM(1,3). 


Bemerkung: Die Darstellung der RM-Codeworte als Polynom erlaubt eine
besonders effiziente und intuitive Codierung: Die zu codierende
Botschaft fasst man als die Folge der Koeffizienten auf, waehrend die
Codierung dann die entsprechende Wertetabelle ist. 

Beispiel: Im RM(1,5) wird ein Wort (a_0,a_1,a_2,a_3,a_4,a_5) aus
{0,1}^6 als die Wertetabelle von a_0 + a_1*x_1 + a_2*x_2 + a_3*x_3 +
a_4*x_4 + a_5*x_5 codiert. 

Im RM(2,3) wird ein Wort (a_0,a_1,a_2,a_3,a_12,a_13,a_23):{0,1}^7
als die Wertetabelle von a_0 + a_1*x_1 + ... + a_12*x_1*x_2 +
a_13*x_1*x_3 + a_23*x_2*x_3 codiert. 

Das Muster 

Botschaft =^= symbolische Repraesentation einer Funktion
Codierung =^= Wertetabelle einer Funktion (i.a. nicht an allen
Argumenten)

tritt in der Codierungstheorie haeufiger auf, insbesondere auch bei
den im naechsten Kapitel behandelten Reed-Solomon Codes.  



RM und Dualitaet 
----------------

(NB: dieser Abschnitt wird nicht behandelt und ist nicht Pruefungsstoff)

Satz: Fuer 0 <= r < m gilt: RM(r,m)_ (dualer Code) =
RM(m-r-1,m). 

Beweis: Sei f:RM(m-r-1,m). Wir zeigen zunaechst, dass
f:RM(r,m)_. Ist g:RM(r,m), so hat f*g Grad m-1, ist also in
RM(m-1,m). Letzterer Code enthaelt aber nur Woerter von geradem
Gewicht (Uebung!), also ist <f,g>=0. Es folgt RM(m-r-1,m) <=
RM(r,m)_. Aus Dimensionsgruenden gilt aber sogar die Gleichheit.

Korollar: Fuer m>=2 ist RM(m-2,m) aequivalent zum dem erweiterten
Hamming-Code H_m^. Erinnerung: H_m^ erweitert H_m um ein zusaetzliches
Paritaetsbit, sodass alle Woerter gerades Gewicht haben. 
Zwei Codes
sind aequivalent, wenn sie sich nur durch eine Permutation der
Bitpositionen unterscheiden. 

Beweisskizze: RM(1,m) hat folgende Generatormatrix: 

111111111111111111..    
010101010101010101..
00110011001100110..
0000111100001111..
.....

Die Zeilen entsprechen den Basisvektoren 1, x_1, x_2, x_3, ..., x_{m}. 

Der erweiterte Hammingcode H_m hat aber bis auf Spaltenpermutation
 dieselbe Kontrollmatrix: 

111111111111111111..  1
10101010101010101..   0
0110011001100110..    0
000111100001111..     0
.....

Die erste Zeile fuehrt den Paritycheck durch, der Rest enspricht der
ueblichen Kontrollmatrix fuer den Hammingcode.



Mehrheitsdecodierung
--------------------

Die Syndromdecodierung ist fuer Codes mit hoeherer Minimaldistanz
nicht praktikabel, z.B. gibt es ja beim RM(1,5), welcher Laenge 32 und
Minimaldistanz 16 hat, insgesamt sum_{i=0}^7 binom(32,i) >= 4 Mio
Syndrome. Die Decodierungstabelle waere schon hier 4MB gross. Beim
RM(1,6) sind es >= 2*10^14, also 200Terabyte.
 
Abhilfe schafft eine Decodierungslogik, die den Fehler, bzw.  das
naechstgelegene Codewort berechnet, statt es in einer Tabelle
nachzusehen.

Wir beschreiben jetzt die Mehrheitsdecodierung fuer den Reed-Muller
Code, welche darauf basiert, dass das urspruengliche Codewort
sozusagen mehrfach redundant ausgerechnet wird. Ergeben die einzelnen
Berechnungen unterschiedliche Ergebnisse, so wird ein
Mehrheitsentscheid durchgefuehrt. Es ist so eingerichtet, dass weniger
als d/2 Fehler die Mehrheit nicht umpolen koennen. Diese
Mehrheitsdecodierung wurde von Irving Reed am Beispiel des Reed-Muller
Codes entdeckt und kommt auch bei anderen Codes zum Einsatz.

Gegeben sei also ein Wort g=f+e, wobei f:RM(r,m) und
wt(e)<=2^{m-r-1}-1. 

Wir zeigen, wie man den Koeffizienten (0 oder 1) in f eines beliebigen
Monoms vom Grad r in f (aufgefasst als Polynomfunktion) aus g
berechnen kann. Fuehrt man diese Prozedur fuer alle binom(m,r) Monome
durch, so koennen diese Monome subtrahiert werden und man erhaelt
g'=f'+e, wobei f':RM(r-1,m). Man kann dann dieselbe Prozedur fuer r-1
anwenden (RM(r-1,m) hat ja noch groessere Minimaldistanz) und so
Schritt fuer Schritt ganz f rekonstruieren. 

Sei also S<={1..m} mit |S|=r gegeben. Unser Ziel ist es, den
Koeffizienten des Monoms prod(x_i,i:S) in f aus g zu rekonstruieren.

Es sei M_S der r-dimensionale Unterraum von {0,1}^m (aufgefasst als
GF(2)-Vektorraum), welcher aus denjenigen Vektoren besteht, die
ausserhalb von S gleich 0 sind. 

Beispiel: r=2, m=5, S={1,4},
M_S=span(10000,00010)={00000,10000,00010,10010}

Definition: Fuer T<={1..m} und |T|<=r schreiben wir f_T fuer das Monom
prod(x_i,i:T). 

Lemma: Es sei T<={1..m}, T=/=S, |T|<=r, b:{0,1}^m. 

         sum(f_S(x+b),x:M_S) = 1

         sum(f_T(x+b),x:M_S) = 0

Beweis: Da wir jeweils ueber ganz M_S summieren, koennen wir o.B.d.A
annehmen, dass b an den Positionen in S Null ist. Es gilt dann also

               sum(f_S(x+b),x:M_S) = sum(f_S(x),x:M_S) 

In der letzteren Summe sind aber alle Beitraege Null, bis auf den fuer
x=1...1. 

Fuer die zweite Summe beachten wir, dass unter den gemachten
Voraussetzungen U := S \ T nichtleer ist. Fuer Vektoren x,x', die auf
T uebereinstimmen, gilt f_T(x+b)=f_T(x'+b). Die Zahl der Vektoren in
solch einer Aequivalenzklasse ist 2^{|U|}, also gerade. Daher ist die
entsprechende Summe gleich Null. []

Lemma: Wenn wt(e) <= 2^{m-r-1}-1, so ist die Mehrheit der Werte 

        v_b :=  sum(e(x+b),x:M_S) 

gleich Null. 

Beweis: Die Mengen M_S+b und M_S+b' sind affine Teilraeume und daher entweder gleich oder disjunkt. Deshalb wird {0,1}^n in 2^{m-r}
disjunkte affine Teilraeume der Form M_S+b zerlegt (das ist standard
lineare Algebra). In weniger als der Haelfte von denen befindet sich
ein Fehler und selbst in denen, in denen sich ein Teil des
Fehlervektors befindet, koennten die sich wegheben. Da es weniger als
die Haelfte von 2^{m-r} Fehler gibt, ist also die Mehrheit der v_b
gleich Null.                                                    []

Sei c_S der Koeffizient des Monoms prod(x_i,i:S) in f. 
Es gilt 

                sum(g(x+b), x:M_S) = 
                sum(f(x+b), x:M_S) + sum(e(x+b), x:M_S) = 
                c_S + v_b 

Die letzte Gleichung folgt aus der Linearitaet und dem ersten
Lemma. Mit dem zweiten Lemma folgt dann, dass die Mehrheit der 
sum(g(x+b), x:M_S) mit c_S uebereinstimmt. Wie eingangs skizziert
koennen also mit dieser Methode sukzessive die Koeffizienten bestimmt
werden. 
 

Document Actions


Funktionsleiste