Error-correcting codes with feedback
- Error-correcting codes with feedback
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.[See Harvnb|Deppe|2007 and Harvnb|Hill|1995.] ]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 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.
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.
An error-correcting code with noiseless feedback is equivalent to an adaptive searching strategy with 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. [Harvnb|Deppe|2007.]
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.
ources
*.
*.
References
ee also
*Noisy channel coding theorem
Wikimedia Foundation.
2010.
Look at other dictionaries:
Forward error correction — In telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding[1] is a technique used for controlling errors in data transmission over unreliable or noisy communication channels. The central idea is… … Wikipedia
Reed–Solomon error correction — Reed Solomon error correction is an error correcting code that works by oversampling a polynomial constructed from the data. The polynomial is evaluated at several points, and these values are sent or recorded. Sampling the polynomial more often… … Wikipedia
List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… … Wikipedia
Block cipher modes of operation — This article is about cryptography. For method of operating , see modus operandi. In cryptography, modes of operation is the procedure of enabling the repeated and secure use of a block cipher under a single key.[1][2] A block cipher by itself… … Wikipedia
Coding theory — is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error correction and more recently also for network coding. Codes are studied by various scientific… … Wikipedia
Hard disk drive — Hard drive redirects here. For other uses, see Hard drive (disambiguation). Hard disk drive Mechanical interior of a modern hard disk drive Date invented 24 December 1954 [1] … Wikipedia
cryptology — cryptologist, n. cryptologic /krip tl oj ik/, cryptological, adj. /krip tol euh jee/, n. 1. cryptography. 2. the science and study of cryptanalysis and cryptography. [1635 45; < NL cryptologia. See CRYPTO , LOGY] * * * Introduction … Universalium
Claude Berrou — (born September 23, 1951, Penmarch) is a French professor in electrical engineering at École Nationale Supérieure des Télécommunications de Bretagne, now Telecom Bretagne. He is the coinventor with Alain Glavieux in 1991 (and Punya Thitimajshima… … Wikipedia
computer — computerlike, adj. /keuhm pyooh teuhr/, n. 1. Also called processor. an electronic device designed to accept data, perform prescribed mathematical and logical operations at high speed, and display the results of these operations. Cf. analog… … Universalium
Nakagami fading — Unfortunately, mobile radio links are subject to severe multipath fading due to the combination of randomly delayed, reflected, scattered, and diffracted signal components. Fading leads to serious degradation in the link carrier to noise ratio… … Wikipedia
