Exercise 4.08Z: Basics about Interleaving

• Return to book

Interleaver description

Interleaving is required, for example, for a channel with burst error characteristics in order to distribute the errors within the burst over a sufficiently large area so that they can subsequently be largely corrected (or at least detected).

For turbo codes based on so-called  RSC encoder  (Recursive Systematic Convolutional Encoder)  – and only such make sense – interleaving is essential also with the AWGN channel, because then there are also always (some) input sequences, which deliver only zeros in the output sequence after quite a few ones, and that to infinity   ⇒   there are output sequences with very small Hamming weight.

If the bits of such input sequences are distributed over a wide range in the second coder, the problem can be (largely) eliminated by the interaction of both component decoders in the case of iterative symbol-wise decoding.

A general distinction is made between

• Block interleaver and
• Random interleaver.

In block interleaving  one fills a matrix with  $S$  columns and  $Z$  rows column by column and reads the matrix row by row. This deterministically scrambles a block of information with  $I_{\rm max} = S \cdot Z$  bits.

On the right, two interleavers are indicated and in graphical form by the assignment  $I_{\rm Out}(I_{\rm In})$. These quantities represent the "index of the output sequence" and the "index of the input sequence", respectively. It holds:

$$1 \le I_{\rm Out} \le I_{\rm max} \hspace{0.05cm}, \hspace{0.5cm} 1 \le I_{\rm In} \le I_{\rm max} \hspace{0.05cm}. $$

In the subtask  (1)  it is asked whether this is  block interleaving  or  random interleaving  . The latter are discussed in the  "theory section"  but only very briefly.

Hints:

• Die Aufgabe bezieht sich auf das Kapitel  "The Basics of Turbo Codes".

• But other $\rm LNTww$–books also discuss interleaving, including the book "Examples of Message Systems" with reference to the

• Standard  Digital Subscriber Line (DSL)   ⇒   "Interleaving and Deinterleaving",
• 2G mobile communication system  GSM   ⇒   "Components of voice– and data transmission",
• 3G mobile communication system  UMTS   ⇒   "Channel Coding",
• 4G mobile communication system LTE   ⇒   "Funktionsweise von SC–FDMA"  (in the book "Mobile Communications").

Questions

1

What interleaver–type is shown in the graphic on the details page?

	Block interleaving,
	Random interleaving.

2

How many rows  ($Z$)  and columns  ($S$)  does the upper "Interleaver matrix 1" have?

$Z \ = \ $

$S \ = \ $

3

It holds  $\underline{u} = (1001'0001'1101'1101'0010'0111)$. How does the scrambled sequence begin  $\underline{u}_{\pi}$?
    Note:   The quotation marks serve only as a reading aid.

	$\underline{u}_{\pi} = (110'100'100'011'111'110'010'001' \text{...}\ )$,
	$\underline{u}_{\pi} = (101'001'000'111'100'101'011'101'\text{...}\ )$.

4

The scrambled sequence be  $\underline{u}_{\pi} = (100'100'011'101'110'100'100'111)$. What is the sequence after deinterleaving?

	$\underline{u} = (1101'0010'0011'1111'1001'0001'\text{...}\ )$,
	$\underline{u} = (1010'0100'0111'1001'0101'1101' \text{...}\ )$.

Solution

Solution

4×3 Interleaver Matrix

(1)  From the regular structure of the function $I_{\rm Out}(I_{\rm In})$ one can see that it is a block interleaver  ⇒  Response 1.

(2)  The index "1" is output as the first character. Further applies:

• The index 5 is output as the second character  ⇒  $\underline{Z = 4}$.
• The index 2 is output as the fourth character  ⇒  $\underline{S = 3}$.

The upper graph shows for the 4×3 interleaver matrix:

• the column by column write (red),
• the row by row readout (green).

Interleaving

(3)  Correct is the proposed solution 2:

• The matrix is written column by column and read row by row.
• After 12 bits, the matrix is cleared and the procedure starts over.
• The graphic shows that now the solution suggestion 2 is correct.

Zum De–Interleaving

(4)  Correct is the proposed solution 1:

• In deinterleaving, the matrix is written row by row and read column by column.
• The graphic shows that here the solution suggestion 1 is correct.