Universal coding with minimum probability of codeword length overflow
Universal coding with minimum probability of codeword length overflow
复制标题
码字长度溢出概率最小的通用编码
DOI：
10.1109/18.79912
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
N. Merhav
中科院分区：
文献类型：
--
作者：
N. Merhav
本文研究了有限状态、有限字母表信源的块变长无损信源编码。目标是最小化码字的归一化长度将超过给定阈值B的概率，服从Kraft不等式。证明了Lempel-Ziv算法（1978）在上述意义下渐近地达到最优性能，与信源和B值无关。对于单线马尔可夫信源的子类，使用最小描述长度的通用码可以更快地收敛到渐近最优性能。证明了这些通用码在最小化缓冲区溢出概率意义下也是近最优的，在竞争意义下也是渐近最优的。>
Lossless block-to-variable length source coding is studied for finite-state, finite-alphabet sources. The aim is to minimize the probability that the normalized length of the codeword will exceed a given threshold B, subject to the Kraft inequality. It is shown that the Lempel-Ziv algorithm (1978) asymptotically attains the optimal performance in the sense just defined, independently of the source and the value of B. For the subclass of unifilar Markov sources, faster convergence to the asymptotic optimum performance can be accomplished by using the minimum-description-length universal code for this subclass. It is demonstrated that these universal codes are also nearly optimal in the sense of minimizing buffer overflow probability, and asymptotically optimal in a competitive sense. >