Error-correcting codes with feedback
In
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,
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
- ^ a b See Deppe 2007 and Hill 1995.
- ^ Berlekamp 1964.
- ^ 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, 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.