Friday, July 23, 2010

The other Blackwell channel

In memory of the late David Blackwell (see obits here and here), I'd like to talk about the Blackwell channel. Not this one, which is the one everyone thinks of, but the other one -- otherwise known as the trapdoor channel, the billiard-ball channel, or the chemical channel. (Find me another information theorist with two channels named after them.)

The channel works like this. Information is transmitted using coloured balls (red to represent 0 and black to represent 1, say). The "channel" is a bag containing a single (red or black) ball. At each channel use, the transmitter inserts a single ball into the bag, and the receiver then removes one of the two balls, selecting uniformly at random between the two. It should be obvious that this model can be generalized in various ways.

Blackwell proposed this model in his 1961 book as an example of a channel with memory: the channel output is clearly dependent on prior channel inputs. Remarkably for such a simple model, capacity is still unknown. As far as I know, the best result is the channel capacity with feedback, found by Permuter et al. to be the logarithm of the golden ratio. Since the transmitter is free to disregard the feedback, this must also be an upper bound on the capacity without feedback.

This channel also admits zero-error codes. For example, even if the initial channel state is unknown, a threefold repetition code (i.e., red, red, red or black, black, black) can be decoded without errors, since there can be at most one wrong-coloured ball at the output; thus, the zero-error capacity is (trivially) at least 1/3. Zero-error capacity is also an open problem for this channel.

No comments: