The Critical Line – Volume 28

Error Correcting Communication

On the 10^th of December last year Voyager 2 became the second man made object to leave the solar system after a 41-year journey. At roughly 17.7 billion kilometres from Earth one may wonder how we’re still able to communicate with it.  The signal strength from Voyager 2 is reduced by the inverse square of its distance to earth, and at such long distances radiation that interferes with the transmission can easily corrupt the data.

Despite the significant noise in this signal, NASA are still able to receive data from Voyager 2 by using a Turbo Encoding. Unlike compression, the Turbo Encoder used by the Voyager probes makes the data it’s sending six times larger, but it safeguards against data corruption. To understand the basic principle of how this works, let’s review a much simpler form of Error Correcting Communication (ECC) – the Hamming Code.

Hamming Code

Consider a transfer of data as a sequence of bits (0 or 1), and an error in the message is a bit randomly flipping from 0 to 1 or vice versa. The Hamming Code, named after Richard Hamming, is a form of ECC that detects errors by looking at the parity of the bits of the data being transferred. In a block of $$2^n-1$$ bits of data, $$2^n-n-1$$ are dedicated to the message that is being sent, and the other $$n$$ encode parity information about the message. By checking the consistency of the message and the parity information allows the decoder to identify when up to 2 bits have been flipped. Or, if it is known that at most one bit was flipped it can also determine which one it was and correct it.

To demonstrate, let’s encode the message 10011010001 of length $$2^4-4-1=11$$ into a block of length $$2^4-1=15$$. First, we leave each position in the block that is a power of 2 blank (these will become the dedicated bits for parity information) and fill the remaining positions with the message. Then the bit at position $$2^{k-1}$$ is set so that the sum of all bits with a $$k^{\text{th}}$$ significant digit of 1 in its binary representation sum to $$0 \mod 2$$.

This is illustrated below. For instance, the numbers with 1 in the first significant digit of their binary representation are the odd numbers (first row in green), the parity digit is set to 1 so that the whole row sums to $$0 \mod 2$$. The column in blue shows the sum of each row equal to zero.

Now suppose the digit in position 10 was flipped, so our received block becomes 101000111110001. Then we can recalculate the parity bits as shown

Because the rows in the above diagram are not all zero we know that there was a data error. Further, the recalculated sums (in blue) are 1010 which is the binary representation of 10 (i.e. the position of the data error).

For your chance to win a $50 book voucher, send your solutions to ActuariesMag@actuaries.asn.au

This Month’s Puzzle

After several years of interstellar travel, you have just touched down on a new planet. You want to explore this new environment, but you need a way to communicate with the mother ship and despite the breaking the barriers of interstellar travel, you are still using a very primitive 32-bit telecommunication device. Usually you use this device by punching in a message of 32 zeros or ones and pressing send. However, your device is malfunctioning. The display screen shows you a random 32-bit message and it is only allowing you to change a single bit. After pressing send another random message is displayed. You don’t know of any repair shops on this planet, so you must find a way to use this device to communicate. You start by writing down a codec/mapping of 32 symbols to numbers (‘A’=1, ‘B’=2, … ‘Z’=26, ‘.’=27, … ‘[space]’=32). Determine a strategy so that by changing at most one digit in each message you can convey the numbers 1-32, which can be used by those remaining on the ship to spell out your message.

Volume 27 Solution 

By Jevon Fulbrook

Thanks to all who attempted the puzzle and congratulations to all those who managed to identify the image as an Australian flag.

Thank you to all those who submitted solutions to this puzzle. Congratulations to James Marshall!

CPD: Actuaries Institute Members can claim two CPD points for every hour of reading articles on Actuaries Digital.