Error-correcting codes with feedback
In , computer science, , , and , error-correcting codes with feedback refers to designed to work in the presence of feedback from the receiver to the sender.
Contents
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 : 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 strategy with errors.
History
In 1956, introduced the channel with noiseless feedback. In 1961, introduced the (also known as ), with a given percentage of wrong answers, and calculated the minimum number of randomly chosen questions to determine the answer.
In his 1964 dissertation, considered error correcting codes with noiseless feedback. 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.
Sources
- .
- .