Optimization of Digital Systems: Standard Forms and Multi-Level Techniques
Explore the fundamentals of digital systems optimization with standard forms and multi-level techniques. Learn about topics such as sum of products, product of sums, two-level circuit optimization, minterms, maxterms, functions of minterms and maxterms. Understand how to define optimal 2-level implementations of Boolean functions and more.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
ECE 352 Standard Forms and Multi-Level Optimization Digital System Fundamentals Standard Forms Multi-Level Optimization 1 1
Topics Standard Forms Sum of Products, Product of Sums Minterms and Maxterms Multi-Level Optimization Standard Forms and Multi-Level Optimization 2 2
Two-Level Circuit Optimization A circuit is n-level if the longest path from any input to output goes through n gates Assume complements of inputs are freely available Two-level optimization Attempt to find the optimal 2-level implementation(s) of a Boolean function Optimal defined in terms of literal count or gate count, etc. Standard Forms and Multi-Level Optimization Sum of Products: AND OR F = AB + BC + D Product of Sums: OR AND G = W(X + Y)(Y + Z) A B C D W X Y Z G F 3 3
Minterms A minterm is a product term (an AND) containing all variables or their complements For n-variable function, are 2n possible minterms A minterm evaluates to 1 for just one input set, so a minterm s truth table contains only a single 1 Standard Forms and Multi-Level Optimization 4 4
Functions of Minterms Can specify function as sum of minterms Use full minterms, or minterm indices Example: F = X Y Z + X Y Z + X Y Z F(X,Y,Z) = m1 + m3 + m7 = m(1,3,7) Standard Forms and Multi-Level Optimization X Y Z F 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 1 0 1 0 0 1 A function s complement includes only the minterms not included in the original F(X,Y,Z) = m1 + m3 + m7 F(X,Y,Z) = m0 + m2 + m4 + m5 + m6 = X Y Z + X Y Z + X Y Z + X Y Z + X Y Z 5 5
Maxterms A maxterm is a sum term (an OR) containing all variables or their complements For n-variable function, are 2n possible maxterms A maxterm evaluates to 0 for just one input set, so a maxterm s truth table contains only a single 0 Standard Forms and Multi-Level Optimization 6 6
Functions of Maxterms Can specify function as product of maxterms Use full maxterms, or maxterm indices Example: F = ( X + Y + Z)( X + Y + Z)(X + Y + Z) F(X,Y,Z) = M6 M4 M0 = M(0,4,6) Standard Forms and Multi-Level Optimization X Y Z F 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 0 1 A function s complement includes only the maxterms not included in the original F(X,Y,Z) = M6 M4 M0 F(X,Y,Z) = M7 M5 M3 M2 M1 = ( X+ Y+ Z ) ( X+Y+ Z) (X+ Y+ Z) (X+ Y+Z) (X+Y+ Z) 7 7
Convert Between Forms Functions can be converted between minterm and maxterm forms by using the other indices Standard Forms and Multi-Level Optimization F(X,Y,Z) = m(7,6,3,2) = M(5,4,1,0) XYZ + XY Z+ XYZ + XY Z = X+Y+ Z X+Y+Z (X+Y+ Z) (X+Y+Z) 8 8
Topics Standard Forms Sum of Products, Product of Sums Minterms and Maxterms Multi-Level Optimization Standard Forms and Multi-Level Optimization 9 9
Multi-Level Circuit Optimization A multiple-level (>2) circuit may have a cost (area) advantage over a 2-level version Boolean transformations may allow us to factor out common expressions and use fewer/smaller gates Fewer/smaller gates occupy less area But it might also be slower because of a longer path from one or more inputs to the output Standard Forms and Multi-Level Optimization Depends on our optimization goal Area, delay, etc. 10 10
Multi-Level Circuit Optimization Not necessarily optimal Unfortunately, there is no closed-form algorithmic procedure to identify the optimum circuit Optimal could be area, delay, power, etc. Use Boolean algebra to find a good implementation Group/identify common logic, factor out common terms Break function into smaller sub-functions (extraction) Optimize each sub-function and use substitution We can use software tools find near-optimal circuits But you should be able to apply the basic ideas: Fewer/smaller gates => less area More levels to the circuit => slower Standard Forms and Multi-Level Optimization Truth is, we cannot have gates with many inputs anyway Design tools may transform 9-input OR into tree of 3-input ORs 11 11
Multi-Level Optimization Example AD + AE + BCD + BCE Two 2-input AND gates Two 3-input AND gates One 4-input OR gate Two levels A D Standard Forms and Multi-Level Optimization E B C D E (A + BC)(D + E) Two 2-input AND gate Two 2-input OR gates Three levels A B C D E 12 12
ECE 352 Standard Forms and Multi-Level Optimization Digital System Fundamentals Standard Forms Multi-Level Optimization 13 13
