Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-09-28
2002-08-20
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S710000
Reexamination Certificate
active
06438572
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention is directed, in general, to logic gates and, more specifically, to an adder having a reduced number of internal layers and method of operation thereof.
BACKGROUND OF THE INVENTION
Digital systems are used extensively in computation and data processing, controls, communications and measurement. Digital systems use digital signals that may only assume discrete values. Typically, digital systems use binary signals that employ only two values. Since such systems only use two distinct values, errors caused by component variations are minimized. As a result, a digital system may be designed such that, for a given input, an output thereof is exactly correct and repeatable. This gives rise to the extreme accuracy for which digital systems are well known.
Analog systems, on the other hand, use analog signals that vary continuously over a specified range. Analog systems are thus particularly vulnerable to error, depending on the accuracy of the components used therein. Since digital systems are generally capable of greater accuracy and reliability than analog systems, many tasks formerly performed by analog systems are now performed exclusively by digital systems.
One basic building block of digital systems is a logic gate. Conventional logic gates have one output and one or more inputs. The number of inputs is called the “fan-in” of the gate. The state of the output is completely determined by the state(s) of the input(s). Conventional logic gates are typically created by coupling a number of transistors together to perform a Boolean function (e.g., AND, OR, NOT). The logic gates are then coupled together to form a multi-layer circuit that is capable of performing logical functions (e.g., arithmetic functions).
The maximum number of gates cascaded in series between the input and the output of such a circuit is typically referred to as the number of layers of gates. Designers are concerned with the number of layers in a circuit for several reasons. In some applications, increasing the number of layers may reduce the required number of gates and/or gate inputs (i.e., fan-in), thus reducing the cost (which may be expressed in terms of integrated circuit area) of building the multi-layer circuit. Of course, cascading a larger number of gates together may result in unacceptable input-output delays and data dependency conditions. When the input of a gate is switched, a finite time elapses before the output of the gate changes. If a large number of gates are cascaded together to form a circuit, the time between an input change and a corresponding change in the output of the circuit may become excessive, thereby slowing down the operation of the multi-layer circuit.
Arithmetic functions are particularly susceptible to the effects of cascaded gates. The serial solution for binary addition is given here as an example. Initially, a first augend bit and a first addend bit are combined to produce a first sum bit and a first carry bit. The first carry bit is then combined with the second augend and addend bits to produce the second sum and carry bits. Since the second sum bit is dependent on the value of the first carry bit, the second sum bit cannot be computed before the first carry bit is computed. While each input-output delay is small, the cumulative input-output delay perceived when adding large numbers, due to the propagation of the carry bits, is, in the worst case, proportional to the number of bits added, and may be prohibitive. Techniques (e.g., carry look-ahead, conditional sum) have been developed to reduce the delay to a logarithmic function of the number of input bits to be added. The number of Boolean gates (e.g., AND, OR, NOT) used by such techniques is in the range of 8n to 35n, or 2n log(n) to 3n log(n), where n is the number of bits to be added and the logarithms are base two.
Increasing processing power is a continuing goal in the development of processors such as microprocessors or digital signal processors (DSPs). Processor designers are generally familiar with three ways to increase the processing power of a central processing unit (CPU). The CPU's clock frequency may be increased so that the CPU can perform a greater number of operations in a given time period. Processors are designed to operate at increasingly high clock frequencies. While a higher clock frequency generally results in increased processing power, the higher clock frequency also increases power dissipation, resulting in higher device operating temperatures. Processor designers, therefore, must address these additional problems to avoid catastrophic device failures.
Another way to increase processing power is to increase input and output data bus width, thereby allowing the CPU to process a greater amount of code and data. Early processors were packaged using dual in-line packaging (DIP) technology. Increasing the width of the data buses was both expensive and unrealistic, often resulting in extremely large device packages. Today, with the use of pin grid array (PGA) packaging, increasing the size of the data buses no longer poses a packaging problem. Of course, a larger number of transistors is required to process the additional information conveyed by the wider data buses.
Yet another way to increase processing power is to change the internal architecture of the processor to overlap the execution of instructions by, for example, superscaling. This method also requires the addition of a large number of transistors, since entire processing stages or execution units must be duplicated. Performing a large number of instructions in parallel may also result in data dependency problems.
Another way to increase processing power is to reduce the number of layers of logic gates in multi-layer circuits such as adders and multipliers. However, reducing the number of layers requires increasing the number of gate inputs. Accordingly, what is needed in the art is a way to increase a processor's processing power by reducing the number of layers of logic gates while maintaining a reduced number of gates and gate inputs.
SUMMARY OF THE INVENTION
To address the above-discussed deficiencies of the prior art, the present invention provides an adder, a processor (such as a microprocessor or digital signal processor), and methods of adding in such adder or processor. In one embodiment, the adder includes: (1) a first and second units in a first logic layer, the first unit receiving first and second addend and augend bits and generating therefrom a first single group-carry-generate bit and first and second carry-propagate bits, the second unit receiving third and fourth addend and augend bits and generating therefrom a second single group-carry-generate bit and third and fourth carry-propagate bits and (2) a third unit in a second logic layer, coupled to the first and second units, that receives the first and second single group-carry-generate bits and the first, second, third and fourth carry-propagate bits and generates therefrom resulting group-carry-generate and group-carry-propagate bits.
The present invention therefore introduces the broad concept of employing logic gates having more than two inputs to process the initial addend and augend and subsequent carry propagate and generate bits more comprehensively thereby to reduce the number of layers an adder of a given width requires. Since the speed of an adder is a function of the number of layers in the adder, a reduction in layer number should serve to increase the speed of the adder, perhaps dramatically.
In one embodiment of the present invention, the first unit comprises a first logic gate that receives the first and second addend and augend bits and generates therefrom the first single group-carry-generate bit and the second unit comprises a second logic gate that receives the third and fourth addend and augend bits and generates therefrom the second single group-carry-generate bit. In a more specific embodiment, the first and second logic gates are threshold gates. In another, more specific embodiment, th
Malzahn David H.
RN2R, L.L.C.
LandOfFree
Adder having reduced number of internal layers and method of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adder having reduced number of internal layers and method of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adder having reduced number of internal layers and method of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2899868