Search code examples
reed-solomonforwarderrorcorrection

Berlekamp-Massey Algorithm not working for Syndrome's Least significant Symbol being 0

Berlekamp-Massey algorithm

I am trying to implement this algorithm in above picture. The Berlekamp-Massey algorithm solves the following problem in a RS(n,k) system : Given a syndrome polynomial

S(z) = {S(n-k-1),........S(2),S(1),S(0)}

, finds the Smallest degree Error polynomial. This algorithm works fine for all Syndromes but when S(0) becomes 0, the error polynomial is incorrect. Is there anything missing from the algorithm mentioned ??

Solution

  • At what point does it fail? Is it failing to produce an error locator polynomial, or does it create one that doesn't have the proper roots, or is it failing later, such as the Forney algorithm?

    I'm not sure if you really mean S(0) in your question. Most articles define S(j) as the sum of elements times successive powers (locations) of (alpha^j). It's important that the syndromes used by a decoder are based on the roots of the generator polynomial, if the first consecutive root = FCR = alpha^0 = 1 (g(x) = (x-1)(x-alpha)(x-alpha^2)...), use S(0) through S(n-k-1), or if FCR = alpha (g(x) = (x-alpha)(x-alpha^2)...), use S(1) through S(n-k).

    Any RS decoder should work, despite zero syndromes, as long as there aren't too many zero syndromes (which would indicate an uncorrectable error).

    The wiki article has a simpler description of the algorithm with example code. Note it uses lambda (Λ) instead of sigma (σ) to represent the error locator polynomial. The description is for the example code, and in this case S[0] could mean S(0) or S(1), depending on the FCR (which is not mentioned).

    https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm

    I also wrote interactive RS programs for 4 bit and 8 bit fields, which include Berlekamp Massey as one of the three decoders implemented in the programs. The programs allow the user to specify FCR as 1 or 2, unless a self-reciprocal polynomial is chosen (a non-popular option used to simplify hardware encoders). In these example programs, the polynomials are generally stored most significant term first (legacy issue), so the code shifts arrays to deal with this.

    http://rcgldr.net/misc/eccdemo4.zip

    http://rcgldr.net/misc/eccdemo8.zip

    I modded one one of my ecc demo programs to work with GF(2^10). I ran your test case:

    S[...] = {0000 0596 0302 0897}   (S[0] = 0)

    These are the iterations and polynomials that I get for BM decoder:

    k      d    σ

0   0000    0001
1   0596    0596 x^2 + 0000 x + 0001
2   0302    0596 x^2 + 1006 x + 0001
3   0147    0585 x^2 + 1006 x + 0001

    roots are:

    383 = 1/(2^526) and 699 = 1/(2^527)

    Trivia, by reversing the coefficients, you get the locators instead of their inverse:

     0001 x^2 + 1006 x + 0585 : roots are 346 = 2^526 and 692 = 2^527

    Note that Forney needs the unreversed polynomial if using Forney to calculate the error values.