Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-04-12
2004-11-09
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S493000
Reexamination Certificate
active
06816877
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a parallel multiplier, and more particularly, to an apparatus and method for digital multiplication adopting a redundant binary arithmetic technique to generate a partial product.
2. Description of the Related Art
With a recent trend toward system-on-a-chip (SoC), the functional blocks to constituting an integrated circuit are being demanded to occupy a small area of hardware while having improved performances. A multiplier is representative of the functional blocks, and plays an important role in many high-performance microprocessors or signal processing chips. Hence, a technique of reducing the size of a multiplier while maintaining the performance thereof is required to conform with the SoC trend.
In a multiplication arithmetic algorithm used in conventional multipliers, partial products are obtained using a modified booth's algorithm (MBA) and are added by a carry-save adder having a structure such as a Wallace-tree, to thereby obtain a final multiplication result. This multiplication is usually achieved using normal binary arithmetic. Here, the partial products can be summed using a redundant binary arithmetic technique instead of normal binary arithmetic technique. The characteristic of redundant binary arithmetic is that there is no continuous propagation of carry as required by general arithmetic for summing partial products.
A conventional arithmetic method performed by a multiplier using a redundant binary arithmetic will now be described. In this method, first, partial products are produced from input values by a normal binary arithmetic operation using an MBA.
A conventional multiplication method using the above-described MBA uses a radix-4 numeration system. That is, when numbers X and Y are multiplied, the number Y having m bits is expressed as in Equation 1 according to the MBA:
Y
=
∑
i
-
0
m
2
-
1
D
i
·
4
i
(
1
)
wherein Di corresponds to one among a group of values −2, −1, 0, 1 and 2, and is obtained by encoding three consecutive bits Y
i+2
, y
i+1
and y
i
of the number Y by a calculation of −2·y
i+2
+y
i+1
+y
i
. Every three consecutive bits of the m bits of number Y are grouped and consecutive groups overlap by one bit such that the last bit of each group is the first bit of the following group, thus
⌈
m
2
⌉
3-bit groups are obtained, and thus the number m of partial products is reduced to
⌈
m
2
+
1
⌉
.
Here, ┌x┐ denotes the smallest integer among integers that are greater than x. The reason why +1 is added is that correction bits to be added to the least significant bit of each of the partial products due to the 2's complement arithmetic are collected and the collected result is considered as a single partial product. The method of grouping three bits to encode m-bit Y in the MBA system is illustrated in Equation 2:
y
m
-
1
⏟
D
m
2
-
1
…
…
y
1
-
1
⏞
…
D
1
2
y
1
-
2
y
1
-
3
⏞
D
1
2
-
2
⏟
D
1
2
-
1
…
…
y
2
y
1
y
0
⏟
D
1
0
⏞
…
D
0
(
2
)
Equation 2 is applied when m is an even number, and always adds ‘0’ next to the least significant bit. In this case, since the MBA performs encoding using a radix-4, every three consecutive bits of the m bits of number Y are grouped and consecutive groups overlap by one bit such that the last bit of each group is the first bit of the following group, as shown in Equation 2. In a general case where the m-bit number Y is encoded in a 2
k
radix numeration system, every k+1 consecutive bits of the m bits of number Y are grouped and consecutive groups overlap by one bit such that the last bit of each group is the first bit of the following group. Here, partial products formed in normal binary numbers are produced by multiplying Di by X.
Next, the partial products formed in normal binary numbers are converted into partial products expressed in redundant binary numbers. That is, the sum of partial products A and B formed in normal binary numbers can be expressed as in Equation 3:
A+B=A
−(−
B
)=
A
−(
{overscore (B)}
+1)=(
A−{overscore (B)}
)−1 (3)
Here, if a−b is defined to be (a,b), it can be seen from Equation 4 that −1 is equal to (0,1):
A−{overscore (B)}
≡(
A,{overscore (B)}
) (4)
wherein the right side represents the redundant binary number of the result of A+B arithmetic operation. In the right side of Equation 3, −1, which is finally added to the least significant bit, is a correction bit to be added by the 2's complement arithmetic operation. Here, −1 can be expressed in a redundant binary number (0,1). When Equation 3 is adopted in the addition of partial products formed in normal binary numbers, the sum of partial products formed in redundant binary numbers can be obtained by pairing many normal binary partial products and inverting one of two normal binary partial products.
Consequently, when m-bit multiplication input values are multiplied by the MBA,
⌈
m
2
⌉
+
1
normal binary partial products are produced. Thus, r normal binary partial products are once summed while being converted into redundant binary numbers, resulting in the
⌈
r
2
⌉
sum expressed in redundant binary numbers.
These redundant binary numbers are summed by a redundant binary arithmetic operation on the basis of an addition rule as shown in Table 1, thereby obtaining the final product of X and Y, the product appearing in a redundant binary form.
Table 1 denotes a rule of summing redundant binary numbers using a conventional arithmatic technique. In Table 1, (a
i
+
,a
i
−
) and (b
i
+
,b
i
−
) denote two redundant binary numbers intended to be added, (c
i
+
,c
i
−
) and (s
i
+
,s
i
−
) represent an intermediate carry and an intermediate sum, respectively, which are expressed in redundant binary numbers, when two numbers are added, and “either” denotes that it does not matter whether ‘0’ or ‘1’ is selected as h
1−1
. Also, h
i−1
denotes an intermediate parameter made to prevent continuous carry propagation. Values of (a
i
+
,a
i
−
) and (b
i
+
,b
i
−
) when h
i
is 1 are bolded values. In the case of h
i
=1, value −1 can be possibly propagated as a carry.
TABLE 1
(a
1
+
,a
1
−
)
CASE
(b
1
+
,b
1
−
)
h
i-1
(c
1
+
,c
1
−
) (s
l
+
,s
l
−
)
1
(0,0) (0,1)
either
(0,0) (0,0)
(1,0)
(0,0) (1,0)
(0,1)
2
(0,1) (0,0)
0
(0,0) (0,1)
(0,0) (0,1)
1
(0,1) (1,0)
3
(1,0) (0,0)
0
(1,0) (0,1)
(0,0) (1,0)
1
(0,0) (1,0)
4
(0,1)
either
(0,1) (0,0)
(0,1)
5
(1,0)
either
(1,0) (0,0)
(1,0)
Referring to Table 1, an addition of two redundant binary numbers [(a
i
+
,a
i
−
) and (b
i
+
,b
i
−
)] corresponds to one among the five cases described above.
In Case 1 that the sum of two redundant binary numbers is zero, both the intermediate carry and the intermediate sum are 0. In Case 2 that the sum of two redundant binary numbers is −1, if there is a possibility that −1 is propagated from the next lower digit, that is, if h
i
is 1, the intermediate sum and the intermediate carry are 1 and −1, respectively, so that −1 is offset by the intermediate sum of 1 even if −1 is propagated. Thus, the addition can be carried out without carry propagation. In Case 3 that the sum of two redundant binary numbers is 1, if there is a possibility that 1 is propagated from the next lower digit, that is, if h
i
is 0, the intermediate sum and the intermediate carry are −1 and 1, respectively, so that 1 is offset by the intermediate
Lee Sang-hoon
Park Hong-june
Chang University of Science and Technology Foundation
Leydig , Voit & Mayer, Ltd.
Ngo Chuong Dinh
LandOfFree
Apparatus for digital multiplication using redundant binary... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for digital multiplication using redundant binary..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for digital multiplication using redundant binary... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3277032