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 February 23, 2021

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 –

      

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

A Two-Variable K-Map

Fig. 1: A Two-Variable K-Map 

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.

A Three-Variable K-Map

Fig. 2: A Three-Variable K-Map

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.

Two-Variable K-Map and Minterms

Fig. 3: Two-Variable K-Map and 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.

Three-Variable K-Map and Minterms

Fig. 4: Three-Variable K-Map and 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.

Four-Variable K-Map and Minterms

Fig. 5: Four-Variable K-Map and 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.

Five-Variable K-Map and Minterms

Fig. 6: Five-Variable K-Map and 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 –


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

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 –

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 –


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 – 

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 –

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.

You may also like:


  • What to expect from the IoT in 2023

  • What are LoRa gateways and what types are available?

  • How does LoRa modulation enable long-range communication?

  • What types of motors are used in electric vehicles?

  • What is the role of embedded software in electric vehicles?

  • What to expect from microcontrollers in 2023

Filed Under: Featured Contributions, Tutorials

 

Next Article

← Previous Article
Next Article →

Questions related to this article?
👉Ask and discuss on Electro-Tech-Online.com and EDAboard.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

  • Exporting sensor readings as data...
  • Inconsistent Charge Termination Voltage with battery charger
  • 21V keeps getting shorted to my UART line.
  • Voltage mode pushpull is a nonsense SMPS?
  • Voltage mode push pull with extra DC blocking capacitor

RSS Electro-Tech-Online.com Discussions

  • Is AI making embedded software developers more productive?
  • Why can't I breadboard this oscillator?
  • using a RTC in SF basic
  • Parts required for a personal project
  • Cataract Lens Options?

Featured – RPi Python Programming (27 Part)

  • RPi Python Programming 21: The SIM900A AT commands
  • RPi Python Programming 22: Calls & SMS using a SIM900A GSM-GPRS modem
  • RPi Python Programming 23: Interfacing a NEO-6MV2 GPS module with Raspberry Pi
  • RPi Python Programming 24: I2C explained
  • RPi Python Programming 25 – Synchronous serial communication in Raspberry Pi using I2C protocol
  • RPi Python Programming 26 – Interfacing ADXL345 accelerometer sensor with Raspberry Pi

Recent Articles

  • GigaDevice launches GD32C231 MCU series with 48MHz Cortex-M23 core and 64KB Flash
  • Advanced Energy releases 425 W CF-rated medical power supply in 3.5 x 6 x 1.5-inch format”
  • LEM combines shunt and Hall effect sensing in 2000 A current measurement unit
  • What is AWS IoT Core and when should you use it?
  • AC-DC power supply extends voltage range to 800 V DC

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