Lossless Source Coding in the Point-to-Point, Multiple Access, and Random Access Scenarios
This work studies point-to-point, multiple access, and random access lossless source coding in the finite-blocklength regime. In each scenario, a random coding technique is developed and used to analyze third-order coding performance. Asymptotic results include a third-order characterization of the Slepian-Wolf rate region with an improved converse that relies on a connection to composite hypothesis testing. For dependent sources, the result implies that 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 is introduced to generalize multiple access (Slepian-Wolf) source coding to the case where encoders decide independently whether or not to participate and the set of participating encoders is unknown a priori to both the encoders and the decoder. The proposed random access source coding strategy employs rateless coding with scheduled feedback. A random coding argument proves the existence of a single deterministic code of this structure that simultaneously achieves the third-order-optimal Slepian-Wolf performance for each possible active encoder set.
© 2020 IEEE. Manuscript received September 4, 2019; revised May 27, 2020; accepted June 8, 2020. Date of publication July 17, 2020; date of current version October 21, 2020. This work was supported in part by the National Science Foundation under Grant CCF-1817241 and Grant CCF-1956386. The work of Shuqing Chen was supported in part by the Oringer Fellowship Fund in Information Science and Technology. This article was presented in part at the 2019 IEEE International Symposium on Information Theory . Matlab code for the computation of nonasymptotic bounds is available at github .