skip to main content


This content will become publicly available on August 16, 2024

Title: Channel coding at low capacity
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
Award ID(s):
1910056
NSF-PAR ID:
10490379
Author(s) / Creator(s):
; ; ;
Publisher / Repository:
IEEE
Date Published:
Journal Name:
IEEE journal on selected areas in information theory
ISSN:
2641-8770
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Low-capacity scenarios have become increasingly important in the technology of Internet of Things (IoT) and the next generation of mobile networks. Such scenarios require efficient and reliable transmission of information over channels with an extremely small capacity. Within these constraints, the performance of state-of-the-art coding techniques is far from optimal in terms of either rate or complexity. Moreover, the current non-asymptotic laws of optimal channel coding provide inaccurate predictions for coding in the low-capacity regime. In this paper, we provide the first comprehensive study of channel coding in the low-capacity regime. We will investigate the fundamental non-asymptotic limits for channel coding as well as challenges that must be overcome for efficient code design in low-capacity scenarios. 
    more » « less
  2. Low-capacity scenarios have become increasingly important in the technology of Internet of Things (IoT) and the next generation of mobile networks. Such scenarios require efficient and reliable transmission of information over channels with an extremely small capacity. Within these constraints, the performance of state-of-the-art coding techniques is far from optimal in terms of either rate or complexity. Moreover, the current non-asymptotic laws of optimal channel coding provide inaccurate predictions for coding in the low-capacity regime. In this paper, we provide the first comprehensive study of channel coding in the low-capacity regime. We will investigate the fundamental non-asymptotic limits for channel coding as well as challenges that must be overcome for efficient code design in low-capacity scenarios. 
    more » « less
  3. 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
  4. 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
  5. In this paper, we consider the equivocation of finite blocklength coset codes when used over binary erasure wiretap channels. We make use of the equivocation matrix in comparing codes that are suitable for scenarios with noisy channels for both the intended receiver and an eavesdropper. Equivocation matrices have been studied in the past only for the binary erasure wiretap channel model with a noiseless channel for the intended recipient. In that case, an exact relationship between the elements of equivocation matrices for a code and its dual code was identified. The majority of work on coset codes for wiretap channels only addresses the noise-free main channel case, and extensions to noisy main channels require multi-edge type codes. In this paper, we supply a more insightful proof for the noiseless main channel case, and identify a new dual relationship that applies when two-edge type coset codes are used for the noisy main channel case. The end result is that the elements of the equivocation matrix for a dual code are known precisely from the equivocation matrix of the original code according to fixed reordering patterns. Such relationships allow one to study the equivocation of codes and their duals in tandem, which simplifies the search for best and/or good finite blocklength codes. This paper is the first work that succinctly links the equivocation/error correction capabilities of dual codes for two-edge type coset coding over erasure-prone main channels. 
    more » « less