Lossless Source Coding in the Point-to-Point, Multiple Access, and Random Access Scenarios

Shuqing Chen, Michelle Effros, Victoria Kostina

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. Via a connection to composite hypothesis testing, a new converse that tightens previously known converses for Slepian-Wolf source coding is established. Asymptotic results include a third-order 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 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.

Knowledge Graph



Sign up or login to leave a comment