Near-Optimality of the Minimum Average Redundancy Code for Almost All Monotone Sources
-
- NARIMANI Hamed
- Department of Electrical and Computer Engineering, Isfahan University of Technology
-
- KHOSRAVIFARD Mohammadali
- Department of Electrical and Computer Engineering, Isfahan University of Technology
-
- GULLIVER T. Aaron
- Department of Electrical & Computer Engineering University of Victoria
Search this article
Abstract
Consider the source coding problem of finding the optimal code, in the sense of average redundancy, for the class of monotone sources with n symbols. The solution of this problem, known as the M code, is the Huffman code for the average distribution of the monotone sources. In this paper, we evaluate the average redundancy of the M code (on the class of monotone sources), and compare it with that of the Huffman code. It is demonstrated that for large n, although the M code is a fixed code (i.e., the codewords are independent of the symbol probabilities) for all monotone sources, its average redundancy is very close to that of the Huffman code. Moreover, it is shown that when n is large, the M code is a near-optimal code not only in the sense of average redundancy, but also the redundancy of almost all monotone sources. In particular, the redundancy of the M code converges in probability to its average value (≅0.029). As a result, the maximum redundancy of the M code, which can be as large as log n - log ln n, rarely occurs.
Journal
-
- IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
-
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E94-A (11), 2092-2096, 2011
The Institute of Electronics, Information and Communication Engineers
- Tweet
Details 詳細情報について
-
- CRID
- 1390282681288681856
-
- NII Article ID
- 10030191446
-
- NII Book ID
- AA10826239
-
- ISSN
- 17451337
- 09168508
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- Crossref
- CiNii Articles
-
- Abstract License Flag
- Disallowed