Reed Solomon – A Brief Introduction

Reed Solomon is one brilliant error correction method that is a non-binary cyclic codes. The codeword looks like the picture below. It has symbols in m-bits. The bit string is treated as a group of bits. The group of bits is treated as non-binary. We will see how it makes this method powerful.

Reed Solomon

Let’s take an example of RS(15,11). This means that we have the codeword with length 15 bits that consists of original message 11 bits  and 4 bits for parity. t is how many errors (in symbols or group of bits) that can be corrected.

p(x) or irreducible polynomial is used to generate the finite field like shown in the table below.

RS(15,11)

Now we need a generator to start the encoding process.

Generator

RS Encoding Process 1

RS Encoding Process 2

RS Encoding Process 3

The process of decoding includes several steps. Let’s take an example of double-symbol error.

RS Decoding

The first process is computing the syndrome to detect the error. For this case will have 4 syndromes: S1, S2, S3 and S4. Each S that is not equal to 0 contains error.

RS Syndrome Computation

The second step is locating the error in e(x). This can be done using matrix.

RS Error Locating

After the location has been determined, now it is the time to calculate the values of the error so we can correct the error.

RS Error Values

Done. We get the message corrected. Do you notice that detecting the errors in symbols (groups of bits) in this method makes it runs faster?

Advertisements