algorithmencodingdecodingreed-solomon# Welch-Berlekamp Algorithm for Reed Solomon code as nonbinary BCH code

I am familiar with RS codes and the classic syndrome-based decoding algorithm. However, I now have the task of implementing an alternative decoder, the Welch-Berlekamp algorithm. Here, the underlying application requires that no syndrome computation is required (I am aware that the syndrome-based approach is simpler in complexity than the Welch-Berlekamp algorithm).

Basically, I know that there are two different variants for RS codes.

**Original encoding**scheme for Reed Solomon code, where there is a fixed set of data points known to encoder and decoder, and a polynomial based on the message to be transmitted, unknown to the decoder.**BCH type code**where a fixed polynomial known to both encoder and decoder.

For the original variant of RS codes, the implementation of the Welch-Berlekamp algorithm initially seems relatively easy to me. Here the system of equations can be set up from the generator matrix and the received symbols.

However, it is now required to implement the Welch-Berlekamp algorithm for the second variant. I am currently having difficulties here and I'm also in doubt as to whether this is even possible for this variant.

I would be very grateful if someone could help me if the Welch-Berlekamp algorithm can also be used for the BCH variant.

Best regards,

RatbaldMeyer

Solution

implement the Welch-Berlekamp algorithm for the second variant

The parameters are not the same.

Variant 1 - Fixed set of data points. For a RS(n, k) code, decoders operate on n symbols to reconstruct the polynomial used to encode a message.

Variant 2 - Fixed generator polynomial with roots that are successive powers of primitive element α, such as (x-2) (x-4) (x-8) ... . For a RS(n, k) code, decoders generate and then operate on n-k syndromes to determine error locations (error locator polynomial) and error values.

Welch-Berlekamp requires O(n^3) operations to invert a matrix. Gao's extended Euclid algorithm has time complexity O(n^2) if the initial and constant polynomial used by the decoder based on the fixed set of data points is pre-calculated (the Wiki article shows this polynomial as R[-1]).

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

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array