Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-09-22
2002-05-21
Ngo, Chuong Dinh (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06393453
ABSTRACT:
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.
001110011
0
10
(922)
x001110011010
(922)
000000000000
0
001110011010
1
000000000000
2
001110011010
3
001110011010
4
000000000000
5
000000000000
6
001110011010
7
001110011010
8
001110011010
9
00
0
000000000
a
+000000000000
b
000011001111100010100100
(850,084)
22221111111111
321098765432109876543210
(Column #)
Hereinafter, the k'th bit from the right in the multiplicand and the m'th bit from the right in the multiplier are respectively referred to as “multiplicand bit k” and “multiplier bit m”. For example, the italicized bit in the above multiplication is referred to as “multiplicand bit 2”. Furthermore, the k'th bit from the right in the m'th partial product is referred to as “partial product bit mk” (or “bit mk”). For example, the underlined bit in the a'th (a
16
, b
16
, C
16
, d
16
, e
16
and f
16
as used herein, are a hexadecimal numerals respectively equal to 10
10
, 11
10
, 12
10
, 13
10
, 14
10
, and 15
10
, partial product is referred to as “partial product bit a9” (or “bit a9”).
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.
REFERENCES:
patent: 3610906 (1971-10-01), Stampler
patent: 5337267 (1994-08-01), Colavin
patent: 5629885 (1997-05-01), Pirson et al.
patent: 6018758 (2000-01-01), Griesbach et al.
ATI International SRL
Ngo Chuong Dinh
Vedder Price Kaufman and Kammholz
LandOfFree
Circuit and method for fast squaring does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circuit and method for fast squaring, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit and method for fast squaring will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2862501