Skript Teil 4
skript4.txt
—
Plain Text,
10 KB (10927 bytes)
Dateiinhalt
Hier noch einmal der Nachtrag zur Syndromdekodierung. Satz: Sei C linearer Code mit Minimalabstand d=2e+1. Zu jedem Syndrom existiert hoechstens ein Fehlervektor vom Gewicht <= e. (Syndromdecodierung). Beweis: Sei x ein Codewort und x1=x+e1 und x2=x+e2 zwei Woerter, wobei w(e1) <= e und w(e2)<=e. Ausserdem sei H e1 = H e2. Es sind e1 und e2 zwei Fehlervektoren vom Gewicht <=e und mit demselben Syndrom (NB: H x1 = H e1 = H e2 = H x2). Es ist H (e1-e2) = 0 und w(e1-e2) <= 2e, da man ja, um von e1 zu e2 zu gelangen, schlimmstenfalls alle Bits, die in e1 gesetzt sind, auf 0 setzen muss und dann alle in e2 gesetzten auf Eins setzen muss. Somit muss e1-e2=0 sein, denn 0:C, und es ist e1=e2. [] Man kann also zu jedem Syndrom in einer Tabelle einen entsprechenden Fehlervektor vom minimalen Gewicht auflisten und dann zur effizienten Dekodierung einfach diese Tabelle verwenden. Man spricht dann von Syndromdekodierung. Blockcodes ueber beliebigem Alphabet ------------------------------------ Wir verallgemeinern die Definition und Theorie der Blockcodes auf groessere Alphabete als nur {0,1}. Dies erlaubt es uns, lineare Codes ueber einem anderen Koerper als GF(2) als Blockcodes aufzufassen (implizit bereits geschehen). Ein Blockcode der Laenge n ueber einem Alphabet Sigma besteht also aus Woertern ueber Sigma der Laenge n. Insbesondere ist ein linearer [n,k,d]_q Code dann ein (q^n,k,d)-Blockcode ueber einem Alphabet der Groesse q. Der Hammingabstand zweier solcher Woerter ist wiederum die Zahl der Positionen, an denen sie sich unterscheiden. Die Kugelpackungsschranke und die Singleton-Schranke gelten sinngemaess fort: Satz (verallgemeinerte Kugelpackungsschranke): Sei C ein Code der Laenge n ueber einem Alphabet Sigma mit |Sigma|=q und mit Minimaldistanz d>=2e+1 fuer e:N. Es gilt: q^n >= |C| * sum_{i=0}^e binom(n,i) Beweis: die Anzahl aller moeglichen Woerter ist q^n. Der Rest des Beweis geht wie im Fall q=2. Satz (verallgemeinerte Singleton Schranke): Ist C ein Code der Minimaldistanz d+1 ueber einem Alphabet Sigma mit |Sigma|=q, so gilt: log(|C|) <= (n-d) * log(q). Beweis: wie der Beweis fuer q=2 unter Beachtung der Rechenregel log_q(x)=log(x)/log(q). Zur Beachtung: oft sind die Alphabetgroessen q Zweierpotenzen, also q=2^k. Man repraesentiert Woerter der Laenge n ueber einem solchen Alphabet dann gerne als Woerter der Laenge nk ueber {0,1}, wobei sich die Alphabetsymbole durch 0-1-Woerter der Laenge k codiert verstehen und diese Codierungen einfach hintereinandergeschrieben werden. Der Hammingabstand zweier Woerter entspricht dann aber nicht der Zahl der Bits an denen sie sich unterscheiden, sondern vielmehr der Zahl der k-Bloecke, in denen mindestens ein Fehler aufgetreten ist. Beispiel: Ist Sigma={a,b,c,d} und wird die Codierung a->00, b->01, c->10, d->11 zugrundegelegt, so entspricht 001011 dem Wort acd und 110011 dem Wort dad. Diese haben den Abstand 2, obwohl sich die Bitfolgen an drei Positionen unterscheiden. Satz von Varsamov ----------------- Als Anwendung der Charakterisierung des Minimalabstandes durch t-Unabhaengigkeit bringen wir jetzt den Satz von Varsamov, der ein Konstruktionsprinzip fuer Codes mit groesseren Distanzen liefert. Satz (Varsamov) Seien n,k,d natuerliche Zahlen mit d<=n. Gilt V_q^{n-1}(d-2)<q^{n-k} dann existiert ein linearer [n,k,d]_q-Code. ( n-1 ) Dabei ist V_q^{n-1}(d-2) = Sum_{i=0}^{d-2} ( i ) (q-1)^i das Volumen der n-1 dimensionalen Kugel vom Radius d-2. Bemerkung Die Kugelpackungsschranke liefert uns, dass fuer einen linearen [n,k,d]_q-Code gelten muss, dass V_q^n([(d-1)/2]) <= q^{n-k} Dieser Satz betrachtet also Kugeln mit (nahezu) dem doppelten Radius (dafuer aber in einer Dimension weniger). Insbesondere sichert dieses Resultat *nicht* die Existenz perfekter Codes. Beweis (Satz von Varsamov) Es genuegt, die Existenz einer d-1 unabhaengigen (n-k) x n Matrix zu zeigen. Diese Matrix wird dann als Check Matrix fungieren (was in der Tat zu einem mindestens n - (n-k) dimensionalen Coderaum fuehrt). Wir fuegen die einzelnen Spalten schrittweise hinzu, und zwar so, dass wir die (d-1)-Unabhaengigkeit nicht verletzen. Wir koennen einen weiteren weiteren Spaltenvektor hinzufuegen, wenn er sich nicht als Linearkombination von hoechstens d-2 der vorhanden Vektoren schreiben laesst. Es gibt q^{n-k} moegliche Spaltenvektoren der Laenge (n-k). Wenn wir schon i-1 < n Spalten haben dann verbieten sich folgende Vektoren. - Linearkombinationen mit genau 0 von 0 verschiedenen Koeffizienten: ein Vektor (der Nullvektor) - Linearkombinationen mit genau 1 von 0 verschiedenem Koeffizienten: i-1 moegliche Vektoren und q-1 moegliche Koeffizienten - Linearkombinationen mit genau 2 von 0 verschiedenen Koeffizienten: (i-1)(i-2)/2 moegliche Vektoren und (q-1)^2 moegliche Koeffizienten - ... - Linearkombinationen mit genau j von 0 verschiedenen Koeffizienten: ( i-1 ) j ( j ) moegliche Vektoren, (q-1) verschiedene Koeffizienten - ... - ...mit d-2... Macht zusammen d-2 ( i - 1) j i-1 n-2 Sum ( ) (q-1) = V (d-2) <= V (d-2) j=0 ( j ) q q Wenn also V_q^{n-2}(d-2) < q^{n-k} ist, was ja die Voraussetzung des Satzes ist, dann ist eine Verlaengerung moeglich. [] Bemerkung: der soeben bewiesene Satz ist in der Literatur auch als Gilbert-Varsamov Schranke bekannt. In der Tat liefert er ja eine untere Schranke an die Groesse des bestmoeglichen Codes mit gegebener Laenge und Minimalabstand. Die Formulierung als "Schranke" traegt der Tatsache Rechnung, dass der Beweis des Satzes kein effizientes Verfahren zur Bestimmung eines entsprechenden Codes liefert. Dualer Code ----------- Zu einem linearen [n,k,d]_q Code C definiert man den zu C dualen Code C* als die Menge aller Woerter w:GF(q)^n, sodass gilt w^T x = 0 fuer alle x:C. Man verifiziert leicht, dass C* Untervektorraum ist. Betrachten wir als Beispiel das Wort w=(0001111)^T. Es ist w^T(1110000)^T=0, w^T(1001100)^T=0, w^T(01010101)^T=0 und w^T(1101001)^T=0. Damit gilt w^T x = 0 fuer alle Codewoerter des [7,4,3]-Hammingcodes und w ist ein Element des zu diesem Code dualen Codes. Die Abbildung x |-> w^T x ist ja linear; daher genuegt es, wie im Beispiel geschehen, die Bedingung fuer die Basisvektoren zu ueberpruefen. Satz: Sei C Code der Laenge n und der Dimension k. Die Dimension von C* ist n-k.Beweis: C* ist gerade der Loesungsraum des homogenen Linearen Gleichungssystems v_i^T x = 0 fuer i=1..k, wobei v_1..v_k eine Basis von C bilden, z.B. die Spalten einer Generatormatrix. Die k Gleichungen des Systems sind also linear unabhaengig und nach dem Dimensionssatz hat der Loesungsraum dann die Dimension n-k. Satz: Der Code C habe Kontrollmatrix H und Generatormatrix G. Die Matrix H^T ist eine Generatormatrix fuer C*, die Matrix G^T bildet eine Kontrollmatrix fuer C*. Beweis: Die von den Spalten von H^T, also den Zeilen von H, erzeugten Woerter liegen alle in C*, denn sie "stehen senkrecht" auf allen Spalten von G. Die Kontrollmatrix hat aber gerade n-k Zeilen; aus Dimensionsgruenden liefert dies somit bereits ganz C*. Andererseits ist G^T H^T = (HG)^T = 0 und es folgt, dass G^T eine Kontrollmatrix ist. Korollar: Fuer jeden linearen Code C gilt C**=C. Definition: Der zum [2^n-1,2^n-1-n,3] Hamming Code duale Code heisst Simplex-Code der Dimension n. NB Wegen 2^n-1-(2^n-1-n)=n hat dieser Simplexcode tatsaechlich Dimension n. Satz: Fuer jedes von Null verschiedene Wort c des [2^n - 1,n]_q-Simplex-Codes gilt w(c)=2^{n-1}, insbesondere hat dieser Code Minimalabstand 2^{n-1}. Beweis Wir bezeichnen mit s_i die i-te Spalte der Generatormatrix. Es ist dies die i- ten Binaerziffer entsprechende Spalte, wenn man die Binaerzahlen der Laenge n als Zeilen der Reihe nach untereinanderschreibt. Wir schreiben ausserdem kurz N= 2^n-1. Sei 0 =/= c = (c_1,...,c_N)^T ein Codewort, etwa c = Sum_i a_i s_i. Wir betrachten U = { (b_1,...,b_n) | Sum_i a_i b_i = 0 } subset (F_2)^n Dies ist (da nicht alle a_i 0 sind) ein n-1 dimensionaler UVR und hat also 2^{n-1}-1 von 0 verschiedene Elemente. Jedem von diesen entspricht genau eine Zeile der Generatormatrix, da diese ja alle von Null verschiedenen Zeilen der Laenge n enthaelt (in systematischer Reihenfolge). Das Element c_i ist aber genau dann 0, wenn die i-te Zeile der Generatormatrix in U liegt. Es sind also 2^{n-1}-1 der c_i gleich Null und damit die verbleibenden 2^{n-1} ungleich Null, wie gewuenscht. QED Es folgt insbesondere, dass alle Codewoerter den gleichen Abstand voneinander haben. Diese Eigenschaft, die sie mit den Ecken eines regulaeren Simplex teilen, erklaert auch den Namen des Codes. Bemerkung: Wir hatten gesehen, dass der Hamming Code eine hohe Datenrate (n - log n Datenbits bei n uebertragenen bits) und geringe Fehlerkorrektur (Minimaldistanz 3, unabhaengig von der Laenge des Code Worte). Fuer den Simplex code ist es genau umgekehrt. Er hat eine hohe Fehlerkorrektur (d_n/n -> 1/2) aber geringe Datenrate (log n Datenbits, bei n uebertragenen bits, also asymptotische Datenrate 0). Abschliessend zeigen wir noch, dass der Simplex Code in gewissem Sinne "bestmoeglich" ist. Dazu zeigen wir eine Schranke an die Groesse von stark fehlerkorrigierenden Codes. Satz (Plotkin-Schranke) Sei C subset {0,1}^n ein (nicht notwendig linearer) Code mit Minimaldistanz d > n/2. Dann gilt |C| <= 2d/(2d - n) Beweis: Wir schaetzen Sum_{x,y} d(x,y) auf zwei verschiedene Arten ab, wobei die Summe ueber Paare (x,y) mit x:C, y:C, x=/=y rangiert. * Zum einen ist d(x,y) >= d fuer x =/= y stets und wir haben |C| * (|C| -1) Summanden, also Sum_{x,y} d(x,y) >= d * |C| * (|C| - 1) * Wir betrachten nun eine Matrix, deren Spalten alle(!) Codewoerter von C umfassen, es ist also eine n x |C| Matrix. Sei nun s_i die Zahl der 0en in der i-ten Zeile. Jede Kombination aus einer Spalte mit 0 in der i-ten Zeile und einer Spalte mit 1 in der i-ten Zeile traegt in der i-ten Zeile 2 zur Summe Sum_{x,y} d(x,y) bei. Also ist Sum_{x,y} d(x,y) <= Sum_i 2 s_i (|C| - s_i) Der Ausdruck auf der rechten Seite wird maximal fuer s_i = |C|/2, also Sum_{x,y} <= n * 2 * |C|/2 * |C|/2 = 1/2 * n * |C|^2 Insgesamt ergibt sich 1/2 * n * |C|^2 >= d * |C| * (|C| -1) n * |C| >= 2* d * (|C| -1) 0 >= (2d -n) * |C| - 2d |C| <= 2d/(2d -n) Bemerkung Fuer den n-dimensionalen Simplex Code gilt gerade * |C| = 2^n * 2d/(2d - N) = 2 * 2^{n-1} / (2*2^{n-1} - 2^n +1) = = 2^{n}/1 = 2^n = |C| Dieser Code ist also im Sinne der Plotkin-Schranke optimal. Bemerkung: Hamming und Simplexcode lassen sich auf beliebige endliche Koerper verallgemeinern. Man erhaelt dann Codes der Laenge (q^n-1)/(q-1) mit q=|F|.
Artikelaktionen