Lossless and lossy source compression with near-uniform output: Is common randomness always required?

Badri N. Vellambi, Matthieu Bloch, Rémi Chou, Jörg Kliewer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

It is known that a sub-linear rate of source-independent random seed (common randomness) can enable the construction of lossless compression codes whose output is nearly uniform under the variational distance (Chou-Bloch-ISIT'13). This work uses finite-blocklength techniques to present an alternate proof that for near-uniform lossless compression, the seed length has to grow strictly larger than √n, where n represents the blocklength of the lossless compression code. In the lossy setting, we show the surprising result that a seed is not required to make the encoder output nearly uniform.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2171-2175
Number of pages5
ISBN (Electronic)9781467377041
DOIs
StatePublished - Sep 28 2015
EventIEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong
Duration: Jun 14 2015Jun 19 2015

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2015-June
ISSN (Print)2157-8095

Other

OtherIEEE International Symposium on Information Theory, ISIT 2015
CountryHong Kong
CityHong Kong
Period6/14/156/19/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Keywords

  • Finite-blocklength techniques
  • Lossless coding
  • Rate-distortion
  • Source coding

Fingerprint Dive into the research topics of 'Lossless and lossy source compression with near-uniform output: Is common randomness always required?'. Together they form a unique fingerprint.

Cite this