论文标题
Z渠道上的两阶段编码
Two-stage coding over the Z-channel
论文作者
论文摘要
在本文中，我们讨论了能够纠正不对称误差部分的两阶段编码算法。假设编码器传输$ n $二进制符号$（x_1，\ ldots，x_n）$一一以上的z渠道，其中仅在传输1时收到1。在某个指定的时刻（例如$ n_1 $），编码器使用无噪声反馈，并根据通道$（y_1，\ ldots，y_ _ {n_1}）$的部分输出调整进一步的编码策略。目的是在假设Z渠道造成的错误总数限制为$τn$，$ 0 <τ<1 $的情况下，将无错误的信息传输尽可能多的信息。我们提出了一种编码策略，该策略在第一阶段使用列表可解码的代码，在第二阶段使用高率低速代码。该策略和我们的相反结果产生了$τ= \ max \ limits _ {0 <w <1} \ frac {w + w^3} {1 + 4W^3} \大约0.44 $从正速率到零速率的两阶段编码策略的急剧过渡。作为侧面结果，我们在Z渠道的可定义代码的大小上得出界限，并证明，对于不对称错误的分数$ 1/4+ε$，错误校正的代码最多包含$ O（ε^{ - 3/3/2}）$ CODEERVORDS。
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 $τ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 $τ=\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+ε$ of asymmetric errors, an error-correcting code contains at most $O(ε^{-3/2})$ codewords.
