Talk:Reed–Solomon error correction

Shortened DVD

I am a new to Reed-solomon. Until recent,I am required to implement Reed-Solomon code on FPGAs. This will be used in our DVD project. However, I have some questions puzzling me greatly. In DVD error correction coding ,should RS(208,192,17) and RS(182,172,11) be shortened or puntured Reed-Solomon codes. I have no way to differentiate the two. Meanwhile, I have great eagerness to comminicate and discuss with others about ECC especially Reed-Solomon codes. My email is skycanny@hotmail.com

Regards!

Cross-interleaved coding

Is CIRC also used on DVDs.

Duality of the two views

• Changed the name of this section to duality of the two views. I'm not aware of any practical decoder that does not require the usage of a known fixed generator polynomial, usually of degree n-k, and views a codeword as a set of coefficients. Once a codeword is created, then a polynomial that views a codeword as a sequence of values can be created using an inverse Fourier transform, but that polynomial varies depending on the codeword, making it unknown to the decoder, which creates an impractical situation where the decoder has to try sub-sets of n values taken k at a time to find the most popular polynomial. Note that although the most popular polynomial method was mentioned in the original article by Reed and Solomon, a pratical decoder using a fixed generator polynomial of degree n-k for encoding and decoding was described by by Daniel Gorenstein and Neal Zierler as early as January 1960 Reed–Solomon_error_correction#History. Rcgldr (talk) 03:16, 4 April 2016 (UTC)

This section could be misleading. Although there exists a duality that allows the same codeword to represent the coefficients of a polynomial and at the same time to represent the values of a different polynomial (this could be done using Lagrange interpolation), the issue is with the method of encoding. With the original encoding scheme, a practical decoder was never discovered. At about the same time (1960), a practical decoder for BCH codes was already discovered and probably influenced RS codes to switch to using a generator polynomial of degree n-k and viewing codewords as coefficients of polynomials Rcgldr (talk) 09:59, 30 March 2016 (UTC)

I'm not sure what you are proposing here. The two views result in the same set of codewords, which is what is meant by "equivalence". It does not mean that the encoding functions are identical. Regarding the historical details, if you have more correct information on them, feel free to clarify. ylloh (talk) 19:59, 30 March 2016 (UTC)

The prior sections in constructions describe different encoding schemes based on the view of the codeword, so the codewords generated using either of the two encoding schemes described in the codeword viewed as a sequence of values are not the same as the codewords generated using the encoding scheme described in the codeword viewed as a sequence of coefficients. The issue is that those two sections that describe the different encoding scheme(s) used for each view is followed by a section that states the two views are equivalent. It should be clarified that codewords produced as described in the prior sections are not the same. Rcgldr (talk) 21:58, 30 March 2016 (UTC)

I haven't been able to find the historical details. At some point in time, the RS encoding scheme was changed to use a generator polynomial, which is required for any of the practical decoders (Peterson, Berlekamp - Massey, Sugiyama) to work. The only related dates I could find are 1960 for the Peterson decoder for BCH code (for a 2 bit correction scheme, so probably before the change was made), and 1969 for the Berlekamp - Massey decoder for RS code (after the change was made). Rcgldr (talk) 21:58, 30 March 2016 (UTC)

I created a separate section for talk about the history below. Rcgldr (talk) 00:30, 4 April 2016 (UTC)

With original view for $GF(q)$ codewords can have up to $q$ symbols, while BCH view can have up to $q-1$ symbols, so it's not the same set of codewords. For some fields, using $q-1$ symbols, it is possible to have identical encodings. I'm adding a talk section about this. Rcgldr (talk) 10:05, 22 October 2024 (UTC)

Duality of the two views - inverse transform equation

Regarding the inverse transform equation for p(x), the equation is correct for non-binary fields $\textstyle v_{i}={\frac {1}{n}}q(\alpha ^{n-i})$, but for binary fields, the equation should be $\textstyle v_{i}=q(\alpha ^{n-i})$,

The issue depends if the field is a a non-binary field, such a a field modulo (929) as used in the examples versus a binary based field GF(2^n) where addition is effectively xor. As a simple way to explain this, for a non-binary field: $\sum _{i=1}^{n}1=n$ but for a binary field where n is an odd number $\sum _{i=1}^{n}1=1$ .

"Error correction" in title

Is there a good reason to include "error correction" in the title here? The current Applications section focuses on error correction, and those are probably the most notable applications, but there are some applications outside of correction, like key recovery, constructing MDS matrices, and some zero-knowledge argument protocols.

The article's scope already seems broader than error correction (e.g. it can correct up to t erasures); should we move it to "Reed-Solomon code" to reflect this broader scope? That would seem more WP:CONCISE and WP:CONSISTENT with Reed–Muller code, Algebraic geometry code, Expander code, etc. (which are also error-correcting codes). — xDanielx ^T/_C\^R 05:03, 29 July 2024 (UTC)