Second order asymptotics in fixed-length source coding and intrinsic randomness
Preprint
Abstract
Second order asymptotics of fixed-length source coding and intrinsic randomness is discussed with a constant error constraint. There was a difference between optimal rates of fixed-length source coding and intrinsic randomness, which never occurred in the first order asymptotics. In addition, the relation between uniform distribution and compressed data is discussed based on this fact. These results are valid for general information sources as well as independent and identical distributions. A universal code attaining the second order optimal rate is also constructed.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Folklore in Source Coding: Information-Spectrum ApproachIEEE Transactions on Information Theory, 2005
- Information-Spectrum Methods in Information Theory2003
- Source code with cost as a nonuniform random number generatorIEEE Transactions on Information Theory, 2000
- Optimistic Shannon coding theorems for arbitrary single-user systemsIEEE Transactions on Information Theory, 1999
- Source codes as random number generatorsIEEE Transactions on Information Theory, 1998
- Second-order noiseless source coding theoremsIEEE Transactions on Information Theory, 1997
- Simulation of random processes and rate-distortion theoryIEEE Transactions on Information Theory, 1996
- Generating random bits from an arbitrary source: fundamental limitsIEEE Transactions on Information Theory, 1995
- Jeffreys' prior is asymptotically least favorable under entropy riskJournal of Statistical Planning and Inference, 1994
- A continuity property of the entropy density for spin lattice systemsCommunications in Mathematical Physics, 1973