View Full Document

# Logic Synthesis

View Full Document
View Full Document

1 views

Unformatted text preview:

Logic Synthesis Sum of Products Courtesy RK Brayton UCB and A Kuehlmann 1 Representation of Boolean Functions Sum of Products A function can be represented by a sum of cubes products f ab ac bc Since each cube is a product of literals this is a sum of products SOP representation A SOP can be thought of as a set of cubes F F ab ac bc A set of cubes that represents f is called a cover of f F1 ab ac bc and F2 abc abc abc abc bc are covers of f ab ac bc 2 SOP ac bc onset minterm ab c b a Note that each onset minterm is covered by at least one of the cubes None of the offset minterms is covered Covers SOP s can efficiently represent many practical logic functions i e for many there exist small covers Two level minimization seeks the minimum size cover least number of cubes 3 Irredundant Cubes Let F c1 c2 ck be a cover for f i e f ik 1 ci A cube ci F is irredundant if F ci f Example f ab ac bc ac bc bc Not covered ab c ac b a F ab f 4 Prime Cubes A literal j of cube ci F f is prime if F ci c i f where c i is ci with literal j of ci deleted A cube of F is prime if all its literals are prime F ac bc a F ci c i Example f ab ac bc ci ab c i a literal b deleted bc F ci c i a ac bc c Not equal to f since offset vertex is covered ac a b a 5 Prime and Irredundant Covers Definition 1 A cover is prime irredundant if all its cubes are prime irredundant Definition 2 A prime of f is essential essential prime if there is a minterm essential vertex in that prime that is in no other prime Definition 3 Two cubes are orthogonal if they do not have any minterm in common E g c1 ab c2 bc are orthogonal c1 ab c2 bc are not orthogonal 6 Prime and Irredundant Covers Example f abc bd cd is prime and irredundant abc is essential since abcd abc but not in bd or cd or ad abc bd c b a d cd Why is abcd not an essential vertex of abc What is an essential vertex of abc What other cube is essential What prime is not essential 7 PLA s Multiple Output Functions A PLA is a function f Bn Bm represented in

Unlocking...