Upper bounds on exponentiated expected length of optimal one-to-one codes

ABSTRACT

In this paper, we consider an exponentially weighted average codeword length introduced by Campbell as a performance measure for source codes. This criterion assumes that the cost is an exponential function of the codeword length and includes the usual expected codeword length criterion as a special case. Such situations could arise when the cost for encoding and decoding is significant, or if the buffer overflow caused by long codewords is a serious issue. The source codes under consideration are one-to-one encodings for a discrete memoryless source, which are "one-shot" encodings associating a distinct codeword with each source symbol. Such encodings could be employed when only a single source symbol rather than a sequence of source symbols needs to be transmitted. For example, such a situation can arise when the last message must be acknowledged before the next message can be transmitted. We consider two slightly different types of one-to-one encodings (depending on whether the empty codeword is used or not) and obtain several new upper bounds on Campbell's average length of optimal one-to-one codes when the probability of the most likely source symbol is available.

REFERENCES

• 1: C. E. Shannon, "A mathematical theory of communication," Bell System Technical Journal, vol. 27, pp. 379--423 (Part I), 623--656 (Part II), July, October 1948.
• 2: A. Rényi, "On measures of entropy and information," Proceedings of 4th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, CA, USA, 1960, pp. 547--561.
• 3: L. L. Campbell, "A coding theorem and Rényi's entropy," Information and Control, vol. 8, pp. 423--429, August 1965.
• 4: L. L. Campbell, "Definition of entropy by means of a coding problem," Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, vol. 6, pp. 113--118, 1966.
• 5: F. Jelinek, "Buffer overflow in variable length coding of fixed rate sources," IEEE Transactions on Information Theory, vol. 14, pp. 490--501, May 1968.
• 6: P. A. Humblet, "Generalization of Huffman coding to minimize the probability of buffer overflow," IEEE Transactions on Information Theory, vol. 27, pp. 230--232, March 1981.
• 7: A. C. Blumer and R. J. McEliece, "The Rényi redundancy of generalized Huffman codes," IEEE Transactions on Information Theory, vol. 34, pp. 1242--1249, September 1988.
• 8: A. D. Wyner, "An upper bound on the entropy series," Information and Control, vol. 20, pp. 176--181, 1972.
• 9: S. K. Leung-Yan-Cheong and T. M. Cover, "Some equivalences between Shannon entropy and Kolmogorov complexity," IEEE Transactions on Information Theory, vol. 24, pp. 331--338, May 1978.
• 10: J. G. Dunham, "Optimal noiseless coding of random variables," IEEE Transactions on Information Theory, vol. 26, p. 345, May 1980.
• 11: J. Rissanen, "Tight lower bounds for optimum code length," IEEE Transactions on Information Theory, vol. 28, pp. 348--349, March 1982.
• 12: E. I. Verriest, "An achievable bound for optimal noiseless coding of a random variable," IEEE Transactions on Information Theory, vol. 32, pp. 592--594, July 1986.
• 13: N. Alon and A. Orlitsky, "A lower bound on the expected length of one-to-one codes," IEEE Transactions on Information Theory, vol. 40, pp. 1670--1672, September 1994.
• 14: C. Blundo and R. De Prisco, "New bounds on the expected length of one-to-one codes," IEEE Transactions on Information Theory, vol. 42, pp. 246--250, January 1996.
• 15: J. Cheng and T.-K. Huang, "New lower bounds on the expected length of one-to-one codes," in Proceedings 4th International Symposium on Turbo Codes in connection with 6th International ITG-Conference on Source and Channel Coding (ISTC+SCC'06), Munich, Germany, April 3--7, 2006.
• 16: Jay Cheng , Tien-Ke Huang, New Lower and Upper Bounds on the Expected Length of Optimal One-to-One Codes, Proceedings of the Data Compression Conference (DCC'06), p.43-52, March 28-30, 2006 [doi>10.1109/DCC.2006.52]
• 17: I. J. Taneja, "A short note on exponentiated mean codeword length for the best 1:1 code," Computational and Applied Mathematics, vol. 3, pp. 199--204, 1984.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

General Terms:
Theory

Keywords:
anti-redundancy, non-prefix codes, one-to-one codes, source coding