How to think about digital circuit design

Question

How does one go about thinking about designing digital logic chips in an abstract way?

I'm currently working through "The Elements of Computing Systems" I'm in the first chapter, and I've implemented the following gates, starting from Nand.

Not

And

Or

Xor

Mux

DMux

16bit Not

16bit And

16bit Or

16bit Mux

8 way Or

I'm now stuck trying to implement a 16 bit four way Mux.

I've tried converting the truth table into canonical notation, but I end up with a gigantic mess. Using canonical representation worked well for "smaller" chips, but is now immensely complicated. How can I think about putting together a "complicated" chip in a way that doesn't involve just mashing together random chips?

Edit:

I'm not really confused about the 16 bit part of the four way Mux. I planned on just using a bunch of four way Muxes in an array. The 4 way mux is the part I'm stuck on.

Answer 1

Lets start with a two input mux.

Two inputs A & B and a select line S. The output will be '1' when the A or B is '1' and the select line selects that input, else it's '0'. So either:

A=1 and S=0
B=1 and S=1

Writing that out as gates:

(A and (not S)) or (B and S)

Expand that up to a 4 way (S is now 2 bits):

A = 1 and S=0
B = 1 and S=1
C = 1 and S=2
D = 1 and S=3

(A and (not S1) and (not S0)) or
(B and (not S1) and (    S0)) or
(C and (    S1) and (not S0)) or
(D and (    S1) and (    S0))

We can see a pattern emerging which is that every input is AND'ed with some "enabling term" which switches that input on or off. As the enabling terms are exclusive (only one can be true at any time) the effect is to switch the output to the desired input.

This can be extended up to any size of MUX.

Answer 2

I applaud your "start at the bottom and work up" approach, it will help you appreciate what is involved in more and more complex circuits over time.

It might also be worth pointing out that once you come to designing digital logic chips on a larger scale, it's usually done at a much higher level these days. Often using a Hardware Description Language (usually Verilog or VHDL), or even using C for parts of the chip in some domains.

Once you work at that level, you very rarely write the code for a MUX, but it is very useful to know as you write the textual description that you're asking the synthesis tool to produce one for you, and that you have some grasp of how "big" (in gates) it's likely to be.

Another point to note is that if you move to designing with FPGAs, your fundamental building block is not NAND gates, but 4 or 6 input look-up tables (with sundry other assisting blocks). That changes your viewpoint, as any function of 4 (or 6) inputs costs the same...