Bit-serial division method and apparatus
US4994995A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Mar 14, 1990 |
| Grant date | Feb 19, 1991 |
| Priority date | — |
| Expiry date | Mar 14, 2010 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH03M13/15
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
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.sup.n) consisting of 2.sup.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.sub.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.sub.i with said lookup table. Then each bit w.sub.i is multiplied by the vector v and a corresponding element c.sub.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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.