On the expected codeword length per symbol of optimal prefix codes for extended sources
Author: 
Jay ChengAuthors Info & Claims
Pages 325 - 328
Abstract
For a discrete memoryless source X, it is well known that the expected codeword length per symbol Ln(X) of an optimal prefix code for the extended source Xn converges to the source entropy. However, the sequence Ln(X) need not be nonincreasing. As the encoding and decoding complexity increases exponentially with the block length, from a practical perspective it is both important and of interest to know when we can have a decrease in the expected codeword length per symbol by increasing the block length.
In this paper, we obtain some results on the behavior of Ln(X) and provide sufficient conditions for Lkn(X)< Ln(X) in terms of k, n, the probability of the most likely source symbol p1 and/or the minimum codeword length of an optimal code for the original source. By using these sufficient conditions, for any given n ≥ 1 and non-dyadic pn<over>1, we also obtain an integer k* ≥ 2 such that Lk'n(X) < Ln(X) for all k' ≥ k*. Our results could be regarded as extensions and generalizations of those by Montgomery and Kumar.
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]
T. M. Cover and J. A. Thomas, Elements of Information Theory, New York, NY: John Wiley & Sons, 1991.
[3]
B. L. Montgomery and B. V. K. V. Kumar, "On the average codeword length of optimal binary codes for extended sources," IEEE Transactions on Information Theory, vol. 33, pp. 293--296, March 1987.
[4]
P. M. Fenwick, "Huffman code efficiencies for extentions of sources," IEEE Transactions on Communications Theory, vol. 43, pp. 163--165, February/March/April 1995.
[5]
R. M. Capocelli and A. De Santis, "A note on D-ary Huffman codes," IEEE Transactions on Information Theory, vol. 37, pp. 174--179, January 1991.
Index Terms
- On the expected codeword length per symbol of optimal prefix codes for extended sources
Recommendations
On the expected codeword length per symbol of optimal prefix codes for extended sources
Given a discrete memoryless source X, it is well known that the expected codeword length per symbol Ln(X) of an optimal prefix code for the extended source Xn converges to the source entropy as n approaches infinity. However, the sequence Ln(X) need not ...
Prefix Codes: Equiprobable Words, Unequal Letter Costs
We consider the following variant of Huffman coding in which the costs of the letters, rather than the probabilities of the words, are nonuniform: ``Given an alphabet of $r$ letters {\em of nonuniform length}, find a minimum-average-length prefix-...
On the average codeword length of optimal binary codes for extended sources
Although optimal binary source coding using symbol blocks of increasing length must eventually yield a code having an average codeword length arbitrarily close to the source entropy, it is known that the sequence of average codeword lengths need not be ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2007
716 pages
ISBN:9781595936950
DOI:10.1145/1280940
- General Chairs:
- Mohsen Guizani,
- Hsiao-Hwa Chen,
- Program Chair:
- Xi Zhang
Copyright © 2007 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
- SIGDOC: ACM Special Interest Group on Systems Documentation
- ACM: Association for Computing Machinery
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 August 2007
Check for updates
Author Tags
Qualifiers
- Article
Conference
IWCMC07
Sponsor:
- SIGDOC
- ACM
IWCMC07: International Wireless Communications and Mobile Computing Conference
August 12 - 16, 2007
Hawaii, Honolulu, USA
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 82Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in