Q-ary Error-Correcting Codes with Feedback

晴彦 金子, Haruhiko Kaneko, 英二 藤原 +1 more

Richard W. Hamming

Ilya Vorobyev, В. В. Лебедев, Alexey Lebedev

In this paper, the problem of correction of a single error in q-ary symmetric channel with noiseless feedback is considered. We propose an algorithm to construct codes with feedback inductively. For all prime power q we prove that two instances of feedback are sufficient to transmit over the q-ary symmetric channel the same number of messages as in the case of complete feedback. Our other contribution is the construction of codes with one-time feedback with the same parameters as Hamming codes for q that is not a prime power. We also construct single-error-correcting codes with one-time feedback of size qn−2for arbitrary q and n ≤ q + 1, which can be seen as an analog for Reed-Solomon codes.

Rudolf Ahlswede, Christian Deppe, Vladimir Lebedev

The two models described in this paper having as ingredients feedback resp. localized errors give possibilities for code constructions not available in the standard model of error correction and also for probabilistic channel models. For the feedback model we present here a coding scheme, which we call the rubber method, because it is based on erasing letters. It is the first scheme achieving the capacity curve for q ges 3. It could be discovered only in the g-ary case for q ges 3, because the letter zero is not used as an information symbol, but solely for error correction. However an extension of the method from using single zeros to blocks of zeros also gives Berlekamp's result - by a different scheme. In the model with feedback and localized errors the help of feedback is addressed. We give an optimal construction for one-error correcting codes with feedback and localized errors

Ivan B. Djordjević