Browse Prior Art Database

Implementation of Reed Solomon Codes over Symbols of Size 16 Bits - Method and Apparatus

IP.com Disclosure Number: IPCOM000111100D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 2 page(s) / 68K

Publishing Venue

IBM

Related People

Blaum, M: AUTHOR [+3]

Abstract

Disclosed is a method of implementing Reed Solomon (RS) codes over 16-bit symbols. The traditional method involves storing a table containing the 2(16) vectors of size 16, which has prohibitive complexity. This problem was overcome by considering each 16-bit symbol as a pair of 8-bit bytes and using a complex-type of arithmetic for products and inversions. In fact, our method can be extended to bytes of any size. Refer here to 8-bit bytes for simplicity.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Implementation of Reed Solomon Codes over Symbols of Size 16 Bits
- Method and Apparatus

      Disclosed is a method of implementing Reed Solomon (RS) codes
over 16-bit symbols.  The traditional method involves storing a table
containing the 2(16)  vectors of size 16, which has prohibitive
complexity.  This problem was overcome by considering each 16-bit
symbol as a pair of 8-bit bytes and using a complex-type of
arithmetic for products and inversions.  In fact, our method can be
extended to bytes of any size.  Refer here to 8-bit bytes for
simplicity.

      Pairs of symbols can be grouped in GF(2(8)) into 16-bit symbols
of a larger field, GF(2(16)), allowing us to use RS codes whenever
the length of the code n is smaller than 2(16)=65536.  Such an upper
bound on the code length seems to be more than enough for most
foreseeable applications.

      Nevertheless, there is a price to shifting to a larger field,
and that is more complicated operations in that field.  In this
disclosure, we show how to make such a price not too high, provided
that the representation of the higher field is set properly.

      Our method is based on the following proposition [1], whose
proof relies on the fact that 2(8)+1=257 is a prime number.

Proposition:

      Let &beta.  be a primitive element in GF(2(8)) of trace 1.
Then, the polynomial x(2)+x+&beta.  is primitive over GF(2(8)).

      Let P(x) be the primitive polynomial of degree 8 over GF(2),
P(x)=x(8)+x(7)+x(6)+x+1, and let &beta.  be a root of P(x) in
GF(2(8)).  Also, let Q(z) denote the primitive polynomial
z(2)+z+&beta.  over GF(2(8)) and let &Omega.  be a root of Q(z) in
GF(2(16)).  For each element u in GF(2(8)) we associate a row vector
u=u(0),u(1),...,u(7)  such that u=u(0)+u(1) &beta.+...+u(7)
&beta.(7).  Similarly, each element &alpha.  i...