## 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 m_{0} and minterm m_{1} are adjacent and differ in the value of the variable y. similarly, minterm m_{0} and minterm m_{2} differ in the x variable. Also, m_{1} and m_{3} differ in the x variable as well. Finally, m_{2} and m_{3} 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).

## 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.

*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.

## K Map Grouping Rules

Group may not include any cell containing a zero

Groups may be horizontal or vertical, but not diagonal

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

Each group should be as large as possible

Groups may overlap

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.

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

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

## 3 thoughts on “Boolean Expression Simplification using Karnaugh Maps”

Pingback: Combinational Circuits Part I -

Pingback: Combinational Circuit II - Binary Adders and Subtractors

JustinLong 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!