Back to results
US 4,251,875 AGranted
Sequential Galois multiplication in GF(2.sup.n) with GF(2.sup.m) Galois multiplication gates
AssigneeSperry Corporation
InventorsJames M. Marver, Wayne R. Olson
Life of this patent
Estimating the term…
Abstract
Configurations of Boolean elements for implementing a sequential GF(2.sup.n) Galois multiplication gate are disclosed. Each configuration includes a single subfield GF(2.sup.m) Galois multiplication gate, where m is a positive integral divisor of n, e.g., n=8 and m=2, and assorted controls. Also disclosed is a sequential implementation of a GF(2.sup.n) Galois linear module as described in the J. T. Ellison Pat. No. 3,805,037 wherein the controls of the sequential GF(2.sup.n) multiply gate cause the Galois addition (bit-wise Exclusive-OR) of an n-bit binary vector, Z, to the final Galois product.
Claims11
A Galois GF(2.sup.n) multiplication gate for performing the Galois multiplication in the Galois field GF(2.sup.n) which Galois GF(2.sup.n) multiplication gate generates the Galois product X.multidot.Y=(X.multidot.Y).sub.0, . . . , (X.multidot.Y).sub.n-1 from the Galois input on n, X input lines
- X.sub.0, . . . , X.sub.n-1
- and from the Galois input on n, Y input lines
- Y.sub.0, . . . , Y.sub.n-1
- comprising:
- a single GF(2.sup.m) Galois multiplication gate having the Galois subfield GF(2.sup.m) where m is a positive integral divisor of n having the relationship of k=n/m, where k is a positive integer greater than 1, k>1, which single GF(2.sup.m) Galois multiplication gate generates k.sup.2 subfield GF(2.sup.m) Galois partial products;
- input sequencer means receiving said X and Y n-bit inputs and sequential coupling k m-bit portions of each of said X and Y n-bit inputs to said single GF(2.sup.m) Galois multiplication gate for enabling said single GF(2.sup.m) Galois multiplication gate to sequentially generate said k.sup.2 subfield GF(2.sup.m) Galois partial products therefrom;
- and,
- means including constant multiplier means, responsively coupled to said single GF(2.sup.m) Galois multiplication gate and sequentially accumulating said sequentially generated k.sup.2 subfield GF(2.sup.m) products for providing on n output lines the n-bit Galois product X.multidot.Y.
5 more elements
A Galois GF(2.sup.n) multiplication gate for performing the Galois multiplication in the Galois field GF(2.sup.n) which Galois GF(2.sup.n) multiplication gate generates the Galois product X.multidot.Y=(X.multidot.Y).sub.0, . . . , (X.multidot.Y).sub.n-1 from the Galois input on n, X input lines
- X.sub.0, . . . , X.sub.n-1
- and from the Galois input on n, Y input lines
- Y.sub.0, . . . , Y.sub.n-1
- comprising:
- a single GF(2.sup.m) Galois multiplication gate having the Galois subfield GF(2.sup.m), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which single GF(2.sup.m) Galois multiplication gate generates k.sup.2 subfield GF(2.sup.m) Galois partial products;
- X input register means for bi-serially receiving said n-bit X input and for sequentially bit-parallelly coupling m-bit portions of said n-bit X input to said single GF(2.sup.m) Galois multiplication gate;
- Y input register means for bit-serially receiving said n-bit Y input and for sequentially bit-parallelly coupling m-bit portions of n-bit Y input to said single GF(2.sup.m) Galois multiplication gate;
- .multidot.t.sup.2.spsp.m.sup.-2, .multidot.t.sup.2.spsp.m.sup.-3, . . . , .multidot.t.sup.d, . . . , .t.sup.2, .multidot.t, .multidot.1,
- .multidot.0 constant multiplier means responsively coupled to said single GF(2.sup.m) Galois multiplication gate for seuentially receiving said k.sup.2 subfield GF(2.sup.m) Galois partial products and sequentially generating k.sup.2 sets of GF(2.sup.m).multidot.t.sup.d or GF(2.sup.m) .multidot.0 Galois partial products therefrom;
- and,
- accumulator means sequentially receiving and accumulating said k.sup.2 sets of subfield GF(2.sup.m).multidot.t.sup.d or GF(2.sup.m).multidot.0 Galois partial products for generating and bit-serially outputting said n-bit Galois product X.multidot.Y.
8 more elements
A Galois GF(2.sup.n) multiplication gate for performing the Galois multiplication in the Galois field GF(2.sup.n) which Galois GF(2.sup.n) multiplication gate generates the Galois product X.multidot.Y=(X.multidot.Y).sub.0, . . . , (X.multidot.Y).sub.n-1 from the Galois input on n, X input lines
- X.sub.0, . . . , X.sub.n-1
- and from the Galois input on n, Y input lines
- Y.sub.0, . . . , Y.sub.n-1
- comprising:
- GF(2.sup.m) Galois multiplication gate means having the Galois subfield GF(2.sup.m), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which GF(2.sup.m) Galois multiplication gate means generates k.sup.2 subfield GF(2.sup.m) Galois partial products;
- input sequencer means for receiving said Galois input on said n, X input lines and said Galois input on said n, Y input lines and sequentially coupling m-bit segments of X(X.sub.m) and Y(Y.sub.m) to said GF(2.sup.m) Galois multiplication gate means;
- .multidot.t.sup.2.spsp.m.sup.-2, .multidot.t.sup.2.spsp.m.sup.-3, . . . , .multidot.t.sup.d, . . . , .multidot.t.sup.2 .multidot.t, .multidot.1, .multidot.0 constant multiplier means responsively coupled to said GF(2.sup.m) Galois multiplication gate means for sequentially receiving said k.sup.2 subfield GF(2.sup.m) Galois partial products and sequentially generating k.sup.2 sets of GF(2.sup.m).multidot.t.sup.d or GF(2.sup.m).multidot.0 Galois partial products therefrom;
- n/m multiplexer means, each receiving in parallel, said k.sup.2 sets of GF(2.sup.m).multidot.t.sup.d or GF(2.sup.m).multidot.0 Galois products from said constant multiplier means;
- n/m toggle means, each coupled to a respectively associated one of said n/m multiplexer means for receiving the output therefrom;
- output register means coupled to each of said n/m toggle means for receiving and formatting the outputs therefrom in an n-bit format, and
- control sequencer means coupled to said input sequencer means, said n/m multiplexer means and said n/m toggle means for sequentially processing said m-bit segments of X(X.sub.m) and Y(Y.sub.m) from said input sequencer means to form said Galois product X.multidot.Y at said output register means.
8 more elements
A Galois GF(2.sup.n) multiplication gate for performing the Galois multiplication in the Galois field GF(2.sup.n) which Galois GF(2.sup.n) multiplication gate generates the Galois product X.multidot.Y=(X.multidot.Y).sub.0, . . . , (X.multidot.Y).sub.n-1 from the Galois input on n, X input lines
- X.sub.0, . . . , X.sub.n-1
- and from the Galois input on n, Y input lines
- Y.sub.0, . . . , Y.sub.n-1
- comprising:
- GF(2.sup.m)Galois multiplication gate means having the Galois subfield GF(2.sup.m), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which GF(2.sup.m) Galois multiplication gate means generates k.sup.2 subfield GF(2.sup.m) Galois partial products;
- X input register means for bit-serially receiving said n-bit X input and for sequentially bit-paralelly coupling m-bit portions of said n-bit X input to said GF(2.sup.m) Galois multiplication gate means;
- Y input register means for bit-serially receiving said n-bit Y input and for sequentially bit-parallelly coupling m-bit portions of said n-bit Y input to said GF(2.sup.m) Galois multiplication gate means;
- X.sub.m .multidot.Y.sub.m register means for receiving and storing said k.sup.2 subfield GF(2.sup.m) Galois partial products from said GF(2.sup.m) multiplication gate means;
- .multidot.t.sup.d constant multiplier means receiving said k.sup.1 subfield GF(2.sup.n) Galois partial products from said X.sub.m .multidot.Y.sub.m register means for performing the appropriate constant multiply for each of said k.sup.2 subfield GF(2.sup.m) Galois partial products;
- Galois sum means for receiving the output of said .multidot.t.sup.d constant multiplier means;
- output register means for receiving said storing the output of said Galois sum means;
- and,
- multiplexer means sequentially coupling the contents of said output register means to said Galois sum means for sequentially enabling said Galois sum means to perform the Galois sum of the output of said .multidot.t.sup.d constant multiplier means and said output register means for each of said k.sup.2 subfield GF(2.sup.m) Galois partial products and generating in said output register means said Galois product X.multidot.Y.
10 more elements
A Galois GF(2.sup.n) multiplication gate for performing the Galois multiplication in the Galois field GF(2.sup.n) which Galois GF(2.sup.n) multiplication gate generates the Galois product X.multidot.Y=(X.multidot.Y).sub.0, . . . , (X.multidot.Y).sub.n-1 from the Galois input on n, X input lines
- X.sub.0, . . . , X.sub.n-1
- and from the Galois input on n, Y input lines
- Y.sub.0, . . . , Y.sub.n-1
- comprising:
- GF(2m) Galois multiplication gate means having the Galois subfield GF(2.sup.m), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which GF(2.sup.m) Galois multiplication gate means generates k.sup.2 subfield GF(2.sup.m) Galois partial products;
- X input means for receiving said n-bit X input and for sequentially coupling m-bit portions of said n-bit X input to said GF(2.sup.m) Galois multiplication gate means;
- Y input means for receiving said n-bit Y input and for sequentially coupling m-bit portions of said n-bit Y input to said GF(2.sup.m) Galois multtiplication gate means;
- X.sub.m .multidot.Y means for receiving and storing said k.sup.2 subfield GF(2.sup.m) Galois partial products from said GF(2.sup.m) multiplication gate means;
- .multidot.t.sup.d constant multiplier means receiving said k.sup.2 subfield GF(2.sup.m) Galois partial products from said X.sub.m .multidot.Y.sub.m means for performing the appropriate constant multiply for each of said k.sup.2 subfield GF(2.sup.m) Galois partial products;
- Galois sum means for receiving the output of said .multidot.t.sup.d constant multiplier means;
- output means for receiving and storing the output of said Galois sum means;
- and,
- multiplexer means sequentially coupling the contents of said output means to said Galois sum means for sequentially enabling said Galois sum means to perform the Galois sum of the output of said .multidot.t.sup.d constant multiplier means and said output means for each of said k.sup.2 subfield GF(2.sup.m) Galois partial products and generating in said output means said Galois product X.multidot.Y.
10 more elements
A Galois GF(2.sup.n) linear gate for performing the Galois linear operation in the Galois field GF(2.sup.n) which Galois GF(2.sup.n) linear gate generates the Galois linear resultant X.multidot.Y+Z=(X.multidot.Y+Z).sub.0, . . . , (X.multidot.Y+Z).sub.n-1 from the Galois input on n, X input lines
- X.sub.0, . . . , X.sub.n-1
- from the Galois input on n, Y input lines
- Y.sub.0, . . . , Y.sub.n-1
- and from the Galois input on n, Z input lines
- Z.sub.0, . . . , Z.sub.n-1
- comprising:
- a single GF(2.sup.m) Galois multiplication gate having the Galois subfield GF(2.sup.m), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which single GF(2.sup.m) Galois multiplication gate generates k.sup.2 subfield GF(2.sup.m) Galois partial products;
- input sequencer means receiving said X and Y n-bit inputs and sequential coupling k m-bit portions of each of said X and Y n-bit inputs to said single GF(2.sup.m) Galois multiplication gate for enabling said single GF(2.sup.m) Galois multiplication gate to sequentially generate said k.sup.2 subfield GF(2.sup.m) Galois partial products therefrom;
- and,
- means, including constant multiplier means, responsively coupled to said single GF(2.sup.m) Galois multiplication gate and to said Z n-bit inputs for sequentially accumulating said sequentially generated k.sup.2 subfield GF(2.sup.m) partial products and providing on n output lines the n-bit Galois linear resultant X.multidot.Y+Z.
7 more elements
A Galois GF(2.sup.n) linear gate for performing the Galois linear operation in the Galois field GF(2.sup.n) which Galois GF(2.sup.n) linear gate generates the Galois linear resultant X.multidot.Y+Z=(X.multidot.Y+Z).sub.0, . . . , (X.multidot.Y+Z).sub.n-1 from the Galois input on n, X input lines
- X.sub.0, . . . , X.sub.n-1
- from the Galois input on n, Y input lines
- Y.sub.0, . . . , Y.sub.n-1
- and from the Galois input on n, Z input lines
- Z.sub.0, . . . , Z.sub.n-1
- comprising:
- GF(2.sup.m) Galois multiplication gate means having the Galois subfield GF(2.sup.m), where m is a positive integral divisor of n having the relationship of k=n/m and where k is a positive integer greater than 1, k>1, which GF(2.sup.m) Galois multiplication gate means generates k.sup.2 subfield GF(2.sup.m) Galois partial products;
- X input means for receiving said n-bit X input and for sequentially coupling m-bit portions of said n-bit X input to said GF(2.sup.m) Galois multiplication gate means;
- Y input means for receiving said n-bit Y input and for sequentially coupling m-bit portions of said n-bit Y input to said GF(2.sup.m) Galois multiplication gate means;
- X.sub.m .multidot.Y.sub.m means for receiving and storing said k.sup.2 subfield GF(2.sup.m) Galois partial products from said GF(2.sup.m) multiplication gate means;
- Z input means for receiving said n-bit Z input and for sequentially coupling m-bit portions of said n-bit Z input to said X.sub.m .multidot.Y.sub.m means;
- said X.sub.m .multidot.Y.sub.m means forming k.sup.2 subfield GF(2.sup.m) Galois partial resultants from said k.sup.2 subfield GF(2.sup.m) Galois partial products and said m-bit portions of said n-bit Z input;
- .multidot.t.sup.d constant multiplier means receiving said k.sup.2 subfield GF(2.sup.n) Galois partial resultants from said X.sub.m .multidot.Y.sub.m means for performing the appropriate constant multiply for each of said k.sup.2 subfield GF(2.sup.m) Galois partial resultants;
- Galois sum means for receiving the output of said .multidot.t.sup.d constant multiplier means;
- output means for receiving and storing the output of said Galois sum means;
- and,
- multiplexer means sequentially coupling the contents of said output means to said Galois sum means for sequentially enabling said Galois sum means to perform the Galois sum of the output of said .multidot.t.sup.d constant multiplier means and said output means for each of said k.sup.2 subfield GF(2.sup.m) Galois partial resultants and generating in said output means said Galois linear resultant X.multidot.Y+Z.
14 more elements
Dependencies are inferred from the claim text.