SE_I DELD K-Map

Carry Look Ahead Adder

Digital logic | Carry Look-Ahead Adder

Motivation behind Carry Look-Ahead Adder :
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 S4 is produced by the corresponding full adder as soon as the input signals are applied to it. But the carry input C4 is not available on its final steady state value until carry C3 is available at its steady state value. Similarly C3 depends on C2 and C2 on C1. Therefore, though the carry must propagate to all the stages in order that output S3 and carry C4 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 S3 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’ Gi and ‘carry propagate’ Pi then,

P_i = A_i ⊕ B_i

Gi = Ai Bi

The sum output and carry output can be expressed in terms of carry generate Gi and carry propagate Pi as

Si = Pi Xor Ci

Ci+1 = Gi + PiCi

where Gi produces the carry when both Ai Bi, are 1 regardless of the input carry. Pi is associated with the propagation of carry from Ci to Ci+1. 

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

C1 = G0 + P0Cin

C2 = G1 + P1C1 = G1 + P1G0 + P1P0Cin

C3 = G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0Cin

C4 = G3 + P3C3 = G3 + P3G2 + P3P2G1 + P3P2P1G0 + P3P2P1P0Cin

From the above Boolean equations we can observe that C4 does not have to wait for C3 and C2 to propagate but actually C4 is propagated at the same time as C3 and C2. 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 (C2, C3 and C4) for a carry look-ahead carry generator shown in below figure.

Time Complexity Analysis:
We could think of a carry look-ahead adder as made up of two “parts”

1.    The part that computes the carry for each bit.

2.    The part that adds the input bits and the carry for each bit position.

The log (n) complexity arises from the part that generates the carry, not the circuit that adds the bits.
Now, for the generation of the n^th carry bit, we need to perform a AND between (n+1) inputs. The complexity of the adder comes down to how we perform this AND operation. If we have AND gates, each with a fan-in (number of inputs accepted) of k, then we can find the AND of all the bits in log_k(n+1) time. This is represented in asymptotic notation as θ(logn).

Advantages and Disadvantages of Carry Look-Ahead Adder :
Advantages –

·         The propagation delay is reduced.

·         It provides the fastest addition logic.

Disadvantages –

·         The Carry Look-ahead adder circuit gets complicated as the number of variables increase.

·         The circuit is costlier as it involves more number of hardware.

BCD Adder using 7483

BCD Adder:

1. A BCD adder adds two BCD digits and produces a BCD digit. BCD number cannot be greater than 9.
2. The two given BCD numbers are to be added using the rules of binary addition.
3. If sum is less than or equal to 9 and carry=0carry=0 then correction is necessary. The sum is correct and in the true BCD form.
4. But if sum is invalid BCD or carry=1carry=1, then the result is wrong and needs correction.
5. The wrong result can be corrected by adding six (0110) to it.
6. The 4 bit binary adder IC 7483 can be used to perform addition of BCD numbers.
7. In this, if the four-bit sum output is not a valid digit, or if a carry C3C3 is generated then decimal 6 (0110 binary) is to be added to the sum to get the correct result.
8. Fig1 shows a 1-digit BCD adders can be cascaded to add numbers several digits long by connecting the carry-out of a stage to the carry-in of the next stage.
9. The output of combinational circuit should be 1 if the sum produced by adder 1 is greater than 9 i.e. 1001. The truth table is as follows

Operation: Case1: Sum ≤ 9 and carry = 0

• The output of combinational circuit Y’ = 0. Hence  B3 B2 B1B0  = 0 0 0 0 for adder-2.
• Hence output of adder-2 is same as that of adder-1

Case2: Sum >9 and carry = 0

• If S_3 S_2 S_1 S_0 of adder -1 is greater than 9, then output Y’ of combinational circuits becomes 1.
• Therefore B3 B2 B1B0  = 0 1 1 0 (of adder-2).
• Hence six (0 1 1 0) will be added to the sum output of adder-1.
• We get the corrected BCD result at the output of adder-2.

We can implement BCD addition using 4-Bit Binary Adder i.e. 7483.

Pin Configuration 7483:

Number Systems

Number System:

A digital system can understand positional number system only where there are a few symbols called 
digits and these symbols represent different values depending on the position they occupy in the number.

A value of each digit in a number can be determined using

       ·    The digit

       ·    The position of the digit in the number

      ·    The base of the number system (where base is defined as the total number of digits available in the 
          number system).

Decimal Number System

The number system that we use in our day-to-day life is the decimal number system. Decimal number 
system has base 10 as it uses 10 digits from 0 to 9. In decimal number system, the successive positions 
to the left of the decimal point represents units, tens, hundreds, thousands and so on.

Each position represents a specific power of the base (10). For example, the decimal number 1234 
consists of the digit 4 in the units position, 3 in the tens position, 2 in the hundreds position, and 1 in the 
thousands position, and its value can be written as

(1×1000) + (2×100) + (3×10) + (4×l)

(1×10³) + (2×10²) + (3×10¹)  + (4×l0⁰)

1000 + 200 + 30 + 1

1234

As a computer programmer or an IT professional, you should understand the following number 
systems which are frequently used in computers.

Binary Number System

Characteristics

        ·    Uses two digits, 0 and 1.

        ·     Also called base 2 number system

        ·      Each position in a binary number represents a 0 power of the base (2). Example: 2⁰

      ·    Last position in a binary number represents an x power of the base (2). Example: 2^x where x represents 
         the last position - 1.

Example

Binary Number: 10101₂

Calculating Decimal Equivalent −

Step	Binary Number	Decimal Number
Step 1	101012	((1 × 24) + (0 × 23) +(1 × 22) + (0 × 21) + (1 × 20))10
Step 2	101012	(16 + 0 + 4 + 0 + 1)10
Step 3	101012	2110

Note: 10101₂ is normally written as 10101.

Octal Number System

Characteristics

        ·     Uses eight digits, 0,1,2,3,4,5,6,7.

        ·     Also called base 8 number system

        ·     Each position in an octal number represents a 0 power of the base (8). Example: 8⁰

      ·     Last position in an octal number represents an x power of the base (8). Example: 8^x where x represents 
          the last position - 1.

Example

Octal Number − 12570₈

Calculating Decimal Equivalent −

Step	Octal Number	Decimal Number
Step 1	125708	((1 × 84) + (2 × 83) + (5 × 82) + (7 × 81) + (0 × 80))10
Step 2	125708	(4096 + 1024 + 320 + 56 + 0)10
Step 3	125708	549610

Note: 12570₈ is normally written as 12570.

Hexadecimal Number System

Characteristics

        ·     Uses 10 digits and 6 letters, 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.

        ·      Letters represents numbers starting from 10. A = 10, B = 11, C = 12, D = 13, E = 14, F = 15.

        ·       Also called base 16 number system.

        ·       Each position in a hexadecimal number represents a 0 power of the base (16). Example 16⁰.

       ·      Last position in a hexadecimal number represents an x power of the base (16). Example 16^x 
           where x represents the last position - 1.

Example −

Hexadecimal Number: 19FDE₁₆

Calculating Decimal Equivalent −

Step	Binary Number	Decimal Number
Step 1	19FDE16	((1 × 164) + (9 × 163) + (F × 162) + (D × 161) + (E × 160))10
Step 2	19FDE16	((1 × 164) + (9 × 163) + (15 × 162) + (13 × 161) + (14 × 160))10
Step 3	19FDE16	(65536 + 36864 + 3840 + 208 + 14)10
Step 4	19FDE16	10646210

Note − 19FDE₁₆ is normally written as 19FDE.

Combinational Circuit

Combinational circuit is a circuit in which we combine the different gates in the circuit, for example encoder, decoder, multiplexer and demultiplexer. Some of the characteristics of combinational circuits are following −

• The output of combinational circuit at any instant of time, depends only on the levels present at input terminals.
• The combinational circuit do not use any memory. The previous state of input does not have any effect on the present state of the circuit.
• A combinational circuit can have an n number of inputs and m number of outputs.

Block diagram

We're going to elaborate few important combinational circuits as follows.

Half Adder

Half adder is a combinational logic circuit with two inputs and two outputs. The half adder circuit is designed to add two single bit binary number A and B. It is the basic building block for addition of two single bit numbers. This circuit has two outputs carry and sum.

Block diagram

Truth Table

Circuit Diagram

Full Adder

Full adder is developed to overcome the drawback of Half Adder circuit. It can add two one-bit numbers A and B, and carry c. The full adder is a three input and two output combinational circuit.

Block diagram

Truth Table

Circuit Diagram

N-Bit Parallel Adder

The Full Adder is capable of adding only two single digit binary number along with a carry input. But in practical we need to add binary numbers which are much longer than just one bit. To add two n-bit binary numbers we need to use the n-bit parallel adder. It uses a number of full adders in cascade. The carry output of the previous full adder is connected to carry input of the next full adder.

4 Bit Parallel Adder

In the block diagram, A₀ and B₀ represent the LSB of the four bit words A and B. Hence Full Adder-0 is the lowest stage. Hence its C_in has been permanently made 0. The rest of the connections are exactly same as those of n-bit parallel adder is shown in fig. The four bit parallel adder is a very common logic circuit.

Block diagram

N-Bit Parallel Subtractor

The subtraction can be carried out by taking the 1's or 2's complement of the number to be subtracted. For example we can perform the subtraction (A-B) by adding either 1's or 2's complement of B to A. That means we can use a binary adder to perform the binary subtraction.

4 Bit Parallel Subtractor

The number to be subtracted (B) is first passed through inverters to obtain its 1's complement. The 4-bit adder then adds A and 2's complement of B to produce the subtraction. S₃ S₂ S₁ S₀ represents the result of binary subtraction (A-B) and carry output C_out represents the polarity of the result. If A > B then Cout = 0 and the result of binary form (A-B) then C_out = 1 and the result is in the 2's complement form.

Block diagram

Half Subtractors

Half subtractor is a combination circuit with two inputs and two outputs (difference and borrow). It produces the difference between the two binary bits at the input and also produces an output (Borrow) to indicate if a 1 has been borrowed. In the subtraction (A-B), A is called as Minuend bit and B is called as Subtrahend bit.

Truth Table

Circuit Diagram

Full Subtractors

The disadvantage of a half subtractor is overcome by full subtractor. The full subtractor is a combinational circuit with three inputs A,B,C and two output D and C'. A is the 'minuend', B is 'subtrahend', C is the 'borrow' produced by the previous stage, D is the difference output and C' is the borrow output.

Truth Table

Circuit Diagram

Multiplexers

Multiplexer is a special type of combinational circuit. There are n-data inputs, one output and m select inputs with 2^m = n. It is a digital circuit which selects one of the n data inputs and routes it to the output. The selection of one of the n inputs is done by the selected inputs. Depending on the digital code applied at the selected inputs, one out of n data sources is selected and transmitted to the single output Y. E is called the strobe or enable input which is useful for the cascading. It is generally an active low terminal that means it will perform the required operation when it is low.

Block diagram

Multiplexers come in multiple variations

• 2 : 1 multiplexer
• 4 : 1 multiplexer
• 16 : 1 multiplexer
• 32 : 1 multiplexer

Block Diagram

Truth Table

Demultiplexers

A demultiplexer performs the reverse operation of a multiplexer i.e. it receives one input and distributes it over several outputs. It has only one input, n outputs, m select input. At a time only one output line is selected by the select lines and the input is transmitted to the selected output line. A de-multiplexer is equivalent to a single pole multiple way switch as shown in fig.

Demultiplexers comes in multiple variations.

• 1 : 2 demultiplexer
• 1 : 4 demultiplexer
• 1 : 16 demultiplexer
• 1 : 32 demultiplexer

Block diagram

Truth Table

Decoder

A decoder is a combinational circuit. It has n input and to a maximum m = 2n outputs. Decoder is identical to a demultiplexer without any data input. It performs operations which are exactly opposite to those of an encoder.

Block diagram

Examples of Decoders are following.

• Code converters
• BCD to seven segment decoders
• Nixie tube decoders
• Relay actuator

2 to 4 Line Decoder

The block diagram of 2 to 4 line decoder is shown in the fig. A and B are the two inputs where D through D are the four outputs. Truth table explains the operations of a decoder. It shows that each output is 1 for only a specific combination of inputs.

Block diagram

Truth Table

Logic Circuit

Encoder

Encoder is a combinational circuit which is designed to perform the inverse operation of the decoder. An encoder has n number of input lines and m number of output lines. An encoder produces an m bit binary code corresponding to the digital input number. The encoder accepts an n input digital word and converts it into an m bit another digital word.

Block diagram

Examples of Encoders are following.

• Priority encoders
• Decimal to BCD encoder
• Octal to binary encoder
• Hexadecimal to binary encoder

Priority Encoder

This is a special type of encoder. Priority is given to the input lines. If two or more input line are 1 at the same time, then the input line with highest priority will be considered. There are four input D₀, D₁, D₂, D₃ and two output Y₀, Y₁. Out of the four input D₃ has the highest priority and D₀ has the lowest priority. That means if D₃ = 1 then Y₁ Y₁ = 11 irrespective of the other inputs. Similarly if D₃ = 0 and D₂ = 1 then Y₁ Y₀ = 10 irrespective of the other inputs.