TTL Brainfuck Computer Part 6 - Breadboards and Puzzles, Old and New

Part 1 (first) - Part 5 (prev) - Part 7 (next)

Breadboards

The new breadboards arrived! At more than three times the price of the old ones and with a one year warranty, I wasn't sure exactly what to expect, but damn. Literally everything about them is an order of magnitude better, right down the quality of the packaging.

Here's a non-exhaustive list of the major differences:

• The plastic looks and feels like ABS (think Legos) rather than HDPE (think plastic milk jugs)
• The silk screening is much clearer and perfectly aligned with the holes
• The boards lay flat by default, even when connected together
• There are more plastic connection tabs along the long edge for better stability
• There are connection tabs along the short edge so they can connect end-to-end, one in the center, and one on each power rail. This made the bus section of my megaboard much more stable
• On visual inspection, none of the holes look like they're obstructed by the clips inside
• They include a metal plate to stick on the back, I'm assuming for both shielding and structural support
• The warm yellowish color is easier on my eyes under fluorescent/LED lighting. It also makes white wires easier to spot
• Even though it's not white, it is completely opaque, so it ends up looking brighter than the white ones.
• The double-sided tape is trimmed so it doesn't get in the way of the connection tabs
• Pushing leads into the board doesn't push the contacts out through the other side
• Actually, the contacts themselves deserve an entire section

3-2-1 Contact!

Imagine you grew up eating nothing but USDA choice sirloin. Now imagine going to Morton's or Gallagher's and having, for the first time, 21+ day dry-aged prime ribeye (or filet, if you prefer). This is what it was like the first time I pushed a lead into these breadboards.

At first it takes a little more force than the cheap ones to open the contact. This is a teeny bit annoying for components with long leads, but I found shortening the leads makes the entire breadboard experience better (much less stuff sticking up to accidentally knock over with fat fingers, easier to add more components nearby, etc.).

As long as the lead is going into the plastic hole, it will be captured by the contacts if you apply enough pressure, unlike the old ones. Those would often bend leads even if you push them in straight down & center.

The power rails hold on even more tightly, which again can be somewhat annoying the first time you insert a lead, but the benefits are well worth it. None of the connections show any signs of loosening after working on other pieces of the board. The bus was physically connected to the left half by only 4 wires (2 ground and 2 power) and never showed any signs of shifting.

The corner-to-corner resistance with the minimum number of connections was about 1.5 Ω compared to the 10-20 Ω of the others (I say 10-20, because any slight movement of the old ones would screw up most of the connections).

So yeah. Don't skimp on your breadboards unless you're a masochist.

Copy Pasta

I spent Thursday evening moving/copying the existing circuitry to the new breadboards. From the experience with the first iteration, I decided to make several changes. Here's the current state:



I realized I had been orienting the breadboards the wrong way around. All of the power & ground connections had to jump across the ground & power rails. This doesn't have any material effect on the functionality, but it did mean some modules would have to cross wires with another to reach power (aesthetically unpleasant), and all the power jumpers are 1/10" longer than they would otherwise need to be (marginally less cost-effective).

Because of this change, I had to move the power adapter to the other side of the assembly, which is actually more convenient for the way my desk is set up. I went ahead and brought the clock with it, and I added a couple switches to the clock for manual mode (not connected yet). I also added an inverting buffer to provide both inverted (yellow) & non-inverted (white) clock signals for when that becomes a thing.

Now all of the components I had working are on the left side of the board, which I'm calling the Data Side. The empty boards on the left will likely end up being the I/O areas. The right side of the board will be the Program Side, and house the program ROM, controller logic, etc.

I also made an effort to do much flatter, cleaner-looking routes. The thick bundles of wire in the previous version made it difficult to use the LED modules I made to monitor the counters, and it was much harder to follow individual wires between components.

Speaking of LED modules, I finished cutting the 16-bit one down to size. One of the LEDs has a janky connection. It would be pretty tedious to remove and I'd worry about damaging the ones nearby in the process, so I'm not going to bother for now.

Since minimal power consumption has never been one of my goals (I'd be using CMOS if it were), and since these breadboards are so much more reliable, I decided to remove one of the tri-state buffer chips (74LS244) from the Data Register and leave the counter inputs always connected to the bus.

I also modified the color scheme. I was originally planning to use rainbow colors to represent the bit positions of data lines (you can see that in the jumpers connecting the top & bottom bus sections on the old version), but that would get confusing with the colors being used for more general "kinds" of signals. I didn't end up using that, even in the previous build, but when I went to connect the new bus sections, it was a good time to solidify my plans.

In the previous build, I thought it was pretty clever how the RAM chip had its bi-directional bus interface in green, and the data register had "from bus" as blue and "to bus" as yellow. However, I was disappointed by the lack of orange overall, which you may notice is "my" color (along with blue). So I decided that all connections directly to/from the data bus would be in orange. I was already using orange for the LOAD signal on the counters, so the "load data from the bus" control lines will be the same color as the connections to the bus, which is neat.

I preserved the meaning of blue and yellow by using yellow to connect the outputs of the counters to the inputs of the tri-state buffers, and blue to "copy" bus signals from the buffer outputs (bus connections) to the counter inputs.

The borrow/carry signals for both the data register and pointer now use the same colors: green for up, brown for down (rhymes!). I also reversed the order of the counters, such that the most significant counter is on the right. This fits a bit more logically with how the count signal flows from the buttons and avoids a two long run of wires across all the chips.

This is actually why the RAM address lines look a bit in disarray; there are only 15 address lines and I had the most significant bit of the 16-bit counter connected to the address lines and I DIDN'T have the second-most significant one connected, so the memory would see 2 addresses repeated twice before moving on to the next. The look of the wires is a result of shifting them all over by one.

Old Puzzles

Swinging back around to the loop optimizations from last time, I had a couple fruitful discussions on Reddit and Hacker News.

The reason I hadn't settled on one way or another is that pre-processing allows me to achieve my performance goals during execution, but it makes the machine into a sort of combined compiler+CPU, rather than "just" a CPU. I feel strongly about both goals and have been struggling with a good way to word this newly discovered principle. The best I have so far is:

• Purity - This is a CPU that runs Brainfuck; strong justification is required to do anything a "normal" CPU or Brainfuck wouldn't do

I really don't want to sacrifice purity for performance, but I also don't want to sacrifice performance for purity. Luckily there is a very precise modification I can make to the principles that can give me (nearly) the best of both worlds:

• Constant time execution of each instruction - It should never take more than 3 cycles to execute any instruction
• Amortized constant time execution of each instruction - Let i be some instruction at a particular location in a program. Let n be the number of times that instruction has been executed since the program started. Let E_n(i) be the average number of cycles required to execute i n times. The limit of E_n(i) as n approaches infinity must be 3 or less.

The "minimal number of execution steps" principle could also be defined in terms of E_n(i), but I think it's clear enough as-is.

I'm now planning to use a hybrid of the approaches from the previous post. The first time through a loop, if the loop condition is 0, it will skip over the instructions in the loop one at a time. In the process, it will index the start & end locations of the loop and any loops nested inside it. The next time the loop is entered, the indexed location will be used to jump to the end if the loop condition is 0.

Another advantage of this approach is that it provides an incremental pathway of increasing complexity for implementing the looping logic. I can start with the "pretend NOP" approach for linear time on both [ & ], add the stack-based approach for constant time ], then use the stack RAM as a bi-directional index for amortizing [.

In a similar vein, I'm also planning to use a data zeroing counter instead of erase-on-reset. The first time a memory location is moved to, it will synthesize a 0 (probably by clearing the data register and scheduling a write to RAM). Unless a program passes over memory locations without ever reading/writing them (a rather silly pessimization in the Brainfuck code), I believe this should match the performance characteristics of pre-zeroed RAM.

New Puzzles

So I got everything hooked up, and after fixing the address lines to RAM, I was still getting some weird issues. I could use the buttons to move up and down in RAM, but at some point the output would stop changing when going down. At first I thought this was just a coincidence; that a bunch of the high memory addresses, by quirk of die process, started out filled with ones on power-up.

Then I hooked up my 16-bit LED counter and the strangeness intensified. With the counters all starting at zero, count up seems to work as expected. If I hit the LOAD button to fill the counter with 1s (due to floating TTL inputs pulling high), counting up once sets it to zero, and it continues counting from there. However, counting down from zero leaves it at zero. If I count up past zero, it will count down to zero and stop. If I load all ones, it seemed to count down from there.

Until I realized that it was the most significant bits that were changing each count not the least significant. O.o When those most significant bits counted down below zero, suddenly all the least significant bits lit up, then the count-down would happen in the least-significant counter, until it reached zero. Then the most significant counter would start changing.

I double checked that borrow/carry-out connected to count down/up of the next chip.

I checked the continuity of connections between the chip pin entering the breadboard and the signal line entering the breadboard and found nothing wrong.

I checked the voltage levels of the borrow lines with a multimeter, and they all went low-then-high as expected when I pressed the down button while the data was all zeroes.

I triple-checked the borrow/carry-to-down/up connections by removing and re-inserting them. Same behavior.

I verified that the underflow works with the data register (2 chips) by having it count down. All of my assumptions checked out.

I replaced all the counter chips with brand new ones that came earlier this week and they behaved exactly the same. This also had the effect of quadruple-checking all of the clear, load, borrow, carry, up, & down connections.

Since a lot of the issues seemed to come from the most significant bit, I swapped out the capacitor on my clock to get a range of ~ 1 to 10KHz and watched "count up" work perfectly over all 16 bits. As soon as i switched to count down, it would quickly hit zero and stop.

I removed the LED bank and measured the output voltages directly, in case the LED board was causing issues. The outputs all stayed low when I tried counting down.

I added a 100uF capacitor across the power rail on the board with the counters in case it was a switching issue. Same behavior.

I rearranged all of the clear/load wires, both to reduce overlap and to double-check their placement, even though they both worked as expected.

Nothing even hinted at a cause until I removed the borrow/down connection between the 2nd and 3rd counter. Once I did that, the low order byte started working perfectly (basically a copy of the data register). After another pass with the multimeter, I still could not see anything wrong.

I started googling for issues with cascading counters, and everything I read says what I'm doing should work as expected.

Knowing how much I don't know about electronics yet, I figured there was some minutiae of electrical engineering I missed. Maybe I'm getting voltage spikes? Maybe the signals are ringing in the breadboard? It's time for the oscilloscope...

Since the clock signal is driven by a schmitt triggered inverter, the rising and falling edges are extremely clean. There is a tiny bit of ringing at the detection limit of my oscilloscope (70MHz), but at +/- 600mV, it should be well below the threshold for a false-1.

Triggering on the clock and watching the various inputs & outputs didn't produce anything unexpected until I probed the borrow output of the third chip. Suddenly the high order bits started flashing rapidly as if the probe of my oscilloscope was dropping it to ground and triggering the count. I don't see how that would be possible unless this was a CMOS chip; my probes are set to 10x attenuation and should not draw enough current to register as a 0. Maybe I'm wrong about that?

It seems consistent though. If I touch the probe to the clear line on the 3rd chip, the first two chips start behaving correctly. Wait what?

I started rearranging some of the connections again while the clock was running and the LED module was plugged in. When I removed the clear line between the 3rd and 4th chip, the first 3 counters started working perfectly.

Ok... Now I'm getting somewhere. I had noticed that the voltage on the Clear line was in the 0.6V range earlier. It seemed a little high, but it did make sense since you have to sink some current from TTL inputs to register a zero, and that is going through a 1K pull-down resister.

I replaced the 1K resister with a 470R and everything is peachy in counter-land.

I don't quite have a clear grasp on what's going on, but the gist of it seems that when underflowing, the fourth chip in the chain gets into a state where it drives the clear line so high the other chips register it as a signal.

I'm sure there's something in the 74LS193's data sheet that would've alerted me to this problem. I had problems before with pull-down resistors. My first electronics kits had CMOS chips (one had CD4000 series, the other had both that and 74HC) so I generally went with 10K. I switched to 1K when I was having some not-similar-enough-to-ring-a-bell issues with the Data Register.

Anyway, here's the thing hooked up to life support, running properly at 32 KHz. The fact that the clock is operating at 88% duty cycle means the actual swiching is happening in the hundreds of KHZ (around 700 if I mathed it right in my head). The pie in the sky goal I have in the back of my mind is 10 MHz for the final build, so this is pretty encouraging.

Next Steps

Once I get Now that I have this counter issue sorted out, all of the major pieces of the Data Side are in place for the +, -, <, and > operations (half of the language), so I plan to move onto the Program Side.

Last week I made a half-hearted attempt to program an EEPROM with my Arduino but didn't get very far. The code was quick & dirty so I'm sure it wasn't doing the right thing somewhere. Hopefully my next post will involve a look through program memory.

Part 1 (first) - Part 5 (prev) - Part 7 (next)