On Complementary Graph Entropy

Author

Tuncel, Ertem ; Nayak, Jayanth ; Koulgi, Prashant ; Rose, Kenneth

Author_Institution

Dept. of Electr. Eng., Univ. of California, Riverside, CA

Volume

55

Issue

6

fYear

2009

fDate

6/1/2009 12:00:00 AM

Firstpage

2537

Lastpage

2546

Abstract

It has been recently discovered that complementary graph entropy characterizes (and offers new insights into) the minimum asymptotic rate for zero-error source coding with decoder side information. This paper presents new results that build on and complement this discovery. Specifically, i) previously unknown subadditivity properties of complementary graph entropy are derived, and ii) zero-error coding rates are characterized in terms of complementary graph entropy for two multiterminal coding scenarios. For both scenarios, the rate characterization implies no rate loss relative to point-to-point source coding.

Keywords

decoding; entropy codes; graph theory; source coding; complementary graph entropy; decoder side information; minimum asymptotic rate; multiterminal coding scenario; point-to-point source coding; subadditivity property; zero-error source coding; Decoding; Engineering profession; Entropy; Information theory; Laboratories; Materials science and technology; Random variables; Source coding; Chromatic entropy; complementary graph entropy; graph entropy; side information; zero-error capacity; zero-error source coding;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2009.2018182

Filename

4957638