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

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.

- Error correcting code
- Reed Solomon Decoding - Error Correction - Syndromes Calculation
- Estimate BER of QPSK in AWGN with Reed-Solomon (240,224) Coding
- How to efficiently create generator Matrix using Reed-Solomon encoding
- Can the Euclid algorithm be used to do Reed Solomon decoding for the more general case where b > 1 in WHP 031?
- Differences Between Systematic Reed Solomon Encoding Methods
- 'UTF-8' decoding error while using unireedsolomon package
- Welch-Berlekamp Algorithm for Reed Solomon code as nonbinary BCH code
- How to apply Reed-Solomon algorithm using zxing in C#
- Error correction on small message (8-Bit) with high resilience, what is the best method?
- Reed-Solomon detection capability
- Reed-Solomon Code for large code length and errors
- CDROM, F2 Reed-Solomon P Q codes in CIRC encoder
- Reed solomon how many missing bytes can be corrected?
- Why error-only decoding has high miscorrection rate for small parity?
- Berlekamp-Massey Algorithm not working for Syndrome's Least significant Symbol being 0
- Construction of Reed Solomon - detection and correction
- Can you please explain Reed Solomon encoding part's Identity matrix?
- Does Reed-Solomon Error algorithm allow correction only if error occur on input data part?
- Use of Reed-Solomon error correction algorithm with 4-state barcodes
- What is the value of the ideal value of the generator polynomial index in the Schifra library for Reed-Solomon error correcting code?
- QR code generation algorithm implementation case analysis
- Reed Solomon Error DETECTION capability is not 2T
- Encoding image, using reed-solomon coder
- Reed Solomon error correction for QR-Code
- CCSDS Reed Solomon Encoding
- Addition and multiplication in a Galois Field
- Errata (erasures+errors) Berlekamp-Massey for Reed-Solomon decoding
- Reed solomon error correction and false positives
- Error detection capability using Berlekamp-Massey algorithm