Successive cancellation list decoding of polar codes provides very good performance for short to moderate block lengths. However, the list size required to approach the performance of maximum-likelihood decoding is still not well understood theoretically. This work identifies information-theoretic quantities that are closely related to this required list size. It also provides a natural approximation for these quantities that can be computed efficiently even for very long codes. Simulation results are provided for the binary erasure channel as well as the binary-input additive white Gaussian noise channel.
more »
« less
This content will become publicly available on March 6, 2025
Data-Driven List Polar Decoder for Symmetric and Asymmetric Input Distributions
This paper introduces extensions to data-driven polar decoders, enabling list decoding and accommodating asymmetric input distributions. These are crucial steps to develop data-driven codes that 1) achieve capacity and 2) are competitive in moderate block lengths. We commence by integrating list de- coding into the data-driven polar codes, which significantly alleviates the inherent error propagation issues associated with successive cancellation decoding. Secondly, we expand the applicability of these codes to channels with stationary, non-uniform input distributions by incorporating the Honda-Yamamoto scheme. Both modifications are computationally efficient and do not require an explicit channel model. Numerical results validate the efficacy of our contributions, which offer a robust and versatile coding mechanism for various channel conditions.
more »
« less
- Award ID(s):
- 2308445
- NSF-PAR ID:
- 10519236
- Editor(s):
- Lapidoth, Amos; Moser, Stefan M
- Publisher / Repository:
- ETH Zurich
- Date Published:
- Format(s):
- Medium: X
- Location:
- Zurich, Switzerland
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Error correction coding schemes with local-global decoding are motivated by practical data storage applications where a balance must be achieved between low latency read access and high data reliability. As an example, consider a 4KB codeword, consisting of four 1KB subblocks, that supports a local-global decoding architecture. Local decoding can provide reliable, low-latency access to individual 1KB subblocks under good channel conditions, while global decoding can provide a “safety-net” for recovery of the entire 4KB block when local decoding fails under bad channel conditions. Recently, Ram and Cassuto have proposed such local-global decoding architectures for LDPC codes and spatially coupled LDPC codes. In this paper, we investigate a coupled polar code architecture that supports both local and global decoding. The coupling scheme incorporates a systematic outer polar code and a partitioned mapping of the outer codeword to semipolarized bit-channels of the inner polar codes. Error rate simulation results are presented for 2 and 4 subblocks.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 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
-
This work develops a novel design of joint detection and decoding receiver for multiple-input multiple output (MIMO) wireless transmissions that utilizes polar codes in forward error correction (FEC). To optimize the overall receiver performance, we integrate the polar code constraints during signal detection by relaxing and transforming FEC code constraints from the original Galois field to the real field. We propose a novel joint linear programming (LP) optimization formulation that takes into consideration the transformed polar code constraints when designing a novel receiver robust against practical obstacles including channel state information (CSI) errors, additive noises, co-channel interferences, and pilot contamination. Our newly proposed joint LP formulation can also be integrated with reduced complexity polar decoders such as successive cancellation (SC) and successive cancellation list (SCL) decoders to deliver superior receiver performance at low cost.more » « less
-
This paper introduces the notion of triangulation codes, a family of non-linear codes that 1) admit efficient encoding/decoding 2) their bit error rate deteriorates gracefully as the quality of the erasure channel degrades. Some coding theoretic properties of these codes are established. In the case of transmitting data over the erasure channel, it is shown that, even with sub-optimal decoding, they can achieve lower bit error rate than uncoded transmission for any number of received output symbols.more » « less
