Lecture-08

Digital Logic Circuits

(502320)

Sehwan (Paul) Kim, Ph.D

Associate Professor, Dept. Biomedical Engineering,
School of Medicine, Dankook University, Korea
Vice President, Beckman Laser Institute Korea,
Specialist, Beckman Laser Institute,
University of California, Irvine, USA

1
 Outline of Chapter 4

 4.1 Introduction
 4.2 Combination Circuits
 4.3 Analysis Procedure
 4.4 Design Procedure
 4.5 Binary Adder-Subtractor
 4.6 Decimal Adder
 4.7 Binary Multiplier
 4.8 Magnitude Comparator
 4.9 Decoders
 4.10 Encoders
 4.11 Multiplexers
 4.12 HDL Models of Combination Circuits
 4.1 Introduction

 Logic circuits for digital systems may be combinational or

sequential.

 A combinational circuit consists of logic gates whose outputs at

any time are determined from only the present combination of
inputs.
 4.2 Combinational Circuits

 Logic circuits for digital system

◆ Sequential circuits
» Contain memory elements.
» The outputs are a function of the current inputs and the state of the memory
elements.
» The outputs also depend on past inputs.
 Combinational Circuits

 A combinational circuits
n
◆ 2 possible combinations of input values

n input Combinational m output

variables ….. variables

…..
Logic Circuit

Figure 4.1 Block diagram of combinational circuit

◆ Specific functions
» Adders, subtractors, comparators, decoders, encoders, and multiplexers.
» MSI (Medium Scale Integrated) circuits or standard cells.
 4-3 Analysis Procedure

 A combinational circuit
◆ Make sure that it is combinational not sequential
» No feedback path.
◆ Derive its Boolean functions (truth table)
◆ Design verification
◆ A verbal explanation of its function
 Analysis Procedure (1/3)

 To determine the function of circuit

 Analysis procedure
◆ Make sure the that circuit is combinational or sequential
◆ obtain 1) the output Boolean functions or 2) the truth table
 Analysis Procedure (2/3)
 Boolean function
◆ Label all gate outputs
◆ Make output functions at each level
◆ Substitute final outputs to input variables

 Truth table
◆ Put the input variables to binary numbers
◆ Determine the output value at each gate
◆ Obtain truth table
 Analysis Procedure (2/3)

T2 = ABC

F1 = T3+T2
T1 = A+B+C

T3 = F2'T1

F2 = AB+AC+BC

 Boolean function
◆ Label all gate outputs Figure 4.2 Logic Diagram for Analysis Example
◆ Make output functions at each level

◆ Substitute final outputs to input variables

 Analysis Procedure (2/3)
 F1 = T3+T2 = F2'T1+ABC = (AB + AC + BC)'(A + B + C) + ABC = (A' +
B')(A' + C')(B' + C')(A + B + C) + ABC = (A' + B'C') (AB' + AC' + BC' +
B'C) + ABC = A'BC' + A'B'C + AB'C' + ABC
 A full-adder
◆ F1: the sum
◆ F2: the carry

 Boolean function
◆ Label all gate outputs

◆ Make output functions at each level

◆ Substitute final outputs to input variables

Analysis Procedure (3/3)

‘
 4-4 Design Procedure

 The design procedure of combinational circuits

◆ State the problem (system spec.)
◆ Determine the required number of input and output from specification
◆ Assign a letter symbol to each input/output
◆ Derive the truth table
◆ Obtain the simplified Boolean functions
◆ Draw the logic diagram and verify design correctness
 Code Conversion Example

 Design “BCD to excess-3 code” converter

 Design Procedure
1) System Specification: BCD to excess-3 code converter
- Excess-3 code : decimal digit + 3
 Code Conversion Example

 Design “BCD to excess-3 code” converter

 Design Procedure
Step 1) System Specification: BCD to excess-3 code converter
- Excess-3 code : decimal digit + 3

Step 2) Determine inputs/outputs

Inputs : A,B,C,D (0000∼1001)
Outputs : W,X,Y,Z (0011∼1100)
 Code Conversion Example

 BCD (A,B,C,D (0000∼1001)) to excess-3 code (W,X,Y,Z (0011∼1100))

Step 3) Design Procedure: Derive the truth table
 Code Conversion Example
CD
 BCD to excess-3 code AB 00 01 11 10
Step 4) Design Procedure:
00
Obtain the simplified Boolean functions

01
ABCD wxyz

11
X X X X
10
X X

Don’t care !!
 The Maps
 BCD to excess-3 code
=w=
4) Design Procedure
Obtain the simplified Boolean functions AB
CD BD BC
00 01 11 10

00

01
1 1 1
A
11
X X X X
10
1 1 X X
w (A, B, C, D)
= S(5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) = A + BC + BD
 The Maps
 BCD to excess-3 code B’D
=x= B’C
4) Design Procedure
CD
Obtain the simplified Boolean functions AB 00 01 11 10

00
1 1 1
BC’D’
01
1

11
X X X X
10
1 X X
x (A, B, C, D)
= S(1,2,3,4,9,10,11,12,13,14,15) = B’C + B’D + BC’D’
 The Maps
 BCD to excess-3 code C’D’ = y = CD
4) Design Procedure
CD
Obtain the simplified Boolean functions AB 00 01 11 10

00
1 1

01
1 1

11
X X X X
10
1 X X
y (A, B, C, D)
= S(0, 3, 4, 7, 8,10,11,12,13,14,15) = CD + C’D’
 The Maps
 BCD to excess-3 code
=z= D’
4) Design Procedure
CD
Obtain the simplified Boolean functions AB 00 01 11 10

00
1 1

01
1 1
11
X X X X
10
1 X X
z (A, B, C, D)
= S(0, 2, 4, 6, 7, 10, 11, 12, 13, 14, 15) = D’
 The Maps

 The simplified functions

◆ z = D'
◆ y = CD +C'D'
◆ x = B'C + B'D+BC'D'
◆ w = A+BC+BD

BCD to Excess-3 Code Converter

 BCD to Excess-3
 BCD to excess-3 code
4) Design Procedure: Draw the logic diagram

z = D'
y = CD +C'D' = CD + (C+D)'
x = B'C + B'D+BC'D’
= B'(C+D) +B(C+D)‘
w = A+BC+BD

Logic Diagram for BCD to Excess-3 Code Converter

 Binary Adder-Subtractor

 Binary adder
◆ Half adder : performs the addition of 2-bits (x+y)
: is a combinational circuit that performs the addition of two bits, this circuit
needs two binary inputs and two binary outputs.
◆ Full adder : performs the addition of 3-bits (x+y+z)
:is a combinational circuit that performs the addition of three bits (two
significant bits and previous carry).
◆ Two half adder can be employed to a full adder

 Realization of Binary adder-subtractor

◆ Half adder
◆ Full adder
◆ Cascade of n-full adder
◆ Providing a complementing circuit
 4-5 Binary Adder-Subtractor

 Half adder
◆ Sum of 2 binary inputs
◆ 0 + 0 = 0 ; 0 + 1 = 1 ; 1 + 0 = 1 ; 1 + 1 = 10
◆ Two input variables: x, y
◆ Two output variables: C (carry), S (sum)
◆ Truth table
C=xy = AND

S=x’y+xy’ = XOR
4-5 Binary Adder-Subtractor

Figure 4.5 Implementation of Half-Adder

 Full-Adder

 Full-Adder
◆ The arithmetic sum of three input
bits.
◆ Three input bits
» x, y: two significant bits.
» z: the carry bit from the previous
lower significant bit.
◆ Two output bits: C, S

S = x’y’z+x’yz’+xy’z’+xyz C=xy+xz+yz = xy+xy’z+x’yz

 Full-Adder

Fig. 4-7 Implementation of Full Adder in Sum of Products

 Full-Adder

Fig. 4-8 Implementation of Full Adder with Two Half Adders and an OR Gate

◆ S = x'y'z+x'yz'+ xy'z'+xyz
◆ C = xy+xz+yz
◆ S = z(xy) = z'(xy'+x'y)+z(xy'+x'y)'= z'xy'+z'x'y+z((x'+y)(x+y')) =
xy'z'+x'yz'+xyz+x'y'z
◆ C = z(xy'+x'y)+xy = xy'z+x'yz+ xy
 Binary Adder

 Sum of two n-bit binary numbers

 4-bit adder
A=1011, B=0011

Figure 4.9 Full-bit adder

 Binary Subtractor

 A－B = A+(2’s complement of B)

 4-bit Adder-subtractor
◆ M=0 (act as adder), A+B; M=1(act as subtractor), A+(B’+1)
◆ x0 = x ◆ x1 = x'

Overflow

Check with XOR Fig. 4.13 4-Bit Adder Subtractor

 Overflow
◆ The storage is limited
◆ Sum of n digit number occupies n+1digit
◆ Occurs when two numbers are same sign
◆ V = 0, no overflow; V = 1, overflow
 Example: 8bit register (1bit sign/7bit number): -128~127

 Exclusive-OR (XOR) Check with XOR

◆ xy = xy'+x'y : if only x is equal to 1 or if only y is equal to 1,
Then 1
 4-6 Decimal Adder

 Add two BCD's

◆ 9 inputs: two BCD's and one carry-in
◆ 5 outputs: one BCD and one carry-out
 Design approaches
◆ Use binary full Adders (4 bit-binary adder)
» The maximum sum ← 9 + 9 + 1 = 19
» Binary to BCD
 BCD Adder (1/3)

 BCD Adder: The truth table

 BCD Adder (2/3)

 Modifications are needed if the sum > 9

◆ If C = 1, then sum > 9
» K = 1, or
» Z8Z4 = 1 (11××), or
» Z8Z2 = 1 (1×1×).
◆ Modification: −(10)d or + 6

C = K +Z8Z4 + Z8Z2

1100 1010
1101 1011
1110
1111
 BCD Adder (3/3)

 Block diagram

6
1100 1010
1101 1011
1110
1111

Fig. 4-14 Block Diagram of a BCD Adder

 Binary Multiplier (1/2)

 Partial products
◆ AND operations

Fig. 4.15 Two-bit by two-bit binary multiplier

 Binary Multiplier (2/2)

 4-bit (K-bits) by 3-bit(J-bits) binary multiplier

 (K-bits) x (J-bits)
 (K x J) AND gates,
(J-1) K-bit adder needed

 (4-bits) x (3-bits)
 (4 x 3) =12 AND gates,
(3-1)ea 4-bit adder needed

Fig. 4.16 Four-bit by three-bit binary

multiplier
 Quiz (1) ANS
 Half-Subtractor (Hint: input 2 bits (X,Y)//output 2 bits (D, B) of difference between two
inputs and borrow. Design step - First, design the truth table, then find the Boolean function
from the truth table. Finally, draw the logic circuit.)

D B

1 ◆ B = x’y
1 0
0

◆ D = x’y+xy’ = xy
 Quiz (1) ANS
 Full-Subtractor (Hint: input 3 bits (X,Y, and Bi); Bi is for borrow input/output 2 bits (D, Bo) of
difference between two inputs and borrow output. Design step - First, design the truth table. Second
simplify the Boolean function using the Karnaugh map. Third, find the simplified Boolean function from
the Karnaugh map. Finally, draw the logic circuit.)

Input Output ◆ Simplified it through k-map

X Y Bi D Bo
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
 Quiz (1) ANS
 Add wires and logic gates within the area labeled “overflow detection” so that
VU = 1 indicates unsigned overflow and VS = 1 indicates signed overflow. You
can connect your gates to whichever wires of the four-bit adder you want to
use.