Fast overflow detection in decoded bit-vector addition

Details Fast overflow detection in decoded bit-vector addition Fast overflow detection in decoded bit-vector addition

1998-12-10

2001-08-14

Malzahn, David H. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06275840

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to the field of semiconductor microprocessors, and, more particularly, to the way that overflows are detected when decoded bit-vectors are added together.
2. Description of the Related Art
Decoded bit-vectors appear frequently in high-speed logic design. Decoded bit-vectors (also known as “one-hot encoded bit-vectors”) are needed for multiplexer (MUX) control, generally simplify control logic and can be added together faster than vectors in encoded form. For example, fast SHIFT operations may be readily used with decoded bit-vectors. A function frequently needed when decoded bit-vectors are added together is the detection of an overflow. Indeed, whether an overflow occurs or not is sometimes more interesting than the numerical value of the sum of the decoded bit-vectors.
An (N+1)-bit decoded bit-vector A=a
N
a
N−1
a
N−2
a
N−3
. . . a
k+1
a
k
a
k−1
. . . a
3
a
2
a
1
a
0
may represent any number from 0 to N. Only one of the bits A[i]=a
i
for any i between 0 and N is different from zero (0) and is set equal to one (1). The number represented by the decoded bit-vector is equal to the number of zeros (0's) to the right of the non-zero bit. For example, the number n is represented by n=A=a
N
a
N−1
a
N−2
. . . a
n+1
a
n
a
n−1
. . . a
2
a
1
a
0
where A[k]=a
k
=0 for k≢n, and A[n]=a
n
=1. More particularly, for N =9, the 10-bit decoded bit-vector representing 4 is 0000010000 and the 10-bit decoded bit-vector representing 3 is 0000001000, for example.
Adding two decoded bit-vectors may be effected by a shift left operation. A first one of the two decoded bit-vectors may be input into a shifter and then the 1 of that input decoded bit-vector may be shifted left by the number of zeros (0's) to the right of the 1 of the second one of the two decoded bit-vectors. For example, adding the 10-bit decoded bit-vector representing 4 (0000010000) to the 10-bit decoded bit-vector representing 3 (0000001000) may be effected by inputting 0000010000 (4) into a shifter and then shifting the 1 of 0000010000 (4) three places to the left, yielding the 10-bit decoded bit-vector result 0010000000 (7).
FIG. 1
illustrates a conventional implementation of 10-bit decoded bit-vector addition using MUXes with ten 2-AND gates and a 10-OR (as shown explicitly in MUX
100
) that is 10 bits wide (ten 10-ORs in parallel, for example, as shown with MUXes
100
-
190
). As shown in
FIG. 1
, the first one of the two 10-bit decoded bit-vectors X (0000010000, corresponding to 4) is input into each of ten MUXes
100
-
190
with the least significant bit (LSB, 0 here) at the top and with the most significant bit (MSB, 0 here) at the bottom. Then, in leftmost MUX
100
, whose output will be the MSB of the result, the second one of the two 10-bit decoded bit-vectors Y (0000001000, corresponding to 3) is input into MUX
100
with the MSB (0 here) at the top and with the LSB (0 here) at the bottom. Consequently, the LSB of X is 2-ANDed with the MSB of Y, the MSB of X is 2-ANDed with the LSB of Y and all the respective intervening bits are similarly 2-ANDed together, as shown in FIG.
1
.
As further shown in
FIG. 1
, Y (0000001000, corresponding to 3) is input into MUX
110
, whose output will be the next to MSB of the result, with the 1 bit shifted upward one place (giving 0000010000, corresponding to 4, reading from MSB to LSB). Similarly, Y (0000001000, corresponding to 3) is input into MUX
120
with the 1 bit shifted upward two places (giving 0000100000, corresponding to 5), into MUX
130
with the 1 bit shifted upward three places (giving 0001000000, corresponding to 6), into MUX
140
with the 1 bit shifted upward four places (giving 0010000000, corresponding to 7), into MUX
150
with the 1 bit shifted upward five places (giving 0100000000, corresponding to 8) and into MUX
160
with the 1 bit shifted upward six places (giving 1000000000, corresponding to 9). The outputs of each of the ten 2-AND gates in each of MUXes
100
-
160
are ORed together to yield the seven MSBs (0010000) of the result X+Y.
Moreover, as shown in
FIG. 1
, Y (0000001000, corresponding to 3) is input into MUX
170
, whose output will be the third LSB of the result, with the 1 bit shifted downward three places (giving 0000000001, corresponding to 0, reading from MSB to LSB). Similarly, Y (0000001000, corresponding to 3) is input into MUX
180
with the 1 bit shifted downward two places (giving 0000000010, corresponding to 1) and into MUX
190
with the 1 bit shifted downward one place (giving 0000000100, corresponding to 2). The outputs of each of the ten 2-AND gates in each of MUXes
170
-
190
are ORed together to yield the three LSBs (000) of the result X+Y. Putting together the seven MSBs (0010000) and the three LSBs (000) gives the final result X+Y=0010000000, corresponding to 7=4+3.
Taking another example, as shown in the conventional design of
FIG. 2
, the first one of the two 10-bit decoded bit-vectors X (0000010000, corresponding to 4) is input into each of ten MUXes
200
-
290
with the least significant bit (LSB, 0 here) at the top and with the most significant bit (MSB, 0 here) at the bottom. Then, in leftmost MUX
200
, whose output will be the MSB of the result, the second one of the two 10-bit decoded bit-vectors Z (0000100000, corresponding to 5) is input into MUX
200
with the MSB (0 here) at the top and with the LSB (0 here) at the bottom. Consequently, the LSB of X is 2-ANDed with the MSB of Z, the MSB of X is 2-ANDed with the LSB of Z and all the respective intervening bits are similarly 2-ANDed together, as shown in FIG.
2
.
As further shown in
FIG. 2
, Z (0000100000, corresponding to 5) is input into MUX
210
, whose output will be the next to MSB of the result, with the 1 bit shifted upward one place (giving 0001000000, corresponding to 6, reading from MSB to LSB). Similarly, Z (0000100000, corresponding to 5) is input into MUX
220
with the 1 bit shifted upward two places (giving 0010000000, corresponding to 7), into MUX
230
with the 1 bit shifted upward three places (giving 0100000000, corresponding to 8) and into MUX
240
with the 1 bit shifted upward four places (giving 1000000000, corresponding to 9). The outputs of each of the ten 2-AND gates in each of MUXes
200
-
240
are ORed together to yield the five MSBs (10000) of the result X+Z.
Moreover, as shown in
FIG. 2
, Z (0000100000, corresponding to 5) is input into MUX
250
, whose output will be the fifth LSB of the result, with the 1 bit shifted downward five places (giving 0000000001, corresponding to 0, reading from MSB to LSB). Similarly, Z (0000100000, corresponding to 5) is input into MUX
260
with the 1 bit shifted downward four places (giving 0000000010, corresponding to 1), into MUX
270
with the 1 bit shifted downward three places (giving 0000000100, corresponding to 2), into MUX
280
with the 1 bit shifted downward two places (giving 0000001000, corresponding to 3) and into MUX
290
with the 1 bit shifted downward one place (giving 0000010000, corresponding to 4). The outputs of each of the ten 2-AND gates in each of MUXes
250
-
290
are ORed together to yield the five LSBs (00000) of the result X+Z. Putting together the five MSBs (10000) and the five LSBs (00000) gives the final result X+Z=1000000000, corresponding to 9=4+5.
When two (N+1)-bit decoded bit-vectors A=a
N
a
N−1
a
N−2
a
N−3
. . . a
n+1
a
n
a
n−1
. . . a
3
a
2
a
1
a
0
(corresponding to n, so that a
n
=1 and a
i
=0 for i≢n) and B=b
N
b
N−1
b
N−2
b
N−3
. . . b
m+1
b
m
b
m−1
. . . b
3
b
2
b
1
b
0
(corresponding to m, so that b
m
=1 and b
i
=0 for i≢m) add up to a number n+m less than or equal to N, then N−m+1 MUXes simil

Affiliated with

Also associated with

Rating

Fast overflow detection in decoded bit-vector addition does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fast overflow detection in decoded bit-vector addition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast overflow detection in decoded bit-vector addition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2505414