Two-Stage Coding Over the Z-Channel
Alexey Lebedev, Vladimir S Lebedev, Nikita Polyanskii · IEEE Transactions on Information Theory · 2022
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.