Source coding and graph entropies

Noga Alon, Alon Orlitsky

Research output: Contribution to journalArticlepeer-review

117 Scopus citations


A sender wants to accurately convey information to a receiver who has some, possibly related, data. We study the expected number of bits the sender must transmit for one and for multiple instances in two communication scenarios and relate this number to the chromatic and Körner entropies of a naturally defined graph.

Original languageEnglish (US)
Pages (from-to)1329-1339
Number of pages11
JournalIEEE Transactions on Information Theory
Issue number5
StatePublished - 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Amortization
  • Chromatic entropy
  • Graph entropy
  • Source coding


Dive into the research topics of 'Source coding and graph entropies'. Together they form a unique fingerprint.

Cite this