Patent US5493522A successfully refreshed from Google Patents.
US5493522A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fast arithmetic modulo divider
Assignee: Northrop Grumman Corp
•
Filing: 1994-09-21
•
Granted: 1996-02-20
•
Expires: 2014-09-21
Abstract
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 B which is the inverse of B when B is odd, but which is equal to 2 n , n=1, 2, 3, 4, when B is even. Combinational logic is used to calculate the product M B A, which is then divided by 2 n , or sifted n places, to obtain Q.
Inventors
- 👤 Jonathan Rosenberg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 18:46
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/724; G06F7/726; G06F7/727; G06F7/721
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
210 words
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 x -1; look-up table means for mapping B onto an electrical signal representing a modulo division operator M B which, when multiplied by B, is equal to 2 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 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 B and A to obtain an electrical signal representative of the product of M B and A. shifter means for physically shifting said electrical signal representative of the product of M B and A by n places in order to divide M B A by 2 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.
Claim 2
Dependent Claim
210 words
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 x -1; look-up table means for mapping B onto an electrical signal representing a modulo division operator M B which, when multiplied by B, is equal to 2 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 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 B and A to obtain an electrical signal representative of the product of M B and A. shifter means for physically shifting said electrical signal representative of the product of M B and A by n places in order to divide M B A by 2 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.
Claim 3
Dependent Claim
19 words
A modulo divider circuit as claimed in claim 1, wherein said input register means comprises two X bit registers.
Claim 4
Dependent Claim
22 words
A modulo divider circuit as claimed in claim 2, where said X bit registers are composed of X individual one bit latches.
Claim 5
Dependent Claim
41 words
A modulo divider as claimed in claim 3, wherein outputs of said latches are simultaneously clocked on one edge of a clock pulse and an input to said output register means is clocked on a second edge of said clock pulse.
Claim 6
Dependent Claim
26 words
A divider circuit as claimed in claim 2, wherein said two X-bit registers are 5-bit registers and said modulo number system is a modulo 32 system.
Claim 7
Dependent Claim
17 words
A modulo divider circuit as claimed in claim 1, wherein said look-up table means comprises a ROM.
Claim 8
Dependent Claim
67 words
A modulo divider circuit as claimed in claim 1, wherein said look-up table means includes means for mapping B onto M B , M B being defined as a modulo number which equals (2 n +2 x k)/B, in order to obtain the electrical signal representative of M B , and wherein k is defined as any whole number which results in M B being an integer.
Claim 9
Dependent Claim
42 words
A modulo divider circuit as claimed in claim 7, wherein said means for mapping comprises means for storing values of said modulo number equal to 2 n +32(k), where k is the smallest number which results in M B being an integer.
Claim 10
Dependent Claim
91 words
A modulo divider circuit as claimed in claim 1, wherein said masker means comprises five input terminals, B0-B4, and five output terminals X0-X4, and wherein each input terminal B m , where m is a whole number less than 5, is directly connected to an input of an AND gate whose output is the corresponding output terminal X m , and wherein each input B m is connected through an inverter to inputs of AND gates which are connected to all outputs X h , where h is greater than m.
Claim 11
Dependent Claim
158 words
A modulo divider circuit as claimed in claim 1, wherein said multiplier means comprises a ripple-through multiplier which includes one stage for each of the X-bits which make up the electrical signals representing A and M B , wherein said multiplier comprises first multiplier stage means for multiplying a first bit of A by a first bit of M B to obtain a first bit of the product Y0, second multiplier stage means for multiplying the first bit of M B by a second bit of A and multiplying a second bit of M B by the first bit of A, and summing means for summing the bit representing M B 0 A1 and M B 1 A0 to obtain a second bit of the product Y1, each stage including means for generating a carry bit connected to inputs to another stage, wherein an Xth stage of said multiplier does not include means for generating the carry bit.
Claim 12
Dependent Claim
30 words
A modulo divider circuit as claimed in claim 10, wherein said first and second multiplier stage means comprises AND gates and said summing means comprises exclusive OR gates and inverters.
Claim 13
Dependent Claim
150 words
A modulo divider circuit as claimed in claim 1, wherein said shifter means comprises means for inputting an X-bit output of said multiplier means, said X-bit output of said multiplier means including bits R0-R, and means for inputting an X-bit output of said masker means, individual bits of said X-bit output of said masker means being consecutively numbered from K0 to K; means for generating an electrical signal representative of the scalar product of vectors (R0, R1, R2, R3, R4) and (K0, K1, K2, K3, K4), said scalar product obtaining means comprising a first stage of said shifter means; and means for obtaining scalar products of (R0, R1, R2, R3, R4) and (Km-1, Km-2, Km-3, and Km-4), where m is the number of a stage of said shifter means and is less than or equal to 4, and where if Km-m is less than zero, then the bit is dropped.
Claim 14
Dependent Claim
92 words
A modulo divider circuit as claimed in claim 12, wherein each said stage comprises a plurality of NAND gates, each NAND gate having inputs connected to receive a respective one of said bits R0 to R and K0 to K, and a plurality of X second NAND gates, said second NAND gates each having an input connected to an output of each of a respective one of a respective one of said first NAND gates, said outputs of said second NAND gates forming individual bits of the electrical signal representative of Q.
Claim 15
Independent Claim
198 words
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 x -1; mapping B onto an electrical signal representing a modulo division operator M B which, when multiplied by B, is equal to 2 n , where n is the number of two's by which B is integrally divisible; generating an electrical signal representing 2 n by outputting an X bit signal indicative of the least significant non-zero bit present in B; processing the electrical signals representing M B and A to obtain an electrical signal representative of the product of M B and A; processing said electrical signals representative of 2 n and the product of M 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 B /2 n ; and making available for output an electrical signal representative of Q.
Claim 16
Independent Claim
198 words
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 x -1; mapping B onto an electrical signal representing a modulo division operator M B which, when multiplied by B, is equal to 2 n , where n is the number of two's by which B is integrally divisible; generating an electrical signal representing 2 n by outputting an X bit signal indicative of the least significant non-zero bit present in B; processing the electrical signals representing M B and A to obtain an electrical signal representative of the product of M B and A; processing said electrical signals representative of 2 n and the product of M 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 B /2 n ; and making available for output an electrical signal representative of Q.
Claim 17
Dependent Claim
50 words
A method as claimed in claim 14, wherein said step of mapping comprises the step of X mapping B onto M B , wherein M B is a modulo number which equals 2 n +32(k), and wherein k is any whole number which results in M B being an integer.
Claim 18
Dependent Claim
27 words
A method as claimed in claim 14, further comprising the step of selecting k to be the smallest number which results in M B being an integer.
Claim 19
Dependent Claim
35 words
A method as claimed in claim 14, wherein said step of generating 2 n comprises the step of generating an X-bit modulo number by zeroing all bits of B except the least significant nonzero bit.
Claim 20
Dependent Claim
108 words
A method as claimed in claim 14, wherein said step of processing the electrical signals representing M B and A comprises the step of generating a bit Y0 equal to the first bit of A multiplied by the first bit of M, and a bit Y1 equal to the first bit of M multiplied by the second bit of A and the second bit of M multiplied by the first bit of A, using combinational logic stages, each stage including a carry bit generating stage connected to inputs of an adjacent stage, wherein a last stage of said multiplier does not include means for generating the carry bit.
Claim 21
Dependent Claim
48 words
A method as claimed in claim 18, wherein each individual product of respective bits is obtained by ANDing the values of the bits together to obtain an intermediate bit, and by passing each intermediate bit through an exclusive OR gate arrangement to respectively generate bits Y0 and Y1.
Claim 22
Dependent Claim
83 words
A method as claimed in claim 14, wherein said step of processing said electrical signals representative of 2 n and the product of M B and A comprises the steps of using combination logic circuit elements to generate the scalar product of vectors formed by individual bits of the X-bit electrical signal representing the product of A and M B , and the X-bit electrical signal representing 2 n , and physical shifting M B by one bit for each vector product generated.
Claim 23
Dependent Claim
26 words
A method as claimed in claim 14, further comprising the step of transferring Q to an output register on the falling edge of said clock pulse.
Claim 24
Dependent Claim
177 words
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 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 B which, when M B is multiplied by B, is equal to 2 n , where n is the number of twos by which B is integrally divisible; multiplication means for processing said electrical signals A and M B to obtain an electrical signal representative of the product M B A of M B and A; and shifter means for processing the electrical signal representative of the product M B A to obtain an electrical signal representative of a number Q which is the result of dividing M B A by 2 n .
Claim 25
Dependent Claim
177 words
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 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 B which, when M B is multiplied by B, is equal to 2 n , where n is the number of twos by which B is integrally divisible; multiplication means for processing said electrical signals A and M B to obtain an electrical signal representative of the product M B A of M B and A; and shifter means for processing the electrical signal representative of the product M B A to obtain an electrical signal representative of a number Q which is the result of dividing M B A by 2 n .
Claim 26
Dependent Claim
19 words
A modulo divider circuit as claimed in claim 22, wherein said input register means comprises two X bit registers.
Claim 27
Dependent Claim
22 words
A modulo divider circuit as claimed in claim 23, where said X bit registers are composed of X individual one bit latches.
Claim 28
Dependent Claim
53 words
A modulo divider as claimed in claim 24, wherein outputs of said latches are simultaneously clocked on one edge of a clock pulse and an input to an output register means for making available for output said electrical signal representative of number Q is clocked on a second edge of said clock pulse.
Claim 29
Dependent Claim
26 words
A divider circuit as claimed in claim 23, wherein said two X-bit registers are 5-bit registers and said modulo number system is a modulo 32 system.
Claim 30
Dependent Claim
17 words
A modulo divider circuit as claimed in claim 22, wherein said look-up table means comprises a ROM.
Claim 31
Dependent Claim
67 words
A modulo divider circuit as claimed in claim 22, wherein said look-up table means includes means for mapping B onto M B , M B being defined as a modulo number which equals (2 n +2 x k)/B, in order to obtain the electrical signal representative of M B , and wherein k is defined as any whole number which results in M B being an integer.
Claim 32
Dependent Claim
42 words
A modulo divider circuit as claimed in claim 28, wherein said means for mapping comprises means for storing values of said modulo number equal to 2 n +32(k), where k is the smallest number which results in M B being an integer.
Claim 33
Dependent Claim
158 words
A modulo divider circuit as claimed in claim 22, wherein said multiplier means comprises a ripple-through multiplier which includes one stage for each of the X-bits which make up the electrical signals representing A and M B , wherein said multiplier comprises first multiplier stage means for multiplying a first bit of A by a first bit of M B to obtain a first bit of the product Y0, second multiplier stage means for multiplying the first bit of M B by a second bit of A and multiplying a second bit of M B by the first bit of A, and summing means for summing the bit representing M B 0 A1 and M B 1 A0 to obtain a second bit of the product Y1, each stage including means for generating a carry bit connected to inputs to another stage, wherein an Xth stage of said multiplier does not include means for generating the carry bit.
Claim 34
Dependent Claim
28 words
A modulo divider circuit as claimed in claim 30, wherein said first and second multiplier stage means comprises AND gates and said summing means comprises exclusive OR gates.
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) | 1999-02-19 | 1999-08-21 | 2000-02-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-02-19 | 2003-08-21 | 2004-02-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-02-19 | 2007-08-21 | 2008-02-20 | $7700.00 | Window Closed / Lapsed |