Reed–Solomon Decoding

National Instruments has partnered with Prentice Hall to bring you large portions of in-depth technical topics from several PTR RF and Communications books, including Digital Communications: Fundamentals and Applications, 2nd Edition. This series of content is designed for a broad range of audiences, from experts who want to review a specific topic to students who need easy-to-understand documentation for their projects.

For the complete list of RF topics, please visit the RF and Communications Resource Main Page.

8.1.6 Reed–Solomon Decoding

In Section 8.1.5, a test message encoded in systematic form using a (7, 3) R–S code,

resulted in a codeword polynomial described by Equation (8.26). Now, assume that

during transmission, this codeword becomes corrupted so that 2 symbols are

received in error. (This number of errors corresponds to the maximum errorcorrecting

capability of the code.) For this 7-symbol codeword example, the error

pattern can be described in polynomial form as

For this example, let the double-symbol error be such that

[+] Enlarge Image

In other words, one parity symbol has been corrupted with a 1-bit error (seen

as ), and one data symbol has been corrupted with a 3-bit error (seen as ). The

received corrupted-codeword polynomial r(X) is then represented by the sum of

the transmitted-codeword polynomial and the error-pattern polynomial as follows:

Following Equation (8.30), we add U(X) from Equation (8.26) to e(X) from

Equation (8.29) to yield

[+] Enlarge Image

In this 2-symbol error-correction example, there are four unknowns—two

error locations and two error values. Notice an important difference between the

nonbinary decoding of r(X) that we are faced with in Equation (8.31) and the binary

decoding that was described in Chapter 6. In binary decoding, the decoder

only needs to find the error locations. Knowledge that there is an error at a particular

location dictates that the bit must be “flipped” from a 1 to a 0, or vice versa. But

here, the nonbinary symbols require that we not only learn the error locations, but

that we also determine the correct symbol values at those locations. Since there are

four unknowns in this example, four equations are required for their solution.

8.1.6.1 Syndrome Computation

Recall from Section 6.4.7, that the syndrome is the result of a parity check

performed on r to determine whether r is a valid member of the codeword set. If in

fact r is a member, then the syndrome S has value 0. Any nonzero value of S indicates

the presence of errors. Similar to the binary case, the syndrome S is made up

of n − k symbols, {S_i} (i = 1, . . . , n − k). Thus, for this (7, 3) R–S code, there are four

symbols in every syndrome vector; their values can be computed from the received

polynomial r(X). Note how the computation is facilitated by the structure of the

code, given by Equation (8.27) and rewritten as

From this structure it can be seen that every valid codeword polynomial

U(X) is a multiple of the generator polynomial g(X). Therefore, the roots of g(X)

must also be the roots of U(X). Since r(X) = U(x) + e(X), then r(X) evaluated at

each of the roots of g(X) should yield zero only when it is a valid codeword. Any

errors will result in one or more of the computations yielding a nonzero result. The

computation of a syndrome symbol can be described as

where r(X) contains the postulated 2-symbol errors as shown in Equation (8.29). If

r(X) were a valid codeword, it would cause each syndrome symbol S_i to equal 0.

For this example, the four syndrome symbols are found as follows:

The results confirm that the received codeword contains an error (which we

inserted) since S ≠ 0.

Example 8.3 A Secondary Check on the Syndrome Values

For the (7, 3) R–S code example under consideration, the error pattern is known since

it was chosen earlier. Recall the property of codes presented in Section 6.4.8.1

when describing the standard array. Each element of a coset (row) in the standard

array has the same syndrome. Show that this property is also true for the R-S code by

evaluating the error polynomial e(X) at the roots of g(X) to demonstrate that it must

yield the same syndrome values as when r(X) is evaluated at the roots of g(X). In

other words, it must yield the same values obtained in Equations (8.33) through

(8.36).

                                              

These results confirm that the syndrome values are the same, whether obtained by

evaluating e(X) at the roots of g(X), or r(X) at the roots of g(X).

8.1.6.2 Error Location

Suppose there are v errors in the codeword at location X^j1, X^j2, . . . X^jv. Then,

the error polynomial shown in Equations (8.28) and (8.29) can be written as

[+] Enlarge Image

There are 2t unknowns (t error values and t locations), and 2t simultaneous

equations. However, these 2t simultaneous equations cannot be solved in the usual

way because they are nonlinear (as some of the unknowns have exponents). Any

technique that solves this system of equations is known as a Reed–Solomon decoding

algorithm.

When a nonzero syndrome vector (one or more of its symbols are nonzero)

has been computed, it signifies that an error has been received. Next, it is necessary

to learn the location of the error or errors. An error-locator polynomial can be defined as

 

The roots of  The reciprocal of the roots of

 are the error-location numbers of the error pattern e(X). Then using autoregressive

modeling techniques [5], we form a matrix from the syndromes, where the first

t syndromes are used to predict the next syndrome. That is,

We apply the autoregressive model of Equation (8.40) by using the largest

dimensioned matrix that has a nonzero determinant. For the (7, 3) double symbol

error-correcting R-S code, the matrix size is 2 × 2, and the model is written as

To solve for the coefficients  and  of the error-locator polynomial  ,

we first take the inverse of the matrix in Equation (8.42). The inverse of a matrix

[A] is found as follows:

 

Safety Check. If the inversion was performed correctly, then the multiplication

of the original matrix by the inverted matrix should yield an identity matrix:

Continuing from Equation (8.42), we begin our search for the error locations

by solving for the coefficients of the error-locator polynomial (X), as follows:

From Equations (8.39) and (8.47),

The roots of   are the reciprocals of the error locations. Once these roots

are located, the error locations will be known. In general, the roots of   may be

one or more of the elements of the field. We determine these roots by exhaustive

testing of the   polynomial with each of the field elements, as shown below.

Any element X that yields   = 0 is a root, and allows us to locate an error:

The two errors were found at locations  Note that the indexing of

the error-location numbers is completely arbitrary. Thus, for this example, we can

designate the 

 

8.1.6.3 Error Values

We can write these equations in matrix form as follows:

To solve for the error values e₁ and e₂, the matrix in Equation (8.52) is inverted

in the usual way, yielding

Now, we solve Equation (8.52) for the error values, as follows

8.1.6.4 Correcting the Received Polynomial with Estimates of the Error Polynomial

From Equation (8.49) and (8.54), the estimated error polynomial is formed,

to yield

The demonstrated algorithm repairs the received polynomial yielding an estimate

of the transmitted codeword, and ultimately delivers a decoded message.

That is,

Since the message symbols constitute the rightmost k = 3 symbols, the decoded

message is

which is exactly the test message that was chosen in Section 8.1.5 for this example.

(For further reading on R-S coding, see the collection of papers in reference [6].)

Relevant NI products

Customers interested in this topic were also interested in the following NI products:

• RF and Communication Hardware and Software
  
• Other Modular Instruments (digital multimeters, digitizers, switching, etc...)
• LabVIEW Graphical Programming Environment

For the complete list of tutorials, return to the NI RF and Communications Fundamentals Main page.

Buy the Book

Purchase Digital Communications from Prentice Hall Professional through this link and receive the following:

• Between 15% and 30% Off
• Free Shipping and Handling

Reader Comments | Submit a comment »