The first one

After playing around with about a half dozen applications for simulating logic circuits, the winner is…

Logisim

It’s free, pretty easy to use, lets me visualize and interact with the circuits, has decent documentation and best of all its file format is XML based so I should be able to translate any circuits I make into my own simulator if/when I get there. There are fancier ones out there, most for $$$, but I’m happy with this one for now 🙂

And so, my first NAND based circuit… a D-type flip flop (DFF)

Exciting isn’t it?

Here’s what it does, when CLK (representing the computer clock which cycles from low (0) to high (1), to low, etc.) is high, the value at A (either high or low) is “pushed” into the various NAND gates. This value is output on X and its inverse (logical NOT) on ~X. The neat part is that when CLK goes low, those values are retained at X and ~X. At least until CLK goes high again, then A is loaded as before and X/~X change.

What’s the use of this? Well, turns out the DFF is a corner stone to building a single “bit” of memory. Yeah, that’s right at least 4 NAND gates are required to represent a single bit of memory. We’re not done though, because to truly “remember” the bit value we need a few more logic gates to retain X when CLK cycles back to high.

Leading to my second and third circuits (no I’m not going to count them all). The key behind a ‘bit’ remembering its value is to feed the DFF’s output (X) back into A. Unfortunately we can’t directly connect X back to A since there would be no way for the various NAND gates to know whether to operate on the value from A or from X.

Fortunately this can be solved by adding a “switch” that lets only one or the other through to the other gates. A “multiplexer” (below) accepts two or more inputs (A0 and A1 in this case) and one or more “select” lines (SEL). The value on the SEL line dictates which of the inputs are passed through to the output (X).

In the figure above, A0 is high (1) and A1 is low (0). Since SEL is low (0) the multiplexer selects the A0 line, resulting in 1 on X. If SEL was 1 then A1 would have been selected, with 0 being output on X.

Get it? Let’s combine that with the DFF above:


So here we’ve added the multiplexer (2×1 means 2 input lines, 1 wire to each) to “switch” between A (a new value to load) and X (the current value in the DFF). Which input to use is stated by SET (0 = X, 1 = A).

As before, when CLK is high the value of the DFF can be changed. However, if SET is high (1) then A is passed in (e.g. the DFF is “set” to 1), otherwise if SET is low (0) then X is used. As before, once CLK goes low the DFF retains its last value and outputs it on X (which is fed into the MUX).

Here’s the sneaky bit, as long as CLK is low, changing either A or SET will have no affect on the DFF’s internal state. Once CLK goes high again, if SET is 0 then the DFF’s current value (output on X) is fed back into itself and so “remembers” its value. This will continue as CLK cycles from low to high; at least until SET becomes 1 again to give the DFF a few value.

Hopefully that all made sense 🙂

Well, that now means that a single “bit” of memory requires 9 NAND gates (5 for the DFF and another 4 for the MUX2x1).

Let’s do some math:

1 word = 16 bits x 9 NANDs = 144 NANDs
64K words of memory = 144 NANDs x 65536 = 9,437,184

That’s almost 10 million NAND gates just for a mere 64K of memory! Hmm, I think I’ll probably need to cheat for main memory like this as I suspect the simulator with die trying to sequence that many NAND gates. I might try using the NAND gate bits for CPU registers though, there will only be a handful and it’d be a shame not to use my bit circuit at all 🙂

That’s enough for now. Think I’ll next try making a few more multiplexers (4, 8 and 16 inputs) as I think those will be useful later on. I’ll also look into the logic needed for demultiplexers which are basically the opposite of multiplexers (given a single line, output it to one of ‘n’ others).

I also need to give some thought to the basic CPU requirements (e.g. word size, memory addressing, number of registers, instruction set, etc.) as they will dictate which types of low-level circuits I need to create.

…and so it begins
Multiplexers Oh My!

Leave a Reply

Your email address will not be published / Required fields are marked *