Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-12-17
2004-11-30
Malzahn, D. H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06826588
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of computer operations on numbers in binary form, including addition, subtraction and comparisons. In particular, it relates to these operations when numbers are represented in redundant form.
BACKGROUND OF THE INVENTION
In digital computations, the representation of numbers has a significant bearing upon the design of digital arithmetic circuits and therefore, upon their performance and complexity. Integer operands are represented in binary forms by ones and zeros in a base
2
number system. Three commonly used representation methods are called: sign-magnitude, one's complement, and two's complement.
FIG. 1
a
shows numbers represented in sign-magnitude. In sign-magnitude numbers, the most significant bit represents the sign (positive or negative) of the number. A sign-magnitude number can be negated by complementing the number's sign bit. When adding two positive or two negative numbers, the operation is straightforward. But, when the signs of the operands are different, the number with the smaller magnitude should be subtracted from the number with the larger magnitude. This makes arithmetic operations on sign-magnitude numbers cumbersome. The circuit for performing arithmetic operations must include an adder circuit, a subtracter circuit and a comparator circuit. Because of the complexity, and because of a serial dependency upon a comparison to control the arithmetic circuitry, designers have proposed other representation methods.
FIG. 1
b
shows numbers represented in one's complement. One way of determining the representation of a negative number in one's complement is to subtract the magnitude of the number from 2
n
−1 where n is the number of digits used in the representation. For example, if the word length is 4 bits, then 2
4
−1=15 is used, and the ones complement representation of −7 is calculated as shown in
120
of
FIG. 1
b.
A simpler way of determining the representation of a negative number in ones complement is to complement each bit of the corresponding positive number. This observation is key to simplifying subtraction for ones complement numbers. Since negating a number, B, is easily accomplished by digital circuitry, subtracting is accomplished through a combination of addition and negation:
A−B=A
+(−
B
)
Since there are two ways to represent zero in the ones complement representation method, addition circuitry is still slightly complicated.
FIG. 1
c
shows numbers represented in twos complement. In twos complement representation, there is only one representation for zero. The representation of a negative number can be determined by subtracting the magnitude of the number from 2
n
where n is the number of digits used to represent the number. For example, to find the representation of −7 in twos compliment, 2
4
=16 is used, as in the calculation shown in
130
of
FIG. 1
c.
FIG. 2
shows a 4-bit adder/subtracter for numbers represented in twos complement. A benefit of twos complement is that it reduces the complexity of the adder circuit. A twos complement adder/subtracter can be simplified by implementing twos complement negation as ones complement negation followed by incrementation.
In an addition/subtraction operation, carry signals propagate from right to left (less significant to more significant) until they reach a final destination, which can include the leftmost digit of a result. The time it takes for carry signals to propagate is directly related to the time it takes for a digital arithmetic circuit to produce a result of an operation. The circuit of
FIG. 2
is referred to as a ripple adder. In a ripple adder, a carry signal at stage i+1 is given as a function of the inputs at the ith stage.
FIG. 3
a
shows a carry-lookahead adder circuit, which uses a circuit shown in
FIG. 3
b
to propagate the carry signal. These circuits directly produce carry propagate and carry generate signals at each stage.
FIG. 3
c
shows a set of alternative circuits used to propagate the carry signal according to Ling's equations in an alternative carry-lookahead adder (Huey Ling, “High-Speed Binary Adder,”
IBM J. Res. Develop
., vol. 25, no. 3, May 1981).
The response time for a ripple adder with n stages is proportional to n, whereas the response time for a faster implementation such as a carry-lookahead adder is proportional to a logarithm of n.
In a system of numbers, where each number is assigned multiple binary representations, the numbers are said to be in redundant form. Further improvements in adder response times make use of numbers represented in redundant forms. For example, U.S. Pat. Nos. 4,890,127 and 5,815,420, use a signed-digit redundant representation form. Each digit is represented as a sign bit and a magnitude bit and can take on values of 1, 0, and −1.
FIG. 4
shows a circuit for calculating the sign bit and magnitude bit for each digit in the result, Z, from the digits of the operands, X and Y (as described in
FIG. 2
in U.S. Pat. No. 4,890,127). Negation is simple but calculations are somewhat complicated due to sign comparisons, and some calculations can generate new carries, which must be allowed to propagate.
FIG. 5
shows a set of rules to determine intermediate carries and sums, that avoids generating problematic new carries but introduces some additional computational complexity (from N. Takagi et al, “High speed VLSI multiplication algorithm with redundant binary addition tree,”
IEEE Trans. On Computes
, 34 (September 1985) 789-796).
Current microprocessors make use of pipelining to reduce the cycle time and exploit parallelism within instruction streams. In order to make pipelining efficient, results from digital arithmetic circuitry are bypassed back to circuit inputs as operands for the next instruction in a pipeline. This technique is preferred over one of waiting until results are written back to a register file, and it provides for higher utilization of a pipeline's parallelism.
Conversion from a redundant representation form to twos complement requires the propagation of carry signals. When results of a first operation are immediately required to perform a second operation, a conversion reduces the benefits of performing digital arithmetic in redundant form.
In U.S. Pat. No. 5,923,579, Widegen et al have shown a three-input comparator, where one of the inputs is an implicit constant.
FIG. 6
shows a preferred embodiment of the comparator device consisting of a custom carry-save adder (CSA) structure and a carry-propagate circuit (CPC). The custom CSA uses two different bit cells depending upon whether that bit position in the constant input is a one or a zero, and the CPC employs a full carry-lookahead circuit to provide the comparison result as quickly as possible.
REFERENCES:
patent: 3935438 (1976-01-01), Grupe
patent: 4422143 (1983-12-01), Guttag
patent: 4569032 (1986-02-01), Lee
patent: 4709226 (1987-11-01), Christopher
patent: 4858168 (1989-08-01), Hwang
patent: 4878192 (1989-10-01), Nishiyama et al.
patent: 4890127 (1989-12-01), Darley
patent: 4899305 (1990-02-01), Needles
patent: 4967388 (1990-10-01), Tate
patent: 4972362 (1990-11-01), Elkind et al.
patent: 5115408 (1992-05-01), Darley et al.
patent: 5140546 (1992-08-01), Ishikawa et al.
patent: 5144577 (1992-09-01), Linnenberg
patent: 5206825 (1993-04-01), Takagi et al.
patent: 5208490 (1993-05-01), Yetter
patent: 5270962 (1993-12-01), Fettweis
patent: 5285406 (1994-02-01), Lynch et al.
patent: 5329477 (1994-07-01), Kudou
patent: 5341322 (1994-08-01), Fettweis et al.
patent: 5386377 (1995-01-01), McClure
patent: 5392423 (1995-02-01), Yetter
patent: 5418736 (1995-05-01), Widigen et al.
patent: 5581497 (1996-12-01), Kumar
patent: 5659495 (1997-08-01), Briggs et al.
patent: 5680339 (1997-10-01), Moyse et al.
patent: 5696954 (1997-12-01), Guttag et al.
patent: 5719803 (1998-02-01), Naffziger
patent: 5754819 (1998-05-01), Lynch et al.
patent: 5764550 (1998-06-01), D'Souza
patent: 5808928 (
Bhushan Bharat
Crawford John
Grochowski Edward
Sharma Vinod
Intel Corporation
Malzahn D. H.
Mennemeier Larry M.
LandOfFree
Method and apparatus for a fast comparison in redundant form... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for a fast comparison in redundant form..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for a fast comparison in redundant form... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3296047