Error-correcting codes with feedback

In mathematics, computer science, telecommunication, information theory, and searching theory, error-correcting codes with noiseless feedback has great practical importance. An error correcting code with noiseless feedback is equivalent to an adaptive searching 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 with a given percentage of wrong answers and calculated the minimimum number of randomly chosen question to . In 1964 Elwyn Berlekamp considered in his dissertation error correcting codes with noiseless feedback.^[1]

The Bar-Kochba game

Bar-Kochba was a Jewish leader who led a revolt against the Roman Empire in 132 CE. Bar Kokhba was once presented a mutilated man, who had his tongue ripped out and hands cut off. Bar Kokhba managed to find out who his attackers were by asking a series of question to which the man could either nod or shake is head. A modern form of this game is Twenty Questions.

The Bar-Kochba game provides a means for communication a message over a noisy channel. Berlekamp 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.

References

1. Christian Deppe (2007), "Coding with Feedback and Searching with Lies", in Imre Csiszár, Gyula O.H. Katona, and Gabor Tardos (ed.), Entropy, Search, Complexity, Bolyai Society Mathematical Studies, vol. 16, Berlin-Heidelberg: Springer, pp. 27–70, doi:10.1007/978-3-540-32777-6, ISBN 978-3-540-32573-4, ISSN 1217-4696

See also

• Noisy channel coding theorem