论文标题
具有一般失真功能的渠道的共享随机模型中的通用代码
Universal codes in the shared-randomness model for channels with general distortion capabilities
论文作者
论文摘要
我们提出了通用频道编码的新模型。与为特定类型的通道设计的标准代码不同，我们最通用的通用代码使每个通道上的通信均具有弹性，前提是噪声级别低于耐受性界限，其中通道的噪声级别t是其模棱两可的对数（可能会扭曲为给定的字符串的最大字符串数）。其他更有限的通用代码仍然适用于大量自然渠道。在通用代码中，编码是与通道无关的，但是解码函数知道通道的类型。我们允许编码和解码函数共享随机性，这对于通道无法使用。通道可以执行的攻击类型有两种情况。在遗忘的情况下，代码字属于一个加法组，并且该频道通过从固定集中添加向量来扭曲代码字。选择基于消息和编码函数，而不是在代码字上。在锤子方案中，频道知道代码字，并且完全是对手。对于通用代码，有两个感兴趣的参数：速率，即消息长度k和codeword长度n与共享随机位的数量之间的比率。我们在带有1 -t/n -o（1）的通用代码的两种情况下都显示了存在，这是O（1）项的最佳模型。共享随机位的数量为O（log n）在遗忘的场景中，而O（n）在锤子方案中是o（n），对于噪声级别的典型值，我们表明是最佳的，modulo，modulo odulo odulo odulo odulo。在这两种情况下，通用编码都是在n中的多项式上完成的，但是通道依赖性的解码过程通常不是有效的。对于某些较弱的通道类别，我们使用多项式时间编码和解码构建通用代码。
We put forth new models for universal channel coding. Unlike standard codes which are designed for a specific type of channel, our most general universal code makes communication resilient on every channel, provided the noise level is below the tolerated bound, where the noise level t of a channel is the logarithm of its ambiguity (the maximum number of strings that can be distorted into a given one). The other more restricted universal codes still work for large classes of natural channels. In a universal code, encoding is channel-independent, but the decoding function knows the type of channel. We allow the encoding and the decoding functions to share randomness, which is unavailable to the channel. There are two scenarios for the type of attack that a channel can perform. In the oblivious scenario, codewords belong to an additive group and the channel distorts a codeword by adding a vector from a fixed set. The selection is based on the message and the encoding function, but not on the codeword. In the Hamming scenario, the channel knows the codeword and is fully adversarial. For a universal code, there are two parameters of interest: the rate, which is the ratio between the message length k and the codeword length n, and the number of shared random bits. We show the existence in both scenarios of universal codes with rate 1-t/n - o(1), which is optimal modulo the o(1) term. The number of shared random bits is O(log n) in the oblivious scenario, and O(n) in the Hamming scenario, which, for typical values of the noise level, we show to be optimal, modulo the constant hidden in the O() notation. In both scenarios, the universal encoding is done in time polynomial in n, but the channel-dependent decoding procedures are in general not efficient. For some weaker classes of channels we construct universal codes with polynomial-time encoding and decoding.
