Browse Prior Art Database

Convenient Roots for a Reed Solomon Code

IP.com Disclosure Number: IPCOM000043189D
Original Publication Date: 1984-Jul-01
Included in the Prior Art Database: 2005-Feb-04
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Graham, TA: AUTHOR [+2]

Abstract

The Reed Solomon error correction code (RS code) has variations that lead to simpler parity generation and parity checking circuits. The text book example of an RS code with n parity symbols chooses some primitive field element a and uses a parity generator of the form: (Image Omitted) Working with symbols drawn from GF(2q), and with 5 parity symbols, this expands to: (Image Omitted) If polynomial (1) is changed so that i = -2, -1, 0, 1, 2, the expansion reduces to: (Image Omitted) This is more easily implemented, since there are fewer distinct coefficients.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 64% of the total text.

Page 1 of 2

Convenient Roots for a Reed Solomon Code

The Reed Solomon error correction code (RS code) has variations that lead to simpler parity generation and parity checking circuits. The text book example of an RS code with n parity symbols chooses some primitive field element a and uses a parity generator of the form:

(Image Omitted)

Working with symbols drawn from GF(2q), and with 5 parity symbols, this expands to:

(Image Omitted)

If polynomial (1) is changed so that i = -2, -1, 0, 1, 2, the expansion reduces to:

(Image Omitted)

This is more easily implemented, since there are fewer distinct coefficients. To generalize, if n is an integer, then to create an RS code with 2n parity symbols, use the generator polynomial:

(Image Omitted)

and to create an RS code with 2n+1 parity symbols, use the generator polynomial:

(Image Omitted)

The form of these coefficients can be simplified. Choose an element b from GF(2q) such that multiplication by b can be implemented simply, and such that for some integer k, which is prime relative to 2q-1, there exists a primitive element q for which b = q-k + qk Now substitute qk for a in polynomial (4). Thus, for example, the generator polynomial for an RS code with five parity symbols becomes:

(Image Omitted)

Specific Example To build an RS code with symbols from GF(256), use APL to create an instance of GF(256) with primitive element q. For this field, list the values of i and j which satify equation (6) below, and for which i is prime relat...