How to decode a message with unknown bit rate in interstellar signal

Question

I have a question about FSK modulation I'm going to frame in terms of a hypothetical:

Imagine that you are transmitting a message to an ET in another solar system. The message is encoded in binary and embedded in the radio signal using FSK modulation. Lets say the signal is broadcast at 5 GHz and FSK +50kHz (i.e. 0 = 5,000,000 kHz and 1 = 5,000,050 kHz). Finally let's say you want to broadcast @ 1 bit per second.

Now lets say the message you send is "1111111111" (10 ones).

Would the ET recipient of this message be able to decode it without knowing the bit rate?

My argument would be no, since to the ET it would just look like an unmodulated signal at 5000050 kHz that lasts for 10 seconds. If the ET didn't know the bit rate, it would be impossible for it to determine whether there was 100 ones or 10 ones encoded in the signal unless some zeroes were present as well. Is this correct? Would the presence of zeroes in the message even help determine the bit rate?

Answer 1

An FSK signal which is the same symbol repeated is an unmodulated carrier, and like an unmodulated carrier, it contains no information. Making some assumptions about the bit shaping filter it might be possible to make a reasonable estimate of the symbol rate judging by the growth and decay of the envelope at the start and end of the transmission, but it's an exercise of little practical value.

A real signal with information in it will have bits that are unpredictable. Consider: when we want to make information as compact as possible, we compress it. And a compressed file is nearly random bits. For related reasons, random bits can't be compressed.

This means in a transmission with information in it, it's extremely unlikely to have a repetition pattern which makes the symbol rate ambiguous. As such, the symbol rate will not be difficult to estimate for example by Fourier analysis: the highest frequency in the baseband signal is likely the symbol rate. Once the symbol rate is approximately known, a clock recovery algorithm can be applied to synchronize to the clock more precisely.

Real-world applications use techniques such as bit stuffing to ensure there are some transitions to facilitate clock recovery even when the data to encode is a long repetition. However in the realm of interstellar communication it's likely your objective is exchange of information, not sending a copy of the empty space of an unused hard drive. As such you're not likely to require bit stuffing: it would only make decoding more difficult.

Answer 2

You are correct that you need to solve this problem somehow. Here are two ways to do it for normal practice:

• Put a known symbol sequence at the beginning of your transmissions, which allows the receiver to detect the rate of symbol transitions and synchronize to it. This is called a preamble or syncword, among other names.

  A long message can be broken up into packets, repeating the preamble for each.

• Arrange so that you are never sending a long sequence of only one symbol, but always have some transitions. This can be bit stuffing or other schemes.

(Explaining symbols: if you are sending one bit at a time you have two symbols; if you send two bits at once by sending one of four different frequencies, that's four symbols, and so on.)

For a receiver who doesn't know the parameters of the transmission or how it is encoded, there is no way they can tell "symbol rate is 1 symbol per second" from "symbol rate is 2 symbols per second, but all the symbols we've seen so far happen to be paired up (like 0011000011001111)". They can only presume that you're not using a wasteful encoding, and decode using the shortest symbol time they've seen.

For example in the specific ET communication problem, you could send the integers in unary (or the Fibonacci sequence or your choice of Obvious Simple Mathematical Thing) and use that as your preamble and also "there is intelligence here" signal.

010110111011110111110111111011111110...

In this case, every 0 symbol demonstrates the shortest symbol time, and it's easy to note that the 111... increases by the length of a 0 each time. If you recorded that as an unknown signal, you would quite readily notice the timing, yes? And algorithms can do even better.