Construction of interleaver and deinterleaver

If the channel has memory, then errors no longer can be characterized as single randomly distributed bit errors. Most block and convolutional codes are designed to correct random independent errors. Using of these codes in the channel with memory results in degradation in error performance. Coding techniques for channels with memory have been proposed, but the great problem with such coding is the difficulty in obtaining accurate models of the often time-varying statistics of such channels.

Interleaving the coded message before transmission and deinterleaving after reception causes bursts of channel errors to be spread out in time and thus to be handled by the decoder as if they where random errors. Since, in all practical cases, the channel memory decreases with the time separation. Separating the symbols in time effectively transforms a channel with memory to a memoryless one, and thereby enables the random-error-correcting codes to be useful in a burst-noise channel.

Interleaving techniques have proven useful for all the block and convolutional codes described in earlier chapters. Two types of interleavers are commonly used: block and convolutional.

A block interleaver accepts the coded symbols in blocks from the encoder, permutes the symbols, and then feeds the rearranged symbols to the modulator. The usual permutation of the block is accompanished by filling the columns of an M-row-by N-column (M×N) array with the encoded sequence. After the array is completely filled, the symbols are then fed to the modulator one row at a time and transmitted over a channel.

Typically, for use with a single-error-correcting code the interleaver parameters are selected such that the number of columns N overbounds the expected burst length. The choise of the number of rows M depends on the coding scheme. For block codes, M should be larger than the code block length n, while for M should be larger than the constraint length. Thus a burst of length N can cause at most a single error in any block codeword: similarly, with convolutional codes, there will be at most a single error in any decoding constraint length. For t-error-correcting codes, the choice of N need only overbound the expected burst length divided by t.

Let’s consider diversity of error burst on the sequence of single errors, using square interleaver 7 ´ 7 (fig. 1.12). In this case bits received with errors for clearness are discussed as “1”.

In the third and fourth columns there are codewords with four and two errors, appearing as a result of the concentrated noise, which can not be corrected by the outer decoder with t_c = 1. Reading the binary bits of this matrix on the rows, we’ll get six code combinations with single errors which can be corrected by decoder.

Such transformations of binary symbols sequence at transmission and reception result in the substantial increase of noise immunity in a channel with independent errors, and also at burst of errors. The sequence of errors regrouped using deinterleaver facilitates possibility of their correction in an outer decoder.

Figure 1.12 – Square matrix of interleaver

A convolutional interleaver consists of T parallel lines, with different delay in each line that represents interleaver period. In general, each successive line has a delay which is M symbols durations higher than the previous line. The structure for M = 1 and T = 3 is illustrated in figure 1.13.

Figure 1.13 – Convolutional interleaver structure with T = 3 and M = 1

In a similar manner to the trellis termination technique (which emits stored data from memories), an insertion of a certain number of zeros at the end of a data block can isolate the interleaved data block. This guarantees a data block of a specific length and generates independent blocks of data for the encoder.

For the data length L = 6 and the convolutional interleaver with M = 1 and T = 3, the interleaved data would be X₁ 0 0 X₄ X₂ 0 0 X₅ X₃ 0 0 X₆.

The performance of a convolutional interleaver is very similar to that of a block interleaver. The important advantage of convolutional over block interleaving is that with convolutional interleaving the end-to-end delay is M(N – 1) symbols, and the memory required is M(N – 1)/2 at both ends of the block interleaving requirements.

Date: 2015-02-16; view: 1346