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

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(35 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 6: Zeile 6:
 
}}
 
}}
  
== Single Parity–check Codes (1) ==
+
== 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</u><sub>2</sub>, ... , <i>u</i><sub>k</sub></i>) ein Prüfbit (englisch: <i>Parity</i>) <i>p</i> hinzu:
+
Der&nbsp; '''Single Parity&ndash;check Code'''&nbsp; $\rm (SPC)$&nbsp; fügt zu dem Informationsblock&nbsp; $\underline{u}= (u_1, u_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, u_k)$&nbsp; ein Prüfbit&nbsp; (englisch: &nbsp;"Parity")&nbsp; $p$&nbsp; hinzu:
 +
[[Datei:P ID2346 KC T 1 3 S1 v2.png|right|frame|Verschiedene&nbsp; "Single Parity–check Codes"&nbsp; $(n = k  + 1)$|class=fit]]
 +
:$$\underline{u} = (u_1, u_2,\hspace{0.05cm} \text{...}  \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}.$$
  
:<math>\underline{u} = (u_1, u_2,\hspace{0.05cm} ... \hspace{0.05cm} , u_k)  \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
+
Die Grafik zeigt drei Coder&ndash;Beispiele mit
\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)
+
*$|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| = 4 \ (k = 2)$,
 +
 
 +
*$|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| = 8 \ (k = 3)$,
 +
 
 +
*$|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| = 16 \ (k = 4)$.
 +
 
 +
 
 +
Dieser sehr einfache Code kann wie folgt charakterisiert werden:
 +
*Aus&nbsp; $n = k  + 1$&nbsp; folgt für die&nbsp; '''Coderate'''&nbsp; $R = k/n = (n-1)/n$&nbsp; und für die&nbsp; '''Redundanz'''&nbsp; $1-R = 1/n$.&nbsp; Für&nbsp; $k = 2$&nbsp; ergibt sich zum Beispiel die Coderate&nbsp; $2/3$&nbsp; und die relative Redundanz beträgt&nbsp; $33.3\%$.
 +
 
 +
*Das Prüfbit erhält man durch die&nbsp; '''Modulo&ndash;2&ndash;Addition'''.&nbsp; Darunter versteht man die Addition im&nbsp; [[Kanalcodierung/Einige_Grundlagen_der_Algebra#Definition_eines_Galoisfeldes|Galoisfeld]]&nbsp; zur Basis &nbsp;$2$ &nbsp; &#8658; &nbsp; $\rm GF(2)$,&nbsp; sodass&nbsp;  $1 \oplus 1 = 0$&nbsp; ergibt:
 +
 
 +
::<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&nbsp; $\underline{x}$&nbsp; eine gerade Anzahl von Einsen.&nbsp; Ausgedrückt mit&nbsp; $\oplus$&nbsp; bzw. in vereinfachter Schreibweise gemäß der zweiten Gleichung lautet diese Bedingung:
 +
::<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.5cm}
 +
\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}. </math>
 +
*Für&nbsp; $k = 2$ &nbsp; &#8658; &nbsp; $n = 3$&nbsp; ergeben sich die folgenden vier Codeworte,&nbsp; wobei das Prüfbit&nbsp; $p$&nbsp; 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}
 +
\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)\hspace{0.05cm}.</math>
 +
 +
*Dieser Code&nbsp; $\mathcal{C} = \big \{ (0, 0, 0), \ (0, 1, 1), \ (1, 0, 1), \ (1, 1, 0) \big \}$&nbsp; ist&nbsp; '''linear''',&nbsp; da die Summe zweier beliebiger Codeworte wieder ein gültiges Codewort ergibt,&nbsp; zum Beispiel
 +
:$$\underline{x}_1 \oplus \underline{x}_2 = \underline{x}_3.$$
  
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>
+
*Für beliebiges&nbsp; $k$ &nbsp; &#8658; &nbsp; $n = k+1$&nbsp; unterscheidet sich jedes Codewort von allen anderen an einer geraden Anzahl von Positionen.&nbsp; Die minimale Distanz des Codes ist also&nbsp;
 +
:$$d_{\rm min} = 2.$$
  
[[Datei:P ID2346 KC T 1 3 S1 v2.png|Single Parity–check Code (<i>n</i> = <i>k</i> + 1)|class=fit]]<br>
+
{{BlaueBox|TEXT= 
 +
$\text{Definition:}$&nbsp; Jeder&nbsp; $\text{Single Parity&ndash;check Code (SPC)}$&nbsp; lässt sich formal wie folgt beschreiben:
  
Dieser sehr einfache Code ist wie folgt charakterisiert:
+
::<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>
*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%.
 
  
*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:
+
*Mit der allgemeinen Codebezeichnung&nbsp; $(n, \ k, \ d_{\rm min})$&nbsp; lässt sich jeder&nbsp; "Single Parity&ndash;check Code"&nbsp; auch mit&nbsp; $\text{SPC }(n, \ n-1, \ 2)$&nbsp; benennen.  
 +
*Die obere Grafik zeigt somit den&nbsp; $\text{SPC (3, 2, 2)}$,&nbsp; den&nbsp; $\text{SPC (4, 3, 2)}$&nbsp; und den&nbsp; $\text{SPC (5, 4, 2)}$.}}<br>
  
::<math>p = u_1 \oplus u_2 \oplus ... \hspace{0.05cm} \oplus u_k
+
Der digitale Kanal ändert möglicherweise das Codewort&nbsp; $\underline{x}= (x_1, x_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, x_n)$&nbsp;  in das Empfangswort&nbsp; $\underline{y}= (y_1, y_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, y_n)$. Mit dem Fehlervektor&nbsp; $\underline{e}= (e_1, e_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, e_n)$&nbsp; gilt:
 +
:$$\underline{y}=  \underline{x} \oplus \underline{e}.$$
 +
 
 +
Zur Decodierung des Single Parity&ndash;check Codes  bildet man das so genannte&nbsp; '''Syndrom''':
 +
 
 +
::<math>s = y_1 \oplus y_2 \oplus \hspace{0.05cm}\text{...} \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}.</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:
+
Das Ergebnis&nbsp; $s=1$&nbsp; weist dann auf&nbsp; (mindestens)&nbsp; einen Bitfehler innerhalb des Codewortes hin,&nbsp; während&nbsp;  $s=0$&nbsp; wie folgt zu interpretieren ist:
 +
*Die Übertragung war fehlerfrei,&nbsp; oder:<br>
 +
*Die Anzahl der Bitfehler ist geradzahlig.<br><br>
 +
 
 +
{{GraueBox|TEXT= 
 +
$\text{Beispiel 1:}$&nbsp; Wir betrachten den&nbsp; $\text{SPC (4, 3, 2)}$&nbsp; und gehen davon aus,&nbsp; dass das Nullwort gesendet wurde.&nbsp; Die Tabelle zeigt alle Möglichkeiten,&nbsp; dass&nbsp; $f$&nbsp; Bit verfälscht werden und gibt das jeweilige Syndrom&nbsp; $s \in \{0, 1\}$&nbsp; an.
 +
[[Datei:P ID2382 KC T 1 3 S1c.png|right|frame|Mögliche Empfangswerte beim&nbsp; $\text{SPC (4, 3, 2)}$ |class=fit]]
 +
 
 +
Für das&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|BSC&ndash;Modell]]&nbsp; mit der Verfälschungswahrscheinlichkeit&nbsp; $\varepsilon = 1\%$&nbsp; ergeben sich dann  folgende Wahrscheinlichkeiten:
 +
*Das Informationswort wird richtig decodiert&nbsp; (blaue Hinterlegung):
 +
 
 +
::<math>{\rm Pr}(\underline{v} = \underline{u}) = {\rm Pr}(\underline{y} = \underline{x}) = (1 - \varepsilon)^n = 0.99^4 \approx 96\,\%\hspace{0.05cm}.</math>
 +
 
 +
*Der Decoder erkennt, dass Übertragungsfehler aufgetreten sind&nbsp; (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}$$
 +
:$$\Rightarrow \hspace{0.3cm} {\rm Pr}(s=1) \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&nbsp; (rote Hinterlegung):
 +
 
 +
::<math>{\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} =  1 - {\rm Pr}(\underline{v} = \underline{u}) - {\rm Pr}(s=1)\approx 0.1\,\%\hspace{0.05cm}.</math>
 +
 
 +
Wir verweisen hier auf das HTML5/JavaScript&ndash;Applet&nbsp; [[Applets:Binomial-_und_Poissonverteilung_(Applet)|"Binomial- und Poissonverteilung"]].&nbsp; Die hier gewonnenen Ergebnisse werden auch in&nbsp; [[Aufgaben:1.5_SPC_(5,_4)_und_BEC%E2%80%93Modell|Aufgabe 1.5]]&nbsp; diskutiert.}}<br>
 +
 
 +
{{GraueBox|TEXT= 
 +
$\text{Beispiel 2:}$&nbsp; Eine Fehlerkorrektur des Single Parity&ndash;check Codes ist beim BSC&ndash;Modell nicht möglich im Unterschied zum&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Erasure_Channel_.E2.80.93_BEC|BEC&ndash;Modell]].&nbsp;
 +
 
 +
Bei diesem werden Bitfehler ausgeschlossen.&nbsp; Ist nur ein Bit ausgelöscht&nbsp; $($englisch: &nbsp; "Erasure", &nbsp;$\rm E)$,&nbsp; so ist aufgrund der Tatsache&nbsp; &bdquo;die Anzahl der Einsen im Codewort ist gerade&rdquo;&nbsp;  auch eine Fehlerkorrektur möglich,&nbsp; zum Beispiel für den&nbsp; $\text{SPC (5, 4, 2)}$:
 +
 
 +
:<math>\underline{y} = (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},</math>
 +
:<math>\underline{y}=(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},</math>
 +
:<math>\underline{y} = (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}.</math>}}
 +
 
 +
 
 +
{{GraueBox|TEXT= 
 +
$\text{Beispiel 3:}$&nbsp; Auch beim&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang|AWGN&ndash;Kanal]]&nbsp; ist Fehlerkorrektur möglich,&nbsp; wenn man&nbsp; "Soft Decision"&nbsp; anwendet.&nbsp; Für das Folgende gehen wir von bipolarer Signalisierung aus:
 +
[[Datei:P ID2387 KC T 1 3 S1d v2.png|right|frame|Zur Verdeutlichung von &bdquo;Soft Decision&rdquo; bei AWGN|class=fit]]
 +
*$x=0$  &nbsp; &rArr; &nbsp; $\tilde{x}= +1$,&nbsp; sowie
 +
*$x=1$  &nbsp; &rArr; &nbsp; $\tilde{x}= -1$.<br>
 +
 +
 
 +
Die Grafik verdeutlicht den hier dargelegten Sachverhalt:
 +
*Beispielsweise lautet der Empfangsvektor&nbsp; (rote Punkte):
 +
 
 +
::<math>\underline{y} =  (+0.8, -1.2, -0.1, +0.5, -0.6)  \hspace{0.05cm}.</math>
 +
*Bei harter Entscheidung&nbsp; (Schwelle&nbsp; $G = 0$,&nbsp; nur die Vorzeichen werden ausgewertet)&nbsp; würde man zu folgendem binären Ergebnis kommen&nbsp; $($grüne Quadrate&nbsp; $Y_i = y_i/ \vert y_i \vert)$:
 +
::<math>\underline{Y} =  (+1, -1, -1, +1, -1)  \hspace{0.05cm}.</math>
 +
 
 +
*In Symbolschreibweise ergibt sich&nbsp; $(0, 1, 1, 0, 1)$,&nbsp; was kein gültiges&nbsp; $\text{SPC (5, 4, 2)}$&ndash;Codewort  ist &nbsp; &#8658; &nbsp;  Syndrom&nbsp; $s = 1$.&nbsp; Also müssen ein, drei oder fünf Bit verfälscht worden sein.<br>
 +
 
 +
*Die Wahrscheinlichkeit für drei oder fünf Bitfehler ist allerdings um Größenordnungen kleiner als diejenige für einen einzigen Fehler.&nbsp; Die Annahme&nbsp; &bdquo;ein Bitfehler&rdquo;&nbsp; ist deshalb nicht abwegig.<br>
 +
 
 +
*Da der Empfangswert&nbsp; $y_3$&nbsp; sehr nahe an der Schwelle&nbsp; $G = 0$&nbsp; liegt,&nbsp; geht man davon aus,&nbsp; dass genau dieses Bit verfälscht wurde.&nbsp; Damit fällt bei&nbsp; "Soft Decision"&nbsp; die Entscheidung für&nbsp; $\underline{z} = (0, 1, 0, 0, 1)$ &nbsp; &#8658; &nbsp; $\underline{v} = (0, 1, 0, 0)$.&nbsp; Die Blockfehlerwahrscheinlichkeit&nbsp; ${\rm Pr}(\underline{v}  \ne  \underline{u})$&nbsp; ist so am geringsten.}}<br><br>
 +
 
 +
== Wiederholungscodes==
 +
<br>
 +
{{BlaueBox|TEXT= 
 +
$\text{Definition:}$&nbsp; Ein&nbsp; $\text{Wiederholungscode}$&nbsp; (englisch: &nbsp; "Repetition Code", $\rm RC)$&nbsp; ist ein linearer binärer&nbsp; $(n, \, k)$&ndash;Blockcode der Form
 +
 
 +
::<math>\mathcal{C} = \big \{ \underline{x} \in {\rm GF}(2^n)\text{:} \ \ x_i = x_j \hspace{0.15cm}{\rm f\ddot{u}r \hspace{0.15cm}alle\hspace{0.25cm} } i, j = 1, \hspace{0.05cm} \text{...} \hspace{0.05cm}, n \big \}.</math>
 +
 
 +
*Der Codeparameter&nbsp; $n$&nbsp; bezeichnet die Codelänge. Unabhängig von&nbsp;  $n$&nbsp; gilt stets&nbsp; $k = 1$.
 +
 +
*Entsprechend existieren nur die zwei Codeworte&nbsp; $(0, 0, \hspace{0.05cm} \text{...} \hspace{0.05cm} , 0)$&nbsp; und&nbsp; $(1, 1, \hspace{0.05cm}\text{...}\hspace{0.05cm} , 1)$,&nbsp; die sich in&nbsp; $n$&nbsp; Binärstellen unterscheiden.
 +
 +
*Daraus folgt für die minimale Distanz&nbsp;  $d_{\rm min} = n$.}}<br>
 +
 
 +
[[Datei:P ID2347 KC T 1 3 S2 v2.png|right|frame|Verschiedene Wiederholungscodes ("Repetition Codes")|class=fit]]
 +
Die Grafik zeigt Wiederholungscodes für&nbsp; $n=3$,&nbsp;  $n=4$&nbsp; und&nbsp; $n=5$.&nbsp; Ein solcher Wiederholungscode weist folgende Eigenschaften auf:
 +
*Dieser&nbsp; $(n, \, 1, \, n)$&ndash;Blockcode besitzt die sehr kleine Coderate&nbsp; $R = 1/n$,&nbsp; ist also nur für die Übertragung bzw. Speicherung kleiner Dateien geeignet.
 +
 
 +
*Andererseits ist der Wiederholungscode sehr robust.
 +
 +
*Beim&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Erasure_Channel_.E2.80.93_BEC|BEC&ndash;Kanal]]&nbsp; ("Binary Erasure Channel")&nbsp; genügt ein richtig übertragenes Bit an beliebiger Position&nbsp; (alle anderen Bit können ausgelöscht sein),&nbsp; um das Informationswort richtig zu decodieren.<br>
 +
 
 +
 
 +
{{GraueBox|TEXT= 
 +
$\text{Beispiel 4: Decodierung und Fehlerwahrscheinlichkeiten beim BSC&ndash;Kanal}$
 +
<br>
 +
 
 +
Es gelte das&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|BSC&ndash;Modell]]&nbsp; mit&nbsp; $\varepsilon = 10\%$.&nbsp; Die Decodierung basiere auf dem Majoritätsprinzip.
 +
*Bei ungeradem&nbsp; $n$&nbsp; können&nbsp; $e=n-1$&nbsp; Bitfehler erkannt und&nbsp; $t=(n-1)/2$&nbsp; Bitfehler korrigiert werden.&nbsp; Damit ergibt sich für die Wahrscheinlichkeit der korrekten Decodierung der Informationsbits&nbsp; $u$:
 +
 
 +
::<math>{\rm Pr}(v = u) =  \sum_{f=0  }^{(n-1)/2} {n \choose f} \cdot \varepsilon^{f} \cdot (1 - \varepsilon)^{n-f} \hspace{0.05cm}.</math>
 +
 
 +
*Die nachfolgenden Zahlenwerte gelten für&nbsp; $n = 5$.&nbsp; Das heißt: &nbsp; Es sind&nbsp; $t = 2$&nbsp; Bitfehler korrigierbar:
 +
 
 +
::<math>{\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\,\%</math>
 +
::<math>\Rightarrow\hspace{0.3cm}{\rm Pr}(v \ne u) = 1-  {\rm Pr}(v = u) \approx 0.85\,\%\hspace{0.05cm}.</math>
 +
 
 +
*Bei geradem&nbsp; $n$&nbsp; können dagegen nur&nbsp; $t=n/2-1$&nbsp; Fehler korrigiert werden.&nbsp; Erhöht man&nbsp; $n$&nbsp; von&nbsp; $5$&nbsp; auf&nbsp; $6$, so sind weiterhin auch nur zwei Bitfehler innerhalb eines Codewortes korrigierbar. Einen dritten Bitfehler kann man zwar nicht korrigieren, aber zumindest erkennen:
 +
 
 +
::<math>{\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}. </math>
 +
 
 +
*Ein&nbsp; (unerkannter)&nbsp; Decodierfehler&nbsp; $(v \ne u)$&nbsp; ergibt sich erst,&nbsp; wenn innerhalb des 6 Bit&ndash;Wortes vier oder mehr Bit verfälscht wurden.&nbsp; Als Näherung unter der Annahme,&nbsp; dass fünf oder sechs Bitfehler sehr viel unwahrscheinlicher sind als vier,&nbsp; gilt:
 +
 
 +
::<math>{\rm Pr}(v \ne u)  \approx {6 \choose 4} \cdot \varepsilon^{4} \cdot (1 - \varepsilon)^{2}=
 +
0.122\,\%\hspace{0.05cm}.</math>
 +
 
 +
*Interessant ist, dass beim&nbsp; $\text{RC(6, 1, 6)}$&nbsp; die Wahrscheinlichkeit&nbsp; ${\rm Pr}(v = u)$&nbsp;  für eine mögliche und richtige Decodierung mit&nbsp; $98.42\%$&nbsp; kleiner ist als beim&nbsp; $\text{RC (5, 1, 5)}$. Für letzteren gilt:&nbsp; ${\rm Pr}(v = u) = 1 \approx 99.15\%.$}}<br>
 +
 
 +
{{GraueBox|TEXT= 
 +
$\text{Beispiel 5: Leistungsfähigkeit des Wiederholungscodes beim AWGN&ndash;Kanal}$
 +
<br>
 +
 
 +
Wir betrachten nun den&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang|AWGN&ndash;Kanal]].&nbsp; Bei uncodierter Übertragung&nbsp; $($oder dem Wiederholungscode mit&nbsp; $n=1)$ &nbsp; ist der Empfangswert&nbsp; $y = \tilde{x}+\eta$,&nbsp; wobei&nbsp; $\tilde{x} \in \{+1, -1\}$ das Informationsbit bei bipolarer Signalisierung bezeichnet und&nbsp; $\eta$&nbsp; den Rauschterm.&nbsp; Um Verwechslungen mit dem Codeparameter&nbsp; $n$&nbsp; zu vermeiden, haben wir das Rauschen umbenannt: &nbsp; $n &#8594; \eta$.<br>
  
::<math> x_1 \oplus x_2 \oplus ... \hspace{0.05cm} \oplus x_n = 0  
+
Für die Fehlerwahrscheinlichkeit gilt mit dem&nbsp; [[Stochastische_Signaltheorie/Gaußverteilte_Zufallsgrößen#.C3.9Cberschreitungswahrscheinlichkeit|komplementären Gaußschen Fehlerintegral]]&nbsp; ${\rm Q}(x)$
\hspace{0.05cm}, \hspace{0.5cm}{\rm oder:}\hspace{0.15cm}  
+
 
\sum_{i=1}^{n} \hspace{0.2cm} x_i = 0\hspace{0.05cm}
+
::<math>{\rm Pr}(v \ne u)  = {\rm Q}(\sqrt{\rho})
, \hspace{0.3cm} {\rm Addition\hspace{0.15cm} in \hspace{0.15cmGF(2)}
+
\hspace{0.05cm},</math>
\hspace{0.05cm}. </math>
+
 
 +
wobei folgende physikalische Größen zu verwenden sind:
 +
*Das Signal&ndash;zu&ndash;Rauschleistungsverhältnis&nbsp; $\rho= 1/\sigma^2 =  2 \cdot E_{\rm S}/N_0$,<br>
 +
 
 +
*die Energie&nbsp; $E_{\rm S}$&nbsp; pro Codesymbol &nbsp; &#8658; &nbsp; &bdquo;Symbolenergie&rdquo;,<br>
 +
 
 +
*die normierte Streuung&nbsp; $\sigma$&nbsp; des Rauschens, gültig für das bipolare Informationsbit&nbsp; $\tilde{x} \in \{+1, -1\}$,&nbsp; und<br>
 +
 
 +
*die konstante (einseitige) Rauschleistungsdichte&nbsp; $N_0$&nbsp; des AWGN&ndash;Rauschens.<br><br>
 +
 
 +
[[Datei:P ID2348 KC T 1 3 S2b v2.png|right|frame|Fehlerwahrscheinlichkeit des Wiederholungscodes beim AWGN–Kanal|class=fit]]
 +
 
 +
Bei einem&nbsp; $(n,\ 1,\ n)$&ndash;Wiederholungscode ergibt sich dagegen für den Eingangswert des Maximum&ndash;Likelihood&ndash;Decoders&nbsp; $y \hspace{0.04cm}' = \tilde{x} \hspace{0.04cm}'+\eta \hspace{0.04cm}'$&nbsp; mit folgenden Eigenschaften:
 +
 
 +
::<math>\tilde{x} \hspace{0.04cm}'  =\sum_{i=1  }^{n} \tilde{x}_i \in \{ +n, -n \}\hspace{0.2cm} \Rightarrow\hspace{0.2cm}
 +
n{\rm -fache \hspace{0.15cm}Amplitude}</math>
 +
::<math>\hspace{4.8cm} \Rightarrow\hspace{0.2cm}n^2{\rm -fache \hspace{0.15cm}Leistung}\hspace{0.05cm},</math>
 +
::<math>\eta\hspace{0.04cm}'  = \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},</math>
 +
::<math>\rho\hspace{0.04cm}'  = \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}.</math>
 +
 
 +
Die Fehlerwahrscheinlichkeit in doppelt logarithmischer Darstellung zeigt die linke Grafik.
 +
#Als Abszisse ist&nbsp; $10 \cdot \lg \, (E_{\rm S}/N_0)$&nbsp; aufgetragen.
 +
#Die Energie pro Bit&nbsp; $(E_{\rm B})$&nbsp; ist &nbsp;$n$&nbsp; mal größer als die Symbolenergie&nbsp; $(E_{\rm S})$,&nbsp; wie im Schaubild für &nbsp;$n=3$&nbsp; verdeutlicht.
 +
 
 +
 
 +
Diese Kurvenschar  kann wie folgt interpretiert werden:
 +
*Trägt man die Fehlerwahrscheinlichkeit über der Abszisse&nbsp; $10 \cdot \lg \, (E_{\rm S}/N_0)$&nbsp; auf,&nbsp; so ergibt sich durch&nbsp; $n$&ndash;fache Wiederholung  gegenüber uncodierter Übertragung&nbsp; $(n=1)$&nbsp; eine signifikante Verbesserung.<br>
 +
 
 +
*Die Kurve für den Wiederholungsfaktor&nbsp; $n$&nbsp; erhält man durch Linksverschiebung um&nbsp; $10 \cdot \lg \, n$&nbsp;  (in dB)&nbsp; gegenüber der Vergleichskurve.&nbsp; Der Gewinn beträgt&nbsp; $4.77 \ {\rm dB} \ (n = 3)$ bzw. $\approx 5 \ {\rm dB} \ (n = 5)$.<br>
 +
 
 +
*Allerdings ist ein Vergleich bei konstantem&nbsp; $E_{\rm S}$&nbsp; nicht fair,&nbsp; da man mit dem&nbsp; $\text{RC (5, 1, 5)}$&nbsp; für die Übertragung eines Informationsbits eine um den Faktor&nbsp; $n$&nbsp; größere Energie aufwendet als bei uncodierter Übertragung: &nbsp; $E_{\rm B}  = E_{\rm S}/{R} = n \cdot E_{\rm S}\hspace{0.05cm}.$
 +
 
 +
 
 +
Aus der rechten Grafik erkennt man,&nbsp; dass alle Kurven genau übereinander liegen,&nbsp; wenn auf der Abszisse&nbsp; $10 \cdot \lg \, (E_{\rm B}/N_0)$&nbsp; aufgetragen wird.}}<br>
 +
 
 +
{{BlaueBox|TEXT= 
 +
$\text{Fazit bezüglich Wiederholungscodes beim AWGN&ndash;Kanal:}$
 +
*Die Fehlerwahrscheinlichkeit ist bei fairem Vergleich unabhängig vom Wiederholungsfaktor&nbsp; $n$: &nbsp; &nbsp; ${\rm Pr}(v \ne u)  = {\rm Q}\left (\sqrt{2E_{\rm B} /{N_0} } \right )
 +
\hspace{0.05cm}.$
 +
 
 +
*Beim AWGN&ndash;Kanal ist durch einen Wiederholungscode kein&nbsp; [[Kanalcodierung/Decodierung_linearer_Blockcodes#Codiergewinn_.E2.80.93_Bitfehlerrate_bei_AWGN| Codiergewinn]]&nbsp; zu erzielen.}}<br>
 +
 
 +
== Hamming–Codes ==
 +
<br>
 +
[https://de.wikipedia.org/wiki/Richard_Hamming Richard Wesley Hamming]&nbsp; hat 1962 eine Klasse binärer Blockcodes angegeben,&nbsp; die sich durch die Anzahl&nbsp; $m = 2, 3, \text{...} $&nbsp; der zugesetzten&nbsp; "Parity Bits"&nbsp; unterscheiden.&nbsp; Für diese Codeklasse gilt:
 +
*Die Codelänge ergibt sich stets  zu&nbsp; $n = 2^m -1$.&nbsp; Möglich sind demzufolge beim Hamming&ndash;Code auch nur die Längen&nbsp; $n = 3$,&nbsp; $n = 7$,&nbsp; $n = 15$,&nbsp; $n = 31$,&nbsp; $n = 63$,&nbsp; $n = 127$,&nbsp; $n = 255$, usw.<br>
 +
 
 +
*Ein Informationswort besteht aus&nbsp; $k = n-m$&nbsp; Bit.&nbsp; Die Coderate ist somit gleich
 +
 
 +
::<math>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} \text{...} \hspace{0.05cm}
 +
\}\hspace{0.05cm}.</math>
 +
 
 +
*Alle Hamming&ndash;Codes haben die minimale Distanz&nbsp; $d_{\rm min} = 3.$&nbsp; Bei größerer Codelänge&nbsp; $n$&nbsp; erreicht man&nbsp; $d_{\rm min} = 3$&nbsp; schon mit weniger Redundanz,&nbsp; also bei größerer Coderate&nbsp; $R$.&nbsp; Aus&nbsp; $d_{\rm min} = 3$&nbsp; folgt weiter, dass hier&nbsp; $e = d_{\rm min} -1 =2$&nbsp; Fehler erkannt werden können und man&nbsp; $t = (d_{\rm min} -1)/2  = 1$&nbsp; Fehler korrigieren kann.<br>
 +
 
 +
*Der Hamming&ndash;Code&nbsp; $\text{HC (3, 1, 3)}$&nbsp; ist identisch mit dem Wiederholungscode&nbsp; $\text{RP (3, 1, 3)}$&nbsp; und lautet:&nbsp; $\mathcal{C} = \big \{ (0, 0, 0) \hspace{0.05cm}, (1, 1, 1)  \big \}\hspace{0.05cm}. $
 +
 
 +
*Bei systematischer Codierung sind die ersten&nbsp; $k$&nbsp; Stellen eines jeden Hamming&ndash;Codewortes&nbsp; $\underline{x}$&nbsp; identisch mit dem Informationswort&nbsp; $\underline{u}$.&nbsp; Anschließend folgen dann  die&nbsp; $m = n-k$&nbsp; Paritätsbit:
 +
 
 +
::<math>\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_1,\ p_2, \hspace{0.05cm}\text{...} \hspace{0.05cm},\ p_{n-k})
 +
  \hspace{0.05cm}.</math>
 +
 
 +
{{GraueBox|TEXT= 
 +
$\text{Beispiel 6:  Paritätsgleichungen des (7, 4, 3)-Hamming-Codes}$
 +
 
 +
Der&nbsp; $\text{(7, 4, 3)}$&ndash;Hamming&ndash;Code wird durch das dargestellte Schaubild verdeutlicht. Daraus kann man die drei Bedingungen ableiten:
 +
[[Datei:P ID2353 KC T 1 3 S3 v2.png|right|frame|Verdeutlichung des $\text{(7, 4, 3)}$–Hamming–Codes ]]
 +
::<math>x_1 \oplus x_2 \oplus x_3 \oplus x_5    = 0 \hspace{0.05cm},</math>
 +
::<math>x_2 \oplus x_3 \oplus x_4 \oplus x_6    = 0 \hspace{0.05cm},</math>
 +
::<math>x_1 \oplus x_2 \oplus x_4 \oplus x_7    = 0 \hspace{0.05cm}. </math>
 +
 
 +
*Im Schaubild kennzeichnet der rote Kreis die erste Prüfgleichung,&nbsp; der grüne die zweite und der blaue die letzte.
 +
 +
*In jedem Kreis muss die Anzahl der Einsen geradzahlig sein.
 +
 
 +
 
 +
[[Datei:P ID2351 KC T 1 3 S3c v2.png|right|frame|Zuordnung $\underline{u} → \underline{x}$ des systematischen $\text{(7, 4, 3)}$–Hamming–Codes|class=fit]]
 +
Bei systematischer Codierung des&nbsp; $\text{(7, 4, 3)}$&ndash;Hamming&ndash;Codes
 +
 
 +
::<math>x_1 = 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 = p_1 ,\hspace{0.2cm}
 +
x_6 = p_2 ,\hspace{0.2cm}
 +
x_7 = p_3 </math>
 +
 
 +
lauten die Bestimmungsgleichungen der drei Prüfbit, wie aus dem Schaubild hervorgeht:
 +
 
 +
::<math>p_1 =u_1 \oplus u_2 \oplus u_3  \hspace{0.05cm},</math>
 +
::<math>p_2 = u_2 \oplus u_3 \oplus u_4  \hspace{0.05cm},</math>
 +
::<math>p_3 = u_1 \oplus u_2 \oplus u_4 \hspace{0.05cm}.</math>
 +
 
 +
Die Tabelle zeigt die&nbsp; $2^k = 16$&nbsp; zulässigen Codeworte des systematischen&nbsp; $\text{(7, 4, 3)}$&ndash;Codes:
 +
:$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6, x_7) =  ( u_1, u_2, u_3, u_4, p_1, p_2, p_3).$$ 
 +
*Das Informationswort&nbsp; $\underline{u} =( u_1, u_2, u_3, u_4)$&nbsp; ist schwarz dargestellt und die Prüfbits&nbsp; $p_1$,&nbsp;  $p_2$&nbsp; und&nbsp; $p_3$&nbsp; rot.
 +
 +
*Man erkennt anhand dieser Tabelle, dass sich jeweils zwei der&nbsp; $16$&nbsp; möglichen Codeworte in mindestens&nbsp; $d_{\rm min} = 3$&nbsp;  Binärwerten unterscheiden.}}<br>
 +
 
 +
Später wird die&nbsp;  [[Kanalcodierung/Decodierung_linearer_Blockcodes|Decodierung linearer Blockcodes]]&nbsp; noch ausführlich behandelt.&nbsp; Das folgende Beispiel soll die Decodierung des Hamming&ndash;Codes eher intuitiv  erklären.<br>
 +
 
 +
{{GraueBox|TEXT= 
 +
$\text{Beispiel 7:  Paritätsgleichungen des (7, 4, 3)-Hamming-Codes}$
 +
<br>
 +
 
 +
Wir gehen weiter vom systematischen&nbsp; $\text{(7, 4, 3)}$&ndash;Code aus und betrachten das Empfangswort&nbsp; $\underline{y} = ( y_1,\ y_2,\ y_3,\ y_4,\ y_5,\ y_6,\ y_7)$.
 +
 
 +
Zur Decodierung bilden wir die drei Paritätsgleichungen
 +
 
 +
::<math> 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)} </math>
 +
::<math>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)} </math>
 +
::<math>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)}</math>
 +
 
 +
Im Folgenden bezeichnet&nbsp; $\underline{v}$&nbsp;  das Decodierergebnis;&nbsp;  dieses sollte stets mit&nbsp;  $\underline{u} = (1, 0, 1, 0)$&nbsp; übereinstimmen:
  
*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:
+
Unter der Voraussetzung,&nbsp; dass in jedem Codewort höchstens ein Bit verfälscht wird,&nbsp; gelten dann die folgenden Aussagen.&nbsp;
 +
*Das Empfangswort&nbsp; $\underline{y} = (1, 0, 1, 0, 0, 1, 1)$&nbsp; erfüllt alle drei Paritätsgleichungen.&nbsp; Das heißt,&nbsp; dass kein einziger Übertragungsfehler aufgetreten ist &nbsp; &#8658; &nbsp; $\underline{y} = \underline{x}$ &nbsp; &#8658; &nbsp; $\underline{v} = \underline{u} = (1, 0, 1, 0)$.<br>
  
::<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}
+
*Werden zwei der drei Paritätsgleichungen erfüllt wie zum Beispiel für das empfangene Wort&nbsp; $\underline{y} =(1, 0, 1, 0, 0, 1, 0)$,&nbsp; so wurde ein Paritätsbit verfälscht und es gilt auch hier&nbsp; $\underline{v} = \underline{u} = (1, 0, 1, 0)$.<br>
\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>
+
*Mit&nbsp; $\underline{y} = (1, 0, 1, 1, 0, 1, 1)$&nbsp; wird nur die Gleichung&nbsp; $\rm (I)$&nbsp; erfüllt und die beiden anderen nicht.&nbsp; Somit kann man die Verfälschung des vierten Binärsymbols korrigieren,&nbsp; und es gilt auch hier&nbsp; $\underline{v} = \underline{u} = (1, 0, 1, 0)$.<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>
+
*Ein Übertragungsfehler des zweiten Bits &nbsp; &#8658; &nbsp; $\underline{y} = (1, 1, 1, 0, 0, 1, 1)$&nbsp; führt dazu,&nbsp; dass alle drei Paritätsgleichungen nicht erfüllt werden.&nbsp; Auch dieser Fehler lässt sich eindeutig korrigieren,&nbsp; da nur&nbsp; $u_2$&nbsp; in allen Gleichungen vorkommt.}}<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).
+
== Aufgaben zum Kapitel ==
 +
<br>
 +
[[Aufgaben:1.5 SPC (5, 4) und BEC–Modell|Aufgabe 1.5: SPC (5, 4) und BEC–Modell]]
  
{{Definition}}''':''' Jeder Single Parity&ndash;check Code (SPC) lässt sich formal wie folgt beschreiben:
+
[[Aufgaben:1.5Z SPC (5, 4) vs. RC (5, 1)|Aufgabe 1.5Z: SPC (5, 4) vs. RC (5, 1)]]
  
:<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>
+
[[Aufgaben:1.6 Zum (7, 4)–Hamming–Code|Aufgabe 1.6: Zum (7, 4)–Hamming–Code]]
  
 
{{Display}}
 
{{Display}}

Aktuelle Version vom 15. Juni 2022, 14:55 Uhr

Single Parity–check Codes


Der  Single Parity–check Code  $\rm (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:

Verschiedene  "Single Parity–check Codes"  $(n = k + 1)$
$$\underline{u} = (u_1, u_2,\hspace{0.05cm} \text{...} \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}.$$

Die Grafik zeigt drei Coder–Beispiele mit

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


Dieser sehr einfache Code kann wie folgt charakterisiert werden:

  • 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$   ⇒   $\rm 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 gemäß 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.5cm} \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 das Prüfbit  $p$  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)\hspace{0.05cm}.\]
  • Dieser Code  $\mathcal{C} = \big \{ (0, 0, 0), \ (0, 1, 1), \ (1, 0, 1), \ (1, 1, 0) \big \}$  ist  linear,  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.  Die minimale Distanz des Codes ist also 
$$d_{\rm min} = 2.$$

$\text{Definition:}$  Jeder  $\text{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  $\text{SPC }(n, \ n-1, \ 2)$  benennen.
  • Die obere Grafik zeigt somit den  $\text{SPC (3, 2, 2)}$,  den  $\text{SPC (4, 3, 2)}$  und den  $\text{SPC (5, 4, 2)}$.


Der digitale Kanal ändert möglicherweise das Codewort  $\underline{x}= (x_1, x_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, x_n)$  in das Empfangswort  $\underline{y}= (y_1, y_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, y_n)$. Mit dem Fehlervektor  $\underline{e}= (e_1, e_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, e_n)$  gilt:

$$\underline{y}= \underline{x} \oplus \underline{e}.$$

Zur Decodierung des Single Parity–check Codes bildet man das so genannte  Syndrom:

\[s = y_1 \oplus y_2 \oplus \hspace{0.05cm}\text{...} \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.

$\text{Beispiel 1:}$  Wir betrachten den  $\text{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 \in \{0, 1\}$  an.

Mögliche Empfangswerte beim  $\text{SPC (4, 3, 2)}$

Für das  BSC–Modell  mit der Verfälschungswahrscheinlichkeit  $\varepsilon = 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}$$
$$\Rightarrow \hspace{0.3cm} {\rm Pr}(s=1) \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} = 1 - {\rm Pr}(\underline{v} = \underline{u}) - {\rm Pr}(s=1)\approx 0.1\,\%\hspace{0.05cm}.\]

Wir verweisen hier auf das HTML5/JavaScript–Applet  "Binomial- und Poissonverteilung".  Die hier gewonnenen Ergebnisse werden auch in  Aufgabe 1.5  diskutiert.


$\text{Beispiel 2:}$  Eine Fehlerkorrektur des Single Parity–check Codes ist beim BSC–Modell nicht möglich im Unterschied zum  BEC–Modell

Bei diesem werden Bitfehler ausgeschlossen.  Ist nur ein Bit ausgelöscht  $($englisch:   "Erasure",  $\rm E)$,  so ist aufgrund der Tatsache  „die Anzahl der Einsen im Codewort ist gerade”  auch eine Fehlerkorrektur möglich,  zum Beispiel für den  $\text{SPC (5, 4, 2)}$:

\[\underline{y} = (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}=(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} = (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}.\]


$\text{Beispiel 3:}$  Auch beim  AWGN–Kanal  ist Fehlerkorrektur möglich,  wenn man  "Soft Decision"  anwendet.  Für das Folgende gehen wir von bipolarer Signalisierung aus:

Zur Verdeutlichung von „Soft Decision” bei AWGN
  • $x=0$   ⇒   $\tilde{x}= +1$,  sowie
  • $x=1$   ⇒   $\tilde{x}= -1$.


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  $Y_i = y_i/ \vert y_i \vert)$:
\[\underline{Y} = (+1, -1, -1, +1, -1) \hspace{0.05cm}.\]
  • In Symbolschreibweise ergibt sich  $(0, 1, 1, 0, 1)$,  was kein gültiges  $\text{SPC (5, 4, 2)}$–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  $y_3$  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  $\underline{z} = (0, 1, 0, 0, 1)$   ⇒   $\underline{v} = (0, 1, 0, 0)$.  Die Blockfehlerwahrscheinlichkeit  ${\rm Pr}(\underline{v} \ne \underline{u})$  ist so am geringsten.



Wiederholungscodes


$\text{Definition:}$  Ein  $\text{Wiederholungscode}$  (englisch:   "Repetition Code", $\rm RC)$  ist ein linearer binärer  $(n, \, k)$–Blockcode der Form

\[\mathcal{C} = \big \{ \underline{x} \in {\rm GF}(2^n)\text{:} \ \ x_i = x_j \hspace{0.15cm}{\rm f\ddot{u}r \hspace{0.15cm}alle\hspace{0.25cm} } i, j = 1, \hspace{0.05cm} \text{...} \hspace{0.05cm}, n \big \}.\]
  • Der Codeparameter  $n$  bezeichnet die Codelänge. Unabhängig von  $n$  gilt stets  $k = 1$.
  • Entsprechend existieren nur die zwei Codeworte  $(0, 0, \hspace{0.05cm} \text{...} \hspace{0.05cm} , 0)$  und  $(1, 1, \hspace{0.05cm}\text{...}\hspace{0.05cm} , 1)$,  die sich in  $n$  Binärstellen unterscheiden.
  • Daraus folgt für die minimale Distanz  $d_{\rm min} = n$.


Verschiedene Wiederholungscodes ("Repetition Codes")

Die Grafik zeigt Wiederholungscodes für  $n=3$,  $n=4$  und  $n=5$.  Ein solcher Wiederholungscode weist folgende Eigenschaften auf:

  • Dieser  $(n, \, 1, \, n)$–Blockcode besitzt die sehr kleine Coderate  $R = 1/n$,  ist also nur für die Übertragung bzw. Speicherung kleiner Dateien geeignet.
  • Andererseits ist der Wiederholungscode sehr robust.
  • Beim  BEC–Kanal  ("Binary Erasure Channel")  genügt ein richtig übertragenes Bit an beliebiger Position  (alle anderen Bit können ausgelöscht sein),  um das Informationswort richtig zu decodieren.


$\text{Beispiel 4: Decodierung und Fehlerwahrscheinlichkeiten beim BSC–Kanal}$

Es gelte das  BSC–Modell  mit  $\varepsilon = 10\%$.  Die Decodierung basiere auf dem Majoritätsprinzip.

  • Bei ungeradem  $n$  können  $e=n-1$  Bitfehler 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  $t=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  $(v \ne 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  $\text{RC(6, 1, 6)}$  die Wahrscheinlichkeit  ${\rm Pr}(v = u)$  für eine mögliche und richtige Decodierung mit  $98.42\%$  kleiner ist als beim  $\text{RC (5, 1, 5)}$. Für letzteren gilt:  ${\rm Pr}(v = u) = 1 \approx 99.15\%.$


$\text{Beispiel 5: Leistungsfähigkeit des Wiederholungscodes beim AWGN–Kanal}$

Wir betrachten nun den  AWGN–Kanal.  Bei uncodierter Übertragung  $($oder dem Wiederholungscode mit  $n=1)$   ist der Empfangswert  $y = \tilde{x}+\eta$,  wobei  $\tilde{x} \in \{+1, -1\}$ das Informationsbit bei bipolarer Signalisierung bezeichnet und  $\eta$  den Rauschterm.  Um Verwechslungen mit dem Codeparameter  $n$  zu vermeiden, haben wir das Rauschen umbenannt:   $n → \eta$.

Für die Fehlerwahrscheinlichkeit gilt mit dem  komplementären Gaußschen Fehlerintegral  ${\rm 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  $\rho= 1/\sigma^2 = 2 \cdot E_{\rm S}/N_0$,
  • die Energie  $E_{\rm S}$  pro Codesymbol   ⇒   „Symbolenergie”,
  • die normierte Streuung  $\sigma$  des Rauschens, gültig für das bipolare Informationsbit  $\tilde{x} \in \{+1, -1\}$,  und
  • die konstante (einseitige) Rauschleistungsdichte  $N_0$  des AWGN–Rauschens.

Fehlerwahrscheinlichkeit des Wiederholungscodes beim AWGN–Kanal

Bei einem  $(n,\ 1,\ n)$–Wiederholungscode ergibt sich dagegen für den Eingangswert des Maximum–Likelihood–Decoders  $y \hspace{0.04cm}' = \tilde{x} \hspace{0.04cm}'+\eta \hspace{0.04cm}'$  mit folgenden Eigenschaften:

\[\tilde{x} \hspace{0.04cm}' =\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{4.8cm} \Rightarrow\hspace{0.2cm}n^2{\rm -fache \hspace{0.15cm}Leistung}\hspace{0.05cm},\]
\[\eta\hspace{0.04cm}' = \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}' = \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 Fehlerwahrscheinlichkeit in doppelt logarithmischer Darstellung zeigt die linke Grafik.

  1. Als Abszisse ist  $10 \cdot \lg \, (E_{\rm S}/N_0)$  aufgetragen.
  2. Die Energie pro Bit  $(E_{\rm B})$  ist  $n$  mal größer als die Symbolenergie  $(E_{\rm S})$,  wie im Schaubild für  $n=3$  verdeutlicht.


Diese Kurvenschar kann wie folgt interpretiert werden:

  • Trägt man die Fehlerwahrscheinlichkeit über der Abszisse  $10 \cdot \lg \, (E_{\rm S}/N_0)$  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 \cdot \lg \, n$  (in dB)  gegenüber der Vergleichskurve.  Der Gewinn beträgt  $4.77 \ {\rm dB} \ (n = 3)$ bzw. $\approx 5 \ {\rm dB} \ (n = 5)$.
  • Allerdings ist ein Vergleich bei konstantem  $E_{\rm S}$  nicht fair,  da man mit dem  $\text{RC (5, 1, 5)}$  für die Übertragung eines Informationsbits eine um den Faktor  $n$  größere Energie aufwendet als bei uncodierter Übertragung:   $E_{\rm B} = 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 \cdot \lg \, (E_{\rm B}/N_0)$  aufgetragen wird.


$\text{Fazit bezüglich Wiederholungscodes beim AWGN–Kanal:}$

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


Hamming–Codes


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

  • Die Codelänge ergibt sich stets zu  $n = 2^m -1$.  Möglich sind demzufolge beim Hamming–Code auch nur die Längen  $n = 3$,  $n = 7$,  $n = 15$,  $n = 31$,  $n = 63$,  $n = 127$,  $n = 255$, usw.
  • Ein Informationswort besteht aus  $k = n-m$  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} \text{...} \hspace{0.05cm} \}\hspace{0.05cm}.\]
  • Alle Hamming–Codes haben die minimale Distanz  $d_{\rm min} = 3.$  Bei größerer Codelänge  $n$  erreicht man  $d_{\rm min} = 3$  schon mit weniger Redundanz,  also bei größerer Coderate  $R$.  Aus  $d_{\rm min} = 3$  folgt weiter, dass hier  $e = d_{\rm min} -1 =2$  Fehler erkannt werden können und man  $t = (d_{\rm min} -1)/2 = 1$  Fehler korrigieren kann.
  • Der Hamming–Code  $\text{HC (3, 1, 3)}$  ist identisch mit dem Wiederholungscode  $\text{RP (3, 1, 3)}$  und lautet:  $\mathcal{C} = \big \{ (0, 0, 0) \hspace{0.05cm}, (1, 1, 1) \big \}\hspace{0.05cm}. $
  • Bei systematischer Codierung sind die ersten  $k$  Stellen eines jeden Hamming–Codewortes  $\underline{x}$  identisch mit dem Informationswort  $\underline{u}$.  Anschließend folgen dann die  $m = n-k$  Paritätsbit:
\[\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_1,\ p_2, \hspace{0.05cm}\text{...} \hspace{0.05cm},\ p_{n-k}) \hspace{0.05cm}.\]

$\text{Beispiel 6: Paritätsgleichungen des (7, 4, 3)-Hamming-Codes}$

Der  $\text{(7, 4, 3)}$–Hamming–Code wird durch das dargestellte Schaubild verdeutlicht. Daraus kann man die drei Bedingungen ableiten:

Verdeutlichung des $\text{(7, 4, 3)}$–Hamming–Codes
\[x_1 \oplus x_2 \oplus x_3 \oplus x_5 = 0 \hspace{0.05cm},\]
\[x_2 \oplus x_3 \oplus x_4 \oplus x_6 = 0 \hspace{0.05cm},\]
\[x_1 \oplus x_2 \oplus x_4 \oplus x_7 = 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.


Zuordnung $\underline{u} → \underline{x}$ des systematischen $\text{(7, 4, 3)}$–Hamming–Codes

Bei systematischer Codierung des  $\text{(7, 4, 3)}$–Hamming–Codes

\[x_1 = 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 = 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 hervorgeht:

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

Die Tabelle zeigt die  $2^k = 16$  zulässigen Codeworte des systematischen  $\text{(7, 4, 3)}$–Codes:

$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6, x_7) = ( u_1, u_2, u_3, u_4, p_1, p_2, p_3).$$
  • Das Informationswort  $\underline{u} =( u_1, u_2, u_3, u_4)$  ist schwarz dargestellt und die Prüfbits  $p_1$,  $p_2$  und  $p_3$  rot.
  • Man erkennt anhand dieser Tabelle, dass sich jeweils zwei der  $16$  möglichen Codeworte in mindestens  $d_{\rm min} = 3$  Binärwerten unterscheiden.


Später wird die  Decodierung linearer Blockcodes  noch ausführlich behandelt.  Das folgende Beispiel soll die Decodierung des Hamming–Codes eher intuitiv erklären.

$\text{Beispiel 7: Paritätsgleichungen des (7, 4, 3)-Hamming-Codes}$

Wir gehen weiter vom systematischen  $\text{(7, 4, 3)}$–Code aus und betrachten das Empfangswort  $\underline{y} = ( y_1,\ y_2,\ y_3,\ y_4,\ y_5,\ y_6,\ y_7)$.

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)}\]

Im Folgenden bezeichnet  $\underline{v}$  das Decodierergebnis;  dieses sollte stets mit  $\underline{u} = (1, 0, 1, 0)$  übereinstimmen:

Unter der Voraussetzung,  dass in jedem Codewort höchstens ein Bit verfälscht wird,  gelten dann die folgenden Aussagen. 

  • Das Empfangswort  $\underline{y} = (1, 0, 1, 0, 0, 1, 1)$  erfüllt alle drei Paritätsgleichungen.  Das heißt,  dass kein einziger Übertragungsfehler aufgetreten ist   ⇒   $\underline{y} = \underline{x}$   ⇒   $\underline{v} = \underline{u} = (1, 0, 1, 0)$.
  • Werden zwei der drei Paritätsgleichungen erfüllt wie zum Beispiel für das empfangene Wort  $\underline{y} =(1, 0, 1, 0, 0, 1, 0)$,  so wurde ein Paritätsbit verfälscht und es gilt auch hier  $\underline{v} = \underline{u} = (1, 0, 1, 0)$.
  • Mit  $\underline{y} = (1, 0, 1, 1, 0, 1, 1)$  wird nur die Gleichung  $\rm (I)$  erfüllt und die beiden anderen nicht.  Somit kann man die Verfälschung des vierten Binärsymbols korrigieren,  und es gilt auch hier  $\underline{v} = \underline{u} = (1, 0, 1, 0)$.
  • Ein Übertragungsfehler des zweiten Bits   ⇒   $\underline{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,  da nur  $u_2$  in allen Gleichungen vorkommt.


Aufgaben zum Kapitel


Aufgabe 1.5: SPC (5, 4) und BEC–Modell

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

Aufgabe 1.6: Zum (7, 4)–Hamming–Code