# 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

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
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