Fast arithmetic modulo divider
AssigneeNorthrop Grumman Corporation
InventorJonathan Rosenberg
Life of this patent
Estimating the term…
Abstract
A circuit and method for carrying out high-speed ripple-through modulo division includes input registers for inputting two modulo 32 numbers A and B. The output of the circuit is a modulo 32 number Q, where A, B, and Q are related by the equation B*Q mod 32=A. The circuit generates a modulo division operator M.sub.B which is the inverse of B when B is odd, but which is equal to 2.sup.n, n=1, 2, 3, 4, when B is even. Combinational logic is used to calculate the product M.sub.B A, which is then divided by 2.sup.n, or sifted n places, to obtain Q.
Claims31
A fast arithmetic modulo divider circuit, comprising:
- input register means for receiving two input electrical signals representative of numbers A and B, each signal made up of X digital bits, where X is a whole number greater than 1 and A and B are whole numbers in a modulo system, A and B each having values between 0 and 2.sup.x -1;
- look-up table means for mapping B onto an electrical signal representing a modulo division operator M.sub.B which, when multiplied by B, is equal to 2.sup.n, where n is the number of two's by which B is integrally divisible;
- masker means for generating an electrical signal representative of 2.sup.n by outputting an X-bit signal indicative of the least significant non-zero bit present in B;
- multiplication means for processing the electrical signals representing M.sub.B and A to obtain an electrical signal representative of the product of M.sub.B and A.
- shifter means for physically shifting said electrical signal representative of the product of M.sub.B and A by n places in order to divide M.sub.B A by 2.sup.n and obtain an electrical signal Q made up of X digital bits;
- and
- output register means for making available for output said electrical signal Q.
A method of processing digital electrical signals, comprising the steps of:
- receiving two input electrical signals representative of binary numbers A and B, each made up of X digital bits, where X is a whole number greater than 1 and A and B are whole numbers in a modulo system, A and B each having values between 0 and 2.sup.x -1;
- mapping B onto an electrical signal representing a modulo division operator M.sub.B which, when multiplied by B, is equal to 2.sup.n, where n is the number of two's by which B is integrally divisible;
- generating an electrical signal representing 2.sup.n by outputting an X bit signal indicative of the least significant non-zero bit present in B;
- processing the electrical signals representing M.sub.B and A to obtain an electrical signal representative of the product of M.sub.B and A;
- processing said electrical signals representative of 2.sup.n and the product of M.sub.B and A in order to obtain an electrical signal made up of X digital bits and representative of a number Q equal to AM.sub.B /2.sup.n ;
- and
- making available for output an electrical signal representative of Q.
A fast modulo divider circuit, comprising:
- input register means for receiving two input electrical signals representative of numbers A and B, each signal made up of X digital bits, where X is a whole number greater than 1 and A and B are whole numbers in a modulo system, A and B each having values between 0 and 2.sup.x -1;
- look-up table means for deriving from the electrical signal representative of the number B and electrical signal representative of a number M.sub.B which, when M.sub.B is multiplied by B, is equal to 2.sup.n, where n is the number of twos by which B is integrally divisible;
- multiplication means for processing said electrical signals A and M.sub.B to obtain an electrical signal representative of the product M.sub.B A of M.sub.B and A;
- and
- shifter means for processing the electrical signal representative of the product M.sub.B A to obtain an electrical signal representative of a number Q which is the result of dividing M.sub.B A by 2.sup.n.
Dependencies are inferred from the claim text.