Error-correcting codes with feedback

In mathematics, computer science, telecommunication, information theory, and searching theory, error-correcting codes with feedback are error correcting codes designed to work in the presence of feedback from the receiver to the sender.^[1]

Problem

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.

Solution

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.

Noisy feedback

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.^[1]

History

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 questions to determine the answer.

In his 1964 dissertation, Elwyn Berlekamp considered error correcting codes with noiseless feedback.^[2][3] In Berlekamp's scenario, the receiver chose a subset of possible messages and asked the sender whether the given message was in this subset, a 'yes' or 'no' answer. Based on this answer, the receiver then chose a new subset and repeated the process. The game is further complicated due to noise; some of the answers will be wrong.

See also

• Noisy channel coding theorem

References

1. See Deppe 2007 and Hill 1995.
2. Berlekamp 1964.
3. Deppe 2007.

Sources

• Berlekamp, Elwyn R. (1964). Block coding with noiseless feedback (PDF) (PhD). Massachusetts Institute of Technology.
• Deppe, Christian (2007), "Coding with Feedback and Searching with Lies", in Imre Csiszár; Gyula O.H. Katona; Gabor Tardos (eds.), Entropy, Search, Complexity, Bolyai Society Mathematical Studies, vol. 16, Springer, pp. 27–70, doi:10.1007/978-3-540-32777-6_2, ISBN 978-3-540-32573-4.
• Hill, Ray (1995), "Searching with lies", Surveys in Combinatorics, London Mathematical Society Lecture Note Series, vol. 218, Cambridge University Press, pp. 41–70, ISBN 0-521-49797-3.