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 -