Explanation

So THAT was it. You're getting us into trouble...

Note: If all you want is to see the decoded message, scroll to the bottom of the page - the images will catch your eye in the way.

Space. The final frontier. The source of so many unanswered questions. Is the universe really infinite? Is there intelligent life in some far, far away planet? And, more importantly, why do all aliens wear those unfathomably ridiculous suits?

Having a shot at answering those questions is in the hands of a selected few. Fortunately, you have become one of them for a day. Thanks to a BBG-sponsored contest, you have won some time in a powerful radiotelescope, capable of broadcasting your thoughts to the stars. There is only a catch, though: as time is limited and you want to have the message repeated several times to ensure reception by the highest intelligences on the galaxy, its length is limited. You only have 8,192 bits, or 1,024 bytes, or 1 kb.

Here's how you do it.

Part I: designing the carrier

The direct inspiration for all this is, as can be easily guessed, the Arecibo message (and its insanely cool "reply"). However, since we have quite a bit more bits available (pardon the pun), it would be wise to design an encoding which makes the message as easily decoded as possible.

In the Arecibo message, the data was broadcast as a series of binary pulses, using frequency shifting. Let's say that you can't afford that luxury, and that your radiotelescope is only capable of broadcasting pulses at a fixed frequency, like a huge Morse transmitter. In that case, directly sending your raw binary stream "as is" is a bad idea (I would argue it also was with the original Arecibo message, but whatever), since the duration and timing of the pulses becomes critical. If your signal gets garbled by passing through some gas nebula or Klingon cloaking device, that could make decoding your message very difficult.

Instead, I settled on a different binary encoding. Lets say the bits of our message are abcdef...., with each letter either 0 or 1. Then, the final, encoded binary stream looks like:

1 a 0 1 b 0 1 c 0 1 d 0 1 e 0 1 f 0...

 That is, each bit is surrounded by a 1 from the left and by a 0 from the right. Ones in the original message get replaced with "110", and zeros get replaced with "100". If the message is 10110101, for instance, then the broadcast would be:

110100110110100110100110

'1' represents transmission in the radiotelescope; '0' represents silence. In order to encode this sequence to a format that the radiotelescope software can understand, you cut it up in 8-bit chunks and convert these to their byte equivalent, high byte first:

11010011 01101001 10100110 -> 211 105 166

There are several advantages to this type of enconding. First, it is very regular. The transmission can be divided into uniformly-sized chunks corresponding to three bits of the encoded message, which correspond either to a short pulse followed by a long silence (binary 0), or a long pulse followed by a short silence (binary 1). The number of distinct pulses also corresponds with the number of bits of the original message. Besides, the high periodicity of the signal will probably set off all alarms on any FFT-based detector on E. T.'s side, which is a sure way to attract attention to the message. So I would argue that this encoding is resilient enough.

Since we are using 3 bits for each bit in the original message and we are limited to 8,192 bits, the maximum length of the broadcast message is 2,730 bits, which gives a 8,190 encoded length; if there are any leftover bits at the end, you just pad with zeroes up to 8,192. It is probably wise to choose a message that is somewhat short of the 2,730 bits, which has two beneficial effects: the length can have a meaningful value (more on that later), and the "silence" at the end of the transmission allows the receiver to easily determine the start and end of the message.

Part II: choosing the message format

A nifty thing about the Arecibo message is that its length (1,679 bits) revealed a lot about its structure. 1,679 is a semiprime number (the product of exactly two prime factors), which is a strong hint to mathematically minded people (er, aliens) that the data is meant to be laid out on a rectangular grid. Further, there were only two ways to arrange the dots. One would yield garbage, and the other would recover the original message.

I wrote a small, hackish script to find the 30 semiprime numbers which were closer to 2,730, the maximum message length, and had at least 11 as the smaller factor. (The script is written in Tcl, and requires the factor program, so if you are not running Unix/Linux, I'd rather not bother). These are the first results:

2717 -> 11 13 19
2701 -> 37 73
2669 -> 17 157
2651 -> 11 241
2641 -> 19 139
2629 -> 11 239
2627 -> 37 71
...

Ok, so I lied to you (somewhat). The program does not only finds semiprime numbers; it also finds numbers with exactly three prime factors. Messages with that length would be ideally suited not to a 2D grid, but to a 3D one. And, sure enough, there is 2717 ( = 11 * 13 * 19) looking innocently at us. (Interestingly, the next numbers with 3 "large" prime factors do not appear in the first 30 spots; the second occurrence is 2431 = 11 * 13 * 17, and lands in the 31st place).

So if we choose 2,717 as the message length, we get several benefits. First, we actually get the most bang from our buck, since it is the maximum message length within our limits which is the product of two or three prime factors. Second, this also sets us apart from the Arecibo message and its 2D limitations, so as to convey the most possible information and to awe the receiver with our geometrical mastery. And third, broadcasting a 3D image to space is plain cool. We already have HDTVs in our living rooms (well, *I* personally don't, but you get the idea), so sending a puny 2D binary array to somebody seems rather Sputnik-era. It does not sound 21st-century at all. However, sending 3D objects? Sign me up!

So that is it. We are sending an encoded 2,717 bit binary message, representing a 3D prism (11 * 13 * 19) of binary information. The exact ordering of the coordinates is somewhat arbitrary. I chose to have a 19 x 13 base and a 11 bit height, encoding first the 19-bit long lines, then the 13-line array forming a plane, and finally the stack of 11 planes. So if you decode the binary message and show it left to right on your screen, with a column size of 19 binary digits, you would see 11 19x13 2D images, which, stacked, form the original 3D diorama.

Part III: the all-important message contents

By now we have settled on mostly everything related with the message format, and now comes the time of deciding what to put on it. A few things are a given; you'll want to have some guides in it which can help the receiver decide when the message has been correctly decoded; and, also, a Boing Boing Gadgets logo is a must, so that they can know who's their daddy. Other than that, almost all the matrix is empty for you to fill. 

I imagine that dreams of galactic glory and peace are entering your mind. Mankind, setting a high standard for all other intergalactic races, sends a beautiful eulogy to knowledge, friendship and unity to our extra-terrestrial friends, which will come to our planet to complete our lives, help us achieve nirvana, and lavish all those New Age gurus which heralded their arrival with spiritual and material riches.

C'mon, man. Don't be such a pussy. They are aliens, see? The most knowledgeable studies on the subject show that an alarming majority of aliens only seek to screw us over, and when the day comes, no amount of yodeling is going to save you. If we have to send a message to them, then it has to be one of strength and immense destructive power, so that they choose to lay eyes on somebody else.

And what conveys "destructive power" better than a Death Star? I rest my case.

To serve as a powerful warning, our message will contain a Death Star, in addition to the guides and the BBG logo. Since the Death Star can only be 11 bits in diameter, there is some empty space which can be filled by including some other information to make our intentions clearer. Such as, oh, a few starfighters.

As making all this by hand would be rather inconvenient, I wrote some other hackish scripts. First, I needed something to base my work on; to that end, prepare-diorama.tcl writes to standard output a text file which already has three guides (straight lines cutting at the origin, which will only appear as such if the dimensions are taken in the correct order) and a sphere (with a convenient stretching at the equator). The results are here. This text file, or a modified version, is meant to be read by an encoder which generates the final encoded message, so that spaces, zeros and dots are ignored (signify empty spaces, or binary zeros) and any other character represents a binary one.

The encoder is here. It reads the diorama text file from standard input and writes the encodeded binary message to 'message.1k' in the current directory. In order to make the creation of the message more fun (and easy), that's not all it does - it also writes a KPovModeler file to the current directory which can then be used to render the result in POV-Ray. As an added bonus, it is possible to use different characters for binary 'ones' (the way the encoder is now, valid 'binary ones' are numbers from 1 to 9 and letters from 'a' through 'f') and the encoder will give them different colors in the generated KPovModeler file.

I then went to town, altering things on the diorama, generating the KPovModeler file, rendering, rinse, repeat. I carved the mega-laser socket from the Death Star; as a sign of mercy, I also added the exhaust pipe leading to the inner core (the sphere is hollow and has a single bit in an inner chamber, connected to the external trench), should they ever need to go the Luke Skywalker way. After adding the BBG logo, the remaining space was convenient enough for adding a schematic version of USS Enterprise and of a X-wing fighter. I seriously considered including a Big Middle Finger on the Sky in the message, but I did not want our race to come across as bullies.

The final text diorama with which the encoded message was generated is here. Here are some 3D renderings of it in all its false-color, blocky glory.

Cool, isn't it?

Part IV: going full circle

In order to fully demonstrate the process, the file decode-message.tcl reads the message.1k file from the current directory and writes a KPovModeler file with the decoded 3D matrix. Although, obviously, the false color is lost on the process, none of the sheer sense of awe imbued by the finest (and fictional) weapons made by mankind is. Here are some renderings of the result.


So that's it. Now go to that radiotelescope, set the power at maximum, blast the message through (bonus: do it at 8 bps and it will take exactly 1,024 seconds, or a little over 17 minutes, to broadcast), and bring 'em on. We are not afraid.