US4567568A
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-01-28
•
Expires: 2003-03-10
Abstract
Abstract Data representing one element α i of a Galois field GF(2 m ) are stored in a first linear shift register, and data representing another element α j of the Galois field GF(2 m ) are stored in a second linear shift register. 2 m elements of Galois field GF(2 m ) are divided into n groups. A table of the reciprocals of n elements located at specific positions respectively in n groups is stored in a converter which includes a decoder and an encoder. The data representing element α j are supplied from the second linear shift register to the decoder. If the data representing the reciprocal of element α j are stored in the converter, they are read from the encoder. If they are not stored in the converter, the first linear shift register and the second linear shift register are shifted N times by control pulses generated by a NOR gate and an AND gate until any one of the reciprocal data are read from the encoder, whereby the register supplies data representing α i+N and the register supplies data representing α - (j+N). A multiplier multiplies element α i by reciprocal α j or multiplies element α i+N by reciprocal α - (j+N), thereby performing the division: a i ÷α j (=α i-j ).
Inventors
- 👤 Jun Inagawa
- 👤 Masahide Nagumo
- 👤 Tadashi Kojima
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 23:46
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/724; G06F7/726; G11; G11B; G11B20/00; G11B20/10; G11B20/18; G11B20/1806; G11B20/1809; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; G06F1/00; G06F1/02; G06F1/03; G06F1/0307
Claims Analysis
Total Claims: 4
Claim 1
Independent Claim
255 words
An apparatus for dividing one element α i of a Galois field GF(2 m ), consisting of 2 m elements divided into n groups, by another element α j , thus performing a division of: α i ÷α j (=α i-j ), where α is the root of a modulus polynomial F.sub.(x), said apparatus comprising: reciprocal data memory means for storing data representing reciprocals of n elements located at specific positions respectively in n groups; a first linear shift register for storing data representing the element α j ; comparator means for comparing the data stored in said first linear shift register with the data stored in said reciprocal data memory means, to thereby deliver data representing the reciprocal of the data stored in said reciprocal data memory means; first shifting means for detecting the number of times said reciprocal data memory means produces no output when said comparator means performs the data comparison, and for generating a shift signal to shift said first linear shift register by N times according to the detecting result; a second linear shift register for storing data α - (j+N) from said reciprocal data memory means; second shifting means for counting said shift signal from said first shifting means and shifting said second linear shift register a number of times determined by the counting result and; multiplier means for multiplying α - (j+N)+N =α -j , output from said second linear shift register, by said element α i , thereby providing an output of α i-j , where 0≦N≦n-1.
Claim 2
Independent Claim
255 words
An apparatus for dividing one element α i of a Galois field GF(2 m ), consisting of 2 m elements divided into n groups, by another element α j , thus performing a division of: α i ÷α j (=α i-j ), where α is the root of a modulus polynomial F.sub.(x), said apparatus comprising: reciprocal data memory means for storing data representing reciprocals of n elements located at specific positions respectively in n groups; a first linear shift register for storing data representing the element α j ; comparator means for comparing the data stored in said first linear shift register with the data stored in said reciprocal data memory means, to thereby deliver data representing the reciprocal of the data stored in said reciprocal data memory means; first shifting means for detecting the number of times said reciprocal data memory means produces no output when said comparator means performs the data comparison, and for generating a shift signal to shift said first linear shift register by N times according to the detecting result; a second linear shift register for storing data α - (j+N) from said reciprocal data memory means; second shifting means for counting said shift signal from said first shifting means and shifting said second linear shift register a number of times determined by the counting result and; multiplier means for multiplying α - (j+N)+N =α -j , output from said second linear shift register, by said element α i , thereby providing an output of α i-j , where 0≦N≦n-1.
Claim 3
Independent Claim
226 words
An apparatus for dividing one element α i of a Galois field GF(2 m ), consisting of 2 m elements divided into n groups, by another element α j , thus performing a divison of: α i ÷α j (=α i-j ), where α is the root of a modulus polynomial F.sub.(x), said apparatus comprising: reciprocal data memory means for storing data representing reciprocals of n elements located at specific positions respectively in n groups; a first linear shift register for storing data representing the element α j ; comparator means for comparing the data stored in said first linear shift register with the data stored in said reciprocal data memory means, to thereby deliver data representing the reciprocal of the data stored in said reciprocal data memory means; a second linear shift register for storing data representing the element α i ; shifting means for detecting the number of times said reciprocal data memory means produces no output when said comparator means performs the data comparison, and for generating a shift signal to shift said first and second linear shift registers by N times according to the detecting result; and multiplier means for multiplying α - (j+N), output from said reciprocal data memory means, by α i+N , output from said second linear shift register, thereby providing an output of α i-j , where 0≦N≦n-1.
Claim 4
Independent Claim
226 words
An apparatus for dividing one element α i of a Galois field GF(2 m ), consisting of 2 m elements divided into n groups, by another element α j , thus performing a divison of: α i ÷α j (=α i-j ), where α is the root of a modulus polynomial F.sub.(x), said apparatus comprising: reciprocal data memory means for storing data representing reciprocals of n elements located at specific positions respectively in n groups; a first linear shift register for storing data representing the element α j ; comparator means for comparing the data stored in said first linear shift register with the data stored in said reciprocal data memory means, to thereby deliver data representing the reciprocal of the data stored in said reciprocal data memory means; a second linear shift register for storing data representing the element α i ; shifting means for detecting the number of times said reciprocal data memory means produces no output when said comparator means performs the data comparison, and for generating a shift signal to shift said first and second linear shift registers by N times according to the detecting result; and multiplier means for multiplying α - (j+N), output from said reciprocal data memory means, by α i+N , output from said second linear shift register, thereby providing an output of α i-j , where 0≦N≦n-1.
References Cited (Backward Citations)
US3533067A
Cited
US3633018A
Cited
US4162480A
Cited
US4142174A
Cited
GB2050014A
Cited
GB2079994A
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-01-27 | 1989-07-29 | 1990-01-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1993-01-27 | 1993-07-29 | 1994-01-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1997-01-27 | 1997-07-29 | 1998-01-28 | $7700.00 | Window Closed / Lapsed |