Space Bits

Join Our Community of Science Lovers!

At certain times of the year, a message from Mars traveling at the speed of light can take 20 minutes to arrive at Earth. As if that weren't bad enough, space radiation may flip one or more bits, where flipping means turning a 1 into a 0 or vice versa. For this reason, you've been called in to help with the coding. Here is what you are told.

The spacecraft will send a bunch of messages, each consisting of 100 bits plus some extra bits as we discuss below. There is an infrequent burst of space noise that can cause one or more consecutive bits to flip. The consecutive sequence of flipped bits will have a length of at most 20. Moreover, those bursts will happen at most once in the time it takes to transmit 150 bits.

We'll work up to that noisiest case in stages.

On supporting science journalism

If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.

Warm-up:
Suppose the noise burst could flip at most one bit in the time it takes to transmit 150. How few bits could you add to the message to detect the presence of an error?

Solution:
Just one extra bit would do it. Count the number of 1s among the 100-bit message. Call that number N. Add an extra bit (the 101st) with a value 1 if N is even and make the extra bit 0 if N is odd. (This is called "odd parity" in the electronic trade.) When the message (along with the extra bit) arrives at earth, there has been an error if the number of 1s among the 101 bits is even. Otherwise there is no error.

Problems:
1. Next, let's assume that the noise burst will flip EXACTLY 20 consecutive bits or will flip no bits at all. How few extra bits would you then need to detect the presence of an error in the message?

Okay, if you’ve solved that, let's try for the full problem.

2. There can be zero or one noise burst in the time it takes to transmit 150 bits. If there is a noise burst, it will flip some consecutive sequence of at most 20 bits. How few extra bits would you then need to detect the presence of an error in the message? (Hint: I can do it with fewer than 115.)

Here is an open question. How many bits would be necessary to determine where such a noisy consecutive sequence of bit flips begins and ends in the setting of question 2? How would you do it?

Subscribe to Support Independent Journalism

Great science journalism requires human expertise, time, effort and creativity. And it costs money. That’s why I and the journalists here at Scientific American hope you’ll join our community.

When you subscribe, you are supporting staff and freelance journalists who are passionate about telling science stories that are true, important and compelling. Our editors and reporters are often experts in their fields, which means they understand the nuances of big discoveries and can untangle the breakthroughs from the hype. With a subscription, you are also supporting rigorous fact-checking to ensure the words we publish are precise and accurate. And you’re supporting original illustrations, graphics and photos that bring you closer to an advanced laboratory, an ice sheet in Antarctica or a space mission in orbit. You’re helping us craft other types of high-quality journalism as well: Our newsletters are carefully written, edited and curated by staffers you have or will come to know and love. Our Science Quickly podcast is based on original reporting, collaboration with editors and scientists and exacting production.

Subscriptions keep this engine running so we can continue to deliver thoughtful, rigorous and independent science journalism to you. In an era of viral misinformation, this work is crucial. If you value what we do, I hope you’ll consider joining us as a subscriber

Thank you,

Jeanna Bryner, Editor in Chief, Scientific American