How to derive the boolean expression of a multi-bit gate

[netanel]

In Unit 1.2 we were given a method to derive the boolean expression of a simple 1 bit input-1 bit output truth table - ANDing together the inputs for each line that outputs 1, and ORing them together.

I found that method to be very useful in finding the expression for, say, a Mux or Dmux gate.

However I'm having trouble in deriving the boolean expression for multi-bit gates, like a Mux4Way16.

Is this method relevant at all when dealing with multi-bit gates? If it is, how do you do it?

[cadet1620]

You can derive the canonical representation for Mux4Way (1-bit) and Mux8Way, and then replicate them 16 times. You will find that the implementations for the one bit versions will be rather big because they have And terms that are 3 and 4 inputs wide and Or terms that are 4 and 8 inputs wide.

For Nand2Tetris, think about the strategy "what did I just build and how can I use it to build the next thing." In the case of Mux4Way16, you can build it out of 3 Mux16.

Think about the symbol for Mux4Way16 and how you can draw 3 Mux16 inside it.

--Mark

[netanel]

After struggling with the canonical representation I realized it is way too complex.

After staring at the abbreviated truth table of Mux4way it became painfully obvious how it can be implemented with 3 Mux gates, though I still wish I could find the solution in a more "math" way rather than drawing the circuit in my mind.
I'm sure this is out of the scope of this course, I just have this tendency to try and understand everything inside out (which brought me to nand2tetris in the first place :)).

[cadet1620]

The best math-like procedure I know is to use canonical form or truth table to generate a Karnaugh map to simplify to either sum-of-products or product-of-sums. But K-maps get tricky above 4 inputs and basically imposible to do by hand above 6 inputs. There are computer algorithms for SOP and POS simplification for larger circuits and to do trickier optimizations.

There is also the issue of what you are optimizing for. A minimum gate solution may not have the fastest performance. For example, in project 2 you will build a ripple carry adder.  There are faster adder circuits, but they require greater gate count.  If you are curious, see these posts: About carry lookahead adder and Carry Select Adder

There is a lot of art in the design of complex circuits. An example is the ALU that Prof. Nisan designed for this course. It's elegant and simple, but can do a large number of arithmetic and logical operations.

--Mark