US20070271323A1 - Compound galois field engine and galois field divider and square root engine and method - Google Patents

Abstract

A Galois field divider engine and method inputs a 1 and a first Galois field element to a Galois field reciprocal generator to obtain an output, multiplies in a Galois field reciprocal generator a first Galois field element by a first element of the Galois field reciprocal generator for predicting the modulo remainder of the square of the polynomial product of an irreducible polynomial m−2 times where m is the degree of the Galois field to obtain the reciprocal of the first Galois field element, and multiplying in the Galois field reciprocal engine the reciprocal of the first Galois field element by a second Galois field element for predicting the modulo remainder of the polynomial product for an irreducible polynomial to obtain the quotient of the two Galois field elements in m cycles; in a broader sense the invention includes a compound Galois field engine for performing a succession of Galois field linear transforms on a succession of polynomial inputs to obtain an ultimate output where each input except the first is the output of the previous Galois field linear transform; Galois field square root is achieved by inputting a Galois field element to a Galois field square root generator to obtain an output which is squared in the Galois field square root generator to predict the modulo remainder of the square of the polynomial product of an irreducible polynomial m−1 times where m is the degree of the Galois field to obtain the square root of the Galois field to obtain the square root of the Galois field element in (m−1) cycles.

Description

RELATED APPLICATIONS
• This application is a divisional application of U.S. patent application Ser. No. 10/440,330 filed May 16, 2003 which is hereby incorporated herein by reference and to which this application claims priority, and claims priority of U.S. Provisional application to Stein et al. entitled A COMPACT GALOIS FIELD MULTIPLIER, filed Oct. 9, 2002 (AD-337J), U.S. Provisional application Ser. No. 60/334,662, filed Nov. 30, 2001 to Stein et al., entitled GF2-ALU (AD-239J); U.S. Provisional application Ser. No. 60/334,510 filed Nov. 20, 2001 to Stein et al., entitled PARALLEL GALOIS FIELD MULTIPLIER (AD-240J); U.S. Provisional application Ser. No. 60/341,635, filed Dec. 18, 2001 to Stein et al., entitled GALOIS FIELD MULTIPLY ADD (MPA) USING GF2-ALU (AD-299J); U.S. Provisional application Ser. No. 60/341,737, filed Dec. 18, 2001, to Stein et al., entitled PROGRAMMABLE GF2-ALU LINEAR FEEDBACK SHIFT REGISTER—INCOMING DATA SELECTION (AD-300J). This application further claims priority of U.S. patent application Ser. No. 10/395,620 filed Mar. 24, 2003 to Stein et al., entitled COMPACT GALOIS FIELD MULTIPLIER ENGINE (AD-337J); U.S. patent application Ser. No. 10/051,533 filed Jan. 18, 2002 to Stein et al., entitled GALOIS FIELD LINEAR TRANSFORMERER (AD-239J); U.S. patent application Ser. No. 10/060,699 filed Jan. 30, 2002 to Stein et al., entitled GALOIS FIELD MULTIPLIER SYSTEM (AD-240J); U.S. patent application Ser. No. 10/228,526 filed Aug. 26, 2002 to Stein et al., entitled GALOIS FIELD MULTIPLY/MULTIPLY—ADD/MULTIPLY ACCUMULATE (AD-299J); and U.S. patent application Ser. No. 10/136,170, filed May 1, 2002 to Stein et al., entitled RECONFIGURABLE INPUT GALOIS FIELD LINEAR TRANSFORMERER SYSTEM (AD-300J).
FIELD OF THE INVENTION
• This invention relates to a Galois field divider engine and method and more generally to a compound Galois field engine for performing a succession of Galois field transforms in one transform operation.
BACKGROUND OF THE INVENTION
• In certain applications such as encryption and error control coding, it is necessary to perform arithmetic operations, e.g., add, subtract, square root, multiply, and divide over Galois fields. Any such operation between any two members in a Galois field will result in an output (sum, difference, square root, product, quotient) which is another value in the same Galois field. The number of elements in a Galois field is 2^mwhere m is the degree of the field. For example, GF(2⁴) would have sixteen different elements in it; GF(2⁸) would have 256. A Galois field is generated from an irreducible polynomial in a particular power. Each Galois field of a particular degree will have a number of irreducible polynomials form each of which may be devised a different field using the same terms but in a different order.
• Division over a Galois field is done by multiplying the dividend by the reciprocal of the divisor. This divisor reciprocal can be generated in a number of ways. One way is to have a stored look-up table of reciprocals where the divisor is the address for the table. One problem with this approach is that for each field of each irreducible polynomial there must be stored a separate table. In addition, the tables can only be accessed in serial: if parallel operations are required a copy of each table must be provided for each parallel operation. Another approach is to multiply each of the stored Galois field elements by the particular divisor. The value that produces a product of one is then the reciprocal of the particular divisor. Once again all of the values have to be stored and in multiple copies if parallel operation is contemplated. And, a Galois field multiplier is required just to accomplish the retrieval. A third approach uses two linear feedback shift registers (LFSR) each configured to generate a selected Galois field of a particular irreducible polynomial. The first is initialized to the divisor; the second is initialized to “1”. Starting from the divisor value the two are clocked synchronously. When the product of the first LFSR equals “1” the divisor has been multiplied by its reciprocal. The product of the second LFSR at that moment is the Galois field element that is the reciprocal of the divisor. One problem with this approach is that for each Galois field of each irreducible polynomial for each degree a different pair of LFSRs is required. In both, the second look-up table approach, above, and the LFSR approach the search for the reciprocal requires up to₂^m−1 iterations.
BRIEF SUMMARY OF THE INVENTION
• It is therefore an object of this invention to provide an improved Galois field divider engine and method.
• It is a further object of this invention to provide such an improved Galois field divider engine which can complete the search for the divisor reciprocal in m−1 iterations.
• It is a further object of this invention to provide such an improved Galois field divider engine which can be easily reconfigured to accommodate different irreducible polynomial Galois fields of different degrees.
• It is a further object of this invention to provide such an improved Galois field divider engine which can function to generate both the divisor reciprocal and multiply it by the dividend.
• It is a further object of this invention to provide such an improved Galois field divider engine which requires less power and less area.
• It is a further object of this invention to provide more generally an improved, compound Galois field engine for performing a succession of Galois field transforms in one transform operation.
• The invention results from the realization that such an improved Galois field division engine and method which is smaller, faster, and more efficient can be achieved with a Galois field reciprocal generator and an input selection circuit for initially inputting a 1 and a first Galois field element to the Galois field reciprocal generator to obtain an output, subsequently multiplying in the Galois field reciprocal generator a first Galois field element by the output of the Galois field reciprocal generator for predicting the modulo remainder of the square of the polynomial product of an irreducible polynomial m−2 times where m is the degree of the Galois field, to obtain the reciprocal of the first Galois field element and multiplying in the Galois field reciprocal engine the reciprocal of the first Galois field element by a second Galois field element for predicting the modulo reminder of the polynomial product for an irreducible polynomial to obtain the quotient of the two Galois field elements in m cycles.
• It was also realized, more generally, that an improved compound Galois field engine for performing a succession of Galois field linear transforms on a succession of polynomial inputs to obtain an ultimate output where each input, except the first, is the output of the previous Galois field linear transform can be accomplished with an input circuit for providing a first input and a Galois field linear transformer having a matrix of cells responsive to the first input and configured to, in one transform, immediately predict the modulo remainder of the succession of Galois field linear transforms of an irreducible Galois field polynomial to obtain the ultimate output of the Galois field linear transform directly from the first input.
• This invention features a Galois field divider engine including a Galois field reciprocal generator and an input selection circuit for initially inputting a 1 and a first Galois field element to the Galois field reciprocal generator to obtain an output, subsequently multiplying in the Galois field reciprocal generator a first Galois field element by the output of the Galois field reciprocal generator for predicting the modulo remainder of the square of the polynomial product of an irreducible polynomial m−2 times, where m is the degree of the Galois field, to obtain the reciprocal of the first Galois field element and multiplying in the Galois field reciprocal engine the reciprocal of the first Galois field element by a second Galois field element for predicting the modulo remainder of the polynomial product, for an irreducible polynomial to obtain the quotient of the two Galois field elements in m cycles.
• In a preferred embodiment, the reciprocal generator may include first and second Galois field multipliers. The first Galois field multiplier may include a first polynomial multiplier circuit and a first Galois field linear transformer. The first Galois field linear transformer may include a matrix of cells. The first Galois field linear transform may include a matrix section and a unity matrix section. The second Galois field multiplier may include a second polynomial multiplier circuit and a second Galois field linear transformer. The second Galois field linear transformer may include a matrix of cells. The second Galois field linear transformer matrix of cells may include a matrix section and a unity matrix section. The output of the first Galois field multiplier may be fed to both multiply inputs of the second Galois field linear multiplier to provide the square of that output. The Galois field reciprocal generator may include a Galois field multiplier including a first polynomial multiplier and a first Galois field transformer and a second Galois field transformer for calculating the square of the first Galois field multiplier output. The second Galois field transformer may be approximately one half the size of the first Galois field transformer. The first and second Galois field transformers each may include a matrix of cells and the second Galois field transformer may include approximately one half the number of cells of the first Galois field transformer. The Galois field reciprocal engine may include a Galois field multiplier and a program circuit for programming the Galois field multiplier to perform a compound multiply-square operation for m−2 times followed by a multiply operation.
• The invention also features in a broader sense a compound Galois field engine for performing a succession of Galois field linear transforms on a succession of polynomial inputs to obtain an ultimate output where each input except the first is the output of the previous Galois field linear transform. There is an input circuit for providing a first input and a Galois field linear transformer having a matrix of cells responsive to the first input and configured to, in one transform, immediately predict the modulo remainder of the succession of Galois field linear transforms of an irreducible Galois field polynomial to obtain the ultimate output of the Galois field linear transform directly from the first input.
• This invention also features a method of Galois field division including initially inputting a 1 and a first Galois field element to a Galois field reciprocal generator to obtain an output, multiplying in the Galois field reciprocal generator a first Galois field element by the output of the Galois field reciprocal generator for predicting the modulo remainder of the square of the polynomial product of an irreducible polynomial m−2 times where m is the degree of the Galois field to obtain the reciprocal of the first Galois field element, and multiplying in the Galois field reciprocal engine the reciprocal of the first Galois field element by a second Galois field element for predicting the modulo remainder of the polynomial product for an irreducible polynomial to obtain the quotient of the two Galois field elements in m cycles.
• This invention also features a Galois field square root engine including a Galois field square root generator and an input circuit for inputting a Galois field element to the Galois field square root generator to obtain the square root of the Galois field elements in one cycle.
• In a preferred embodiment, the Galois field square root engine may include a Galois field multiplier, and a program circuit for programming the Galois field multiplier to perform a compound square operation of m-l times in one cycle.
• The invention also features a Galois field square root method including inputting a Galois field element to a Galois field square root generator to obtain an output and squaring in the Galois field square root generator the output of the Galois field square root generator for predicting the modulo remainder of the square of the polynomial product of an irreducible polynomial m−1 times where m is the degree of the Galois field to obtain the square root of the Galois field element in (m−1) cycles.
BRIEF DESCRIPTION OF THE DRAWINGS
• Other objects, features and advantages will occur to those skilled in the art from the following description of a preferred embodiment and the accompanying drawings, in which:
• FIG. 1 is a functional block diagram of a compact Galois field multiplier engine according to the invention;
• FIG. 2 is a more detailed functional block diagram of a conventional Galois field multiplier engine according to the invention;
• FIG. 3 is a more detailed functional block diagram of the compact Galois field multiplier engine ofFIG. 1 displaying the reduced size Galois field linear transformer unity matrix feature of the invention;
• FIG. 4 is a schematic of a typical programmable X-OR circuit cell for the matrix of the Galois field linear transformer circuit ofFIGS. 2 and 3;
• FIG. 5 is a simplified schematic diagram of the Galois field linear transformer circuit ofFIGS. 3 and 9 illustrating the programming of the matrix section and unity matrix section cells according to the invention for a particular polynomial of power eight;
• FIG. 6 is a simplified schematic diagram of the Galois field linear transformer circuit ofFIGS. 3 and 9 illustrating the programming of the matrix section and unity matrix section cells according to the invention for another polynomial of power eight;
• FIG. 7 is a simplified schematic diagram of the Galois field linear transformer circuit ofFIGS. 3 and 9 illustrating the programming of the matrix section and unity matrix section cells according to the invention for yet another polynomial of power four;
• FIG. 8 is a simplified schematic diagram of the Galois field linear transformer circuit ofFIGS. 3 and 9 illustrating the programming of a second matrix section as a sparse matrix for supporting polynomial powers between half (4) powers and full (8) powers in this particular embodiment;
• FIG. 9 is a more detailed block diagram of a compact Galois field multiplier engine ofFIG. 1 incorporating both the reduced size matrix and the reduced hardware and localized bus features of the invention;
• FIG. 10 is a block diagram of Galois field multiplier engine according to the invention employing a number of Galois field linear transformer units;
• FIG. 11 is a schematic view of a polynomial multiplier usable inFIGS. 2, 3,5 and9;
• FIG. 12 is an illustration the transfer function for the polynomial multiplier ofFIG. 11;
• FIG. 13 is a simplified schematic block diagram of a divider engine according to this invention;
• FIG. 14 is a more detailed view of the Galois field multiplier and squarer ofFIG. 13;
• FIG. 15 is a chart of the reduced transfer function values for the polynomial multiplier ofFIG. 12;
• FIG. 16 is a view of a Galois field multiplier and squarer similar to that ofFIG. 14 implementing the reduced transfer function ofFIG. 15;
• FIG. 17 is a schematic illustration of the pattern of enabled cells of the Galois field linear transformer ofFIG. 14;
• FIG. 18 is a schematic illustration of the pattern of enabled cells of the Galois field linear transformer ofFIG. 16 utilizing the reduced transfer function;
• FIG. 19 is a schematic illustration of the pattern of enabled cells of a compound Galois linear engine for compound Galois field engine for performing a succession of Galois field linear transforms on a succession of polynomial inputs to obtain an ultimate output e.g. division according to a more general feature of this invention;
• FIG. 20 is a simplified schematic diagram of a compound Galois field engine utilizing the Galois field transform illustrated inFIG. 19;
• FIG. 21 is a flow chart of the Galois field divider method according to this invention;
• FIG. 22 is a schematic block diagram of a square root engine according to this invention;
• FIG. 23 is a schematic illustration of the pattern of enabled cells of a compound Galois field linear engine for performing a succession of Galois field linear transforms on a succession of polynomial inputs as shown inFIG. 22 to obtain an ultimate output e.g. square root according to the more general feature of this invention;
• FIG. 24 is a flow chart of the Galois field square root method according to this invention; and
• FIG. 25 is a simplified block diagram of a compound Galois field engine according to this invention.
DISCLOSURE OF THE PREFERRED EMBODIMENT
• Aside from the preferred embodiment or embodiments disclosed below, this invention is capable of other embodiments and of being practiced or being carried out in various ways. Thus, it is to be understood that the invention is not limited in its application to the details of construction and the arrangements of components set forth in the following description or illustrated in the drawings.
• Before disclosing the compound Galois field engine and the divisor engine and method of this invention an explanation of Galois field transformers and multipliers is presented for a better understanding.
• A Galois field GF(n) is a set of elements on which two binary operations can be performed. Addition and multiplication must satisfy the commutative, associative and distributive laws. A field with a finite number of elements is a finite field. An example of a binary field is the set {0, 1} under modulo 2 addition and modulo 2 multiplication and is denoted GF(2). Themodulo 2 addition and multiplication operations are defined by the tables shown in the following illustration. The first row and the first column indicate the inputs to the Galois field adder and multiplier. For e.g. 1+1=0 and 1*1=1.

  Modulo 2 Addition (XOR)

  +	0	1
  0	0	1
  1	1	0

• Modulo 2 Multiplication (AND)

  *	0	1
  0	0	0
  1	0	1

• In general, if p is any prime number then it can be shown that GF(p) is a finite field with p elements and that GF(p^m) is an extension field with pm elements. In addition, the various elements of the field can be generated as various powers of one field element, β, by raising it to different powers. For example GF(256) has 256 elements which can all be generated by raising the primitive element, β, to the 256 different powers.
• In addition, polynomials whose coefficients are binary belong to GF(2). A polynomial over GF(2) of degree m is said to be irreducible if it is not divisible by any polynomial over GF(2) of degree less than m but greater than zero. The polynomial F(X)=X²+X+1 is an irreducible polynomial as it is not divisible by either X or X+1. An irreducible polynomial of degree m which divides X²m−1+1, is known as a primitive polynomial. For a given m, there may be more than one primitive polynomial. An example of a primitive polynomial for m=8, which is often used in most communication standards is F(X)=0×11=x⁸+x⁴+x³+x²+1.
• Galois field addition is easy to implement in software, as it is the same as modulo addition. For example, if 29 and 16 are two elements in GF(2⁸) then their addition is done simply as an XOR operation as follows: 29 (11101)⊕ 16(10000)=13(01101).
• Galois field multiplication on the other hand is a bit more complicated as shown by the following example, which computes all the elements of GF(2⁴), by repeated multiplication of the primitive element β. To generate the field elements for GF(2⁴) a primitive polynomial G(x) of degree m=4 is chosen as follows G(x)=X⁴+X+1. In order to make the multiplication be modulo so that the results of the multiplication are still elements of the field, any element that has the fifth bit set is brought into a 4-bit result using the following identity F(β)=β⁴+β+1=0. This identity is used repeatedly to form the different elements of the field, by setting β⁴=1+β. Thus the elements of the field can be enumerated as follows:
  {0, 1, β, β²β³, 1+β, β+β², β²+β³, 1+β+β³, . . .1+β³,}
  since β is the primitive element for GF(2⁴) it can be set to 2 to generate the field elements of GF(2⁴) as {0,1,2,4,8,3,6,12,11 . . . 9}.
• It can be seen that Galois field polynomial multiplication can be implemented in two basic steps. The first is a calculation of the polynomial product c(x)=a(x)*b(x) which is algebraically expanded, and like powers are collected (addition corresponds to an XOR operation between the corresponding terms) to give c(x). For example c(x)=(a₃x³+a₂x²+a₁x¹+a₀)*(b₃x³+b₂x³+b₁x¹+b₀) c(x)=c₆x⁶+c₅x⁵+c₄x⁴+c₃x³+c₂x²+c₁x¹+c₀where:$c_0=a_0*b_0$$c_1=a_1*{\mathrm{<figure-callout\; label="b"\; filenames="US20070271323A1-20071122-D00011.png,US20070271323A1-20071122-D00015.png"\; state="\{\{state\}\}">b</figure-callout>}}_0\oplus a_0*b_1$$c_2=a_2*{\mathrm{<figure-callout\; label="b"\; filenames="US20070271323A1-20071122-D00011.png,US20070271323A1-20071122-D00015.png"\; state="\{\{state\}\}">b</figure-callout>}}_0\oplus a_1*{\mathrm{<figure-callout\; label="b"\; filenames="US20070271323A1-20071122-D00005.png,US20070271323A1-20071122-D00006.png"\; state="\{\{state\}\}">b</figure-callout>}}_1\oplus a_0*b_2$$c_3=a_3*{\mathrm{<figure-callout\; label="b"\; filenames="US20070271323A1-20071122-D00011.png,US20070271323A1-20071122-D00015.png"\; state="\{\{state\}\}">b</figure-callout>}}_0\oplus a_2*{\mathrm{<figure-callout\; label="b"\; filenames="US20070271323A1-20071122-D00005.png,US20070271323A1-20071122-D00006.png"\; state="\{\{state\}\}">b</figure-callout>}}_1\oplus a_1*{\mathrm{<figure-callout\; label="b"\; filenames="US20070271323A1-20071122-D00011.png,US20070271323A1-20071122-D00012.png"\; state="\{\{state\}\}">b</figure-callout>}}_2\oplus a_0*b_3$$c_4=a_3*{\mathrm{<figure-callout\; label="b"\; filenames="US20070271323A1-20071122-D00005.png,US20070271323A1-20071122-D00006.png"\; state="\{\{state\}\}">b</figure-callout>}}_1\oplus a_2*{\mathrm{<figure-callout\; label="b"\; filenames="US20070271323A1-20071122-D00011.png,US20070271323A1-20071122-D00012.png"\; state="\{\{state\}\}">b</figure-callout>}}_2\oplus a_1*b_3$$c_5=a_3*{\mathrm{<figure-callout\; label="b"\; filenames="US20070271323A1-20071122-D00011.png,US20070271323A1-20071122-D00012.png"\; state="\{\{state\}\}">b</figure-callout>}}_2\oplus a_2*b_3$$c_6=a_3*b_3$
• The second is the calculation of d(x)=c(x) modulo p(x).
• To illustrate, multiplications are performed with the multiplication of polynomials modulo an irreducible polynomial. For example: (if m(x) =x⁸+x⁴+x³+x+1)
• {57}*{83}={c1} because,$\begin{array}{c}\left(x^6+x^4+x^{2}x+1\right)+\left(x^7+x+1\right)=x^{13}\oplus x^{11}\oplus x^9\oplus x^8\oplus x^7\\ x^7\oplus x^5\oplus x^3\oplus x^2\oplus x\\ x^6\oplus x^4\oplus x^2\oplus x\oplus x\\ =x^{13}\oplus x^{11}\oplus x^9\oplus x^8\oplus x^6\oplus \\ x^5\oplus x^4\oplus x^3\oplus 1\\ x^{13}+x^{11}+x^9+x^8+x^6+x^5{x}^4+x^3+1\mathrm{modulo}(x^8+x^4+x^3+\\ x+1)\\ =x^7+x^6+1\end{array}$
• An improved Galoisfield multiplier system10, foreclosing on this approach includes a multiplier circuit for multiplying two polynomials a₀-a₇in an A register with the polynomial b₀-b₇in an B register with coefficients over a Galois field to obtain their product is given by the fifteen-term polynomial c(x) defined as Chart II. The multiplier circuit actually includes a plurality of multiplier cells.$c14=a7*b7$$c13=a7*b6\oplus a6*b7$$c12=a7*b5\oplus a6*b6\oplus a5*b7$$c11=a7*b4\oplus a6*b5\oplus a5*b6\oplus a4*b7$$c10=a7*b3\oplus a6*b4\oplus a5*b5\oplus a4*b6\oplus a3*b7$$c9=a7*b2\oplus a6*b3\oplus a5*b4\oplus a4*b5\oplus a3*b6\oplus a2*b7$$\begin{array}{c}c8=a7*b1\oplus a6*b2\oplus a5*b3\oplus a4*b4\oplus a3*b5\oplus a2*b6\oplus \\ \begin{array}{c}a1*b7\\ c7=a7*b0\oplus a6*b1\oplus a5*b2\oplus a4*b3\oplus a3*b4\oplus a2*b5\oplus \\ a1*b6\oplus a0*b7\hspace{1em}\\ c6=a6*b0\oplus a5*b1\oplus a4*b2\oplus a3*b3\oplus a2*b4\oplus a1*b5\oplus \\ a0*b6\hspace{1em}\end{array}\end{array}$$\mathrm{c5}=a5*b0\oplus a4*b1\oplus a3*b2\oplus a2*b3\oplus a1*b4\oplus a0*b5;$$c4=a4*b0\oplus a3*b1\oplus a2*b2\oplus a1*b3\oplus a0*b4$$c3=a3*b0\oplus a2*b1\oplus a1*b2\oplus a0*b3$$c2=a2*b0\oplus a1*b1\oplus a0*b2$$c1=a1*b0\oplus a0*b1$$c0=a0*b0$
  The operation of a Galois field multiplier system is explained in U.S. patent application to Stein et al. entitled GALOIS FIELD MULTIPLIER SYSTEM [AD-240J] Ser. No. 10/060,699 filed Jan. 30, 2002 which is incorporated herein in its entirety by this reference.
• Each of the fifteen polynomial c(x) term includes an AND function as represented by an * and each pair of terms are combined with a logical exclusive OR as indicated by a ⊕. This product as represented in Chart II is submitted to a Galois field linear transformer circuit which may include a number of Galois field linear transformer units each composed of 15×8 cells, which respond to the product produced by the multiplier circuit to predict the modulo remainder of the polynomial product for a predetermined irreducible polynomial. The A₀, B₀multiplication is performed in a first unit the A₁, B₁in a second unit, the A₂, B₂in a third unit, and the A_n, B_nin the last unit. The operation of a Galois field linear transformer circuit and each of its transformer units is explained in U.S. patent application to Stein et al. entitled GALOIS FIELD LINEAR TRANSFORMER[AD-239J] Ser. No. 10/051,533 with a filing date of Jan. 18, 2002, which is incorporated herein in its entirety by this reference. Each of the Galois field linear transformer units predicts the modulo remainder by dividing the polynomial product by an irreducible polynomial. That irreducible polynomial may be, for example, anyone of those shown in Chart III.$\begin{array}{cc}\text{:}\mathrm{GF}\left(2^1\right)& \\ 0\times 3& \left(x+1\right)\\ & \\ \text{:}\mathrm{GF}\left(2^2\right)& \\ 0\times 7& \left(x^2+x+1\right)\\ & \\ \text{:}\mathrm{GF}\left(2^3\right)& \\ 0\times B& \left(x^3+x+1\right)\\ 0\times D& \left(x^3+x^2+1\right)\\ & \\ \text{:}\mathrm{GF}\left(2^4\right)& \\ 0\times 13& \left(x^4+x+1\right)\\ 0\times 19& \left(x^4+x^3+1\right)\\ & \\ \text{:}\mathrm{GF}\left(2^5\right)& \\ 0\times 25& \left(x^5+x^2+1\right)\\ 0\times 29& \left(x^5+x^3+1\right)\\ 0\times 2F& \left(x^5+x^3+x^2+x+1\right)\\ 0\times 37& \left(x^5+x^4+x^2+x+1\right)\\ 0\times 3B& \left(x^5+x^4+x^3+x+1\right)\\ 0\times 3D& \left(x^5+x^4+x^3+x^2+1\right)\\ & \\ \text{:}\mathrm{GF}\left(2^6\right)& \\ 0\times 43& \left(x^6+x+1\right)\\ 0\times 5B& \left(x^6+x^4+x^3+x+1\right)\\ 0\times 61& \left(x^6+x^5+1\right)\\ 0\times 67& \left(x^6+x^5+x^2+x+1\right)\\ 0\times 6D& \left(x^6+x^5+x^3+x^2+1\right)\\ 0\times 73& \left(x^6+x^5+x^4+x+1\right)\\ & \\ \text{:}\mathrm{GF}\left(2^7\right)& \\ 0\times 83& \left(x^7+x+1\right)\\ 0\times 89& \left(x^7+x^3+1\right)\\ 0\times 8F& \left(x^7+x^3+x^2+x+1\right)\\ 0\times 91& \left(x^7+x^4+1\right)\\ 0\times 9D& \left(x^7+x^4+x^3+x^2+1\right)\\ 0\times A7& \left(x^7+x^5+x^2+x+1\right)\\ 0\times \mathrm{AB}& \left(x^7+x^5+x^3+x+1\right)\\ 0\times B9& \left(x^7+x^5+x^4+x^3+1\right)\\ 0\times \mathrm{BF}& \left(x^7+x^5+x^4+x^3+x^2+x+1\right)\\ 0\times C1& \left(x^7+x^6+1\right)\\ 0\times \mathrm{CB}& \left(x^7+x^6+x^3+x+1\right)\\ 0\times D3& \left(x^7+x^6+x^4+x+1\right)\\ 0\times E5& \left(x^7+x^6+x^5+x^2+1\right)\\ 0\times F1& \left(x^7+x^6+x^5+x^4+1\right)\\ 0\times F7& \left(x^7+x^6+x^5+x^4+x^2+x+1\right)\\ 0\times \mathrm{FD}& \left(x^7+x^6+x^5+x^4+x^3+x^2+1\right)\\ & \\ \text{:}\mathrm{GF}\left(2^8\right)& \\ 0\times 11D& \left(x^8+x^4+x^3+x^2+1\right)\\ 0\times 12B& \left(x^8+x^5+x^3+x+1\right)\\ 0\times 12D& \left(x^8+x^5+x^3+x^2+1\right)\\ 0\times 14D& \left(x^8+x^6+x^3+x^2+1\right)\\ 0\times 15F& \left(x^8+x^6+x^4+x^3+x^2+x+1\right)\\ 0\times 163& \left(x^8+x^6+x^5+x+1\right)\\ 0\times 165& \left(x^8+x^6+x^5+x^2+1\right)\\ 0\times 169& \left(x^8+x^6+x^5+x^3+1\right)\\ 0\times 171& \left(x^8+x^6+x^5+x^4+1\right)\\ 0\times 187& \left(x^8+x^7+x^2+x+1\right)\\ 0\times 18D& \left(x^8+x^7+x^3+x^2+1\right)\\ 0\times 1A9& \left(x^8+x^7+x^5+x^3+1\right)\\ 0\times 1C3& \left(x^8+x^7+x^6+x+1\right)\\ 0\times 1CF& \left(x^8+x^7+x^5+x^3+x^2+x+1\right)\\ 0\times 1E7& \left(x^8+x^7+x^6+x^5+x^2+x+1\right)\\ 0\times 1F5& \left(x^8+x^7+x^5+x^4+x^2+1\right)\end{array}$
• The Galois field multiplier presented here GF(2⁸) is capable of performing withpowers 2⁸andpowers 2⁴and under as shown in Chart III.
• An example of the GF multiplication occurs as follows:

  	Before GF( ) multiplication;		After GF9( ) multiplication;
  	Polynomial 0x11d		Polynomial 0x11d

  	GF( )	45 23 00 01h	GF( )	45 23 00 01h
  		57 34 00 01h		57 34 00 01h
  		xx xx xx xxh		72 92 00 01h

• There is shown inFIG. 1 a compact Galoisfield multiplier engine10 accompanied by anA input register12,B input register14 and anoutput register16. CompactGalois field engine10 is capable of a number of different operations, including multiply, multiply-add and multiply-accumulate.
• Conventional Galois field multiplier engine10a,FIG. 2, requires three registers, Aregister12a, B register14aand C register26a. The burden of these registers must be carried by the associated digital signal processor (DSP)core28 and require extensive external bus work. In addition tobus30, for supplying data to Aregister12a,bus34 for supplying data to B register14aandbus36 for supplying data to C register26a, there is required abus32 for feeding back the output fromregister16ato thedigital signal processor28 andbus34 orbus36 for feeding back that output fromdigital signal processor28 to B register14aor C register26a.Bus31 connects the output of Galois fieldlinear transformer circuit20 and output register16a. Thuspolynomial multiplier circuit18 can provide to themultiple input40 ofmatrix22 of Galois fieldlinear transformer circuit20 the proper values in conjunction with the values fed from C register26ato theadder input42 ofmatrix22 to perform multiply, multiply-add and multiply-accumulation functions.Matrix22 is shown here as an eight by fifteen matrix for supporting multiplication of polynomials of power eight but may be made larger or smaller, containing more orfewer cells24, depending upon the power of the polynomial to be serviced.
• The number ofcells24bper row,FIG. 3, ofmatrix22bof Galois fieldlinear transformer circuit20binengine10bmaybe reduced by nearly half, by configuringmatrix22binto two matrix sections, amatrix section50 and aunity matrix section52. The unity matrix section requires only one set ofcells54 wherein these unity matrix section cells represent the prediction of the remainder when the output of the multiplier circuit is a polynomial with a power less than the power of the irreducible polynomial. Thus inFIG. 3 where the irreducible polynomial has a power of eight any polynomial of less than eight will not exceed the modulo and will be passed right through the matrix, thus the absent cells inunity matrix section52 are unnecessary. This saves nearly half of the cells required for thematrix22bresulting in a smaller, simpler and faster engine.
• Eachcell24b,FIG. 4, may include an ANDcircuit100 and an exclusive ORcircuit102. There is adata input104 and an enableinput106. Exclusive ORcircuit102 provides an output online108 to the input of the next exclusive OR circuit and receives at itsinput110 the output from the previous exclusive OR circuit, except for the last exclusive OR circuit whose output is connected to the output of the matrix and the first exclusive OR circuit whose input is connected to theadder input42b,FIG. 3, or42g,FIG. 9. An enable signal online106 enables the data online104 to pass through ANDgate100 and to be exclusively ORed by exclusive ORcircuit102 with the input online110. The lack of an enabling signal online106 simply passes the input online110 through the exclusive ORgate102 tooutput line108. An enabling signal online106 enablescell24. In this manner the entire matrix maybe reconfigured for any particular irreducible polynomial.
• The efficacy ofengine10b,FIG. 3, can be understood by choosing an irreducible polynomial from Chart III, supra, and implementing it by enabling the necessary cells. For example, to implement the first polynomial of power eight designated 0×11d representing the irreducible polynomial x⁸+x⁴+x³+x²+1, the enabled cells, indicated generally at24cc, form aunity matrix52c,FIG. 5, with a line ofcells54cas previously depicted inFIG. 3. When choosing the second irreducible polynomial from Chart III, 0×12b, the irreducible polynomial x⁸+x⁵+x³+x+1 produces a pattern of enabledcells24dd,FIG. 6, inmatrix section50dandunity matrix52dwhere once again theunity matrix section52dresults in a line of enabledcells54d.
• The reduction in the number of required cells is not limited to only polynomials having the same power as the irreducible polynomial. It also applies to any of those having the power of one half or less of the power of the irreducible polynomial. For example, the eight by fifteenmatrix22b, shown inFIG. 3 and referred to by way of explanation inFIGS. 5 and 6 could also support polynomials to the power of one, two, three, or four, but not powers of five, six and seven, if the irreducible polynomial power was sixteen the matrix that supported it could also support polynomials up to eight, but not nine through fifteen. If it were the power of thirty-two it could support polynomials of thirty-two power and up to sixteen, but not seventeen through thirty-one. For example, as shown inFIG. 7 for an irreducible polynomial of the fourth power both thematrix section50eandunity matrix section52ebecome smaller and can be implemented anywhere withinmatrix22e. Here thematrix section50ehas a plurality of enabledcells24ee along with the enabled cells inunity matrix52ewhich now has a smaller line of enabledcells54e, making up theunity matrix section52e.
• If it is desirable to service the intermediate polynomials of power five, six and seven the unity matrix section can be replaced with asparse matrix section52f,FIG. 8, wherein additional lines of enabledcells54ff,54fff,54ffff, can be employed to support polynomials of power seven, six and five respectively. But it is somewhat less of a reduction in the size of the matrix and required number of cells.
• The number of input registers can be reduced from three to two and the number of external buses relied upon to communicate with the digital signal processor (DSP)28g,FIG. 9, can be reduced and localized to be internal of theengine10gitself. Thus, as shown inFIG. 9, there are but two input registers A12gandB14gand the feedback fromoutput31gdoes not need to go through DSP28gbut goes directly, locally, onengine10gthroughinternal bus60 to multiplierinput selection circuit62 and adderinput selection circuit64. Digital signal processor28gneed only provide control signals online66 to multiplierinput selection circuit62 and online68 to adderinput selection circuit64. Thus in the multiply mode, multiplierinput selection circuit62, passes an input from B register14gtopolynomial multiplier circuit18gwhile adderinput selection circuit64 provides an additive identity level, in this case, aground level70 to theadder input42gof Galois fieldlinear transformer circuit20g. In the multiply-add modedigital signal processor28 instructs multiplierinput selection circuits62 to feed back the output frommatrix22goverline60 topolynomial multiplier circuit18gand instructs adderinput selection circuits64 to pass the polynomial in B register14gto theadder input42gof Galois fieldlinear transformer circuit20g. In the multiply-accumulate mode digital signal processor28ginstructs multiplierinput selection circuit62 to deliver the polynomial from B register14gtopolynomial multiplier circuit18gand instructs adderinput selection circuit64 to feed back the output online60 of Galois fieldlinear transformer circuit20g.
• Another feature is the reconfigurability of Galois fieldlinear transformer circuit20gby virtue of the selective enablement ofcells24g.Reconfigurable control circuit80 selectively enables the ones ofcells24grequired to implement the coefficients of the selected irreducible polynomial and itself can be reduced in size since the number of cells it needs to control has been reduced.
• The operation of a reconfigurable input Galois field linear transformer circuit is explained in U.S. patent application Ser. No. 10/136,170, filed May 1, 2002 to Stein et al., entitled RECONFIGURABLE INPUT GALOIS FIELD LINEAR TRANSFORMERER SYSTEM (AD-300J) and all its priority applications and documents which are incorporated herein in their entirety by this reference.
• Although thus far for the sake of simplicity the explanation has been with respect to only one engine, a number of the engines may be employed together as shown inFIG. 10 where each engine has amultiplier circuit10h,10i,10j,10k. . .10nand a Galois fieldlinear transformer20h,20i,20j,20k. . .20ncircuit. With a single centralreconfigurable control circuit80¹controlling them all. These engines can share the same wide [32, 64, 128] bit A and B registers were each operates on a different 8 bit (Byte) segment , or each can be serviced by its ownreconfigurable control unit80h,80i,80j,80k. . .80nand each by its own pair of A and B registers A₀, andB₀12h, and14h; A₁and, B₁,12i, and14i; A₂and B₂,12jand14j, A₃andB₃12kand14kand so on.
• Apolynomial multiplier circuit181,FIG. 11, usable in the embodiment shown herein to provide an output c0-c14 includes a plurality of ANDgates120 which combined with exclusive ORgates122 can multiply any pair of polynomials from Aregister121 and B register141 e.g., polynomials a₀-a₇, polynomials b₀-b₇as illustrated in the table124FIG. 12.
• There is shown inFIG. 13 a Galoisfield divider engine150 according to this invention including a Galois fieldreciprocal generator155 having aGalois field multiplier152 and a secondGalois field multiplier154 for performing a squaring function.Engine150 performs the division β/β_kby executing the operation β₁* 1/β_k, where β₁and β_kare elements of a Galois field, for example, where m=8, that is GF(2⁸): the degree of the field is eight. InitiallyGalois field multiplier152 receives a 1 and β_kand multiplies them together. The output is then squared inGalois field multiplier154 and fed back toGalois field multiplier152. This result is multiplied by β_kover and over again for m−2 times so that a total of m−1 iterations has occurred. At this point the reciprocal 1/β_kis obtained and instead of β_kbeing supplied as it has been for each of the m−2 iterations it is now β₁that is supplied to perform the multiplication β₁*(1/β_k). Thus, the entire division takes place in a total of m iterations, m−1 for generating the reciprocal and 1 more for multiplying the reciprocal of the divisor and the dividend to get the quotient. The timely application of “1”, β_kand β₁is performed byinput selection circuit171.
• The fact that${\beta }^{2^{m-2}}=\frac{1}{\beta }$
  is shown by the following exposition, given: the field of GF(q) is made up from the numbers {0, 1 . . . (q−1)}. If we multiply by β (β is a field member ≠0} each member of {1, 2 . . . (q−1)} to get {(1β, 2β . . . (q−1)β} we can easily see that we get the same set back again (with the order changed). This means that 1,·2· . . . (q−1)=1β·2β· . . . (q−1)β=1·2· . . . (q−1)β^(q−1)by cancelling thefactors 1··2· . . . ·(q−1) from both sides assures us that
  β^q−1=1.   (1)
  Therefore
  β⁻¹β^q−2  (2)
• Replacing q with 2^mresults in the expression$\begin{array}{cc}{\beta }^{2^m-2}=\frac{1}{\beta }& \left(3\right)\end{array}$
• FIG. 13 is a straightforward implementation of this expression.
• According to (3) for n=7 we need to calculate β²⁵⁴. β²⁵⁴can be calculated as ⊕1¹²⁸·β⁶⁴·β¹⁶·β⁸·β⁴·β². Which can be iteratively calculated as$\begin{array}{c}n=1\text{:}{\left(\beta ·1\right)}^2={\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00011.png,US20070271323A1-20071122-D00012.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^2\\ n=2\text{:}{\left({\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00011.png,US20070271323A1-20071122-D00012.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^2·1\right)}^2={\beta }^4·{\beta }^2\\ n=3\text{:}{\left({\beta }^4·{\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00011.png,US20070271323A1-20071122-D00012.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^2·\beta \right)}^2={\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00007.png,US20070271323A1-20071122-D00008.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^8·{\beta }^4·{\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00011.png,US20070271323A1-20071122-D00012.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^2={\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00001.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^{14}\\ ⋮\\ n=7\text{:}{\left({\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00008.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^{64}·{\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00002.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^{32}·{\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00001.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^{16}·{\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00007.png,US20070271323A1-20071122-D00008.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^8·{\beta }^4·{\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00011.png,US20070271323A1-20071122-D00012.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^2·\beta ·\right)}^2\\ ={\beta }^{128}·{\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00008.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^{64}·{\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00002.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^{32}·{\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00001.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^{16}·{\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00007.png,US20070271323A1-20071122-D00008.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^8·{\beta }^4·{\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00011.png,US20070271323A1-20071122-D00012.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^2={\mathrm{<figure-callout\; label="\beta "\; filenames="US20070271323A1-20071122-D00018.png"\; state="\{\{state\}\}">\beta </figure-callout>}}^{254}\end{array}$
• The circuit ofFIG. 13 starts from an initial value of 1 and generates at155 the following successive values:

  	Iteration #

  	1	2	3	4	5	6	7

  Value atPoint 155	β3	β6	β14	β30	B62	β126	B254

  
  As can be seen, the final value of β⁻¹is obtained in (n−1) cycles. The same circuit is generating β⁻¹for all intermediate powers of m GF(2^m) {m=3.7}, for example if m=4, β^2m−2=14 is generated at n=3.
• In one embodiment, Galois fieldreciprocal generator155a,FIG. 14, may includeGalois field multiplier152aandGalois field multiplier154a.Galois field multiplier152aincludes Galois fieldlinear transformer156 and apolynomial multiplier158.Galois field multiplier156 is shown as including a matrix of exclusive OR cells having two sections,matrix section160 and reducedunity matrix section162, but this is not a necessary limitation of the invention asunity matrix section162 may be implemented with a full matrix as ismatrix section160 if size is not an issue.Galois field multiplier154aalso includes apolynomial multiplier164 andGalois field transformer166 which also may include, but not necessarily, afull matrix section168 and a reducedunity matrix section170. Here againunity section170 is advantageous as to cost and area but it is not necessary as a full section could be used there. Galoisfield divider engine150aperforms a division in m iterations. In the first iterationinput selection circuit171 introduces a 1 in combination with β_ktoGalois field multiplier152a. This produces an output β_konline172 which is delivered to bothpolynomial multiplier inputs174,176 ofGalois field multiplier154a. Thus, a squaring function is performed and the output is fed back to aninput178 ofinput selection circuit171. This iteration occurs m−2 times where m is the degree of the Galois field. After m−2 iterationsinput selection circuit171 introduces the dividend β₁toGalois field multiplier152abecause at that time the value atoutput178 is the reciprocal 1/β_k. By now multiplying β₁, the dividend, times 1/β_k, the divisor, the result is β₁is divided by β_kto obtain the quotient of the Galois field division at180.
• The values atinputs174 and176 take the form of, from the most significant digit to the least, b₇-b₀and a₇-a₀. When the squaring function is being performed as here, then each of the values b₇-b₀will be the same, respectively, as each of the values of a₇-a₀because they are the same numbers. The number of digits b₇-b₀, a₇-a₀depends upon the size of the polynomial, which in this case where m is 8 would be eight digits. Whatever the size, since the values are the same at both inputs, the exclusive OR function will be zero. That is, like inputs to an exclusive OR gate renders a zero output as is well known. Thus, referring again toFIG. 12, it can be seen that for each of the polynomial multiply outputs c₀-c₁₄, the odd-numbered ones inFIG. 12 contain pairs of identical values. For example, c₁is equal to a₁*b₀⊕a₀*b₁. Since we are squaring we know that the two values being presented atinputs174 and176 are the same, therefore a₀and b₀are the same and a₁and b₁are the same. Therefore, c₁when exclusively ORed will have a value of zero. The same is true for the rest of the odd numbered Galois field multiplier outputs c₃, c₅, c₇, c₉, c₁₁, c₁₃. The result is shown at182,FIG. 15 where it can be seen not only that there are zero values resulting at the odd numbered c₁-c₁₃, but that the remaining non zero even numbered values require no exclusive OR gates, only multiplication. For example, c₀is a₀*b₀. But this is a simple AND function resulting in a value of a₀. Similarly, with respect to c₂the value a₁is multiplied by bi giving an AND function which results in the simple output of a₁. The same effect is true in c₄, c₆, c₈, c₁₀, c₁₂, and c₁₄. The same applies toGalois field multiplier156b.Galois field multiplier154bwhich effects the squaring function can be reduced in size by one half shown by the reduction by one half of thematrix section168bandunity section170b. Also, now since the function has turned into a simple input as shown incolumn184,FIG. 15, two separate inputs are not required and so thepolynomial multiplier164 is no longer needed.
• Galois field transformers156cand166c,FIG. 17, are implemented identically. The shaded circles indicate the enabled exclusive OR gate cells in each of the transformers. The programming is accomplished by the codes incolumn190 and is the same for bothtransformers156cand166c.Transformer156creceives the inputs c₀-c₁₄and provides the outputs A₀-A₇. These form the inputs with the zeros of A₀-A₇of Galois fieldlinear transformer166cwhose final outputs are B₀-B₇. Both transformers have been implemented for the Galois field of degree eight GF(2⁸) (m=8for the irreducible polynomial (O×12b). When the reduction shown inFIG. 15 is effected,Galois field multiplier156d,FIG. 18 stays the same as do all of the programming instructions in thecolumn190d, but Galois fieldlinear transformer166dhas had every other column, the zero columns, eliminated, resulting in the structure shown inFIG. 16.
• When the Galois field divider engine has been reduced as shown inFIG. 16, a further reduction is now achievable. Because Galoisfield divider engine154bhas no polynomial multiplier in the secondGalois field transformer166b, a single matrix or transformer can be constructed which delivers the output B₀-B₇directly from c₀-c₁₄without the interim A₀-A₇terms, in one cycle and using a singlelinear transformer200,FIG. 19.Transformer200 has been programmed to have the combination of exclusive OR cells indicated by the shaded circles enabled in order to perform both of the Galois field linear transforms in one Galois field linear transformer and in one operation. Thus, the inputs c₀-c₁₄are directly transformed by Galois fieldlinear transformer200 to the ultimate outputs B₀-B₇. The compounding which reduces the twomatrices156dand166d,FIG. 18, to the single matrix Galois fieldlinear transformer200 inFIG. 19 can be seen by a simple illustration using B₇,FIG. 18, which can be seen as equivalent to the exclusive ORs A₇, A₆, and A₅, as shown in Galois fieldlinear transformer166d. Referring then to Galois fieldlinear transformer156d(where the backslash indicates a cancellation of a term because it is duplicated), it can be seen that
• A₅is equal to c₁₄, c₁₃, c₁₂, c₈, c₅
• A₆is equal to c₉, c₆,
• A₇is equal to, and c₇,
• all with the exclusive OR functions between them. This results in the output c₁₄, exclusive OR c₁₃, exclusive OR c₁₂, exclusive OR c₉, exclusive OR c₈, exclusive OR c₇, exclusive OR c₆, exclusive OR c₅. Thus, inmatrix200,FIG. 19, B₇can be seen to include the exclusive OR combination of c₁₄, c₁₃, c₁₂, c₉, c₈, c₇, c₆, and c₅. One implementation of such a compounded Galoisfield divider engine202 is shown inFIG. 20 where Galois field linear transform,matrix200 ofFIG. 19 appears in conjunction with apolynomial multiplier204 andinput selection circuit171ewith dualinput selection units206,208. Now the Galois fieldreciprocal generator205 has been implemented by a single, compound Galois fieldlinear transformer200.Input selection unit206 is capable of performing multiply-add (MPA), multiply-accumulate (MAC), and multiply (MPY).Input selection unit208 functions similarly and provides to Galois fieldlinear transformer200 the adder input as previously explained.Program sequencer210 provides the mapping of the control flip-flops212 which enable and disable the matrix of cells including the exclusive OR gates. The program sequencer can program theGFLT matrix200 as a compound multiplier performing (GF_MPY(α,β))²in one cycle for division ,as a Galois field multiplier for multiplication, as a multiply and accumulate for multiply and accumulation and as a multiply-add for the multiply-add function.
• In operation, initially the GFLT is programmed as a compound multiplier performing (GF_MPY(α,β)², a 1 is provided atinput214 and β_katinput216. Following that for m−2 iterations, theoutput180 is fed back oninput214 while β_kremains oninput216. After m−2 iterations, when the system has gone through a total of m−1 iterations, the input at214 is now the reciprocal of β_k. At this point the GFLT is programmed as a Galois Field multiplier, β_katinput216 is now replaced with input β₁so that the next multiplication, the m^thiteration, multiplies β₁times the reciprocal of β_kto provide the output β₁divided by β_k. The Galois field division method of this invention is shown inFIG. 21 where the divisor β_kand dividend β₁are provided atstart240. A query is then made as to whether this iteration is the m^thiteration instep242, where m is the degree of the Galois field involved. If it is the mth iteration, the system goes directly to step244 where the Galois field multiplication of β₁by the Galois field linear transform output of the reciprocal 1/β_kis performed. The quotient is then produced at246. If the iteration has not reached m, then the query is made instep248 as to whether it is the first iteration. If it is, multiplication of β_kby 1 is effected instep250 and then the square of that value is performed over a Galois field instep252. If it is not the first iteration, then instep254, the Galois field multiplication of β_kby the Galois field linear transform output is performed and then the square is performed in Galois field multiplier instep252. The output from the square calculation is then fed back,step242, and the iteration begins again.
• Thus far the invention has focused on a Galois field divider engine and method and to the ability to reduce that engine in size by first reducing the size of one of the Galois field linear transformers and eliminating one of the polynomial multipliers and then by combining the functions of the two linear transformers so that a succession of Galois field linear transforms on a succession of polynomial inputs is performed to obtain the ultimate output (quotient) as shown inFIGS. 19 and 20. But, this is not a necessary limitation of the invention, that is it is not limited to merely division. A compound Galois field engine according to this invention may perform any succession of Galois field linear transforms on a succession of polynomial inputs to obtain an ultimate output where each input, except the first, is the output of the previous Galois field linear transform. That is in one transform it can immediately predict the modulo remainder of the succession of Galois field linear transforms of an irreducible Galois field polynomial to obtain the ultimate output of the Galois field linear transform directly from the first input.
• Another example of this fact can be seen in the square root operation of a Galois field member β. There is shown inFIG. 22 a compoundGalois field engine300 according to this invention that performs (m−1) successive Galois fieldlinear transforms302,304 . . .306 wherein a first input f,308 is submitted toGalois field transformer302 and then the transformed output becomes the input to the next Galois fieldlinear transformer304, whose output becomes the input to the next Galois field linear transformer, and so on, until it reaches thefinal transformer306 as in this case, the √{square root over (β)} output. In accordance with this invention, by compounding the Galois field linear transformers as shown in310FIG. 23, the (m−1) transformers ofFIG. 22 can be reduced to produce the simplified implementation shown inFIG. 23 of only one GFLT, where, the initial input β can be transformed in a single operation by the compound Galois field linear transformersquare root engine330 to provide in one iteration, the √{square root over (β)} output.
• The fact that √{square root over (β)}=β^2(m−1)is shown by the following exposition given: in (1) we have shown that β^q−1=1.
• Replacing q with 2^mand multiplying both sides by , results in the expression
  β^2m=β  (4)
  Taking the √ form both sides results in the expression
  β^(2m)/2=√{square root over (β)}  (5)
  or
  β^2(m−1)=√{square root over (β)}  (6)
  FIG. 22 is a straightforward implementation of this expression.
• The Galois field square root method of this invention is shown inFIG. 24 where the field element β are provided atstart312. A query is then made as to whether this iteration is the m^th−1 iteration instep314, where m is the degree of the Galois field involved. If it is the m^th−1 iteration, the system goes directly to step316 where the Galois field square root of β is produced. If the iteration has not reached m−1, then the query is made instep318 as to whether it is the first iteration. If it is, the square of that β value is performed over a Galois field instep320. If it is not the first iteration, the square of the Galois field linear transform output is performed over a Galois field instep322. The output from the square calculation is then fed back,step314, and the iteration begins again. A programming circuit, control flip-flops212aandprogramming sequencer210a, programs the Galois field linear transformersquare root engine330 as shown inFIG. 23.
• In summary, generally a compoundGalois field engine260,FIG. 25 according to this invention may perform a number of successive Galois fieldlinear transforms262,264,266,268 wherein a first input A,270 is submitted toGalois field transformer262 and then the transformed output B becomes the input to the next Galois fieldlinear transformer264, whose output C in turn becomes the input to the next Galois field linear transformer,266 whose output D becomes the input to the next Galois fieldlinear transformer268, and so on. In this case, the ultimate output is E. In accordance with this invention, by compounding the Galois field linear transformers as shown inFIG. 19, by reducing the two transformers ofFIG. 18 to produce the implementation shown inFIG. 20, the initial input A can be transformed in a single operation by compound Galois fieldlinear transformer280 to provide in that one iteration, the ultimate output E.
• Although specific features of the invention are shown in some drawings and not in others, this is for convenience only as each feature may be combined with any or all of the other features in accordance with the invention. The words “including”, “comprising”, “having”, and “with” as used herein are to be interpreted broadly and comprehensively and are not limited to any physical interconnection. Moreover, any embodiments disclosed in the subject application are not to be taken as the only possible embodiments.
• Other embodiments will occur to those skilled in the art and are within the following claims:

Claims (3)

1. A Galois field square root method comprising:

inputting a Galois field element to a Galois field square root generator to obtain an output; and

squaring in the Galois field square root generator the output of the Galois field square root generator for predicting the modulo remainder of the square of the polynomial product of an irreducible polynomial m−1 times where m is the degree of the Galois field to obtain the square root of the Galois field element in (m−1) cycles.

2. A Galois field square root engine comprising:

a Galois field square root generator;

an input circuit for inputting a Galois field element to the Galois field square root generator to obtain the square root of the Galois field elements in one cycle.

3. The Galois field square root engine ofclaim 2 in which said Galois field square root engine includes a Galois field multiplier, and a program circuit for programming said Galois field multiplier to perform a compound square operation of m−1 times in one cycle.

Images