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. Towards quantum belief propagation for LDPC decoding in wireless networks

   https://doi.org/10.1145/3372224.3419207  

   Kasi, Srikar ; Jamieson, Kyle ( September 2020 , Proceedings of the 26th Annual International Conference on Mobile Computing and Networking (ACM MobiCom))

   We present Quantum Belief Propagation (QBP), a Quantum Annealing (QA) based decoder design for Low Density Parity Check (LDPC) error control codes, which have found many useful applications in Wi-Fi, satellite communications, mobile cellular systems, and data storage systems. QBP reduces the LDPC decoding to a discrete optimization problem, then embeds that reduced design onto quantum annealing hardware. QBP's embedding design can support LDPC codes of block length up to 420 bits on real state-of-the-art QA hardware with 2,048 qubits. We evaluate performance on real quantum annealer hardware, performing sensitivity analyses on a variety of parameter settings. Our design achieves a bit error rate of 10--8 in 20 μs and a 1,500 byte frame error rate of 10--6 in 50 μs at SNR 9 dB over a Gaussian noise wireless channel. Further experiments measure performance over real-world wireless channels, requiring 30 μs to achieve a 1,500 byte 99.99% frame delivery rate at SNR 15-20 dB. QBP achieves a performance improvement over an FPGA based soft belief propagation LDPC decoder, by reaching a bit error rate of 10--8 and a frame error rate of 10--6 at an SNR 2.5--3.5 dB lower. In terms of limitations, QBP currently cannot realize practical protocol-sized (e.g., Wi-Fi, WiMax) LDPC codes on current QA processors. Our further studies in this work present future cost, throughput, and QA hardware trend considerations. 

   more » « less
3. Belief Propagation with Quantum Messages for Symmetric Classical-Quantum Channels

   https://doi.org/10.1109/ITW54588.2022.9965841  

   Brandsen, S. ; Mandal, Avijit ; Pfister, Henry D. ( November 2022 , 2022 IEEE Information Theory Workshop (ITW))

   Belief propagation (BP) is a classical algorithm that approximates the marginal distribution associated with a factor graph by passing messages between adjacent nodes in the graph. It gained popularity in the 1990’s as a powerful decoding algorithm for LDPC codes. In 2016, Renes introduced a belief propagation with quantum messages (BPQM) and described how it could be used to decode classical codes defined by tree factor graphs that are sent over the classical-quantum pure-state channel. In this work, we propose an extension of BPQM to general binary-input symmetric classical-quantum (BSCQ) channels based on the implementation of a symmetric "paired measurement". While this new paired-measurement BPQM (PMBPQM) approach is suboptimal in general, it provides a concrete BPQM decoder that can be implemented with local operations. Finally, we demonstrate that density evolution can be used to analyze the performance of PMBPQM on tree factor graphs. As an application, we compute noise thresholds of some LDPC codes with BPQM decoding for a class of BSCQ channels. 

   more » « less
4. Polar Codes with Local-Global Decoding

   Zhu, Ziyuan ; Wu, Wei ; Siegel, Paul H. ( March 2023 , Proceedings of 14th Annual Non-Volatile Memories Workshop)

   Error correction coding schemes with local-global decoding are motivated by practical data storage applications where a balance must be achieved between low latency read access and high data reliability. As an example, consider a 4KB codeword, consisting of four 1KB subblocks, that supports a local-global decoding architecture. Local decoding can provide reliable, low-latency access to individual 1KB subblocks under good channel conditions, while global decoding can provide a “safety-net” for recovery of the entire 4KB block when local decoding fails under bad channel conditions. Recently, Ram and Cassuto have proposed such local-global decoding architectures for LDPC codes and spatially coupled LDPC codes. In this paper, we investigate a coupled polar code architecture that supports both local and global decoding. The coupling scheme incorporates a systematic outer polar code and a partitioned mapping of the outer codeword to semipolarized bit-channels of the inner polar codes. Error rate simulation results are presented for 2 and 4 subblocks. 

   more » « less
5. Low Complexity Robust Data Demodulation for GNSS

   https://doi.org/10.3390/s21041341  

   Ortega, Lorenzo ; Poulliat, Charly ; Boucheret, Marie Laure ; Aubault Roudier, Marion ; Al-Bitar, Hanaa ; Closas, Pau ( February 2021 , Sensors)

   null (Ed.)

   In this article, we provide closed-form approximations of log-likelihood ratio (LLR) values for direct sequence spread spectrum (DS-SS) systems over three particular scenarios, which are commonly found in the Global Navigation Satellite System (GNSS) environment. Those scenarios are the open sky with smooth variation of the signal-to-noise ratio (SNR), the additive Gaussian interference, and pulsed jamming. In most of the current communications systems, block-wise estimators are considered. However, for some applications such as GNSSs, symbol-wise estimators are available due to the low data rate. Usually, the noise variance is considered either perfectly known or available through symbol-wise estimators, leading to possible mismatched demodulation, which could induce errors in the decoding process. In this contribution, we first derive two closed-form expressions for LLRs in additive white Gaussian and Laplacian noise channels, under noise uncertainty, based on conjugate priors. Then, assuming those cases where the statistical knowledge about the estimation error is characterized by a noise variance following an inverse log-normal distribution, we derive the corresponding closed-form LLR approximations. The relevance of the proposed expressions is investigated in the context of the GPS L1C signal where the clock and ephemeris data (CED) are encoded with low-density parity-check (LDPC) codes. Then, the CED is iteratively decoded based on the belief propagation (BP) algorithm. Simulation results show significant frame error rate (FER) improvement compared to classical approaches not accounting for such uncertainty. 

   more » « less