Ein linearer Block-Code mit k Informationsbits und n Codewortbits wird als binärer (n,k)-Code bezeichnet. Der lineare Coderaum wird aufgespannt durch k linear unabhängige Basisvektoren von je n Bits. Man fasst sie zusammen in der sog. Generatormatrix G . Aus einem Informationsvektor u ergibt sich das Codewort durch
x = u * G
wo die Matrixmultiplikation im endlichen Körper mit den Elementen 0 und 1 (GF(2)) durchzuführen ist. Die GF(2)-Arithmetik ergibt sich durch Ganzzahlarithmetik plus modulo-2-Rechnung.
Die Arithmetik endlicher Körper wird im Kapitel 6 ausführlich behandelt. Wer dieses nicht beherrscht, sollte zunächst diesen Abschnitt überspringen.
Die Überprüfung eines empfangenen Wortes y auf Fehler erfolgt durch Multiplikation mit einer Prüfmatrix H :
s = y * H
Im Fehlerfreien Fall ist s der Nullvektor. Andernfalls gibt s Hinweise auf die Position von Fehlern.
Die Prüfmatrix ergibt sich wie folgt:
Der Coderaum ist ein k-dimensionaler Unterraum des n-dimensionalen GF(2)n , der von
den k Zeilenvektoren der Generatormatrix aufgespannt wird. Zum Aufspannen des GF(2)n
kann man diese Basisvektoren und weitere n-k zu diesen orthogonale Vektoren. Letztere sind
die Zeilen von H' . Wegen der Orthogonalität gilt dann
G * H = 0
D.H. jede Linearkombination der Zeilen von G , also jedes Codewort, mit H multipliziert ergibt 0 .
Beispiele
(1) (5,4)-Paritätscode
Eine Generatormatrix für den Paritätscode für k = 4, n = 5 ist
G = ( 1 0 0 0 1 )
( 0 1 0 0 1 )
( 0 0 1 0 1 )
( 0 0 0 1 1 )
In Matlab:
k = 4; G = [eye(k),ones(k,1)]; result2fig(G)
Mit dem Informationsvektor u = [ 1 1 0 1 ] ergibt sich sofort das Codewort:
x = u * G = ( 1 1 0 1 ) * ( 1 0 0 0 1 ) = ( 1 1 0 1 1 )
( 0 1 0 0 1 )
( 0 0 1 0 1 )
( 0 0 0 1 1 )
In Matlab:
( Die Funktion mod2(x) berechnet mod( round(x) , 2 )
und realisiert damit die Arithmetik im GF(2) )
u = [ 1 1 0 1 ]; x = mod2( u*G ); result2fig(x)
Der Paritätscode ist systematisch, denn die ersten vier Bits des Codewortes sind die Information.
Die Prüfmatrix ist
H = ( 1 )
( 1 )
( 1 )
( 1 )
In Matlab:
H = ones(k+1,1); result2fig(H)
Die Prüfung unseres Codewortes x muss s = 0 ergeben:
s = x * H = ( 1 1 0 1 1 ) * ( 1 ) = 0
( 1 )
( 1 )
( 1 )
In Matlab:
s = mod( x*H ,2); result2fig(s)
Der Paritätscode wird üblicherweise im letzten Bit modifiziert. Man addiert einen Vektor dessen Komponenten der Reihe nach angeben, ob das jeweilige Bit zu modifizieren ist. In diesem Fall ist also im GF(2) folgender Vektor zu addieren:
d = ( 0 0 0 0 1 )
Die Codierungsvorschrift lautet damit:
x = u * G + d = ( 1 1 0 1 ) * ( 1 0 0 0 1 ) + ( 0 0 0 0 1 ) = ( 1 1 0 1 0 )
( 0 1 0 0 1 )
( 0 0 1 0 1 )
( 0 0 0 1 1 )
In Matlab:
d = [ 0 0 0 0 1 ]; x = mod( u*G + d , 2); result2fig(x)
Der Minimalabstand des Paritätscodes ist D = 2 . Es ist also keine Fehlerkorrektur, aber eine Erkennung von Einbitfehlern möglich.
(2) (3,1)-Wiederholungscode
Eine Generatormatrix für den (3,1)-Wiederholungscode ist
G = ( 1 1 1 )
Mit dem Informationsvektor u , der in diesem Fall nur ein Bit enthält, ergibt sich sofort das Codewort:
a. u = 0 : x = ( 0 ) * ( 1 1 1 ) = ( 0 0 0 ) b. u = 1 : x = ( 1 ) * ( 1 1 1 ) = ( 1 1 1 )
Der (n,k)-Wiederholungscode ist systematisch. Sein Minimalabstand D = n . Es ist also eine Korrektur von bis zu floor((n-1)/2) Bits (hier also 1 Bit) oder die Erkennung von (n-1)-Bitfehlern möglich. Die Korrektur erfolgt einfach durch Mehrheitsentscheid.
In Matlab:
n = 3; G = ones(1,n); result2fig(G) % Generatormatrix
u = [0]; x = mod2( u*G ); result2fig(x) % Codewort 0
bzw.
u = [1]; x = mod2( u*G ); result2fig(x) % Codewort 1
Mehrheitsentscheid:
u = randb(1); % zufälliges Bit x = u*G; result2fig(x) % Codewort f = [0 1 0]; result2fig(f) % zweites Bit wird falsch y = mod2( x + f ); result2fig(y) % Fehler anbringen z = sum(y)>sum(y==0); result2fig(z) % Korrektur durch Mehrheitsentscheid
(3) (7,4)-Hammingcode
Eine Generatormatrix für den (7,4)-Hammingcode ist
G = ( 1 0 0 0 1 0 1 )
( 0 1 0 0 1 1 1 )
( 0 0 1 0 1 1 0 )
( 0 0 0 1 0 1 1 )
In Matlab:
G = [1 0 0 0 1 0 1; 0 1 0 0 1 1 1; 0 0 1 0 1 1 0; 0 0 0 1 0 1 1]; result2fig(G)
Mit dem Informationsvektor u ergibt sich sofort das Codewort.
Geben Sie den zu kodierenden Vektor von 4 Informationsbits an:
u = inputbinmat('Zeilenvektor u (4 Binärstellen)')
x = mod( u*G ,2); result2fig(x)
Dieser Hamming-Code ist systematisch, denn die ersten vier Bits des Codewortes sind die Information. Dies liegt daran, dass die k*n-Generatormatrix links mit einer k*k-Einheitsmatrix beginnt.
Der Hamming-Code wird meistens durch ein Paritätsbit ergänzt und häufig modifiziert.
Die Prüfung auf Fehler erfolgt durch die Berechnung des Syndroms s durch Multiplikation mit der Matrix
H = ( 1 0 1 )
( 1 1 1 )
( 1 1 0 )
( 0 1 1 )
( 1 0 0 )
( 0 1 0 )
( 0 0 1 )
In Matlab (hier gleich allgemein für alle systematischen Hammingcodes):
[k,n] = size(G); H = [G(:,k+1:n); eye(n-k)]; result2fig(H)
Im Falle eines fehlerfreien Codewortes ist s = 0 :
s = mod2( x*H ); result2fig(s)
Bei Einbitfehlern ist das Syndrom s gleich der Spalte, deren Nummer die Stelle des Fehlers im empfangenen Wort angibt.
Geben Sie den 4-stelligen Informationsvektor und einen 7-stelligen Fehlervektor an, der die Fehlerstellen durch Einsen markiert, für Fehler an der 3. Stelle also 0010000:
G = [1 0 0 0 1 0 1; 0 1 0 0 1 1 1; 0 0 1 0 1 1 0; 0 0 0 1 0 1 1];
H = [G(:,5:7); eye(3)];
u = inputbinmat('Informationsvektor u (4 Binärstellen)') % Information
x = mod( u*G ,2) % Codewort
f = inputbinmat('Fehlervektor f (7 Binärstellen)') % Fehlervektor
y = mod2( x+f ) % Bitfehler anbringen
s = mod2( y*H ) % Syndrom
b = 1; % Schleifenanfangswert
z = y;
if any(s) while any(s~=H(b,:)) b = b+1; end; end % Suche nach Identität der Zeile
if any(s) z(b) = mod2( y(b)+1 ); end % Korrektur
v = z(1:4); result2fig(v) % die dekodierte Information
Dieses Skript ist Kern der Funktion hammingcode(u,f). Als Default generiert diese Funktion zufällige Bitmuster für die Information u (4 Bits) und für den Fehlervektor (7 Bits mit Fehlerwahrscheinlichkeit p = 0.1 ):
demohammingcode
demohammingcode( [0 0 1 1], 3 )
demohammingcode( [0 0 1 1], [3 5] )
Prüfen Sie den Hammingcode mit folgenden Anzahlen von Bitfehlern: 0, 1, 2, 3.
(4) Weitere Hammingcodes
Die Generatormatrizen und Prüfmatrizen für binäre systematische (n,k)-Hamming-Codes
werden durch die Funktion hamminggenerator(r,m) erzeugt ( n = 2r - 1 ; k = n - r ).
Das Prinzip ist sehr einfach:
Man bildet eine binäre Matrix A , deren Zeilen sämtliche Binärmuster mit wenigstens
zwei Einsen enthält. Dieser Matrix wird eine Einheitsmatrix passender Größe links
vorangestellt. H wird entsprechend generiert, so dass G*H = 0 .
hamminggenerator(4,0);
hamminggenerator(4,1);
In Matlab kann man auch gleich prüfen, ob G*H = 0 erfüllt ist:
r = 4; G = hamminggenerator(r,0); result2fig(G) H = hamminggenerator(r,1); result2fig(H) GxH = mod2( G*H ); result2fig(GxH)
Mit r = 2 ergibt sich der (3,1)-Wiederholungscode, der also auch zu den Hamming-Codes gezählt werden kann.
(5) Cyclic Redundancy Check (CRC)
Eine beliebte Methode zur Erkennung von Fehlern in Blöcken von m Binärwörtern der
Breite n Bit sind systematische zyklische Codes. Diese haben den entscheidenden
Vorteil der Generierung und Prüfung durch sehr einfache lineare rückgekoppelte
Schieberegister deren formale Behandlung auf Polynomarithmetik beruht. Eine
MATLAB-Beschreibung, die die Schieberegister-Realisierung simuliert, liegt in crc
vor (siehe deren Rumpf für die einfache Realisierung). Diese Funktion wird
benutzt in der Funktion democrc(f) , die zufällige Informationsvektoren
der Länge 512 generiert, diese mit dem CRC codiert und nach der Invertierung
der im Parameter f angegebenen Stellen des Codewortes wieder decodiert.
Zurückgegeben wird der boolesche Wert, ob ein Fehler erkannt wurde:
democrc([]); % keine Bitfehler: leerer Fehlerindexvektor
democrc(1+ceil(527*rand(1,10))); % 10 Bitfehler
democrc(1+ceil(527*rand(1,200))); % 200 Fehlerindices
Die Fehlerindices werden hier als Zufallszahlen generiert und können deshalb mehrfach auftreten. Daher ist die Gesamtzahl der Fehlerstellen u.U. kleiner als die Anzahl der Fehlerindices.
Falls ein Bündelfehler der Länge L auftritt (und sonst kein Fehler), und g der Grad des Polynoms ist (gleich der Anzahl der Bits des CRC), so gilt für die Wahrscheinlichkeit P der Entdeckung durch den CRC:
L ≤ g : P = 1.0
L = g + 1 : P = 2-(g+1)
L > g + 1 : P = 2-g
Der zuunterst genannte Fall ist der allgemeine Fall von über die gesamte Sequenz verteilten Fehlern.
(6) Zyklische-Codes
Zyklische Codes eignen sich besonders zur Erkennung von Bündelfehlern. Es gibt aber auch viele zyklische Codes zur Fehler-Korrektur und zur Bündelfehler-Korrektur. In der Literatur findet man dann anstelle der Generatormatrizen die Generatorpolynome. Eine Umrechnung kann man vornehmen mit den Funktionen genpoly2genmat bzw. checkpoly2checkmat . Ein perfekter Dreibit-Fehlerkorrigierender zyklischer (23,12)-Code ist z.B. der Golay-Code mit dem Generatorpolynom
g(x) = x11 + x10 + x6 + x5 + x4 + x2 + 1
Eine Generatormatrix ergibt sich nach:
genpoly2genmat(23,12,[1 1 0 0 0 1 1 1 0 1 0 1]); % Golay-Generator
(7) Random-Block-Codes
Ein Code ist umso besser je mehr Bits des Codewortes von jeweils einem Bit der Information abhängen. Die Generatormatrix sollte im Idealfall also in jeder Zeile etwa gleich viele Einsen und Nullen haben. Das legt nahe, eine zufällige Matrix zu verwenden. Allerdings steht man dann vor dem Problem der Decodierung. Wir beschränken uns auf die Codierung von k≤12 Informationsbits. Dann kann man noch gut eine vollständige Suche nach dem kleinsten euklidischen Abstand des empfangenen Wortes von sämtlichen 2k möglichen Codewörtern durchführen. Die Decodierung durch Suche des kleinsten Abstandes wird erläutert durch das sehr einfache Beispiel eines binären 3-Bit-Codewortes, welches man als Ecke eines Würfels ansehen kann:
demosoftdecode
Die Bits des Codewortes werden durch Addition normalverteilter Werte gestört. Als wahrscheinlichstes Codewort wählt man dasjenige, welches im 3-D-Raum den kleinsten Abstand vom empfangenen Wort hat. Bei längeren Codewörtern ist der Abstand im entsprechend höherdimensionalen Raum zu berechnen.
Wir ermitteln die Verteilung der Distanzen durch Simulation mit der Funktion decoddemo :
help decoddemo
Zunächst ein Versuch mit einem zufälligen (32,8)-Code ohne Rauschen:
decoddemo( randb([8,32]), randb(8), 0)
Und nun mit Rauschen:
decoddemo( randb([8,32]), randb(8), 0.5)
Hinweise zur erwarteten Verteilung:
(1) Die kumulative Verteilung weicht aufgrund des zufälligen Informationsmusters und der
zufälligen Wahl von der erwarteten Verteilung ab. Mehrfaches Aufrufen wird die erwartete
Kurve bestätigen.
(2) Der Mittelwert des Abstandsquadrates für einen zufälligen binären (n,k)-Code ist ohne
Rauschen (n/2) * (Signalabstand)2 . Bei Rauschen mit der Standardabweichung σ kommt der Erwartungswert n*σ2 der χ2-Verteilung hinzu.
(3) Die Varianz des Abstandsquadrates ist (n/2)*(Signalabstand)2 + 2*n*σ2 .
Hier ein Versuch mit einem (2048,8)-Code:
decoddemo( randb([8,2048]), randb(8), 1.0)
Auch bei starkem Rauschen ist die Decodierung noch sehr sicher:
decoddemo( randb([8,2048]), randb(8), 3.0)
Die erträgliche Grenze der Decodierzeit ist etwa erreicht mit dem (12,1024)-Code:
decoddemo( randb([12,1024]), randb(12), 4.0)
Die Codierung ist bei diesen Codes nicht sehr aufwändig. Das Problem jedoch ist die Decodierung. Nur mit einer vollständigen Suche findet man das am besten passende Codewort. Für große k kommt daher eine vollständige Suche nicht in Betracht. Unter einem guten Code versteht man im allgemeinen einen Code, der mit erträglichem Decodieraufwand auch bei relativ großem Rauschen eine kleine Fehlerrate ergibt.
Für kleine Codewortlängen sind zufällig generierte Codes meistens nicht optimal. Wir vergleichen als Bespiel den oben besprochenen (23,12)-Golay-Code, dessen Minimalabstand 7 beträgt, mit zufällig generierten (23,12)-Codes, deren Minimalabstand so gut wie immer deutlich kleiner als 7 ist:
Golay-Code:
decoddemo( genpoly2genmat(23,12,[1 1 0 0 0 1 1 1 0 1 0 1]), randb(12), 0)
Random-Code:
decoddemo( randb([12,23]), randb(12), 0)
Wiederholt man diese Aufrufe mehrfach mit σ = 0.7 , so wird man feststellen, dass zwar der Golay-Code wegen der optimalen Anordnung der Codewörter mit Abstand 7 besser ist, aber nicht so wesentlich, wie man vielleicht vermutet hat.
Aufgabe 5.2 Der (15,11)-Hamming-Code soll mit dem Paritätscode erweitert
werden zu einem systematischen (16,11)-Code. Der Code lässt sich mit der
Funktion hamminggenerator erzeugen.
Geben Sie G und H an.