Engineers Garage

  • Projects and Tutorials
    • Electronic Projects
      • 8051
      • Arduino
      • ARM
      • AVR
      • PIC
      • Raspberry pi
      • STM32
    • Tutorials
    • Circuit Design
    • Project Videos
    • Components
  • Articles
    • Tech Articles
    • Insight
    • Invention Stories
    • How to
    • What Is
  • News
    • Electronic Products News
    • DIY Reviews
    • Guest Post
  • Forums
    • EDABoard.com
    • Electro-Tech-Online
    • EG Forum Archive
  • Digi-Key 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
  • EE Resources
    • DesignFast
    • LEAP Awards
    • Oscilloscope Product Finder
    • White Papers
    • Webinars
  • EE Learning Center
    • Design Guides
      • WiFi & the IOT Design Guide
      • Microcontrollers Design Guide
      • State of the Art Inductors Design Guide
  • Women in Engineering

Gate Level Implementation – DE Part 8

By Hai Prasaath K

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 –

 Implementation of AND, OR and Invert with NAND Gate

Fig. 1: 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 –

Two-Level AND-OR Implementation Before NAND-NAND

Fig. 2: 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 –

NAND Gate Symbols

Fig. 3:NAND Gate Symbols

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

Replacing AND-OR Gates by NAND Gate

Fig. 4: Replacing 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 –

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

Fig. 5: 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 –

Implementation of AND, OR and Invert with NOR Gate

Fig. 6: 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 –

Two-Level AND-OR Implementation Before NOR-NOR Implementation

Fig. 7: 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 –

NOR Gate Symbols

Fig. 8: NOR Gate Symbols

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

Replacing AND-OR Gates by NOR Gate

Fig. 9: Replacing 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 –

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

Fig. 10: 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: Recent Articles

 

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.

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!


Featured Tutorials

  • PS2 Keyboard To Store Text In SD Card Using Arduino Circuit Setup On Breadboard
    How To Use PS2 Keyboard To Store Text In SD Card Using Arduino- (Part 42/49)
  • Wireless Path Tracking System Using Mouse, XBee And Arduino Circuit Setup On Breadboard
    How To Make A Wireless Path Tracking System Using Mouse, XBee And Arduino- (Part 43/49)
  • How to Make a Wireless Keyboard Using Xbee with Arduino- (Part 44/49)
  • Making Phone Call From GSM Module Using Arduino Circuit Setup On Breadboard
    How to Make Phonecall From GSM Module Using Arduino- (Part 45/49)
  • How to Make a Call using Keyboard, GSM Module and Arduino
    How To Make A Call Using Keyboard, GSM Module And Arduino- (Part 46/49)
  • Receiving SMS Using GSM Module With Arduino Prototype
    How to Receive SMS Using GSM Module with Arduino- (Part 47/49)

Stay Up To Date

Newsletter Signup

Sign up and receive our weekly newsletter for latest Tech articles, Electronics Projects, Tutorial series and other insightful tech content.

EE Training Center Classrooms

EE Classrooms

Recent Articles

  • Renesas delivers intelligent sensor solutions for IoT applications
  • Microchip Technology releases AVR-IoT Cellular Mini Development Board
  • Qualcomm acquires Cellwize to accelerate 5G adoption and spur infrastructure innovation
  • MediaTek’s chipset offers high-performance option for 5G smartphones
  • Nexperia’s new level translators support legacy and future mobile SIM cards

Most Popular

5G 555 timer circuit 8051 ai Arduino atmega16 automotive avr bluetooth dc motor display Electronic Part Electronic Parts Fujitsu ic infineontechnologies integratedcircuit Intel IoT ir lcd led maximintegratedproducts microchip microchiptechnology Microchip Technology microcontroller microcontrollers mosfet motor powermanagement Raspberry Pi remote renesaselectronics renesaselectronicscorporation Research samsung semiconductor sensor software STMicroelectronics switch Technology vishayintertechnology wireless

RSS EDABOARD.com Discussions

  • LLC HB with synchronous rectifiers can be very dodgy?
  • building lm2596 dc dc using Arduino uno
  • ADS Cascode Power Amplifier Loadpull Problem
  • DC DC converter output voltage rise time
  • ESP32 Bluetooth and Wifi Module Interface with Cloud

RSS Electro-Tech-Online.com Discussions

  • Trying to make a custom automated water container for my UV purifier. Can anyone help with where to begin?
  • Control Bare LCD With ATmega328p
  • Are Cross-wind compensation and Road crown compensation functions inputs to LKA function?
  • undefined reference header file in proteus
  • Help diagnosing a coffee maker PCB
Engineers Garage
  • Analog IC TIps
  • Connector Tips
  • DesignFast
  • EDABoard Forums
  • EE World Online
  • Electro-Tech-Online Forums
  • Microcontroller Tips
  • Power Electronic Tips
  • Sensor Tips
  • Test and Measurement Tips
  • 5G Technology World
  • About Us
  • Contact Us
  • Advertise

Copyright © 2022 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 | Advertising | About Us

Search Engineers Garage

  • Projects and Tutorials
    • Electronic Projects
      • 8051
      • Arduino
      • ARM
      • AVR
      • PIC
      • Raspberry pi
      • STM32
    • Tutorials
    • Circuit Design
    • Project Videos
    • Components
  • Articles
    • Tech Articles
    • Insight
    • Invention Stories
    • How to
    • What Is
  • News
    • Electronic Products News
    • DIY Reviews
    • Guest Post
  • Forums
    • EDABoard.com
    • Electro-Tech-Online
    • EG Forum Archive
  • Digi-Key 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
  • EE Resources
    • DesignFast
    • LEAP Awards
    • Oscilloscope Product Finder
    • White Papers
    • Webinars
  • EE Learning Center
    • Design Guides
      • WiFi & the IOT Design Guide
      • Microcontrollers Design Guide
      • State of the Art Inductors Design Guide
  • Women in Engineering