Patent US4574361A successfully refreshed from Google Patents.
US4574361A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus for dividing the elements of a Galois field
Assignee: Toshiba Corp
•
Filing: 1983-03-10
•
Granted: 1986-03-04
•
Expires: 2003-03-10
Abstract
Abstract An apparatus divides one element α i of a Galois field GF(2 m ) by another element α j of the field. Divider data α j are supplied to one of the first linear shift registers and to the other first linear shift registers through α N1 , α N2 , . . . multiplier circuits, respectively. Simultaneously, dividend data α i are supplied to one of the second linear shift registers and to the other second linear shift registers through α N1 , α N2 , . . . multiplier circuits, respectively. "1" detector circuits are connected to the outputs of the first linear shift registers, respectively. The first linear shift registers and the second linear shift registers are shifted several times until any "1" detector circuit detects "1" in response to output signals from a 2-input AND gate. When "1" is detected, a NOR gate supplies a signal of logical "0" to the AND gate, whereby the AND gate stops supplying output signals. 2-input AND circuits are connected at one input terminal to the outputs of the "1" detector circuits and at the other input terminal to the outputs of the second linear shift registers. The AND circuit connected to the "1" detector circuit supplies the data stored in the second linear shift register to which it is connected. The data representing the quotient of the division α i -α j , are delivered through an OR circuit.
Inventors
- 👤 Jun Inagawa
- 👤 Masahide Nagumo
- 👤 Tadashi Kojima
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 08:53
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; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F7/60; G06F7/72; G06F7/724; G06F7/726; G11; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1806; G11B20/1809
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
216 words
An apparatus for dividing one element α i of a Galois field GF(2 m ) consisting of 2 m elements by another element α j , thus performing a division of α i ÷α j , where α is the root of a modulus polynominal F.sub.(x), said apparatus comprising: a first linear shift register for storing data representing the element α j ; a second linear shift register for storing data representing the element α i ; a first "1" detector circuit connected to the output of said first linear shift register; first shift means for detecting the number of times said first "1" detector circuit produces no output and for generating a shift signal to shift said first and second linear shift registers M times according to the detecting result; and first output means for providing, as a quotient of the division α i ÷α j , that output α i ·α M of said second linear shift register which is obtained when the output of said first linear shift register controlled by said first shift means becomes α j ·α M =1, when said first output means receives a "1" detection output of said first "1" detector circuit which is obtained when said first "1" detector circuit detects that α j ·α M =1.
Claim 2
Independent Claim
216 words
An apparatus for dividing one element α i of a Galois field GF(2 m ) consisting of 2 m elements by another element α j , thus performing a division of α i ÷α j , where α is the root of a modulus polynominal F.sub.(x), said apparatus comprising: a first linear shift register for storing data representing the element α j ; a second linear shift register for storing data representing the element α i ; a first "1" detector circuit connected to the output of said first linear shift register; first shift means for detecting the number of times said first "1" detector circuit produces no output and for generating a shift signal to shift said first and second linear shift registers M times according to the detecting result; and first output means for providing, as a quotient of the division α i ÷α j , that output α i ·α M of said second linear shift register which is obtained when the output of said first linear shift register controlled by said first shift means becomes α j ·α M =1, when said first output means receives a "1" detection output of said first "1" detector circuit which is obtained when said first "1" detector circuit detects that α j ·α M =1.
Claim 3
Dependent Claim
227 words
An apparatus according to claim 1, further comprising: at least one first multiplier circuit for multiplying the element α j by a predetermined multiplier α N ; at least one second multiplier circuit for multiplying the element α i by the predetermined multiplier α N ; at least one third linear shift register for receiving the output of said first multiplier circuit; at least one fourth linear shift register for receiving the output of said second multiplier circuit; at least one second "1" detector circuit coupled to the output of said third linear shift register; at least one second shift means for detecting the number of times said second "1" detector circuit produces no output and producing a shift signal to shift said third and fourth linear shift registers M times according to the detection result; and at least one second output means for providing, as a quotient of the division α i ÷α j , that output α i ·α N ·α M of said fourth linear shift register which is obtained when the output of said third linear shift register controlled by said second shift means becomes α j ·α N ·α M =1, in response to a "1" detection output of said second "1" detector circuit which is obtained when said second "1" detector circuit detects that α j ·α N ·α M =1.
Claim 4
Dependent Claim
30 words
An apparatus according to claim 2, wherein the power N of the multiplier α N for said first and second multiplier circuits is a multiple of 1/n 2 m (n≧2).
Claim 5
Dependent Claim
27 words
An apparatus according to claim 2, wherein the power N of the multiplier α N for said first and second multiplier circuits is a multiple of 1.
Claim 6
Dependent Claim
30 words
An apparatus according to claim 1, wherein when shifted, each of said first and second linear shift registers provides data that equals stored data multiplied by α for each shifting.
Claim 7
Dependent Claim
32 words
An apparatus according to claim 1, wherein when shifted, each of said first and second linear shift registers provides data that equals stored data multiplied by α NO (NO≧2) for each shifting.
References Cited (Backward Citations)
US3828175A
Cited
US4099160A
Cited
US4142174A
Cited
EP0012828A1
Cited
GB2081479A
Cited
US4473887A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1989-03-03 | 1989-09-02 | 1990-03-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1993-03-03 | 1993-09-02 | 1994-03-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1997-03-03 | 1997-09-02 | 1998-03-04 | $7700.00 | Window Closed / Lapsed |