ispLever
CORE
TM
Reed-Solomon Decoder
User’s Guide
October 2005
ipug07_04.0
Lattice Semiconductor
Reed-Solomon Decoder User’s Guide
Introduction
Lattice’s Reed-Solomon Decoder core provides an ideal solution that meets the needs of today’s forward error cor-
rection applications. The Reed-Solomon Decoder core provides a customizable solution allowing forward error cor-
rection of data in many communication applications. This core allows designers to focus on the application rather
than the Reed-Solomon Decoder, resulting in a faster time to market.
Reed-Solomon codes are widely used in various applications for forward error correction and detection. Lattice’s
Reed-Solomon Decoder core is a fully synchronous core developed in conjunction with Lattice’s Reed-Solomon
Encoder core to provide a complimentary pair. For more information on these and other Lattice products, refer to
the Lattice web site at www.latticesemi.com.
This user’s guide explains the functionality of the Reed-Solomon Decoder core and how it can be implemented to
provide decoding on any data transmission. It also explains how to achieve the maximum level of performance.
The Reed-Solomon Decoder core comes with the documentation and files listed below:
• Data sheet
• Lattice gate level netlist
• RTL simulation model
• Core instantiation template
Features
• Forward Error Correction (FEC) for communication and common applications
• Selectable Reed-Solomon standards:
– CCSDS (255,223)
– ATSC (207,187)
– DVB (204,188)
– OC192 (255,239)
• Shortened codes supported
• Fully synchronous design
• Error/erasures supported
• Supports symbol widths from 3 to 12 bits, corresponding to GF(8) and GF(4096) respectively
• User-defined and default field and generator polynomials supported
• Generates failure flags and measurement information
General Description
Reed-Solomon codes are used to perform Forward Error Correction. FEC encoders introduce redundancy in data
before it is transmitted. The redundant data (check symbols) are transmitted along with the original data through
the channel. A Reed-Solomon decoder at the receiver is used to recover any corrupted data This type of error cor-
rection is widely used in data communications applications such as hard disk and media storage (CD) systems,
Digital Video Broadcast (DVB) and Optical Carriers (e.g. OC-192).
The codes are represented by the format RS(n,k) where n is the total number of s-bit wide symbols, and k is the
number of s-bit wide information (data) symbols in a codeword. The Reed-Solomon Decoder performs detection
and correction of encoded data available at the receiver after demodulation. The RS encoded data is then pro-
cessed to determine whether any errors have occurred during transmission. Once the number of errors is deter-
mined, the decoder decides if they are within the range of correction. After determining this, the decoder corrects
the errors in the received data. A typical application of space signal processing is shown in Figure 1.
2
Lattice Semiconductor
Reed-Solomon Decoder User’s Guide
Figure 1. Application of Reed-Solomon code in a Space Communication System
Data Bits
RS
Encoder
Interleaver
Convolutional
Encoder
Transmit
Data
Decoded
Bits
RS
Decoder
Deinterleaver
Viterbi
Decoder
Receive
Data
A Reed-Solomon Decoder can correct errors and erasures. The maximum number of correctable erroneous sym-
bols in a codeword is t = (n-k)/2, and the maximum number of correctable erasures in a codeword is µ = n-k.
Reed-Solomon codes are based on finite field arithmetic, also known as Galois Field. The size of the field is deter-
mined by the width
s
of the information symbol, and the field has 2
s
elements. When n is less than the maximum
value of 2
s
-1, the code is called a shortened code.
Reed-Solomon codes are characterized by two polynomials: the field polynomial and the generator polynomial.
The field polynomial defines the Galois Field to which the information and check symbols belong. The generator
polynomial determines the check symbol generation, and is a prime polynomial for all codewords (i.e. all code-
words are exactly divisible by the generator polynomial). Both the field and generator polynomials are user config-
urable.
Field Polynomial
The field polynomial can be specified as any prime polynomial up to 2
s+1
- 1. The field polynomial is defined by its
decimal value (f). The decimal value of a field polynomial is determined by setting x = 2 in the polynomial and cal-
culating the result. For example, the polynomial x
2
+ x + 1 in decimal value is 2
2
+ 2 + 1 = 7.
Generator Polynomial
The generator polynomial determines the value of the check symbols. The starting root (
gstart
) and root spacing
(
rootspace
) variables define the generator polynomial. The general form of the generator polynomial is:
n-k-1
g(x) =
∏
(x -
α
rootspace * (gstart + i)
)
i=0
(1)
Shortened Codes
A shortened code has a lesser number of total symbols than the maximum possible for the given symbol width. An
example of a shortened code would be, RS(204,188) where s = 8.
3
Lattice Semiconductor
Block Diagram
Figure 2. Reed-Solomon Decoder Block Diagram
Control Bus
Reed-Solomon Decoder User’s Guide
Error
Magnitude
Corrector
d_in
Syndrome
Transform
Key
Equation
Solver
Error
Locator
Output
Processing
Unit
d_out
ram
ready
err_fnd
rst_b
sync
Control
blk_start
blk_end
clk
Functional Description
The data received by the RS Decoder is Reed-Solomon encoded data. This data is a representation of a polyno-
mial in a Galois Field. If there are no errors in the received data, the data polynomial will evaluate to zero at the
roots of the generator polynomial. This result is obtained because the roots of the generator polynomial and
received data polynomial are the same when no errors are present. If the received data has been corrupted during
the transmission, the polynomial will not evaluate to zero. The RS Decoder can construct the syndrome polynomial
by evaluating the received polynomial at all the roots of the generator polynomial. Once the syndrome polynomial
has been constructed, it can be used to solve the Error Locator polynomial and Error Evaluator polynomial. Using
these two polynomials, the decoder can find the error locations and magnitudes. Finally, the decoder can correct
the errors in the received data, provided the errors are in the range of possible correction (determined by the level
of encoding that has been performed).
If there are errors in the received codeword, it can be expressed as follows:
r(x) = c(x) + e(x)
where:
• c(x) is the Transmitted codeword.
• r(x) is the Received codeword.
• e(x) is the Error polynomial.
The syndrome polynomial S(x) is obtained by evaluating the received word at each root of the generator polyno-
mial. The Error Locator polynomial
Λ
(x) is orthogonal to the syndrome polynomial in the Galois field. This can be
represented as:
S(x)
Λ
(x) =
Ω
(x) mod x
2t
where:
4
Lattice Semiconductor
•
Ω
(x) is the Error Evaluator polynomial.
• 2t is the number of check symbols introduced by the decoder.
Reed-Solomon Decoder User’s Guide
The following sections describe the function of each block of the RS Decoder.
Syndrome Transform
The Syndrome Transform (also called Syndrome Generation) block evaluates the received codeword of the gener-
ator polynomial. If the received data contains an error, the syndrome polynomial generated will be non-zero. If the
received data has no error, the syndrome polynomial is zero, and the data is passed out of the decoder without any
error correction.
Key Equation Solver
This is the heart of the Reed-Solomon Decoder. This block generates the Error Locator polynomial
Λ
(x) (also
known as the “Key Equation” as it is the key to solve the decoding problem). After the Error Locator polynomial has
been found, it is used to determine the Error Evaluator polynomial
Ω
(x).
Error Locator
This block is implemented using the Chien-search method. Essentially, this method evaluates the Error Locator
polynomial at all the elements in the Galois Field. The Error Locator polynomial evaluates to zero at its roots. The
Chien-search takes m cycles, where m is the number of elements in the Galois Field. After m cycles, all roots have
been determined. If the roots are determined before the m cycles are over, the search is terminated early.
Error Magnitude Corrector
Once the location of the error has been determined, the Error Magnitude Corrector evaluates the evaluator polyno-
mial at the root. It uses the result to calculate the value of the error at the given location. Once this has been deter-
mined, the value is added to the received word to recover the corrected data. The addition occurs after the Error
Locator evaluates to zero.
Control Circuit
The control circuit handles the interface, pipelining and handshaking communication between the various blocks
and the I/O pins. The control circuit moves the data without processing it through the decoder when no error is
detected. Similarly, when the number of errors exceeds the maximum range of correction, the control circuit stops
all data processing activities. The control circuit interacts with the other blocks to generate the status signals like
fail
,
err_fnd
,
err_cnt
,
ers_cnt
and other handshaking signals. Once the block has been processed, the
control circuit sends out the ready signal to the output to start the processing of the next data.
5
京公网安备 11010802033920号
EEWORLD
