## Interleaving

### Block Interleaving

#### Block Interleaving Features

A block interleaver accepts a set of symbols and rearranges them, without repeating or omitting any of the symbols in the set. The number of symbols in each set is fixed for a given interleaver. The interleaver's operation on a set of symbols is independent of its operation on all other sets of symbols.

An interleaver permutes symbols according to a mapping. A corresponding deinterleaver uses the inverse mapping to restore the original sequence of symbols. Interleaving and deinterleaving can be useful for reducing errors caused by burst errors in a communication system.

Each interleaver function has a corresponding deinterleaver function. In typical usage of the interleaver/deinterleaver pairs, the inputs of the deinterleaver match those of the interleaver, except for the data being rearranged.

A block interleaver accepts a set of symbols and rearranges them, without repeating or omitting any of the symbols in the set. The number of symbols in each set is fixed for a given interleaver.

The set of block interleavers in this toolbox includes a general block interleaver as well as several special cases. Each special-case interleaver function uses the same computational code that the general block interleaver function uses, but provides a syntax that is more suitable for the special case. The interleaver functions are described below.

Type of InterleaverInterleaver FunctionDescription
General block interleaver`intrlv`Uses the permutation table given explicitly as an input argument.
Algebraic interleaver`algintrlv`Derives a permutation table algebraically, using the Takeshita-Costello or Welch-Costas method. These methods are described in [4].
Helical scan interleaver`helscanintrlv`Fills a matrix with data row by row and then sends the matrix contents to the output in a helical fashion.
Matrix interleaver`matintrlv`Fills a matrix with data elements row by row and then sends the matrix contents to the output column by column.
Random interleaver`randintrlv`Chooses a permutation table randomly using the initial state input that you provide.

Types of Block Interleavers.  The set of block interleavers in this library includes a general interleaver/deinterleaver pair as well as several special cases. Each special-case block uses the same computational code that its more general counterpart uses, but provides an interface that is more suitable for the special case.

The Matrix Interleaver block accomplishes block interleaving by filling a matrix with the input symbols row by row and then sending the matrix contents to the output port column by column. For example, if the interleaver uses a 2-by-3 matrix to do its internal computations, then for an input of `[1 2 3 4 5 6]`, the block produces an output of `[1 4 2 5 3 6]`.

The Random Interleaver block chooses a permutation table randomly using the Initial seed parameter that you provide in the block mask. By using the same Initial seed value in the corresponding Random Deinterleaver block, you can restore the permuted symbols to their original ordering.

The Algebraic Interleaver block uses a permutation table that is algebraically derived. It supports Takeshita-Costello interleavers and Welch-Costas interleavers. These interleavers are described in [4].

#### Improve Error Rate Using Block Interleaving in MATLAB

The following example illustrates how an interleaver improves the error rate in a communication system whose channel produces a burst of errors. A random interleaver rearranges the bits of numerous codewords before two adjacent codewords are each corrupted by three errors.

Three errors exceed the error-correction capability of the Hamming code. However, the example shows that when the Hamming code is combined with an interleaver, this system is able to recover the original message despite the 6-bit burst of errors. The improvement in performance occurs because the interleaving effectively spreads the errors among different codewords so that the number of errors per codeword is within the error-correction capability of the code.

```st1 = 27221; st2 = 4831; % States for random number generator n = 7; k = 4; % Parameters for Hamming code msg = randi([0 1],k*500,1); % Data to encode code = encode(msg,n,k,'hamming/binary'); % Encoded data % Create a burst error that will corrupt two adjacent codewords. errors = zeros(size(code)); errors(n-2:n+3) = [1 1 1 1 1 1]; % With Interleaving %------------------ inter = randintrlv(code,st2); % Interleave. inter_err = bitxor(inter,errors); % Include burst error. deinter = randdeintrlv(inter_err,st2); % Deinterleave. decoded = decode(deinter,n,k,'hamming/binary'); % Decode. disp('Number of errors and error rate, with interleaving:'); [number_with,rate_with] = biterr(msg,decoded) % Error statistics % Without Interleaving %--------------------- code_err = bitxor(code,errors); % Include burst error. decoded = decode(code_err,n,k,'hamming/binary'); % Decode. disp('Number of errors and error rate, without interleaving:'); [number_without,rate_without] = biterr(msg,decoded) % Error statistics```

The output from the example follows.

```Number of errors and error rate, with interleaving: number_with = 0 rate_with = 0 Number of errors and error rate, without interleaving: number_without = 4 rate_without = 0.0020 ```

#### Improve Error Rate Using Block Interleaving in Simulink

The following example shows how to use an interleaver to improve the error rate when the channel produces bursts of errors.

Before running the model, you must create a binary vector that simulates bursts of errors, as described in Improve Error Rate Using Block Interleaving in Simulink. The Signal From Workspace block imports this vector from the MATLAB workspace into the model, where the Logical Operator block performs an XOR of the vector with the signal.

To open the completed model, enter `doc_interleaver` at the MATLAB® command line. To build the model, gather and configure these blocks:

• Bernoulli Binary Generator, in the Random Data Sources sublibrary of the Comm Sources library

• Check the box next to Frame-based outputs.

• Set Samples per frame to `4`.

• Hamming Encoder, in the Block sublibrary of the Error Detection and Correction library. Use default parameters

• Buffer, in the Buffers sublibrary of the Signal Management library in DSP System Toolbox™

• Set Output buffer size (per channel) to `84`.

• Random Interleaver, in the Block sublibrary of the Interleaving library in Communications Toolbox™

• Set Number of elements to `84`.

• Set Operator to `XOR`.

• Signal From Workspace, in the Sources library of the DSP System Toolbox product

• Set Signal to `errors`.

• Set Sample time to `4/7`.

• Set Samples per frame to `84`.

• Random Deinterleaver, in the Block sublibrary of the Interleaving library in Communications Toolbox

• Set Number of elements to `84`.

• Buffer, in the Buffers sublibrary of the Signal Management library in DSP System Toolbox

• Set Output buffer size (per channel) to `7`.

• Hamming Decoder, in the Block sublibrary of the Error Detection and Correction library. Use default parameters.

• Error Rate Calculation, in the Comm Sinks library

• Set Receive delay to `(4/7)*84`.

• Set Computation delay to `100`.

• Set Output data to `Port`.

On the Simulation tab, in the Simulate section, set Stop time to `length(errors)`. The Simulate section appears on multiple tabs.

Creating the Vector of Errors.  Before running the model, use the following code to create a binary vector in the MATLAB workspace. The model uses this vector to simulate bursts of errors. The vector contains blocks of three 1s, representing bursts of errors, at random intervals. The distance between two consecutive blocks of 1s is a random integer between 1 and 80.

```errors=zeros(1,10^4); n=1; while n<10^4-80; n=n+floor(79*rand(1))+3; errors(n:n+2)=[1 1 1]; end ```

To determine the ratio of the number of 1s to the total number of symbols in the vector `errors` enter

```sum(errors)/length(errors) ```

Your answer should be approximately 3/43, or .0698, since after each sequence of three 1s, the expected distance to the next sequence of 1s is 40. Consequently, you expect to see three 1s in 43 terms of the sequence. If there were no error correction in the model, the bit error rate would be approximately .0698.

When you run a simulation with the model, the error rate is approximately .019, which shows the improvement due to error correction and interleaving. You can see the effect of interleaving by deleting the Random Interleaver and Random Deinterleaver blocks from the model, connecting the lines, and running another simulation. The bit error rate is higher without interleaving because the Hamming code can only correct one error in each codeword.

### Convolutional Interleaving

#### Convolutional Interleaving Features

A convolutional interleaver consists of a set of shift registers, each with a fixed delay. In a typical convolutional interleaver, the delays are nonnegative integer multiples of a fixed integer (although a general multiplexed interleaver allows unrestricted delay values). Each new symbol from an input vector feeds into the next shift register and the oldest symbol in that register becomes part of the output vector. A convolutional interleaver has memory; that is, its operation depends not only on current symbols but also on previous symbols.

The total delay due to a convolutional interleaver and deinterleaver pair is N × slope × (N – 1).

• N is the number of registers

• slope is the register length step

This diagram shows the structure of a general convolutional interleaver comprised of a set of shift registers, each having a specified delay shown as D(1), D(2),..., D(N), and a commutator to switch input and output symbols through registers. The kth shift register holds D(k) symbols, where k = 1, 2, 3, … N. The kth shift register has a delay value of ((k–1) × slope). With each new input symbol, the commutator switches to a new register and shifts in the new symbol while shifting out the oldest symbol in that register. When the commutator reaches the Nth register, upon the next new input, the commutator returns to the first register.

Communications Toolbox implements convolutional interleaving functionality using Simulink® blocks, System objects, and MATLAB functions. The convolutional interleavers in this toolbox have input arguments that indicate the number of shift registers and the delay for each shift register.

The set of convolutional interleavers in this product includes a general interleaver/deinterleaver pair as well as several special cases. Each special-case function uses the same computational code that its more general counterpart uses, but provides a syntax that is more suitable for the special case. The special cases are described below.

Type of InterleaverInterleaving FunctionDescription
General multiplexed interleaver`muxintrlv`Allows unrestricted delay values for the set of shift registers.
Convolutional interleaver`convintrlv`The delay values for the set of shift registers are nonnegative integer multiples of a fixed integer that you specify.
Helical interleaver`helintrlv`Fills an array with input symbols in a helical fashion and empties the array row by row.

The `helscanintrlv` function and the `helintrlv` function both use a helical array for internal computations. However, the two functions have some important differences:

• `helintrlv` uses an unlimited-row array, arranges input symbols in the array along columns, outputs some symbols that are not from the current input, and leaves some input symbols in the array without placing them in the output.

• `helscanintrlv` uses a fixed-size matrix, arranges input symbols in the array across rows, and outputs all the input symbols without using any default values or values from a previous call.

Types of Convolutional Interleavers.  The set of convolutional interleavers in this library includes a general interleaver/deinterleaver pair as well as several special cases. Each special-case block uses the same computational code that its more general counterpart uses, but provides an interface that is more suitable for the special case.

The most general block in this library is the General Multiplexed Interleaver block, which allows arbitrary delay values for the set of shift registers. To implement the preceding schematic using this block, use an Interleaver delay parameter of [D(1); D(2); ...; D(N)].

More specific is the Convolutional Interleaver block, in which the delay value for the kth shift register is (k-1) times the block's Register length step parameter. The number of shift registers in this block is the value of the Rows of shift registers parameter.

Finally, the Helical Interleaver block supports a special case of convolutional interleaving that fills an array with symbols in a helical fashion and empties the array row by row. To configure this interleaver, use the Number of columns of helical array parameter to set the width of the array, and use the Group size and Helical array step size parameters to determine how symbols are placed in the array. See the reference page for the Helical Interleaver block for more details and an example.

#### Delays of Convolutional Interleavers

After a sequence of symbols passes through a convolutional interleaver and a corresponding convolutional deinterleaver, the restored sequence lags behind the original sequence. The delay, measured in symbols, between the original and restored sequences is indicated in the table below. The variable names in the second column (`delay`, `nrows`, `slope`, `col`, `ngrp`, and `stp`) refer to the inputs named on each function's reference page.

Delays of Interleaver/Deinterleaver Pairs

Interleaver/Deinterleaver PairDelay Between Original and Restored Sequences
`muxintrlv`, `muxdeintrlv``length(delay)*max(delay)`
`convintrlv`, `convdeintrlv``nrows*(nrows-1)*slope`
`helintrlv`, `heldeintrlv``col*ngrp*ceil(stp*(col-1)/ngrp)`

Delays of Convolutional Interleavers.  After a sequence of symbols passes through a convolutional interleaver and a corresponding convolutional deinterleaver, the restored sequence lags behind the original sequence. The delay, measured in symbols, between the original and restored sequences is

Number of shift registers × Maximum delay among all shift registers

for the most general multiplexed interleaver. If your model incurs an additional delay between the interleaver output and the deinterleaver input, the restored sequence lags behind the original sequence by the sum of the additional delay and the amount in the preceding formula.

Note

For proper synchronization, the delay in your model between the interleaver output and the deinterleaver input must be an integer multiple of the number of shift registers. You can use the DSP System Toolbox Delay block to adjust delays manually, if necessary.

Convolutional Interleaver block

In the special case implemented by the Convolutional Interleaver/Convolutional Deinterleaver pair, the number of shift registers is the Rows of shift registers parameter, while the maximum delay among all shift registers is

B × (N-1)

where B is the Register length step parameter and N is the Rows of shift registers parameter.

Helical Interleaver block

In the special case implemented by the Helical Interleaver/Helical Deinterleaver pair, the delay between the restored sequence and the original sequence is

`$CN⌈\frac{s\left(C-1\right)}{N}⌉$`

where C is the Number of columns in helical array parameter, N is the Group size parameter, and s is the Helical array step size parameter.

Effect of Delays on Recovery of Convolutionally Interleaved Data Using MATLAB.  If you use a convolutional interleaver followed by a corresponding convolutional deinterleaver, then a nonzero delay means that the recovered data (that is, the output from the deinterleaver) is not the same as the original data (that is, the input to the interleaver). If you compare the two data sets directly, then you must take the delay into account by using appropriate truncating or padding operations.

Here are some typical ways to compensate for a delay of D in an interleaver/deinterleaver pair:

• Interleave a version of the original data that is padded with D extra symbols at the end. Before comparing the original data with the recovered data, omit the first D symbols of the recovered data. In this approach, all the original symbols appear in the recovered data.

• Before comparing the original data with the recovered data, omit the last D symbols of the original data and the first D symbols of the recovered data. In this approach, some of the original symbols are left in the deinterleaver's shift registers and do not appear in the recovered data.

The following code illustrates these approaches by computing a symbol error rate for the interleaving/deinterleaving operation.

```x = randi([0 63],20,1); % Original data nrows = 3; slope = 2; % Interleaver parameters D = nrows*(nrows-1)*slope; % Delay of interleaver/deinterleaver pair hInt = comm.ConvolutionalInterleaver('NumRegisters', nrows, ... 'RegisterLengthStep', slope); hDeint = comm.ConvolutionalDeinterleaver('NumRegisters', nrows, ... 'RegisterLengthStep', slope); % First approach. x_padded = [x; zeros(D,1)]; % Pad x at the end before interleaving. a1 = step(hInt, x_padded); % Interleave padded data. b1 = step(hDeint, a1) % Omit input padding and the first D symbols of the recovered data and % compare servec1 = step(comm.ErrorRate('ReceiveDelay',D),x_padded,b1); ser1 = servec1(1) % Second approach. release(hInt); release(hDeint) a2 = step(hInt,x); % Interleave original data. b2 = step(hDeint,a2) % Omit the last D symbols of the original data and the first D symbols of % the recovered data and compare. servec2 = step(comm.ErrorRate('ReceiveDelay',D),x,b2); ser2 = servec2(1)```

The output is shown below. The zero values of `ser1` and `ser2` indicate that the script correctly aligned the original and recovered data before computing the symbol error rates. However, notice from the lengths of `b1` and `b2` that the two approaches to alignment result in different amounts of deinterleaved data.

```b1 = 0 0 0 0 0 0 0 0 0 0 0 0 59 42 1 28 52 54 43 8 56 5 35 37 48 17 28 62 10 31 61 39 ser1 = 0 b2 = 0 0 0 0 0 0 0 0 0 0 0 0 59 42 1 28 52 54 43 8 ser2 = 0 ```

Combining Interleaving Delays and Other Delays.  If you use convolutional interleavers in a script that incurs an additional delay, d, between the interleaver output and the deinterleaver input (for example, a delay from a filter), then the restored sequence lags behind the original sequence by the sum of d and the amount from the table Delays of Interleaver/Deinterleaver Pairs. In this case, d must be an integer multiple of the number of shift registers, or else the convolutional deinterleaver cannot recover the original symbols properly. If d is not naturally an integer multiple of the number of shift registers, then you can adjust the delay manually by padding the vector that forms the input to the deinterleaver.

#### Convolutional Interleaving and Deinterleaving Using a Sequence of Consecutive Integers in MATLAB

The example below illustrates convolutional interleaving and deinterleaving using a sequence of consecutive integers. It also illustrates the inherent delay of the interleaver/deinterleaver pair.

```x = [1:10]'; % Original data delay = [0; 1; 2]; % Set delays of three shift registers. hInt = comm.MultiplexedInterleaver('Delay', delay); hDeint = comm.MultiplexedDeinterleaver('Delay', delay); y = step(hInt,x) % Interleave. z = step(hDeint,y) % Deinterleave.```

In this example, the `muxintrlv` function initializes the three shift registers to the values `[]`, `[0]`, and `[0 0]`, respectively. Then the function processes the input data `[1:10]'`, performing internal computations as indicated in the table below.

Current InputCurrent Shift RegisterCurrent OutputContents of Shift Registers
`1`1`1`
 `[]` `[0]` `[0 0]`
`2`2`0`
 `[]` `[2]` `[0 0]`
`3`3`0`
 `[]` `[2]` `[0 3]`
`4`1`4`
 `[]` `[2]` `[0 3]`
`5`2`2`
 `[]` `[5]` `[0 3]`
`6`3`0`
 `[]` `[5]` `[3 6]`
`7`1`7`
 `[]` `[5]` `[3 6]`
`8`2`5`
 `[]` `[8]` `[3 6]`
`9`3`3`
 `[]` `[8]` `[6 9]`
`10`1`10`
 `[]` `[8]` `[6 9]`

The output from the example is below.

```y = 1 0 0 4 2 0 7 5 3 10 state_y = value: {3x1 cell} index: 2 z = 0 0 0 0 0 0 1 2 3 4 ```

Notice that the “Current Output” column of the table above agrees with the values in the vector `y`. Also, the last row of the table above indicates that the last shift register processed for the given data set is the first shift register. This agrees with the value of `2` for `state_y.index`, which indicates that any additional input data would be directed to the second shift register. You can optionally check that the state values listed in `state_y.value` match the “Contents of Shift Registers” entry in the last row of the table by typing `state_y.value{:}` in the Command Window after executing the example.

Another feature to notice about the example output is that `z` contains six zeros at the beginning before containing any of the symbols from the original data set. The six zeros illustrate that the delay of this convolutional interleaver/deinterleaver pair is `length(delay)*max(delay) = 3*2 = 6`. For more information about delays, see Delays of Convolutional Interleavers.

#### Convolutional Interleaving and Deinterleaving Using a Sequence of Consecutive Integers in Simulink

The example below illustrates convolutional interleaving and deinterleaving using a sequence of consecutive integers. It also illustrates the inherent delay and the effect of the interleaving blocks' initial conditions.

To open the model, enter `doc_convinterleaver` at the MATLAB command line. To build the model, gather and configure these blocks:

Tip

Select the To Workspace block from the DSP System Toolbox / Sinks sublibrary. For more information, see To Workspace Block Configuration for Communications System Simulations.

• Ramp (Simulink). Use default parameters.

• Zero-Order Hold (Simulink). Use default parameters.

• Convolutional Interleaver

• Set Rows of shift registers to `3`.

• Set Initial conditions to ```[-1 -2 -3]'```.

• Convolutional Deinterleaver

• Set Rows of shift registers to `3`.

• Set Initial conditions to ```[-1 -2 -3]'```.

• Two copies of To Workspace (Simulink).

• Set Variable name to `interleaved` and `restored`, respectively, in the two copies of this block.

• Set Save format to `Array` in each of the two copies of this block.

Connect the blocks as shown in the preceding figure. On the Simulation tab, in the Simulate section, set Stop time to `20`. The Simulate section appears on multiple tabs. Run the simulation and execute the following command:

```comparison = [[0:20]', interleaved, restored] comparison = 0 0 -1 1 -2 -2 2 -3 -3 3 3 -1 4 -2 -2 5 -3 -3 6 6 -1 7 1 -2 8 -3 -3 9 9 -1 10 4 -2 11 -3 -3 12 12 0 13 7 1 14 2 2 15 15 3 16 10 4 17 5 5 18 18 6 19 13 7 20 8 8 ```

In this output, the first column contains the original symbol sequence. The second column contains the interleaved sequence, while the third column contains the restored sequence.

The negative numbers in the interleaved and restored sequences come from the interleaving blocks' initial conditions, not from the original data. The first of the original symbols appears in the restored sequence only after a delay of 12 symbols. The delay of the interleaver-deinterleaver combination is the product of the number of shift registers (3) and the maximum delay among all shift registers (4).

For a similar example that also indicates the contents of the shift registers at each step of the process, see Convolutional Interleaving and Deinterleaving Using a Sequence of Consecutive Integers in MATLAB.

### Selected Bibliography for Interleaving

[1] Berlekamp, E.R., and P. Tong, “Improved Interleavers for Algebraic Block Codes,” U. S. Patent 4559625, Dec. 17, 1985.

[2] Clark, George C., and J. Bibb Cain. Error-Correction Coding for Digital Communications. Applications of Communications Theory. New York: Plenum Press, 1981.

[3] Forney, G. D. Jr., “Burst-Correcting Codes for the Classic Bursty Channel,” IEEE Transactions on Communications, vol. COM-19, October 1971, pp. 772-781.

[4] Heegard, Chris and Stephen B. Wicker. Turbo Coding. Boston: Kluwer Academic Publishers, 1999.

[5] Ramsey, J. L, “Realization of Optimum Interleavers,” IEEE Transactions on Information Theory, IT-16 (3), May 1970, pp. 338-345.

[6] Takeshita, O. Y. and D. J. Costello, Jr., “New Classes Of Algebraic Interleavers for Turbo-Codes,” Proc. 1998 IEEE International Symposium on Information Theory, Boston, Aug. 16–21, 1998. pp. 419.