Boolean Expression Simplification using Karnaugh Maps

Why Gate Level Minimization

This is the design task of finding an optimal gate level implementation of the Boolean function describing a digital circuit. There are many advantages in gate level minimization. Minimize the number of gates used reduces the cost.  It also minimizes the total delay (critical path delay). So if the delay reduce it cause a performance improvement. Minimization is important since it reduces the complexity and satisfy design constraints. But it is difficult to execute by manual when the logic has more inputs. Computer based logic synthesis tools are used to it efficiently and quickly. This lecture will help you to get a foundation understanding of gate level minimization. You will able to execute a manual design of simple circuits using Karnaugh map.

Map Method

Boolean expression may be simplified by algebraic means. But the procedure of minimization is complex because there is not a specific procedure to follow. It lacks specific rules to predict each succeeding step in the manipulative process. Map method is a pictorial form of a truth table used to minimize Boolean expression without having to use Boolean algebra theories.  Map method provides a simple, straightforward procedure for minimizing Boolean functions. This method also known as Karnaugh map or K-map.

Karnaugh Map (K- Map)

  • A diagram made up of squares
  • The collection of squares is a graphical representation of a Boolean function.
  • Each square represents one Minterm of the function that is to be minimized.
  • The Minterms are arrange not in a binary sequence, but in a sequence similar to the Gray code.
  • The simplified expression produced by the map are always in one of the two standard forms which are sum of products or product of sums.
  • Alternative algebraic expression for the same function are derived by recognizing patterns of squares.

Two Variable K-Map

There are four Minterms for two variable function. Map consist of four squares, one for each Minterm.

Minterm and maxterm

Minterm m0 and minterm m1 are adjacent and differ in the value of the variable y. similarly, minterm m0 and minterm m2 differ in the x variable. Also, m1 and m3 differ in the x variable as well. Finally, m2 and m3 differ in the value of the variable y.

K-Map and Truth tables

The K-Map is just a different form of the truth table. As an example consider a two variable function. We choose a, b, c and d from the set {0,1} to implement a particular function, F (x, y).

Boolean algebra truth table
K map

Karnaugh Map Function Representation

Example F (x, y) = x

For function F (x, y), the two adjacent cells containing 1’s can be combined using the Minimization theorem.

K map

F (X, Y) = XȲ + XY =X

Three Variable Karnaugh Map

There are Eight minterms for three variables. The map consists of eight squares, one for each minterm where each minterm corresponds to the product terms.

Karnaugh Map

K Map Grouping Rules

Group may not include any cell containing a zero

Karnaugh Map

Groups may be horizontal or vertical, but not diagonal

K Map

Groups must contain 1, 2, 4, 8 or in general 2n cells. That is if n=1, a group will contain two 1’s since 21=2. If n=2, a group will contain four 1’s since 2n = 4.

K Map

Each group should be as large as possible

Karnaugh Map

Groups may overlap

K Map

Groups may wrap around the table. The leftmost cell in a row may be grouped with the rightmost cell and the top cell in a column may be grouped with the bottom cell.

K Map

Each cell containing a one must be in at least one group.

Karnaugh Map

There should be as few groups as possible, as long as this does not contradict any of the previous rules.

K Map

Table of Contents

3 thoughts on “Boolean Expression Simplification using Karnaugh Maps”

  1. Pingback: Combinational Circuits Part I -

  2. Pingback: Combinational Circuit II - Binary Adders and Subtractors

  3. Long time supporter, and thought I’d drop a comment.

    Your wordpress site is very sleek – hope you don’t mind me asking what theme
    you’re using? (and don’t mind if I steal it? :P)

    I just launched my site –also built in wordpress like yours– but the theme slows (!) the site
    down quite a bit.

    In case you have a minute, you can find it by searching
    for “royal cbd” on Google (would appreciate any feedback) –
    it’s still in the works.

    Keep up the good work– and hope you all take care of yourself during the coronavirus scare!

Leave a Comment

Your email address will not be published. Required fields are marked *