Channel Coding/Objective of Channel Coding

1. Channel Coding
2. Binary Block Codes for Channel Coding
3. Objective of Channel Coding

• [[Channel Coding/{{{Vorherige Seite}}} | Previous page]]
• Next page

• [[Channel Coding/{{{Vorherige Seite}}} | Previous page]]
• Next page

# Overview on The First Main Chapter #

The first chapter deals with block codes for error detection and error correction and provides the basics for describing more effective codes such as the  Reed-Solomon codes  (see Chapter 2), the  convolutional codes  (Chapter 3), and the  iteratively decodable product codes  (turbo codes) and  low-density parity-check codes  (Chapter 4). We restrict ourselves here to binary codes.

This specific field is called  channel coding  in contrast to  source coding  (redundancy reduction for reasons of data compression) and to  line coding  (additional redundancy to adapt the digital signal to the spectral characteristics of the transmission medium).

In detail, it covers:

• Definitions and introductory examples of error detection and error correction,
• a brief review of appropriate channel models and decision maker structures,
• known binary block codes such as single parity-check code, repetition code and Hamming code,
• the general description of linear codes using generator matrix and check matrix,
• the decoding possibilities for block codes, including syndrome decoding,
• simple approximations and upper bounds for block error probability, and
• an information-theoretic bound on channel coding.

Error Detection and Error Correction

Transmission errors occur in every message transmission system. It is possible to keep the probability  $p_{\rm S}$  of such a symbol error very small, for example by using a very large signal energy. However, the symbol error probability  $p_{\rm S} = 0$  is never achievable because of the Gaussian WDF of the thermal noise that is always present.

Particularly in the case of heavily disturbed channels and also for safety-critical applications, it is therefore essential to provide special protection for the data to be transmitted, adapted to the application and channel. For this purpose, redundancy is added at the transmitter and this redundancy is used at the receiver to reduce the number of decoding errors.

$\text{Definitions:}$

• Error Detection  :   The decoder checks the integrity of the received blocks and marks any errors found. If necessary, the receiver informs the transmitter about erroneous blocks via the return channel, so that the transmitter sends the corresponding block again.
  

• Error Correction   The decoder detects one (or more) bit errors and provides further information for them, for example their positions in the transmitted block. In this way, it may be possible to completely correct the errors that have occurred.
  

• The  Channel Coding  includes procedures for error detection as well as those for error correction.
  

All '’’ARQ’’' (Automatic Repeat Request) procedures use error detection only. Less redundancy is required for error detection than for error correction. One disadvantage of ARQ is its low throughput when channel quality is poor, i.e. when entire blocks of data must be frequently re-requested by the receiver.

In this book we mostly deal with  Forward Error Correction  which leads to very small error rates if the channel is sufficiently good (large SNR). With worse channel conditions, nothing changes in the throughput, i.e. the same amount of information is transmitted. However, the error rate can then assume very large values.

Often FEC and ARQ methods are combined, and the redundancy is divided between them in such a way,

• so that a small number of errors can still be corrected,

but *when there are many errors, a repeat of the block is requested.

Some Introductory Examples of Error Detection

$\text{Example 1:   Single Parity–Check Code (SPC)}$
If one adds  $k = 4$  bit by a so-called check bit (English:   Parity Bit ) in such a way that the sum of all ones is even, for example (with bold check bits)

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

it is very easy to recognise a single error. Two errors within a code word, on the other hand, remain undetected.

$\text{Example 2:   International Standard Book Number (ISBN)}$
Since the 1960s, all books have been given 10-digit codes (ISBN–10 ). Since 2007, the specification according to ISBN–13  is additionally obligatory. For example, these are for the reference book [Söd93]:

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

The last digit  $z_{10}$  for ISBN–10 results from the previous digits  $z_1 = 3$,  $z_2 = 5$, ... ,  $z_9 = 5$  according to the following calculation rule:

\[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}. \]

Note that  $z_{10} = 10$  must be written as  $z_{10} = \rm X$  (Roman numeral representation of „10”), since the number  $10$  cannot be represented as a digit in the decimal system.

The same applies to the check digit for 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 \hspace{-0.05cm}- \hspace{-0.05cm} \big [(9\hspace{-0.05cm}+\hspace{-0.05cm}8\hspace{-0.05cm}+\hspace{-0.05cm}5\hspace{-0.05cm}+\hspace{-0.05cm}0\hspace{-0.05cm}+\hspace{-0.05cm}7\hspace{-0.05cm}+\hspace{-0.05cm}1) \cdot 1 + (7\hspace{-0.05cm}+\hspace{-0.05cm}3\hspace{-0.05cm}+\hspace{-0.05cm}4\hspace{-0.05cm}+\hspace{-0.05cm}5\hspace{-0.05cm}+\hspace{-0.05cm}2\hspace{-0.05cm}+\hspace{-0.05cm}5) \cdot 3\big ] \hspace{-0.2cm} \mod 10 \]

\[\Rightarrow \hspace{0.3cm} z_{13}= 10 - (108 \hspace{-0.2cm} \mod 10) = 10 - 8 = 2 \hspace{0.05cm}. \]

With both variants, in contrast to the above parity check code (SPC), number twists such as  $57 \, \leftrightarrow 75$  are also recognised, since different positions are weighted differently here

.

$\text{Example 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 nach  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:   zwischen 400 und 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  $\rm 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  $\rm 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 gegenüber der Faltungscodierung hiermit 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 \, \rm {µ m})$  auf etwa  $1.75\, \rm cm$ verteilt werden.
  

• Mit der Coderate  $R ≈ 1/3$  kann man ca.  $10\%$  „Erasures” korrigieren. 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  $\rm 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.
  

Spur 14:

Spur 3:

Resumee dieser Audiodemo:

• Die Fehlerkorrektur der CD basiert auf zwei seriell–verketteten  Reed–Solomon–Codes  sowie einer  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 \, \rm 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, diese Audio–Demo verwenden zu dürfen.

Zusammenspiel zwischen Quellen– und Kanalcodierung

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

Bildübertragung mit Quellen– und Kanalcodierung

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

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

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

• Der Kanalcodierer fügt wieder Redundanz hinzu und zwar gezielt, so dass einige der auf dem Kanal entstandenen Fehler im Kanaldecoder 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 nicht korrigierbarer Fehlermuster nicht exakt mit der Quellensymbolfolge übereinstimmen wird. Man erkennt innerhalb der Sinkensymbolfolge einen (rot markierten) Bitfehler.

$\text{Beispiel 8:}$  Für obige Grafik wurde beispielhaft und stark vereinfachend angenommen, dass

• die Quellensymbolfolge nur die Länge  $40$  hat,
• der Quellencodierer die Daten um den Faktor  $40/16 = 2.5$  komprimiert, und
• der Kanalcoder  $50\%$  Redundanz hinzufügt.

Übertragen werden müssen also nur  $24$  Codersymbole statt  $40$  Quellensymbole, was die Übertragungsrate insgesamt um  $40\%$  reduziert.

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.

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

Bildübertragung ohne Quellen– und Kanalcodierung

$\text{Beispiel 10:}$  Nun betrachten wir den Fall, dass man die komprimierten Daten (zum Beispiel JPG) ohne Fehlersicherungsmaßnahmen direkt überträgt.

Bildübertragung mit Quellencodierung, ohne Kanalcodierung

• Da die komprimierte Quelle nur noch wenig Redundanz besitzt, führt jeder einzelne Übertragungsfehler dazu, dass ganze Bildblöcke falsch decodiert werden.
  
• Dieses Codierschema (Quellencodierung, aber keine Kanalcodierung) sollte auf jeden Fall vermieden werden.

Blockschaltbild und Voraussetzungen

Im weiteren Verlauf gehen wir von dem skizzierten Blockschaltbild mit Kanalcodierer, Digitalem Kanal und Kanaldecoder aus.

Blockschaltbild zur Beschreibung der Kanalcodierung

Dabei gelten folgende Voraussetzungen:

• Der Vektor  $\underline{u} = (u_1, u_2, \text{...} \hspace{0.05cm}, u_k)$  kennzeichnet einen  Informationsblock  mit  $k$  Symbolen.
• Meist beschränken wir uns auf Binärsymbole (Bits)   ⇒   $u_i \in \{0, \, 1\}$ für $i = 1, 2, \text{...} \hspace{0.05cm}, k$  mit gleichen Auftrittswahrscheinlichkeiten für Nullen und Einsen.
  

• Jeder Informationsblock  $\underline{u}$  wird durch ein  Codewort  (oder einen  Codeblock)  $\underline{x} = (x_1, x_2, \text{...} \hspace{0.05cm}, x_n)$  mit  $n \ge k$, $x_i \in \{0, \, 1\}$  dargestellt. Man spricht dann von einem binären  $(n, k)$–Blockcode  $C$. Die Zuordnung bezeichnen wir mit  $\underline{x} = {\rm enc}(\underline{u})$, wobei „enc” für „Encoder–Funktion” steht.
  

• Das  Empfangswort $\underline{y}$  ergibt sich aus dem Codewort  $\underline{x}$  durch  Modulo–2–Addition  mit dem ebenfalls binären Fehlervektor  $\underline{e} = (e_1, e_2, \text{...} \hspace{0.05cm}, e_n)$, wobei „$e= 1$” für einen Übertragungfehler steht und „$e= 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.5cm} y_i = x_i \oplus e_i \hspace{0.05cm}, \hspace{0.2cm} i = 1, \text{...} \hspace{0.05cm} , n\hspace{0.05cm}, x_i \hspace{-0.05cm} \in \hspace{-0.05cm} \{ 0, 1 \}\hspace{0.05cm}, \hspace{0.5cm}e_i \in \{ 0, 1 \}\hspace{0.5cm} \Rightarrow \hspace{0.5cm}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  AWGN–Kanal bei binärem Eingang. Systeme mit  Soft Decision  sind mit diesem einfachen Modell nicht modellierbar.
  

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

• Ist der Fehlervektor  $\underline{e} \ne \underline{0}$, so ist  $\underline{y}$  meist kein gültiges Element des verwendeten Blockcodes, und die Decodierung ist dann keine reine Zuordnung  $\underline{y} \rightarrow \underline{v}$, sondern eine auf maximale Übereinstimmung (mimimale Fehlerwahrscheinlichkeit) basierende Schätzung von  $\underline{v}$.
  

Einige wichtige Definitionen zur Blockcodierung

Wir betrachten nun den beispielhaften binären Blockcode

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

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

• Jedes einzelne Codewort  $\underline{u}$  wird durch fünf Bit beschrieben. Im gesamten Buch drücken wir diesen Sachverhalt durch die  Codewortlänge  (englisch:  Code Length )  $n = 5$ aus.

• Der obige Code beinhaltet vier Elemente. Damit ist der  Codeumfang  (englisch:   Size )  $ <div style="clear:both;"> </div> </div> \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}.\] <div class="bluebox"> $\text{Definition:}$  Ein  $(n, \hspace{0.05cm}k, \hspace{0.05cm}d_{\rm min})\text{ – Blockcode}$  besitzt die Codewortlänge  $n$, die Informationsblocklänge  $k$  und die minimale Distanz  $d_{\rm min}$. *Nach dieser Nomenklatur handelt es sich im hier betrachteten Beispiel um einen  $(5, \hspace{0.05cm}2,\hspace{0.05cm} 2)$ – Blockcode. *Manchmal verzichtet man auf die Angabe von  $d_{\rm min}$  und spricht dann von einem  $(n,\hspace{0.05cm} k)$ – Blockcode. <div style="clear:both;"> </div> </div><br> =='"`UNIQ--h-3--QINU`"' Beispiele für Fehlererkennung und Fehlerkorrektur == <br> Die eben definierten Größen sollen nun an zwei Beispielen verdeutlicht werden. <div class="greybox"> $\text{Beispiel 11:}$     $\text{(4, 2, 2)–Blockcode}$ In der Grafik verdeutlichen die nach rechts bzw. links zeigenden Pfeile den Codiervorgang bzw. die Decodierung: :'"`UNIQ-MathJax2-QINU`"' :'"`UNIQ-MathJax3-QINU`"' [[File:P ID2532 KC T 1 1 S5a v2.png|center|frame|(4, 2, 2)–Blockcode zur Fehlererkennung|class=fit]] Rechts sind alle  $2^4 = 16$  möglichen Empfangsworte  $\underline{y}$  dargestellt: * Von diesen können  $2^n - 2^k = 12$  nur durch Bitfehler entstanden sein. *Empfängt der Decoder ein solches „weißes” Codewort, so erkennt er zwar einen Fehler, er kann diesen aber wegen  $d_{\rm min} = 2$  nicht korrigieren. *Empfängt er beispielsweise  $\underline{y} = (0, 0, 0, 1)$, so kann nämlich mit gleicher Wahrscheinlichkeit  $\underline{x_0} = (0, 0, 0, 0)$  oder  $\underline{x_1} = (0, 1, 0, 1)$ gesendet worden sein. <div style="clear:both;"> </div> </div><br> [[File:P ID2533 KC T 1 1 S5b v2.png|right|frame|(5, 2, 3)–Blockcode zur Fehlerkorrektur|class=fit]] <div class="greybox"> $\text{Beispiel 11:}$     $\text{(5, 2, 3)–Blockcode}$ Hier gibt es wegen $k=2$ vier gültige Codeworte : :'"`UNIQ-MathJax4-QINU`"' :'"`UNIQ-MathJax5-QINU`"' In der Grafik dargestellt ist die Empfängerseite, wobei man verfälschte Bit an der Kursivschrift erkennt. <br clear="all"> *Von den  $2^n - 2^k = 28$  unzulässigen Codeworten lassen sich nun  $20$  einem gültigen Codewort (Füllfarbe:   rot, grün, blau oder ocker) zuordnen, wenn man davon ausgeht, dass ein einziger Bitfehler wahrscheinlicher ist als deren zwei oder mehr. *Zu jedem gültigen Codewort gibt es fünf unzulässige Codeworte mit jeweils nur einer Verfälschung   ⇒   Hamming–Distanz  $d_{\rm H} =1$. Diese sind in dem jeweiligen Quadrat mit roter, grüner, blauer oder ockerfarbenen Hintergrundfarbe angegeben. *Die Fehlerkorrektur ist für diese aufgrund der minimalen Distanz  $d_{\rm min} = 3$  zwischen den Codeworten möglich. *Acht Empfangsworte sind nicht decodierbar. Beispielsweise könnte das Empfangswort  $\underline{y} = (0, 0, 1, 0, 1)$  aus dem Codewort  $\underline{x}_0 = (0, 0, 0, 0, 0)$  entstanden sein, aber auch aus dem Codewort  $\underline{x}_3 = (1, 1, 1, 0, 1)$. In beiden Fällen wären zwei Bitfehler aufgetreten. <div style="clear:both;"> </div> </div><br> =='"`UNIQ--h-4--QINU`"' Zur Nomenklatur in diesem Buch == <br> Eine Zielvorgabe unseres Lerntutorials  $\rm LNTwww$  war, das gesamte Fachgebiet der Nachrichtentechnik und der zugehörigen Grundlagenfächer mit einheitlicher Nomenklatur zu beschreiben. In diesem zuletzt in Angriff genommenen Buch „ 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.<br> *Die Autoren der wichtigsten Bücher zur Kanalcodierung – englischsprachige und deutsche – verwenden weitgehend eine einheitliche Nomenklatur. Wir erlauben uns deshalb nicht, die Bezeichnungen zur Kanalcodierung in unser Übertragungstechnik–Schema zu pressen.<br><br> Einige Nomenklaturänderungen gegenüber den anderen  $\rm LNTwww$–Büchern sollen hier genannt werden: *Alle Signale werden durch Symbolfolgen in Vektorschreibweise dargestellt. Beispielsweise kennzeichnet  $\underline{u} = (u_1, u_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, u_k)$  die  <i>Quellensymbolfolge</i>  und  $\underline{v} = (v_1, v_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, v_k)$  die <i>Sinkensymbolfolge</i>. Bisher wurden diese Symbolfolgen mit  $\langle q_\nu \rangle$  bzw.  $\langle v_\nu \rangle$  bezeichnet.<br> *Der Vektor $\underline{x} = (x_1, x_2, \hspace{0.05cm}\text{...} \hspace{0.05cm}, x_n)$  bezeichnet nun das zeitdiskrete Äquivalent zum Sendesignal  $s(t)$, während das Empfangssignal  $r(t)$ durch den Vektor  $\underline{y} = (y_1, y_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, y_n)$  beschrieben wird. Die Coderate ist der Quotient </i>  $R=k/n$   mit   $0 \le R \le 1$ und die Anzahl der Prüfbits ergibt sich zu  $m = n-k$. *Im ersten Hauptkapitel sind die Elemente  $u_i$  und  $v_i$   $($jeweils mit Index  $i = 1, \hspace{0.05cm}\text{...} \hspace{0.05cm}, k)$  der Vektoren  $\underline{u}$  und  $\underline{v}$  stets binär  $(0$  oder  $1)$, ebenso wie die  $n$  Elemente  $x_i$  des Codewortes  $\underline{x}$. Bei digitalem Kanalmodell  ([[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|BSC]],  [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Binary_Erasure_Channel_.E2.80.93_BEC|BEC]],  [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Error_.26_Erasure_Channel_.E2.80.93_BSEC|BSEC]]) gilt auch für die  $n$  Empfangswerte  $y_i \in \{0, 1\}$. *Das  [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang|AWGN–Kanalmodell]]  ist durch reellwertige Ausgangswerte  $y_i$  gekennzeichnet. Der <i>Codewortschätzer</i> gewinnt in diesem Fall aus dem Vektor  $\underline{y} = (y_1, y_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, y_n)$  den binären Vektor  $\underline{z} = (z_1, z_2, \hspace{0.05cm}\text{...} \hspace{0.05cm}, z_n)$, der mit dem Codewort  $\underline{x}$  zu vergleichen ist. *Der Übergang von  $\underline{y}$  auf  $\underline{z}$  erfolgt durch Schwellenwertentscheidung   ⇒   <i>Hard Decision</i> oder nach dem MAP–Kriterium   ⇒   <i>Soft Decision</i>. Bei gleichwahrscheinlichen Eingangssymbolen führt die „Maximum Likelihood”–Schätzung ebenfalls zur minimalen Fehlerrate. *Im Zusammenhang mit dem AWGN–Modell macht es Sinn, binäre Codesymbole $x_i$ bipolar (also $\pm1$) 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 zum Kapitel

Aufgabe 1.1: Zur Kennzeichnung aller Bücher

Aufgabe 1.2: Einfacher binärer Kanalcode

Aufgabe 1.2Z: 3D–Darstellung von Codes

Quellenverzeichnis