极化码(Polar Codes)及其串行消除译码
- 提出者
- Erdal Arikan
- 年份
- 2009
- 类型
- recursive error-correcting code
- 类别
- Coding theory
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
极化码由 Erdal Arikan 于 2009 年提出,是首个被证明能够达到对称二元输入无记忆信道香农容量的构造性码族。它们采用递归构造和串行消除译码(successive cancellation decoding),这是一种具有理论保证的简单贪心算法。极化码已被采用于 5G 新空口(NR)的控制信道编码,并正在为未来的 6G 系统进行研究。与(经验性的)Turbo 码和 LDPC 码不同,极化码提供了严格的理论基础。
方法背后的直觉
极化码基于信道极化(channel polarization)的概念:对一组独立同分布的信道应用特定的递归变换,会产生一个新集合,其中一些信道变得几乎无噪声(容量为 1),另一些则变得几乎无用(容量为 0)。信息比特被放置在无噪声信道上;冻结比特(接收方已知)填充无用信道。译码采用串行消除法:按顺序逐比特译码,利用先前译出的比特来精炼对剩余比特的估计。递归结构确保译码复杂度与码长呈线性关系,而极化特性保证了渐近容量逼近性能。
历史学
Arikan 于 2009 年发表的关于信道极化的论文具有变革性:首次证明了一个构造性码族能够以多项式复杂度达到容量。后续研究开发了实用的译码器(置信传播、列表译码)来解决中等信噪比下的错误地板问题。极化码被采用于 3GPP 5G NR Release 15 的控制信道(例如,PBCH、DCI),取代了 Turbo 码。对于数据信道,由于在中等块长下具有更好的经验性能,选择了 LDPC 码。Arikan 荣获 IEEE 信息论学会论文奖,极化码至今仍是活跃的研究领域。
何时使用
极化码特别适用于中短分组长度(100-1000 比特)和严格的延迟要求(无迭代译码)。在 5G/6G 的控制信道或任何优先考虑可证明容量逼近保证的场景中使用极化码。对于非常长的码字(>10k 比特),如果更倾向于 LDPC 的灵活性,则应避免使用极化码。极化码在块衰落信道中表现出色;在平坦衰落中,与 LDPC 相比没有特别优势。
局限与注意事项
- 串行消除在低信噪比下存在指数级错误传播(错误地板)
- 冻结比特设计需要预先知道信道信噪比;需要自适应
- 短块长下的性能不如 LDPC/Turbo 码,除非进行巧妙修改
- 置信传播或列表译码(以缓解错误地板)增加了复杂度,接近 LDPC
- 与 Turbo 码和 LDPC 码相比,实现生态系统不够成熟
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 首个具有香农容量逼近证明的构造性码族
- 简单的串行消除译码;线性时间复杂度 O(N log N)
- 递归结构支持硬件高效实现
- 无迭代处理;确定性延迟(对实时系统很重要)
- 用于分析性能和优化码构造的理论框架
- 通过冻结比特选择实现对不同信噪比和块长的固有自适应
应用
- 5G NR 控制信道(PBCH、DCI):短分组可靠传输,具有严格的延迟约束
- 卫星通信:面向任务关键链路的结构化编码,具有确定性译码延迟
- 量子密钥分发:理论安全性结合实际纠错
- 航空航天遥测:具有超高可靠性和有界译码延迟的航天器通信
- 光通信:短距离但高速链路,快速确定性译码至关重要
使用方式
使用方式
信息比特(加上冻结比特)通过一个递归构造的生成矩阵(克罗内克积结构)形成码字。
生成矩阵 G 通过重复克罗内克积 [[1,0],[1,1]] 构建;这产生了递归的极化结构。
编码后的比特被传输;接收到的比特是软值(来自信道的对数似然比)。
串行消除译码器按顺序处理比特:对于比特 i,它计算给定所有先前译出比特和信道观测值的条件对数似然比。
每个比特通过对其 LLR 进行切片来译码(正值 -> 1,负值 -> 0)。如果比特 i 是冻结比特,则使用已知值。译出的比特向前馈送,以精炼剩余比特的 LLR 估计。
常见陷阱
- 使用基本的串行消除在低信噪比下;需要置信传播或列表译码才能获得合理的误码率
- 为错误的信道条件设计冻结比特集;如果实际信噪比与设计信噪比不同,性能会下降
- 假设线性译码复杂度意味着快速译码;每个比特仍需要 LLR 计算,总计为 O(N log N)
- 忽略量化效应;定点 LLR 量化(尤其是分支决策)会影响错误地板
- 未利用自适应性;基于 CSI 反馈的冻结比特重新选择可显著提高性能
常见问题
什么是信道极化及其如何实现容量逼近码?
信道极化将 N 个相同的信道转换为 N 个具有极化容量的信道:一些接近 1(无噪声),另一些接近 0(无用)。高容量信道上的信息比特受到保护;低容量信道被冻结。随着 N 的增长,高容量信道的比例接近香农容量。这种结构允许简单的串行消除译码达到容量。
为什么串行消除在低信噪比下存在错误地板?
串行消除通过利用先前比特估计,一次一个地贪婪地译码一个比特。如果早期比特被错误译码,该错误会传播到所有下游比特,导致级联错误。这种错误地板源于对过去决策的依赖。置信传播或列表译码通过探索替代方案和推迟硬决策来缓解此问题。
如何选择冻结比特?
冻结比特被放置在估计互信息量低(容量低)的信道上。一种方法是模拟目标信噪比和块长下的极化过程,按容量对信道进行排序,然后冻结 K 个容量最低的信道。这需要预先知道信噪比。自适应极化码可以根据反馈或 CSI 估计来更新冻结比特集。
什么是极化码的列表译码?
列表译码不是在每一步都做出单一的硬决策,而是维护一个候选部分码字列表并探索多个路径。处理完所有比特后,选择最佳路径(按似然度)。这显著降低了错误地板,但将复杂度增加到 O(L N log N),其中 L 是列表大小。列表大小 8-32 是典型的;在性能和复杂度之间取得了良好的平衡。
相关方法
参考文献
Arikan, E. (2009). Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Transactions on Information Theory, 55(7), 3051-3073.
打开 DOI 文献已复制。Sasoglu, E., Telatar, I., & Yildirim, E. (2011). Polarization for arbitrary discrete memoryless channels. In Proceedings of the IEEE Information Theory Workshop (ITW), 144-148.
打开出版物文献已复制。