Content deleted Content added
Mangojuice (talk | contribs) clarify, further distance text from copyvio version |
Geometry guy (talk | contribs) Add the Hill ref that might be forgotten otherwise |
||
Line 4:
<!-- End of AfD message, feel free to edit beyond this point -->
In [[mathematics]], [[computer science]], [[telecommunication]], [[information theory]], and [[searching theory]], '''error-correcting codes with feedback''' refers to [[error correcting codes]] designed to work in the presence of feedback from the receiver to the sender.<ref name="standard">See {{Harvnb|Deppe|2007}} and {{Harvnb|Hill|1995}}.</ref>▼
▲In [[mathematics]], [[computer science]], [[telecommunication]], [[information theory]], and [[searching theory]], '''error-correcting codes with feedback''' refers to [[error correcting codes]] designed to work in the presence of feedback from the receiver 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.
Line 11 ⟶ 10:
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.
An error-correcting code with noiseless feedback is equivalent to an adaptive [[search]]ing strategy with errors.<ref name="
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 questions to determine the answer. In 1964 [[Elwyn Berlekamp]] considered in his dissertation error correcting codes with noiseless feedback.<ref
▲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 questions 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>
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.
==Notes==
{{reflist}}▼
==References==
* {{citation|first=Christian|last=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}}.
▲{{reflist}}
* {{citation|first=Ray|last=Hill|title=Searching with lies|series=Cambridge London Mathematical Society Lecture Note Series, Surveys in Combinatorics|pages=41-70|year=1995|isbn=0-521-49797-3}}.
==See also==
*[[Noisy channel coding theorem]]
{{signal-processing-stub}}
| |||