brainwagon

I was interested in WSPR and visual MEPT oeprations for quite some time. I operated both a beacon and a QRSS aggregator on 30m for a while, but I grew a bit tired of it, and it’s been silent for a year or so. But I haven’t stopped thinking about them. In fact, I’ve had an idea percolating in the back of my head since last year, when I became aware of the work of Leemon Baird and William Bahn on Jam Resistant codes.

But I’m getting ahead of myself. Here are some of what I think could be improved with WSPR:

1. WSPR requires accurate clocks both for receiving and transmitting. To be successfully decoded, transmissions must start within a window just a few seconds long surrounding even numbered minutes. This makes both sending and receiving systems complicated: they probably need to access an external reference (NTP, GPS or WWV) to operate reliably over an extended period.
2. Fixed frequency operation can cause collisions. Each transmitter selects a fixed transmit frequency, and relies on multiplexing over time to avoid collisions. WSPR software itself provides no real help in selection of an appropriate free frequency.
3. The choice of a convolutional code is somewhat odd. The payload is only 50 bits long, but we pad the results with 31 zeros to flush out the convolutional coder. Thus, we are actually getting the error correction of a rate 1/2 code, but we are only sending as much data as if we were sending a rate 1/3 code.

I had been pondering some of these issues, when I became aware of the work of Baird and Bahn. They are researchers for the Air Force Academy, and were particularly studying the problem of providing jam proof communications without the need for shared secrets. Briefly, you can imagine using spread spectrum to provide a measure of jam proofing: because the data is spread out among many frequencies over time, the spread spectrum signal has a good measure of jam proofing: the jammer needs to put energy over most of the frequency most of the time, where as the transmitter can put his full power on just one frequency at a time (other variants of spread spectrum are a bit different, but the principle holds). The only way a jammer can work efficiently is by knowing the sequence, which is usually a cryptographic secret.

This is where Baird, Bahn, and Collins’ work comes in: In their paper:

Baird, Leemon C. III, Bahn, William L. & Collins, Michael D. (2007) Jam-Resistant Communication Without Shared Secrets Through the Use of Concurrent Codes, Technical Report, U. S. Air Force Academy, USAFA-TR-2007-01, Feb 14.

they show a simple technique that can be used to transmit signals with high reliability and a high degree of jam resistance, without requiring any kind of shared secret or cryptography.

The idea is somewhat subtle, but reasonably straightforward. The idea is to create take the binary message (say, the same 50 bits that we use for WSPR). This message gets padded by a series of zeros (maybe lots of them, perhaps a multiple of the original message length). You then need a hash function (some details matter, but you can think of using a standard one like MD5 or one of the SHA variants if you like). Now, for each prefix of the message (bit streams of length one, then two, then three, and so on), you compute the hash of that prefix. Let’s say that you are going to transmit the message by sending short, powerful bursts of energy at particular times in particular window. (You can imagine this being the two minute window used to transmit WSPR to make it more practical). If we divide that into (say) 8192 slots, then we could take each hash, take the lower 13 bits, and use that to specify a particular time when that bit would get turned on. If we send 500 bits total (9 zero checksum bits) for every real one, we are sending about 500/8192 slots, or about 6% of the total. To mark the start and stop, let’s turn on the first and last bit. That’s pretty much the entire transmit side.

What’s cool is that you can decode the message on the remote side, and if you ignore efficiency, it isn’t even that hard. Let’s say that you located a stretch of bits 8190 long, between two on bits. That might be a message. So, how do you decode it? Well, the first bit might be a zero or a one. You basically pretend that you are transmitting, and encode both messages. That will return a location, which you check to see is on. If it isn’t, then you know that guess was wrong. If it is, then that hypothesis is good. It’s possible that none could be right. That means there is probably not a message in that span. It’s possible that one could be right, in which case you then add a zero, and then try adding an one, and seeing if the hypothesis still holds. There are times when both results will check out, but statistically it is unlikely. When you hit the “checksum bits”, you know that there is only one possibility: a zero. If the specified hash doesn’t yield a location that is turned on, you know that you are on the wrong track. (The overall algorithm reminds me somewhat of a Viterbi style decoder, although it is actually considerably simpler).

There are lots of details to make this efficient (you want a hash function which allows incremental updates as you add individual bits to the message) but it’s pretty straightforward.

Anyway, I think this could be the basis for a new highly-collision resistant beaconing protocol for amateur radio. It would enable very simple transmitters (a simple microcontroller could hold the sequence in internal EEPROM, no need for highly accurate clocks) and the system would be more highly jam resistant than the current system. We could use simple CW transmissions, or adapt to slower rates with more diverse frequency usage. And, the technology has been paid for by your tax dollars, so no pesky patent/IP issues would seem to apply.

What do people think? I’m interested in hearing some feedback from digitally minded radio amateurs.

Addendum: if my descriptionw as insufficient, try reading the papers (especially Visually Understanding Jam Resistant Communication) and/or posting some questions in the comments.