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.

In this paper, we discuss two-stage encoding algorithms capable of correcting a fraction of asymmetric errors. Suppose that the encoder transmits$n$binary symbols$(x_{1},\ldots,x_{n})$one-by-one over the Z-channel, in which a 1 is received only if a 1 is transmitted. At some designated moment, say$n_{1}$, the encoder uses noiseless feedback and adjusts further encoding strategy based on the partial output of the channel$(y_{1},\ldots,y_{n_{1}})$. The goal is to transmit error-free as much information as possible under the assumption that the total number of errors inflicted by the Z-channel is limited by$\tau n$,$0 < \tau < 1$. We propose an encoding strategy that uses a list-decodable code at the first stage and a high-error low-rate code at the second stage. This strategy and our converse result yield that there is a sharp transition at$\tau =\max \limits _{0 < w < 1}\frac {w + w^{3}}{1+4w^{3}}\approx 0.44$from positive rate to zero rate for two-stage encoding strategies. As side results, we derive bounds on the size of list-decodable codes for the Z-channel and prove that for a fraction$1/4+ \varepsilon $of asymmetric errors, an error-correcting code contains at most$O(\varepsilon ^{-3/2})$codewords.

Koopman introduced in 1946 a two-sided search model. In this search model, the searched object is active and can move one step after each test at most. In this paper we analyze the model of a combinatorial two-sided search by allowing more moves of the searched object after each test. We give search strategies and show that these strategies are optimal. We consider adaptive and non-adaptive strategies. We show the surprising result that with the combinatorial two-sided search on a path graph the optimal non-adaptive search needs the same number of questions as the corresponding adaptive search strategy does. The strategy obtained can also be used to transmit the position of a moving element through a channel. Furthermore, the strategy is a generalization of a group testing strategy to a moving searched element.