Aufgaben:Exercise 4.10: Turbo Encoder for UMTS and LTE

• Return to book

Turbocoder for UMTS and LTE

The mobile communications standards  "UMTS"  and  "LTE"  each use a turbo code that is largely identical to the encoder described in the  "The Basics of Turbo Codes"  chapter.

• The  $1/n$ convolutional code is systematic, meaning that the code sequence  $\underline{x}$  includes the information sequence  $\underline{u}$  as a component.
• The parity-check sequences  $\underline{p}_1$  and  $\underline{p}_2$  are based on the same transfer function:

$$G_1(D) = G_2(D) = G(D).$$

• $\underline{p}_1$  and  $\underline{p}_2$  however, use different input sequences  $\underline{u}$  and  $\underline{u}_{\pi}$, respectively. Here,  ${\rm \Pi}$  marks the interleaver, for UMTS and LTE mostly a  $S$ random interleaver.

Given filter structure

The main difference compared to the description in the theory part results from a different transfer function  $G(D)$ given by the recursive filter structure drawn on the left.

Hints:

• The exercise belongs to the chapter  "Basics of Turbo Codes".
• Knowledge is expected about
  • the  "Algebraic and Polynomial Description of Convolutional Codes",
  • the  "Code Description with State and Trellis Diagram".
• For further guidance on how to do this, see the  "Exercise 4.8" and the  "Exercise 4.9".
• The information sequence  $\underline{u}$  is partially specified by its  $D$–transform for easier description in the subtasks. For example:

$$\underline{u}= (\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} 0\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} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm}\hspace{0.05cm} \text{...}\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad U(D) = D+ D^2\hspace{0.05cm},$$

$$\underline{u}= (\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}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} \text{...}\hspace{0.05cm}) \quad \circ\!\!-\!\!\!-^{\hspace{-0.25cm}D}\!\!\!-\!\!\bullet\quad U(D) = D+ D^8\hspace{0.05cm}.$$

Questions

1

What are the characteristics of the considered turbo code (memory  $m$,  influence length  $\nu$,  rate $R$)?

$ m \hspace{0.2cm} = \ $

$ \nu \hspace{0.3cm} = \ $

$R \hspace{0.2cm} = \ $

2

What are the (identical) transfer functions  $G_1(D) = G_2(D) = G(D)$?

	$G(D) = (1 + D + D^3)/(1 + D^2 + D^3)$.
	$G(D) = (1 + D^2 + D^3)/(1 + D + D^3)$.

3

What is the impulse response  $\underline{g}$ ?

	$\underline{g} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, 1, \hspace{0.05cm} \text{...}\hspace{0.05cm})$
	$\underline{g} = (1, \, 1, \, 1, \, 1, \, 0, \, 0, \, 1, \, 0, \, 1, \, 1, \, 1, \, 0, \, 0, \, 1, \, 0, \hspace{0.05cm} \text{...}\hspace{0.05cm})$.
	$\underline{g}$  continues to infinity.

4

Are there periodic components within the impulse response  $\underline{g}$ ?

	Yes, with the period  $P = 7$.
	Yes, with the period  $P = 8$.
	No.

5

Let $U(D) = D + D^2$. Which statements are true?

	The initial sequence  $\underline{p}$  contains a periodic component.
	The period  $P$  is unchanged from  $\underline{g}$ .
	The Hamming weight of the input sequence is  $w_{\rm H}(\underline{u}) = 2$.
	The Hamming weight of the output sequence is  $w_{\rm H}(\underline{p}) = 6$.

6

Which statements are true for  $U(D) = D + D^8$ ?

	The initial sequence  $\underline{p}$  contains a periodic component.
	The period  $P$  is unchanged from  $\underline{g}$ .
	The Hamming weight of the input sequence is  $w_{\rm H}(\underline{u}) = 2$.
	The Hamming weight of the output sequence  is $w_{\rm H}(\underline{p}) = 6$.

Solution

Solution

Polynomial division for subtask (3)': $G(D) = (1 + D + D^3) \ / \ (1 + D^2 + D^3)$

(1)  The code parameters are $k = 1$ and $n = 3$   ⇒   Code rate $\underline{R = 1/3}$.

• The memory is $\underline{m = 3}$.
• The influence lengths result in $\nu = 1, \ \nu_2 = 4$ and $\nu_3 = 4$  ⇒  Total influence length $\underline{\nu = 9}$.

(2)  As the comparison of the "recursive filter" on the data page with the "filter structure" in the theory section for fractional–rational $G(D)$, the suggested solution 1 is correct.

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

Die obere Grafik verdeutlicht die Polynomdivision $(1 + D + D^3) \ / \ (1 + D^2 + D^3)$. Zur Erläuterung:

• Abgebrochen ist die Darstellung mit dem Rest $D^8 + D^9 = D^7 \cdot (D + D^2)$.
• Damit gilt auch:

$$(D^8 + D^9) \hspace{0.05cm} /\hspace{0.05cm} (1+ D^2+ D^3 ) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} D^7 \cdot (D+ D^2+ D^3 + D^6) + {\rm Rest_2}$$

• Nach Zusammenfassen:

$$G(D) = 1 + D + D^2 + D^3 + D^6 + D^8+ D^9+ D^{10} + D^{13} + \hspace{0.05cm}\text{ ... }\hspace{0.05cm} \hspace{0.05cm}. $$

• Die $D$–Rücktransformierte ergibt den Lösungsvorschlag 2:

$$\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} 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} 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} 0\hspace{0.05cm}, \hspace{0.05cm} 1\hspace{0.05cm}, \hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm}\text{ ... }\hspace{0.05cm})\hspace{0.05cm}. $$

• Die Impulsantwort setzt sich bis ins Unendliche fort   ⇒   Lösungsvorschlag 3 ist ebenfalls richtig.

Zustandsübergangsdiagramm und Impulsantwort

(4)  Die Impulsantwort kann wie folgt ausgedrückt werden:

$$\underline{g}= \Big (\hspace{0.03cm}1\hspace{0.03cm}, \big [ \hspace{0.03cm} 1\hspace{0.03cm}, \hspace{0.03cm} 1\hspace{0.03cm}, \hspace{0.03cm} 1\hspace{0.03cm}, \hspace{0.03cm} 0\hspace{0.03cm}, \hspace{0.03cm} 0\hspace{0.03cm}, \hspace{0.03cm} 1\hspace{0.03cm}, \hspace{0.03cm} 0\hspace{0.03cm} \big ]_{\rm per} \Big ) \hspace{0.15cm}\Rightarrow \hspace{0.15cm} \underline{P = 7} \hspace{0.05cm}. $$

Im Zustandsübergangsdiagramm (rechts) ist die Impulsantwort $\underline{g}$ gelb hinterlegt. Die Impulsantwort ergibt sich als die Paritysequenz  $\underline{p}$  für die Informationssequenz  $\underline{u} = (1, \, 0, \, 0, \, 0, \, 0, \, \text{ ... })$.

• Die Übergänge im Diagramm sind mit "$u_i\hspace{0.05cm}|\hspace{0.05cm}\underline{x}_i$" beschriftet, was gleichbedeutend ist mit "$u_i\hspace{0.05cm}|\hspace{0.05cm}u_i \hspace{0.05cm}p_i$".
• Die Paritysequenz  $\underline{p} \ (=$ Impulsantwort  $\underline{g})$  ergibt sich somit aus dem jeweiligen zweiten Coderausgangssymbol.
• $\underline{g}$ wird durch folgende Zustände repräsentiert:

$$S_0 → [S_1 → S_2 → S_5 → S_3 → S_7 → S_6 → S_4 ] → [S_1 → \ ... \ → S_4] → \ \text{ ... } $$

(5)  Die folgende Grafik zeigt die Lösung anhand der Generatormatrix $\mathbf{G}$. Es gilt $\underline{u} = (0, \, 1, \, 1, \, 0, \, 0, \, \text{ ... } )$.

$\underline{p} = (0, \, 1, \, 1, \, \text{ ... } ) \cdot \mathbf{G}$

Man erkennt, dass die Lösungsvorschläge 1, 2 und 3 richtig sind:

• Die vorliegende Paritysequenz $\underline{p}$ hat die gleiche Periode $P = 7$ wie die Impulsantwort $\underline{g}$.
• Das Hamming–Gewicht der (begrenzten) Eingangsfolge ist tatsächlich $w_{\rm H}(\underline{u}) = 2$.
• Der Vorschlag 4 ist falsch. Vielmehr gilt hier für die semi–infinite Ausgangssequenz: $w_{\rm H}(\underline{p}) → \infty$.

Im Übergangsdiagramm werden zunächst die Zustände $S_0 → S_0 → S_1 → S_3 → S_7 → S_6 → S_4 → S_1$ durchlaufen. Danach folgt (unendlich oft) der periodische Anteil $S_1 → S_2 → S_5 → S_3 → S_7 → S_6 → S_4 → S_1$.

(6)  Die letzte Grafik zeigt die Lösung für $U(D) = D + D^8 \Rightarrow \underline{u} = (0, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 1, \, 0, \, 0, \, \text{ ... })$.

$\underline{p} = (0, \, 1, \, 0, \, 0, \, 0, \, 0, \, 0, \, 0, \, 1, \, 0, \, 0, \, \text{ ... }) \cdot \mathbf{G}$

Richtig sind die Lösungsvorschläge 3 und 4:

• Die Eingangssequenz $\underline{u}$ beinhaltet zwei Einsen und die Ausgangssequenz $\underline{p}$ sechs Einsen.
• Ab der Position 10 ist nun die Ausgangssequenz $\underline{p} \equiv\underline{0}$  
  ⇒   die Vorschläge 1 und 2 treffen also nicht zu.

Weitergehende Hinweise:

• Für einen Turbocode sind insbesondere solche Eingangsfolgen $\underline{u}$, deren $D$–Transformierte als $U(D) = f(D) \cdot [1 + D^{P}]$ darstellbar sind, äußerst ungünstig.
• Sie bewirken den Error Floor, wie er auf der Seite "Leistungsfähigkeit der Turbocodes" im Theorieteil zu erkennen ist.
• $P$  gibt dabei die Periode der Impulsantwort  $\underline{g}$ an.
• In unserem Beispiel gilt  $f(D) = D$  und  $P = 7$.