NDLI: The Minimum Average Code for Finite Memoryless Monotone Sources

Content Provider	IEEE Xplore Digital Library
Author	Khosravifard, M. Saidi, H. Esmaeili, M. Gulliver, T.A.
Copyright Year	1963
Abstract	The problem of selecting a code for finite monotone sources with N symbols is considered. The selection criterion is based on minimizing the average redundancy (called Minave criterion) instead of its maximum (i.e., Minimax criterion). The average probability distribution P^Nmacr, whose associated Huffman code has the minimum average redundancy, is derived. The entropy of the average distribution (i.e., H(P^Nmacr)) and the average entropy of the monotone distributions (i.e., H(P^Nmacr)) are studied. It is shown that both logN-H(P^Nmacr) and logN-H(P^Nmacr) are asymptotically equal to a constant (sime0.61). Therefore, there is only a negligible penalty (at most 1.61 bits/symbol) in using a simple fixed-length code with respect to the optimal code. An efficient near-optimal encoding technique is also proposed. The consequences of the two approaches, i.e., Minave and Minimax, are compared in terms of their associated distributions and associated codes. In order to evaluate the average performance of the Minimax code, we prove that the informational divergence of the average distribution and Minimax distribution asymptotically grows as -2.275+loglogN
Sponsorship	IEEE Information Theory Society
Starting Page	955
Ending Page	975
Page Count	21
File Size	983493
File Format	PDF
ISSN	00189448
Volume Number	53
Issue Number	3
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-03-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Minimax techniques Entropy Degradation Probability distribution Encoding Source coding Data compression minimum average criterion Average redundancy finite monotone sources fixed-length code Huffman code Minave code Minimax code
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The minimum average code for finite memoryless monotone sources (2002)

Huffman Redundancy for Large Alphabet Sources

The minimum average code for finite memoryless monotone sources

Minimum expected length of fixed-tovariable lossless compression without prefix constraints: Memoryless sources (2011)

Minimum Expected Length of Fixed-to-Variable Lossless Compression of Memoryless Sources

On the Optimal Coding (2001)

Minimum expected length of fixed-to-variable lossless compression without prefix constraints.

Generalized Shannon Code Minimizes the Maximal Redundancy (2001)

The minimum codeword length and redundancy in the binary Huffman code for uncertain sources

The Minimum Average Code for Finite Memoryless Monotone Sources

Similar Documents

The minimum average code for finite memoryless monotone sources (2002)

Huffman Redundancy for Large Alphabet Sources

The minimum average code for finite memoryless monotone sources

Minimum expected length of fixed-tovariable lossless compression without prefix constraints: Memoryless sources (2011)

Minimum Expected Length of Fixed-to-Variable Lossless Compression of Memoryless Sources

On the Optimal Coding (2001)

Minimum expected length of fixed-to-variable lossless compression without prefix constraints.

Generalized Shannon Code Minimizes the Maximal Redundancy (2001)

The minimum codeword length and redundancy in the binary Huffman code for uncertain sources

The Minimum Average Code for Finite Memoryless Monotone Sources