2025-11-20T14:55:15.130233

On the Weight Spectrum of Rate-Compatible Polar Codes

Ye, Li, Liu et al.
The weight spectrum plays a crucial role in the performance of error-correcting codes. Despite substantial theoretical exploration of polar codes with mother code length, a framework for the weight spectrum of rate-compatible polar codes remains elusive. In this paper, we address this gap by presenting the theoretical results for enumerating the number of minimum-weight codewords for quasi-uniform punctured, Wang-Liu shortened, and bit-reversal shortened decreasing polar codes. Additionally, we propose efficient algorithms for computing the average spectrum of random upper-triangular pre-transformed shortened and punctured polar codes. Notably, our algorithms operate with polynomial complexity relative to the code length. Simulation results affirm that our findings yield a precise estimation of the performance of rate-compatible polar codes.
academic

On the Weight Spectrum of Rate-Compatible Polar Codes

基本信息

  • 论文ID: 2410.19242
  • 标题: On the Weight Spectrum of Rate-Compatible Polar Codes
  • 作者: Zicheng Ye, Yuan Li, Zhichao Liu, Huazi Zhang, Jun Wang, Guiying Yan, Zhiming Ma
  • 分类: cs.IT math.IT
  • 发表时间: 2024年10月
  • 论文链接: https://arxiv.org/abs/2410.19242

摘要

权重谱在纠错码性能中起着至关重要的作用。尽管对母码长度的极化码进行了大量理论探索，但速率兼容极化码的权重谱框架仍然难以捉摸。本文通过提出准均匀删余、Wang-Liu缩短和比特反转缩短递减极化码的最小权重码字数量枚举的理论结果来解决这一空白。此外，我们提出了计算随机上三角预变换缩短和删余极化码平均谱的高效算法。值得注意的是，我们的算法相对于码长具有多项式复杂度。仿真结果证实我们的发现对速率兼容极化码的性能给出了精确估计。

研究背景与动机

问题背景

  1. 极化码的局限性: 极化码由于其Kronecker乘积的固有结构，原始码长被限制为2的幂次。然而，实际应用通常需要传输不同码长的消息，这需要删余(puncturing)和缩短(shortening)技术来提供必要的码长灵活性。
  2. 权重谱的重要性: 权重谱对最大似然(ML)解码性能有重大影响，可以通过基于低权重码字数量的联合界进行近似。然而，计算精确权重谱的复杂度通常随码长呈指数增长。
  3. 现有研究的不足: 尽管对母码长度的极化码权重谱有大量研究，但对速率兼容极化码权重谱的系统性框架仍然缺失。现有方法要么复杂度过高，要么适用范围有限。

研究动机

本文旨在填补速率兼容极化码权重谱理论的空白，为准均匀删余(QUP)、Wang-Liu缩短和比特反转缩短极化码提供系统的权重谱分析框架。

核心贡献

  1. 理论贡献: 提出了计算QUP、Wang-Liu缩短和比特反转缩短递减极化码最小权重码字数量的完整理论框架和公式。
  2. 算法创新: 开发了计算随机上三角预变换缩短和删余极化码平均权重谱的多项式复杂度算法。
  3. 性能评估: 通过仿真验证了所提方法能够精确估计速率兼容极化码的性能，特别是在高信噪比条件下。
  4. 复杂度优化: 所有提出的算法都具有相对于码长的多项式复杂度，确保了方法的可扩展性和实用性。

方法详解

任务定义

本文研究的核心任务是计算速率兼容极化码的权重谱，特别是最小权重码字的数量。给定信息集I和速率匹配模式(删余或缩短模式)，目标是确定码字权重的分布。

理论基础

极化码的单项式表示

极化码可以描述为环F₂x₁,...,xₘ/(x₁²-x₁,...,xₘ²-xₘ)中的单项式码。单项式集合定义为：

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

递减单项式码

信息集I⊆M是递减的，如果∀f≼g且g∈I，则f∈I。这里≼表示单项式的偏序关系。

核心算法

1. 比特反转缩短极化码

定理2: 设C(I,Y'ᵢ)是长度为N=2ᵐ的缩短递减r阶极化码，缩短模式为Y'ᵢ。对于度数为r的单项式f，最小权重d=2^(m-r)的码字数量为：

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

其中βf(i)是f在Y'ᵢ中的因子数量。

算法1描述了计算过程：

  • 复杂度：O(|Y'||Iᵣ|) = O(N²)
  • 对每个度数为r的单项式f，计算其被缩短的因子数量
  • 递归更新剩余码字数量

2. QUP极化码

通过引理5建立了迭代方程来计算Pf(d,a)：

对于单项式f = xᵢ₁...xᵢₜ，定义Nf(w,a)为前a位中权重为w的码字数量，则：

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

3. 预变换极化码平均权重谱

定理7给出了预变换极化码的平均权重谱：

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

通过算法3实现，复杂度为O(N³)。

技术创新点

  1. 统一框架: 首次为多种速率匹配模式提供统一的权重谱分析框架。
  2. 多项式复杂度: 所有算法都实现了多项式复杂度，突破了传统指数复杂度的限制。
  3. 对称性利用: 巧妙利用码字的对称性质简化计算，如Wang-Liu缩短可通过QUP的对称性得到。
  4. 递归分解: 通过将长度N的码分解为两个长度N/2的子码来降低计算复杂度。

实验设置

数据集和参数

  • 码长：N = 32, 96, 768, 896等
  • 信息位数：K = 24, 48, 72, 192, 384, 576等
  • 信息集选择：基于高斯近似(GA)方法
  • 预变换：PC-polar码(使用5长度循环移位寄存器)

评价指标

  • 最小权重dₘᵢₙ和最小权重码字数量Aₘᵢₙ
  • 联合界(Union Bound)计算的误块率(BLER)
  • SCL解码(列表大小32)的实际性能

对比方法

  • SCL解码收集的权重谱
  • 传统的指数复杂度精确计算方法
  • 概率方法的近似结果

实验结果

主要结果

表2显示了理论计算与SCL解码收集结果的对比：

  • 当删余位数较少时，理论下界与实际值完全吻合
  • 删余位数增加时，下界可能显著小于实际值，这是因为高权重码字在删余后可能变为低权重

表3展示了不同码的最小权重和最小权重码字数量：

  • QUP：dₘᵢₙ = 12, Aₘᵢₙ = 56 (96,24码)
  • Wang-Liu缩短：dₘᵢₙ = 16, Aₘᵢₙ = 292
  • 比特反转缩短：dₘᵢₙ = 16, Aₘᵢₙ = 490

性能验证

图1-8显示了联合界与SCL解码性能的对比：

  • 在高信噪比下，理论联合界与实际SCL性能高度吻合
  • 对于预变换极化码，平均权重谱同样能准确预测性能
  • 验证了所提方法的准确性和实用性

复杂度分析

  • 算法1（比特反转缩短）：O(N²)
  • 算法2（QUP）：O(N³)
  • 算法3（预变换平均谱）：O(N³)

相关工作

极化码权重谱研究

  • Bardet等人将极化码视为递减单项式码，应用LTA自同构确定最小权重码字数量
  • 后续研究量化了1.5wₘᵢₙ和2wₘᵢₙ以下权重的码字数量

算法方法

  • SCL解码收集低权重码字的方法
  • 多项式复杂度的概率近似方法
  • 树交集方法降低计算复杂度

预变换极化码

  • CRC辅助、奇偶校验、PAC码等预变换方法
  • 上三角预变换不降低码距离的理论证明
  • 平均权重谱的递归公式

结论与讨论

主要结论

  1. 建立了速率兼容极化码权重谱的完整理论框架
  2. 提供了多项式复杂度的高效算法
  3. 理论预测与实际性能高度吻合，特别是在高信噪比下

局限性

  1. 对于大量删余的情况，最小权重码字数量的下界可能不够紧
  2. 算法复杂度虽为多项式，但对于极长码仍可能面临计算挑战
  3. 主要关注递减极化码，对非递减码的适用性有限

未来方向

  1. 改进删余码权重谱的紧界估计
  2. 扩展到更一般的极化码构造方法
  3. 研究权重谱与其他性能指标的关系

深度评价

优点

  1. 理论完备性: 首次为多种速率匹配模式提供统一的理论框架，填补了重要理论空白
  2. 算法效率: 实现多项式复杂度是重大突破，使大码长的权重谱计算成为可能
  3. 实验验证: 充分的仿真验证了理论的准确性，特别是联合界与实际性能的吻合度
  4. 实用价值: 方法可直接用于极化码性能预测和优化设计

不足

  1. 下界松弛: 对于高删余率情况，理论下界可能显著低估实际值
  2. 适用范围: 主要适用于递减极化码，限制了普适性
  3. 复杂度: 虽然是多项式，但O(N³)对超长码仍有挑战

影响力

  1. 学术贡献: 为极化码理论提供了重要的分析工具，推进了该领域的理论发展
  2. 实用价值: 为5G/6G通信系统中极化码的设计和优化提供理论支撑
  3. 方法论: 多项式复杂度算法的设计思路对其他编码理论问题具有借鉴意义

适用场景

  1. 通信系统设计: 5G NR、卫星通信等需要速率兼容极化码的场景
  2. 性能分析: 需要快速准确预测极化码性能的应用
  3. 码字优化: 基于权重谱进行极化码构造和参数优化

参考文献

论文引用了40篇重要文献，涵盖了极化码基础理论、权重谱分析、预变换技术和速率匹配等关键领域，为研究提供了坚实的理论基础。