Optimum Overflow Thresholds in Variable-Length Source Coding Allowing Non-Vanishing Error Probability
From MaRDI portal
Publication:5211571
DOI10.1109/TIT.2019.2920417zbMATH Open1433.94053arXiv1810.07863OpenAlexW2896401816WikidataQ127792308 ScholiaQ127792308MaRDI QIDQ5211571FDOQ5211571
Authors: Ryo Nomura, Hideki Yagi 
Publication date: 28 January 2020
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: 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. We also derive general formulas of the optimum overflow thresholds in the optimistic coding scenario. Finally, we apply general formulas derived in this paper to the case of stationary memoryless sources.
Full work available at URL: https://arxiv.org/abs/1810.07863
Cited In (2)
This page was built for publication: Optimum Overflow Thresholds in Variable-Length Source Coding Allowing Non-Vanishing Error Probability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211571)
