About this document

Erasure Decoding

Assume a received vector with errors and f erasures. Let , the error locators and , the erasure locators.

Define the erasure locator polynomial:

Decoding is done according to the following steps:

1. Compute the erasure polynomial using the erasure information provided by the receiver.
2. Replace the erased coordinates with zeros and compute the syndrome polynomial S(x).
3. Compute the modified syndrome polynomial

   

4. Apply the Berlekamp algorithm to find the connection polynomial using the modified syndrome coefficients
5. Find the roots of , thus the error locations.
6. Determine the magnitudes of the errors and erasures. For that, first define the error/erasure locator polynomial

   

   The error and erasure values are

   

   where

   

Example: Error/erasure decoding using a (7,3) Reed-Solomon code

Let the received polynomial be

Assume two erasures at locations . Then,

Replace the erased coordinates by zeros and compute the syndromes:

The modified syndrome polynomial is given by:

Now apply the Berlekamp algorithm to find :

Therefore,

Next, find polynomials and :

Finally, compute the error and erasure magnitudes:

The corresponding codeword is: