Digital Logic Design

Chapter 4

1
Combinational Logic

 Outline
 Combinational Circuits
 Analysis
 Design
 Binary Adder / Subtractor
 Multiplier
 Comparator
 Encoder / Decoder
 Multiplexers / Demultiplexers

2
Combinational Circuits

 Recall
 Single/multiple inputs  Single output
 Many realistic problems use multiple outputs
 Named as combinational circuits
 Combinational circuit
 Output depends only on input(s)

3
Sequential Circuits

 What happens if we add memory to the circuit?

 Becomes a feedback system

 Sequential Circuits

4
Combinational Circuit Analysis

 Determine the function of circuit

 Instead of developing the circuit based on the function
 Circuit analysis
 Determine the output functions as algebraic expressions
OR
 Determine the truth table of the outputs

5
Combinational Circuit Analysis: Example1
Determining the output functions as algebraic expressions
 Analysis steps
1. Label all gate outputs with symbols
2. Determine Boolean function at the output of each gate
3. Express functions in terms of input variables + simplify

6
Combinational Circuit Analysis: Example1
Determining the output functions as algebraic expressions
 Step 1
Label all gate outputs with symbols

T2

T1 F

T3

7
Combinational Circuit Analysis: Example1
Determining the output functions as algebraic expressions
 Step 2
Determine Boolean function at the output of each gate

8
Combinational Circuit Analysis: Example1
Determining the output functions as algebraic expressions
 Step 3
Express functions in terms of input variables + simplify
T1  ( xy)
T2  ( xT1 )
T3  ( yT1 )
F  (T2T3 )  (( xT1 )( yT1 ))
 xT1  yT1  x ( xy)  y ( xy)
 x ( x  y )  y ( x  y )
 xx  xy   xy  yy 
 xy   xy  x  y

9
 Combinational Circuit Analysis: Example2
Determining the truth table of outputs
 Analysis steps
1. Label all gate outputs with symbols
2. Determine Boolean function at the output of each gate
3. Determine the truth table of outputs

10
 Combinational Circuit Analysis: Example2
Determining the truth table of outputs
 Step 1
Label all gate outputs with symbols

T4

T5

T6

11
Combinational Circuit Analysis: Example2

Determining the truth table of outputs

 Step 2
Determine Boolean function at the output of each gate

 Here
 T2 = ABC
 T1 = A+B+C
 T4=AB, T5=AC, T6=BC
 F2 = T4+T5+T6
=AB + AC + BC
 T 3 = F2’ T 1
 F 1 = T3 + T 2

12
 Combinational Circuit Analysis: Example2
Determining the truth table of outputs
 Step 3
Determine the truth table of outputs

A B C T1=A T2= T4=A.B T5=A.C T6=B.C F2=T4+T5 F2’ T3= F1=T2

+B+C A.B.C +T6 F2’.T1 +T3
0 0 0 0 0 0 0 0 0 1 0 0
0 0 1 1 0 0 0 0 0 1 1 1
0 1 0 1 0 0 0 0 0 1 1 1
0 1 1 1 0 0 0 1 1 0 0 0
1 0 0 1 0 0 0 0 0 1 1 1
1 0 1 1 0 0 1 0 1 0 0 0
1 1 0 1 0 1 0 0 1 0 0 0
1 1 1 1 1 1 1 1 1 0 0 1

13
Combinational Circuit Design
 Design procedure
1. Determine the number of inputs and outputs
2. Assign symbols
3. Derive the truth table
4. Obtain minimized output functions
5. Obtain simplified output functions
6. Draw the logic diagram

 Truth tables: input and output columns

 Multiple methods to solve

 Boolean algebra, map methods, computer aided solution

 Issues to consider
 Number of gates
 Gate inputs
 Propagation delay
 Number of interconnections

14
Combinational Circuit Design: Example

 Design a circuit that converts a BCD digit to Excess-3

code

15
Combinational Circuit Design: Example

 Design a circuit that converts a BCD digit to Excess-3

code

 Step 1&2: Inputs and Outputs

 Input: BCD digit
 4 inputs: A, B, C, D
 Output: Excess-3 digit
 4 outputs: w, x, y, z

 Step 3: Truth table

16
Combinational Circuit Design: Example
 Step 4: Minimize output functions

17
Combinational Circuit Design: Example

 Step 5: Simplification
 z = D’
 y = CD+C’D’
= CD+(C+D)’
 x = B’C+B’D+BC’D’
= B’(C+D)+BC’D’
= B’(C+D)+B(C+D)’
 w = A+BC+BD
= A+B(C+D)

18
Combinational Circuit Design: Example
 Step 6: Circuit Diagram

19
Binary Adders
 Addition is important function in computer system

 What does an adder do?

 Add binary digits
 Generate carry if necessary
 Consider carry from previous computation

 Binary adders operate bit-wise

 A 16-bit adder uses 16 one-bit adders

 Binary adders come in two flavors

 Half adder adds two bits and generates result and carry
 Full adder considers carry input in addition to half adder
 Two half adders make one full adder

20
Binary Half Adder

 Specification
 Design a circuit that adds two bits and generates the sum and a carry

 Input / Output

21
Binary Half Adder

 Specification
 Design a circuit that adds two bits and generates the sum and a carry

 Input/Output
 Two inputs: x, y
 Two output: S (sum), C (carry)

 Functionality

22
Binary Half Adder

 Specification
 Design a circuit that adds two bits and generates the sum and a carry

 Input/Output
 Two inputs: x, y
 Two output: S (sum), C (carry)

 Functionality

23
Binary Half Adder

24
Binary Half Adder
C= ∑(3)=xy
S= ∑(1,2)= 01+10= x’y+xy’

25
Full Adder 1 1

0 0 1
0 1 1
 Half adder works only for a single bit
1 0 0
 When multiple bits are involved, carry bits should be considered
 Solution  Full adder

 Specifications
 A circuit that adds three bits and
generates sum and carry

 Input/output
 Three inputs: x, y, Cin
 Two outputs: S (Sum), Cout (Carry)

 Truth table

26
Full Adder

 Half adder works only for a single bit

 When multiple bits are involved, carry bits should be considered
 Solution  Full adder

 Specifications
 A circuit that adds three bits and
generates sum and carry

 Input/output
 Three inputs: x, y, Cin
 Two outputs: S (Sum), Cout (Carry)

 Truth table

27
XOR gate/ XNOR gate
A B F A xor B= A’B +AB’ +
0 0 0 0 xor 0 = 1.0+0.1=0+0=0
0 1 1 0 xor 1= 1.1+0.0=1+0=1
1 0 1 1 xor 0= 0.0+1.1= 0+1=1
1 1 0
1 xor 1= 0.1+1.0=0+0=0

A B F A xnor B= AB +A’B’ .
0 0 1 0 xnor 0 = 0.0+1.1=0+1=1
0 1 0 0 xnor 1= 0.1+1.0=0+0=0
1 0 0
1 xnor 0= 1.0+0.1= 0+0=0
1 1 1
1 xnor 1= 1.1+0.0=1+0=1

Copyright 2011, Naveed Bin Rais (CIIT) 28

Full Adder

 Derive and minimize Boolean expressions

29
Full Adder

 Derive and minimize Boolean expressions

30
Full Adder

 Circuit

S  xyCin  xyCin  xyCin  xyCin  x  y  Cin

Cout  xy  xCin  yCin  ( x  y)Cin  xy

31
Full Adder

 Circuit

32
Full Adder from Half Adders

 How can two half adders make a full adder?

 Observations
 Three inputs x, y, z can be added in two steps
 x+y+z = (x+y) + z
 What about the carry?
 Carry can occur when adding x+y and when adding z

 Full adder: S = x  y  z , C = xy + (x  y)z

33
Full Adder from Half Adders

34