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.

It's alive!

After implementing an 8-bit full adder, I decided to turn it into an 8-bit ALU.  The ALU supports addition, subtraction, NOT, OR, and AND.  It's considerably more complicated than the full-adder, but at the same time I'm happy with the degree of reuse I was able to achieve.  The addition of support for AND, for example, required only the addition of a 2-1 mux per bit (2 74HCT157s for the whole ALU).

I've wired up two bits so far, and have started testing to ensure that the basics are sound before I turn it into even more of a rats nest.  This turns out to have been a wise choice, as I made a few mistakes with the control bits -- mistakes which are much easier to correct with two bits than four.

I'll post schematics and diagrams when I get all eight bits done.

Dave's Lab Power Supply Design

This post is more of a memo to self than anything else.  It's a reminder to me to watch the complete set of EEVblog Lab Power Supply Design videos.

Part 1

Part 2

Part 3

Part 4

Part 5

Part 6

Part 7

Decoupling with Bypass Capacitors

To ease myself into this hobby, I began with the SparkFun Beginning Embedded Electronics tutorials. They were a great way to start, and had me well on my way to making my first RS-232-controlled blinkenlight in no time. As part of that tutorial, they told me to install bypass caps near Vcc on all ICs. Okfine, monkey can add prophylactic caps everywhere. But why? The SparkFun page describes their function at a high level, but I've always wanted to know more. Cap monkey want pictures. Cap monkey want to know why he has a pill box compartment dedicated to his supply of 100 or so 0.1uF caps.

This post is what I've been looking for. Details. Pictures. Sample circuits. What more could a cap monkey want?

http://www.vagrearg.org/?p=decoupling

A full adder -- complete!

I started this post back in October when I actually finished the work, but I forgot to post it then.  So here it is now.

Three million wires later, my 8-bit full adder is complete.

Here it is with the front panel attached.  I use the front panel in lieu of switches and LEDs.

Here's the circuit by itself:

Each pair of columns calculates four bits.  Each bit needs nine gates, and consists of two dedicated 7400s (actually 74HCT00s) and a quarter of a common 7400.  If we number the ICs in column-major order, bit 0 is calculated by ICs 1, 2, and a quarter of 3; bit 1 is calculated by ICs 4, 5, and a quarter of 3; bit 2 is calculated by ICs 6, 7, and a quarter of 3; bit 3 is calculated by (wait for it) ICs 8, 9, and the final quarter of 3.

Due to layout weirdness, bits 0-3 are calculated by the right pair of columns, while bits 4-7 are calculated by the left pair of columns.  I'd love to say the vertical offset is intentional, but it's actually due to a layout mistake or change in plans, the details of which I've since forgotten.

Wiring this thing up was mind-numbing, but it was awesome to see it come to life (I tested each bit after I wired it up).

Here's the schematic.  My original intent was to build a 4-bit adder, but I had so much fun wiring(!), that I decided to do it twice, for 8 bits.

A full adder

A full adder, slowly but surely....

Here's 3.5 bits (out of a planned 8):

... and 5.5 bits:

Only 1.5 bits to go!

Front Panel up and running

At long last, I finished populating the front panel board.  Oh what an adventure that was.  I also built up quite the list of things to change for v2, if ever there is a v2.  Even if there isn't, I learned a lot about what to do and not to do for the next PCB I design.

Before I get into the details, here are some pictures of the completed front panel board:


Here's a video of the front panel controlling a simple 2-input AND gate from a 74HCT08N.  The whole purpose of the front panel is to make LEDs and switches unnecessary, but LEDs make an appearance in this circuit for validation purposes -- just to confirm that the front panel is doing what it says it's doing.

Things I learned:

Lots more and better silkscreening.  I'm having a heck of a time identifying the correct input and output pins, to say nothing of distinguishing between the +5 and GND pins.  I should've silk-screened the pin numbers all along the bottom headers.  Silk-screened IC numbers (the manufacturer's part-number -- not the Ux or ICx number) are less useful when they're under the IC -- especially if you're using sockets.  I also failed to leave any orientation marks to help me plug in the ISP cable correctly.

Status indicators.  There aren't any LEDs on the board, which can make it difficult to tell whether the board is on, whether it's receiving data, or in general what it's doing.  Eventually it would be fun to have LEDs on every input and output pin, but in the meantime, for v2, I'd settle for power and one that flickers when data is transmitted or received.

More space for I/O cable connections.  I'm still conflicted as to how I'd like to connect the front panel to the PCB.  I had originally thought to use ribbon cables with IDC connectors, but those are wide enough that I'd need to either widen the whole board or make a third and fourth row of I/O pins.  A further complication there would be that I'd need cables with IDC 1x4 on one end and 8x1 0.1" sockets on the other.  That could get expensive, but we'll see -- connector prices jump dramatically once you stray even slightly from the beaten path.

Pin orderings matter for the ISP connector.  I used the P6 connector in the schematic capture program, which numbers pins like an IC -- ascending counter-clockwise from the upper left.  Unfortunately, the pins are supposed to be numbered in zig-zag style, with 1 and 2 on the top row, 3 and 4 on the middle row, and 5 and 6 on the bottom row.  The end result of that was chaos, and a non-functioning ISP connection.  I ended up cobbling together a cable to go between the ISP and PCB which unraveled the confusion.

Pin orderings matter for the DB-9 connector.  The DB-9 part I used on the schematic used the male DB-9 pin numbering, which is the mirror image of the pin numbering for the female DB-9 that I'd eventually be using.  Happily, I was able to get myself out of that situation by mounting the DB-9 on the bottom of the PCB rather than the top.  Doing so actually made the design better, as my USB-to-serial adaptor takes the form of a heavy dongle that plugs into the DB-9 port, so mounting it on the bottom of the board kept the dongle from flipping the board over.  Unfortunately, getting to this realization required much gnashing of teeth, the purchase of an unnecessary male DB-9 connector, the sacrifice of a female DB-9 connector, and much soldering and desoldering.