# Block Interleaver Design for RS codes

### Introduction:

A \( (n,k) \) Reed Solomon (RS) encoder, takes \(k\) user data symbols and converts it into a n symbol wide codeword, by adding \(n-k\) parity symbols. The error correcting capability \((t)\) of the RS code is computed as \( t \leq \frac{n-k}{2}\). That is, a RS code with \(n-k\) parity symbols can correct a burst error of upto \(\frac{n-k}{2}\) 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 \(b \gt t\), the error correcting code will fail. This is where interleaving comes to our rescue.

Let us assume that \(b > t\) and \(b \leq t × d \), where d (the interleaving depth) is an integer. The Reed-Solomon \((n,k)\) 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 \(n = 255,\; k = 235,\; t = 10,\; d = 5 \),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.

Here, the data is written row by row and read back column by column.Consider now the effect of a burst error of length \(b > t\), (where \(t\) is the number of correctable errors per block) and \(b \leq v \times d \) for some \(v\), 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 \(d \times i\) will effect at most \(d + 1\) 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 \(d \gt t\), these errors are within the error correction capability of the code and can be corrected. In this case, \(d\) 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 \(t= \frac{n-k}{2} = 10\) symbols errors. Lets assume that the channel that we are going to use, is expected to cause \(b=253\) symbols. Then the interleaver depth \((d)\) is calculated as

$$ d \gt \frac{b}{t} = \frac{253}{10} = 25.3 $$

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 \(d \times n = 26 \times 255 \) (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 ‘*****‘.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
%Demonstration of design of Block Interleaver for Reed Solomon Code %Author : Mathuranathan for http://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&gt;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&gt;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 -&gt; \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 ''*''-&gt;\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-&gt;\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_____________________________________________________________________________

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________________

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

Pingback: Random Interleaver | GaussianWaves()

Pingback: Interleavers and deinterleavers | GaussianWaves()