More Like this

1. Finite-Blocklength and Error-Exponent Analyses for LDPC Codes in Point-to-Point and Multiple Access Communication

   https://doi.org/10.1109/ISIT44484.2020.9173963  

   Liu, Yuxin; Effros, Michelle (June 2020, 2020 IEEE International Symposium on Information Theory (ISIT))

   null (Ed.)

   This paper applies error-exponent and dispersionstyle analyses to derive finite-blocklength achievability bounds for low-density parity-check (LDPC) codes over the point-to-point channel (PPC) and multiple access channel (MAC). The error-exponent analysis applies Gallager's error exponent to bound achievable symmetrical and asymmetrical rates in the MAC. The dispersion-style analysis begins with a generalization of the random coding union (RCU) bound from random code ensembles with i.i.d. codewords to random code ensembles in which codewords may be statistically dependent; this generalization is useful since the codewords of random linear codes such as LDPC codes are dependent. Application of the RCU bound yields finite-blocklength error bounds and asymptotic achievability results for both i.i.d. random codes and LDPC codes. For discrete, memoryless channels, these results show that LDPC codes achieve first- and second-order performance that is optimal for the PPC and identical to the best prior results for the MAC. 

   more » « less
2. A Shannon-Theoretic Approach to the Storage–Retrieval Trade-Off in PIR Systems

   https://doi.org/10.3390/info14010044  

   Tian, Chao; Sun, Hua; Chen, Jun (January 2023, Information)

   We consider the storage–retrieval rate trade-off in private information retrieval (PIR) systems using a Shannon-theoretic approach. Our focus is mostly on the canonical two-message two-database case, for which a coding scheme based on random codebook generation and the binning technique is proposed. This coding scheme reveals a hidden connection between PIR and the classic multiple description source coding problem. We first show that when the retrieval rate is kept optimal, the proposed non-linear scheme can achieve better performance over any linear scheme. Moreover, a non-trivial storage-retrieval rate trade-off can be achieved beyond space-sharing between this extreme point and the other optimal extreme point, achieved by the retrieve-everything strategy. We further show that with a method akin to the expurgation technique, one can extract a zero-error PIR code from the random code. Outer bounds are also studied and compared to establish the superiority of the non-linear codes over linear codes. 

   more » « less
3. Explicit Time and Space Efficient Encoders Exist Only with Random Access

   https://doi.org/10.4230/LIPIcs.CCC.2024.5  

   Cook, Joshua; Moshkovitz, Dana (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Santhanam, Rahul (Ed.)

   We give the first explicit constant rate, constant relative distance, linear codes with an encoder that runs in time n^{1 + o(1)} and space polylog(n) provided random access to the message. Prior to this work, the only such codes were non-explicit, for instance repeat accumulate codes [Divsalar et al., 1998] and the codes described in [Gál et al., 2013]. To construct our codes, we also give explicit, efficiently invertible, lossless condensers with constant entropy gap and polylogarithmic seed length. In contrast to encoders with random access to the message, we show that encoders with sequential access to the message can not run in almost linear time and polylogarithmic space. Our notion of sequential access is much stronger than streaming access. 

   more » « less
4. Nested LDPC Codes for Random Access Communication

   https://doi.org/10.1109/ISIT45174.2021.9518171  

   Liu, Yuxin; Effros, Michelle (July 2021, 2021 IEEE International Symposium on Information Theory (ISIT))

   This paper proposes a nested low-density parity-check (LDPC) code design. Combining this nested LDPC code with the random access coding strategy introduced by Yavas, Kostina, and Effros yields a random access LDPC (RA-LDPC) code for reliable communication in random access communication environments where neither the transmitters nor the receiver knows which or even how many transmitters wish to communicate at each moment. Coordination is achieved using sparse scheduled feedback. Bounds on the finite-blocklength performance of the RA-LDPC code under maximum likelihood (ML) decoding are derived using both error exponent and dispersion style analyses. Results include bounds on the penalty of the RA-LDPC code as a function of the LDPC code densities. 

   more » « less
5. Lattices from Linear Codes and Fine Quantization: General Continuous Sources and Channels

   Shirani, Farhad; Pradhan, Sandeep (June 2018, 2018 IEEE International Symposium on Information Theory (ISIT))

   In this paper we consider the information-theoretic characterization of performance limits of a broad class of multiterminal communication problems with general continuousvalued sources and channels. In particular, we consider point-topoint source coding and channel coding with side information, distributed source coding with distortion constraints and function reconstruction problems (two-help-one). We develop an approach that uses fine quantization of the source and the channel variables followed by random coding with unstructured as well as structured (linear) code ensembles. This approach leads to lattice-like codes for general sources and channels. 

   more » « less