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
Capacityachieving Polarbased LDGM Codes with Crowdsourcing Applications
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 binaryinput memoryless symmetric (BMS) channel and any e>0.085, we show an explicit sequence of capacityachieving 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
 NSFPAR ID:
 10195605
 Date Published:
 Journal Name:
 Proceedings of IEEE International symposium on information theory
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


This paper gives a simple method to construct generator matrices with polynomial entries (and hence offers an alternative encoding method to the one commonly used) for all quasicyclic lowdensity paritycheck (QCLDPC) codes, even for those that are rank deficient. The approach is based on constructing a set of codewords with the desired total rank by using minors of the paritycheck matrix. We exemplify the method on several wellknown and standard codes. Moreover, we explore the connections between the minors of the paritycheck matrix and the known upper bound on minimum distance and provide a method to compute the rank of any paritycheck matrix representing a QCLDPC code, and hence the dimension of the code, by using the minors of the corresponding polynomial paritycheck matrix.more » « less

We introduce two generalizations to the paradigm of using Random KhatriRao Product (RKRP) codes for distributed matrix multiplication. We first introduce a class of codes called Sparse Random KhatriRao Product (SRKRP) codes which have sparse generator matrices. SRKRP codes result in lower encoding, computation and communication costs than RKRP codes when the input matrices are sparse, while they exhibit similar numerical stability to other state of the art schemes. We empirically study the relationship between the probability of the generator matrix (restricted to the set of nonstragglers) of a randomly chosen SRKRP code being rank deficient and various parameters of the coding scheme including the degree of sparsity of the generator matrix and the number of nonstragglers. Secondly, we show that if the master node can perform a very small number of matrix product computations in addition to the computations performed by the workers, the failure probability can be substantially improved.more » « less

null (Ed.)A bstract There is a rich connection between classical errorcorrecting codes, Euclidean lattices, and chiral conformal field theories. Here we show that quantum errorcorrecting codes, those of the stabilizer type, are related to Lorentzian lattices and nonchiral CFTs. More specifically, real selfdual stabilizer codes can be associated with even selfdual Lorentzian lattices, and thus define Narain CFTs. We dub the resulting theories code CFTs and study their properties. Tduality transformations of a code CFT, at the level of the underlying code, reduce to code equivalences. By means of such equivalences, any stabilizer code can be reduced to a graph code. We can therefore represent code CFTs by graphs. We study code CFTs with small central charge c = n ≤ 12, and find many interesting examples. Among them is a nonchiral E 8 theory, which is based on the root lattice of E 8 understood as an even selfdual Lorentzian lattice. By analyzing all graphs with n ≤ 8 nodes we find many pairs and triples of physically distinct isospectral theories. We also construct numerous modular invariant functions satisfying all the basic properties expected of the CFT partition function, yet which are not partition functions of any known CFTs. We consider the ensemble average over all code theories, calculate the corresponding partition function, and discuss its possible holographic interpretation. The paper is written in a selfcontained manner, and includes an extensive pedagogical introduction and many explicit examples.more » « less

null (Ed.)Abstract—We study a problem of constructing codes that transform a channel with high bit error rate (BER) into one with low BER (at the expense of rate). Our focus is on obtaining codes with smooth (“graceful”) inputoutput BER curves (as opposed to thresholdlike curves typical for long errorcorrecting codes). This paper restricts attention to binary erasure channels (BEC) and contains two contributions. First, we introduce the notion of Low Density Majority Codes (LDMCs). These codes are nonlinear sparsegraph codes, which output majority function evaluated on randomly chosen small subsets of the data bits. This is similar to Low Density Generator Matrix codes (LDGMs), except that the XOR function is replaced with the majority. We show that even with a few iterations of belief propagation (BP) the attained inputoutput curves provably improve upon performance of any linear systematic code. The effect of nonlinearity bootstraping the initial iterations of BP, suggests that LDMCs should improve performance in various applications where LDGMs have been used traditionally. Second, we establish several twopoint converse bounds that lower bound the BER achievable at one erasure probability as a function of BER achieved at another one. The novel nature of our bounds is that they are specific to subclasses of codes (linear systematic and nonlinear systematic) and outperform similar bounds implied by the area theorem for the EXIT functionmore » « less