coding-cs16-07
coding-cs16-07.txt
—
Plain Text,
10 KB (10762 bytes)
File contents
Cyclic Redundancy Checks ~~~~~~~~~~~~~~~~~~~~~~~~ Die Idee hinter der Fehlererkennung bei der alternativen Beschreibung von Reed-Solomon Codes liefert auch ein Verfahren, um fuer binaere Codes auf einfache Weise Fehlererkennung zu erreichen. Sei c in F2[X] ein festes Polynom vom Grad r. Wir betrachten zu einer Nachricht (m_0,...,m_{k-1}) in {0,1}* das Polynom k-1 i m = Sum m X in F [X] i=0 i 2 r Wir berechnen f = X m mod c und setzen als Nachricht (die Koeffizienten von) r t := X m + f Man beachte, dass der Grad von f hoechstens r-1 ist; der Code beginnt also mit der Nachricht, ist also "systematisch". Ausserdem ist die Nachricht kongruent 0 modulo c, so dass wieder durch Polynomdivision eine Fehlererkennung moeglich ist. Ist ein Fehleraufgetreten, so wurde t + e empfangen. Dieser Fehler wird genau dann erkannt, wenn e kein Vielfaches von c ist. Betrachten wir den Fall, dass *genau ein Bit* falsch uebertragen wurde. Dann ist e= X^i fuer ein i. Ist c =/= 1 mit konstantem Glied, so wird dieser Fehler immer erkannt. Fuer *2 Bitfehler*, also e = X^i(X^j+1) ergibt sich (unter der Annahme, dass c =/= 1 mit konstantem Glied), dass c nicht in X^j+1 aufgehen darf. Daher waehlt man bewusst Polynome, die nicht in X^j+1 fuer kleines j aufgehen; etwa geht X^15+X^14+1 in keinem X^j+1 fuer j < 32768 auf. Um eine *ungerade Zahl von Bitfehlern* zu erkennen genuegt es, ein Polynom c mit einer geraden Zahl von Monomen zu waehlen. (Denn dann aendert sich die Paritaet der Zahl der Monome bei keinem Schritt in der Polynomdivision.) Besonderes Interesse liegt in *Burst-Fehlern*. Ein Burst ist eine Folge aufeinanderfolgender Bits, die falsch uebertragen wurden. Der Fehler ist dann von der Form e = X^i(X^{k-1} + .. + X +1). Fuer c nicht von der Fom X^j wird der Fehler nur dann nicht erkannt, wenn c in X^{k-1} + ... + 1 aufgeht. Das ist der Fall, wenn k<r und c nicht gerade das Polynom X^{k-1}+...+1 ist. Man beachte, dass dieses Argument auch zeigt, dass Bloecke von Fehlern auch dann erkannt werden, wenn zwischendrin einzelne Bits nicht falsch uebertragen werden -- vorausgesetzt, das Muster der Fehler ist nicht gerade die Koeffizientenfolge von c. In der Praxis nimmt man solche c, die auch laengere Burstfehler mit grosser Wahrscheinlichkeit erkennen. Standardisiert sind die folgenden Polynome. 12 11 3 2 CRC-12 = X + X + X + X + X +1 16 15 2 CRC-16 = X + X + X + 1 16 12 5 CRC-CCIT = X + X + X + 1 Diese Polynome erkennen auch einen Grossteil laengerer Burstfehler. Zusammengesetzte Codes ~~~~~~~~~~~~~~~~~~~~~~ Burstfehler bilden ein besonderes Interesse bei der Fehlerkorrektur, da diese oft auftreten (Stoerungen von anderen Aussendungen, Kratzer auf optischen Datentraeger, etc). Die Verwendung eines grossen Alphabets (etwa F(2^k) fuer grosses k) ist an diese Art von Fehlern besonders gut angpasst: bis zu L*k Fehler in aufeinanderfolgenden Bits betreffen hoechstens (L+1) Zeichen des Codes ueber F(2^k). Hierbei haben wir angenommen, dass die einzelnen Zeichen von F(2^k) als Folge von k aufeinanderfolgenden Bits uebertragen werden, was durchaus ueblich ist. Dies ist ein einfaches Beispiel von Konkatenations-Codes: zuerst wird mit einem "aeusseren" Code die Nachricht als Folge von Woertern ueber F(2^k) codiert, anschliessend jedes Zeichen mit einem "inneren" Code als Bitfolge. In unserem Fall ist der innere Code trivial, aber dies muss nicht notwendig zu sein. **Konkatenationscodes Definition | Fuer C_1 einen (n_1,2^{k_1})-Code ueber dem Alphabet F_{2^{k_2}} | und C_2 einen binaeren (n_2,2^{k_2})-Code wird ein binaerer | Code C_2 o C_1 wie folgt definiert. | | Nachrichten aus {0,1}^{k_1 * k_2} werden as k_1 viele F_{2^{k_2}} | Zeichen gelesen und mit C_1 codiert. Dies liefert n_1 viele | F_{2^{k_2}} Zeichen, die -- als Bitstrings der Laenge k_2 gelesen -- | mit C_2 codiert werden. Bemerkung Bei C_2 o C_1 wird C_1 oft aeusserer Code und C_2 innerer Code genannt. Die Laengen lassen sich unmittelbar ablesen. Proposition | Fuer C_1 einen (n_1,2^{k_1})-Code ueber F_{2^{k_2}} und C_2 binaerer | (n_2,2^{k_2})-Code ist C_2 o C_1 ein (n_1 n_2, 2^{k_1 * k_2})-Code. Lemma | Fuer C_1 einen (n_1,2^{k_1},d_1) Code ueber F_{2^{k_2}} und C_2 binaerer | (n_2,2^{k_2},d_2)-Code hat C_2 o C_1 die Minimaldistanz mindestens d_1*d_2. Beweis Seien s_1 und s_2 in {0,1}^{k_1 * k_2} verschieden. Diese Woerter seien durch den aeusseren Code als (c_1,...c_{n_1}) und (c_1',...,c_{n_1}') codiert. Da C_1 Minimaldistanz d_1 hat, unterscheiden sich diese Codewoerter an mindestens d_1 Stellen (i.e., fuer mindestens d_1 viele i gilt c_i =/= c_i'.). Fuer jede dieser Stellen unterscheiden sich die Codierungen mit C_2 an mindestens d_2 Stellen, macht zusammen d_1 * d_2. Die Decodierung von Ausfaellen ist straight forward. Wenn in einem inneren Zeichen ausreichend wenig Ausfaelle sind, so dass wir es rekonstruieren koennen, dann tun wir dies. Anschliessend rekonstruieren wir den aeusseren Code, so dies moeglich ist. Wie man leicht sieht, reicht dieses Verfahren um die maximal moegliche Zahl von Ausfaellen zu dekodieren. Lemma | Sind C_1 und C_2 Codes mit Minimaldistanzen d_1 und d_2, so | dekodiert eine Ausfalldekodierung des inneren Codes gefolgt von | einer Ausfalldekodierung des aeusseren Codes d_1 * d_2 - 1 | Ausfaelle. Ein aehnlich naiver Algorithmus zur Fehlerkorrektur schafft nur rund die Haelfte, dessen, was moeglich waere. Lemma | Sind C_1 und C_2 Codes mit Minimaldistanzen d_1 und d_2, so | korrigiert eine Fehlerkorrektur des inneren Codes gefolgt von einer | Fehlerkorrektur des aeusseren Codes | | ( | d_1 - 1 | ) ( | d_2 -1 | ) | | | ------- | +1 | | | ------ | +1 | -1 | ( |_ 2 _| ) ( |_ 2 _| ) | | Fehler. Beweis Bei der gegebenen Fehlerzahl koennen in hoechstens \floor{(d_1-1)/2} Woertern des inneren Codes echt mehr als \floor{(d_2-1)/2} Fehler aufgetreten sein. Alle bis auf diese inneren Woerter werden also korrekt dekodiert, so das im auesseren Code hoechstens \floor{(d_1-1)/2} Zeichen falsch sind. Damit kann der aeussere Code das Wort korrekt decodieren. Eine andere Moeglichkeit besteht darin, als inneren Code einen lediglich *fehlererkennenden* Code zu verwenden. Zeichen (also Woerter des inneren Codes) in denen Fehler erkannt werden, werden dann als Ausfaelle durch den aeusseren Code behandelt. Aehnlich werden auch gerne innere Codes (etwa mit Minimaldistanz 4) verwendet, um eine geringe Zahl von Fehler (etwa 1) zu korrigieren und zu erkennen, wenn mehr Fehler (hier: 2) aufgetreten sind; in letzterem Fall wird das Zeichen als Ausfall behandelt. **Produktcodes Mit aehnlichen Ideen koennen auch binaere Codes (die selber beispielsweise Konkatenationscodes sein koennen, wie etwa "binaere RS-Codes" (mit Identifikation 2^{k} =~= {0,1}^k als innerem Code)) zu laengeren Codes zusammengefasst werden. Der einfachste Fall ist der des Produkt-Codes. Definition | Sind C_1 und C_2 Codes der Laenge n_1 und n_2 ueber demselben | Alphabet, so ist der Produkt-Code C_1 * C_2 gegeben durch alle | n_2 * n_1 Matrizen, deren Zeilen Codewoerter aus C_1 und deren | Spalten Codewoerter aus C_2 sind. Bemerkung Sind C_1 und C_2 systematische Code mit m_1 und m_2 Daten-Zeichen, so kann schrittweise codiert werden. ----- ----- --- ----- --- | | C_1 | | | | C_2 | | | | | M | ------> | M | | | ------> | M | | | | | | | | | | | | | ----- ----- --- ----- --- |-------| |-------| (M|AM) B Wie bei Konkatenationscodes ueberlegt man sich dass die Minimaldistanz das Produkt der Minimaldistanzen ist. Lemma | Sind C_1 und C_2 gerade (n_1,q^{m_1},d_1) und (n_2,q^{m_2},d_2) | Codes ueber Fq, so ist C_1*C_2 ein (n_1 * n_2, q^{m_1 * m_2}, d_1 * d_2) | Code. Auch hier koennen wir mit naiver Decodierung die selbe Qualitaet wie bei Konkatenations-Codes erreichen. Die Argumente sind auch gleich. Lemma | "Simple-Product Decoding", also dekodieren erst der Spalten, | anschliessend der ersten m_2 Zeilen korrigiert d_1 * d_2 Ausfaelle | oder alternativ | | ( | d_1 - 1 | ) ( | d_2 -1 | ) | | | ------- | +1 | | | ------ | +1 | -1 | ( |_ 2 _| ) ( |_ 2 _| ) | | Fehler. **CIRC Fuer die Codierung auf CDs werden Cross-Interleaved Reed-Solomon Codes verwendet. Zwei RS-Codes (ueber F256) werden auf eine andere geometrische Weise verschraenkt, die keine feste Blockgroesse des zusammengesetzen Codes erfordert. Wir gehen davon aus, dass beide Codes systematisch sind. Ein Block von Nachrichten ------------------------ ...... | | M | ------------------------ ...... wird dann zunaechst mit dem ersten Code so codiert, dass alle Diagonalen(!) C_1 Codewoerter sind. *----------------------- ...... |* | * Nachricht | * ----*------------------- ...... -----*------------------ ...... |00..0* XXXXXXXXXXXXXXXX C_1 Redundanzen -------*---------------- ...... ^ | C_1 Codewort Anschliessend wird jede der sich neu ergebenden Spalten mit C_2 codiert. --------*-------------- ...... | * | * Nachricht | * --------*--------------- ...... --------*--------------- ...... |00..0XX*XXXXXXXXXXXXXXX C_1 Redundanzen --------*--------------- ...... --------*--------------- ...... |YYYYYYY*YYYYYYYYYYYYYYYY C_2 Redundanzen --------*--------------- ...... ^ | C_2 Codewort Wie ueblich sieht man, dass die Minimaldistanz das Produkt der Minimaldistanzen ist. Bei CDs wird als C_1 ein RS Code (ueber F256) mit 24 Datenbytes und 28 Byte Codelaenge verwendet; C_2 ist ein RS Code mit 28 Datenbytes (wie ueberraschend!) und 32 Byte Codelaenge. **Diamantencodes Bei CIRCs ist die "unterste Zeile" in nur einer Codierung eingeschlossen. Dies wird manchmal als Nachteil gesehen. Um dies zu umgehen wurde folgender Code vorgeschlagen. Codewoerter beim Diamantencode sind solche Matrizen, bei denen alle Spalten C_2 Codewoerter und alle vollstaendigen(!) Diagonalen C_1 Codewoerter sind. ----*--------------------------*------- ..... | * * | * * | * * | * * | * * ----------*--------------------*------- ..... C_1 Codewort C_2 Codewort
Document Actions