Saturday, January 18, 2020

TTL Brainfuck Computer Part 9 - Clocking Back In

Part 1 (first) - Part 8 (prev) - Part 10 (next)

After sitting in a box for two years over two moves, the BFCPU has re-emerged and progress has resumed!

Before the box

Shortly after I posted the last update I incorporated the new clock generator which you can see in the upper-left, though not exactly in the form pictured. There weren't any of the colored wires going over to the right side of the board. I just used a single jumper to connect any of the frequency divider outputs to a final flip-flop at the end.

The flip-flop served a few purposes:
  • Final divide-by-two stage to make a very slow clock since I didn't have a button anymore
  • Buffer so the frequency dividers wouldn't have to drive the clocks for everything else on the board
  • Provides inverted and non-inverted output
After that, I connected the program counter to the program ROM address lines.

Since brainfuck programs only have 8 instructions, I only need 3 bits for the instruction set. I connected the first three data lines of the ROM to some blue LEDs and the unused lines to red ones.

As a quick sanity check to make sure the chips play well together, I connected the high bit of the ROM data and the manual reset button through a NOR gate to the program counter. Since the ROM is filled with FF in the unwritten areas, this means the program I had written onto it:

00 01 02 03   +-><

would repeat indefinitely.

I connected a slow clock to the program counter, and ... nothing. The program counter was all zeros and staying that way. The data lines of the ROM were all off, since the first instruction is 00. If I disconnected bit 7 everything would work. I spent a few days trying to diagnose the problem. I checked voltage levels, I added a buffer between the ROM data line and the reset circuitry, and then looked again at the data sheet.

If I'm remembering correctly from two years in the future, I discovered that I had not ordered the part that was TTL-compatible. So I spent a bit of time looking into options for level shifting, but my efforts were quickly put on hold.

I got a new job that was an hour commute each way for only 16 miles of driving, so my available time and mental capacity drained away. We decided to move closer to work, so everything was packed up.

We never really settled into the first place we moved, and our bedroom had water intrusion from the storms last winter. So we moved again when our lease was up. Fast forward several months, I have yet another new job and I finally finish unpacking most of my boxes.

After the box

I got my electronics desk set up and started digging through my neural records to figure out what my next steps would be. At first I went back to looking at logic level shifting solutions, but it would just be a hack for a mistaken purchase. Plus, I was never fully convinced that that was even the problem.

So I went back to investigating the circuit. I tried passing bit 7 through a bus transceiver before going to the reset line. I checked the current passing through the reset lines of the counters. I checked the voltages coming out of the ROM, the transceiver, the NOR gate, etc. Everything was consistent between bit 7 being attached and not.

Then I looked at the absolute voltage levels. On the board with the ROM chip I was seeing it dip down to about 4.7 volts, even though the power supply output was reading 5.0. Eventually I narrowed it down to the power line coming into the board. So I soldered up some new leads with some 0.1" headers to provide more low resistance paths to the power supply. It was in vain though. The program counter was still resetting.

Feeling a bit defeated, I hooked things back up to the scope. This time I looked for a pulse on the ROM data line. Lo and behold, for the 150 nanoseconds that the ROM takes to switch between addresses, the data lines are all high. This means the counter would reset immediately after incrementing to the second instruction!

All I had to do was make sure the reset only occurred on the other edge of the clock. Either I misread that the part was incompatible or I'm getting lucky, but everything I'm seeing so far points to the ROM chip working exactly as intended.

With that problem solved, I was officially making progress once more!

Of course, restarting isn't what most programs do when they get to the end. If you write a brainfuck program to compute some result, you want to see that result. Starting the program from the beginning of non-empty RAM would have unpredictable results. So I decided to use bit 7 as a halt signal instead. This meant revisitng the clock circuitry.

Design Time

Before getting to that, though, I started thinking more about the high level design. I've had a soft goal of one instruction per clock through this entire process, and I wanted to make sure I worked out the details for the four instructions I'm working on.

I was watching Robert Baruch's series Building a 6800 CPU on an FPGA with nMigen and decided to come up with timing diagrams for the clock, ROM outputs, and control signals. As an example, to execute a + instruction, there are three steps:
  1. Read and decode the instruction
    • Increment the program counter
    • Set the RAM to input
    • Set the data register to output
  2. Pulse the data register's count up line
  3. Pulse the RAM's write line
For one instruction per cycle, step 1 needs to happen on the rising edge of every clock. Step 2 has to wait 150 ns for the program ROM to update plus a bit more for that to propagate to the enable signals. Step 3 has to wait however long the count up was pulsed. Then step 1 of the next instruction will have to wait for the RAM write pulse to finish.

With three different places to wait per cycle, there was no way I could just use the rising and falling edges of the clock. The first obvious thought is to use a three-phase clock, but that would be overkill. I would have six different rising or falling edges per instruction in that case. I only needed one more edge than I already had.

I decided to add a single phase, delayed by the time it takes to decode an instruction (about 160ns). The instruction is read on phase 0, the data register is incremented on phase 1, and the RAM is written on the falling edge of phase 0. Rather than using pulse generators on the clock edges, I logically combined the two phases into an adder clock and a write clock. Here's the timing diagram for the full program:

In order for the phases to overlap correctly, the clock speed has to be a bit slower than half the speed of the decoder (160ns → 320ns). That works out to a bit over 3 MHz. Not too shabby! Though if I really want to push the performance in the future, I can add a third phase for the write clock and optimize the adder->write->next instruction timings.

For the actual hardware, I looked up some example circuits, and found one built around the 74LS123. This is a pair of delayed pulse circuits that can be wired up to act as a clock phase shifter. All I needed to make it work were some jumper wires, a 5k resistor, and a 10 pF capacitor.

Now that I knew I had a path to success, I started working on the clock circuitry again.

Muxing it up

While I really liked having the ability to select from a wide range of very accurate clocks, it didn't have a convenient interface. You had to know or find out by trial and error which pins on the chips have the clock outputs, which ones are faster than the others, etc. and manually switch a long jumper wire between them. As I mentioned earlier, I also lacked the ability to manually trigger the clock.

I had 26 different clock signals available from 8.000 MHz to 0.238 Hz. I knew it was going to take an entire section to make a selector, so I shifted the entire right half of the board down by one to make room for a new clock section.

I found the largest multiplexers in my kit which can combine up to 8 signals into one using a three bit selection. This means I could connect 24 of the clocks to three chips, then use a fourth chip to select from those. So this means there need to be three switches to select the inputs on each of the first three multiplexers, and two switches to select between multiplexers.

That left 5 inputs open on the final stage and one unused switch. I hooked one up to a wire I can use to select a clock the old way. I hooked the first four inputs up to a manual clock button and the unused switch to the high order selector bit.

So with the pictured DIP switch, the first switch on the left toggles between step vs run mode (all four manual inputs vs any of the four clock inputs). Skipping one switch, the 3rd and 4th are used to select among the three multiplexers (00, 01, and 10 slowest to fastest) and the manual clock selector wire (11). The final three switches are hooked up to the other three multiplexers. This makes it easy to switch among two different clock speeds and manual mode.

The final multiplexer output goes into the flip-flop that used to be the last stage of the frequency divider. So this means the clock toggles between high and low each time you press and release the button.

While moving the boards to accommodate the clock, I also discovered the earlier voltage issues were from a single wire that had corroded. Replacing it brought the voltage back up to 4.98 across the board, so I put the old power switch back and gave it both an "on" and "off" LED.

Back to the drawing board

So now I had a nice convenient clock selector and single-step mode, I went back to implementing the phase shifter. I went back to the 74LS123 design doc and verified the parts I would need: 5k resistor and 10 pF capacitor.

Wait... 10 pF? I think the smallest capacitor I have in my kits is 22 pF and they're all in use keeping the high frequency clocks from ringing. Not only that, but this is a freaking breadboard computer! 10 pF is down in the range where all the large, parallel runs of metal in the slots can make a significant difference. There's no way I would be able to get a reliable result from this. Thankfully I RTFMed before starting to wire it up.

So my next thought was to find something in my TTL kit with a lot of gates that could be used for a propagation delay. I figured it would be one of the high numbered ones, and the highest I had was 74LS374. Well what do you know. Eight flip flops? That's exactly the kind of thing I was looking for. The '374 was edge triggered though, so chaining them together would divide the frequency in half each time. Luckily I also had the '373 which is "transparent" so it would pass along the change immediately.

Note to self: replace the '93s in the frequency divider with '374s

I had to use 12 stages (one and a half chips' worth) to get the 160ns delay I was after, but it worked like a charm.

Next I implemented the clock phase combiner in logisim-evolution and did some boolean algebra to figure out how to use a single kind of gate (NOR or NAND) to reduce the chip count. I wired that up, hooked up a clock fast enough to see the two different phases clearly on the scope, and saw something pretty similar to the timing diagram!

I had to do a bit of tweaking since the '373's flip-flops seem to respond faster on the falling edge than the rising edge. So at first I was getting a lot less overlap than there should have been. After switching around some of the phases and inverting the logic, it was all working as intended.

It's the final count down!

Now that I have the clock pulses I need, the last thing between here and fully executing instructions is the decoder. Figuring out which instruction is loaded is pretty simple. The 74LS155 takes a 3-bit input and makes one of its 8 outputs low depending on the value. So I just hooked that up to the low three bits of the ROM. You can see the outputs of this selector on the right here:

Since I want FF to represent halt, all of the data lines go into an 8-bit NAND. I was starting to work out what gates/chips I would need to combine the halt signal with the clocks. Then I realized the flip-flop in the final stage of the clock selector has an input that will stop it from toggling. I just hook the NAND up to that and halt is implemented!

This is where things stand right now. I just need to send the output of the selector and the correct clock signals over to the other side of the board. I'm optimistic that my next update will have a fully excuting brainfuck program (albeit without loops or I/O).

Until Part 10!

Part 1 (first) - Part 8 (prev) - Part 10 (next)

Thursday, October 12, 2017

Lucky break

Yesterday we were leaving Lucky (a supermarket) in downtown Hayward. Ahead in the parking lot, right next to our car, a delivery truck began backing out while a group of teenagers was walking behind it. They started waving their hands, slamming on the sides of the truck to get the driver to stop but he kept backing out. The running board hit one of the boys in the shin and he fell over. The driver continued backing up as the fallen boy scrambled away, and the others ran around to the front of the the truck trying to get him to stop.

The driver finally stopped, sticking partway out into the lot and blocking our car in. At least four other people watched it happen, and they just went to their cars or into the stores and didn't want to get involved. We stood by to make sure the boys had support from witnesses.

At first the scene was just commotion; the boys understandably were riled up, yelling threats of lawsuits and arrest, filming with their cell phones, taking the license plate number etc.

Then the driver started to back out again!

This guy hit a minor pedestrian with a commercial truck and was going to leave the scene before any officials arrived. He backed all the way out to the point where he could start driving forward. I stepped in front of the truck and put my body against it as he inched forward. He stopped when I looked in his eyes and pulled out my phone to call 911. The boys started swarming the truck, some joining me in front or going to the back to block his exit, some climbing on the cab roof, etc.

I told the dispatcher that I was witnessing a hit-and-run in progress, and that we were preventing him from leaving. I gave her my details, the location, etc. and said she was sending some officers.

The driver sat there with the engine running, blocking the main lane of traffic in the lot. A woman leaving the store complained about her car being blocked in. By this time some of the angst had died down, and my wife suggested we get him to pull back into his original spot.

We all started to gesture as such, asking him to park again, backing off the front of the truck to give him some room. My wife went up to the driver's window and asked him directly a few times. Eventually we saw him put the truck into gear and he parked, though he left the engine running. The boys sat down on the back of the truck, and a minute or two later the Lucky manager came out.

He started asking us the usual from those of us at the back of the truck: contact info, what happened, whether we had already called the police. While we were talking with the manager, the driver finally turned off the engine and stepped out.

When the manager talked to the driver, things turned towards the surreal. We overheard the driver saying something like "they got hit on purpose to get money," blaming them even though he tried to flee the scene. The manager came back and started asking once more about whether we had called the police, and said that he had as well, but that since it was private property they might not come. He asked if the boys were injured, and said that it would be really bad for the driver if the police came.

In near unison, the teenagers, my wife, and I screamed "WHAAT?!!" followed by individual variations of "Are you fucking kidding me? It's going to be bad for HIM? What about the fact that he just hit a pedestrian and tried to leave the scene? He should be arrested!"

By this point it had been about 10 minutes since I called 911, and with the manager seeming to advocate for the driver, I called the non-emergency police number to check on the status of our call. She asked "aren't they on scene already?" I said no, but started looking around and saw a police car at the corner waiting to turn right.

Two cars showed up at first. The officers took down my info and account, then one talked to the boys and the other went around to talk to the driver. As another police car arrived, I overheard the officer say to the driver something like "this wouldn't be so bad for you if you had a license."

In the hopes of planting as few assumptions as possible, I have intentionally omitted any mention of race. But at this point, I can't just say "Everything calmed down for no apparent reason when the third officer arrived." The manager was latino, as was the driver of the truck. The first two officers were white, as were we. The third officer was black, as were the kids.

Most of the people on the scene noticeably relaxed when he arrived, and various mental circuits that had been shut down in preparation for fight/flight started to fire back up again.

With our accounts provided to the police and no longer feeling like we were the only ones around who could offer these boys any hope, I realized we were all standing outside in the acrid smoke funneling down from the fires up north. My wife and I had just bought some breathing masks from the hardware store nearby, and figuring that the police would be taking statements for a bit, I went back to buy a few packs for everyone. As I was leaving the store, the boys were walking away from the scene, so I handed them the masks and wished them a good one.

When I got back to the car, my wife was there holding our dog as the police dispersed and the driver started to leave. Since there were no serious injuries, the police made him report the incident to his company and let him leave without arrest. At one point while I was gone, my wife said one of the white officers asked something like "Well who do you think will win you or the truck?" mirroring the victim blaming of the manager. This just added further insult to injury.

We sat there for a while reflecting on what happened. There is a lot to feel ambivalent over. When the incident first occurred, the truck was moving slowly enough that the kids might have been able to avoid being hit, but that's a matter for the police/insurance to sort out. When the driver tried to flee there was no doubt that we needed to stay to support the kids.

When I left to buy the masks, my wife felt helpless in the face of the victim blaming attitude of the cops, but I could see the boys appreciated the gesture. In addition to the victim blaming, the police also treated her with less credibility than me or than when I was around.

Earlier we were gung ho! "He should be arrested for hit and run." But at the end of the day, I'm glad he wasn't. When I looked into his eyes I saw no malice, only fear.

Thursday, June 22, 2017

TTL Brainfuck Computer Part 8 - Clocking Progress

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

Note: there are plenty of pretty pictures below the fold

My pie-in-the-sky goal for the clock speed of this computer was originally 10 MHz. The LS series chips should be capable of 16 MHz, but that's not accounting for the poorly engineered environment of a hobbyist's breadboard computer. I figured 10 MHz would offer enough head room for the chips to cope.

As it turns out, the limiting factor is the EEPROM, which takes 150ns for the data to be valid after changing the address. If I set the address on the rising edge of the clock and read the data on the falling edge, that would be a period of 300ns or a frequency of 3⅓ MHz. While that's only one third of my original goal, it's well within the range of early personal computers (not that the performance will be remotely comparable).

So now I actually have a realistic target frequency, which likely can be pushed a dozen or two percentage points beyond spec (hello, overclocking!). Unfortunately the trusty 555 just isn't up to the task.

First of all, most sources I've read say it's only good up to about 1 MHz. But as an easily adjustable variable frequency (i.e. a single dial), the range and resolution are extremely limited.

I'm using a 1 M potentiometer right now. In order to have a usable range between, say, 0.5 Hz and 32 KHz, I have to manually switch from a 10 μF capacitor to a 10 nF. I'd need to go down another two orders of magnitude on the capacitor or up two on the resistor to reach 3⅓ MHz, and as I mentioned earlier, that would push the 555 well beyond its limits.

The adjustment resolution is similarly frustrating. Even though the potentiometer changes resistance linearly, the effect on clock rate highly non-linear. At the low speed end of the dial, a tiny movement makes a large difference in the clock speed. At the high speed end, the duty cycle changes more than the frequency.

Duty Dilligence

Speaking of the duty cycle, in order to keep the time spent on as close as possible to the time spent off, the capacitors and resistors need to be in particular ratios. To get a variable 555 timer with an even duty cycle, you would need both a potentiometer and a variable capacitor, each with an abnormally wide range.

As I mentioned in a previous post, the uneven duty cycle means the chips had to respond as if the clock was around 600-700 KHz even though the clock period was only 32 KHz. If I had a 3⅓ MHz clock with an 88% duty cycle, the chips would be seeing a pulse 18ns wide, which is equivalent to ~28 MHz with a 50% duty cycle.

As a quick fix for the duty cycle issue, I switched the inverter on the clock for a 74LS73, using one of the J/K flip-flops in toggle mode as a single-bit counter. Since it changes with each pulse rather than at each clock edge, its output will have a duty cycle as even as the 555's period. However, the period of the flip-flop's output will be half that of the 555, so I replaced the 10 nF capacitor with a 4.7 nF to maintain the frequency range I was used to.

The blue line on the oscilloscope is the output of the 555 timer. You can see how it spends significantly more time on (up) than off (down). The yellow line is the output of the flip-flop. You can see how it rises or falls every time the clock signal falls. Since I'm using a "raw" flip-flop instead of a counter chip, I have access to both the Q and Q' outputs to use as clock and inverted clock. The white and yellow LEDs are connected to them, respectively.

The Crystal Method

One of my first toy projects when I got back into electronics was a slowly shifting RGB mood light on Arduino. The LED itself is on a tiny breadboard and attached to the arduino with 3 signals and ground. I wanted to put the code on an ATTiny on the same board as the LED for a truly minimalist design. The ATTiny requires an external crystal to run at full speed, so I got a crystal assortment from 4 MHz to 25 MHz. I haven't made much progress on that project, but I do have everything I need for a stable, high frequency clock for the BFCPU.

The metal can on the left is an 8.000 MHz crystal. When it's resonating, it generates a near sine wave at that frequency, but it doesn't provide much current. The nearest chip is a 74HC04 hex inverter. As a CMOS chip, its inputs respond to voltage rather than current, but its outputs can provide a wide range of current. This allows it to act as a gateway between the crystal and the TTL chips. Since the output of the first inverter is part of the crystal feedback circuit, it runs through another inverter to actually provide the 8 MHz clock signal for the rest of the system.

The other chips on the board are all 74LS93s, the ripple-carry cousins of the '193 counters that make up most of the computer so far. These act as frequency dividers, giving me a selectable clock speed for any power of ½ of 8.000 MHz (4 MHz, 2 MHz, 1 MHz, 500 KHz, etc.), down to 0.4768 Hz, or about one cycle every two seconds. I'm only interested in a single "bit" at a time, so the ripple carry isn't going to be an issue.

The two 22 pF capacitors on the left corner of the board are part of the crystal resonator. The bypass capacitors straddling the high frequency chips from near to far are 1 nF, 4.7 nF, 10 nF, and 47nF, chosen experimentally to minimize noise on the outputs. There are also a couple of 100 nF capacitors across the power rails closer to the low frequency chips for the same purpose.

With nothing attached to the clock I was getting some pretty significant ringing in the outputs, sometimes as much as +6 V to -1.5 V peak-to-peak. It turned out to mostly be inductance from the oscilloscope probes, and pretty much disappeared when the clock was attached to other parts of the circuit.

Poor 555 clock, blinking away in solitude back there

In this shot, the long yellow lead on the left is connected to the 8 MHz output of the CMOS chip, and into the count enable circuitry of the Data Pointer and Data Register. The blue lead/oscilloscope probe is connected to the same signal.

The Data Pointer is set to count down, as you can see by the red lead going to Vcc just to the left of the blue LEDs. The yellow oscilloscope probe at the top is connected to the low order bit of the Data Pointer, which should be changing at half the period of the clock. Here's the result:

The scope is triggering on the clock signal, and you can see the measurement of 8.00029 MHz in the lower right. As expected, the first counter stage is flipping with every pulse. The edges don't quite line up because of the propagation delay in the counters and the NAND gates combining the clock with the control lines. If I had measured the clock at the counter input, the edges would be much closer. I left this running for an hour or so with "infinite persistence" and there wasn't a single glitch. So far so good for pushing the limits of my components!

One interesting thing to note is that TTL considers anything above 2 V to be a high signal. You can see here that the counter's output reaches just above 3 V, with a slight peak before switching. At lower frequencies, the voltage has some time to build further due to capacitive effects, and generally tops out around 4-4.5 V. You can see the effect of this in the previous image, where the 3 left-most LEDs are noticeably dimmer than the rest. The second bit from the left is the one switching the fastest, and is also the dimmest. You can see the same effect when I enable counting on the data register:

This isn't just an artifact of the camera or variability in LED quality or resistor value (which is also noticeable). If the switching speed were instantaneous, the LED would be spending just as much time on as it is off, so the only reason the brightness would be different is if the amount of current flowing is different. Since the resistance of the LED (plus resistor) is essentially fixed, the only way the current can be different is if the voltage is different.

Switching speed is not instantaneous, and doesn't change very much with clock speed. At high frequencies, instead of 50% on 50% off, it's more like 40% on, 40% off, 20% somewhere in the middle. This amplifies the effect of the already lower voltage.

Other Updates and Plans

The Data Pointer's up/down signals are now connected to the clock and control lines via NAND gates, just like the Data Register. The only buttons left are Clear signals. The Data Pointer doesn't ever load data, the load lines are all tied high.

In a couple of the pictures above you can see the beginnings of the program side. From top to bottom is the Stack Pointer, Stack RAM, Program Pointer, and Program ROM. I'm in the process of wiring up the Program Pointer to the Program ROM.

The milestone I'm shooting for next is to have a program in ROM control the Data Pointer and Data Register counters. But first I need to work the new clock design into the computer.

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

Wednesday, June 21, 2017

Complaint Breadboard

As much as I have ranted over the first breadboards I used for my Brainfuck computer, the company behind them has tried to help. After I left a one-star review on Amazon, they admitted that their manufacturing quality varied and sent me new ones. They were indeed a bit better than the first ones in a few specific ways, so I bumped my review up to three stars.

Over time, the experience was more unpleasant than first impressions suggested. They couldn't compete with a few other cheap breadboards I've acquired over the years. I won't list my grievances again here, but I decided to go back to a one-star review.

Pile of sh... re-assembled boards
Earlier this month they sent me an e-mail saying:

Sorry to disturb you again. 
I read from your review that you were dissatisfied with our breadboard. We sincerely apologize for that and we took your comment very seriously. After strict tests, we have developed a new breadboard which is of better quality. We have sent out 3 new breadboards to your address via China Post which will take about 15-20 days to deliver . The tracking number is [REDACTED] and you can track it here: ^.^
We care very much about how you feel and your review means everything to us. So we’d really appreciate it if you could give us an update review based on the new breadboard and our service. ^.^ 
Once again I apologize for all the inconvenience caused in this case and I look forward to your reply. Thank you very much!! 

The cynic in me thinks they mean "we found another supplier" when they say "we have developed", but I can't complain about the effort they're putting into making me a satisfied customer. I'm also a sucker for friendly emoji. :)

After bouncing back and forth between USPS facilities in San Francisco and Oakland for a week, they arrived a couple days ago. Whether the cynic in me turns out to be right or not, these new ones are vastly improved over the originals.

Bottom: old Elegoo board. Middle: new Elegoo board. Top: corner of my Brainfuck Computer built with Jameco boards
Two things are obvious at first glance: the plastic is much higher quality, both in look and feel, and the silk-screening is clearer. On closer inspection, there seems to be much more consistency in the way the contacts line up with the holes.

Here is a close up of the old board. You can see several areas where the contacts are directly under the holes. This would block entry of pins unless you put them in at an angle, which might go off to the side of the clip rather than into the center.

And here is one of the new ones for comparison:

One thing you might notice is that the contacts are much more visible in the new board when looking at an angle. You can see the bright spots on the left side of the holes on the left part of the board but on the right side of the holes on the right side of the board. This shows both that the contacts are more centered with respect to the holes and that they are closer to the surface of the breadboard.

Combined, these two fixes should alleviate most of the problems I had with the old ones. Insertion of components with multiple pins is much less frustrating, and retention of components is much better. In particular, these new boards seem to hold onto my DIP and tactile switches just as well as the Jameco boards.

The new boards also lay much flatter. The old ones had a noticeable curve out of the box, so they would tend to stretch and strain when assembled into a large panel. Here's a video demonstrating the improvements in curvature. Note: I'm using the one old Elegoo board that remained completely intact (I didn't cut the power strip off) to give it the best chances.

To be fair, there are still some problems with consistency. One of the three boards I received has a power rail where one contact in each block of 5 holes is misaligned:

I have not yet done any serious testing of their electrical characteristics since I'm not planning to assemble these into another computer. The contacts don't feel quite as eager to grip as the Jameco ones, so your mileage may vary.

All in all, I'm actually quite glad to have these three new boards. I had been using some of the old ones for a couple side projects, and am eager to transfer them over.

Update 2017-06-22:

All in all I'm happy with their performance. While the power connections feel a bit looser than the Jameco boards, the electrical contact seems pretty stable. The board has no problem handling an 8 MHz crystal clock with a 24 stage (6x4 bit counter) TTL frequency divider. There is virtually no noticeable effect on the clock outputs when I jiggle the power leads coming into or jumping across the board. I'm not sure how they'd behave in the bus strip/massive board configuration I'm using for the computer, but so far they look promising.

Wednesday, June 14, 2017

TTL Brainfuck Computer Part 7 - EEPROM woes

Part 1 (first) - Part 6 (prev) - Part 8 (next)

Another week, another head scratcher. I briefly mentioned past troubles getting an EEPROM writer going with my Arduino. I had another read of the data sheet, and went about rewriting much of the code. I didn't notice any glaring mistakes along the way, but did gain much more confidence that my code was doing what it should be.

Arduino Mega2560 connected to EEPROM

Alas, I still was unable to get any successful data writes onto the chip. I decided to try moving it over to a breadboard with some dip switches for addressing. The address pins are pulled down through 100K resistors, and the other side of the switch is pulled up through 10K resistors. These values should work fine since this is a CMOS chip and I'm not after super fast speeds. They just need to act as a voltage divider not a current source/sink, and I have verified that the voltages are around 4.5 for the high level and 0.3 for the low level.

The I/O pins are connected to one of my LED modules to show the output of the ROM, and to an 8-bit dip switch for entering data. The output enable and chip enable pins are the blue & yellow jumper wires, respectively, which I manually connect to ground or Vdd.

The load signal is connected to the common pole of a DPST switch (tucked above the LEDs next to the ROM), with the normally closed position connected to Vdd and normally open connected to ground.

Manual EEPROM reader/writer after some fixes

The pinout for the EEPROM identical to the RAM chips I'm using (the difference in address line numbers should be immaterial). According to the data sheet, doing a single byte write should have the same steps, as well: Disable output (set OE high), enable the chip (set CE low), and pulse the the Load input low. When the load input goes low, the address is latched; when the load input goes high again, the data is latched.

The main difference with the RAM chip is the timings. When you issue a write, you have to wait ~5ms for the operation to complete before the data will be readable (and before doing another single-byte write). That's definitely not an issue here since I'm doing this all by hand. Unlike the EEPROM in Ben Eater's computer, this one does not specify a maximum pulse width for the write cycle, so I just have a small RC filter to compensate for switch bounce.

Enabling output shows the expected 1s everywhere in the factory-fresh ROM. Before I had the data dip switch, to do a write I would:
  • Disable the ROM output
  • Move the I/O lines from the LED array to ground
  • Press and release the LOAD button
  • Move the I/O lines back to the LED array
  • Enable ROM output
This always resulted in a full bank of lit LEDs, suggesting the write failed. There were no signs of floating inputs to suggest it was rapidly changing addresses. To rule out connection issues, I swapped out the EEPROM for one of the RAM chips. Everything worked as expected.

By this point I was at a complete loss. I'd gone over the data sheet another few times. I added some bypass capacitors across the power strips near where the ROM connects to power & ground, I made sure the voltages make sense on the address pins and control signals. I used the dip switches to control the output enable pin to verify that the ROM senses the dip switch signals correctly.

The fact that 2 different software/microcontroller attempts failed, as well as the manual attempts described above, and with the successful test with a RAM chip, it became hard to stand by the "poor craftsman blames his tools" principle... Maybe the data sheet incorrectly omitted a maximum time for the write pulse? Maybe I got a bad batch? Maybe I zapped all four of them them with static? (not likely; I have a grounding strap I touch every time I sit down and have never even noticed a tickle).

Nearly ready to give up rolling my own, I started googling around for existing Arduino X28C256 EEPROM programming code. I came across a forum thread where someone said the chips come software write-protected from the supplier, despite the data sheet saying "The X28C256 is shipped from Xicor with the software data protection NOT ENABLED" (emphasis in original).

The Software Data protection feature requires sub-millisecond timing, so I headed back to my Arduino code, refactored things a bit, and set it up to send the unlock signal. It did not work. The data was still all 1s. In a desperate attempt to avoid an even more intense rage face, I gave up for the night.

The next day it hit me... While the order of the address and data lines is immaterial for normal usage, it is absolutely critical for sending the magic values to do the software unlock. I rearranged the address lines so that they match the pinout (the data already did) and re-ran the unlock. It still failed!

I need to clarify what I mean by "failing" here: The code that writes some test data reads it back and validates it against the test data. It turns on the Arduino built-in LED if it finds a mismatch. That light came on. I assumed this meant the write failed. Thinking that was a dead end, I put the ROM chip into my manual programmer to do some more investigation.

Lo and behold, when I enabled the chip, some of the bits were off! Not only that, but they seem to be the correct bits for the capital T in my test data: "This is ...". The next 3 addresses had the telltale "lower case" bit set, and the 5th address in the ROM had only the 32 bit set, which is a space. Apparently my write succeeded but my verification failed.

After one more pass over my code I finally realized what happened: the test data string in the original version called itself 64 bytes, but it was actually only 60 bytes. Apparently the 3 bytes beyond the end of the string are used for global variables. The writer would write whatever happened to be in those cells to the ROM, then failed verification when it read that value back but the Arduino's memory had changed. Here is the current code for the EEPROM programmer after fixing that issue.

I can now reliably unlock and write data to the EEPROM, and the unlocked chip works as expected in the manual programmer. Some further improvements I want to make are to use buttons to control the writing/unlocking and add a lock feature. This way it won't clobber the ROM every time it turns on, and I'll be able to use it to easily lock the chips once I have them programmed to avoid any unintended writes.

Until then, I've used my manual programmer to write the first program that will run on this computer:
Or in the CPU's encoding:

Part 1 (first) - Part 6 (prev) - Part 8 (next)

Friday, June 2, 2017

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

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


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 En(i) be the average number of cycles required to execute i n times. The limit of En(i) as n approaches infinity must be 3 or less.
The "minimal number of execution steps" principle could also be defined in terms of En(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)

Wednesday, May 31, 2017

TTL Brainfuck Computer Part 5 - Complexities and Missteps

Part 1 (first) - Part 4 (prev) - Part 6 (next)

My guiding principles, both separately and in conjunction, present some interesting challenges. Here are the optimization puzzles I'm currently working on.

Minimizing Clock Per Instruction

Modifying a value in RAM involves moving the data from RAM to the Data Register, in/decrementing the Data Register, and moving the data from the Data Register back to RAM. Since Brainfuck programs usually have several +/- in a row, the data only needs to be transferred at the beginning and end of a run.

To state more clearly, you only need to write to RAM when the Data Register has been incremented/decremented and the memory location is about to change. Similarly, you only need to read from RAM if the memory location has changed since the previous read. The story gets a bit more complicated with the I/O instructions, but that's for another day.

As an alternative to the conditional read/write, I've been toying with the idea of putting the read/writes and inc/decs out of phase. So the RAM would be read/written on rising clock, and inc/dec would happen on falling clock. Coincidentally (or more likely by foresight of the 7400 series designers), the control signals to the RAM and counters already follow this logic. I haven't followed this line of thinking very far though so I'm not sure where it will lead.

Zeroing RAM

When a Brainfuck program begins, all memory locations have to start at 0. One option would be to keep a "Clear Pointer" of the highest accessed address. Whenever the Data Pointer goes up, if it is higher than the Clear Pointer, write a 0 to that location. With some clever micro-instruction logic, this would only take 2 extra cycles the first time you access a RAM location.

A simpler (and somewhat less fun) option would be to have the reset circuitry walk through RAM with a fast clock and set it all to 0 before running the program. I feel like this better fits the "Minimal number of execution steps per instruction" principle, and more directly reflects the execution of an interpreted/complied Brainfuck program on a regular computer.

Fixing a Major Brainfuck

If you've been paying really close attention so far and, and if you have an intimate working knowledge of Brainfuck, you may have noticed some hand waiving in my early posts about constant time looping. My logisim implementation had a 'uge mistake in its implementation of the Brainfuck language, and I didn't notice until long after I'd started on the breadboard project.

The loop construct,  [ ... ], is represented in C as while (*data_pointer) { ... }. This means that as the loop is entered, the current RAM value is read. If it's 0, the contents of the loop are skipped. Otherwise, the contents of the loop run. At the end of the loop, if the contents of RAM at the current location is NOT zero, then it jumps back to the beginning of the loop.

Unfortunately, the way I built it in logisim would be represented by do { ... } while (*data_pointer);. This means the contents of the loop always run at least once. An open question is whether this change breaks the language's Turing Completeness. Another open question is what do we call this new language? But those questions are for another time.

Does this problem mean I have to sacrifice [ to the O(n) gods? Not necessarily... If I'm planning to do the "zero RAM on reset" strategy, I could throw in a parallel "index all the loop locations". I would have a bit of circuitry walk through program memory looking for all the [ and ]. In another RAM, at each address where there is a [ in the program, write the address of the corresponding ]. This reset circuitry could use the existing Stack RAM to balance the brackets.

So that's where I am as of this moment. The replacement breadboards should be here today. Yay!


On second thought, the index could be used for both [ and ], and the stack would only be necessary during analysis. That would make the control circuitry more consistent.

Part 1 (first) - Part 4 (prev) - Part 6 (next)