Circuit and method for fast squaring

A circuit for squaring an n-bit value includes a partial product bit generator which logically AND's a bit of the n-bit value having a weight 2k (k is an integer) with the same bit of weight 2k to generate a partial product bit of weight 22k. Another partial product bit generator receives and logically AND's a bit of the n-bit value of weight 2k and a bit of weight 2m (m is an integers) to generate a partial product bit of weight 2(k+m+1). The second partial product bit generator may be the only partial product bit generator in the squaring circuit to logically AND the bit of weight 2m and the bit of weight 2k. The circuit may also include other partial product bit generators. However, the required number of partial product bit generators is significantly reduced by about &frac12; compared to the conventional squaring circuit. The associated Wallace tree structure is simplified and made smaller because of the reduction in partial product bits. Therefore, a faster and smaller circuit for squaring is provided.

BACKGROUND OF THE INVENTION

It is often necessary to compute the square of an n-bit (e.g., a 12-bit) value.

One conventional squaring method uses regular school book multiplication in which a 12-bit value is both the multiplier and the multiplicand as in the following example.

A partial product bit generator mk such as an AND gate mk is used to generate each partial product bit mk. One input terminal of each AND gate mk receives multiplicand bit k while the other input terminal receives multiplier bit m.

A circuit that implements this method requires a minimum of n 2 (e.g., 144) AND gates to square an n-bit value. Additionally, in a Wallace tree of 3:2 carry save adders, each column may require up to n 2 (e.g., 10) carry save adders. If each column has the same number of carry save adders, a total of 2n (e.g., 24) columns may require up to (2n) (n 2) 2n 2 4n (e.g., 240) carry save adders. These AND gates and carry save adders occupy significant space on a die.

It is desirable to reduce the number of partial product bit generators and carry save adders required to square. By so doing, the partial product bit generator array and accompanying Wallace tree are made smaller and faster than in the conventional squaring circuit.

SUMMARY OF THE INVENTION

A circuit for squaring an n-bit value in accordance with the present invention is provided. The circuit includes a partial product bit generator which logically AND's a bit of the n-bit value of weight 2 k (k is an integer) with the same bit of weight 2 k to provide a partial product bit of weight 2 2k on an output terminal. Another partial product bit generator has at least two input terminals configured to receive a bit of the n-bit value of weight 2 k and a bit of weight 2 m (m is an integers). The second partial product bit generator logically AND's these bits and generates a partial product bit of weight 2 (k m 1) . In one embodiment, the second partial product bit generator is the only partial product bit generator in the squaring circuit to logically AND the bit of weight 2 m and the bit of weight 2 k .

A method in accordance with the present invention is also provided by generating a first partial product bit of weight 2 2k from a bit of weight 2 k in a first partial product bit generator. A bit of weight 2 k is logically AND'ed with a bit of weight 2 m to generate a second partial product bit of weight 2 (k m 1) in a second partial product bit generator. Another method includes providing the first and second partial product bit generators described above.

The circuit may also include other partial product bit generators. However, the required number of partial product bit generators is significantly reduced by about compared to the conventional squaring circuits. For example, is squaring a 12-bit value, the number of partial product bit generators needed is reduced from 144 to 78, and even to 66 in one embodiment. The associated Wallace tree structure is simplified and made smaller because of this reduction in partial product bits. Therefore, a faster and smaller circuit for squaring is provided.

The present invention and its advantages and features will be more fully understood in light of the following detailed description and the claims.

DESCRIPTION OF THE INVENTION

Throughout the figures and description, like reference symbols indicate like elements unless otherwise noted.

Partial product bits in the conventional school book method of squaring are mirrored . For example, in the following multiplication, the italicized partial product bits are vertically mirrored about the bolded partial product bits.

Squaring may also be performed by deleting all of the lower bits ( right bits ) and by shifting the upper bits 1 bit left as in the following example.

In the above method, the number of product bits is reduced from n 2 (e.g., 144) in the conventional method to n(n 1)/2 (e.g., 78), a reduction of almost 50%. Furthermore, the maximum number of partial product bits per column is (n/2) 1 truncated (e.g., 7 if n equals 12). Therefore, the maximum number of carry save adders required for a column is reduced from n 2 (e.g., 10) to (n/2) 1 truncated (e.g., 5).

FIG. 1 shows a block diagram of a circuit that accomplishes the above described squaring. In FIG. 1 , two 12-bit registers 110 and 120 are each configured to store the same 12-bit value y b 16 : 0 to be squared. Each bit y q of the 12-bit value y b 16 : 0 has a weight 2 q , where for q is the set of integers from 0 to b 16 . Register 110 has lead lines corresponding to each bit y b 16 : 0 as does register 120 . In one embodiment, only one register 110 is used to provide bits y b 16 : 0 . In another embodiment, bits y b 16 : 0 are provided by a circuit (not shown) other than a register.

In response to a signal SQUARE on line 111 , signals representing each bit of value y b 16 : 0 are provided to a partial product bit generator array 130 ( array 130 ). Array 130 generates partial product bits and provides the partial product bits to a respective one of column adders CA 0 to CA 23 that corresponds to the weight of the partial product bit. The column adders CA 0 to CA 23 may provide the resulting square in redundant form (i.e., a carry and sum bit for each bit place), in which case the result is provided to a carry propagate adder 140 .

FIG. 2 is a detailed gate level diagram of array 130 which may be, for example, an array of AND gates. Each AND gate mk (e.g., AND gate 1 b 16 in FIG. 2 ) has two numbers m and k (e.g., 1 and b 16 ) associated with its input terminals. The left number m (e.g., 1 for AND gate 1 b 16 ) indicates that one input terminal is configured to receive bit y m (e.g., bit y 1 ) from registers 110 or 120 . The right number k (e.g., b 16 for AND gate 1 b 16 ) indicates that the other input terminal is configured to receive bit y k (e.g., y b 16 ) from registers 110 or 120 . Each AND gate mk receives bits y m and y k on its input terminal and provides bit mk on its output terminal. For example, AND gate 1 b 16 receives bits y 1 and y b 16 and generates partial product bit 1 b 16 . Likewise, AND gate 00 receives bit y 0 and provides partial product bit 00 . The other AND gates and partial product bits are not labeled in FIG. 2 for clarity.

The column adders of FIG. 1 receive and add the partial product bits mk according to the following Table 1.

As shown in Table 1, the maximum number of partial product bits received by any column adder is 7 received by column adder CA 12 . The maximum required number of 3:2 carry save adders needed to reduce the 7 partial product bits to a sum and carry value is only 5. Therefore, the above describes a circuit and method for squaring which reduces the number of required partial product bit generators by almost 50% compared to the prior art. This simplifies the adder tree and reduces the area of the adder tree needed to add the reduced number of partial product bits. Therefore, the above describes a squaring circuit that is faster and smaller than in conventional squaring.

The maximum number of partial product bits per column may be reduced from (n/2) 1 truncated (e.g., 7) to (n/2) truncated (e.g., 6) as is described hereafter. The reduction is accomplished by shifting one partial product bit from the column with the most partial product bits (e.g., column 12 ) to its more significant neighbor (e.g., column 13 ). The reduction is described with reference to FIG. 3 A and FIG. 3 B.

FIG. 3A shows a portion 300 of array 130 that includes only AND gates 56 and 66 . In portion 300 , column 12 generates two partial product bits 56 and 66 , while column 13 generates none. In FIG. 3B , portion 300 is replaced with a portion 310 in which column 12 generates only one partial product bit p , while column 13 also generates a partial product bit p . Although the total number of partial product bits does not change by replacing portion 300 with 310 , the number of partial product bits generated by column 12 of the partial product bit generator array 130 is reduced from 7 to 6. The number of partial product bits generated by column 13 is increased from 5 to only 6. The maximum number of partial product bits generated by any one column of array 130 is thus reduced by 1 to 6. Thus, the maximum number of 3:2 carry save adders required per column is reduced to 4 for squaring a 12-bit value.

The following truth table (Table 2) shows the relationship between portion 310 input bits y 5 and y 6 and output partial product bits p and p .

TABLE 2 Input Output Bits bit Bits y 5 y 6 56 p p x 0 0 0 0 0 1 0 0 1 1 1 1 1 0 X means that the output bits p and p are not dependent on bit y 5 if bit y 6 is 0. Bit p has a 1 value only if bit y 5 has a 0 value and bit y 6 has a 1 value. Bit p has a 1 value only if both of bits y 5 and y 6 have a 1 value.

FIG. 3B shows a circuit (portion 310 ) that implements truth Table 2. An AND gate 315 logically AND's bits y 5 and y 6 to generate bit 56 . Another AND gate 330 logically AND's bits 56 and y 6 to generate bit p . An XOR gate 320 logically XOR's bits 56 and y 6 to generate partial product bit p .

An alternative embodiment of portion 310 is shown in FIG. 3 C. AND gate 56 logically AND's bit y 5 and y 6 to generate partial product bit p . An inverter 340 inverts bit y 5 to generate bit y 5 . An AND gate 350 logically AND's bits y 5 and y 6 to generate bit p .

The above embodiments reduce the required number of partial product bit generators required to square. Furthermore, the required tree structure for adding the partial product bits is simplified. Therefore, what is provided is a faster squaring circuit and method that requires less space than conventionally known.

Although the principles of the present invention are described with reference to specific embodiments, these embodiments are illustrative only and not limiting. Many other applications and embodiments of the principles of the present invention will be apparent in light of this disclosure and the claims set forth below.

For example, although the lower bits are described above as being deleted while the upper bits are shifted left, the upper bits may be deleted while the lower bits are shifted left one bit as shown in the following example.

Alternatively, a combination of upper and lower bits may be deleted so that there are no upper (or lower) bits that has a corresponding lower (or upper) bit. The remaining partial product bits are shifted left 1 bit.

The above describes a squaring circuit in which there are no bits mk that have a corresponding bit km. However, the advantages of the present invention may be obtained, although to a lesser extent, by only shifting left a single bit (e.g., bit 1 b 16 ) and deleting the corresponding bit (e.g., bit b 16 1 ) as in the following example.