Source coding and graph entropies

被引：104

作者：

Alon, N ^{[1
]}

Orlitsky, A ^{[1
]}

机构：

[1] TEL AVIV UNIV,RAYMOND & BEVERLY SACKLER FAC EXACT SCI,IL-69978 TEL AVIV,ISRAEL

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 1996年 / 42卷 / 05期

关键词：

source coding; graph entropy; chromatic entropy; amortization;

D O I：

10.1109/18.532875

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 Korner entropies of a naturally defined graph.

引用

页码：1329 / 1339

页数：11

共 18 条

[1] REPEATED COMMUNICATION AND RAMSEY GRAPHS [J].

ALON, N ;

ORLITSKY, A .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1995, 41 (05) :1276-1289

[2]

ALON N, 1994, IEEE T INFORM THEORY, V38, P1670

[3]

BOPANA RB, 1989, P 21 ANN ACM S THEOR, P320

[4]

Cover T. M., 2005, ELEM INF THEORY, DOI 10.1002/047174882X

[5] ENTROPY SPLITTING FOR ANTIBLOCKING CORNERS AND PERFECT GRAPHS [J].

CSISZAR, I ;

KORNER, J ;

LOVASZ, L ;

MARTON, K ;

SIMONYI, G .

COMBINATORICA, 1990, 10 (01) :27-40

[6]

FEDER T, 1991, PROCEEDINGS - 32ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, P239, DOI 10.1109/SFCS.1991.185374

[7] ON THE SIZE OF SEPARATING SYSTEMS AND FAMILIES OF PERFECT HASH FUNCTIONS [J].

FREDMAN, ML ;

KOMLOS, J .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1984, 5 (01) :61-68

[8]

Kahn J., 1992, Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, P178, DOI 10.1145/129712.129731

[9] NEW BOUNDS FOR PERFECT HASHING VIA INFORMATION-THEORY [J].

KORNER, J ;

MARTON, K .

EUROPEAN JOURNAL OF COMBINATORICS, 1988, 9 (06) :523-530

[10]

KORNER J, 1986, SIAM J ALGEBRA DISCR, V7, P560

← 1 2 →