23
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ What type of spacecraft are we looking at here, and what data does it need to communicate? $\endgroup$ – Cadence Apr 17 at 10:32
  • 28
    $\begingroup$ What's the relationship between bits and Morse code? At five bits per hour you cannot reasonably communicate anything other than predefined status messages. (English has an entropy of about 1.3 bits per character, and a typical word is 4 or 5 characters. At 5 bits per hour with optimal compression you can send about 20 words per day of unconstrained text. This is too low, so in practice you will want to predefine a number of status messages and send an index into the message table.) $\endgroup$ – AlexP Apr 17 at 10:41
  • 4
    $\begingroup$ If it's 5 bits per hour excluding error handling, you're probably better to drop error handling and use those extra bits for the message. A mildly scrambled message is still better than not being able to send the message at all (usually). $\endgroup$ – Jack Aidley Apr 17 at 13:17
  • 6
    $\begingroup$ why 5 bits per hour? You can manage way better with radio today, which is one of the lowest tech options for space communication. Radio is still pretty poor, but it provides way better speeds than "5 bits an hour" $\endgroup$ – opa Apr 17 at 16:28
  • 2
    $\begingroup$ @opa I am assuming OP has FTL communication, it's just slow. Your simple radio will take decades or centuries to send a signal. $\endgroup$ – Andrey Apr 17 at 20:38

13 Answers 13

56
$\begingroup$

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.

  • For a very common command with the ID 6, you need to send the command's ID followed by the terminator: 0110 0000.
  • A very uncommon command with the ID 26683 would look like this: 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.

$\endgroup$
  • 7
    $\begingroup$ +1. If you have even the slightest notion of the kinds of things you want to say you can vastly reduce the amount of information required. “Tell [astronaut] that their [medical property] is [phrase detailing concerns]” could theoretically only take a couple of bytes to transmit if the parser is cleverly designed. $\endgroup$ – Joe Bloggs Apr 17 at 11:26
  • 31
    $\begingroup$ So, basically, Q codes, created circa 1909 by the British government, to be used by maritime ships (both civilian and military) for precisely the reason in the question. As a nice bonus, language is irrelevant, so long as each party has a lookup table in their own language. $\endgroup$ – Chronocidal Apr 17 at 11:33
  • 16
    $\begingroup$ 1 byte -> 15 commands, 2 bytes -> 255 commands...what? Why not 256 and 16384? $\endgroup$ – genesis Apr 17 at 12:05
  • 3
    $\begingroup$ If using the terminated ID approach Huffman encoding could aid in ensuring the most common commands are the more efficient. Also, you might want to add to the protocol a mechanism for including parameters with the command as a separate parameter command could easily take more space than simply allowing each command to have an arbitrary number of parameters. $\endgroup$ – FluxIX Apr 17 at 14:33
  • 1
    $\begingroup$ 4 bits -> 16 commands, 1 byte -> 256 commands, 2 bytes -> 65536 commands $\endgroup$ – Vaelus Apr 18 at 4:30
17
$\begingroup$

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:

  1. Is the system pre-defined, i.e. can there be word-lists?
  2. Are characters/words sent individually or can you apply compression to a large amount of data and then send it in bulk?

If you want something that is simple, sciency and requires no setup, go with Huffman-coding individual letters based on frequency in English. ;)

$\endgroup$
  • 1
    $\begingroup$ as you can see with XKCD it gets so wordy to convoy a simple idea. May still work better than ASCII $\endgroup$ – Andrey Apr 17 at 20:37
  • $\begingroup$ @Andrey I'm not sure I would call rocket science a "simple idea". $\endgroup$ – TheHansinator Apr 17 at 23:51
  • 2
    $\begingroup$ @Andrey Though, in all seriousness, the words chosen for the compressed language would probably be chosen specifically for the domain - e.g. the language chosen for a spaceship probably would include words like "rocket". $\endgroup$ – TheHansinator Apr 17 at 23:54
  • $\begingroup$ Many of the answers here come down to creating your own language (as a subset of English) or compressing by using bit patterns to match to existing word lists. The latter is what Huffman-coding accomplishes, but without the requirement of a priori knowledge of the words you will use. $\endgroup$ – Jon Wolski Apr 18 at 21:47
9
$\begingroup$
  1. Encode whole words instead of single letters.
  2. Use Huffmann encoding based on word frequency in the specific context of space travel. So that frequent words ('the', 'yes', 'shields') have less bits than less frequent words.
  3. Use markov chains to take the context of the sentence into account as well.
$\endgroup$
  • 2
    $\begingroup$ This is the best compromise between flexibility and efficiency. It's much more flexible than a simple code table but much more efficient than encoding a language one character at a time. I think your answer might do better with a few short examples though. $\endgroup$ – Vaelus Apr 18 at 4:33
6
$\begingroup$

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).

$\endgroup$
6
$\begingroup$

Not Morse code

From Wikipedia:

International Morse code is composed of five elements:[1]

  1. short mark, dot or "dit" (▄▄▄▄): "dot duration" is one time unit long
  2. longer mark, dash or "dah" (▄▄▄▄▄▄): three time units long
  3. inter-element gap between the dots and dashes within a character: one dot duration or one unit long
  4. short gap (between letters): three time units long
  5. 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'.

Bits

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.

$\endgroup$
4
$\begingroup$

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....

$\endgroup$
  • $\begingroup$ I'm pretty sure that style of writing predates common SMS usage. I recall half the people on the internet talking that way in the late 90s, a time when most people did not have internet but even fewer people had the ability to send text messages. $\endgroup$ – Loduwijk Apr 17 at 18:22
  • $\begingroup$ Was previously beeper speak: 143 133 43 43 5318008 $\endgroup$ – RIanGillis Apr 17 at 21:02
  • $\begingroup$ @Aaron true, you had stuff like 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$ – VLAZ Apr 18 at 6:30
  • $\begingroup$ @VLAZ wrote "That's why it's called 'textspeak' not ..." I'm not sure if I had ever heard it called "textspeak" before I saw this answer. If I had, maybe I just don't recall, or didn't associate it with phone texting. However, I have generally heard this type of messaging called "netspeak", and we were using that term in the late 90's and early 2000's. $\endgroup$ – Loduwijk Apr 19 at 14:53
3
$\begingroup$

Huffman Encoding

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.

$\endgroup$
  • $\begingroup$ One other very important part of Huffman Encoding: It can be done online. While you can send a dictionary (or have agreed upon a dictionary before you left), that dictionary can be updated mid flight. So if you find you suddenly need to talk about medical issues a lot, the Huffman trees will start to adapt to encode medical words into fewer bits. This lets you take advantage of locality of context. $\endgroup$ – Cort Ammon Apr 19 at 16:44
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Yeah, something similar to PSK31, or maybe JT65, FT8 or some such for their low S/N characteristics, was my first thought as well. One benefit of it, and many similar encoding schemes (I'm not sure I really want to call it a modulation per se, though one could make an argument that it's a baseband modulation) is that they use variable-length encodings. That requires some kind of synchronization, but allows the more commonly used code points to be encoded more compactly and thus transmitted more quickly. $\endgroup$ – a CVn Apr 17 at 17:30
2
$\begingroup$

Building on other answers

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:

  • it, to -> t
  • is -> s
  • have -> hv
  • cat -> ct
  • are -> r

Example sentence: hw r u?

An alternative approach

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):

  • 12:00 = 0
  • 12:05 = 1
  • 12:10 = 2
  • 12:15 = 3
  • etc

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.

$\endgroup$
  • 1
    $\begingroup$ If your channel lets you control time delays that way, its bandwidth is more than 5 bits per hour. $\endgroup$ – jeffB Apr 18 at 17:25
2
$\begingroup$

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:

  • List of all english words (58.000 or so, now expecting that list to include technical terms though)
  • List of all technical terms, including eventual keywords for programming languages (foreach i.e). I expect it to be below 10.000 for most fields (personal estimate)
  • Usefull symbols (punctuation, formatting symbols, short names for math functions, single digits and characters). would probably be less than 255 things.
  • Code names (example: astronaut 1: Bill, communication received: Roger etc.

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:

  1. Occurrencies of words and word sequences in last decades of communications.
  2. Occurrencies of words and word sequences in english language.
  3. Evaluate if there are emergency words (like "CAME IMMEDIATLY BACK").

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!

^^^^

ALL ABOVE THAT:

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:

Compute words frequencies

you see that some words are really good candidate for 4 bits encoding:

  1. the
  2. you
  3. bits
  4. to
  5. of
  6. words
  7. in
  8. and
  9. a
  10. is
  11. that
  12. be
  13. word
  14. are
  15. if
  16. for

And there just 150 words that are not used uniquely, those words could become good 8 bits-candidates, and also some sentences like:

  • to be
  • 4 bits
  • more often
  • of words
  • you can
  • the dictionary
  • is 0
  • 8 bits

And some senteces are good to keep in the 14 bit dictionary, in example:

  • would probably be
  • you could use

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!

$\endgroup$
2
$\begingroup$

Here is the literal answer to your question:

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.

And here are some enhancements to that by adding special "modes"...

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".

Mode 1: Table of most common words or phrases

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.

Mode 2: Look-back

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.

Mode 3: Copy/paste, possibly with separate paste-buffers

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.

Mode 4: Compression

Just what it sounds like. The following data uses a given compression algorithm.

And More!

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.

Multiple versions of each mode

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.

So how efficient is this?

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.

$\endgroup$
  • $\begingroup$ Your modes 1-3 are already part of common LZ-derived compression algorithms. The "table of common phrases" strategy, for example, is exposed by 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$ – Henning Makholm Apr 17 at 21:40
  • 1
    $\begingroup$ Base64 typically increases the size of a message by about 1/3. Encoding three 8 bit bytes takes four Base64 symbols. Even if you duse a different code table for base 64 characters that uses 6 bits per symbol instead of 8, it would still take 24 bits to encode three 8 bit bytes, so at best there's still no benefit. $\endgroup$ – Vaelus Apr 18 at 4:41
  • $\begingroup$ @Vaelus The examples you linked to (admittedly on the page that I linked to) is not about base64 character encoding, but rather about taking binary data and representing it in a character format that is more platform independent. Scroll up to the beginning of the "Examples" section and read the first paragraph. That is essentially doing the opposite of what I suggested. I linked to the page more for the "6-bit characters" explanation and the table. I will edit my answer to clear this up. $\endgroup$ – Loduwijk Apr 19 at 14:40
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Welcome to the site! I think there's a solid answer in here, maybe consider rephrasing it more decisively rather than "as a thought". Particularly, relating how this would apply usefully to our low-bitrate spacecraft communication system! $\endgroup$ – Ruadhan Apr 18 at 10:25
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't think OP mentioned radio/electromagnetic communication anywhere. I assume he thinks about something like manipulating entangled particles to achieve FTL communication and as it is pure fantasy, there might be arbitrary limitations on how much time it takes to 'reset' given particle to be able to send another bit. $\endgroup$ – Artur Biesiadowski Apr 19 at 10:53
  • 1
    $\begingroup$ Sure, or maybe if we want to give a very realistic explaination, the communication is very noisy but thanks to checksums and error correction codes and intereferometry we are able just to extract 5 bits of information from the Gigabyte/second bit stream $\endgroup$ – GameDeveloper Apr 20 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.