Error-correcting codes with feedback

From Wikipedia, the free encyclopedia

The grammar of this article or section needs to be improved.
Please do so in accordance with Wikipedia's style guidelines.

In mathematics, computer science, telecommunication, 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.^[1]

The main scenario imagined is the following. Suppose that Alice wishes to send a value x to Bob, but 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 where Bob will successfully understand the value x even if the message Alice sends and the message Bob receives are not exactly the same. In an error-correcting code with feedback, the channel is two-way, where Bob can send feedback to Alice about the message he received.

In an error-correcting code with noiseless feedback, the feedback the sender receives 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 searching strategy with errors.^[1]

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 minimimum number of randomly chosen questions to determine the answer. In 1964 Elwyn Berlekamp considered in his dissertation error correcting codes with noiseless feedback.^[2]

Berlekamp's approach was to have the receiver choose a subset of possible messages and ask the sender whether the given message was in this subset, a yes/no answer. Based on this answer the receiver then chooses a new subset and the process is repeated. The game is further complicated as due to noise that some of the answers will be wrong.

[edit] Sources

Deppe, Christian (2007), “Coding with Feedback and Searching with Lies”, in Imre Csiszár, Gyula O.H. Katona, and Gabor Tardos, Entropy, Search, Complexity, vol. 16, Bolyai Society Mathematical Studies, Berlin-Heidelberg: Springer, pp. 27-70, ISBN 978-3-540-32573-4, ISSN 1217-4696, DOI 10.1007/978-3-540-32777-6 .
Hill, Ray (1995), Searching with lies, Cambridge London Mathematical Society Lecture Note Series, Surveys in Combinatorics, pp. 41-70, ISBN 0-521-49797-3 .