COMPUTER DESIGN /FEBRUARY 1968 pp60/1
[US MAGAZINE]

The Exclusive-Or Element

by IVOR CATT
The Bunker-Ramo Corp.
Teleregister Div.



Failure of the Exclusive-OR Element to take its rightful place as one of the primary logic elements is based on historical reasons which are not valid today. If an I/C family of logic packages exceeds three types, the exclusive OR element should be part of the family.

Historical

It was probably difficult to implement the Exclusive-OR with relays.

When we entered the diode-triode era, diodes in parallel provided the AND or the OR function and a triode provided the INVERT function and also the (very necessary) amplification and restandardization. Drring the diode-triode era, diodes were expensive and triodes were more so. There was a tendency to try to go through more than one stage of diodes, AND-OR, before reaching the more expensive triode INVERT. This gave the AOI (AND-OR-INVERT) type of gate, which appeared to some designers to minimize the ex-pensive triode, giving a great deal of logical power per triode. However, the majority favored the simple AND-INVERT for reasons of speed and because it was doubtful if all of the logical power of the AOI could be put to good use.

The advent of transistors did not significantly alter the picture. As before, diodes were expensive and transistors (instead of triodes) were very expensive. Some designers used the AND-INVERT, and some argued for the AOI. some went further, and used, or tried to use, four stages of diodes in series before bringing a transistor to the rescue. The logic function was AOAOI.

With the development of integrated circuits, tradeoffs that applied to discrete diode transistor logic were transferred directly to integrated circuit design. As far as I can see, no concessions were made when choosing logic functions to the fact that the integrated circuit was a new environment, and new tradeoffs would apply. At least, the resulting products were remarkably similar to the discrete circuits they replaced. As with discrete circuits, the integrated AND-INVERT (called NOR or NAND) took about 80% of the market, and the AOI took about 20%.

Up till now, the idea that AND, OR and INVERT are the basic logic functions has been firmly entrenched. Many techniques have been developed to handle these functions, including Boolean Algebra and minimization with Veich diagrams, minterms and maxterms.

Analysis

A logic element with one input, A, can be either a link, with output A, or an inverter, with output . The first type will be dismissed as trivial. The second type, the Inverter, has a truth table as follows:

Picture

A logic element with two inputs, A and B, can be of 16 types. Of these, eight types treat A and B symmetrically. That is, if the inputs are replaced by each other, the output remains the same. The truth tables for these eight types are drawn in Figure 1. We shall dismiss the last two as trivial. This leaves us with types 1 thru 6.

Type 1 is the AND gate. Type 3 is the OR gate. Type 2 is the exclusive OR. The other three types are the image of types 1 thru 3, and we shall neglect them.

We now see that if we limit ourselves to logic elements with two inputs or less, the primary functions appear to be:

    1.    Inverter
    2.    AND
    3.    OR
    4.    Exclusive OR
For a set of logic elements to be complete, it must include the INVERTER. A complete set of logic elements need contain only the INVERTER and either the AND or the OR. With these two elements, any logic function can be implemented. By studying the truth tables or by using De Morgan's theorem, we see that the AND and the OR function are very similar to each other.

Picture

In their truth tables, the centre of gravity of the 1's is not at the centre of the table, but falls somewhere on the N.W.-S.E. diagonal. However, the Exclusive-OR appears to be a quite different type of function. In its truth table, the centre of gravity of the 1's is at the centre of the table. We can therefore call it a "balanced function," and the output will be true half of the time if we go through all possible combinations of inputs.

If we limit ourselves to functions of two variables or less, we now see that there are three types:

1. INVERTER
2. UNBALANCED FUNCTION (AND or OR).
3. BALANCED FUNCTION (Exclusive OR).

Although one unbalanced function plus the Inverter make up a complete set, a Balanced function (Exclusive OR) plus the Inverter do not. That is, some logic functions cannot be implemented using only Exclusive OR's and Inverters.

So if a family of logic elements is being designed using only one type, then the NOR or the NAND, which em-braces both the unbalanced function and the Inverter, is the proper choice to make, and the Balanced function (Exclusive-OR) rightly will not appear in the family.

If a family of logic elements is being designed using more than one type, it looks as though the Balanced function (Exclusive-OR), as one of the three primary logic functions, has a strong claim to be included.


ALTERNATIVE NAMES FOR THE EXCLUSIVE-OR

Probably the greatest disadvantage under which this logic function labours is its name. Other possible names for the Exclusive-OR, which give an indication of its versatility, are as follows:

    1. Equivalent (Actually, Non-Equivalent) This is the name it should carry.

    2. Parity

    3. Comparator

    4. Inverter

    [5. Sum in binary adder.]

Illustrations below illustrate this versatility.

    Picture

    Picture

    Picture

    Picture

    Top of Page

First published in COMPUTER DESIGN /FEBRUARY 1968 pp60/1
IvorCatt.org | IvorCatt.com | Electromagnetism1 | Oldest Website | IvorCatt 2004 Archive