Kanalcodierung/Grundlagen der Faltungscodierung: Unterschied zwischen den Versionen
| Zeile 65: | Zeile 65: | ||
*Auch schon bei kleinen Werten für $k$ und $n$ überführt ein Faltungscoder eine ganze Sequenz von Informationsbits $(k' → ∞)$ in eine sehr lange Sequenz von Codebits $(n' = k'/R)$. Ein solcher Code bietet somit oft ebenfalls eine große Korrekturfähigkeit.<br> | *Auch schon bei kleinen Werten für $k$ und $n$ überführt ein Faltungscoder eine ganze Sequenz von Informationsbits $(k' → ∞)$ in eine sehr lange Sequenz von Codebits $(n' = k'/R)$. Ein solcher Code bietet somit oft ebenfalls eine große Korrekturfähigkeit.<br> | ||
| − | *Es gibt effiziente Faltungsdecoder ⇒ [[Kanalcodierung/Decodierung_von_Faltungscodes# | + | *Es gibt effiziente Faltungsdecoder ⇒ [[Kanalcodierung/Decodierung_von_Faltungscodes#Viterbi.E2.80.93Algorithmus.2C_basierend_auf_Korrelation_und_Metriken_.281.29| Viterbi–Algorithmus]] bzw. [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#BCJR.E2.80.93Decodierung:_Vorw.C3.A4rts.E2.80.93R.C3.BCckw.C3.A4rts.E2.80.93Algorithmus| BCJR–Algorithmus.]] Diese können <i>Soft–Decision–Input</i> (Zuverlässigkeitsinformationen über den Kanal) einfach verarbeiten und liefern auch <i>Soft–Decision–Output</i> (Zuverlässigkeitsinformation über das Decodierergebnis).<br> |
== Rate–1/2–Faltungscodierer (1) == | == Rate–1/2–Faltungscodierer (1) == | ||
Version vom 27. November 2017, 11:41 Uhr
Inhaltsverzeichnis
Voraussetzungen und Definitionen
Wir betrachten in diesem Kapitel eine unendlich lange binäre Informationssequenz $\underline{u}$ und unterteilen diese in Informationsblöcke $\underline{u}_i$ zu je $k \ {\rm Bit}$. Man kann diesen Sachverhalt wie folgt formalisieren:
\[\underline{\it u} = \left ( \underline{\it u}_1, \underline{\it u}_2, ... \hspace{0.1cm}, \underline{\it u}_i , ... \hspace{0.1cm}\right ) \hspace{0.3cm}{\rm mit}\hspace{0.3cm} \underline{\it u}_i = \left ( u_i^{(1)}, u_i^{(2)}, ... \hspace{0.1cm}, u_i^{(k)}\right )\hspace{0.05cm},\]
\[u_i^{(j)}\in {\rm GF(2)}\hspace{0.3cm}{\rm f\ddot{u}r} \hspace{0.3cm}1 \le j \le k \hspace{0.5cm}\Rightarrow \hspace{0.5cm} \underline{\it u}_i \in {\rm GF}(2^k)\hspace{0.05cm}.\]
Im Englischen bezeichnet man eine solche Sequenz ohne negative Indizes als semi–infinite.
\[\underline{\it x}_i = \left ( x_i^{(1)}, x_i^{(2)}, ... \hspace{0.1cm}, x_i^{(n)}\right )\in {\rm GF}(2^n)\hspace{0.05cm}.\]
Dieses ergibt sich entsprechend
- den $k$ Bit des aktuellen Informationsblockes $\underline{u}_i$, und
- den $m$ vorherigen Informationsblöcken $\underline{u}_{i–1}, \ ... \ \underline{u}_{i–m}$.
Die folgende Grafik verdeutlicht diesen Sachverhalt für die Parameter $k = 4, n = 7, m = 2$ und $i = 4$. Die $n = 7$ zum Zeitpunkt $i = 4$ erzeugten Codebits $x_4^{(1)}, \ ... \ , x_4^{(7)}$ können (direkt) von den $k \cdot (m+1) = 12$ rot markierten Informationsbits abhängen und werden durch Modulo–2–Additionen erzeugt.
Gelb eingezeichnet ist zudem ein $(n, k)$–Faltungscodierer. Zu beachten ist, dass sich der Vektor $\underline{u}_i$ und die Sequenz $\underline{u}^{(i)}$ grundlegend unterscheiden. Während $\underline{u}_i = (u_i^{(1)}, u_i^{(2)}, \ ... \ , u_i^{(k)})$ die $k$ zum Zeitpunkt $i$ parallel anliegenden Informationsbits zusammenfasst, bezeichnet $\underline{u}^i = (u_i^{(i)}$, $u_2^{(i)}, \ ...)$ die (horizontale) Sequenz am $i$–ten Eingang des Faltungscodierers. Für den Faltungscode gelten folgende Definitionen:
- Die Coderrate ergibt sich wie bei den Blockcodes zu $R = k/n$.
- Man bezeichnet $m$ als das Gedächtnis (englisch: Memory) des Codes und den Convolutional Code selbst mit ${\rm CC}(n, k, m)$.
- Daraus ergibt sich die Einflusslänge (englisch: Constraint Length) zu $\nu = m + 1$.
- Für $k > 1$ gibt man diese Parameter oft auch in Bit an: $m_{\rm Bit} = m \cdot k$ bzw. $\nu_{\rm Bit} = (m + 1) \cdot k$.
Gemeinsamkeiten und Unterschiede gegenüber Blockcodes
Aus der Definition auf der letzten Seite ist ersichtlich, dass ein binärer Faltungscode mit $m = 0$ (also ohne Gedächtnis) identisch wäre mit einem binären Blockcode wie in Kapitel 1 beschrieben. Wir schließen diesen Grenzfall aus und setzen deshalb für das Folgende stets voraus:
- Das Gedächtnis $m$ sei größer oder gleich $1$.
- Die Einflusslänge $\nu$ sei größer oder gleich $2$.
Gilt beispielsweise $x_4^{(1)} = u_4^{(1)}, \ x_4^{(2)} = u_4^{(2)}, \ x_4^{(3)} = u_4^{(3)}, \ x_4^{(4)} = u_4^{(4)}$ sowie
\[x_4^{(5)} = u_4^{(1)}+ u_4^{(2)}+u_4^{(3)}\hspace{0.05cm} ,\hspace{0.3cm} x_4^{(6)} = u_4^{(2)}+ u_4^{(3)}+u_4^{(4)}\hspace{0.05cm} ,\hspace{0.3cm} x_4^{(7)} = u_4^{(1)}+ u_4^{(2)}+u_4^{(4)}\hspace{0.05cm} ,\]
so handelt es sich um einen so genannten systematischen Hamming–Code $(7, 4, 3)$ entsprechend Kapitel 1.3. In der Grafik sind diese speziellen Abhängigkeiten für $x_4^{(1)}$ und $x_4^{(7)}$ rot eingezeichnet.
In gewisser Weise könnte man auch einen $(n, k)$–Faltungscode mit Gedächtnis $m ≥ 1$ als Blockcode interpretieren, dessen Codeparameter $n' >> n$ und $k' >> k$ allerdings sehr viel größere Werte annehmen müssten als die des vorliegenden Faltungscodes. Aufgrund der großen Unterschiede in der Beschreibung, in den Eigenschaften und insbesondere bei der Decodierung betrachten wir aber Faltungscodes in diesem Lerntutorial als etwas völlig Neues. Hierfür sprechen folgende Gründe:
- Ein Blockcodierer setzt Informationsworte der Länge $k \ \rm Bit$ blockweise in Codeworte mit $n \ \rm Bit$ um. Der Blockcode ist dabei um so leistungsfähiger, je größer seine Codewortlänge $n$ ist. Bei gegebener Coderate $R = k/n$ erfordert dies auch eine große Informationswortlänge $k$.
- Dagegen wird die Korrekturfähigkeit eines Faltungscodes im wesentlichen durch sein Gedächtnis $m$ bestimmt. Die Codeparameter $k$ und $n$ werden hier meist sehr klein gewählt $(1, \ 2, \ 3, \ ...)$. Von praktischer Bedeutung sind somit nur ganz wenige und zudem sehr einfache Faltungscodes.
- Auch schon bei kleinen Werten für $k$ und $n$ überführt ein Faltungscoder eine ganze Sequenz von Informationsbits $(k' → ∞)$ in eine sehr lange Sequenz von Codebits $(n' = k'/R)$. Ein solcher Code bietet somit oft ebenfalls eine große Korrekturfähigkeit.
- Es gibt effiziente Faltungsdecoder ⇒ Viterbi–Algorithmus bzw. BCJR–Algorithmus. Diese können Soft–Decision–Input (Zuverlässigkeitsinformationen über den Kanal) einfach verarbeiten und liefern auch Soft–Decision–Output (Zuverlässigkeitsinformation über das Decodierergebnis).
Rate–1/2–Faltungscodierer (1)
Die Grafik zeigt einen $(n = 2, \ k = 1)$–Faltungscodierer. Zum Taktzeitpunkt $i$ liegt das Informationsbit $u_i$ am Codereingang an und es wird ein 2–Bit–Codeblock $\underline{x}_i = (x_i^{(1)}, \ x_i^{(2)})$ ausgegeben.
Unter Berücksichtigung der (halb–unendlich) langen Informationssequenz $\underline{u}$ ergibt sich folgendes Modell:
Um aus einem einzigen Informationsbit $u_i$ zwei Codebits $x_i^{(1)}$ und $x_i^{(2)}$ generieren zu können, muss der Faltungscodierer mindestens ein Speicherelement beinhalten:
\[k = 1\hspace{0.05cm}, n = 2 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} m \ge 1 \hspace{0.05cm}.\]
Anmerkung: Die beiden Begriffe Faltungscodierer und Faltungscoder werden in unserem Lerntutorial synonym verwendet und können beliebig ausgetauscht werden. Beide Begriffe bezeichnen die konkrete Umsetzung einer Informationssequenz $\underline{u}$ in eine Codesequenz $\underline{x}$.
Die Begriffe Faltungscodierer und Faltungscode sollte man allerdings nicht verwechseln. Unter einem Faltungscode ${\rm CC}(k, \ n, \ m)$ ⇒ $R = k/n$ versteht man die Menge aller möglichen Codesequenzen $\underline{x}$, die mit diesem Code unter Berücksichtigung aller möglichen Informationssequenzen $\underline{u}$ (am Eingang) generiert werden kann. Es gibt verschiedene Faltungscodierer, die den gleichen Faltungscode realisieren.
[[Datei:P ID2595 KC T 3 1 S3c v1.png|center|frame|Faltungscodierer mit $k = 1, \ n = 2$, \ m = 1$ sowie Beispielsequenzen|class=fit]]<br> Es handelt sich hier um einen <i>systematischen</i> Faltungscodierer, gekennzeichnet durch $x_i^{(1)} = u_i$. Der zweite Ausgang liefert $x_i^{(2)} = u_i + u_{i–1}$. In der beispielhaften Ausgangssequenz nach <i>Multiplexing</i> sind alle $x_i^{(1)}$ rot und alle $x_i^{(2)}$ blau beschriftet.<div style="clear:both;"> </div> </div><br> =='"`UNIQ--h-3--QINU`"' Rate–1/2–Faltungscodierer (2) == <br> Nachfolgend sehen Sie links das Ersatzschaltbild eines $(n = 2, \ k = 1)$–Faltungscodierers, aber nun mit $m = 2$ Speicherelementen. Die beiden Informationsbits lauten: \[x_i^{(1)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{i} + u_{i-1}+ u_{i-2} \hspace{0.05cm},\] \[x_i^{(2)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{i} + u_{i-2} \hspace{0.05cm}.\] Wegen $x_i^{(1)} ≠ u_i$ handelt es sich hier nicht um einen systematischen Code.<br> [[Datei:P ID2596 KC T 3 1 S3d v1.png|center|frame|Faltungscoder $(k = 1, \ n = 2, \ m = 2)$ in zwei verschiedenen Darstellungen|class=fit]]<br> Rechts angegeben ist eine Realisierungsform dieses Coders. Man erkennt: *Die Informationssequenz $\underline{u}$ wird in einem Schieberegister der Länge $L = m + 1 = 3$ abgelegt.<br> *Zum Taktzeitpunkt $i$ beinhaltet das linke Speicherelement das aktuelle Informationsbit $u_i$, das zu den nächsten Taktzeitpunkten jeweils um eine Stelle nach rechts verschoben wird.<br> *Aus der Anzahl der gelben Quadrate ergibt sich wieder das Gedächtnis $m = 2$ des Coders.<br><br> Aus den beiden Darstellungen wird deutlich, dass $x_i^{(1)}$ und $x_i^{(2)}$ jeweils als der Ausgang eines Digitalen Filters über dem Galoisfeld GF(2) interpretiert werden kann, wobei beide Filter parallel mit der gleichen Eingangsfolge $\underline{u}$ arbeiten. Da sich (ganz allgemein) das Ausgangssignal eines Filters aus der [[Signaldarstellung/Faltungssatz_und_Faltungsoperation#Faltung_im_Zeitbereich| Faltung]] des Eingangssignals mit der Filterimpulsantwort ergibt, spricht man von <i>Faltungscodierung</i>.<br> =='"`UNIQ--h-4--QINU`"' Faltungscodierer mit k = 2 Eingängen == <br> Nun betrachten wir einen Faltungscodierer, der aus $k = 2$ Informationsbits $n = 3$ Codebits generiert. Die Informationssequenz $\underline{u}$ wird in Blöcke zu je zwei Bit aufgeteilt. Zum Taktzeitpunkt $i$ liegt am oberen Eingang das Bit $u_i^{(1)}$ an und am unteren Eingang $u_i^{(2)}$. Für die $n = 3$ Codebits zum Zeitpunkt $i$ gilt dann: [[Datei:P ID2598 KC T 3 1 S4 v1.png|right|frame|Faltungscodierer mit $k = 2$ und $n = 3$]] \[x_i^{(1)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{i}^{(1)} + u_{i-1}^{(1)}+ u_{i-1}^{(2)} \hspace{0.05cm},\] \[x_i^{(2)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{i}^{(2)} + u_{i-1}^{(1)} \hspace{0.05cm},\] \[x_i^{(3)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{i}^{(1)} + u_{i}^{(2)}+ u_{i-1}^{(1)} \hspace{0.05cm}.\] In der Grafik sind die Info–Bits $u_i^{(1)}$ und $u_i^{(2)}$ rot bzw. blau gekennzeichnet, und die vorherigen Info–Bits $u_{i–1}^{(1)}$ und $u_{i–1}^{(2)}$ grün bzw. braun. Anzumerken ist: *Das <b>Gedächtnis</b> $m$ ist gleich der maximalen Speicherzellenzahl in einem Zweig ⇒ hier $m = 1$. *Die <b>Einflusslänge</b> $\nu$ ist gleich der Summe aller Speicherelemente ⇒ hier $\nu = 2$.<br> *Alle Speicherelemente seien zu Beginn der Codierung (<i>Initialisierung</i>) auf Null gesetzt.<br><br> Der hiermit definierte Code ist die Menge aller möglichen Codesequenzen $\underline{x}$, die sich bei Eingabe aller möglichen Informationssequenzen $\underline{u}$ ergeben. Sowohl $\underline{u}$ als auch $\underline{x}$ seien dabei (zeitlich) unbegrenzt.<br> <div class="example">''':''' Die Informationssequenz sei $\underline{u} = (0, 1, 1, 0, 0, 0, 1, 1, \ ...)$. Daraus ergeben sich die beiden Teilsequenzen $\underline{u}^{(1)} = (0, 1, 0, 1, \ ...)$ und $\underline{u}^{(2)} = (1, 0, 0, 1, \ ...)$. Mit der Festlegung $u_0^{(1)} = u_0^{(2)} = 0$ folgt aus den obigen Gleichungen für die $n = 3$ Codebits: *im ersten Codierschritt $(i = 1)$: :\[x_1^{(1)} = u_{1}^{(1)} = 0 \hspace{0.05cm},\hspace{0.4cm} x_1^{(2)} = u_{1}^{(2)} = 1 \hspace{0.05cm},\hspace{0.4cm} x_1^{(3)} = u_{1}^{(1)} + u_{1}^{(2)} = 0+1 = 1 \hspace{0.05cm},\] *im zweiten Codierschritt $(i = 2)$: :\[x_2^{(1)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{2}^{(1)} + u_{1}^{(1)}+ u_{1}^{(2)} = 1 + 0 + 1 = 0\hspace{0.05cm},\hspace{0.4cm} x_2^{(2)} = u_{2}^{(2)} + u_{1}^{(1)} = 0+0 = 0\hspace{0.05cm},\] :\[x_2^{(3)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{2}^{(1)} + u_{2}^{(2)}+ u_{1}^{(1)} = 1 + 0+0 =1\hspace{0.05cm},\] *im dritten Codierschritt $(i = 3)$: :\[x_3^{(1)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{3}^{(1)} + u_{2}^{(1)}+ u_{2}^{(2)} = 0+1+0 = 1\hspace{0.05cm},\hspace{0.4cm} x_3^{(2)} = u_{3}^{(2)} + u_{2}^{(1)} = 0+1=1\hspace{0.05cm},\] :\[x_3^{(3)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{3}^{(1)} + u_{3}^{(2)}+ u_{2}^{(1)} = 0+0+1 =1\hspace{0.05cm},\] *und schließlich im vierten Codierschritt $(i = 4)$: :\[x_4^{(1)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{4}^{(1)} + u_{3}^{(1)}+ u_{3}^{(2)} = 1+0+0 = 1\hspace{0.05cm},\hspace{0.4cm} x_4^{(2)} = u_{4}^{(2)} + u_{3}^{(1)} = 1+0=1\hspace{0.05cm},\] :\[x_4^{(3)} \hspace{-0.15cm} = \hspace{-0.15cm} u_{4}^{(1)} + u_{4}^{(2)}+ u_{3}^{(1)} = 1+1+0 =0\hspace{0.05cm}.\] Damit lautet die Codesequenz nach dem Multiplexer: $\underline{x} = (0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, \ ...)$.
Aufgaben
A3.1 Analyse eines Faltungscoders
Zusatzaufgaben:3.1 Faltungscodes der Rate 1/2
