Paul’s Puzzler: Mission Possible!
In the last issue of our newsletter we posed the question of a receiver being able to obtain the correct packet after one or more transmissions without any of the transmissions/retransmissions being received correctly. While it may sound like ‘Mission Impossible’, it can be done and here is how.
The general area is known as Incremental Redundancy (IR) as well as Hybrid ARQ. I personally prefer the latter, for a simple reason: It demonstrates the limitation of the “divide and conquer” approach of the Open System Interconnection (OSI) model commonly used when discussing data communications.
The OSI ‘divorces’ the physical layer from the data link layer (also called layers 1 and 2 respectively), while IR ‘marries’ them together. In short, when a packet is received in error (the result of a physical layer failure), clearly not all bits are wrong. In fact most bits are right, just a few are wrong. When using IR/H-ARQ one decodes the bits using “soft decoding”. All that means is that not only does the receiver attempt to determine if a given bit is a 0 or a 1, but it also assigns a level of confidence in its decision. If the packet is determined to be corrupted, it is still kept in the receiver’s memory—and it’s important to note that what’s kept is the packet’s ‘soft version’, i.e., the value of each bit along with the assigned confidence in its value. A retransmission is usually accompanied by a different, sometimes ‘incremental’ form of error control coding (that is redundancy) and the receiver attempts to decode the new version, again, soft decode it. The physical layer will often fail us again, resulting in a corrupted packet. However, the two versions are then “soft combined” and while it is very likely that both transmissions contain some errors, it is also very likely that the combined version is error-free! Thus neither transmission is ok, but we got the right packet! Of course, if the mission is not quite accomplished with two transmissions, we can keep trying.
This concept has been implemented for the first time in mobile communications in EDGE. It’s employed in UMTS/HSDPA/HSUPA and cdma2000/EVDO and, needles to say, also in WI-FI and WiMAX. You may ask why it was not implemented sooner. The answer is: Computers! As you can probably imagine, it takes a fair amount of storage and processing speed, neither of which was available in the earlier days of mobile communications. It is the convergence of computing technology with communications engineering that has made the idea practical at this time.
By the way, did you figure out how to deal with the twin brothers at the intersection?
Yes, it is possible to get the job done with only ten bucks, and thus getting the right answer without ever knowing if it is provided by the truth teller or the liar! You just ask, “If I were to ask your brother which way it is to NYC, which way would he point? Whichever way the twin points leads to Boston and the other, to NYC. You know the answer, you still don’t know if you’ve stumbled on the truth teller or the prevaricator!