CS 3343/3341
 Analysis of Algorithms 
Spring 2012
Weird Topic
  Transmitting Half a Bit, Part 1  

Joke (before talking about halves of a bit, here's a joke about thirds of a cigarette):

A bum can make a cigarette out of 3 butts. After smoking it, he will have 1 butt left over.

How many smokes can he get from 10 butts? Answer: 5.

Well, from the 10, he takes 9 butts to make 3 cigarettes and smokes them. This leaves 4 butts. He makes another cigarette out of 3 of the 4 butts and smokes it. Now he has 2 butts left. He's had only 4 smokes. What to do?

Puzzle: A man takes two kinds of medicine: A and B. Each day he must take one pill from the A bottle and one from the B bottle. He must take exactly one pill of each type, neither more nor less.

One day he dumps out one A pill and then tries to dump one B pill, but spills out two Bs instead. The three pills are mixed together on the table. He soon realizes that both kinds of pill are identical round white tablets. He can't tell them apart. To make matters worse, the pills are very expensive, and he mustn't waste any of them. He stares at the three identical looking white pills, one A and two Bs. What can he do?

Transmitting Half a Bit at a Time: Suppose we have a sequence of message bits ready for transmission. Look at the first two message bits taken together. Depending on what these bits are, we send a message of the form: "The first two bits are not 10", assuming this is true. We are saying that the first two bits are not a "1" followed by a "0". The remaining combinations are still possible for these two bits, namely "00", "01", or "11". So we've eliminated one-fourth of the four possibilities for two bits. That's sort of like sending half a bit. Of the remaining possibilities above, suppose the second transmission is: "not 00". Then only "10" and "11" are still possible, so we have revealed that the first bit is a "1" with two transmissions. If instead the second transmission is "not 11", then the remaining possibilities are "00" and "10", so in this case we reveal that the second bit is a "0", while the first bit remains unknown. Once again we have transmitted a single bit with two transmissions, although in this case it was the second message bit, leaving the first still to be transmitted.

Here is a table that illustrates the above process:

Handling Two Message Bits: Input is either 00, 01, 10, or 11
First
Transmission		Possiblities
Remaining		 Second
Transmission		Possiblities
Remaining		 Meaning
not 01 00
10
11 		not 00 10
11		 1st bit is "1"
not 11 00
10		 2nd bit is "0"
not 10 00
01
11 		not 00 01
11		 2nd bit is "1"
not 11 00
01		 1st bit is "0"

In the table below, the process above has been made into an algorithm. The algorithm may use random numbers to decide what to send, so the transmissions are not unique. The original message bits are always recovered exactly by this process.

Algorithm: Sending information half-a-bit at a time.
Input: A sequence of message bits: m0, m1, m2, m3, ...
Output: A sequence of 1-bit transmissions, two for each message bit: s0, t0, s1, t1, s2, t2, ...

Method: Take the first two message bits, m0 m1:

First 1-bit transmission, s0:

    if m0 m1 == 01 then
    transmit("not 10");
    else if m0 m1 == 10 then
    transmit("not 01");
    else choose one of transmit("not 01") and transmit("not 10") with equal probability.
      [transmit("not 01") is represented by s0 = "0", and transmit("not 10") by s0 = "1]

Second 1-bit transmission, t0:

    if m0 m1 == 11 then
    transmit("not 00");
    else if m0 m1 == 00 then
    transmit("not 11");
    else choose one of transmit("not 00") and transmit("not 11") with equal probability.
      [transmit("not 00") is represented by t0 = "0", and transmit("not 11") by t0 = "1]

After the two 1-bit transmissions, the receiver knows the value of either m0 or m1.
The receiver has no information about the other bit.
Whichever it is, add m2 to the unknown bit and process these two as above.

With each pair of transmissions, the receiver learns the value of another message bit. It's possible for a single message bit's value to be left unknown while later bits are revealed. At the end of the message, the last value or last deferred value must be revealed directly (without this algorithm).

Revision date: 2011-12-05. (Please use ISO 8601, the International Standard Date and Time Notation.)