Space Bits

Image: Cloe Liane Shasha

• The Best Science Writing Online 2012

Showcasing more than fifty of the most provocative, original, and significant online essays from 2011, The Best Science Writing Online 2012 will change the way...

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.

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?

View
1. 1. tonysmart 09:50 AM 2/1/08

Sorry, but your solution to the warm-up problem isnt right: if the parity bit was the one flipped in transit you would conclude there was an error in the 100 bit message when there wasnt!

--
Edited by tonysmart at 02/01/2008 2:36 AM

2. 2. tonysmart 09:50 AM 2/1/08

Sorry, but your solution to the warm-up problem isnt right: if the parity bit was the one flipped in transit you would conclude there was an error in the 100 bit message when there wasnt!

--
Edited by tonysmart at 02/01/2008 2:38 AM

3. 3. tonysmart 09:50 AM 2/1/08

Sorry, but your solution to the warm-up problem isnt right: if the parity bit was the one flipped in transit you would conclude there was an error in the 100 bit message when there wasnt!

--
Edited by tonysmart at 02/01/2008 2:39 AM

4. 4. Tucker M 03:30 PM 2/1/08

I think the point is to tell whether there was an error in the total transmission, including any error in the error-detecting data.  If so, the described solution is accurate.

5. 5. Code Cracker 04:37 PM 2/1/08

Well, the warmup question only required that we be able to detect an error.  It didn't exclude false positives.  And to be fair to the premise of the question, false positives seem like less of a problem than false negatives.

Here are the best answers I've figured out:

1.  9

2.  77

Does anyone have better solutions?

6. 6. Code Cracker 05:03 PM 2/1/08

Hmm, I just realized I made a mistake.  Let me change my answer to Problem 2 to 78.

7. 7. gunondeer 09:34 PM 2/5/08

Do Not be so stupid-the solution is simple: instead of thinking(oximoron) about re arranging the bits, just alter the radiation around the bit mesage. In other words , make the bit message immune to the effects of radiation. Just like aluminium hydreoxide protects the human body from the effects of radiation, use a electromagnetic tube to run with the bit message . The em tube will insulate the bits by deflecting the radiation around the tube and not through the tube. the only problem I see is that a direct line of communationcations (like microwave transmission) will have to be established. The question of bit speed and em speed is different: you have to fire the em tube longer in order to creatino a tunnel for the bit message to follow down the center of the em tube/tunnel.
rmartinosr@verizon.net

8. 8. cdcinks 11:36 PM 2/13/08

I think I can do it with 11 bits.

The warm up shows how a parity bit can be used to detect errors in a message if at most one bit changes. To solve problems one and two, I will logically stripe the data across 11 "columns" of data. The first bit will be in column one, the second bit in column two, etc. Each column will be given a parity bit. I need eleven columns because even if the noise burst wrecks twenty consecutive bits, then there will still be at least one column with only one change. The parity bits on those columns will indicate the error.

This does nothing for correcting or locating the error, but 11 bits should detect one, regardless of message size.

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

More from Scientific American

• @ScientificAmerican | 3 hours ago

Can We Harness Disruption to Improve Our World's Future?

• News | 3 hours ago

Federal Flood Maps Left New York Unprepared for Sandy, and FEMA Knew It

• News | 5 hours ago

Smart Wig Could Compete with Google Glass

• News | 6 hours ago | 1

Will to Persevere Can Be Triggered by Electric Stimulation

• Climatewire | 8 hours ago | 5

More »

Latest from SA Blog Network

• Wonderful Things: The Pugnacious, Alien-esque Skeleton Shrimp

The Artful Amoeba | 1 hour ago
• Can We Harness Disruption to Improve Our World's Future?

STAFF
@ScientificAmerican | 3 hours ago
• British Storm Brings Up History's First Work of Social Media

Plugged In | 3 hours ago
• Rolling on Wheels That Aren t Round

Observations | 3 hours ago
• The future of nuclear energy: Let a thousand flowers bloom

The Curious Wavefunction | 4 hours ago

Science Jobs of the Week

Space Bits

X

Give a 1 year subscription as low as \$14.99

X

X

Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X