Exercise 3.3: Code Sequence Calculation via U(D) and G(D)

Betrachtete Generatormatrix

Nebenstehend ist für den betrachteten Faltungscode der linke obere Ausschnitt der Generatormatrix $\mathbf{G}$ dargestellt. Daraus sollen unter der Randbedingung $m ≤ 2$ die Teilmatrizen $\mathbf{G}_l$ extrahiert werden, womit dann die Übergangsfunktionsmatrix entsprechend folgender Gleichung zusammengestellt werden kann:

$${\boldsymbol{\rm G}}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \sum_{l = 0}^{m} {\boldsymbol{\rm G}}_l \cdot D\hspace{0.03cm}^l =$$

$$ \ = \ \hspace{-0.15cm} {\boldsymbol{\rm G}}_0 + {\boldsymbol{\rm G}}_1 \cdot D + ... \hspace{0.05cm}+ {\boldsymbol{\rm G}}_m \cdot D\hspace{0.03cm}^m \hspace{0.02cm}.$$

Gesucht werden die $n$ Codesequenzen $\underline{x}^{(1)}, \ \underline{x}^{(2)}, \ ... \ , \ \underline{x}^{(n)}$, wobei von der Informationssequenz

$$\underline{u} = (0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}, ... \hspace{0.05cm}) $$

auszugehen ist. Diese Sequenz ist dabei in $k$ Teilsequenzen $\underline{u}^{(1)}, \ \underline{u}^{(2)}, \ ... \ , \ \underline{u}^{(k)}$ aufzuspalten. Aus deren $D$–Transformierten

$${U}^{(1)}(D) \hspace{0.15cm}\bullet\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\circ\hspace{0.15cm} \underline{u}^{(1)},\hspace{0.25cm} ...\hspace{0.25cm},\hspace{0.05cm} {U}^{(k)}(D) \hspace{0.15cm}\bullet\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\circ\hspace{0.15cm} \underline{u}^{(k)} $$

wird dann der Vektor $\underline{U}(D) = (U^{(1)}(D), \ ... \ , \ U^{(k)}(D))$ gebildet. Dann gilt für den Codesequenzvektor in $D$–Darstellung:

$$\underline{X}(D) = \left (\hspace{0.05cm} {X}^{(1)}(D)\hspace{0.05cm}, \hspace{0.05cm} ... \hspace{0.12cm}, \hspace{0.05cm} {X}^{(k)}(D)\hspace{0.05cm}\right ) = \underline{U}(D) \cdot {\boldsymbol{\rm G}}(D)\hspace{0.05cm}.$$

Hinweise:

Die Aufgabe gehört zum Themengebiet des Kapitels Algebraische und polynomische Beschreibung.
Der hier zugrunde liegende Codierer ist identisch mit dem von Aufgabe A3.2.
Nachdem auch von der gleichen Informationssequenz $\underline{u}$ ausgegangen wird, muss sich hier die gleiche Codesequenz $\underline{x}$ ergeben wie in Aufgabe A3.2, siehe Musterlösung.
Die Lösungswege beider Aufgaben unterscheiden sich allerdings grundlegend.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

Musterlösung

Solution

(1) Die Generatormatrix eines Faltungscodes hat die allgemeine Form:

$${ \boldsymbol{\rm G}}=\begin{pmatrix} { \boldsymbol{\rm G}}_0 & { \boldsymbol{\rm G}}_1 & { \boldsymbol{\rm G}}_2 & \cdots & { \boldsymbol{\rm G}}_m & & & \\ & { \boldsymbol{\rm G}}_0 & { \boldsymbol{\rm G}}_1 & { \boldsymbol{\rm G}}_2 & \cdots & { \boldsymbol{\rm G}}_m & &\\ & & { \boldsymbol{\rm G}}_0 & { \boldsymbol{\rm G}}_1 & { \boldsymbol{\rm G}}_2 & \cdots & { \boldsymbol{\rm G}}_m &\\ & & & \ddots & \ddots & & & \ddots \end{pmatrix}\hspace{0.05cm}.$$

Aus der Grafik auf der Angabenseite lassen sich die $k × n$–Teilmatrizen ermitteln:

$${ \boldsymbol{\rm G}}_0=\begin{pmatrix} 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}\hspace{0.05cm},\hspace{0.2cm} { \boldsymbol{\rm G}}_1=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}\hspace{0.05cm},\hspace{0.2cm} { \boldsymbol{\rm G}}_2=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{pmatrix}\hspace{0.05cm}. $$

Die Codeparameter lauten somit: $\underline{n = 4}, \ \underline{k = 3}$ und $\underline{m = 2}$. Hinweis: Der dargestellte Teil von $\mathbf{G}$ hätte für $m > 2$ das gleiche Aussehen wie für $m = 2$. Deshalb war die Zusatzangabe $m ≤ 2$ erforderlich.

(2) Entsprechend dem Angabenblatt gilt

$${\boldsymbol{\rm G}}(D) = {\boldsymbol{\rm G}}_0 + {\boldsymbol{\rm G}}_1 \cdot D + {\boldsymbol{\rm G}}_2 \cdot D^2 = \begin{pmatrix} 1 & 1 & 0 & 1 \\ 0 & 1+D & 1+D & 1 \\ 0 & D & 1+D^2 & 1+D^2 \end{pmatrix}\hspace{0.05cm}.$$

Das bedeutet: Alle Lösungsvorschläge sind richtig.

(3) Nach Aufteilung der Informationssequenz

$$\underline{u} = (0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}, ... \hspace{0.05cm})$$

auf die drei Teilsequenzen $\underline{u}^{(1)}$, $\underline{u}^{(2)}$ und $\underline{u}^{(3)}$ und anschließender $D$–Transformation erhält man

$$\underline{u}^{(1)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad {U}^{(1)}(D) = D + D^2 \hspace{0.05cm},$$

$$\underline{u}^{(2)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad {U}^{(2)}(D) = 1+D \hspace{0.05cm},$$

$$\underline{u}^{(3)} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad {U}^{(3)}(D) = 1 + D^2 \hspace{0.05cm}.$$

Richtig ist demnach nur der Lösungsvorschlag 2.

(4) In der ersten Spalte von $\mathbf{G}(D)$ steht nur eine Eins in Zeile 1, die zwei anderen Matrixelemente sind $0$ ⇒ Es handelt sich um einen systematischen Code ⇒ $\underline{x}^{(1)} = \underline{u}^{(1)} = (0, \, 1, \, 1)$ ⇒ Lösungsvorschlag 1.

(5) Die $D$–Transformierte $X^{(2)}(D)$ ergibt sich als das Vektorprodukt aus der $D$–Transformierten der Informationssequenz ⇒ $\underline{U}(D) = (U^{(1)}(D), \, U^{(2)}(D), \, U^{(3)}(D))$ und der zweiten Spalte von $\mathbf{G}(D)$:

$$X^{(2)}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} ( D + D^2) \cdot 1 + ( 1+D) \cdot ( 1+D) +( 1+D^2) \cdot D\hspace{0.03cm}=$$

$$\ = \ \hspace{-0.15cm}D + D^2 +1 +D +D + D^2 +D + D^3 = 1+D^3 \hspace{0.05cm}.$$

Richtig ist also der Lösungsvorschlag 2, nämlich $\underline{x}^{(2)} = (1, \, 0, \, 0)$. Da wir uns nur für die drei ersten Bit interessieren, ist der Beitrag $D^3$ nicht relevant.

(6) Analog zur Teilaufgabe (5) erhält man hier:

$$X^{(3)}(D) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} ( D + D^2) \cdot 0 + ( 1+D) \cdot ( 1+D) +( 1+D^2) \cdot ( 1+D^2)=$$

$$\ = \ \hspace{-0.15cm}1 + D + D + D^2 +1 + D^2 + D^2 + D^4 = D^2 + D^4 \hspace{0.05cm}.$$

Daraus ergibt sich $\underline{x}^{(3)} = (0, \, 0, \, 1)$ ⇒ Lösungsvorschlag 3. Das gleiche Ergebnis erhält man auch für $\underline{x}^{(4)}$. Nach Zusammenfügen aller $n = 4$ Teilsequenzen erhält man

$$\underline{x} = (0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm}, \hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} ... \hspace{0.05cm})\hspace{0.05cm},$$

und damit (natürlich) das gleiche Ergebnis wie in der Aufgabe A3.2.

	Das $\mathbf{G}(D)$–Element in Zeile 1, Spalte 1 ist „$1$”.
	Das $\mathbf{G}(D)$–Element in Zeile 2, Spalte 2 ist „$1 + D$”.
	Das $\mathbf{G}(D)$–Element in Zeile 3, Spalte 3 ist „$1 + D^2$”.

	$\underline{x}^{(1)} = (0, \, 1, \, 1, \, ...)$,
	$\underline{x}^{(1)} = (1, \, 0, \, 0, \, ...)$,
	$\underline{x}^{(1)} = (0, \, 0, \, 1, \, ...)$.

	$\underline{x}^{(2)} = (0, \, 1, \, 1, \, ...)$,
	$\underline{x}^{(2)} = (1, \, 0, \, 0, \, ...)$,
	$\underline{x}^{(2)} = (0, \, 0, \, 1, \, ...)$.

	$\underline{x}^{(3)} = (0, \, 1, \, 1, \, ...)$,
	$\underline{x}^{(3)} = (1, \, 0, \, 0, \, ...)$,
	$\underline{x}^{(3)} = (0, \, 0, \, 1, \, ...)$.

	$U^{(1)}(D) = 1$,
	$U^{(2)}(D) = 1 + D$,
	$U^{(3)}(D) = D^2$.