Building Blocks: The long climb up the error correction ladder leads to one of today’s best data tricks — Reed-Solomon coding.
By Rob Howald
We will discuss how this odd structure fits into a real system, and why we go to the trouble.
The early part of my career, after I finally concluded that the Red Sox were not going to be drafting any Villanova engineering graduates to fill their roster, was spent doing RF and microwave design. Of course, early on,
design meant figuring out why everyone kept saying “puff” (that’s geek RF talk for picofarad), looking for 1 Henry inductors, building computer models of 10-kHz wide bandpass filters at 18 GHz, and memorizing the resistor color code jingle. I spent a lot of time learning how to play an HP spectrum analyzer like a piano, and sticking my head into ice-encrusted chambers to tune misbehaving amplifiers, oscillators, filters, phase-locked loops (PLLs), and multipliers. To the outsider, RF and
microwave design is often seen and referred to as black magic. Outsiders believe that the inside of the RF box is ugly and complicated, and that it’s better not to try to understand what is milling around inside of it. I can tell you one thing for sure — there are no 1 Henry inductors in there.
Like RF, forward error correction (FEC) is sometimes thought of as magic. It’s the magic chip that turns 1e
-5
into 1e
-8
when inserted in the demodulator path. Heaven
only knows what is going on in there. The goal of this month’s column is to present one of today’s most powerful FEC approaches — RS codes — and to dispel the magical atmosphere surrounding FEC. Although the codes discussed in this month’s column were founded on linear algebraic principles, later works pulled them together using other common threads.
Last month, we began our latest foray into the idea of FEC. On the long and winding road, we made a pit stop with cyclic codes, and
lavished some attention on cyclical redundancy check (CRC) codes in particular, discussing their merits and their shortcomings. If this isn’t ringing a bell yet, it could be that your memory is fading. Or possibly (although highly unlikely), you didn’t read “Building Blocks” last month. For the few who didn’t do their homework, last month’s column was a piece entitled “Reed-Solomon from the Ground Up” (
Communication Systems Design
, May 1999, pp. 16-19). After
walking through cyclic codes, I introduced the Bose-Chaudhuri-Hocquenghem (BCH) code family.
BCH redux
- BCH codes are, indeed, cyclic codes. However, they have added properties that allow them to be evaluated through classical coding parameters, such as minimum distance and code word error-rate calculations. By contrast, for the CRC codes, only coverage and burst correction capability can be predicted. Some basic themes and important facts with regard to BCH codes are:
- BCH codes are cyclic. In general, cyclic codes do not quantify easily in terms of key-code parameters, but BCH cyclic codes do.
- BCH are a large and important class of codes in and of themselves.
- BCH codes are practical and realizable with known efficient decoding algorithms.
- The design of a BCH code can be selected by defining desired coding parameters that can be related directly to overhead and performance.
- Some BCH codes are also of
known weight distribution (the number of vectors of a given weight [number of 1s for binary], are important for error detection analysis).
- BCH codes are the most powerful linear codes for a significant range of block lengths.
- The most important set of nonbinary BCH codes are RS codes.
BCH codes are rooted in linear algebraic equations and the properties of those equations. Because of their popularity, there are tables of equations that can be used to apply the best BCH
codes for a given performance and tolerable overhead.
The following applies for binary BCH codes: for any integers (
m 3, t <
2
m
- 1
), there is a binary BCH code of block length
n =
2
m
- 1
with error correcting capability
t
. The number of overhead symbols is (
n - k
)
mt
. The minimum distance — a parameter related to the performance of the code in terms of the separation of the code words —
is then
d 2t + 1
. Some example BCH codes (
n,k
) for rate
r =
k
n
codes are:
- Single-error correcting (corrects one error in a coded block) (
t = 1
):
(7,4); m = 3, d 3, n - k = mt, r =
4
7
- Double-error correcting (
t = 2
):
(15,7); m = 4, d 5, n - k = mt, r =
7
15
- Triple-error correcting (
t = 3
):
(15,5); m = 4, d 7, n - k < mt, r =
1
3
- Ten-error correcting (
t = 10
):
(63, 18); m = 6, d 21, n - k < mt,
r =
2
7
.
The last code uses 63-bit blocks. It can be recovered correctly if there are less than or equal to ten transmission errors. This seems big, but much larger codes are easily made.
The performance term
d
is an inequality, but the equality
d = 2t + 1
is called the designed distance. The equality is true in many cases. Also, the amount of overhead
(
n - k
above) gives a false impression of being uncontrolled. This false impression is part of the price of avoiding linear algebra. The selected parameters refer to a particular generator polynomial — essentially, the equation that processes the incoming stream into a BCH encoded output. The degree of this polynomial is exactly the (
n - k
) overhead term.
A Fire drill
The early heydey of coding research resulted in a massive analy-sis of linear block codes, with minimum
distance and error rate performance bounds. There was one annoying little detail: most of the research counted on randomly-distributed errors, such as those generated by additive white Gaussian noise (AWGN). Most traditional codes tend to handle these randomly-distributed errors best, although cyclic codes do have burst correction features. Unfortunately, channels with impairments (particularly dominant impairments) other than AWGN tend to create errors that occur in bursts. Some examples include fading,
impulse noise, and phase noise. Burst errors are more difficult to handle. For example, block after block of code words with an error-correcting capability of
t = 2
will do poorly in an environment where five error-free blocks in a row are followed by a block that has twelve errors. Had the twelve errors been distributed evenly throughout the six code words, all of the code words would have been handled. In 1959, the Fire codes were invented as a generalization of earlier results for burst codes drawn
from work with cyclic codes. Subsequently, other approaches surfaced. This error- correction capability became more interesting as digital communications expanded into what is now a wide array of troublesome channels.
Amazingly, RS codes were invented in 1960 (a nickel to name the inventor — hint: there were two). However, for quite a long time it was felt that RS codes were a theoretical exercise and of little practical value. RS codes are nonbinary. In other words, the code symbols are not just 1s
and 0s, but can be a larger alphabet of algebraic characters. There wasn’t a straightforward and efficient way to implement this, particularly on the more complex decoding side. But as digital communications continued to move towards higher throughput on crazier channels, technology moved just as quickly. Developing efficient ways to implement RS codes was part of this growth. And, since then, RS codes have become of great interest because of their desirable properties.
How RS codes work
Binary BCH codes and their associated algebraic structures can be generalized into a nonbinary structure. In this sense, the code parameters for a
t
-symbol correcting block code of symbols over a
q
-symbol alphabet becomes: block length:
n = q - 1
, overhead:
n - k = 2t
, minimum distance:
d = 2t + 1.
What does it mean to have an alphabet size of
q = 21
and
t = 2
? Actually, not very much. But what if I instead considered an alphabet size of 16 (as in
2
4
= 16
)? Now, a block of length 15 can represent 60 bits, where each gang of 4 bits is a binary representation of the oddball alphabet. Toss in a way to efficiently decode the blocks, and progress is made.
We’ve touched on higher-order modulation schemes such as M-QAM many times in past “Building Blocks” columns. If
M = 16
for this example, then each quadrature amplitude modulation (QAM) symbol can represent one RS code symbol. RS implementation, at
its core, is essentially binary, whether through direct binary encoding or binary coding built into the modulation.
Encoding built into the modulation would follow something like this for an RS code where
t = 1
and
q = 16
:
- There are fifteen code symbols per block.
- Since
n - k = 2t
, there would be thirteen information symbols in a block and two overhead symbols.
- Each symbol for
q = 16
can be mapped to one 16-QAM symbol.
Such a symbol is 4 bits per symbol.
- Thus, 4 x 13 = 52 payload bits would enter and be treated by the encoder as thirteen q-ary symbols. (Get it? Q-ary instead of bi-nary.)
- The RS encoding would perform some algebraic manipulation (via a defined polynomial) and produce two parity check symbols (also from the alphabet of
q = 16
— another modulation symbol).
- The RS block would consist of the fifteen consecutive symbols from a 16-QAM constellation, with each
symbol now compatible with physical layer transport, yet also easily related to an RS code symbol.
- The decoder would work with this fifteen-symbol block, delivering 4 bits per symbol of payload data.
Key RS properties
There have to be good reasons to live with this added nonbinary complexity. One reason is evident in the previous example — we have already developed ways to transmit digital information in a nonbinary fashion using higher-order modulation schemes such
as M-QAM, M-phase shift keying (PSK), and M-frequency shift keying (FSK). Thus, these techniques can be leveraged to assist the coding. However, this approach puts constraints on the block sizes that can be used. Very high-order modulation formats are less able than digital encoding formats to process blocks of more symbols than 16, 64, or even 256. These longer block sizes can be accompanied by bigger coding gains, and would add little implementation difficulty. However, for modest RS gains and
simplified encoding and modulation, high-order modulation formats work nicely.
Consider this same block of symbols from a family of
q = 16
symbols, but rely on plain old binary signaling via baseband, FSK, or PSK. We have fifty-two payload symbols heading across the channel with a 4-bit appendage as overhead redundancy. Now there’s an inherent burst protection capability. A burst of noise that disturbs the transmission can do so up to 4 bits in a row, and the RS decoder won’t care. This is
important — RS error-correcting capability,
t
, means
t
-symbol correcting. Wiping out either a single bit or all 4 bits means wiping out only one RS symbol, which is perfect for a
t = 1
code if all else stays clean. This inherent burst protection makes RS codes particularly useful in some cases. To maintain the same throughput as uncoded transmission, the coded transmission must exist at a higher rate. A bursty interference of the same duration will impact more symbols than an uncoded
interference.
There are some analytical bonuses with these codes. First, RS codes are maximum distance separable (MDS), meaning all of the possible code words are as far away, algebraically, as possible in code space. It implies a uniform code word distribution in a code space. Few other codes have this property, and none of much practical value. For the modulation-based code word implementation previously described, there can be great confidence that the choice of coding used will perform excellently.
Also, this modulation scheme fits into a hard decoding demodulation approach. This means error rate performance can be calculated directly from known detection performance probabilities embedded within code word error analysis, sidestepping the code word weighting information.
Another interesting property deals with the weight distribution. For MDS codes, the weight distribution is known exactly. This doesn’t happen very often in the FEC world, and it’s fortunate when it does. Knowing the exact
weight distribution is valuable for systems such as the binary representation of q-ary symbols for coding, where such information is needed to evaluate error performance.
Finally, RS codes work well as the envelope in a concatenated FEC system. As previously mentioned, random error correcting codes do poorly with bursty traffic. Thus, the two codes complement each other very well, and the RS codes mitigate the leftover error burst. These two codes in series then result in a 1 + 1 = 3 type of thinking.
RS cleans up the burst errors well, and many contemporary channels have burst error-generating mechanisms. Also, when a channel does generate errors that are handed to a first line of defense decoder at the receiver, bursts of errors tend to remain after the random error correcting decoder has done its best. The RS decoder fits well in this situation.
RS codes are still the subject of extensive development and analysis, due to how new and powerful they are. RS codes are seeing so much use that various
industries need to figure out exactly how forceful they are under various impairments associated with different channels. For now, our meander through the FEC forest has come to an end. FEC is truly a “forest for the trees” topic. There are a thousand different tree species, with accompanying research that breaks down the equivalent DNA structure of each. What’s important to communication systems designers is what kind of link performance gains these codes provide. A short list of powerful
code families is used in most FEC applications. The three we plowed through in the past two months — CRC codes, BCH codes, and RS codes — all qualify as part of this list.
And here is a final observation to keep in mind when dealing with these three related disciplines: Ask any RF guy and he will tell you that modem guys don’t know RF. Ask any modem guy and he will tell you that FEC guys don’t know modems. Ask any FEC guy (they occasionally come out of the office when their
workstations overheat) and he will tell you that neither of those other guys knows communications. As for some goofball hybrid like me? Well, those Red Sox are looking pretty weak this year. I’d better hang out by the phone.
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.
Return to
Table of Contents
Puzzled by a network processing design issue?