More Like this

1. Pseudorandom Linear Codes Are List-Decodable to Capacity

   Putterman, Aaron; Pyne, Edward (January 2024, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024)

   We introduce a novel family of expander-based error correcting codes. These codes can be sampled with randomness linear in the block-length, and achieve list decoding capacity (among other local properties). Our expander-based codes can be made starting from any family of sufficiently low-bias codes, and as a consequence, we give the first construction of a family of algebraic codes that can be sampled with linear randomness and achieve list-decoding capacity. We achieve this by introducing the notion of a pseudorandom puncturing of a code, where we select n indices of a base code C ⊂ 𝔽_q^m in a correlated fashion. Concretely, whereas a random linear code (i.e. a truly random puncturing of the Hadamard code) requires O(n log(m)) random bits to sample, we sample a pseudorandom linear code with O(n + log (m)) random bits by instantiating our pseudorandom puncturing as a length n random walk on an exapnder graph on [m]. In particular, we extend a result of Guruswami and Mosheiff (FOCS 2022) and show that a pseudorandom puncturing of a small-bias code satisfies the same local properties as a random linear code with high probability. As a further application of our techniques, we also show that pseudorandom puncturings of Reed-Solomon codes are list-recoverable beyond the Johnson bound, extending a result of Lund and Potukuchi (RANDOM 2020). We do this by instead analyzing properties of codes with large distance, and show that pseudorandom puncturings still work well in this regime. 

   more » « less
2. Information Bottleneck Decoding of Rate-Compatible 5G-LDPC Codes

   https://doi.org/10.1109/ICC40277.2020.9149304  

   Stark, Maximilian; Bauch, Gerhard; Wang, Linfang; Wesel, Richard D. (June 2020, ICC 2020 - 2020 IEEE International Conference on Communications (ICC))

   The new 5G communications standard increases data rates and supports low-latency communication that places constraints on the computational complexity of channel decoders. 5G low-density parity-check (LDPC) codes have the so-called protograph-based raptor-like (PBRL) structure which offers inherent rate-compatibility and excellent performance. Practical LDPC decoder implementations use message-passing decoding with finite precision, which becomes coarse as complexity is more severely constrained. Performance degrades as the precision becomes more coarse. Recently, the information bottleneck (IB) method was used to design mutual-information-maximizing lookup tables that replace conventional finite-precision node computations. The IB approach exchanges messages represented by integers with very small bit width. This paper extends the IB principle to the flexible class of PBRL LDPC codes as standardized in 5G. The extensions include puncturing and rate-compatible IB decoder design. As an example of the new approach, a 4-bit information bottleneck decoder is evaluated for PBRL LDPC codes over a typical range of rates. Frame error rate simulations show that the proposed scheme outperforms offset min-sum decoding algorithms and operates very close to double-precision sum-product belief propagation decoding. 

   more » « less
3. CRC-Aided High-Rate Convolutional Codes With Short Blocklengths for List Decoding

   https://doi.org/10.1109/TCOMM.2023.3324370  

   Sui, Wenhui; Towell, Brendan; Asmani, Ava; Yang, Hengjie; Grissett, Holden; Wesel, Richard D. (January 2023, IEEE Transactions on Communications)

   Tal, Ido (Ed.)

   Recently, rate-1/ n zero-terminated (ZT) and tail-biting (TB) convolutional codes (CCs) with cyclic redundancy check (CRC)-aided list decoding have been shown to closely approach the random-coding union (RCU) bound for short blocklengths. This paper designs CRC polynomials for rate-( n - 1)/ n ZT and TB CCs with short blocklengths. This paper considers both standard rate-( n -1)/ n CC polynomials and rate-( n - 1)/ n designs resulting from puncturing a rate-1/2 code. The CRC polynomials are chosen to maximize the minimum distance d min and minimize the number of nearest neighbors A dmin . For the standard rate-( n - 1)/ n codes, utilization of the dual trellis proposed by Yamada et al . lowers the complexity of CRC-aided serial list Viterbi decoding (SLVD). CRC-aided SLVD of the TBCCs closely approaches the RCU bound at a blocklength of 128. This paper compares the FER performance (gap to the RCU bound) and complexity of the CRC-aided standard and punctured ZTCCs and TBCCs. This paper also explores the complexity-performance trade-off for three TBCC decoders: a single-trellis approach, a multi-trellis approach, and a modified single-trellis approach with pre-processing using the wrap around Viterbi algorithm. 

   more » « less
4. Rate-Compatible, Bandwidth-Efficient, Low-Density Parity-Check (LDPC) Codes for Aeronautical Telemetry

   https://doi.org/10.3390/e26121045  

   Cummins, Andrew D; Mitchell, David G; Perrins, Erik (December 2024, Entropy)

   Low-density parity-check (LDPC) codes form part of the IRIG-106 standard and have been successfully deployed for the Telemetry Group version of shaped-offset quadrature phase shift keying (SOQPSK-TG) modulation. Recently, LDPC code solutions have been proposed and optimized for continuous phase modulations (CPMs), including pulse code modulation/frequency modulation (PCM/FM) and the multi-h CPM developed by the Advanced-Range TeleMetry program (ARTM CPM), the latter of which was shown to perform around one dB from channel capacity. In this paper, we consider the effect of the random puncturing and shortening of these LDPC codes to further improve spectrum efficiency. We perform asymptotic analyses of the ARTM0 code ensembles and present numerical simulation results that affirm the robust decoding performance promised by LDPC codes designed for ARTM CPM. 

   more » « less
5. Random Shortening of Linear Codes and Applications

   https://doi.org/10.1007/978-3-031-49193-1_14  

   Chen, Xue; Cheng, Kuan; Li, Xin; Mao, Songtao (December 2023, Lecture notes in computer science)

   Random linear codes (RLCs) are well known to have nice combinatorial properties and near-optimal parameters in many different settings. However, getting explicit constructions matching the parameters of RLCs is challenging, and RLCs are hard to decode efficiently. This motivated several previous works to study the problem of partially derandomizing RLCs, by applying certain operations to an explicit mother code. Among them, one of the most well studied operations is random puncturing, where a series of works culminated in the work of Guruswami and Mosheiff (FOCS’ 22), which showed that a random puncturing of a low-biased code is likely to possess almost all interesting local properties of RLCs. In this work, we provide an in-depth study of another, dual operation of random puncturing, known as random shortening, which can be viewed equivalently as random puncturing on the dual code. Our main results show that for any small , by starting from a mother code with certain weaker conditions (e.g., having a large distance) and performing a random (or even pseudorandom) shortening, the new code is -biased with high probability. Our results hold for any field size and yield a shortened code with constant rate. This can be viewed as a complement to random puncturing, and together, we can obtain codes with properties like RLCs from weaker initial conditions. Our proofs involve several non-trivial methods of estimating the weight distribution of codewords, which may be of independent interest. 

   more » « less