Reed–Solomon Encoding

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.5 Reed–Solomon Encoding

Equation (8.2) expresses the most conventional form of Reed–Solomon (R–S)

codes in terms of the parameters n, k, t, and any positive integer m > 2. Repeated

here, that equation is

where n − k = 2t is the number of parity symbols, and t is the symbol-error correcting

capability of the code. The generating polynomial for an R-S code takes the following

form:

The degree of the generator polynomial is equal to the number of parity

symbols. R-S codes are a subset of the BCH codes described in Section 6.8.3 and

Table 6.4. Hence, it should be no surprise that this relationship between the degree

of the generator polynomial and the number of parity symbols holds just as it does

for BCH codes. This can be verified by checking any of the generator polynomials

in Table 6.4. Since the generator polynomial is of degree 2t, there must be precisely

2t successive powers of that are roots of the polynomial. We designate the roots

of g(X) as:  It is not necessary to start with the root ; starting with

any power of is possible. Consider as an example, the (7, 3) double-symbol error

correcting R-S code. We describe the generator polynomial in terms of its 2t =

n − k = 4 roots, as follows:

Following the format of low order to high order, and changing negative signs to

positive, since in the binary field + 1 = −1, the generator g(X) can be expressed as

8.1.5.1 Encoding in Systematic Form

Since R-S codes are cyclic codes, encoding in systematic form is analogous to

the binary encoding procedure established in Section 6.7.3. We can think of shifting

a message polynomial m(X) into the rightmost k stages of a codeword register and

then appending a parity polynomial p(X) by placing it in the leftmost n − k stages.

Therefore we multiply m(X) by X^{n − k}, thereby manipulating the message polynomial

algebraically so that it is right-shifted n − k positions. In Chapter 6, this is

shown in Equation (6.61) in the context of binary encoding. Next, we divide X^{n − k}

m(X) by the generator polynomial g(X), which is written as

where q(X) and p(X) are quotient and remainder polynomials, respectively. As in the

binary case, the remainder is the parity. Equation (8.23) can also be expressed as

The resulting codeword polynomial U(X), shown in Equation (6.64), is

rewritten as

We demonstrate the steps implied by Equations (8.24) and (8.25) by encoding

the three-symbol message

with the (7, 3) R-S code whose generator polynomial is given in Equation (8.22). We first

multiply (upshift) the message polynomial 

yielding  We next divide this upshifted message polynomial by

the generator polynomial in Equation (8.22),   

Polynomial division with nonbinary coefficients is more tedious than its binary counterpart

(see Example 6.9), because the required operations of addition (subtraction)

and multiplication (division) must follow the rules in Tables 8.2 and 8.3,

respectively. It is left as an exercise for the reader to verify that this polynomial division

results in the following remainder (parity) polynomial:

Then, from Equation (8.25), the codeword polynomial can be written as

8.1.5.2 Systematic Encoding with an (n − k)-Stage Shift Register

Using circuitry to encode a 3-symbol sequence in systematic form with the

(7, 3) R-S code described by g(X) in Equation (8.22) requires the implementation

of a LFSR, as shown in Figure 8.9. It can be easily verified that the multiplier terms

in Figure 8.9 taken from left to right correspond to the coefficients of the polynomial

in Equation (8.22) (low order to high order). This encoding process is the nonbinary

equivalent of the cyclic encoding that was described in Section 6.7.5. Here,

corresponding to Equation (8.20), the (7, 3) R-S nonzero codewords are made up

of 2^m − 1 = 7 symbols, and each symbol is made of m = 3 bits.

Notice the similarity amongst Figures 8.9, 6.18, and 6.19. In all three cases the

number of stages in the shift register is n − k. The figures in Chapter 6 illustrate

binary examples where each shift-register stage holds 1 bit. Here the example is

nonbinary, so that each stage in the shift register of Figure 8.9 holds a 3-bit symbol.

In Figure 6.18, the coefficients labeled g₁, g₂,. . . are binary. Therefore, they take on

values of 1 or 0, simply dictating the presence or absence of a connection in the

LFSR. However in Figure 8.9, since each coefficient is specified by 3-bits, it can

take on one of 8 values.

The nonbinary operation implemented by the encoder of Figure 8.9, forming

codewords in a systematic format, proceeds in the same way as the binary one. The

steps can be described as follows:

1. Switch 1 is closed during the first k clock cycles to allow shifting the message

symbols into the (n − k)-stage shift register.

 

[+] Enlarge Image

                                   Figure 8.9 LFSR Encoder for a (7,3) R–S code.

2. Switch 2 is in the down position during the first k clock cycles in order to

allow simultaneous transfer of the message symbols directly to an output

register (not shown in Figure 8.9).

3. After transfer of the kth message symbol to the output register, switch 1 is

opened and switch 2 is moved to the up position.

4. The remaining (n − k) clock cycles clear the parity symbols contained in the

shift register by moving them to the output register.

5. The total number of clock cycles is equal to n, and the contents of the output

register is the codeword polynomial p(X) + X^{n − k}m(X), where p(X) represents

the parity symbols, and m(X) the message symbols in polynomial form.

We use the same symbol sequence that was chosen as a test message in

Section 8.1.5.1, and we write

                                                     

where the rightmost symbol is the earliest symbol, and the rightmost bit is the

earliest bit. The operational steps during the first k = 3 shifts of the encoding circuit

of Figure 8.9 are as follows:

After the third clock cycle, the register contents are the 4 parity symbols, 

 and , as shown. Then, switch 1 of the circuit is opened, switch 2 is toggled

to the up position, and the parity symbols contained in the register are shifted to

the output. Therefore the output codeword, written in polynomial form, can be expressed

as

[+] Enlarge Image

The process of verifying the contents of the register at various clock cycles is somewhat

more tedious than in the binary case. Here, the field elements must be added

and multiplied by using Table 8.2 and Table 8.3, respectively.

The roots of a generator polynomial g(X) must also be the roots of the codeword

generated by g(X), because a valid codeword is of the form

Therefore an arbitrary codeword, when evaluated at any root of g(X), must

yield zero. It is of interest to verify that the codeword polynomial in Equation

(8.26) does indeed yield zero when evaluated at the 4 roots of g(X). In other

words, this means checking that

Evaluating each term independently yields

This demonstrates the expected results that a codeword evaluated at any root of

g(X) must yield zero.

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 »