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...
Read More »
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.
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?
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.
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?
See what we're tweeting about
8 Comments
Add CommentSorry, 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!
Reply | Report Abuse | Link to this--
Edited by tonysmart at 02/01/2008 2:36 AM
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!
Reply | Report Abuse | Link to this--
Edited by tonysmart at 02/01/2008 2:38 AM
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!
Reply | Report Abuse | Link to this--
Edited by tonysmart at 02/01/2008 2:39 AM
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.
Reply | Report Abuse | Link to thisWell, 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?
Reply | Report Abuse | Link to thisHmm, I just realized I made a mistake. Let me change my answer to Problem 2 to 78.
Reply | Report Abuse | Link to thisDo 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.
Reply | Report Abuse | Link to thisrmartinosr@verizon.net
I think I can do it with 11 bits.
Reply | Report Abuse | Link to thisThe 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.