Error-correcting codes with feedback: Difference between revisions

Revision as of 14:55, 5 December 2007

Latest revision as of 06:16, 24 July 2025

(29 intermediate revisions by 22 users not shown)

Line 1:

<!-- Please do not remove or change this AfD message until the issue is settled -->

{{AfDM|page=Error correcting codes with feedback|date=2007 November 28|substed=yes}}

<!-- For administrator use only: {{oldafdfull|page=Error correcting codes with feedback|date=28 November 2007|result='''keep'''}} -->

<!-- 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 noiseless feedback''' has great practical importance. Anare [[error correcting codecodes]] withdesigned noiselessto work in the presence of feedback isfrom equivalentthe receiver to anthe [[adaptivesender.<ref search]]ingname="standard">See strategy{{Harvnb|Deppe|2007}} withand errors{{Harvnb|Hill|1995}}. </ref>

{{Unreferenced|date=September 2007}}

In [[mathematics]], [[computer science]], [[telecommunication]], [[information theory]], and [[searching theory]], '''error-correcting codes with noiseless feedback''' has great practical importance. An [[error correcting code]] with noiseless feedback is equivalent to an [[adaptive search]]ing strategy with errors.

== Problem ==

In 1956 [[Claude Shannon]] introduced the discrete memoryless channel with noiseless feedback.

In 1961 [[Alfréd Rényi]] introduced the Bar-Kochba game with a given percentage of wrong answers and calculated the minimimum number of randomly chosen question to . In 1964 [[Elwyn Berlekamp]] considered in his dissertation error correcting codes with noiseless feedback.<ref>{{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>

Alice (the sender) wishes to send a value ''x'' to Bob (the receiver). The communication channel between Alice and Bob is imperfect, and can introduce errors.

==The Bar-Kochba game==

[[Bar-Kochba]] was a Jewish leader who led a revolt against the Roman Empire in 132 CE. Bar Kokhba was once presented a mutilated man, who had his tongue ripped out and hands cut off. Bar Kokhba managed to find out who his attackers were by asking a series of question to which the man could either nod or shake is head. A modern form of this game is [[Twenty Questions]].

== Solution ==

The Bar-Kochba game provides a means for communication a message over a noisy channel. Berlekamp 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.

An error-correcting code is a way of [[coding theory|encoding]] ''x'' as a message such that Bob will successfully understand the value ''x'' as intended by Alice, even if the message Alice sends and the message Bob receives differ. In an error-correcting code with feedback, the channel is [[Two-way communication|two-way]]: Bob can send feedback to Alice about the message he received.

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

==References==

== History ==

{{reflist}}

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.

TheIn Bar-Kochbahis game1964 providesdissertation, a[[Elwyn meansBerlekamp]] forconsidered communicationerror acorrecting messagecodes overwith anoiseless noisy channelfeedback. <ref>{{Harvnb|Berlekamp|1964}}.</ref><ref>{{Harvnb|Deppe|2007}}.</ref> approachIn wasBerlekamp's to havescenario, the receiver choosechose a subset of possible messages and askasked the sender whether the given message was in this subset, a 'yes/' or 'no' answer. Based on this answer, the receiver then chooseschose a new subset and repeated the process is repeated. The game is further complicated as due to noise that; some of the answers will be wrong.

==See also==

*[[Noisy channel coding theorem]]

==References==

{{signal-processing-stub}}

{{reflist}}

==Sources==

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

In* 1961 [[Alfréd Rényi]] introduced the Bar-Kochba game with a given percentage of wrong answers and calculated the minimimum number of randomly chosen question to . In 1964 [[Elwyn Berlekamp]] considered in his dissertation error correcting codes with noiseless feedback.<ref>{{citation|authorfirst=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, |editor2=Gyula O.H. Katona, and |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-7027–70}}</ref>.

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

[[Category:Information theory]]

[[Category:Mathematics]]