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.

In this paper, we consider encoding strategies for the Z-channel with noiseless feedback. We analyze the combinatorial setting where the maximum number of errors inflicted by an adversary is proportional to the number of transmissions, which goes to infinity. Without feedback, it is known that the rate of optimal asymmetric-error-correcting codes for the error fraction$\tau \ge 1/4$vanishes as the blocklength grows. In this paper, we give an efficient feedback encoding scheme with$n$transmissions that achieves a positive rate for any fraction of errors$\tau < 1$and$n\to \infty $. Additionally, we state an upper bound on the rate of asymptotically long feedback asymmetric error-correcting codes.

Berlekamp and Zigangirov completely determined the capacity error function for binary error correcting codes with noiseless feedback. It is still an unsolved problem if the upper bound for the capacity error function in the non-binary case of Ahlswede, Lebedev, and Deppe is sharp. We consider channels with limited magnitude and feedback. For several classes of these channels we completely determine the capacity error function. All our algorithms do not use all the feedback immediately. Furthermore, a special case of the problem is equivalent to Shannons zero-error problem.

We consider two generalizations of group testing: threshold group testing (introduced by Damaschke [8]) and majority group testing (a further generalization, including threshold group testing and a model introduced by Lebedev [15]). We show that each separating code gives a nonadaptive strategy for threshold group testing for some parameters. This is a generalization of a results on "guessing secrets", introduce. We introduce threshold codes and show that each threshold code gives a nonadaptive strategy for threshold group testing. We show that there exist threshold codes such that we can improve the lower bound for the rate of threshold group testing. We consider majority group testing if the number of defective elements is unknown (otherwise it reduces to threshold group testing). We show that cover-free codes and separating codes give strategies for majority group testing. We give a lower bound for the rate of majority group testing.

We consider a generalization of group testing, which gets together majority group testing and group testing with density tests. In contrast to the classical goal of group testing we want to find m defective elements of D defective elements. We examine four different test functions. We give adaptive strategies and lower bounds for the number of tests. We treat the cases if the number of defectives are known and if the number of defectives are bounded or unknown.

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