Error-correcting codes with feedback: Difference between revisions

Revision as of 23:13, 1 December 2007

Revision as of 21:39, 2 December 2007

Line 8:

{{Wikify|date=September 2007}}

{{copyvio|url=Coding with Feedback and Searching with Lies, Springer-Verlag (see [[Wikipedia:Articles for deletion/Error-correcting codes with feedback]])}}

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 search]]ing strategy with errors. In the vast literature regarding this problem, many papers simultaneously deal with various sorts of restrictions on the searching/coding protocol.

[[Alfréd Rényi]] reported the following story about the Jew [[Bar Kochba]] in 135 CE, who defended his fortress against the Romans.

<blockquote>It is also said that Bar Kochba sent out a scout to the Roman camp who

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

At the beginning of the 20th 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 [[Claude 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ényi 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 [[Elwyn Berlekamp]] considered in his dissertation error correcting codes with noiseless feedback.

A sender wants to transmit a message <math>x\in \mathcal{X}</math> over

a noisy binary channel. <math>\mathcal{X} = \left\{1,\dots,N\right\}</math> denotes

the set of possible messages

and <math>Y~=~\left\{~0,1~\right\}</math> 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 <math>Y^n</math> and a codeword is in the form of:

:<math> c\left(x,y^{n-1}\right)=\left(c_1\left(x\right),\ldots,c_n\left(x,y^{n-1}\right)\right),</math>

where

:<math> c_i : \mathcal{X} \times Y^{i-1} \to Y</math>

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 <math>l\in \N_0</math> 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'' <math>(S\subset \mathcal{X})</math>. 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.

Later in 1976 [[Stanislaw Ulam]] suggested independently an interesting two-person search game, also called ''[[Ulam's game]]'':

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

Obviously this binary sequential

search problem with errors is equivalent to Berlekamp's

quiet-question-noisy-answer-game and to the Bar-Kochba game with lies.

Ulam raised this problem in 1976; that was twelve years after

Berlekamp considered the block coding with feedback and fifteen years after R\'enyi's

paper. At first the authors did not remember that the problem was much earlier known and have been considered by Berlekamp and Rényi. For this reasons it is called the Ulam-Rényi game.

In 1992 [[Joel Spencer]] presented another aspect of Ulam-Ré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é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ős]], who always asked questions and Carole corresponds to an [[ORACLE (computer)|ORACLE]], whose answers need to be wisely evaluated.

[[Category:Error detection and correction]]

[[Category:Information theory]]