Error-correcting codes with feedback: Difference between revisions

Revision as of 02:37, 30 November 2007

Revision as of 08:37, 30 November 2007

Line 23:

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\'enyiRé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{\cal X}$</math> over

a noisy binary channel. $<math>\mathcal{\cal 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), \dotsldots,c_n\left(x,y^{n-1}\right)\right),</math>

: <math> c\left(x,y^{n-1}\right)=\left(c_1\left(x\right), \dots,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

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

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.

is a function for the $i$-th code letter which depends on the message we want to

Berlekamp's idea was to consider each transmission as the following quiet-question-noisy-answer-game:

transmit and the $(i-1)$ bits which have been received before. We suppose that the

: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

noise does not change more than $l\in \N_0$ bits of a codeword.

was among the subset $''S$'' $<math>(S\subset \mathcal{\cal X})$</math>. The sender sends ``1" for yes and

Berlekamp's idea was to consider each transmission as the following

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.

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.

Later in 1976 [[Stanislaw Ulam]] suggested independently an interesting two-person search game:

Line 65 ⟶ 56:

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.

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

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.

paper.

The rows are numbered from $''l$'' to 0 and the columns by two and one.

At first the authors did not remember

that the problem was much earlier known and have been considered by

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

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}nyiRényi game.

game. Throughout this paper we shall call Carole and Paul the two

players. This idea goes back to Spencer, who also explained:

Erd\"osPaul corresponds to [[Paul Erdős]], who always asked questions and Carole corresponds to an [[ORACLE (computer)|ORACLE]], whose answers need to be wisely evaluated.

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]]