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 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.