More Like this

1. Capacity-Achieving Polar-Based Codes With Sparsity Constraints on the Generator Matrices

   https://doi.org/10.1109/TCOMM.2023.3282603  

   Pang, James Chin-Jen; Mahdavifar, Hessam; Pradhan, S. Sandeep (September 2023, IEEE Transactions on Communications)

   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$$ . 

   more » « less
2. Channel coding at low capacity

   Fereydounian, Mohammad; Hassani, Hamed; Jamal, Vahid; Mahdavifar, Hessam (August 2023, IEEE journal on selected areas in information theory)

   Low-capacity scenarios have become increasingly important in the technology of the In- ternet of Things (IoT) and the next generation of wireless networks. Such scenarios require efficient and reliable transmission over channels with an extremely small capacity. Within these constraints, the state-of-the-art coding techniques may not be directly applicable. More- over, the prior work on the finite-length analysis of optimal channel coding provides inaccurate predictions of the limits in the low-capacity regime. In this paper, we study channel coding at low capacity from two perspectives: fundamental limits at finite length and code construc- tions. We first specify what a low-capacity regime means. We then characterize finite-length fundamental limits of channel coding in the low-capacity regime for various types of channels, including binary erasure channels (BECs), binary symmetric channels (BSCs), and additive white Gaussian noise (AWGN) channels. From the code construction perspective, we charac- terize the optimal number of repetitions for transmission over binary memoryless symmetric (BMS) channels, in terms of the code blocklength and the underlying channel capacity, such that the capacity loss due to the repetition is negligible. Furthermore, it is shown that capacity- achieving polar codes naturally adopt the aforementioned optimal number of repetitions. 

   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. Finite-Blocklength Performance of Sequential Transmission over BSC with Noiseless Feedback

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

   Yang, Hengjie; Wesel, Richard D. (June 2020, 2020 IEEE International Symposium on Information Theory (ISIT))

   null (Ed.)

   In this paper, we consider the problem of sequential transmission over the binary symmetric channel (BSC) with full, noiseless feedback. Naghshvar et al. proposed a one-phase encoding scheme, for which we refer to as the small-enough difference (SED) encoder, which can achieve capacity and Burnashev's optimal error exponent for symmetric binary-input channels. They also provided a non-asymptotic upper bound on the average blocklength, which implies an achievability bound on rates. However, their achievability bound is loose compared to the simulated performance of SED encoder, and even lies beneath Polyanskiy's achievability bound of a system limited to stop feedback. This paper significantly tightens the achievability bound by using a Markovian analysis that leverages both the submartingale and Markov properties of the transmitted message. Our new non-asymptotic lower bound on achievable rate lies above Polyanskiy's bound and is close to the actual performance of the SED encoder over the BSC. 

   more » « less
5. Smoothing of Binary Codes, Uniform Distributions, and Applications

   https://doi.org/10.3390/e25111515  

   Pathegama, Madhura; Barg, Alexander (November 2023, Entropy)

   The action of a noise operator on a code transforms it into a distribution on the respective space. Some common examples from information theory include Bernoulli noise acting on a code in the Hamming space and Gaussian noise acting on a lattice in the Euclidean space. We aim to characterize the cases when the output distribution is close to the uniform distribution on the space, as measured by the Rényi divergence of order α∈(1,∞]. A version of this question is known as the channel resolvability problem in information theory, and it has implications for security guarantees in wiretap channels, error correction, discrepancy, worst-to-average case complexity reductions, and many other problems. Our work quantifies the requirements for asymptotic uniformity (perfect smoothing) and identifies explicit code families that achieve it under the action of the Bernoulli and ball noise operators on the code. We derive expressions for the minimum rate of codes required to attain asymptotically perfect smoothing. In proving our results, we leverage recent results from harmonic analysis of functions on the Hamming space. Another result pertains to the use of code families in Wyner’s transmission scheme on the binary wiretap channel. We identify explicit families that guarantee strong secrecy when applied in this scheme, showing that nested Reed–Muller codes can transmit messages reliably and securely over a binary symmetric wiretap channel with a positive rate. Finally, we establish a connection between smoothing and error correction in the binary symmetric channel. 

   more » « less