Appendix 3.1: Calculation of Reed-Solomon Generator Polynomials

Appendix 3.1: Calculation of Reed-Solomon Generator Polynomials

For a Reed-Solomon codeword over GF(2 ³ ), there will be seven three-bit symbols. For location and correction of one symbol, there must be two redundant symbols P and Q, leaving A-E for data.

The following expressions must be true, where a is the primitive element of x ³ • x • 1 and • is XOR throughout:

(1) 

(2) 

Dividing equation (2) by a :

a ⁶ A • a ⁵ B • a ⁴ C • a ³ D • a ² E • a P • Q = 0

= A • B • C • D • E • P • Q

Cancelling Q, and collecting terms:

( a ⁶ • 1)A • ( a ⁵ • 1)B • ( a ⁴ • 1)C • ( a ³ 1)D • ( a ² • 1)E

= ( a • 1)P

Using section 3.16 to calculate ( a ⁿ + 1), e.g. a ⁶ + 1 = 101 + 001 = 100 = a ² :

a ² A • a ⁴ B • a ⁵ C • a D • a ⁶ E = a ³ P

a ⁶ A • a B • a ² C • a ⁵ D • a ³ E = P

Multiplying equation (1) by a ² and equating to equation (2):

a ² A • a ² B • a ² C • a ² D • a ² E • a ² P • a ² Q = 0

= a ⁷ A • a ⁶ B • a ⁵ C • a ⁴ D • a ³ E • a ² P • a Q

Cancelling terms a ² P and collecting terms (remember a ² • a ² = 0):

( a ⁷ • a ² )A • ( a ⁶ • a ² )B • ( a ⁵ • a ² )C • ( a ⁴ • a ² )D •

( a ³ • a ² )E = ( a ² • a )Q

Adding powers according to section 3.16, e.g.

a ⁷ • a ² = 001 • 100 = 101 = a ⁶ :

a ⁶ A • B • a ³ C • a D • a ⁵ E = a ⁴ Q

a ² A • a ³ B • a ⁶ C • a ⁴ D • a E = Q