please dont rip this site

Reed-Solomon Data Link Error Detection / Correction Method

Reed-Solomon block codes are popular in communications and data-storage applications. Like fire codes, Reed-Solomon-code implementations append symbols to the end of a transmission to locate and correct errors during decoding. Reed-Solomon-code systems' effectiveness at high data rates results from operations taking place at the code-symbol rate or at a fixed number of times per code word. Either way, the number of operations is much smaller than the number of bits. Chips that implement these types of high-speed real-time correctors are commercially available, as are DSP-software options.

Each RS symbol is actually a group of M bits. Just one bit error anywhere in a given symbol spoils the whole symbol. That's why RS codes are often called "burst-error-correcting" codes; if you're going to have bit errors, you'd like to concentrate them into as few RS symbols as possible. Many RS codes in use are "shortened", i.e., the block size, or number of symbols used: N, is smaller than the symbol size, or maximum number of symbols: 2M-1 would indicate.

Since RS can be done on any message length and can add any number of extra check symbols, a particular RS code will be expressed as RS (N,N-R) code where N is the total number of symbols per codeword; R is the number of check symbols per codeword and; therefore, N-R is the number of actual information symbols per codeword. The typical RS decoder can correct up to (N-R)/2 symbol errors per block Note that "errors" and "erasures" are not the same things.

For example, digital video broadcast (DVB) specification uses a RS (204,188) code, utilizing sixteen check symbols per 188, 8-bit, information symbols for a total codeword length of 204 symbols and can correct eight symbols. This means that a burst error of 57 to 64 consecutive bits can be corrected.

RS encoding then consists of the generation of these check symbols from the original data. The process is based upon finite field (also known as Galois field or GF) arithmetic. Finite fields are so named because all arithmetic is closed over the field (the result of any operation is still an element of the field). In other words, GF addition bears no resibalence to normal addition; adding two large GF values will probably get you a smaller value. Its sort of like always taking the modulo of the result (or throwing away the carry) so that the values never exceed the space available to store them. The field elements are all values from 0 to 2M-1. Therefore, for a bit width of 3, the field will contain the values (0,1,2,3,4,5,6,7), though not necessarily in that order.

The field polynomial, which is used to determine the order of the elements in the finite field, is generally determined by specification (the example DVB specification mentioned uses eight bit symbols {m=8} and a field polynomial of 285 per specification). Valid field polynomials are a function of the bit width to be operated on. For example, the valid field polynomials for m=3 are 11 and 13.

The generator polynomial starting root is generally determined by specification (DVB uses a generator polynomial starting at root zero), although any value in the finite field can be used.

Generally, a Reed-Solomon corrector provides a number of symbol corrections, say T, in an N-symbol code word. T is independent of the location of the errors inside the code word. When you use this method with complex interleaving, this approach can easily correct large error bursts. Further algorithm refinements allow even more correction capability if you know the error location by some other means. These "soft-error" indicators can come, for example, from up-stream decoding violations. It is unable to both locate and correct errors in a block that has more than T symbol errors.

See also

Books

See also:


file: /Techref/method/error/rs.htm, 7KB, , updated: 2009/1/23 11:42, local time: 2024/12/3 22:18,
TOP NEW HELP FIND: 
18.97.14.82:LOG IN

 ©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions?
Please DO link to this page! Digg it! / MAKE!

<A HREF="http://www.massmind.org/Techref/method/error/rs.htm"> Reed-Solomon Data Link Error Detection / Correction Method </A>

After you find an appropriate page, you are invited to your to this massmind site! (posts will be visible only to you before review) Just type a nice message (short messages are blocked as spam) in the box and press the Post button. (HTML welcomed, but not the <A tag: Instead, use the link box to link to another page. A tutorial is available Members can login to post directly, become page editors, and be credited for their posts.


Link? Put it here: 
if you want a response, please enter your email address: 
Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
Did you find what you needed?

 

Welcome to massmind.org!

 

Welcome to www.massmind.org!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  .