Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
37 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
161.00 kB
Просмотров:
76
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Lecture Two-Level Logic](/documents_6/bc34ceb00f3e46beb329469dc7576205/img0.jpg)
Содержание слайда: Lecture 3
Two-Level Logic Minimization Algorithms
Hai Zhou
ECE 303
Advanced Digital Design
Spring 2002
№2 слайд![Outline CAD Tools for -level](/documents_6/bc34ceb00f3e46beb329469dc7576205/img1.jpg)
Содержание слайда: Outline
CAD Tools for 2-level minimization
Quine-McCluskey Method
ESPRESSO Algorithm
READING: Katz 2.4.1, 2.4.2, Dewey 4.5
№3 слайд![Two-Level Simplification](/documents_6/bc34ceb00f3e46beb329469dc7576205/img2.jpg)
Содержание слайда: Two-Level Simplification Approaches
№4 слайд![Review of Karnaugh Map Method](/documents_6/bc34ceb00f3e46beb329469dc7576205/img3.jpg)
Содержание слайда: Review of Karnaugh Map Method
№5 слайд![Example of Karnaugh Map Method](/documents_6/bc34ceb00f3e46beb329469dc7576205/img4.jpg)
Содержание слайда: Example of Karnaugh Map Method
№6 слайд![Quine-McCluskey Method](/documents_6/bc34ceb00f3e46beb329469dc7576205/img5.jpg)
Содержание слайда: Quine-McCluskey Method
№7 слайд![Quine-McCluskey Method](/documents_6/bc34ceb00f3e46beb329469dc7576205/img6.jpg)
Содержание слайда: Quine-McCluskey Method
№8 слайд![Quine Mcluskey Method](/documents_6/bc34ceb00f3e46beb329469dc7576205/img7.jpg)
Содержание слайда: Quine Mcluskey Method
№9 слайд![Quine McCluskey Method Contd](/documents_6/bc34ceb00f3e46beb329469dc7576205/img8.jpg)
Содержание слайда: Quine McCluskey Method (Contd)
№10 слайд![Quine-McCluskey Method Contd](/documents_6/bc34ceb00f3e46beb329469dc7576205/img9.jpg)
Содержание слайда: Quine-McCluskey Method (Contd)
№11 слайд![Finding the Minimum Cover We](/documents_6/bc34ceb00f3e46beb329469dc7576205/img10.jpg)
Содержание слайда: Finding the Minimum Cover
We have so far found all the prime implicants
The second step of the Q-M procedure is to find the smallest set of prime implicants to cover the complete on-set of the function
This is accomplished through the prime implicant chart
Columns are labeled with the minterm indices of the onset
Rows are labeled with the minterms covered by a given prime implicant
Example a prime implicant (-1-1) becomes minterms 0101, 0111, 1101, 1111, which are indices of minterms m5, m7, m13, m15
№12 слайд![Prime Implicant Chart](/documents_6/bc34ceb00f3e46beb329469dc7576205/img11.jpg)
Содержание слайда: Prime Implicant Chart
№13 слайд![Prime Implicant Chart](/documents_6/bc34ceb00f3e46beb329469dc7576205/img12.jpg)
Содержание слайда: Prime Implicant Chart
№14 слайд![Prime Implicant Chart Contd](/documents_6/bc34ceb00f3e46beb329469dc7576205/img13.jpg)
Содержание слайда: Prime Implicant Chart (Contd)
№15 слайд![Prime Implicant Chart Contd](/documents_6/bc34ceb00f3e46beb329469dc7576205/img14.jpg)
Содержание слайда: Prime Implicant Chart (Contd)
№16 слайд![Second Example of Q-M Method](/documents_6/bc34ceb00f3e46beb329469dc7576205/img15.jpg)
Содержание слайда: Second Example of Q-M Method
№17 слайд![Second Example Contd](/documents_6/bc34ceb00f3e46beb329469dc7576205/img16.jpg)
Содержание слайда: Second Example (Contd)
№18 слайд![Prime Implicant Chart for](/documents_6/bc34ceb00f3e46beb329469dc7576205/img17.jpg)
Содержание слайда: Prime Implicant Chart for Second Example
№19 слайд![Essential Primes for Example](/documents_6/bc34ceb00f3e46beb329469dc7576205/img18.jpg)
Содержание слайда: Essential Primes for Example
№20 слайд![Delete Columns Covered by](/documents_6/bc34ceb00f3e46beb329469dc7576205/img19.jpg)
Содержание слайда: Delete Columns Covered by Essential Primes
№21 слайд![Resultant Minimum Cover](/documents_6/bc34ceb00f3e46beb329469dc7576205/img20.jpg)
Содержание слайда: Resultant Minimum Cover
№22 слайд![ESPRESSO Method](/documents_6/bc34ceb00f3e46beb329469dc7576205/img21.jpg)
Содержание слайда: ESPRESSO Method
№23 слайд![Boolean Space The notion of](/documents_6/bc34ceb00f3e46beb329469dc7576205/img22.jpg)
Содержание слайда: Boolean Space
The notion of redundancy can be formulated in Boolean space
Every point in a Boolean space corresponds to an assignment of values (0 or 1) to variables.
The on-set of a Boolean function is set of points (shown in black) where function is 1 (similarly for off-set and don’t--care set)
№24 слайд![Boolean Space If g and h are](/documents_6/bc34ceb00f3e46beb329469dc7576205/img23.jpg)
Содержание слайда: Boolean Space
If g and h are two Boolean functions such that on-set of g is a subset of on-set of h, then we write
g C h
Example g = x1 x2 x3 and h = x1 x2
In general if f = p1 + p2 + ….pn, check if pi C p1 + p2 + …p I-1 + pn
№25 слайд![Redundancy in Boolean Space x](/documents_6/bc34ceb00f3e46beb329469dc7576205/img24.jpg)
Содержание слайда: Redundancy in Boolean Space
x1 x2 is said to cover x1 x2 x3
Thus redundancy can be identified by looking for inclusion or covering in the Boolean space
While redundancy is easy to observe by looking at the product terms, it is not always the case
If f = x2 x3 + x1 x2 + x1 x3, then x1 x2 is redundant
Situation is more complicated with multiple output functions
f1 = p11 + p12 + … + p1n
f2 = ….
Fm = pm1 + pm2 + … p mn
№26 слайд![Minimizing Two Level](/documents_6/bc34ceb00f3e46beb329469dc7576205/img25.jpg)
Содержание слайда: Minimizing Two Level Functions
Sometimes just finding an irredundant cover may not give minimal solution
Example:
Fi = b c + a c + a bc (no cube is redundant)
Can perform a reduction operation on some cubes
Fi = a b c + a c + a bc (add a literal a to b c )
Now perform an expansion of some cubes
Fi = a b + a c + a bc(remove literal c from a b c )
Now perform irredundant cover
Fi = a b + a c (remove a b c )
At each step need to make sure that function remains same, I.e. Boolean equivalence
№27 слайд![Espresso Algorithm](/documents_6/bc34ceb00f3e46beb329469dc7576205/img26.jpg)
Содержание слайда: Espresso Algorithm
№28 слайд![Details of ESPRESSO Algorithm](/documents_6/bc34ceb00f3e46beb329469dc7576205/img27.jpg)
Содержание слайда: Details of ESPRESSO Algorithm
Procedure ESPRESSO ( F, D, R) /* F is ON set, D is don’t care, R OFF *
R = COMPLEMENT(F+D); /* Compute complement */
F = EXPAND(F, R) ; /* Initial expansion */
F = IRREDUNDANT(F,D); /* Initial irredundant cover */
F = ESSENTIAL(F,D) /* Detecting essential primes */
F = F - E; /* Remove essential primes from F */
D = D + E; /* Add essential primes to D */
WHILE Cost(F) keeps decreasing DO
F = REDUCE(F,D); /* Perform reduction, heuristic which cubes */
F = EXPAND(F,R); /* Perform expansion, heuristic which cubes */
F = IRREDUNDANT(F,D); /* Perform irredundant cover */
ENDWHILE;
F = F + E;
RETURN F;
END Procedure;
№29 слайд![Need for Iterations in](/documents_6/bc34ceb00f3e46beb329469dc7576205/img28.jpg)
Содержание слайда: Need for Iterations in ESPRESSO
№30 слайд![ESPRESSO Example](/documents_6/bc34ceb00f3e46beb329469dc7576205/img29.jpg)
Содержание слайда: ESPRESSO Example
№31 слайд![Example of ESPRESSO Input](/documents_6/bc34ceb00f3e46beb329469dc7576205/img30.jpg)
Содержание слайда: Example of ESPRESSO Input/Output
№32 слайд![Two-Level Logic Design](/documents_6/bc34ceb00f3e46beb329469dc7576205/img31.jpg)
Содержание слайда: Two-Level Logic Design Approach
№33 слайд![SOP and POS Two-Level Logic](/documents_6/bc34ceb00f3e46beb329469dc7576205/img32.jpg)
Содержание слайда: SOP and POS Two-Level Logic Forms
We have looked at two-level logic expressions
Sum of products form
F = a b c + b c d + a b d + a c
This lists the ON sets of the functions, minterms that have the value 1
Product of sums form (another equivalent form)
F = ( a + b + c ) . ( b + c + d ) . ( a + b + d ) . ( a + c)
This lists the OFF sets of the functions, maxterms that have the value 0
Relationship between forms
minimal POS form of F = minimal SOP form of F
minimal SOP form of F = minimal POS form of F
№34 слайд![SOP and POS Forms](/documents_6/bc34ceb00f3e46beb329469dc7576205/img33.jpg)
Содержание слайда: SOP and POS Forms
№35 слайд![Product of Sums Minimization](/documents_6/bc34ceb00f3e46beb329469dc7576205/img34.jpg)
Содержание слайда: Product of Sums Minimization
For a given function shown as a K-map, in an SOP realization one groups the 1s
Example:
For the same function in a K-map, in a POS realization one groups the 0s
Example: F(A,B,C,D) = (C.D) + (A.B.D) + (A.B.C)
With De Morgan’s theorem
F = (C + D) . (A + B + D) . (A + B + C)
Can generalize Quine McCluskey and ESPRESSO techniques for POS forms as well
№36 слайд![Two Level Logic Forms](/documents_6/bc34ceb00f3e46beb329469dc7576205/img35.jpg)
Содержание слайда: Two Level Logic Forms
№37 слайд![Summary CAD Tools for -level](/documents_6/bc34ceb00f3e46beb329469dc7576205/img36.jpg)
Содержание слайда: Summary
CAD Tools for 2-level minimization
Quine-McCluskey Method
ESPRESSO Algorithm
NEXT LECTURE: Combinational Logic Implementation Technologies
READING: Katz 4.1, 4.2, Dewey 5.2, 5.3, 5.4, 5.5 5.6, 5.7, 6.2