ECE 3110: Introduction to Digital SystemsPrevious…Karnaugh MapsKarnaugh-map usagePrime-number detector (again)Slide 6Simplifying the Sum of ProductsExample 1Definitions :Prime-Implicant TheoremMinimal sumHow to get minimal sumNext:ECE 3110: Introduction to Digital SystemsSimplifying Sum of Productsusing Karnaugh Maps2Previous…Algebra MinimizationK-Map3Karnaugh MapsKarnaugh Map : a representation of the truth table by a matrix of squares (cells) , where each square corresponds to a minterm ( or a maxterm) of the logic function.For n-variable function, we need 2^n rows truth table and 2^n squares (cells).The square number is equivalent to the row number in the truth tableTo represent a logic function, the truth table values are copied into their corresponding cells .The arrangements of the squares help to identify the input variable redundancy ( X.Y.Z+X.Y.Z’=X.Y )4Karnaugh-map usagePlot 1s corresponding to minterms of function.Circle largest possible rectangular sets of 1s.# of 1s in set must be power of 2OK to cross edgesRead off product terms, one per circled set.Variable is 1 ==> include variableVariable is 0 ==> include complement of variableVariable is both 0 and 1 ==> variable not includedCircled sets and corresponding product terms are called “prime implicants”Minimum number of gates and gate inputs5Prime-number detector (again)6When we solved algebraically, we missed one simplification -- the circuit below has three less gate inputs.7Simplifying the Sum of Products Two main steps :1) Combining/Grouping the 1-cells.2) Writing the product term for each group.Rules : ( for n-variable function )1) The group size must be a power of 2.2) A set of 2^i cells can be combined if there are ( i ) variables that take all possible combinations within the set and the remaining ( n-i ) variables have the same value within that set.3) The corresponding product term for each group contains (n-i) literals: - The variable is complemented if it is 0 in the combined cells - The variable is uncomplemented if it’s 1 in the combined cells - The variable is not included in the product term if it takes the values 0 and 1 within the combined cells8Example 1The canonical sum is : F=X’Y’Z’+X’YZ’+XY’Z’+XY’Z+XYZ’Combine cells (0,2,6,4)X=0,1 , Y= 0,1 , Z=0Product Term : Z’Combine cells ( 4,5 )Z=0,1 , Y=0 , X=1Product Term : XY’F= XY’+Z’01 3 2XYZXZ1 10 000 01017 610115 41110Y9Definitions :A logic function P implies a logic function F if for every input combination for which P=1, then F=1 also. ( P is an implicant of F, P implies F, p=>F, F includes P, or F covers P )Any minterm or combination of minterms in the canonical sum expression is an implicant of the output functionA prime implicant is a group of combined minterms that cant be combined with any other minterm or group of minterms (a circled set)Distinguished 1-cell: is an input combination that is covered by only one prime implicant. (a unique minterm)Essential prime implicant is a prime implicant which covers one or more distinguished 1-cells (i.e. at least one minterm isn’t contained in any other prime implicant.)A minimal sum of a logic function is a sum-of-products expression for F such that no sum-of-products expression for F has fewer product terms.In Example 1 : - X’Y’Z’ , (X’Y’Z’+XYZ’) , XY’ are implicants of F - XY’ , Z’ are prime implicants and essential prime implicants10Prime-Implicant TheoremA minimum sum is a sum of prime implicants.Complete sum: sum of all the prime implicants of a logic function.Complete sum is not always minimal.Which prime implicants should be included and which should not be included in the minimum sum?11Minimal sumEssential prime implicants (if available) must be included.Secondary essential prime implicants must be included.If a logic function with no essential prime implicants at all.Trial and errorBranching method12How to get minimal sumLoad the minterms and maxterms into the K-map by placing the 1’s and 0’s in the appropriate cells.Look for groups of minterms and write the corresponding product terms ( the prime implicants): a- The group size should be a power of 2. b- Find the largest groups of minterms first then find smaller groups of minterms until all groups are found and all 1-cells are covered.Determine the essential prime implicants.Select all essential prime implicants and the minimal set of the remaining prime implicants that cover the remaining 1’s. It’s possible to get more than one equally simplified expressionif more than one set of the remaining prime implicants contains the same number of minterms.13Next:Simplifying Products of sums (POS)Other minimizationRead Ch. 4.3.6--4.5HW