decodingreed-solomoneuclidean-algorithm# Can the Euclid algorithm be used to do Reed Solomon decoding for the more general case where b > 1 in WHP 031?

I have been attempting to understand how to decode the following RS(7,3) code (prim Poly = 1011, prim Elem = 2, b = 2) per the Euclid algo described in WHP 031 previously linked to on the wikipedia page here: https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction without success.

- My source codeword = [3 2 1 2 3 7 7]
- Codeword w/ 2 errors = [3 2 5 2 3 7 1]
- calculated syndromes = [2 2 0 1]
- error magn, omega = [4 5]
- error loc, lambda = [2 1 1]

I have used a python implementation of the Berlekamp-Massey algo to verify that the syndrome and error magn, and error loc polys are correct and that the codeword with 2 errors can be correctly decoded with b = 2 (first consecutive root = 4), but cannot understand how I might have implemented Euclid's algo incorrectly for larger values of b other than 0 or 1 where the syndrome takes the form S(x) = Sb+2t+1 * x^2t-1 + .... + Sb+1 * x + Sb.

Is the algo capable of handling the cases for larger values of b? Does the approach in WHP 031 require modification for these cases?

Solution

Can the Euclid algorithm be used to do Reed Solomon decoding for the more general case where b > 1

Yes

I fixed the broken Wiki link to use an internet archive link. That article is not very descriptive of the algorithm. Sugiyama's extended Euclid algorithm can be used for FCR (first consecutive root) of 2^{`b`

> 1}. In this case FCR = 2^2 = 4, which results in a self-reciprocal generator polynomial (coefficients are 1 4 6 4 1, which reversed are the same). Following the Wiki example:

algorithm:

Let `t`

= number of generator roots.
Let s(x) = polynomial with syndromes as coefficients.
The key equation is

```
Λ(x) s(x) = q(x) x^t + Ω(x)
```

The extended Euclidean algorithm can find a series of polynomials of the form

```
a[i](x) s(x) + b[i](x) x^t = r[i](x)
```

where the degree of r[i](x) decreases as i increases, and once the degree of r[i] < t/2, then Λ(x) = a[i](x), and Ω(x) = r[i](x). Both Λ(x) and Ω(x) are usually divided by the low order (constant) term of Λ(x) so that the lowest order term of Λ(x) = 1. q(x) and b[i](x) don't need to be saved, so the algorithm becomes:

```
r[−1] = x^t
a[-1] = 0
r[ 0] = s(x)
a[ 0] = 1
i = 0
while degree of r[i] ≥ t/2
i = i + 1
q = r[i-2] / r[i-1] (quotient)
r[ i] = r[i-2] - q r[i-1] (remainder)
a[ i] = a[i-2] - q a[i-1] (euclidean polynomial)
Λ(x) = a[i] / a[i][lo] ([lo] is low order term)
Ω(x) = r[i] / a[i][lo] ([lo] is low order term)
```

example from question:

```
generator roots: 4 3 6 7
generator poly: 1x^4 + 6x^3 + 4x^2 + 6x + 1
encoded msg: 3 2 1 2 3 7 7
error msg: 3 2 5 2 3 7 1
syndromes: s[{4 3 6 7}] = {5 7 0 4}
r[-1] 1x^4 + 0x^3 + 0x^2 + 0x + 0
a[-1] 0
r[ 0] 4x^3 + 0x^2 + 7x + 5
a[ 0] 1
q 7x + 0
r[ 1] 3x^2 + 6x + 0
a[ 1] 7x + 0
q 5x + 1
r[ 2] 1x + 5
a[ 2] 6x^2 + 7x + 1
Λ(x) 6x^2 + 7x + 1
Ω(x) 1x + 5
roots of Λ(x) 1 3
locators (1/roots) 1 6
indexes 6-log{1 6} = 6-{0 4} = 6 2
error values 6 4
error msg: 3 2 5 2 3 7 1
error values: 4 6
corrected msg: 3 2 1 2 3 7 7
```

- How to decode a string from Instagram backup in Swift?
- Decoding a txt file [Javascript]
- Parsing problems of vDDDTypes data with icalendar in python
- Why am I receiving an error when setting up a SSH Key for GitHub?
- How do I decode an encoded HttpWebResponse?
- How to decode Piexif XPKeywords?
- Why does base64 encoding require padding if the input length is not divisible by 3?
- How can I send and receive WebSocket messages on the server side?
- PowerShell - Issues Downloading Base64-Encoded PDF (Blank/White PDF)
- Decoding JWE with web-token/jwt-framework in PHP takes too much time
- How to handle/suppress Spring Boot DispatcherServlet exceptions related to URLDecoder
- Swift Error Handling Techniques for Decoding JSON as Either Object or Array
- Converting from Base64 returns the same result for different strings
- Maximum json file size which can be decoded without failure
- deduce some matching ENCODE function from existing DECODE function
- How to decode cbor encoded hex string using perl libraries?
- How to encode and decode sequential integer from DB to a pseudorandom Base36 6 character long string
- Encode String to Base64 using Delphi in TMS Web Core
- How would something that counts up in a specific base work in python?
- Does Decoder require an external data representation that has keys?
- What does the header struct for a webm (vp9) video stream look like?
- Fail to decompress Gzip response and GBK encoding using zlib.inflate in Nodejs
- Customise JSON decoder for nested object with Swift for iOS
- Some doubts about huggingface's BPE algorithm
- How do I allow HTML tags to be submitted in a textbox in asp.net?
- Decode Simple Encoded Array in Java
- C# File Path encoding and decoding
- How to determine if a word(4 bytes) is a 16-bit instruction or 32-bit instruction?
- Decoding error with async/await function to fetch Data
- Conversion of Base64 Encoded into XSLX