Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-12-23
2003-05-20
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S702000, C708S704000
Reexamination Certificate
active
06567836
ABSTRACT:
BACKGROUND
This disclosure is related to digital circuits for data processing, and more specifically, to digital adders.
A digital adder circuit digitally adds two digital numbers. Adding is a basic data manipulation in digital processing. Many electronic data processing devices, including microprocessors, implement one or more digital adders.
Binary adders are widely used in various digital electronic devices. Adding two binary numbers includes adding bits at each bit position of two input binary numbers using an exclusive or (“XOR”) operation, and also adding the corresponding carry-in bit from an adjacent lesser significant bit position, to produce a sum bit for that bit-position. A carry-out bit produced by that sum is determined and is then sent to the next, more significant bit position.
The carry-out bit from each bit position is zero, i.e., a “kill”, when two inputs to be added are both zero, no matter what the carry-in bit is. When two inputs to the bit position are both one, the carry-out bit is always one, i.e., a “generate”. The value of the carry-in bit does not affect the carry-out bit. However, when the two inputs are different, the carry-out bit is the carry-in bit to that bit position, i.e., the bit position “propagates” its carry-in bit to the next bit position. Binary adders use a special logic, a “PGK cell”, to process the carry at each bit position. Each PGK cell includes logic elements such as transistors to perform the above carry processing based on whether the addition operation at the bit position produces a propagate (“P”), a generate (“G”), or a kill (“K”).
This carry computation by each PGK cell takes time and need be carried out at each bit position. Hence, the carry computation can significantly affect the overall processing speed of a binary adder, especially, when the bit number is large, such as in a 32-bit adder. It is therefore desirable to develop binary adders that can efficiently process the carry information at a high speed.
SUMMARY
The present devices and techniques include mechanisms that allow propagation of a carry bit by skipping or bypassing two or more selected bit positions in binary adders, whenever permissible, though two or more levels of carry-skip paths in the carry processing part of the adders.
One embodiment of such adders includes carry-processing cells connected in series, carry-skip cells each coupled across a group of carry-processing cells, and a plurality of logic gates to control the carry-skip cells.
Each carry-processing cells processes carry information to generate a carry signal. Each carry-skip cell is coupled across a respective group of carry-processing cells to send a carry directly to a carry-processing cell that is subsequent to a most significant bit position in the respective group, when each and every carry-processing cell in the respective group produces a propagate.
Each logic gate is coupled between a carry-skip cell and a respective group of carry-processing cells to receive all carry signals from the respective group to produce an output. The number of carry-processing cells in all groups of carry-processing cells associated with the carry-skip cells is less than a maximum number. This number has a relationship with a total number of the carry-processing cells in the adder.
REFERENCES:
patent: 3451458 (1969-06-01), Stueber
patent: 3664403 (1972-05-01), Doran et al.
patent: 3728532 (1973-04-01), Pryor
patent: 3768537 (1973-10-01), Hess et al.
patent: 3884285 (1975-05-01), Russell et al.
patent: 3938574 (1976-02-01), Burmester et al.
patent: 4100172 (1978-07-01), Mui et al.
patent: 4128438 (1978-12-01), Wolff et al.
patent: 4482663 (1984-11-01), Kraus
patent: 4519430 (1985-05-01), Ahmad
patent: 4584661 (1986-04-01), Grundland
patent: 4590052 (1986-05-01), Chevallier et al.
patent: 4704414 (1987-11-01), Kerner et al.
patent: 5066721 (1991-11-01), Hamada et al.
patent: 5089554 (1992-02-01), Bomo et al.
patent: 5110969 (1992-05-01), Dittrich et al.
patent: 5159009 (1992-10-01), Wolff et al.
patent: 5227425 (1993-07-01), Rauline
patent: 5278783 (1994-01-01), Edmondson
patent: 5753732 (1998-05-01), Wideman et al.
patent: 1424503 (1976-02-01), None
Silvio Turrini et al., A Fully-Statis Low Power, High Performance 64-bit 3-level carry skip adder, 1994, IEEE Symposium on Low Power Electronics, p. 68-69.*
Chetana Nagendra et al., Area-Time-Power Tradeoffs in Parallel Adders, Oct. 1996, IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing vol. 43, No. 10, p. 689-702.*
Min Cha et al., Modified Carry Skip Adder for Reducing First Block Delay, Aug. 2000, IEEE Symposium on Circuits and Systems, p. 346-348.*
Pak K. Chan et al., Delay Optimization of Carry-Skip Adders and Block Carry-Lookahead Adders Using Multidimentional Dynamic Programming, Aug. 1992, IEEE Transactions on Computers, vol. 41, No. 8, p. 920-930.*
Vitit Kantabutra, Designing Optimum One-Level Carry-Skip Adders, Jun. 1993, IEEE Transactions on Computer, vol. 42, No. 6, p. 759-764.*
Goel et al., A New Time-Position Algorithm for the Modeling of Multilevel Carry Skip Adders in VHDL, 1996, IEEE, p. 158-161.*
Pak K. Chan et al., Delay Optimization of Carry-Skip Adders and Block Carry-Lookahead Adders, 1991, IEEE, p. 154-164.*
Akhilesh Tyagi, A Reduced Area Scheme for Carry-Select Adders, 1990, IEEE, p. 255-258.*
Silvio Turrini, “Optimal Group Distribution in Carry-Skip Adders”, Feb. 1989, Western Research Laboratory (WRL) Research Report 89/2, Copyright ©1989 Digital Equipment Corporation.
Bartlett, P.D. and Ghosh, T., Journal of Organic Chemistry, 1987, 52, 4937.
Garrett, A.B. and Hirschler, Alfred E., Journal of American Chemical Society, 1938, vol. 60 304.
Shields, T.C. and Kurtz, A.N., Journal of the American Chemical Society, 1969, 91, 5415.
Do Chat C.
Intel Corporation
Ngo Chuong Dinh
LandOfFree
Multi-level carry-skip adder does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-level carry-skip adder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-level carry-skip adder will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3051823