A Digital Chronometer

Math and the Internet is a summer course for advanced high school students. It is part of the Michigan Math and Science Scholars program, which is sponsored by several departments at the University of Michigan. The course lasts for two weeks, and we have class for 6 hours a day. It was originally developed by Jason Howald and Mark Conger, and in 2010 the instructors were Mark Conger (that's me), Sunny Fawcett, and Shashir Reddy.

We covered a number of topics, including error correcting codes, Google's Page Rank, several data compression algorithms (which led to discussions of fractals and Fourier series), and cryptography, which culminated when we learned the RSA public-key encryption algorithm and exchanged messages with another class doing the same thing. Pictures from all 10 days were posted for the parents and anyone else to look at.

We also spent 2½ days working on understanding computer hardware, from the bottom up. That means we started with transistors, Then we built logic gates, then we built NAND Latches to see how memory works, then we convinced ourselves that we could use our latches to build Flip-Flops. At each stage we took the attitude that if we'd built it, it was fair game to use a chip that someone else had built to do the same thing. So eventually we used 74LS00 (nand), 02 (nor), 04 (not), 08 (and), 32 (or), and 86 (xor) ICs for our logic gates, and 74LS74 ICs for flip-flops.

Pictures of our hardware exploits are available here and here . We used breadboards, power suppies, and workstations donated by Matt Smith of the UM Electrical Engineering and Computer Science Department. The reason EECS was willing to give them to us is that EECS students design all their circuits in an online simulator these days, and don't ever build with wires. Matt thinks this is a shame.

On the second day we learned how to make memory and then set an ambitious goal for ourselves: build a 24-hour digital chronometer by lunchtime of the next day. (We used the word "chronometer" because "clock" has a technical meaning—see below.)

The specifications were for 6 digits, H10 (the tens digit of the hour), H1 (the ones digit of the hour), M10, M1, S10, and S1, two each for hours, minutes, and seconds. We had purchased 6 large 7- segment LEDs from Jameco. Each digit required three parts to make it work:

  1. A 2, 3, or 4-bit register to hold the current value of the digit, in binary. Its value should increase by 1 whenever the previous digit is rolling over to 0.
  2. A set of logic gates which decide whether each segment of the LED should be lit or not, based on the value of the register.
  3. A set of relays, one for each segment, which allow our 5-volt logic gates to control the 14 volts needed by the LEDs.

S1, M1, and H1 need to hold values from 0 to 9, and pass from 9 to 0. S10 and M10 hold values from 0 to 5, and pass from 5 to 0. Finally, H10 holds values from 0 to 2, and passes from 2 to 0. There's also the added problem that H1 needs to pass from 3 to 0 if H10 is 2. That is, the next hour after 23 is 00.

Parts of the Job

We split the job into tasks, and everyone took on a task.


How Memory Works

A flip-flop represents one bit of memory. That is, it contains a wire which is either at +5V or +0V. It's useful sometimes to call +5V "true" or "1", and to call +0V "false" or "0". This wire is memory in the sense that we can set it to a particular value, and then read that value later.

Well, that doesn't seem so impressive; after all, you can set a wire to a given voltage just by attaching it to either +5V or +0V. What makes the flip-flop so useful, though, is that there's a time delay between reading it and writing it. Here's how it works:

So Q is like "the president" and D is "the president elect". When the clock ticks, the president elect is promoted. This timing mechanism turns out to be the key to making a computer, because it allows things to happen is a proscribed order, rather than all at once. In other words, you can write computer programs which do one thing, then stop and think before deciding what to do next.

How to Connect the Counting Registers

Our registers need to count from 0 to some maximum value, and then roll back to 0 again. But most don't increment each second. S1 does, but S10 increments every 10 seconds, M1 evey minute, M10 every 10 minutes, H1 every hour, and H10 every 10 hours. So each register needs to be told when it's time to increment. Therefore it needs an input wire, which we'll called INC, which is 1 if the register should increment the next time the clock ticks, and 0 if it should not. INC(S1) can be wired to a switch, and then we can start and stop the clock with the switch.

But what about the other INC's? How do we decide when to tell, say, S10 to increment? Well, it should only increment when S1 is changing from 9 to 0. That is, when S1 is "overflowing": being asked to increment when it's already at its maximum value. Likewise, M1 should increment when S10 is overflowing, M10 when M1 is overflowing, etc. So each digit should have an output, OVR, which will be attached to the INC of the next digit.

Building a Counting Register

We need one flip-flop for each bit our register will have. Let's say we're making S1. It needs to hold values from 0 to 9, so it requires 4 bits, which is to say, 4 flip-flops. Call the bits Q0, Q1, Q2, and Q3 in order from least significant to most significant. We use Q to remind us of how the flip-flop works. Then incrementing is like adding INC to the number Q3Q2Q1Q0. That is, doing the addition problem

where the C's are the carry bits (just like the way we all learned to do addition in 2nd or 3rd grade). So R0 is the sum (mod 2) of INC and Q0, which is to say, R0 = INC xor Q0. Likewise, R1 = C1 xor Q1, and so on. We'll need to carry to the 2's column only if the sum in the ones column is at least 2, which only happens if INC and Q0 are both 1. So C1 = INC and Q0. Similarly C2 = C1 and Q1, and so on. In fact, if we accept C0 as an alternate name for INC, we can summarize the rules as

Rk = Ck xor Qk
Ck+1 = Ck and Qk

So what should we do with the R's? Well, they should be the next values of the register, so we should send them to the D pins on the flip-flops, of course. Well, almost. We want to do that unless the register is about to overflow, in which case the D's should be set to 0. So here on the left is a proposed scheme for the counting part of the register. UND = not OVR.

The rest of the register needs to compute OVR and UND, the former for output to the next digit, and the latter for use by the counting part. This part will be different for each digit, since their max values are different. For S1, the max is 9, so this scheme will do:

The final challenge is, of course, to build that using ICs. Here is one built by Jeff Walker, Nicholas Zajciw, Effie Landau, and Aaron Fein. (They didn't have the benefit of the labels on the chips; I only thought to stick those on later.) If you look closely you can see that three of the flip-flops are being used, so this is a 0-5 register.

LED Logic

The second part of a digit is the logic which takes the register bits (which describe the value of the digit in binary) as input and for output produce a 0 or a 1 for each of the 7 segments of the LEDs. For technical reasons, in this case, 0 means "on" and 1 means "off".

For example, consider the top right segment. It should be on for most digits—in fact, for all of the digits 0-9 except 5 and 6. So here's a truth table connecting register bits to that segment:

Segment Relays

Each LED segment contains 5 LEDs, and the voltage drop across each is about 1.6 volts. They're wired in series, so the total drop is about 8 volts, which is too much for our 5-volt logic circuits to power directly. The recommended current is 30 mA.

We borrowed a 14-volt power supply from writer, electrical engineer, ham radio operator, and friend of the class Dan Romanchik. Dan and I struggled for most of an evening to find a good way to control the LEDs, and finally settled on using a relay for each segment. So the basic setup is this:

We actually ended up using 220 ohm resistors instead of 200, which makes the current

I = (14V − 5×1.6V) / 220 Ω = 27 mA

which is close enough to the target of 30. The task of setting up the relays required care but not ingenuity, so in the interest of time, Sunny, Shashir and I did the wiring. A typical setup for 7 segments plus the decimal point looked like this:

The one blue resistor in the picture is 1000Ω, and it's for the decimal point, which only has 1 LED. The pins of the LEDs are off the bottom of the picture, and the cluster of wires in the SE corner shows where the logic wires plug in.

Putting it Together: the Climax

We worked on the digits all day Thursday 7/15. That evening Shashir and Sunny and I installed the relays, and tested to make sure we had enough power to run all the LEDs at once. The logic for one of them, H10, which goes from 0 to 2, was completely working. It was built by Michael Lacy and Brian Chantrupon, and it's the "2" in the upper left corner of the picture.

The next morning we marshalled on. I had announced to all the other instructors, and to the students, that we would have a show at noon to display our accomplishments. So the pressure was on.

As any engineer knows, the last 10% of a project takes 50% of the effort. In other words, after you've done the part of the project that you planned for, you always run into unexpected problems at the end. In our case we had problems debugging the registers; one wire which is off by one row can mess the whole thing up. Some of our registers incremented in funny sequences, like 1-3-4-0. With 20-20 hindsight, it would be a good idea to keep careful track of each wire that's plugged in. That is, maintain a document that maps row numbers on the breadboard to quantities on the logic diagram. We'll do that next year.

Two registers that did work perfectly were the 0-9 registers built by Pratheek Nagaraj and Jessica Li. We transported everything down to the math atrium and set it up for visitors to see, and at its peak we had a clock that counted from 00 to 99. It was pretty cool. The video above starts with a demo of the 0-9 digits, then shows the clock counting. Pratheek demonstates how to speed it up and stop it, and then there's a picture of (almost) all of us together.


Flash forward now to Monday 7/26, after camp was over, all the students had gone home, and we'd all gotten some sleep. Sunny and I had a meeting to talk about how everything went, and then our plan was to start cleaning up. But when we came to the subject of taking apart the students' work to box the parts up for next year, we just couldn't do it. One of us suggested that instead we try to get the whole clock working, all 6 digits. The other readily agreed, and when Shashir showed up a little later he signed on to the plan immediately.

So we began to assess what we had. A few things had been cannibalized on the last day of class, when we sent students home, so some forensics was needed to figure out what was missing. In general, though, we found that the students were very close to having the whole thing working. A wire here and a wire there, and the registers and LED logic they had built were ready to go.

Shashir built a couple of LED logic sets that we hadn't gotten to, and I built a 0-9 register and debugged one of the 0-5 registers. Sunny debugged the other registers, and Shashir copied my 0-9. (One of the 0-9 registers had unfortunately suffered the most cannibalization, and proved difficult to fix.) Sunny also built logic to deal with the problem of the hours rolling over from 23 to 00. That one is left to the reader to figure out. Hint: you need an or gate.

We set up all six digits in my office and wired them together:

We had some trouble with the clock at first; some digits seemed to pause or change too often. We tried the clocks on a number of different workstations until we got one that worked. (Probably the problem was our wiring. It's important that the clock signal not "bounce", that is, the change from +0V to +5V and back again needs to be clean, with no noise or backtracking. My bet is that we had some noise somewhere.)

Eventually, though, it all worked! It's best to watch it with the lights off. For fun we wired the OVR bits to the decimal points on the LEDs. So you can see when they're about to roll over.

It was a lot of fun, and I'm really glad to have seen it all work. I hope our students didn't mind that we worked on their creations. I should say again: they were very close to working already, and we just put them together.