How to find possible errors in Reed-Solomon with only the syndrome?

2
votes

I am working on an assignment for a class I am taking.

I need to give the location and magnitude of a codeword's error, if possible, for a couple given syndromes. If I can figure out the methodology on how to do it for one I could do the rest, but I am lost on the first one.

Here is the syndrome: [2, 2, 0, 1]

I am to use a Reed-Solomon code with q = 11 and the primitive element as 2.

I created the following H matrix trying to solve this:

1  1  1  1  1  1   1  1   1  1
1  2  4  8  5  10  9  7   3  6
1  4  5  9  3  2   8  10  7  6
1  8  9  6  4  10  3  2   5  7

But since all I have is the syndrome, I'm not sure where to go from here. I'm sure I'm missing something rather straight forward here, hopefully someone can point it out to me.

I found Berlekamp, Peterson, and Euclidean approaches online, but we haven't gone over any of those and I don't understand how they work from the limited explanation online. We have used an error locating polynomial approach but I don't know how to apply it to this scenario, since to get to the point where you have 4 equations with 4 unknowns you would need to know the input codeword.

Thank you.

1
reed-solomon

1 Answers

0
votes

With 4 syndromes and no erasures (known error locations), only 2 errors can be corrected. There are 2 equations with 2 unknowns. Referring to the example in the wiki article:

https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Error_locator_polynomial

In your case, the syndrome subscripts are 0 to 3, instead of the wiki's 1 to 4.

S0 Λ2 + S1 Λ1 = -S2 (= 11 - S2)
S1 Λ2 + S2 Λ1 = -S3 (= 11 - S3)

Inverting a 2 by 2 matrix is straightforward, so there's no need for using Berlekamp Massey or extended Euclid algorithm.

If all the error locations are known (erasures), then the code only needs to solve for error values, using E for error value and L for locator, and ^ for exponentiation: 

 1^L1 E1 +  1^L2 E2 +  1^L3 E3 +  1^L4 E4 = S0
 2^L1 E1 +  2^L2 E2 +  2^L3 E3 +  2^L4 E4 = S1
 4^L1 E1 +  4^L2 E2 +  4^L3 E3 +  4^L4 E4 = S2
 8^L1 E1 +  8^L2 E2 +  8^L3 E3 +  8^L4 E4 = S3