|
<!-- Please do not remove or change this AfD message until the issue is settled -->
{{AfDM|page=Error correcting codes with feedback|date=2007 November 28|substed=yes}}
<!-- For administrator use only: {{oldafdfull|page=Error correcting codes with feedback|date=28 November 2007|result='''keep'''}} -->
<!-- End of AfD message, feel free to edit beyond this point -->
In [[mathematics]], [[computer science]], [[telecommunication]], [[information theory]], and [[searching theory]], '''error-correcting codes with feedback''' are [[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>
{{Unreferenced|date=September 2007}}
{{tone}}
{{Wikify|date=September 2007}}
== Problem ==
In [[mathematics]], [[computer science]], telecommunication, information theory, and searching theory '''error-correcting codes with noiseless feedback''' has great practical importance. An error correcting code with noiseless feedback is equivalent to an adaptive searching strategy with errors.
In the vast literature regarding this
problem, many papers simultaneously deal with
various sorts of restrictions on the searching/coding protocol.
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.
R\'enyi reported the following story about the Jew Bar Kochba in 135 CE, who defended his fortress against the Romans.
== Solution ==
"It is also said that Bar Kochba sent out a scout to the Roman camp who
An error-correcting code is a way of [[coding theory|encoding]] ''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 communication|two-way]]: Bob can send feedback to Alice about the message he received.
was captured and tortured, having his tongue cut out. He escaped from
captivity and reported back to Bar Kochba, but being unable to talk,
he could not tell in words what he had seen. Bar Kochba accordingly
asked him questions which he could answer by nodding or shaking his
head. Thus he acquired from his mute scout the information he needed
to defend the fortress. It occurred to me that, if the story of Bar
Kochba were true, then he would have been the forefather of
information theory."
== Noisy feedback ==
At the beginning of the 20th
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.
century the so-called Bar-Kochba game was very popular in Budapest.
In this game, one player has to find out, by asking yes/no-questions,
what the second player has in mind.
In 1956 Shannon introduced the discrete memoryless
channel with noiseless feedback. He proved that the forward capacity is the
same as without feedback, but the zero-error capacity is in some cases
bigger with feedback than without.
In 1961 R\'enyi introduced the Bar-Kochba game with a
given percentage of wrong answers. He described a sequential and a
non-sequential version of the game in the introduction of the
paper. He solved the non-sequential problem to find the minimal number
of questions to determine the searched number with a certain
probability, if the answers are correct with a given
probability and the questions are chosen at random. He also remarked
that the problem is connected with the coding problem in information
theory.
In 1964 Berlekamp considered in his dissertation error correcting codes with noiseless feedback.
An error-correcting code with '''noiseless feedback''' is equivalent to an [[Adaptive algorithm|adaptive]] [[search algorithm|search]] strategy with errors.<ref name="standard">See {{Harvnb|Deppe|2007}} and {{Harvnb|Hill|1995}}.</ref>
A sender wants to transmit a message $x\in {\cal X}$ over
a noisy binary channel. ${\cal X} = \left\{1,\dots,N\right\}$ denotes
the set of possible messages
and $Y~=~\left\{~0,1~\right\}$ the binary coding alphabet. We have a passive feedback,
that means that the sender always knows what has been received. The codewords
are elements of $Y^n$ and a codeword is in the form of :
$c\left(x,y^{n-1}\right)=\left(c_1\left(x\right), \dots,c_n\left(x,y^{n-1}\right)\right)$, where $c_i:{\cal X} \times Y^{i-1} \to Y$
is a function for the $i$-th code letter which depends on the message we want to
transmit and the $(i-1)$ bits which have been received before. We suppose that the
noise does not change more than $l\in \N_0$ bits of a codeword.
Berlekamp's idea was to consider each transmission as the following
quiet-question-noisy-answer-game:
The sender and the receiver have a
common partition strategy. After the sender has chosen a message, the
receiver chooses a subset $S$ of the set of messages and asks if the message
was among the subset $S$ $(S\subset {\cal X})$. The sender sends ``1" for yes and
``0" for no over the noisy channel. Then the receiver chooses a new subset
where his choice depends on the answer etc. . The receiver
tries to get the message with $n$ questions and a jammer (the noise) wants
to avoid this by changing at most $l$ answers.
== History ==
Later in 1976 Ulam suggested
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.
independently an interesting two-person search
game:
In his 1964 dissertation, [[Elwyn Berlekamp]] considered error correcting codes with noiseless feedback.<ref>{{Harvnb|Berlekamp|1964}}.</ref><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.
"Someone thinks of a number between one and one
million. Another person is allowed to ask up to twenty questions, to
each of which the first person is supposed to answer only yes or no.
Now suppose one were allowed to lie once or twice, then how many questions would one need
to get the right answer."
==See also==
Obviously this binary sequential
*[[Noisy channel coding theorem]]
search problem with errors is equivalent to Berlekamp's
quiet-question-noisy-answer-game and to the Bar-Kochba game with lies.
==References==
Ulam raised this problem in 1976; that was twelve years after
{{reflist}}
Berlekamp considered
the block coding with feedback and fifteen years after R\'enyi's
==Sources==
paper.
* {{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 }}
At first the authors did not remember
* {{citation|first=Christian|last=Deppe|chapter=Coding with Feedback and Searching with Lies|series=Bolyai Society Mathematical Studies| volume = 16|editor=Imre Csiszár |editor2=Gyula O.H. Katona |editor3=Gabor Tardos|title=Entropy, Search, Complexity|publisher=Springer |doi=10.1007/978-3-540-32777-6_2 |chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-32777-6_2 |year=2007 |isbn=978-3-540-32573-4|pages=27–70}}.
that the problem was much earlier known and have been considered by
* {{citation|first=Ray|last=Hill|chapter=Searching with lies |series=London Mathematical Society Lecture Note Series |title=Surveys in Combinatorics |volume=218 |pages=41–70 |chapter-url=https://archive.org/details/surveysincombina0000unse/page/41 |year=1995|isbn=0-521-49797-3|publisher=Cambridge University Press |url={{GBurl|rbjGGtvkxUkC|pg=PP1}} }}.
Berlekamp and R\'enyi. For this reasons it is called the Ulam-R{\'e}nyi game.
In 1992 Spencer presented another aspect of Ulam-R{\'e}nyi's game.
He considered the following two person
game. We take a board with two columns and $l+1$ rows.
The rows are numbered from $l$ to 0 and the columns
by two and one.
A field with some chips on it corresponds to every row. Each round of the game is played in
three steps.
At the first step Paul distributes the chips of the field on the corresponding columns. At the
second step Carole chooses one column. All chips in this column are shifted by
one row down.
The chips in row 0
and the selected column are removed.
At step three all chips of one row are taken on its
corresponding field. Then the round is finished.
The game is terminated if every chip up to one is removed.
The aim of Carole is to get the number of rounds
as large as possible whereas Paul wants to get a small number of rounds.
Also this game is equivalent to the Ulam-R{\'e}nyi
game. Throughout this paper we shall call Carole and Paul the two
players. This idea goes back to Spencer, who also explained:
Paul corresponds to Paul
Erd\"os, who always asked questions and Carole corresponds to an ORACLE, whose
answers need to be wisely evaluated.
[[Category:Error detection and correction]]
[[Category:Information theory]]
| 