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 (x1,…,xn) one-by-one over the Z-channel, in which a 1 is received only if a 1 is transmitted. At some designated moment, say n1, the encoder uses noiseless feedback and adjusts further encoding strategy based on the partial output of the channel (y1,…,yn1). 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 τn, 0<τ<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 τ=0<w<1max1+4w3w+w3≈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+ε of asymmetric errors, an error-correcting code contains at most O(ε−3/2) codewords.
