Boolean Algebra - Chapter 2 PDF

Digital systems Chapter 2 1 Boolean algebra Dr. Iness NEDJI MILAT [email protected] First year – 2024/2025 2 Introduction  Digital system is a combination of several circuits (electronic dev...

Digital systems Chapter 2 1 Boolean algebra Dr. Iness NEDJI MILAT [email protected] First year – 2024/2025 2 Introduction  Digital system is a combination of several circuits (electronic devices),  These circuits are designed and their behaviors are analyzed using Boolean algebra, a mathematical discipline.  Named after George Boole (1815-1864)  An English mathematician, who was the first to develop and describe a formal system for working with truth values.  Boolean logic is a branch of mathematics that deals with rules for manipulating the two logical truth values true (1) and false (0).  Set of electronic elements 3 Boolean Algebra (logic gates)  A digital circuit can be represented as a black box with inputs (signals that are provided to the circuit) and outputs (signals that the circuit produces in response to those inputs). Logic Bloc. Inputs. Outputs....  Boolean Algebra is the mathematical logic used for understanding existing circuits or designing new circuits.  It is used to describe the relationship between inputs and outputs using basically three logical operators :  AND A S S = F (A,B,C) = A.B + B.C  OR B F  NOT (unary) C Algebraic expression 4 Boolean Algebra : Basic operators NOT operator Result is 1 only if operand is 0 𝑨 𝑨 Inversion or negation of the value 0 1 Notation: A 1 0 𝑨 𝑩 𝑨 𝑩 AND operator 0 0 0 result is 1 only if both operands (variables) are 1 0 1 0 also known as logical product notation: A  B 1 0 0 1 1 1 𝑨 𝑩 𝑨+𝑩 OR operator 0 0 0 result is 1 if either of the operands (variables) is 1 0 1 1 also known as logical sum notation: A + B 1 0 1 1 1 1 5 Boolean Algebra: Useful Laws 1. Operations with 0 and 1 (Identity and Annulment Laws): X+0=X X 1=X X+1=1 X 0=0 2. Idempotent Law: X+X=X X X=X 3. Involution Law: (𝑿) = X 4. Complementarity Law : X +𝑿 = 1 X 𝑿 =0 6 Boolean Algebra: Useful Laws 5. Commutative Law : X+Y=Y+X X Y=Y X 6. Associative Law : (X + Y) + Z = X + (Y + Z) (X Y) Z = X (Y Z) =X+Y+Z =X Y Z 7. Distributive Law : X (Y+ Z) = (X Y) + (X Z) X + (Y Z) = (X + Y) (X + Z) 7 Boolean Algebra: Theorems Useful for simplifying algebraic expressions (boolean equations) 1. Expansion Theorem : X Y + X 𝒀 = X (X + Y) (X + 𝒀) = X 2. Absorption Theorem :  X+X Y=X  X (X + Y) = X  (X + 𝒀 ) Y = X Y  (X 𝒀) + Y = X + Y 8 Boolean Algebra : Proving Theorems EX1: Prove the expansion theorem: X Y + X Y = X X ( Y + 𝐘) = X Distributive X 1 =X Complement X =X Identity EX2: Prove the absorption theorem: X + X Y = X X 1+X Y =X Identity X (1+Y) =X Distributive X 1 =X Identity X =X Identity 11 9 Boolean Algebra : DeMorgan’s Law 𝑿 𝒀 𝑿+𝒀 𝑿 𝒀 𝑿𝒀 NOR (Not OR) is equivalent to AND with inputs complemented 0 0 1 1 1 1 0 1 0 1 0 0 (𝑿 + 𝒀) = 𝑿 𝒀 1 0 0 0 1 0 1 1 0 0 0 0 𝑿 𝒀 𝑿𝒀 𝑿 𝒀 𝑿+𝒀 NAND (Not AND) is equivalent to OR 0 0 1 1 1 1 with inputs complemented 0 1 1 1 0 1 (𝑿 𝒀) = 𝑿 + 𝒀 1 0 1 0 1 1 1 1 0 0 0 0 These are conversions between different types of logic functions They can prove useful if you do not have every type of gate 10 Boolean Algebra : Example of use  Simplify the function of F by using Boolean algebra laws and theorems: F(A,B,C,D) = A’.B’.C’ + A.B’.C’ + A’.B’.D Boolean function describing a circuit with 15 gates !! (7 Not, 6 And, 2 Or operations) Solution : F(A,B,C,D) = A’B’C’ + AB’C’ + A’B’D (we can omit the and notation (.)) = (A’+ A)B’C’ + A’B’D Distributive = B’C’+A’B’D Complementarity = B’(C’+A’D) Distributive Simplified function describing the same circuit but with only 6 gates. (3 Not, 2 And, 1 Or operations)  Abstract vs. Implementation 11  Computers are built around the idea of two states :  true and false  on and off  1 and 0  Computers, as we know them today, are implementations of Boole’s Laws of Thought (binary logic)  Boolean Algebra is used for understanding or designing electronic circuits by describing the interconnections between their inputs and outputs.  These electronic circuits (called logic circuits)  use voltages to represent logical values (1 or 0)  perform logical operations on boolean variables. Function/Behaviour 12 Transistors  Problem: How to achieve a hardware implementation of binary logic?  Solution: Use Transistors  Computers are built from very large numbers of very small structures: transistors  Intel’s Pentium IV microprocessor, 2000, was made up of more than 42 million MOS transistors  The 11th generation Intel Core i9, 2021, is made up of more than tens of billions MOS transistors  Apple’s M1 Max, 2021, is made up of more than 56 billion MOS transistors 13 MOS Transistor  MOS Transistor (Metal Oxide Semi-conductor transistor) is an electronic device primarily composed of three terminals:  Gate: Controls the flow of current between the other two terminals.  Source: The terminal where current enters the transistor.  Drain: The terminal where current exits the transistor.  The transistor operates “logically,” very similar to the way wall switch work  Applying a voltage to the gate can control the flow of current (On/Off) between the source and drain. 14 Different Types of MOS Transistors There are two types of MOS transistors: n-type and p-type  N-type :  The gate is normally "open" (does not conduct current) when no voltage (0v) is applied.  Applying a voltage (3v) to the gate can “close" the transistor, creating a channel between the source and drain and allowing current to flow.  P-type :  The gate is normally “close" (conducts current) when no voltage (0v) is applied.  Applying a voltage (3v) to the gate can “open" the transistor, preventing current flow between source and drain. 15 How Does a Transistor Work? Implementation using switches  The lamp can be turned on and off by simply manipulating the switch to make or break the closed circuit A Z A Z Z  A  Compose switches into more complex ones (Boolean functions): B A A Z  A and B = A.B Z  A or B = A+B OR AND B  Instead of switch, we could use MOS transistor to make or break the closed circuit. 16 How does a n-type transistor Work?  The n-type transistor in a circuit with a battery and a lamp (not realist example) 3 Volt 0 Volt Power Supply Power Supply Drain The circuit is closed Gate when the gate is supplied with 3V n-type Source 17 How does a p-type transistor Work?  The p-type transistor works in exactly the opposite fashion from the n-type transistor 00 3Volt Volt 3 0Volt Volt Power Supply Power Supply Source Drain The circuit is closed Gate when the gate is not supplied (0V) p-type Source Drain 18 Transistors vs Logic Gates vs Circuit  Now, we know how a transistor works  How do we build logic structures (circuits) out of transistors? 1. We construct basic logical units out of MOS transistors. Logic gates They implement logical oprations (NOT, AND, OR, NAND, NOR,..) 2. We construct logical Circuit out of logic gates to perform more complicated tasks. Algebraic expression Boolean Function Truth table 19 Logic Gates (Boolean operations) 20 CMOS NOT Gate (Inverter) 3V 3V 3V Out (Y) Y = 0V A= 3V P A Y In (A) Out (Y) 0V NOTN 0V 𝑌=𝐴 3V 3V A 0V Y  This is actually the CMOS NOT Gate (Complementary MOS = n-type Out (Y) Y = 3V Y += p-type) A 0V  Why do we call it NOT? A Y  If A = 0V then Y = 3V 0 1 0V 0V 1 0  If A = 3V then Y = 0V A P N Y  Digital circuit: one possible interpretation 0 ON OFF 1  Interpret 0V as logical (binary) 0 value 1 OFF ON 0  Interpret 3V as logical (binary) 1 value  NOT CMOS NOT, NAND, AND Gates 21 A Y A A A Y Y Y Y=A B B A Y A B Y A B Y 0 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 1 3V 3V 3V 3V P1 P2 P1 P2 P3 P Out (Y) Out (Y) In (A) Out (Y) In (A) N1 In (A) N1 N3 N In (B) N2 In (B) N2 0V 0V 0V 0V  Logic GATES Name Symbol Function Truth Table 22 A B X A X=A B 0 0 0 AND X or 0 1 0 1 0 0 B X = AB 1 1 1 A B X A 0 0 0 OR X X=A+B 0 1 1 1 0 1 B 1 1 1 A X NOT A X X = A’ 0 1 1 0 A X 0 0 Buffer A X X=A 1 1 A B X A 0 0 1 NAND X X = (AB)’ 0 1 1 1 0 1 B 1 1 0 A B X A 0 0 1 NOR X X = (A + B)’ 0 1 1 0 0 0 B 1 1 0 A B X A X=AB XOR X or 0 0 0 1 0 1 Exclusive OR 1 0 1 B X = A’B + AB’ 1 1 0 A B X A X = (A  B)’ XNOR X or 0 0 0 1 1 0 Exclusive NOR B X = A’B’+ AB 1 0 0 or Equivalence 1 1 1 23 Logic Circuit (Boolean function) 24 Types of circuit  A logic circuit is composed of : Input(s) Output(s)  Inputs : each input maybe 0 or 1 Logic block  Outputs : each input maybe 0 or 1  Logic block : contains the logic gates.  Two types of circuit :  Combinational (arithmetic and logical operations)  The output depends only on the present values of the inputs. Output = F (Inputs)  Sequential (storage (bits of SRAM))  The output depends on present input values and past output value Output (t) = F (Inputs(t), Output (t-1)) 25 Boolean function vs logic block Implements a Boolean function Input(s) Logic block Output(s) (Gates)  Boolean function describes relationship between inputs and outputs : Output = F (Inputs)  For each output of the circuit, there corresponds a specific function.  The same input values produce the same output value every time  Boolean function specifies how the inputs are connected together using logical operators (gates) to produce the desired outputs.  A Boolean function may be represented as:  An algebraic expression  A truth table 26 Boolean function : as an Algebraic Expression For example : X Y F S Z S = X + Y ·Z  Variable S (Output) is a function of X, Y, and Z, can also be written as : S = F (X, Y, Z) = X + Y. Z  The RHS of the equation is called an algebraic expression.  The symbols X, Y, Z are the literals of the Boolean function.  For a given Boolean function, there may be more than one algebraic expressions S=X+Y·Z S=X+Y·Z+Z.Z S=X.(Y+Y)+Y·Z S=X.Y+X.Y +Y·Z 27 Boolean function : as a Truth Table Truth table: shows what is the output X of the circuit for each possible input F Y S Z X Y Z S 0 0 0 0 0 S = F (X, Y, Z) = X + Y · Z 1 0 0 1 1 2 0 1 0 0 The number of rows in the truth table is equal 3 0 1 1 0 to 2n, where n is the number of literals in the 4 1 0 0 1 function (inputs). 5 1 0 1 1 The combinations of 0s and 1s for rows of this 6 1 1 0 1 table are obtained from the binary numbers by 7 1 1 1 1 counting from 0 to 2n-1 28 Canonical Forms of Boolean function  A Boolean function can have many alternative algebraic expressions  Different Boolean expressions lead to different gate realizations (several designs) Problem  But, many alternative Boolean expressions have the same truth table.  A Boolean function has a unique Truth table signature Problem  But, it becomes an expensive representation when dealing with a large number of inputs (>4)  Solution : use a Canonical form (standard) to represent a Boolean expression  It provides a unique algebraic signature and it isn’t an expensive representation.  There are two-level canonical forms : Minterms SOP Form Ex : F(A,B,C) = ABC + A’BC + A’BC’ +.. Sum Of Products POS Form Ex : G(A,B,C) = (A+B+C). (A+B’+C’).. Product Of Sums Maxterms  Some Definitions 29  Variable : 𝑨 ,𝑩 ,𝑪  Complement: variable with a bar over it 𝑨,𝑩,𝑪  Literal: variable or its complement 𝑨, 𝑨,𝑩,𝑩,𝑪,𝑪  Implicant: product (AND) of literals (𝑨 ∙ 𝑩 ∙ 𝑪) , (𝑨 ∙ 𝑪) , (𝑩 ∙ 𝑪)  Minterm: product (AND) that includes all input variables (𝑨 ∙ 𝑩 ∙ 𝑪) , (𝑨 ∙ 𝑩 ∙ 𝑪) , (𝑨 ∙ 𝑩 ∙ 𝑪)  Maxterm: sum (OR) that includes all input variables (𝑨 + 𝑩 + 𝑪) , (𝑨 + 𝑩 + 𝑪) , (𝑨 + 𝑩 + 𝑪) 30 Sum of Products Form (SOP) More used Also known as Disjunctive normal form or Minterm expansion Example : 𝐀 𝐁 𝐂 𝐅 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 c = 𝐀. 𝐁. 𝐂 + 𝑭 c 𝐀. 𝐁. 𝐂 c c 𝐀. 𝐁. 𝐂 + c 𝐀. 𝐁. 𝐂 + 𝐀. 𝐁. 𝐂 + 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 Minterm 1 0 1 1 1 1 0 1 1 1 1 1 Idea of canonical SOP form : 1. Find all the input combinations for which the output of the function is TRUE (=1). 2. Connect the inputs of each combination with AND gates to get Minterm (Product of all Inputs). Input value =1 means true literal (A), Otherwise (=0), complemented literal (𝐀). 3. Connect all Minterms with OR gates. 31 Shorthand notation for canonical SOP  31agree on the order of the variables in the rows of truth table… If we then we can enumerate each row with the decimal number that corresponds to the binary number of the input pattern FULL Expression for canonical SOP 𝐀 𝐁 𝐂 𝐅 minterms 0 0 0 0 0 𝑨𝑩𝑪 = m0 1 0 0 1 0 𝑨𝑩𝑪 = m1 F = 𝑨𝐁𝐂 + 𝐀𝑩𝑪 + 𝐀𝑩𝐂 + 𝐀𝐁𝑪 + 𝐀𝐁𝐂 2 0 1 0 0 𝑨𝑩𝑪 = m2 3 0 1 1 1 𝑨𝑩𝑪 = m3 We can write F as a sum of minterms 4 1 0 0 1 𝑨𝑩𝑪 = m4 5 1 0 1 1 𝑨𝑩𝑪 = m5 F = m3 + m4 + m5 + m6 + m7 6 1 1 0 1 𝑨𝑩𝑪 = m6 7 1 1 1 1 𝑨𝑩𝑪 = m7 Or, we can use a summation notation Shorthand Notation for Minterm 110 : 𝑨𝑩𝑪 F = ∑ m(3,4,5,6,7) Shorthand Notation for canonical SOP 32 Canonical SOP vs Minimal SOP F in canonical SOP form: F(A,B,C) = ∑m(3,4,5,6,7) = m3 + m4 + m5 + m6 + m7 = 011 + 100 + 101 + 110 + 111 F = 𝐀𝐁𝐂 + 𝐀𝐁𝐂 + 𝐀𝐁𝐂 + 𝐀𝐁𝐂 + 𝐀𝐁𝐂 Canonical form ≠ Minimal form 𝑭 = 𝐀𝑩 𝑪 + 𝑪 + 𝑨𝐁𝐂 + 𝐀𝐁(𝑪 + 𝑪) = 𝐀𝑩 + 𝑨𝐁𝐂 + 𝐀𝐁 = 𝐀(𝑩 + 𝑩) + 𝑨𝐁𝐂 = 𝐀 + 𝑨𝐁𝐂 = 𝐀 + 𝐁𝐂 Minimal (Optimal) SOP form 2-Level AND/OR Realization Terms 33 Canonical SOP Forms  SOP (sum-of-products) leads to two-level logic  Example: 𝑌 = 𝐴 ∙ 𝐵 ∙ 𝐶 + 𝐴 ∙ 𝐵 ∙ 𝐶 + 𝐴 ∙ 𝐵 ∙ 𝐶 A B C A B C minterm: ABC minterm: ABC minterm: ABC Level 1 Level 2 (get minterms) (connect minterms with Or) Y Products Sum 34 Product Of Sums Form (POS) Also known as Conjunctive normal form or Maxterm expansion Example : 0 1 0 0 0 0 0 0 1 𝐀 𝐁 𝐂 𝐅 𝑭c = 𝐀 + 𝐁 + 𝐂 c. 𝐀 + 𝐁 + 𝐂 c. (𝐀 + 𝐁 + 𝐂) c 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 Maxterm 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 Idea of canonical POS form : 1. Find all the input combinations for which the output of the function is FALSE (=0). 2. Connect the inputs of each combination with OR gates to get Maxterm (Sums of all Inputs). Input value =0 means true literal (A), Otherwise (=1), complemented literal (𝐀). 3. Connect all Maxterms with AND gates. 35 Shorthand Notation of canonical POS FULL Expression for canonical POS 𝐀 𝐁 𝐂 𝐅 maxterms 0 0 0 0 0 𝑨+𝑩+𝑪 = M0 𝐅 = (𝐀 + 𝐁 + 𝐂)(𝐀 + 𝐁 + 𝐂)(𝐀 + 𝐁 + 𝐂) 1 0 0 1 0 𝑨+𝑩+𝑪 = M1 We can write F as a product of maxterms 2 0 1 0 0 𝑨+𝑩+𝑪 = M2 3 0 1 1 1 𝑨+𝑩+𝑪 = M3 F = M0. M1. M2 4 1 0 0 1 𝑨+𝑩+𝑪 = M4 5 1 0 1 1 𝑨+𝑩+𝑪 = M5 Or, we can use a Product notation 6 1 1 0 1 𝑨+𝑩+𝐂 = M6 7 𝑨+𝑩+𝑪 F= 𝑴(𝟎, 𝟏, 𝟐) 1 1 1 1 = M7 Shorthand Notation for Maxterm 100 : 𝑨 + 𝑩 + 𝑪 Shorthand Notation for canonical POS Note that the maxterms are formed around the “zeros” of the function (and the minterms around the “ones”). This is not the complement of the function (but the same function)! F POS ≠ FSOP FPOS = FSOP FPOS = Demorgan (FSOP ) ? 0 1 36 1. Useful Conversions SOP/POS  Minterm to Maxterm conversion: 1. Rewrite minterm shorthand using maxterm shorthand. 2. Replace minterm indices with the indices not already used E.g., 𝐅 𝑨, 𝑩, 𝑪 = 𝒎 𝟑, 𝟒, 𝟓, 𝟔, 𝟕 = 𝑴(𝟎, 𝟏, 𝟐).  Maxterm to Minterm conversion: 1. rewrite maxterm shorthand using minterm shorthand 2. replace maxterm indices with the indices not already used E.g., 𝐅 𝑨, 𝑩, 𝑪 = 𝑴(𝟎, 𝟏, 𝟐) = 𝒎 𝟑, 𝟒, 𝟓, 𝟔, 𝟕 37 Logic circuit Designing : Steps to follow x y z F Truth 0 0 0 0 1. Determine the truth table for problem 0 0 1 1 Table statement 0 1 0 0 0 1 1 0 2. Consider each output independently 1 0 0 1 1 0 1 1 a) Consider all nonzero entries for the 1 1 0 1 output 1 1 1 1 Boolean b) Write the logic equation (SOP) Function F = x’y’z + xy’z’ + xy’z + xyz’ + xyz c) Simplify the logic equation using the laws of Boolean algebra (if F = x + y’z possible) or Karnaugh Map method. x F Logic y 3. Draw the logic diagram (gates Diagram implementation) of the simplified logic z equation (circuit) 38 Logic Simplification: Karnaugh Maps (K-Maps) 39 Quick Recap on Logic Simplification  The original Boolean expression may not be optimal F = A’.(A + B) + (B + A.A).(A + B’)  we can reduce a given Boolean expression to an equivalent expression with fewer terms using Boolean algebra laws or karnaugh map method. F=A+B  The goal of logic simplification:  Reduce the complexity of the circuit (by minimizing the number of gates).  Reduce the implementation cost and space (get the smallest circuit with the same function).  Enhance the speed of a circuit (Reduced gate delays lead to faster circuit operation). 40 Logic Simplification  Systematic techniques for simplifications Key Tool: The Uniting Theorem — 𝑭 = 𝑨𝑩 + 𝑨𝑩 𝑭= 𝑨𝑩 + 𝑨𝑩 = 𝑨 𝑩 + 𝑩 = 𝑨 𝟏 = 𝑨 B's value changes within the rows where F=1 (“ON set”) A's value does NOT change within the ON-set rows If an input (B) can change without changing the output, that input value is not needed ➙ B is eliminated, A remains 𝑮 = 𝑨𝑩 + 𝑨𝑩 = 𝑨 + 𝑨 𝑩 = 𝑩 B's value stays the same within the ON-set rows A's value changes within the ON-set rows ➙ A is eliminated, B remains 41 Karnaugh Map (K-map) method  In 1953, Maurice Karnaugh was a telecommunications engineer at Bell Labs.  He invented a graphical way of visualizing and then simplifying Boolean expressions using Uniting theorem. Another way to represent a truth table 2-variable K-map 3-variable K-map 4-variable K-map 𝑩 0 1 𝑩𝑪 𝑪𝑫 𝑨 0 1 𝑨 00 01 11 10 𝑨𝑩 00 01 11 10 0 0 0 1 3 2 00 0 1 3 2 2 3 1 1 4 5 7 6 01 4 5 7 6 Output 12 13 15 14 11 8 9 11 10 10 The Gray Code is used to represent Numbering Scheme: 00, 01, 11, 10 42 K-map Simplification for Three Variables (1) 𝐗 𝐘 𝐙 F 𝑭 𝑿, 𝒀, 𝒁 = X’Y’Z’ + X’Y’Z + X’YZ’ + X’YZ + XY’Z’ + XYZ’ 0 0 0 0 1 = 𝒎 𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟔 1 0 0 1 1 2 0 1 0 1 𝒀𝒁 00 3 𝑿 01 11 10 0 1 1 1 4 1 0 0 1 0 1 0 1 1 1 3 1 2 5 1 0 1 0 6 1 1 0 1 1 1 4 0 5 0 7 1 6 7 1 1 1 0 Process of K-map simplification : 1. Group the adjacent cells containing 1s (for SOP) or 0s (for POS)  The number of 1s (or 0s) in a group must be a power of 2 (1,2,4,8,etc).  The goal is to form the largest possible groups  Groups can be formed only at right angles (horizontal or vertical); diagonal groups are not allowed.  Groups can overlap and wrap around the sides of the Kmap. 2. Write the simplified expression in SOP form 43 K-map Simplification for Three Variables (2) 𝐗 𝐘 𝐙 F 𝑭 𝑿, 𝒀, 𝒁 = X’Y’Z’ + X’Y’Z + X’YZ’ + X’YZ + XY’Z’ + XYZ’ 0 0 0 0 1 = 𝒎 𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟔 1 0 0 1 1 2 0 1 0 1 𝒀𝒁 00 3 𝑿 01 11 10 0 1 1 1 4 1 0 0 1 0 1 0 1 1 1 3 1 2 5 1 0 1 0 6 1 1 0 1 1 1 4 0 5 0 7 1 6 7 1 1 1 0 Process of K-map simplification : 1. Group the adjacent cells containing 1s (for SOP) or 0s (for POS) 2. Write the simplified expression in SOP form :  For each group, determine which variables are constant, and which vary across group. Eliminate varying variables, then connect the constant variables with AND (product term).  Green group : eliminate Y and Z and remain X’  Red group : eliminate X and Y and remain Z’  Combine all the product terms (for all groups) using the OR operation. F(X,Y,Z) = X’ + Z’ 44 45 K-map for 4 Input Variables 𝑪𝑫 𝑨𝑩 00 01 11 10 SOP (more used) 0 1 3 2 00 1 0 0 1 4 5 7 6 𝐅(𝐀, 𝐁, 𝐂, 𝐃) = 𝒎(𝟎, 𝟐, 𝟓, 𝟖, 𝟗, 𝟏𝟎, 𝟏𝟏, 𝟏𝟐, 𝟏𝟑, 𝟏𝟒, 𝟏𝟓) 01 0 1 0 0 12 13 15 14 11 1 1 1 1 𝐅 = 𝐀 + 𝑩𝑫 + 𝐁𝑪𝑫 8 9 11 10 10 1 1 1 1 𝑪𝑫 POS 𝑨𝑩 00 01 11 10 0 1 3 2 00 1 0 0 1 4 5 7 6 𝐅(𝐀, 𝐁, 𝐂, 𝐃) = 𝑴(𝟏, 𝟑, 𝟒, 𝟔, 𝟕) 01 0 1 0 0 12 13 15 14 𝐅 = (𝐀 + 𝑩 + 𝑪). 𝐀 + 𝑩 + 𝑫.(𝐀 + 𝑩 + 𝑫) 11 1 1 1 1 8 9 11 10 10 1 1 1 1 46 K-map Example: Two-bit Comparator A B C D F1 F2 F3 0 0 0 0 1 0 0 0 0 0 1 0 1 0 A AB = CD 0 0 1 0 0 1 0 2-bit number F1 0 0 1 1 0 1 0 B AB < CD 0 1 0 0 0 0 1 F2 0 1 0 1 1 0 0 C AB > CD 0 1 1 0 0 1 0 F3 2-bit number 0 1 1 1 0 1 0 D 1 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 Design Approach: 1 1 0 0 0 0 1 Deduce the 4-Variable K-map 1 1 0 1 0 0 1 for each of the 3 1 1 1 0 0 0 1 output functions 1 1 1 1 1 0 0 47 K-map Example: Two-bit Comparator (2) K-map for F1 A B C D F1 F2 F3 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 𝑪𝑫 00 01 11 10 2 0 0 1 0 0 1 0 𝑨𝑩 1 3 2 00 0 3 0 0 1 1 0 1 0 1 4 0 1 0 0 0 0 1 7 6 01 4 5 5 0 1 0 1 1 0 0 1 6 0 1 1 0 0 1 0 12 15 14 11 13 7 0 1 1 1 0 1 0 1 8 1 0 0 0 0 0 1 9 11 10 8 9 1 0 0 1 0 0 1 10 1 10 1 0 1 0 1 0 0 11 1 0 1 1 0 1 0 12 1 1 0 0 0 0 1 13 1 1 0 1 0 0 1 F1 = A'B'C'D' + A'BC'D + ABCD + AB'CD' 14 1 1 1 0 0 0 1 15 1 1 1 1 1 0 0 48 K-map Example: Two-bit Comparator (3) K-map for F2 0 A B C D F1 F2 F3 0 0 0 0 1 0 0 1 𝑪𝑫 00 01 11 10 0 0 0 1 0 1 0 2 𝑨𝑩 0 0 1 0 0 1 0 00 0 1 3 2 3 1 1 1 0 0 1 1 0 1 0 4 0 1 0 0 0 0 1 01 4 5 7 6 5 1 1 0 1 0 1 1 0 0 6 0 1 1 0 0 1 0 12 11 13 15 14 7 0 1 1 1 0 1 0 8 1 0 0 0 0 0 1 9 11 10 10 8 9 1 10 1 0 0 1 0 0 1 1 0 1 0 1 0 0 11 1 0 1 1 0 1 0 12 1 1 0 0 0 0 1 13 F2 = A'C + A'B'D + B'CD 1 1 0 1 0 0 1 14 1 1 1 0 0 0 1 F3 = ? (Exercise for you) 15 1 1 1 1 1 0 0 49 K-maps with “Don’t Care”  Real circuits don’t always need to have an output defined for every possible input.  For example, some calculator displays consist of 7-segment LEDs. These LEDs can display 27 -1 patterns, but only ten of them are useful.  If a circuit is designed so that a particular set of inputs can never happen, we call this set of inputs a don’t care condition.  They are very helpful to us in Kmap circuit simplification. 50 Example 1 : Seven-segment Decoder (Don’t Care) A B C D a b c d e f g 0 0 0 0 1 1 1 1 1 1 0  Don’t Care really means I don’t care what my 0 0 0 1 0 1 1 0 0 0 0 circuit outputs if this appears as input 0 0 1 0 1 1 0 1 1 0 1  You have an engineering choice to use DON’T CARE patterns 0 0 1 1 1 1 1 1 0 0 1 intelligently as 1 or 0 to better simplify the circuit 0 1 0 0 0 1 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 a 0 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 f b 1 0 0 1 1 1 1 0 0 1 1 g 1 0 1 0 x x x x x x x 1 0 1 1 x x x x x x x 1 1 0 0 x x x x x x x e c 1 1 0 1 x x x x x x x I can pick 0 or 1 for any x 1 1 1 0 x x x x x x x 1 1 1 1 x x x x x x x 51 Example 2 : BCD Increment Function (Don’t Care)  BCD (Binary Coded Decimal) digits  Encode decimal digits 0 - 9 with bit patterns 00002 — 10012  When incremented, the decimal sequence is 0, 1, …, 8, 9, 0, 1 A B C D W X Y Z 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 ABCD 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 + 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 WXYZ 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 X X X X 1 0 1 1 X X X X These input patterns should 1 1 0 0 X X X X never be encountered in practice 1 1 0 1 X X X X (hey -- it’s a BCD number!) 1 1 1 0 X X X X So, associated output values are 1 1 1 1 X X X X “Don’t Cares”  ABCD 52 K-map for BCD Increment Function + 1 WXYZ W X 𝑪𝑫 𝑪𝑫 𝑨𝑩 00 01 11 10 𝑨𝑩 00 01 11 10 00 00 1 01 1 01 1 1 1 11 X X X X 11 X X X X 10 1 X X 10 X X Y 𝑪𝑫 Z 00 01 11 10 𝑪𝑫 𝑨𝑩 𝑨𝑩 00 01 11 10 00 1 1 00 1 1 01 1 1 01 1 1 11 X X X X 11 X X X X 10 X X 10 1 X X 53 K-map for BCD Increment Function W 𝑪𝑫 𝑨𝑩 00 01 11 10 00 01 1 W(without don’t cares) = AB'C'D' + A'BCD 11 X X X X W(with don’t cares) = AD' + BCD 10 1 X X X 𝑪𝑫 𝑨𝑩 00 01 11 10 00 1 X (without don’t cares) = A'BC' + A'BD' + A'B'CD 01 1 1 1 11 X X X X X (with don’t cares) = BC‘ + BD‘ + B’CD 10 X X 54 K-map for BCD Increment Function W 𝑪𝑫 𝑨𝑩 00 01 11 10 00 01 1 W(without don’t cares) = AB'C'D' + A'BCD 11 X X X X W(with don’t cares) = AD' + BCD 10 1 X X X 𝑪𝑫 𝑨𝑩 00 01 11 10 00 1 X (without don’t cares) = A'BC' + A'BD' + A'B'CD 01 1 1 1 11 X X X X X (with don’t cares) = BC‘ + BD‘ + B’CD 10 X X 55 K-map for BCD Increment Function Y 𝑪𝑫 𝑨𝑩 00 01 11 10 00 1 1 Y (without don’t cares) = A’C'D + A'CD’ 01 1 1 11 X X X X Y (with don’t cares) = CD‘+ BC'D 10 X X Z 𝑪𝑫 𝑨𝑩 00 01 11 10 00 1 1 Z (without don’t cares) = A'D' + B'C'D’ 01 1 1 11 X X X X Z (with don’t cares) = D' 10 1 X X 56 K-map for BCD Increment Function Y 𝑪𝑫 𝑨𝑩 00 01 11 10 00 1 1 Y (without don’t cares) = A’C'D + A'CD’ 01 1 1 11 X X X X Y (with don’t cares) = CD‘+ A’C'D 10 X X Z 𝑪𝑫 𝑨𝑩 00 01 11 10 00 1 1 Z (without don’t cares) = A'D' + B'C'D’ 01 1 1 11 X X X X Z (with don’t cares) = D' 10 1 X X