Karnaugh Maps : Part 2 - Map Rolling, Overlapping groups, Redundant groups - and some examples and problems

Number System


  Digital Electronics : Karnaugh Maps Part 2

K Maps Tutorial, Digital Electronics

Here's a quick note about the topics which will be introduced in this tutorial :

Map Rolling

A pair, quad or an octet can be formed by combining the adjacent ones in rectangular form. A combination can also be obtained by rolling the map (just like a world map is rolled to combine the left-most and right- most edges) along its length or width. This is called map rolling.

Overlapping groups

The groups (pairs/quads/octets) that we form can also overlap each other. It means that a single value can be contained in more than one group.

Redundant groups

A group which has all its values also contained in some other groups is called a redundant group. A redundant group must be removed as it just adds extra terms.

Here are the kind of the problems you will learn to solve in this tutorial :

F = X’Y’Z’ + X’Y’Z + XYZ’ + XY’Z + XYZ

To reduce a Boolean expression using K-map, first make the K-map for the expression. Now group the 1s in the priority order— Octet quad pair single value. That is, make octets wherever possible than quads than pairs. After that, remove the redundant groups. Then write the reduced terms for the remaining groups and add them all. The result is your reduced expression.

Complete Tutorial with Examples of K-Maps :

Here's a list of all the tutorials we currently have in this area - Introductory Digital Electronic Circuits and Boolean logic

 Introduction to the Number System : Part 1
Introducing number systems. Representation of numbers in Decimal, Binary,Octal and Hexadecimal forms. Conversion from one form to the other.
 Number System : Part 2
Binary addition, subtraction and multiplication. Booth's multiplication algorithm. Unsigned and signed numbers. 
Introduction to Boolean Algebra : Part 1
 Binary logic: True and false. Logical operators like OR, NOT, AND. Constructing truth tables. Basic postulates of Boolean Algebra. Logical addition, multiplication and complement rules. Principles of duality.  Basic theorems of boolean algebra: idempotence, involution, complementary, commutative, associative, distributive and absorption laws. 
Boolean Algebra : Part 2
De-morgan's laws. Logic gates. 2 input and 3 input gates. XOR, XNOR gates. Universality of NAND and NOR gates. Realization of Boolean expressions using NAND and NOR. Replacing gates in a boolean circuit with NAND and NOR.
  Understanding Karnaugh Maps : Part 1Introducing Karnaugh Maps. Min-terms and Max-terms. Canonical expressions. Sum of products and product of sums forms. Shorthand notations. Expanding expressions in SOP and POS Forms ( Sum of products and Product of sums ). Minimizing boolean expressions via Algebraic methods or map based reduction techniques. Pair, quad and octet in the context of Karnaugh Maps.

Karnaugh Maps : Part 2
Map rolling. Overlapping and redundant groups. Examples of reducing expressions via K-Map techniques.
 Introduction to Combinational Circuits : Part 1
Combinational circuits: for which logic is entirely dependent of inputs and nothing else. Introduction to Multiplexers, De-multiplexers, encoders and decoders.Memories: RAM and ROM.  Different kinds of ROM - Masked ROM, programmable ROM. 
 Combinational Circuits : Part 2
 Static and Dynamic RAM, Memory organization.
Introduction to Sequential Circuits : Part 1
Introduction to Sequential circuits. Different kinds of Flip Flops. RS, D, T, JK. Structure of flip flops. Switching example. Counters and Timers. Ripple and Synchronous Counters. 
Sequential Circuits : Part 2
ADC or DAC Converters and conversion processes. Flash Converters, ramp generators. Successive approximation and quantization errors.