Error-correcting codes with feedback: Difference between revisions

Revision as of 18:21, 9 January 2013

Revision as of 19:46, 10 June 2013

Line 11:

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 [[Adaptive algorithm|adaptive]] [[search]]{{dn|date=June 2013}} strategy with errors.<ref name="standard" />

== History ==

In 1956, [[Claude Shannon]] introduced the [[Discrete signal|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 minimum number of randomly chosen questions to determine the answer.

Line 22 ⟶ 21:

* {{citation|first=Christian|last=Deppe|chapter=Coding with Feedback and Searching with Lies|series=Bolyai Society Mathematical Studies| 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}}.

* {{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|publisher=Cambridge Univ. Press|___location=Cambridge}}.

==References==

{{reflist}}

Line 29:

[[Category:Error detection and correction]]

{{signal-processing-stub}}