Error-correcting codes with feedback: Difference between revisions

Revision as of 06:11, 2 September 2010

Revision as of 15:23, 3 November 2010

Line 1:

{{Copyedit|for=grammar|date=January 2009}}

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>

== Problem ==

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 swill 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.

we

In an error-correcting code with '''noisy feedback''', the feedback the sender receives is always free of errors. In an error-correcting code with 'a''noisy feedback''', errors can occur in the feedback as well as in the message.

s

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

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.

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>

== Solution ==

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.

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

In an error-correcting code withwithout '''noisy feedback''', the feedback received by the sender receives is always free of errors. In an error-correcting code with 'a''noisy feedback''', errors can occur in the feedback, as well as in the message.

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

== History ==

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

==Sources==