Precise coding with noiseless feedback.

摘要

The construction of block codes for communicating over discrete, noisy channels is a central problem of information theory. A block code is a set of codewords such that if the sender chooses one of the codewords to transmit, and no more than a specified number of errors occur, then the recipient can, with certainty, determine which codeword was sent.; If the recipient is also able to transmit information to the sender, instantly and without error, then the theoretical information capacity of the forward channel is not increased, but our ability to utilize that capacity with a coding scheme is enhanced. Assume a binary forward channel. The reverse channel can be used to transmit to the sender, after each bit is sent, the value of the bit as received by the recipient. The sender can then use that information in deciding what bit to send next; this is the idea of an adaptive block code.; We demonstrate that, for many choices of parameters, adaptive block codes may be constructed that are much better than standard block codes without feedback. For a wide range of parameters, we construct precisely optimal adaptive block codes, which contain the maximum possible number of codewords, given the length of the codes and the number of errors they tolerate.; The construction of adaptive block codes is equivalent to the formulation of strategies for a game described by Ulam, a version of “Twenty Questions” with lies. A corollary to our main result resolves Ulam's open question: given 1,000,000 objects, how many binary questions are required to identify a particular object, when the answerer is permitted to lie a given number of times? Our results are, in fact, much more precise: we show not only that one million objects may be distinguished with a certain number of questions, when a certain number of lies are allowed, but we determine the exact number (greater than one million) of objects that can be so distinguished, for each possible number of allowed lies.