Overflow Probability of Variable-Length Codes with Codeword Cost

Ryo Nomura*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Article number8839856
Pages (from-to)8194-8206
Number of pages13
JournalIEEE Transactions on Information Theory
Issue number12
Publication statusPublished - 2019 Dec


  • Codeword cost
  • general source
  • information-spectrum
  • overflow probability
  • variable-length coding

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Overflow Probability of Variable-Length Codes with Codeword Cost'. Together they form a unique fingerprint.

Cite this