Set 1 Combinational Logic & Boolean Algebra Review PDF

Combinational Logic & Boolean Algebra Dr. Hani Saleh Outline Combinational logic review Boolean Algebra Minimization –Max term, min term –K-map Example 2  How many combinations we can have? Figure 2.1 Block diagram symbol for combinational logic having...

Combinational Logic & Boolean Algebra Dr. Hani Saleh Outline Combinational logic review Boolean Algebra Minimization –Max term, min term –K-map Example 2  How many combinations we can have? Figure 2.1 Block diagram symbol for combinational logic having four inputs and three outputs. 3 Figure 2.2 Schematic symbols and Boolean relationships for some common logic gates. 4 5 6 DeMorgan’s Law (x · y)´ = x´ + y´ (DeMorgan’s Theorem) (x + y)´ = x´ · y´ 7 Figure 2.10 Theorems for minimizing Boolean expressions. 8 Figure 2.12 Boolean relationships for the exclusive-or operation. Which Gate is universal Gate? 9 Universal Gates Universal Gates: A universal gate is a gate which can implement any Boolean function without need to use any other gate type. NAND Gate is a Universal Gate: To prove that any Boolean function can be implemented using only NAND gates, we will show that the AND, OR, and NOT operations can be performed using only these gates. 10 Universal Gates Homework: Prove that the NOR gate is a universal gate? 11  Circuit Transformation Why do we need to use NAND, NOR And not AND/OR? CMOS is inverted Logic 12 Figure 2.48 Circuit transformations to obtain a NAND/Inverter realization of an SOP expression. We prefer NAND over NOR gate, why? 13 Figure 2.49 Circuit transformations to obtain a NOR/Inverter realization of a POS expression. 14 General Design Procedure for Combinational Logic 1. Understand the Problem 4. Technology Mapping What is the circuit supposed to do? Draw a logic diagram using Write down inputs (data, control) and ANDs, ORs, and inverters outputs Map the logic diagram into the Draw a block diagram or other picture selected technology – ROM, PAL, PLA – Mux, decoder and OR-gate 2. Formulate the Problem using a – Discrete gates Suitable Design Representation Considerations: cost, delays, fan- Truth tables or waveform diagrams in, fan-out are typical 5. Follow the Implementation May require encoding of symbolic Procedure inputs and outputs K-maps for two-level, 3. Logic Minimization multi-level Minimize the output functions Design tools and hardware using K-map or Boolean algebra description language (e.g., Verilog) 6. Verification –Verify the correctness of the design, either manually or using simulation 15 SOP & POS 16 Synthesis Using AND, OR, and NOT Gates Definitions F(a,b,c)=a’b’c+ab Variables: a,b,c Variable – Represents a quantity (0 or 1); typically inputs Literal: a,a’,b,b’,c Literal – Appearance of a variable (repetition included) Product Term Product: a’b’c, ab – Product of literals Minterm: a’b’c Minterm – product term whose literals include every ab abc variable of the function exactly once in true abc’ or complemented form Sum-of-Products (SOP) form Sum-of-Products: a’b’c+ab – ORing of product terms; abc + abc’ – Note: (a + b)c is not in SOP form  Synthesis Using AND, OR, and NOT Gates Sum-of-Products Form Sum-of-product form – Function can be represented as minterm ANDed with corresponding value of f – Only minterms that correspond to row with F = 1 appear in resulting expression More concise form uses row-number subscripts to specify a given function Σ symbol denotes logical sum  Synthesis Using AND, OR, and NOT Gates Sum-of-Products Form Derive sum-of-product form for the following truth table F = m1 · 1 + m4 · 1 + m5 ·1 + m6 · 1 F = m1 + m4 + m5 + m6 F = x1’x2’x3 + x1x2’x3’ + x1x2’x3 + x1x2x3’ F(x1, x2, x3) = Σ(m1, m4 , m5 , m6) F(x1, x2,x3) = Σ(1, 4, 5, 6)  Synthesis Using AND, OR, and NOT Gates Maxterm Maxterms – Complement of minterm m0’ = M0 – DeMorgan’s Theorem – (xy)’ = x’ + y’ List of maxterms for 3-input table listed below – Notation Mi denotes maxterm for a particular row  Synthesis Using AND, OR, and NOT Gates Maxterm Principle of duality – Given a logic expression, its dual is obtained by replacing all “·” operators with “+” operators, inverting variables and replacing all 0’s with 1’s – The dual of any true statement is also true Possible to synthesize function f by considering all rows where f=1(sum-of-products form) Principle of duality also suggests possible to synthesize function f by considering all rows where f=0 – Product-of-sums forms  Synthesis Using AND, OR, and NOT Gates Product-of-Sum Form Product-of-sum form – Function can be represented as maxterms with corresponding value of f=0 ANDed together More concise form uses row-number subscripts to specify a given function Π symbol denotes logical sum  Synthesis Using AND, OR, and NOT Gates Product-of-Sum Form Derive product-of-sum form for the following truth table  Synthesis Using AND, OR, and NOT Gates Product-of-Sum Form Derive product-of-sum form for the following truth table F(x1, x2,x3) = ∏(M0,M2,M3,M7 F(x1, x2,x3) = ∏(0,2,3,7)  Synthesis Using AND, OR, and NOT Gates Product-of-Sum Form Is sum-of-products and product-of-sums really equivalent? Matches K-MAPS 26 Two Variables K-map -Example Fill in each cell with corresponding x1 x2 f value of F 0 0 1 Draw circles around adjacent 1’s 0 1 1 –Groups of 1, 2 or 4 1 0 0 Circle indicates optimization 1 1 1 opportunity –We can remove a variable To obtain function OR all product Truth table x1 terms contained in circles x2 0 1 –Make sure all 1’s are in at least one circle 0 1 0 f = x2 + x1 1 1 1 Generalized Three Variables K-map x1 x2 x3 Three Variable K-map x1x2 0 0 0 m0 x3 00 01 11 10 0 0 1 m1 0 m0 m2 m6 m4 0 1 0 m2 0 1 1 m3 1 m1 m3 m7 m5 1 0 0 m4 1 0 1 m5 (b) Karnaugh map 1 1 0 m6 REMEMBER: K-map graphically place minterms 1 1 1 m7 next to each other when they differ by one variable m2 cannot be placed next to m4 (x1’x2x3’, x1x2’x3’) (a) Truth table m2 can be placed next to m6 (x1’x2x3’, x1x2x3’) m6 can be placed next to m4 (x1x2x3’, x1x2’x3’) Generalized Three Variables K-map … cont. Circles can cross left/right sides –Remember, edges are adjacent –Minterms differ in one variable only Circles must have 1, 2, 4, or 8 cells – 3,5, or 7 not allowed –3/5/7 doesn’t correspond to algebraic transformations that combine terms to eliminate a variable Circling all the cells is OK –Function just equals 1 Generalized Three Variables K-map … cont. Two adjacent 1s means one variables can be eliminated –Same as in two-variable K-maps Four adjacent 1s means two variables can be eliminated –Makes intuitive sense – those two variables appear in all combinations, so one must be true –Draw one big circle –shorthand for the algebraic transformations above Three Variables K-map – example -1 Let us try an example x1x2 x3 00 01 11 10 0 0 0 1 1 f = x1x3 +x2x3 1 1 0 0 1 Three Variables K-map – example -1 Let us try an example x1x2 x3 00 01 11 10 0 0 0 1 1 f = x1x3 +x2x3 1 1 0 0 1 Generalized Four Variables K-map … cont. Four-variable K-map follows same principle –Left/right adjacent –Top/bottom also adjacent –Adjacent cells differ in one variable –Two adjacent 1’s mean one variable can be eliminated Four adjacent 1s means two variables can be eliminated –Eight adjacent 1s means three variables can be eliminated Generalized Four Variables K-map … cont. Four-variable K-map follows same principle –Left/right adjacent –Top/bottom also adjacent –Adjacent cells differ in one variable –Two adjacent 1’s mean one variable can be eliminated Four adjacent 1s means two variables can be eliminated –Eight adjacent 1s means three variables can be eliminated Generalized Five Variables K-map Generalized Six Variables K-map  Strategy For Minimization The cells (or squares) at the end of columns or rows of a K-Map differ by only one variable (i.e. logically adjacent). Important Note: in combining the squares in a K-Map, the following rules should be obeyed: 1. Every cell containing a 1 must be included at least once. 2. Largest possible group of squares (power of 2 only) must be formed; these are called prime implicants. This ensures that maximum number of variables is eliminated, i.e. groups formed of 2n cells eliminated n variables. 3. The 1’s must be contained in the minimum number of groups to avoid duplication. DON’T CARE & CAN’T HAPPEN Some logic cct.s do not use all of the possible input combinations the unused input combinations are called CAN’T HAPPEN. In other logic cct.s the output is correct whether the input is a 1 or a 0 these input combinations are called DON’T CARE. DON’T CARE & CAN’T HAPPEN terms are usually represented by X and may be used as 1’s or 0’s whichever result in a simpler answer. An X need not be used at all if it does not contribute to simplifying a function. DON’T CARE & CAN’T HAPPEN - Examples Example 1: Simplify the logic function with associated Don’t Cares. f ( w , x, y, z)   (1, 3, 7, 11, 15) D(w, x, y, z) = (0, 2, 5) Don’t Care f  wx  yz DON’T CARE & CAN’T HAPPEN - Examples Example 2: Simplify the logic function with associated Don’t Cares. f(w, x, y, z) = (3, 4, 5, 6, 7, 11, 12, 14) D(w, x, y, z) = (1, 9, 10, 13, 15) Don’t Care f = x+z Example 1: Design Half Adder. Given 2-bits find the sum and the carry? sum = a ⊕ b C_out= a.b Sum = ab’ + a’b = a ⊕ b C_out = ab 41 Example 2: Design Full Adder. Given 2-bits and a carry in find the sum and the carry out? (Modular design concept) a b c SOP 42 Minimization using Boolean Algebra 43 IMPLEMENTATION DEVICES PAL, PLA & ROM 44  Programable Array Logic (PAL) Programmable Array Logic (PAL) is a programmable logic device With a fixed OR array and a programmable AND array. Because only AND gates are programmable , the PAL is easier to program, but is not as flexible as the PLA. 45 Programmable logic device (PLA) A programmable logic array (PLA) is a kind of programmable logic device used to implement combinational logic circuits. The PLA has a set of programmable AND gate planes, which link to a set of programmable OR gate planes, which can then be conditionally complemented to produce an output. It has 2N AND gates for N input variables, and for M outputs from the PLA, there should be M OR gates, each with programmable inputs from all of the AND gates. This layout allows for many logic functions to be synthesized in the sum of products canonical forms. 46  Full Adder implementation Using PLA cin y x x.y x.cin y.cin S = x⊕ y ⊕cin x.y’.cin’ cout​= (x.y)+(x.cin​)+(y⋅cin​) x’.y.cin’ x.y.cin x’.y’.cin s cout Read Only Memory (ROM) Read-only memory can normally only be read ROMs are effective at implementing truth tables Any logic function can be implemented using ROMs Multiple single-bit functions embedded in a single ROM Also used in computer systems for initialization ROM doesn’t lose storage value when power is removed  ROM Example Suppose there are 11 address lines (11 inputs) (i.e., 2^11 = 2048 different addresses) Suppose there are 8 outputs ROM is 2^11 x 8 = 2 KByte =16 Kbits 49  ROM for the Implement Combinational Logic K input bits 2K words by M bits Implement M arbitrary functions of K variables Example 8 words by 5 bits: 3 A ROM Input Lines B 8 words C x 5 bits F0 F1 F2 F3 F4 5 Output Lines 50 ROM To Implement Combinational Logic F0 = … F1 = …. F2 = ……. F3 = ……… 51 ROM Example Specify a truth table for a ROM which implements: F = AB + A’BC’ G = A’B’C + C’ A B C F G H E H = AB’C’ + ABC’ + A’B’C E = A’B’C’+ABC 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 1 1 1 1 0 0 1 ROM To Implement Combinational Logic Truth Table A F F = AB + A’BC’ B G G = A’B’C + C’ C H H = AB’C’ + ABC’ + A’B’C E E = A’B’C’+ABC 0 1 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 0 1 53 Muxes, De-muxes, decoders & Encoders IMPORTANT COMBINATIONAL CIRCUITS 54 Figure 2.52 Gate-level schematic for a two- channel multiplexer circuit. 55 Figure 2.53 Schematic symbol for an n-channel multiplexer with an m-bit channel selector address. 56  Figure 2.54 Truth table and circuit for a 16-input mux implementation of a 4-bit majority function. The 4-bit majority function outputs a 1 if the majority of the input bits are 1, and it outputs 0 otherwise. 57 Figure 2.55 Gate-level schematic for an n-output de-multiplexer circuit having an m-bit destination address. 58 Figure 2.56 Schematic symbols for an encoder: (a) an encoder with an n-bit input bus and (b) an encoder with individual bit-line inputs. 59 Figure 2.57 Input–output words for a 5 : 3 encoder that indicates the number of asserted bits in the input word.(count number of ones) 60 Figure 2.58 Input–output words for an 8 : 3 priority encoder. 61 Figure 2.59 Block diagram symbols for decoders: (a) decoder with input/output busses and (b) decoder with an expanded output bus. 62 Figure 2.60 The input–output patterns for an eight-client decoder. 63 Figure 2.61 A truth table for two functions implemented by a single 4-to-16 decoder. Inputs 64 Figure 2.62 The input–output patterns for an eight-client priority decoder. 65  Backup 66