Tag Archives: cellular chronometer

Cellular Chronometer Part 2: The PCB

I’m designing an LED matrix clock that plays Conway’s Game of Life to evolve a representation of the current time. See the whole series of blog posts about the project here.

At the heart of this project is the PCB. I set out to push my limits a bit, and I certainly succeeded at that. This is by far the most complex board I’ve ever worked on, owing mostly the sheer number of components (132 LEDs, 14 resistors, 4 capacitors, a crystal, a microcontroller, and a linear regulator) crammed in such a small space (25 x 100 mm).

The basic layout is that the front of the board is the LED matrix, while the back hosts all the support circuitry. Let’s look at each of those in turn.

The matrix


Laying out a grid of LEDs should be easy, right? Well, not that easy. Immediately after I got done drawing the schematic for the matrix, I discovered that the LEDs I selected simply weren’t going to fit in the available space. Faced with the prospect of 132 separate REPLACE commands, I quickly developed the beginnings of what I’m now considering my EAGLE secret weapon: what I’m calling external scripting. I wrote a simple Ruby script that generated all the names of the LEDs, and then piped that through some bash magic to compose the commands I needed. Once I pasted the results into the EAGLE command bar, boom, all LEDs replaced in one fell swoop.

Not an easy schematic to draw. Yes, I did it by hand.

Not an easy schematic to draw. Yes, I did it by hand.

This technique worked so well that I knew I’d take advantage of it again. I didn’t have to wait long. As soon as I switched from the schematic to the board, I found myself needing to actually position the LEDs. I tried making the grid match my desired spacing, but that was proving too tricky, especially when combined with having to position all the LEDs in a precise order. Scripting to the rescue!

A word on the LED layout scheme

A quick aside: at this point in the project, I had to decide on a layout scheme for the LEDs that both made it easy to route the board as well as write code to map the LEDs into a 2D grid. Charlieplex LEDs are addressed by (high pin, low pin) pairs, but I’ll need to interact with them from a more (x, y) perspective. This would not be something easy to change later, as its encoded in the hardware itself.

I elected to go with a strategy that put high/low pairs and their inverse next to each other, thinking that this would limit the number of far-flung connections needed. These pairs are laid out in a sort of round-robin fashion so that they’re all exercised. The result ends up looking like this:


Anyways. Using the earlier technique, I wrote another Ruby script that generated EAGLE commands to position all the LEDs according to this scheme. The scripting here was really crucial, because I had to try out multiple tweaks before I got everything just right, and without a script, I would have been committing to several hundred clicks per experiment!

Supporting electronics


The ATMEGA is the centerpiece of the back of the board. Nearby is the 16MHz crystal, and to either side are the momentary switches that allow the setting of the time. The top edge of the board is the bank of current-limiting resistors needed to drive the LEDs. Finally, on the edges of the board, there’s a 6-pin ICSP programming header and your standard LM317 linear regulator circuit set up to output 5V.

A note on the power supply. I don’t think this thing is going to be a power hog, and I’d ultimately like it to be pretty compact and beautiful, so I’m planning to just stick a 9V battery in there and call it a day. This is sorta phoning it in, but since the ICSP header breaks out the 5V bus, I figure I can always solder in a USB cable and power it from a wall wart if I have to.

Putting it together

I sent the Gerber files off to Seeed Studio’s FusionPCB service for production. About a month later, the boards turned up, and I couldn’t wait to assemble them.

2013-09-11 18.55.49

When reading about other folks’ LED matrix projects online, a common complaint was that it was difficult to get all the SMD LEDs aligned properly without some sort of jig. I didn’t want to mess around with creating a special fab tool, so instead I made the conscious choice to go with solder paste and hot air reflow. The idea was that I’d get the automatic alignment effect that solder paste + hot air exhibits.

Here, I made a miscalculation. Instead of making a solder paste stencil and applying it with a putty knife (which I’ve done before!), I decided to just dispense the paste directly from the syringe. This was a disaster. The paste I have has gotten kind of old, making it less apt to flow out the tiny syringe tips I have. Plus, I somehow lost the plunger that came with the paste, and was stuck using a Sharpie marker as a makeshift plunger. Not what I would call ergonomic. Still, this might have been OK for a few tens of pads… but I was applying paste to both sides of 125 LEDs! It took well over an hour, and by the end, I was in a lot of pain and didn’t have the patience to do it correctly. Consequently, a lot of the later LEDs got a huge glop of paste that sometimes bridged their pads and was just generally poorly done.

Populating the board was painstaking, but nowhere near as difficult as the pasting. When it was done, I fired up my trusty heat gun to reflow the board. About 85% of the LEDs did exactly what I was hoping for and sucked themselves right into place, but the rest pulled away from their pads, tombstoned, or clearly bridged under. I ended up spending another hour or so just going through and doing rework on the bad LEDs.


With the matrix side behind me, I turned my attention to the back of the board. At this point I was pretty done with solder paste, so I switched over to the iron. First up was the microcontroller. I used the “flow and wick” technique, which worked like a charm – after I refreshed my memory from this excellent SparkFun tutorial. (Heres a better video that illustrates the technique more closely.) The rest of the components were no problem – I just tinned the pads, positioned the components with tweezers, and then reflowed the pads until the pieces stuck. The one exception here was the crystal, which doesn’t have any exposed leads. For this guy, I just tinned the pads, then positioned the crystal and hit it with the hot air gun. I was relieved when I saw the crystal shift and adjust itself into place. Phew.


Turning it on

With the board fully populated, it was time to turn it on. It’s always scary to do the first power on test of a new project, particularly one where it’s impossible to do incremental tests. I flashed a spare Arduino with with ArduinoISP sketch, hooked it up to the programming header, and proceeded to burn a bootloader. Astoundingly, it worked the first time!

Next, it was time to test the matrix itself. I had already developed a Charlieplex matrix driver during my minimal prototyping stage, but the new board was really different and needed a new driver. But before I dove into porting the complex logic onto the new board, I wrote a trivial sketch that just exercised all the LEDs in sequence by manually toggling the pin pairs according to the scheme described above.

Guess what? It didn’t work. At least, not all of it. There were numerous spots in the matrix where LEDs were skipped, and a few spots where instead of a single LED lighting, multiple LEDs would glow dimly. It turns out there were a few problems here. The first was that my test sketch accidentally referenced the same pin twice, making it do a weird rewind-stutter thing during the test sweep. That one took an embarrassingly long time to find. With that software error out of the way, I proceeded from one LED to the next, debugging each misbehaving one. A few of the LEDs were in backwards – a population error. Some just seemed to be busted, and worked after replacing with a spare. Whether they came off the reel that way or were damaged during reflow, who knows.

By the end of the night, I was done debugging and all the LEDs worked as expected. Hooray! No disastrous issues! Now, I could finally start on the actual production sketch.

Cellular Chronometer Part 1: Reversing the Game of Life

I’m designing an LED matrix clock that plays Conway’s Game of Life to evolve a representation of the current time. See the whole series of blog posts about the project here.

The very first step of making the Cellular Chronometer is figuring out how I’m going to make the clock display the time. As a quick refresher, Conway’s Game of Life is what’s called a “cellular automaton“, which is a set of simple rules that’s played over a grid of cells, each of which are alive or dead. You process the grid with the rules and get a new grid with a different set of cells. Cellular automata are interesting because simple starting configurations can lead to really wild phenomena like self-replicating patterns and apparent movement.

But what I want to do is be able to get the game to display specific states. I want to populate the grid with a state that I know will evolve into a digital display of the current minute. The only reasonable way I could think to do this is to craft my desired state in advance and then do a search backwards – that is, in the reverse direction of the regular Game of Life – to find prior states. This happens to be a nontrivial problem. Played forwards, the Game of Life has very simple deterministic rules, but played backwards, there are an immense number of possible configurations to examine. In computer science terms, this problem is bounded by 2^n, where n is the number of cells in the grid. 2^n gets really big really fast. Not good.

Luckily, like so many other aspects of the Game of Life, work has been done trying to efficiently search for prior game states. I figured this out after two weeks of fruitless genetic algorithms experiments when a desperate Google search led me here. While the code didn’t prove useful to me, I managed to suss out that there are several existing algorithms that do what I need. The one that I best understood is called Duparc’s Method. The key win is that instead of being 2^n in the size of the pattern, Duparc’s method is only 2^n in the height of the grid! Since my grid is only five cells tall, this makes the search into a tractable problem, even if it does turn my MacBook into a proper lap-roaster.

duparc_illustrationIt’s hard to be 100% sure if I took the same approach as Duparc, since his original research paper is written in French. The way my algorithm works is to divide the grid in half vertically again and again until I’m working with single columns, at which point I essentially rotate the column into a row apply the same subdivision algorithm again until I reach a single cell. Single cells – both alive and dead – have a nice, cacheable method for determining all their prior states. Once I have the partial answers for a single cell, I intersect them with the answers from the neighboring cell by checking the overlap between the two. If the cells shared by the two possible solutions match, then the combined solution is also viable. Partial solutions that don’t match neighbors are discarded. This same process of merging based on overlapping cells continues back up the search tree until we reach the root, at which point we have a set of possible prior generations.

Something that took me a long time to grasp fully is that the algorithm naturally has to search in a grid bigger than the one you’re starting with. The reason for this is that while true “gardens of eden” are extremely rare, if you constrain the grid to a finite number of cells, it’s not at all hard to come up with a pattern that isn’t produceable. I ultimately came up with this sort-of logical proof to convince myself on this one:

  • In a grid of N cells, there are 2^N unique configurations
  • Some of these 2^N configurations will lead to non-unique next generations (ie, all cells dead is pretty common)
  • Therefore, it cannot be possible to generate each of the 2^N initial configurations from one of the other initial configurations.

In practice, this just means that you have to allow a “gutter” of arbitrary-valued cells around your desired image. If it’s really important to trim the excess, you just select ultimate solutions that have the extra cells as dead, since that’s the same as the border on a finite grid. The risk is that you’ll filter all the possible solutions by doing so.

As I developed this algorithm, I found that the line between “ever finishes” and “never finishes” was very fine. Most of the problems stemmed from running out of memory on my 16GB MacBook. A given target grid can have millions of intermediate states, and they need to be cached to make the algorithm run in a reasonable amount of time. The tweak that I credit with getting me all the way over the line was to discard many of the intermediate answers that, while actually unique, had the same border regions as other answers. Since the merging algorithm examines only the region of overlap between two sets of sub-solutions, any non-overlapping sections don’t actually increase your chance of finding some solution, and as such they can be discarded. This does mean that not all prior states are found, but for my purposes, I only need one.

Screen Shot 2013-09-01 at 8.57.39 PM

Along with improving the algorithm, I found that I had to tweak my font. Early on I guessed that different fonts and digit spacings would have an effect on whether a given configuration was reversible. I was surprised by how many of the configurations I wanted to generate were impossible with the grid dimensions I was enforcing. I had the algorithm report a bunch of statistics while searching so that I could see (at an aggregate level) when all possible solutions were being eliminated. I learned that particular characters were difficult to reverse, like 4s, 5s, and 0s. But the one that most surprised me was the colon I added between the hours and minutes. That guy turned out to be stubborn in some of the worst cases. In the end, I had to compromise and hand-edit certain minutes so that they would reach a prior generation.

The end result of all this hard work is 720 unique start states that will each evolve into one of the minutes of the 12-hour day. I’ll embed these states directly into the firmware for the clock so that my tiny microcontroller won’t have to do any “real” work, just run the Game of Life from each start state and advance the pointer every minute.

You can find the Ruby code for this crazy search in my GitHub repo.

The Cellular Chronometer

Making a clock seems to be a rite of passage for hobby electronics folks. The appeal is pretty obvious: straightforward functionality built with common components, and when you’re done, you have something that you can actually use in your daily life.

A little over a month ago, I had the idea for a clock project. But my clock is going to be a bit unusual. I’m designing an LED matrix clock that shows the current time by playing a different instance of Conway’s Game of Life every minute that evolves into the digital representation of the current minute. I’m going to call it the Cellular Chronometer.

This project concept hits the sweet spot for me in a number of ways. First and foremost, the challenge of making the Game of Life do my bidding is exactly the kind of deep, interesting algorithmic problem I love to tackle. I get to use all of my optimization and analysis skills to get a pretty cool result. Second, I am a sucker for designs that make use of cleverness to get a lot out of a little, so naturally I’ve been dying for a reason to build a Charlieplex, and this is the perfect opportunity. Finally, since this is something I want to actually put on display somewhere in my home or office, there’s a nice industrial design aspect to it. I want it to look well-made and polished when it’s finished.

Making an LED matrix should be pretty straightforward, as should be the “clock” behavior. I’m most familiar with Atmel microntrollers and the Arduino environment, so I’m going to use that for all the coding. Playing the Game of Life on a microcontroller is nothing new, but it’s probably impossible to search for prior game states on something with so little memory, so I’m planning to use my laptop to pre-compute all of the starting states that lead to my desired end states. And finally, I’m thinking that I’ll do the enclosure out of wood (either laser-cut or CNC-milled) so that I can finish it handsomely.

There are a lot of individual steps to this project, and I’m going to try to document them individually as I work through the project. Stay tuned for updates!