Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Parallel

Jam Session


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].


Solution to March Dr. Ecco


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.

Reader Solutions to "The Luck of the 4"

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


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.