US4918638A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multiplier in a galois field
Assignee: Panasonic Holdings Corp
•
Filing: 1987-10-09
•
Granted: 1990-04-17
•
Expires: 2007-10-09
Abstract
Abstract A circuit effects regular multiplicaton of two field elements in a Galois field GF (2m). Each of the field elements is expressed by an m-bit binary number. The two field elements are applied to a binary multiplier array which generates (2m-1)-bit partial products. The partial products are divided by a generator polynomial of the Galois field to produce final m-bit binary products.
Inventors
- 👤 Michihito Matsumoto
- 👤 Kazuhiro Murase
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 10:23
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/38; G06F7/48; G06F7/52; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; H03M13/151; G06F7/60; G06F7/72; G06F7/724; H03M13/033
Claims Analysis
Total Claims: 6
Claim 1
Independent Claim
119 words
An apparatus for carrying out multiplication of field elements P=Σp i ·α i , Q=Σq i ·α i (i=0 through m-1) in a Galois field GF(2 m ) whose generator polynomial is g(x)=x m +Σk i ·x i (i=0 through m-1, ki=binary coefficient) comprising: a binary multiplier array supplied with the field elements P, Q for generating partial products R=Σr n ·α n (n=0 through 2m-2) where r n =Σp u ·q v for all n=u+v (u=0 through m-1≦n and v=0 through m-1≦); and a polynomial reducer supplied with the partial products R for generating final products S=Σs i ·α i (i=0 through m-1, Si=binary component of S) through division of the partial products R by the generator polynomial.
Claim 2
Independent Claim
119 words
An apparatus for carrying out multiplication of field elements P=Σp i ·α i , Q=Σq i ·α i (i=0 through m-1) in a Galois field GF(2 m ) whose generator polynomial is g(x)=x m +Σk i ·x i (i=0 through m-1, ki=binary coefficient) comprising: a binary multiplier array supplied with the field elements P, Q for generating partial products R=Σr n ·α n (n=0 through 2m-2) where r n =Σp u ·q v for all n=u+v (u=0 through m-1≦n and v=0 through m-1≦); and a polynomial reducer supplied with the partial products R for generating final products S=Σs i ·α i (i=0 through m-1, Si=binary component of S) through division of the partial products R by the generator polynomial.
Claim 3
Dependent Claim
38 words
An apparatus according to claim 1, wherein said binary multiplier array comprises AND gates each for effecting an AND operation of p i ·q i and exclusive-OR gates for effecting bit addition of outputs from said AND gates.
Claim 4
Dependent Claim
64 words
An apparatus according to claim 1, wherein said polynomial reducer comprises a plurality of exclusive-OR gates for reducing terms of α 2m-2 through α m of the partial products R to terms of α m-1 through α 0 thereof and effecting bit addition of the terms which have been reduced and the terms of α m-1 through α 0 of the partial products R.
Claim 5
Dependent Claim
67 words
An apparatus according to claim 1, wherein said polynomial reducer comprises a plurality of exclusive-OR gates arranged for reducing each term α n of the partial products R to terms of α n-1 through α n-m thereof in repeated cycles from n=2m-2 to m, thereby reducing terms of α 2m-2 through α m of the partial products R to terms of α m-1 through α 0 thereof.
Claim 6
Dependent Claim
36 words
An apparatus according to claim 4, wherein said polynomial reducer further includes AND gates connected so that one input of each of the AND gates is controlled by a coefficient k i of the generator polynomial.
References Cited (Backward Citations)
US4037093A
Cited
US4251875A
Cited
JPS57155667A
Cited
US4473887A
Cited
US4587627A
Cited
JPS60144834A
Cited
US4697248A
Cited
US4745568A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-04-16 | 1993-10-16 | 1994-04-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-04-16 | 1997-10-16 | 1998-04-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-04-16 | 2001-10-16 | 2002-04-17 | $7700.00 | Window Closed / Lapsed |