More Like this

1. 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
2. Coded Distributed Computing: Performance Limits and Code Designs

   https://doi.org/10.1109/ITW44776.2019.8989097  

   Jamali, Mohammad Vahid; Soleymani, Mahdi; Mahdavifar, Hessam (August 2019, 2019 IEEE Information Theory Workshop (ITW))

   We consider the problem of coded distributed computing where a large linear computational job, such as a matrix multiplication, is divided into $$k$$ smaller tasks, encoded using an $(n,k)$ linear code, and performed over $$n$$ distributed nodes. The goal is to reduce the average execution time of the computational job. We provide a connection between the problem of characterizing the average execution time of a coded distributed computing system and the problem of analyzing the error probability of codes of length $$n$$ used over erasure channels. Accordingly, we present closed-form expressions for the execution time using binary random linear codes and the best execution time any linear-coded distributed computing system can achieve. It is also shown that there exist good binary linear codes that attain, asymptotically, the best performance any linear code, not necessarily binary, can achieve. We also investigate the performance of coded distributed computing systems using polar and Reed-Muller (RM) codes that can benefit from low-complexity decoding, and superior performance, respectively, as well as explicit constructions. The proposed framework in this paper can enable efficient designs of distributed computing systems given the rich literature in the channel coding theory. 

   more » « less
3. Capacity-achieving Polar-based LDGM Codes with Crowdsourcing Applications

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

   Pang, James (June 2020, Proceedings of IEEE International symposium on information theory)

   In this paper we study codes with sparse generator matrices. More specifically, codes with a certain constraint on the weight of all the columns in the generator matrix are considered. The end result is the following. For any binary-input memoryless symmetric (BMS) channel and any e>0.085, we show an explicit sequence of capacity-achieving codes with all the column wights of the generator matrix upper bounded by (log N) to the power (1+e), where N is the code block length. The constructions are based on polar codes. Applications to crowdsourcing are also shown. 

   more » « less
4. Decoding Reed–Muller Codes Using Redundant Code Constraints

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

   Lian, Mengke; Hager, Christian; Pfister, Henry D. (June 2020, 2020 IEEE International Symposium on Information Theory (ISIT))

   The recursive projection-aggregation (RPA) decoding algorithm for Reed-Muller (RM) codes was recently introduced by Ye and Abbe. We show that the RPA algorithm is closely related to (weighted) belief-propagation (BP) decoding by interpreting it as a message-passing algorithm on a factor graph with redundant code constraints. We use this observation to introduce a novel decoder tailored to high-rate RM codes. The new algorithm relies on puncturing rather than projections and is called recursive puncturing-aggregation (RXA). We also investigate collapsed (i.e., non-recursive) versions of RPA and RXA and show some examples where they achieve similar performance with lower decoding complexity. 

   more » « less
5. Almost Optimal Scaling of Reed-Muller Codes on BEC and BSC Channels

   Hassani, Hamed; Kudekar, Shrinivas; Ordentlich, Or; Polyanskiy, Yury; Urbanke, Rudiger (June 2018, 2018 IEEE Int. Symp. Inf. Theory (ISIT))

   Consider a binary linear code of length N, minimum distance dmin, transmission over the binary erasure channel with parameter 0 <  < 1 or the binary symmetric channel with parameter 0 <  < 1 2 , and block-MAP decoding. It was shown by Tillich and Zemor that in this case the error probability of the block-MAP decoder transitions “quickly” from δ to 1−δ for any δ > 0 if the minimum distance is large. In particular the width of the transition is of order O(1/ √ dmin). We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as Θ(1/N 1 2 −κ ), for any κ > 0, even if the minimum distance of the code is not linear. This condition applies e.g., to Reed-Mueller codes. Since Θ(1/N 1 2 ) is the smallest transition possible for any code, we speak of “almost” optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacity-achieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the Blowing-Up Lemma. 

   more » « less