Error-correcting codes with feedback: Difference between revisions

Revision as of 09:11, 5 December 2007

Revision as of 14:55, 5 December 2007

Line 8:

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.<ref>{{citation|author=Christian Deppe|chapter=Coding with Feedback and Searching with Lies|series=Bolyai Society Mathematical Studies|issn=1217-4696| volume = 16|editor=Imre Csiszár, Gyula O.H. Katona, and Gabor Tardos|title=Entropy, Search, Complexity|publisher=Springer|place=Berlin-Heidelberg|doi=10.1007/978-3-540-32777-6|year=2007|isbn=978-3-540-32573-4|pages=27-70}}</ref>

==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==

{{reflist}}

==See also==

*[[Noisy channel coding theorem]]

{{signal-processing-stub}}