Error-correcting codes with feedback: Difference between revisions

Revision as of 05:44, 19 December 2019

Latest revision as of 06:16, 24 July 2025

(6 intermediate revisions by 4 users not shown)

Line 1:

In [[mathematics]], [[computer science]], [[telecommunication]], [[information theory]], and [[searching theory]], '''error-correcting codes with feedback''' refers toare [[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>

== Problem ==

Line 9 ⟶ 10:

== Noisy feedback ==

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 algorithm|search]] strategy with errors.<ref name="standard">See {{Harvnb|Deppe|2007}} and {{Harvnb|Hill|1995}}.</ref>

Line 16 ⟶ 17:

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.

In his 1964 dissertation, [[Elwyn Berlekamp]] considered error correcting codes with noiseless feedback.<ref>{{Harvnb|Berlekamp|1964}}.</ref><ref>{{Harvnb|Deppe|2007}}.</ref> In Berlekamp's scenario, the receiver chose a subset of possible messages and asked the sender whether the given message was in this subset, a 'yes' or 'no' answer. Based on this answer, the receiver then chose a new subset and repeated the process. The game is further complicated due to noise; some of the answers will be wrong.

==SourcesSee also==

*[[Noisy channel coding theorem]]

* {{citation|first=Christian|last=Deppe|chapter=Coding with Feedback and Searching with Lies|series=Bolyai Society Mathematical Studies| volume = 16|editor=Imre Csiszár |editor2=Gyula O.H. Katona |editor3=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=[https://archive.org/details/surveysincombina0000unse/page/41 41–70]|year=1995|isbn=0-521-49797-3|publisher=Cambridge Univ. Press|___location=Cambridge|url=https://archive.org/details/surveysincombina0000unse/page/41}}.

==References==

{{reflist}}

==See alsoSources==

* {{cite thesis |type=PhD |first=Elwyn R. |last=Berlekamp |title=Block coding with noiseless feedback |publisher=Massachusetts Institute of Technology |year=1964 |url=https://dspace.mit.edu/bitstream/handle/1721.1/14783/17010923-MIT.pdf }}

*[[Noisy channel coding theorem]]

* {{citation|first=Christian|last=Deppe|chapter=Coding with Feedback and Searching with Lies|series=Bolyai Society Mathematical Studies| volume = 16|editor=Imre Csiszár |editor2=Gyula O.H. Katona |editor3=Gabor Tardos|title=Entropy, Search, Complexity|publisher=Springer |placedoi=Berlin10.1007/978-Heidelberg3-540-32777-6_2 |doichapter-url=https://link.springer.com/chapter/10.1007/978-3-540-32777-66_2 |year=2007 |isbn=978-3-540-32573-4|pages=27–70}}.

* {{citation|first=Ray|last=Hill|titlechapter=Searching with lies |series=Cambridge London Mathematical Society Lecture Note Series, |title=Surveys in Combinatorics |volume=218 |pages=[41–70 |chapter-url=https://archive.org/details/surveysincombina0000unse/page/41 41–70] |year=1995|isbn=0-521-49797-3|publisher=Cambridge Univ.University Press |___locationurl=Cambridge{{GBurl|urlrbjGGtvkxUkC|pg=https://archive.org/details/surveysincombina0000unse/page/41PP1}} }}.

[[Category:Error detection and correction]]