Error-correcting codes with feedback: Difference between revisions

Revision as of 14:55, 5 December 2007

Revision as of 18:59, 5 December 2007

Line 5:

{{Unreferenced|date=September 2007}}

In [[mathematics]], [[computer science]], [[telecommunication]], [[information theory]], and [[searching theory]], '''error-correcting codes with noiseless feedback''' hasrefers great practical importance. Anto [[error correcting codecodes]] withdesigned noiselessto feedbackwork isin equivalentthe topresence anof [[adaptivefeedback search]]ingfrom strategythe withreceiver errors.to the sender.

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 [[coding theory|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 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>

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.

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

An error-correcting code with noiseless feedback is equivalent to an adaptive [[search]]ing strategy with errors.<ref name="deppe" />

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 questionquestions to determine the answer. In 1964 [[Elwyn Berlekamp]] considered in his dissertation error correcting codes with noiseless feedback.<ref name="deppe">{{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 provides a means for communication a message over a noisy channel. 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.