Error-correcting codes with feedback: Difference between revisions

Revision as of 21:03, 16 December 2007

Latest revision as of 06:16, 24 July 2025

(25 intermediate revisions by 20 users not shown)

Line 1:

{{Grammar}}

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

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>

The main scenario imagined is the following. Suppose that Alice wishes to send a value ''x'' to Bob, but the communication channel between Alice and Bob is imperfect, and can introduce errors. An error-correcting code is a way of [[coding theory|encoding]] ''x'' as a message where Bob will successfully understand the value ''x'' even if the message Alice sends and the message Bob receives are not exactly the same. In an error-correcting code with feedback, the channel is two-way, where Bob can send feedback to Alice about the message he received.

== Problem ==

In an error-correcting code with '''noiseless feedback''', the feedback the sender receives 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.

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.

An error-correcting code with noiseless feedback is equivalent to an adaptive [[search]]ing strategy with errors.<ref name="standard" />

== Solution ==

In 1956 [[Claude Shannon]] introduced the 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 minimimum number of randomly chosen questions to determine the answer. In 1964 [[Elwyn Berlekamp]] considered in his dissertation error correcting codes with noiseless feedback.<ref>{{Harvnb|Deppe|2007}}.</ref>

The main scenario imagined is the following. Suppose that Alice wishes to send a value ''x'' to Bob, but the communication channel between Alice and Bob is imperfect, and can introduce errors. An error-correcting code is a way of [[coding theory|encoding]] ''x'' as a message wheresuch that Bob will successfully understand the value ''x'' as intended by Alice, even if the message Alice sends and the message Bob receives are not exactly the samediffer. In an error-correcting code with feedback, the channel is two[[Two-way, wherecommunication|two-way]]: Bob can send feedback to Alice about the message he received.

== Noisy feedback ==

Berlekamp's 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.

In an error-correcting code withwithout '''noiselessnoisy feedback''', the feedback received by the sender receives 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]]ing strategy with errors.<ref name="standard">See {{Harvnb|Deppe|2007}} and {{Harvnb|Hill|1995}}.</ref>

==Notes==

== 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 minimimumminimum number of randomly chosen questions to determine the answer. In 1964 [[Elwyn Berlekamp]] considered in his dissertation error correcting codes with noiseless feedback.<ref>{{Harvnb|Deppe|2007}}.</ref>

In his 1964 dissertation, [[Elwyn Berlekamp's]] approachconsidered waserror tocorrecting havecodes with noiseless feedback.<ref>{{Harvnb|Berlekamp|1964}}.</ref><ref>{{Harvnb|Deppe|2007}}.</ref> In Berlekamp's scenario, 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.

==References==

* {{citation|first=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, 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}}.

==See also==

*[[Noisy channel coding theorem]]

==References==

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

* {{citation|first=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}}.

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

{{signal-processing-stub}}

[[Category:Error detection and correction]]

[[Category:Information theory]]

[[Category:Mathematics]]