Fast overflow detection in decoded bit-vector addition
AssigneeIntel Corporation
InventorsUmair A. Khan, Wolf C. Witt
Life of this patent
Estimating the term…
Abstract
A method for detecting overflow in an add operation on first and second decoded bit-vectors is provided, the method including generating a one-ahead vector using the first decoded bit-vector. The method also includes selecting an overflow bit from bits of the one-ahead vector using the second decoded bit-vector.
Claims30
A method for detecting overflow in an add operation on first and second decoded bit-vectors, said method comprising:
- generating a one-ahead vector using the first decoded bit-vector;
- and
- selecting an overflow bit from bits of the one-ahead vector using the second decoded bit-vector.
A method for detecting overflow in adding a first decoded bit-vector A=aNaN−1aN−2aN−3 . . . ak+1akak−1 . . . a3a2a1a0 and a second decoded bit-vector B=bNbN−1bN−2bN−3 . . . bk+1bkbk−1 . . . b3b2b1b0, said method comprising:
- generating a one-ahead vector OA using the first decoded bit-vector A so that the i-th bit OA[i] of the one-ahead vector OA is OA[i]=OR(aN,aN−1,aN−2,aN−3, . . . ,ai+3,ai+2,ai+1) for 0≦i≦N−2, OA[i]=aN for i=N−1, and OA[i]=0 for i=N;
- and
- selecting an overflow bit from bits of the one-ahead vector OA using the second decoded bit-vector B so that the overflow bit is OR(AND(OA[0],bN), AND(OA[1],bN−1), AND(OA[N−1],b1), AND(OA[N],b0)).
A method for detecting overflow in adding a first decoded bit-vector A=aNaN−1aN−2aN−3 . . . ak+1akak−1 . . . a3a2a1a0 and a second decoded bit-vector B=bNbN−1bN−2bN−3 . . . bk+1bkbk−1 . . . b3b2b1b0, said method comprising:
- generating a one-ahead vector OA using the first decoded bit-vector A so that the i-th bit OA[i] of the one-ahead vector OA is the sum from j=i+1 to N of aj for 0≦i≦N−1 and OA[i]=0 for i=N;
- and
- selecting an overflow bit from bits of the one-ahead vector OA using the second decoded bit-vector B so that the overflow bit is the sum from s=0 to N−1 of the products (OA[s]bN-s).
An article of manufacture comprising:
- a computer useable medium having a computer readable program code embodied in said medium for causing a computer to detect overflow in an add operation on first and second decoded bit-vectors, said computer readable program code in said article of manufacture including:
- computer readable program code for causing said computer to generate a one-ahead vector using the first decoded bit-vector;
- and
- computer readable program code for causing said computer to select an overflow bit from bits of the one-ahead vector using the second decoded bit-vector.
An article of manufacture comprising:
- a computer useable medium having a computer readable program code embodied in said medium for causing a computer to detect overflow in adding a first decoded bit-vector A=aNaN−1aN−2aN−3 . . . ak+1akak−1 . . . a3a2a1a0 and a second decoded bit-vector B=bNbN−1bN−2bN−3 . . . bk+1bkbk−1 . . . b3b2b1b0, said computer readable program code in said article of manufacture including:
- computer readable program code for causing said computer to generate a one-ahead vector OA using the first decoded bit-vector A so that the i-th bit OA[i] of the one-ahead vector OA is OA[i]=OR(aN,aN−1,aN−2,aN−3, . . . ,ai+3,ai+2,ai+1) for 0≦i≦N−2, OA[i]=aN for i=N−1, and OA[i]=0 for i=N;
- and
- computer readable program code for causing said computer to select an overflow bit from bits of the one-ahead vector OA using the second decoded bit-vector B so that the overflow bit is OR(AND(OA[0], bN), AND(OA[1], bN−1), . . . , AND(OA[N−1], b1), AND(OA[N], b0)).
An article of manufacture comprising:
- a computer useable medium having a computer readable program code embodied in said medium for causing a computer to detect overflow in adding a first decoded bit-vector A=aNaN−1aN−2aN−3 . . . ak+1akak−1 . . . a3a2a1a0 and a second decoded bit-vector B=bNbN−1bN−2bN−3 . . . bk+1bkbk−1 . . . b3b2b1b0, said computer readable program code in said article of manufacture including:
- computer readable program code for causing said computer to generate a one-ahead vector OA using the first decoded bit-vector A so that the i-th bit OA[i] of the one-ahead vector OA is the sum from j=i+1 to N of aj for 0≦i≦N−1 and OA[i]=0 for i=N;
- and
- computer readable program code for causing said computer to select an overflow bit from bits of the one-ahead vector OA using the second decoded bit-vector B so that the overflow bit is the sum from s=0 to N−1 of the products (OA[s]bN-s).
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for detecting overflow in an add operation on first and second decoded bit-vectors, said method comprising:
- generating a one-ahead vector using the first decoded bit-vector;
- and
- selecting an overflow bit from bits of the one-ahead vector using the second decoded bit-vector.
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for detecting overflow in adding a first decoded bit-vector A=aNaN−1aN−2aN−3 . . . ak+1akak−1 . . . a3a2a1a0 and a second decoded bit-vector B=bNbN−1bN−2bN−3 . . . bk+1bkbk−1 . . . b3b2b1b0, said method comprising:
- generating a one-ahead vector OA using the first decoded bit-vector A so that the i-th bit OA[i] of the one-ahead vector OA is OA[i]=OR(aN,aN−1,aN−2,aN−3, . . . ,ai+3,ai+2,ai+1) for 0≦i≦N−2, OA[i]=aN for i=N−1, and OA[i]=0 for i=N;
- and
- selecting an overflow bit from bits of the one-ahead vector OA using the second decoded bit-vector B so that the overflow bit is OR(AND(OA[0], bN), AND(OA[1], bN), . . . , AND(OA[N−1], b1), AND(OA[N], b0)).
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for detecting overflow in adding a first decoded bit-vector A=aNaN−1aN−2aN−3 . . . ak+1akak−1 . . . a3a2a1a0 and a second decoded bit-vector B=bNbN−1bN−2bN−3 . . . bk+1bkbk−1 . . . b3b2b1b0, said method comprising:
- generating a one-ahead vector OA using the first decoded bit-vector A so that the i-th bit OA[i] of the one-ahead vector OA is the sum from j=i+1 to N of aj for 0≦i≦N−1 and OA[i]=0 for i=N;
- and
- selecting an overflow bit from bits of the one-ahead vector OA using the second decoded bit-vector B so that the overflow bit is the sum from s=0 to N−1 of the products (OA[s]bN-s).
Dependencies are inferred from the claim text.