|
Ecco poses a signal-jamming puzzle this month.
April 01, 2005
URL:http://www.drdobbs.com/parallel/jam-session/184406053
Dennis is a professor of computer science at the Courant Institute, New York University. His latest books include Dr. Ecco's Cyberpuzzles: 36 Puzzles for Hackers and Other Mathematical Detectives (W.W. Norton, 2002) and Database Tuning: Principles, Experiments, and Troubleshooting Techniques (Morgan Kaufman, 2002). He can be contacted at [email protected].
The young man at the entrance to Ecco's apartment turned out to be a Special Forces colonel. "Name is Carl," he said introducing himself.
He registered mild surprise to find Liane, Tyler, and me also there.
"No matter," he said. "Just don't publish for two months."
Once I agreed (did I have a choice?), he began to speak: "Our spy in enemy territory has a weak transmitter that transmits 1 bit per millisecond simultaneously to two receivers, one east and one northwest. The enemy can't detect our transmitter, but knows we are there, so has a jamming device that broadcasts noise in focused directions. The jamming device rotates counterclockwise every 10 milliseconds. When the jam signal intersects the spy's signal in some direction, the jam signal may flip a bit going in that direction, but just one. Therefore, it can flip at most one in every 10 bits going east and a different bit (again at most one in every 10) going northwest.
"Our spy must be able to send reliable messages, so we plan to encode the transmission with redundant bits to recover each 10-bit signal without errors. We should be able to do something fairly efficient, given the fact that we have two receivers."
Easy Warm-up: Suppose our only goal were to detect whether there were an error and we had just one receiver. How could we ensure detection using only one bit in every 10?
Solution to Easy Warm-up: Use the concept of parity. Allow 9 data bits and then one "parity" bit with the property that if there are no errors among the 10 bits, the number of 1s altogether will be odd. If the receiver counts the number of 1s and finds that the number is even, it has discovered an error.
Harder warm-up: What if there were only one receiver? How many bits are necessary to correct against any single error in 10 bits sent? (Think about the information you would need to locate the error.)
Solution: We want an encoding that sends at least 6 data bits for every 10 transmitted bits. The other bits will be redundant, but will allow the correction of any single bit flip. We need 4 bits to correct any possible bit because the 4 bits can count up to 16 possibilities. This is more than sufficient to indicate which of the 10 bits has been flipped (10 possibilities) or whether none have been (11th possibility). If there were three or fewer check bits, there would be 8 or fewer configurations of check bits to use as a diagnostic.
"Here are the questions gentlemen," Carl paused looking at Liane, "and young lady.
"1. How would you use the four check bits in the case of a single receiver?
"Now back to the case of multiple receivers. Suppose that the jammer may flip bits going to the two receivers but these must be different bits. You are sending the same message to both receivers. Moreover, the receivers will combine their information.
"2. Suppose further the position of the different bits must differ by an odd number, e.g., 1, 3, 5, 7, 9. In this situation, can you safely send 8 data bits out of every 10 bits transmitted?
"3. What if the offset is known to be 4 bits?"
"4. Can you do as well if you don't know the offset?"
Dr. Ecco was able to solve all but the fourth one.
Jeanne Boyarsky and Michael Birken both improved on my solution to The Luck of the 4. Jeanne showed that 36 could be computed with three 4s: 4×(4/.4R). Birken went further, finding a very suggestive "unfindable" phone number in the 315 area code. He also showed that 36 out of the first 40 numbers could be done with just three 4s. This included such remarkable insights as that 37 can be rendered as: ((!4)+(√[.4R]))/(√[.4R])=(74/3)×(3/2).
DDJ