An Ergodic Walk

I saw on the ArXiV earlier this month a paper on interstellar communication by Berkeley’s own David Messerschmitt. I only met him once, really, at my prelim exam oh so many years ago, but I figured I would give it a read. And here you thought spread spectrum was dead…

Prof. Messerschmitt proposes using spread-spectrum because of its combination of interference robustness and detectability. The fundamental assumption is that the receiver doesn’t know too much about the modulation strategy of the transmitter (this is a case of stochastic encoding but deterministic decoding). The choice of wide-band signaling is novel — SETI-related projects have looked for narrowband signals. The bulk of the paper is on what to do at the transmitter:

The focus of this paper is on the choice of a transmitted signal, which directly parallels the receiver’s challenge of anticipating what type of signal to expect. In this we take the perspective of a transmitter designer, because in the absence of explicit coordination it is the transmitter, and the transmitter alone, that chooses the signal. This is significant be- cause the transmitter designer possesses far less information about the receiver’s environment than the receiver designer, due to both distance (tens to hundreds of light-years) and speed-of-light delay (tens to hundreds of years). While the receiver design can and should take into account all relevant characteristics of its local environs and available resources and technology, in terms of the narrower issue of what type of signal to expect the receiver designer must rely exclusively on the perspective of the transmitter designer.

The rest of the paper centers on designing the coding scheme which is robust to any kind of radio-frequency interference (RFI), without assuming any knowledge at the decoder — specific knowledge of the RFI (say, a statistical description) can only enhance detection, but the goal is to be robust against the modeling issues. To get this robustness, he spends a fair bit of time is spent developing isotropic models for noise and coding (which should be familiar to information theorists of a Gaussian disposition) and then reduces the problem to looking for appropriate time and bandwidth parameters.

This is definitely more of a “communication theory” paper, but I think some of the argument could be made clearer by appeals to some things that are known in information theory. In particular, this communication problem is like coding over an AVC; the connection between spread-spectrum techniques and AVCs has been made before by Hughes and Thomas. However, translating Shannon-theoretic ideas from AVCs to concrete modulation schemes is a bit messy, and some kind of translation is needed. This paper doesn’t quite “translate” but it does bring up an interesting communication scenario : what happens when the decoder only has a vague sense of your coding scheme?