On the Weight Spectrum of Rate-Compatible Polar Codes

Basic Information

• Paper ID: 2410.19242
• Title: On the Weight Spectrum of Rate-Compatible Polar Codes
• Authors: Zicheng Ye, Yuan Li, Zhichao Liu, Huazi Zhang, Jun Wang, Guiying Yan, Zhiming Ma
• Classification: cs.IT math.IT
• Publication Date: October 2024
• Paper Link: https://arxiv.org/abs/2410.19242

Abstract

The weight spectrum plays a crucial role in the performance of error-correcting codes. Although extensive theoretical exploration has been conducted on polar codes of mother code length, the weight spectrum framework for rate-compatible polar codes remains elusive. This paper addresses this gap by proposing theoretical results for enumerating the number of minimum weight codewords in quasi-uniform puncturing, Wang-Liu shortening, and bit-reversal shortening decreasing polar codes. Furthermore, we present an efficient algorithm for computing the average spectrum of shortened and punctured polar codes with random upper triangular pre-transformation. Notably, our algorithm exhibits polynomial complexity with respect to code length. Simulation results confirm that our findings provide accurate performance estimates for rate-compatible polar codes.

Research Background and Motivation

Problem Background

1. Limitations of Polar Codes: Polar codes are constrained by their inherent Kronecker product structure, with original code length restricted to powers of 2. However, practical applications typically require transmission of messages with different code lengths, necessitating puncturing and shortening techniques to provide the required code length flexibility.
2. Importance of Weight Spectrum: The weight spectrum has significant impact on maximum likelihood (ML) decoding performance and can be approximated through union bounds based on the number of low-weight codewords. However, computing the exact weight spectrum typically exhibits exponential complexity growth with code length.
3. Insufficiency of Existing Research: Although substantial research exists on the weight spectrum of polar codes at mother code length, a systematic framework for the weight spectrum of rate-compatible polar codes remains absent. Existing methods either suffer from excessive complexity or have limited applicability.

Research Motivation

This paper aims to fill the gap in weight spectrum theory for rate-compatible polar codes by providing a systematic weight spectrum analysis framework for quasi-uniform puncturing (QUP), Wang-Liu shortening, and bit-reversal shortening polar codes.

Core Contributions

1. Theoretical Contribution: Proposes a complete theoretical framework and formulas for computing the number of minimum weight codewords in QUP, Wang-Liu shortening, and bit-reversal shortening decreasing polar codes.
2. Algorithmic Innovation: Develops polynomial-complexity algorithms for computing the average weight spectrum of shortened and punctured polar codes with random upper triangular pre-transformation.
3. Performance Evaluation: Validates through simulation that the proposed methods provide accurate performance estimates for rate-compatible polar codes, particularly under high signal-to-noise ratio conditions.
4. Complexity Optimization: All proposed algorithms exhibit polynomial complexity with respect to code length, ensuring scalability and practical applicability.

Methodology Details

Task Definition

The core task studied in this paper is computing the weight spectrum of rate-compatible polar codes, particularly the number of minimum weight codewords. Given an information set I and a rate-matching pattern (puncturing or shortening mode), the objective is to determine the distribution of codeword weights.

Theoretical Foundation

Monomial Representation of Polar Codes

Polar codes can be described as monomial codes in the ring F₂x₁,...,xₘ/(x₁²-x₁,...,xₘ²-xₘ). The monomial set is defined as:

M ≜ {x₁^(a₁)...xₘ^(aₘ) | (a₁,...,aₘ) ∈ F₂ᵐ}

Decreasing Monomial Codes

An information set I⊆M is decreasing if ∀f≼g and g∈I, then f∈I. Here ≼ denotes the partial order relation on monomials.

Core Algorithms

1. Bit-Reversal Shortening Polar Codes

Theorem 2: Let C(I,Y'ᵢ) be a shortened decreasing r-th order polar code of length N=2ᵐ with shortening pattern Y'ᵢ. For a monomial f of degree r, the number of codewords with minimum weight d=2^(m-r) is:

|Tf(d,Y'ᵢ)| = λf(1 - βf(i)/2ʳ)

where βf(i) is the number of factors of f in Y'ᵢ.

Algorithm 1 describes the computation process:

• Complexity: O(|Y'||Iᵣ|) = O(N²)
• For each monomial f of degree r, compute the number of its shortened factors
• Recursively update the number of remaining codewords

2. QUP Polar Codes

Lemma 5 establishes iterative equations for computing Pf(d,a):

For a monomial f = xᵢ₁...xᵢₜ, define Nf(w,a) as the number of codewords with weight w in the first a positions, then:

• When a ≤ 2^(it-1), w≠0: Nf(w,a) = Σₛ∈B(f,t) 2^αf(s)Nf(s)(w,a) + Nf(0)(w,a)
• When 2^(it-1) < a ≤ 2^it: Nf(w,a) = Nf(2^(it-t) - w, 2^it - a)
• When a > 2^it: Nf(w,a) = Nf(w - 2^(it-t), a - 2^it)

3. Average Weight Spectrum of Pre-transformed Polar Codes

Theorem 7 provides the average weight spectrum of pre-transformed polar codes:

E[N(d,T,X)] = Σ₁≤j≤K 2^(K-j)Ad(m,(0₁^(Ij-1),1),X) / 2^(N-Ij)

Implemented through Algorithm 3 with complexity O(N³).

Technical Innovations

1. Unified Framework: First to provide a unified weight spectrum analysis framework for multiple rate-matching modes.
2. Polynomial Complexity: All algorithms achieve polynomial complexity, breaking through the limitation of traditional exponential complexity.
3. Symmetry Exploitation: Cleverly utilizes codeword symmetry properties to simplify computation, such as deriving Wang-Liu shortening from QUP symmetry.
4. Recursive Decomposition: Reduces computational complexity by decomposing codes of length N into two subcodes of length N/2.

Experimental Setup

Datasets and Parameters

• Code lengths: N = 32, 96, 768, 896, etc.
• Number of information bits: K = 24, 48, 72, 192, 384, 576, etc.
• Information set selection: Based on Gaussian Approximation (GA) method
• Pre-transformation: PC-polar codes (using 5-length cyclic shift registers)

Evaluation Metrics

• Minimum weight dₘᵢₙ and number of minimum weight codewords Aₘᵢₙ
• Block Error Rate (BLER) computed via union bound
• Actual performance of SCL decoding (list size 32)

Comparison Methods

• Weight spectrum collected by SCL decoding
• Traditional exponential-complexity exact computation methods
• Approximate results from probabilistic methods

Experimental Results

Main Results

Table 2 shows comparison between theoretical calculations and SCL decoding results:

• When the number of punctured bits is small, theoretical lower bounds perfectly match actual values
• As the number of punctured bits increases, lower bounds may be significantly smaller than actual values, because high-weight codewords may become low-weight after puncturing

Table 3 presents minimum weights and numbers of minimum weight codewords for different codes:

• QUP: dₘᵢₙ = 12, Aₘᵢₙ = 56 (96,24 code)
• Wang-Liu shortening: dₘᵢₙ = 16, Aₘᵢₙ = 292
• Bit-reversal shortening: dₘᵢₙ = 16, Aₘᵢₙ = 490

Performance Verification

Figures 1-8 show comparison between union bounds and SCL decoding performance:

• At high signal-to-noise ratios, theoretical union bounds align closely with actual SCL performance
• For pre-transformed polar codes, average weight spectrum similarly predicts performance accurately
• Validates the accuracy and practicality of the proposed methods

Complexity Analysis

• Algorithm 1 (Bit-reversal shortening): O(N²)
• Algorithm 2 (QUP): O(N³)
• Algorithm 3 (Pre-transformed average spectrum): O(N³)

Related Work

Weight Spectrum Research on Polar Codes

• Bardet et al. treat polar codes as decreasing monomial codes and apply LTA automorphisms to determine the number of minimum weight codewords
• Subsequent research quantifies the number of codewords with weights below 1.5wₘᵢₙ and 2wₘᵢₙ

Algorithmic Methods

• SCL decoding collection methods for low-weight codewords
• Polynomial-complexity probabilistic approximation methods
• Tree intersection methods to reduce computational complexity

Pre-transformed Polar Codes

• Pre-transformation methods including CRC-aided, parity-check, and PAC codes
• Theoretical proof that upper triangular pre-transformation does not reduce code distance
• Recursive formulas for average weight spectrum

Conclusions and Discussion

Main Conclusions

1. Establishes a complete theoretical framework for the weight spectrum of rate-compatible polar codes
2. Provides efficient polynomial-complexity algorithms
3. Theoretical predictions align closely with actual performance, particularly at high signal-to-noise ratios

Limitations

1. For cases with heavy puncturing, lower bounds on the number of minimum weight codewords may not be sufficiently tight
2. Although algorithms have polynomial complexity, they may still face computational challenges for extremely long codes
3. Primarily focuses on decreasing polar codes, with limited applicability to non-decreasing codes

Future Directions

1. Improve tight bound estimates for punctured code weight spectra
2. Extend to more general polar code construction methods
3. Investigate relationships between weight spectrum and other performance metrics

In-Depth Evaluation

Strengths

1. Theoretical Completeness: First to provide a unified theoretical framework for multiple rate-matching modes, filling an important theoretical gap
2. Algorithm Efficiency: Achieving polynomial complexity represents a major breakthrough, enabling weight spectrum computation for long codes
3. Experimental Validation: Comprehensive simulations validate theoretical accuracy, particularly the alignment between union bounds and actual performance
4. Practical Value: Methods can be directly applied to polar code performance prediction and optimization design

Weaknesses

1. Loose Lower Bounds: For high puncturing rates, theoretical lower bounds may significantly underestimate actual values
2. Limited Applicability: Primarily applicable to decreasing polar codes, restricting generality
3. Complexity: Although polynomial, O(N³) complexity remains challenging for ultra-long codes

Impact

1. Academic Contribution: Provides important analytical tools for polar code theory, advancing theoretical development in this field
2. Practical Value: Offers theoretical support for polar code design and optimization in 5G/6G communication systems
3. Methodological Significance: The design approach for polynomial-complexity algorithms has reference value for other coding theory problems

Applicable Scenarios

1. Communication System Design: Applications requiring rate-compatible polar codes such as 5G NR and satellite communications
2. Performance Analysis: Applications requiring rapid and accurate polar code performance prediction
3. Codeword Optimization: Polar code construction and parameter optimization based on weight spectrum

References

The paper cites 40 important references covering fundamental polar code theory, weight spectrum analysis, pre-transformation techniques, and rate-matching, providing a solid theoretical foundation for the research.