Content deleted Content added
→Sources: tweak cites |
Removed {{Merge}} tag |
||
| (4 intermediate revisions by 3 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
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.
==
*[[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}} }}.▼
==References==
{{reflist}}
==
* {{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]]
| |||