Implementing the chirp protocol using WebAudio

Yesterday I went to check out chirp.io to see if they had any news on their API. Chirp is an app/protocol to transmit small bits of data using sound. It works remarkably well, and is as easy and magical to use as Bu.mp, with much simpler technology underneath.

Chirp.io homepage

Seeing that they still don't have an API, I decided to find out how hard it was to generate a chirp myself. Fortunately they have a detailed enough description of their protocol at chirp.io/tech/.

So here is how you can reverse-engineer (not quite) a chirp.

The protocol

The chirp protocol is very simple. A message consists of 20 characters: 2 for a "front door" code (a chirp identifier), 10 characters of actual payload, plus 8 characters or error-correction codes. The character table has 32 entries, from 0-9 to a-v.

First thing was to figure out all the frequencies. Each character corresponds to a note/frequency, separated by a semitone, that go from 1760Hz (A6) to 10548Hz (E9). You can see a chart with notes and corresponding frequencies here.

A semitone is defined by s = 1.05946311. This results in an exponential distribution of frequencies. To go up a semitone you multiply the previous frequency by s, or do Math.pow(s, n_semitones).

With that in mind, we can generate a map of the corresponding tones:

semitone      = 1.05946311
baseFrequency = 1760

characters = '0123456789abcdefghijklmnopqrstuv'

freqCodes = {}
frequencies = []

# Generate the frequencies that correspond to each code point.
for char, i in characters
    freq = +(baseFrequency * Math.pow semitone, i).toFixed 3
    freqCodes[char] = freq
    frequencies[i] = freq

###
    0: 1760
    1: 1864.655
    2: 1975.533
    3: 2093.005
    4: 2217.461
    5: ...
###

These frequencies do not match exactly to the chart, I'm not sure if due to floating point errors or bad charts, but they are close enough. For better precision just create a map of the values.

Audio generation

To generate the audio, we're just going to use a simple oscillator pumping out sine waves. The official chirps have a bit more going on that makes them sound more pleasant and bird-like, but this doesn't seem to be necessary for the transmission to work.

First, create a new AudioContext:

context = new AudioContext()

Then an oscillator and a gain node:

oscillator = context.createOscillator()
oscillator.type = 0 # sine wave

gainNode = context.createGainNode()
gainNode.gain.value = 0.5

And finally connect everything:

oscillator.connect gainNode
gainNode.connect context.destination

Now we have our audio pipeline setup. If you call oscillator.start(0) you should get a steady 440Hz tone.

A naive approach to playing out the tones would be trying to change the oscillator.frequency value on the fly, maybe like this:

i = 0
chirp = do ->
    oscillator.frequency.value = frequencies[i]
    return if ++i > frequencies.length
    setTimeout chirp, 100

But that will actually generate a sweeping tone - the oscillator has a default ramp value that you can't change. What you can do is pre-program it using the AudioParam interface; it's the standard way to automate parameters in WebAudio. For simplicity we can use the setValueAtTime method, which sets a parameter to an exact value at a defined point in time.

Assuming chirp contains the 20-char long string to be transmitted, we can loop over the characters and define the 20 tone sequence:

for char, i in chirp
    oscillator.frequency.setValueAtTime freqCodes[char], beepLength / 1000 * i

And stop the oscillator after the full chirp length, otherwise it keeps going with the last frequency:

oscillator.stop beepLength / 1000 * (chirp.length + 1)

Payload

In theory the 10-character payload could be anything (within the provided table), providing up to 50 bits. The Chirp app just generates a unique ID, which points to the actual resource online. Even if you increase the chirp length by orders of magnitude you're still not going to get enough bandwith to send pictures over soundwaves :(

The final 8 characters of error-correction are generated by a Reed-Solomon algorithm. It's the same error-correction used in CDs, DVDs, barcodes, satellites and space probes. That means it is complex enough that there are very few implementations around, none of them in javascript.

The RS scheme depends on something called a Galois Field. According to my very limited math exploration, these are fields that have the curious and useful property that every operation between two elements results in a value that is also an element of the field. They come in powers of two; probably the reason why the Chirp guys chose a table size 32 - 16 is too low density, 256 would result in notes way too close for reliable detection.

Most implementations of these work with 8-bit symbols, using a GF(28), but we need a GF(25). I found a python implementation of Reed-Solomon, but failed to convert it to 5-bit space. An easier way might be to compile a C implementation using Emscripten to run in the browser.

For now, we can simply grab a ready-made chirp code for testing. This is what one looks like:

A chirp's spectrum

Since I didn't have time to write a pitch-detector + decoder (maybe tomorrow before breakfast?) I used a slightly low-tech approach to decode a message from this blog post:

Decoding a chirp

The code is hjsrg00lgbif4c6u07sq. It can error-correct up to 5 characters, so feel free to experiment with it - for instance hjsrg00lgbif4c600000 seems to work fine in a low noise environment.

So now we just need to feed that code and set the frequencies in the oscillator. Here is the working chirp player using the WebAudio API - open the Chirp app on your phone and press the yellow button:

And the original audio for comparison:

If you have any suggestions on how to implement the error correction, I'd love to hear them. Goals for the future:

  • implement Reed-Solomon error-correcting codes in javascript
  • detector + decoder (wireless p2p data using open web APIs!)
  • get closer to chirp's sound signature

And don't forget to check out chirp.io!

Follow me on twitter.