Error-correcting codes with feedback: Difference between revisions

Revision as of 04:56, 22 October 2007

Revision as of 18:41, 10 November 2007

Line 1:

{{Wikify|date=September 2007}}

{{Unreferenced|date=September 2007}}

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

Line 37:

In 1964 Berlekamp considered in his dissertation error correcting codes with noiseless feedback.

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

Line 50:

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 Ulam suggested

Later in 1976 Ulam suggested

independently an interesting two-person search

game:

Line 76 ⟶ 74:

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