Parity and checksum are poor methods because they are unable to detect transpositions.
If we receive a message which does have a nonzero remainder, we can detect this, and in some cases use the nonzero remainder to determine where the errors occurred and correct them. In all cases, we have this magic technique of taking data bits, using a division algorithm to compute the remainder, and concatenating the remainder, such that the resulting message has zero remainder. If we compute parity bits of a Hamming code, and concatenate them to the data bits, the resulting message has a remainder of zero modulo the Hamming code polynomial.If we compute the CRC of a message (with no initial/final bit flips), and concatenate the CRC, the resulting message has a remainder of zero modulo the CRC polynomial.If we compute the checksum of a string of bytes, and concatenate a negated checksum, the resulting message has a checksum of zero modulo 256.If we compute the parity of a string of bits, and concatenate a parity bit, the resulting message has a parity of zero modulo 2.You may have noticed a pattern in some of the coding techniques discussed in the previous article: A \( (255, 247) \) RS code would be able to correct 4 errors, and a \( (255,223) \) RS code would be able to correct 16 errors, with each error being an arbitrary error in one transmitted symbol. The Reed-Solomon codes with \( n=255 \) are very common, since then each symbol is an element of \( GF(2^8) \) and can be represented as a single byte. They are not binary codes each symbol must have \( 2^m \) possible values, and is typically an element of \( GF(2^m) \). A Reed-Solomon \( (n,k) \) code, where \( n=2^m-1 \) and \( k=n-2t \), can correct up to \( t \) errors. Reed-Solomon codes, like many other error-correcting codes, are parameterized. We’re also going to talk about some performance metrics of error-correcting codes. We’ll see that encoding a message using Reed-Solomon is fairly simple, so easy that we can even do it in C on an embedded system. (I had meant to cover this topic in Part XV, but the article was getting to be too long, so I’ve split it roughly in half.) These are one of the workhorses of error-correction, and they are used in overwhelming abundance to correct short bursts of errors.
This time we are going to cover Reed-Solomon codes. If you are new to this topic, I would strongly suggest going back to read that article before this one. Last time, we talked about error correction and detection, covering some basics like Hamming distance, CRCs, and Hamming codes.
0 kommentar(er)
