Error-correcting codes with feedback: Difference between revisions

Revision as of 15:23, 3 November 2010

Revision as of 18:21, 9 January 2013

Line 15:

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