US4994995A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Bit-serial division method and apparatus
Assignee: International Business Machines Corp
•
Filing: 1990-03-14
•
Granted: 1991-02-19
•
Expires: 2010-03-14
Abstract
Abstract A bit-serial division method for computing the value v/u, where v and u are each n-bit vectors that are elements in a finite Galois field GF(2 n ) consisting of 2 n elements. The n-bit components of each element in the field are coordinates of the element in a canonical basis of the field. Vector u is converted from canonical basis to a dual basis. Vector u in dual basis also comprises n bits in the finite field ordered according to an index i that takes on values from 0 to (n-1). All bits n of the converted vector u are loaded into a shift register in parallel, then converted from dual basis back to canonical basis to produce a single bit output w 0 from a lookup table which generates bitwise the inverse of the n-bit vector u. The bits in the shift register are shifted (n-1) times to generate successive additional single bit outputs w i with said lookup table. Then each bit w i is multiplied by the vector v and a corresponding element c i in dual basis to generate a cumulative sum of these products that provides, upon completion of the (n-1) shifts, the bit-serial division result v/u.
Inventors
- 👤 Robert W. Anderson
- 👤 Ralph L. Gee
- 👤 Trung L. Nguyen
- 👤 Martin A. Hassner
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 13:10
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/724; G06F7/726; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
212 words
A bit-serial division method for computing the value v/u, where v and u each are n-bit vectors that are elements in a finite Galois field GF(2 n ) consisting of 2 n elements and wherein the n-bit components of each element in said field are the coordinates of such element in a canonical basis of said field, comprising the steps of: converting the vector u from the canonical basis to a dual basis, said vector u in said dual basis also comprising n bits ordered according to an index i that takes on values from 0 to (n-1); loading into a shift register in parallel all bits n of the converted vector u; converting the converted n-bit vector u from the dual basis back to canonical basis to produce a single bit output w O from a lookup table which generates bitwise the inverse of the n-bit vector u; shifting the bits in the shift register (n-1) times to generate successive additional single bit outputs w i with said lookup table; and then multiplying each bit w i by the vector v and a corresponding element c i in dual basis to generate a cumulative sum of these products that provides, upon completion of said (n-1) shifts, the bit-serial division result v/u.
Claim 2
Dependent Claim
212 words
A bit-serial division method for computing the value v/u, where v and u each are n-bit vectors that are elements in a finite Galois field GF(2 n ) consisting of 2 n elements and wherein the n-bit components of each element in said field are the coordinates of such element in a canonical basis of said field, comprising the steps of: converting the vector u from the canonical basis to a dual basis, said vector u in said dual basis also comprising n bits ordered according to an index i that takes on values from 0 to (n-1); loading into a shift register in parallel all bits n of the converted vector u; converting the converted n-bit vector u from the dual basis back to canonical basis to produce a single bit output w O from a lookup table which generates bitwise the inverse of the n-bit vector u; shifting the bits in the shift register (n-1) times to generate successive additional single bit outputs w i with said lookup table; and then multiplying each bit w i by the vector v and a corresponding element c i in dual basis to generate a cumulative sum of these products that provides, upon completion of said (n-1) shifts, the bit-serial division result v/u.
Claim 3
Dependent Claim
33 words
The method of claim 1, wherein the n-bit vector u in canonical basis consists of the consecutive powers of a finite field generator starting with the 0th power up to the (n-1)th power.
Claim 4
Dependent Claim
89 words
The method of claim 1, wherein the shift register is a linear feedback register, and including the steps of: providing a polynomial function of a single variable whose roots generate the finite field; wiring the shift register according to a preselected polynomial obtained from said polynomial function by substituting into said function the inverse of the variable; then normalizing by a power of the variable sufficiently large to eliminate all fractions; and using the shift register, computing and updating at each shift the values of converted n-bit vector u.
Claim 5
Dependent Claim
36 words
The method of claim 1, including the steps of: normalizing all 2 n elements in the finite field by multiplying said 2 n elements by a constant chosen to minimize the cost of implementation in hardware.
Claim 6
Dependent Claim
28 words
The method of claim 1, including the step of computing the lookup table by evaluating a trace function of all said 2 n elements in the finite field.
Claim 7
Dependent Claim
9 words
The method of claim 1, wherein n is 8.
Claim 8
Dependent Claim
41 words
The method of claim 1, wherein the finite field is generated by a primitive root a of an irreducible polynomial X 8 +X 4 'X 3 +X 2 +1 with GF(2) coefficients to provide an optimally hardware efficient bit-serial division circuit.
Claim 9
Dependent Claim
248 words
A bit-serial division method for computing the value v/u, where v and u each are n-bit vectors that are elements in a finite Galois field GF(2 2 ) consisting of 2 n elements and wherein the n-bit components of each element in said field are the coordinates of such element in a canonical basis of said field, comprising the steps of: converting the n-bit vector u from the canonical basis representation to an n-bit vector in an optimized dual basis chosen to minimize the cost of implementation in hardware, said vector u in said dual basis also comprising n bits ordered according to an index i that takes on values from 0 to (n-1); loading in parallel the n-bits of vector u into a linear feedback shift register that operates over the optimized dual basis; converting the n-bit vector u stored in the linear feedback shift register back to canonical basis to produce a single bit output w O from a lookup table which generates bitwise the inverse of the n-bit vector u; shifting the bits in the shift register (n-1) times to generate successive additional single bit outputs w i with the lookup table; and then multiplying each bit w i by the vector v and a respective element c i , where c i is the corresponding finite field element in the optimized dual basis, to produce a cumulative sum of these products that provides, upon completion of said (n-1) shifts, the bit-serial division result v/u.
Claim 10
Dependent Claim
248 words
A bit-serial division method for computing the value v/u, where v and u each are n-bit vectors that are elements in a finite Galois field GF(2 2 ) consisting of 2 n elements and wherein the n-bit components of each element in said field are the coordinates of such element in a canonical basis of said field, comprising the steps of: converting the n-bit vector u from the canonical basis representation to an n-bit vector in an optimized dual basis chosen to minimize the cost of implementation in hardware, said vector u in said dual basis also comprising n bits ordered according to an index i that takes on values from 0 to (n-1); loading in parallel the n-bits of vector u into a linear feedback shift register that operates over the optimized dual basis; converting the n-bit vector u stored in the linear feedback shift register back to canonical basis to produce a single bit output w O from a lookup table which generates bitwise the inverse of the n-bit vector u; shifting the bits in the shift register (n-1) times to generate successive additional single bit outputs w i with the lookup table; and then multiplying each bit w i by the vector v and a respective element c i , where c i is the corresponding finite field element in the optimized dual basis, to produce a cumulative sum of these products that provides, upon completion of said (n-1) shifts, the bit-serial division result v/u.
Claim 11
Dependent Claim
34 words
The method of claim 8, including during the second-mentioned converting step, normalizing all 2 n elements of said finite field to the optimized dual form by multiplying said all elements by a fixed element.
Claim 12
Dependent Claim
9 words
The method of claim 8, wherein n is 8.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-02-18 | 1994-08-20 | 1995-02-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-02-18 | 1998-08-20 | 1999-02-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-02-18 | 2002-08-20 | 2003-02-19 | $7700.00 | Window Closed / Lapsed |