9
$\begingroup$

In the Welch-Berlekamp algorithm for decoding Reed-Solomon codes, one is given a list of points $(a_i, b_i)$ representing a message with $e$ errors on the $b_i$ in unknown locations (and $e$ is given to the algorithm). The output is a polynomial passing through all of the given points except those in which errors occurred.

The method involves solving a system of linear equations of the form

$$b_i E(a_i) = Q(a_i)$$

for all $i$ where $E$ has degree $e$ and $Q$ has degree at most $e+k$. The variables are the coefficients of $E$ and $Q$.

To ensure that $E$ has degree $e$ one usually adds the constraint that the coefficient of $x^e$ is 1 to the linear system above. However, in practice one doesn't necessarily know $e$. One inefficient (but still polynomial time) way to deal with this is to try $e$ for all values starting with $(n+k-1)/2 - 1$ going down until a solution is found.

My question is: is there a more efficient way to determine $e$? Alternatively, is there a modification to the linear system that allows one to use an upper bound on $e$ instead of the exact value?

In particular I want to use this specific decoder for Reed-Solomon codes, and not a completely different algorithm based on other techniques.


In response to DW's answer, here is my working example. Everything is done modulo 7.

plain message is: [2, 3, 2]
polynomial is: 2 + 3 t^1 + 2 t^2
encoded message is: [[0, 2], [1, 0], [2, 2], [3, 1], [4, 4]]
corrupted message is: [[0, 2], [1, 0], [2, 3], [3, 1], [4, 4]]

So the error is in the third point.

When $e=2$ the polynomial equation in question is

$$b_i(e_0 + e_1x + e_2x^2) - q_0 - q_1x - q_2 x^2 - q_3x^3 - q_4x^4 = 0$$

And plugging in $x = 0,1,2,3,4$ gives the system in matrix form:

[2, 0, 0, 6, 0, 0, 0, 0, 0]
[0, 0, 0, 6, 6, 6, 6, 6, 0]
[3, 6, 5, 6, 5, 3, 6, 5, 0]
[1, 3, 2, 6, 4, 5, 1, 3, 0]
[4, 2, 1, 6, 3, 5, 6, 3, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 1]

The last row is the constraint that $e_2 = 1$. Applying Gaussian elimination we get

[1, 0, 0, 0, 0, 0, 1, 4, 0]
[0, 1, 0, 0, 0, 0, 3, 3, 1]
[0, 0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 2, 1, 0]
[0, 0, 0, 0, 1, 0, 2, 2, 5]
[0, 0, 0, 0, 0, 1, 4, 5, 2]

And picking 1 for both free variables we get a solution vector of

[2, 2, 1, 4, 1, 0, 1, 1]

Which translates to

E is 2 + 2 t^1 + 1 t^2
Q is 4 + 1 t^1 + 0 t^2 + 1 t^3 + 1 t^4

And $E$ does not divide $Q$. Note that $Q$ factors as $(t + 6) (t^3 + 2t^2 + 2t + 3) \mod 7$

For $e=1$ I get a good solution:

system is:    
[2, 0, 6, 0, 0, 0, 0]
[0, 0, 6, 6, 6, 6, 0]
[3, 6, 6, 5, 3, 6, 0]
[1, 3, 6, 4, 5, 1, 0]
[4, 2, 6, 3, 5, 6, 0] 
[0, 1, 0, 0, 0, 0, 1]

reduced system is:

[1, 0, 0, 0, 0, 0, 5]
[0, 1, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 3]
[0, 0, 0, 1, 0, 0, 3]
[0, 0, 0, 0, 1, 0, 6]
[0, 0, 0, 0, 0, 1, 2]

solution is [5, 1, 3, 3, 6, 2]
Q is 3 + 3 t^1 + 6 t^2 + 2 t^3
E is 5 + 1 t^1
P(x) = 2 + 3 t^1 + 2 t^2 # this is correct!
r(x) = 0

Note that while the counterexample above was generated by code I wrote from scratch (it was basically the first thing I tried), one can check the solutions are valid by hand, so even if my code is buggy it's still a valid counterexample to the claim that using $e=2$ works.

$\endgroup$
  • $\begingroup$ @D.W. the solution vector is valid. It is actually 1*2 + 1*1 + 4*1 (the dimensionality of the solution vector is one off because the last column of the matrix is left out). My leaving out the $b_i$ is a typo in the writeup here, but it is correct in my implementation. You can see its effect, for example, in the second row of the system which uses the point [1, 0], and the first three entires are all zero because they're multiplied by 0. If my example is unclear I can post my code on github. I consider my code clean, but it would be messier due to its generality. $\endgroup$ – JeremyKun Aug 18 '15 at 2:04
3
+50
$\begingroup$

The same procedure actually works to correct any number of errors up to $e$.

The requirement is that the error polynomial $E(x)$ has to be zero at every point $a_i$ where there was an error. Nothing says it has to be zero at only those points; you can have an $E(x)$ that is zero at other points too, and that's OK, as long as its degree is $e$.

So, if $e$ is an upper bound on the number of errors, there will exist a polynomial $E(x)$ with all the desired properties (i.e., has degree exactly $e$ and is zero at every point where there is an error). For instance, if there are fewer than $e$ errors, then there exists a polynomial $E(x)$ that's zero at every error, and zero at a few more points to get the number of zeros up to exactly $e$.

Finally, the correctness theorem says that if such a polynomial $E(x)$ exists, then the Berlekamp-Welch algorithm will be able to find it. So, even if there are fewer than $e$ errors, the procedure will still work correctly to identify $E(x)$. Once you have $E(x)$, you can identify $n-e$ positions that are error-free, and then you can decode in a straightforward way.


To document the result of the conversation about the "counterexample" in the question:

That's actually not a valid counterexample. The flaw was in the calculation of how many errors you should expect Berlekamp-Welch to be able to correct. The distance is $n-k+1$, so you should expect it to be able to correct up to $(n-k)/2$ errors (as Ran G. points out). In your counterexample $n=5$ and $k=3$, so $(n-k)/2=1$, so you should only expect this procedure to be able to correct one error, i.e., $e=1$. So, when you ran the procedure on an example with $e=2$, there's no reason to expect the procedure to work correctly.

So, the counterexample isn't actually a counterexample, and it doesn't contradict my answer above.

$\endgroup$
  • 1
    $\begingroup$ @JeremyKun the distance is $n-k+1$ so the code can correct up to $(n-k)/2$ errors, right? $\endgroup$ – Ran G. Aug 17 '15 at 19:44
  • $\begingroup$ Although a proof is missing, the explanation in this answer makes sense to me. Setting zeros in $E(x)$ "tells" the algorithm which points it should ignore when interpolating the polynomial. Therefore as long as the set of zeros in $E(x)$ contains the set of point in which errors have happened, the decoding should work. In this case there should be more free variables (to set the other places of zeros in arbitrary way). $\endgroup$ – Ran G. Aug 17 '15 at 19:56
  • $\begingroup$ Ooooh is this the problem... that I messed up the Singleton bound? So to verify, if I were to set $n = 7$, introduce a single error, and set $e=2$, then we should expect everything to work out. I will try this now. $\endgroup$ – JeremyKun Aug 18 '15 at 2:08
  • $\begingroup$ Okay, this works on the examples I'm trying it on. Excellent! $\endgroup$ – JeremyKun Aug 18 '15 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.