Course Outline - 醫學影像處理實驗室MIPL

Chapter 3
Gate-Level Minimization
授課教師: 張傳育博士 (Chuan-Yu Chang Ph.D.)
E-mail: [email protected]
Tel: (05)5342601 ext. 4337
Office: EB212
3-1 Introduction

Gate-level minimization refers to the design
task of finding an optimal gate-level
implementation of Boolean functions
describing a digital circuit.
Digital Circuits
3-2
3-2 The Map Method

The complexity of the digital logic gates


the complexity of the algebraic expression
Logic minimization


algebraic approaches: lack specific rules
the Karnaugh map




a simple straight forward procedure
a pictorial form of a truth table
applicable if the # of variables < 7
A diagram made up of squares

each square represents one minterm
Digital Circuits
3-3
3-2 The Map Method (cont.)

Boolean function



sum of minterms
sum of products (or product of sum) in the simplest
form
The simplest algebraic expression is an algebraic
expression with



The expression produces a circuit diagram with


a minimum number of terms
a minimum number of literals
A minimum number of gates and the minimum number of
inputs to each gates
The simplified expression may not be unique
Digital Circuits
3-4
Two-Variable Map

A two-variable map






four minterms
x' = row 0; x = row 1
y' = column 0;
y = column 1
a truth table in square
diagram
xy
x+y =
Fig. 3.2 Representation of functions
in the map
Digital Circuits
3-5
A three-variable map



Eight minterms
The Gray-code-like sequence
Any two adjacent squares in the map differ by only
one variable



primed in one square and unprimed in the other
e.g., m5 and m7 can be simplified
m5+ m7 = xy'z + xyz = xz (y'+y) = xz
Digital Circuits
3-6
A three-variable map (cont.)

Example 3-1


F(x,y,z) = S(2,3,4,5)
F = x'y + xy'
Digital Circuits
3-7
A three-variable map (cont.)



m0 and m2 (m4 and m6) are adjacent
m0+ m2 = x'y'z' + x'yz' = x'z' (y'+y) = x'z'
m4+ m6 = xy'z' + xyz' = xz' (y'+y) = xz'
Digital Circuits
3-8
A three-variable map (cont.)

Example 3-2

F(x,y,z) = S(3,4,6,7) = yz+ xz'
Digital Circuits
3-9

Four adjacent squares



2, 4, 8 and 16 squares
m0+m2+m4+m6 = x'y'z'+x'yz'+xy'z'+xyz'
= x'z'(y'+y) +xz'(y'+y)
= x'z' + xz‘ = z'
m1+m3+m5+m7 = x'y'z+x'yz+xy'z+xyz
=x'z(y'+y) + xz(y'+y)
=x'z + xz = z
Digital Circuits 3-10

Example 3-3


F(x,y,z) = S(0,2,4,5,6)
F = z'+ xy'
Digital Circuits 3-11

Example 3-4



F = A'C + A'B + AB'C + BC
express it in sum of minterms
find the minimal sum of products expression
Digital Circuits 3-12
3-3 Four-Variable Map

The map


16 minterms
combinations of 2, 4, 8, and 16 adjacent squares
Digital Circuits 3-13

Example 3-5


F(w,x,y,z) = S(0,1,2,4,5,6,8,9,12,13,14)
F = y'+w'z'+xz'
Digital Circuits 3-14

Example 3-6 Simplify the Boolean function
F = ABC + BCD + ABCD + ABC
Digital Circuits 3-15
卡諾圖化簡的規則
輸入端有N個變數時，則繪出2N個空格與其對應。
將真值表內輸入所對應的輸出依次填入空格內。
如果為布林代數式時：





若沒有明確的輸出則填入×或(don’t care)。
圈選的相鄰項越大越好，其中，相鄰項的個數須符合2n。










當布林代數式為SOP型時，將1填入對應的方格內，其餘的部分則
填0。
當布林代數式為POS型時，將0填入對應的方格內，其餘的部分則
填1。
n=0，20=1，當圈一格時無法消去任何變數。
n=1，21=2，當圈二格時可以消去1個變數。
n=2，22=4，當圈四格時可以消去2個變數。
n=3，23=8，當圈八格時可以消去3個變數。
n=4，24=16，當圈十六格時可以消去4個變數。
圈在一起的0或1必須滿足相鄰間僅有一個位元不同。
用最少的圈圈，把所有1的項圈起來。
圈過還可再圈。
Digital Circuits 3-16
Prime Implicants

意含項(implicant)：


質含項(prime implicant)：


任一個乘積項即為該函數的一個意含項(implicant)，
i.e，在卡諾圖內，由含有“1”之方格所組合的所有
矩形均是implicant。
某一implicant不再為另一個implicant的子集
(subset)此種implicant稱為prime implicant。
必要項(essential prime implicant)：

若函數的某個最小項(min term)僅包含在其中一個
prime implicant時，則該prime implicant稱為必要
項(essential prime implicant)
Digital Circuits 3-17

求下列卡諾圖之prime implicant, essential
prime implicant。
YZ
X
00
0
1

1
01
11
1
1
1
10
1
由卡諾圖中可看出，


prime implicants= X Z , X Z , Y Z , X Y 
essential prime implicants= X Z , X Z


Digital Circuits 3-18

求F(A, B, C, D)=S(0, 1, 2, 4, 5, 10, 11, 13, 15)之必要
項及最簡的SOP。
01
CD
11
10
00
AB
00
01
11
10
1
1
1
1
1
1
1
1
1
由卡諾圖中可看出共有7個prime implicant，其中
essential prime implicant只有1項 AC
因此，化簡後 F  AC  ABD ABC  ABD or BCD 

Digital Circuits 3-19
Consider F ( A, B, C, D)  (0,2,3,5,7,8,9,10,11,13,15)


the simplified expression may not be unique
F = BD+B'D'+CD+AD = BD+B'D'+CD+AB
= BD+B'D'+B'C+AD = BD+B'D'+B'C+AB'
Digital Circuits 3-20
3-4 Five-Variable Map

Map for more than four variables becomes
complicated

five-variable map: two four-variable map (one on
the top of the other)
Digital Circuits 3-21

Table 3.1 shows the relationship between the number
of adjacent squares and the number of literals in the
term.
Digital Circuits 3-22

Example 3-7

F = S(0,2,4,6,9,13,21,23,25,29,31)
F = A'B'E'+BD'E+ACE
Digital Circuits 3-23
Another Map for Example 3-7
F = S(0,2,4,6,9,13,21,23,25,29,31)
ABC
DE
000 001 011
00
1
1
11
1
111
101 100
1
1
1
1
1
1
01
10
010 110
1
1
Digital Circuits 3-24
 Another Map for Example 3-7
Digital Circuits 3-25
3-5 Product of Sums Simplification


Approach #1
 Simplified F' in the form of sum of products
 Apply DeMorgan's theorem F = (F')'
 F': sum of products => F: product of sums
Approach #2: duality
 將基本定理之OR與AND運算互換 , 把0變成1 , 1變成0，即可
得出對偶式(dual)。
 combinations of maxterms (it was minterms)
 M0M1 = (A+B+C+D)(A+B+C+D')
= (A+B+C)+(DD')
CD
= A+B+C
AB
00
01
11
10
00
M0
M4
M12
M8
01
M1
M5
M13
M9
11
M3
M7
M15
M11
10
M2
M6
M14
M10
Digital Circuits 3-26

Example 3-8




F = S(0,1,2,5,8,9,10)
F' = AB+CD+BD'
Apply DeMorgan's theorem; F=(A'+B')(C'+D')(B'+D)
Or think in terms of maxterms
Digital Circuits 3-27

Gate implementation of the function of
Example 3-8
Digital Circuits 3-28

Consider the function defined in Table 3.2.
In sum-of-minterm:
F ( x, y, z)  (1,3,4,6)
In sum-of-maxterm:
F ( x, y, z )  (0,2,5,7)
Taking the complement of F
F ( x, y, z )  ( x  z)( x  z )
Digital Circuits 3-29

Consider the function defined in Table 3.2.
Combine the 1’s:
F ( x, y, z)  xz  xz
Combine the 0’s :
F ( x, y, z)  xz  xz
Digital Circuits 3-30
3-6 Don't-Care Conditions

The value of a function is not specified for
certain combinations of variables


The don't care conditions can be utilized in
logic minimization


BCD; 1010-1111: don't care
can be implemented as 0 or 1
Example 3-9


F (w,x,y,z) = S(1,3,7,11,15)
d(w,x,y,z) = S(0,2,5)
Digital Circuits 3-31




F = yz + w'x'; F = yz + w'z
F = S(0,1,2,3,7,11,15) ; F = S(1,3,5,7,11,15)
either expression is acceptable
Also apply to products of sum
Digital Circuits 3-32
3-7 NAND and NOR Implementation

NAND gate is a universal gate

can implement any digital system
Digital Circuits 3-33
NAND and NOR Implementation


Two graphic symbols for a NAND gate
對等邏輯

對等邏輯在邏輯電路的分析化簡上相當好用，它可
以用來消去許多的迪莫根運算，
Digital Circuits 3-34
Two-level Implementation



The implementation of Boolean function with
NAND gates requires that the functions be in sum
of products
Example: F = AB+CD
F = ((AB)' (CD)' )' =AB+CD
Fig. 3-20 Three ways to implement F = AB + CD
Digital Circuits 3-35
Two-level Implementation (cont.)

Example 3-10
F ( x, y, z)  (1,2,3,4,5,7)
F ( x, y, z )  xy  xy  z
Digital Circuits 3-36
Two-level Implementation (cont.)

The procedure




Simplify the function and express it in sum of
products form.
Draw a NAND gate for each product term; the
inputs to each NAND gate are the literals of the
term
Draw a single NAND gate / invert-OR gate for the
second sum term.
A term with a single literal requires an inverter in
the first level. If the single literal is complemented,
it can be connected directly to an input of the
second-level NAND gate.
Digital Circuits 3-37
Multilevel NAND Circuits

AND-OR logic => NAND-NAND logic

The general procedure for converting a multilevel
AND-OR diagram into an all-NAND diagram





Convert all AND gates to NAND gates with AND-inverter
graphic symbols.
Convert all OR gates to NAND gates with inverter-OR
graphic symbols.
Check all the bubbles in the diagram. For every bubble
that is not compensated by another small circle along the
same line, insert an invert or complement the input literal.
(1)將邏輯函數化成積之和(SOP)最簡函數。
(2)將此SOP取兩次補數，再以迪莫根定理化簡，使
其OR運算全部變成以” ∙”(AND)為連接的運算。
Digital Circuits 3-38
Multilevel NAND Circuits

Example: F = A(CD + B) + BC
Fig. 3.22
Implementing F = A(CD + B) + BC
Digital Circuits 3-39
Multilevel NAND Circuits
Fig. 3.23 Implementing
F = (AB +AB)(C+ D)
Digital Circuits 3-40
Example

Problem 3.16

Simplify the following functions, and implement
them with two-level NAND gate circuits:
(a) F(A,B,C,D)=A’B’C+AC’+ACD+ACD’+A’B’D’
(b) F(A,B,C)=(A’+B’+C’)(A’+B’)(A’+C’)
Digital Circuits 3-41
Multilevel NAND Circuits

Simply the Multilevel NAND Circuits
Digital Circuits 3-42
NOR Implementation


NOR function is the dual of NAND function
The NOR gate is also universal



The transformation from the OR-AND diagram to a NOR
diagram






The function be simplified into product-of-sum form.
The simplified POS express is obtained from the map by combing
the 0’s and complementing.
Changing the OR gates to NOR gates with OR-invert graphic
symbols
Changing the AND gate to a NOR gate with an invert-AND graphic
symbol.
A single literal term going into the second-level gate must be
complemented.
方法：
(1)將邏輯函數化成和之積(POS)最簡函數。
(2)將此POS取兩次補數，再以迪莫根定理化簡，使其AND運算全
部變成以”＋”(OR)為連接的運算。
Digital Circuits 3-43
NOR Implementation
Logic operations with NOR gates
Digital Circuits 3-44

Two graphic symbols for a NOR gate
Example: F = (A + B)(C + D)E
Fig. 3.26
Implementing
F = (A + B)(C + D)E
Digital Circuits 3-45
NOR Implementation

F=(AB+E)(C+D)
Digital Circuits 3-46
NOR Implementation
Example: F = (AB +AB)(C + D)
Fig. 3.27
Implementing F = (AB +AB)(C + D) with NOR gates
Digital Circuits 3-47
Example

Problems 3.19

Simply the following functions, and implement
them with two-level NOR gate circuit:
(a) F=wx’+y’z’+w’yz’
(b) F(x,y,z)=[(x+y)(x’+z)]’
Digital Circuits 3-48
3-8 Other Two-level Implementations

Wired logic



a wire connection between the outputs of two
gates
open-collector TTL NAND gates: wired-AND logic
the NOR output of ECL gates: wired-OR logic
F  ( AB)  (CD)  ( AB  CD)  ( A  B)(C   D) AND-OR-INVERT function
F  ( A  B)  (C  D)  [( A  B)(C  D)]
OR-AND-INVERT function
Digital Circuits 3-49
Nondegenerate Forms


Consider four types of gates: AND, OR, NAND,
and NOR.
16 possible combinations of two-level forms


eight of them: degenerate forms = a single operation
The eight nondegenerate forms




AND-OR, OR-AND, NAND-NAND, NOR-NOR, NOR-OR,
NAND-AND, OR-AND, AND-OR
AND-OR and NAND-NAND = sum of products
OR-AND and NOR-NOR = product of sums
NOR-OR, NAND-AND, OR-AND, AND-OR = ?
Digital Circuits 3-50
AND-OR-Invert Implementation

AND-OR-INVERT (AOI) Implementation

NAND-AND = AND-NOR = AOI
F = (AB+CD+E)'
F' = AB+CD+E(sum of products)

simplify F' in sum of products


Digital Circuits 3-51
Other Two-level Implementations (cont.)

OR-AND-INVERT (OAI) Implementation

OR-NAND = NOR-OR = OAI
F = ((A+B)(C+D)E)'
F' = (A+B)(C+D)E
(product of sums)

simplified F' in products of sum


Digital Circuits 3-52
Tabular Summary and Examples

Example 3-11





F' = x'y+xy'+z
F = (x'y+xy'+z)'
(F': sum of products)
(F: AOI implementation)
F = x'y'z' + xyz‘
(F: sum of products)
F' = (x+y+z)(x'+y'+z) (F': product of sums)
F = ((x+y+z)(x'+y'+z))'
(F: OAI)
Digital Circuits 3-53
Tabular Summary and Examples
Digital Circuits 3-54
Digital Circuits 3-55
3-9 Exclusive-OR Function

Exclusive-OR (XOR): XOR is equal to 1 if only x and
y differ in value.


Exclusive-NOR (XNOR): XNOR is equal to 1 if both x
and y are equal.


(xy)' = xy + x'y'
Some identities







xy = xy'+x'y
x0 = x
x1 = x'
xx = 0
xx' = 1
xy' = (xy)'
x'y = (xy)'
Commutative and associative


AB = BA
(AB) C = A (BC) = ABC
Digital Circuits 3-56
Exclusive-OR Function (cont.)

Implementations

(x'+y')x + (x'+y')y = xy'+x'y = xy
Digital Circuits 3-57
Exclusive-OR Function (cont.)

Odd function

ABC = (AB'+A'B)C' +(AB+A'B')C
= AB'C'+A'BC'+ABC+A'B'C
= S(1,2,4,7)

The three-variable exclusive-OR function is equal to 1 if only one
variable is equal to 1, or if all three variables are equal to 1.
For more variables, an odd number of variables be equal to 1.

Digital Circuits 3-58
Exclusive-OR Function (cont.)



The four minterms of the function are a unit
distance apart from each other.
The odd function is identified from the four
minterms whose binary values have an odd
number of 1’s.
The complement of an odd function is an even
function.


The three-variable even function is equal to 1 when an
even number of its variables is equal to 1.
Logic diagram of odd and even functions
Digital Circuits 3-59
Exclusive-OR Function (cont.)

Four-variable Exclusive-OR function

ABCD = (AB’+A’B)(CD’+C’D)
= (AB’+A’B)(CD+C’D’)+(AB+A’B’)(CD’+C’D)
Digital Circuits 3-60
Exclusive-OR Function (cont.)

Parity Generation and Checking


XOR functions are very useful in error detection
and correction codes.
Parity generator



A circuit that generates the parity bit in the transmitter.
a parity bit: P = xyz
Parity checker




A circuit that checks the parity bit in the receiver.
parity check: C = xyzP
C=1: an odd number of data bit error
C=0: correct or an ever # of data bit error
Digital Circuits 3-61
Exclusive-OR Function (cont.)
Digital Circuits 3-62
Exclusive-OR Function (cont.)
Digital Circuits 3-63
3.10 Hardware Description Language (HDL)

Hardware Description Language (HDL)



HDL is a computer-based language that describe
the design of digital systems in a textual form.
Used for describing hardware structure and the
function/behavior of logic circuits.
HDL are used in several major steps in the
design flow of an integrated circuit





Design entry
Functional simulation or verification
Logic synthesis
Timing verification
Fault simulation
Digital Circuits 3-64
Hardware Description Language (HDL) (cont.)

Design entry


Creates an HDL-based description of the functionality that is to be
implemented in hardware.
The description can be in a variety of forms:


Logic simulation



Boolean logic equation, truth tables, a netlist of interconnected gates,
an abstract behavioroal model.
Displays the behavior of a digital system through the use of a
computer.
A simulator interprets the HDL description and produces readable
output.
Logic synthesis


The process of deriving a list of physical components and their
interconnections from the model of a digital system described in an
HDL.
Logic synthesis is similar to compiling a program in a conventional
high-level language.

Logic synthesis produces a database describing the elements and
structure of a circuit.
Digital Circuits 3-65
Hardware Description Language (HDL) (cont.)

Timing verification




Confirms that the fabricated integrated circuit will operate at
a specified speed.
Propagation delays ultimately limit the speed at which a
circuit can operate.
Timing verification checks each signal path to verify that it is
not compromised by propagation delay.
Fault simulation


Compares the behavior of an ideal circuit with the behavior
of a circuit that contains a process-induced flaw.
Fault simulation is used to identify input stimuli that can be
used to reveal the difference between the faulty circuit and
the fault-free circuit.
Digital Circuits 3-66
A Top-Down Design Flow
第三版內容，參考用!
Specification
RTL design and
Simulation
Logic Synthesis
Gate Level Simulation
ASIC Layout
FPGA Implementation
Digital Circuits 3-67
Module Declaration




Examples of keywords:
module, end-module, input, output, wire, and, or, and not.
Any text between two forward slashes (//) and the end of the line
is interpreted as a comment.
Verilog is case sensitive.
A module is the fundamental descriptive unit in the Verilog
language
Fig. 3-37 Circuit to demonstrate an HDL
Digital Circuits 3-68
HDL Example 3.1

HDL description for circuit shown in Fig. 3.37
Digital Circuits 3-69
Gate Displays
Example: timescale directive
30ns
20ns
10ns
‘timescale 1 ns/100ps
Digital Circuits 3-70
HDL Example 3.2

Gate-level description with propagation delays for
circuit shown in Fig. 3.37
Digital Circuits 3-71
HDL Example 3.3

Test bench for simulating the circuit with delay
Digital Circuits 3-72
Simulation output for HDL Example 3.3
Digital Circuits 3-73
Boolean Expression
 Boolean expression for the circuit of Fig. 3.37
 Boolean expression:
HDL Example 3.4
Digital Circuits 3-74
HDL Example 3.4
Digital Circuits 3-75
User-Defined Primitives
 General rules:
 Declaration:
Implementing the hardware in Fig. 3.39
Digital Circuits 3-76
HDL Example 3.5
Digital Circuits 3-77
HDL Example 3.5 (Continued)
Digital Circuits 3-78
Fig. 3.39
Schematic for circuit with_UDP_02467
Digital Circuits 3-79

Download Report