# How to incorporate erasures (known error locations) in computation Reed-Solomon error locator?

I'm implementing Reed-Solomon error correction for 2D barcode formats (part of the ZXing project). It already has a working implementation, which I managed to create, mostly years ago when I understood the math more.

The implementation only corrects errors (misread codeword at unknown location), not erasures (known location). Of course, erasures can be trivially treated as errors by forgetting that you know the location, but you use up an extra error correction codeword this way. Instead, I know that one has to use the knowledge of the error location to be able to correct the maximum possible number of errors.

I understand that knowledge of location lets you construct part of the error locator polynomial. If the locations are $j_1$, $j_2$, ... then part of the error locator polynomial is

$\sigma(x) = (1 - \exp(j_1)x) (1 - \exp(j_2)x)\cdots$

What I don't know yet is how to use this in the algorithm! How does the error locator use this as a starting point to locate the remaining errors? I feel like it's something as simple as multiplying or dividing something by this partial error locator polynomial.

I am using the Euclidean algorithm to find the error locator and error correction polynomial, not Berlekamp-Massey. The algorithm is more or less the one on the PDF417 Wikipedia page.

-
+1: But can somebody please enlighten me, why do quick response code people refer to individual symbols as codewords. In all the umpteen coding theory books that I have read, a codeword always refers to an instance of a coded block of information symbols + redundant symbols. Yet proponents of 2D-barcodes have the gall to refer to a symbol (= element of GF(256) = one byte's worth of information and/or redundancy) as a codeword. I am not blaming you, Sean. I just want to point fingers at someone, when/if I get a chance :-) –  Jyrki Lahtonen Apr 30 '12 at 13:08
Luckily Dilip knows this stuff. I would have referred you to Blahut's book with the caveat that you will need to switch to a Berlekamp-Massey style algorithm with erasure locations taken into account at the initialization stage (as well as in the end when recovering the erasure values, unless you decode in the frequency domain, when that step is IIRC the same). –  Jyrki Lahtonen Apr 30 '12 at 13:30
Guilty as charged... I only know this from barcodes and yes the input bytes are all codewords, so that's why I parroted the same terminology here. Yeah someone else has told me I need to switch to Berlekamp-Massey and I know how to use lambda there. –  Sean Owen Apr 30 '12 at 16:34
The Berlekamp-Massey algorithm and extended Euclidean algorithm are essentially the same as far are decoding BCH (and RS) codes is concerned. I have even designed a circuit (for errors-only decoding) in which if the input is the syndrome in one order, the circuit can be viewed as executing the Berlekamp-Massey algorithm while if the input is the syndrome in reverse order, the circuit can be viewed as executing the extended Euclidean algorithm. I don't have a similar circuit design for errors-and-erasures decoding, but Berlekamp-Massey algorithm needs more hardware than the Euclidean algorithm. –  Dilip Sarwate Apr 30 '12 at 18:00

Zhiyuan Yan and I presented a paper on this very topic at the 2009 IEEE International Symposium on Information Theory. I won't refer you to the Proceedings of this Symposium because the on-line version is hidden behind IEEE's paywall and because the algorithm given there is not quite right. The corrected version is available on arxiv. Here is what the abstract says.

The extended Euclidean algorithm (EEA) for polynomial greatest common divisors is commonly used in solving the key equation in the decoding of Reed-Solomon (RS) codes, and more generally in BCH decoding. For this particular application, the iterations in the EEA are stopped when the degree of the remainder polynomial falls below a threshold. While determining the degree of a polynomial is a simple task for human beings, hardware implementation of this stopping rule is more complicated. This paper describes a modified version of the EEA that is specifically adapted to the RS decoding problem. This modified algorithm requires no degree computation or comparison to a threshold, and it uses a fixed number of iterations. Another advantage of this modified version is in its application to the errors-and-erasures decoding problem for RS codes where significant hardware savings can be achieved via seamless computation.

-
Very nice! Let me dig in to this tonight. –  Sean Owen Apr 30 '12 at 16:36
Your paper had the one nugget of knowledge I needed. You multiply the syndrome $S(x)$ by the known error polynomial, then multiply the resulting $\sigma(x)$ by the same after the Euclidean algorithm. The rest is the same as far as I can tell. –  Sean Owen Apr 30 '12 at 23:52
The key tricks are that computing the erasure-locator polynomial $\sigma_{\epsilon}(x)$ from a list of erasure locations can be combined with the computation of the modified syndrome polynomial, and "seeding" the computation of the error-locator polynomial $\sigma_e(x)$ with $\sigma_{\epsilon}(x)$ instead of $1$ gets you the errata-locator polynomial $\sigma_e(x)\sigma_{\epsilon}(x)$ directly as part of the Euclidean algorithm iterations instead of getting $\sigma_e(x)$ as usual and then multiplying by $\sigma_{\epsilon}(x)$ "after the Euclidean algorithm" as you call it. –  Dilip Sarwate May 1 '12 at 2:23
Ah so the result of the Euclidean algorithm already locates both the unknown and known errors... of course, or else why would the evaluator polynomial be able to correct both the erasures and substitutions. So that second multiplication by the erasure locator that I mentioned is merely superfluous, adding roots that were already there. Right? –  Sean Owen May 1 '12 at 13:51
Yes, when seeded with $\sigma_{\epsilon}(x)$ (and the syndrome having been modified appropriately), the Euclidean algorithm will produce the errata locator and errata evaluator; no need for a second multiplication. The seamless computation mentioned in the abstract in my answer iteratively computes the modified syndrome and $\sigma_{\epsilon}(x)$ and puts them both in the place where they need to be for the Euclidean algorithm to do its job. –  Dilip Sarwate May 1 '12 at 15:29

I found the solution(s):

• either compute the Forney syndrome (by computing erasures_locator * syndrome, where * is the galois field polynomial multiplication).
• either modify your iterative decoding algorithm (BM or Euclidian or other) to directly account for the erasures locator polynomial in initialization, and by tweaking a few other variables (like the number of iterations which must be substracted by the number of erasures), then you can directly decode erasures at the same time as errors without using the Forney syndrome (just the standard syndrome). An errata decoder using Euclidian algorithm is described here: Efficient algorithms for decoding Reed-Solomon codes with erasures, Todd Mateer. I also described how to do that with the Berlekamp-Massey algorithm in this SO post.

Both approaches will give the same result, I have verified it in my implementation (I implemented both approaches).

Note that there are probably other approaches beyond these two, but to my knowledge, they are by far the most common.

-