Talk:Reed–Solomon error correction/Archive 2

This is an archive of past discussions about Reed–Solomon error correction. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

Archive 2

Archive 3

Alternate Generator Polynomials

The examples in the article use a generator polynomial where the first consecutive root is α :

(X-α) (X-α²) (X-α³) ... (X-α^t)

If the first consecutive root of a generator polynomial isn't α, then the method used to calculate Ω(x) in the Euclidean example would need to be modified. I'm not sure if the Forney method would also need to be modified. Methods based on the error equations Error_locators_and_values should not require any modifications.

A generator polynomial may have a first consecutive root of 1: (X-1) (X-α) ... (X-α^t-1) or a generator polynomial may be reciprocal (X-α^(N/2)-(t/2)) ... (X-α^(N/2)+(t/2)) = 1 X^t + g1 X ^t-1 + g2 X ^t-2 + ... + g2 X ² + g1 X + 1.

Rcgldr (talk) 02:44, 26 October 2011 (UTC)

This is addressed in the Forney algorithm article using the parameter c. Also see the BCH code article. Bobmath (talk) 03:41, 26 October 2011 (UTC)

Thanks. I was wondering if alternate generator polynomials and the related the c parameter should be noted somewhere on the RS wiki page, but since there's a link to the Forney algorithm, that is probably good enough. Rcgldr (talk) 05:48, 26 October 2011 (UTC)

Isn't a Reed–Solomon code always a narrow-sense BCH code, so c must be one? See BCH code#Special cases. If that's the case, then other values for c (such as 0) don't belong here. Glrx (talk) 21:07, 26 October 2011 (UTC)

DAT drives use generator polynomials with c = 0. The ancient floppy tape drives (QIC-40) used a (32,29) code with c = -1 (reciprocal polynomial with 3 parities). Some other computer peripherals use reciprocal polynomials, c = (N/2)-(n/2), N = number of symbols, n = number of parities (N and n are even numbers). These were all considered to be RS codes by the resident ECC experts at the time. The Forney algorithm article already explains how to deal with c ≠ 1, so an RS article reference about this could just link to the Forney article. Rcgldr (talk) 02:00, 27 October 2011 (UTC)

I think fcr (first consecutive root) and the logarithm base (often called the generator, but I find it confusing with the generator polynomial) should be addressed in the article since they both are critical parameters to encode/decode RS codes, along with the primitive polynomial, n and k. Lrq3000 (talk) 00:49, 24 June 2015 (UTC)

Error in definition in Euclidean decoder section?

From the article:

$\Lambda (x)=\Lambda _{e}x^{e-1}+\Lambda _{e-1}x^{e-2}+\cdots +\Lambda _{1}x+1$

The terms at the start have the subscript on lambda 1 higher than the power of x, but the $\Lambda _{1}x$ term has them matching. For working through the maths to get the matrix shown below in the article, I think the terms should actually be $\Lambda _{e}x^{e}$ . More references for this section would be appreciated.

It was an error, and it's fixed now, the subscript on both Lamba and Omega terms should match the power of x, in the example, starting with x^e since there are e error locators and e error values. I just noticed this myself and fixed it before visiting this talk page. The matrix part of the section was already correct. Thanks for catching this, as I didn't think anyone was following this article anymore. I thought I had a watch on both the article and the talk page, but never got a notice. Rcgldr (talk) 12:26, 22 October 2015 (UTC)

As for references, the key equation is similar to the Omega equation in Forney_algorithm. Doing a search for Reed Solomon extended Euclid Algorithm got a few hits, including this pdf file: [1] , which has a similar mistake to the one I made before: on page 47, the last term in equation 11 should be S_2t x^2t-1. The main issue is a derivation of the key equation, since the rest of the section follows from the key equation. Rcgldr (talk) 12:26, 22 October 2015 (UTC)

Another issue is that the Reed Solomon article uses t to represent the number of parity symbols, while most references and the Forney article use 2 t to represent the number of parity symbols. I didn't want to change the entire Reed Solomon article. Rcgldr (talk) 12:26, 22 October 2015 (UTC)

Wrong link? "function table"

Hi,

I think that the link to the "function table" page (in the "Basis" section) is pointing to an unintended place.

I'm not sure, so if I'm wrong, please ignore / delete this comment.

134.191.232.70 (talk) 09:47, 18 February 2016 (UTC)

I deleted the WL and tagged the section as unreferenced. I'm unfamiliar with "function table" terminology, but I don't have the time right now to chase it. Glrx (talk) 01:39, 20 February 2016 (UTC)

Basis

I removed this section since it basically described the original impractical decoder, which is now described as theoretical decoding procedure in a separate section. If a basis section is wanted, it should provide a simple description of the BCH like implementation of RS codes, but I'm not sure if a simple description is possible. Rcgldr (talk) 09:13, 30 March 2016 (UTC)

I approve of this decision ylloh (talk) 19:59, 30 March 2016 (UTC)

History

Credit and gratitude goes to Dave Forney for helping me find early references to the work done on RS codes. I updated the history section based on his efforts. Rcgldr (talk) 02:08, 2 April 2016 (UTC)

Decoder using discrete Fourier transform

This section was previously named decoding in frequency domain and it started off with the statement The above algorithms are presented in the time domain. However, time domain and frequency domain are concepts specific to the Fourier transform, but in this case, a discrete Fourier transform is being used to map a codeword into a set of syndromes (it's the same calculation).

This section previously included the statement By definition, a code word of a Reed–Solomon code is given by the sequence of values ... , which conflicted with the section titled The BCH view: The codeword as a sequence of coefficients, which is used to describe an encoder and three decoders that view a codeword as a sequence of coefficients.

The previous version did not include a clear explanation of how this procedure works.

A discrete Fourier transform maps a codeword into a set of $n$ syndromes $S_{0}$ , $S_{1}$ , ... , $S_{n-1}$ . These are the same syndromes as described in the other practical decoders. For the syndromes $S_{1}$ , ... , $S_{t}$ , the original codeword terms sum up to zero (because the generator polynomial has roots $\alpha ^{1}$ , ..., $\alpha ^{t}$ ), so those syndromes effectively become a mapping of the error terms. Those syndromes $S_{1}$ , ... , $S_{t}$ are used to generate an error locator polynomial, in the same manner as any of the practical decoder methods. The rest of the $n$ terms can be converted into a set of error values using the relationship between the error locator polynomial and syndromes. This allows the mapped codeword to be corrected, and mapped back using an inverse transform to produce a corrected codeword.

This method works, but I don't see what the advantage is. Each transform requires mapping $n$ terms, as opposed to mapping $t$ terms to generate syndromes. Generation of the error locator polynomial is the same. Generation of error values requires calculating $n-t$ mapped error values, as opposed to calculating $v$ non-mapped error values (using a method like Forney). Rcgldr (talk) 09:01, 6 April 2016 (UTC)

Need more explanation on the decoding and error correction process

In the "The BCH view: The codeword as a sequence of coefficients" section of the article, near the end of this section it says: "The receiver can evaluate $r(a)$ at the roots of $g(a)$ and build a system of equations that eliminates $s(a)$ and identifies which coefficients of $r(a)$ are in error, and the magnitude of each coefficient's error. If the system of equations can be solved, then the receiver knows how to modify the received word $r(a)$ to get the most likely codeword $s(a)$ that was sent."

What is the process for "building a system of equations"? I was going to use the info provided in this wiki article to build an implementation of Reed Solomon in this software I'm writing. However, I'm only able to implement the encoding part, not the decoding part, because of the lack of information in this wiki article related to actually building and solving that system of equations it mentions, and construct a fixed polynomial based on it. And that's the problem. It only mentions the process It doesn't describe it. How can I implement a process, without knowledge of how that process works? Benhut1 (talk) 18:29, 2 August 2016 (UTC)

The process for building a system of equations is described in Reed–Solomon_error_correction#Peterson.E2.80.93Gorenstein.E2.80.93Zierler_decoder . As noted, solving the system of equations using this classic approach involves inverting a matrix or the equivalent. The Berlekamp-Massey or Euclidean type decoders avoid having to invert a matrix. Rcgldr (talk) 00:19, 9 August 2016 (UTC)

Remove em dash from title

The em dash in the article title breaks many auto-linkers; I think using a normal dash (-) would be much better. 2602:252:D79:2010:EC67:F33E:5BDE:D7AB (talk) 19:21, 17 December 2016 (UTC)

The house style is to use an endash (– and not an emdash &emdash;). See MOS:DASH. There is also an article with an ordinary hyphen (Reed-Solomon error correction) that redirects to this article (Reed–Solomon error correction), so a link using a hyphen rather than an endash will get to the right place. Glrx (talk) 20:33, 23 December 2016 (UTC)

Original view decoders

There are practical (polynomial time) decoders based on Reed Solomon original view of a codeword as sequence of function values that the RS article previously did not mention. I created a new section for these decoders, moving the theoretical "most popular" algorithm to this section as well as adding descriptions of two practical decoders. Rcgldr (talk) 01:39, 13 January 2018 (UTC)

List or soft decoders

There are also "list" or "soft" decoders first documented by Madhu Sudan back in 1996 which I referenced in the history section. I've seen references as recent as 2012 in efforts to improve the performance of such decoders. "list" refers to the fact that a list of potential polynomials that go through at least n-e points of $(a_{i},b_{i})$ where $a_{i}$ represents the set of fixed values and $b_{i}$ represents the received message values. Note this goes beyond the classical (n-k)/2 limit for error correction. "soft" is used to distinguish between list type decoders versus classical "hard" decoders which generate a single polynomial or detect an uncorrectable error. Rcgldr (talk) 01:39, 13 January 2018 (UTC)

Constructions, n ≤ q versus n < q

For Reed Solomon using the original view, the restriction is n ≤ q, where n is the code word size, and q the number of elements in a field. In the case of n = q, the values 0 to q-1 are input values and the message based polynomial is used to calculate the n value code word, c₀ to c_n-1. Rcgldr (talk) 10:10, 21 January 2018 (UTC)

For Reed Solomon using the BCH view, the restriction is n < q, due to the cyclic nature of detecting errors by dividing by a generator polynomial (or it's factors), which cycles every q elements. As a minimal example, consider the field GF(2^2), a field modulo 1 x^2 + 1 x + 1 with generator polynomial (1x + 1)(1x + 2) = 1x^2 + 3x + 2. Attempt to use it with a code word of size 4 == n == q. Consider decoding the single error code words {e,0,0,0} or {0,0,0,e}: dividing either code word by (1x + 1) or (1x + 2) results in the same syndrome value, S₀ == S₁ == e. With a code word of size n = q, there's no way to distinguish error values between the first and last coefficients of a code word. Another way to look at this is that the error locator polynomial uses powers of the primitive α or it's inverse to locate errors, which restricts the number of possible error locator values to q-1, since α raised to any power can't equal 0. Rcgldr (talk) 10:10, 21 January 2018 (UTC)

I recommend noting this in the Construction section, with less verbiage, with links to citable sources. Rcgldr (talk) 10:10, 21 January 2018 (UTC)

Euclidean Division Algorithm Decoder

This alternative method is simpler to implement than the Berlekamp Massey algorithm. The algorithm is described in several books, web sites and also in NASA Tech Brief article MSC-21834 (which seems to be missing title page and author) a Tutorial on Reed Solomon Error Correction Coding. I found what appears to be an updated version of the same pdf file here, the author is William Geisel, and a web search for his name will get a few hits on the tutorial:

nasa_archive_19900019023.pdf

Rcgldr (talk) 11:38, 11 October 2011 (UTC)

Go ahead and add it. Berlekamp–Massey is really pretty simple, but the operation of the Euclidean algorithm may be easier to understand. Bobmath (talk) 12:48, 11 October 2011 (UTC)

It might be better to simply post a reference to the tutorial at the nasa site for the near term, although that's based on binary type fields (the examples use 4 bit coefficients). I'd probably used the decimal based example for the Berlekamp Massey algorithm in the wiki article, but I'll need to create a program to make sure the results are ok, and I'm not sure how to get the pretty formatting with a fixed size font I'd want to show the division steps, probably as a pair of shift registers. Rcgldr (talk) 19:50, 11 October 2011 (UTC)

Euclidean section added. Kept it simple. Euclidean_decoder Rcgldr (talk) 05:45, 15 October 2011 (UTC)

Euclidean section updated to show a key equation that the algorithm is based on. The key equation is similar to the Omega formula used in the Forney article. Rcgldr (talk) 20:36, 29 October 2015 (UTC)

Thanks to Bobmath (page does not exist?) for cleaning up the the Euclidean section. Rcgldr (talk) 15:19, 15 October 2011 (UTC)

I'm not done yet :) Bobmath (talk) 15:39, 15 October 2011 (UTC)

OK, it looks better now. The while statement improves the readability since it handles the all zero syndrome case. It also matches the code I actually use.

Moved the definition for t = number of parities to the start of the algorithm description. Rcgldr (talk) 16:57, 15 October 2011 (UTC)

I didn't mention the failure handling, but I don't think that's needed for the article. The first check after the loop: if (degree_of(S_i)) != (-1+degree_of(A_i)) then it's failed. If it's less, then Ω(x) has leading zeroes, which I've never seen in a valid case. If it's more, then there's a conflict in the syndromes. The second check: if (number of valid roots of Λ(x)) != (degree_of(Λ(x)), then there are too many errors. The final check is regenerating sydromes or re-encoding, but I haven't seen this fail after getting past the first two checks. Mis-correction can occur if the garbled message is close enough to a valid message (in this case, the number of errors after mis-correction will exceed the number of parities). One mystery to me is why S_i needs to be negated to produce Ω(x) for odd error cases (the (-1)^{deg A_i} term), but it beats having to do a full Ω(x) calculation. I and most of the people I've worked with generally prefer the Euclidean algorithm.

Rcgldr (talk) 16:57, 15 October 2011 (UTC)

I forgot to update this part of the talk section. The "mystery" about negation for odd error cases was due to a bug in the described extended Euclid algorithm steps, which was fixed back on September 4, 2015, but not noted here in the talk section. Rcgldr (talk) 17:19, 21 January 2018 (UTC)

sample output of Euclidean algorithm, using two shift registers. Each register holds two values, the current remainder on the left, and a reversed polynomial (built up using the quotient values from the remainder divisions) on the right, that ends up as the error locator polynomial.

dividend=>   001 000 000 000 000|001 <= reversed polynomial
divisor=>    000 925 762 637 732|000 

dividend=>   925 762 637 732|533 232 
divisor=>    000 683 676 024|001 000 

dividend=>   683 676 024|544 704 608 <= A(i) = reversed locator polynomial 
divisor=>    000 673 596|533 232 000 

remainder=>  673 596|533 232 000 000

A(i):        544 704 608
omega:       673 596
A(i)/544:    001 821 329
omega/544:   546 732

Rcgldr (talk) 19:47, 4 February 2017 (UTC)

Properties

The paragraph that starts with "For practical uses of Reed–Solomon codes ..." needs an update, since there are practical original view decoders such as Berlekamp Welch, Gao, ... , not previously included in the article. "symbols per block" should be "symbols per codeword". For an 8 bit symbol field, original view RS code can use up to 256 symbols per codeword, and BCH view RS code up to 255 symbols per codeword. Although a cyclic code would require exactly 255 symbols and could be shortened by replacing the missing leading symbols with zeroes, I'm not sure if this is a detail needed at this point in the article. Typical BCH view encoders and decoders work with shortened codewords without special modifications, other than a decoder that generates a locator that is outside the range of a shortened codeword would report that an uncorrectable error has been detected. Rcgldr (talk) 17:38, 24 January 2018 (UTC)

Remarks

This section should be moved to after the properties section, since it references concepts introduced in the properties section. Rcgldr (talk) 18:03, 24 January 2018 (UTC)

Shortened codewords only need padding with zeroes to preserve the cyclic nature of a cyclic code. Both original view and BCH view RS algorithms don't rely on the cyclic nature of a cyclic code and can operate with RS(n,k) codes without any special treatment for shortened codewords, other than decoders that generate error locations outside the range of a shortened codeword report an uncorrectable error. Rcgldr (talk) 18:03, 24 January 2018 (UTC)

Berlekamp Massey decoder

I shortened the description on this section to just reference Berlekamp–Massey algorithm. That reference, along with the example should be good enough for the Reed Solomon article.

The Berlekamp–Massey algorithm article, has a decent description for the binary case, but just a code fragment for the more general case. Perhaps that article could be updated with something like the text below. Since I previously wrote a basic description here, I'm leaving it on this discussion page for now:

The Berlekamp Massey algorithm calculates a discrepancy based on a subset of v+1 syndromes, S_j ... S_j+v and a set of v coefficients, where v is the current number of assumed errors and initially set to zero:

discrepancy = S_j+v + Λ₁ S_j+v-1 + Λ₂ S_j+v-2 ... + Λ_v-1 S_j+1 + Λ_v S_j

This discrepancy as well as some internal variables are used to decide if v needs to be increased and/or if the coefficients need to be updated on each iteration. j is initally set to zero and advanced as needed during iteration so that all syndromes are used in the algorithm. When the algorithm completes, there will be v coefficients, and {1 Λ₁ Λ₂ ... Λ_v} will be the coefficients of the error location polynomial, Λ(x).

Rcgldr (talk) 07:06, 16 October 2011 (UTC)

If anyone is interested, I added an algorithm description to Berlekamp–Massey algorithm

Rcgldr (talk) 00:27, 19 October 2011 (UTC)

Article statement - The Berlekamp Massey algorithm is the most popular procedure for finding the error locator polynomial. - Based on my experience as a firmware programmer for computer peripherals, I have the impression that the Euclidean algorithm is most popular. Going by the Wiki standard, is there any reference than can cite the popularity of any single algorithm? Also does most popular mean it's used in the most devices or used in the most number of implementations of RS codes for different device types? Rcgldr (talk) 17:38, 19 October 2011 (UTC)

As far as I know Berlekamp-Massey is more suitable for hardware implementation than Euclidean as it lends for implementation with linear shift registers. Since RS is dominantly used in electronic consumer products that statement should be true. I assume that should be verifiable via Google as I don't have a reference at hand right now (and no time to get involved in editing this article at the moment). Nageh (talk) 18:38, 19 October 2011 (UTC)

If you look at the sample output shown in the Euclidean Division Algorithm Decoder section above, you can see the shift register implementation typically used in hardware. There are two shift registers, fixed in size (2 + # parities), with an index for each register used to separate each register into it's R(x)/A(x) or S(x)/B(x) poynomials. In addition, you get the error valuator polynomial for free (it's S(x) / low order term A(x)). I first started seeing Euclid method around 1989. In the meantime, I updated the intro for Berlekamp Massey with a proper description of the algorithm and just mentioned it's an alternate interative procedure. Both algortihms are popular, but I've only personally seen one instance of Berlekamp Massey used, versus several instances of Euclid used, while your experience is obviously different. I'm not sure it's important to pick which one is most popular. Rcgldr (talk) 19:36, 19 October 2011 (UTC)

You are right, I thought Berlekamp-Massey would be most popular but based on a quick search it seem that both are about equally popular. Regarding which one is more suitable for hardware implementation, here is a paper that states that Berlekamp-Massey is thought to be more efficient while Euclidean is simpler: [2] It also shows that both algorithms are ultimately equivalent via some reformulations. I agree that both algorithms can be implemented using linear shift registers, so the difference is probably not that big in the end. Nageh (talk) 20:21, 19 October 2011 (UTC)

The hardware guys hate having to turn chips, so they often prefer simpler. Each algorithm needs some checks to handle failure cases caused by too many errors. In the case of most failures, Λ(x) will still be unique, and all algorithms produce the same Λ(x), so in that sense, they are equivalent. If too many syndromes are zero, (an e error case can result in e-1 zeroed syndromes), then there are multiple Λ(x)'s that will satisfy S__i + Λ₁ S_i-1 + ... = 0, but none of them will be valid, and the different algorithms will produce different Λ(x)'s (or fail to produce one), but in these cases, failure will be detected, and the produced Λ(x)'s ignored. Berlekamp Massey iterates once per number of syndromes. Euclid only iterates once per number of errors, but there's more data involved in each iteration. I'm not sure of the tradeoffs in a mostly hardware impelentation. There's also a wiki article for Berlekamp–Welch_algorithm, which I'm not familiar with. It's been a while since I've worked with RS codes. Rcgldr (talk) 23:51, 19 October 2011 (UTC)

The Berlekamp–Welch_algorithm article didn't make it clear that it is an original view decoder, and I didn't follow up on it at the time. Recently, I did a rewrite to clean it up and added a reference and example in the Reed Solomon article, as well as Gao's improved extended Euclid algorithm for an original view decoder. Rcgldr (talk) 16:36, 30 January 2018 (UTC)

Article statement - A linear feedback shift register is constructed which produces the nth syndrome S_n as output after reading S₁...S_n−1 as input. The feedback coefficients of this shift register are the coefficients of the error locator polynomial. - That's not how it's described in the wiki article or any text (or actual implementation) that I'm aware of. The normal implementation is calculate a discrepancy, d = Λ₁ S_i ... + Λ_e S_i+e where e is the number of errors. I added an algorithm description that matches the coding examples in this article: Berlekamp_Massey_algorithm. I can cite references: Error Correcting Codes - Peterson and Weldon, second edition, page 290, equation 9.31; nasa_archive_19900019023.pdf - William A Geisel, page 66. Rcgldr (talk) 17:38, 19 October 2011 (UTC)

I had Gill's lecture notes (from the reference section) in mind when I wrote that, but I may not have chosen the best wording. I felt that something should be added because there's a conceptual jump from polynomials to shift registers that was pretty jarring. I'm not sure whether the present wording smooths that out. Bobmath (talk) 19:45, 19 October 2011 (UTC)

Glrx has added the section on the Peterson decoder, I have only added some material on soft decoding and list decoding at the end of the decoding section. Much of the text in between needs review and corrections, so feel free to go ahead if you feel you can improve it. Nageh (talk) 18:38, 19 October 2011 (UTC)

Peterson decoder section seems ok to me. As mentioned, I updated the intro description for Berlekamp Massey. There's also an iterative procedure for finding the error evaluator polynomial (Ω(x)) which isn't mentioned at all on the RS page. A similar procedure is more often used to generate a matrix that produces error values given a set of syndromes, to be used in multi-layer RS implementations where a set of columns in an RS matrix all share the same erasure locations, which are the rows of the RS matrix. Rcgldr (talk) 20:01, 19 October 2011 (UTC)

Duality of the two views - discrete Fourier transform - should be deleted

This section is mis-leading as it falsely implies that Fourier transform or inverse Fourier transform could be used to map between the original view and the BCH view. Rcgldr (talk) 22:32, 26 January 2018 (UTC)

For the original view, for the Fourier stuff to work, the evaluation points need to be restricted to αⁱ for i = 0 to n-1. Systematic encoding can use Lagrange interpolation instead of inverse transform, without the restriction on evaluation points. Fourier transform just re-encodes data using the generator polynomial. So the Fourier stuff for original view is not only redundant, it places a restriction on the evaluation points, which can normally be {0, 1, ..., n-1} in any order with n ≤ q. Rcgldr (talk) 22:32, 26 January 2018 (UTC)

For the BCH view, the Fourier transform is the same calculation as syndromes, other than it calculates n syndromes instead of t syndromes. There's no need for an inverse transform or Lagrange interpolation on the n syndromes, and the inverse transform may not work (since BCH view is not based on evaluation points). Lagrange interpolation would just map the n syndromes back to the original received message (including the error values). Lagrange interpolation on the received message would generate a polynomial of degree < n, but BCH view doesn't make use of such a polynomial. Rcgldr (talk) 22:32, 26 January 2018 (UTC)

BCH decoders already mention a Fourier based decoder. Rcgldr (talk) 22:32, 26 January 2018 (UTC)

A section on Fourier transform could be added to the original view section, noting the restriction on evaluation points, but the original view encoders and decoders in the article don't use Fourier transforms. Rcgldr (talk) 22:32, 26 January 2018 (UTC)

I removed the "duality" section and added a Fourier section to original view section. The Fourier stuff is somewhat pointless, as it's a duplicate of the described original view encoder, and the BCH Fourier decoder relies on standard BCH decoders in order to generate the error locator polynomial. I don't know if there's a way to directly perform a correction with a Fourier transformed BCH view, and assuming it is possible, what advantage it would have over the current BCH decoders. Rcgldr (talk) 16:42, 30 January 2018 (UTC)

RS original view theoretical decoder

This section mentions finding the most popular polynomial by checking all subsets of n elements taken k at a time, and notes it's impractical for a case like RS(255,249), a 3 error handling code that would require 359 billion subsets. However, an alternative would be to look for all subsets of n elements taken n - e at at time, where e is the maximum number of errors the code handles. Using the example, the number of subsets would be comb(255,252), still large at 2 million, but far smaller than the 359 billion. With this approach, if there are e errors, there should be only one sub-set that produces a polynomial of degree < k. The rest of the sub-sets would include one of the errors, and I don't think it's possible for a subset with an error term to correspond to a polynomial of degree < k. I don't know if Reed Solomon original concept for a decoder included this alternative, or if it would always work (assuming total number of errors ≤ e. Using the RS(7,3) examples, there would be 35 subsets of 3 elements, or 21 subsets of 5 elements. Rcgldr (talk) 09:02, 12 March 2018 (UTC)

Article clean up due to including both original view and BCH view decoders

Reed Solomon codes can be based on either the original view, or the BCH view. The article previously focused on the BCH view, since it didn't include any practical original view decoders (these are slower than BCH view decoders, but still practical). I've since added the practical original decoders to the article, and also cleaned up the article to cover both original view and BCH view. For some reason, the more recent developments have been based on the original view, including list decoders, but most current implementations of Reed Solomon codes are BCH view. The original view decoders are slower, the easiest case to compare are Sugiyama's extended Euclid algorithm for BCH view and Gao's extended Euclid algorithm for original view. The Gao algorithm is about (n/(n-k))^2 slower than the Sugiyama algorithm, and it also need space to hold n+2 elements as opposed to (n-k)+2 elements during the process. Rcgldr (talk) 20:02, 15 March 2018 (UTC)

I'm wondering if and where a note in the article that most current applications (CD, DVD, hard drives, ...) are BCH view, that BCH view decoders are faster and require less space than original view decoders, but that more recent research such as list decoders are based on original view. For RS(n,k) when n is relatively small, the speed and space overhead of original view isn't much of an issue, and there may be an advantage of decoding beyond the normal limits (such as list decoders), but I haven't found a good reference for this, as it appears the research is ongoing. Rcgldr (talk) 03:26, 30 April 2018 (UTC)

The lead now mentions BCH view is most common. I've since found that list decoders provide a list of possible original view polynomials that could correct otherwise uncorrectable data, but don't have a means of specifying which polynomial in a list would be the most likely polynomial. There are cases where a list decoder only finds a single polynomial of degree less than k, but it's not a guarantee that it is the correct polynomial. Rcgldr (talk) 14:53, 26 May 2018 (UTC)

Lead is too complicated

It's a mathematical subject and mathematics has its own language but I feel that the lead should at least be understandable by any intelligent reader. However, it contains this: "or correct up to ⌊t/2⌋ symbols" without any explanation of the symbols used. I don't know what it means and I can't even enter it into Google to find out. Could someone please rewrite it in English? 83.104.249.240 (talk) 02:53, 29 April 2018 (UTC)

I'll take a look at this later. Another issue in the lead is that original view Reed Solomon code is not cyclic (except for the case where the set of evaluation points are successive powers of α). The lead should define symbols as being values in a block of data treated as elements of a finite field. Rcgldr (talk) 17:55, 29 April 2018 (UTC)

I updated the lead section to define the terminology used in the article. Rcgldr (talk) 14:53, 26 May 2018 (UTC)

Short Bursts?!

From the article: "Viterbi decoders tend to produce errors in short bursts."

That's not good I guess. May someone comment on this statement? --Abdull 07:19, 16 October 2005 (UTC)

I added a link to the Viterbi decoder article from that sentence. The statement is true, but should probably be discussed in one of the Viterbi articles, and then cited from here. The following statement in the article that 'Correcting these burst errors is a job best done by short or simplified Reed-Solomon codes.' seems to deserve a citation or a bit more discussion. Edurant 13:25, 10 October 2006 (UTC)

I agree. So I added a sentence about error bursts to the Viterbi decoder article, with a reference. --DavidCary (talk) 05:17, 22 December 2019 (UTC)

Reed & Solomon's original view ... choice of evaluation points

From the article: "In many contexts it is convenient to choose the sequence a₁, ... a_n, of evaluation points so that they exhibit some additional structure ... sequence of successive powers of a primitive root α ", but for the original view encoding and original view decoders mentioned in the article, any permutation of the values {0, 1, 2, ..., n-1} can be used for evaluation points. For example, in The Original View of Reed–Solomon Codes, the sequence starts off with 0, which is not a power of α. Rcgldr (talk) 09:19, 22 January 2018 (UTC)

Thanks for the comment. I agree that the "in many contexts.." is too vague, so I changed the wording from when I wrote this 5 years ago (wow). Feel free to modify further. However, it is a relevant theoretical feature of RS codes that they can be made cyclic in this way and this paragraph is the only place where it is explained why they are cyclic, so I'd rather keep the paragraph here or somewhere else in the article. Of course, I don't see why the order of evaluation points would matter at all in practical applications and this intuition agrees with your implementation experiences, so I added a remark that it doesn't matter in practice. (ideally, this remark should be supported with a reference)

I was initially concerned about rotation of a cyclic codeword changing the generator polynomial, although not it's degree, but then thought about the fact that only the evaluation points are shared between encoder and decoder and not the polynomial, so the polynomial coefficients change, but it's still a valid codeword, and an original view decoder will still work (I verified this with Berlekamp Welch and Gao decoders in yet another program I wrote). I then deleted the paragraph with the intent of moving it closer to the start of the original view section, where I added a partial list of common choices for sets of evaluation points (based on original decoder references), but restored it back to it's original spot, as I don't know if it's a common choice, since I could only find examples where the goal was how to make original view RS code cyclic as opposed to actual decoder algorithms. I changed the last sentence of the paragraph to note that the original view decoders in the article don't require a cyclic code and can use any set of n ≤ q distinct values of the field F, including 0. Rcgldr (talk) 12:25, 24 January 2018 (UTC)

If you include 0 as an evaluation point, the code is not cyclic. This is why 0 is excluded. Since the fact that RS can be made cyclic is a little bit of a distraction, I moved this discussion to the end of the "Properties" section. ylloh (talk)

I should have made it more clear that including 0 or changing the order would make the original view code non-cyclic. It's gone now and not needed since the discussion has been relocated. The first sentence of the relocated discussion ends with "make the code cycle", should that be "make the code cyclic"? I'm thinking "classical view" should be "original view" to be consistent with the rest of the article. The statement "all non-zero elements of F take the form αⁱ for i ∈ {1, 2, ..., q-1}" is the equivalent of "... i ∈ {1, 2, ..., 0}" (since α^q-1 = α⁰ = 1). Perhaps this could be changed to " ... i ∈ {0, 1, 2, ..., q-2}". The discussion could include the statement that "Reed Solomon BCH view is inherently cyclic, since BCH codes are cyclic". Rcgldr (talk) 17:08, 24 January 2018 (UTC)

ylloh - I don't see the point of making an original view RS code cyclic, as none of the decoders mentioned in the article rely on a cyclic code. There are erasure codes based on modified Vandermonde matrices that would avoid 0 as an evaluation point, but the purpose is not to create a cyclic code but to ensure that any k by k sub matrix of a n by k encoding matrix for an original view RS code is invertible. I don't know the reasoning behind these codes (such as some forms of jerasure), since the methods based on Raid 6 (original, 3 or 4 parity Raid 6 variations) are more efficient. Rcgldr (talk) 04:55, 5 August 2020 (UTC)