Error-correcting codes with feedback

Template:Wikify is deprecated. Please use a more specific cleanup template as listed in the documentation.

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.

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

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.

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 ${\displaystyle x\in {\mathcal {X}}}$ over a noisy binary channel. ${\displaystyle {\mathcal {X}}=\left\{1,\dots ,N\right\}}$ denotes the set of possible messages and ${\displaystyle 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 ${\displaystyle Y^{n}}$ and a codeword is in the form of:

${\displaystyle c\left(x,y^{n-1}\right)=\left(c_{1}\left(x\right),\ldots ,c_{n}\left(x,y^{n-1}\right)\right),}$

where

${\displaystyle c_{i}:{\mathcal {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 ${\displaystyle l\in \mathbb {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 ${\displaystyle (S\subset {\mathcal {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.

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

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.

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, whose answers need to be wisely evaluated.