coding-cs16-07

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