Close

NAND or NOR ? A taxonomy of topologies

A project log for PDP - Processor Design Principles

Distilling my experience and wisdom about the architecture, organisation and design choices of my CPUs

yann-guidon-ygdesYann Guidon / YGDES 12/16/2020 at 21:4710 Comments

When you start to design a computer, you usually start with rule 1. Use binary, 2s complement numbers (unless you're @SHAOS or @alice crush) but it's only the beginning. You have to choose a technology, which is a complex entangled web of compromises and constraints.

Of course,

In fact, from here on, I guess you'll use discrete (MOS)FET or BJTs and things get downhill from there.

Many Hackaday projects, and in particular the #Hackaday TTLers, love to explore and play with various ways to interconnect discrete transistors. It's just a notch below the thrill of designing an integrated circuit but way above that in the BMOW wow-factor. You can touch it, probe it, fix and patch it, show it off and impress...

Creating a logic gate is an art in itself (ask Harvey about it), which draws from both boolean arithmetic and small-signal analog design, and we can dig in the literature, in the past or in the present, to find inspiration. Where each "logic family" differs is what they can express and how they perform each function. The range of possible functions is a sort of expressiveness, and this also deeply influences your higher-level design, as well as design methodology.

This page is important because it gives you a taste of how miserable you will feel, once you get a few working gates. For example, if too few inputs are possible, the final circuit will be slower because of logic fan-in restrictions: for logic reduction, a 2-tree uses more stages than a 3-tree, and a 4-tree is faster, but might each gate might be slower, so you must find a balance somewhere. One typical example is how you design a XOR gate: it might cripple your critical datapath and speed if your logic family is too limited.

The basic gates provide NOR and/or NAND, which I call "first order gates" because there is one level of inversion. Along with the MUX2, these are the "most basic gates" from which you can build all other circuits, but MUX2 is cheating because it contains both inversions, OR and AND. Building a computer with them is possible, but still a challenge ! You have to turn everything into a sequence of NOR or NANDs. This is why "expressiveness" is so important for architects and circuit designers : some families offer a wider range of gates that make life easier, critical datapaths shorter and circuits simpler.

Another choice or constraint is your ability or willingness to use complementary transistors. If all you have, or can get, is a single type, then you are more limited in the possible topologies and you are forced to perform more boolean trickery with the few possible gates. OTOH if you can source both P and N types, you can exploit both NOR and NAND, or combine them in creative ways that could reduce both complexity and power.

But mostly you end up with NANDs and/or NORs... you have to choose carefully !

Note that if you are not concerned with raw speed, and you're willing to deal with saturation and weird levels, you can play with less advertised aspects of transistors to create some shortcuts and extend your "expressiveness":

However these "analog tricks" break the principle of a "logic family" where every member can be connected to the others.

.
.

The conclusion of this exposé is simple:

Apart from ECL which offers some flexibility, most discrete logic families are restricted to NAND or NOR gates.

You have to adapt your logic design, architecture and physical parameters to the family you choose, and learn to break most boolean circuits into NORs or NANDs, it's a skill that is learned like a language.

This also means that if you can express your architecture as a collection of NOR gates, you are then free to implement it with several types of logic gates, which you can choose with more freedom. In fact, I found only recently that NOR is the more natural choice for many families than NAND:

You can twist and tweak the rules if you get access to complementary parts (as with IBM's "current steering logic" which was the precursor to ECL) but then the design would become too specialised and less portable.

Discussions

Yann Guidon / YGDES wrote 01/02/2021 at 03:54 point

Another comment :

It probably isn't a good idea to rebuild a TTL multi_emitter transistor from individual transistors, when I had tried this this gave me "crosstalk" between the inputs of the NAND.

  Are you sure? yes | no

Yann Guidon / YGDES wrote 01/02/2021 at 03:51 point

Comment from a friend :

Some years ago I had tinkered with output buffers where a NPN and a PNP transistor are wired together like in CBJT, BC547 and BC557, I gave up because the transistors had a habit of turning into a 100MHz..200MHz oscillator.


  Are you sure? yes | no

Tim wrote 12/18/2020 at 18:31 point

  Are you sure? yes | no

Yann Guidon / YGDES wrote 12/18/2020 at 19:59 point

I guess MUX2 like relays...

  Are you sure? yes | no

alice crush wrote 12/18/2020 at 11:02 point

So does the relay fall more in the nand or the nor camp?

  Are you sure? yes | no

Yann Guidon / YGDES wrote 12/18/2020 at 11:49 point

IMHO, neither :-)

This log covers the transistors, which are "tripoles" (at least for those you can easily buy in bulk for less than $0.01 each) and they have inherent limitations, in particular : the input and the output share the same reference node.

The simplest relays are tetrapoles : SPST types have 4 pins in 2 isolated sets, and are (usually) not polarised, so they are halfway in the MUX2 class. Already you can make a XOR gate with proper signaling and no effort.

But even SPST is not recommended for digital designs :-) Use at least SPDT, which are pentapoles that allow true MUX2, and DPDT for more practical implementations (they will save you from having to wire 2 relays in series or parallel, which happens a lot with SPDT).

  Are you sure? yes | no

Tim wrote 12/17/2020 at 06:37 point

>you end up back to "only NOR" domain


You also get a very stable wired AND due to the strong output driver. This logic type is probably not that inefficient. I shall look into some basic gates and latches when i find the time.

>It's good to get started but your system won't easily exceed a few MHz of operating frequency. Be careful with your signal margins though.


Why? DTL has quite good signal margins. At least compared to RTL, ECL.

  Are you sure? yes | no

Yann Guidon / YGDES wrote 12/17/2020 at 13:45 point

OK I forgot about tying output collector/drain buffers together... It was late in the night, I hope you'll excuse me :-P

Now, what about mixing DTL and RTL to get both NORs and NANDs ?

  Are you sure? yes | no

Tim wrote 12/17/2020 at 16:14 point

Late night engineering is the best :)

Will you could easily build a DTL NOR by connecting the outputs of two inverters. 

Hm... I am realizing that a wired AND of a NOR gate is just another NOR gate. So this is not very useful.

  Are you sure? yes | no

Yann Guidon / YGDES wrote 12/17/2020 at 16:45 point

@Tim which again proves this log's point : the logic family influences the range of boolean primitives.

"Know your family and choose it well"

  Are you sure? yes | no