Carry Look-Ahead Adder

 The adder produce carry propagation delay while performing other arithmetic operations like multiplication and divisions as it uses several additions or subtraction steps. This is a major problem for the adder and hence improving the speed of addition will improve the speed of all other arithmetic operations. Hence reducing the carry propagation delay of adders is of great importance. There are different logic design approaches that have been employed to overcome the carry propagation problem. One widely used approach is to employ a carry look-ahead which solves this problem by calculating the carry signals in advance, based on the input signals. This type of adder circuit is called a carry look-ahead adder.

Here a carry signal will be generated in two cases:

  1. Input bits A and B are 1
  2. When one of the two bits is 1 and the carry-in is 1.

In ripple carry adders, for each adder block, the two bits that are to be added are available instantly. However, each adder block waits for the carry to arrive from its previous block. So, it is not possible to generate the sum and carry of any block until the input carry is known. The i^{th} block waits for the i-1^{th} block to produce its carry. So there will be a considerable time delay which is carry propagation delay. 


 

Consider the above 4-bit ripple carry adder. The sum S_{3} is produced by the corresponding full adder as soon as the input signals are applied to it. But the carry input C_{4} is not available on its final steady-state value until carry C_{3} is available at its steady-state value. Similarly C_{3} depends on C_{2} and C_{2} on C_{1} . Therefore, though the carry must propagate to all the stages in order that output S_{3} and carry C_{4} settle their final steady-state value. 

The propagation time is equal to the propagation delay of each adder block, multiplied by the number of adder blocks in the circuit. For example, if each full adder stage has a propagation delay of 20 nanoseconds, then S_{3} will reach its final correct value after 60 (20 × 3) nanoseconds. The situation gets worse, if we extend the number of stages for adding more number of bits. 

Carry Look-ahead Adder : 
A carry look-ahead adder reduces the propagation delay by introducing more complex hardware. In this design, the ripple carry design is suitably transformed such that the carry logic over fixed groups of bits of the adder is reduced to two-level logic. Let us discuss the design in detail. 


 




 




Consider the full adder circuit shown above with corresponding truth table. We define two variables as ‘carry generate’ G_{i} and ‘carry propagate’ P_{i} then, 
P_{i} = A_{i} \oplus B_{i} \newline G_{i} = A_{i} B_{i}
 

The sum output and carry output can be expressed in terms of carry generate G_{i} and carry propagate P_{i} as


S_{i} = P_{i} \oplus C_{i} \newline C_{i+1} = G_{i} + P_{i} C_{i}
where G_{i} produces the carry when both A_{i} , B_{i} are 1 regardless of the input carry. P_{i} is associated with the propagation of carry from C_{i} to C_{i + 1} . 
 

The carry output Boolean function of each stage in a 4 stage carry look-ahead adder can be expressed as


C_{1} = G_{0} + P_{0} C_{in} \newline C_{2} = G_{1} + P_{1} C_{1} = G_{1} + P_{1} G_{0} + P_{1} P_{0} C_{in} \newline C_{3} = G_{2} + P_{2} C_{2} = G_{2} + P_{2} G_{1} + P_{2} P_{1} G_{0} + P_{2} P_{1} P_{0} C_{in} \newline C_{4} = G_{3} + P_{3} C_{3} = G_{3} + P_{3} G_{2} + P_{3} P_{2} G_{1} + P_{3} P_{2} P_{1} G_{0} + P_{3} P_{2} P_{1} P_{0} C_{in} \newline
 

From the above Boolean equations we can observe that C_{4} does not have to wait for C_{3} and C_{2} to propagate but actually C_{4} is propagated at the same time as C_{3} and C_{2} . Since the Boolean expression for each carry output is the sum of products so these can be implemented with one level of AND gates followed by an OR gate.


The implementation of three Boolean functions for each carry output (C_{2} , C_{3} and C_{4} ) for a carry look-ahead carry generator shown in below figure. 

 

Comments

Post a Comment

Popular posts from this blog

What is Artificial Intelligence ?

Image
  Artificial Intelligence  (AI) refers to the simulation of human intelligence in machines that are programmed to think and act like humans. It involves the development of algorithms and computer programs that can perform tasks that typically require human intelligence such as visual perception, speech recognition, decision-making, and language translation "Artificial Intelligence is the study of how to make computers do things at which, at the movement, people are better". ~ Rich and Knight (1991) Types of Artificial Intelligence Artificial Intelligence (AI) is broadly classified into: Types of AI Based on Capabilities Types of AI Based on Functionalities
Read more

Cybersecurity in the AI Era: Evolve Faster Than the Threats or Get Left Behind

  AI is changing cybersecurity faster than many defenders realize. Attackers are already using AI to automate reconnaissance, generate sophisticated phishing lures, and exploit vulnerabilities before security teams can react. Meanwhile, defenders are overwhelmed by massive amounts of data and alerts, struggling to process information quickly enough to identify real threats. AI offers a way to level the playing field, but only if security professionals learn to apply it effectively. Organizations are beginning to integrate AI into security workflows, from digital forensics to vulnerability assessments and endpoint detection. AI allows security teams to ingest and analyze more data than ever before, transforming traditional security tools into powerful intelligence engines. AI has already demonstrated its ability to accelerate investigations and uncover unknown attack paths, but many companies are hesitant to fully embrace it. Many AI models are implemented with such velocity that th...
Read more

Computer Organization | Instruction Formats (Zero, One, Two and Three Address Instruction)

Image
  Instruction formats refer to the way instructions are encoded and represented in machine language. There are several types of instruction formats, including zero, one, two, and three-address instructions. Each type of instruction format has its own advantages and disadvantages in terms of code size, execution time, and flexibility. Modern computer architectures typically use a combination of these formats to provide a balance between simplicity and power. Different Types of Instruction Fields A computer performs a task based on the instructions provided. Instructions in computers are comprised of groups called  fields . These fields contain different information for computers which are all written in 0s and 1s. Each field has a different significance or meaning, based on which a CPU decides what to perform. The most common fields are: The operation field specifies the operation to be performed, like addition. Address field which contains the location of the operand, i.e., re...
Read more