6
$\begingroup$

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.

  • 0
    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.2012-04-30

2 Answers 2

6

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.

  • 0
    I fixed my issues $a$nd I expl$a$ined in my SO post why they happend and how to fix them. I guess you are probably encountering a similar problem so this may help. http://stackoverflow.com/questions/30215337/errata-erasureserrors-berlekamp-massey-for-reed-solomon-decoding2015-06-25
0

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.