Error-correcting codes with feedback: Difference between revisions

Revision as of 02:30, 30 November 2007

Revision as of 02:33, 30 November 2007

Line 8:

{{Wikify|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 searchingsearch]]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.

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,

Line 23 ⟶ 20:

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.

At the beginning of the 20th

In 1961 R\'enyi introduced the Bar-Kochba game with a given percentage of wrong answers. He described a sequential and a

century the so-called Bar-Kochba game was very popular in Budapest.

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.

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.

A sender wants to transmit a message $x\in {\cal X}$ over

Line 50 ⟶ 32:

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 :

$: <math> 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$</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