Talk:Reed–Solomon error correction

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)

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!

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)

Cross-interleaved coding

Is CIRC also used on DVDs.

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)

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)

Need More Info:

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

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

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)

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.

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)

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)

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?