Category: Interleaver

Random Interleaver

Note: There is a rating embedded within this post, please visit this post to rate it.

Random Interleaver:

The Random Interleaver rearranges the elements of its input vector using a random permutation. The incoming data is rearranged using a series of generated permuter indices. A permuter is essentially a device that generates pseudo-random permutation of given memory addresses. The data is arranged according to the pseudo-random order of memory addresses.

The de-interleaver must know the permuter-indices exactly in the same order as that of the interleaver. The de-interleaver arranges the interleaved data back to the original state by knowing the permuter-indices.

Random Interleaver
Random Interleaver

The interleaver depth (D) (Not sure what this term means ? – check out this article – click here) is essentially the number of memory addresses taken for permutation at a time. If the number of memory addresses taken for permutation increases, the interleaver depth increases.

In the Matlab simulation that is given below, an interleaver depth of 15 is used for illustration. This means that 15 letters are taken at a time and are permuted (rearranged randomly). This process is repeated consecutively for the next block of 15 letters.

As you may observe from the simulation that increasing the interleaver depth will increase the degree of randomness in the interleaved data and will decrease the maximum burst length after the de-interleaver operation.

Matlab Code:

A sample Matlab code that simulates the above mentioned random interleaver is given below. The input data is a repeatitive stream of following symbols – “THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_“. This code simulates only the interleaving/de-interleaving part.The burst errors produced by channel are denoted by ‘*‘.

%Demonstration of PseudoRandom Interleaver/Deinterleaver
%Author : Mathuranathan for https://www.gaussianwaves.com
%License - Creative Commons - cc-by-nc-sa 3.0

clc;
clear;
%____________________________________________
%Input Parameters
%____________________________________________
D=15; %Interleaver Depth. More the value of D more is the randomness
n=5; %Number of Data blocks that you want to send.
data='THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_'; % A constant pattern used as a data
%____________________________________________
%Make the length of the data to be a multiple of D. This is for
%demonstration only.Otherwise the empty spaces has to be zero filled.
data=repmat(data,1,n); %send n blocks of specified data pattern
if mod(length(data),D) ~=0
    data=[data data(1:(D*(fix(length(data)/D+1))-length(data)))];
end

%We are sending D blocks of similar data
%intlvrInput=repmat(data(1:n),[1 D]);
%fprintf('Input Data to the Interleaver -> \n');
%disp(char(intlvrInput));
%disp('____________________________________________________________________________');

%INTERLEAVER
%Writing into the interleaver row-by-row
permuterIndex=randperm(D);
intrlvrOutput=[];
index=1;

for i=1:fix(length(data)/D)
    intrlvrOutput=[intrlvrOutput data(permuterIndex+(i-1)*D)];
end

for i=1:mod(length(data),D)
    intrlvrOutput=[intrlvrOutput data(permuterIndex(i)+fix(length(data)/D)*D)];
end

uncorruptedIntrlvrOutput=intrlvrOutput;

%Corrupting the interleaver output by inserting 10 '*'
intrlvrOutput(1,25:34)=zeros(1,10)+42;

%DEINTERLEAVER
deintrlvrOutput=[];

for i=1:fix(length(intrlvrOutput)/D)
    deintrlvrOutput(permuterIndex+(i-1)*D)=intrlvrOutput((i-1)*D+1:i*D);
end

for i=1:mod(length(intrlvrOutput),D)
    deintrlvrOutput((fix(length(intrlvrOutput)/D))*permuterIndex+i)=intrlvrOutput((i+1):(i+1)*D);
end

deintrlvrOutput=char(deintrlvrOutput);
disp('Given Data -->');
disp(data);
disp(' ')
disp('Permuter Index-->')
disp(permuterIndex);
disp(' ')
disp('PseudoRandom Interleaver Output -->');
disp(uncorruptedIntrlvrOutput);
disp(' ')
disp('Interleaver Output after being corrupted by 10 symbols of burst error - marked by ''*''->');
disp(char(intrlvrOutput));
disp(' ')
disp('PseudoRandom Deinterleaver Output -->');
disp(deintrlvrOutput);

Simulation Result:

Given Data –>
THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX
_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY
_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN
_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_Q

Permuter Index–>
15 1 11 9 7 12 5 6 13 4 2 10 3 8 14

PseudoRandom Interleaver Output –>
NTBKIRQUO_H_ECWR__PUO_JVXFSOMET_DYAO_LGET_HZ__HR_COUIWQEB_KN_
FOSMVJUE_O_XPRHTO_ZGLA__HDEYTFEOBKWICNU_RQ__TOV_PEUMRJXO_S_EH
GDY_AZTLEO__HO_WR_NCK_IQOUBFHXEOSRMP_U_VJ_T_E_O_TZYHA_GLDEXQN
OB_K_FCUWIROE_RV__PSTMJEUOHQ_TGDHY_EZL_AO_

Interleaver Output after being corrupted by 10 symbols of burst error – marked by ‘*‘->
NTBKIRQUO_H_ECWR__PUO_JV**********AO_LGET_HZ__HR_COUIWQEB_KN_FOS
MVJUE_O_XPRHTO_ZGLA__HDEYTFEOBKWICNU_RQ__TOV_PEUMRJXO_S_EHGDY
_AZTLEO__HO_WR_NCK_IQOUBFHXEOSRMP_U_VJ_T_E_O_TZYHA_GLDEXQNOB_K
_FCUWIROE_RV__PSTMJEUOHQ_TGDHY_EZL_AO_

PseudoRandom Deinterleaver Output –>
THE_QUICK_BROWN_***_JU*P*_OV*R*THE_LAZ*_*OG_*HE_QUICK_BROWN_FOX_
JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LA
ZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BR
OWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_Q

As we can see from the above simulation that, even though the channel introduces 10 symbols of consecutive burst error, the interleaver/deinterleaver operation has effectively distributed the errors and reduced the maximum burst length to 3 symbols.

See also:

[1] Introduction to Interleavers and deinterleavers
[2] Block Interleaver Design for RS codes

Additional Resources:

[1] Concatenation and Advanced Codes – Applications of interleavers- Stanford University

Recommended Books

Block Interleaver Design for RS codes

Introduction:

A Reed Solomon (RS) encoder, takes user data symbols and converts it into a n symbol wide codeword, by adding parity symbols. The error correcting capability of the RS code is computed as . That is, a RS code with parity symbols can correct a burst error of upto symbol errors.

Block Interleavers:

Suppose, assume that the dominant error mechanism in a channel is of burst type. A burst of length b is defined as a string of b unreliable consecutive symbols. If the expected burst length, b is less than or equal to t (the number of correctable symbol errors by RS coding), the code can be used as it is. However, if bursts length , the error correcting code will fail. This is where interleaving comes to our rescue.

Let us assume that and , where d (the interleaving depth) is an integer. The Reed-Solomon code can be used if we can spread the burst error sequence over several code blocks so that each block has no more than t errors (which can then be corrected). This can be accomplished using block interleaving as follows. Instead of encoding blocks of k symbols and then sending the encoded symbols consecutively, we can interleave the encoded blocks and transmit the interleaved data. In the case where ,the data bytes output from the Reed-Solomon encoder would appear as shown below , where bytes numbered 0 to 234 are the data bytes and bytes 235 to 254 are the parity check bytes.

Code Structure for Reed Solomon (RS) Codes

Here, the data is written row by row and read back column by column.Consider now the effect of a burst error of length , (where is the number of correctable errors per block) and for some , on the received symbols in the table. Because of the order in which the symbols are sent, a burst length less than or equal to will effect at most consecutive columns of the table, depending on where the burst starts. Notice that any single row (which corresponds to a codeword) has no more than v errors in it. If , these errors are within the error correction capability of the code and can be corrected. In this case, becomes the interleaving depth. The trade-off is that extra buffer space is required to store the interleaver table and additional delay is introduced. The worst case burst length determines the size of the table (and the interleaving depth) and the table size determines the amount of buffer space required and the delay.

Design Example:

Consider a (255,235) Reed Solomon coding system. This code can correct upto symbols errors. Lets assume that the channel that we are going to use, is expected to cause symbols. Then the interleaver depth is calculated as

In this case , an interleaver depth of 26 is enough to combat the burst errors introduced by the channel. The block interleaver dimensions would be (26 rows by 255 columns).

Matlab Code:

A sample matlab code that simulates the above mentioned block interleaver design is given below. The input data is a repeatitive stream of following symbols – “THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_“. A (255,235) Reed Solomon decoder (with correction capability of 10 symbols) is used. We assume that the channel is expected to produce a maximum of consecutive 20 symbols of burst error. The burst errors are denoted by ‘*‘.

%Demonstration of design of Block Interleaver for Reed Solomon Code
%Author : Mathuranathan for https://www.gaussianwaves.com
%License - Creative Commons - cc-by-nc-sa 3.0
clc;
clear;
%____________________________________________
%Input Parameters
%____________________________________________
%Interleaver Design for Reed-Solomon Codes
%RS code parameters
n=255;  %RS codeword length
k=235;  %Number of data symbols
b=20;  %Number of symbols that is expected to be corrupted by the channel
%____________________________________________

p=n-k;  %Number of parity symbols
t=p/2; %Error correction capability of RS code

fprintf('Given (%d,%d) Reed Solomon code can correct : %d symbols \n',n,k,fix(t));
fprintf('Given - expected burst error length from the channel : %d symbols \n',b);
disp('____________________________________________________________________________');
if(b>t)
    fprintf('Interleaving  MAY help in this scenario\n');
else
    fprintf('Interleaving will NOT help in this scenario\n');
end
disp('____________________________________________________________________________');
D=ceil(b/t)+1; %Intelever Depth

memory = zeros(D,n); %constructing block interleaver memory

data='THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_'; % A constant pattern used as a data

%If n>length(data) then repeat the pattern to construct a data of length 'n'
data=char([repmat(data,[1,fix(n/length(data))]),data(1:mod(n,length(data)))]);

%We sending D blocks of similar data
intlvrInput=repmat(data(1:n),[1 D]);

fprintf('Input Data to the Interleaver -> \n');
disp(char(intlvrInput));
disp('____________________________________________________________________________');

%INTERLEAVER
%Writing into the interleaver row-by-row
for index=1:D
    memory(index,1:end)=intlvrInput((index-1)*n+1:index*n);
end
intlvrOutput=zeros(1,D*n);
%Reading from the interleaver column-by-column
for index=1:n
    intlvrOutput((index-1)*D+1:index*D)=memory(:,index);
end

%Create b symbols error at 25th Symbol location for test in the interleaved output
%'*' means error in this case
intlvrOutput(1,25:24+b)=zeros(1,b)+42;
fprintf('\nInterleaver Output after being corrupted by %d symbol burst error - marked by ''*''->\n',b);
disp(char(intlvrOutput));
disp('____________________________________________________________________________');

%Deinteleaver
deintlvrOutput=zeros(1,D*n);
%Writing into the deinterleaver column-by-column
for index=1:n
    memory(:,index)=intlvrOutput((index-1)*D+1:index*D)';
end

%Reading from the deinterleaver row-by-row
for index=1:D
    deintlvrOnput((index-1)*n+1:index*n)=memory(index,1:end);
end
fprintf('Deinterleaver Output->\n');
disp(char(deintlvrOnput));
disp('____________________________________________________________________________');

Simulation Result:

Given : (255,235) Reed Solomon code can correct : 10 symbols
Given : expected burst error length from the channel : 20 symbols

Interleaving MAY help in this scenario

Input Data to the Interleaver ->
THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_T
HE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_
JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUIC
K_BROWN_FOX_JUMPS_OVER_THE_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_
QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_
LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JU
MPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_THE_QUICK_BROWN_FOX
JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUIC
K_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY
DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_O
VER_THE_____________________________________________________________________________

Interleaver Output after being corrupted by 20 symbols burst error – marked by ‘*‘->
TTTHHHEEE___QQQUUUIIICCC********************N___FFFOOOXXX___JJJUUUMMMPPPSSS___OOOVV
VEEERRR___TTTHHHEEE___LLLAAAZZZYYY___DDDOOOGGG___TTTHHHEEE___QQQUUUIIICCCKKK
___BBBRRROOOWWWNNN___FFFOOOXXX___JJJUUUMMMPPPSSS___OOOVVVEEERRR___TTTHHH
EEE___LLLAAAZZZYYY___DDDOOOGGG___TTTHHHEEE___QQQUUUIIICCCKKK___BBBRRROOOWWWN
NN___FFFOOOXXX___JJJUUUMMMPPPSSS___OOOVVVEEERRR___TTTHHHEEE___LLLAAAZZZYYY___
DDDOOOGGG___TTTHHHEEE___QQQUUUIIICCCKKK___BBBRRROOOWWWNNN___FFFOOOXXX___JJJ
UUUMMMPPPSSS___OOOVVVEEERRR___TTTHHHEEE___LLLAAAZZZYYY___DDDOOOGGG___TTTHHHEE
E___QQQUUUIIICCCKKK___BBBRRROOOWWWNNN___FFFOOOXXX___JJJUUUMMMPPPSSS___OOOV
VVEEERRR___TTTHHHEEE___LLLAAAZZZYYY___DDDOOOGGG___TTTHHHEEE___QQQUUUIIICCCKKK___
BBBRRROOOWWWNNN___FFFOOOXXX___JJJUUUMMMPPPSSS___OOOVVVEEERRR___TTTHHHEEE__
_____________________________________________________________________________
Deinterleaver Output->
THE_QUIC*******_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_
LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUM
PS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BR
OWN_FOX_JUMPS_OVER_THE_THE_QUIC*******_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BRO
WN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_TH
E_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_
LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_THE_QUIC******N_FOX_JUMPS_OVER_THE_L
AZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS
_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN
_FOX_JUMPS_OVER_THE_LAZY_DOG_THE_QUICK_BROWN_FOX_JUMPS_OVER_THE________________
_____________________________________________________________

As we can see from the above simulation that, eventhough the channel introduces 20 symbols of consecutive burst error (which is beyond the correction capability of the RS decoder), the interleaver/deinterleaver operation has effectively distributed the errors and reduced the maximum burst length to 7 symbols (which is easier to correct by (255,235) Reed Solomon code.

See also:

[1] Introduction to Interleavers and deinterleavers
[2] Random Interleavers

Additional Resources:

[1] Notes on theory and construction of Reed Solomon Codes – Bernard Sklar
[2] Concatenation and Advanced Codes – Applications of interleavers- Stanford University

Interleavers and deinterleavers

Note: There is a rating embedded within this post, please visit this post to rate it.
Interleavers and Deinterleavers are designed and used in the context of characteristics of the errors that might occur when the message bits are transmitted through a noisy channel. To understand the functions of an interleaver/deinterleaver, understanding of error characteristics is essential. Two types are errors concern communication system design engineer. They are burst error and random error

Random Errors:

Error locations are independent of each other. Error on one location will not affect the errors on other locations. Channels that introduce these types of errors are called channels without memory (since the channel has no knowledge of error locations since the error on location does not affect the error on another location).

Burst Errors:

Errors are depended on each other. For example, in channels with deep fading characteristics, errors often occur in bursts (affecting consecutive bits). That is, error in one location has a contagious effect on other bits. In general, these errors are considered to be dependent and such channels are considered to be channels with memory.

Interleaver/Deinterleaver :

One of the most popular ways to correct burst errors is to take a code that works well on random errors and interleave the bursts to “spread out” the errors so that they appear random to the decoder. There are two types of interleavers commonly in use today, block interleavers and convolutional interleavers.

The block interleaver is loaded row by row with L codewords, each of length n bits. These L codewords are then transmitted column by column until the interleaver is emptied. Then the interleaver is loaded again and the cycle repeats. At the receiver, the codewords are deinterleaved before they are decoded. A burst of length L bits or less will cause no more than 1 bit error in any one codeword. The random error decoder is much more likely to correct this single error than the entire burst.The parameter L is called the interleaver degree, or interleaver depth. The interleaver depth is chosen based on worst case channel conditions. It must be large enough so that the interleaved code can handle the longest error bursts expected on the channel. The main drawback of block interleavers is the delay introduced with each row-by-row fill of the interleaver.

Convolutional interleavers eliminate the problem except for the delay associated with the initial fill. Convolutional interleavers also reduce memory requirements over block interleavers by about one-half [1]. The big disadvantage of either type of interleaver is the interleaver delay introduced by this initial fill. The delay is a function of the interleaver depth and the data rate and for some channels it can be several seconds long. This long delay may be unacceptable for some applications. On voice circuits (as in GSM), for example, interleaver delays confuse the unfamiliar listener by introducing long pauses between speaker transitions. Even short delays of less than one second are sufficient to disrupt normal conversation. Another disadvantage of interleavers is that a smart jammer can choose the appropriate time to jam to cause maximum damage. This problem is overcome by randomizing the order in which the interleaver is emptied.

In practice, interleaving is one of the best burst-error correcting techniques. In theory, it is the worst way to handle burst errors. Why? From a strict probabilistic sense, we are converting “good” errors into “bad” errors. Burst errors have structure and that structure can be exploited. Interleavers “randomize” the errors and destroy the structure. Theory differs from reality,however. Interleaving may be the only technique available to handle burst errors successfully.

For example, Viterbi [2] showed that, for a channel impaired by a pulse jammer, exploiting the burst structure is not enough. Interleaving is still required. This does not mean that we should be careless about our choice of code and take up the slack with long interleavers. Codes designed to correct burst errors can achieve the same performance with much shorter interleavers. Until the coding theorists discover a better way, interleaving will be an essential error control coding technique for bursty channels.

References :

[1]B. Sklar, Digital Communications Fundamentals and Applications, Englewood Cliffs, New Jersey: Prentice Hall, 1988.
[2]A. J. Viterbi, “Spread Spectrum Communications – Myths and Realities,” IEEE Communications Magazine, vol. 17, No. 5, pp. 11-18, May 1979.

See also:

[1] Block Interleaver Design for Reed Solomon Codes
[2] Random Interleavers

Additional Resources:

[1] Notes on theory and construction of Reed Solomon Codes – Bernard Sklar
[2] Concatenation and Advanced Codes – Applications of interleavers- Stanford University

Recommended Books