Difference between revisions of "Channel Coding/The Basics of Product Codes"
From LNTwww
| Line 8: | Line 8: | ||
== Grundstruktur eines Produktcodes == | == Grundstruktur eines Produktcodes == | ||
<br> | <br> | ||
| − | Die Grafik zeigt den prinzipiellen Aufbau von Produktcodes, die bereits 1954 von Peter Elias eingeführt wurden. Der | + | Die Grafik zeigt den prinzipiellen Aufbau von Produktcodes, die bereits 1954 von [https://de.wikipedia.org/wiki/Peter_Elias Peter Elias] eingeführt wurden. |
| + | [[File:P ID3000 KC T 4 2 S1 v1.png|right|frame|Grundstruktur eines Produktcodes|class=fit]] | ||
| + | <br><br><br><br>Der hier dargestellte '''zweidimensionale Produktcode''' $\mathcal{C} = \mathcal{C}_1 × \mathcal{C}_2$ basiert auf den beiden linearen und binären Blockcodes mit den Parametern $(n_1, \ k_1)$ bzw. $(n_2, \ k_2)$. Die Codewortlänge ist $n = n_1 \cdot n_2$. | ||
| + | <br clear=all> | ||
| + | Diese $n$ Codebits lassen sich wie folgt gruppieren: | ||
| + | *Die $k = k_1 \cdot k_2$ Informationsbits sind in der $k_2 × k_1$–Matrix $\mathbf{U}$ angeordnet. Die Coderate ist gleich dem Produkt der Coderaten der beiden Basiscodes: | ||
| + | :$$R = k/n = (k_1/n_1) \cdot (k_2/n_2) = R_1 \cdot R_2.$$ | ||
| − | [[ | + | *Die rechte obere Matrix $\mathbf{P}^{(1)}$ mit der Dimension $k_2 × m_1$ beinhaltet die Prüfbits (englisch: <i>Parity</i>) hinsichtlich des Codes $\mathcal{C}_1$. In jeder der $k_2$ Zeilen werden zu den $k_1$ Informationsbits $m_1 = n_1 \, –k_1$ Prüfbits hinzugefügt, wie in einem Kapitel am Beispiel der [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes_.282.29|Hamming–Codes]] beschrieben wurde.<br> |
| − | + | *Die linke untere Matrix $\mathbf{P}^{(2)}$ der Dimension $m_2 × k_1$ beinhaltet die Prüfbits für den zweiten Komponentencodes $\mathcal{C}_2$. Hier erfolgt die Codierung (und auch die Decodierung) zeilenweise: In jeder der $k_1$ Spalten werden die $k_2$ Informationsbits noch um $m_2 = n_2 \, –k_2$ Prüfbits ergänzt.<br> | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | *Die linke untere Matrix $\mathbf{P}^{(2)}$ der Dimension $m_2 × k_1$ beinhaltet die Prüfbits | ||
*Die $m_2 × m_1$–Matrix $\mathbf{P}^{(12)}$ rechts unten bezeichnet man als <i>Checks–on–Checks</i>. Hier werden die vorher erzeugten Parity–Matrizen $\mathbf{P}^{(1)}$ und $\mathbf{P}^{(2)}$ entsprechend den Prüfgleichungen verknüpft.<br><br> | *Die $m_2 × m_1$–Matrix $\mathbf{P}^{(12)}$ rechts unten bezeichnet man als <i>Checks–on–Checks</i>. Hier werden die vorher erzeugten Parity–Matrizen $\mathbf{P}^{(1)}$ und $\mathbf{P}^{(2)}$ entsprechend den Prüfgleichungen verknüpft.<br><br> | ||
| − | Alle Produktcodes entsprechend obiger Grafik weisen folgende | + | {{BlaueBox|TEXT= |
| − | *Bei linearen Komponentencodes $ | + | $\text{Fazit:}$ Alle Produktcodes entsprechend obiger Grafik weisen folgende Eigenschaften auf: |
| + | *Bei linearen Komponentencodes $\mathcal{C}_1$ und $\mathcal{C}_2$ ist auch der Produktcode $\mathcal{C} = \mathcal{C}_1 × \mathcal{C}_2$ linear.<br> | ||
| − | *Jede Zeile von $C$ gibt ein Codewort von $ | + | *Jede Zeile von $\mathcal{C}$ gibt ein Codewort von $\mathcal{C}_1$ wieder und jede Spalte ein Codewort von $\mathcal{C}_2$.<br> |
| − | *Die Summe zweier Zeilen ergibt aufgrund der Linearität wieder ein Codewort von $ | + | *Die Summe zweier Zeilen ergibt aufgrund der Linearität wieder ein Codewort von $\mathcal{C}_1$.<br> |
| − | *Ebenso ergibt die Summe zweier Spalten ein gültiges Codewort von $ | + | *Ebenso ergibt die Summe zweier Spalten ein gültiges Codewort von $\mathcal{C}_2$.<br> |
*Jeder Produktcodes beinhaltet auch das Nullwort $\underline{0}$ (ein Vektor mit $n$ Nullen).<br> | *Jeder Produktcodes beinhaltet auch das Nullwort $\underline{0}$ (ein Vektor mit $n$ Nullen).<br> | ||
| − | *Die minimale Distanz von $C$ ist $d_{\rm min} = d_1 \cdot d_2$, wobei $d_i$ die minimale Distanz von $ | + | *Die minimale Distanz von $C$ ist $d_{\rm min} = d_1 \cdot d_2$, wobei $d_i$ die minimale Distanz von $\mathcal{C}_i$ angibt.}} |
| − | == Iterative Syndromdecodierung von Produktcodes | + | == Iterative Syndromdecodierung von Produktcodes == |
<br> | <br> | ||
Wir betrachten nun den Fall, dass ein Produktcode mit Matrix $\mathbf{X}$ über einen Binärkanal übertragen wird. Die Empfangsmatrix sei $\mathbf{Y} = \mathbf{X} + \mathbf{E}$, wobei $\mathbf{E}$ die Fehlermatrix bezeichnet. Alle Elemente der Matrizen $\mathbf{X}, \ \mathbf{E}$ und $\mathbf{Y}$ seien binär, also $0$ oder $1$.<br> | Wir betrachten nun den Fall, dass ein Produktcode mit Matrix $\mathbf{X}$ über einen Binärkanal übertragen wird. Die Empfangsmatrix sei $\mathbf{Y} = \mathbf{X} + \mathbf{E}$, wobei $\mathbf{E}$ die Fehlermatrix bezeichnet. Alle Elemente der Matrizen $\mathbf{X}, \ \mathbf{E}$ und $\mathbf{Y}$ seien binär, also $0$ oder $1$.<br> | ||
| − | Für die Decodierung der beiden Komponentencodes bietet sich die Syndromdecodierung entsprechend dem [[Kanalcodierung/Decodierung_linearer_Blockcodes#Blockschaltbild_und_Voraussetzungen| | + | Für die Decodierung der beiden Komponentencodes bietet sich die Syndromdecodierung entsprechend dem Kapitel [[Kanalcodierung/Decodierung_linearer_Blockcodes#Blockschaltbild_und_Voraussetzungen| Decodierung linearer Blockcodes]] an. Im zweidimensionalen Fall bedeutet dies: |
| − | *Man decodiert zunächst die $n_2$ Zeilen der Empfangsmatrix $\mathbf{Y}$, basierend auf der Prüfmatrix $\mathbf{H}_1$ des Komponentencodes $ | + | *Man decodiert zunächst die $n_2$ Zeilen der Empfangsmatrix $\mathbf{Y}$, basierend auf der Prüfmatrix $\mathbf{H}_1$ des Komponentencodes $\mathcal{C}_1$. Eine Möglichkeit ist die Syndromdecodierung.<br> |
| − | *Dazu bildet man jeweils das sogenannte Syndrom $\underline{s} = \underline{y} \cdot \mathbf{H}_1^{\rm T}$, wobei der Vektor $\underline{y}$ der Länge $n_1$ die aktuelle Zeile von $\mathbf{Y}$ angibt und „ | + | *Dazu bildet man jeweils das sogenannte Syndrom $\underline{s} = \underline{y} \cdot \mathbf{H}_1^{\rm T}$, wobei der Vektor $\underline{y}$ der Länge $n_1$ die aktuelle Zeile von $\mathbf{Y}$ angibt und „T” für „transponiert” steht.<br> |
| − | *Entsprechend dem berechneten $\underline{s}_{\mu}$ (mit $0 ≤ \mu < 2^{n_1 \, –k_1}$) findet man dann in einer vorbereiteten Syndromtabelle das wahrscheinliche Fehlermuster $\underline{e} = \underline{e}_{\mu}$ .<br> | + | *Entsprechend dem berechneten $\underline{s}_{\mu}$ (mit $0 ≤ \mu < 2^{n_1 \, –k_1}$) findet man dann in einer vorbereiteten Syndromtabelle das zugehörige wahrscheinliche Fehlermuster $\underline{e} = \underline{e}_{\mu}$ .<br> |
*Bei nur wenigen Fehlern innerhalb der Zeile stimmt dann $\underline{y} + \underline{e}$ mit dem gesendeten Zeilenvektor $\underline{x}$ überein. Sind zu viele Fehler aufgetreten, so kommt es allerdings zu Fehlkorrekturen.<br> | *Bei nur wenigen Fehlern innerhalb der Zeile stimmt dann $\underline{y} + \underline{e}$ mit dem gesendeten Zeilenvektor $\underline{x}$ überein. Sind zu viele Fehler aufgetreten, so kommt es allerdings zu Fehlkorrekturen.<br> | ||
| − | *Anschließend syndromdecodiert man die $n_1$ Spalten der (korrigierten) Empfangsmatrix $\mathbf{Y}'$, diesmal basierend auf der (transponierten) Prüfmatrix $\mathbf{H}_2^{\rm T}$ des Komponentencodes $ | + | *Anschließend syndromdecodiert man die $n_1$ Spalten der (korrigierten) Empfangsmatrix $\mathbf{Y}'$, diesmal basierend auf der (transponierten) Prüfmatrix $\mathbf{H}_2^{\rm T}$ des Komponentencodes $\mathcal{C}_2$.<br> |
*Hierzu bildet man das Syndrom $\underline{s} = \underline{y}' \cdot \mathbf{H}_2^{\rm T}$, wobei der Vektor $\underline{y}'$ der Länge $n_2$ die betrachtete Spalte von $\mathbf{Y}'$ bezeichnet.<br> | *Hierzu bildet man das Syndrom $\underline{s} = \underline{y}' \cdot \mathbf{H}_2^{\rm T}$, wobei der Vektor $\underline{y}'$ der Länge $n_2$ die betrachtete Spalte von $\mathbf{Y}'$ bezeichnet.<br> | ||
| − | *Aus einer zweiten Syndromtabelle (gültig für den Code $ | + | *Aus einer zweiten Syndromtabelle (gültig für den Code $\mathcal{C}_2$) findet man für das berechnete $\underline{s}_{\mu}$ (mit $0 ≤ \mu < 2^{n_2 \, –k_2}$) das wahrscheinliche Fehlermuster $\underline{e} = \underline{e}_{\mu}$ der bearbeiteten Spalte.<br> |
*Nach Korrektur aller Spalten liegt die Marix $\mathbf{Y}$ vor. Nun kann man wieder eine Zeilen– und anschließend eine Spaltendecodierung vornehmen ⇒ zweite Iteration, und so weiter, und so fort.<br><br> | *Nach Korrektur aller Spalten liegt die Marix $\mathbf{Y}$ vor. Nun kann man wieder eine Zeilen– und anschließend eine Spaltendecodierung vornehmen ⇒ zweite Iteration, und so weiter, und so fort.<br><br> | ||
| − | + | {{GraueBox|TEXT= | |
| − | *dem Hammingcode $(7, 4, 3)$ ⇒ Code $ | + | $\text{Beispiel 1:}$ Zur Verdeutlichung des Decodieralgorithmuses betrachten wir wieder den $(42, 12)$ Produktcode, basierend auf |
| + | *dem Hammingcode $(7, 4, 3)$ ⇒ Code $\mathcal{C}_1$,<br> | ||
| − | *dem verkürzten Hammingcode $(6, 3, 3)$ ⇒ Code $ | + | *dem verkürzten Hammingcode $(6, 3, 3)$ ⇒ Code $\mathcal{C}_2$.<br><br> |
Die Prüfmatrizen dieser beiden systematischen Komponentencodes lauten in transponierter Form: | Die Prüfmatrizen dieser beiden systematischen Komponentencodes lauten in transponierter Form: | ||
| − | :<math>{ \boldsymbol{\rm H}}_1^{\rm T} = | + | :<math>{ \boldsymbol{\rm H} }_1^{\rm T} = |
\begin{pmatrix} | \begin{pmatrix} | ||
1 &0 &1 \\ | 1 &0 &1 \\ | ||
| Line 72: | Line 75: | ||
0 &0 &1 | 0 &0 &1 | ||
\end{pmatrix} \hspace{0.05cm}, \hspace{0.5cm} | \end{pmatrix} \hspace{0.05cm}, \hspace{0.5cm} | ||
| − | { \boldsymbol{\rm H}}_2^{\rm T} = | + | { \boldsymbol{\rm H} }_2^{\rm T} = |
\begin{pmatrix} | \begin{pmatrix} | ||
1 &1 &0 \\ | 1 &1 &0 \\ | ||
| Line 82: | Line 85: | ||
\end{pmatrix}\hspace{0.05cm}.</math><br> | \end{pmatrix}\hspace{0.05cm}.</math><br> | ||
| − | + | ||
| − | + | ||
Die linke Grafik zeigt die Empfangsmatrix $\mathbf{Y}$, Aus Darstellungsgründen wurde die Codermatrix $\mathbf{X}$ zu einer $6 × 7$–Nullmatrix gewählt, so dass die neun Einsen in $\mathbf{Y}$ gleichzeitig Übertragungsfehler darstellen.<br> | Die linke Grafik zeigt die Empfangsmatrix $\mathbf{Y}$, Aus Darstellungsgründen wurde die Codermatrix $\mathbf{X}$ zu einer $6 × 7$–Nullmatrix gewählt, so dass die neun Einsen in $\mathbf{Y}$ gleichzeitig Übertragungsfehler darstellen.<br> | ||
| Line 135: | Line 138: | ||
Die verbliebenen drei Fehler werden durch zeilenweise Decodierung der <b>zweiten Iterationsschleife</b> korrigiert.<br> | Die verbliebenen drei Fehler werden durch zeilenweise Decodierung der <b>zweiten Iterationsschleife</b> korrigiert.<br> | ||
| − | Ob alle Fehler eines Blockes korrigierbar sind, hängt vom Fehlermuster ab. Hier verweisen wir auf Aufgabe A4.7.<br> | + | Ob alle Fehler eines Blockes korrigierbar sind, hängt vom Fehlermuster ab. Hier verweisen wir auf Aufgabe A4.7.}}<br> |
== Leistungsfähigkeit der Produktcodes == | == Leistungsfähigkeit der Produktcodes == | ||
Revision as of 11:06, 6 December 2017
Contents
Grundstruktur eines Produktcodes
Die Grafik zeigt den prinzipiellen Aufbau von Produktcodes, die bereits 1954 von Peter Elias eingeführt wurden.
Grundstruktur eines Produktcodes
Der hier dargestellte zweidimensionale Produktcode $\mathcal{C} = \mathcal{C}_1 × \mathcal{C}_2$ basiert auf den beiden linearen und binären Blockcodes mit den Parametern $(n_1, \ k_1)$ bzw. $(n_2, \ k_2)$. Die Codewortlänge ist $n = n_1 \cdot n_2$.
Diese $n$ Codebits lassen sich wie folgt gruppieren:
- Die $k = k_1 \cdot k_2$ Informationsbits sind in der $k_2 × k_1$–Matrix $\mathbf{U}$ angeordnet. Die Coderate ist gleich dem Produkt der Coderaten der beiden Basiscodes:
- $$R = k/n = (k_1/n_1) \cdot (k_2/n_2) = R_1 \cdot R_2.$$
- Die rechte obere Matrix $\mathbf{P}^{(1)}$ mit der Dimension $k_2 × m_1$ beinhaltet die Prüfbits (englisch: Parity) hinsichtlich des Codes $\mathcal{C}_1$. In jeder der $k_2$ Zeilen werden zu den $k_1$ Informationsbits $m_1 = n_1 \, –k_1$ Prüfbits hinzugefügt, wie in einem Kapitel am Beispiel der Hamming–Codes beschrieben wurde.
- Die linke untere Matrix $\mathbf{P}^{(2)}$ der Dimension $m_2 × k_1$ beinhaltet die Prüfbits für den zweiten Komponentencodes $\mathcal{C}_2$. Hier erfolgt die Codierung (und auch die Decodierung) zeilenweise: In jeder der $k_1$ Spalten werden die $k_2$ Informationsbits noch um $m_2 = n_2 \, –k_2$ Prüfbits ergänzt.
- Die $m_2 × m_1$–Matrix $\mathbf{P}^{(12)}$ rechts unten bezeichnet man als Checks–on–Checks. Hier werden die vorher erzeugten Parity–Matrizen $\mathbf{P}^{(1)}$ und $\mathbf{P}^{(2)}$ entsprechend den Prüfgleichungen verknüpft.
$\text{Fazit:}$ Alle Produktcodes entsprechend obiger Grafik weisen folgende Eigenschaften auf:
- Bei linearen Komponentencodes $\mathcal{C}_1$ und $\mathcal{C}_2$ ist auch der Produktcode $\mathcal{C} = \mathcal{C}_1 × \mathcal{C}_2$ linear.
- Jede Zeile von $\mathcal{C}$ gibt ein Codewort von $\mathcal{C}_1$ wieder und jede Spalte ein Codewort von $\mathcal{C}_2$.
- Die Summe zweier Zeilen ergibt aufgrund der Linearität wieder ein Codewort von $\mathcal{C}_1$.
- Ebenso ergibt die Summe zweier Spalten ein gültiges Codewort von $\mathcal{C}_2$.
- Jeder Produktcodes beinhaltet auch das Nullwort $\underline{0}$ (ein Vektor mit $n$ Nullen).
- Die minimale Distanz von $C$ ist $d_{\rm min} = d_1 \cdot d_2$, wobei $d_i$ die minimale Distanz von $\mathcal{C}_i$ angibt.
Iterative Syndromdecodierung von Produktcodes
Wir betrachten nun den Fall, dass ein Produktcode mit Matrix $\mathbf{X}$ über einen Binärkanal übertragen wird. Die Empfangsmatrix sei $\mathbf{Y} = \mathbf{X} + \mathbf{E}$, wobei $\mathbf{E}$ die Fehlermatrix bezeichnet. Alle Elemente der Matrizen $\mathbf{X}, \ \mathbf{E}$ und $\mathbf{Y}$ seien binär, also $0$ oder $1$.
Für die Decodierung der beiden Komponentencodes bietet sich die Syndromdecodierung entsprechend dem Kapitel Decodierung linearer Blockcodes an. Im zweidimensionalen Fall bedeutet dies:
- Man decodiert zunächst die $n_2$ Zeilen der Empfangsmatrix $\mathbf{Y}$, basierend auf der Prüfmatrix $\mathbf{H}_1$ des Komponentencodes $\mathcal{C}_1$. Eine Möglichkeit ist die Syndromdecodierung.
- Dazu bildet man jeweils das sogenannte Syndrom $\underline{s} = \underline{y} \cdot \mathbf{H}_1^{\rm T}$, wobei der Vektor $\underline{y}$ der Länge $n_1$ die aktuelle Zeile von $\mathbf{Y}$ angibt und „T” für „transponiert” steht.
- Entsprechend dem berechneten $\underline{s}_{\mu}$ (mit $0 ≤ \mu < 2^{n_1 \, –k_1}$) findet man dann in einer vorbereiteten Syndromtabelle das zugehörige wahrscheinliche Fehlermuster $\underline{e} = \underline{e}_{\mu}$ .
- Bei nur wenigen Fehlern innerhalb der Zeile stimmt dann $\underline{y} + \underline{e}$ mit dem gesendeten Zeilenvektor $\underline{x}$ überein. Sind zu viele Fehler aufgetreten, so kommt es allerdings zu Fehlkorrekturen.
- Anschließend syndromdecodiert man die $n_1$ Spalten der (korrigierten) Empfangsmatrix $\mathbf{Y}'$, diesmal basierend auf der (transponierten) Prüfmatrix $\mathbf{H}_2^{\rm T}$ des Komponentencodes $\mathcal{C}_2$.
- Hierzu bildet man das Syndrom $\underline{s} = \underline{y}' \cdot \mathbf{H}_2^{\rm T}$, wobei der Vektor $\underline{y}'$ der Länge $n_2$ die betrachtete Spalte von $\mathbf{Y}'$ bezeichnet.
- Aus einer zweiten Syndromtabelle (gültig für den Code $\mathcal{C}_2$) findet man für das berechnete $\underline{s}_{\mu}$ (mit $0 ≤ \mu < 2^{n_2 \, –k_2}$) das wahrscheinliche Fehlermuster $\underline{e} = \underline{e}_{\mu}$ der bearbeiteten Spalte.
- Nach Korrektur aller Spalten liegt die Marix $\mathbf{Y}$ vor. Nun kann man wieder eine Zeilen– und anschließend eine Spaltendecodierung vornehmen ⇒ zweite Iteration, und so weiter, und so fort.
$\text{Beispiel 1:}$ Zur Verdeutlichung des Decodieralgorithmuses betrachten wir wieder den $(42, 12)$ Produktcode, basierend auf
- dem Hammingcode $(7, 4, 3)$ ⇒ Code $\mathcal{C}_1$,
- dem verkürzten Hammingcode $(6, 3, 3)$ ⇒ Code $\mathcal{C}_2$.
Die Prüfmatrizen dieser beiden systematischen Komponentencodes lauten in transponierter Form:
\[{ \boldsymbol{\rm H} }_1^{\rm T} =
\begin{pmatrix}
1 &0 &1 \\
1 &1 &0 \\
0 &1 &1 \\
1 &1 &1 \\
1 &0 &0 \\
0 &1 &0 \\
0 &0 &1
\end{pmatrix} \hspace{0.05cm}, \hspace{0.5cm}
{ \boldsymbol{\rm H} }_2^{\rm T} =
\begin{pmatrix}
1 &1 &0 \\
1 &0 &1 \\
0 &1 &1 \\
1 &0 &0 \\
0 &1 &0 \\
0 &0 &1
\end{pmatrix}\hspace{0.05cm}.\]
Die linke Grafik zeigt die Empfangsmatrix $\mathbf{Y}$, Aus Darstellungsgründen wurde die Codermatrix $\mathbf{X}$ zu einer $6 × 7$–Nullmatrix gewählt, so dass die neun Einsen in $\mathbf{Y}$ gleichzeitig Übertragungsfehler darstellen.
Zur Syndromdecodierung des $(42, 12)$–Produktcodes
Hinweis: Für die folgenden Berechnungen ist der Link zu den transponierten Prüfmatrizen nützlich.
Die zeilenweise Syndromdecodierung geschieht über das Syndrom $\underline{s} = \underline{y} \cdot \mathbf{H}_1^{\rm T}$. Im Einzelnen:
- Zeile 1 ⇒ Einzelfehlerkorrektur ist erfolgreich (ebenso in den Zeilen 3, 4 und 6):
Syndromtabelle für den Code $C_1$
- \[\underline{s} = \left ( 0, \hspace{0.02cm} 0, \hspace{0.02cm}1, \hspace{0.02cm}0, \hspace{0.02cm}0, \hspace{0.02cm}0, \hspace{0.02cm}0 \right ) \hspace{-0.03cm}\cdot \hspace{-0.03cm}{ \boldsymbol{\rm H <div style="clear:both;"> </div> </div>_1^{\rm T} \hspace{-0.05cm}= \left ( 0, \hspace{0.03cm} 1, \hspace{0.03cm}1 \right ) = \underline{s}_3\]
- \[\Rightarrow \hspace{0.3cm} \underline{y} + \underline{e}_3 = \left ( 0, \hspace{0.02cm} 0, \hspace{0.02cm}0, \hspace{0.02cm}0, \hspace{0.02cm}0, \hspace{0.02cm}0, \hspace{0.02cm}0 \right ) \hspace{0.05cm}.\]
- Zeile 2 ⇒ Fehlkorrektur bezüglich Bit 5:
- \[\underline{s} = \left ( 1, \hspace{0.02cm} 0, \hspace{0.02cm}0, \hspace{0.02cm}0, \hspace{0.02cm}0, \hspace{0.02cm}0, \hspace{0.02cm}1 \right ) \hspace{-0.03cm}\cdot \hspace{-0.03cm}{ \boldsymbol{\rm H}}_1^{\rm T} \hspace{-0.05cm}= \left ( 1, \hspace{0.03cm} 0, \hspace{0.03cm}0 \right ) = \underline{s}_4\]
- \[\Rightarrow \hspace{0.3cm} \underline{y} + \underline{e}_4 = \left ( 1, \hspace{0.02cm} 0, \hspace{0.02cm}0, \hspace{0.02cm}0, \hspace{0.02cm}1, \hspace{0.02cm}0, \hspace{0.02cm}1 \right ) \hspace{0.05cm}.\]
- Zeile 5 ⇒ Fehlkorrektur bezüglich Bit 3:
- \[\underline{s} = \left ( 0, \hspace{0.02cm} 0, \hspace{0.02cm}0, \hspace{0.02cm}1, \hspace{0.02cm}1, \hspace{0.02cm}0, \hspace{0.02cm}0 \right ) \hspace{-0.03cm}\cdot \hspace{-0.03cm}{ \boldsymbol{\rm H}}_1^{\rm T} \hspace{-0.05cm}= \left ( 0, \hspace{0.03cm} 1, \hspace{0.03cm}1 \right ) = \underline{s}_3\]
- \[\Rightarrow \hspace{0.3cm} \underline{y} + \underline{e}_3 = \left ( 0, \hspace{0.02cm} 0, \hspace{0.02cm}1, \hspace{0.02cm}1, \hspace{0.02cm}1, \hspace{0.02cm}0, \hspace{0.02cm}0 \right ) \hspace{0.05cm}.\]
Die spaltenweisen Syndromdecodierung entfernt alle Einzelfehler in den Spalten 1, 2, 3, 4, 6 und 7.
Syndromtabelle für den Code $C_2$
- Spalte 5 ⇒ Fehlkorrektur bezüglich Bit 4:
- \[\underline{s} = \left ( 0, \hspace{0.02cm} 1, \hspace{0.02cm}0, \hspace{0.02cm}0, \hspace{0.02cm}1, \hspace{0.02cm}0 \right ) \hspace{-0.03cm}\cdot \hspace{-0.03cm}{ \boldsymbol{\rm H}}_1^{\rm T} \hspace{-0.05cm}= \left ( 1, \hspace{0.03cm} 0, \hspace{0.03cm}0 \right ) = \underline{s}_4\]
- \[\Rightarrow \hspace{0.3cm} \underline{y} + \underline{e}_4 = \left ( 0, \hspace{0.02cm} 1, \hspace{0.02cm}0, \hspace{0.02cm}1, \hspace{0.02cm}1, \hspace{0.02cm}0 \right ) \hspace{0.05cm}.\]
Die verbliebenen drei Fehler werden durch zeilenweise Decodierung der zweiten Iterationsschleife korrigiert.
Ob alle Fehler eines Blockes korrigierbar sind, hängt vom Fehlermuster ab. Hier verweisen wir auf Aufgabe A4.7.}}
Leistungsfähigkeit der Produktcodes
Die 1954 eingeführten Produktcodes waren die ersten Codes, die auf rekursiven Konstruktionsregeln basierten und somit grundsätzlich für die iterative Decodierung geeignet waren. Der Erfinder Peter Elias hat sich diesbezüglich zwar nicht geäußert, aber in den letzten zwanzig Jahren hat dieser Aspekt und die gleichzeitige Verfügbarkeit schneller Prozessoren dazu beigetragen, dass inzwischen auch Produktcodes in realen Kommunikationssystemen eingesetzt werden, z. B. beim Fehlerschutz von Speichermedien und bei Glasfasersystemen mit sehr hoher Datenrate.
Meist verwendet man sehr lange Produktcodes (großes $n = n_1 \cdot n_2$) mit folgender Konsequenz:
- Aus Aufwandsgründen ist hier die Maximum–Likelihood–Decodierung auf Blockebene für die Komponentencodes $C_1$ und $C_2$ nicht anwendbar, auch nicht die Syndromdecodierung, die ja eine Realisierungsform der ML–Decodierung darstellt.
- Anwendbar ist dagegen auch bei großem $n$ die iterative symbolweise MAP–Decodierung, wie in Kapitel 4.1 beschrieben. Der Austausch von extrinsischer und Apriori–Information geschieht hier zwischen den beiden Komponentencodes. Genaueres hierüber findet man in [Liv15][1].
Bit–/Blockfehlerrate eines $(1024, 676)$–Produktcodes beim AWGN–Kanal
Die Grafik zeigt für einen $(1024, 676)$–Produktcode, basierend auf dem Extended Hammingcode ${\rm eHC} \ (32, 26)$ als Komponentencodes, die AWGN–Bitfehlerwahrscheinlichkeit (links) in Abhängigkeit der Iterationen $(I)$ sowie rechts die Fehlerwahrscheinlichkeit der Blöcke (bzw. Codeworte). Die Coderate beträgt $R = R_1 \cdot R_2 = 0.66$, womit sich die Shannon–Grenze zu $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) \approx 1 \ \rm dB$ ergibt.
Links erkennt man den Einfluss der Iterationen. Beim Übergang von $I = 1$ auf $I$ gewinnt man ca. $2 \ \rm dB$ (bei der Bitfehlerrate $10^{–5}$) und mit $I = 10$ ein weiteres $\rm dB$. Weitere Iterationen lohnen sich nicht.
Auch alle in Kapitel 1.6 genannten Schranken können hier angewendet werden, so auch die in der rechten Grafik gestrichelt eingezeichneten Truncated Union Bound:
\[{\rm Pr(Truncated\hspace{0.15cm}Union\hspace{0.15cm} Bound)}= W_{d_{\rm min}} \cdot {\rm Q} \left ( \sqrt{d_{\rm min} \cdot {2R \cdot E_{\rm B}}/{N_0}} \right ) \hspace{0.05cm}.\]
Die minimale Distanz beträgt $d_{\rm min} = d_1 \cdot d_2 = 4 \cdot 4 = 16$. Mit der Gewichtsfunktion des ${\rm eHC} \ (32, 26)$,
\[W_{\rm eHC(32,\hspace{0.08cm}26)}(X) = 1 + 1240 \cdot X^{4} + 27776 \cdot X^{6}+ 330460 \cdot X^{8} + ...\hspace{0.05cm} + X^{32},\]
erhält man für den Produktcode $W_{d, \ \rm min} = 1240^2 = 15376000$. Damit ist die obere Gleichung bestimmt.
Aufgaben
Zusatzaufgaben:Z4.6: Grundlagen der Produktcodes
Zusatzaufgaben:Z4.7: Syndromdecodierung – Prinzip
Quellenverzeichnis
- ↑ Liva, G.: Channels Codes for Iterative Decoding. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2015.
