Shared galois field multiplier

Details Shared galois field multiplier Shared galois field multiplier

1999-11-12

2004-03-02

Mai, Tan V. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C380S028000

Reexamination Certificate

active

06701336

ABSTRACT:

BACKGROUND OF THE INVENTION
The invention relates generally to error correcting systems and, more particularly, to error correcting systems which perform Galois field multiplication during encoding and decoding processes.
As storage systems migrate to longer sector sizes, error correcting codes (ECC) with longer block lengths are needed. One way to achieve format efficiency is to use different field element (e.g., symbol) sizes—smaller symbols for shorter sectors and larger symbols for longer sectors. Symbols of different sizes can share some frequently used field operations. For example, addition may be performed for differently sized symbols using exclusive-OR adders. Galois field multiplication, which multiplies two elements in a Galois field, is frequently used in error correction encoding and decoding hardware, such as Reed-Solomon encoders or decoders, but requires dedicated multiplier hardware for each different symbol size. Consequently, error correction systems having one type of Galois field multiplier to accommodate a symbol/sector size are incompatible with alternative symbol/sector sizes. Some well-known field multipliers are described in Berlekamp, Algebraic Coding Theory, Academic Press, 1968, at pps. 47-48, as well as Peterson and Weldon, Error Correction Codes, 2d Edition, MIT Press, 1972, at pps. 170-182.
SUMMARY OF THE INVENTION
This invention features a Galois field multiplier that can operate on field elements of more than one size.
Generally, in one aspect of the invention, a Galois field multiplier includes computation circuitry for receiving an input, the computation circuitry being responsive to a control signal to perform computations based on the input having a first size to produce an output of the first size, or to perform computations based on the input having a second, different size to produce an output of the second size.
Embodiments of the invention may include one or more of the following features.
The computation circuitry can include select circuitry, responsive to the control signal, for configuring the computation circuitry.
In one embodiment, the input can be an element of a Galois field GF(2
m
) of a cyclic type (“cyclic Galois field”), that is, having a generator polynomial of the form x
m
+x
m−1
+x
m−2
+ . . . +x+1, and the computation circuitry can further include shifting circuitry, coupled to and responsive to the select circuitry, for performing a cyclic shifting of bits of the input.
The first size can be 10 bits and the associated input an element of the cyclic Galois field GF(2
10
). The second size can be 12 bits and the associated input an element of the cyclic Galois field GF(2
12
). The shifting circuitry can further include a plurality of shifting units connected in parallel, a first one of the shifting units for receiving input values for the input and cyclically shifting the input values, each next consecutive one of the other shifting units receiving a cyclically shifted output from a previous one of the shifting units and cyclically shifting the cyclically shifted output.
The input can be a first input and the computation circuitry can receive a second input of the same size as the first input. The field multiplier can further include: a plurality of AND gates, each of the AND gates coupled to a value of the second input, a least significant one of the AND gates coupled to the received input values of the first input, a next most significant one of the AND gates coupled to cyclically shifted output of the first one of the shifting units, and each next most significant one of the AND gates coupled to and receiving a cyclically shifted output from the next consecutive one of the other shifting units to form product values; and a plurality of Galois field adders, one adder for each input value, each adder for receiving one of the product values for a corresponding one of the input values from each of the AND gates, for producing a set of multiplier output values of the output.
In another embodiment, the input can be a first input and the computation circuitry can receive a second input having the same size as the first input. The first and second inputs of the Galois field multiplier can each be elements of an extended Galois field GF((2
m
)
k
) over a field GF(2
m
). In this alternative embodiment, the computation circuitry can be implemented to compute the product of the first and second inputs using the Karatsuba-Ofman algorithm and can further include a plurality of base multipliers coupled to the control line, each of the base multipliers for taking the multiplications over the field GF(2
m
). Each of the plurality of base multipliers can include base multiplier computation circuitry for receiving base multiplier inputs to produce base multiplier outputs, the base multiplier computation circuitry being adapted to respond to the control signal.
The shared-field multiplier of the invention offers several advantages. First, it performs the job of at least two dedicated multiplier circuits with reduced hardware complexity by exploiting common attributes of multiplication operations in different fields. Second, the shared-field multiplier allows ECC systems to satisfy different sector length requirements with flexibility and efficiency. ECC systems designed for a first symbol size may be compatible with and can therefore be upgraded to a second symbol size as sector and ECC block formats change.
Other features and advantages of the invention will be apparent from the following description taken together with the claims.


REFERENCES:
patent: 4866716 (1989-09-01), Weng
patent: 5107503 (1992-04-01), Riggle et al.
patent: 5136592 (1992-08-01), Weng
patent: 5381423 (1995-01-01), Turco
patent: 5948117 (1999-09-01), Weng et al.
patent: 6141420 (2000-10-01), Vanstone et al.
patent: 6148430 (2000-11-01), Weng
patent: 6199088 (2001-03-01), Weng et al.
patent: 6230179 (2001-05-01), Dworkin et al.
patent: 6349318 (2002-02-01), Vanstone et al.
patent: 6366941 (2002-04-01), Wolf et al.
patent: 6374383 (2002-04-01), Weng
Richard E. Blahut “A Theory and Practice of Error Control Codes”, Addison-Wesley Publishing Company, Reading MA, table of contents, chapter 4 pp. 65-92, chapter 5, pp. 93-129, and chapter 8 pp. 207-247 (1983).
Peterson et al., “Error-Correcting Codes, Second Edition”, MIT Press, Cambridge, MA, London, England, table of contens, chapter 4 pp. 76-115, chapter 6 pp. 144-169, chapter 7 pp. 170-205, and chapter 8 pp. 206-265 (1972).
E.D. Mastrovito, “A VLSI Design for Multiplication Over Finite Field GF(2m)”, Lecture Notes in Computer Science 357, pp. 297-309, Springer-Verlag, Berlin (Mar. 1989).
Berlekamp, “Algebraic Coding Theory”, pp. 47-48, Academic Press (1968).
Wofl, “Efficient circuits for multiplying in GF(2m) for certain values of m”,Discrete Mathematics106/107:497-502 (1992).

Affiliated with

Also associated with

Rating

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

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3286432