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 closedform expressions for the execution time using binary random linear codes and the best execution time any linearcoded 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 ReedMuller (RM) codes that can benefit from lowcomplexity 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
Decoding Reed–Muller Codes Using MinimumWeight Parity Checks
Reed–Muller (RM) codes exhibit good performance under maximumlikelihood (ML) decoding due to their highly symmetric structure. In this paper, we explore the question of whether the code symmetry of RM codes can also be exploited to achieve nearML performance in practice. The main idea is to apply iterative decoding to a highlyredundant paritycheck (PC) matrix that contains only the minimumweight dual codewords as rows. As examples, we consider the peeling decoder for the binary erasure channel, linearprogramming and belief propagation (BP) decoding for the binaryinput additive white Gaussian noise channel, and bitflipping and BP decoding for the binary symmetric channel. For short block lengths, it is shown that nearML performance can indeed be achieved in many cases. We also propose a method to tailor the PC matrix to the received observation by selecting only a small fraction of useful minimumweight PCs before decoding begins. This allows one to both improve performance and significantly reduce complexity compared to using the full set of minimumweight PCs.
more »
« less
 Award ID(s):
 1718494
 NSFPAR ID:
 10064524
 Date Published:
 Journal Name:
 IEEE International Symposium on Information Theory
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


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 blockMAP decoding. It was shown by Tillich and Zemor that in this case the error probability of the blockMAP 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 ReedMueller 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 capacityachieving 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 BlowingUp Lemma.more » « less

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 classicalquantum purestate channel. In this work, we propose an extension of BPQM to general binaryinput symmetric classicalquantum (BSCQ) channels based on the implementation of a symmetric "paired measurement". While this new pairedmeasurement 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

null (Ed.)This paper proposes a finiteprecision decoding method for lowdensity paritycheck (LDPC) codes that features the three steps of Reconstruction, Computation, and Quantization (RCQ). Unlike MutualInformationMaximization Quantized Belief Propagation (MIMQBP), RCQ can approximate either belief propagation or MinSum decoding. MIMQBP decoders do not work well when the fraction of degree2 variable nodes is large. However, sometimes a large fraction of degree2 variable nodes is used to facilitate a fast encoding structure, as seen in the IEEE 802.11 standard and the DVBS2 standard. In contrast to MIMQBP, the proposed RCQ decoder may be applied to any offtheshelf LDPC code, including those with a large fraction of degree2 variable nodes. Simulations show that a 4bit MinSum RCQ decoder delivers frame error rate (FER) performance within 0.1 dB of floating point belief propagation (BP) for the IEEE 802.11 standard LDPC code in the low SNR region. The RCQ decoder actually outperforms floating point BP and MinSum in the high SNR region were FER less than 10 −5 . This paper also introduces Hierarchical Dynamic Quantization (HDQ) to design the timevarying nonuniform quantizers required by RCQ decoders. HDQ is a lowcomplexity design technique that is slightly suboptimal. Simulation results comparing HDQ and optimal quantization on the symmetric binaryinput memoryless additive white Gaussian noise channel show a mutual information loss of less than 10 −6 bits, which is negligible in practice.more » « less

In general, the generator matrix sparsity is a critical factor in determining the encoding complexity of a linear code. Further, certain applications, e.g., distributed crowdsourcing schemes utilizing linear codes, require most or even all the columns of the generator matrix to have some degree of sparsity. In this paper, we leverage polar codes and the wellestablished channel polarization to design capacityachieving codes with a certain constraint on the weights of all the columns in the generator matrix (GM) while having a lowcomplexity decoding algorithm. We first show that given a binaryinput memoryless symmetric (BMS) channel $W$ and a constant $s \in (0, 1]$ , there exists a polarization kernel such that the corresponding polar code is capacityachieving with the rate of polarization $s/2$ , and the GM column weights being bounded from above by $N^{s}$ . To improve the sparsity versus error rate tradeoff, we devise a columnsplitting algorithm and two coding schemes for BEC and then for general BMS channels. The polarbased codes generated by the two schemes inherit several fundamental properties of polar codes with the original $2 \times 2$ kernel including the decay in error probability, decoding complexity, and the capacityachieving property. Furthermore, they demonstrate the additional property that their GM column weights are bounded from above sublinearly in $N$ , while the original polar codes have some column weights that are linear in $N$ . In particular, for any BEC and $\beta < 0.5$ , the existence of a sequence of capacityachieving polarbased codes where all the GM column weights are bounded from above by $N^{\lambda} $ with $\lambda \approx 0.585$ , and with the error probability bounded by ${\mathcal {O}}(2^{N^{\beta }})$ under a decoder with complexity ${\mathcal {O}}(N\log N)$ , is shown. The existence of similar capacityachieving polarbased codes with the same decoding complexity is shown for any BMS channel and $\beta < 0.5$ with $\lambda \approx 0.631$ .more » « less