Paul’s Puzzler: Mission Impossible!
Here’s a quick one for you packet switching, layer 2 experts. Let’s see how long it takes you to answer the following:
- If a transmitted packet is received in error, how does the receiver know, at least with a very high probability, that it is (a) correct or (b) corrupted (contains some erroneous bits)?
- From your data communications background, what does the receiver do with a corrupted packet?
- How does the receiver end up receiving the correct packet?
And, here are the answers:
- A Cyclic Redundancy Checks (CRC) is typically used to determine if a packet is received correctly. Recall that if the received packet fails the CRC, it is guaranteed to be erroneous. If it passes, there’s a very high probability – though not quite 100% — that it is correct. In this case, it’s nevertheless treated as being correct. Thus the concept of “the probability of undetectable error.”
- The erroneously received packet is typically discarded, and layer 2 invokes the retransmission strategy.
- The transmitter, having been told of the failure to correctly receive the packet, retransmits it. The process is repeated until, in principle, the packet is received correctly.
Which brings me to the question of the day: Can the receiver obtain the correct packet after one or more retransmissions, without it ever being received correctly? This may seem like “Mission Impossible”. To figure out whether it is or not, we’ll consider a brain teaser. You may have run into a version of this teaser before, but here is the version suited to the discussion of the problem at hand.
A road divides into a fork, with one branch leading to New York and the other, to Boston. There are no signs or other landmarks, except for two identical twins who will answer any well-defined binary question for ten bucks a question. However, there’s a catch. One of the twins always tells the truth, while the other always lies. And of course you don’t know who’s who. So here’s our question: Can you determine which road leads to which city without ever discerning the twins’ identity?
By spending $10 you can ask a question to which you already know the answer, e.g., “Does the sun rise in the East?” If the answer is “Yes”, you know you’ve stumbled onto the truth teller. If “No”, you know you’ve got the fibber. Ten bucks well spent! Now, for another ten dollars you ask the same person, “Which way is it to NYC?” Having already determined who’s who, you will know exactly how to interpret the answer. So for a $20 investment you know everything you wanted to know—and a little bit more, since we had never particularly cared to tell the twins apart.
The real question, though, is that of finding the way to NYC and Boston for only $10, i.e., with a single question. Can we do it and still not know which twin is which? I am not saying that it is doable, but here is the problem:
- If you believe it is doable, what’s the question that will get the job done?
- If you don’t think so, can you prove that in fact two questions are the minimum required?
By now you’re probably wondering what this has to do with CRC’s and the like. Well, it may seem like finding out which way is which with only one question (and getting the correct packet without ever having a successful transmission/reception) are “Mission Impossible”. But they actually are a “Mission Possible”! For an answer to how both of these apparently impossible feats can be accomplished, tune in next week.
Editor’s Note: Dr. Paul Kakaes, one of our industry’s master trainers, is teaching the coming WebLive classes on OFDM/MIMO (Dec 9) and LTE (Dec 10-11). Read bio.