Talk:Reed–Solomon error correction/Archive 1

Archive 1

Archive 2

Archive 3

Clarification on the Values Stored in Data Symbols

I came here to learn about Reed-Solomon codes, and I found the article to be very helpful, but there is one thing I do not understand: Are the data symbols coefficients of the polynomial or coordinates of the plotted points?

The article says "The coefficients of the polynomial are the data symbols of the block." That seems clear enough, but if it's true, then I simply don't understand Reed-Solomon codes at all, and I'd welcome a lot of clarification.

If that sentence is not true, then I speculate all symbols are Y-coordinates of the plotted points (the parity symbols being coordinates of the oversampled points). That interpretation makes more sense to me. Is it correct?

68.6.61.250 04:54, 25 December 2005 (UTC)

I rewrote the start of that paragraph. Read it again and see if it is clearer. (I could tell you the answer, but if you still cant figure it out from the text, then we n need to fix the text further :) - grubber 05:14, 25 December 2005 (UTC)

Need More Info:

We need to clean up the references to to their inital paper.

--ReptileLawyer 15:11, 18 April 2006 (UTC)

Detectable Errors

RS is able to correct (n - k) / 2 errors.

How many errors in a segment he can detect 100% accurate?

(the algorithm is able to detect to a certain level, if he is not able to correct too many errors up too (n - k) / 2. Where is the limit?) —The preceding unsigned comment was added by 85.5.235.196 (talk) 10:55, 16 March 2007 (UTC).

======

Reed-Solomon codes are Maximum Distance Separable (MDS) codes, and are guaranteed to have a minimum distance of n - k + 1. So one can detect up to n - k errors with certainty.

Lack of detail

Compared to Hamming code, almost no detail is given on how to actually compute a Reed-Solomon code. Perhaps this should be considered for future addition. Shawn K. Quinn 13:16, 27 January 2007 (UTC)

I have added a more formal definition of a RS code. More details would be welcome! - grubber 19:59, 30 January 2007 (UTC)

Your formal definition wasn't complete. To be a Reed-Solomon code, the set $\{x_{1},\ldots ,x_{n}\}$ must be all non-zero elements of the field. I have added this to the definition. The more general class of codes where the points are arbitrary has the correct minimum distance, but the actual algorithm for finding the error locations relies on the additional property. Also, codes in the more general class are not called "Reed-Solomon" codes according to my references (does anyone know if they have a name? It's not polynomial codes because this means something else.) Selinger (talk) 01:52, 15 March 2008 (UTC)

Explanantion of author does not make sense

Try this from me --

A message stream of 'k' symbols is treated as a degree k-1 polynomial over GF(2^s) (GF(2^s)=galois field with n=2^s -1 ), with each symbol being coefficient of the said polynomial. This is referred to as 'message poynomial'(lets call it 'm(x)' with degree 'k-1'). There is another fixed polynomial with coefficients from the GF(2^s) called a 'generator polynomial' of degree 'n-k'. lets call it g(x). A code polynomial of degree 'n-1' (lets call it 'c(x)')is formed by the following algebra - c(x) = x^(n-k)*m(x)+r(x), where r(x) is remainder formed by dividing x^(n-k)*m(x) with g(x). It is clear now that c(x) divides g(x). This is true for any message stream. The coeffcients of c(x) are now called code symbols. Thus, a 'k' stream of symbols (message) is turned into a 'n' stream of symbols (code). This block of 'n' symbols that contains only 'k' useful message symbols is transimitted over the channel. The so called parity symbols are the 'n-k' coeffcients of r(x). The fact that any code polynomial is divisible by a fixed polynomial (=g(x)) is known to both sides, sender and the reciever. The reciever, knowing this property has the ability to extract the k symbols from the recieved 'n' symbol code block (even if up to '(n-k)/2' symbols have been corrupted).

-rajesh p.

What you are describing is a polynomial code. Reed-Solomon codes can be defined either as a polynomial code (from a generator polynomial as you suggest, or from given roots), or as the graphs of polynomials. The definition in terms of graphs is mathematically simpler (it doesn't require primitive roots of unity) and therefore probably more appealing for an encyclopedia. Most non-specialists can easily appreciate that low-degree polynomials have few roots, and this is the only mathematical fact really needed. However, the alternative definition in terms of a generator polynomial is important for the error correction algorithm, which is the real value of Reed-Solomon codes. I have therefore added a section on the alternative definition. Selinger (talk) 04:28, 15 March 2008 (UTC)

able to correct twice as many erasures as errors ?

"A Reed–Solomon code (like any linear code) is able to correct twice as many erasures as errors" I think it is true for Reed-Solomon but not for any linear code. This property is true for perfect codes ( Perfect codes are codes that reach the Hamming bound). I propose to change linear code into perfect codes. --Cunchem 15:23, 2 April 2009 (UTC)

Oli Filth

Provide an example of codeword + applied error(s) for an MDS code such that when decoded the resulting codeword is not equal to the original and where none of the undecodable criteria are met during the decoding phase. Until then that statement is invalid and will remain removed from the article. —Preceding unsigned comment added by NoNewsToday (talk • contribs) 21:24, 20 April 2010 (UTC)

This was a completely unqualified revert by User:NoNewsToday. An undetectable error (I suppose that is what you mean by decodable criteria) occurs whenever the error turns a codeword into a word that resides within the minimum distance of another codeword. The simplest case is that the error will turn one codeword into another valid codeword. The probability that an error turns it into the sphere of another codeword is already marginal (specifically it is at most 10^-5 for a standard (255,223) RS code for any given bit error probability). The probability that it turns it exactly into another codeword is even lower by a magnitude.

Nageh (talk) 21:39, 20 April 2010 (UTC) (Edit: Nageh (talk) 21:48, 20 April 2010 (UTC))

Perhaps I've missed some crucial point, but otherwise, of course there are error polynomials that will cause one valid codeword to be received as another.

Incidentally, please don't misuse the word "spamming". Oli Filth^{(talk|contribs)} 21:41, 20 April 2010 (UTC)

Please provide either an example (codeword and error index and magnitude) or citation (legitimate source ie: Lin&Costello et al) to this statement. Otherwise it will be reverted, I'll give guys 24hours. —Preceding unsigned comment added by NoNewsToday (talk • contribs) 00:02, 21 April 2010 (UTC)

Your request for a single error index and magnitude shows that you misunderstand the issue. If there were only one error and n-k >= 2, then that error would be corrected. The problem is there can be as many error indices and magnitudes as there are symbols. Every symbol in the message could have been corrupted.

For your example request, let C0(x) and C1(x) be arbitrary but distinct codewords. Transmit codeword C1(x). Let the transmission error E(x) = C0(x) - C1(x). (E(x) will have at least n-k nonzero coefficients, so the error is not guaranteed to be recoverable.) The received codeword will be R(x) = C1(x) + E(x) = C1(x) + C0(x) - C1(x) = C0(x). The receiver, seeing a legit codeword, will presume incorrectly that C0(x) was sent.Glrx (talk) 01:12, 21 April 2010 (UTC)

Glrx, there are two places in common and sane implementations of RS decoders that can detect and trivially reject codewords, for the scenario of a decoder RS(N,K) decoding errors <= K/2.

The first is the syndrome calculation - if its result is all 0 (zero) then there are no errors, the other is root calculation of lambda via Chien search, given a none all-zero syndrome if no roots are found or if the number of roots its greater than K/2. If a decoder does not adhere to these simple logical constraints, its not a valid decoder. Claiming the code can sometimes be erroneous is hence wrong.

Your explanation is that of an error-prone decoding process that has some serious logical flaws as to how the process occurs - I would suggest you read-up on the issue.

As I said before, the comment is not referenced, is in no way substantiated - and is nothing more than an assumption, so under Wiki rules its not even permissible. I would like to take this to a wiki moderator, as it seems just under those conditions it should be rightfully removed.

So lets all be a little sane and err on the side of caution and remove this reference until someone can rightfully substantiate or provide a valid citation for it. A substantial proof as I've explained before would be for a code RS(N,K) a codeword C and error vector e where |e| <= K/2 would decode using a sane decoder to C' where C is not equal to C' - if there is such a scenario please provide it as it would come contrary to some fundamental concepts in algebraic geometry - which would most definitely give the provider of such a scenario a big kudos boost in the math world. —Preceding unsigned comment added by NoNewsToday (talk • contribs) 20:40, 21 April 2010 (UTC)

And where in the whole world did you read anything about the assumption that the number of symbol errors must be < k/2? And do you think this is a civil discussion in any way from your side that you simple revert again? And do you actually have any theoretical knowledge on error correction coding? I think the answer is 'no' to all these questions.

Here is a ref for you: Kasami T.,Lin S., "On the probability of undetected error for the maximum distance separable codes." IEEE Transactions on Communications, 32(9):998–1006, 1984.

If you don't understand it I advise you to start Lin&Costello right from the beginning again.

Nageh (talk) 21:04, 21 April 2010 (UTC) (Sorry for being impolite.)

PS: I have already tried to explain to you above when such errors can happen. You have completely ignored this. I leave it to you as an exercise to compute the probability that on a binary symmetric channel with a certain bit/symbol error probability there are (a) more than k/2 errors, and (b) an error turns a code word into another codeword, and (c) an error turns a code word into the minimum-distance sphere of another codeword (in increasing order of difficulty). Good luck with your homework! Nageh (talk) 21:08, 21 April 2010 (UTC)

PPS: I would have accepted removal/rewrite of the footnote based on a statement like "The footnote is not clear or confusing because... " or "I don't understand why this is the case" but not because you just say that is an "invalid assumption". Nageh (talk) 21:11, 21 April 2010 (UTC)

The point I'm trying to make is that the comment should explicitly state that in the scenario where the codeword has more errors than what the code can correct - and yes I agree if there are more errors its possible to either detect none or even correct the codeword incorrectly. My position is that if the number of errors <= K/2 there is no way such an ambigious state can occur. So as a final solution either the statement needs to be more explicit by making it clear what the scenario (perhaps something similar to the statement in the CRC article), or not have it at all.

PPSS: this has a good discussion on the issue: http://ipnpr.jpl.nasa.gov/progress_report/42-84/84F.PDF if you like we can work together on some kind of wording on this page.

—Preceding unsigned comment added by NoNewsToday (talk • contribs) 21:20, 21 April 2010 (UTC)

The article (as far as I can see) states no such assumption on the number of symbol errors; consequently the footnote is neither ambiguous nor incorrect. Oli Filth^{(talk|contribs)} 21:30, 21 April 2010 (UTC)

The only situation where the comment is correct is if the number of errors is greater than K/2 either change the reference or removed it. Pretty simple.

This has already been elucidated; there is no need to state that, as there is no such assumption in the article.

Please also note that you're dangerously close to violating the 3-revert rule; please stop making the same change until you've gained consensus with the three editors who've been reverting you. Oli Filth^{(talk|contribs)} 21:39, 21 April 2010 (UTC)

I'd like to reference removed until we can come to some valid consensus

That's not how it works. Incidentally, I've now reported you for violating WP:3RR. Oli Filth^{(talk|contribs)} 21:55, 21 April 2010 (UTC)

Thanks, I was just about to do the same. Nageh (talk) 21:57, 21 April 2010 (UTC)

I believe we came to a valid consensus: three to keep the note and one to remove it. On the subject, I would give Nageh opinion great weight. He's made a lot of recent contributions to this article, and those edits demonstrate a clear and deep understanding of the subject. Furthermore, you now admit a correctly functioning decoder could calculate the wrong codeword if there were more that (n-k)/2 errors. Given your understanding of the note's viewpoint and its correctness, I fail to understand why you would revert it.Glrx (talk) 22:59, 21 April 2010 (UTC)

A last comment to NoNewsToday before I'm off. Mentioning that a decoding error for a code that can reliably correct up to k/2 errors requires more than k/2 errors is a pleonasm, so leaving out the additional statement introduces no ambiguity whatsoever, especially if no such assumptions are stated anywhere in the article. Bye, Nageh (talk) 22:10, 21 April 2010 (UTC)

MOS, MOSMATH, TeX, etc.

It almost seems as if someone worked really hard at being unfamiliar with WP:MOS, WP:MOSMATH, and standard TeX conventions. Lots of stuff like

Reed-Solomon

instead of

Reed–Solomon

and

$(a,...,b)\,$

instead of

$(a,\ldots ,b)\,$

and

(1, ..., a)

instead of

(1, ..., a)

and

n-k+1

instead of

n − k + 1

and so on. Probably more cleanup is needed. Michael Hardy (talk) 21:38, 27 April 2011 (UTC)

You would do a lot better spending time on making this articles easily understood and genuinely educational. Too many of them are written by idiots who have no idea of how to communicate unfamiliar concepts. WilliamSommerwerck (talk) 16:16, 4 June 2011 (UTC)

You, too, would do a lot better spending time on making these article easily understood instead of calling other well-meaning editors idiots! Nageh (talk) 16:24, 4 June 2011 (UTC)

Criticism accepted. I'll see what I can do. WilliamSommerwerck (talk) 22:02, 4 June 2011 (UTC)

Graphs

As I'm an utter programming layman(though one with a good intuition for math/logic), the concept was totally unclear until I hit the last section. Perhaps it could be moved up? —Preceding unsigned comment added by 67.101.43.231 (talk) 02:36, 17 May 2008 (UTC)

A burst in time domain isn't transfomed to a sine wave, instead it's transformed to a infinite number of frequencyies if the bursts rise time is infinite short. Look at this picture: http://members.optushome.com.au/walshjj/transform_pairs.gif So I think Figure 3 and 4 are wrong —Preceding unsigned comment added by 62.167.25.67 (talk) 15:35, 22 July 2008 (UTC)

A single-sided impulse in one domain transforms to a complex exponential in the other (i.e. $\ \delta (t+T)\leftrightarrow e^{j\omega T}$. The real projection of this is indeed a cosinusoid. Oli Filth^(talk) 15:43, 22 July 2008 (UTC)

While A single sided impulse in time is a complex exponential in the frequency domain, the sketch shows a square wave in the time domain. This is a sinc function in the frequency domain. it is wrong. — Preceding unsigned comment added by 64.129.125.134 (talk) 15:51, 10 August 2011 (UTC)

maximum burst error length

The Reed–Solomon error correction article currently claims "The result is a CIRC that can completely correct error bursts up to 4000 bits, or about 2.5 mm on the disc surface." which doesn't exactly match the cross-interleaved Reed-Solomon coding article which claims "CIRC corrects error bursts up to 3,500 bits in sequence (2.4 mm in length as seen on CD surface)".

What is the correct number? --75.37.227.177 19:52, 10 August 2007 (UTC)

I think this should be a simple calculation:

If I understand correctly, the CIRC is physically read off the CD (after EFM decoding) as large blocks, each large block a stream of 7 168 consecutive bits long.

Each of the 28 substrings of 256 consecutive bits is decoded as a "inner" RS code.

In a maximum-correctable-burst, several of those substrings are completely wiped out. One byte of each of those 28 substrings goes to a 28-byte "outer" RS code, which is decoded into 24 data bytes and corrects up to 4 byte errors.

So I get 4 * 256 = 1 000 consecutive bits that can be corrected in a CIRC large block. The maximum correctible burst occurs when the last 1000 bits are destroyed in one CIRC large block and the first 1000 bits are destroyed in the next CIRC large block, giving 2000 bits.

Where did I go wrong in this calculation? --75.37.227.177 19:52, 10 August 2007 (UTC)

This is about 4 years old and the conflict is not resolved. I assume there's a 4 way interleave on the outer code, allowing 4096 bit bursts to be corrected, of that 3072 are data bits. So I'm not sure where the 4000 and 3500 numbers originate from. Rcgldr (talk) 01:06, 14 October 2011 (UTC)

Explanation of syndrome calculation

For the Berlekamp-Massey algorithm example, the syndrome values are listed in the table, but how they are calculated is not explained. Here's an example of how syndrome 0 is calculated. Note all coefficients are modulo 929. I'm not sure if this somewhat lengthy section should be added to the main article:

syndrome 0 = r(x) modulo (x - 3) = r(x) modulo (x + 926) = 732

Using long hand polynomial division to calculate syndrome 0:

             003 011 156 924 176 086
        ----------------------------
001 926 |003 002 123 456 191 487 474
         003 920
          --------
             011 123
             011 896
             -------
                 156 456
                 156 461
                 -------
                     924 191
                     924 015
                     -------
                         176 487
                         176 401
                         -------
                             086 474
                             086 671
                             -------
                                 732

Rcgldr (talk) 09:47, 13 October 2011 (UTC)

Detailed discussion of the Berlekamp-Massey algorithm should go to the respective article. Basics such as a trivial polynomial (long) division have no place at either. Nageh (talk) 09:57, 13 October 2011 (UTC)

Thanks for pointing out the gap in the example. You actually don't need to use long division to calculate the syndromes, just evaluate the polynomial r(x). I've added a couple of lines to show that. Bobmath (talk) 14:38, 13 October 2011 (UTC)

Thanks for the update. For anyone that would actually be reading these articles, the long division example isn't needed, but is there any wiki article to show that evaluating r(x) with either the syndromes or generator polynomial is the equivalent to grinding it out with long division? Rcgldr (talk) 20:24, 13 October 2011 (UTC)

Polynomial remainder theorem. Bobmath (talk) 04:09, 14 October 2011 (UTC)

Article should include a summary of the algorithm

I think the article should include a summary of the algorithm for encoding and then decoding. If I understand the algorithm correctly, then this should be a valid summary:

Encoding:

1. Take the cleartext word you want to transmit, perhaps "123". The cleartext word must be k symbols (letters/numbers/characters, in this case digits) long.

2. Use the individual symbols from that cleartext word as the coefficients of a polynomial of degree k-1. So: p(x) = 1x^2 + 2x + 3

3. The code word (encoded word) will be n symbols long. In pseudocode:

For i in (1,2,3...n):

$next_symbol = p(i) = 1(i)^2 + 2(i) + 3

Write $next_symbol at the end of the code word

4. Transmit or store the code word.

Decoding:

1. Receive or read the code word.

2. "Graph" the code word by making a scatter plot.

3. Look at the graph, and see if it is smooth, low-frequency, and trustworthy.

If the code word was "12221000122210001", then your graph will look like a nice low frequency wave. You can trust there are no errors.

If the code word was "92221000122210001", then you will notice a big spike at the "9" which is way to high frequency to actually belong. The "9" must be an error.

4. Erase any stray points (like the "9" above), and then "connect the dots" with the remaining points.

5. You just drew a nice smooth curve. Use math tricks to find the polynomial that gives that curve. If you find the polynomial is p(x) = 1x^2 + 2x + 3, then the cleartext word must have been "123", the coefficients.

Do people agree that a cleaned-up (and if necessary, corrected) version of this should go in the article?Fluoborate (talk) 06:24, 12 June 2009 (UTC)

"cleartext" is not appropriate in this case, I think we should use "source data" or "source word" instead. The encoding part seems ok to me, but the step 3 confuses me: what is a smooth low frequency and trustworthy curves ? :) and what do you mean by connecting the dots? If I'm right the smoothness of the curves can be replaced by the fact that the curves correspond to a ploynomial of degree at most "n-1". If not, we are sure that at least one symbol is in error. The correction step will be to find the closest polynomial of degree at most "n-1" to this set of points. And the "math tricks" that you are speaking of is something like polynomial interpolation if I'm right. IMO it is interesting to have a simple presentation of the algorithm like this one, but we should also have a more mathematical and rigorous one. In addition, several approach are possible to encode RS codes, for exemple depending on the channel considered (BEC, or AWGN/BSC ...), and we should specify the type of error corrected by the algorithm. Cunchem (talk) 09:10, 12 June 2009 (UTC)

I'm a degreed EE, and have a decent math background. I remain amazed that people writing technical material refuse to provide simple explanations that would greatly clarify the mathematics. Consider CDs. They use Eight To Fourteen (ETF) encoding, where each eight-bit data byte is converted to 14 bits. That is, the 256 possible data values are mapped into a "space" of 16,384 values, which is more-resistant to corruption. The 14 bits are the coefficients of the polynomial. See how simple it is?

Of course, technical writers wouldn't dare give a simple explanation, because then they wouldn't look smart -- and the readers wouldn't be intimidated. WilliamSommerwerck (talk) 16:13, 4 June 2011 (UTC)

I know this is old, but perhaps William will read this some day. coding ... decoding - an example of coding and decoding is included in the article here: Example. They use Eight To Fourteen (ETF) encoding, where each eight-bit data byte is converted to 14 bits. ... The 14 bits are the coefficients of the polynomial. - The 14 bit pattern is used for a modulation scheme, Compact_Disc_Data_structure. Other than the last output and first input stages, everything else in the drive operates with 8 bit values, so the RS encoding and decoding would be working with 8 bit values. Rcgldr (talk) 14:37, 15 October 2011 (UTC)

Euclidean decoder

• Article statement - A_i(0) is the constant term of A_i. Changed from low order term to constant term. constant term could imply a coefficient that doesn't change during iterations. I would prefer low order term, but the example clarifies what is meant by A_i(0), which should be good enough. Rcgldr (talk) 18:00, 19 October 2011 (UTC)

"Low order" isn't a standard mathematical term, AFAIK, but I guess the meaning should be clear. The A_is don't change, anyway. Bobmath (talk) 19:25, 19 October 2011 (UTC)

I did a web search for polynomial lower order term and got quite a few hits. I also see this used for describing binary numbers, the low order bit or low order byte. Also some web pages refer to the coefficients of polynomials as constants, which gets confusing. The wiki article for Polynomial refers to terms of of a polynomial by degree, and calls the last term constant, so either seems ok. I don't want to call it term of zero degree. Rcgldr (talk) 20:41, 19 October 2011 (UTC)

Please avoid order, the order of a polynomial (or a group member) is something completely different. Constant term is good and unambiguous. I guess trailing term would be too, though it's not so common. Nageh (talk) 21:11, 19 October 2011 (UTC)

In that case constant term seems the best. trailing term or leading term could be confusing since A_i is shown reversed in the example. I show A_i reversed since that's typically how it's implemented in hardware or software. Rcgldr (talk) 21:23, 19 October 2011 (UTC)

A friend of mine complained about the usage of constant term so I changed it to constant (least significant) term in attempt to make everyone happy. I have a old handout taken from an ECC book and on page 299, its states A_i ... must be divided by it's low-order coefficient which is why I used that wording in the first place. There's a reference to a book, Error Correction Coding by Clark and Cain (Plenum Press), but I don't have that book. Rcgldr (talk) 00:42, 20 October 2011 (UTC)

error value calculations with multi-layer codes

In the case of a multi-layer code like CIRC, it's usually faster to generate a matrix for the outer code correction. Consider the inner code to be the rows of a matrix, and the outer code to the columns. The rows are handled first, and then correction on the columns of all rows can be treated as erasure cases, multiplying the inverted locator matrix with each column's syndromes to do the correction. If an error occurs in a column, then the failing row (once determined) can be added to the row erasure list, a new inverted locator matrix generated and correction continued. Expansion of terms from the Forney algorithm can be used avoid having to actually invert a matrix. For a 3 error case:

${\begin{bmatrix}X_{1}^{1}&X_{2}^{1}&X_{3}^{1}\\X_{1}^{2}&X_{2}^{2}&X_{3}^{2}\\X_{1}^{3}&X_{2}^{3}&X_{3}^{3}\\\end{bmatrix}}{\begin{bmatrix}Y_{1}\\Y_{2}\\Y_{3}\end{bmatrix}}={\begin{bmatrix}S_{1}\\S_{2}\\S_{3}\end{bmatrix}}$

${\begin{bmatrix}Y_{1}\\Y_{2}\\Y_{3}\end{bmatrix}}={\begin{bmatrix}-(1+\Lambda _{1}X_{1}^{-1}+\Lambda _{2}X_{1}^{-2})/\Lambda '(X_{1})&-(X_{1}^{-1}+\Lambda _{1}X_{1}^{-2})/\Lambda '(X_{1})&-(X_{1}^{-2})/\Lambda '(X_{1})\\-(1+\Lambda _{1}X_{2}^{-1}+\Lambda _{2}X_{2}^{-2})/\Lambda '(X_{2})&-(X_{2}^{-1}+\Lambda _{1}X_{2}^{-2})/\Lambda '(X_{2})&-(X_{2}^{-2})/\Lambda '(X_{2})\\-(1+\Lambda _{1}X_{3}^{-1}+\Lambda _{2}X_{3}^{-2})/\Lambda '(X_{3})&-(X_{3}^{-1}+\Lambda _{1}X_{3}^{-2})/\Lambda '(X_{3})&-(X_{3}^{-2})/\Lambda '(X_{3})\\\end{bmatrix}}{\begin{bmatrix}S_{1}\\S_{2}\\S_{3}\end{bmatrix}}$

Rcgldr (talk) 23:57, 26 October 2011 (UTC)

Reed Solmon article intro - Berlekamp Massey implied to be only efficient decoding algorithm.

From the intro section: where encoding symbols are derived from the coefficients of a polynomial constructed by multiplying p(x) with a cyclic generator polynomial. This gives rise to an efficient decoding algorithm, which was discovered by Elwyn Berlekamp and James Massey, and is known as the Berlekamp–Massey decoding algorithm. Seems the real breakthrough was discovering the relationship between the error locator polynomial and syndromes as explained in the Peterson_decoder section, where the Berlekamp method is mentioned as an improvement: ''Peterson (1960) developed a practical decoder based on syndrome decoding. ... Berlekamp (below) would improve on that decoder. So there's a conflict in the article. Seems like the intro section should be revised. The Euclidean based algorithm is yet another improved method, but not mentioned in the intro section. Rcgldr (talk) 08:19, 1 November 2011 (UTC)

The lead section is right, actually. Peterson's decoder does not scale well for larger number of errors. Also, it was only designed for binary BCH codes, originally. It was Gorenstein and Ziegler who extended Peterson's algorithm for the decoding of non-binary BCH/RS codes to what is now known as the Peterson–Gorenstein–Zierler algorithm. So it is the body of the article that primarily needs improvement. When it comes to notable algorithms, Chien search and Forney's algorithm also needs more attention. The Euclidean algorithm is less an improvement rather than an alternative to Berlekamp-Massey, but obviously needs more attention, too. Nageh (talk) 09:15, 1 November 2011 (UTC)

I second Nageh's characterization. The notion of "practical" is a moving target. The RS count-the-subsets decoder was impractical. The PGZ decoder is practical in the sense that it could be implemented, but it has an awkward error location polynomial step that examines several systems of linear equations (matrix ops are O(t³), so PGZ number of errors step is O(t⁴)?). The hardware to do that for many check symbols would be expensive. In contrast, the BM decoder's error location polynomial is simpler (O(t²)?). Glrx (talk) 17:06, 2 November 2011 (UTC)

Now that I've re-read both sections, the issue is "practical" versus "efficient". I think the linear RS method qualifies as "practical", assuming it is/was used in some devices. On page 105 of the cited RS tutorial (1990) 1990019023.pdf is a claim that for 3 (possibly 4) or smaller maximum error cases, an optimized linear method (the math worked out in advance for the determinants, eliminating xors of duplicate terms), would require less hardware than the iterative methods. The real breakthrough would seem to be the discovery of the relationship between the error locator polynomial and the syndromes, which the mentioned RS decoder algorithms (linear, BM, Euclid) are based on. The main exception would be single burst decoders that re-encode the received message and forwards or backwards cycle the re-calculated parities until the most significant half of the parities are zero, in which case the least significant half is the error value. The first section should also include Euclid as well as BM as an efficient algorithm. The Euclid method requires two shift registers of the same size as used by BM's main shift register, but BM needs a "previous" copy of Λ(x). Euclid iterates t=#errors times, while BM iterates N=#syndrome times. Euclid produces Ω(x), but BM and linear method require a second iteration to produce Ω(x). So it's a trade off in size versus speed. Rcgldr (talk) 04:03, 3 November 2011 (UTC)

unindent - I changed the title of this discussion section to BM implied to be only efficient algorithm. Perhaps the statement in question could be changed to This gives rise to efficient decoding algorithms (described below). This would avoid having to clarify the pros and cons of each algorithm in the intro section. Rcgldr (talk) 04:16, 3 November 2011 (UTC)

article section 4.2 - Peterson Decoder - 4.2.3 - Error locator polynomial

Quote from the end of the article: However, this method doesn't tell you the number of errors, v.

To determine number of errors with Peterson decoder, assume max error case (# syndromes / 2). If this is grearer than the actual number of errors, the matrix will be redundant and not be invertible (or check the determinant, which will be zero). In this case the procedure is to decrease number of errors by 1, and repeat this process until the actual number of errors (which could be zero) is determined.

Section 4.2.3 of the article should be updated with similar wording to explain how the number of errors can be determined using the Peterson decoder. Rcgldr (talk) 18:36, 23 January 2013 (UTC)

Done. Glrx (talk) 16:42, 24 January 2013 (UTC)

Thanks. Rcgldr (talk) 15:34, 2 February 2013 (UTC)

First paragraph - encoded message generated by division (modulo), versus multiplying?

From the first paragraph of the article:

Instead, RS codes are viewed as cyclic BCH codes, where encoding symbols are derived from the coefficients of a polynomial constructed by multiplying p(x) with a cyclic generator polynomial.

I realize that a large matrix multiply can be performed to encode data, but doesn't the BCH method normally involve multiplying the message p(x) by x^t (t is number of parity symbols to append to p(x)), then dividing this by the generator polynomial g(x), and appending the remainder to the message:

$s(x)=(p(x)\ x^{t})-((p(x)\ x^{t})\ |\ g(x))$

Rcgldr (talk) 04:59, 26 February 2013 (UTC)

Both methods can be used. The only important issue is that g(x) divide the transmitted polynomial. I believe it is more common for the sender to divide so that the transmitted message is in the clear. Some text that kept making that point has been removed. Glrx (talk) 02:09, 27 February 2013 (UTC)

Note - I editted this talk section so that it matches the names used in the rest of the article. Also, a large matrix multiply could be used for either encode method. The encode matrix would be smaller in the sender divides case.

I didn't read far enough. The sender divides method is covered in the later remarks section:

In this case, the t check symbols are created by computing the remainder, s_r(x):

$s_{r}(x)=(p(x)\times x^{t})\ {\bmod {\ }}g(x)$

and that remainder is used to make an evenly divisible codeword:

$s(x)=p(x)\times x^{t}-s_{r}(x)$

So the two methods are s(x) = p(x) g(x) or s(x) = ( p(x) x^t ) - ( (p(x) x^t) | g(x) ). Perhaps the first paragraph of the article should also mention the second method.

Rcgldr (talk) 14:49, 28 February 2013 (UTC)

• I moved that part of the "remarks" section to a new subsection systematic encoding procedure. There are many different encoding methods, each with their advantages and disadvantages. I think the lead section of the article should stay on a higher level and not dive into the details of any particular method. ylloh (talk) 17:08, 28 February 2013 (UTC)

In the new systematic encoding section:

multiplying p(x) by x^t to make room for the t+1 check symbols

but I think that should be

multiplying p(x) by x^t to make room for the t check symbols

If the lead section is to stay on a high level, it shouldn't mention a specific construction method such as multiping p(x) by g(x). The wording could be something like the encoded message s(x) is based on p(x) and g(x) and is constructed so that it is an exact multiple of g(x).

Rcgldr (talk) 10:19, 1 March 2013 (UTC)

Thanks, I corrected the +/-1 error. Your wording describes the two methods that we have in the BCH view well, but does not capture Reed & Solomon's original view. Maybe we should add a description of both views (but not the different encoding methods)? ylloh (talk) 14:37, 1 March 2013 (UTC)

unindent - I'm thinking that the lead section should just provide a basic description of current implementations of RS codes, and review the history in later sections. Rcgldr (talk) 20:15, 1 March 2013 (UTC)

There's an inconsistency in the ordering of coefficients. The convention I've normally used considers the coefficients from most signficant to least signficant, p(x) = p_(k-1) x^(k-1) + p_(k-2) x^(k-2) + ... + p_0. This is the convention used in the examples for Berlekamp–Massey decoder and Euclidean decoder, with the Euclidean decoder clarifing the ordering by stating that R and S are forward, A and B are reversed. From the earlier section, Systematic encoding procedure - the message as an initial sequence of values, it is stated that the first k entries of the codeword are exactly equal to x. In the section you added Systematic encoding procedure , first is changed to last : the k last coefficients are identical to the coefficients of p(x). Rcgldr (talk) 20:15, 1 March 2013 (UTC)

In theoretical computer science, the "classical" view of Reed-Solomon codes is still used today because it is somewhat more intuitive and elegant, so I wouldn't call it "history". I don't have a strong opinion on whether or not it should be mentioned in the lead.

You're right, there's now some inconsistency between the definition and the examples. I think the examples should always briefly mention which encoder is being discussed (in this case, a systematic BCH encoder with q,n,k set in some way). If there is a consensus in the relevant coding literature whether to write polynomials from left to right or from right to left, that consensus variant should be used in the definition sections. However, I suspect that one does not care about it and usually writes it from the smallest monomial to the largest because this leads to the cleanest notation. Maybe we can use the cleanest notation at first and then add the remark that the codewords in the systematic BCH code are reversed when it is used in practical applications (so that codewords always start with the message)? ylloh (talk) 21:27, 1 March 2013 (UTC)

My only issue with the lead article is that it mentions one specific method s(x) = p(x) g(x) but not the other s(x) = ( p(x) x^t ) - ( (p(x) x^t) | g(x) ), and this is in reference to BCH codes, and I had the impression that even "classic" BCH codes use s(x) = ( p(x) x^t ) - ( (p(x) x^t) | g(x) ). Using s(x) = p(x) g(x) is more complicated for both encoder and decoder. The encoder involves more data and/or a larger encoding matrix. The decoder would have do the equivalent of first correcting a received s(x), then dividing the corrected s(x) by g(x) to produce p(x). Rcgldr (talk) 23:29, 1 March 2013 (UTC)

In the articles and text books I've seen, when polynomials are written out as a series of terms, they are usually written with most significant term first (especially for examples of polynomial math such as long hand multiplication or division), even though when a polynomial is written as a sum (sigma) or product (pi) series, the series index normally goes from 0 to n-1 or from 1 to n. In the cases where it isn't clear what the order of the terms of a polynomial are, instead of using "first ... " or "last ... ", the terms "most signifcant ... " or "least signifcant ... " could be used. Rcgldr (talk) 17:14, 6 March 2013 (UTC)

Yes, the monomial order still needs some streamlining. Also, e.g., in the beginning the message is called "x" (conforming with other articles such as Hamming code or Hadamard code) and the variable is called "a" (conforming with $\alpha$, I suppose), and in later parts of the article, the variable is called x. I think a is not a good choice, but I'd prefer to call the message x. Maybe we can use capital "X" or "y" for the variable? What do you think? ylloh (talk) 18:19, 6 March 2013 (UTC)

polymonomial term order - This is already fixed. The ordering of terms is now consistent within the article.

Throughout most of the article, the original message is considered to be coefficients of a polnomial p(x). The conflict occurs in Reed & Solomon's original view section, where x is the message represented as a set of symbols, and where p(...) is described as a generator polynomial that produces a scalar to be evaluated at n points to produce a codeword C(x), but then defines $p_{x}(a)$ as a summation of the products of scalars $x_{i}\ a^{i-1}$. Rcgldr (talk) 23:11, 6 March 2013 (UTC)

Singleton bound?

So the singleton bound says delta + R ≤ 1. But if delta = 1 - k/n + 1/n, and R = k/n, then the formula reads: 1 + 1/n ≤ 1, which is only valid if n < 0. That doesn't seem right? 194.39.218.10 (talk) 06:28, 30 September 2013 (UTC)

Trivial typo, not sure but anyway I'm afraid to edit article page11:27, 24 July 2013 (UTC)80.221.245.225 (talk)

Near the top of the article:

"Furthermore, RS codes are suitable as multiple-burst bit-error correcting codes"

Shouldn't that be "multiple-bit burst errors" ?

Or maybe it's right the way it is.

80.221.245.225 (talk) 11:27, 24 July 2013 (UTC)

RS codes can handle multiple bursts; the error symbols may be scattered throughout the message. Some ECC codes are for single bursts within a block. Glrx (talk) 20:23, 25 July 2013 (UTC)

Those two sentences could be removed, since there's previous text explaining that an RS code can correct up to t/2 symbols. Perhaps that other sentence could include the wording any combination up to t/2 symbols. Rcgldr (talk) 12:40, 19 November 2013 (UTC)

Correcting error bursts is important, and that is what the lede is trying to get across. My memory is dim, but I think Fire codes were used to correct single burst errors on disk drives. RS codes replaced Fire codes because they can correct multiple random and burst errors. Glrx (talk) 01:09, 22 November 2013 (UTC)

My issue is that the term bursts is typcially bit oriented, while RS codes are symbol oriented. Perhaps the article statement could be changed to multiple burst / multiple bit error correcting code. It doesn't make it clear that a n+2 bit burst could affect 3 n bit symbols, or that interleaving could be used to reduce the impact of a multi-bit burst error. Rcgldr (talk) 03:37, 22 November 2013 (UTC)

The page has a bug

I discuss it on my blog. Am I wrong? Potential conflict-of-interest disclosure, I used to work at MIT Lincoln Laboratory. — Preceding unsigned comment added by Yanazendo (talk • contribs) 05:52, 27 November 2014 (UTC)

Erasure correction

The article claims that a Reed-Solomon code can correct twice as many erasures as errors - this would be (n-k), a conclusion supported by the code having distance (n-k+1)

But it goes on to state "2E + S < n − k ... where E is the number of errors and S is the number of erasures in the block."

If there are no errors, this implies it cannot in fact correct (n-k) erasures. Shouldn't the < in that equation in fact be a "less than or equal" symbol? James mcl (talk) 20:49, 15 May 2008 (UTC)

Yes, that is correct, and someone already fixed the mistake in the article. Lrq3000 (talk) 00:19, 24 June 2015 (UTC)

Erasures

I wrote the text that said that a Reed-Solomon code is twice as powerful at erasure correction than at error correction. This text was correct, and I've reverted the page.

In this context, the word 'erasure' refers to a symbol in a particular location that is known (or is very likely) to be in error, but the actual error value isn't known. (This occurs because Reed-Solomon codes are non-binary; if we were talking about a single bit known to be in error, then it would be obvious how to fix it!)

With a Reed-Solomon decoder equipped for erasure correction, you can tell it which specific symbols you believe to be in error, and the decoder will compute the corresponding error values; i.e., it will correct the erasures. Why do this instead of just letting the decoder figure out which symbols are in error? Because the decoder can correct more errors this way. E.g., the (255,223) code heavily used in deep space communications has 32 parity symbols, so it can correct up to 16 symbol errors if the locations of those errors are not known. But if you know where two of those errors are, then the code can correct them *plus* 15 more errors in unknown locations, for a total of 17 corrections.

User: Karn

Just a minor point: of course the concept of "erasure" is also meaningful for binary codes. This is because "erasure" does not mean that the location is known to be an error; it means that the location is known to be meaningless. Perhaps you lost the 3rd bit of your transmission because you accidentally - but knowingly - set it to 0. In this case, you don't know if there's an error at that location - but you know it has to be reconstructed. Selinger (talk) 02:13, 15 March 2008 (UTC)

I like in general the idea of explaining erasure as an error at a known location. However it is true that the usual meaning of error is that the symbol received is definitely not the symbol sent, hence in general gives some information about the symbol sent. In the case of a binary alphabet it gives all the information about the symbol. An erasure indicates only the position of the symbol but nothing about its value. But I'm not sure how to reword the definition without losing its simplicity. Ozga (talk) 16:43, 26 July 2008 (UTC)

I agree, this should be mentioned in the article, since an erasure, even if it has the correct value, is still consuming one parity symbol for reconstruction. So really, an erasure is an information about the meaningfulness of a symbol at given position, not an indication that it's an error. Lrq3000 (talk) 00:32, 24 June 2015 (UTC)