|Publication number||US5493522 A|
|Application number||US 08/309,641|
|Publication date||Feb 20, 1996|
|Filing date||Sep 21, 1994|
|Priority date||Sep 21, 1994|
|Publication number||08309641, 309641, US 5493522 A, US 5493522A, US-A-5493522, US5493522 A, US5493522A|
|Original Assignee||Northrop Grumman Corporation|
|Export Citation||BiBTeX, EndNote, RefMan|
|Patent Citations (5), Referenced by (7), Classifications (7), Legal Events (5)|
|External Links: USPTO, USPTO Assignment, Espacenet|
1. Field of the Invention
This invention relates to circuitry and an electrical signal processing method for performing high-speed ripple-through modulo division operations.
2. Description of Related Art
Modulo division is used in digital computing devices such as arithmetic logic units (ALU's) and as part of address generators. The purpose of modulo division is to divide two X-bit digital input signals A and B and derive a single X-bit digital output signal Q in the form:
(B*Q) mod2x =A (1)
where mod2x indicates a modulo operation, which by definition is equivalent to an operation of the form:
B*Q=A+2x n (2)
where n is a whole number.
For a modulo 32 system, which uses a 5-bit input, the corresponding equations describing the modulo relationship between A, B, and Q are:
where A, B, and Q are between 0 and 31.
In order to simplify the notation used herein, an equal sign with a 32 under it (=) will hereinafter specify equivalence under modulo 32, and an equal sign without any notation under it will specify regular equivalence. In addition, M(32) denotes modulo-32 arithmetic. It is to be understood, however, that modulo 32 arithmetic, in which X=5, is to be taken as an illustrative example only, and that the principles discussed herein may easily be generalized to cover the case where X is any positive integer greater than 1, although the modulo arithmetic for X less than 5 is essentially trivial.
A wide variety of modulo division circuitry is available at present, but most such circuitry is limited in the speed at which modulo numbers A and B can be processed. This limitation is related to a property of modulo division which makes it impossible, using conventional methods, to multiply A by the inverse of B in order to obtain the quotient Q of A and B. While all odd numbers in the modulo system have defined inverses, no even number in the modulo system has a defined inverse. Thus, conventional modulo division circuitry relies upon iterative "long division" techniques involving multiple shift registers to perform successive multiply and accumulate operations, each of which must be separately clocked in order to coordinate operations, greatly reducing processing speed.
Despite the above-described theoretical obstacle to improving the speed of modulo division circuitry, it is nevertheless an objective of the invention to provide a modulo divider circuit of improved speed.
It is a further objective of the invention to provide a modulo divider circuit which avoids the need for iterative division techniques involving multiple clocked registers, the clocked registers being used only to store initial inputs and the final result.
It is a still further objective of the invention to provide a method of carrying out modulo division by using combinational logic circuitry to obtain an output signal which represents the modulo quotient of two modulo inputs A and B.
These and other objectives of the invention are accomplished by providing circuitry which creates an inverse modulo division operator MB defined as follows: ##EQU1## where n is defined as the number of twos by which B is integrally divisible, Under this definition of n, if B is odd, then n is zero. If B is even, on the other hand, then n is an element of the set (1, 2, 3, 4), and depends on the value of B. With n defined in this manner, the inverse modulo division operator MB is simply the inverse of B if B is odd. If B is even, then MB is a number between 0 and 31 which fits the definition provided by equation 5.
Application of the modulo division operator MB is accomplished by the inventive modulo division circuitry as follows: Multiplication of both sides of equation 1 by the operator MB yields ##EQU2## Therefore, by equation 5 and the commutative property of modulo division, ##EQU3##
In other words, the invention accomplishes modulo division by processing the electrical input signals to obtain electrical signals representative of the product of a modulo division operator MB and one of the input signals A, and then divides the result by 2n, the latter operation being effected by shifting the 5-bit digital signal representing the product AMB to the right n times, and by dropping the rightmost bit after each shift.
By generating and applying the modulo division operator MB as described above, only six functional electrical circuit elements are needed to carry out the invention. The six functional elements are:
1. Input registers for receiving modulo numbers A and B.
2. A look-up table, preferably in the form of a ROM, for generating MB by mapping B to MB.
3. A masker circuit which generates a value of 2n that corresponds to the value of B.
4. A multiplier, preferably in the form of a modulo-32 ripple-through multiplier, for multiplying A and MB.
5. A shifter circuit which utilizes the value of 2n to shift the product AMB and thereby obtain Q, preferably by performing a vector multiply that forms a combinational logical shift on AMB.
6. An output register.
Each of these functional electrical circuit elements will be described in detail below.
FIG. 1 is a block diagram of the functional layout of a fast modulo divider circuit according to a preferred embodiment of the invention.
FIG. 2 is a table of look-up values for the ROM shown in FIG. 1.
FIG. 3 is a schematic diagram of a masker circuit for use in the divider of FIG. 1.
FIG. 4 is a schematic diagram of a multiplier circuit for use in the divider of FIG. 1.
FIG. 5 is a schematic diagram of a shifter circuit for use in the divider of FIG. 1.
FIG. 6 is a table listing the critical path and worst-case delay time conditions for performing a modulo division operation on a digital input signal using the circuit of FIG. 1.
FIG. 7 is a schematic diagram showing the manner in which the circuits of FIGS. 3-5 are connected together to obtain a divider circuit which corresponds to the divider of FIGS. 1 and 2.
FIG. 1 shows a modulo divider 1 constructed in accordance with the principles of a preferred embodiment of the invention. Divider 1 accepts two five-bit digital electronic input signals A and B, and derives one five-bit digital electronic output signal Q, defined by the relationship ##EQU4##
Because B has no inverse if B is even, an inverse modulo division operator MB is instead defined as follows: ##EQU5## where, if B is odd, n=0, i.e., MB is the inverse of B, and where n is an element of the set (1, 2, 3, 4) if B is even.
Unlike the ordinary inverse of B, the inverse modulo division operator MB can easily be shown to exist for all possible values of B in the modulo system. Since MB exists for all B, then: ##EQU6##
By an associative property of modulo arithmetic, ##EQU7## and, by equation 10, ##EQU8## Thus, the preferred modulo divider circuit derives Q by processing the electrical input signals to effect a multiplication of A by MB, and subsequently to effect a division of AMB by 2n, n being the number of 2's by which B is integrally divisible.
As illustrated in FIG. 1, the preferred divider 1 is composed of six functional blocks, including a first functional block made up of input registers 2 and 3 to which 5-bit signals representing modulo numbers A and B are input, a look-up table in the form of a ROM 4 for mapping B to MB, a masker circuit 5 which generates a value of 2n that corresponds to a given B, a modulo-32 ripple-through multiplier 6 for multiplying A and MB, a shifter circuit 7 which uses the value of 2n to do a vector multiply that accomplishes a combinational logical shift on the product of A and MB, and an output register 8.
Registers 2 and 3 are conventional registers which may take a variety of forms, including the arrangement shown in FIG. 7, in which registers 2 and 3 are each made up of five individual latches 9-13 and 14-18 for holding individual bits received in serial fashion via input terminals 19 and 20, and for outputting A and B in parallel on the rising edge of a clock pulse input via terminal 21.
ROM 4 is encoded with the data listed in FIG. 2. The value of B stored in register 3 is read by ROM 4, which functions as a look-up table to output the values for MB as defined in equation (10) above. As will be described in more detail below, the value of MB depends on the position of the least significant non-zero bit in B, since the first n-1 bits of B must be zero in order for B to be divisible by 2n. However, n is derived by the shifter circuit 7 and is not determined by the look-up table. The values for n are included in FIG. 2 for reference only.
The values for MB which are stored in ROM 4 are determined as follows: In order to satisfy equation 10 under the rules of modulo arithmetic, MB must be equal to (2n +32 k)/B, where k is an integer chosen such that MB is also an integer, and n is the number of 2's by which B is integrally divisible. In FIG. 2, k was selected to be the smallest value which results in MB being an integer, but higher values of k which also permit MB to be an integer could also be used.
Although the look-up table is implemented in the illustrative example by ROM 4, it will be appreciated by those skilled in the art that the look-up or mapping function could also be accomplished by a straight random logic or programmable array logic (PAL) circuit designed to map B onto MB. While the above discussion implies that MB could also be calculated from n and B, use of a look-up table is much faster. The ROM in question is conventional, except for the data stored therein, and therefore will not be discussed in further detail.
Masker circuit 5, as shown in FIG. 3, uses a set of four inverters 22-25, one buffer 26, and four AND gates 27-30, one for each output bit, to select the least significant non-zero bit, in order to represent the number of times two divides integrally into B, as shown in FIG. 3. The individual bits of the modulo number B are labeled from B0 to B4 using conventional notation, where a high or logical 1 electrical signal at bit location B0 indicates the number 1 (n=0), a high signal at bit location B1 indicates the number 2 (n=1), a high signal at bit location B2 indicates the number 4 (n=2), and so forth. For m=0 to 4, location Bm therefore represents 2m, and B equals B4+B3+B2+B1+B0. The output X has the same form as the input, but the bits are numbered from X0 to X4.
The masker circuit is arranged such that a zero bit at any of the input locations B0 to B4 zeroes the corresponding output location, but produces a high or logical 1 signal at all higher order locations. A "1" bit at location Bm, on the other hand, produces a logical 1 at the input to the AND gate of the corresponding output bit Xm, and is inverted to produce a zero at all higher order locations (i.e., at bits Xh, where h>m). The result is that the inputs to the AND gate corresponding to the first logical 1 are all logical 1's, while all other AND gates are zeroed either directly by the input of the AND gate corresponding to the zero bit, or by the corresponding inverter connected to the first logical 1 bit, which zeroes all higher order AND gates. In other words, masker 5 masks off all bits not in the nth position, where n is the position of the least significant non-zero bit.
More generally, given that Bm represents the mth bit position in B, and Xm represents the mth bit position in the output X, X can be mathematically expressed as: ##EQU9##
Multiplier 6 is a modified ripple-through multiplier, as shown in detail in FIG. 4. Multiplier 6 outputs a five bit digital signal representing the product of MB and A by using combinational logic, instead of multiplying by successive shift and adds with several registers. Each output, Y0 -Y4, and each carry, is generated based on the following formulas: ##EQU10## where Cn-m is the carry from the nth stage to the mth stage.
The multiplier implements these functions directly by parallelly processing the respective Y bits in a plurality of stages. AND gates 31-45 output a logical 1-bit if the corresponding A and MB bits are one, but they output a zero bit if either of the corresponding A and MB bits is zero.
A carry occurs if more than one term is equal to 1 as determined by AND gates 46, and 63-65, NAND gates 47-62, and inverters 66-76. The exclusive OR gates 77-86 pass a one bit if an odd number of its inputs are equal to 1, and thus the exclusive OR gates serve to generate the sums of the individual products in equation 15. Because the multiplier performs modulo 32 arithmetic, all sums above the fifth bit, and all carries to sums above the fifth bit, may be disregarded, which reduces the size of the multiplier, and makes the output the modulo 32 result of the multiplication. In other words, the last stage of the multiplier does not require any carry gates.
The value for n generated by masker 5 (actually 2n), and the signal representative of the product of MB and A which is output by multiplier 6, are input to shifter 7, as shown in FIG. 5. The purpose of shifter 7 is to effectively divide MB A by 2n. Shifter 7 performs a vector-shift and vector-vector multiply simultaneously to accomplish this function. Essentially, shifter 7 takes the value of 2n and uses it to shift the signal output by multiplier 6 n times towards the rightmost or least significant bit. The R inputs of shifter 7 correspond to the Y outputs of multiplier 6. The K inputs of shifter 7 correspond to the X outputs of masker 5. For purposes of the shift operation, the two five-bit numbers are treated as five-vectors. If a logical shift of R to the right n times of R is denoted by R(n), then each output, Q0 -Q4 is described as follows:
QN =K·R(n) (16)
Since K, which is the masked output of masker circuit 5, has only one bit position that is non-zero, namely the nth, the result of the scalar or dot product of K and R will be the nth bit position in R(n). By performing the dot product five times, each time using R shifted one more place to the right, the five elements in Q are generated. In other words, the first stage 90 of the shifter calculates the dot product of K and R to give the QO bit. The next stage 91 calculates the dot product of K and R shifted one bit to the right with the right-most bit dropped to give Q1, with successive stages 92, 93, and 94 also calculating the dot product of K and R, R being shifted to the right by one bit for each stage. It will be noted that each time a bit is dropped, one less NAND gate is needed.
Mathematically, the operation of stages 90-94, carried out by NAND gates 95-108 which output a 1 bit unless both corresponding R and K bits are 1, and NAND gates 109-112 which therefore output a 1 bit unless all input bits to the stage are one, is expressed by De Morgan's law as follows: ##EQU11## The results from shifter 7 are stored in output register 8 during the next rising edge of the clock pulse after the falling edge which initiates the output from registers 2 and 3.
FIG. 6 lists the critical path through the exemplary circuit implementation shown in FIG. 7. Delay times are given for worst-case conditions, with an output capacitance of 0.26 pF. Delay times for the ROM are based on a combinational circuit similar to a PAL circuit, but will vary based on actual implementation. Larger output capacitances, or the use of I/O pads, would significantly increase delay times.
In practice, as noted above, the input registers 1 and 2 may be in the form of parallelly connected one-bit latches, as may the output register. The input registers are clocked on the rising edge of a clock pulse and the output latches are clocked on the trailing edge of the clock pulse. Functional blocks 4-7 are each in the form of discrete chips or integrated circuits wired together as indicated.
The illustrated device has an approximate power dissipation of 0.29 mW/Mhz, and an equivalent gate count of 333, not including values for the ROM. Both the gate count and AC power dissipation may be varied based on the actual implementation of the ROM. All of these calculated values are based on data given in the VGT Portable CMOS Library by VLSI Technology, with λ=1.
As noted at various places above, the illustrated embodiment is preferred, but is not intended to be limiting in any way. The specific circuits shown for the various functional blocks may be modified by those skilled in the art to perform the same processing functions in a different manner. In addition, the principles of the invention are applicable not only to 5-bit modulo 32 designs, but also to modulo16, modulo64 and any other modulo system. Consequently, it is intended that the scope of the invention be defined solely by the claims appended hereto.
|Cited Patent||Filing date||Publication date||Applicant||Title|
|US4567568 *||Mar 10, 1983||Jan 28, 1986||Tokyo Shibaura Denki Kabushiki Kaisha||Apparatus for dividing the elements of a Galois field|
|US4574361 *||Mar 10, 1983||Mar 4, 1986||Tokyo Shibaura Denki Kabushiki Kaisha||Apparatus for dividing the elements of a Galois field|
|US4975867 *||Jun 26, 1987||Dec 4, 1990||Digital Equipment Corporation||Apparatus for dividing elements of a Galois Field GF (2QM)|
|US4994995 *||Mar 14, 1990||Feb 19, 1991||International Business Machines Corporation||Bit-serial division method and apparatus|
|US5379243 *||Aug 31, 1992||Jan 3, 1995||Comstream Corporation||Method and apparatus for performing finite field division|
|Citing Patent||Filing date||Publication date||Applicant||Title|
|US5815655 *||Feb 28, 1997||Sep 29, 1998||Fujitsu Limited||Device for generating error path list and method of extracting the worst paths|
|US6256656 *||Dec 28, 1998||Jul 3, 2001||Silicon Graphics, Inc.||Apparatus and method for extending computational precision of a computer system having a modular arithmetic processing unit|
|US7061975 *||Dec 18, 2000||Jun 13, 2006||Seiko Epson Corporation||Noncyclic digital filter and radio reception apparatus comprising the filter|
|US7849125||Jul 7, 2006||Dec 7, 2010||Via Telecom Co., Ltd||Efficient computation of the modulo operation based on divisor (2n-1)|
|US20020159515 *||Dec 18, 2000||Oct 31, 2002||Nobuhiko Kenmochi||Noncyclic digital filter and radio reception apparatus comprising the filter|
|US20050038845 *||Aug 12, 2004||Feb 17, 2005||Infineon Technologies Ag||Device and method for calculating a result of a division|
|US20060242220 *||Apr 20, 2005||Oct 26, 2006||Texas Instruments, Inc.||Hardware divider|
|Cooperative Classification||G06F7/726, G06F7/727, G06F7/721|
|European Classification||G06F7/72F3, G06F7/72H|
|Sep 21, 1994||AS||Assignment|
Owner name: GRUMMAN AEROSPACE CORPORATION, NEW YORK
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:ROSENBERG, JONATHAN;REEL/FRAME:007151/0446
Effective date: 19940912
|Aug 19, 1999||FPAY||Fee payment|
Year of fee payment: 4
|Sep 10, 2003||REMI||Maintenance fee reminder mailed|
|Feb 20, 2004||LAPS||Lapse for failure to pay maintenance fees|
|Apr 20, 2004||FP||Expired due to failure to pay maintenance fee|
Effective date: 20040220