Error-correcting codes with feedback: Difference between revisions

Revision as of 03:11, 6 October 2023

Latest revision as of 06:16, 24 July 2025

(2 intermediate revisions by 2 users not shown)

Line 1:

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

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 18 ⟶ 19:

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

* {{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 }}

* {{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 |doi=10.1007/978-3-540-32777-6_2 |chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-32777-6_2 |year=2007 |isbn=978-3-540-32573-4|pages=27–70}}.

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

==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 |doi=10.1007/978-3-540-32777-6_2 |chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-32777-6_2 |year=2007 |isbn=978-3-540-32573-4|pages=27–70}}.

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

[[Category:Error detection and correction]]