Skip to content Skip to navigation

Connexions

You are here: Home » Content » Digital Logic Worked Example: Optimal construction of Boolean logic function with simple operators

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Digital Logic Worked Example: Optimal construction of Boolean logic function with simple operators

Module by: Yuqiang Mu, Gbenga Badipe, Adrian Galindo. E-mail the authorsEdited By: Elec and Comp 326

Summary: This module represents a "worked example" of a digital logic design problem that is either commonly seen in conventional education on the subject or would be constructive in building one's understanding in a certain area of digital logic. Specifically, it deals with the procedural synthesis/optimization of a Boolean logic function using only one type of "basic" logic operator (i.e. NAND/NOR); this module will outline (both algebraically and by gate-level analysis) the procedure and reasoning behind creating XNOR logic from only NORs.

Synthesis and Optimization of XNOR logic using the NOR operator

Introduction

For virtually all of today's budding ECE students, calculation and implementation of Boolean logic functions is a staple skill in conventional logic design courses. The subject of Boolean logic is one of the core elements of the Computer Engineering canon; students are exposed to the Boolean world in preparation for their descent into the realm of higher and more complex logic.

It is commonly taught in introductory courses that any kind of Boolean function, no matter how complicated, can be constructed with a combination of NAND and NOR operators (the two most simple Boolean operators to construct with conventional CMOS technology), and it was by this overarching assertion that the module you see before you was created. This worked example illustrates the commonly-seen process of constructing a more complex two-variable logic function only using one kind of rudimentary Boolean operator.

Exercise 1: XNOR Synthesis and Optimization

Problem

Show how a two-variable XNOR function can be implemented using only NOR gates and sketch out a schematic approach. Carry out this problem using the fewest amount of gates needed to do so.

Solution

  1. Step I. Analyze the question to determine the objective and given information:
    • Given: Only NOR gates are allowed.
    • Given: Proceed with intent to optimize (parsimony).
    • Objective: Construct XNOR logic.
  2. Step II. Find concrete expression for the desired function:

    IMPORTANT: For the entirety of this solution, note that the Boolean notation assumes standard operator priority ("order of operations"); notably, NOT before AND before OR (unless, naturally, something of lower priority is parenthesized).

    Figure 1: (**Table courtesy of wikipedia.org)
    Truth Table: XNOR
    Truth Table: XNOR (XNOR Truth Table.PNG)
    PoS representation from truth table: (¬A∨B)∧(¬B∨A) A B B A

    Want NOR construct on outermost level:

    ¬(A⊕B)=(¬A∨B)∧(¬B∨A)=¬(¬A∧B)∧¬(¬B∧A)=¬(¬A∧B∨¬B∧A) A B A B B A A B B A A B B A

  3. Step III. Simplify the Boolean equation (Algebra and schematic):
    • Circuit so far:

      Y=¬(¬A∧B∨¬B∧A) Y A B B A

      3.PNG
    • Apply "Bubble-pushing" (not necessary here) and DeMorgan (done to the two ANDs here) to get more NORs:

      Y=¬(¬(A∨¬B)∨¬(B∨¬A)) Y A B B A

      4.PNG
    • Convert inverters to NOR logic: At this point, the answer seems to be in sight once one realizes that the unary NOT can be implemented by simply tying both inputs of the NOR together; this results in a final result of 5 NOR gates (3 + 2 for the two inverters on the inputs).

      Unfortunately, the above approach is not the most reduced one. It is easily shown that the cost can be reduced by one gate (making the final cost 4 gates) after some maneuvering: specifically, one can apply the following equivalence (derived from the Covering property -- X + XY = X):

      X∨Y=X∨Y∧(X∨¬X)=X∨X∧Y∨¬X∧Y=X∨¬X∧Y X Y X Y X X X X Y X Y X X Y

      • Apply the above equivalence to each set of inputs to the first two NORs:

        IMPORTANT: Note that a NOR is simply an inverted OR; as such, the above property holds for NOR as well: X NOR Y = X NOR ~XY.

        ¬(A∨¬B)=¬(A∨¬A∧¬B) A B A A B

        ¬(B∨¬A)=¬(B∨¬B∧¬A) B A B B A

        (Note that the AND component of the two resulting expressions are IDENTICAL; this is what will reduce the synthesis cost of XNOR by one gate)

        5.PNG
      • Apply DeMorgan's on each of the AND operators:

        ¬A∧¬B=¬(A∨B) A B A B

        ¬(A⊕B)=¬(¬(A∨¬(A∨B))∨¬(B∨¬(B∨A))) A B A A B B B A

        Final Form.PNG

        The optimal implementation of XNOR with NOR gates has been reached.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks