Freescale Semiconductor
Application Note
AN2407
Rev. 1, 12/2004
Freescale Semiconductor, Inc., 2003, 2004. All rights reserved.
This application note describes the implementation of the Reed-
Solomon error-control codes on the StarCoreTM SC140 DSP
core. Reed-Solomon codes are the preferred error-control
coding procedures in a wide range of applications, such as
ADSL, digital cellular phones, storage devices, and deep-space
communications. Their popularity originates from their strong
capability to correct both random and burst errors.
The current trend for improving DSP-processing speed is to
place multiple processor units on a single chip with an
architecture that supports parallel execution. The StarCore
SC140 family of DSPs exemplifies this trend. It has four data-
arithmetic units (DALUs) and two address-generation units
(AGUs). Code implementation for these processors should
capitalize on their capabilities. This document describes the
implementation of the Reed-Solomon encoder and decoder on
the SC140 core. The document begins with a basic theoretical
background on the Reed-Solomon algorithm and then discusses
the implementation of the encoder and decoder. Little or no
background on the subject is required.
CONTENTS
1
Basics of Forward Error Correction (FEC) .............2
2
Theory ..................................................................... 3
2.1
Galois Fields ........................................................... 3
2.2
Reed-Solomon Codes ..............................................6
2.3
Error-Correcting Performance of
Reed-Solomon Codes ..............................................9
3
SC140 Core Overview ..........................................10
4
Implementation on the SC140 Core.......................12
4.1
Polynomial Evaluation Over GF(256) .................. 13
4.2
MAC Instructions Over Galois Fields ..................14
4.3
Look-up Tables .....................................................14
4.4
Lowest Cycle Count Limit for Polynomial
Evaluation .............................................................15
4.5
Cycle Count of the Reed-Solomon Routines ........16
5
Results ................................................................... 17
6
Summary ............................................................... 19
7
References .............................................................19
Reed Solomon Encoder/Decoder on
the StarCoreTM SC140/SC1400 Cores,
With Extended Examples
By Jasmin Oz and Assaf Naor
Reed Solomon Encoder/Decoder on the StarCoreTM SC140/SC1400 Cores, With Extended Examples, Rev. 1
2
Freescale Semiconductor
Basics of Forward Error Correction (FEC)
1
Basics of Forward Error Correction (FEC)
In an ideal communication scheme, the information received is identical to the source transmission. However, in a
typical real communication scheme, the information passes through a noisy communication channel to the receiver.
The information received at the destination is likely to contain errors due to the channel noise. The acceptable level
of transmitted signal corruption (error level) depends on the application. Voice communication, for example, is
relatively error tolerant. However, the prospect of occasionally losing a digit in communications of financial data
highlights the need for error-control mechanisms.
In 1948, C.E. Shannon proved in his classic paper [1] that a communications channel can be made arbitrarily
reliable by encoding the information so that a fixed fraction of the channel is used for redundant information. In the
years that followed, there was a rapid development in designing FEC schemes. Today, a variety of effective coding
algorithms are widely used. FEC offers a number of benefits:
Data integrity is critical in the design of most digital communication systems and all storage devices.
Along with the design trend toward increasing bandwidths and data volumes, there is a drive to
decrease the allowed error rates. FEC enables a system to achieve high data reliability.
FEC yields low error rates and performance gains for systems in which other options, such as
increasing the transmitted power or installing noise-limiting components, are too expensive or
impractical.
System costs may be reduced by eliminating an expensive or sensitive component and compensating
for the lost performance by a suitable FEC scheme.
For an overview of FEC schemes, consult [2] and [3].
FEC adds carefully designed information to the transmitted data and uses this redundant information to reconstruct
the potentially corrupted data. Figure 1 depicts a typical communications scheme.
Figure 1. FEC Communications System
The two main type of error-control codes used in communications systems are as follows:
Convolutional codes. Each bit depends on the current bit as well as on a number of previous bits. In
this sense, the convolutional code has a memory. The most common scheme for decoding
convolutional codes is the Viterbi algorithm.
Block codes. A bitstream is divided into message blocks of fixed length called frames. The valid code-
word block is formed from the message bitstream by adding a proper redundant part. Each code word
is independent of the previous one, so the code is memory-less.
Source Encoder
FEC Encoder
Modulation
Demodulation
FEC Decoder
Source Decoder
Destination
Input Source
Channel
Noise
Theory
Reed Solomon Encoder/Decoder on the StarCoreTM SC140/SC1400 Cores, With Extended Examples, Rev. 1
Freescale Semiconductor
3
The Reed-Solomon codes are block codes. Unlike convolutional codes, Reed-Solomon codes operate on multi-bit
symbols rather than on individual bits. The question of whether to choose convolutional codes or block codes
depends on several variables. In low-speed, low-integrity applications, convolutional codes are the better choice,
and block codes are suitable for high-speed, high-integrity applications. An example of an application suited to
convolutional codes is a digitized voice communication in which a relatively high bit-error rate (about 10
3
) is
acceptable. For blocks of machine-oriented data in which the desired bit-error rate ranges from 10
10
to 10
14
,
block codes are the natural choice. Some applications use both convolutional and block codes. In such applications,
concatenated codes result in strong performance by operating in two steps. The inner decoder, usually
convolutional, reduces the bit-error rate to a medium-low level, and the outer decoder, usually a block type,
reduces the bit-error rate further, to a very low level.
The errors introduced by the communications channel are classified into two main categories:
Random errors. The bit-error probabilities are independent of each other. For example, thermal noise
in communication channels typically causes random errors.
Burst errors. The bit errors occur sequentially in time. Burst errors can be caused by such conditions as
a fading communications channel or mechanical defects in a storage system.
When an FEC system is designed, the statistical nature of the noise environment must be considered, as well as the
acceptable output bit-error rate. When the environment consists predominately of random errors, convolutional
codes provide a low bit-error rate solution. However, when the environment has lower bit-error rates, long-length
block codes often perform even better. In burst-error channels, Reed-Solomon codes are among the best codes
because errors composed of many consecutive corrupted bits translate into only a few erroneous symbols.
2
Theory
The Reed-Solomon code was developed in 1960 by I. Reed and G. Solomon [4]. This code is an error detection and
correction scheme based on the use of Galois field arithmetic. This section provides background information on
binary and extended Galois fields and summarizes the essence of the Reed-Solomon codes. For details on Reed-
Solomon codes, consult the literature, for example, [5] and [6].
2.1 Galois Fields
A number field has the following properties:
Both an addition and a multiplication operation that satisfy the commutative, associative, and
distributive laws.
Closure, so that adding or multiplying elements always yields field elements as results.
Both zero and unity elements. The zero element leaves an element unchanged under addition. The
unity element leaves an element unchanged under multiplication.
An additive/multiplicative inverse for each field element. The sole exception is the zero element,
which has no multiplicative inverse.
Division is defined as the inverse of multiplication such that if a
b = c, it follows that c divided by a yields b. An
example of a number field is the set of real numbers together with the addition and multiplication operations.
Galois fields differ from real number fields in that they have only a finite number of elements. Otherwise, they
share all the properties common to number fields.
Reed Solomon Encoder/Decoder on the StarCoreTM SC140/SC1400 Cores, With Extended Examples, Rev. 1
4
Freescale Semiconductor
Theory
2.1.1 Binary Field, GF(2)
The simplest Galois field is GF(2). Its elements are the set {0,1} under modulo-2 algebra. Addition and subtraction
in this algebra are both equivalent to the logical XOR operation. The addition and multiplication tables of GF(2)
are shown in Figure 2.
Figure 2. Addition (XOR) and Multiplication Tables of GF(2)
There is a one-to-one correspondence between any binary number and a polynomial in that every binary number
can be represented as a polynomial over GF(2), and vice versa. A polynomial of degree D over GF(2) has the
following general form:
where the coefficients f
0
,..., f
D
are taken from GF(2). A binary number of (N+1) bits can be represented as an
abstract polynomial of degree N by taking the coefficients equal to the bits and the exponents of x equal to the bit
locations.
For example, the binary number 100011101 is equivalent to the following polynomial:
The bit at the zero position (the coefficient of x
0
) is equal to 1, the bit at the first position (the coefficient of x) is
equal to 0, the bit at the second position (the coefficient of x
2
) is equal to 1, and so on. Operations on polynomials,
such as addition, subtraction, multiplication and division, are performed in an analogous way to the real number
field. The sole difference is that the operations on the coefficients are performed under modulo-2 algebra. For
example, the multiplication of two polynomials is as follows:
This result differs from the result obtained over the real number field (the middle expression) due to the XOR
operation (the + operation). The terms that appear an even number of times cancel out, so the coefficients of x
5
and
x
7
are not present in the end result.
2.1.2 Extended Galois Fields GF(2
m
)
A polynomial p(x) over GF(2) is defined as irreducible if it cannot be factored into non-zero polynomials over
GF(2) of smaller degrees. It is further defined as primitive if n = (x
n
+ 1) divided by p(x) and the smallest positive
integer n equals 2
m
1, where m is the polynomial degree. An element of GF(2
m
) is defined as the root of a
primitive polynomial p(x) of degree m. An element
is defined as primitive if
Addition
+
0
1
0
0
1
1
1
0
Multiplication
x
0
1
0
0
0
1
0
1
f x
( )
f
0
f
1
x
f
2
x
2
f
3
x
3
... f
+
D
x
D
+
+
+
=
100011101
1
x
2
x
3
x
4
x
8
+
+
+
+
1
x
2
x
3
x
4
+
+
+
(
) x
3
x
5
+
(
)
x
3
x
5
x
5
x
6
x
7
x
7
x
8
x
9
x
3
x
6
x
8
x
9
+
+
+
=
+
+
+
+
+
+
+
=
imod(2
)
m1
Theory
Reed Solomon Encoder/Decoder on the StarCoreTM SC140/SC1400 Cores, With Extended Examples, Rev. 1
Freescale Semiconductor
5
where
, can produce 2
m1
field elements (excluding the zero element). In general, extended Galois fields of
class GF(2
m
) possess 2
m
elements, where m is the symbol size, that is, the size of an element, in bits. For example,
in ADSL systems, the Galois field is GF(256). It is generated by the following primitive polynomial:
1+x
2
+x
3
+x
4
+x
8
This is a degree-eight irreducible polynomial. The field elements are degree-seven polynomials. Due to the one-to-
one mapping that exists between polynomials over GF(2) and binary numbers, the field elements are representable
as binary numbers of eight bits each, that is, as bytes. In GF(2
m
) fields, all elements besides the zero element can be
represented in two alternative ways:
1.
In binary form, as an ordinary binary number.
2.
In exponential form, as
p
. It follows from these definitions that the exponent p is an integer ranging
from 0 to (2
m
2). Conventionally, the primitive element is chosen as 0x02, in binary representation.
As for GF(2), addition over GF(2
m
) is the bitwise XOR of two elements. Galois multiplication is performed in two
steps: multiplying the two operands represented as polynomials and taking the remainder of the division by the
primitive polynomial, all over GF(2). Alternatively, multiplication can be performed by adding the exponents of
the two operands. The exponent of the product is the sum of exponents, modulo 2
m
1.
Polynomials over the Galois field are of cardinal importance in the Reed-Solomon algorithm. The mapping
between bitstreams and polynomials for GF(2
m
) is analogous to that of GF(2). A polynomial of degree D over
GF(2
m
) has the most general form:
where the coefficients f
0
f
D
are elements of GF(2
m
). A bitstream of (N+1)m bits is mapped into an abstract
polynomial of degree N by setting the coefficients equal to the symbol values and the exponents of x equal to the bit
locations. The Galois field is GF(256), so the bitstream is divided into symbols of eight consecutive bits each. The
first symbol in the bitstream is 00000001. In exponential representation, 00000001 becomes
0
. Thus,
0
becomes
the coefficient of x
0
. The second symbol is 11001100, so the coefficient of x is
127
and so on.
The elements are conventionally arranged in a log table so that the index equals the exponent, and the entry equals
the element in its binary form. Table 1 displays the log table for ADSL systems.
Table 1. Exponential-to-Binary Table for ADSL Systems
p
p
0
0x01
1
0x02
2
0x04
3
0x08
4
0x10
i
N
f x
( )
f
0
f
1
x
f
2
x
2
f
3
x
3
... f
+
D
x
D
+
+
+
=
11110011
11111101
10110111
01110101
11001100
00000001
233
80
158
21
127
0
f(x) =
0
+
127
x
+
21
x
2
+
158
x
3
+
80
x
4
+
233
x
5
...
PDF 
ZIP