Source coding and graph entropies

Noga Alon; Alon Orlitsky

doi:10.1109/18.532875

Source coding and graph entropies

Noga Alon, Alon Orlitsky

Research output: Contribution to journal › Article › peer-review

119 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	1329-1339
Number of pages	11
Journal	IEEE Transactions on Information Theory
Volume	42
Issue number	5
DOIs	https://doi.org/10.1109/18.532875
State	Published - 1996
Externally published	Yes

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

Amortization
Chromatic entropy
Graph entropy
Source coding

Access to Document

10.1109/18.532875

Cite this

@article{177c5b152556466aaf8c7de73f233943,

title = "Source coding and graph entropies",

abstract = "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{\"o}rner entropies of a naturally defined graph.",

keywords = "Amortization, Chromatic entropy, Graph entropy, Source coding",

author = "Noga Alon and Alon Orlitsky",

note = "Funding Information: Manuscript received May 16, 1995; revised February 7, 1996. This work was supported in part by the Fund for Basic Research administered by the",

year = "1996",

doi = "10.1109/18.532875",

language = "English (US)",

volume = "42",

pages = "1329--1339",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "5",

}

TY - JOUR

T1 - Source coding and graph entropies

AU - Alon, Noga

AU - Orlitsky, Alon

N1 - Funding Information: Manuscript received May 16, 1995; revised February 7, 1996. This work was supported in part by the Fund for Basic Research administered by the

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

KW - Amortization

KW - Chromatic entropy

KW - Graph entropy

KW - Source coding

UR - http://www.scopus.com/inward/record.url?scp=0030241020&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030241020&partnerID=8YFLogxK

U2 - 10.1109/18.532875

DO - 10.1109/18.532875

M3 - Article

AN - SCOPUS:0030241020

SN - 0018-9448

VL - 42

SP - 1329

EP - 1339

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 5

ER -

Source coding and graph entropies

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this