Polar codes constructed with large polarization kernels were recently proven to be able to achieve optimal finite-length scaling properties. However, straightforward decoding for large kernel polar codes introduces a complexity coefficient that is exponential to the kernel sizes, which makes such codes generally believed to be impractical. In this paper, we present a new method that decodes large kernel polar codes with a complexity coefficient that is polynomial to the kernel sizes. This could facilitate the implementation of large kernel polar codes for practical use in the future.Successive cancellation decoding for large kernel polar codes requires calculation on the probabilities of its bit channels. Similar to conventional polar codes, those bit channels follow a recursive relation, which make this calculation boil down to computing the probabilities for bit channels of a single polarization kernel. This kernel-level computation can be shown equivalent to soft-output maximum-likelihood (ML) decoding on a single bit of a linear block code. In our proposed method, we first use linear operations to represent the considered linear block code as a polar code with dynamically frozen bits, and then use a modified polar list decoder to get an approximate value on the soft-output of the desired bit. This method is motivated by the observation that at short block lengths, polar list decoding with a large enough list size can well-approximate ML decoding. The proposed low-complexity method allows us to decode polar codes constructed with a 64 × 64 polarization kernel with scaling exponent µ ≈ 2.87 for the first time.
Polar codes constructed with large polarization kernels were recently proven to be able to achieve optimal finite-length scaling properties. However, straightforward decoding for large kernel polar codes introduces a complexity coefficient that is exponential to the kernel sizes, which makes such codes generally believed to be impractical. In this paper, we present a new method that decodes large kernel polar codes with a complexity coefficient that is polynomial to the kernel sizes. This could facilitate the implementation of large kernel polar codes for practical use in the future.Successive cancellation decoding for large kernel polar codes requires calculation on the probabilities of its bit channels. Similar to conventional polar codes, those bit channels follow a recursive relation, which make this calculation boil down to computing the probabilities for bit channels of a single polarization kernel. This kernel-level computation can be shown equivalent to soft-output maximum-likelihood (ML) decoding on a single bit of a linear block code. In our proposed method, we first use linear operations to represent the considered linear block code as a polar code with dynamically frozen bits, and then use a modified polar list decoder to get an approximate value on the soft-output of the desired bit. This method is motivated by the observation that at short block lengths, polar list decoding with a large enough list size can well-approximate ML decoding. The proposed low-complexity method allows us to decode polar codes constructed with a 64 × 64 polarization kernel with scaling exponent µ ≈ 2.87 for the first time.
A method for efficiently successive cancellation (SC) decoding of polar codes with high-dimensional linear binary kernels (HDLBK) is presented and analyzed. We devise a l-expressions method which can obtain simplified recursive formulas of SC decoder in likelihood ratio form for arbitrary linear binary kernels to reduce the complexity of corresponding SC decoder. By considering the bit-channel transition probabilities WG(⋅)(⋅∣0) and WG(⋅)(⋅∣1) separately, a W-expressions method is proposed to further reduce the complexity of HDLBK based SC decoder. For a m×m binary kernel, the complexity of straightforward SC decoder is O(2mNlogN). With W-expressions, we reduce the complexity of straightforward SC decoder to O(m2NlogN) when m≤16. Simulation results show that 16×16 kernel polar codes offer significant advantages in terms of error performances compared with 2×2 kernel polar codes under SC and list SC decoders.
Successive-cancellation list (SCL) decoding is a widely used and studied decoding algorithm for polar codes. For short blocklengths, empirical evidence shows that SCL decoding with moderate list sizes (say,L≤32) closely matches the performance of maximum-likelihood (ML) decoding. Hashemi et al. proved that on the binary erasure channel (BEC), SCL decoding actually coincides with ML decoding for list sizesL≥2γ, whereγis a new parameter we call the mixing factor. Loosely speaking, the mixing factor counts the number of information bits mixed-in among the frozen bits; more preciselyγ=∣{i∈Fc:i≤max{F}}∣, whereF⊂[n]denotes the set of frozen indices. Herein, we extend the aforementioned result of Hashemi et al. from the BEC to arbitrary binary-input memoryless symmetric channels. Our proof is based on capturing all2γdecoding paths that correspond to theγinformation bits appearing before the last frozen bit, and then finding the most-likely extension for each of these paths efficiently using a nearest coset decoding algorithm introduced herein. Furthermore, we present a hybrid successive-cancellation list (H -SCL) decoding algorithm, which is a hybrid between conventional SCL decoding and nearest coset decoding. We believe that the hybrid algorithm can outperform the conventional SCL decoder with lower decoding complexity.
Polar coding gives rise to the first explicit family of codes that provably achieve capacity for a wide range of channels with efficient encoding and decoding. But how fast can polar coding approach capacity as a function of the code length? In finite-length analysis, the scaling between code length and the gap to capacity is usually measured in terms of the scaling exponent μ. It is well known that the optimal scaling exponent, achieved by random binary codes, is μ = 2. It is also well known that the scaling exponent of conventional polar codes on the binary erasure channel (BEC) is μ = 3.627, which falls far short of the optimal value. On the other hand, it was recently shown that polar codes derived from ℓ × ℓ binary polarization kernels approach the optimal scaling exponent μ = 2 on the BEC as ℓ→∞, with high probability over a random choice of the kernel. Herein, we focus on explicit constructions of ℓ×ℓ binary kernels with small scaling exponent for ℓ ≤ 64. In particular, we exhibit a sequence of binary linear codes that approaches capacity on the BEC with quasi-linear complexity and scaling exponent μℓtransforms an underlying BEC into ℓ bit-channels W1, W2>,..., Wℓ. The erasure probabilities of W1, W2>,..., Wℓ, known as the polarization behavior of Kℓ, determine the resulting scaling exponent μ(Kℓ). We first introduce a class of self-dual binary kernels and prove that their polarization behavior satisfies a strong symmetry property. This reduces the problem of constructing Kℓto that of producing a certain nested chain of only ℓ/2 self-orthogonal codes. We use nested cyclic codes, whose distance is as high as possible subject to the orthogonality constraint, to construct the kernels K32and K64. In order to evaluate the polarization behavior of K32and K64, two alternative trellis representations (which may be of independent interest) are proposed. Using the resulting trellises, we show that μ(K32) = 3.122 and explicitly compute over half of the polarization-behavior coefficients for K64, at which point the complexity becomes prohibitive. To complete the computation, we introduce a Monte-Carlo interpolation method, which produces the estimate μ(K64) ≃ 2.87. We augment this estimate with a rigorous proof that μ(K64) <; 2.97.
Polar codes constructed by large kernels can attain better finite length performance than those originating from Arıkan’s 2 × 2 kernel. However, the successive cancellation (SC) decoding for these polar codes is impractical even for relatively small kernel size ofmbecause complexity of thekernel computationgrows exponentially withm. This research shows whenm> 2, there exists a large amount oflike termsin the kernel computation which yields a ground for facilitating the decoding. By transferring the kernel computation from the probability domain to the likelihood ratio domain (l-domain), the so-calledl-formula method provides an efficient way to combine the like terms in the kernel computation for kernels up to size 11. However, thel-formula method becomes intractable for kernel size beyond 11. To further reduce the computational complexity, this paper proposes aW-formula method which transforms the kernel computation into the probability pair domain (W-domain). Advanced from thel-domain, the numerator and denominator of the likelihood ratio are considered separately, which eases the restrictions of combining like terms. TheW-formula method can combine much more like terms resulting in a significant reduction on the number of sub-formulas for medium kernels (m≤ 16). Furthermore, in theW-domain, sub-formulas become regular and there exist many common sub-formulas whose computations can be shared. Being able to handle kernels of size up to 16, we show that theW-formula based SC decoding achieves a significant complexity reduction over the existing non-approximate SC decoding (thel-formula based SC decoding).
This paper aims to take advantage of the performances of polar decoding techniques for the benefit of binary linear block codes (BLBCs) with the main objective is to study the performances of the SSCL decoding for short-length BLBCs. Polar codes are one of the most recent error-correcting codes to be invented, and they have been mathematically demonstrated to be able to correct all errors under a specific situation, using the successive-cancellation decoder. However, their performances for real-time wireless communications at short block lengths remain less attractive. To take advantage of the performance of these codes in favor of error correction codes of short block length, an adaptation of the simplified successive-cancellation list as a decoder for polar codes for the benefit of short block length binary linear block codes is presented in this paper. This adaptation makes it possible to take advantage of the performances of less complex decoding methods for polar codes for BLBCs with latency and complexity optimization of the standard successive-cancellation list decoder. The experiment shows that the method can achieve the performances of the most famous order statistic decoder for binary linear block codes, which can achieve the performances of maximum-likelihood decoding with computational complexity and memory constraints.