Kanalcodierung/Zielsetzung der Kanalcodierung

1. Kanalcodierung
2. Grundbegriffe der Nachrichtentechnik
3. Zielsetzung der Kanalcodierung

• Vorherige Seite
• Nächste Seite

• Vorherige Seite
• Nächste Seite

Fehlererkennung und Fehlerkorrektur

Bei einem jeden Nachrichtenübertragungssystem kommt es zu Übertragungsfehlern. Man kann zwar die Wahrscheinlichkeit pS für einen solchen Symbolfehler sehr klein halten, zum Beispiel durch eine sehr große Signalenergie. Die Symbolfehlerwahrscheinlichkeit pS = 0 ist aber wegen der Gaußschen WDF des stets vorhandenen thermischen Rauschens nie erreichbar.

Insbesondere bei stark gestörten Kanälen und auch für sicherheitskritische Anwendungen ist es deshalb unumgänglich, die zu übertragenden Daten angepasst an Anwendung und Kanal besonders zu schützen. Dazu fügt man beim Sender Redundanz hinzu und nutzt diese Redundanz beim Empfänger, um die Anzahl der Decodierfehler zu verringern. Dabei unterscheidet man:

• Fehlererkennung (englisch: Error Detection): Der Decoder prüft die Integrität der empfangenen Blöcke und markiert gefundene Fehler. Eventuell informiert der Empfänger den Sender über fehlerhafte Blöcke via Rückkanal, so dass dieser den entsprechenden Block noch einmal sendet.
  

• Fehlerkorrektur (englisch: Error Correction): Der Decoder erkennt einen (oder mehrere) Bitfehler und liefert für diese weitere Informationen, z.B. deren Positionen im übertragenen Block. Damit können unter Umständen die entstandenen Fehler vollständig korrigiert werden.
  
  

Die Kanalcodierung (englisch: Channel Coding oder auch Error–Control Coding) umfasst sowohl Verfahren zur Fehlererkennung als auch solche zur Fehlerkorrektur.

Alle ARQ–Verfahren (englisch: Automatic Repeat Request) nutzen ausschließlich Fehlererkennung. Für die Fehlererkennung ist weniger Redundanz erforderlich als für eine Fehlerkorrektur. Ein Nachteil der ARQ ist der geringe Durchsatz bei schlechter Kanalqualität, also dann, wenn häufig ganze Datenblöcke vom Empfänger neu angefordert werden müssen.

In diesem Buch behandeln wir größtenteils die Vorwärtsfehlerkorrektur (englisch: Forward Error Correction, FEC), die bei einem ausreichend guten Kanal (großes SNR) zu sehr kleinen Fehlerraten führt. Bei schlechteren Kanalbedingungen ändert sich am Durchsatz nichts, das heißt, es wird die gleiche Informationsmenge übertragen. Allerdings kann dann die Fehlerrate sehr große Werte annehmen.

Oft werden FEC– und ARQ–Verfahren kombiniert, und zwischen diesen die Redundanz so aufgeteilt,

• dass eine kleine Anzahl von Fehlern noch korrigierbar ist,
• bei vielen Fehlern aber eine Wiederholung des Blocks angefordert wird.

Einige einführende Beispiele (1)

Es folgen zunächst einige Beispiele zur Fehlererkennung. Auf der nächsten Seite werden dann ein paar Einsatzgebiete von Fehlerkorrektur genannt.

Single Parity Check Code (SPC)

Ergänzt man k = 4 Bit um ein sog. Prüfbit (englisch: Parity Bit) derart, dass die Summe aller Einsen geradzahlig ist, zum Beispiel (mit rotem Prüfbit)

00000, 00011, ... , 11110, ...

so kann man einen Einzelfehler sehr einfach erkennen. Zwei Fehler innerhalb eines Codewortes bleiben dagegen unerkannt. Die deutsche Bezeichnung ist Paritätsprüfcode.

International Standard Book Number (ISBN)

Seit den 1960er Jahren werden alle Bücher mit 10–stelligen Kennzahlen (ISBN–10) versehen. Seit 2007 ist zusätzlich noch die Angabe entsprechend ISBN–13 verpflichtend. Beispielsweise lauten diese für das Fachbuch [Söd93]:

3–540–57215–5 (ISBN–10) bzw. 978–3–54057215–2 (ISBN–13).

Die letzte Ziffer z₁₀ (rot markiert) ergibt sich bei ISBN–10 aus den vorherigen Ziffern z₁ = 3, z₂ = 5, ... , z₉ = 5 nach folgender Rechenregel:

\[z_{10} = \left ( \sum_{i=1}^{9} \hspace{0.2cm} i \cdot z_i \right ) \hspace{-0.3cm} \mod 11 = (1 \cdot 3 + 2 \cdot 5 + ... + 9 \cdot 5 ) \hspace{-0.2cm} \mod 11 = 5 \hspace{0.05cm}. \]

Zu beachten ist, dass z₁₀ = 10 als z₁₀ = „X” geschrieben werden muss (römische Zahlendarstellung von „10”), da sich die Zahl 10 im Zehnersystem nicht als Ziffer darstellen lässt.

Entsprechend gilt für die Prüfziffer bei ISBN–13:

\[z_{13} \hspace{-0.1cm} = \hspace{-0.1cm} 10 - \left ( \sum_{i=1}^{12} \hspace{0.2cm} z_i \cdot 3^{(i+1) \hspace{-0.2cm} \mod 2} \right ) \hspace{-0.3cm} \mod 10 = \] \[\hspace{0.6cm} = \hspace{-0.1cm} 10 - [(9+8+5+0+7+1) \cdot 1 + (7+3+4+5+2+5) \cdot 3] \hspace{-0.2cm} \mod 10 = \] \[\hspace{0.6cm} = \hspace{-0.1cm} 10 - (108 \hspace{-0.2cm} \mod 10) = 10 - 8 = 2 \hspace{0.05cm}. \]

Bei beiden Varianten werden im Gegensatz zum obigen Paritätsprüfcode (SPC) auch Zahlendreher wie 57 ⇒ 75 erkannt, da hier unterschiedliche Positionen verschieden gewichtet werden.

Strichcode (eindimensionaler Barcode)
Der am weitesten verbreitete fehlererkennende Code weltweit ist der Strichcode oder Balkencode (englisch: Bar Code) zur Kennzeichnung von Produkten, zum Beispiel EAN–13 (European Article Number) mit 13 Ziffern. Diese werden durch verschieden breite Balken und Lücken dargestellt und können mit einem opto–elektronischen Lesegerät leicht entschlüsselt werden. Die ersten drei Ziffern kennzeichnen das Land (beispielsweise Deutschland: 400 – 440), die nächsten vier bzw. fünf Stellen den Hersteller und das Produkt. Die letzte Ziffer ist die Prüfziffer z₁₃, die sich genau so berechnet wie bei ISBN–13.

Einige einführende Beispiele (2)

Es folgen noch einige Beispiele zur Fehlerkorrektur. Genauere Details hierzu finden Sie in [KM+09].

2D–Barcodes für Online–Tickets

Wenn Sie eine Fahrkarte der Deutschen Bahn online buchen und ausdrucken, finden Sie ein Beispiel eines zweidimensionalen Barcodes, nämlich den 1995 von Andy Longacre bei der Firma Welch Allyn in den USA entwickelten Aztec–Code, mit dem Datenmengen bis zu 3000 Zeichen codiert werden können. Aufgrund der Reed–Solomon–Fehlerkorrektur ist die Rekonstruktion des Dateninhalts auch dann noch möglich, wenn bis zu 40% des Codes zerstört wurden, zum Beispiel durch Knicken der Fahrkarte oder durch Kaffeeflecken.

Rechts ist ein QR–Code (Quick Response) mit zugehörigem Inhalt dargestellt. Der QR–Code wurde 1994 für die Autoindustrie in Japan zur Kennzeichnung von Bauteilen entwickelt und erlaubt ebenfalls eine Fehlerkorrektur. Inzwischen ist der Einsatz des QR–Codes sehr vielfältig. In Japan findet man ihn auf nahezu jedem Werbeplakat und auf jeder Visitenkarte. Auch in Deutschland setzt er sich mehr und mehr durch.

Bei allen 2D–Barcodes gibt es quadratische Markierungen zur Kalibrierung des Lesegerätes.

Codes für die Satelliten– und Weltraumkommunikation
Eines der ersten Einsatzgebiete von Fehlerkorrekturverfahren war die Kommunikation von/zu Satelliten und Raumfähren, also Übertragungsstrecken, die durch niedrige Sendeleistungen und große Pfadverluste gekennzeichnet sind. Schon 1977 wurde bei der Raum–Mission Voyager 1 zu Neptun und Uranus eine Kanalcodierung eingesetzt, und zwar in Form der seriellen Verkettung eines Reed–Solomon–Codes und eines Faltungscodes.

Damit genügte schon der Leistungskennwert 10 · lg E_B/N₀ ≈ 2 dB, um die geforderte Fehlerrate 5 · 10^–5 (bezogen auf die komprimierten Daten nach der Quellencodierung) zu erreichen. Ohne Kanalcodierung sind dagegen für die gleiche Fehlerrate fast 9 dB erforderlich, also eine um den Faktor 10^0.7 ≈ 5 größere Sendeleistung.

Auch das geplante Marsprojekt (die Datenübertragung vom Mars zur Erde mit 5W–Lasern) wird nur mit einem ausgeklügelten Codierschema erfolgreich sein.

Die Aufzählung wird auf der nächsten Seite fortgesetzt.

Einige einführende Beispiele (3)

Kanalcodes für die Mobilkommunikation

Ein weiteres umsatzstarkes Anwendungsgebiet, das ohne Kanalcodierung nicht funktionieren würde, ist die Mobilkommunikation. Hier ergäben sich bei ungünstigen Bedingungen ohne Codierung Fehlerraten im Prozentbereich und aufgrund von Abschattungen und Mehrwegeausbreitung (Echos) treten die Fehler oft gebündelt auf. Die Fehlerbündellänge beträgt dabei manchmal einige hundert Bit.

• Bei der Sprachübertragung im GSM–System werden die 182 wichtigsten (Klasse 1a und 1b) der insgesamt 260 Bit eines Sprachrahmens (20 ms) zusammen mit einigen wenigen Paritäts– und Tailbits faltungscodiert (mit Memory m = 4 und Rate R = 1/2) und verwürfelt. Zusammen mit den 78 weniger wichtigen und deshalb uncodierten Bits der Klasse 2 führt dies dazu, dass die Bitrate von 13 kbit/s auf 22.4 kbit/s ansteigt.
  

• Man nutzt die (relative) Redundanz von r = (22.4 – 13)/22.4 ≈ 0.42 zur Fehlerkorrektur. Anzumerken ist, dass „r = 0.42” aufgrund der hier verwendeten Definition aussagt, das 42% der codierten Bits redundant sind. Mit dem Bezugswert „Bitrate der uncodierten Folge” ergäbe sich <nobr>r = 9.4/13 = 0.72</nobr> mit der Aussage: Zu den Informationsbits werden 72% Prüfbits hinzugefügt.
  

• Bei UMTS (Universal Mobile Telecommunications System) werden Faltungscodes mit den Raten R = 1/2 bzw. R = 1/3 eingesetzt. Bei den UMTS–Modi für höhere Datenraten und entsprechend geringeren Spreizfaktoren verwendet man dagegen Turbo–Codes der Rate R = 1/3 und iterative Decodierung. Abhängig von der Anzahl der Iterationen erzielt man hier gegenüber der Faltungscodierung Gewinne von bis zu 3 dB.
  
  

Fehlerschutz der Compact Disc

Bei einer CD (Compact Disc) verwendet man einen cross–interleaved Reed–Solomon–Code (RS) und anschließend eine sogenannte Eight–to–Fourteen–Modulation. Die Redundanz nutzt man zur Fehlererkennung und –korrektur. Dieses Codierschema zeigt folgende Charakteristika:

• Die gemeinsame Coderate der zwei RS–Komponentencodes beträgt R_RS = 24/28 · 28/32 = 3/4. Durch die 8–to–14–Modulation und einiger Kontrollbits kommt man zur Gesamtcoderate R ≈ 1/3.
  

• Bei statistisch unabhängigen Fehlern gemäß dem BSC–Modell (Binary Symmetric Channel) ist eine vollständige Korrektur möglich, so lange die Bitfehlerrate den Wert 10^–3 nicht überschreitet.
  

• Der CD–spezifische Cross Interleaver verwürfelt 108 Blöcke miteinander, so dass die 588 Bit eines Blockes (jedes Bit entspricht ca. 0.28 μm) auf etwa 1.75 cm verteilt werden.
  

• Mit der Coderate R ≈ 33% kann man ca. 10% Erasures korrigieren und die verloren gegangenen Werte lassen sich durch Interpolation (näherungsweise) rekonstruieren  ⇒ Fehlerverschleierung.
  
  

Zusammenfassend lässt sich sagen: Weist eine CD einen Kratzer von 1.75 mm Länge in Abspielrichtung auf (also mehr als 6000 aufeinanderfolgende Erasures), so sind immer noch 90% aller Bit eines Blockes fehlerfrei, so dass sich auch die fehlenden 10% rekonstruieren lassen, oder dass die Auslöschungen zumindest so verschleiert werden können, dass sie nicht hörbar sind.

Auf der nächsten Seite folgt eine Demonstration zur Korrekturfähigkeit der CD.

Die „Geschlitzte CD” – eine Demonstration des LNT der TUM

Ende der 1990er Jahre haben Mitarbeiter des Lehrstuhls für Nachrichtentechnik der TU München unter Leitung von Professor Joachim Hagenauer eine Musik–CD gezielt beschädigt, indem insgesamt drei Schlitze von jeweils mehr als einem Millimeter Breite eingefräst wurden. Damit fehlen bei jedem Defekt fast 4000 fortlaufende Bit der Audiocodierung.

Die Grafik zeigt die „geschlitzte CD”. Sowohl in der Spur 3 als auch in der Spur 14 gibt es bei jeder Umdrehung zwei solcher fehlerhafter Bereiche. Sie können sich die Musikqualität mit Hilfe der beiden Audioplayer (Abspielzeit jeweils ca. 15 Sekunden) verdeutlichen. Die Theorie zu dieser Audio–Demo finden Sie auf der vorherigen Seite.

Audio File Please add link and do not upload flash videos.

Audio File Please add link and do not upload flash videos.

Resumee dieser Audiodemo:

• Die Fehlerkorrektur der CD basiert auf zwei seriell–verketteten Reed–Solomon–Codes sowie Eight–to–Fourteen Modulation. Die Gesamtcoderate zur RS–Fehlerkorrektur beträgt R = 3/4.
  

• Ebenso wichtig für die Funktionsfähigkeit der CD wie die Codes ist der dazwischen geschaltete Interleaver, der die ausgelöschten Bits („Erasures”) über eine Länge von fast 2 cm verteilt.
  

• Bei der Spur 14 liegen die beiden defekten Bereiche genügend weit auseinander. Deshalb ist der Reed–Solomon–Decoder in der Lage, die fehlenden Daten zu rekonstruieren.
  

• Bei der Spur 3 folgen die beiden Fehlerblöcke in sehr kurzem Abstand aufeinander, so dass der Korrekturalgorithmus versagt. Das Resultat ist ein fast periodisches Klackgeräusch.
  
  

Wir bedanken uns bei Rainer Bauer, Thomas Hindelang und Manfred Jürgens herzlich dafür, diese Audio–Demo verwenden zu dürfen.