Die Kanalkodierung oder Vorwärtsfehlerkorrektur ist eine Methode in der Nachrichtentechnik, um digitale Daten bei der Speicherung oder bei der Übertragung über gestörte Kanäle gegen Bitfehler zu schützen.

In Ergänzung zur Kanalkodierung werden die Verfahren der Quellenkodierung benutzt, um ein Signal so zu komprimieren, dass es möglichst effektiv übertragen werden kann, also eine möglichst geringe Bandbreite benötigt.

Die Kodierungstheorie beschäftigt sich mit den mathematischen Grundlagen von Kanalkodierung und untersucht mit algebraischen Methoden die Eigenschaften der Codes.

Verfahren

---

Einem digitalen Signal, das über einen gestörten Kanal übertragen wird, überlagern sich auf seinem Weg für gewöhnlich Fehler, die sich dadurch bemerkbar machen, dass ein oder mehrere Bits verfälscht werden – aus einer „1“ wird eine „0“ oder umgekehrt. Die Aufgabe der Kanaldekodierung im Empfänger ist es nun, die Positionen der verfälschten Bits herauszufinden und diese dann zu korrigieren (durch Setzen auf den jeweils anderen Wert). Um dem Empfänger diese Aufgabe zu ermöglichen, fügt der Sender dem Nutzsignal vermittels der Kanalkodierung redundante Informationen hinzu.

Die Kanalkodierung besteht daher aus einem Verfahren zur Encodierung der Daten am Eingang eines Übertragungskanals und ihrer Decodierung an seinem Ausgang. Durch die Kodierung wird der zu übermittelnden Information – unter Berücksichtigung der speziellen Eigenschaften des Kanals – Redundanz gezielt hinzugefügt. Diese Redundanz enthält Informationen, die es erlauben, eine bestimmte Anzahl von Fehlern zu erkennen und – wenn genügend Information vorhanden ist – auch zu korrigieren. Neben der Verbesserung der Datensicherheit kann so auch meistens die Leistungseffizienz verbessert werden. Fehlerkorrektur.PNG Die Idee hinter den meisten Kodierungsverfahren ist es, den „Wiedererkennungswert“ der gesendeten Nachrichten zu erhöhen, indem dafür gesorgt wird, dass die Codewörter möglichst viele Unterschiede aufweisen. Ein Decodierer kann so erkennen, ob während der Übertragung Fehler aufgetreten sind, und entscheiden, welchem ursprünglich gesendeten Codewort ein empfangenes Wort entspricht. In der Informationstheorie ist die Hamming-Distanz ein Maß für die Unterschiedlichkeit.

Ein Code wird insbesondere durch seine Rate gekennzeichnet: $R=k/n$, wobei $k$ die Anzahl der Zeichen eines Wortes am Eingang des Kodierers ist und $n$ die Anzahl am Ausgang. Es werden also $k$ Symbole am Eingang auf $n$ Symbole am Ausgang abgebildet. Eine kleine Rate (großes $n$) bedeutet einen höheren Bedarf an Bandbreite, ist aber bei bestimmten Kanälen unter Umständen notwendig. Durch geschicktes Verketten von Codes und das Streuen von Fehlern (durch Interleaving) kann diese Rate oft erheblich vergrößert werden. Die Codes einer Compact Disc erreichen zum Beispiel eine Rate von $3/4$ und können sehr gut Fehler korrigieren.

Die Festlegung eines Kodierungsverfahren berücksichtigt sowohl die Qualitätsansprüche an das zu übertragende Signal als auch die Eigenschaften des Kanals. Wird beispielsweise ein nicht quellencodiertes Fernsehsignal mit einer Datenrate von 270 Mbit/s übertragen, und wird ein Bit auf dem Übertragungsweg verfälscht, so macht sich das in nur einem Pixel eines (Halb-)Bildes bemerkbar. Wird aber ein MPEG-codiertes Fernsehsignal übertragen, kann ein Bitfehler zumindest schon einen Makroblock verfälschen. Bei den Kanaleigenschaften ist seine Fehlercharakteristik zu berücksichtigen: Gibt es statistisch verteilte Einzelbitfehler oder gibt es häufige Burststörungen, bei denen gleich mehrere aufeinanderfolgende Bits verfälscht werden?

Kanalcodes

---

Kennt man die Fehlerarten, die in einem Übertragungskanal auftreten, kann man verschiedene Codes konstruieren, die die häufigen Fehlerarten gut, weniger häufigere Fehlerarten weniger gut korrigieren können. Die folgende Abbildung zeigt eine Übersicht häufig verwendeter Codeklassen. Codeklassen.png

• Blockcodes
• Faltungscodes
• Ungerboeck-Code
• Reed-Muller-Code
• Hamming-Code
• Reed-Solomon-Code (z.B. verwendet in bestimmten RAID-Systemen)
• Fire-Code
• BCH-Code
• Golay-Code

Turbo-Code wird die Verkettung von unterschiedlichen Kanalcodes gerne genannt. Durch Rückkopplungen können sich Dekodierer gegenseitig unterstützen)

Beispiel für Fehlererkennung: Paritätskontrolle (parity check)

---

Die Paritätskontrollcodierung hängt einer Folge von Bits (Informationswort) ein Paritätskontrollbit an: Je nachdem, ob die Summe der Einsen (Paritätssumme) im Informationswort gerade oder ungerade ist, wird eine Null bzw. eine Eins angehängt. Die resultierende Bitfolge hat in jedem Fall eine gerade Paritätssumme und ist um eine Stelle länger als das Informationswort. Es wird Codewort genannt.

Beispiel: Das Informationswort 0011101 hat vier Einsen. Vier ist eine gerade Zahl, das Paritätskontrollbit ist also die Null, und das resultierende Codewort ist 00111010. Das Informationswort 1010010 hat hingegen eine ungerade Paritätssumme und wird in das Codewort 10100101 codiert. Beide Codewörter weisen eine gerade Paritätssumme auf.

Ein derart kodiertes Wort kann nun gespeichert oder übertragen werden. Sollte dabei ein Bit verfälscht werden (eine Null in eine Eins oder eine Eins in eine Null), so ist die Paritätssumme des resultierenden Worts ungerade, und der Dekodierer erkennt, dass es zu einem Fehler gekommen ist. Es ist aber für den Dekodierer nicht möglich, den Fehler zu korrigieren, da nicht bekannt ist, welches Bit verfälscht wurde. Falls das Kommunikationssystem Rückfragen zulässt, wird der Decodierer die fragliche Bitfolge nochmal anfordern. Wurde jedoch mehr als ein Bit verfälscht, so ist es eventuell gar nicht möglich, den Fehler zu erkennen, da die Paritätssumme dann auch gerade sein kann. Man sagt: Der Paritätskontrollcode ist 1-fehlererkennend und 0-fehlerkorrigierend.

Die ursprüngliche Form der ASCII-Zeichentabelle besteht aus 128 Zeichen, jedes Zeichen ist durch eine Folge von sieben Bits eindeutig festgelegt. Da ein Rechner acht Bits zu einem Byte zusammenfasst, wird dieses achte Bit gerne verwendet, um ein Paritätskontrollbit anzuhängen.

Beispiel für Fehlererkennung: ISBN-Code

---

Der ISBN-Code basiert auf einer ähnlichen Idee wie der Paritätskontrollcode. Ein Buch bekommt eindeutig eine neunstellige Nummer zugeteilt. Schreibt man diese Nummer als $z\_1z\_2\backslash ldots\; z\_8z\_9$, so hängt der Kodierer diesem Informationswort eine Prüfziffer an. Diese berechnet sich als die Zahl, die als Rest bei der ganzzahligen Teilung von $\backslash sum\_\{k=1\}^\{9\}k\backslash cdot\; z\_k=1\backslash cdot\; z\_1+2\backslash cdot\; z\_2+\backslash dots\; +9\backslash cdot\; z\_9$ durch 11 entsteht. Sollte bei der Teilung der Rest 10 übrigbleiben, so wird dieser in Anlehnung an das römische Zahlensystem durch den Buchstaben X symbolisiert. Da ISBN-Nummern häufig mündlich weitergegeben werden, ist der Code besonders auf die Erkennung von menschlichen Fehlern ausgelegt: Wird bei der Übertragung eine Stelle verändert oder werden zwei Stellen vertauscht, so ist die Gleichung für die Prüfziffer nicht mehr gültig, und der Fehler wird erkannt.

Siehe auch

---

• Kodierungstheorie
• Fehlerkorrekturverfahren
• Hash-Funktion
• Bitfehlerrate
• Fehlerverdeckung (error concealment)

Übertragungstechnik | Kodierungstheorie

Forward error correction | FEC | kanaalcodering