Search for: All records

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 well-established channel polarization to design capacity-achieving codes with a certain constraint on the weights of all the columns in the generator matrix (GM) while having a low-complexity decoding algorithm. We first show that given a binary-input memoryless symmetric (BMS) channel $$W$$ and a constant $$s \in (0, 1]$$ , there exists a polarization kernel such that the corresponding polar code is capacity-achieving 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 trade-off, we devise a column-splitting algorithm and two coding schemes for BEC and then for general BMS channels. The polar-based 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 capacity-achieving 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 capacity-achieving polar-based 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 capacity-achieving polar-based codes with the same decoding complexity is shown for any BMS channel and $$\beta < 0.5$$ with $$\lambda \approx 0.631$$ . 

We consider the rate-limited quantum-to-classical optimal transport in terms of output-constrained rate-distortion coding for discrete quantum measurement systems with limited classical common randomness. The main coding theorem provides the achievable rate region of a lossy measurement source coding for an exact construction of the destination distribution (or the equivalent quantum state) while maintaining a threshold of distortion from the source state according to a generally defined distortion observable. The constraint on the output space fixes the output distribution to an i.i.d. predefined probability mass function. Therefore, this problem can also be viewed as information-constrained optimal transport which finds the optimal cost of transporting the source quantum state to the destination state via an entanglement-breaking channel with limited communication rate and common randomness. 

—In this work, we address the lossy quantum-classical (QC) source coding problem, where the task is to compress the classical information about a quantum source, obtained after performing a measurement, below the Shannon entropy of the measurement outcomes, while incurring a bounded reconstruction error. We propose a new formulation, namely, "rate-channel theory", for the lossy QC source coding problem based on the notion of a backward (posterior) channel. We employ a singleletter posterior channel to capture the reconstruction error in place of the single-letter distortion observable. The formulation requires the reconstruction of the compressed quantum source to satisfy a block error constraint as opposed to the average singleletter distortion criterion in the rate-distortion setting. We also develop an analogous formulation for the classical variant with respect to a corresponding posterior channel. Furthermore, we characterize the asymptotic performance limit of the lossy QC and classical source coding problems in terms of single-letter quantum mutual information and mutual information quantities of the given posterior channel, respectively. We provide examples for the above formulations.