Technical Program

Paper Detail

Paper Title Lossless Source Coding in the Point-to-Point, Multiple Access, and Random Access Scenarios
Paper IdentifierWE2.R7.3
Authors Shuqing Chen, Michelle Effros, Victoria Kostina, California Institute of Technology, United States
Session Lossless Compression II
Location Bièvre, Level 5
Session Time Wednesday, 10 July, 11:40 - 13:20
Presentation Time Wednesday, 10 July, 12:20 - 12:40
Manuscript  Click here to download the manuscript
Abstract This paper treats point-to-point, multiple access and random access lossless source coding in the finite-blocklength regime. A random coding technique is developed, and its power in analyzing the third-order coding performance is demonstrated in all three scenarios. Results include a third-order-optimal characterization of the Slepian-Wolf rate region and a proof showing that for dependent sources, the independent encoders used by Slepian-Wolf codes can achieve the same third-order-optimal performance as a single joint encoder. The concept of random access source coding, which generalizes the multiple access scenario to allow for a subset of participating encoders that is unknown a priori to both the encoders and the decoder, is introduced. Contributions include a new definition of the probabilistic model for a random access-discrete multiple source, a general random access source coding scheme that employs a rateless code with sporadic feedback, and an analysis demonstrating via a random coding argument that there exists a deterministic code of the proposed structure that simultaneously achieves the third-order-optimal performance of Slepian-Wolf codes for all possible subsets of encoders.