How to invert three signals with only two NOT gates (and *no* XOR gates): Part 2

Clive Maxfield

May 22, 2006

Clive Maxfield

In the 8th May 2006 issue of EE Times, I published a "Brain Boggler" in my Logically Speaking column. The idea is that we have a black box with three inputs called A, B, and C; and three outputs called not-A, not-B, and not-C. Each of these outputs is the logical inversion of its corresponding input; that is, if A = 0, then not-A = 1, and vice versa. The problem is to implement the contents of the block box with only two inverting NOT gates, along with as many AND and OR gates as we care to use.

A rather novel solution
In Part 1 of this column, we presented some conventional solutions to this problem using basic combinatorial logic. However, one reader – Tom Watson – came up with a rather novel proposal involving a ring oscillator, a delay chain, an inverting multiplexer, and three latches.

Unfortunately, Tom's original submission came to me in the form of an email containing ASCII-art descriptions of his circuits and waveforms, which made it somewhat difficult for me to determine exactly what was going on. But I understood the gist of Tom's proposal, noodled it over in my noggin, and came up with the following proposed implementation (with apologies to Tom for any errors I've introduced into his masterpiece).

First of all, we should note that we can form a simple non-inverting buffer gate by taking a 2-input AND gate and strapping both of its inputs together as illustrated in Fig 1 (we could achieve exactly the same effect using a 2-input OR gate).

1. Implementing a buffer gate using a 2-input AND gate.

Next, let's assume that each of our NOT, AND, and OR gates has an input-to-output delay of 1 time unit (TU). For the purposes of these discussions, we don’t particularly care what the duration of this time unit is – just so long as everything is relative to each other (even my Aunt Barbara is relative). Thus, if we wished to introduce a delay of say four time units into a signal, we could do so using a chain of four AND gates connected in series as illustrated in Fig 2

2. Implementing a delay of four time units using four AND gates in series.

Of course, rather than drawing out all four AND gates, it's easier for us to draw a simple buffer symbol annotated with the required delay ("4 TUs" in this example). OK, now let's suppose that we use one of our NOT gates and a pile of AND gates to build the simplest of clock generators (a rudimentary oscillator) with a period of 90 TUs Fig 3.

3. Creating a simple clock generator.

Now let's suppose that we augment our simple clock generator with a delay element of 14 TUs followed by an AND gate connected as shown in Fig 4. As we see, the result is that we will be presented with a positive-going pulse with a duration of 15 TUs once every cycle of the main clock generator.

4. Generating pulses.