Worldbuilding Stack Exchange is a question and answer site for writers/artists using science, geography and culture to construct imaginary worlds and settings. It only takes a minute to sign up.
Sign up to join this community
What would be the most efficient text communication method for a spacecraft operating on a super low bit rate (I'm talking something like 5 bits an hour, excluding error handling)?
As you want both complexity (full English language and numbers) and speed (letters per day) resorting to something like Morse code seems the most obvious solution but is there any other options out there?
The most efficient communication is probably a command set. Since you contemplated Morse code, I assume that the communication is done via a fully defined interface - both sender and receiver know what a bit sequence is supposed to mean.
A command set is no more that giving different codes predefined meanings. With one singe bit you can define 2 commands:
| value | meaning |
| 0 | light off |
| 1 | light on |
With 4 bits you can define 15 different commands, with 1 byte (8 bits) 255 commands, with 2 bytes 65535 commands and so on. If all you really need is to display texts to an astronaut, you have to store a bunch of ready made texts like "Activate X-ray sensors" in a database and send the corresponding message ID from Earth. For more complex messages you can store text templates in a database and then compile a message from several templates.
An early real-world example is the list of Q-Codes, created circa 1909, by the British government as a "list of abbreviations... prepared for the use of British ships and coast stations licensed by the Postmaster General".
If you need to communicate more than simple texts, you would separate a message into a command part and a message part. You could, for example, tell the space ship:
Activate X-ray sensors
By sending a signal of 2 bytes:
| byte | value | meaning |
| 1 | 01 | activate appliance |
| 2 | 08 | X-ray sensor array |
Communication with an astronaut would be possible with a different command:
| byte | value | meaning |
| 1 | 04 | write to terminal |
| 2 | 08 | text with ID 8 |
That would result in slightly longer commands, but the possibilities of what you can achieve with a few bytes are multiplied.
If you have a really big database with a whole lot of different texts, it might be more efficient to terminate commands with a defined code. For this approach, the database must be sorted in a way that gives the most frequent commands the lowest ID.
Let's define 0000 as the terminator.
0110 0000. 0110 1000 0011 1011 0000. The advantage is that you can have commands of dynamic lengths (instead of sending a whole bunch of useless 0's to fill up the static length of a command).
The disadvantage is that every command is longer than it could ideally be. So this approach only gets worthwhile when you need a great many commands.
After defining your command set, the next step is to make sure that you received the correct message. Losing just a single bit can change a message of "Activate X-ray sensors" into "Destroy X-ray sensors" or similar. This is usually done with a checksum, which requires some more bits to transmit.
Have a look at the difference between two common data transmission protocols for the internet: UDP and TCP. UDP is the most efficient in respect to transfer rate, but TCP trades some efficiency for reliability by including some overhead for error checking.
According to Schneier the entropy of English text is below 1.6 bit per letter. Given a difficult constraint such as yours I would expect people to come up with compression algorithms getting close to that.
If you don't need the full power of English you might get much better compression if you can pre-define a small set of words that would be sufficient. Something similar in principle to https://xkcd.com/1133/
I think you need to answer two important questions:
If you want something that is simple, sciency and requires no setup, go with Huffman-coding individual letters based on frequency in English. ;)
You might look at digital modes for amateur radio here. Some of those modes use what's called "varicode" -- where different characters have different symbol lengths (Morse code is a varicode system -- more commonly used letters are shorter in terms of transmission time). When sending English text, a varicode will minimize the number of bits required for a sufficiently large sample (which reasonably ought to include a large number of messages). If "text speak" is used commonly, it might make sense to design the varicode used around letter frequencies in that particular text format.
If longer messages are common, some form of compression would make sense -- text typically compresses will with common compression algorithms, but the compression headers make this inefficient for very small blocks of data (text or otherwise).
From Wikipedia:
International Morse code is composed of five elements:[1]
- short mark, dot or "dit" (▄▄▄▄): "dot duration" is one time unit long
- longer mark, dash or "dah" (▄▄▄▄▄▄): three time units long
- inter-element gap between the dots and dashes within a character: one dot duration or one unit long
- short gap (between letters): three time units long
- medium gap (between words): seven time units long
If we use one bit to store one unit of information, it takes four bits to transmit even the shortest letter ('e') and its subsequent gap. The next shortest are 'i' and 't' at six bits. Then 'a', 'n', and 's' at eight. The longest character in the Morse alphabet is 0, which requires five dashes or twenty-two units/bits. And that only supports the thirty-six character latin alphanumeric alphabet.
Morse is designed around humans. Humans do better with indeterminate length than fixed length, as we don't have good timing ability (we can't tell a five unit pause from a four unit pause consistently). But if these messages are being transmitted computer to computer, computers have great ability at timing. We can use superior fixed length formats. Heck, even with humans, twelve minute long units means that it is easy to track whether you're getting a pause or a dot (a zero or a one).
Even worse, if you are transmitting Morse over bits. Because (extended) ASCII's eight bits is more efficient unless the message is composed entirely of 'eitans'.
Meanwhile, if we transmit ASCII, we could transmit a 0 with eight bits. If we break things into nybbles, we can transmit one nybble with a checksum bit every hour. So two hours to transmit one character with some error detection included. Or ninety-six minutes without the checksums.
If we instead use ten bits (two hours), we can do something like Lempel-Ziv. So the first 256 characters are the extended ASCII set. The remaining 768 symbols actually represent multiple characters. So common sequences (e.g. "the ", "ing", and "tion") would have their own ten-bit representation, e.g. 0100000000. This allows the full flexibility of ASCII while also producing a shorter message on average.
The Lempel-Ziv algorithm builds the dictionary from the message itself. We can do better by agreeing on a dictionary beforehand. You can also use this to integrate the error correction and the dictionary, which improves your effective speed.
Numbers are generally going to be better sent as bits than as characters. I.e. instead of sending ASCII 3840, just send 111100000000. That's only twelve bits, hardly more than a single character.
Textspeak
SMS messages originally were 160 characters so textspeak evolved to reduce everything down to the most compact form through abbreviations, acronyms and emoticons.
Sounds like a good reason to send teenagers into space....
brb, afk or the glorious asl back before text messaging but SMS opened text communication to vastly more people and placed even more constraints, so the previous abbreviations were not only used, but new ones were introduced and some old stuff was refined even more due to the constraints. That's why it's called "textspeak" not "IRC speak" or "ICQ speak" or anything like that.
$\endgroup$
Basically, you want the same methodology we use today for writing to a .zip file. Basically what happens is we take the most common character in the file (probably 'e'), and say that it simply corresponds to the bit '1'. Then the next most common one ('a' maybe?) will be '01', and the next most common (let's say 't') will be '001'.
So, given this system, "eat" = "101001", while "tea" = "001101".
This is the most efficient form of encoding there is, as it gives you access to any number of characters while still using very few bits for the vast majority of the ones you're using.
Note though: this is most effective when some letters/characters are used far more than other ones (as it is in modern English).
Also, most .zip files will send along a "dictionary" of bit combinations and characters, so the other person can translate out of it. This can be wasteful to send every time, especially for short messages. However, if every user has a well-known dictionary that is encoded to best represent common English usages it can work.
A receiver will pick up the raido signal plus background noise (most notably cosmic background radiation). Generally the received noise power is greater for greater receiver bandwidth. So to get a good signal to noise ratio one can transmit the radio signal within a very narrow frequecy band and put a very narrow band filter on the front of the receiver.
EXAMPLE: The receiver was picking up 1 micro-watt of radio signal and 1 milli-watt of noise power with a 1MHz bandwidth (so a SNR of 0.001).
Droping the bandwith to 10Hz would result in 1 micro watt of radio signal power and 10 nano-watts of received noise power (so a SNR of 100)
Consider a protocol like PSK31 (or similar) used by HAM radios instead of moorse code.
PSK31 uses pure tones of relatively long duration to send 1s and 0s. The longer those tones are the more narrow the filter at the receiver can be. PSKxxx can be used to send low data rate messages across the plannet using only a few watts of power.
Another alternative (though more complex) is using long strings of physical 1s and 0s to represent a single symbol in the protocol. This method is used by GPS for example. The GPS signal is normally about 30X lower power than the background noise, but by correlating long strings of 1024 bits the receiver is able to on average lock onto the signal.
EXAMPLE: Define two long sequences of physical 1s and 0s for each letter of the alphabet. Each code is very different from the other codes.
Let A be 00101010 10001010 10100101 00101010 ...
Let B be 10100001 10100101 00010101 00010100 ...
Let C be 01001010 01010100 00010100 00110101 ...
The sequences may be thousands of bits long if you want. The patterns are generated by a computer automatically when the user types a letter on the keyboard.
The physical bit sequences are sent at a much higher rate than the actual symbols. For example if you want t send one symbol per second and your sequences are 1000 bits long then you send the physical bits at 1000 bits per second.
When receiving the signal + noise; the noise will cause the receiver to make the wrong decision on the physical 1s and 0s some percentage of the time. The receiver stores the received bit pattern and compares it to one of the codes. The receiver then selects the code which most closely matches the received pattern. Even if most of the received bits are wrong, the received code is likely to match most closely to the code sent by the transmitter rather than one of the other codes. Thus the receiver can determine what the transmitter sent even if the background noise is much higher than the received radio signal.
Some other advantages of using long codes is that the codes inherently correct physical bit errors at the receiver. Also different transmitters can each use different code sets so they can talk at the same time (this approach is how CDMA cell phones work).
In addition to the different encoding and compression methods, one thing to look into is shorthand techniques that allow you to drop letters while still being able to interpret the message. Some examples:
Example sentence: hw r u?
Encode your information in time delays
Presumably there is some reason that you can't speed up the data transmission, but perhaps you can slow it down. At 5 bits per hour, that's 12 minutes between each bit. Instead of sending each bit at regular interval, you can delay transmission of bits and use the delay time as a means of conveying information.
So let's say you expect a minimum of 12 minutes between each bit, you can encode the data as follows (time is in mm:ss format):
The more data you encode, the fewer bits per day you'll be able to transmit, so there will be some optimal balance you'll have to figure out based on the minimum delay interval you consider acceptable. Then you can perhaps use the bits themselves as an error checking mechanism, or to still transmit data.
Ok, since all other answers give some general advice, I instead provide a full-fledged solution, that would probably work for real use case with minor tweaking. Start from a usefull dictionary of stuff you need to bit-encode:
You get with something around 70.000 things to be encoded in the most efficient bit space.
Then analyze all communications in the past decades, find sequences of words or single words that are used more often.
Add to the dictionary the sequence of words. I would not be surprised if we are still below 70.000 usefull terms.
Now prune the dictionary, remove synonims without technical relevance, outdated or never used terms. I expect it to shrink to at least 30.000 terms, If done aggressively probably we can stay safe with 15.000 terms. For that part I would elect a number of people (say 1000 people), be it experts in english language and technicians/scientists/programmers/engineer. Each person is awarded with 1000 random words and it is given the task to sort that words by likely-ness to be usefulll given the context of the mission. Each person should carefully check the meaning of each word, search for synonyms etc. It would probably be a year of work because it has to be done carefully. It is not and error that I gave to much words too much people, each word will be examined by more than one person and in more than one field.
Ok, now it gets the interesting part you sort the words/setenctes/symbols using the following priorities:
With less than 16.000 words, you know every single word can be encoded in 14 bits. However since you know some words are more often used than others (in example the most occurring text sequence would probably be "SPACE" or ".SPACE") you can prioritize certain words to be encoded in less bits. You can take inspiration from UTF-8 or other bit encoding schemes. UTF use 8 bits' bytes, here since you need 14 bits encoding space you could use bytes made of 5+5+7 bits:
if first bit is 0, the next 4 bits forms a word ( the 16 more often used words, guarantees a transmission time of 1 hour for those words)
if first bit is 1 and second is 0, the next 8 bits forms a word (the 255 more often used words after the first 8, so we actually reached 263 words in 10 bits)
Note that the 263 most common words may contain something really not reasonable, so those must be reviewed by a team of people. Just that thing could save thousand bytes in future communications.
if first two bits are 1 and third is 0, the next 14 bits forms a word
You could also reserve some emergency modes to encode information that is not included in the dictionary:
if the first 3 bits are 1, you enter text mode. that means you send single characters and digits there are 26 characters and 10 digits, "T,E,A,O" are not sent since those are most common letters: we have 36 - 4 letters, so 32, enough to require just 5 bits, so at this point for each letter you send 0, plus the bits to encode the character
if during text mode a 1 is received insted of the 0-starting-character you rollback to regular mode.
You could use as much special modes as you wish (coordinates, small software updates to ship etc.) Each special mode can be activated by setting first N bits to 1, or by using a special word in the dictionary (so first two bits are 1, third bit is 0, and then fourteen 1s). You can even use a custom mode to de-prioritize words on the fly. In Example:
Received sequence 1111111111100, then received XXXX (4 bits word), then received XXXYYYYY ( 8 bits word), those 2 words are swapped in dictionary. So that future communications can benefit of 5 bits less for a word that is going to be used more often. This sequence requires 14+4+8 bits (26 bits, so if you need to use a particular word more than 5 times you already saved some bits:
You had "Banana" in dictionary, it was a 8 bits word, so required 10 bits for transmission, and you had "Yes" that was a 4 bits word and required just 5 bits for transmission. If you know you are going to use Banana 6 times, you send the swap sequence for "Yes" and "Banana". The sequence is 26 bits, and Banana-4 written 6 times is 30 bits, so in total 56 bits, If you don't swap Banana, writing Banana 6 times requires 60 bits. You saved 4 bits using the swapping sequence.
In reality the swap sequence should double the limit, so it become usefull if you write Banana more than 11 times, because you have also to keep in mind that at some point you want to switch "Banana" and "Yes" again.
The good side of this encoding, is that since information is transmitted at very low pace, you can have whole teams working on saving bits with the help of computer algorithms (that can automate insertion of certain special sequences). While you are sending your first 5 bits, you have time to examine the next horus/days of communications and continuosly improve them.
Since the dictionary include sequences of words and sentences I can expect it to have in average 1 word per hour in regular communication. So basically 1 word/5 bits, which is exceptional!
^^^^
Probably all the above can be done by 1 people alone (in example I could write some programs to help and do that in one month or so), but since that task requires a lot of safety, various experties fields etc. It is highly suggested that many many people work on that to assure the minimal number of bits is used in the end.
When writing text to and from the ship, people will be helped with text editors that shows words that can't be encoded, and suggest alternative sequences or words that use less bits. The text editor will highlight in blue sequences of 4 bits, in green sequences of 8 bits, yellow the longer sequences, and suggest special modes when it thinks it is appropriate. It will add also a line break after each day of transmission (you will likely to see a lot of line breaks), and text that was already sent cannot longer be erased from text editor.
A simple example: If we run the above algorithm on the text above "ALL ABOVE THAT": with the following oline tool:
you see that some words are really good candidate for 4 bits encoding:
And there just 150 words that are not used uniquely, those words could become good 8 bits-candidates, and also some sentences like:
And some senteces are good to keep in the 14 bit dictionary, in example:
The following sentence:
You could use the dictionary for that
will be encoded in
You could use| the dictionary| for| that
Which means in bits:
17 | 10 | 5 | 5
In colors
Yellow | green | blue | blue
just 37 bits for a sentence!
Use reverse base64 character encoding (i.e. base64 text → binary transmission → base64 text). You can see an example base64 table here, but note that the rest of the page there is using base64 characters for a different purpose, so ignore the use cases on that page. This allows you to represent the English characters, including numbers, which is precisely what you said you wanted, using 6 bits per character which is just 1 bit short of fitting into 1 hour's worth of transmission in your circumstance.
This includes both upper and lower case letters. If you are fine with restricting yourself to one case, which would still fulfill your requirements, then you would have room left to include more punctuation or other enhancements (up to 26 other enhanced transmission modes). I would recommend using some of this extra space to represent some extremely common words or short phrases that you would use very, very often. Then use a few of the character slots for other special meanings, such as "the next few bytes represent status codes" or "the following data is compressed".
For the examples below, I'll assume that 2 of the characters represent different word/phrase lookup tables using 9 bits each since this allows the lookup to take exactly 3 hours to send, including the initial 6 bits (6 + 9 = 15 bits = 3 hours). This allows for 512 bits worth of lookup power times 2; that is, 1024 different shortened words or phrases.
Using this format...
"Hey Bob" as plain text requires 6*7=42 bits = 8 hours + 2 bits
"communication array damaged by [reason]", assuming "communication array" and "damaged" are both in the lookup table, would take 9 hour + 3 bits + [however long it takes to send the reason]. "communication array damaged by Klingon torp" would take 24 hours - less if either "Klingon" or "torp" were send as lookup words instead of as plain text.
This is a "repeat recent word" mode. In computer science, it has been shown that recently used data is among the most likely data to be used next, and that is what a PC memory cache is for. We can do something similar by making 1 of the character slots represent "The next 4 bits refer to a previous word; count back that many words in the most recent transmitted data."
With this, "Klingon fleet approaches from 294 and Klingon admiral on comms saying Klingon destroyers equipped with new black hole tech" allows you to shorten 2 instances of "Klingon" to exactly 2 hours worth of data each; the first one providing "0110" (6) as the 4-bit-lookback value and the second instance being "0101" (5). In some communications this could save a lot of time if words are repeated often. Note that pronouns like "their" could have been used in some places, but that would take 7 plaintext characters (including surrounding spaces), which in this case would have taken 6 hours + 2 bits longer to send.
This would allow customized shortcuts that were not thought of before launch, a sort of copy/paste. "start copying here", then continue the message, then a "stop copying here"... then later you can send a "paste" character to repeat a long message. "comms good, thrusters good, life support good, magnetic-artificial-gravity [copy]working intermittently due to a swarm of flies in the grav-capacitor[end copy] from a meal someone left out for days", then you only have to send that long text 1 time, and each time after that you send "comms good, thrusters good, life support good, magnetic-artificial-gravity [paste]", and you do that until it changes back to "good". Also, "comms", "thrusters", "life support", "magnetic-artificial-gravity", and "good" might all be in the lookup table, meaning this entire message takes 22 hours + 1 bit to send after the first time you send it. Even better is if you make this "paste mode" be followed by a few bits for a "paste buffer number". Then you could "[copy1]comms good, [etc.], [copy2]working intermittently due to...[end-copy-2][end-copy-1] from a meal that..." Then every time you want to send an updated status, if it's the same as the one before it takes 1 hour plus a few bits.
You can tweak the exact representation (different send modes, number of bits for each, etc.) to improve performance based on your expected communications to improve performance further.
Just what it sounds like. The following data uses a given compression algorithm.
You can add whatever other features you want in a similar fashion. Also note that, as stated by @HenningMakholm in comment below, some of these features are implemented in some compression software available for use today. Henning's example was zlib.
If you cut out lower case and still have more character slots left over after implementing all the punctuation and mode's you want, you can use left over character slots to expand modes that you already have. This is similar to what I did above with the lookup tables, I suggested using 2 of the base64 character slots that were freed up from tossing lower-case to give us 2 separate lookup tables. You could also do similar to double your look-back reach or to double your number of copy/paste buffers. You can also increase or decrease the number of bits following a mode-byte, such as having 4 bits after copy/paste to have 16 paste buffers, or only 2 extra bits to save on transmission time but allow only 4 paste buffers.
Worst case scenario this requires 6 bits per character. Average case scenario you will use a few lookups, look-backs, or some compression to beat the worst case, so you require 3-5 bits per character. Best case is messages that can be relayed entirely, or nearly entirely, by lookups and look-backs, which will be often for normal day to day activities that go as expected - for such common communication, if you have a well tuned number of bits for each special mode, you should achieve better than 1 bit per character. Many times much, much better than 1 bit per character, such as with the status report example a couple paragraphs up.
zlib by methods to set a pre-agreed "dictionary". (Some additional tweaking to the algorithm could probably be applied to make it squeeze the last few bits out of short messages, though).
$\endgroup$
Apr 17, 2019 at 21:40
As a thought, back in the day you used to have predictive text on a mobile phone with.
[1|.], [2|abc], [3|def], [4|ghi], [5|jkl], [6|mno], [7|pqrs], [8|tuv], [9|wxyz], [0| ].
If you were OK with predictive text (so, display as predicted - allow ship to skip through poss. words if they don't make sense). You'd need those 10 digits, plus a control character to signal if it was a number or character. That would need 4 bits / letter, so ~48min/letter by your timing. That would leave 5 extra 'control' characters.
Now, why should you only have one control character to act as a shift? Why not 2? You'd get 4 options for each key (2^2), so you can drop predictive text entirely and have 1 character per symbol (plus a few spares for punctuation characters etc) if the two flags are set.
Carrying on that path, you then have an additional 4 control keys, which by my book is 2^4 = 16 options, over the above 10 keys ... you get ~160 extra characters. You could use those as templates (similar to the Q-codes), so get full text plus qcodes, all in 4 bits (~48min per character).
On top of the answers talking about encoding, I'd also look into finding clever ways to incorporate steganography in the medium and/or message. With 5 bits per hour, you have a VERY limited throughput rate, so anything you can do to hide additional bits of information could help enormously. Maybe some clever manipulation of the signal carrier or something related to signal orientation. This would depend on what type of interstellar communication you're sending out.
Speaking of which, I would like to also include a bit of frame challenge. 5 bits per hour is a pretty weird bandwidth. Assuming 2 bits per radio oscillation, 5 bits per hour is roughly 0.0007 hz. that is REALLY low. As in, impossibly low. The lowest frequency Humans use right now is 3 Hz, and that's only for communication with submarines. To go 4 orders of magnitude lower would require a HUGE antenna: Antenna length needed is essentially the distance light travels in 1 second divided by the frequency. In this case, that would be an antenna that is hundreds of millions of kilometers long. That's an ABSURD length.
