TY - JOUR
T1 - Overflow Probability of Variable-Length Codes with Codeword Cost
AU - Nomura, Ryo
N1 - Funding Information:
Manuscript received October 29, 2013; revised September 14, 2018; accepted August 20, 2019. Date of publication September 16, 2019; date of current version November 20, 2019. This work was supported in part by JSPS KAKENHI under Grant JP26420371 and Grant JP18K04150. This article was presented in part at the 2012 IEEE International Symposium on Information Theory. The author is with the Center for Data Science, Waseda University, Tokyo 162-0042, Japan (e-mail: nomu@waseda.jp). Communicated by Y. Oohama, Associate Editor for Source Coding. Color versions of one or more of the figures in this article are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TIT.2019.2941888
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2019/12
Y1 - 2019/12
N2 - Lossless variable-length source coding with codeword cost is considered for general sources. The problem setting, where we impose on unequal costs on code symbols, is called the variable-length coding with codeword cost. In this problem, the infimum of average codeword cost have already been determined for general sources. On the other hand, the overflow probability, which is defined as the probability of codeword cost being above a threshold, have not been considered yet. In this paper, we first determine the infimum of achievable threshold in the first-order sense and the second-order sense for general sources with additive memoryless codeword cost. Then, we compute it for some special sources such as i.i.d. sources and mixed sources. A generalization of the codeword cost is also discussed.
AB - Lossless variable-length source coding with codeword cost is considered for general sources. The problem setting, where we impose on unequal costs on code symbols, is called the variable-length coding with codeword cost. In this problem, the infimum of average codeword cost have already been determined for general sources. On the other hand, the overflow probability, which is defined as the probability of codeword cost being above a threshold, have not been considered yet. In this paper, we first determine the infimum of achievable threshold in the first-order sense and the second-order sense for general sources with additive memoryless codeword cost. Then, we compute it for some special sources such as i.i.d. sources and mixed sources. A generalization of the codeword cost is also discussed.
KW - Codeword cost
KW - general source
KW - information-spectrum
KW - overflow probability
KW - variable-length coding
UR - http://www.scopus.com/inward/record.url?scp=85077372998&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85077372998&partnerID=8YFLogxK
U2 - 10.1109/TIT.2019.2941888
DO - 10.1109/TIT.2019.2941888
M3 - Article
AN - SCOPUS:85077372998
SN - 0018-9448
VL - 65
SP - 8194
EP - 8206
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 12
M1 - 8839856
ER -