Optimum Overflow Thresholds in Variable-Length Source Coding Allowing Non-Vanishing Error Probability
Optimum Overflow Thresholds in Variable-Length Source Coding Allowing Non-Vanishing Error Probability
复制标题
DOI：
10.1109/tit.2019.2920417
复制
发表时间：
2018-10
影响因子：
2.5
通讯作者：
R. Nomura;H. Yagi
中科院分区：
文献类型：
--
作者：
R. Nomura;H. Yagi
对于一般源，考虑允许错误概率达到某个常数的可变长度源编码问题。在这个问题中，变长码的最佳平均码字长度已经确定。另一方面，在本文中，我们关注溢出（或超出码字长度）概率而不是平均码字长度。在错误概率和溢出概率均小于或等于某个常数的约束下，溢出阈值的下确界称为最优溢出阈值。在本文中，我们首先推导这些概率的有限长度上限和下界，以分析最佳溢出阈值。然后，通过使用这些界限，我们确定一阶和二阶形式的最佳溢出阈值的通用公式。接下来，我们考虑导出的通式的另一种表达式，以揭示与固定长度源编码问题中的最佳编码率的关系。最后，我们将本文推导的一般公式应用于固定无记忆源的情况。
The variable-length source coding problem allowing the error probability up to some constant is considered for general sources. In this problem, the optimum mean codeword length of variable-length codes has already been determined. On the other hand, in this paper, we focus on the overflow (or excess codeword length) probability instead of the mean codeword length. The infimum of overflow thresholds under the constraint that both of the error probability and the overflow probability are smaller than or equal to some constant is called the optimum overflow threshold. In this paper, we first derive finite-length upper and lower bounds on these probabilities so as to analyze the optimum overflow thresholds. Then, by using these bounds, we determine the general formula of the optimum overflow thresholds in both of the first-order and second-order forms. Next, we consider another expression of the derived general formula so as to reveal the relationship with the optimum coding rate in the fixed-length source coding problem. Finally, we apply the general formula derived in this paper to the case of stationary memoryless sources.