Skip to main content

Boolean Expression Simplification

The k-map Method

The "Karnaugh Map Method", also known as k-map method, is popularly used to simplify Boolean expressions. The map method is first proposed by Veitch and then modified by Karnaugh, hence it is also known as "Veitch Diagram". The map is a diagram made up of squares (equal to 2 power number of inputs/variables). Each square represents a minterm, hence any Boolean expression can be represented graphically using a k-map.


The above diagram shows two (I), three (II) and four (III) variable k-maps. The number of squares is equal 2 power number of variables. Two adjacent squares will differ only by one variable. The numbers inside the squares are shown for understanding purpose only. The number shown corresponds to a minterm in the the Boolean expression.

Simplification using k-map:
  • Obtain the logic expression in canonical form.
  • Identify all the minterms that produce an output of logic level 1 and place 1 in appropriate k-map cell/square. All others cells must contain a 0.
  • Every square containing 1 must be considered at least once.
  • A square containing 1 can be included in as many groups as desired.
  • There can be isolated 1's, i.e. which cannot be included in any group.
  • A group must be as large as possible. The number of squares in a group must be a power of 2 i.e. 2, 4, 8, ... so on.
  • The map is considered to be folded or spherical, therefore squares at the end of a row or column are treated as adjacent squares.
The simplest Boolean expression contains minimum number of literals in any one in sum of products or products of sum. The simplest form obtained is not necessarily unique as grouping can be made in different ways.

Valid Groups

The following diagram illustrates the valid grouping k-map method.


Simplification: Product of Sums

The above method gives a simplified expression in Sum of Products form. With slight modification to the above method, we can get the simplified expression in Product of Sums form. Group adjacent 0's instead of 1's, which gives us the complement of the function i.e. F'. The complement of obtained F' gives us the required expression F, which is done using the DeMorgan's theorem. See Example-2 below for better understanding.

Examples:

1. Simplify F(A, B, C) = Σ (0, 2, 4, 5, 6).

The three variable k-map of the given expression is:


The grouping is also shown in the diagram. Hence we get,
F(A, B, C) = AB' + C'


2. Simplify F(A, B, C) = Σ (0, 2, 4, 5, 6) into Product of Sums.

The three variable k-map of the given expression is:


The 0's are grouped to get the F'.
F' = A'C + BC

Complementing both sides and using DeMorgan's theorem we get F,
F = (A + C')(B' + C')


3. Simplify F(A, B, C, D) = Σ( 0, 1, 4, 5, 7, 8, 9, 12, 13)


The four variable k-map of the given expression is:


The grouping is also shown in the diagram. Hence we get,
F(A, B, C, D) = C' + A'BD

Comments

Anonymous said…
This comment has been removed by the author.

Popular posts from this blog

Digital Design Interview Questions - All in 1

1. How do you convert a XOR gate into a buffer and a inverter (Use only one XOR gate for each)? Answer 2. Implement an 2-input AND gate using a 2x1 mux. Answer 3. What is a multiplexer? Answer A multiplexer is a combinational circuit which selects one of many input signals and directs to the only output. 4. What is a ring counter? Answer A ring counter is a type of counter composed of a circular shift register. The output of the last shift register is fed to the input of the first register. For example, in a 4-register counter, with initial register values of 1100, the repeating pattern is: 1100, 0110, 0011, 1001, 1100, so on. 5. Compare and Contrast Synchronous and Asynchronous reset. Answer Synchronous reset logic will synthesize to smaller flip-flops, particularly if the reset is gated with the logic generating the d-input. But in such a case, the combinational logic gate count grows, so the overall gate count savings may not be that significant. The clock works as a filter for sma

XMR: Cross Module Reference

Cross Module Reference   Cross Module Reference abbreviated as XMR is a very useful concept in Verilog HDL (as well as system Verilog). However it seems to be less known among many users of Verilog. XMR is a mechanism built into Verilog to globally reference (i.e., across the modules) to any nets, tasks, functions etc. Using XMR, one can refer to any object of a module in any other module, irrespective of whether they are present below or above its hierarchy. Hence, a XMR can be a:   Downward reference OR Upward reference   Consider the following hierarchy:     Module A   Net x   Instance P of Module B     Net x   Instance M of Module D   Net x   Instance Q of Module C   Net x   Instance N of Module E    Net x   Instance R of Module B   Net x   Instance M of Module D   Net x     In test bench:   Instance top of Module A   In the above scenario, there is a

Synchronous Reset vs. Asynchronous Reset

Why Reset? A Reset is required to initialize a hardware design for system operation and to force an ASIC into a known state for simulation. A reset simply changes the state of the device/design/ASIC to a user/designer defined state. There are two types of reset, what are they? As you can guess them, they are Synchronous reset and Asynchronous reset. Synchronous Reset A synchronous reset signal will only affect or reset the state of the flip-flop on the active edge of the clock. The reset signal is applied as is any other input to the state machine. Advantages: The advantage to this type of topology is that the reset presented to all functional flip-flops is fully synchronous to the clock and will always meet the reset recovery time. Synchronous reset logic will synthesize to smaller flip-flops, particularly if the reset is gated with the logic generating the d-input. But in such a case, the combinational logic gate count grows, so the overall gate count savings may not be