Secret Decoders

I’ve been a bit lazy giving updates but I did spend some time working out an overall design for the instruction set I outlined last time. Getting close on that, but for today I’ll go over some new circuit components that should be useful.

A few posts ago I described demultiplexers, which can be used to direct an input value to one of its ‘n’ output lines. A decoder is quite similar, except instead of passing an input value through a decoder simply selects (sets to 1) one of its ‘n’ outputs based on its inputs.

DEC4x1

For example, consider the 2:4 decoder (2 input lines, selecting one of 4 output lines) above. When A1 is high (1) and A0 is low (0) then line X2 is selected (2 is 10 in binary; A1=1 and A0=0).

Similarly, the other combinations of A1 and A0 select their corresponding output line:

A1 A0 1 0
0 0 X0 all others
0 1 X1 all others
1 0 X2 all others
1 1 X3 all others

Here’s how it all works. Take a close look at the table above and note the combination of 0’s and 1’s for the A1 and A0 input lines. If both A1 and A0 are low (0) then X0 is high (1), if A1 is low (0) and A0 is high (1) then X1 is high (1), and so on.

The 2:4 decoder circuit emulates this logic table using a series of AND and NOT gates to combine its two input lines (A1 and A0) accordingly.

An AND gate (the semi-circular symbols in the circuit above) outputs high (1) only if both of its inputs are also high otherwise it outputs low (0). A NOT gate (triangles in the circuit above) outputs the “opposite” of its input (e.g. high to low, low to high).

Let’s look at the X2 example again. According to the table above, X2 is selected (high) only when A1=1 and A0=0. However we can’t simply AND the two input values (e.g. “A1 AND A0”) because we’d get “1 AND 0” which results in 0. Not the quite result we’re looking for.

The key here is the A0=0 part. What we really want is “1 AND 1” but only when A0 is 0. That’s where the NOT comes into play…NOT 0 = 1!

This allows us to express our desired “1 AND 1” as “1 AND (NOT 0)”; or in terms of our input lines “A1 AND (NOT A0)”. The only way that expression is true (1) is if A1 = 1 and A0=0. If you don’t believe me, the table below might help 🙂

Output A1 A0 NOT A0 A1 AND (NOT A0) Value
X0 0 0 1 0 AND 1 0
X1 0 1 0 0 AND 0 0
X2 1 0 1 1 AND 1 1
X3 1 1 0 1 AND 0 0

There’s a whole world of boolean logic (or boolean algebra) available to us to play games like this 🙂 We’ll probably use a few more tricks like this in future circuits too.

Following through with this, the remaining output lines can be determined using similar boolean logic:

Output A1 A0 Logic
X0 0 0 (NOT A1) AND (NOT A0)
X1 0 1 (NOT A1) and A0
X2 1 0 A1 AND (NOT A0)
X3 1 1 A1 AND A0

I’ll leave it up to you to figure out how these are all wired into that 2:4 decoder circuit diagram 🙂

By combining multiple AND and NOT gates it’s possible to create 3:8, 4:16, etc. decoders. Since I’m pretty sure I’ll need at least the 3:8 and 4:16 decoders I wired some up:

DEC8x1 DEC16x1

You probably noticed that I cheated a bit 🙂

Rather than creating a large number of AND and NOT gates I instead used a lower order decoder (e.g. a 2:4 for the 3:8 and a 3:8 for the 4:16) along with a 2-output demultiplexer.

The decoder handles the “lower most” input lines (e.g. the lower 2 of 3 inputs, or the lower 3 or 4 inputs) while the demultiplexer handles the “upper most” input line by redirecting decoder’s outputs to either the lower or upper ‘n’ output lines (e.g. the lower/upper 4 outputs, or the lower/upper 8 outputs).

Well, I just realized that I didn’t really give any examples on what a decoder can be used for! It’s getting late though so trust me, they’re useful 🙂


Enter the Demux

We’ve already agreed that multiplexers are cool. What’s next?

Well, they’re really only half of the picture for logical switches. The demultiplexer essentially performs the opposite task. That is, given a single input line send its value to one of ‘n’ output lines.

Let’s start with a DMUX2x1 (that is 2 outputs, 1 line each):

DMUX2x1

With this circuit, A is the single input (being either 0 or 1) and SEL states whether to place A on X0 (SEL = 0) or X1 (SEL = 1), with the other being set to 0. In the example above we have A = 1 and SEL = 1, so the value of A (1) is output on X1 (with X0 being 0).

How do we extend this to more than 2 outputs? As with the MUX4x1 (and others) we use multiple DMUX2x1s to create a DMUX4x1; then multiple DMUX4x1s to create a DMUX8x1 and so on. Let’s not get ahead of ourselves though and do a DMUX4x1 first:

DMUX4x1

This circuit works pretty much the exact opposite way the MUX4x1 did. Recall that SEL0 and SEL1 represent the least-significant and most-significant digits of the two-digit binary number used to select what value goes on the output (00 for X0, 01 for X1, 10 for X2 and 11 for X3).

With the DMUX4x1 above, the most-significant digit is decoded by the left-most DMUX2x1 and sends the input value (A) to either the upper-right DMUX2x1 (if SEL1=0) or the lower-right DMUX2x1 (if SEL1=1).

With this decision made, the choice is narrowed down to either X0/X1 (upper DMUX2x1) or X2/X3 (lower DMUX2x1). The selected DMUX2x1 (upper or lower) then decodes the least significant digit (SEL0) to determine which of its two lines to output A on (e.g. X2 with SEL0=0 or X3 with SEL0=1).

Like I said, pretty much like the MUX4x1 but in reverse 🙂 For reference, here’s the MUX4x1 again:

MUX4x1

Okay, let’s keep going and combine some DMUX4x1s into a DMUX8x1:

DMUX8x1

For eight output lines (X0 to X7) we need to have 3 SEL lines (2^3 = 8) which form a three digit binary number (000, 001, 010, 011, 100, 101, 110, 111).

The DMUX4x1 we created above accepts two SEL lines to select one of its 4 outputs (00, 01, 10, 11) so to cover all eight outputs we’ll need two of those: one for selecting X0 through X3 and a second for X4 through X7. But which two SEL lines (SEL0, SEL1, SEL2) do we use?

Look a couple paragraphs up to where I listed the eight 3-digit binary numbers. Notice how the 2-digit binary numbers are repeated twice, once with the 3rd digit as 0 and again with it as 1:

Decimal Binary 3rd digit 2nd & 1st digits Output
0 000 0 00 X0
1 001 0 01 X1
2 010 0 10 X2
3 011 0 11 X3
4 100 1 00 X4
5 101 1 01 X5
6 110 1 10 X6
7 111 1 11 X7

This means that we can connect SEL0 (1st digit) and SEL1 (2nd digit) to our two DMUX4x1s. The 3rd digit (SEL2) can then be used to select between those two DMUX4x1 using a DMUX2x1.

Let’s work through the example in the DMUX4x1 figure above. With SEL2 = 1, A (1) is output on X1 of the DMUX2x1 which is fed into the lower DMUX4x1. Lines SEL1 (1) and SEL1 (0) then tell that DMUX4x1 to output A on X2 (10 in binary is 2 in decimal) which corresponds to X6 of the DMUX8x1. Or in other words, setting SEL2 = 1, SEL1 = 1, SEL0 = 0 (110 in binary or 6 in decimal) outputs A (1) on X6.

Got all that?

I really wish I had a way that you could play with these circuits live 🙂 Maybe I’ll try to get some Logisim files up for you to experiment with.

Now to round out our collection, here’s a DMUX16x1:

DMUX16x1

For those of you keeping track, here’s where we stand for the number of NAND gates being used:

Circuit # NANDs
MUX2x1 4
MUX4x1 12
MUX8x1 28
MUX16x1 60
DMUX2x1 5
DMUX4x1 15
DMUX8x1 35
DMUX16x1 75

They certainly add up!

That’s it for multiplexers and demultiplexers (at least for now) so what’s the next topic? Well, I’ve been giving some thought to the basic CPU hardware (word size, addressing, registers, etc.) and instruction encoding. Thinking next time I’ll put some of those ideas down on “paper”.


Multiplexers Oh My!

I’ve been playing more with Logisim – getting used to the UI and building more circuits – multiplexers and demultiplexers in fact.

So last time I showed you the MUX 2×1 I built to help create a single “bit” of memory:

MUX2x1

To recap, a multiplexer lets you choose between two (or more) input lines (e.g. A0 and A1 above), sending only one of them to the output (X). The SEL line states which of the two inputs (SEL = 0 for A0, SEL = 1 for A1) to pass through to X.

That’s great for two lines, but what if you have more to chose from? Turns out this basic logic can be relatively easily extended to additional lines by combining multiple MUXs. Let’s start with a MUX4x1:

MUX4x1

So now we have two SEL lines (SEL0 and SEL1) and four input lines to choose from (A0 to A3). How do we set the SEL lines to pick a particular input line?

If you’re not already familiar with binary numbers, now would be a good time to read up 🙂

Given two SEL lines (each being 0 or 1) we can create 2^2 = 4 values in binary: 00, 01, 10, 11 which correspond to the decimal values 0, 1, 2 and 3. Hmm, notice that we named the input lines above A0, A1, A2 and A3? That wasn’t coincidental 🙂

That means in order to pick input A2 as our output (as in the diagram above) we need to set the two SEL lines to the binary number 10 (or 2 in decimal) or in other words SEL0 = 0 and SEL1 = 1.

Why that and not SEL0=1 and SEL=0?

In terms of binary number counting SEL0 represents the “least significant digit” (right most) of the two digit binary number (e.g. 0 of 10); which means that it repeats each time a more significant digit (e.g. SEL1) changes. In decimal numbers we might count from 0 to 9, 10 to 19, 20 to 29, etc. Binary works the same way, but we only have 1 and 0 to work with. So 00, 01, 10, 11.

Read that over a couple times if you need to 🙂

Okay, so with SEL0 representing the least significant digit, let’s see what the circuit does with it. You can see that SEL0 (0) is fed into the two both of the MUX2x1’s on the left. This means that the top MUX2x1 will select A0 (the first of its two inputs) and the bottom MUX2x1 will select A2 (the first of its two inputs).

That narrows down our options from 4 lines to just 2 (A0 or A2). Now we need to choose which of those two to output – that’s where the “most significant digit” (SEL1) comes into play. The outputs of the two MUX2x1’s are fed into a third MUX2x1 with the SEL1 line making the choice. In this case, SEL1=1 so its second input (A2, the output from the lower MUX2x1) is output on X.

Yup, yup.

Following through with this logic we get…drum roll…a MUX8x1 and MUX16x1!

MUX8x1   MUX16x1

Cool huh? Maybe a little hypnotic too 🙂

That’s all for now, I’ll write about the demultiplexers next time!


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.