Understanding Karnaugh Maps Part 1 - Introducing Literals, Min-terms, Max-terms, Canonical Expressions, Sum-Of-Product (SOP) and Product-Of-Sum(POS) Forms and Expansions


Number System

 



                                                                                                                    --------------xxxxx--------------



  Digital Electronics : Karnaugh Maps Part 1

 

 
K Maps Tutorial, Digital Electronics

Here's a quick walk through of the ideas which will be introduced in this tutorial


Karnaugh Maps / K-maps


Before going through the Karnaugh maps, some terms need to be clarified. These are as follows—

• Literals : 

A literal is a single logic variable or its complement. For example— X, Y, A’, Z, X’, etc.

• Minterms: 

A minterm is the product of all the literals with or without complement involved in a logic system.

For example—
AB, A’B, AB’, A’B’ (for a problem containing only A and B),
A’BC, ABC, AB’C… (for a problem containing A, B and C)
When the values of different variables are given, minterms can be easily formed as- 
If X=0, Y=0 minterm would be X’Y’
If X=1, Y=0, Z=1 minterm would be XY’Z
So, use the variable with value 1 as it is and variable with value 0 as complemented to find the minterm.

• Maxterm: 

A maxterm is the sum of all the literals with or without complement involved in a logic system.
For example—
A+B, A+B’, A’+B, A’+B’ (for problem containing only A and B)
A+B+C, A’+B+C’, … (for problem containing A, B and C)
When the values of different variables are given, maxterms can be easily formed as-
If X=0, Y=0 maxterm would be X+Y
If X=1, Y=0, Z=1 maxterm would be X’+Y+Z’
So use the variable with value 1 as complemented and variable with value 0 as it is to find the maxterm.

• Canonical expressions

A Boolean expression containing entirely of minterms or maxterms is known as canonical expression. These are of two types—

 • Sum Of Product(SOP form)

It is the sum of all the minterms that result in a true value of the output variable. For example—
XY’+X’Y+XY
XYZ’+X’YZ+X’Y’Z+XYZ
AB+AB’

• Product Of Sums(POS form)

It is the product of all the maxterms that result in a false value of the output variable. For example—
(X+Y’)(X’+Y)(X+Y)
(X+Y+Z’)(X’+Y+Z)(X’+Y’+Z)(X+Y+Z)

(A+B)(A+B’)


• Shorthand notation


The minterms and the maxterms can be represented by shorthand notation which makes it very easy and fast to write and work with. Shorthand notations can be obtained as follows-

• For minterm representation


To represent a minterm as shorthand notation following steps are to be followed-
1. Write 0 for a complemented term and 1 for non-complemented term. This will give you a binary number.
2. The shorthand notation will be an ‘m’ with the decimal equivalent of the binary number as subscript of ‘m’.

Eg.
The minterm XYZ’ is represented as- XYZ’ will be represented as— XYZ’ --> 110 => So  we get m6

•  For maxterm representation

To represent a maxterm as shorthand notation following steps are to be followed-
Write 1 for a complemented term and 0 for non-complemented
The shorthand notation will be a capital ‘M’ with the decimal term. This will give you a binary number equivalent of the binary number as subscript of ‘M’.

Eg. The minterm X+Y’ is represented as- X+Y+Z’ will be represented as— X+Y’+Z --> 010 => So M2

Minterm expansion of an expression

Any expression can be represented using minterms. To find the minterm expansion of an expression following steps have to be followed-
1. Write down all the terms in the expression
2. Put X where ever a literal is missing to convert the terms to minterms
3. Use all the combinations of Xs to find minterms
4. Remove the duplicate/repeated terms and write the terms together.

Complete Tutorial with Examples :



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 1 Introducing 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. 
 


 



Comments