 Cyclic Redundancy Check (CRC) :
This error detection method computes the remainder of a polynomial division of a generator polynomial into a message. The remainder, which is usually 16 or 32 bits, is then appended to the message. When another remainder is computed, a nonzero value indicates an error. Depending on the generator polynomial's size, the process can fail in several ways, however, it is very difficult to determine how effective a given CRC will be at detecting errors. The probability that a random code word is valid (not detectable as an error), is completely a function of the code rate: 1  2(n  k). Where n is the number of bits of formed from k original bits of data ,(n  k) is the number of redundant bits, r.
Use of the CRC technique for error correction normally requires the ability to send retransmission requests back to the data source.
 Hamming distance based checks :
If we want to detect d bit errors in an n bit word we can map every n bit word into a bigger n+d+1 bit word so that the minimum Hamming distance between each valid mapping is d+1. This way, if one receives a n+d+1 word that doesn't match any word in the mapping (with a Hamming distance x <= d+1 from any word in the mapping) it can successfully detect it as an erroneous word. Even more, d or fewer errors will never transform a valid word into another, because the Hamming distance between each valid word is at least d+1, and such errors only lead to invalid words that are detected correctly. Given a stream of m*n bits, we can detect x <= d bit errors successfully using the above method on every n bit word. In fact, we can detect a maximum of m*d errors if every n word is transmitted with maximum d errors.
Monday, December 14, 2009
Error Detection Methods Cont...
Posted by Sunflower at 12/14/2009 04:33:00 PM
Labels: CRC, Cyclic Redundancy Check, Error correction, Error Detection, Errors, Hamming Distace, HC
Subscribe by Email 

Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment