Aufgaben:Exercise 4.09: Recursive Systematic Convolutional Codes

• Return to book

State transition diagram of an RSC code

In the  "Exercise 4.8"  important properties of convolutional codes have already been derived from the state transition diagram, assuming a non-recursive filter structure.

Now a rate $1/2$ RSC code is treated in a similar manner. Here "RSC" stands for "Recursive Systematic Convolutional".

The transfer function matrix of an RSC convolutional code can be specified as follows:

$${\boldsymbol{\rm G}}(D) = \left [ 1\hspace{0.05cm},\hspace{0.3cm} G^{(2)}(D)/G^{(1)}(D) \right ] \hspace{0.05cm}.$$

Otherwise, exactly the same conditions apply here as in exercise 4.8. We refer again to the following theory pages:

1. "Systematic convolutional codes"
2. "Representation in the state transition diagram"
3. "Definition of the free distance"
4. "GF(2) description forms of a digital filter"
5. "Application of the D–transform to rate 1/n convolution encoders"
6. "Filter structure with fractional–rational transfer function"

In the state transition diagram, the state  $S_0$  is always assumed. Two arrows go from each state. The label is "$u_i \hspace{0.05cm}| \hspace{0.05cm} x_i^{(1)}x_i^{(2)}$". For a systematic code, this involves:

• The first code bit is identical to the information bit:   $\hspace{0.2cm} x_i^{(1)} = u_i ∈ \{0, \, 1\}$.
• The second code bit is the parity-check bit:   $\hspace{0.2cm} x_i^{(2)} = p_i ∈ \{0, \, 1\}$.

Hints:

• The exercise refers to the chapter  "Basics of Turbo Codes".
• Similar exercises can be found in chapters 3.1 through 3.3.

• The following vectorial quantities are used in the questions for this exercise:
  • the information sequence:  $\hspace{0.2cm} \underline{u} = (u_1, \, u_2, \text{...} \hspace{0.05cm} )$,
  • the parity-check sequence:  $\hspace{0.2cm} \underline{p} = (p_1, \, p_2, \text{...} \hspace{0.05cm})$,
  • the impulse response:  $\hspace{0.2cm} \underline{g} = (g_1, \, g_2, \text{...} \hspace{0.05cm} ); \hspace{0.2cm}$ this is equal to the parity sequence $\underline{p}$  for  $\underline{u} = (1, \, 0, \, 0, \text{...} \hspace{0.05cm} )$.

Questions

1

Wie lautet die Impulsantwort  $\underline{g}$ ?

	Es gilt  $\underline{g} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, 1, \text{...} \hspace{0.05cm})$.
	Es gilt  $\underline{g} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \text{...} \hspace{0.05cm})$.

2

Es gelte  $\underline{u} = (1, \, 1, \, 0, \, 1)$. Welche Aussagen gelten für die Paritysequenz  $\underline{p}$ ?

	Es gilt  $\underline{p} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \text{...} \hspace{0.05cm})$.
	Es gilt  $\underline{p} = (1, \, 0, \, 0, \, 0, \, 0, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \text{...} \hspace{0.05cm})$.
	Bei begrenzter Informationssequenz  $\underline{u}$  ist stets auch  $\underline{p}$  begrenzt.

3

Wie lautet die  $D$–Übertragungsfunktion  $G(D)$?

	Es gilt  $G(D) = 1 + D + D^2 + D^4 + D^5 + D^7 + D^8 + \text{...} \hspace{0.05cm}$
	Es gilt  $G(D) = (1 + D^2)/(1 + D + D^2)$.
	Es gilt  $G(D) = (1 + D + D^2)/(1 + D^2)$.

4

Nun gelte  $\underline{u} = (1, \, 1, \, 1)$. Welche Aussagen gelten für die Paritysequenz  $\underline{p}$?

	Es gilt  $\underline{p} = (1, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \text{...} \hspace{0.05cm})$.
	Es gilt  $\underline{p} = (1, \, 0, \, 0, \, 0, \, 0, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \text{...} \hspace{0.05cm})$.
	Bei unbegrenzter Impulsantwort  $\underline{g}$  ist stets auch  $\underline{p}$  unbegrenzt.

5

Wie groß ist die freie Distanz  $d_{\rm F}$  dieses RSC–Coders?

$d_{\rm F} \ = \ $

Musterlösung

Solution

(1)  Verfolgt man die Übergänge im Zustandsdiagramm für die Sequenz  $\underline{u} = (1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0)$  am Eingang, so erhält man den Weg

$$S_0 → S_1 → S_3 → S_2 → S_1 → S_3 → S_2 → S_1 → S_3 → \hspace{0.05cm}\text{...} \hspace{0.05cm}$$

• Bei jedem Übergang ist das erste Codesymbol $x_i^{(1)}$ gleich dem Informationsbit $u_i$ und das Codesymbol $x_i^{(2)}$ gibt das Paritybit $p_i$ an.
• Damit erhält man das Ergebnis entsprechend dem Lösungsvorschlag 1:

$$\underline{p}= (\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} 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}\text{...} \hspace{0.05cm}) = \underline{g}\hspace{0.05cm}.$$

• Bei einem jeden RSC–Code ist die Impulsantwort $\underline{g}$ unendlich lang und wird irgendwann periodisch, in diesem Beispiel mit der Periode  $P = 3$  und  "$0, \, 1, \, 1$".

Verdeutlichung von  $\underline{p} = (1, \, 1, \, 0, \, 1)^{\rm T} \cdot \mathbf{G}$

(2)  Die Grafik zeigt die Lösung dieser Aufgabe entsprechend der Gleichung  $\underline{p} = \underline{u}^{\rm T} \cdot \mathbf{G}$.

• Hierbei ist die Generatormatrix  $\mathbf{G}$  nach unten und rechts unendlich weit ausgedehnt.
• Richtig ist der Lösungsvorschlag 2.

(3)  Richtig sind die Lösungsvorschläge 1 und 2:

• Zwischen der Impulsantwort $\underline{g}$ und der $D$–Übertragungsfunktion $\mathbf{G}(D)$ besteht der Zusammenhang gemäß dem ersten Lösungsvorschlag:

$$\underline{g}= (\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}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}, ... ) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad G(D) = 1\hspace{-0.05cm}+\hspace{-0.05cm} D\hspace{-0.05cm} +\hspace{-0.05cm} D^2\hspace{-0.05cm} +\hspace{-0.05cm} D^4 \hspace{-0.05cm}+\hspace{-0.05cm} D^5 \hspace{-0.05cm}+\hspace{-0.05cm} D^7 \hspace{-0.05cm}+\hspace{-0.05cm} D^8 + \hspace{0.05cm} \text{...} \hspace{0.05cm}.$$

• Überprüfen wir nun den zweiten Vorschlag:

$$G(D) = \frac{1+ D^2}{1+ D + D^2} \hspace{0.3cm}\Rightarrow \hspace{0.3cm} G(D) \cdot [1+ D + D^2] = 1+ D^2 \hspace{0.05cm}.$$

• Die folgende Rechnung zeigt, dass diese Gleichung tatsächlich stimmt:

$$(1+ D+ D^2+ D^4 +D^5 + D^7 + D^8 + \hspace{0.05cm} \text{...}) \cdot (1+ D+ D^2 ) =$$

$$=1+ D+ D^2\hspace{1.05cm} +D^4 + D^5 \hspace{1.05cm} +D^7 + D^8 \hspace{1.05cm} + D^{10}+ \hspace{0.05cm} \text{...}$$

$$+ \hspace{0.8cm}D+ D^2+D^3 \hspace{1.05cm}+ D^5 + D^6 \hspace{1.05cm} +D^8 + D^9 \hspace{1.25cm} +\hspace{0.05cm} \text{...} $$

$$+ \hspace{1.63cm} D^2+D^3+ D^4 \hspace{1.05cm}+ D^6 +D^7 \hspace{1.05cm}+ D^9 + D^{10} \hspace{0.12cm}+ \hspace{0.05cm} \text{...}$$

$$=\underline{1\hspace{0.72 cm}+ D^2} \hspace{0.05cm}.$$

• Da aber die Gleichung (2) stimmt, muss die letzte Gleichung falsch sein.

(4)  Richtig ist nur der Lösungsvorschlag 1:

• Aus $\underline{u} = (1, \, 1, \, 1)$ folgt $U(D) = 1 + D + D^2$. Damit gilt auch:

$$P(D) = U(D) \cdot G(D) = (1+D+D^2) \cdot \frac{1+D^2}{1+D+D^2}= 1+D^2\hspace{0.3cm} \Rightarrow\hspace{0.3cm} \underline{p}= (\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} 0\hspace{0.05cm},\hspace{0.05cm}\text{...}\hspace{0.05cm})\hspace{0.05cm}. $$

• Wären die Größen  $u_i$  und  $g_i$  reellwertig, so würde die (diskrete) Faltung  $\underline{p} = \underline{u} * \underline{g}$  stets zu einer Verbreiterung führen   ⇒   $\underline{p}$  wäre in diesem Fall breiter als  $\underline{u}$  und auch breiter als  $\underline{g}$.
• Bei  $u_i ∈ {\rm GF}(2)$  und  $g_i ∈ {\rm GF}(2)$  kann es (muss es aber nicht) dagegen vorkommen, dass auch bei unbegrenztem  $\underline{u}$  oder bei unbegrenztem  $\underline{g}$  das Faltungsprodukt  $\underline{p} = \underline{u} * \underline{g}$  begrenzt ist.

Verdeutlichung von  $\underline{p} = (1, \, 1, \, 1, \, 0, \, ...)^{\rm T} \cdot \mathbf{G}$

• Das Ergebnis wird abschließend noch entsprechend der Gleichung $\underline{p} = \underline{u}^{\rm T} \cdot \mathbf{G}$ überprüft.

(5)  Nach ähnlicher Vorgehensweise wie in der Aufgabe A4.8, (4) erkennt man:

• Die freie Distanz wird auch hier durch den Pfad  $S_0 → S_0 → S_1 → S_2 → S_0 → S_0 → \hspace{0.05cm}\text{...}\hspace{0.05cm}$ bestimmt.
• Die zugehörige Codesequenz  $\underline{x}$  ist nun aber  " $00 \ 11 \ 10 \ 11 \ 00 \ ... $".
• Damit ergibt sich die freie Distanz zu  $d_{\rm F} \ \underline{= 5}$.
• Beim nichtrekursiven Code (Aufgabe 4.8) war dagegen die freie Distanz  $d_{\rm F} = 3$.