Digital Electronics and Logic Design (Code : 210245) Semester III - Computer Engineering (Savitribai Phule Pune University) Strictly as per the New Choice Based Credit System Syllabus (2019 Course) Savitribai Phule Pune University w.e.f. academic year 2020-2021 J. S. Katre ME. (Electronics and Telecommunication) Formerty, Assistant Professor Department of Electronics Engineering Vishwakarma Institute of Technology (V.LT), Pune, Maharashtra, India We TechKnowledge “SP publications (Book Code POT23A) Harish G. Narula Formerly Assistant Professor (Senior) Department of Computer Engineering D. J. Sanghvi College of Engineering, Mumba Maharashtra, India PO123A Price ¢ 385/-Digital Electronics and Logic Design : (Code : 210245) (Semester II, Computer Engineering, Savitribai Phule Pune University) J. S. Katre, Harish G. Narula Copyright © by Authors. All rights reserved. No part of this publication may be reproduced, copied, or stored in a retrieval system, distributed or transmitted in any form or by any means, including photocopy, recording, or other electronic or mechanical methods, without the prior written permission of the publisher. This book is sold subject to the condition that it shall not, by the way of trade or otherwise, be lent, resold, hired out, or otherwise circulated without the publisher's prior written consent in any form of binding or cover other than which it is published and without a similar condition including, this condition being imposed on the subsequent purchaser and without limiting the rights under copyright reserved above. First Printed in India January 2002 First Edition ‘August 2020 (TechKnowledge Publications) This edition is for sale in India, Bangladesh, Bhutan, Maldives, Nepal, Pakistan, Sri Lanka and designated countries in South-East Asia. Sale and purchase of this book outside of these countries is unauthorized by the publisher. ISBN : 978-93-89889-47-5 Published by : TechKnowledge Publications Head Office : 8/5, First floor, Maniratna Complex, Taware Colony, Aranyeshwar Corner, Pune - 411 009, Maharashtra State, India Ph : 91-20-24221234, 91-20-24225678, Email : info@techknowledgebooks.com, Website : www.techknowledgebooks.com [210245] (FID : PO123) (Book Code : PO123A) (Book Code POT23A)We dedicate this Publication soulfully and wholeheartedty, in loving memory of our beloved founder director, Late Shri. Pradeepyi Lalchandji Lunawat, who will always 6e an inspiration, a positive force and strong support behind us. “My work is my prayer to God” ~ Lt. Shiri. Pradeepfi L. Lunawat Soulful Tribute and Gratitude for all Your Sacrifices, Hardwork, and 40 years of Strong Vision... (Book Code POT23A)Syllabus. Digital Electronics and Logic Design : Sem. IIl, Computer Engineering (SPPU) ‘Teaching Scheme = Examination Scheme and Marks Lecture : 03 Hrs. / Week Mid-Sem. (TH) : 30 Marks End-Sem. (TH) : 70 Marks Prerequisite Courses : 104010 : Basic Electronics Engineering Companion Course : 210249 : Digital Electronics Lab Course Objectives : The goal of this course is to impart the fundamentals of digital logic design; starting from learning the basic concepts of the different base number systems, to basic lagic elements and deriving logical expressions to further optimize a circuit diagram, Objective is to see that learners are not only able to evaluate different combinational logic designs, but also design their own digital cicuits given different parameters. To study number systems and develop skills for design and implementation of combinational logic circus and sequential circuits To understand the functionalities, properties and applicability of logic families. To introduce programmable logic devices and ASM chart and synchronous state machines. To introduce students to basics of microprocessor. Course Outcomes : (On completionof the course, learner wil be able to COL: Simplify Boolean expressions using KMap. €O2: Design and implement combinational circuits, CO3: Design and implement sequential circuits CO4: Develop simple real-world application using ASM and PLO. COS: Differentiate and Choose appropriate logic families IC packages as per the given design specifications. + Explain organization and architecture of computer system. Course Contents Unit £ Minimization Technique Logic design minimization technique : Minimization of Boolean function using K-Maps (upto 4 variables) and Quine ~ McCluskey method, Representation of signed number - Sign magnitude representation, 1's complement and 2's complement form, Sum of product and product of sum form, Minimization of SOP and POS using K-Maps. Exemplar / Case studies : Digital locks using logic gates. (Refer chapter 1) Unit Combination Logic Design : Code converter - BCD, Excess-3, Gray code, Binary code, Half-adder, Full adder, Half subtractor, Full subtractor, Binary adder (IC 7483), BCD adder, Look ahead cary generator, Multiplexers (MUX) : MUX (IC 74153, 74151), Cascading multiplexers, Demultiplexers (DEMUX) - Decoder (IC 74138, IC 74154), Implementation of SOP and POS using MUX, DMUX, Comparators (2 bit), Party generators and checker. Exemplar / Case studies : Combinational logic design of BCD to 7 segment display controller (Refer chapter 2) (Book Code POT23A)Unit Or ‘Sequential Logic Design Flip flop : SR, KD, T, Preset and clear, Master slave JK flip flops, Truth tables and excitation tables, Conversion from cone type to another type of flip lop. Registers: SISO, SIPO, PISO, PIPO, Shift registers, Bidirectional shift register, Ring counter, Universal shift register. Counters : Asynchronous counter, Synchronous counter, BCD counter, Johnson's counter, Modulus of the counter (IC 7490). Synchronous Sequential circuit Design : Models ~ Moore and Mealy, State iagram and state table, Design procedure, Sequence generator and detector. Exemplar / Case studies : Electronic Voting Machine (EV). (Refer chapters 3, 4, 5 and 6) Unit IV Algorithmic State machines and Programmable Logic Devices : Algorithmic State Machines : Finite State Machines (FSM) and ASM, ASM charts, Notations, Construction of ASM chart and realization for sequential circuits. PLD's : PLD, ROM as PLD, Programmable Logic Array (PLA), Programmable Array Logic (PAL), Designing combinational circuits using PLDs. Exemplar / Case studies : Waveform generator using MUX controller method, (Refer chapters 7 and 8) Logic Families : Classification of logic families : Unipolar and bipolar logic families, Characteristics of digital ICs : Fan-in, Fan-out, Current and voltage parameters, Noise immunity, Propagation delay, Power dissipation, Figure of Merits, Operating temperature range, Power supply requirements. Transistor - Transistor logic : Operation of TTL NAND gate (Two input), TTL with active pull Up, TTL with open collector output, Wired AND connection, Tristate TTL devices, TL characteristics. CMOS : CMOS inverter, CMOS characteristics, CMOS configurations - Wired logic, Open drain outputs. Exemplar / Case studi : To study the various basic gate design using TTLICMOS logic family. (Refer chapter 9) Unit VI Introduction to Computer Architecture : Introduction to ideal microprocessor ~ Data bus, Address bus, Control bus, Microprocessor based systems ~ Basic ‘operation, Microprocessor operation, Block diagram of microprocessor, Functional units of microprocessor ~ ALU using IC 74181, Basic arithmetic operations using ALU IC 74181, 4-bit multiplier circuit using ALU and shift registers, Memory organization and operations, Digital circuit using decoder and registers for memory operations. Exemplar / Case Studies: Microprocessor based system in Communication / Instrumentation Control (Refer chapter 10) Serre ae ce ie hu ER Mkt a euler (Book Code POT23A)table of Contents DELD (Sem_IIl/ Comp_/ SPPU) unix 1.42 _ Disadvantages of Algebraic Method of ‘Simplification at Chaptor 4: Minimization Techniques 4-4 to 4-46. 1.8 Kamaugh-Map Simplification 14 ‘Syllabus: Logic design minimization techni yllabus : Logie design minimization technique FEPEEPaEeEnaenes aa Minimization of Boolean function using K-Maps (upto 4 variables) and Quine - McCluskey method, Representation 1.52. K.map Boxes and Associated Product of signed number - Sign magnitude representation, 1's Terms 112 ‘complement and 2's complement form, Sum of product 153 semana Mtr tne Kevan 112 ‘and product of sum form, Minimization of SOP and POS using K Maps, 1.54 Truth Table toKimap 412 Exemplar / Case study: Digital locks using logic gates. 1.55 Representation of Standard SOP 4.4. System or Cireut 12 Form on K-map 113 44.4 Digital Systems 4.2 | 18) Minimization of Bootean Expressions using K-map 114 1.4.2 Types of Digital Systems 12 1.6.1 How does Simplification Takes Place ? 1-18 1.1.3 Combinational Circuit Design 13 1.2 Standard Re for Le al Funct 4-3 162 inns a ations for Logical Fun . ae eee eee said (Pairs, Quads and Octets) 1-14 1.2.4 Sumot-Products (SOP) F 14 eer 1.6.3 Grouping Two Adjacent 1 ponent 2.2 Product ofthe Sums Form (POS) 4 lait i 1 23 Standard or Canonical SOP and _PRSEPSSEEennnPeseen POS Forms 14 ‘Ones (Quad) 1.16 1.24 Conversion ofa Logie Expression to ‘Standard SOP or POS Form 15 1.6.5 Grouping Eight Adjacent 1.3. Concepts of Minterm and Maxterm 1-6 ‘Ones (Octet) AAT 1.3.1. Representation of Logical Expressions 116.6 Summary of Rules Followed for K-Map using Minterms and Maxterms 17 ‘Simpitication 118 1.3.2 Writing SOP and POS Forms fora Given | 1.7 _ Minimization of SOP Expressions Truth Table 17 (K Map Simpitfcation) 118 4.3.3 Representation of Truth Table using 41.7.4. Elimination of a Redundant Group ...1-20 Standard SOP Exoression 17 17.2. Minimization of Logic Functions not 1.34 Representation of Truth Table using Specified in Standard SOP Form .....1-24 Standard POS Exoression 18 4.7.3 Don't Care Conditions 1.22 1.8.5 Conversion from SOP to POS and Vice 4.8 Product of Sum (POS) Senpliicetion ies Versa 18 1.8.1 Kemap Representation of POS Form ... 1-25 1.4 Methods to Simpify he Boolean Functions... 1-9 1.82 Representation of Standard POS 1.4.1. Algebraic Simpiication 19 Form on Ksmap is Techknowledgtable of Contents DELD (Sem_IIl/ Comp_/ SPPU) 1.8.3 Simplification of Standard POS Form 2.1 Introduction to Combinational Circuits 22 using Kmap a 2.1.1 Analysis of a Combinational Circuit .....2-2 1.9 Quine Me-Cluskey Minimization Technique Pe 7 2.1.2 Design of Combinational Logic using (Tabular Method) 1-30 Statements 23 1.9.1 Important Definitions 131 22 Code Converters 24 4.40 Unsigned Binary Numbers 1-40 22.1 BCD to Excess 3 Converter 24 1.10.1 Important Features of Unsigned PN,“ S 1 Nat tay 222 BCD to Gray Code Converter 25 Wet etc ash ted tas 22.3 Binary to Gray Code Converter 26 1.11.1 Range of Sign-Magnitude Numbers .....1-40. 2.24 Wp ZECD Converter coal 1.12. 1's. and 2's Complements of a Binary Number ...1-41 27 Brees 3 to BCD Getprerter ano) aaa Ganglenent jax | 23). Binary Adders and Subtractors 240 1.122 Representation of Positive and Negative P31 Types of Bly Albers 240 Numbers using 1's Complement... 1 232. Half Adder an 4.4232 Complement soe 2.93. FuAdder 242 1.124 Representation of Positive and Negative ais Nie Acie using Hell Ater aa Numbers using 2's Complement «01-42 23.5 Applications of Full Adder 244 1.125. Signed Complement Numbers 1-43 2.3.6 Binary Subtractors 244 1.126 Addition of Signed Magrituse Nunbere iW. i 23.7 Half Subtractor 244 1.12.7 Arithmetic Subtraction (Subtraction of eo all Subree ee ‘Signed Numbers) 4-48 239 Full Subtractor using «+ Review Questions... Hol Subtractors 246 eae 24 The mBit Parallel Adder 247 SE 24.1 Four Bit Parallel Adder Using Chaptor2: Combinational Logic Design 2-1 to 2-70 —re———e==—E—_—vvrverrrrss Full Adders 247 Sonne I ee ee Neer 24.2 Propagation Delay in Parallel Adder ....2-17 Binary code, Halt-adder, Full adder, Helf subtractor, Full ‘subtractor, Binary adder (IC 7483), BCD adder, Look 2.4.3 Look Ahead — Cary Adder 218 ahead carry generator, Multiplexers (MUX) : MUX (IC 2.4.4 — Four Bit Fast Adder with Look-Ahead 74163, 74151), Cascading multiplexers, Demultplexers any bap (DEMUX) - Decoder (IC 74138, IC 74154), Implementation of SOP end POS using MUX, DMUX, Comperetrs (2 bt), 2.45 Binary Adder IC 74 LS 83/74 LS 283.2419 Parity generators and checker. 2.46 Four Bit Binary Adder using IC 7483 ...2.20 Exemplar / Case study : Combinational logic design of 247 Cescading of Adders 229 BCD to 7 segment display controller. SdWF table of Contents DELD (Sem_IIl/ Comp_/ SPPU) 25 nit Parallel Subtractor 2.128. Implementation of Boolean SOP (Use of Adder as Subtractor) 2.20 Expression with Don't Care 25.1 4BitParallel Subtractor using 2's ee fr Complement 2.21 | 213 Demuttiploxers 248 25.2 4.it Binary Paralie! Adder/Subtractor 2-21 2.18.1 Demutiplexer Principle 244 26 BCD Addition 2.22 | 2.14 Types of Demutiplexers 245 26.1 BCD Adder 223 2141 1:2 Demultplexer 245 2.7 Magnitude Comparators 2.25 2.142 124 Demutiplexer 2.468 27.1 1-Bit Binary Comparator 225 2.143 4:8 Demuttplexer 247 27.2 A2-8it Comparator 226 2,144 |C 74138 a5 1:8 DE-MUX 247 28 — Multiplexer (Data Selector) 22r 2.148" 1:16 Demutiplexer 248 28.1 Necessity of Multiplexers 2.28 2.146 DM541S154/0M7418 154 4 Line 282 Advantages of Multplexers 228 (0 todd Seger / Demux 240 29 Types of Multiplexers zc}) 215 ComulierNigs fe eda hlalele 28 2.184 Comparison of Mutiplexer and Demultiptexer 260 292 Ad: 1 Multiplexer .« 229 2482 Use of DEMUX in Combinational Logie 293 8:1 Multiplexer 230 Design oleh 29.4 Applications of a Multiplexer 230 |\b.46 Encoders bes 2.10. Study of Ditferent Multiplexer ICs 231 Saad ive erehesaats lea 2.10.18: 1 Muliploxer (74151) 231 | 947 prosty Encoder bles 2G Aga s TSIOm sags ses 2.17.4. Protty Encoders in the IC FOE on. 253 (Oual 4 1 Mutiplexes) 232 218 Decoder 258 211 Multiplexer Tree / Cascading of Multiploxer....2-32 2.181 204 Line Decoder 254 2.42. Use of Multiplexers in Combinational id bead 7 2.182. Difference between Decoder and Demultiplexer 264 2.121 Implementation ofa Logical Expression ipa ented soe Fait pee 2.18.3 Demultplexer as Decoder 255 2122 Use of 8: 1 MUXt0 Realize a ee eee eee te 4 Variable Function 239 2.185 1:8DEMUX as 3:8 Decoder 255 2.12. Implementation of a Logical Expression 2.186 1C-74138.8.9: 8 Decoder 288 Ce ene ere eee 2.18.7 4 Line to 16 Line Decoder using 3: 8 2.124 Implementing a Standard POS Decoder 287 Expression using Multiplexer 242 TechKnouteds|table of Contents DELD (Sem_IIl/ Comp_/ SPPU) 2.188 Combinational Logic Design Using 3.1.4 Latch 33 a 287 | 32 SRLatch using NOR Gates 34 2.18.9 Advantage of Decoder Realization .....2.60 Sat topeaion ORE i 2.19. Parity Generators / Checkers 261 3.22 Symbol end Trth Teble of SR Latch ..35 2.19.1 Parity Generator 261 3.23 Characteristic Equation 36 2192 Parity Checker 262 3.24 S-R Latch using NAND Gates 38 2193 1674180 AParity 3.3 Triggering Methods. 37 Generator / Checker 263 sat Metutd: cr nent ot Level Triggering 3 2.194 74180 as Parity Generat 264 Seer 3.3.2 _Typesof Level Triggered Fip-Nops .....3-7 2195 Cascading of 74180 265 See 333° Concept of Edge THgering 38 -xamples for Pract eee ee eee tre 33.4 Types of Edge Triggered Flip Flops .....3-8 221 Case Study Combinational Logic Dasign of PMD orss tsicnee a BOD to 7 Segment Display Controller 2.68 3.4.1. Types of Level Triggered (Ciocked) Flip 221.1 Seven Segment LED Display 12-68 to 8 2212 Typescf Seven Segment Displays:265 | 45 the Gated $R Latch 2.21.3 Common Anode Display 265 (Level Triggered S-R Flip Flop) 38 2.21.4 Common Cathode Display 265 35.1 Positive Level Triggered SR Flip-op 38 221.8 Use of a Decoder for Driving the Seven ‘Segment Display 267 3.52 Negative Level Triggered SR Flip Flop 39 2.21.6 BCD to Seven Segment Display Driver cof encce Display) 4, 3.5.3 Disadvantage of S-Rlatch 3.10 © Ce cumtons ay 3.54 Application of SR latch 340 A, 36 The Gated D Latch (Clocked D Flip Flop) «3-10 37 Gated JK Latch Chapter 9 :_Fllp Flops 341t03:98 (Level Triggered JK Flip Flop) at Syllabus : SR, JK, D, T, Preset and clear, Master slave JK 3.7.1 Race Around Condition in fp flops, Truth tables and excitation tables, Conversion ok Latch ot from one type to another type of fp fop. age cobittas bubae latch aha 3.1. Introduction 32 Flip-op 3412 3.1.1 Clock Signal 3.2 | 38 Edge Triggered Flip Flops 342 3.1.2 Comparison of Combinational and 3.8.1 Positive Edge Triggered SR Sequential Circuits 32 Flip Flop 33 3.1.3 {-BitMemory Cell (Basic Bistable 3.8.2 Negative Edge Triggered S-R Element) 33 Flip Fiop 314 TechKnouteds|table of Contents DELD (Sem_IIl/ Comp_/ SPPU) 39 Edge Triggered 0 Flip Flop 314 3.15.3 Excitation Table of JK Flip Flop... 3-24 3.9.1 Positive Edge Triggered D 3.16.4 Excitation Table of T Flip Flop 3-25 Flip Flop S14 | 3.46 Conversion of Flip Flops 3-25 3.9.2 Negative Edge Triggered 3.16.1 Conversion from $-R Flip Flop to D D Fip Flop 345 one flee 3.8.3 Applications of D Flipflop ae 3.16.2 Conversion of JK FF to T FF 3.26 p10 Esge Thaaerd AESeastons Ac +B ct (€2217) Fig. 1.2.1: Realization of given logic expression — When we realize the Boolean equation by using gates, each literal acts as an input as shown in Fig. 1.2.1. SF tonnesWF ve. (sem.u1/ Comp. SPPU) = Any logic expression can be expressed in the flowing two standard forms 1. Sum-of Products form (SOP) and 2. Product-of-Sums form (POS) ~ These two forms are suitable for reducing the given logic expression ots simplest form, 4.2.1. Sum-of-Products (SOP) Form : ~ Refer to logic expression shown in Fig, 1.22. It isin the form of sum of three terms AB, AC and BC with each individual term is product of two variables. Say A-B or ACetc. sum Y= aptactec Produet terme (€-1217(2) Fig. 1.2.2 : Sum-of- Products (SOP) form = Therefore such expressions are known as expression ie SOP form, = The sums and products in the SOP form are not the actual additions or multiplications. In fact they are the (OR and AND functions. ~ A.B and C are the literals or the inputs of the combinational circuit = Some more examples of the SOP expressions are as follows Y = ABC + BCD + ABD, AS XV + y+ Xi, Y = PQ sPQR + POR = Thus in each product term there can be one or more than one literals ANDed together. The literals can be in their complemented or uncomplemented form, 4.2.2. Product of the Sums Form (POS) Refer to the logic expression shown in Fig. 1.2.3. Products Y= ase t@rc taro Sum terms (€-1218) Fig. 1.23 : Product of Sums (POS) form = Its in the form of product of three terms (A + 8), (B + ©) and (A + ©, with each term is in the form of sum of two variables. zation Techniques — Such expressions are said to be in the Product of Sums (POS) form, = Some other examples of POS expressions form are as follows Y= (A+B+Q-(A+B)(A+O) A= K+) K++] Y = P+R)-(P#Q-P +R) The literals are ORed|together to form the sum terms and the sum terms are ANDed to get the expression in the POS form. 4.2.3. Standard or Canonical SOP and POS Forms Ganenical or standard forms : — (The word standard isyused inverder to describe a condition of switching equation. The meaning of the word standard is conforming to @ general rule ~ This rule) states that each term used in a switching equation must contain all the available input variables = The wo formats of a switching equation inthe standard form are: 1. | Sum of Product (SOP) format. 2.5, Product of Sum (POS) format. — “When we simplify a Boolean equation, sometimes an input variable is eliminated to simplify the equation — But standard expressions are not simplified, I is said that the standard expression is the opposite of simplification, So it contains redundancies. — Many times, switching equations written in the SOP or POS form are not standard. That means each term may not contain al the input variables — Consider the SOP and POS expressions. shown in Fig. 124 Standard SOP form: ¥=ABC + ABE + AEC Each product term consists ofall the Iterelsin the complemented ‘or uncomplemontod form rd POS form :¥= (A+B+0)-(A+B+0)-(A+B+5) Each sum tam consists of al the literals inthe complemented ‘or uncomplamented form (€1219(4) Fig. 1.2.4 : Standard SOP and POS forms SE lettooategeWF ve. (sem.u1/ Comp. SPPU) = Referring to Fig, 1.24 we can say that a logic expression. |s said to be in the standard SOP or POS form if each product term (for SOP); and sum term (for POS) consists fof all the literals in their complemented or uncomplemented form Non-standard forms : ~The two standard forms discussed earlier are the basic forms that are obtained from the truth table. However these forms are not used often because these {equations are not in the minimized form because each term contains all the literals There is another way to express the Boolean functions. Itis called as the non-standard form. = In this form each term may contain one, two or any number of literals. It is not necessary that each term should contain all the literals. There can be two types of non-standard forms 1. Non-standard SOP form. 2. Non-standard POS form = The examples of standard and non-standard SOP and POS expressions are given in Table 12.1. (€-8065) Table 1.2.1 : Non-standard and standard SOP and POS forms Expression Type Non-standard SOP Y¥=AB +ABC ABC. Y=A8 +AB+AB (+B) (AB) (A+B) ‘Standard SOP. ‘Slandard POS: Non-standard POS x8) (A+B +c) 1.2.4 Conversion of a Logic Expression to Standard SOP or POS Form : = Let us see how to convert the given non-standard SOP. and POS expressions into the corresponding non- standard SOP and POS forms. Conversion from non-standard SOP to standard SOP form : The procedure to be followed for converting @ non- standard SOP expression into a standard SOP expression is as follows Steps to be followed Step For each term in the given non-standard SOP| expression find the missing literal zation Techniques |Step2: Then AND this term with the term formed by| ‘ORiing the missing literal and its complement. [Step 3: Simplify the expression to get the standard SOP| expression, Ex. 4.2.4: Convert the expression Y = AB + AC + BC into the standard SOP form. Soin. = The given expression has 3-input variables A, B and C. ‘Step 1 : Find the missing literal for each term AB + AC 4.BC TTT Missing iteral —» OC BOA (2) ‘Step 2: AND each term with (Missing literal + Its complement): (¢-2883) /ANDING. yeno! (c+ 0) 40 GHB 20 A+R ‘Step 3 : Simplify the expres sor jon to got the standard ¥ =,AB(C+T) + AC(B +B) + BC(A+A) ABC + ABC + ABC + ABC + ABC + ABC (ABC + ABC) + (ABC + ABZ) + ABC + ABC BULA + A=A (ABC + ABC) = ABC and ( ABC + ABC) = ABC Y=ABC-+ABS+ASC+ABC Standard SOP form ——— Each term contains the literals (e182) Conversion from non-standard POS to standard POS form: = The conversion of non-standard POS expression into standard POS form can be obtained by following the steps given below ‘Steps to be followed : |Step1: For each term in the given non-standard POS| expression, find the missing literal |Step2: Then OR each euch term with the term formed by| ‘ANDing the missing literal in that term with its ‘complement. [Step 3: Simplify the expression to get the standard POS. Be TetloontetatWF ve10 sem.t1/ Comp. /SPPU) 1 £4.22: Convert the expression Y = (A+ 8) (A + C) (8 + C) into standard POS form, Soin. Step ind the missing literal for each term A+B) (A+0) 643) TTY (2384) Missing itoral literal. ts OR each term with (Missing complement) (A+B +06)- (R40 + BB) (840+ AA) Missing literal ANDed with its complement L ‘This tom is ORed with the torm formed by 'ANDing the missing itera with its complement (e153) Step 3 : Simplify the expression to got standard POS : Y = (A+B+CC)(A+C + BB) (B+ C+ AAD But A+BC = (A+ B)(A+C) Y = (A+B+Q(A4B+C) (A+ C48) (A+C+B)@+E+A(B+C+A) But ALA =A (A+B+O~rCrB (AsB+0. and (A+ B+) (8+ +A)=(A48+0) (e154) Y = (A#B+0) (A+B40) (A¥B4C) (A+B) Standard POS form eae Each term contains ‘llth ters Convert the following expressions into their standard SOP or POS forms 1. Y=AB+AC+BC 2 Y=(A+B)@ +c) 3 Y=A+BC+ARC Soln. : Solve it yourself. ‘Ans. : LY = ABC+ ABE +ABC+ABC 2 Y¥ = A+B+Q(A+B+OG+C+AB+C+A) BY = ABC+ABC + ABC+ ABC + BCA 1.3 Concepts of Minterm and Maxterm : Minterm Each individual term in the standard SOP form is called 8 minterm. This is shown in Fig, 1.3.1. zation Techniques Maxterm = Each individual term inthe standard POS form is called as maxterm, Ths i shown in Fig, 1.3. oc + abe + kee LLL een inv torm 'Sealled miniorn ‘Standard SOP. Standard POS Y (A+8)+(A+8) LL 1 een natu tom isealled maxterm (€-1220(a) Fig. 1.3.1 : Concept of maxterm and minterm ~ Table 1.3.1 gives the minterms and maxterms for a three variable/literal logic function. Let ¥ be the output and A, B,C be the inputs. 067) Table 1.3.1 : Minterms and maxterms for three variables: Variables | Mintermsa] Maxterms aje[cj. ofolalasc- ol of: [ae c= of1fojasc ol 1fi [asc vfololase: 1fo[1[aBc= 1[1[olase t[+ [7 [aec= ~The number of minterms and maxterms is 2) = & In general for “n’ number of variables the number of ‘minterms or maxterms wil be 2" = Each minterm is represented by rm where i 2' ~1 and each maxterm is represented by M, Wiring minterm fora particular combination of ABC : = Consider ABC = O11. Assume that A,B, Care input to an AND gate — We want the output ofthe AND gate to be 1. For that all ts inputs should be 1 = So take the complement of that input whichis 0 Le. Ain this case and write the mints Minterm = A 8€ contesponding to ABC = 011 Similaty other minterms in Table 13.1 can be obtained Writing maxterm fora particular combination of ABC : — Let ABC = 012 = Assume that ABC ae inputs to an OR gate.WF ve. (sem.u1/ Comp. SPPU) We want the output ofthe OR gate tobe 0. So all the inputs othe OR gate should be Os = Soinven the inputs whch re 1s. 8 and Cin this case and write the mater, Maxterm = (A + B + C) corresponding to ABC = 0.11 Silay other mayterms in Table 1.31 can be obtained zation Techniques ~ Hence itis possible to obtain the logic expression in the standard SOP or POS form ifa truth table is given to us. 4.3.3 Representation of Truth Table using ‘Standard SOP Expression : — The procedure to be followed for writing the standard SOP expression from a given truth table is as follows. Ex.1.3.1; For the truth table of two variables write the | |Step1: From the given truthitable, consider only those| rminterms and maxterms. combinations of inputs wich produce an outpui Soin. : von eigenen pala ator chute |step2: Write “down a product term interms of input variables for each such combination. (4065) Table P. 1.3.1: Solution to Ex. 1.3.1 [step 3: OR all these product terms produced in step 2 to [Variablesiiterala] Minterms] Maxterms Get the standard SOP. a. s my, Tele MTAEB Ex.1.32: From the truth table P. 1.22, obtain the logical TT WaAvEl ‘expression in the standard SOP form. 1 [0 ,=A+8 (can Table P.1.3.2: Given truth table 712 =A x ° 1.3.1 Representation of Logical Expressions ° using Minterms and Maxterms : - ~ We can represent the logical expression using the Pt gical expres 9 the | gain minterms and maxterms as follows : = ABC +ABC + ABC +— Givan logic expression adie ate al My Mg My_-+—=Comresponcing minterms Y = my-+mg+mg=2m (8,4, 7) Other way of representation (0355) where & denotes sum of products 2. =(AsB40) (A4B+0) (A+B+0) « Given expression Se Mz My Mg = Cofeepondng maxtonme Y = MaMoMe Y=IIM@.2.6) +Other way of presentation ‘whore 1 denotes product of sume. (6156) 1.3.2 Writing SOP and POS Forms for a Given Truth Table : We know that a logic expression can be represented in the truth table form. For example, the expression Y= ABs B which is the Boolean expression for an EX-NOR gate can also be represented using a truth table, ‘Step 1 Consider only those combinations of inputs which ‘correspond to Y = 1 ‘Steps 2 and 3: the second and the third Table P. 13.2(2) write the product terms — For entries in (€-6157 Table P. 1.3.2(0) ¥ ye yy 8 Boolean expressions in ‘the product forms ° ~ Now OR (Add) all the product terms to write the final expression in standard SOP form as follows y= \r¥, = Ae+AB Em(L2) Ex. 1.3.3: For the truth table shown in Table P. 1.3.3 ite the logic expression in the standard SOP for. Be TetloontetatWF ve. (sem.u1/ Comp. SPPU) (€-6a12) Table P, 1.3.3 : Given truth table Ale [ely ofololo OU) LoN AIA] Fc ony of1fofo o[1}ifo TY 8c mo [ol] 1]o +[+[o[o TONITE a2 om) Soln. : Step 1: Product terms corresponding to combinations of Inputs for which ¥ = 4 ‘Stop 2: OR (Add) all the product terms : Ring all the product terms we get, RBC+ ABC + ABC Ans: Y = memem,= 2m,4,7) 1.3.4 Representation of Truth Table using Standard POS Expression : ~ Follow the procedure given below to get the expression in standard POS expression from a given trath table From the given truth {8B16, consider only thase combinations of inputs. which produce & lo ‘output (Y = 0 Wirte the maxterms only for such combination. ‘AND these maxterms to obtain the @xpression in standard POS form ‘Write. the logic expression in standard POS form forthe truth table shown in Table P. 1.3.4 (€-6415) Table P. 1.3.4: Given truth table AT®[e]y Oo fo fo] ara+comy ofo[i[1 o[+[o[t Ofna] A+B + Ton) +[o[o|[t1 Teen A+ 8 +S ony TAO ola+s+omy thts Write maxterms for the combinations of input which produce Y= 0. zation Techniques ‘Step : AND (take product of) all the maxterms to get standard POS form : = ANDing (taking product of) all the maxterms written in step Lwe get, (A+B+O-(A+B+C)(A+B+C)(A +B+0) M,° My*Mg*M, = [1M (0, 3, 5,6) 4.3.5 Conversion from SOP to POS and Vice Versa : = It is important to note that the SOP and POS forms ‘written for the same truth table are always logically equivalent, ~ This point can be proved by solving the following example Ex.13 5: For the given tuth table write the logical ‘expressions in’ the standard SOP and POS forms and prove their equivalence. (€-6a1e) Table P. 1.35: Given truth table minterms [TA] B | © | ¥ | Maxterms o fo [oo Jasasc 280. \Foujon|u|a 0] + [0 [o jasdec oft] so |asaes ase [ijelpolla t[o [1 [o asa. t[ 1) 0/0 fasasc asc [ijl Soin. ‘Step 1: Minterms and maxterms for the combinations of inputs producing Y = 1 and 0 respectively, ‘Step 2: Write the standard SOP and POS expressions : ‘Standard SOP form : Y = ABC + ABC + ABC ‘Standard POS form : Y= AtB+QA+B+Q(A+B+C) (A+8+T)A+B+Q ‘Step 3: To prove the equivalence between SOP and POS forms : = Consider the standard POS form, (A+8+Q(A+B+QA+B+E) (+8+t)A+8+0 Be TetloontetatWF ve. (sem.u1/ Comp. SPPU) But(A+B+C)(A+B+Q = (A+C+B-8) arg Y=(A+0} (A+B +0) (A+B +0)A+B +0) oO @ @ (corse = Multiply the terms (1 « 2) and (8 « 4) to get, Y = AA+AB + AC + AC + BC + CE} (ARAB sAC+AB+ BBs OC+AC +8 +E) ButAa = Y = (A+AB + AC +AC +8q) AsAB+AC+AB+ BC +AC+ BC] = A+B) +AC +O +80 (0+ BA+ AC +O +A8 + 8c + Buta 8) = 1 CrC=1, ars=1 Y = A+A+EQ (A+ Asha +80 +8Cy But A+A =A And A+A = B® (A+ BC) [A +AB # BC + BC) = (AsBQ A 1 +B)+8C+8q) put(1+B) = 1 Y = (A+BQ)(A+ BC +BC) = AAP ABC HABC + ABC + (BC-BC) + (6C-BC) But AA =)0, (6C-BC) = Oand (BC- BC) =0 Y= ABC + ABC + ABC + This is same as standard SOP form ‘Thus the equivalence SOP and POS forms is proved (6363) Step 4: Express output in terms of minterms and maxterms : = The output can be expressed in terms of minterms and. ‘maxterms as follows Y= mptm,+m, ln terms of minterms. = Emaar and Y= My My My: My Mg.utn terms of maxterms. = 1MO23,56) ~ Due to equivalence between SOP and POS forms we can write, Mi tion Techniques Em(4,7) = 1M 0.2,3,5,6) a) Complementary relationship between minterms and maxterms. ~ From Equation (1) we can conclude that the relationship between the expressions expressed using minterms and ‘maxterms is complementary celationship. ~ We can exploit this complementary relationship to write the expression in terms af maxterms if the expression in terms of mintermsis known and vice versa, = For example, fa SOP expression for 4-variables is given by, Yo= Sm (0,1,3,5,6,7,11, 12,15) = “Then we can get the equivalent POS expression using the complementary relationship as follows Y = 11M (2,4,8,9,20,13, 14) 1.4 Methods to Simplify the Boolean Functions ~The methods Jused for simplifying expressions are as follows 1. | Algebraic method. 2) Karnaugh-map simplification, the Boolean 3. Quine Me-Cluskey method and 4. Variable Entered Mapping (VEM) technique. — The Boolean theorems and De-Morgan’s theorems are Useful in simplifying the given Boolean expressions. ~ We can then realize the logical expressions using either the standard gates or universal gates = We should use the minimum possible number of logic gates for the realization of a lagical expression. ~ This is possible if we can simply the logical expressions. ~ In this chapter we will discuss one of the simplification techniques called Kamnaugh map or K-map and the Quine Me-Cluskey Method or the Tabular Method. 1.4.1 Algebraic Simplification : ~ We have studied the Boolean laws and De-Morgan’s theorems. = We can use them to simplify the given Boolean expression in the following way. = The most important thing is to convert the given expression into SOP form, SE lettooategeWF ve. (sem.u1/ Comp. SPPU) Standard procedure for algebraic simplification : [Step 1: Bring the given expression into the SOP form by) using the Boolean laws and De-Morgan's theorems, |Step 2: Simplify this SOP expression by checking the| ‘product terms for common factors. Ex.1.4.1: Simplify the expression given below AB + (A+B) (A+B). Soln. : ‘Step 4 : Bring the given expression in SOP form Given expression Y = AB+ (A+ 8) (A+B) = AB+ (AK + AB +A8 +88) : Search for common factors and simplify : y Step AB + AR + AB + AB + BB = AB+AB+BB+AA+AB But AB + AB = AB,BB=BandAA=0 Y = ABs B+AB=B(A+ 1) +AB Bu A+) = 1 Y = B+AB=B(1+A)=Busince(1+A)=1 y=8 Ans. This s simplified expression, For the logic circuit shown in Fig, P. 1.4.2 write Ex. 1.4.2 ‘the Boolean expression and simplify it. A AsB 8 yet y At c (221) Fig. P.1.42 : Given logic circuit Soln. : ‘Step 1 : Write the Boolean expression : The expression for output of the given logic circuit i, Y = (A+ 8)(AB)(A+O) ring this expression in SOP form : Stop = Multiply the terms to get the expression into SOP form, = (A+B) (AAB + ABC) BULAA = A zation Techniques Y = (A+ 8) (AB + ABQ = AAB + AABC + BAB + BABC = AB + ABC + AB + ABC = AB + AB + ABC + ABC Band ABC + ABC = ABC AB + ABC = AB(+ 0) Y= as since 1 + € ~ Thisis the simplified expression. Ex.14.3: Simplify the following three variable logic ‘expression, ¥ = ITM (1, 3,5) Soin. ~The given. expression can be expressed in terms of rmaxterms a5 Yo= My-My/M, (A+B 4T)(A4B+C)(A+B+C) ‘Step 1 : Bring the expression into SOP form : YE AtBrE)AB +) MrB+e) = sb +O @A+ a+ AC + AB +38 +BC+A ‘Step 2 : Simplify +tQ But AA = 0,88 = Oand@ AY = (A+B4T)(ABHAC +AB+BC+AT +BT+C) = (A+847)[AB+AC+AC +AB+BC+8C +7) = (A+B +C)(AB+T (AFA) +AB+ CBs 8) +] But (A+A)=1,(6+8)=1 Y = A+6+C)(aB+C+AB+C+C) Butt +t = (A+B 47) (AB +AB+E+C) = (A+B +S) AB +AB But AAB = AB, AAB AB, ABB =O and CC=C Y = AB+AC+ AB + BC + ABC + ABC +T But AB + AB = AB Y = AB+AC+BC + ABC + ABC + C = AB+ ABC + AC + BC+ ABC+T = AB(L+C)+AC+ BC +ABC+E Be TetloontetatWF ve. (sem.u1/ Comp. SPPU) AB+AC+BC+ABC+E —since(d+C)=1 AB+CA+B+AB+1) y= aa+t since(A+B+AB+1)=1 y = This is simplified expression. ag+c Ans. Ex.1.4.4: Simplify the following three variable Boolean expression Y=Em(24,6) Soln. : Solve it yourself. Ans. : y=aa+e Ex.1.4.5: Convert the expression Y = 11 M (1, 3, 6) into ‘minterms and simpli to get the same answer. Soln. : Solve it yourself. ‘Ans. : vst +B 1.4.2 Disadvantages of Algebraic Method of Simplification : 1. In the algebraic method of simplification we need 10 write lengthy equations, find the common tetms, and use various laws and theorems to minimize the expressions. So it isa time consuming work 2. On top of that, sometimes we are not sure whether the further simplification is really possible or note That) means whether we have really obtained the minimized expression or not 1.5 Karnaugh-Map Simplificat This is another simplification technique to reduce the Boolean equation. = It overcomes all the disadvantages of the algebraic simplification technique. = K-map (short form of Kamaugh map) is a graphical ‘method of simplifying a Boolean equation, K-map is a graphical chart made up of rectangular boxes, = The information contained in a truth table or available in the SOP or POS form can be represented on a K-map. ~The K-map can be used for systematic simplification of Boolean expression. = Kemaps can be written for 2, 3, 4 .. upto 6 variables. Beyond that the K-map technique becomes very cumbersome. zation Techniques K-map is ideally suitable for designing the combinational logic circuits using either a SOP method or a POS method. = The K-map is drawn for output ¥ and the input variables (A.B, C.. etc) are used for making the entries in the boxes. 4.5.1, K-map Structure : ‘The structure of a 2 input (variable) Karnaugh is shown in Fig. 15.10). — This K-map is drawn for oltput Y of any two input combinational, circuit such as a logic gate with inputs A and 8, ie, AB= 00, 01, 10 and 11. 2 Variable K-map, Ri + Aand Bf inputs or varatles a ee Load tarethovahe of oS Tribes boxes we have terior Ihevalveso!¥ ve, but (a) Structures oft 2-ariable Kap 8 Variable Kenan 8¢ BC BC sac don ot “iy This coquono0 flows ray do ar nt binary Treat : mls) 0 5B Ap AB AB cower ft 40 3 <0 value of Bc ¢ ~ Ativoo variable Knap consists of 8 boxes {Tho postions of varabos A.C ar iniorchargable () Structures ofa variable K-map 4YarableK-mep _Seqyononas er ary eode ‘A 4vanable Knap ae.88 AB 43 a8 | co | conasnot boxes OC tcomotti ato: | obson tt 10 305] Nao coo oy con x B10} to (6) Structares of variable Komap (€217 Fig. 15.1: Structures of 2, 3, 4 variable K-map, — A 2 variable K-map consists of 2° = 4 rectangular boxes, Inside these boxes we have to enter the values of output Y for different combinations of inputs A and 8. = The K-map comprises a box for every line in the truth table, For a 2-input combinational circuit there are 4-lines in the truth table, so there will be 4-boxes in the 2 variable K-map. SF FechknouteWF ve. (sem.u1/ Comp. SPPU) = For a 3ariable Kemap there wil be 8 bores, fr 4+vatable map ther wil be 36 boxes and 50 on, = The 0 and 1's written on top oF sides of the boxes represent the values of the corresponding variables. The sequence is funny (Itis gray code! — In truth tables, the values of inputs follow a standard binary sequence (00, 01, 10,11), — _Butin K-maps the input values are ordered in a different sequence (00, 01, 11, 10) ~ This is as per the gray code and not binary code. So that as we move along a row or column only one variable will change its value at atime. — If the labeting is done as per the gray code, only then the elimination of variables and therefore the simplification will take place. When pairs, quads or octets are identiied with the ‘normal labeling, this elimination will not take ple. = Hence gray code is used in labeling the calls of 2 K-map. 4.5.2, K-map Boxes and Associated Product Term = The rectangular boxes inva K-map are to be filled with the values of output, Y Korresponding “to different combinations of inputs, a8 shown in Fig, 1.52. = Each fow and column of a K-map i labelled with a variable, or & group of variables or their complements. For example, see the shaded boxin Fig. 152). ~ This box corresponds to the fist row which is labelled by Aand frst column labelled by 8 Hence the product term written inside this box is AB as shown in Fig. 1.5.2(2) js the shaded box shown in B and the = Another Fig. 1.5.2(0. The first row is labelled with example first column with CD. Hence the product term written 5 in this box is A Similarly the other product terms have been inserted, in the remaining boxes, zation Techniques 5 ac at alae | ae | alase asc acc Jase, alas fas | fase jase, lasc jasc] Inside each box wo subatuo@ product (09 Two variable Kap (0) Thee variable Kmap see So. Each colume zo é0 co Job ‘Stabbed kaGo|ABCD|ABCD Reto Aecd ABEO|AECO ABCD) B® pructicmis ls) ag flo he Feolsscolazcchon mascot ABG0|ASco|AScD) " ‘herowand a lapses Sune, (©) Four variable Remap (a) Labeled cee) Fi 1.5.3 Alternative Way to Label the K-map : = We can label the Yows and columns of a K-map in a different way as shown in Fig. 1.5.3 = Instead, of labelling the rows and columns with the 15.2: K-map boxes and associated product terms inputs and their complements (A, A, AB etc), their values in terms of Os and 1s is used for labelling, = And inside the boxes, instead of writing the actual product term, the corresponding shorthand minterm are entered. Rotations my my ‘ontored inside tre boxes ible K-map—_(b) Three variable Kemapp (a) Two w eo nel oo_or_ 11 10 10] mo] m | ms] m2 orf mame [mr | ms | motomsare minions of a4 varabie equation ti] Me 10} ms | me [rm fro (©) Four variable K-map (C219) Fig. 15.3 : Alternative way to label K-map 4.5.4 Truth Table to K-map : Whenever the K-map is to be practically used for simplification, the entries inside the boxes are to be written by referring to the given truth table. WF etoonetgWF ve. (sem.u1/ Comp. SPPU) In this section we are going to learn how to represent the given truth table on a Kamaugh map. Relation between a truth table and K-map entries : Fig. 15.4(2) illustrates the mapping of a truth table on. theme Touth tle 2 Variable K-map ree]. Tle] i O° Co wie inks ec tbo Se and’ ore tno inp or variables ohand (€-220) Fig. 1.5.4(a) : Relation between a truth table and K-maps for 2 variables ontortho valves oY (oupa) oresponang to aferert combinations Referring to Fig. 15.4(@) we conclude that inside the boxes of the K-map we have to enter the values of ‘output Y corresponding to various combinations of A, and 8. = Fig. 154(b) shows the representation of a truth table using a 3-variable K-map and Fig. 15.4(¢) shows the epresentation of a truth table using a 4-variable K-map. af Sinpat | y 8+ combinational ca] rut 23 Vatiable K-map 8 69 of a8 No peo otis 10 S00 oF 0 Tole]. apelelo else of ofa oftft afafa s[e[e 10] o | 0 ape Note: Inside the boxea we enter ‘ho valubs of corresponding to. dlifrent comeinatons of & and 8 ig. 1.5.4(b): Relation between a truth table and K-map for 3-variables zation Techniques (5603) Truth table ©). “variable Kemep op AB\_00_o1_11/ 40 10 oof 1] 0] 1.0 1J or} o | o | Ay] o ° 4 1 ofa] 0 sal tas) ul i io} Lea dt Sl “sl 4 (€222) Fig. 15.4(¢): Relation between the truth table ‘and 4-variable K-map 4.5.5 Representation of Standard SOP Form on K-map : ~The logical expression in standard SOP form can be represented with the help of a K-map by simply entering 1's in the cells (boxes) of the K-map corresponding to each minterm present in the equation, ~The remaining cells (boxes) are filled with zeros. — && 15.1 iilustrates the concept of transferring a standard SOP expression on K-map. Ex.1.5.1: Represent the equation given below on Karnaugh map. Y=RBC+ABC+ABC + ABC + ABC. Soin. — The given expression is in the standard SOP form. Each term represents @ minterm. — We have to enter 1's in the boxes corresponding to leach minterm, as shown in Fig. P. 1.5. Be TetloontetatWF ve. (sem.u1/ Comp. SPPU) zation Techniques ABE AES. ‘And the top cells are adjacent to their corresponding ec BeBe BAN atone atta bottom cel aia. Let most and ght mest Tap and conesponing oles 3, "VM O° cots aro acjacont botom calls are adasent Mdeoon— (El JR Ee eo[ “ie “sare a =| 44 | to the minierms in the inte et oven Boban xposson ave (€23 Fig. P15. Representation of standard tact SOP on Komap jac ° Pot the folowng Boolean expression on oat” Aaagonl = V7 ‘sncont Koma y 7 i 777) rencent cats b [2] adjacent cots WSC5B_G0_ 00 ob coo 10 : [| D)prerorcate AB) 1] o | a 0 oo] ¥) o fatto ee) 4° |B FY acacon cots mofofefm] ole foe [igfaece |e aa dole Jefe] aeee asl otofo| ufos oto O) ) 1 od Od goen' fel od Sul Sa He Jal iell fal st] tats (all tenllaglte (© 229 Fig, 162 : station of adjacent cls “1's corespond the minors in the ‘iven Boolean exproesion (224 Fig, P. 1.5.2: Representation of canonical ‘SOP on Karnaugh map Minimization of Boolean Expressions using K-map : 1.6 Simplification of Boolean expressions. using K-map is based on combining or grouping. the terms in the adjacent cells (or boxes) of a K-map. = Two cells of a K-map are said to be adjacent if they differ in only one variable as shown in Fig. 1.6. BC aX oo of 1140 ETT le (€225) Fig. 1.6.1 : Adjacent or non-adjacent cells +1 and 2 are adjacent ‘91 and 5 are adjacent ‘= But 1-6 of 2-5 are not adjacent Note the cells on left or right side or at the bottom and top of cells are adjacent cells. But the cells connected diagonally are not the adjacent ones. ~The left most cells are adjacent to their corresponding right most cell as shown in Fig. 1.6.2). 1.6.1 How does Simplification Takes Place ? = “Once we transfer the logic function or truth table on a Karnaugh map, we have to use the grouping technique for simplifying the logic function. ~ Grouping means combining the terms in the adjacent cells = The grouping of either adjacent 1's or adjacent 0's results in the simplification of Boolean expression in the SOP or POS forms respectively — If we group the adjacent 1's then the result of simplification is in SOP (Sum Of Products) form. — And if the adjacent 0's are grouped, then the result of simplification isin the POS (Product Of Sums) form, 1.6.2 Way of Grouping (Pairs, Quads and Octets) : = While grouping, we should group most number of 1's (or 0s, ~The grouping follows the binary rule ie. we can group 1, 2, 4, 8, 16, 32 .... number of 1's or O's. We cannot group 3,5, 7, 1. Pairs : A group of two adjacent 1's or O's is called as @ umber of 1's or Os pai Be TetloontetatWF ve. (sem.u1/ Comp. SPPU) 2. Quad : A group of four adjacent 1s oF OS is called asa quad, 3. ete octet 1.6.3 Grouping Two Adjacent One's (Pairs) : group of eight adjacent 1's or O's is called as it we group two adjacent 1's on a K-map, to form a pair, Ithen the resulting term will have one less literal (variable) Ithan the original term. That means by pairing two| ladjacent 1's we can eliminate ono variable. The grouping of two adjacent 1's and elimination of one variable due to pairing is illustrated in Figs. 1.6.3(@) t0(a). Given Kemap j-hec Ca od AX pe_Bo_o/ Ba //*° 0] 0 fa’) 1b croup of adjacont 1's tovapate (€228) Fig. 1.6.3(0) Simplification : Thus Cis eliminated, Conclusion : = Due to formation of pair the variable C is eliminated. So henceforth just by IGoking at the pair we should be able to identify the variable that will be eliminated The other types of pairs and corresponding simplifications are as shown in? Fig. 1642) and Fig. 16.4(6) Given K-map : Hc ec AX BE _Bo/ BC Bo woft]olo alofa}o|o L_aB0 16.310) ‘Simplification : Y= ABC+ABC ~ Thus Ais el Given K-map : zation Techniques BCA +A) y = BC iminated, since (A + A) ‘Simplification : = Thuse Given K-map : v= Ac (+8) y= ae since (8 + B) = {s eliminated. & ase Yt (228 Fig. 16.3(¢) ‘Simplification : Y = RBCO+ ABCD =BCOA +A) y= CD — Thus Ais eliminated Example of overlap Given K-map : Bo \ 58 Alea] as Pairl: AB+AB _ (B+ B)=A Ale ° ‘Note that B is eliminated sr AB+AB =5 Note that A is eliminated (© 229) Fig. 1.6.4(0)WF ve. (sem.u1/ Comp. SPPU) Final expression y= A+B = Note that in order to cover all the 1's, we have to overlap two pairs as shown, Given K-map : ec Pair 8 This pair isnot requited &\ 86 _Bo_80/86 a) o | o [24¢/)¥+{—pair 1: ABC + ABC 7 ABC +C)=AB alo | aja] | Pair 2; ABC + ABC = ACB + B)= AC. (€229) Fig. 1.6.4(b) : Different types of pairs and the corresponding simplifications = __ Add the two product terms to get, ¥ BrAC INote: In this K-map three pairs were possible to be| formed. However only two pairs are sufficient to} include all the 1's present in the K-map. Then the| third pairs not required 1.6.4 Grouping Four Adjacent Ones (Quad) : If we group four 1's fram the adjacent cells of a K-map, then the group is called 35 a Quad. = Im such a quad tworvariables associated with the interme are same and the 6ther two are nat the same ~ Alter forming a! Qiiad, the simplification takes place in such a way that the two variables which are not seme willbe eliminated ~ Thus.a quad eliminates two variables. ~ Fig. 16.5(@) to (9 shows various types of Quads and the corresponding mathematical simplification, = Note that overlapping is possible in Quads. Given K-map : ob oa) apa Toya a5 (©220) Fig. 1.6.5(0) 6 zation Techniques ‘Simplification Y = ABCD + ABCD + ABCD + ABCD = ABCD +ED+cD+CH) = ABIC(@+D)+C(+Dy AB IC + C] ‘Thus Cand D ae eliminated. Given Kmap : 0, W150 cob @loyo ofe ole Mele Gyzc0 (23) Fig. 16.5(6) Simplification : Y= ABCD +A8CO+ ABCD + ABCD = CDIAB+AB+AB+ AB) = COAG+8)+A(8 +B) EpA+al=Co ‘Thus A and B are eliminated. Four adjacent ones forming a square Cs aX G6_GD_co_ cB. wlo]lo]o]o vel ata] o | o (c2n1@) Fig. 1.6.50) Y = ABCD+a8cD+ABCD+ ABCD = BCDA+A)+BTDA+A) = aCD+eco=8¢(0+D) Y = BC Thus A and D are eliminated, Be TetloontetatWF ve. (sem.u1/ Comp. SPPU) Top and bottom 1's forming a Quad : 0. 7 ANB 450004 ob i wel o|olo|o as} oc] ol[o]o a5] 0 T° *Lviso ean Fig. 1.6508) D + ABCD + ABCD + ABCD ABE +Q+ ABD E+O ABD + ABD Y = BDA+A)= BD ‘Thus A and C are eliminated, Leftmost and rightmost 1's forming a Quad : 3B (Aand © are elminated) (62310) Fig. 1.6.5(€) ¥ = KeCB+ascd+Aacd+ascd BCDA+A)+BCDA+A) BCb+B8Cd y = 8DC+Q=80 Thus Aand C are eliminated. 1's corresponding to corners forming a Quad : 00, ad\ CO Co_cp 400 AB] el olololo Ge & Y= BD(Aand Carocliminatod) (€232) Fig. 16.510) y = 35 ‘Thus A and C are eliminated. ‘Overlapping of Quads and pairs ; Bee Hs 'G_60_00» ob. o]ololo CDir : off [el al} offe[o (reriapping) ahd oro par Teoma 60, (233) Fig. 16.519) 1.6.5 Grouping Eight Adjacent Ones (Octet) : It is possible to form 2 group of eight adjacent ones, Such a group is called as octet ‘When an octet is formed three variables will change and coy one variable will remain same in all the minterms. The three variables that change willbe eliminated and the variable which does not change will appear as output ‘Thus octet eliminates three variables Fig, 16.6(a) to () shows various types of octets and the corresponding output. Given K-map : coe 5 a\'5_D_co_o ml todo qo well | [4 8.C and D are clminated (€234) Fig. 1.6.6(0) Be TetloontetatWF ve. (sem.u1/ Comp. SPPU) Simplification : Y = ABCD +ABCD+ ABCD + ABCD BCD +ABCD+ABCD +e (+d) +ABcw+d) Y = ABE +O +ABE+Q) B= A > ve — The only variable that remains same is A . So it appears 2s output Cy Ad\’5_B0_co_ob 8 zation Techniques 4.6.6 Summary of Rules Followed for K-Map ‘Simplification : ‘Summary : No zeros allowed. No diagonals, Only power of 2 number of cells in each group. Groups should be as large as possible. Every one must be in at least one group. Overlapping allowed. Wrap around allowed. Fewest number of groups possible. 1.7 Minimization of SOP Expressions (K Map Simplification) : wl ol oft rel o | 0 [a aslo] oft [1 & ¢ AB and D ave olminated (6234199 (b) ep op oD. ripe puss | ofofo ote ofofo] |r=8 TTi tty ‘ACandD are climinatos (2340) “ese & @ AB and C are clminated (235) (@) Fig. 16.6 ~The Ksmap can be (used. to" simplify the logical expression to a level beyond which it cannot be further simplified, = Aker such a simplification, it will require minimum, umber of gates with minimum number of inputs to the ates, — Such an expression is called as a minimized expression, For minimizing the logical expression, follow the procedure given below. Minimization procedure : [Step 1: Prepare the K-map and place 1’s according to the| siven truth table or logical expression. Fill the remaining cells by 0's. Locate the isolated 1's i.e. the 1's which cannot be| ‘combined with any other 1, Encircle such 1's. Identify the 1's which can be combined to form a| pair in only one way and encircle them. Identify the 1's which can form a quad in only one| way and encircle them. Identify the 1's which can form an octet in only ‘one way and encircle them. ‘After identifying the pairs, quads and octets, check if any 1 is yet to be encircled. If yes then encircle them with each other or with the already encircled 1's (by means of overlapping). [step 2: [step a: step: [step 5: [Step 6: = Note that the number of groups should be minimum. — Also note that any 1 can be included any number of times without affecting the expression. = Letus solve some examples on this to make the concept clear.WF ve. (sem.u1/ Comp. SPPU) Ex.1.7.1: A logical expression in the standard SOP fon is as follows Y=ABC+ABC+ABC+ABC Minimize it using the K-map technique. Soin: ¥ = Ym(0,2,3.5) ~The required K-map is as shown in Fig. P. 17.1 _—Pai't Re Mnenized expressionis at v= 5+ AS+ 08 Palet Par 2 Isolated fo | 0 fo par2-RE r+ (€250) Fig. 1.7 Ex.1.72: The logical expression representing a logic Gireuit is ¥ = Em (0, 1, 2, 5, 13, 15). Draw the K-map and find the minimized logical expression Soln. : = From the given expression, itis clear that the number of variables is 4. Vem, +m, +m, +m, + my +My = The required K-map is as shown in Fig. P. 17.2. Pait2 ACD 2 35 co] coy cB mE 3140 Part ABD B 8 8 o9| ° Re or] o ° = Pair 3+ ABD set 4 B10] 0 | 0 | o | o (251) Fig. P.1.7.2 = Minimized expression is, (case) + AOD + ABD Soy Pai Palr2 Pairs For the logical expression given below draw ‘the Kmap and obtain the simplified logical expression. Y= Em (1,5, 7,9, 14, 13, 15) Realize the minimized expression using the basic gates. 19 imization Techniques Soin. = The given expression is, YS mermermemy rma + ms + ms = It can_be expressed on shown in Fig. P. 1.7.30). K-map as owns 160. eo 4 ound? 80 | —ouss:ao 3+ spe aD 0 cdo iad ap (€252) Fig. P.1.7.3(a) Realization : Equation (1) can be realized as shown in Fig. P. 1.7.3(b). AsB4d e Dari eoe (€253) Fig. P.1.7.3(b) : Realization with minimum ‘number of gates ong o> Ex. 17 Minimize the folowing Boolean expression using K-map and realize it using the basic gates. ¥ = Em (1,3, §, 9, 11, 13) Soin. — The given expression can be expressed in terms of the rminterms as, Y= mememeem,+my+ ms = The corresponding K-map is shown in Fig. P. 1.7.4). op apX 85 6 cD cB aunts BD j — Quad 2:0 Mineized expression y=B0+00=D(8+0) fechKnowledgéWF ve. (sem.u1/ Comp. SPPU) Realization : zation Techniques 4, We would visualize 2 quad shown by dotted lines in — Fig, P.1.7.4(0) shows realization using gates Fig, P1780 O oo So/ ep cB of $1 fo Dewi a Mb) ® Using K-map realize the following expression ° using minimum number of gates. A Zm(1,3.4,5,7,9, 14,13, 15) 7 ‘@ Soin, : Solve it yoursel. 4 Ans.: Y= ABC+D ee Ex. 1.7.6: Minimize the following expression using K-map (€250 Fig. P.1.7.8(0) and realize using the basic gates. Bm (1, 2,9, 10, 11, 14, 15) Soln. : Solve it yourself. Ans.: Y=B(C@D)+AC Ex.1.7.7: Minimize the folowing expression and realize Using basic gates, Y= 3m (0, 2,5, 6,7, 8, 10,13, 15) Soln. : Solve it yoursett. Ans.: Y=BD +BD + ABC 4.7.1. Elimination of a Redundant Group : —Ifall the 1's in a group are already being used in some. fother groups, then that group is called as a redundant group. = A redundant group has to be eliminated, because it increases the number of gates required, Effect of a redundant group and its elimination is illustrated in the Ex 17.8 Ex. 8: Minimize the following expression using the K-map. Em (1,5,6,7, 11, 12, 13, 16) Soln. : 1. The given expression can be expressed in the standard SOP form as follows Y= meme mem, + my +m + mst ms where m,, mg... mjcare the minterms. 2. The required K-map is shown in Fig. P. 7.8(a), 3, There are no isolated 1's, So encircle the separate pairs as shown in Fig. P. L7.8(@) ~The question is should we encircle this quad ? = The answer will be obtained by writing the expression of Yiwithout and with this quad as follows {Expression without quad?W= AGD + ABC + ABE + ACD o @ @ ASD + Rac + ABC + ACD +80 oO @ ® Redundant quad Expression with quad : Y (©5355) Conelusion : ~ If we encircle the quad, then the expression for output consists of an additional term. So quad should not be encircled. Its called as the redundant group. ~ Hence the correct K-map is shown in Fig. P.1.7.8(b). Vat ie © as a 7 we cw to/ co ob cof 10 Holo |M:| 0} o a — Group 2: ABC ae ot] o | a. | G+] = ACD+ACD+ABC+ABC WF tonnesWF ve. (sem.u1/ Comp. SPPU) D (AG-+A0) +8 (AC +AG) 4 zation Techniques Procedure EXNOR —EX-OR (6160) Y = D(ABC)+BAGG Solve the following using minimization technique : 2=1(A,B,C,D)= 5 (0, 2,4,7, 11, 13, 16) Soin. : Simplification using K-map : WL vo rt ola or aco: 80 10 (©1692) Fig. P.1.7.9(a) B + ABD + BCD+ ACD Solve the following | equations) using Corresponding minimization techniques, also draw MSI design for the minimized output equation Z=1(A,B,0/D)=3(0, 3, 4,9, 10, 12, 14) Son. : Solve it yoursalf. eo 1.7.2. Minimization of Logic Functions not Specified in Standard SOP Form = Till now we have seen how to use the K-map to minimize an expression which is given in standard SOP form. = Now let us see the use of K-map for minimization when the given expression is not in the standard form. The procedure to be followed under such conditions is as follows = The given expression, Y = ABCD+ABCD+ABC+ABD+AC4+B lstop1: Enter 4 for minterms (ie. A BCD and ABCD) present in the given expression, [step2: Enter a pair of 1's for each term with one less variable than total (ie. for AB 6, A D because these terms have one less variable) [step 3: Enter four aojacent 1's for each term with two less variables than total (i. AC). [step 4: Repeat forthe other tems in a similar way. [step 5: Once the K-nap is obtained. the minimization procedure is same as the one discussed earlier. — This procedure will be clear as you solve the example given below, ‘Ex 17.412 _Minimize the logic equation given below: Y =ABCD + ABCD ABC +ABD + AC +B oO ® © © & cos Soin. ‘Step 1: Enter 1 in the call with A = 0, B = 0, 1 for the first term A BCD and in the cell with A B = 41,01, D =0 for the second term ABCD as shown in Fig. P. 1.7.11(a), seen wee go/e Bool o| o| + 7B o1 a apni] oto] of o, 4B 10 | Eco ap? ob feo od “cd oo for 1X 10 ie t B00 ala] yy AB ot ° 1 pv fseb asi oof oJ rol 0] o] oo ” (€26y Fig. P.1.731 Be TetloontetatWF ve. (sem.u1/ Comp. SPPU) Step 2: Step 3: Step 4: Consider the third term A & C. Enter 1 in two cells eh conespond i A= 0,8 = 0 end C= 0,28 shown in Fp. P. 711). Now corer the fourth term A B B and enter 1 in two cells which correspond Ax 0, = Owe =a shown in Fig. P. 1.7.11(b). Now consider the fifth term AC. Enter 1 in four cole coesponng to A= 1 and C= 0,28 shown in Fig. P. 1,7.11(). AB é co cd welt) ) +]: pease (€20 Fig. P.1.74@) Finaly coepondng tthe eich erm enter eight 13 coeaponan LOWS as snot Fy. A741 es a Sado ep od on mols fa] sft as otf 0 | 0 | of 0 |trose 8 ones eowrespond te the term 8 AB tt AB 10 (€-202) Fig. P.1.7.11(d) The final K-map is as shown in Fig, P. 1.7.11(@). Use the normal simplification techniques discussed earlier 10 simplify this K-map and get the minimized expression, zation Techniques oo as” 06 a cD od 00 011110, grup 0B wmolalala la ie 01 | croup 3» ACD von) apie Group 2+ AE 8 10) a) alah i croup: (€-263) Fig, P. 1.7.11(@) : Final Kemap, The simplified equation is, Y = B+aC+AcD 4.7.3 Don’t Care Conditions : For SOP form, we enter 1's corresponding to the combinations of input variables which produce a high output. And we enter Os in the remaining cells of the K-map. For the POS form we enter 0's corresponding to the combinations f inputs which produce alow output and enters in the remaining cels ofthe K-map. Buti isnot alvays true thatthe cells not containing 1's {in SOP) will contain Os because some combinations of input variable donot occur Take the example of a 4 bit BCD counter twill have valid outputs from 0000 to 1001 only. Also for some functions the outputs corresponding to certain combinations of input variables do not matter. ‘Tat means for such input combinations it does not matter whether the value of output is 0 or 1 In such stuation we are free to assume a 0 oF 1 as output fr each of such input combinations. These conditions are known as the “Don't care conditions” and in the K-map it is represented as » (cross) mark in the corresponding cel Important : ‘The don't care condition (x) may be assumed to be 0 or ‘Las per the need for simplification, ‘Simplify the expression given below using K-map. The don't care conditions are Indicated by d (). Y= m1, 3,7, 11, 15) +0 (0,2, 5) PRE Pees Be TetloontetatWF ve. (sem.u1/ Comp. SPPU) Soln. : The given equation is, Ym myemy+mzemyytimys + 40,2, 5) ao DDon' care consitons ‘a enterx marke (co16 = The required K-map is shown in Fig. P. 1.7.12, co weN” cd cB Grp? AB oor 1110 78 00 | BOT + Taf | xf} — dont care coretions amtealod at's war} o| x |Ial] o aa nt olo {it} o ae wl of o {Ly} o L Group 1:60 (€-260) Fig. P.17.12 = _ Simplified expression Y INote: Every don't care mark need not be considered| while grouping Ex.1.7.13: Simplity the following expression. once by Considering the don't care conditions and once by ignoring the don’t care condition Y= Em (1, 4,8, 12,13, 16)+d(3, 14) Soln. : art |: Simplification without don't care condition ~The K-map by neglecting the don't caré condition is shown in Fig. P. 17.130). a 86D oxcup 1 weX 2 oo foo ob wwlo|#|ofo ie or} | o | 0 | o oat on Group 4+ AB wolzi fo lo] o Simplification neglecting don't care condition D+ BCD+ ACD + ABD o ®@ © # (c305) ‘Simpttiod equation is ¥ = 3 zation Techniques Part I: Simplification with don't care conditions — The K-map including the don't care conditions is shown in Fig, P.1.7.31b). aa — Srp 4-+ FD w\ eo o/h vs fgets ee ibe ore 1 28 wa ofia' fo | o | o Perse i .13(b) : Simplification using don't care conditions ‘Dont care conditions| retried aa (6266) Fi » Simplified equation iY = AB+ ACD + BCD + ABD 0” 2 8 055) Y= AB+CDIA+ 8) ABD INote : "The dent care condition reduces the number of gates required for implementation Ex.1.7114: Minimize the folowing function using K-map and reaize using lon gates F(A.B,C,0) =m (1,3,7,11,15)44(0,2,5) Soin. = For Ksmap refer Ex 17.12. — Implementation using logic gates is as shown in Fig. 1.7.14 D+ AB a >_> Poy pb >’ (€-4185) Fig. P. 7.14 : Implementation using logic gates Ex.7.7.15: Minimize the folowing function using K-map and realize using logic gates, F(A.B,C,D) =m (1,5, 7, 13, 15) + d(0, 6, 12, 14) (OEE Be TetloontetatWF ve. (sem.u1/ Comp. SPPU) Soln. Simplfication using K-map is as shown in Fig. . 17.15. eo & tp co cd ae\ oor 10 pai — Group 1 76 00| Gayo | o ae or) o | x all" gt o Group 2: BD send x [la x arolo fo lo | o of oof Oa On (€-5100 Fig. P. 1.7.15 Implementation using logic gates is as shown in Fig. P. 1.7.15(2). be, om >i BC+ BD (€s102) Fig. P.1.7.15(@) #(AB,C.D) = ABC +80 ‘Minimize the following logic function and realize using NAND gates FIA, B, C, D) = Bm (1, 3, +402, 13), Soln. : ‘Step 1 : Simplification using K-map : co #80 aB\ 0 ot tt Step 00 off o " 10 Abe FIA8.CD) = ABiC+ 60+ AD + ABC (©5695) Fig. P. 1.7.26(a) : K-map : Implementation using NAND gate: Taking double inversion of RH, = ABC+CD+AD + ABC zation Techniques BSc -€D-AD- ABC (Using De-Morgan's theorem) = Implementation using NAND gates i as shown in Fig, P. 17.16(b). ee eee Fasc) - 1.7.16(b) : Implementation using NAND gates Ex. 17:47: Solve the following equations, corresponding minimization techniques (A,B, C,D)= 3m 27,8, 10, 14, 13, 16) (A.B.C,D)=3m 0, 3,4,9. 10, 12, 14) using 12 2. Soin, 1.22 (A,B,C D) = Em(2,7, 8, 10, 11, 13,15) co dX 00 o1_ 1130, of 0 (7928) Fig. 1.7.17(2): K-map (CB + BCD + ABD + ABC + ABD 2. z= £(A,B,C,D) = Em(0, 3, 4,9, 10, 12, 14). ‘Simplification using K-map : eo +-Aaco € BCD (©2696) Fig. 1.7.17(b) ACD+BCD +ACD+A BCDYWF ve. (sem.u1/ Comp. SPPU) Ext. 18: Soe the following reduction using K-map, also draw MSI circuit for the output 1. Z=1(AB,C,D) =5(1,2,7, 8, 10, 12, 18) +4 (0, 5,6) 2. Z=1(A.B,C,D) = (1,3,4,6,8, 11,15) +6 (0, 5,7) DRE Soln. : Solve it yourself. Ans. 1 Z=f(AB,6.0) 2 (A.B,C,0) =AD +AB+CD+BCD Ex.1.7.19: Solve the following equation using ‘corresponding minimization technique. Draw the diagram for the output Z=(A,B,C,D) ‘Em (2, 4, 6, 11, 12, 14) + d (3, 10). Sol: Solve It yourslt soa. Z = fABCO)=BD + ¢ 20: Solve the following equation using K map ‘minimization technique. Draw the MSI design for the minimized output : Z=f(A/B,C,D) sm (1,9, 6, 7, 12, 13) + (0, 2,8, 9) DE Solve it yourself B+aeg 18 Simplification : Product of Sum (POS) 1.8.1 K-map Representation of POS Form : = The POS form equations consist of maxterms. = In the K-map corresponding to POS form equation we have to enter a 0 corresponding to each maxterm. = The K-maps corresponding to the POS form are shown, in Fig. 1.81. 8 3 A AR a _o 1 e\_o 1 Aol ase | ase Bo] ase | Ave on Ail Ase | Ase Bal ase | Ave (286) Fig, 1.8.1(a) : Two variable K-map for POS form ec a0 ot 4 to O]A+B4+C/A+B4 G]AF5+ClA+B4c] A+B+C/A+B4ClA+B+C/A+B+C AB, On \ 00 on u 10 ofase+cla+s+clA+B+cla+a+o JA+B+C/A+B4C/A#8+C/A+B4C| (€-286)(b) Three variable K-map for POS form oo ok ot 4 10 a 0 cola sBac+ 0) AsBsc+0| AvBeC4d oifas BeO+D|A+B+0+0] Av8+0+0 nfAs8+c+D|AsB+c+0/ A+ Reo+Ge tolAeBec+D|AvB+o+5 Ase+d+9] (© Four variable K-map for POS form (6286) Fig. 1.8.1 ‘The entries in the K-map can be shown in terms of the ‘maxterms My M, ... tc. ag shown in Fig. 18.2, ) Fig. 1.8.2(Contd..) Be TetloontetatWF ve. (sem.u1/ Comp. SPPU) D AQ or 30 00] Mo | M, My or] Ma My | Me ni] Me | Mao | Mis | Me 10] Me Mu | Mo © (€287 Fig. 1.8.2: Kemap in terms of maxterms 1.8.2. Representation of Standard POS Form x4 on K-map : Logical expressions in the standard POS form can be represented on K-map by entering 0's in the cells of K-map corresponding to each maxterm present in the given equation, The remaining cells are filled with 1's This technique is illustrated in Ex. 1.8.1. 1; Represent the folowing standard POS expression on Kamaugh map. (A+B +0)(A+8+0)(A+B+0). Soln. : Each term inthe given logical equation is a maxterm. Enter @ 0 corresponding to each maxterm as shown in Fig. P18. ‘The given expression has three maxterms as follows (A+8+0 = My (AsB+Q = My AsB+C) = Mm Hence we have tO write the structure of 3 variable K-map as usual and enter O's at My , Mz and Mg as shown in Fig. P.1.8.. 7 My= (+840) \ 86.66 _sc 36. + ° TL fed reer on ao MBSA BHO) aX oo! or 1110 obeys 71 od Merrseo 1 vdite Mg=(A+ 8 +0) 1.8.1: Representation of standard POS on K-map 8 zation Techniques Ex.1.82: Represent the following standard POS ‘equation on the Kamaugh map. Y=A+B+C+B)A+B+E+D) (A+8+6+5)@+5+0+0) Soin. ~The given expression contains four maxterms as follows ss oo s o My M, BsB+eyD) 2M, ~ Enter a 0 €orresponding to each maxterm as shown in Fig, P.1.82. M,=asB 4040 My=A+8+E+5 CD i ABN _€6_6D.“ep. cB Mip=(@+B+0+0) on M=AsB+04+5 +845+5 oo v8 00 01." 1110 of Jefe] or o- M,=A4+B4540 °. feral sol ssl 10 dd ul ol (A+B+0+D) (€-285) Fig. P. 1.8.2: Representation of standard POS on K-map 1.8.3. Simplification of Standard POS Form using K-map : Minimization procedure : 1. The given POS expression consists of maxterms, 2. Corresponding to every maxterm enter a 0 in the K- wien