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.
翻译:我们推出了新的通用频道编码模式。 与为特定类型的频道设计的标准代码不同的是, 我们最普遍的通用代码使每个频道的通信具有弹性, 只要噪音水平低于可容忍的约束范围, 一个频道的噪音水平是其模糊性的对数( 最大字符数可以扭曲为给定的字符串的最大数 ) 。 另一个更限制性的通用代码仍然适用于大类自然频道。 在通用代码中, 编码是独立于频道的, 但解码功能知道频道的类型。 我们允许编码和解码功能共享随机性功能, 而频道是无法使用的。 有两种关于频道可以执行的攻击类型的假设情景。 在模糊的假设情景中, 一个频道的噪音水平是一个添加组组组, 频道通过从固定的矢量添加一个矢量来扭曲一个编码。 选择基于信息与编码功能, 但不在编码中。 在哈明度假设中, 频道了解代码, 但它是完全的。 对于一个通用代码, 有两种参数: 读数是隐藏的 O 版本, 版本的版本中, 我们的版本的版本中显示的是 O 。 版本的版本中, 版本的版本中, 版本中的版本中是 版本中, 版本中的版本中的版本中的版本中的版本中, 版本中的版本中的版本中的版本中的版本中, 和版本中的版本中的版本中的版本中, 的版本中的版本中, 的版本中, 和版本中显示是共享的版本中的版本中的版本中的版本中的版本中的版本中的版本中, 。