跳转到内容
Jason's Study

Polar 极化码 — 把好坏不一的信道整成"完美/全错"两组

是什么

Polar Codes（极化码）是一套纠错编码方案——通过递归”变换”，把 N 个一样的信道硬生生分成两组：一组变得”几乎完美”（一定能送达），另一组变得”几乎全错”（一定丢）。然后只往”完美”那组传真正的数据，“全错”那组塞预先约定的 0（叫冻结位）。

日常类比：你要寄 100 张明信片，但其中一些容易丢。怎么办？把它们两两配对洗牌——洗完后能识别出”一定能送达”的 70 张和”一定丢”的 30 张。你只往安全的 70 张写信息，会丢的 30 张写”0”占位。这听起来像魔术，但土耳其学者 Arıkan 在 2009 年用数学严格证明了：只要洗牌方式选对、N 足够大，就一定能极化。

为什么重要

四件事让 Polar 在编码理论史里地位特殊：

  1. 第一个理论上达到 shannon-1948 信道容量上界的实用码。Reed-Solomon、Turbo、LDPC 都很接近，但都不等于。Polar 是数学上严格”=”。
  2. 5G NR 控制信道（PDCCH / PUCCH）2018 年正式采用。每一台 5G 手机里都跑这套数学。
  3. 6G 候选标准之一。学术界讨论中。
  4. 学术界 50 年的”圣杯”。1948 Shannon 立下”容量可达”承诺后，60 年没人能严格构造一个达到的码。2009 年一篇文章解决——地位类似 Wiles 证费马大定理。

核心要点

Polar 编码做三件事，可以拆成 三步：

  1. 极化（Polarize）：把 N 路平均信道通过递归 XOR 组合变成 N 个虚拟子信道。其中一些容量趋近 1（完美），一些趋近 0（无用），中间地带消失。类比：100 张明信片洗牌后能识别出”必送达”和”必丢”两组。

  2. 选位（Information Set Selection）：找出哪些子信道是”好”的。指标叫 Bhattacharyya 参数 Z——Z 越接近 0 越好，越接近 1 越坏。把 N 个 Z 排序，挑最小的 K 个用来传数据，其余 N - K 个塞 0。

  3. 解码（Successive Cancellation, SC）：从前往后逐位推。已知前面解出的位加上收到的信号，推出当前位。冻结位直接用 0 不需要推。

三步都靠一个 2×2 矩阵 F = [[1, 0], [1, 1]] 反复做 Kronecker 积——简洁到不可思议。

实践案例

案例 1：N = 4 时的极化变换

最小例子：把 4 个一样的信道 W 变成 4 个有等级的子信道。

输入 4 个比特 u₁, u₂, u₃, u₄；编码后送出 4 个比特 x₁, x₂, x₃, x₄。蝶形结构：

u₁ ─⊕────⊕── x₁
     │    │
u₂ ──┘─⊕──┴── x₂
        │
u₃ ─⊕──┴────── x₃
     │
u₄ ──┴───────── x₄

总共 4 个 XOR 步骤。从接收端看：

  • 解 u₁ 最难——它影响所有 x
  • 解 u₄ 最易——它只影响 x₄
  • u₁ → “差信道”，u₄ → “好信道”

案例 2：N = 8 怎么挑哪些子信道传数据

用 Bhattacharyya 参数 Z 追踪”信道质量”。Z ∈ [0, 1]，越小越好。

BEC（二元擦除信道，擦除率 0.5）上 Z 的递推非常简洁：

# 把父信道 Z 拆成两个子信道
z_minus = 2 * z - z * z   # 第一个变差（z 增大）
z_plus  = z * z            # 第二个变好（z 减小）

从 Z = 0.5 起步，递归 3 次（n=3，N=8）：

第 0 层:  [0.5]
第 1 层:  [0.75, 0.25]
第 2 层:  [0.9375, 0.5625, 0.4375, 0.0625]
第 3 层:  [0.996, 0.879, 0.809, 0.379, 0.621, 0.191, 0.121, 0.004]

排序选最小的 4 个（K=4）：索引 7, 6, 5, 3 是好信道，传数据；其余 4 个塞 0。

案例 3：5G LDPC vs Polar 的分工

3GPP 5G NR 规定：

  • 数据信道（PDSCH/PUSCH）用 LDPC——每次传几千到上万比特，长块场景 LDPC 占优
  • 控制信道（PDCCH/PUCCH）用 Polar——每次传几十到几百比特，短块场景 Polar 占优

为什么不一种码统一？因为没有一种码在所有块长都最优。Polar 在短块上数学保证可达容量、SCL + CRC 解码低延迟；LDPC 在长块上迭代解码并行度高、错误地板低。

踩过的坑

  1. SC 解码会”早期错误传播”：前面一位解错，后面全错。实际 5G 用 SCL（List Decoding）+ CRC 辅助——同时跟踪 L=8 条候选路径，最后用 CRC 选对的那条。但论文严格证明的”达到容量”只对 SC + N→∞ 成立，工程部署没有这种保证。

  2. “Polar 是 5G 唯一编码”是误解：5G 数据信道（占带宽 95% 以上）是 LDPC，Polar 只在控制信道。说”5G 用 Polar”应该说全”5G 控制信道用 Polar”。

  3. Polar 不是所有场景都最优：块长 ≥ 4096 比特时，LDPC 错误率反而更低。卫星通信（DVB-S2X）至今用 LDPC 没切。

  4. 递推公式简洁但只在 BEC 上精确：z_plus = z² 和 z_minus = 2z - z² 仅在 BEC 信道精确，BSC / AWGN 上是上界。实际选信息位需要蒙特卡洛 / 高斯近似 / 密度演化。

适用 vs 不适用场景

适用：

  • 短块编码（≤ 1024 比特）+ 低延迟需求 → 5G 控制信道、IoT 控制信令
  • 需要严格容量可达性数学保证的理论研究
  • 硬件并行度要求中等的场景（SC/SCL 比迭代 BP 更可控）

不适用：

  • 长块编码（≥ 4096 比特） → LDPC 性能更好
  • 需要极高并行度的解码 → LDPC 的消息传递天然并行，SCL 内在串行
  • 完全不同的信道模型（光纤 / 量子） → Polar 设计基于二元 DMC

历史小故事（可跳过）

  • 1948 年：shannon-1948 提出”信道容量”概念，证明”R < C 时容量可达”——但只是存在性证明，没说怎么构造。这成了 60 年开放问题。
  • 1962 年：Gallager 提出 LDPC（Low-Density Parity-Check）码，但当时算力不足，被遗忘。
  • 1993 年：Berrou 等人提出 Turbo 码，性能接近 Shannon 容量上界——但只是经验性接近，没数学保证。
  • 1996 年：MacKay 重新发现 LDPC，用现代迭代解码后性能也接近上界。仍只是经验。
  • 2009 年：Arıkan 在《Channel Polarization》里证明：Polar 码 + SC 解码器，N → ∞ 时块差错率 ≤ N · 2^{-N^β}（β < 1/2），严格达到 Shannon 容量。
  • 2016 年：3GPP RAN1 #87 会议（Reno），正式选 Polar 入 5G 控制信道。
  • 2018 年：5G NR 商用，Polar 进入手机。
  • 2023 年起：6G 标准化讨论，Polar 是主候选之一。

Arıkan 1986 年从 MIT 拿博士回到 Bilkent University（土耳其安卡拉），独自一人花了 23 年想清楚这件事。论文被引超 9000 次。

学到什么

  1. 递归同质块能产生涌现——一堆相同的中等信道反复 XOR 组合后，群体性质发生相变（50% 完美 + 50% 无用，中间消失）。这种”简单结构 + 递归 → 涌现”是好几个领域共同范式。
  2. 理论 → 算法 → 工程，每一步隔 10 年——1948 立 → 2009 解 → 2018 部署。等不及的人做不出。
  3. 数学终结一个开放问题，地位等同 Wiles 证费马大定理——Polar 是 60 年问题的句号。这种历史性收尾在工程领域不多。
  4. “标准化胜出 ≠ 技术胜出”——5G 控制信道选 Polar 是技术、专利布局、公司游说的复合结果。下一代未必延续。

延伸阅读

关联

  • shannon-1948 —— Shannon 立下的”容量可达”承诺，2009 年被 Polar 兑现
  • turing-1936 —— 可计算性奠基；Polar 的 SC 解码本身是可计算过程的具体例子

反向链接