Objective of Channel Coding

1. Channel Coding
2. Binäre Blockcodes zur Kanalcodierung
3. Objective of Channel Coding

• Previous page
• Next page

• Previous page
• Next page

# ÜBERBLICK ZUM ERSTEN HAUPTKAPITEL #

Das erste Kapitel behandelt Blockcodes zur Fehlererkennung und Fehlerkorrektur und liefert die Grundlagen zur Beschreibung effektiverer Codes wie zum Beispiel den Reed–Solomon–Codes (siehe Kapitel 2), den Faltungscodes (Kapitel 3) sowie den iterativ decodierbaren Produkt–Codes (Turbo–Codes) und Low–density Parity–check Codes (Kapitel 4). Wir beschränken uns hier auf binäre Codes.

Man bezeichnet dieses spezifische Fachgebiet als Kanalcodierung im Gegensatz zur Quellencodierung (Redundanzminderung aus Gründen der Datenkomprimierung) und zur Leitungscodierung (zusätzliche Redundanz zur Anpassung des Digitalsignals an die spektralen Eigenschaften des Übertragungsmediums).

Im Einzelnen werden behandelt:

• Definitionen und einführende Beispiele zur Fehlererkennung und Fehlererkorrektur,
• eine kurze Wiederholung geeigneter Kanalmodelle und Entscheiderstrukturen,
• bekannte binäre Blockcodes wie Single Parity-check–, Wiederholungs– und Hamming–Code,
• die allgemeine Beschreibung linearer Codes mittels Generatormatrix und Prüfmatrix,
• die Decodiermöglichkeiten für Blockcodes, unter anderem die Syndromdecodierung,
• einfache Näherungen und obere Schranken für die Blockfehlerwahrscheinlichkeit, sowie
• eine informationstheoretische Grenze der Kanalcodierung.

Fehlererkennung und Fehlerkorrektur

Bei einem jeden Nachrichtenübertragungssystem kommt es zu Übertragungsfehlern. Man kann zwar die Wahrscheinlichkeit $p_{\rm S}$ für einen solchen Symbolfehler sehr klein halten, zum Beispiel durch eine sehr große Signalenergie. Die Symbolfehlerwahrscheinlichkeit $p_{\rm S} = 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, zum Beispiel 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 zur Fehlererkennung

$\text{Beispiel 1: Single Parity Check Code (SPC)}$
Ergänzt man $k = 4$ Bit um ein so genanntes Prüfbit (englisch: Parity Bit) derart, dass die Summe aller Einsen geradzahlig ist, zum Beispiel (mit fettgedruckten Prüfbits)

$$0000\boldsymbol{0}, 0001\boldsymbol{1}, \text{...} , 1111\boldsymbol{0}, ...$$

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

$\text{Beispiel 2: 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]:

• $\boldsymbol{3–540–57215–5}$ (für ISBN–10), bzw.
• $\boldsymbol{978–3–54057215–2}$ (für ISBN–13).

Die letzte Ziffer $z_{10}$ ergibt sich bei ISBN–10 aus den vorherigen Ziffern $z_1 = 3$, $z_2 = 5$, ... , $z_9 = 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} = 10$ als $z_{10} = \rm 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}= 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 = 10 - [(9+8+5+0+7+1) \cdot 1 + (7+3+4+5+2+5) \cdot 3] \hspace{-0.2cm} \mod 10 \]

\[\Rightarrow \hspace{0.3cm} z_{13}= 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 \, \leftrightarrow 75$ erkannt, da hier unterschiedliche Positionen verschieden gewichtet werden.

$\text{Beispiel 3: 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.

1D–Barcode

• 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_{13}$, die sich genau so berechnet wie bei ISBN–13.

Einige einführende Beispiele zur Fehlerkorrektur

$\text{Beispiel 4: 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.

2D–Barcodes: Aztec– und QR–Code

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. Details hierzu finden Sie in [KM+09].

$\text{Beispiel 5: 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 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_{\rm B}/N_0 \approx 2 \, \rm 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 \, \rm 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.

$\text{Beispiel 6: Kanalcodes für die Mobilkommunikation}$
Ein weiteres und besonders 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 \, \rm 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 \, \rm kbit/s$ auf $22.4 \, \rm 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 $r = 9.4/13 \approx 0.72$ 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 \, \rm dB$.

$\text{Beispiel 7: Fehlerschutz der Compact Disc}$
Bei einer CD (Compact Disc) verwendet man einen cross–interleaved Reed–Solomon–Code (RS) und anschließend eine so genannte 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_{\rm 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 \, \mu m$) auf etwa $1.75\, \rm cm$ verteilt werden.
  

• Mit der Coderate $R ≈ 1/3$ 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\, \rm mm$ Länge in Abspielrichtung auf (also mehr als $6000$ aufeinanderfolgende Erasures), so sind immer noch $90\%$ aller Bits 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.

„Geschlitzte CD” des LNT/TUM

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 im $\\text{Beispiel 7}$ 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.

Zusammenspiel zwischen Quellen– und Kanalcodierung (1)

Die Nachrichtenübertragung natürlicher Quellen wie Sprache, Musik, Bilder, Videos, usw. geschieht meist entsprechend dem nachfolgend skizzierten zeitdiskreten Modell.

Zu dieser aus [Liv10] entnommenen Grafik ist Folgendes anzumerken:

• Quelle und Sinke sind digitalisiert und werden durch (gleich viele) Nullen und Einsen repräsentiert.
  

• Der Quellencodierer komprimiert die binären Daten – im betrachteten Beispiel ein Digitalfoto – und reduziert somit die Redundanz der Quelle.
  

• Der Kanalcodierer fügt wieder Redundanz hinzu und zwar gezielt, so dass die auf dem Kanal entstandenen Fehler im Kanaldecoder größtenteils korrigiert werden können.
  

• Für den Kanal wird hier ein zeitdiskretes Modell mit binärem Eingang und Ausgang verwendet, das auch die Komponenten der technischen Sende– und Empfangseinrichtungen (Modulator, Entscheider, Taktwiedergewinnung) geeignet berücksichtigen sollte.
  
  

Bei richtiger Dimensionierung von Quellen– und Kanalcodierung ist die Qualität des empfangenen Fotos hinreichend gut, auch wenn die Sinkensymbolfolge aufgrund nichtkorrigierter Fehlermuster nicht exakt mit der Quellensymbolfolge übereinstimmen wird. Im Beispiel erkennt man einen Bitfehler.

Für obige Grafik wurde beispielhaft angenommen, dass der Quellencoder die Daten um den Faktor 40/16 = 2.5 komprimiert und der Kanalcoder 50% Redundanz hinzufügt. Übertragen werden müssen also nur 60% aller Quellensymbole, zum Beispiel 24 statt 40.

Würde man auf die Quellencodierung verzichten, in dem man das ursprüngliche Foto im BMP–Format übertragen würde und nicht das komprimierte JPG–Bild, so wäre die Qualität vergleichbar, aber eine um den Faktor 2.5 höhere Bitrate und damit sehr viel mehr Aufwand erforderlich.

Zusammenspiel zwischen Quellen– und Kanalcodierung (2)

Würde man sowohl auf die Quellen– als auch auf die Kanalcodierung verzichten, also direkt die BMP–Daten ohne Fehlerschutz übertragen, so wäre das Ergebnis trotz (um den Faktor 40/24) größerer Bitrate äußerst dürftig.

Die untere Grafik zeigt das Ergebnis für den Fall, dass man die komprimierten Daten (zum Beispiel JPG) ohne Fehlersicherungsmaßnahmen direkt überträgt. Dieses Codierschema (Quellencodierung, aber keine Kanalcodierung) sollte auf jeden Fall vermieden werden.

Da die komprimierte Quelle nur noch wenig Redundanz besitzt, führt jeder einzelne Übertragungsfehler dazu, dass ganze Bildblöcke falsch decodiert werden.

Blockschaltbild und Voraussetzungen

Im weiteren Verlauf gehen wir von folgendem Blockschaltbild aus:

Dabei gelten folgende Voraussetzungen:

• Der Vektor u = (u₁, u₂, ... , u_k) kennzeichnet einen Informationsblock mit k Symbolen. Meist beschränken wir uns auf Binärsymbole (Bits)  ⇒  u_i ∈ {0, 1} für i = 1 , 2, ... , k mit gleichen Auftrittswahrscheinlichkeiten für Nullen und Einsen.
  

• Jeder Informationsblock u wird durch ein Codewort (oder Codeblock) x = (x₁, x₂, ... , x_n) mit n > k, x_i ∈ {0, 1} dargestellt. Man spricht dann von einem binären (n, k)–Blockcode C. Die Zuordnung bezeichnen wir mit x = enc(u), wobei „enc” für „Encoder–Funktion” steht.
  

• Das Empfangswort y ergibt sich aus dem Codewort x durch Modulo–2–Addition mit dem ebenfalls binären Fehlervektor e = (e₁, e₂, ... , e_n), wobei „e_i = 1” für einen Übertragungfehler steht und „e_i = 0” anzeigt, dass das i–te Bit des Codewortes richtig übertragen wurde. Es gilt also:

\[\underline{y} = \underline{x} \oplus \underline{e} \hspace{0.05cm}, \hspace{0.3cm} y_i \hspace{-0.15cm} = \hspace{-0.15cm} x_i \oplus e_i \hspace{0.05cm}, \hspace{0.2cm} i = 1, ... \hspace{0.05cm} , n\hspace{0.05cm},\]

\[x_i \hspace{-0.15cm} \in \hspace{-0.15cm} \{ 0, 1 \}\hspace{0.05cm}, \hspace{0.2cm}e_i \in \{ 0, 1 \}\hspace{0.3cm} \Rightarrow \hspace{0.3cm}y_i \in \{ 0, 1 \}\hspace{0.05cm}.\]

• Die Beschreibung durch das digitale Kanalmodell – also mit binärem Eingang und Ausgang – ist allerdings nur dann anwendbar, wenn das Übertragungssystem harte Entscheidungen trifft – siehe Kapitel 1.2. Systeme mit Soft Decision sind mit diesem einfachen Modell nicht modellierbar.
  

• Der Vektor υ nach der Kanaldecodierung hat die gleiche Länge k wie der Informationsblock u. Den Decodiervorgang beschreiben wir mit der „Decoder–Funktion” als υ = dec(y). Im fehlerfreien Fall gilt analog zu x = enc(u) auch υ = enc^–1(y).
  

• Ist der Fehlervektor e ≠ 0, so ist y meist kein gültiges Element des verwendeten Blockcodes, und der Decodiervorgang ist dann keine reine Zuordnung y → υ, sondern bezeichnet dann eine auf maximale Übereinstimmung (mimimale Fehlerwahrscheinlichkeit) basierende Schätzung von υ.
  

Einige wichtige Definitionen zur Blockcodierung

Wir betrachten nun den beispielhaften binären Blockcode

\[\mathcal{C} = \{ (0, 0, 0, 0, 0) \hspace{0.05cm}, (0, 1, 0, 1, 0) \hspace{0.05cm},(1, 0, 1, 0, 1) \hspace{0.05cm},(1, 1, 1, 1, 1) \}\hspace{0.05cm}.\]

Dieser Code wäre zum Zwecke der Fehlererkennung oder –korrektur weniger gut geeignet. Aber er ist so konstruiert, dass er die Berechnung wichtiger Beschreibungsgrößen anschaulich verdeutlicht:

• Jedes einzelne Codewort x wird durch fünf Bit beschrieben. Im gesamten Buch drücken wir diesen Sachverhalt durch die Codelänge (englisch: Code Length) n = 5 aus.

• Der obige Code beinhaltet vier Elemente. Damit ist der Codeumfang (englisch: Size) |C| = 4. Entsprechend gibt es auch vier eindeutige Zuordnungen (englisch: Mappings) zwischen u und x.

• Die Informationsblocklänge u wird mit k bezeichnet. Da bei allen binären Codes |C| = 2^k gilt, folgt aus |C| = 4 der Wert k = 2. Die Zuordnungen zwischen u und x lauten bei obigem Code C:

\[\underline{u_0} = (0, 0) \leftrightarrow (0, 0, 0, 0, 0) = \underline{x_0}\hspace{0.05cm}, \hspace{0.2cm} \underline{u_1} = (0, 1) \leftrightarrow (0, 1, 0, 1, 0) = \underline{x_1}\hspace{0.05cm}, \]

\[\underline{u_2} = (1, 0) \leftrightarrow (1, 0, 1, 0, 1) = \underline{x_2}\hspace{0.05cm}, \hspace{0.2cm} \underline{u_3} = (1, 1) \leftrightarrow (1, 1, 1, 1, 1) = \underline{x_3}\hspace{0.05cm}.\]

• Der Code weist die Coderate R = k/n = 2/5 auf. Dementsprechend beträgt seine Redundanz 1 – R, also 60%. Ohne Fehlerschutz – also für den Fall n = k – wäre die Coderate R = 1.
  

• Eine kleine Coderate zeigt an, dass von den n Bits eines Codewortes nur sehr wenige tatsächlich Information tragen. Beispielsweise gilt für einen Wiederholungscode (k = 1) mit n = 10: R = 0.1.
  

• Das Hamming–Gewicht w_H(x) des Codewortes x gibt die Zahl der Codewortelemente x_i ≠ 0 an. Bei einem binären Code ⇒ x_i  ∈  {0, 1} ist w_H(x) gleich der Summe x₁ + x₂ + ... + x_n:

\[w_{\rm H}(\underline{x}_0) = 0\hspace{0.05cm}, \hspace{0.3cm}w_{\rm H}(\underline{x}_1) = 2\hspace{0.05cm}, \hspace{0.3cm} w_{\rm H}(\underline{x}_2) = 3\hspace{0.05cm}, \hspace{0.3cm}w_{\rm H}(\underline{x}_3) = 5\hspace{0.05cm}. \]

• Die Hamming–Distanz d_H(x, x') zwischen den beiden Codeworten x und x' bezeichnet die Anzahl der Bitpositionen, in denen sich x und x' unterscheiden:

\[d_{\rm H}(\underline{x}_0, \hspace{0.05cm}\underline{x}_1) = 2\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{x}_0, \hspace{0.05cm}\underline{x}_2) = 3\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{x}_0, \hspace{0.05cm}\underline{x}_3) = 5\hspace{0.05cm},\]

\[d_{\rm H}(\underline{x}_1, \hspace{0.05cm}\underline{x}_2) = 5\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{x}_1, \hspace{0.05cm}\underline{x}_3) = 3\hspace{0.05cm}, \hspace{0.3cm} d_{\rm H}(\underline{x}_2, \hspace{0.05cm}\underline{x}_3) = 2\hspace{0.05cm}.\]

• Eine wichtige Eigenschaft eines Codes C, die seine Korrekturfähigkeit wesentlich beeinflusst, ist die minimale Distanz zwischen zwei beliebigen Codeworten:

\[d_{\rm min}(\mathcal{C}) = \min_{\substack{\underline{x},\hspace{0.05cm}\underline{x}' \hspace{0.05cm}\in \hspace{0.05cm} \mathcal{C} \\ {\underline{x}} \hspace{0.05cm}\ne \hspace{0.05cm} \underline{x}'}}\hspace{0.1cm}d_{\rm H}(\underline{x}, \hspace{0.05cm}\underline{x}')\hspace{0.05cm}.\]

• Manchmal fügt man den Parameter d_min noch an die Kurzbezeichnung an und spricht dann von einem (n, k, d_min)–Blockcode. Nach dieser Nomenklatur handelt es sich im hier betrachteten Beispiel um einen (5, 2, 2)–Blockcode.
  

Beispiele für Fehlererkennung und Fehlerkorrektur

Beispiel A: Wir betrachten zunächst einen (4, 2, 2)–Blockcode mit den Zuordnungen

\[\underline{u_0} = (0, 0) \leftrightarrow (0, 0, 0, 0) = \underline{x_0}\hspace{0.05cm}, \hspace{0.8cm} \underline{u_1} = (0, 1) \leftrightarrow (0, 1, 0, 1) = \underline{x_1}\hspace{0.05cm},\]

\[\underline{u_2} = (1, 0) \leftrightarrow (1, 0, 1, 0) = \underline{x_2}\hspace{0.05cm}, \hspace{0.8cm} \underline{u_3} = (1, 1) \leftrightarrow (1, 1, 1, 1) = \underline{x_3}\hspace{0.05cm}.\]

Die nach rechts bzw. links zeigenden Pfeile verdeutlichen den Codiervorgang bzw. die Decodierung.

Rechts sind alle 2⁴ = 16 möglichen Empfangsworte y dargestellt. Von diesen können 2ⁿ – 2^k = 12 nur durch Bitfehler entstanden sein. Empfängt der Decoder ein „weißes” Codewort, so erkennt er zwar einen Fehler, er kann diesen aber wegen d_min = 2 nicht korrigieren. Empfängt er y = (0, 0, 0, 1), so kann mit gleicher Wahrscheinlichkeit das Codewort x₀ = (0, 0, 0, 0) oder x₁ = (0, 1, 0, 1) gesendet worden sein.

Im Beispiel B betrachten wir den (5, 2, 3)–Blockcode gemäß der zweiten Grafik mit den (gültigen) Codeworten (0, 0, 0, 0, 0), (0, 1, 0, 1, 1), (1, 0, 1, 1, 0) und (1, 1, 1, 0, 1). Dargestellt ist die Empfängerseite. Von den 2ⁿ – 2^k = 28 unzulässigen Codeworten lassen sich nun 20 einem gültigen Codewort (rot, grün, blau oder ocker) zuordnen, wenn man davon ausgeht, dass ein einziger Bitfehler wahrscheinlicher ist als deren zwei. In der Grafik erkennt man verfälschte Bit an der Kursivschrift.

Die Fehlerkorrektur ist aufgrund der minimalen Distanz d_min = 3 zwischen den Codeworten möglich. Allerdings sind acht Empfangsworte nicht decodierbar. Beispielsweise könnte das Empfangswort y = (0, 0, 1, 0, 1) sowohl aus dem Codewort x = (0, 0, 0, 0, 0) durch zwei Bitfehler entstanden sein oder auch aus x = (1, 1, 1, 0, 1). Auch in diesem Fall wären zwei Bitfehler aufgetreten.

Zur Nomenklatur in diesem Buch

Eine Zielvorgabe unseres Lerntutorials LNTwww war, das gesamte Fachgebiet der Nachrichtentechnik und der zugehörigen Grundlagenfächer mit einheitlicher Nomenklatur zu beschreiben. In diesem zuletzt in Angriff genommenen LNTwww–Buch „Einführung in die Kanalcodierung” müssen nun doch einige Änderungen hinsichtlich der Nomenklatur vorgenommen werden. Die Gründe hierfür sind:

• Die Codierungstheorie ist ein weitgehend in sich abgeschlossenes Fachgebiet und nur wenige Autoren von einschlägigen Fachbüchern zu diesem Gebiet versuchen, einen Zusammenhang mit anderen Aspekten der Digitalsignalübertragung herzustellen.
  

• Die Autoren der wichtigsten Bücher zur Kanalcodierung – englischsprachige und auch deutsche – verwenden eine in weiten Bereichen einheitliche Nomenklatur. Deshalb erlauben wir uns nicht, die Bezeichnungen zur Kanalcodierung in unser Übertragungstechnik–Schema zu pressen.
  
  

Die wichtigsten Änderungen gegenüber den anderen LNTwww–Büchern sind:

• Alle Signale werden durch die entsprechenden Symbolfolgen in Vektorschreibweise dargestellt. Beispielsweise kennzeichnet u = (u₁, u₂, ... , u_k) die Quellensymbolfolge und υ = (υ₁, υ₂, ... , υ_k) die Sinkensymbolfolge. Bisher wurden diese Symbolfolgen mit 〈q_ν〉 bzw. 〈υ_ν〉 bezeichnet.
  

• Das zeitdiskrete Äquivalent zum Sendesignal s(t) bzw. zum Empfangssignal r(t) in anderen Büchern sind die Vektoren x = (x₁, x₂, ... , x_n) und y = (y₁, y₂, ... , y_n). Die Coderate ergibt sich zu R = k/n (Werte zwischen 0 und 1  ⇒  n ≥ k), und m = n – k gibt die Anzahl der Prüfbits an.

• Im Kapitel 1 sind die Elemente u_i und υ_i (jeweils i = 1, ... , k) der Vektoren u und υ stets binär (0 oder 1), ebenso wie die n Elemente x_i des Codewortes x. Bei digitalem Kanalmodell (BSC, BEC, BSEC ⇒ Kapitel 1.2) gilt auch für die n Empfangswerte y_i ∈ {0, 1}.

• Das AWGN–Kanalmodell (erste Seite von Kapitel 1.2) ist durch reellwertige Ausgangswerte y_i gekennzeichnet. Der Codewortschätzer gewinnt daraus den binären Vektor z = (z₁, z₂, ... , z_n), der mit dem Codewort x zu vergleichen ist.

• Der Übergang von y auf z erfolgt entweder durch Schwellenwertentscheidung ⇒ Hard Decision oder nach dem MAP–Kriterium ⇒ Soft Decision. Die Schätzung gemäß „Maximum Likelihood” führt bei gleichwahrscheinlichen Eingangssymbolen ebenfalls zur minimalen Fehlerrate.

• Im Zusammenhang mit dem AWGN–Modell macht es Sinn, die binären Codesymbole x_i bipolar (also als +1 oder –1) darzustellen. An den statistischen Eigenschaften ändert sich dadurch nichts. Wir kennzeichnen im Folgenden die bipolare Signalisierung durch eine Tilde. Dann gilt:

\[\tilde{x}_i = 1 - 2 x_i = \left\{ \begin{array}{c} +1\\ -1 \end{array} \right.\quad \begin{array}{*{1}c} {\rm falls} \hspace{0.15cm} x_i = 0\hspace{0.05cm},\\ {\rm falls} \hspace{0.15cm}x_i = 1\hspace{0.05cm}.\\ \end{array}\]

Aufgaben

A1.1 Zur Kennzeichnung aller Bücher

A1.2 Einfacher binärer Kanalcode