Die Codierungstheorie ist die mathematische Theorie der Verfahren zur fehlerfreien Übertragung von Nachrichten in unsicheren (gestörten) Kanälen. Durch Verwendung kombinatorischer und algebraischer Methoden werden fehlererkennende und fehlerkorrigierende Codes konstruiert und ihre Eigenschaften untersucht.

Ausgangspunkt für die Entwicklung der Codierungstheorie war der 1948 von Claude Shannon bewiesene Kanalcodierungssatz, der eigentlich zur Informationstheorie gehört. Jeder gestörte Kanal kann durch einen maximalen Informationsfluß, die Kanalkapazität, beschrieben werden, mit der die Nachrichten übertragen werden können (der ungestörte Kanal hat die Kapazität 1, der vollgestörte die Kapazität 0).

Nach dem Kanalcodierungssatz gibt es zu jeder Informationsrate, die kleiner als die Kanalkapazität ist, Codes, bei denen die Decodierfehlerwahr-scheinlichkeit beliebig klein wird. Dieser überraschende (aber leider nicht konstruktive) Existenzsatz besagt, daß man die Kapazität fast voll ausnutzen kann und trotz Störungen auf dem Kanal die Codierung so auswählen kann, daß die Decodierfehler nur mit beliebig kleiner Wahrscheinlichkeit auftreten können.

Ziel der Codierungstheorie ist die Konstruktion leicht implementierbarer Codes mit einfachen Decodierregeln, die gute fehlererkennende und fehlerkorrigierende Eigenschaften haben.

Nachrichten, die von einer Quelle zu einem Empfänger übertragen werden, werden im allgemeinen zweimal codiert. Die erste (Quellen-)Codierung teilt die Nachricht in Blöcke auf und filtert Redundanzen heraus, bei der zweiten (Kanal-)Codierung, wird einem Block der Länge k ein zu übertragender Block der Länge n zugeordnet.

Mit derQuellencodierung ist meist eine Kompression verbunden, die fehlerkorrigierenden Eigenschaften werden durch die Kanalcodierung und-decodierung garantiert.

Betrachtet man Codierungen auf Nachrichten der Länge k, bei denen alle Codewörter die gleiche Länge n haben, so nennt man diese auch (n, k)-Blockcodes. Sind die Codierungen darüber hinaus lineare Abbildungen, bezeichnet man sie als lineare Codes.

Durch Codierung der Nachrichten (Elemente eines k-dimensionalen Raumes \({{\mathbb{F}}}_{q}^{k}\)) in einen n-dimensionalen Raum (\({{\mathbb{F}}}_{q}^{n}\)) bei der die Bildelemente paarweise einen sog. Hamming-Abstand d_H nicht kleiner als d haben, kann man alle Fehler, die in höchstens d/2 Komponenten auftreten, erkennen und die, die in maximal (d – 1)/2 Komponenten die Nachricht verfälscht haben, korrigieren.

Ein erkennbarer Fehler tritt beispielsweise auf, wenn man ein Wort c′ empfängt, das kein Codewort ist. Man kann versuchen, den Fehler zu korrigieren, indem man c′ durch das Codewort c₀ mit dem kleinsten Hamming-Abstand zu c′ ersetzt, also

\begin{eqnarray}{d}_{H}({c}_{0},{c}^{\prime})=\mathop{\min }\limits_{c\in C}\{{d}_{H}(c,{c}^{\prime} )\}.\end{eqnarray}

Die einfachste Codierung entsteht durch Anhängen eines Paritätsbits; sie entdeckt 1-Bit-Fehler, kann diese aber wegen des zu geringen Abstands nicht korrigieren (minimaler Hamming-Abstand 2, Informationsrate (n – 1)/n).

Eine einfache 1-Bit-Fehler korrigierende Codierung entsteht durch dreimaliges Wiederholen jedes einzelnen Bits (minimaler Hamming-Abstand 3, Informationsrate 1/3).

Allgemein gilt für einen (n, k)-Blockcode C, daß der minimale Hamming-Abstand des Codes nicht größer als n – k+1 sein kann (Singleton-Schranke). Damit kann ein (n, k)-Blockcode bestenfalls ⌊(n – k)/2⌋ Fehler korrigieren.

Für einen linearen Code (die Codierung ist in diesem Fall eine lineare Abbildung von \({{\mathbb{Z}}}_{q}^{k}\) nach \({{\mathbb{Z}}}_{q}^{n}\)) gilt zusätzlich die Plotkin-Schranke für den minimalen Abstand \({d}_{\min }=\mathop{\min }\limits_{C\times C}({d}_{H})\) und damit für die fehlerkorrigierenden Eigenschaften dieses Codes

\begin{eqnarray}{d}_{\min }\le \displaystyle \frac{n(q-1){q}^{k-1}}{{q}^{k}-1}.\end{eqnarray}

Diese Schranken werden beispielsweise durch die Hamming-Codes mit Informationsrate

\begin{eqnarray}\displaystyle \frac{{q}^{k}-1-k(q-1)}{{q}^{k}-1},\end{eqnarray}

Gute Beispiele für praktisch verwendbare Blockcodes sind die linearen Codes, und darunter die zyklischen Codes, sowie die gut implementierbaren auf Schieberegistern basierenden Faltungscodes.

Literatur

[1] Berlekamp, E.R.: Algebraic coding theory. McGraw-Hill New York, 1968.

[2] Blahut, R.E.: Theory and practice of error control codes. Addison-Wesley Reading, 1983.

[3] Heise, W.; Quattrocchi, P.: Informations- und Codierungstheorie. Springer-Verlag Berlin, 1989.