Galois field multiplier system

Details Galois field multiplier system Galois field multiplier system

2002-01-30

2004-07-20

Ngo, Chuong Dinh (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06766345

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to a Galois field multiplier system.
BACKGROUND OF THE INVENTION
Multiplication of polynomials with coefficients in Galois fields (GF) is widely used in communication systems for Reed Solomon (RS) coding and in advanced encryption standards (AES). Galois field multiplication is difficult and time consuming for traditional digital signal processors (DSP) to perform. DSP's are optimized for finite impulse response (FIR) filtering and other multiply accumulate (MAC) intensive operations, but do not efficiently process Galois field types of operations. One approach uses straight forward polynomial multiplication and division over the Galois field using linear feedback shift registers (LFSR's) which process one bit at a time. This is a very slow process. For example, in broadband communication for AES types of applications, where the bit rate is up to 40 megabits per second, there will be up to 5 million GF multiplications per second (MPS) and each multiplication may require many e.g. 60-100 operations. Another approach uses look-up tables to perform the Galois field multiplication. Typically, this approach requires 10-20 or more cycles which for 5 mps results in a somewhat lower but still very large number of operations e.g. 20×5=100 mps or more. Reed-Solomon codes have been widely accepted as the preferred error control coding scheme for broadband networks. A programmable implementation of a Reed-Solomon encoder and decoder is an attractive solution as it offers the system designer the unique flexibility to trade-off the data bandwidth and the error correcting capability that is desired based on the condition of the channel. The first step in Reed-Solomon decoding is the computing of the syndromes. The syndromes can be formally defined as Si=R mod G where i=(0,1 . . . 15). The received code word may be expressed in polynomial form as R
i
=r
o
X
N−1
+r
1
X
N−2
+ . . . r
N−1
where the length of the received word is N. It can be seen that computing the syndrome amounts to polynomial evaluation over Galois field at the roots as defined by the j′
th
power of the i′
th
root of the generator polynomial. For each received word in the Reed-Solomon Algorithm there are sixteen syndromes to be calculated which raise the operations by a factor of sixteen to 1.6 GIGA-operations per second-not practical on current microprocessors. Using the straight forward multiplication instead of the look-up tables raises the operation rate to 6.4 GIGA-operations per second. The need for Galois field multiplications is increasing dramatically with the expansion of the communications field and the imposition of encryption requirements on the communication data. This further complicates the matter because each domain-error checking, encryption-needs Galois field multiplication over a different Galois field which requires different sets of look-up tables.
BRIEF SUMMARY OF THE INVENTION
It is therefore an object of this invention to provide a new and improved Galois field multiplier system.
It is a her object of this invention to provide such a new and improved Galois field multiplier system which is much faster than current look-up tables and linear feedback shift registers (LFSR) implementations.
It is a further object of this invention to provide such a new and improved Galois field multiplier system which reduces the amount of storage required.
It is a further object of this invention to provide such a new and improved Galois field multiplier system which dramatically reduces the number of required operations per second.
It is a further object of this invention to provide such a new and improved Galois field multiplier system which can reduce the required operation to a fraction of a cycle.
The invention results from the realization that a Galois field multiplication can be effected by doing more then one Galois field multiplication in a cycle in two steps: first, the multiplication of the two polynomials with coefficients over a Galois field to obtain their product, and second, the division of their product by a predetermined irreducible polynomial to obtain the modulo remainder and the further realization that such a Galois field multiplication can be achieved with a system that has a Galois field linear transformer circuit which responds to the multiplication product to predict the modulo remainder and a storage circuit which supplies to the Galois field linear transformer circuit a set of coefficients for predicting the modulo remainder for a predetermined irreducible polynomial.
This invention features a Galois field multiplier system including a multiplier circuit for multiplying two polynomials with coefficients over a Galois field to obtain their product and a Galois field linear transformer circuit responsive to the multiplier circuit for predicting the modulo remainder of the polynomial product for an irreducible polynomial. A storage circuit supplies to the Galois field linear transformer circuit a set of coefficients for predicting the modulo remainder for a predetermined irreducible polynomial.
In a preferred embodiment, the Galois field linear transformer circuit may divide the polynomial product by the irreducible polynomial to obtain the modulo remainder. The multiplier circuit may include an AND-logic circuit for each term of the polynomial product to effect the Galois multiplication. The mulitplier circuit may include an exclusive Or-logic circuit for each pair of terms in the polynomial product to effect the Galois summation. The Galois field linear transformer circuit may include a Galois field linear transformer including a matrix responsive to a number of input bits in one or more bit streams and having a plurality of outputs for providing the Galois field linear transformation of those bits. The matrix may include a plurality of cells, each cell including an exclusive OR-logic circuit and an AND-logic circuit having an output connected to the exclusive OR-logic circuit and an input connected to one of the input bits. The Galois field linear transformer circuit may include a plurality of Galois field transformer units and the storage circuit may supply the coefficients in parallel to the Galois field transformer units. The Galois field linear transformer circuit may include a plurality of storage units, one associated with each of the Galois field linear transformer units. Wherein the storage circuit provides an input to the AND-logic circuit for setting the matrix to obtain a multi-cycle Galois field linear transformation of the inputs in a single cycle.


REFERENCES:
patent: 3303477 (1967-02-01), Voigt
patent: 3805037 (1974-04-01), Ellison
patent: 4722050 (1988-01-01), Lee et al.
patent: 4847801 (1989-07-01), Tong
patent: 4852098 (1989-07-01), Brechard et al.
patent: 4918638 (1990-04-01), Matsumoto et al.
patent: 5095525 (1992-03-01), Almgren et al.
patent: 5214763 (1993-05-01), Blaner et al.
patent: 5379243 (1995-01-01), Greenberger et al.
patent: 5386523 (1995-01-01), Crook et al.
patent: 5446850 (1995-08-01), Jeremiah et al.
patent: 5689452 (1997-11-01), Cameron
patent: 5832290 (1998-11-01), Gostin et al.
patent: 5996057 (1999-11-01), Scales, III et al.
patent: 6049815 (2000-04-01), Lambert et al.
patent: 6199086 (2001-03-01), Dworkin et al.
patent: 6199087 (2001-03-01), Blake et al.
patent: 6223320 (2001-04-01), Dubey et al.
patent: 6230179 (2001-05-01), Dworkin et al.
patent: 6246768 (2001-06-01), Kim
patent: 6349318 (2002-02-01), Vanstone et al.
patent: 6434662 (2002-08-01), Greene et al.
patent: 6587864 (2003-07-01), Stein et al.
patent: 2002/0041685 (2002-04-01), McLoone et al.
patent: 2002/0147825 (2002-10-01), Stein et al.
patent: 2003/0103626 (2003-06-01), Stein et al.
patent: 2003/0110196 (2003-06-01), Stein et al.
patent: 2003/0115234 (2003-06-01), Stein et al.
patent: 2003/0133568 (2003-07-01), Stein et al.
patent: 2003/0140211 (2003-07-01), Stein et al.
patent: 2003/0140212 (2003-07-01), Stein et al.
patent: 2003/0140213 (2003-07-01), Ste

Affiliated with

Also associated with

Rating

Galois field multiplier system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Galois field multiplier system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Galois field multiplier system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3211116