Engineers Garage

  • Electronics Projects and 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 Implementation – DE Part 8

By Hai Prasaath K January 30, 2022

In the previous tutorial, gate level minimization of boolean functions was discussed. A boolean function must be expressed in standard form as either sum of products (SoP) or product of sums (PoS). Once a boolean function in case is minimized to SoP or PoS form, it can be easily fabricated as two-level implementation of AND and OR gates. A two-level implementation is preferred so that there is minimum delay in signal propagation through logic gates from input to output of the digital circuit.

Practically, digital circuits are constructed with NAND or NOR gates rather than AND or OR gates. The NAND and NOR gates are easy to fabricate with semiconductor components. These are the universal gates from which all other logic gates can be constructed. That is why, all the digital ICs are constructed with NAND or NOR gate rather than other logic gates.

NAND as Universal Gate –

NAND is a universal gate. All other logic gates can be constructed by the NAND gate. A NOT gate can be constructed by one-input NAND gate. A single input NAND gate works same as inverter or NOT gate. The AND gate can be implemented by connecting a NAND gate to a single-input NAND gate where single input NAND gate will work as inverter or NOT gate. The OR gate can be implemented by connecting inputs to single input NAND gates acting as inverter which then connect to a  NAND gate. The implementation of AND,  OR, and NOT gates with the help of NAND gate is shown in the following logic gate diagrams –

 Image Showing Implementation of AND, OR and Invert with NAND Gate

Fig. 1: Image showing Implementation of AND, OR and Invert with NAND Gate

Two-Level Implementation with NAND Gate –

For two-level implementation of a boolean function with NAND gate, it must be expressed in sum of products form. The AND operation (product) between boolean variables (binary data paths) can be implemented by connecting the inputs to a  NAND gate which should be connected to a single input NAND gate acting as inverter. The OR operation (sum) can be implemented by connecting the outputs from level 1 to single input NAND gates acting as inverters which should be connected to a NAND gate. Since the complement of a complement of a boolean variable is its normal form, the single input NAND gates at the output of level 1 and at the input of level 2 on same lines can be removed. Therefore, a sum of product expression can be implemented by NAND gates by simple NAND-NAND implementation.

Suppose, a four-variable boolean function F is as follow –

F = AB + CD

In AND-OR implementation, its logic gate diagram will be as follow –

Image showing Two-Level AND-OR Implementation before NAND-NAND Implementation

Fig. 2: Image showing Two-Level AND-OR Implementation before NAND-NAND Implementation 

A NAND gate can be either shown as AND-Invert or Invert-OR as they are equivalent. The following graphic symbols can be used for NAND gate –

Symbols of NAND Gate

Fig. 3: Symbols of NAND Gate

On replacing the AND plus OR gate by NAND gate in the implementation of the function F, the following logic diagram is obtained –

Image showing Replacement of AND-OR Gates by NAND Gate

Fig. 4: Image showing Replacement of AND-OR Gates by NAND Gate

As mentioned above  the complement of a complement of a boolean variable is its normal form, the single input NAND gates at the output of level 1 and at the input of level 2 on same lines can be removed. So, After removing even number of inverters on same line, the final NAND-NAND implementation of the function will be as follow –

Image showing Two-Level NAND-NAND Implementation of a Sum of Product Expression

Fig. 5: Image showing Two-Level NAND-NAND Implementation of a Sum of Product Expression

Multi-Level Implementation with NAND Gate –

The gating structure of a digital circuit need not be always feasible to be implemented at two levels. Many times, due to design limitations or for feasibility of the fabrication of an IC, there may require to implement the logic gate diagram of a digital circuit in three or four levels. here are also some boolean functions like Ex-OR which can only be implemented in 3-level or more gate structure. In such case, the boolean function must be first expressed in terms of AND, OR and NOT gates. A logic gate diagram with AND, OR and NOT gates must be drawn and the AND, OR and NOT gates must be replaced by their NAND equivalents. Now, the even number of bubbles (denoting NOT in the NAND Gate) on the same lines must be removed and the remaining single bubbles on lines must be replaced by single input NAND gates. The left is the all-NAND logic gate diagram of the digital circuit.

NOR as Universal Gate –

NOR is also a universal gate like the NAND gate. All other logic gates can be constructed by the NOR gate too. A NOT gate can be constructed by one-input NOR gate. A single input NOR gate works same as inverter or NOT gate. The OR gate can be implemented by connecting a NOR gate to a single-input NOR gate where single input NOR gate will work as inverter or NOT gate. The AND gate can be implemented by connecting inputs to single input NOR gates acting as inverter which then connect to a  NOR gate. The implementation of other gates with NOR gate is the dual of the implementation of other gates with the NAND gate. The implementation of AND, OR and NOT gates with the help of NOR gate is shown in the following logic gate diagrams –

Image showing Implementation of AND, OR and Invert with NOR Gate

Fig. 6: Image showing Implementation of AND, OR and Invert with NOR Gate

Two-Level Implementation with NOR Gate –

For two-level implementation of a boolean function with NOR gate, it must be expressed in product of sums form. The NOR gate implementation of the AND, OR and NOT gate is just the dual of their NAND gate implementation. The OR operation (sum) between boolean variables (binary data paths) can be implemented by connecting the inputs to a  NOR gate which should be connected to a single input NOR gate acting as inverter. The AND operation (product) can be implemented by connecting the outputs from level 1 to single input NOR gates acting as inverters which should be connected to another NOR gate. Since the complement of a complement of a boolean variable is its normal form, the single input NOR gates at the output of level 1 and at the input of level 2 on same lines can be removed. Therefore, a product of sum expression can be implemented by NOR gates by simple NOR-NOR implementation.

Suppose, a four-variable boolean function F is as follow –

F = (A + B)(C + D)

In AND-OR implementation, its logic gate diagram will be as follow –

Image showing Two-Level AND-OR Implementation before NOR-NOR Implementation

Fig. 7: Image showing Two-Level AND-OR Implementation before NOR-NOR Implementation

A NOR gate can be either shown as OR-Invert or Invert-AND as they are equivalent. The following graphic symbols can be used for NOR gate –

Symbols of NOR Gate

Fig. 8: Symbols of NOR Gate

On replacing the AND, OR  and NOT gates by NOR gate in the implementation of the function F, the following logic diagram is obtained –

Image Showing Replacement of AND-OR Gates by NOR Gate

Fig. 9: Image showing Replacement of AND-OR Gates by NOR Gate

As mentioned above  the complement of a complement of a boolean variable is its normal form, the single input NOR gates at the output of level 1 and at the input of level 2 on same lines can be removed. So, After removing even number of inverters on same line, the final NOR-NOR implementation of the function will be as follow –

Image showing Two-Level NOR-NOR Implementation of a Product of Sum Expression

Fig. 10: Image showing Two-Level NOR-NOR Implementation of a Product of Sum Expression

All Possible Two-Level Implementations and Non-degenerate Forms –

Considering two-level implementation of boolean functions and taking AND, OR, NAND and NOR gates available, there can be sixteen possible combinations for two-level implementation of a boolean expression. The eight of these combinations degenerate to single operation, so they are called degenerate forms. The eight degenerate forms are as follow –

1) AND-AND: It degenerates to AND operation. Like if there are four boolean variables A, B, C and D connected in AND-AND gate structure, it will deduce as follow –

F = (AB)(CD)

= ABCD

2) AND-NAND: It degenerates to NAND operation. Like if there are four boolean variables A, B, C and D connected in AND-NAND gate structure, it will deduce as follow –

F = ((AB)(CD))’

= (AB)’ + (CD)’

= A’ + B’ + C’ + D’

= (ABCD)’

3) OR-OR: It degenerates to OR operation. Like if there are four boolean variables A, B, C and D connected in OR-OR gate structure, it will deduce as follow –

F = (A + B) + (C + D)

= A + B + C + D

4) OR-NOR: It degenerates to NOR operation. Like if there are four boolean variables A, B, C and D connected in OR-NOR gate structure, it will deduce as follow –

F = ((A + B) + (C + D))’

= (A + B)'(C + D)’

= A’B’C’D’

= (A + B + C + D)’

5) NAND-OR: It degenerates to NAND operation. Like if there are four boolean variables A, B, C and D connected in NAND-OR gate structure, it will deduce as follow –

F = (AB)’ + (CD)’

= A’ + B’ + C’ + D’

= (ABCD)’

6) NAND-NOR: It degenerates to  AND operation. Like if there are four boolean variables A, B, C and D connected in NAND-NOR gate structure, it will deduce as follow –

 F = ((AB)’ + (CD)’)’

= (A’ + B’ + C’ + D’)’

= (ABCD)

7) NOR-AND: It degenerates to NOR operation. Like if there are four boolean variables A, B, C and D connected in NOR-AND gate structure, it will deduce as follow –

F = (A + B)'(C + D)’

= A’B’C’D’

= (A + B + C + D)’

8) NOR-NAND: it degenerates to OR operation. Like if there are four boolean variables A, B, C and D connected in NOR-NAND gate structure, it will deduce as follow –

F = ((A + B)'(C + D)’)’

= (A + B) + (C + D)

= A + B + C + D

The remaining eight forms either deduce to sum of products expression or product of sum expression for a boolean function. These are called non-degenerate forms. The eight non-degenerate forms are AND-OR, AND-NOR, OR-AND, OR-NAND, NAND-AND, NAND-NAND, NOR-OR and NOR-NOR. The AND-OR is dual of OR-AND, NAND-NAND is dual of NOR-NOR, NOR-OR is dual of NAND-AND while OR-NAND is dual of AND-NOR and vice-versa. The AND-OR and OR-AND forms are basic forms of a boolean expression. The NAND-NAND and NOR-NOR forms are the universal implementation of any boolean function. The NAND-AND and AND-NOR are equivalent and called AND-OR-Invert implementation. The OR-AND and NOR-OR are also equivalent and called OR-AND-Invert implementation.

AND-OR-Invert Implementation –

Both NAND-AND and AND-NOR perform AND-OR-Invert operation. It is simple AND-OR operation with invert operation implemented at the output. Suppose there are four boolean variables – A, B, C and D, then NAND-AND operation between them will be as follow –

F = (AB)'(CD)’

= (AB + CD)’

Similarly, the AND-NOR operation with four boolean variables – A, B, C and D will deduce as follow –

F = (AB+CD)’

OR-AND-Invert Implementation –

Both OR-NAND and NOR-OR perform OR-AND-Invert operation. It is simple OR-AND operation with invert operation implemented at the output. Suppose there are four boolean variables – A, B, C and D, then OR-NAND operation between them will be as follow –

F = ((A + B)(C + D))’

Similarly, NOR-OR operation with four boolean variables – A, B, C and D will deduce as follow –

F = (A + B)’ + (C + D)’

= ((A + B)(C + D))’

Now, with the knowledge of Gate Level Implementation, any boolean function can be constructed with universal logic gates – NAND and NOR. In the next tutorial, there is a short introduction to VHDL. VHDL is a computer based language that describes the hardware of a digital circuit in textual form. It is a computer based design tool that is extremely helpful in design of large scale digital circuits. The designing of small circuits can be done manually, but large digital circuits require computer based tools for designing. Such tools not only ease the design process, they also reduce the chances of a flawed design.


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: Internet of Things
Explore practical strategies for minimizing attack surfaces, managing memory efficiently, and securing firmware. Download now to ensure your IoT implementations remain secure, efficient, and future-ready.

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

  • How can I get the frequency please help!
  • Elektronik devre
  • 12VAC to 12VDC 5A on 250ft 12AWG
  • SPI speed pic18f66j15
  • Antiparallel Schottky Diodes VDI-Load Pull

RSS Electro-Tech-Online.com Discussions

  • Actin group needed for effective PCB software tutorials
  • how to work on pcbs that are thick
  • compatible eth ports for laptop
  • How to repair this plug in connector where wires came loose
  • Kawai KDP 80 Electronic Piano Dead

Featured – Designing of Audio Amplifiers part 9 series

  • Basics of Audio Amplifier – 1/9
  • Designing 250 Milli Watt Audio Power Amplifier – 2/9
  • Designing 1 Watt Audio Power Amplifier – 3/9
  • Designing a Bass Boost Amplifier – 4/9
  • Designing a 6 Watt Car Audio Amplifier – 5/9
  • Design a low power amplifier for headphones- 6/9

Recent Articles

  • ITG Electronics releases gate drive transformers with 200 – 450 V DC capability
  • Stackpole introduces HCJ jumpers with 70.7 amp continuous current capability
  • Infineon releases MCU with 128K flash and multi-sense capabilities
  • ST introduces 600V GaN gate drivers with 300 ns start-up time
  • ABLIC releases S-19116 automotive voltage detector with 6.8μs response time

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

  • Electronics Projects and 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