, computer science
, information theory
, and searching theory
, error-correcting codes with feedback
refers to error correcting codes
designed to work in the presence of feedback from the receiver to the sender.
Alice (the sender) wishes to send a value x
to Bob (the receiver). The communication channel between Alice and Bob is imperfect, and can introduce errors.
An error-correcting code is a way of encoding x
as a message such that Bob will successfully understand the value x
as intended by Alice, even if the message Alice sends and the message Bob receives differ. In an error-correcting code with feedback, the channel is two-way
: Bob can send feedback to Alice about the message he received.
In an error-correcting code without noisy feedback
, the feedback received by the sender is always free of errors. In an error-correcting code with noisy feedback
, errors can occur in the feedback, as well as in the message.
An error-correcting code with noiseless feedback
is equivalent to an adaptive search
strategy with errors.
In 1956, Claude Shannon
introduced the discrete memoryless
channel with noiseless feedback. In 1961, Alfréd Rényi
introduced the Bar-Kochba game
(also known as Twenty questions
), with a given percentage of wrong answers, and calculated the minimum number of randomly-chosen... Read More