In mathematics,

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...

telecommunication Telecommunication is the transmission of information by various types of technologies over wire, radio, optical, or other electromagnetic systems. It has its origin in the desire of humans for communication over a distance greater than tha ...

information theory Information theory is the scientific study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. ...

, and

searching theory In microeconomics, search theory studies buyers or sellers who cannot instantly find a trading partner, and must therefore search for a partner prior to transacting. Search theory clarifies how buyers and sellers choose when to acknowledge a co ...

, error-correcting codes with feedback refers to

error correcting codes In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...

designed to work in the presence of feedback from the receiver to the sender.See and .

Problem

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.

Solution

An error-correcting code is a way of

encoding In communications and information processing, code is a system of rules to convert information—such as a letter (alphabet), letter, word, sound, image, or gesture—into another form, sometimes data compression, shortened or secrecy, secret ...

''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: 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

search Searching or search may refer to: Computing technology * Search algorithm, including keyword search ** :Search algorithms * Search and optimization for problem solving in artificial intelligence * Search engine technology, software for findi ...

strategy with errors.See and .

History

In 1956,

Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American mathematician, electrical engineer, and cryptographer known as a "father of information theory". As a 21-year-old master's degree student at the Massachusetts In ...

introduced the

discrete Discrete may refer to: *Discrete particle or quantum in physics, for example in quantum theory *Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit *Discrete group, a ...

memoryless In probability and statistics, memorylessness is a property of certain probability distributions. It usually refers to the cases when the distribution of a "waiting time" until a certain event does not depend on how much time has elapsed alread ...

channel with noiseless feedback. In 1961,

Alfréd Rényi Alfréd Rényi (20 March 1921 – 1 February 1970) was a Hungarian mathematician known for his work in probability theory, though he also made contributions in combinatorics, graph theory, and number theory. Life Rényi was born in Budapest ...

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 Elwyn Ralph Berlekamp (September 6, 1940 – April 9, 2019) was a professor of mathematics and computer science at the University of California, Berkeley.Contributors, ''IEEE Transactions on Information Theory'' 42, #3 (May 1996), p. 1048. DO10. ...

considered error correcting codes with noiseless feedback.. 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.

Sources

* . * .

References