More Like this

1. Bounds on the List Size of Successive Cancellation List Decoding

   https://doi.org/10.1109/SPCOM50965.2020.9179593  

   Coskun, Mustafa Cemil; Pfister, Henry D. (July 2020, 2020 International Conference on Signal Processing and Communications (SPCOM))

   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
2. Polar Codes with Local-Global Decoding

   Zhu, Ziyuan; Wu, Wei; Siegel, Paul H. (March 2023, Proceedings of 14th Annual Non-Volatile Memories Workshop)

   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
3. DEEPPOLAR: inventing nonlinear large-kernel polar codes via deep learning

   Hebbar, Ashwin; Ankireddy, Sravan; Kim, Hyeji; Oh, Sewoong; Viswanath, Pramod (July 2024, Gesturz quicknews)

   Progress in designing channel codes has been driven by human ingenuity and, fittingly, has been sporadic. Polar codes, developed on the foundation of Arikan's polarization kernel, represent the latest breakthrough in coding theory and have emerged as the state-of-the-art error-correction code for short-to-medium block length regimes. In an effort to automate the invention of good channel codes, especially in this regime, we explore a novel, non-linear generalization of Polar codes, which we call DEEPPOLAR codes. DEEPPOLAR codes extend the conventional Polar coding framework by utilizing a larger kernel size and parameterizing these kernels and matched decoders through neural networks. Our results demonstrate that these data-driven codes effectively leverage the benefits of a larger kernel size, resulting in enhanced reliability when compared to both existing neural codes and conventional Polar codes. 

   more » « less
4. 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
5. A Joint Detection and Decoding Receiver Design for Polar Coded MIMO Wireless Transmissions

   https://doi.org/10.1109/ISIT.2018.8437879  

   Jalali, Amin; Ding, Zhi (June 2018, 2018 IEEE International Symposium on Information Theory (ISIT))

   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