Building Blocks: Reed-Solomon from the
Ground Up.
As error correction methods move completely into the mainstream in modern communications, everyone keeps mentioning these Reed and Solomon fellows.
By Rob Howald
Many thanks to all the readers who sent in suggestions for upcoming column topics. I can’t think of a single silly one; a testament to this column’s educated readership base. It is especially remarkable, considering I can think of silly topics of my own already published on these hallowed pages. My daughter,
for example, would like me to do a column on snakes, so I can tell everyone about her pet Florida king snake (I only wish that were a joke). Beyond this, nothing but credible topics arrived, and I will try to honor them. Of course, it’s partly out of my control, because getting to all of them means that the top brass at
Communication Systems Design
has to spend another year pretending they like working with me. However, I do hope to dip into the stack later this year.
Turbo codes is a topic
that received multiple votes. If you recall, a past “Building Blocks” column (“Springing Forward to Higher Performance,”
Communication Systems Design
, March 1997) introduced the topic of forward error correction (FEC). I know that I have mentioned FEC (pronounced “feck” when modem insiders want to impress) on several other occasions while discussing various communications topics. For the past two months, the discussion has centered on trellis coded modulation (TCM).
Before I dive into turbo codes, it seems like a good idea to cover one more step on the FEC ladder. This month’s and next month’s discussions will focus on an important mainstay in modern, powerful FEC techniques — Reed-Solomon (RS) codes. Now, lest you get worried that these “Building Blocks” FEC topics are following the MSNBC example of variety in programming, circa 1998 (all Monica, all the time), rest assured that there will be plenty of variety forthcoming. Because RS codes and
TCM represent today’s most representative offerings of implemented, high-performance coding, I thought I should round out this topic. This discussion requires working through some fundamentals covering yet more coding ground.
For true FEC diehards, there is now a book devoted completely to RS codes, and it is listed in the resources section at the end of this article.
4
There are lots of FEC books, and I have listed my three favorites (resources 1, 2, and 3), along with a true theoretical
staple (resource 2).
RS road map
To complicate things, RS codes can be derived from several different starting points. The inventors derived the codes through the linear algebra route. We are going to take an easier route (from an explanation standpoint), in order to relieve some of the mathematical burden. Unfortunately, this route requires the introduction of another type of code. Actually, this new code family is an excellent code family to force upon you, and a fantastic tongue twister to
boot. These are the Bose-Chaudhuri-Hocquenghem (BCH) codes. (Perhaps, for selfish reasons, we can wish Dr. Bose had decided to work with Jones and Smith.) Before we go BCH’ing, we need to introduce other important ideas in the error correction field.
Introducing RS through BCH makes sense because the RS codes can be considered an extension of the BCH codes. It also makes for straightforward understanding, in conjunction with a determined effort to maintain a math-free zone, because BCH codes can speak
our language of bits and bytes. Thinking of digital data in its raw form as 1s and 0s (binary) comes naturally. On the other hand, RS codes are nonbinary. How can this be? In fact, representation of the nonbinary RS code symbols occurs with binary information, but the code structure itself is based on those nonbinary symbols. But we’re getting ahead of ourselves. Let’s introduce the BCH codes (via cyclic codes) and work our way up.
Cyclic basics
If you came into contact with simple
codes during your career struggles, they were probably traditional cyclic codes. Any time you stumble across a CRC-something or other, you have landed upon a cyclic redundancy check code, a popular code in computer-to-computer communications. A cyclic code is easy to define: for every code word vector of length n expressed as [C
0
, C
1
, C
2
, …. C
n - 1
], there is another code word given by [C
n - 1
, C
1
, C
2
, …. C
n - 2
]. That is, the second code word is a shift to the right by one code symbol. In digit land, this is a multiplication by two. It is particularly easy to recognize as a shift register operation. We like that part — it’s easy to understand and implement — there is a price, however. Aside from computer searches, the quality of a cyclic code, in terms of traditional code parameters, is not easily evauated. For example, their minimum distance is unknown. Minimum distance is how far apart,
digitally, the different valid code vectors are. This makes it easier for a decoder to tell them apart. (See the code word example in
Figure 1
and the code word interpretation in
Figure 2
.)
Also, we don’t know the weight distribution of a cyclic code. How about trying that one out at home. Try asking: “honey, what exactly is your idea of an ideal weight distribution?” It’s bound to be a hit. After
apologizing for your nerd humor from the guestroom, you can explain how this term represents the number of code words of a given weight. For a binary code word (1s and 0s), the weight of a code word is the number of 1s (all 0s have weight zero). Because it is the same as the minimum distance, this parameter is valuable for determining exact error rate performance, and the minimum weight is an important relative performance parameter for linear block codes.
So, cyclic codes are easy, but we don’t
know how good they are. Fortunately, they have other properties that provide practical measures of “goodness.” One such measure is called coverage. Think of the code word in
Figure 1
. Any other valid code word looks different from it digitally (or from a linear algebraic perspective). If transmission errors occur in the middle of the code word, it should still look more like one code word than another, making correct detection easier. An error, or two,
is a slam dunk for a good code with the right design parameters for the channel. But let’s say your networked PC is transmitting a message to another PC elsewhere in the network. Now, imagine some highly unlikely occurance happened to muck things up. A communications foul-up garbles the message, so that the received word is completely random. The idea of coverage is that the probability of this totally random word just happening to be a valid word can be predicted. This is certainly one situation to
avoid. If the code word looks valid to the decoder, the message will be treated like an error-free message, and will be processed. It will all be erroneous information, however. As it turns out, the coverage, or probability that a random code word is valid, is completely a function of the code rate: Coverage = 1 - 2
-(n - k)
.
As can be seen in
Figure 1
, (n - k) is the number of redundant bits, r. The ratio, kn, is the code rate. A CRC-7 code, for
example, has seven redundant bits, and 99.2% of random receptions won’t be valid code words. For CRC-32, the percentage is a staggering 99.999999977%.
The cyclic code family’s burst error correction capability is another powerful idea. It’s predictable in CRC codes. The example shown in
Figure 1
is one in which bursts of errors are likely. Random errors, the foundation of much linear block code theory, are best associated with the basic additive
Gaussian (thermal) noise channel. However, many phenomena in real channels are likely to cause errors in bursts. Communications problems, or power problems, have this effect. Similarly, fading conditions and phase noise tend to cause these types of errors.
For cyclic codes, bursts of length r or less are 100% correctable by a cyclic code of redundancy r. Bursts of length (r + 1) are correctable, and the percentage is predictable. The percentage correctable beyond (r + 1) is also predictable. For CRC-7, the
correctable percentage for a length of eight errors is about 99.4%, and above 99% for lengths greater than eight errors.
Many basic, as well as many new, sophisticated systems are built around cyclics. Furthermore, burst correction capability is one of the most powerful reasons to use RS codes.
BCH basics
Isn’t it fitting that the development of BCH codes can also be brought about in two ways? We’ll sidestep the linear algebraic way again, via the BCH link to cyclic codes. BCH
codes are binary block codes, (as discovered by our triumvirate of coding buddies mentioned earlier). Recall that block codes are the simplest to operate. A block of payload data is augmented with a set of binary digits for redundancy. The redundancy introduces additional information that, in linear algebra space, distinguishes the payload binary vector from other possible payload vectors, making transmission more robust (as shown in
Figure 1
).
There are many
ways to introduce redundancy. The best codes provide the most robustness with the least additional overhead of bits. Finding codes that qualify as the best hasn’t always been simple. However, various texts on the topic, list what represent the best known codes for various block sizes and code rates. The smaller the code rate for a particular amount of error correcting capability, the better. BCH codes offer various code rates that are optimal, in some sense, or at least known as good codes. Double
error-correcting codes ECC (which fix two transmission miscues) have been proven optimal in the linear algebraic, FEC sense of the definition.
2
Earlier, we discussed the simplicity of cyclic codes. The idea of the shift-register relationship implied a straightforward implementation of encoders and decoders. Once again, we skipped the math part, but the core of a cyclic code is a binary polynomial. We also implied the ease of digital multiplication via shift registers. Indeed, the simplicity of
encoding for cyclic codes receives its power from the shift register and basic digital logic circuitry, which allow fast clocking speeds, and thereby real-time, nonintrusive encoding and decoding. This simplicity has its price in available code performance information. This is where the BCH link kicks in. BCH codes are also cyclic codes. The BCH code addresses this code performance issue in a bigger way than the parameters discussed in the previous section. We can examine code performance for BCH codes in
traditional ways — including the minimum distance. This knowledge also leads to approximations that can be used for error rate analysis. The results are a code family commonly considered one of the most powerful available. Things clean up even more for RS codes.
Next month, we will do some more BCH’ing, and then begin our worship of Reed and Solomon.
Rob Howald is the manager of systems engineering in the transmission network systems group at General Instrument in Hatboro, PA. He has a
BSEE and an MSEE from Villanova University, and received his PhD from Drexel University. He can be reached at
rhowald@gi.com.
| Resources
|
- Lin, S., and Costello, D., Error Control Coding: Fundamentals and Applications, Prentice-Hall, Englewood Cliffs, NJ, 1983.
- Peterson, Wesley, W., and Weldon
E.J., Jr., Error-Correcting Codes, Second Edition, MIT Press, Cambridge, MA, 1972.
- Wicker, S., Error Control Systems for Digital Communication and Storage, Prentice-Hall, Englewood Cliffs, NJ, 1995.
- Wicker, S., and Bhargava, V., Editors, Reed-Solomon Codes and Their Applications, IEEE Press, Piscataway, NJ, 1994.
- Wilson, S., Digital Modulation and Coding, Prentice-Hall, Englewood Cliffs, NJ, 1996.
|
Puzzled by a network processing design issue?
