Pipelined bit-serial Galois Field multiplier

• US 4,797,848 A
• Filed: 04/18/1986
• Issued: 01/10/1989
• Est. Priority Date: 04/18/1986
• Status: Expired due to Fees

• Current Assignee: Hughes Aircraft Company (Rtx Corporation)
• Original Assignee: Hughes Aircraft Company (Rtx Corporation)
• Inventors: Walby, Douglas R.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): NGUYEN, LONG
• Application Number:
  US06/853,529
• Time in Patent Office: 998 Days
• Field of Search: 364/746, 364/754, 364/757-760, 364/768
• US Class Current: 708/492
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence

Abstract

A bit-serial pipeline Galois Field multiplier for multiplying an element K(X)=K_m-1 X^m-1 +K_m-2 X^m-2 X^m-2 +. . . +K₀ with another element Y(X)=Y_m-1 X^m-1 +Y_m-2 X^m-2 +. . . +Y₀ to obtain Z₀ =Z_m-1 X^m-1 +Z_m-2 X^m-2 +. . . +Z₀, which is also an element of the field generally defined by P(X)=a_m X^m +a_m-1 X^m-1 +a_m-2 X^m-2 +. . . a₁ X+a₀. The multiplier has an input shift register buffer circuit, an intermediate shift register circuit, an output shift register circuit and multiplying and summing device. The input shift register buffer circuit is configured for serially receiving the K(X) coefficients. The multiplying and summing device receives arrangements of K(X) coefficients and the Y(X) coefficients and operates thereon, by multiplying corresponding pairs of register stage elements and Y(X) coefficients and summing the products. The output shift register circuit receives the resulting coefficients and, beginning m clock intervals after the inputting of K(X) and Y(X) coefficients is started, starts continuous outputing of the product coefficients Z_m-1, Z_m-2, . . . , Z₀.

Claims

1. A pipeline Galois Field (2^m) multiplier for multiplying elements of a finite field, represented by factors K(X) and Y(X), to obtain a product Z(X), wherein K(X) has the form K(X)=K_m-1 X^m-1 +K_m-2 X^m-2 + . . . +K₀, Y(X) has the form Y(X)=Y_m-1 X^m-1 +Y_m-2 X^m-2 + . . . +Y_o and Z(X) has the form Z(X)=Z_m-1^m-1 +Z_m-2 X^m-2 + . . . +Z_o, said multiplier apparatus comprising:

(a) a serial in, parallel out input shaft register buffer circuit having m serially arranged register stages R_m-1, R_m-2, . . . , R₀ and being connected for serially receiving the K(X) coefficients K_m-1, K_m-2, . . . , K₀ ;

(b) computer means connected for receiving, in parallel, at a preselected clock pulse, the contents of the R_m-l, R_m-2, . . . , R₀ register stages of the initiating register circuit and for serially receiving the Y(X) coefficients Y_m-1, Y_m-2, . . . , Y₀, and for operating thereon to provide an intermediate series of m logic functions S_i =f_m-1 Y_m-1 +f_m-2 Y_m-2 + . . . +f₀ Y₀, wherein f_m-1, f_m-2, . . . , f₀ are functions of K_m-1, K_m-2, . . . , K₀ ;

(c) a serial in serial out output shift register circuit having m serial arranged shift register stages R_m-1 ", R_m-2 ", . . . , R₀ " and being connected for serially receiving the series of m logic functions S_i from the computing means and, in response thereto, providing a serial output of Z(X) product coefficients Z_m-1, Z_m-2, . . . , Z₀ ; and

(d) timing means for providing clock pulses to the input and output shift register circuits and to the computing means for synchronizing the operation thereof.

2. The Galois Field (2^m) multiplier as claimed in claim 1 wherein the input and output shift register circuits and the computing means are configured for enabling a substantially continuous input of K(X) coefficients into the input shift register buffer circuit and a substantially continuous input of Y(X) coefficients into the computing means and for enabling a substantially continuous output of Z(X) coefficients from the output shift register circuit.

3. The Galois Field (2^m) multiplier as claimed in claim 2 wherein the serial input of K(X) coefficients into the input shift register buffer circuit and the serial input of the Y(X) coefficients into the computing means both start at the same clock pulse and the serial output of the Z(X) coefficients from the output shift register circuit starts a predetermined number N of clock pulses thereafter.

4. The Galois Field (2^m) multiplier as claimed in claim 3 wherein the number N is equal to m.

5. The Galois Field (2^m) multiplier as claimed in claim 1 wherein the computing means includes an intermediate shift register having m serially arranged registers R_m-1 '"'"', R_m-2 '"'"', . . . , R₀ '"'"', said register stages R_m-1 '"'"', R_m-2 '"'"', . . . , R₀ '"'"' being connected for receiving the contents of corresponding ones of the register stages R_m-1, R_m-2, . . . , R₀ of the input shift register buffer circuit.

6. The Galois Field (2^m) multiplier as claimed in claim 5 wherein the computing means includes multiplying and summing means connected for receiving, in parallel, the contents of the register stages R_m-1 '"'"', R_m-2 '"'"', . . . , R₀ '"'"' at predetermined clock pulses and for simultaneously receiving, in parallel, the Y(X) coefficients Y_m-1, Y_m-2, . . . , Y₀, said multiplying and summing means being configured for multiplying corresponding pairs of the R_m-1 '"'"', R_m-2 '"'"', . . . , R₀ '"'"' stage contents and the Y_m-1, Y_m-2, . . . , Y₀ coefficients and summing the resulting products to provide said S_i output.

7. The Galois Field (2^m) multiplier as claimed in claim 6 wherein the computing means include serial-to-parallel bit converting means for serially receiving the Y_m-1, Y_m-2, . . . , Y₀ coefficients and for subsequently outputting said Y_m-1, Y_m-2, . . . , Y₀ coefficients in parallel for the multiplying and summing means.

8. The Galois Field (2^m) multiplier as claimed in claim 5 wherein the input shift register buffer circuit, the intermediate shift register circuit and the output shift register circuit are substantially identical to one another.

9. The Galois Field (2^m) multiplier as claimed in claim 8 wherein the input shift register buffer circuit, the intermediate shift register circuit and the output shift register circuit each includes feedback means connected between the input thereto and the corresponding register stages.

10. The Galois Field (2^m) multiplier as claimed in claim 9 wherein the input shift register buffer circuit includes an input modulo adder connected to receive the K(X) coefficients and to the first-in-series register stage R_m-1 and wherein the feedback means includes feedback to the input modulo adder from those of the register stages R_m-1, R_m-2, . . . , R₀ which correspond to those coefficients a_m-1, a_m-2, . . . , a₀ of the primitive root polynomial that are equal to 1, and wherein corresponding feedback is provided for the intermediate shift register circuit and the output shift register circuit.

11. The Galois Field (2^m) multiplier as claimed in claim 10 wherein the preselected clock pulse of which the computing means receives the contents of the initiating shift register stages R_m-1, R_m-2, . . . , R₀ is about the mth clock cycle after input of the K(X) and Y(X) elements input is initiated.

12. A pipeline Galois Field (2^m) multiplier for multiplying a field element of the form K(X)=K_m-1 X^m-1 +K_m-2 X^m-2 + . . . +K₀ by another field element of the form Y(K)=Y_m-1 X^m-1 +Y_m-2 X^m-2 + . . . +Y₀ to obtain the product Z(X)=Z_m-1 ^m-1 +Z_m-2 X^m-2 + . . . +Z₀, the field being characterized by the primitive root polynomial P(X)=a_m X^m +a_m-1 X^m-1 + . . . +a₁ X+a₀, wherein at least some by the coefficients a_m-1, a_m-2, . . . , a₀ are equal to 1 and the others of said coefficients a_m-1, a_m-2, . . . , a₀ are equal to 0, the multiplier comprising:

(a) input shift register buffer means including m serially arranged shift register stages R_m-1, R_m-2, . . . , R₀, and being connected for serially receiving the K(X) coefficients K_m-1, K_m-2, . . . , K₀ and for providing in response thereto, after m shifts, a pre-established initial arrangement of the K(X) coefficients in said register stages R_m-1, R_m-2, . . . , R₀ ;

(b) intermediate shift register means including serially arranged shift register stages R_m-1 '"'"', R_m-2 '"'"', . . . , R₀ '"'"' and being connected for receiving, in parallel, said initial arrangement of K(X) coefficients from the initiating shift register stages R_m-1, R_m-2, . . . , R₀ into said shift register stages R_m-1 '"'"', R_m-2 '"'"', . . . , R₀ '"'"' and for providing in response thereto, a sequence of m sets of particular arrangements of K(X) coefficients in the R_m-1 '"'"', R_m-2 '"'"', . . . , R₀ '"'"' register stages;

(c) multiplying and summing means connected for serially receiving the Y(X) coefficients, Y_m-1, Y_m-2, . . . , Y₀ and for serially receiving the sequence of m sets of K(X) coefficients from the intermediate shift register stages R_m-1 '"'"', R_m-2 '"'"', . . . , R₀ '"'"' for multiplying individual ones of said m sets of K(X) coefficients with corresponding ones of the Y(X) coefficients to produce a set of m products for each said set and summing the resulting said m products from each of said m sets to provide an output sequence of m intermediate product coefficients S_i =S_m-1, S_m-2, . . . , S₀, which correspond to a sequence of m sets of particular arrangements of K(X) coefficients received from the working shift registers R_m-1 '"'"', R_m-2 '"'"', . . . , R₀ '"'"';

(d) output shift register means including m serially arranged register stages R_m-1 ", R_m-2 ", . . . , R₀ " and being connected for serially receiving the sequence of m intermediate product coefficients S_i from the multiplying and summing means and for providing, in response thereto, a sequence of Z(X) coefficients, Z_m-1, Z_m-2, . . . , Z₀ ; and

(e) timing means for timing the operation of the input shift register buffer means, the intermediate shift register means, the multiplying and summing means and the output shift register means by providing clock pulses thereto.

13. The Galois Field (2^m) multiplier as claimed in claim 12 wherein there are m of said K(X) coefficients, K_m-1, K_m-2, . . . , K₀, m of said Y(X) coefficients, Y_m-1, Y_m-2, . . . , Y₀, m of said S_i intermediate coefficient S_m-1, S_m-2, . . . , S₀ and m of said Z(X) coefficients Z_m-1, Z_m-2, . . . , Z₀ and wherein the input shift register buffer means, the intermediate shift register means, the multiplying and summing means and the output shift register means are configured for enabling the output shift register means to continuously provide the sequence of Z(X) coefficients at a rate of one coefficient per clock pulse.

14. The Galois Field (2^m) multiplier as claimed in claim 13 wherein the output shift register means provide the first one of the sequence of Z(X) coefficients about m clock pulses after the first one of the K(X) elements is received by the initiating shift register means.

15. The Galois Field (2^m) multiplier as claimed in claim 13 wherein the multiplying and summing means are configured for receiving sequential one of the Y(X) coefficient, Y_m-1, Y_m-2, . . . , Y₀ at the same clock pulse that corresponding ones of the K(X) coefficients K_m-1, K_m-2, . . . , K₀ are received by the input shift register buffer means.

16. The Galois Field (2^m) multiplier as claimed in claim 12 wherein the multiplying and summing means includes multiplying means and serial-to-parallel converting means, said multiplying means being connected for serially receiving m sets of particular arrangements of K(X) coefficient from the register stages R_m-1 '"'"', R_m-2, . . . , R₀ '"'"', the contents of said R_m-1 '"'"', R_m-2 '"'"', . . . , R₀ '"'"' register stages, comprising each said set of particular arrangements, being received in parallel by the multiplying means, said converting means being connected for serially receiving the Y(X) coefficients and for outputting the set of m of said Y(X) coefficients in parallel to the multiplying means each time the multiplying means receives one of said sets of particular arrangements of K(X) coefficients from the R_m-1 '"'"', R_m-2 '"'"', . . . , R₀ '"'"' register stages.

17. The Galois Field (2^m) multiplier as claimed in claim 12 wherein each of the input shift register means, the intermediate shift register means and the output shift register means include feed back means connected from predetermined stages of the respective R_m-1, R_m-2, . . . , R₀ ;

R_m-1 '"'"', R_m-2 '"'"', . . . , R₀ '"'"' and R_m-1 ", R_m-2 ", . . . , R₀ " register stages back to the input of the respective R_m-1, R_m-1 '"'"', and R_m-1 " register stages.

18. The Galois Field (2^m) multiplier as claimed in claim 17 wherein said predetermined stages of the register stages R_m-1, R_m-2, . . . , R₀ ;

R_m-1 '"'"', R_m-2 '"'"', . . . , R₀ '"'"' and R_m-1 ", R_m-2 ", . . . , R₀ " are selected to correspond to those of said a_m-1, a_m-2, . . . , a₀ coefficients of the primitive root polynomial that are equal to 1, a_m-1 corresponding to register stages R_m-1, R_m-1 '"'"' and R_m-1 ", a_m-2 corresponding to register stages R_m-2, R_m-2 '"'"', R_m-2 ", and so forth.