UNIVERSAL NOISELESS CODING
UNIVERSAL NOISELESS CODING
复制标题
DOI：
10.1109/tit.1973.1055092
复制
发表时间：
1973-01-01
影响因子：
2.5
通讯作者：
DAVISSON, LD
中科院分区：
文献类型：
--
作者：
DAVISSON, LD
通用编码是对未知参数信源进行块到块无记忆信源编码的任何渐近最优方法。本文认为，无噪声编码等来源，主要是在可变长度编码，与性能测量作为一个函数的编码冗余相对于每个字母的条件源熵给定的未知参数。发现普遍的（即，当且仅当参数空间和消息空间之间的每字母平均互信息为零时，加权意义上的零冗余）编码才是可能的。当且仅当两个空间之间的信道容量为零时，通用编码在极大极小意义上是可能的。通用编码在极大极小意义上是可能的，当且仅当存在独立于未知参数的概率质量函数，对于该概率质量函数，已知条件概率质量函数的相对熵为零。文中给出了几个例子来说明这一思想。特别注意的是，对于任何固定的参数是平稳和遍历的源，虽然整个合奏是不是。对于这样的源，如果字母表是有限的，或者更一般地，如果熵是有限的，则加权通用码总是存在的。如果应用额外的熵稳定性约束，则得到极小极大通用码。本文还简要地讨论了固定速率通用编码，并用误码率来衡量其性能。
Universal coding is any asymptotically optimum method of block-to-block memoryless source coding for sources with unknown parameters. This paper considers noiseless coding for such sources, primarily in terms of variable-length coding, with performance measured as a function of the coding redundancy relative to the per-letter conditional source entropy given the unknown parameter. It is found that universal (i.e., zero redundancy) coding in a weighted sense is possible if and only if the per-letter average mutual information between the parameter space and the message space is zero. Universal coding is possible in a maximin sense if and only if the channel capacity between the two spaces is zero. Universal coding is possible in a minimax sense if and only if a probability mass function exists, independent of the unknown parameter, for which the relative entropy of the known conditional-probability mass-function is zero. Several examples are given to illustrate the ideas. Particular attention is given to sources that are stationary and ergodic for any fixed parameter although the whole ensemble is not. For such sources, weighted universal codes always exist if the alphabet is finite, or more generally if the entropy is finite. Minimax universal codes result if an additional entropy stability constraint is applied. A discussion of fixed-rate universal coding is also given briefly with performance measured by a probability of error.