Reed-Solomon Codes Help Correct Errors in Digital Designs

Engineers turn to advanced error-correction techniques to improve efficiency and operation in modern wireless devices.

By: Iain E G Richardson and Martyn J Riley, 4i2i Communications Ltd.

Contents
The Basics
Combining Codes
Error Correction Performance
Implementation
Software Implementation
A Practical, Flexible Tool

The digital age has arrived in the wireless industry. CDMA, TDMA, GSM, and other digital cellular networks are popping up in countries throughout the world. AMPS phones are being replaced by multimode phones that support both analog and digital operation. PCS services are moving full speed ahead touting their digital capabilities.

By nature, digital systems transmit information by breaking information into strings of 1s and 0s. However, interference and noise can cause a digital receiver to confuse 1s and 0s in the message. Therefore, engineers must employ error-correcting codes (ECCs) in their digital wireless designs to account for these occasional errors.

(top)

The Basics
Figure 1 shows a general block diagram of a digital transmission system with an ECC encoder and decoder. In this example, data from the source is encoded before transmission. The encoded data is then transmitted (picking up interference and errors in the process). Next, the ECC decoder processes the received data and attempts to reconstruct the original data. Finally, the output of the decoder is fed to the data sink.

If the encoder and decoder are correctly specified and designed, the number of errors in the decoded data (usually measured in terms of bit error rate [BER]) is lower than the number of errors if ECC is not used.

Many ECC techniques have been developed for wireless; each with its own advantages and disadvantages. Two of the most common are convolutional and Reed-Solomon codes.

Convolutional codes are designed to operate continuously in a wireless system. Thus, a convolutional encoder operates on a continuous stream of data using a shift-register to produce a continuous encoded output stream.

Convolutional codes are effective for correcting bit errors, such as the type of error distribution produced by an additive white Gaussian noise (AWGN) channel. However, these codes are not good at correcting burst errors, which are longer sequences of errors that might be produced by a fading channel, for example.

Reed-Solomon codes are block-based error correcting codes with a wide range of applications in digital communications and storage. For example, Reed-Solomon codes are used to correct errors in many digital wireless applications such as cellular/PCS networks, wireless local-area network (WLAN) systems, and low Earth orbit (LEO) satcom systems.

Reed-Solomon codes belong to a family of block codes, in which the encoder processes a discrete block of data to produce an encoded block (or codeword). Other block codes include the single error correcting Hamming code, the triple error correcting Golay code, and the family of Bose-Chaudhuri-Hocquenghem (BCH) codes.

(top)

Combining Codes
Different types of error correcting codes can be combined to produce concatenated codes. For example, Reed-Solomon codes are often combined with convolutional codes to improve all-round performance. In this combined setup, the convolutional code corrects randomly distributed bit errors but not bursts of errors while the Reed-Solomon code cleans up the residual burst errors.

Reed Solomon codes are linear block codes that are a subset of BCH codes. A Reed-Solomon code is specified as RS (codeword: n,k) with s-bit symbols. This means that the encoder takes k data symbols of s bits each and adds parity symbols to make an n symbol There are n-k parity symbols of s bits each (Figure 2).

Reed-Solomon codes are particularly good at correcting bursts of errors (also known as sequences of bit errors). A Reed-Solomon decoder can correct up to t symbols that contain errors in a codeword, where 2t = n-k. For example, a popular Reed-Solomon code is RS(255,223) with 8-bit symbols. Each codeword contains 255 code word bytes, of which 223 bytes are data and 32 bytes are parity. In this example, n = 255, k = 223, and s = 8. When these figures are plugged into the above equation, we can see that 2t = 32 and t = 16.

As we can quickly see, the Reed-Solomon decoder in this example can correct any 16 symbol errors in the codeword: i.e. errors in up to 16 bytes anywhere in the codeword can be automatically corrected. In the worst case, 16 bit errors may occur, each in a separate symbol (byte) so that the decoder corrects 16 bit errors. In the best case, 16 complete byte errors occur so that the decoder corrects 16 x 8 bit errors.

Given a symbol size s, the maximum codeword length (n) for a Reed-Solomon code is n = 2s - 1. For example, the maximum length of a code with 8-bit symbols (s=8) is 255 bytes.

Reed-Solomon codes may be shortened by (conceptually) making a number of data symbols zero at the encoder, not transmitting them, and then re-inserting them at the decoder. Thus, the RS(255,223) code described from above can be shortened to (200,168). The encoder takes a block of 168 data bytes, (conceptually) adds 55 zero bytes, creates a (255,223) codeword, and transmits only the 168 data bytes and 32 parity bytes.

The amount of processing "power" required to encode and decode Reed-Solomon codes is related to the number of parity symbols per codeword. A large value of t means that a large number of errors can be corrected but requires more computational power than a small value of t.

(top)

Error Correction Performance
When designing a wireless system, an engineer typically has to achieve a target BER. This BER generally depends on the type of data that is carried. For example, coded video data may require a very low BER (e.g. 10-7 or less) whereas coded speech may have an acceptable BER of 10-4, depending on the speech decoding algorithm.

BER depends on the signal-to-noise ratio (SNR). Thus, one way of reducing BER to acceptable levels is to increase transmitter power (or to reduce the spacing between transmitter and receiver). The benefit of ECC is that, if used effectively, it can improve the received BER without increasing the transmitted power. This performance improvement is measured as coding gain.

In Figure 3, BER is plotted against Eb/N0 (for a received signal without ECC (uncoded) and for the same received signal after ECC decoding (coded). In this case, the Eb/N0 ratio required to achieve a BER of 10-4 is 14 dB in the uncoded case and 5 dB in the coded case. Hence, ECC has provided a coding gain of 7 dB in this wireless system.

Note that the coding gain changes depending on the target BER. Figure 3 shows that in some cases, ECC provides little or no improvement (or can even make the performance worse). The performance depends on the type of ECC, the parameters of the code, and on the type of channel and demodulator. It is therefore very important to choose the ECC code carefully (for example by simulating the proposed design with different code parameters).

(top)

Implementation
Reed-Solomon codes are based on a specialist area of mathematics known as Galois fields (also known as finite fields). A finite field is a group of numbers (or elements) and arithmetic operations (+,-,x,/ etc.) on which elements behave differently than usual. For example, the result of adding two elements from the field is another element in the field (i.e. modulo arithmetic). A Reed-Solomon encoder or decoder needs to carry out these arithmetic operations, which require special hardware or software functions.

A number of commercial hardware implementations exist for Reed-Solomon encoding and decoding. Typically, a hardware architecture will contain special arithmetic and logic units for carrying out operations using Galois field arithmetic.

Many existing systems use off-the-shelf ICs that encode and decode Reed-Solomon codes. These ICs tend to support a certain amount of programmability (for example, RS(255,k) where t= 1 to 16 symbols).

Recently, many engineers have turned towards VHDL and Verilog designs for their hardware architectures. These designs have a number of advantages over standard ICs. A logic core can be integrated with other VHDL or Verilog components and synthesized to a field-programmable gate array (FPGA) or application-specific IC (ASIC), enabling so-called system-on-a-chip (SOC) designs where multiple modules can be combined in a single IC.

Depending on production volumes, logic cores can often give significantly lower system costs than standard ICs. By using logic cores, a designer avoids the potential need to do a lifetime buy of a Reed-Solomon IC.

(top)

Software Implementation
Until recently, software implementations in real-time required too much computational power for all but the simplest of Reed-Solomon codes (i.e. codes with small values of t). The major difficulty in implementing Reed-Solomon codes in software is that general-purpose processors do not support Galois field arithmetic operations.

For example, to implement a Galois field multiply in software requires a test for 0, two log table look-ups, modulo add, and anti-log table look-up. However, careful design together with increases in processor performance mean that software implementations can operate at relatively high data rates. The following Table gives some example benchmark figures on a 166 MHz Pentium PC:

Note: The data rates presented in the above table represent decoding only. Encoding is considerably faster since it requires less computation.

The figures presented in the above table show that an acceptable throughput can be achieved with a mid-range, general-purpose processor. Encoding and decoding of Reed-Solomon codes can be practically achieved on a range of processors, including embedded processors and DSPs.

(top)

A Practical, Flexible Tool
ECCs provide a practical and flexible tool for improving the performance of a wireless system. Reed-Solomon block codes are particularly effective at correcting bursts of errors (due to fading) and relatively powerful Reed-Solomon codes can now be implemented in software or as part of an FPGA or ASIC design.

Good error correcting performance depends on the careful choice of the type of code and the parameters of the code. Simulation of the system is often the best way to estimate performance and select the code parameters.

(top)

Edited by Robert Keenan