E1.2 Digital Electronics I 5.1 Cot 2007 E1.2 Digital Electronics I Cot 2007

Points Addressed in this Lecture Standard form of Boolean Expressions– Sum-of-Products (SOP), Product-of-Sums (POS)– Canonical formLecture 5: Logic Simplication &Karnaugh Map Boolean simplification with Boolean Algebra Boolean simplification using Karnaugh Maps “Don’t cares”Professor Peter CheungDepartment of EEE, Imperial College London(Floyd 4.5-4.11)(Tocci 4.1-4.5)E1.2 Digital Electronics I5.1Cot 2007E1.2 Digital Electronics IForms of Boolean ExpressionsCot 2007Canonical Form Sum-of-products form (SOP)– first the product (AND) terms are formed then theseare summed (OR)– eg: ABC DEF GHI Product-of-sum form (POS)– first the sum (OR) terms are formed then the productsare taken (AND)– eg: (A B C) (D E F) (G H I) Canonical form is not efficient but sometimesuseful in analysis and design In an expression in canonical form, everyvariable appears in every termf(A, B,C, D) ABCD ABCD ABCD– note that the dot (meaning AND) is often omitted It is possible to convert between these two formsusing Boolean algebra (DeMorgan’s)E1.2 Digital Electronics ICot 2007E1.2 Digital Electronics ICot 2007

– An SOP expression can be forced into canonical formby ANDing the incomplete terms with terms of theform (X X ) where X is the name of the missingvariable– eg:f ( A, B, C) AB BC Previous example: Construct the truth table for this function– use a 0 when the variable is complemented, 1 otherwisef ( A, B , C ) ABC ABC ABCR o w N u m ber01234567 AB(C C) ( A A) BC ABC ABC ABC ABC ABC ABC ABCA00001111B00110011C01010101f00010011– f can be written as the sum of row numbers having TRUE minterms– The product term in a canonical SOP expression iscalled a 'minterm'E1.2 Digital Electronics IA Notation using Canonical Formf ( 3,6,7 )Cot 2007Simplifying Logic CircuitsE1.2 Digital Electronics ICot 2007Method 1: Minimization by Boolean Algebra First obtain one expression for the circuit, then try to simplify. Example: Make use of relationships and theorems to simplifyBoolean Expressions– perform algebraic manipulation resulting in acomplexity reduction– this method relies on your algebraic skill– 3 things to try Two methods for simplifying– Algebraic method (use Boolean algebra theorems)– Karnaugh mapping method (systematic, step-by-step approach)E1.2 Digital Electronics I5.7Cot 2007E1.2 Digital Electronics ICot 2007

a) Grouping– Given b) Multiplication by redundant variablesA AB BC– write it as– then apply– Multiplying by terms of the form A A does notalter the logic– Such multiplications by a variable missing from a termmay enable minimization– eg:AB AC BC AB ( C C ) AC BCA(1 B ) BC1 B 1 ABC ABC AC BC BC (1 A ) AC (1 B )– Minimized formA BCE1.2 Digital Electronics I BC ACCot 2007E1.2 Digital Electronics ICot 2007Example of Logic DesignDesign a logic circuit having 3 inputs, A, B, C will have itsoutput HIGH only when a majority of the inputs are HIGH. c) Application of DeMorgan's Theorem– Expressions containing several inversions stacked one uponthe other may often by simplified by applying DeMorgan'sTheorem.– DeMorgan's Theorem "unwraps" the multiple inversion– eg:Step 1 Set up the truth tableABC ACD BC ( A B C ) ( A C D ) BC ( A B C D ) BCE1.2 Digital Electronics IStep 2 Write the AND term forABCx0000001001000111 ABC ( A B C D)each case where the output10001011 ABCDis a 1.1101 A BC ABC1111 ABCCot 2007E1.2 Digital Electronics I5.12Cot 2007

Step 5 Implement the circuitStep 3 Write the SOP form the outputStep 4 Simplify the output expressionx ABC A BC AB C ABCx ABC ABC A BC ABC AB C ABC BC ( A A) AC ( B B ) AB (C C ) BC AC ABE1.2 Digital Electronics I5.13Cot 2007E1.2 Digital Electronics I5.14Cot 2007Minimization by Karnaugh Maps– 4 Variable example What is a Karnaugh map?AB\CD– 3 Variable Example:A\BC000111011– A grid of squares– Each square represents one mintermA . B . C , bottom-right represents0111?1000100 eg: top-left represents001110A. B. C– The minterms are ordered according to Gray code– The square marked ? representsA . B.C . D– The square marked ? representsA . B.C. D only one variable changes between adjacent squares– Squares on edges are considered adjacent to squares on oppositeedges– Karnaugh maps become clumsier to use with more than 4 variablesE1.2 Digital Electronics ICot 2007– Note that they differ in only the C variable.E1.2 Digital Electronics ICot 2007

Filling out a Karnaugh MapMinimization Technique Write the Boolean expression in SOP form For each product term, write a 1 in all the squares whichare included in the term, 0 elsewhere Minimization is done by spotting patterns of 1's and 0's Simple theorems are then used to simplify the Booleandescription of the patterns Pairs of adjacent 1's– canonical form: one square– one term missing: two adjacent squares– two terms missing: 4 adjacent squares Eg:– remember that adjacent squares differ by only one variable– hence the combination of 2 adjacent squares has the formP(A A)X A BC A B C AB C ABCA\BC000111– this can be simplified (from before) to just P100001010111E1.2 Digital Electronics ICot 2007E1.2 Digital Electronics ICot 2007X A BC AB C ABC ABC Take out previous example (Slide 12) “Cover” all the 1’s with maximum grouping:A\BC000111100001010111the adjacent squares A B C and A B C differ only in A– hence they can be combined into just BC– normally indicated by grouping the adjacent squares to becombinedA\BC000111100001010111 The simplified Boolean equation is one that sums all the termscorresponding to each of the group:X AC BC AB Adjacent Pairs– The same idea extends to pairs of pairsE1.2 Digital Electronics ICot 2007E1.2 Digital Electronics ICot 2007

More examplesMore Examples of 00011001101100001111111110010010BD ABCAB C DE1.2 Digital Electronics IE1.2 Digital Electronics I5.23Cot 2007E1.2 Digital Electronics I5.22Cot 2007Cot 2007E1.2 Digital Electronics I5.24Cot 2007

Complete Simplification Process1. Construct the K map and place 1s and 0s in the squaresaccording to the truth table.2. Group the isolated 1s which are not adjacent to any other1s. (single loops)3. Group any pair which contains a 1 adjacent to only oneother 1. (double loops)4. Group any octet even if it contains one or more 1s that havealready been grouped.5. Group any quad that contains one or more 1s that have notalready been grouped, making sure to use the minimumnumber of groups.6. Group any pairs necessary to include any 1s that have notyet been grouped, making sure to use the minimum numberof groups.7. Form the OR sum of all the terms generated by each group.E1.2 Digital Electronics I5.25Cot 2007E1.2 Digital Electronics IDon’t Care Conditions5.26Cot 2007More “Don’t Care” examples In certain cases some of the minterms may never occuror it may not matter what happens if they do– In such cases we fill in the Karnaugh map with and X“Don’t care” conditions should be changed to either 0 or 1to produce K-map looping that yields the simplestexpression. meaning don't care– When minimizing an X is like a "joker" X can be 0 or 1 - whatever helps best with the minimization– Eg:A\BC000111100001X10011– simplifies to B if X is assumed 1X BE1.2 Digital Electronics ICot 2007E1.2 Digital Electronics I5.28Cot 2007

The Karnaugh Map with 5 variablesOPENE1.2 Digital Electronics I M F1 M F 3 M F 25.29Cot 2007 Compared to the algebraic method, the K-map process is amore orderly process requiring fewer steps and alwaysproducing a minimum expression. The minimum expression in generally is NOT unique. For the circuits with large numbers of inputs (larger thanfour), other more complex techniques are used.5.315.30Cot 2007SummaryK Map Method SummaryE1.2 Digital Electronics IE1.2 Digital Electronics ICot 2007 SOP and POS –useful forms of Boolean equations Design of a comb. Logic circuit(1) construct its truth table, (2) convert it to a SOP, (3)simplify using Boolean algebra or K mapping, (4)implement K map: a graphical method for representing a circuit’struth table and generating a simplified expression “Don’t cares” entries in K map can take on values of 1or 0. Therefore can be exploited to help simplificationE1.2 Digital Electronics I5.32Cot 2007

E1.2 Digital Electronics I 5.29 Cot 2007 OPEN M F1 M F3 M F2 E1.2 Digital Electronics I 5.30 Cot 2007 The Karnaugh Map with 5 variables E1.2 Digital Electronics I 5.31 Cot 2007 K Map Method Summary Compared to the algebraic method, the K-map process is a more orderly process requiring fewer steps and always producing a minimum expression.