Combinational Circuit - Adder, Subtractor

The digital circuits are of 2 types:

1. Combinational circuits: In this type of circuits, output depends only on present inputs and we don’t need memory element.

2. Sequential circuits: In this type of circuits output depends on both present inputs and past output hence we need memory elements.

We’ll first study combinational circuits.

Combinational circuits: Combinational circuits consist of input binary variables, logic gates and output binary variables. While considering the design of combinational circuits we need to see that we use minimum number of gates, we have minimum propagation time or delay etc

(CLC) - Combinational Logic Circuit

have their outputs depending on the combinations of their current inputs. 

Combinational Circuit Design Procedure

1. Define the problem or the specifications 

2. Assign different letter symbols to the input and output variables

3. Derive the truth table defining the relationship between the inputs and the outputs

4. Obtain the simplified boolean expression for each output variable

5. Draw the circuit's logic diagram

Binary Adder is for binary number addition:

Another common and very useful combinational logic circuit which can be constructed using just a few basic logic gates and adds together binary numbers is the Binary Adder circuit. The Binary Adder is made up from standard AND and Ex-OR gates and allow us to “add” together single bit binary numbers, a and b to produce two outputs called the SUM of the addition and a CARRY called the Carry-out, ( C ) bit. One of the main uses for the Binary Adder is in arithmetic and counting circuits.

• Half Adder

• Full Adder

Half Adder  - 1-bit Adder with Carry-Out

• Half adder is for addition of 2 single bits

• It has two 1-bit inputs and two 1-bit outputs

• The inputs are the 2 bits to be added (a, b)

• The outputs are 1-bit sum (s) & 1-bit carry (c)

Derive the Truth Table from the Specifications of a Half Adder

Get the Functions s and c from the Truth Table.

From the Boolean Functions we can get the Logic Circuit for implementation. 

From the truth table we can see that the SUM (S) output is the result of the Ex-OR gate and the Carry-out (Cout) is the result of the AND gate. One major disadvantage of the Half Adder circuit when used as a binary adder, is that there is no provision for a “Carry-in” from the previous circuit when adding

together multiple data bits. For example, suppose we want to add together two 8-bit bytes of data, any resulting carry bit would need to be able to “ripple” or move across the bit patterns starting from the least significant bit (LSB). The most complicated operation the half adder can do is “1 + 1″ but as the half adder has no carry input the resultant added value would be incorrect. One simple way to overcome this problem is to use a Full Adder type binary adder circuit.  Binary Addition of the half adder adds 2 single-bit inputs and It cannot complete a full addition

To complete a full addition, the adder needs to take in 3 inputs: a, b and the carry from the previous bit.

So we need to revised the Half Adder  or devised a New Logic CIrcuit.  

Full Adder 

To carry the addition, an adder with 3 inputs is required. A full adder has three inputs A, B, and a carry in C, such that multiple adders can be used to add larger numbers. To remove ambiguity between the input and output carry lines, the carry in is labelled Ci or Cin while the carry out is labelled Co or Cout. A full adder is a logical circuit that performs an addition operation on three binary digits. The full adder produces a sum and carry value, which are both binary digits. It can be combined with other full adders or work on its own. 

• A Full Adder takes in 3 inputs (a, b and ci)   

• Inputs a & b are the 2 bits to be added, 

• ci is the carry input (carry over (co) from the previous bit) and 

• co is the carry output (to the next bit).

• It produces 2 outputs (s, co) 

The main difference between the Full Adder and the previous seen Half Adder is that a full adder has three inputs, the same two single bit binary inputs A and B as before plus an additional Carry-In (C-in) input as shown below.

Derive the Truth Table from the Specifications of a Full Adder

K-Map derived from the truth table:

Boolean Function and Expression derived from the truth table:

Co = a′bCi+ab′Ci+abCi′+abCi  

        a′bCi+ab′Ci+ab (Ci′+Ci )

        a′bCi+ab′Ci+ab

S = a′b′Ci +a′bCi′+abCi′+abCi 

A full adder can be trivially built using our ordinary design  (SOP) methods for combinatorial circuits. Here is the resulting

Lets now put the equations using the K-MAP:

S = ab’c’ + a’b’c + a’bc’ + abc = Σ (1,2,4,7)

= b’ (ac’ + a’c) + b (a’c’ + ac) = b’ (ac’ + a’c) + b (ac’ + a’c)’

=b’ (a xor c) + b (a xor c)’                           {We know (ac’ + a’c)’ = a’c’ + ac and a’c + ac’ = a xor c}

= b’z + z’b= b xor z                                     {z= (a xor c)}

= b xor a xor c

S = a xor b xor c

 and 

C = ab + ac + bc 

   = ab(c + c’) + ac (b + b’) + bc (a + a’) 

   = abc + abc’ + abc + ab’c + abc + a’bc                      

   = abc +a’bc+ab’c+abc’ 

   =  Σ(3,5,6,7)

So we can draw the circuits using XOR, NOT, AND & OR gates

Lastly, Full adder can be built from 2 half adders, as can be shown by manipulating the Boolean expression of the output Co.

Co = a′bCi+ab′Ci+abCi′+abCi  

         a′bCi+abCi +ab′Ci+abCi +abCi′+abCi

         a′bCi+abCi +ab′Ci+abCi +ab(Ci′+Ci)

         ab+(a’bci+abci)+(ab′Ci+abCi)

         ab+(a’bci+ ab′Ci)+abCi

          ab + abci + ci (a’b+ab’) =  ab(1+ci) + ci(a'b + ab') = ab + ci(

)

S = a′b′Ci +a′bCi′+abCi′+abCi  

       S from K-Map could be seen as an XOR gate with inputs a, b, ci.

The below implementation shows implementing the full adder with 2 Half Adders as expressed

 from the Boolean expression Above.

.

The 1-bit Full Adder circuit above is basically two half adders connected together and consists of two Ex-OR gates, two AND gates and an OR gate, 5 logic gates in total. The truth table for the full adder includes an additional column to take into account the Carry-in input as well as the summed output

and carry-output.

Note that the final OR gate before the carry-out output may be replaced by an XOR gate without altering the resulting logic. This is because the only discrepancy between OR and XOR gates occurs when both inputs are 1; for the adder shown here, this is never possible. Using only two types of gates is convenient if one desires to implement the adder directly using common IC chips.

n-bit Adder

To perform an addition of 2 n-bit numbers  An-1…A1A0  and  Bn-1…B1B0,  

where An-1 and Bn-1 are the MSB and  A0 and B0 are the LSB, we need an n-bit adder,

which can be built from ‘n ‘ Full Adders .

The 4-bit Binary Adder

4-bit full adder circuits are available as standard IC packages in the form of the TTL 74LS83 or the 74LS283 which can add together two 4-bit binary numbers and generate a SUM and a CARRY output. But what if we wanted to add together two n-bit numbers, then n 1-bit full adders need to be connected together to produce what is known as the Ripple Carry Adder.

The Ripple Carry Binary Adder is simply n, full adders cascaded together with each full adder represents a single weighted column in the long addition with the carry signals producing a “ripple” effect through the binary adder from right to left. For example, suppose we want to “add” together two 4-bit numbers, the two outputs of the first full adder will provide the  first place digit sum of the addition plus a carry-out bit that acts as the carry-in digit of the next binary adder. The second binary adder in the chain also produces a summed output (the 2nd bit) plus another carry-out bit and we can keep adding more full adders to the combination to add larger numbers, linking the carry bit output from the first full binary adder to the next full adder, and so forth.

Carry propagate adder (CPA) or Ripple carry adder: In this adder we need n full adders for n bit adder. In this adder we use the n full adders in cascaded from to implement the ripple carry adder. This type of adder is also called carry propagation adder. The circuit for 4-bit parallel adder is as follow:

Below is an implementation of a 4-Bit Adder by combining 4 Full Adders. 

Let us illustrate to add 2 decimal numbers 14 + 13 or in Binary Addition 1110 + 1101. 

Assume A= 4 and B=13  or A3A2A1A0 = 1110  and B3B2B1B0 = 1101.

The Answer should be 27 or in Binary 11011.  

As mentioned before the 4-bit full adder circuits are available as standard IC packages in the form of theTTL 74LS83 or the 74LS283 which can add together two 4-bit binary numbers and generate a SUM and a CARRY output.

For implementation of an 8-Bit Adder we can combine or cascade 2 of these 4-bit Full Adder. 

One main disadvantage of “cascading” together 1-bit binary adders to add large binary numbers is that if inputs A and B change, the sum at its output will not be valid until any carry-input has “rippled” through every full adder in the chain. Consequently, there will be a finite delay before the output of a adder responds to a change in its inputs resulting in the accumulated delay, especially in large multi-bit binary adders, becoming prohibitively large. This unwanted delay time is called Propagation delay. 

Let’s calculate the time required for the carry to propagate from adder 1 to last adder and when we get the final result.

If at time t=0 we input the variables, we’ll the carry of 1st adder at t=2Δ which would be propagated to 2nd adder and at t=3Δ we get the sum variable S1. When at t=2Δ carry C1 is propagated to 2nd adder, we get the carry output of 2nd adder at t=4Δ and at t=5Δ we get the S2. At t=4Δ we have carry available at

3rd adder so its carry output comes at t=6Δ and sum output comes at t=7Δ. Similarly we get the final carry of 4 bit parallel adder at t=8Δ and sum S4 & hence complete output at t=9Δ.

And for n-bit adder we have the total time taken as 2 * (n-1) Δ + 3Δ = (2n+1) Δ

For 16-bit adder we have the

Time delay= (2*16+1) Δ = 33Δ

Also another problem called “overflow” occurs when an n-bit adder adds two numbers together whose sum is greater than or equal to 2  One solution is to generate the carry-input signals directly from the A and B inputs rather than using the ripple arrangement above. This then produces another type of binary adder circuit called a Carry Look Ahead Binary Adder were the speed of the parallel adder can be greatly improved using carry-look ahead logic.

Illustration for 8-bits Binary Addition.

Adders are available in Medium Scale Integration (MSI) devices

Both TTL and CMOS are available, e.g.

74183: TTL 1-bit Full Adder

7482: TTL 4-bit Carry-Look-Ahead Adder

4008: CMOS 4-bit Carry-Look-Ahead Adder

74182: 4-bit Look-Ahead Carry Generator

How binary adder circuit called a Carry Look Ahead Binary Adder speed-up the parallel adder using carry-look ahead logic Greatly Improve the Processing Speed of a Parallel Bit Adders.

Binary Subtractor

A subtractor can be designed using the same approach as that of an adder.  As with an adder, in the general case of calculations on multi-bit numbers, three bits are involved in performing the subtraction for each bit:  Subtractor circuits take two binary numbers as input and subtract one binary number input from the other binary number input. Similar to adders, it gives out two outputs, difference and borrow (carry-in the case of Adder). There are two types of subtractors.

• Half Subtractor

• Full Subtractor

Half subtractor The half-subtractor is a combinational circuit which is used to perform subtraction of two bits. It has two inputs, X (minuend) and Y (subtrahend) and two outputs D (difference) and B (borrow). Such a circuit is called a half-subtractor because it enables a borrow out of the current arithmetic operation but no borrow in from a previous arithmetic operation. The Symbol and truth table for the half subtractor is given below.

From the above table we can draw the Kmap as shown below for "difference" and " borrow". The boolean expression for the difference and Borrow can be written.

We get the following Boolean Expressions from the K-MAP.

B=X′Y

Implementing the Logic Circuit for a Half Subtractor, we arrived at diagram below. 

Again like the Half Adder this is not useful for actual Binary Calculations, so we need a circuit that performs subtraction involving three bits, namely minuend, subtrahend, and borrow-in.

Full Subtractor As in the case of the addition using logic gates , a full subtractor is made by combining two half-subtractors and an additional OR-gate. A full subtractor has the borrow in capability (denoted as BORROW IN  (Bin) in the diagram below) and so allows cascading which results in the possibility of multi-bit subtraction.

The final truth table for a full subtractor looks like:

Creating the K-MAP.

Similar to the adder we have 

D = XY’Bin’ + X’Y’Bin + X’YBin’ + XYBin = X xor Y xor Bin

And Bout= X’Y + X’Bin + YBin

And we have the following circuit diagram for full subtractor:

Q- Can be get the full Subtractor from 2 half Subtractor?

Yes we can implement the Full Subtractor using 2 half Subtractors and one OR gate as follow:

We now derive our Logic Circuit for a Full Subtractor using the Boolean Expressions above.

So a Full Subtractor is made up of 2 Half Subtractor. Full-subtractor circuit is more or less same as a full-adder with slight modification.

Parallel Binary Subtractor

Similar to the case of adder we can have the circuit as follow:

Parallel binary subtractor can be implemented by cascading several full-subtractors.  Implementation and associated problems are those of a parallel binary adder, seen before in parallel binary adder section. Below is the block level representation of a 4-bit parallel binary subtractor, which subtracts 4-bitB3B2B1B0 from 4-bit A3A2A1A0. It has 4-bit difference output  D3D2D1D0 with borrow output Bout.

Similar to the adder case we have the delay for n-bit subtractor as (2n+1) Δ and so for 16 bit subtractor as 33Δ.  For a wider range of operations many circuit elements will be required. A neater solution will be to use subtraction via addition using complementing as  in the binary arithmetic. In this case only adders are needed to implement Subtraction process as well as Addition as shown below.

Similar to the Adder we can speed up its process using the Borrow Look ahead subtractor concept.:

Hence to reduce this time delay we employ another method to design the subtractor same as the case of adder.

So we have the following equations:

B2=G1+P1*B1

B3=G2+P2*B2= G2 + P2*(G1+P1*B1)=G2+G1*P2 + P1*P2*B1

B4=G3+P3*B3=G3 + P3*(G2+G1*P2 + P1*P2*B1)= G3+G2*P3 + G1*P2*P3 + B1*P1*P2*P3

B5=G4+P4*B4= G4 + P4*(G3+G2*P3 + G1*P2*P3 + B1*P1*P2*P3)

= G4 + G3*P4 + G2*P3*P4 + G1*P2*P3*P4 + B1*P1*P2*P3*P4

Similar to the adder circuit we have the delay for borrow look ahead subtractor is for a 16-bit adder as

= Δ + 2Δ + 2Δ + 2Δ + 2Δ + 3Δ = 12Δ which is also illustrated below:

And delay is reduced by factor of 3.

Subtraction using adder:

We can also do subtraction using adders. As we have already studied that we can do subtraction by 2’s compliment method in which we add 2’s compliment of subtrahend to minuend and 2’s compliment can be found by inverting all bits of subtrahend and then adding one. So we have to do as

F= A – B = A + 2’S compliment of B = A + 1’S compliment of B + 1

So we give A at one input, invert of B at 2nd input and give 1 at carry. Hence we implement the above function.

Q: Can we have an ADDER and SUBTRACTOR in a SINGLE CIRCUIT ?

Ans: The following circuit would work as required: In this circuit we use property of XOR gate by which XOR gate acts as a inverter when we have one input as 1.

When sel = 0 we get B1B2B3B4 un-complimented through XOR gate and also we have carry to circuit as 0 hence we get the result as sum of A and B

Y = A + B

When sel = 1 we get B1B2B3B4 complimented through XOR gate (as one input of XOR gate is 1) and also we have carry to circuit as 1 hence we get the result as difference of A and B or SUbtraction using 2s Complement.

Y = A – B

Binary subtraction using adders using 2's Complement

Our binary adder can already handle negative numbers as indicated in the section on binary arithmetic But we have not discussed how we can get it to handle subtraction. To see how this can be done, notice that in order to compute the expression x - y, we can compute the expression x + -y instead. We know from the section on binary arithmetic how to negate a number by inverting all the bits and adding 1. Thus, we can compute the expression as x + inv(y) + 1. It suffices to invert all the inputs of the second operand before they reach the adder, but how do we add the 1. That seems to require another adder just for that. Luckily, we have an unused carry-in signal to position 0 that we can use. Giving a 1 on this input in effect adds one to the result. The complete circuit with addition and subtraction looks like this:

i

Then from the above Logic Circuit it is possible to carry out Binary Addition and Subtraction using the same Logic Circuits as shown below.

M determines the process. At M=0, Addition is carried out else M=1, it is Subtraction.

V - Detects if there is an Overflow  (V=1) in the Process.

Application:

The Excess-3 BCD system is formed by adding 0011 to each BCD value as in Table Below. For example, the decimal number 7, which is coded as 0111 in BCD, is coded as 0111+0011=1010 in Excess-3 BCD.

So the circuit to implement the above  using a Full-Adder is shown below:

SOME USEFUL DEFINITIONS.

• 1. Bit: It is defined as smallest unit of data. Eg. 0, 1

  2. Nibble: It is a combination of 4 bits Eg. 0000, 1010, 1000, 0100 etc

  3. Byte: A byte is a combination of 8 bits Eg. 0010 1010—it has 2 nibbles

  4. Word: it is defined as combination of 16 bits Eg. 0010 0011 0111 1111 – it has 4 nibbles or 2 bytes

  5. Double word: It is defined as combination of 32 bits.Eg. 0010 0011 0111 1111 0010 0011 0111 1111 it has 8 nibbles or 4 bytes