No, really -- 2 bits this time

It took me far longer than I had anticipated, but I've finally got the two-bit ALU working correctly.  As I said in my previous post, the problems were all in the control bits.  All sorts of unholy things happen when you try to reduce their number.  Had I chosen to use five bits, the control bit space would've been very sparse, but getting the circuit working would've been merely a matter of nailing down which combination of control bits to use for each operation.  But no, I had to try to be clever.  I had to see if I could use three bits.  Turns out yes, I can.  The trickiness arises when you try to find the one magical bit pattern which will allow all five operations to work without stepping on each other.

Hardware Layout

Here's a diagram of a typical bit in the ALU:

The circuit for a typical bit is best described as a modified full adder.  These modifications, which are necessary to support five operations (ADD, SUB, AND, OR, and 1-bit NOT), are as follows:

1. There's now a subtraction mux which determines whether the full adder sees B or not-B.  Not-B is presented only when we're subtracting.
2. I added two result taps (RA and RB), in addition to the traditional output (labeled RC).  RA gives me access to AND and NOT; RB to OR; and RC to ADD and SUB.  A final 4-1 mux, controlled by OP0 (low bit) and OP1 (high bit), selects between the three.
3. Two muxes -- one controlled by OP2 for AND, and one controlled by OP0 for OR and NOT -- intercept input values and replace them with hard-coded values.  The OP0 mux, for example, allows us to turn the two following NAND gates into NOT gates.

I started out thinking I'd need five control bits -- OP0-3 and SUB.  Somehow I realized that only OP0-2 and SUB were required, and started working on eliminating one of those four.  SUB is pretty much off the table, as it can't be derived from any other line, and doesn't influence any other lines.  I tried guessing at values, with marginal success, until I came up with an approach which simplified things significantly.

First, realize that OP0 and OP2 are the important players.  We'll need OP1 to help select among the result bits, but we can reorder the input values to the R mux just about any way we like, so there's less pressure there.  So first we'll figure out the OP0, OP2, and SUB values for each operation, and then we'll come up with values for OP1 which make the R mux work (i.e. which don't result in overlap).  Once we've come up with OP1 values, we'll see if we can derive one of the OP bits from the other two.

If we just happen to pick OP0 and OP2 alignments (i.e. which bit gives the hard-coded 1 and which passes the existing value through) shown in the diagram above, we get the following truth table:

Operation	OP0	OP1	OP2	SUB
ADD	0	1	1	0
SUB	0	1	1	1
NOT	1	0	1	0
AND	0	0	0	0
OR	1	1	1	0

Looking at this table, we can see that OP2 is easily derived as OP0+OP1.  Three extra NAND gates, and we're down to three input control lines (OP0, OP1, and SUB).

An aside: We had some flexibility with the OP0 and OP2 mux pin assignments, because it's trivial to swap the pins, reversing the entire column in the truth table.  Say we started with the OP2 mux having the hard-coded 1 when OP2 is high.  OP2 in the truth table would thus be 0, 0, 0, 1, 0.  This can still be synthesized from OP0 and OP1 as OP0 NOR OP1, but that requires four NAND gates.  Flip the pin assignments on the OP2 mux, and we need only build an OR gate, which requires three NANDs.

Verification

Testing the ALU is a bit of a pain with 2 bits, and would be even more annoying when fully built out. Five operations times 2 bits (eventually 8 bits) -- it just screams for automation. While the Front Panel may seem a bit silly for interactive use (wiring up LEDs and switches isn't that hard, though it is tedious), it really comes into its own for testing. I wrote a program which uses the Front Panel to set the control and input bits to a particular configuration, and to then verify that the output bits have the expected value. That program takes an input file which describes how to perform each verification.

Armed with an input file which contains 36 test cases, I can now validate the entire ALU in about 15 seconds by running a single command. Suddenly all that time spent building the Front Panel seems quite worthwhile.