Combinational logic

Combinational circuit

When logic gate are connected together to produce a specified output on certain specified combination of input variables, with no memory involved, then it is Combinational circuit.
Output depends only on present inputs.
It may have m-binary inputs and n-binary outputs.

                   
              ____________________
     ------> |                    | ------>
 I/P ------> |   Combinational    | ------>  O/P
     . m     |      Circuit       |     n . 
     .       |                    |       .
     ------> |                    | ------>
              --------------------

Application:

Used in ALU (Arithmetic and logical unit ), data transmission, code converter etc.
Combinational circuit
1. Arithmetic & logical function
  - Adders
  - Subtractors
  - Comparitions
2. Data transmission
  - MUX & DeMUX
  - Encident Decoder
3. Code converters
  - Binary
  - BCD
  - Gray

Adder

Adder is a combinational circuit which perform addition of number (binary numbers, BCD, Excess-3).
Usage: Most importantly used in ALU, calculate address, table indices, increment and decrement operator etc.

Half Adder

A digital logical combinational circuit, which perform arithmetic addition of two, one-bit numbers.
Simplest form of addition of two binary digits, consists of four possible combinations.
Inputs are two single binary bits A and B, and two outputs sum (S) and carry (C).
No provision to add a carry, coming from the lower order bits.

                                
          ____________________
A -----> |                    | ------> Sum
         |       Half         |          
  I/P    |       Adder        |   O/P
         |                    |
B -----> |                    | ------> Carry
          --------------------

 Truth Table 

     Input    |    Output 
    -------------------------
    A     B   |  Sum    Carry 
    0     0   |   0       0
    0     1   |   1       0
    1     0   |   1       0  
    1     1   |   0       1

Full adder

A full adder is used to add only 3 binary bits. It has three inputs A, B and C_in and two outputs S and Co produced by addition of three inputs bits.
A_{(First operand)}, B_{(second operand)}
C in_{(Carry from the previous lower signigicant position)}

                       
                                     ____________________
                           A -----> |                    | ------> Sum
                                    |       Full         |          
                           B -----> |       Adder        |  
                                    |                    |
                        C in -----> |                    | ------> C out
                                     --------------------

                            Truth Table 

                              Input       |    Output 
                          --------------------------------
                           A     B   C in |  Sum     C out 
                           0     0     0  |   0       0
                           0     0     1  |   1       0
                           0     1     0  |   1       0  
                           0     1     1  |   0       1  
                           1     0     0  |   1       0
                           1     0     1  |   0       1
                           1     1     0  |   0       1
                           1     1     1  |   1       1

Full Adder using Half Adders

4 bit Parallel Adder using Full Adders

Serial Adder

Parallel adder performs the addition at higher speed but disadvantage is that it requires a large amount of logic circuitary.
Serial adder performs bit by bit addition so it requires simple circuitary then parallel adder but results in low speed of operation.

Half Subtractor

                    
                                   ____________________
                          A -----> |                    | ------> Difference (D)
                                   |       Half         |          
                            I/P    |    Subtractor      |   O/P
                                   |                    |
                          B -----> |                    | ------> Borrow (B0)
                                    --------------------

                        Truth Table 

                          Input    |    Output 
                        ---------------------------
                         A     B   |   D      B0 
                         0     0   |   0       0
                         0     1   |   1       1
                         1     0   |   1       0  
                         1     1   |   0       0

                         D = A'B + AB'
                           = AB' + A'B
                           = A ^ B
                         B0 = A'B

Full Subtractor

                    
                                 ____________________
                        A -----> |                    | ------> D
                                 |       Full         |          
                        B -----> |    Subtractor      |  
                                 |                    |
                     b in -----> |                    | ------> b out
                                  --------------------

                         Truth Table 

                           Input       |    Output 
                       --------------------------------
                        A     B   b in |   D     b out 
                        0     0     0  |   0       0
                        0     0     1  |   1       1
                        0     1     0  |   1       1  
                        0     1     1  |   0       1  
                        1     0     0  |   1       0
                        1     0     1  |   0       0
                        1     1     0  |   0       0
                        1     1     1  |   1       1

Parallel subtractor

Now the A (A₃A₂A₁A₀) will be added to the 2's complement of B (B₃B₂B₁B₀) to produce the sum, i.e., the difference between the A and B, and C_out (output carry), i.e. the borrow output of the 4-bit subtractor.
When the control input 'C' is kept low, the controlled inverter allows B (B₃B₂B₁B₀) without any change to the input of full adder, and the input carry C_in of LSB of full adder, becomes zero, Now A (A₃A₂A₁A₀) and B (B₃B₂B₁B₀) are added with C_in = 0.
Hence, the circuit functions as 4-bit adder/subtractor resulting in sum S (S₃S₂S ₁S₀) and carry output C_out.

Multiplexers

It is a combinational circuit that selects binary information from one of many input lines and directs it to output line.
It is simply a Data Selector.
Remember in multiplexer number of input can be many but output will always be one. Out of many input one is selected using select line / selector value.

Advantages:

Reduces no. of wires.
Reduces circuit complexity & cost.
Implementation of various circuit using MUX like adder (half/full), subtractor (half/full).

There are following type of MUX:

2x1 MUX
4x1 MUX
8x1 MUX
16x1 MUX

Note:

In 2x1 MUX → input = 2, Selection lines = 1 (as 2 = 2¹) and O/Ps = One
In 4x1 MUX → input = 4, Selection lines = 2 (as 4 = 2²) and O/Ps = One
In 8x1 MUX → input = 8, Selection lines = 3 (as 8 = 2³) and O/Ps = One
In 16x1 MUX → input = 16, Selection lines = 4 (as 16 = 2⁴) and O/Ps = One
In 32x1 MUX → input = 32, Selection lines = 5 (as 32 = 2⁵) and O/Ps = One

2x1 MUX

A 2x1 multiplier has 2 inputs, one control line and on O/P. Its circuit diagram and truth table is shown below:

Working:

Case1: When S0 = 0 then upper AND gate has I/Ps I0 and 1. AND gate multiplies them and give O/P I0. The lower AND gate I/Ps I0 and 0 so lower AND gate gives O/P 0. The OR gate add these I/Ps I0 and 0, so the final O/P is I0.
Case 2: When S0 = 1 then upper AND gate has I/Ps I1 and 0 AND gate multiplies then and gives O/P 0. The lower AND gate has I/Ps I1 and 1 so lower AND gate gives O/P I1. The OR gate add these I/Ps and 0 and I1, so the final O/P is I1.

4x1 MUX

A 4x1 multiplexer has 4 inputs (I0, I1, I2, I3), two selection line (S0 and S1) and one O/P. Its block diagram, circuit diagram and truth table is shown below:

Working:

Case 1: When S0 = 0 and S1 = 0 then upper AND gate has I/Ps 1, 1, I0. AND gate multiplies them and gives O/P I0 and all other AND gate give O/P 0.
Case 2: When S0 = 0 and S1 = 1 then second AND gate has I/Ps 1, 1, I1. AND gate multiplies them and gives O/P I1 and All other AND gate give O/P 0.
Case 3: When S0 = 1 and S1 = 0 then third AND gate has I/Ps 1, 1 ,I3. AND gate multiplies them and gives O/P I2. All other AND gate give O/P 0.
Case 4: When S0 = 1 and S1 = 1 then last AND gate give O/P 1, 1, I3. AND gate multiplies them and gives O/P I3. All other AND gate give O/P 0.

8x1 MUX

A 8x1 multiplexer has 8 inputs (I0, I1, I2, I3, I4, I5, I6, I7), three selection line (S0, S1 and S2) and one O/P. Its block diagram, circuit diagram and truth table is shown below:

Implementing boolean function using multiplexer

F(A, B, C) = ∑(1, 3, 5, 6)

Video lecture

F(A, B, C, D) = ∑(1, 2, 5, 7, 9, 14, 15)

Demultiplexer

A De-multiplexer (DMUX) is opposite of multiplexer.
It has single input, n selection lines and 2ⁿ output lines.
It passes the I/P in one O/P line among 2ⁿ O/P lines. It is also called as "Data Distributor"
There are following types of D-MUX:
1. 1x2 D-MUX
2. 1x4 D-MUX
3. 1x8 D-MUX
4. 1x16 D-MUX

1x2 D-MUX

A 1x2 D-MUX has only one input, one selection line and 2 O/Ps. Its circuit diagram and truth table is shown below:

Working

Case 1: When S₀ = 0 then upper AND gate has I/Ps I0 and 1. AND gate multiplies them and gives O/P I0 from O/P line O₀, hence O₀ = I₀. The lower AND gate has I/Ps I₀ and 0 so lower AND gate gives O/P 0.
Case 2: When S₀ = 1 then upper AND gate has I/Ps I₀ and 0. AND gate multiples them and gives O/P 0. The lower AND gate has I/Ps I₀ and 1 so lower AND gate gives O/P I₀ from O/P line O₁, hence O₁ = I₀.

1x4 D-MUX

A 1x4 D-MUX has only one input, 2 selection line (S0 and S1) and four O/Ps (O₀, O₁, O₂ and O₃). Its block diagram, circuit diagram and truth table is shown below:

Working

Case 1: When S0 = 0 and S1 = 0 then upper AND gate has I/Ps 1, 1, A. AND gate multiplies them and gives O/P A. So we get O/P from line O₀. All other AND gate give O/P 0.
Case 2: When S0 = 1 and S1 = 1 then second AND gate has I/Ps 1, 1, A. AND gate multiplies them and gives O/P A. So we get O/P from line O₁. All other AND gate give O/P 0.
Case 4: When S0=1 and S1=1 then last AND gate has I/Ps 1, 1, A. AND gate multiples them and gives O/P A. So we get O/P from line O₃. All other AND gate give O/P 0.

Encoder

An encoder is a digital circuit that performs the inverse operation of a decoder.
It converts information into Binary number system.
An encoder has 2ⁿ (or fewer) input lines and n output lines.
Example of an encoder is the octal-to-binary encoder whose truth table and circuit diagram are given below. It has 8 I/Ps and 3 O/Ps.

                    
            Inputs                     Outputs
A0  A1  A2  A3  A4  A5  A6  A7       B2   B1   B0
1   0   0   0   0   0   0   0        0    0    0
0   1   0   0   0   0   0   0        0    0    1
0   0   1   0   0   0   0   0        0    1    0
0   0   0   1   0   0   0   0        0    1    1
0   0   0   0   1   0   0   0        1    0    0
0   0   0   0   0   1   0   0        1    0    1
0   0   0   0   0   0   1   0        1    1    0
0   0   0   0   0   0   0   1        1    1    1

The 8 to 3 or octal to binary encoder consists of 8 inputs: A7 to A0 and 3 outputs: B2 , B1 and B0. Each input line corresponds to each octal digit and three outputs generate corresponding binary code.

Decimal to Binary Encoder

A Decimal to Binary Encoder converts decimal I/P into Binary O/P. It has 10 I/Ps and 4 O/Ps. It circuit diagram and truth table is given below:

Truth table ↓

                        
              INPUTS                            OUTPUTS
A0  A1  A2  A3  A4  A5  A6  A7  A8  A9      B3  B2  B1  B0
1   0   0   0   0   0   0   0   0   0       0   0   0   0
0   1   0   0   0   0   0   0   0   0       0   0   0   1
0   0   1   0   0   0   0   0   0   0       0   0   1   0
0   0   0   1   0   0   0   0   0   0       0   0   1   1
0   0   0   0   1   0   0   0   0   0       0   1   0   0
0   0   0   0   0   1   0   0   0   0       0   1   0   1
0   0   0   0   0   0   1   0   0   0       0   1   1   0
0   0   0   0   0   0   0   1   0   0       0   1   1   1
0   0   0   0   0   0   0   0   1   0       1   0   0   0
0   0   0   0   0   0   0   0   0   1       1   0   0   1

Decoder

A decoder is a combinational circuit. It converts (or decode) binary number into another number systems. It has n inputs and 2ⁿ outputs.
Types of decoder:
1. 2x4 line decoder
2. 3x8 line decoder (binary to octal decoder)
3. 4x16 line decoder

2x4 Decoder

A 2x4 Decoder has 2 inputs (A and B) and 4 O/Ps (D0, D1, D2, D3). Its circuit diagram and truth table is shown below:

Truth table

                        
  I/P   |    O/P
A   B   |  D0  D1  D2  D3
0   0   |  1   0   0   0
0   1   |  0   1   0   0
1   0   |  0   0   1   0
1   1   |  0   0   0   1

Working ↡

Case 1: When A = 0 and B = 0 then upper AND gate has I/Ps 1, 1. AND gate multiplies them and gives O/P 1. So we get O/P from line D0. All other gate give O/P 0.
Case 2: When A = 0 and B = 1 then second AND gate has I/Ps 1, 1. AND gate multiplies them and gives O/P 1. So we get O/P from line D1. All other AND gate give O/P 0.
Case 4: When A=1 and B=1 then last AND gate has I/Ps 1, 1. AND gate multiples them and gives O/P 1. So we get O/P from line D3. All other AND gate give O/P 0.

Binary to Octal Decoder (3x8 Decoder)

It has 3 inputs (A, B and C) and has 8 O/Ps (D0, D1, ..., D7). It takes binary input and gives Octal O/P. Its circuit diagram and truth table is shown below.

Truth table

                        
   I/P      |       O/P
A   B   C   |   D0  D1  D2  D3  D4  D5  D6  D7
0   0   0   |   1   0   0   0   0   0   0   0
0   0   1   |   0   1   0   0   0   0   0   0
0   1   0   |   1   0   1   0   0   0   0   0
0   1   1   |   1   0   0   1   0   0   0   0
1   0   0   |   1   0   0   0   1   0   0   0
1   0   1   |   1   0   0   0   0   1   0   0
1   1   0   |   1   0   0   0   0   0   1   0
1   1   1   |   1   0   0   0   0   0   0   1

Working ↓

Case 1: When A = 0, B = 0 and C = 0 then upper AND gate has I/Ps 1, 1, 1. This AND gate multiplies them and gives O/P 1. So we get O/P from line D0. All other gate give O/P 0.
It shows that when we apply 000 (Binary 0) then we get O/P from D0 (0 in octal).
Case 2: When A = 0, B = 0 and C = 1 then second AND gate has I/Ps 1,1,1. This AND gate multiplies them and gives O/P 1. So we get O/P from line D1. All other gate give O/P 0.
It shows that when we apply 001 (Binary 1) then we get O/P form D1 (1 in octal).
Case 3: When A = 0, B = 1 and C = 0 then third AND gate has I/Ps 1, 1, 1. This AND gate multiplies them and gives O/P 1. So we get O/P from line D2. All other AND gate give O/P 0.
It shows that when we apply 010 then we get O/P from D2 (2 in octal).
Case 7: When A = 1, B = 1 and C = 1 then last AND gate has I/Ps 1, 1, 1. This AND gate multiplies them and gives O/P 1. So we get O/P from line D7. All other AND gate give O/P 0.
It shows that when we apply 111 then we get O/P from D7 (7 in octal).

Binary to Decimal Decoder (4x10 line Decoder)

It has 4 inputs (A, B, C and D) and has 10 O/Ps (D0, D1, ..., D9). It takes binary input and gives Decimal O/P. Its circuit diagram and truth table is shown below:

Truth table

                        
   I/P         |            O/P
A   B   C  D   |   D0  D1  D2  D3  D4  D5  D6  D7  D8  D9
0   0   0  0   |   1   0   0   0   0   0   0   0   0   0
0   0   0  1   |   0   1   0   0   0   0   0   0   0   0
0   0   1  0   |   1   0   1   0   0   0   0   0   0   0
0   0   1  1   |   1   0   0   1   0   0   0   0   0   0
0   1   0  0   |   1   0   0   0   1   0   0   0   0   0
0   1   0  1   |   1   0   0   0   0   1   0   0   0   0
0   1   1  0   |   1   0   0   0   0   0   1   0   0   0
0   1   1  1   |   1   0   0   0   0   0   0   1   0   0
1   0   0  0   |   1   0   0   0   0   0   0   0   1   0
1   0   0  1   |   1   0   0   0   0   0   0   0   0   1

Working ↡

Case 1: When A = 0, B = 0, C = 0 and D = 0 then upper AND gate has I/Ps 1, 1, 1, 1. This AND gate multiplies them and gives O/P 1. So we get O/P from line D0. All other AND gate give O/P 0.
It shows that when we apply 0000 (Binary 0) then we get D0 (0 in Decimal).
Case 2: When A=0, B=0, C=0 and D=1 then second AND gate has I/Ps 1, 1, 1, 1. This AND gate multiplies them and gives O/P 1. So we get O/P from line D1. All other AND gate give O/P 0.
It shows that when we apply 0001 then we get O/P from D1 (1 in Decimal).
Case 8: When A=1, B=0, C=0, D=0 then second last AND gate has I/Ps 1,1,1,1. This AND gate multiplies them and gives O/P 1. So we get O/P from line D8. All other AND gate give O/P 0.
It shows that when we apply 1000 then we get O/P from D8 (8 in Decimal)
Case 9: When A=1, B=0, C=0, D=1 then last AND gate has I/Ps 1,1,1,1. This AND gate multiples them and gives O/P 1. So we get O/P from line D9. All other AND gate give O/P 0.
It shows that when we apply 1001 then we get O/P from D9 (9 in Decimal)

Combinational logic

Combinational logic

Combinational circuit

Adder

Half Adder

Full adder

Full Adder using Half Adders

4 bit Parallel Adder using Full Adders

Serial Adder

Half Subtractor

Full Subtractor

Parallel subtractor

Multiplexers

2x1 MUX

4x1 MUX

8x1 MUX

Implementing boolean function using multiplexer

Demultiplexer

1x2 D-MUX

1x4 D-MUX

Encoder

Decimal to Binary Encoder

Decoder

2x4 Decoder

Binary to Octal Decoder (3x8 Decoder)

Binary to Decimal Decoder (4x10 line Decoder)

Previous Year Questions