Engineers Garage

  • Electronic Projects & Tutorials
    • Electronic Projects
      • Arduino Projects
      • AVR
      • Raspberry pi
      • ESP8266
      • BeagleBone
      • 8051 Microcontroller
      • ARM
      • PIC Microcontroller
      • STM32
    • Tutorials
      • Audio Electronics
      • Battery Management
      • Brainwave
      • Electric Vehicles
      • EMI/EMC/RFI
      • Hardware Filters
      • IoT tutorials
      • Power Tutorials
      • Python
      • Sensors
      • USB
      • VHDL
    • Circuit Design
    • Project Videos
    • Components
  • Articles
    • Tech Articles
    • Insight
    • Invention Stories
    • How to
    • What Is
  • News
    • Electronic Product News
    • Business News
    • Company/Start-up News
    • DIY Reviews
    • Guest Post
  • Forums
    • EDABoard.com
    • Electro-Tech-Online
    • EG Forum Archive
  • DigiKey Store
    • Cables, Wires
    • Connectors, Interconnect
    • Discrete
    • Electromechanical
    • Embedded Computers
    • Enclosures, Hardware, Office
    • Integrated Circuits (ICs)
    • Isolators
    • LED/Optoelectronics
    • Passive
    • Power, Circuit Protection
    • Programmers
    • RF, Wireless
    • Semiconductors
    • Sensors, Transducers
    • Test Products
    • Tools
  • Learn
    • eBooks/Tech Tips
    • Design Guides
    • Learning Center
    • Tech Toolboxes
    • Webinars & Digital Events
  • Resources
    • Digital Issues
    • EE Training Days
    • LEAP Awards
    • Podcasts
    • Webinars / Digital Events
    • White Papers
    • Engineering Diversity & Inclusion
    • DesignFast
  • Guest Post Guidelines
  • Advertise
  • Subscribe

Gate Level Minimization – DE Part 7

By Hai Prasaath K January 30, 2022

In the previous tutorial, all the possible boolean functions between two variables were discussed. In the tutorial – Boolean Algebra, various theorems and postulates were stated which are useful in simplifying a boolean expression or function. However, the simplification of a boolean expression using theorems and postulates is quite cumbersome and prone to errors. Therefore, for simplification of boolean expressions, some map methods were devised. The most commonly used map method is Karnaugh Map or K-Map.

These methods are based on the fact that every boolean function has a unique truth table. A boolean function can be represented by several boolean expressions but its truth table will always remain the same. This is due to the fact that a digital circuit will always have fixed outputs or response corresponding to the inputs. Let us first discuss, K-map.

Karnaugh Map –

The Karnaugh map is the most common simplification technique for boolean expressions. It is based on the following facts –

1) Any boolean function however may be represent able in several forms or boolean expressions always have a unique truth table. If two boolean expressions have same truth table, they are the same function.

2) Any boolean function can be represented by sum of products (Minterms) or product of sums (Maxterms).

3) The sum of Minterms or product of Maxterms is reducible by applying various boolean theorems.

The K-map is basically a tabular representation of the truth table. For example, a two-variable function can have the following truth table –

      Truth Table of a Two-Variable Boolean Function

Fig. 1: Truth Table of a Two-Variable Boolean Function

Its K-map will tabulate the function outputs corresponding to input variable values as follow –

Image showing K-Map of a Two-Variable Boolean Function

Fig. 2: Image showing K-Map of a Two-Variable Boolean Function

K-Map is useful is minimizing boolean expressions containing up to 5 variables or less. Once the map is constructed, the minimized expression can be deduced by the following process –

1) Enter 1s in those cells corresponding to the combinations for which the function value is 1 in the truth table. Then, fill 0s in the remaining cells of the K-map. Each cell in the map represents a Minterm. The boolean function represented by the map (the map is just a graphical representation of truth table) is sum of the minterms which may contain one or more boolean variables as literals.

2) Examine the map for 1-valued cells that cannot be combined with any other 1-valued cell or form groups with other 1-valued cells. That means identify 1-valued cells that have no adjacent 1-valued cell. Such groups represent minterms containing all the boolean variables as literals in the term as part of the boolean function.

3) Examine the map for 1-valued cells that are adjacent to only one another 1-valued cell and form groups containing only two 1-valued cells but are not part of any group containing four or eight 1-valued cells. Such groups represent minterms containing boolean variables as literals one less than the maximum number of boolean variables in the term as part of the function. Such groups are called pairs.

4) Examine the map for 1-valued cells that are adjacent to only three another 1-valued cells and form groups containing only four 1-valued cells but are not part of any group containing eight 1-valued cells. Such groups represent minterms containing boolean variables as literals two less than the maximum number of boolean variables in the term as part of the function. Such groups are called quads. In a 2-variable function, the formation of quad means the output of function is 1.

5) Examine the map for 1-valued cells that are adjacent to seven another 1-valued cells and form groups containing eight 1-valued cells but are not part of any group containing sixteen or higher 1-valued cells. Such groups represent minterms containing boolean variables as literals three less than the maximum number of boolean variables in the term as part of the function. Such groups are called octets. In a 3-variable function, the formation of octet means the output of function is 1.

6) Form all the groups of singles, pairs, quads and octets such that there are minimum number of groups. The pairs, quads and octets can also be formed with the combination of 1-valued cells at opposite edges of the map. Like in the following K-map for 3-variable boolean function, m0 and m8 at the corners are forming a pair.

Image showing K-Map of a Three-Variable Boolean Function

Fig. 3: Image showing K-Map of a Three-Variable Boolean Function

7) Remove any redundant groups.

8) A 1-valued cell with no adjacent 1-valued cell gives a Minterm containing 2, 3, 4, 5 variable term for 2-variable, 3-variable, 4-variable and 5-variable boolean function or K-map respectively. A pair of 1-valued cells gives a Minterm containing 1, 2, 3, 4 variable term for 2-variable, 3-variable, 4-variable and 5-variable boolean function or K-map respectively. A quad of 1-valued cells gives a Minterm containing 1, 2, 3 variable term for 3-variable, 4-variable and 5-variable boolean function or K-map respectively. The formation of quad for a 2-variable function means it is equal to 1. An octet of 1-valued cells gives a Minterm containing 2 or 3 variable term for 4-variable and 5-variable boolean function or K-map respectively. The formation of octet for a 3-variable function means it is equal to 1.

9) If a single 1-valued cell is identified, it represents a Minterm having the boolean variable as literal in the term for been matched to value of 1 for the respective boolean variable and/or having complement of the boolean variable as literal in the term for been matched to value 0 for the respective boolean variable. Such 1-valued cell will induct a Minterm in the function containing all the boolean variables either in compliment or normal form. If a pair is identified, one boolean variable will be eliminated and a Minterm containing one less number of maximum boolean variables is inducted in the boolean function. Similarly, a quad leads to elimination of two boolean variables in the Minterm and so on. The boolean variable having a bit change within the pair, quad or octet is eliminated in the term.

10) The boolean function is the logical sum of the Minterms generated by all the groups. The boolean function as product of sum can be similarly generated by groups of 0s.

Two-variable K-map –

A two-variable K-map has four cells as the maximum number of minterms possible with two boolean variables is 4 (2^2). There can be maximum 16 functions (2^2*2) generated by two boolean variables.

Image showing K-Map of a Two-Variable Boolean Function by Minterms

Fig. 4: Image showing K-Map of a Two-Variable Boolean Function by Minterms

A function generated by a two-variable K-map is reducible by single 1-valued cells or pairs. The formation of a quad in two-variable K-map means the function is equal to 1.

Three-variable K-map –

A three-variable K-map has eight cells as the maximum number of minterms possible with three boolean variables is 8 (2^3). There can be maximum 64 functions (2^2*3) generated by three boolean variables.

Image showing K-Map of a Three-Variable Boolean Function by Minterms

Fig. 5: Image showing K-Map of a Three-Variable Boolean Function by Minterms

A function generated by a three-variable K-map is reducible by single 1-valued cells, pairs or quad. The formation of an octet in three-variable K-map means the function is equal to 1.

Four-Variable K-map –

A four-variable K-map has sixteen cells as the maximum number of minterms possible with four boolean variables is 16 (2^4). There can be maximum 256 functions (2^2*4) generated by four boolean variables.

Image showing K-Map of a Four-Variable Boolean Function by Minterms

Fig. 6: Image showing K-Map of a Four-Variable Boolean Function by Minterms

A function generated by a four-variable K-map is reducible by single 1-valued cells, pairs, quads or octets. The formation of 16 single-valued cells in four-variable K-map means the function is equal to 1.

Five-Variable K-map –

A five-variable K-map has thirty two cells as the maximum number of minterms possible with five boolean variables is 32 (2^5). There can be maximum 1024 functions (2^2*5) generated by five boolean variables.

Image showing K-Map of a Five-Variable Boolean Function by Minterms

Fig. 7: Image showing K-Map of a Five-Variable Boolean Function by Minterms

A function generated by a five-variable K-map is reducible by single 1-valued cells, pairs, quads, octets or group of 16 1-valued cells. The formation of 32 single-valued cells in five-variable K-map means the function is equal to 1.

Don’t Care Combinations –

It is not necessary that all output for a boolean function be always known. In digital circuits, there can be possibility where for certain combinations, the output can be either 1 or 0. In such case, either d, x or Ø is inserted in the K-map for the corresponding input combinations. For deriving the boolean expression, either 1 or 0 can be assumed at don’t care combinations to deduce a minimal sum of products or product of sum expression.

Quine-McCluskey Method –

The K-map is useful in deducing boolean expressions involving four boolean variables or less. Further, it gets complex. So, another method called Quine-McCluskey method is used for deducing boolean expressions involving four or more boolean variables. Quine-McCluskey method is a tabular method for deriving the minimal boolean expression. From the truth table of a boolean function, the combinations for which the output of the function is 1 can be listed. These combinations can be indexed in ascending order as binary numbers. For example, suppose there is a boolean function involving four boolean variables (A, B, C, D) having the following truth table –

Truth Table of a Four-Variable Boolean Function

Fig. 8: Truth Table of a Four-Variable Boolean Function

The combinations resulting into 1 on being indexed in ascending order as binary numbers gives the following table for the above case

Table used in Quine-McCluskey Method for Four-Variable Boolean Function

Fig. 9: Table used in Quine-McCluskey Method for Four-Variable Boolean Function

This boolean function can be written as follow –The combinations resulting into 1 on being indexed in ascending order as binary numbers gives the following table for the above case –

F (A, B, C, D) = ∑ (0, 5, 8, 9, 10, 11, 14, 15)

In the first step of Quine-McCluskey method, the minterms are arranged in groups by the number of 1s in them as follow –

Table used in Quine-McCluskey Method for Four-Variable Boolean Function

Fig. 10: Table used in Quine-McCluskey Method for Four-Variable Boolean Function

Any two minterms in adjacent groups like group 0 and 1, group 1 and 2 or group 2 and 3 and so on are now compared and examined for change in the value of only one boolean variable. Such minterms are selected as match and tabulated as pairs in the next step with a dash in place where single boolean variable has changed for the match like as follow –

Table used in Quine-McCluskey Method for Four-Variable Boolean Function

Fig. 11: Table used in Quine-McCluskey Method for Four-Variable Boolean Function

In the next step, the matches in the adjacent groups from table in step 2 are compared and examined for dash for the same variable and change in the value of only one boolean variable. Such matches are selected as quads and tabulated in the next table with a dash in place where single boolean variable has changed for the match. The pairs in second table and minterms in first table that were not matched in the respective tables are also tabulated in the next table (third table) as follow – 

Table used in Quine-McCluskey Method for Four-Variable Boolean Function

Fig. 12: Table used in Quine-McCluskey Method for Four-Variable Boolean Function

The quads, pairs or singles derived in the third table (removing the redundant ones) are called prime implements. In the next step, the prime implements are tabulated against minterms and the minterms included in the respective prime implement (quad, pair or single) is marked by X against the respective prime implement as follow –

Table used in Quine-McCluskey Method for Four-Variable Boolean Function

Fig. 13: Table used in Quine-McCluskey Method for Four-Variable Boolean Function

In the final table, the columns having a single X are examined and rows containing such X are identified. The prime implements respective to those rows are noted and the terms respective to those prime implements are included as sum of products in the boolean expression by comparison of prime implements and boolean variables from the third table. In the third table, the boolean variable against selected prime implement having value dash is not included, the boolean variable against selected prime implement having value 1 is included in normal form in the respective term and the boolean variable against selected prime implement having value 0 is included in compliment form in the respective term. The selected prime implements from fourth table are called essential implements. For the above boolean function, in the fourth table, all the rows are having  an X which is single in at least one column. So all rows are selected and all prime implements are essential implements for the boolean function. From third table, the boolean expression for the function can be derived as follow –

F (A, B, C, D) = AB’ + AC + B’C’D’ + A’BC’D

Now with the knowledge of K-map and Quine-McCluskey method, any boolean function with a given truth table can be easily minimized. In the next tutorial, learn about logic gate implementation of a minimized boolean expression.


Filed Under: Digital Electronics, Featured Contributions, Tutorials

 

Next Article

← Previous Article
Next Article →

Questions related to this article?
👉Ask and discuss on EDAboard.com and Electro-Tech-Online.com forums.



Tell Us What You Think!! Cancel reply

You must be logged in to post a comment.

EE TECH TOOLBOX

“ee
Tech Toolbox: 5G Technology
This Tech Toolbox covers the basics of 5G technology plus a story about how engineers designed and built a prototype DSL router mostly from old cellphone parts. Download this first 5G/wired/wireless communications Tech Toolbox to learn more!

EE Learning Center

EE Learning Center
“engineers
EXPAND YOUR KNOWLEDGE AND STAY CONNECTED
Get the latest info on technologies, tools and strategies for EE professionals.

HAVE A QUESTION?

Have a technical question about an article or other engineering questions? Check out our engineering forums EDABoard.com and Electro-Tech-Online.com where you can get those questions asked and answered by your peers!


RSS EDABOARD.com Discussions

  • Why need use TOPmetal Stacking?
  • Monte-Carlo simulation error on ADE-XL
  • Nastic Monster Energy Sensor
  • Snooping Around is All
  • Identification of a 6 pin smd chip (sto-23-6) marked E2

RSS Electro-Tech-Online.com Discussions

  • Fun with AI and swordfish basic
  • using a RTC in SF basic
  • Does US electric code allow branching ?
  • Faulty heat air gun (dc motor) - problem to locate fault due to Intermittent fault
  • Sump pit water alarm - Kicad 9

Featured – LoRa/LoRaWan Series

  • What is the LoRaWAN network and how does it work?
  • Understanding LoRa architecture: nodes, gateways, and servers
  • Revolutionizing RF: LoRa applications and advantages
  • How to build a LoRa gateway using Raspberry Pi
  • How LoRa enables long-range communication
  • How communication works between two LoRa end-node devices

Recent Articles

  • How IoT network topologies work
  • The top five AI startups to watch in 2025
  • STMicroelectronics unveils SoC based on secure MCU
  • Nexperia’s 48 V ESD diodes support higher data rates with ultra-low capacitance design
  • Taoglas releases Patriot antenna with 18 integrated elements covering 600 to 6000 MHz

EE ENGINEERING TRAINING DAYS

engineering

Submit a Guest Post

submit a guest post
Engineers Garage
  • Analog IC TIps
  • Connector Tips
  • Battery Power Tips
  • DesignFast
  • EDABoard Forums
  • EE World Online
  • Electro-Tech-Online Forums
  • EV Engineering
  • Microcontroller Tips
  • Power Electronic Tips
  • Sensor Tips
  • Test and Measurement Tips
  • 5G Technology World
  • Subscribe to our newsletter
  • About Us
  • Contact Us
  • Advertise

Copyright © 2025 WTWH Media LLC. All Rights Reserved. The material on this site may not be reproduced, distributed, transmitted, cached or otherwise used, except with the prior written permission of WTWH Media
Privacy Policy

Search Engineers Garage

  • Electronic Projects & Tutorials
    • Electronic Projects
      • Arduino Projects
      • AVR
      • Raspberry pi
      • ESP8266
      • BeagleBone
      • 8051 Microcontroller
      • ARM
      • PIC Microcontroller
      • STM32
    • Tutorials
      • Audio Electronics
      • Battery Management
      • Brainwave
      • Electric Vehicles
      • EMI/EMC/RFI
      • Hardware Filters
      • IoT tutorials
      • Power Tutorials
      • Python
      • Sensors
      • USB
      • VHDL
    • Circuit Design
    • Project Videos
    • Components
  • Articles
    • Tech Articles
    • Insight
    • Invention Stories
    • How to
    • What Is
  • News
    • Electronic Product News
    • Business News
    • Company/Start-up News
    • DIY Reviews
    • Guest Post
  • Forums
    • EDABoard.com
    • Electro-Tech-Online
    • EG Forum Archive
  • DigiKey Store
    • Cables, Wires
    • Connectors, Interconnect
    • Discrete
    • Electromechanical
    • Embedded Computers
    • Enclosures, Hardware, Office
    • Integrated Circuits (ICs)
    • Isolators
    • LED/Optoelectronics
    • Passive
    • Power, Circuit Protection
    • Programmers
    • RF, Wireless
    • Semiconductors
    • Sensors, Transducers
    • Test Products
    • Tools
  • Learn
    • eBooks/Tech Tips
    • Design Guides
    • Learning Center
    • Tech Toolboxes
    • Webinars & Digital Events
  • Resources
    • Digital Issues
    • EE Training Days
    • LEAP Awards
    • Podcasts
    • Webinars / Digital Events
    • White Papers
    • Engineering Diversity & Inclusion
    • DesignFast
  • Guest Post Guidelines
  • Advertise
  • Subscribe