μWWVB: A Tiny WWVB Station

μWWVB is a watch stand that automatically sets the time on atomic wristwatches where regular WWVB signal isn’t available. The system acquires the correct time via GPS and sets radio-controlled clocks by emulating the amplitude-modulated WWVB time signal.

Background

Atomic Clocks

Most so-called atomic clocks aren’t true atomic clocks; rather, they are radio-controlled clocks that are synchronized to true atomic clocks. Radio clocks maintain time by using an internal quartz crystal oscillator and periodically synchronizing with an atomic clock radio signal. Quartz clocks have a fractional inaccuracy $\delta f / f \approx 6 \times 10^{-6}$, which means that they can gain or lose about 15 seconds every month. Official NIST US time is kept by an ensemble of cesium fountain atomic clocks — their newest clock, NIST-F2, has a fractional inaccuracy $% $, meaning that the clock would neither gain nor lose one second in about 300 million years.

Most radio-controlled clocks in the United States are synchronized to the WWVB radio station, which continuously broadcasts official NIST US time. WWVB broadcasts from Fort Collins, Colorado, using a two-transmitter system with an effective radiated power of 70 kW. Theoretically, during good atmospheric conditions, the signal should cover the continental United States. Unfortunately, I can’t get my wristwatch to receive the 60 kHz amplitude-modulated time signal in my dorm room in Cambridge, Massachusetts.

Getting Accurate Time

Taking into account frequency uncertainty, WWVB can provide time with an accuracy of about 100 microseconds. In the absence of WWVB, there are other sources that can provide reasonably accurate time. The Network Time Protocol (NTP), which operates over the Internet, can provide time with an accuracy of about 1 millisecond. GPS can theoretically provide time with an accuracy of tens of nanoseconds. I decided to use GPS, mostly because I didn’t want to make my WWVB emulator dependent on an Internet connection.

Legality

Building a WWVB emulator involves transmitting on 60 kHz. In general, it’s not legal to broadcast on arbitrary frequencies at an arbitrary transmit power, because transmissions cause interference. Many parts of the radio spectrum are already in use, as allocated by the Federal Communications Commission (FCC).

Luckily, the FCC grants exemptions for certain unlicensed transmissions, as specified by 47 CFR 15. This is explained in some detail in “Understanding the FCC Regulations for Low-Power Non-Licensed Transmitters”.

Transmitters in the 60 kHz band are allowed, and the emission limit at that frequency is given in 47 CFR 15.209. As long as the field strength is under $40 \text{ \muV/m}$ as measured at 300 meters, it’s fine. In my use case, I have the transmitter within a couple inches of the receiver in my wristwatch, so I don’t need to transmit at a high power.

Electronics

Board

I designed and fabricated a tiny custom board designed to interface with a GPS and an antenna:

The board is powered by a $1 ATtiny44A microcontroller. I used a 20 MHz external crystal oscillator for the microcontroller so I’d have a more accurate clock than I would with the internal RC oscillator. The board has a Mini-USB connector for power, an AVR ISP header for programming the microcontroller, and a JST-SH 6 pin connector for the GPS. I included pin headers for the antenna, making sure to connect them to a port that works with fast PWM. I also included 3 LEDs as status indicators — a red LED for power, a green LED to indicate a GPS lock, and a blue LED to show the unmodulated WWVB signal. I designed the board using the EAGLE PCB design software and milled the board from a single-sided FR-1 circuit board blank on an Othermill v2: Once the board was finished, I used solder paste and a hot air gun to solder my components. Hand soldering surface-mount components is pretty painful, but using solder paste, the entire soldering process took only ten minutes. GPS For my GPS module, I used a USGlobalSat EM-506, a high-sensitivity GPS powered by the SiRFstarIV chipset. Antenna The 60 kHz WWVB signal has a very long wavelength: $\lambda = c / f$, so the wavelength is approximately $(3 \times 10^8 \text{ m/s}) / 60 \text{ kHz} = 5000 \text{ m}$. It’s challenging to design good antennas for such long wavelengths — a quarter-wavelength antenna would be about 1250 meters long! WWVB uses a sophisticated antenna setup that’s automatically tuned using a computer to achieve an efficiency of about 70%. Luckily, for my use case, I didn’t need to worry about designing a really efficient antenna and doing careful impedance matching — I was transmitting over such a small distance that efficiency didn’t matter too much. I didn’t want to build my own antenna, so I gutted a radio clock and repurposed its ferrite core loopstick antenna. Thanks to antenna reciprocity, which says that the receive and transmit properties of an antenna are identical, I knew that this should work. Software I wrote software to periodically get accurate time via GPS and continuously rebroadcast the time following the WWVB protocol. The software is written in plain C and doesn’t use any libraries or anything. I used the CrossPack development environment on macOS for compiling my code and flashing my microcontroller. Getting the software to work just right took a good amount of effort. To make it easier, I initially designed each component separately, and still, I ended up spending a lot of time debugging: NMEA GPS Interface According to the datasheet, the EM-506 has a UART interface and supports both the SiRF Binary protocol and the NMEA protocol. NMEA 0183 is a standardized ASCII-based protocol, so I opted to use that over SiRF Binary. After implementing software UART on the ATtiny44A, getting time data from the GPS was as simple as sending over a command to query for the ZDA (date and time) NMEA message: $PSRF103,08,01,00,01*2D


In response, I’d get back a message with the current date and time (in UTC). For example, for 26 December 2016, 18:00:00, I’d get the following NMEA message1:

Algorithms in the Real World: Committee Assignment

I recently had another chance to use a fancy algorithm to solve a real-world problem. These opportunities don’t come up all that often, but when they do, it’s pretty exciting!

Every year, MIT HKN has a bunch of eligible students who need to be matched to committees. As part of the assignment process, the officers decide how many spots are available on each committee, and then we have every eligible rank the committees. In the past, officers matched people manually, looking at the data and trying to give each person one of their 1st or 2nd choices. Unfortunately, this is time-consuming and unlikely to result in an optimal assignment if we’re trying to maximize overall happiness.

Example

To see how assignments can be suboptimal, we can go through an example.

Committee Capacity
Tutoring 2
Outreach 1
Social 2
Person Tutoring Outreach Social
Alice 1 3 2
Bob 1 3 2
Charlie 1 2 3
Dave 2 1 3
Eve 2 1 3

In the above table, 1 means first choice, and 3 means third choice. We could imagine assigning people by going down the list and assigning each person to their highest-ranked committee that has available slots. This would result in assigning Alice to Tutoring (1st choice), Bob to Tutoring (1st choice), Charlie to Outreach (2nd choice), Dave to Social (3rd choice), and Eve to Social (3rd choice).

Not only is this algorithm unfair to the people at the bottom of the list, but it’s also suboptimal. If we want to minimize the sum of the rankings for committees we placed people on, we could go with Alice–Social, Bob–Social, Charlie–Tutoring, Dave–Outreach, Eve–Tutoring. This results in a “cost” of 8, which is optimal, rather than the cost of 10 we got with the first assignment, which was constructed greedily.

In the actual data set, there were 8 committees and 57 eligible members, so it wouldn’t have been feasible to manually find an optimal assignment.

Problem Statement

More formally: we have $k$ committees and $n$ people. Each committee $j$ has a capacity of $c_j$ people, where we’re guaranteed that $\sum_{j = 1}^{k} c_j = n$. We know people’s preferences, which for any given person $i$ is a permutation of the committees, $\sigma_i$, mapping the highest ranked committee to $1$ and the lowest-ranked committee to $k$. Our goal is to find an assignment $A$ of people to committees that solves the following optimization problem:

Above, $\delta$ is the Kronecker delta. Essentially, we want to find the assignment that minimizes cost while satisfying our constraints of having a specific number of people on each committee.

Algorithm

It turns out that the committee assignment problem can be transformed into an instance of the assignment problem (which can also be thought of as finding a minimum weight matching in a bipartite graph).

In the assignment problem, you have $n$ people, $n$ jobs, and a cost matrix $C$ where $C_{ij}$ is the cost of having person $i$ do job $j$, and you want to find the minimum cost assignment such that each person is assigned to a unique job.

The committee assignment problem can be trivially transformed into an instance of the assignment problem, simply by making $c_j$ copies of each committee $j$, counting each as a separate “job”, and constructing an appropriate cost matrix from the $\sigma_i$s.

Luckily, the assignment problem is well-studied in computer science, and there’s a known solution — the Hungarian algorithm solves this problem. There’s even an implementation of the algorithm built into SciPy. This makes solving the committee assignment problem really easy — it only requires a little bit of code to implement the transformation described above.

Results

Using this algorithmic approach to solve the committee assignment problem worked really well for us! We made some slight modifications to the process — one of the committees hand-picked their members, and then we used the algorithm on the remaining 52 members and 7 committees. When running the program, we decided to minimize the sum of the squares of the costs rather than minimizing just the sum.

With 52 people and 7 committees, our implementation ran in less than half a second and gave us an assignment with 37 people getting their first choice, 13 getting their second choice, and 2 getting their third choice.

Gavel: An Expo Judging System

Gavel is an automated end-to-end expo judging system. We’ve used it to automate judging at HackMIT, a 1000-person event with over 200 projects and 100 judges. Dozens of other events have also used Gavel since the software was released in private beta in late 2015.

Gavel fully automates expo judging logistics and project ranking — the system tells judges which projects to look at, collects judges’ votes, and produces a ranking of projects.

Here’s a demo of the judge interface:

Model

Gavel’s model is pretty different from traditional scoring methods — it’s based on the method of pairwise comparisons, and the system uses fancy math to come up with a ranking. For reasons described in detail in this post, pairwise comparisons work much better than having judges input scores from 1 to 10 or something like that.

History

The HackMIT team has used Gavel for four events now. We implemented the first prototype, a text message based system built on top of Twilio, at Blueprint in Spring 2015. In Fall 2015, we switched to a new algorithm and reimplemented the system as a web app for HackMIT. We continued to use that implementation for Blueprint in Spring 2016. For this year’s HackMIT, we completely redesigned the frontend and the admin panel of the application, changing basically everything except for the core algorithms. Now the system is a whole lot more user-friendly for both judges and event organizers.

Here’s what judging looked like at HackMIT this year:

Public Release

Using this system has made judging logistics super easy for us, and we believe that it has also led to higher-quality results. We thought that other events could benefit from using Gavel too, so we’re releasing the software to the public!

We’re releasing the latest version of the system, Gavel v1.0, which is what we used at HackMIT 2016. From this point on, Gavel will be developed as an open source project.