Two-stage coding over the Z-channel

In this paper, we discuss two-stage encoding algorithms capable of correcting a fraction of asymmetric errors. Suppose that we can transmit $n$ binary symbols $(x_1,\ldots,x_n)$ one-by-one over the Z-channel, in which a $1$ is received if and only if a $1$ is transmitted. At some moment, say $n_1$, it is allowed to use the complete feedback of the channel and adjust further encoding strategy based on the partial output of the channel $(y_1,\ldots,y_{n_1})$. The goal is to transmit as much information as possible under the assumption that the total number of errors 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<\omega<1}\frac{\omega + \omega^3}{1+4\omega^3}\approx 0.44$ from positive rate to zero rate for two-stage encoding strategies. As side results, we derive lower and upper bounds on the size of list-decodable codes for the Z-channel and prove that for a fraction $1/4+\epsilon$ of asymmetric errors, an error-correcting code contains at most $O(\epsilon^{-3/2})$ codewords.