Kanalcodierung/Beispiele binärer Blockcodes: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 8: Zeile 8:
 
== Single Parity–check Codes==
 
== Single Parity–check Codes==
 
<br>
 
<br>
Der <i>Single Parity&ndash;check Code</i> (SPC) fügt zu dem Informationsblock <i><u>u</u></i> = (<i>u</i><sub>1</sub>, <i>u</i><sub>2</sub>, ... , <i>u</i><sub>k</sub>) ein Prüfbit (englisch: <i>Parity</i>) <i>p</i> hinzu:
+
Der <i>Single Parity&ndash;check Code</i> (SPC) fügt zu dem Informationsblock $\underline{u}= (u_1, u_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, u_k)$ ein Prüfbit (englisch: <i>Parity</i>) $p$ hinzu:
  
:<math>\underline{u} = (u_1, u_2,\hspace{0.05cm} ... \hspace{0.05cm} , u_k)  \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
+
::<math>\underline{u} = (u_1, u_2,\hspace{0.05cm} ... \hspace{0.05cm} , u_k)  \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
\underline{x} =  (x_1, x_2,\hspace{0.05cm} ... \hspace{0.05cm} , x_n) = (u_1, u_2,\hspace{0.05cm} ... \hspace{0.05cm} , u_k, p)
+
\underline{x} =  (x_1, x_2,\hspace{0.05cm}\text{...} \hspace{0.05cm} , x_n) = (u_1, u_2,\hspace{0.05cm} \text{...}\hspace{0.05cm} , u_k, p)
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
Die Grafik zeigt drei Beispiele solcher Codes mit |<i>C</i>| = 4 (<i>k</i> = 2), |<i>C</i>| = 8 (<i>k</i> = 3) und |<i>C</i>| = 16 (<i>k</i> = 4).<br>
+
[[Datei:P ID2346 KC T 1 3 S1 v2.png|right|frame|Single Parity–check Code $(n = k  + 1)$|class=fit]]
 +
Die Grafik zeigt drei Coder&ndash;Beispiele mit  
 +
*$|\mathcal{C}| = 4 \ (k = 2)$,  
 +
*$|\mathcal{C}| = 8 \ (k = 3)$ und  
 +
*$|\mathcal{C}| = 16 \ (k = 4)$.<br>
 +
 
 +
 
 +
 
  
[[Datei:P ID2346 KC T 1 3 S1 v2.png|Single Parity–check Code (<i>n</i> = <i>k</i> + 1)|class=fit]]<br>
 
  
 
Dieser sehr einfache Code ist wie folgt charakterisiert:
 
Dieser sehr einfache Code ist wie folgt charakterisiert:
*Aus <i>n</i> = <i>k</i> + 1 folgt für die Coderate R = k/n = (<i>n</i> &ndash; 1)/<i>n</i> und für die Redundanz 1 &ndash; <i>R</i> = 1/<i>n</i>. Für <i>k</i> = 2 ergibt sich zum Beispiel die Coderate 2/3 und die relative Redundanz beträgt 33.3%.
+
*Aus $n = k + 1$ folgt für die ''Coderate'' $R = k/n = (n-1)/n$ und für die ''Redundanz'' $1-R = 1/n$. Für $k = 2$ ergibt sich zum Beispiel die Coderate 2/3 und die relative Redundanz beträgt 33.3%.
  
*Das Prüfbit erhält man durch die Modulo&ndash;2&ndash;Addition. Darunter versteht man die Addition im Galoisfeld zur Basis 2 &nbsp;&#8658;&nbsp; GF(2), sodass  1&oplus;1 = 0 ergibt:
+
*Das Prüfbit erhält man durch die Modulo&ndash;2&ndash;Addition. Darunter versteht man die Addition im [[Kanalcodierung/Einige_Grundlagen_der_Algebra#Definition_eines_Galoisfeldes|Galoisfeld]] zur Basis 2 &nbsp; &#8658; &nbsp; GF(2), sodass  $1 \oplus 1 = 0$ ergibt:
  
::<math>p = u_1 \oplus u_2 \oplus ... \hspace{0.05cm} \oplus u_k  
+
::<math>p = u_1 \oplus u_2 \oplus \text{...} \hspace{0.05cm} \oplus u_k  
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
*Damit enthält jedes gültige Codewort <i><u>x</u></i> eine gerade Anzahl von Einsen. Ausgedrückt mit &oplus; bzw. in vereinfachter Schreibweise entsprechend der zweiten Gleichung lautet diese Bedingung:
+
*Damit enthält jedes gültige Codewort $\underline{x}$ eine gerade Anzahl von Einsen. Ausgedrückt mit $\oplus$ bzw. in vereinfachter Schreibweise entsprechend der zweiten Gleichung lautet diese Bedingung:
  
::<math> x_1 \oplus x_2 \oplus ... \hspace{0.05cm} \oplus x_n = 0  
+
::<math> x_1 \oplus x_2 \oplus \text{...} \hspace{0.05cm} \oplus x_n = 0  
 
\hspace{0.05cm}, \hspace{0.5cm}{\rm oder:}\hspace{0.15cm}  
 
\hspace{0.05cm}, \hspace{0.5cm}{\rm oder:}\hspace{0.15cm}  
 
\sum_{i=1}^{n} \hspace{0.2cm} x_i = 0\hspace{0.05cm}
 
\sum_{i=1}^{n} \hspace{0.2cm} x_i = 0\hspace{0.05cm}
Zeile 34: Zeile 40:
 
\hspace{0.05cm}. </math>
 
\hspace{0.05cm}. </math>
  
*Für <i>k</i> = 2 &#8658; <i>n</i> = 3 ergeben sich die folgenden vier Codeworte, wobei in der ersten Zeile das Prüfbit jeweils durch einen kleinen Pfeil markiert ist:
+
*Für $k = 2$ &nbsp; &#8658; &nbsp; $n = 3$ ergeben sich die folgenden vier Codeworte, wobei in der ersten Zeile das Prüfbit jeweils durch einen kleinen Pfeil markiert ist:
  
 
::<math>\underline{x}_0 = (0, 0_{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 0)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_1 = (0, 1_{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 1)\hspace{0.05cm}, \hspace{0.2cm}
 
::<math>\underline{x}_0 = (0, 0_{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 0)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_1 = (0, 1_{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 1)\hspace{0.05cm}, \hspace{0.2cm}
 
\underline{x}_2 = (1, 0 _{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 1)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_3 = (1, 1 _{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 0)</math>
 
\underline{x}_2 = (1, 0 _{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 1)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_3 = (1, 1 _{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 0)</math>
  
*Es handelt sich um einen linearen Code, da die Summe zweier beliebiger Codeworte wieder ein gültiges Codewort ergibt, zum Beispiel <i><u>x</u></i><sub>1</sub> &oplus; <i><u>x</u></i><sub>2</sub> = <i><u>x</u></i><sub>3</sub>.<br>
+
*Es handelt sich um einen ''linearen Code'', da die Summe zweier beliebiger Codeworte wieder ein gültiges Codewort ergibt, zum Beispiel :$$\underline{x}_1 \oplus \underline{x}_2 = \underline{x}_3.$$<br>
  
*Für beliebiges <i>k</i> &nbsp;&#8658;&nbsp; <i>n</i> = <i>k</i> + 1 unterscheidet sich jedes Codewort von allen anderen an einer geraden Anzahl von Positionen. Bei diesem Code ist die minimale Distanz <i>d</i><sub>min</sub> = 2.<br><br>
+
*Für beliebiges $k$ &nbsp; &#8658; &nbsp; $n = k+1$ unterscheidet sich jedes Codewort von allen anderen an einer geraden Anzahl von Positionen. Bei diesem Code ist die minimale Distanz $d_{\rm min} = 2$.<br><br>
  
Mit der allgemeinen Codebezeichnung (<i>n</i>, <i>k</i>, <i>d</i><sub>min</sub>) lässt sich jeder <i>Single Parity&ndash;check Code</i> auch mit (n, n &ndash; 1, 2) benennen. Die Grafik zeigt den SPC (3, 2, 2), den SPC (4, 3, 2) und den SPC (5, 4, 2).
+
{{BlaueBox|TEXT= 
 +
$\text{Definition:}$&nbsp; Jeder '''Single Parity&ndash;check Code''' (SPC) lässt sich formal wie folgt beschreiben:
  
{{Definition}}''':''' Jeder Single Parity&ndash;check Code (SPC) lässt sich formal wie folgt beschreiben:
+
::<math>\mathcal{C} = \{ \underline{x} \in {\rm GF}(2^n)\hspace{-0.15cm}: \hspace{0.15cm}{\rm mit \hspace{0.15cm}geradzahliger\hspace{0.15cm} Anzahl\hspace{0.15cm} von\hspace{0.15cm} Einsen\hspace{0.15cm} in \hspace{0.15cm} } \underline{x} \}\hspace{0.05cm}.</math>
 +
 
 +
*Mit der allgemeinen Codebezeichnung $(n, k, d_{\rm min})$ lässt sich jeder <i>Single Parity&ndash;check Code</i> auch mit $(n, n-1, 2)$ benennen.
 +
*Die obere Grafik zeigt somit den SPC (3, 2, 2), den SPC (4, 3, 2) und den SPC (5, 4, 2).}}<br>
  
:<math>\mathcal{C} = \{ \underline{x} \in {\rm GF}(2^n)\hspace{-0.15cm}: \hspace{0.15cm}{\rm mit \hspace{0.15cm}geradzahliger\hspace{0.15cm} Anzahl\hspace{0.15cm} von\hspace{0.15cm} Einsen\hspace{0.15cm} in \hspace{0.15cm}} \underline{x} \}\hspace{0.05cm}.</math>{{end}}<br>
 
  
== Single Parity–check Codes (2) ==
 
<br>
 
 
Der digitale Kanal ändert möglicherweise das Codewort <i><u>x</u></i> = (<i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, ... , <i>x<sub>n</sub></i>)  in das Empfangswort <i><u>y</u></i>&nbsp;=&nbsp;(<i>y</i><sub>1</sub>, <i>y</i><sub>2</sub>, ... ,&nbsp;<i>y<sub>n</sub></i>), wobei mit dem Fehlervektor <i><u>e</u></i>&nbsp;=&nbsp;(<i>e</i><sub>1</sub>, <i>e</i><sub>2</sub>, ... ,&nbsp;<i>e<sub>n</sub></i>) gilt: <u><i>y</i></u> = <u><i>x</i></u> &oplus; <u><i>e</i></u>. Zur Decodierung des <i>Single Parity&ndash;check Codes</i>  bildet man das sogenannte Syndrom:
 
Der digitale Kanal ändert möglicherweise das Codewort <i><u>x</u></i> = (<i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, ... , <i>x<sub>n</sub></i>)  in das Empfangswort <i><u>y</u></i>&nbsp;=&nbsp;(<i>y</i><sub>1</sub>, <i>y</i><sub>2</sub>, ... ,&nbsp;<i>y<sub>n</sub></i>), wobei mit dem Fehlervektor <i><u>e</u></i>&nbsp;=&nbsp;(<i>e</i><sub>1</sub>, <i>e</i><sub>2</sub>, ... ,&nbsp;<i>e<sub>n</sub></i>) gilt: <u><i>y</i></u> = <u><i>x</i></u> &oplus; <u><i>e</i></u>. Zur Decodierung des <i>Single Parity&ndash;check Codes</i>  bildet man das sogenannte Syndrom:
  
Zeile 63: Zeile 70:
 
{{Beispiel}}''':''' Wir betrachten den SPC (4, 3, 2) und gehen davon aus, dass das Nullwort gesendet wurde. Die Tabelle zeigt alle Möglichkeiten, dass <i>f</i> Bit verfälscht werden und gibt das jeweilige Syndrom <i>s</i> (entweder 0 oder 1) an.<br>
 
{{Beispiel}}''':''' Wir betrachten den SPC (4, 3, 2) und gehen davon aus, dass das Nullwort gesendet wurde. Die Tabelle zeigt alle Möglichkeiten, dass <i>f</i> Bit verfälscht werden und gibt das jeweilige Syndrom <i>s</i> (entweder 0 oder 1) an.<br>
  
[[Datei:P ID2382 KC T 1 3 S1c.png|Mögliche Empfangswerte beim SPC (4, 3, 2) |class=fit]]<br>
+
[[Datei:P ID2382 KC T 1 3 S1c.png|center|frame|Mögliche Empfangswerte beim SPC (4, 3, 2) |class=fit]]
  
 
Für das BSC&ndash;Modell mit <i>&epsilon;</i> = 1% ergeben sich dann  folgende Wahrscheinlichkeiten:
 
Für das BSC&ndash;Modell mit <i>&epsilon;</i> = 1% ergeben sich dann  folgende Wahrscheinlichkeiten:
Zeile 100: Zeile 107:
 
Auch beim [http://www.lntwww.de/Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang AWGN&ndash;Kanal] ist Fehlerkorrektur möglich, wenn man <i>Soft Decision</i> anwendet. Für das Folgende gehen wir von bipolarer Signalisierung aus: <i>x</i> = 0 &#8594; <i>x</i>&#x0303; = +1, &nbsp;&nbsp; <i>x</i> = 1 &#8594; <i>x</i>&#x0303; = &ndash;1.<br>
 
Auch beim [http://www.lntwww.de/Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang AWGN&ndash;Kanal] ist Fehlerkorrektur möglich, wenn man <i>Soft Decision</i> anwendet. Für das Folgende gehen wir von bipolarer Signalisierung aus: <i>x</i> = 0 &#8594; <i>x</i>&#x0303; = +1, &nbsp;&nbsp; <i>x</i> = 1 &#8594; <i>x</i>&#x0303; = &ndash;1.<br>
 
   
 
   
[[Datei:P ID2387 KC T 1 3 S1d v2.png|Zur Verdeutlichung von <i>Soft Decision</i> bei AWGN|class=fit]]<br>
+
[[Datei:P ID2387 KC T 1 3 S1d v2.png|center|frame|Zur Verdeutlichung von <i>Soft Decision</i> bei AWGN|class=fit]]<br>
  
 
Die Grafik verdeutlicht den hier dargelegten Sachverhalt:
 
Die Grafik verdeutlicht den hier dargelegten Sachverhalt:
Zeile 127: Zeile 134:
 
Ein solcher (<i>n</i>, 1, <i>n</i>)&ndash;Blockcode besitzt nur die sehr kleine Coderate <i>R</i> = 1/<i>n</i>, ist aber auch sehr robust. Insbesondere beim BEC&ndash;Kanal genügt ein einziges richtig übertragenes Bit an beliebiger Position (alle anderen Bit können ausgelöscht sein), um das Informationswort richtig zu decodieren.<br>
 
Ein solcher (<i>n</i>, 1, <i>n</i>)&ndash;Blockcode besitzt nur die sehr kleine Coderate <i>R</i> = 1/<i>n</i>, ist aber auch sehr robust. Insbesondere beim BEC&ndash;Kanal genügt ein einziges richtig übertragenes Bit an beliebiger Position (alle anderen Bit können ausgelöscht sein), um das Informationswort richtig zu decodieren.<br>
  
[[Datei:P ID2347 KC T 1 3 S2 v2.png|Wiederholungscode (<i>Repetition Code</i>)|class=fit]]<br>
+
[[Datei:P ID2347 KC T 1 3 S2 v2.png|center|frame|Wiederholungscode (<i>Repetition Code</i>)|class=fit]]<br>
  
 
Betrachten wir zunächst die Decodierung und Fehlerwahrscheinlichkeiten beim BSC&ndash;Kanal.<br>
 
Betrachten wir zunächst die Decodierung und Fehlerwahrscheinlichkeiten beim BSC&ndash;Kanal.<br>
Zeile 184: Zeile 191:
 
Die linke Grafik zeigt die Fehlerwahrscheinlichkeit in doppelt logarithmischer Darstellung. Als Abszisse ist 10 &middot; lg (<i>E</i><sub>S</sub>/<i>N</i><sub>0</sub>) aufgetragen. Die Bildbeschreibung folgt auf der nächsten Seite.<br>
 
Die linke Grafik zeigt die Fehlerwahrscheinlichkeit in doppelt logarithmischer Darstellung. Als Abszisse ist 10 &middot; lg (<i>E</i><sub>S</sub>/<i>N</i><sub>0</sub>) aufgetragen. Die Bildbeschreibung folgt auf der nächsten Seite.<br>
  
[[Datei:P ID2348 KC T 1 3 S2b v2.png|Fehlerwahrscheinlichkeit des Wiederholungscodes beim AWGN–Kanal|class=fit]]<br>
+
[[Datei:P ID2348 KC T 1 3 S2b v2.png|center|frame|Fehlerwahrscheinlichkeit des Wiederholungscodes beim AWGN–Kanal|class=fit]]<br>
  
 
== Wiederholungscodes (3) ==
 
== Wiederholungscodes (3) ==
Zeile 267: Zeile 274:
 
<br>Die nachfolgende Tabelle zeigt die 2<sup><i>k</i></sup> = 16 zulässigen Codeworte <i><u>x</u></i> = (<i>u</i><sub>1</sub>, <i>u</i><sub>2</sub>, <i>u</i><sub>3</sub>, <i>u</i><sub>4</sub>, <i>p</i><sub>1</sub>, <i>p</i><sub>2</sub>, <i>p</i><sub>3</sub>) des systematischen (7, 4, 3)&ndash;Codes. Das Informationswort <i><u>u</u></i> = (<i>u</i><sub>1</sub>, <i>u</i><sub>2</sub>, <i>u</i><sub>3</sub>, <i>u</i><sub>4</sub>) ist schwarz dargestellt und die Prüfbits <i>p</i><sub>1</sub>, <i>p</i><sub>2</sub>, <i>p</i><sub>3</sub> rot. Man erkennt anhand dieser Tabelle, dass sich jeweils zwei der 16 möglichen Codeworte in mindestens <i>d</i><sub>min</sub> = 3 Binärwerten unterscheiden.<br>
 
<br>Die nachfolgende Tabelle zeigt die 2<sup><i>k</i></sup> = 16 zulässigen Codeworte <i><u>x</u></i> = (<i>u</i><sub>1</sub>, <i>u</i><sub>2</sub>, <i>u</i><sub>3</sub>, <i>u</i><sub>4</sub>, <i>p</i><sub>1</sub>, <i>p</i><sub>2</sub>, <i>p</i><sub>3</sub>) des systematischen (7, 4, 3)&ndash;Codes. Das Informationswort <i><u>u</u></i> = (<i>u</i><sub>1</sub>, <i>u</i><sub>2</sub>, <i>u</i><sub>3</sub>, <i>u</i><sub>4</sub>) ist schwarz dargestellt und die Prüfbits <i>p</i><sub>1</sub>, <i>p</i><sub>2</sub>, <i>p</i><sub>3</sub> rot. Man erkennt anhand dieser Tabelle, dass sich jeweils zwei der 16 möglichen Codeworte in mindestens <i>d</i><sub>min</sub> = 3 Binärwerten unterscheiden.<br>
  
[[Datei:P ID2351 KC T 1 3 S3c v2.png|Zuordnung <i><u>u</u></i> → <i><u>x</u></i> des systematischen (7, 4, 3)–Hamming–Codes|class=fit]]<br>
+
[[Datei:P ID2351 KC T 1 3 S3c v2.png|center|frame|Zuordnung <i><u>u</u></i> → <i><u>x</u></i> des systematischen (7, 4, 3)–Hamming–Codes|class=fit]]<br>
  
 
Die Decodierung linearer Blockcodes wird im [http://www.lntwww.de/Kanalcodierung/Decodierung_linearer_Blockcodes#Blockschaltbild_und_Voraussetzungen Kapitel 1.5] ausführlich behandelt. Das nun folgende Beispiel soll die Decodierung des Hamming&ndash;Codes eher intuitiv  erklären.<br>
 
Die Decodierung linearer Blockcodes wird im [http://www.lntwww.de/Kanalcodierung/Decodierung_linearer_Blockcodes#Blockschaltbild_und_Voraussetzungen Kapitel 1.5] ausführlich behandelt. Das nun folgende Beispiel soll die Decodierung des Hamming&ndash;Codes eher intuitiv  erklären.<br>

Version vom 11. November 2017, 11:12 Uhr

Single Parity–check Codes


Der Single Parity–check Code (SPC) fügt zu dem Informationsblock $\underline{u}= (u_1, u_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, u_k)$ ein Prüfbit (englisch: Parity) $p$ hinzu:

\[\underline{u} = (u_1, u_2,\hspace{0.05cm} ... \hspace{0.05cm} , u_k) \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x} = (x_1, x_2,\hspace{0.05cm}\text{...} \hspace{0.05cm} , x_n) = (u_1, u_2,\hspace{0.05cm} \text{...}\hspace{0.05cm} , u_k, p) \hspace{0.05cm}.\]
Single Parity–check Code $(n = k + 1)$

Die Grafik zeigt drei Coder–Beispiele mit

  • $|\mathcal{C}| = 4 \ (k = 2)$,
  • $|\mathcal{C}| = 8 \ (k = 3)$ und
  • $|\mathcal{C}| = 16 \ (k = 4)$.



Dieser sehr einfache Code ist wie folgt charakterisiert:

  • Aus $n = k + 1$ folgt für die Coderate $R = k/n = (n-1)/n$ und für die Redundanz $1-R = 1/n$. Für $k = 2$ ergibt sich zum Beispiel die Coderate 2/3 und die relative Redundanz beträgt 33.3%.
  • Das Prüfbit erhält man durch die Modulo–2–Addition. Darunter versteht man die Addition im Galoisfeld zur Basis 2   ⇒   GF(2), sodass $1 \oplus 1 = 0$ ergibt:
\[p = u_1 \oplus u_2 \oplus \text{...} \hspace{0.05cm} \oplus u_k \hspace{0.05cm}.\]
  • Damit enthält jedes gültige Codewort $\underline{x}$ eine gerade Anzahl von Einsen. Ausgedrückt mit $\oplus$ bzw. in vereinfachter Schreibweise entsprechend der zweiten Gleichung lautet diese Bedingung:
\[ x_1 \oplus x_2 \oplus \text{...} \hspace{0.05cm} \oplus x_n = 0 \hspace{0.05cm}, \hspace{0.5cm}{\rm oder:}\hspace{0.15cm} \sum_{i=1}^{n} \hspace{0.2cm} x_i = 0\hspace{0.05cm} , \hspace{0.3cm} {\rm Addition\hspace{0.15cm} in \hspace{0.15cm} GF(2)} \hspace{0.05cm}. \]
  • Für $k = 2$   ⇒   $n = 3$ ergeben sich die folgenden vier Codeworte, wobei in der ersten Zeile das Prüfbit jeweils durch einen kleinen Pfeil markiert ist:
\[\underline{x}_0 = (0, 0_{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 0)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_1 = (0, 1_{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 1)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_2 = (1, 0 _{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 1)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_3 = (1, 1 _{\hspace{0.05cm} \rightarrow}\hspace{0.05cm} 0)\]
  • Es handelt sich um einen linearen Code, da die Summe zweier beliebiger Codeworte wieder ein gültiges Codewort ergibt, zum Beispiel :$$\underline{x}_1 \oplus \underline{x}_2 = \underline{x}_3.$$
  • Für beliebiges $k$   ⇒   $n = k+1$ unterscheidet sich jedes Codewort von allen anderen an einer geraden Anzahl von Positionen. Bei diesem Code ist die minimale Distanz $d_{\rm min} = 2$.

$\text{Definition:}$  Jeder Single Parity–check Code (SPC) lässt sich formal wie folgt beschreiben:

\[\mathcal{C} = \{ \underline{x} \in {\rm GF}(2^n)\hspace{-0.15cm}: \hspace{0.15cm}{\rm mit \hspace{0.15cm}geradzahliger\hspace{0.15cm} Anzahl\hspace{0.15cm} von\hspace{0.15cm} Einsen\hspace{0.15cm} in \hspace{0.15cm} } \underline{x} \}\hspace{0.05cm}.\]
  • Mit der allgemeinen Codebezeichnung $(n, k, d_{\rm min})$ lässt sich jeder Single Parity–check Code auch mit $(n, n-1, 2)$ benennen.
  • Die obere Grafik zeigt somit den SPC (3, 2, 2), den SPC (4, 3, 2) und den SPC (5, 4, 2).



Der digitale Kanal ändert möglicherweise das Codewort x = (x1, x2, ... , xn) in das Empfangswort y = (y1, y2, ... , yn), wobei mit dem Fehlervektor e = (e1, e2, ... , en) gilt: y = xe. Zur Decodierung des Single Parity–check Codes bildet man das sogenannte Syndrom:

\[s = y_1 \oplus y_2 \oplus ... \hspace{0.05cm} \oplus y_n = \sum_{i=1}^{n} \hspace{0.2cm} y_i \hspace{0.1cm} \in \hspace{0.2cm} \{0, 1 \} \hspace{0.05cm}.\]

Das Ergebnis „s = 1” weist dann auf (mindestens) einen Bitfehler innerhalb des Codewortes hin, während „s = 0” wie folgt zu interpretieren ist:

  • Die Übertragung war fehlerfrei, oder:
  • Die Anzahl der Bitfehler ist geradzahlig.

: Wir betrachten den SPC (4, 3, 2) und gehen davon aus, dass das Nullwort gesendet wurde. Die Tabelle zeigt alle Möglichkeiten, dass f Bit verfälscht werden und gibt das jeweilige Syndrom s (entweder 0 oder 1) an.
Mögliche Empfangswerte beim SPC (4, 3, 2)

Für das BSC–Modell mit ε = 1% ergeben sich dann folgende Wahrscheinlichkeiten:

  • Das Informationswort wird richtig decodiert (blaue Hinterlegung):
\[{\rm Pr}(\underline{v} = \underline{u}) = {\rm Pr}(\underline{y} = \underline{x}) = (1 - \varepsilon)^n = 0.99^4 \approx 96\,\%\hspace{0.05cm}.\]
  • Der Decoder erkennt, dass Übertragungsfehler aufgetreten sind (grüne Hinterlegung):
\[{\rm Pr}(s=1) \hspace{-0.1cm} = \hspace{-0.1cm} \sum_{f=1 \atop f \hspace{0.1cm}{\rm ungerade} }^{n} {n \choose f} \cdot \varepsilon^{f} \cdot (1 - \varepsilon)^{n-f} = \]
\[\hspace{1.8cm} = \hspace{-0.1cm} {4 \choose 1} \cdot 0.01 \cdot 0.99^3 + {4 \choose 3} \cdot 0.01^3 \cdot 0.99 \approx 3.9\,\%\hspace{0.05cm}.\]
  • Das Informationswort wird falsch decodiert (rote Hinterlegung):
\[{\rm Pr}(\underline{v} \ne \underline{u}) \hspace{-0.1cm} = \hspace{-0.1cm} \sum_{f=2 \atop f \hspace{0.1cm}{\rm gerade} }^{n} {n \choose f} \cdot \varepsilon^{f} \cdot (1 - \varepsilon)^{n-f} = \]
\[\hspace{2cm} = \hspace{-0.1cm} 1 - {\rm Pr}(\underline{v} = \underline{u}) - {\rm Pr}(s=1)\approx 0.1\,\%\hspace{0.05cm}.\]
Wir verweisen hier auf das Modul Ereigniswahrscheinlichkeiten der Binomialverteilung. Please add link and do not upload flash videos.


In der Aufgabe A1.5 werden die hier gewonnenen Ergebnisse noch ausführlich diskutiert.

Single Parity–check Codes (3)


Eine Fehlerkorrektur des Single Parity–check Codes ist beim BSC–Modell nicht möglich im Unterschied zum BEC–Kanal (Binary Erasure Channel). Bei diesem werden Bitfehler ausgeschlossen. Ist nur ein Bit ausgelöscht (englisch: Erasure, E), so ist aufgrund der Tatsache „die Anzahl der Einsen im Codewort ist gerade” auch eine Fehlerkorrektur möglich, zum Beispiel für den SPC (5, 4):

\[\underline{y} \hspace{-0.1cm} = \hspace{-0.1cm} (1, 0, {\rm E}, 1, 1) \hspace{0.2cm}\Rightarrow\hspace{0.2cm}\underline{z} = (1, 0, 1, 1, 1) \hspace{0.2cm}\Rightarrow\hspace{0.2cm} \underline{v} = (1, 0, 1, 1) = \underline{u}\hspace{0.05cm},\] \[\underline{y} \hspace{-0.1cm} = \hspace{-0.1cm} (0, 1, 1, {\rm E}, 0) \hspace{0.2cm}\Rightarrow\hspace{0.2cm}\underline{z} = (0, 1, 1, 0, 0) \hspace{0.2cm}\Rightarrow\hspace{0.2cm} \underline{v} = (0, 1, 1, 0) = \underline{u}\hspace{0.05cm},\] \[\underline{y} \hspace{-0.1cm} = \hspace{-0.1cm} (0, 1, 0, 1, {\rm E}) \hspace{0.2cm}\Rightarrow\hspace{0.2cm}\underline{z} = (0, 1, 0, 1, 0) \hspace{0.2cm}\Rightarrow\hspace{0.2cm} \underline{v} = (0, 1, 0, 1) = \underline{u}\hspace{0.05cm}.\]

Auch beim AWGN–Kanal ist Fehlerkorrektur möglich, wenn man Soft Decision anwendet. Für das Folgende gehen wir von bipolarer Signalisierung aus: x = 0 → x̃ = +1,    x = 1 → x̃ = –1.

Zur Verdeutlichung von Soft Decision bei AWGN


Die Grafik verdeutlicht den hier dargelegten Sachverhalt:

  • Beispielsweise lautet der Empfangsvektor (rote Punkte):
\[\underline{y} = (+0.8, -1.2, -0.1, +0.5, -0.6) \hspace{0.05cm}.\]
  • Bei harter Entscheidung (Schwelle G = 0, nur die Vorzeichen werden ausgewertet) würde man zu folgendem binären Ergebnis kommen (grüne Quadrate Yi = yi / |yi|):
\[\underline{Y} = (+1, -1, -1, +1, -1) \hspace{0.05cm}.\]
  • In Symbolschreibweise ergibt sich daraus (0, 1, 1, 0, 1), was kein gültiges Codewort ist  ⇒  Syndrom s = 1. Also müssen ein, drei oder fünf Bit verfälscht worden sein.
  • Die Wahrscheinlichkeit für drei oder fünf Bitfehler ist allerdings um Größenordnungen kleiner als diejenige für einen einzigen Fehler. Die Annahme „ein Bitfehler” ist deshalb nicht abwegig.
  • Da der Empfangswert y3 sehr nahe an der Schwelle G = 0 liegt, geht man davon aus, dass genau dieses Bit verfälscht wurde. Damit fällt bei Soft Decision die Entscheidung für z = (0, 1, 0, 0, 1)  ⇒  υ = (0, 1, 0, 0). Die Blockfehlerwahrscheinlichkeit Pr(υu) ist so am geringsten.

Wiederholungscodes


: Man bezeichnet einen linearen binären (n, k)–Blockcode

\[\mathcal{C} = \{ \underline{x} \in {\rm GF}(2^n): x_i = x_j \hspace{0.15cm}{\rm f\ddot{u}r \hspace{0.15cm}alle\hspace{0.25cm}} i, j = 1, ... \hspace{0.1cm}, n \}\]

als Wiederholungscode (englisch: Repetition Code, RC) der Länge n. Es gilt also stets k = 1. Entsprechend existieren nur zwei Codeworte (0, 0, ... , 0) und (1, 1, ... , 1), die sich in n Binärstellen unterscheiden. Daraus folgt für die minimale Distanz dmin = n.


Ein solcher (n, 1, n)–Blockcode besitzt nur die sehr kleine Coderate R = 1/n, ist aber auch sehr robust. Insbesondere beim BEC–Kanal genügt ein einziges richtig übertragenes Bit an beliebiger Position (alle anderen Bit können ausgelöscht sein), um das Informationswort richtig zu decodieren.

Wiederholungscode (Repetition Code)


Betrachten wir zunächst die Decodierung und Fehlerwahrscheinlichkeiten beim BSC–Kanal.

: Es gelte der BSC–Kanal mit ε = 10%. Die Decodierung basiere auf dem Majoritätsprinzip. Bei ungeradem n können e = n – 1 Fehler erkannt und t = (n – 1)/2 Bitfehler korrigiert werden. Damit ergibt sich für die Wahrscheinlichkeit der korrekten Decodierung der Informationsbits u:

\[{\rm Pr}(v = u) = \sum_{f=0 }^{(n-1)/2} {n \choose f} \cdot \varepsilon^{f} \cdot (1 - \varepsilon)^{n-f} \hspace{0.05cm}.\]

Die nachfolgenden Zahlenwerte gelten für n = 5. Das heißt: Es sind t = 2 Bitfehler korrigierbar:

\[{\rm Pr}(v = u) = (1 - \varepsilon)^5 + 5 \cdot \varepsilon \cdot (1 - \varepsilon)^4 + 10 \cdot \varepsilon^2 \cdot (1 - \varepsilon)^3 \approx 99.15\,\%\]

\[\Rightarrow\hspace{0.3cm}{\rm Pr}(v \ne u) = 1- {\rm Pr}(v = u) \approx 0.85\,\%\hspace{0.05cm}.\]

Bei geradem n können dagegen nur n/2 – 1 Fehler korrigiert werden. Erhöht man n von 5 auf 6, so sind weiterhin auch nur zwei Bitfehler innerhalb eines Codewortes korrigierbar. Einen dritten Bitfehler kann man zwar nicht korrigieren, aber zumindest erkennen:

\[{\rm Pr}({\rm nicht\hspace{0.15cm} korrigierbarer\hspace{0.15cm} Fehler}) = {6 \choose 3} \cdot \varepsilon^{3} \cdot (1 - \varepsilon)^{3}= 20 \cdot 0.1^{3} \cdot 0.9^{3}\approx 1.46\,\%\hspace{0.05cm}. \]

Ein (unerkannter) Decodierfehler (υu) ergibt sich erst, wenn innerhalb des 6 Bit–Wortes vier oder mehr Bit verfälscht wurden. Als Näherung unter der Annahme, dass fünf oder sechs Bitfehler sehr viel unwahrscheinlicher sind als vier, gilt:

\[{\rm Pr}(v \ne u) \approx {6 \choose 4} \cdot \varepsilon^{4} \cdot (1 - \varepsilon)^{2}= 0.122\,\%\hspace{0.05cm}.\]

Interessant ist, dass beim RC(6, 1, 6) die Wahrscheinlichkeit Pr(υ = u) für eine mögliche und richtige Decodierung mit 98.42% kleiner ist als beim RC(5, 1, 5).


Wiederholungscodes (2)


Nun interessieren wir uns für die Leistungsfähigkeit des Wiederholungscodes beim AWGN–Kanal. Bei uncodierter Übertragung (oder dem Wiederholungscode mit n = 1) ist der Empfangswert y = x̃ + η, wobei x̃ ∈ {+1, –1} das Informationsbit bei bipolarer Signalisierung bezeichnet und η den Rauschterm. Um Verwechslungen mit dem Codeparameter n zu vermeiden, wurde das Rauschen umbenannt: nη.

Für die Fehlerwahrscheinlichkeit gilt mit dem Komplementären Gaußschen Fehlerintegral Please add link and do not upload flash videos. Q(x)

\[{\rm Pr}(v \ne u) = {\rm Q}(\sqrt{\rho}) \hspace{0.05cm},\]

wobei folgende physikalische Größen zu verwenden sind:

  • das Signal–zu–Rauschleistungsverhältnis ρ = 1/σ2 = 2 ES/N0,
  • die Energie ES pro Codesymbol  ⇒  Symbolenergie,
  • die normierte Streuung σ des Rauschens, gültig für das Nutzsignal x̃ ∈ {+1, –1}, und
  • die konstante (einseitige) Rauschleistungsdichte N0 des AWGN–Rauschens.

Bei einem (n, 1, n)–Wiederholungscode ergibt sich dagegen für den Eingangswert des ML–Decoders y ' = x̃ ' + η ' mit folgenden Eigenschaften:

\[\tilde{x} \hspace{0.04cm}' \hspace{-0.1cm} = \hspace{-0.1cm} \sum_{i=1 }^{n} \tilde{x}_i \in \{ +n, -n \}\hspace{0.2cm} \Rightarrow\hspace{0.2cm} n{\rm -fache \hspace{0.15cm}Amplitude} \hspace{0.2cm} \Rightarrow\hspace{0.2cm}n^2{\rm -fache \hspace{0.15cm}Leistung}\hspace{0.05cm},\] \[\eta\hspace{0.04cm}' \hspace{-0.1cm} = \hspace{-0.1cm} \sum_{i=1 }^{n} \eta_i\hspace{0.2cm} \Rightarrow\hspace{0.2cm} n{\rm -fache \hspace{0.15cm}Varianz:\hspace{0.15cm}} \sigma^2 \rightarrow n \cdot \sigma^2\hspace{0.05cm},\] \[\rho\hspace{0.04cm}' \hspace{-0.1cm} = \hspace{-0.1cm} \frac{n^2}{n \cdot \sigma^2} = n \cdot \rho \hspace{0.2cm} \Rightarrow\hspace{0.2cm}{\rm Pr}(v \ne u) = {\rm Q}(\sqrt{n \cdot \frac{2E_{\rm S}}{N_0}})\hspace{0.05cm}.\]

Die linke Grafik zeigt die Fehlerwahrscheinlichkeit in doppelt logarithmischer Darstellung. Als Abszisse ist 10 · lg (ES/N0) aufgetragen. Die Bildbeschreibung folgt auf der nächsten Seite.

Fehlerwahrscheinlichkeit des Wiederholungscodes beim AWGN–Kanal


Wiederholungscodes (3)


Es folgt nun die Interpretation der angegebenen Grafiken.

Fehlerwahrscheinlichkeit des Wiederholungscodes beim AWGN–Kanal

Die linke Grafik kann wie folgt interpretiert werden:

  • Trägt man die Fehlerwahrscheinlichkeit über der Abszisse 10 · lg (ES/N0) auf, so ergibt sich durch n–fache Wiederholung gegenüber uncodierter Übertragung (n = 1) eine signifikante Verbesserung.
  • Die Kurve für den Wiederholungsfaktor n erhält man durch Linksverschiebung um 10 · lg n (in dB) gegenüber der Vergleichskurve. Der Gewinn beträgt 4.77 dB (n = 3) bzw. ca. 7 dB (n = 5).
  • Allerdings ist ein Vergleich bei konstantem ES nicht fair, da man mit einem (5, 1) Repetition Code für die Übertragung eines Informationsbits eine um den Faktor n größere Energie aufwendet:
\[E_{\rm B} = \frac{E_{\rm S}}{R} = n \cdot E_{\rm S} \hspace{0.05cm}.\]

Aus der rechten Grafik erkennt man, dass alle Kurven genau übereinander liegen, wenn auf der Abszisse 10 · lg (EB/N0) aufgetragen wird. Daraus folgt:

Zusammenfassung der Ergebnisse für den Wiederholungscode bei AWGN

  • Die Fehlerwahrscheinlichkeit ist bei fairem Vergleich unabhängig vom Wiederholungsfaktor n:
\[{\rm Pr}(v \ne u) = {\rm Q}\left (\sqrt{\frac{2E_{\rm B}}{N_0}} \right ) \hspace{0.05cm}.\]
  • Beim AWGN–Kanal ist durch einen Wiederholungscode kein Codiergewinn zu erzielen.

Hamming–Codes (1)


Richard Wesley Hamming hat 1962 eine Klasse binärer Blockcodes angegeben, die sich durch die Anzahl m = 2, 3, ... der zugesetzten Parity Bits unterscheiden. Für diese Codeklasse gilt:

  • Die Codelänge ergibt sich zu n = 2m – 1. Möglich sind demzufolge beim Hamming–Code nur die Längen n = 3, n = 7, n = 15, n = 31, n = 63, n = 127, n = 255, usw.
  • Ein Informationswort besteht aus k = nm Bit. Die Coderate ist somit gleich
\[R = \frac{k}{n} = \frac{2^m - 1 - m}{2^m - 1} \in \{1/3, \hspace{0.1cm}4/7,\hspace{0.1cm}11/15,\hspace{0.1cm}26/31,\hspace{0.1cm}57/63, \hspace{0.1cm}120/127,\hspace{0.1cm}247/255, \hspace{0.05cm} ... \hspace{0.05cm} \}\hspace{0.05cm}.\]
  • Alle Hamming–Codes weisen die minimale Distanz dmin = 3 auf. Bei größerer Codelänge n erreicht man die minimale Distanz 3 schon mit weniger Redundanz, also bei größerer Coderate R.
  • Aus der Angabe dmin = 3 folgt weiter, dass hier e = dmin – 1 = 2 Fehler erkannt werden können und t = (dmin – 1)/2 = 1 Fehler korrigiert werden kann.
  • Der Hamming–Code (3, 1, 3) ist identisch mit dem Wiederholungscode (3, 1, 3):
\[\mathcal{C} = \{ (0, 0, 0) \hspace{0.05cm}, (1, 1, 1) \}\hspace{0.05cm}. \]
  • Bei systematischer Codierung sind die ersten k Stellen eines jeden Codewortes identisch mit dem Informationswort. Anschließend folgen bei einem Hamming–Code die m = nk Paritätsbit:
\[\underline{x} = ( x_1, x_2, ... \hspace{0.05cm}, x_n) = ( u_1, u_2, ... \hspace{0.05cm}, u_k, p_1, p_2, ... \hspace{0.05cm}, p_{n-k}) \hspace{0.05cm}.\]

Im Folgenden betrachten wir stets den (7, 4, 3)–Hamming–Code, der durch das folgende Schaubild verdeutlicht wird. Daraus lassen sich die drei Bedingungen ableiten:

Verdeutlichung des (7, 4, 3)–Hamming–Codes

\[x_1 \oplus x_2 \oplus x_3 \oplus x_5 \hspace{-0.1cm} = \hspace{-0.1cm} 0 \hspace{0.05cm},\] \[x_2 \oplus x_3 \oplus x_4 \oplus x_6 \hspace{-0.1cm} = \hspace{-0.1cm} 0 \hspace{0.05cm},\] \[x_1 \oplus x_2 \oplus x_4 \oplus x_7 \hspace{-0.1cm} = \hspace{-0.1cm} 0 \hspace{0.05cm}. \]

Im Schaubild kennzeichnet der rote Kreis die erste Prüfgleichung, der grüne die zweite und der blaue die letzte. In jedem Kreis muss die Anzahl der Einsen geradzahlig sein.




Hamming–Codes (2)


Systematischer (7, 4, 3)–Hamming–Code

Bei systematischer Codierung des (7, 4, 3)–Hamming–Codes

\[x_1 \hspace{-0.2cm} = \hspace{-0.2cm} u_1 ,\hspace{0.2cm} x_2 = u_2 ,\hspace{0.2cm} x_3 = u_3 ,\hspace{0.2cm} x_4 = u_4 ,\hspace{0.2cm}\] \[x_5 \hspace{-0.2cm} = \hspace{-0.2cm} p_1 ,\hspace{0.2cm} x_6 = p_2 ,\hspace{0.2cm} x_7 = p_3 \]

lauten die Bestimmungsgleichungen der drei Prüfbit, wie aus dem Schaubild rechts hervorgeht:

\[p_1 \hspace{-0.1cm} = \hspace{-0.1cm} u_1 \oplus u_2 \oplus u_3 \hspace{0.05cm},\] \[p_2 \hspace{-0.1cm} = \hspace{-0.1cm} u_2 \oplus u_3 \oplus u_4 \hspace{0.05cm},\] \[p_3 \hspace{-0.1cm} = \hspace{-0.1cm} u_1 \oplus u_2 \oplus u_4 \hspace{0.05cm}.\]


Die nachfolgende Tabelle zeigt die 2k = 16 zulässigen Codeworte x = (u1, u2, u3, u4, p1, p2, p3) des systematischen (7, 4, 3)–Codes. Das Informationswort u = (u1, u2, u3, u4) ist schwarz dargestellt und die Prüfbits p1, p2, p3 rot. Man erkennt anhand dieser Tabelle, dass sich jeweils zwei der 16 möglichen Codeworte in mindestens dmin = 3 Binärwerten unterscheiden.

Zuordnung ux des systematischen (7, 4, 3)–Hamming–Codes


Die Decodierung linearer Blockcodes wird im Kapitel 1.5 ausführlich behandelt. Das nun folgende Beispiel soll die Decodierung des Hamming–Codes eher intuitiv erklären.

: Wir gehen vom systematischen (7, 4, 3)–Code aus und betrachten das Empfangswort y = (y1y2y3y4y5y6y7). Zur Decodierung bilden wir die drei Paritätsgleichungen

\[ y_1 \oplus y_2 \oplus y_3 \oplus y_5 \hspace{-0.1cm}= \hspace{-0.1cm} 0 \hspace{0.05cm},\hspace{0.5cm}{\rm (I)} \] \[y_2 \oplus y_3 \oplus y_4 \oplus y_6 \hspace{-0.1cm}= \hspace{-0.1cm}0 \hspace{0.05cm},\hspace{0.5cm}{\rm (II)} \] \[y_1 \oplus y_2 \oplus y_4 \oplus y_7 \hspace{-0.1cm}= \hspace{-0.1cm} 0\hspace{0.05cm}. \hspace{0.5cm}{\rm (III)}\]

Unter der Voraussetzung, dass in jedem Codewort höchstens ein Bit verfälscht wird, gelten dann die folgenden Aussagen. υ bezeichnet das Decodierergebnis und sollte mit u = (1, 0, 1, 0) übereinstimmen:

  • Das Empfangswort y = (1, 0, 1, 0, 0, 1, 1) erfüllt alle drei Paritätsgleichungen. Das heißt, dass kein einziger Übertragungsfehler aufgetreten ist   ⇒   y = x  ⇒  u = (1, 0, 1, 0).
  • Werden zwei der drei Paritätsgleichungen erfüllt wie zum Beispiel für das empfangene Wort y = (1, 0, 1, 0, 0, 1, 0), so wurde ein Paritätsbit verfälscht und es gilt auch hier υ = (1, 0, 1, 0).
  • Mit y = (1, 0, 1, 1, 0, 1, 1) wird nur die Gleichung (I) erfüllt und die beiden anderen nicht. Somit kann man die Verfälschung des vierten Binärsymbols korrigieren, und es gilt auch hier υ = u.
  • Ein Übertragungsfehler des zweiten Bits   ⇒   y = (1, 1, 1, 0, 0, 1, 1) führt dazu, dass alle drei Paritätsgleichungen nicht erfüllt werden. Auch dieser Fehler lässt sich eindeutig korrigieren.


Aufgaben


A1.5 SPC (5, 4) und BEC–Modell

Zusatzaufgaben:1.5 SPC (5, 4) vs. RC (5, 1)

A1.6 Zum (7, 4)–Hamming–Code