Device and method for performing multiple modulus conversion using inverse modulus multiplication
US6697831B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Feb 28, 2002 |
| Grant date | Feb 24, 2004 |
| Priority date | — |
| Expiry date | Mar 1, 2022 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/729
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and device are provided that allow computation of multiple modulus conversion (MMC) outputs using little or no division operations. Instead of division operations, multiplication and logical shift operations are used to produce pseudo-quotients and pseudo-remainders, which may be corrected in a final step to produce correct MMC outputs. This allows for more efficient implementation, since division is typically less efficient than multiplication and logical shift. The method and device operate on MMC inputs that may be partitioned into sub-quotients of varying numbers of digits in any numbering system. The multiplication and logical shift operations are performed on each of the sub-quotients according to a procedure derived from long-division techniques.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.