Interleaving

R2026b

Interleaving is useful for reducing bursts of errors in a communications system. To combat error bursts, an interleaver rearranges the sequence of input data symbols according to a predetermined rule, or mapping. A corresponding deinterleaver uses the inverse mapping to restore the original sequence of symbols. In the typical use of interleaver/deinterleaver pairs, the inputs of the deinterleaver match those of the interleaver, except that the data is permuted. Permutation spreads contiguous, clustered errors across multiple code blocks, which makes isolating and correcting the errors easier. Communications Toolbox™ includes features to apply this technique through block interleaving and convolutional interleaving.

Block Interleaving

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 a fixed block size for a given interleaver. The interleaver's operation on a set of symbols is independent of its operation on all other sets of symbols.

The block interleaver options in Communications Toolbox software include a general block interleaver as well as interleavers for special cases. Each special-case interleaver uses the same computational code that the general block interleaver uses but provides a syntax that is more suitable for the special case.

Type of Interleaver	Description	Functions	Blocks
General block interleaver	Uses the permutation table given explicitly as an input argument.	intrlv, deintrlv	General Multiplexed Interleaver, General Multiplexed Deinterleaver
Matrix interleaver	Fills a matrix with data elements row by row and then sends the matrix contents to the output column by column.	matintrlv, matdeintrlv	Matrix Interleaver, Matrix Deinterleaver
Random interleaver	Chooses a permutation table randomly by using the initial state input that you provide.	randintrlv, randdeintrlv	Random Interleaver, Random Deinterleaver

Improve Error Rate Using Block Interleaving in MATLAB

This example shows how an interleaver improves the error rate in a communications 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, 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];

Display the bit error rate with interleaving and deinterleaving applied.

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

Number of errors and error rate, with interleaving:

[number_with,rate_with] = biterr(msg,decoded)       % Error statistics

number_with = 
0

rate_with = 
0

Display the bit error rate with no interleaving and deinterleaving applied.

code_err = bitxor(code,errors);                     % Include burst error
decoded = decode(code_err,n,k,'hamming/binary');    % Decode

Number of errors and error rate, with no interleaving:

[number_without,rate_without] = biterr(msg,decoded) % Error statistics

number_without = 
4

rate_without = 
0.0020

Improve Error Rate Using Block Interleaving in Simulink

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

The doc_interleaver model applies Hamming encoding and random interleaving to a binary signal. The model consists of these blocks, configured as noted:

• Bernoulli Binary Generator — Check the box next to Frame-based outputs. Set Samples per frame to 4.

• Hamming Encoder — Use default parameter settings.

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

• Random Interleaver — Set Number of elements to 84.

• Logical Operator (Simulink) — Set Operator to XOR.

• Signal From Workspace — Set Signal to errors. Set Sample time to 4/7. Set Samples per frame to 84.

• Random Deinterleaver — Set Number of elements to 84.

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

• Hamming Decoder — Use default parameter settings.

• Error Rate Calculation — Set Receive delay to (4/7)*84. Set Computation delay to 100. Set Output data to Port.

• Display (Simulink) — Use default parameter settings.

• Signal To Workspace — Use default parameter settings.

In the Simulate section of the model, Stop time is set to length(errors). The Simulate section appears on multiple tabs. Before deinterleaving and decoding, the signal gets impaired by a vector of random bursty errors.

Opening the doc_interleaver model runs the initFcn callback, which creates a vector of bursty errors 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 in the range [1, 80]. The Signal From Workspace block imports this vector from the MATLAB workspace into the model, where the Logical Operator block performs an XOR operation of the vector with the signal. For more information, see Model Callbacks (Simulink).

Compute and display the ratio of the number of 1s to the total number of symbols in the errors vector, sum(errors)/length(errors). The error rate is approximately 3/43, or 0.0698, because 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 0.0698.

sum(errors)/length(errors) = 0.072.

Run the model with Hamming coding and interleaving enabled and display the error rate.

Error rate with Hamming coding and interleaving is 0.0205.

To see the effect of interleaving, comment out the Random Interleaver and Random Deinterleaver blocks from the model and rerun the simulation. The bit error rate is higher without interleaving because the [7,4] Hamming code can correct only one error in each codeword.

Error rate with Hamming coding and no interleaving is 0.0831.

Convolutional Interleaving

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. Since a convolutional interleaver has memory, its operation depends not only on current symbols but also on previous symbols.

The total delay due to a convolutional interleaver/deinterleaver pair is N × slope × (N – 1), where N is the number of registers and slope is the register length step.

The structure of a general convolutional interleaver comprises a set of shift registers, each having a specified delay 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.

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

The convolutional interleaver options in Communications Toolbox software have input arguments that indicate the number of shift registers and the delay for each shift register.

Type of Interleaver	Description	Functions	System Objects	Blocks
Convolutional interleaver	Uses delay values for the set of shift registers that are nonnegative integer multiples of a fixed integer that you specify.	convintrlv, convdeintrlv	comm.ConvolutionalInterleaver, comm.ConvolutionalDeinterleaver	Convolutional Interleaver, Convolutional Deinterleaver
Helical interleaver	Fills an array with input symbols in a helical fashion and empties the array row by row.	helintrlv, heldeintrlv	—	Helical Interleaver, Helical Deinterleaver

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. You can calculate the delay, measured in symbols, between the original and restored sequences by using the following equations. The variables in the equations (nrows, slope, col, ngrp, and stp) refer to the inputs for the associated functions.

Interleaver/Deinterleaver Functions	Delay Between Original and Restored Sequences
convintrlv, convdeintrlv	nrows×(nrows–1)×slope
helintrlv, heldeintrlv	col×ngrp×ceil(stp×(col–1)/ngrp)

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. 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.

Effect of Delays on Recovery of Convolutionally Interleaved Data

If you use a convolutional interleaver followed by a corresponding convolutional deinterleaver, then a nonzero delay means that the recovered data output from the deinterleaver is not the same as the original data that was 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.

Typical approaches to compensate for a delay of D in an interleaver/deinterleaver pair include:

• Approach 1 — 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, no data is lost. All the original symbols appear in the recovered data.

• Approach 2 — 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, data is lost. Some of the original symbols are left in the shift registers of the deinterleaver and do not appear in the recovered data.

This code illustrates these approaches by computing a symbol error rate for the interleaving/deinterleaving operation and the length of the recovered data vector.

Configure Simulation

Generate a signal to interleave. Define interleaver parameters and compute the delay of the interleaver and deinterleaver pair. Create interleaver, deinterleaver, and error rate computation objects.

x = randi([0 63],20,1);
nrows = 3; slope = 2;
D = nrows*(nrows-1)*slope;
convInt = comm.ConvolutionalInterleaver(NumRegisters=nrows, ...
    RegisterLengthStep=slope);
convDeint = comm.ConvolutionalDeinterleaver(NumRegisters=nrows, ...
    RegisterLengthStep=slope);
errRate = comm.ErrorRate(ReceiveDelay=D);

Approach 1

Pad x with D extra symbols at the end before interleaving.

x_padded = [x; zeros(D,1)];

a1 = convInt(x_padded);
b1 = convDeint(a1);

Omit input padding and the first D symbols of the recovered data and compare.

servec1 = errRate(x_padded,b1);
ser1 = servec1(1);

Approach 2

Omit last D symbols of x and first D symbols of the recovered data

release(convInt); 
release(convDeint);
release(errRate);
a2 = convInt(x);
b2 = convDeint(a2);

Omit the last D symbols of the original data and the first D symbols of the recovered data and compare.

servec2 = errRate(x,b2);
ser2 = servec2(1);

Display the symbol error rates and length of the deinterleaved output vector for the two approaches. The zero values of ser1 and ser2 indicates correct alignment of the original and recovered data before computing the symbol error rates. The output vectors result in different amounts of deinterleaved data.

fprintf('Symbol Error Rate for Approach 1: %.4f\n',ser1);

Symbol Error Rate for Approach 1: 0.0000

fprintf('Symbol Error Rate for Approach 2: %.4f\n',ser2);

Symbol Error Rate for Approach 2: 0.0000

fprintf('Length of recovered data for Approach 1: %d\n',length(b1));

Length of recovered data for Approach 1: 32

fprintf('Length of recovered data for Approach 2: %d\n',length(b2));

Length of recovered data for Approach 2: 20

Delays of Convolutional Interleavers in Simulink

After a sequence of symbols passes through a convolutional interleaver and a corresponding convolutional deinterleaver, the restored sequence lags behind the original sequence. 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 D.

Interleaver/Deinterleaver Pair	Delay Between Original and Restored Sequences	Description
Convolutional Interleaver, Convolutional Deinterleaver	D = B × (N–1)	B is the Register length step parameter value. N is the Rows of shift registers parameter value.
Helical Interleaver, Helical Deinterleaver	D = $$CN\lceil \frac{s(C-1)}{N}\rceil$$	C is the Number of columns in helical array parameter N is the Group size parameter s is the Helical array step size parameter

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. If necessary, use the Delay block to adjust delays manually.

Convolutional Interleaving Consecutive Integer Sequence in Simulink

This example shows convolutional interleaving and deinterleaving using a sequence of consecutive integers, the inherent delay, and the effect of the interleaving the initial conditions of blocks.

The doc_convinterleaver model applies convolutional interleaving to a signal. The model consists of these blocks, configured as noted:

• Ramp (Simulink) — Use default parameter settings.

• Zero-Order Hold (Simulink) — Use default parameter settings.

• 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 Signal To Workspace — 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.

In the Simulate section, Stop time is set to 20.

Run the model and compare the output. In the output, the first column contains the original symbol sequence. The second column contains the interleaved sequence, and the third column contains the restored sequence. The negative numbers in the interleaved and restored sequences come from the initial conditions of the interleaving blocks, 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).

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

References

[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.