Reed Solomon Codes – Introduction

The Hamming codes described in the previous articles are suitable for random bit errors in a sequence of transmitted bits. If the communication medium is prone to burst errors (channel errors affecting contiguous blocks of bits) (missing symbols are called erasures ), then Hamming code may not be suitable.

For example in CD, DVD and in Hard drives, the data is written in contiguous blocks and are retrieved in contiguous blocks. The heart of a hard disk is the read/write channel (an integral part of the disk drive controller SOC chip). The read/write channel is used to improve the signal to noise ratio of the data that is written into and read from the disk. Its design is aimed at providing reliable data retrieval from the disk. Algorithms like PRML (Partial Response signaling with Maximum Likelihood detection) are used to increase the areal densities of the disk (packing more bits in a given area on the disk platter). Error control coding is used to improve the performance of the detection algorithm and to protect the user data from erasures. In this case, a class of Error correcting codes called Reed Solomon Codes (RS Codes) are used. RS Codes have been utilized in hard disks for the past 15 to 20 years. RS codes are useful for channels having memory (like CD,DVD).

The other applications of RS Codes include:

1) Digital Subscriber line (DSL) and its variants like ADSL, VDSL…
2) Deep space and satellite communications
3) Barcodes
4) Digital Television
5) Microwave communication, Mobile communications and many more…

Reed Solomon Codes are linear block codes, a subset of the BCH codes called non-binary BCH. (n,k) RS code contains k data symbols and n-k parity symbols. RS Codes are also cyclic codes since the cyclic shift of any codeword will result in another valid RS codeword.

Note the usage of the word “symbols” instead of “bits” when referring to RS Codes. The word symbol is used to refer a group of bits. For example if I say that I am using a (7,3) RS Code with 5 bit symbols, it implies that each symbol is a collection of 5-bits and the RS Codeword is made up of 7 such symbols, of which 3 symbols represent data and remaining 4 symbols represent parity symbols.

A m-bit RS (n,k) Code can be defined using

where t is the symbol error correcting capability of the RS code. This code corrects t symbol errors. We can also see that the minimum distance for RS code is given by

This gives the maximum possible d_min. A code with maximum d_min is more reliable as it will be able to correct more errors.

Example:

Consider a (255,247) RS code , where each symbol is made up of m=8 bits. This code contains 255 symbols (each 8 bits of length) in a codeword of which 247 symbols are data symbols and the remaining 8 symbols are parity symbols. This code can correct any 4 symbol burst errors.

If the errors are not occurring in a burst fashion, it will affect the codeword symbols randomly and it may corrupt more than 4 symbols. At this situation the RS code fails. So it is essential that the RS codes should be used only for burst error correction. Other techniques like interleaving/deinterleaving are used in tandem with RS codes to combat both burst and random errors.

Performance Effects of RS Codes :

1) block length Increases (n) -> BER decreases
2) Redundancy Increases (k) -> code rate decreases -> BER decreases -> complexity increases
( code rate = n/k)
3) Optimum code rate for an RS code is calculated from the decoder performance (for a particular channel) at various code rates. The code rate which require the lowest E_b/N₀ for a given BER is chosen as the optimum code rate for RS Code design.

Matlab Code:

Here is a simple Matlab code (which can be found in Matlab Help, posted here with a little bit detailed explanation) for better understanding of RS code

%Matlab Code for RS coding and decoding

n=7; k=3; % Codeword and message word lengths
m=3; % Number of bits per symbol
msg = gf([5 2 3; 0 1 7;3 6 1],m) % Two k-symbol message words

% message vector is defined over a Galois field where the number must
%range from 0 to 2^m-1

codedMessage = rsenc(msg,n,k) % Two n-symbol codewords
dmin=n-k+1 % display dmin
t=(dmin-1)/2 % diplay error correcting capability of the code 

% Generate noise - Add 2 contiguous symbol errors with first word;
% 2 discontiguous symbol errors with second word and 3 distributed symbol
% errors to last word
noise=gf([0 0 0 2 3 0 0 ;6 0 1 0 0 0 0 ;5 0 6 0 0 4 0],m)
received = noise+codedMessage

%dec contains the decoded message and cnumerr contains the number of
%symbols errors corrected for each row. Also if cnumerr(i) = -1 it indicates
%that the ith row contains unrecoverable error
[dec,cnumerr] = rsdec(received,n,k)

% print the original message for comparison
display(msg)

% Given below is the output of the program. Only decoded message, cnumerr and original
% message are given here (with comments inline)
% The default primitive polynomial over which the GF is defined is D^3+D+1 ( which is 1011 -> 11 in decimal).
dec = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)

Array elements =
5 2 3
0 1 7
6 6 7

cnumerr =
2
2
-1 ->>> Error in last row -> this error is due to the fact that we have added 3 distributed errors with the last row where as the RS code can correct only 2 errors. Compare the decoded message with original message given below for confirmation

% Original message printed for comparison
msg = GF(2^3) array. Primitive polynomial = D^3+D+1 (11 decimal)

Array elements =
5 2 3
0 1 7
3 6 1

Reference :

[1] Mathematics behind RS codes – Bernard Sklar – Click Here

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