Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-09-08
2004-02-17
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S628000, C708S629000, C708S603000
Reexamination Certificate
active
06692534
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to combination multiplication and addition operations in a computing environment. More particularly, the present invention relates to an apparatus for performing nonparallel and parallel multiplication/addition operations, and a method for operating that apparatus.
2. The Background Art
In modern computers, it is often true that multiplication operations must be performed in order to satisfy a given objective. Those multiplication operations are often performed in either of two ways, traditional and parallel.
This disclosure primarily concerns itself with traditional multiplication where two numbers such as those seen in
FIG. 1A
are split into upper and lower halves such as those seen in FIG.
1
B. The upper and lower halves are then multiplied together in four operations, i.e the upper half of the first number is multiplied with the upper and lower halves of the second number, and the lower half of the first number is multiplied with the upper and lower halves of the second number, and then the four results are added together to form the final result of the multiplication.
Therefore, two numbers “A” and “B” (shown here as numbers
10
and
12
, each being 32-bits wide in this example) being multiplied together will each be broken into 16-bit halves, resulting in an upper half
14
and a lower half
16
from original number
10
, and an upper half and a lower half
20
from original number
12
.
Once the numbers are split apart into halves, and operation known as booth decoding is performed on one of the two halves as a first step in the multiplication of that number with the other number.
Booth decoding is a process by which overlapping groups of three bits each chosen from a first number are used to determine quantities of the second number which must be added together in order to produce a correct final multiplication result. In the example which follows, a first number and a second number are to be multiplied together. The second number is used as the key in booth decoding. In booth decoding when using the lower bits of the second number, a leading zero is added as the least significant bit of the lower half of the second number resulting in three-bit groups such as booth groups
22
,
24
,
26
,
28
,
30
,
34
,
36
, and
38
. Group
38
has two zeros added as most significant bits of the lower half, in order to properly complete that group.
When determining booth groups corresponding to the upper half of the second number, prior art systems again add a zero as the least significant bit of that upper half and use that zero when determining the rightmost booth group such as booth group
40
. The remaining booth groups such as booth groups
42
,
44
,
46
,
48
,
50
,
52
, and
54
are then determined as previously described.
In, order to determine the nine booth groups associated with this lower half of the second number, and also properly use those nine booth groups, the prior art uses the apparatus depicted in FIG.
2
.
Referring to
FIG. 2
, prior art system
56
includes booth recoder
58
which has and input for receiving a first number and an input for receiving a second number. Booth recoder
58
has nine outputs, each of those nine outputs providing partial products corresponding to the respective booth groups
22
,
24
,
26
,
28
,
30
,
32
,
34
,.
36
, and
38
. Eight of the nine outputs are provided in groups of four to two 4:2 compressors
60
and
62
the outputs of which are said to a third 4:2 compressor
64
.
The ninth output
66
of booth recoder
58
together with the two outputs
68
and
70
of 4:2 compressor
64
are provided to 3:2 compressor
72
. The two outputs of 3:2 compressor
72
are then provided to adder
74
to perform the final addition operation required. Output
76
of adder
74
is the final result of the multiplication.
While prior art systems are suitable for their intended purpose they require hardware which is unnecessary and which requires valuable space which could otherwise be used for different purpose. It would therefore be beneficial to provide a system which requires less hardware and therefore requires less space. This benefit and others are provided by the present invention.
SUMMARY OF THE INVENTION
The present invention provides an apparatus for booth decoding which stores the most significant bit of the lower half of the number used as the key for booth decoding. By using this stored bit to determine the rightmost booth group corresponding to the upper half of the key, booth decoding may be accomplished more quickly using an apparatus that is simpler and smaller than prior art assemblies.
REFERENCES:
patent: 4825401 (1989-04-01), Ikumi
patent: 5521856 (1996-05-01), Shiraishi
patent: 6233597 (2001-05-01), Tanoue et al.
Tzeng Allan
Wang Yong
Martine & Penilla LLP
Ngo Chuong Dinh
Sun Microsystems Inc.
LandOfFree
Specialized booth decoding apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Specialized booth decoding apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Specialized booth decoding apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3345105