Buffer overflow in variable length coding of fixed rate sources
Buffer overflow in variable length coding of fixed rate sources
复制标题
固定速率源的可变长度编码中的缓冲区溢出
DOI：
10.1109/tit.1968.1054147
复制
发表时间：
1968
期刊：
影响因子：
--
通讯作者：
F. Jelinek
中科院分区：
文献类型：
--
作者：
F. Jelinek
在本文中，我们开发和分析了一个很容易仪表化的离散无记忆固定速率源的可变长度编码方案，其中缓冲区溢出导致码字擦除的位置，完全指定给用户。因此，永远不会发生同步丢失。我们发现最佳（即，最小化缓冲器溢出的概率）码字长度要求，相对于各种恒定传输速率R，并且表明这些不会导致最小平均码字长度。缓冲区溢出概率的相应界限提供了信源编码和Renyi广义信源熵之间的联系。我们表明，进一步，具有最佳字长的代码可以构建埃利亚斯的方法，我们开发相应的顺序仪表编码器和解码器。我们表明，这些编码器和解码器的复杂性只与编码的消息块长度k线性增长，提供的编码器字母表的大小d是2的幂，否则增长不差于二次与k。
In this paper, we develop and analyze an easily instrumentable scheme for variable length encoding of discrete memoryless fixed-rate sources in which buffer overflows result in codeword erasures at locations that are perfectly specified to the user. Thus, no loss of synchronism ever occurs. We find optimal (i.e., minimizing the probability of buffer overflow) code-wold length requirements under the Kraft inequality constraint, relative to various constant transmission rates R , and show that these do not result in the minimal average code-word length. The corresponding bounds on the probability of buffer overflow provide a linkup between source coding and Renyi's generalized source entropy. We show, further, that codes having optimal word lengths can be constructed by the method of Elias, and we develop corresponding sequentially instrumented encoders and decoders. We show that the complexity of these encoders and decoders grows only linearly with the encoded message block length k , provided the size d of the coder alphabet is a power of 2 , and otherwise grows no worse than quadratically with k .