Universal Multiterminal Source Coding Algorithms With Asymptotically Zero Feedback: Fixed Database Case
Publication in refereed journal


Times Cited
Web of Science10WOS source URL (as at 16/11/2020) Click here for the latest count
Altmetrics Information
.

Other information
AbstractConsider a source network in which a finite alphabet source X = {X-i}(i=0)(infinity) is to be encoded and transmitted, and another finite alphabet source Y = {Y-i}(i=0)(infinity) correlated with X is available only to the decoder as side information. Traditionally, the channel between the encoder and decoder in the source network is assumed to be one-way. This, together with the fact that the encoder does not have access to Y, implies that the encoder has to know the achievable rates before encoding. In this paper, we consider universal source coding for a feedback source network in which the channel between the encoder and decoder is two-way and asymmetric. Assume that the encoder and decoder share a random database that is independent of both X and Y. A string matching-based (variable-rate) block coding algorithm with simple progressive encoding and joint typicality decoding is first proposed for the feedback source network. The simple progressive encoder does not need to know the achievable rates at the beginning of encoding. It is proven that for any (X, Y) in a large class of sources satisfying some mixing conditions, the average number of bits per letter transmitted from the encoder to the decoder (compression rate) goes to the conditional entropy H (X vertical bar Y) of X given 11 asymptotically, and at the same time the average number of bits per letter transmitted from the decoder to the encoder (feedback rate) goes to 0 asymptotically. The algorithm and the corresponding analysis results are then extended to the case where both X and Y are to be encoded separately, but decoded jointly. Finally, a universal decoding algorithm is proposed to replace the joint typicality decoding, and the resulting universal compression algorithm consisting of the simple progressive encoder and the universal decoding algorithm is further shown to be asymptotically optimal for the class of all jointly memoryless source-side information pairs (X,Y).
All Author(s) ListYang EH, He DK, Uyematsu T, Yeung RW
Journal nameIEEE Transactions on Information Theory
Year2008
Month12
Day1
Volume Number54
Issue Number12
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages5575 - 5590
ISSN0018-9448
eISSN1557-9654
LanguagesEnglish-United Kingdom
KeywordsDatabase; distributed source coding; entropy; feedback; phi-mixing; string matching; universal data compression
Web of Science Subject CategoriesComputer Science; Computer Science, Information Systems; COMPUTER SCIENCE, INFORMATION SYSTEMS; Engineering; Engineering, Electrical & Electronic; ENGINEERING, ELECTRICAL & ELECTRONIC

Last updated on 2020-17-11 at 00:45