Looking for a Tutor Near You?

Post Learning Requirement »
x

Choose Country Code

x

Direction

x

Ask a Question

x

x
x
For better view click here
x
Hire a Tutor
DISCOVER

Digital Electronics Circuit Optimisation Using K-MAPs I

Loading...

Published in: Physics
6,140 Views

This tutorial introduces the concept of Karnaugh Map(also called popularly as K-MAP) for the digital combinational circuit implementations of two and three variables. It will show that how a particular two or three variable canonical form can be converted in the form of a graphical representation like that of a Karnaugh Map.

Parag P / Indore

10 years of teaching experience

Qualification: M. Tech. Embedded Systems

Teaches: Algebra, Mathematics, Physics, Statistics, Electronics

Contact this Tutor
  1. Digital Electronics Presentation on Lecture 8 : Circuit Optimisation using K- Maps-I Presented By : Parag Parandkar
  2. Acknowledgement The presenter would like to thanks and acknowledge for the adoption of slides from Logic and Computer Design fundamentals 4th Edition by Charles Kime and Thomas for 2008 Pearson Education limited. > The copyrights belongs to the original author. The presentation is being used for educational and non commercial purpose.
  3. Contents Circuit Optimisation Cost Criteria > Boolean function optimisation Introducing K Map > 2 Variable K-Map > 3 variable K-Map Application of K-Map : 1 bit adder
  4. Circuit Optimization ' Goal: To obtain the simplest implementation for a given function Optimization is a more formal approach to simplification that is performed using a specific procedure or algorithm Optimization requires a cost criterion to measure the simplicity of a circuit Distinct cost criteria we will use: — Literal cost (L) — Gate input cost (G)
  5. Cost Criteria Literal Count: — Simple to evaluate by counting all literals — However, does not represent circuit complexity accurately in all cases ' Gate Input Cost (or Count): — Good measure of logic implementation — Proportional to the number of transistors and wires used in the implementation — Important when measuring cost of circuits with more than two levels
  6. Boolean Function Optimization Minimizing the gate input (or literal) cost of a Boolean equation reduces the circuit cost We choose gate input cost ' Boolean Algebra and graphical techniques are tools to minimize cost criteria values Some important questions: — When do we stop trying to reduce the cost? — Do we know when we have a minimum cost? Treat optimum or near-optimum cost functions for two-level (SOP and POS) circuits first ' Introduce a graphical technique using Karnaugh maps (K-maps for short)
  7. Karnaugh Map (K-map) A K-map is a collection of squares — Each square represents a minterm — The collection of squares is a graphical representation of a Boolean function — Adjacent squares differ in the value of one variable — Alternative algebraic expressions for the same function are derived by recognizing patterns of squares The K-map can be viewed as — A reorganized version of the truth table
  8. Karnaugh Map (K-map) A K-map is a collection of squares — Each square represents a minterm — The collection of squares is a graphical representation of a Boolean function — Adjacent squares differ in the value of one variable — Alternative algebraic expressions for the same function are derived by recognizing patterns of squares The K-map can be viewed as — A reorganized version of the truth table
  9. Karnaugh maps Alternate way of representing Boolean function All rows of truth table represented with a square — Each square represents a minterm Easy to convert between truth table, K-map, and SOP — Unoptimized form: number of I 's in K-map equals number of minterms (products) in SOP — Optimized form: reduced number of minterms 0 x'y' xy' F o 1
  10. simplification procedure. Two variable maps. 01 01 F=AB '+A'B 110 Three variable maps. BC oo 01 11 10 Karnaugh Maps A Karnaugh map is a graphical tool for assisting in the general 01 11 o 1 F=AB +A'B ' 1 A o o o o 1 1 1 1 B 0 o 1 1 o o 1 1 o 1 0 1 o 1 o 1 o 1 1 1 1 1 1 F-AB 'C ' +AB 'C +ABC +ABC ' C + A' BC'
  11. Rules for K-Maps We can reduce functions by circling 1 's in the K-map • Each circle represents minterm reduction • Following circling, we can deduce minimized and-or form. Rules to consider O Every cell containing a 1 must be included at least once. O The largest possible "power of 2 rectangle" must be enclosed. The I 's must be enclosed in the smallest possible number of rectangles. Example
  12. Karnaugh Maps A Karnaugh map is a graphical tool for assisting in the general simplification procedure. Two variable maps. 01 01 F=AB '+A'B 110 Three variable maps. BC oo 01 11 10 o 11 1 1 F=AB +A'B +AB ' F=A+B 11 1 1 1 F=A+B'C+BC' F-AB 'C' +AB 'C +ABC +ABC' + A'B'C + A'BC'
  13. Karnaugh maps Numbering scheme based on Gray—code - e.g., 00, 01, 11, 10 Only a single bit changes in code for adjacent map cells This is necessary to observe the variable transitions AB c oo 01 10
  14. More Karnaugh Map Examples a 01 b ' Examples 001 ab oo 01 11 10 C 00010 cout = ab + bc + ac 1. Circle the largest groups possible. a b 100 C ab oo 01 11 10 man 2. Group dimensions must be a power of 2. 3. Remember what circling means !
  15. Some Uses of K-Maps ' Provide a means for: — Finding optimum or near optimum ' SOP and POS standard forms Two-level AND/OR and OR/AND circuits for functions with small numbers of variables — Visualizing concepts related to manipulating Boolean expressions, and — Demonstrating concepts used by computer-aided design programs to simplify large circuits
  16. Application of Karnaugh Maps: One-bit Adder Cin The o o o Adder 1 1 1 Cout B o o 1 o o 1 Cin o 1 o o 1 o S Cout o o How to use a Karnaugh Map instead of the Algebraic simplification? S = A'B'Cin + A'BCin' + A'BCin + ABCin Cout A'BCin + A B 'Cin + ABCin' + ABCin = BCin + ACin + AB
  17. Application of Karnaugh Maps: One-bit Adder The Cin Adder Cout s 1 1 Cin A O O 1 1 1 B O 1 1 O 1 1 1 Cin O 1 1 1 O 1 S O 1 1 O 1 O O 1 Cout O 1 1 1 1 Now we have to cover all the Is in the Karnaugh Map using the largest rectangles and as few rectangles as we can. Karnaugh Map for Cout
  18. Application of Karnaugh Maps: One-bit Adder The Cin Adder Cout s A O O 1 1 1 B O 1 1 O 1 1 1 Cin O 1 1 1 O 1 S O 1 1 O 1 O O 1 Cout O 1 1 1 1 0010 Now we have to cover all the Is in the Karnaugh Map using the largest rectangles and as few rectangles as we can. Cin Cout = ACin Karnaugh Map for Cout
  19. Application of Karnaugh Maps: One-bit Adder The Cin Adder Cout s A O O 1 1 1 B O 1 1 O 1 1 1 Cin O 1 1 1 O 1 S O 1 1 O 1 O O 1 Cout O 1 1 1 1 0010 Now we have to cover all the Is in the Karnaugh Map using the largest rectangles and as few rectangles as we can. Cin Cout = Acin + AB Karnaugh Map for Cout
  20. Application of Karnaugh Maps: One-bit Adder The Cin Adder Cout s A O O 1 1 1 B O 1 1 O 1 1 1 Cin O 1 1 1 O 1 S O 1 1 O 1 O O 1 Cout O 1 1 1 1 0010 Now we have to cover all the Is in the Karnaugh Map using the largest rectangles and as few rectangles as we can. Cin Cout = ACin + AB + BCin Karnaugh Map for Cout
  21. Application of Karnaugh Maps: One-bit Adder The Cin Adder Cout o 1 A O O 1 1 1 B O 1 O 1 Cin O 1 1 O S Cout O 1 1 O B 1 o o 1 Cin Karnaugh Map for S S -A'BCin'
  22. Application of Karnaugh Maps: One-bit Adder The Cin A O O Adder 1 1 Cout BIO 10 Cin Karnaugh Map for S B O 1 O 1 Cin O 1 1 O S Cout O 1 1 O S = A'BCin' + A'B'Cin
  23. Application of Karnaugh Maps: One-bit Adder The Cin A O O Adder 1 1 Cout 0101 Cin Karnaugh Map for S B O 1 O 1 Cin O 1 1 O S Cout O 1 1 O S = A'BCin' + A'B'Cin + ABCin
  24. Application of Karnaugh Maps: The One-bit Adder Can you draw the circuit diagrams? Cin Adder Cout A O O s 1 1 1 1 B O 1 1 O 1 1 S Cin O 1 1 1 O 1 S O 1 1 O 1 O O 1 Cout 1 1 1 1 Cin Karnaugh Map for S A'BCin' + A' B 'Cin + ABCin + AB 'Cin' No Possible Reduction!
  25. Summary Karnaugh map allows us to represent functions with new notation Representation allows for logic reduction. Implement same function with less logic Each square represents one minterm Each circle leads to one product term Not all functions can be reduced Each circle represents an application of: Distributive rule -- x(y + z) = xy + xz Complement rule x + x' = I

Need a Tutor or Coaching Class?

Post an enquiry and get instant responses from qualified and experienced tutors.

Post Requirement

Related PPTs

Upload PPTs

If you have your own PowerPoint Presentations which you think can benefit others, please upload on LearnPick. For each approved PPT you will get 100 Credit Points and 100 Activity Score which will increase your profile visibility.

Upload Now
Home > PowerPoint Slides > Digital Electronics Circuit Optimisation Using K-MAPs I