US4037093A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Matrix multiplier in GF(2m)
Assignee: Bull HN Information Systems Inc
•
Filing: 1975-12-29
•
Granted: 1977-07-19
•
Expires: 1995-12-29
Abstract
Abstract The invention comprises circuitry for systematically multiplying two arbitrary field elements in a Galois field GF(2m). Each element is represented by an m-bit binary number. The multiplicand field element is passed serially through a plurality of m-1 modulo multipliers. The multiplicand and the product from each of the m-1 modulo multipliers are passed through networks which are gated by bits of the multiplier field element forming partial products. The partial products are summed to form the bit representations of the final product.
Inventors
- 👤 Gordon E. Gregg
- 👤 Thomas H. Howell
- 👤 Leonard Rabins
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 15:33
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/724
Claims Analysis
Total Claims: 6
Claim 1
Independent Claim
197 words
An apparatus for multiplying arbitrary field elements F(x) and P (x) (where F(x)=f i x i , P(x)=P i x i for i from 0 to m-1) in a Galois field GF(2 m ), where g(x)-g i x i (i=0 to m) is a generator polynomial for said Galois field, comprising: m-1 ordered multiplying means, the first of said ordered multiplying means responsive to signals representing field elements of F(x), the remainder of said ordered multiplying means responsive to output signals from the preceding one of said ordered multiplying means, each of said multiplying means multiplying its output by x and producing a result modulo g(x); m ordered logical means, the ith of said logical means coupled to the (i-1) of said multiplying means and having input signals x i F(x), ith logical means gating its input by p i and producing a partial product of PxG; and PxF from m summing means responsive to said m logical means for receiving said partial products, said summing means generating signals corresponding to the product P+F modulo g(x), each member of said summing means responsive to a corresponding component of a partial product of each of said logical means.
Claim 2
Independent Claim
197 words
An apparatus for multiplying arbitrary field elements F(x) and P (x) (where F(x)=f i x i , P(x)=P i x i for i from 0 to m-1) in a Galois field GF(2 m ), where g(x)-g i x i (i=0 to m) is a generator polynomial for said Galois field, comprising: m-1 ordered multiplying means, the first of said ordered multiplying means responsive to signals representing field elements of F(x), the remainder of said ordered multiplying means responsive to output signals from the preceding one of said ordered multiplying means, each of said multiplying means multiplying its output by x and producing a result modulo g(x); m ordered logical means, the ith of said logical means coupled to the (i-1) of said multiplying means and having input signals x i F(x), ith logical means gating its input by p i and producing a partial product of PxG; and PxF from m summing means responsive to said m logical means for receiving said partial products, said summing means generating signals corresponding to the product P+F modulo g(x), each member of said summing means responsive to a corresponding component of a partial product of each of said logical means.
Claim 3
Dependent Claim
40 words
The apparatus as defined in claim 1 wherein each of said ith logical means comprises a plurality of m logic gates enabled by p i , the jth said logic gates responsive to the jth bit of x i F(x).
Claim 4
Dependent Claim
46 words
The apparatus as defined in claim 1 wherein said summing means comprises m summing circuits, the ith of said summing circuits receiving the ith bit of each of said partial products and generating a signal corresponding to said ith bit of said product PxF modulo g(x).
Claim 5
Dependent Claim
79 words
The apparatus as defined in claim 1 wherein each of said plurality of multiplying means comprises a switching and gating circuit, wherein when the inputs to said circuit are J(x)=j i x i and the output of said circuit are H(x)=h i x i , said circuit switches and gates its inputs to produce outputs with the following relationships: h 0 =j m -1 h i =j i -1 (j m -1 .g i ,) where i=1 to m-1.
Claim 6
Dependent Claim
70 words
The apparatus as defined in claim 4 wherein each of said circuits comprises: m-1 ordered AND gates responsive to g 1 to g m -1 respectively, all of said AND gates responsive to j m -1 , and m-1 ordered XOR gates, the ith of said XOR gates responsive to the ith of said AND gates and to j i -1 for generating a signal corresponding to h i .
References Cited (Backward Citations)
US3557356A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1980-07-18 | 1981-01-17 | 1981-07-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1984-07-18 | 1985-01-17 | 1985-07-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1988-07-18 | 1989-01-17 | 1989-07-19 | $7700.00 | Window Closed / Lapsed |