NDLI: On the finite-length performance of universal coding for k-ary memoryless sources

Content Provider	IEEE Xplore Digital Library
Author	Beirami, A. Fekri, F.
Copyright Year	2010
Description	Author affiliation: School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta 30332, USA (Beirami, A.; Fekri, F.)
Abstract	In this paper, we investigate the performance of universal coding schemes on finite-length memoryless sequences. Rissanen demonstrated that for the universal compression of k-ary memoryless sources, expected redundancy for regular codes is asymptotically lower bounded by k-1 over 2 log n for almost all sources. Xie and Barron derived the minimax expected redundancy for k-ary memoryless sources, which characterizes the maximum redundancy over all possible source parameters. It does not provide much information about different source parameter values. This paper is a finite-length extension to Rissanen's result. Our treatment in this paper is probabilistic. In particular, we derive a lower bound on the probability measure of the sources that are not compressible with a redundancy smaller than a certain fraction of k-1 over 2 log n. In other words, we demonstrate a lower bound on the redundancy for a given percentile of sources. We demonstrate that as the length of the memoryless sequence decreases, the redundancy tends to become significant and comparable to the entropy of the sequence.
Starting Page	740
Ending Page	744
File Size	510705
Page Count	5
File Format	PDF
ISBN	9781424482153
e-ISBN	9781424482160
DOI	10.1109/ALLERTON.2010.5706981
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-09-29
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Source coding Redundancy Entropy Channel coding Ellipsoids
Content Type	Text
Resource Type	Article

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

Results on the redundancy of universal compression for finite-length sequences

Universal Fixed-Length Coding Redundancy

On the Cost of Finite Block Length in Quantizing Unbounded Memoryless Sources

Universal fixed-to-variable source coding in the finite blocklength regime

A New Universal Coding Scheme for the Binary Memoryless Source (1977)

Capacity of the binomial channel, or minimax redundancy for memoryless sources

On the cost of finite block length in quantizing unbounded memoryless sources

Universal Variable-to-Fixed Length Source Codes (2001)

On lossless universal compression of distributed identical sources

On the finite-length performance of universal coding for k-ary memoryless sources

Similar Documents

Results on the redundancy of universal compression for finite-length sequences

Universal Fixed-Length Coding Redundancy

On the Cost of Finite Block Length in Quantizing Unbounded Memoryless Sources

Universal fixed-to-variable source coding in the finite blocklength regime

A New Universal Coding Scheme for the Binary Memoryless Source (1977)

Capacity of the binomial channel, or minimax redundancy for memoryless sources

On the cost of finite block length in quantizing unbounded memoryless sources

Universal Variable-to-Fixed Length Source Codes (2001)

On lossless universal compression of distributed identical sources

On the finite-length performance of universal coding for k-ary memoryless sources