🗊Презентация Two-Level Logic Minimization Algorithms. Lecture 3

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Two-Level Logic Minimization Algorithms. Lecture 3, слайд №1Two-Level Logic Minimization Algorithms. Lecture 3, слайд №2Two-Level Logic Minimization Algorithms. Lecture 3, слайд №3Two-Level Logic Minimization Algorithms. Lecture 3, слайд №4Two-Level Logic Minimization Algorithms. Lecture 3, слайд №5Two-Level Logic Minimization Algorithms. Lecture 3, слайд №6Two-Level Logic Minimization Algorithms. Lecture 3, слайд №7Two-Level Logic Minimization Algorithms. Lecture 3, слайд №8Two-Level Logic Minimization Algorithms. Lecture 3, слайд №9Two-Level Logic Minimization Algorithms. Lecture 3, слайд №10Two-Level Logic Minimization Algorithms. Lecture 3, слайд №11Two-Level Logic Minimization Algorithms. Lecture 3, слайд №12Two-Level Logic Minimization Algorithms. Lecture 3, слайд №13Two-Level Logic Minimization Algorithms. Lecture 3, слайд №14Two-Level Logic Minimization Algorithms. Lecture 3, слайд №15Two-Level Logic Minimization Algorithms. Lecture 3, слайд №16Two-Level Logic Minimization Algorithms. Lecture 3, слайд №17Two-Level Logic Minimization Algorithms. Lecture 3, слайд №18Two-Level Logic Minimization Algorithms. Lecture 3, слайд №19Two-Level Logic Minimization Algorithms. Lecture 3, слайд №20Two-Level Logic Minimization Algorithms. Lecture 3, слайд №21Two-Level Logic Minimization Algorithms. Lecture 3, слайд №22Two-Level Logic Minimization Algorithms. Lecture 3, слайд №23Two-Level Logic Minimization Algorithms. Lecture 3, слайд №24Two-Level Logic Minimization Algorithms. Lecture 3, слайд №25Two-Level Logic Minimization Algorithms. Lecture 3, слайд №26Two-Level Logic Minimization Algorithms. Lecture 3, слайд №27Two-Level Logic Minimization Algorithms. Lecture 3, слайд №28Two-Level Logic Minimization Algorithms. Lecture 3, слайд №29Two-Level Logic Minimization Algorithms. Lecture 3, слайд №30Two-Level Logic Minimization Algorithms. Lecture 3, слайд №31Two-Level Logic Minimization Algorithms. Lecture 3, слайд №32Two-Level Logic Minimization Algorithms. Lecture 3, слайд №33Two-Level Logic Minimization Algorithms. Lecture 3, слайд №34Two-Level Logic Minimization Algorithms. Lecture 3, слайд №35Two-Level Logic Minimization Algorithms. Lecture 3, слайд №36Two-Level Logic Minimization Algorithms. Lecture 3, слайд №37
Скачать
Вы можете ознакомиться и скачать презентацию на тему Two-Level Logic Minimization Algorithms. Lecture 3. Доклад-сообщение содержит 37 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Lecture 3 Two-Level Logic Minimization Algorithms Hai Zhou ECE 303 Advanced Digital Design Spring 2002
Описание слайда:
Lecture 3 Two-Level Logic Minimization Algorithms Hai Zhou ECE 303 Advanced Digital Design Spring 2002

Слайд 2


Outline CAD Tools for 2-level minimization Quine-McCluskey Method ESPRESSO Algorithm READING: Katz 2.4.1, 2.4.2, Dewey 4.5
Описание слайда:
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 Approaches
Описание слайда:
Two-Level Simplification Approaches

Слайд 4


Review of Karnaugh Map Method
Описание слайда:
Review of Karnaugh Map Method

Слайд 5


Example of Karnaugh Map Method
Описание слайда:
Example of Karnaugh Map Method

Слайд 6


Quine-McCluskey Method
Описание слайда:
Quine-McCluskey Method

Слайд 7


Quine-McCluskey Method
Описание слайда:
Quine-McCluskey Method

Слайд 8


Quine Mcluskey Method
Описание слайда:
Quine Mcluskey Method

Слайд 9


Quine McCluskey Method (Contd)
Описание слайда:
Quine McCluskey Method (Contd)

Слайд 10


Quine-McCluskey Method (Contd)
Описание слайда:
Quine-McCluskey Method (Contd)

Слайд 11


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
Описание слайда:
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
Описание слайда:
Prime Implicant Chart

Слайд 13


Prime Implicant Chart
Описание слайда:
Prime Implicant Chart

Слайд 14


Prime Implicant Chart (Contd)
Описание слайда:
Prime Implicant Chart (Contd)

Слайд 15


Prime Implicant Chart (Contd)
Описание слайда:
Prime Implicant Chart (Contd)

Слайд 16


Second Example of Q-M Method
Описание слайда:
Second Example of Q-M Method

Слайд 17


Second Example (Contd)
Описание слайда:
Second Example (Contd)

Слайд 18


Prime Implicant Chart for Second Example
Описание слайда:
Prime Implicant Chart for Second Example

Слайд 19


Essential Primes for Example
Описание слайда:
Essential Primes for Example

Слайд 20


Delete Columns Covered by Essential Primes
Описание слайда:
Delete Columns Covered by Essential Primes

Слайд 21


Resultant Minimum Cover
Описание слайда:
Resultant Minimum Cover

Слайд 22


ESPRESSO Method
Описание слайда:
ESPRESSO Method

Слайд 23


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)
Описание слайда:
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 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
Описание слайда:
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 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
Описание слайда:
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 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
Описание слайда:
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
Описание слайда:
Espresso Algorithm

Слайд 28


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;
Описание слайда:
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 ESPRESSO
Описание слайда:
Need for Iterations in ESPRESSO

Слайд 30


ESPRESSO Example
Описание слайда:
ESPRESSO Example

Слайд 31


Example of ESPRESSO Input/Output
Описание слайда:
Example of ESPRESSO Input/Output

Слайд 32


Two-Level Logic Design Approach
Описание слайда:
Two-Level Logic Design Approach

Слайд 33


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
Описание слайда:
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
Описание слайда:
SOP and POS Forms

Слайд 35


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
Описание слайда:
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
Описание слайда:
Two Level Logic Forms

Слайд 37


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
Описание слайда:
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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию