2025-11-13T11:37:11.218189

ORCAS Codes: A Flexible Generalization of Polar Codes with Low-Complexity Decoding

Zunker, RÃ¼benacke, Brink

Motivated by the need for channel codes with low-complexity soft-decision decoding algorithms, we consider the recursive Plotkin concatenation of optimal low-rate and high-rate codes based on simplex codes and their duals. These component codes come with low-complexity maximum likelihood (ML) decoding which, in turn, enables efficient successive cancellation (SC)-based decoding. As a result, the proposed optimally recursively concatenated simplex (ORCAS) codes achieve a performance that is at least as good as that of polar codes. For practical parameters, the proposed construction significantly outperforms polar codes in terms of block error rate by up to 0.5 dB while maintaining similar decoding complexity. Furthermore, the codes offer greater flexibility in codeword length than conventional polar codes.

academic

ORCAS Codes: A Flexible Generalization of Polar Codes with Low-Complexity Decoding

基本信息

论文ID: 2508.09744
标题: ORCAS Codes: A Flexible Generalization of Polar Codes with Low-Complexity Decoding
作者: Andreas Zunker, Marvin Rübenacke, Stephan ten Brink (斯图加特大学电信研究所)
分类: cs.IT (信息理论), eess.SP (信号处理), math.IT (数学信息理论)
发表时间: 2025年10月13日 (arXiv v2)
论文链接: https://arxiv.org/abs/2508.09744

低功耗需求: 随着物联网和移动设备的普及，需要具有低复杂度软判决解码算法的信道编码
性能优化: 极化码虽然理论上能达到信道容量，但在实际有限长度下性能受限
灵活性要求: 传统极化码的码长必须是2的幂次，限制了实际应用的灵活性

现有方法局限性

极化码: SC解码下的块错误率(BLER)性能有限，需要外码和列表解码来改善，但显著增加了解码复杂度
BCH-Plotkin级联码: 需要复杂的软判决解码(如OSD)，码率和长度不够灵活
长度匹配: 现有的缩短或删减技术会降低BLER性能

研究动机

提出一种同时具备以下特性的新编码方案：

至少与极化码相当的性能
低复杂度解码
灵活的码长和码率选择

核心贡献

提出ORCAS码构造方法: 基于单纯形码及其对偶码的递归Plotkin级联，实现了极化码的灵活泛化
设计最优组件码:
- 低码率：自然删减重复单纯形(NPRS)码
- 高码率：NPRS对偶(NPRSD)码
开发高效解码算法: 基于快速Hadamard变换(FHT)和Chase-II综合征解码的低复杂度ML解码
提供理论分析: 给出了组件码的权重分布和最优性证明
实现性能提升: 在实际参数下比极化码性能提升0.3-0.5 dB，同时保持相似的解码复杂度

定义：维数k ≤ lb(n)的码为低码率码
构造：通过自然删减重复单纯形码Sk(r)得到
删减规则：删减前a(n,k) = (-n) mod Mk个比特
生成矩阵：重复Bk,Mk的每列ρn,k(i)次，其中： $ρ_{n,k}(i) = \lfloor\frac{n}{M_k}\rfloor + \begin{cases} 1 & \text{if } i > M_k - (n \bmod M_k) \\ 0 & \text{otherwise} \end{cases}$

高码率NPRSD码:

定义：维数k ≥ n-lb(n)的码为高码率码
构造：NPRS码的对偶码
最优性：对于k ≥ n-lb(n)，NPRSD码是渐近BLER最优的

2. 递归设计算法

使用扩展的密度演化(DE)算法进行码设计：

Algorithm 1: ORCAS码构造
输入: SNR Es/N0, 码长n, 码维k
输出: 码率分布r

1. 从设计SNR开始递归分割
2. 对每个(n,k)节点：
   - 如果是叶节点(n∈{2,3,5,7,9})，使用NPRS/NPRSD码
   - 否则继续Plotkin分割
3. 使用union bound估计BLER
4. 选择最优的组件码组合

3. 解码算法

SC解码框架:

使用标准SC算法的LLR更新规则
叶节点调用专用组件码解码器

NPRS解码 (基于FHT):

对重复比特的LLR求和
应用FHT-based单纯形解码器
特殊情况：k=2时退化为CW码(SPC)，k=1时为重复码

NPRSD解码 (基于Chase-II):

使用min近似进行SPC软合并
Chase-II解码：翻转p=lb(n)个最不可靠比特的所有子集
应用综合征解码器

技术创新点

自然删减策略: 相比代数删减，简化了实现但保持了大部分参数的最优性
统一解码框架: 将不同组件码的解码统一在SC框架下
复杂度优化: 通过排序置换将组合选择从二次时间降到线性时间
灵活长度支持: 原生支持非2幂次码长，无需长度匹配

实验设置

参数配置

码长: n ∈ {96, 256, 640}
码率: R ∈ {1/4, 1/2, 3/4}
目标BLER: 10^-6
信道: BI-AWGN with BPSK调制

对比方法

标准极化码(SC解码)
对于非2幂次长度，极化码使用长度匹配技术

长度匹配策略

长度n	码率R=1/4	码率R=1/2	码率R=3/4
96	比特反序删减	自然缩短	自然缩短
640	自然删减	比特反序缩短	自然缩短

评价指标

块错误率(BLER)
解码复杂度(吞吐量测试)
与PPV meta-converse bound的比较

实验结果

主要结果

性能提升:

在所有测试参数下，ORCAS码比极化码性能提升0.3-0.5 dB
对于非2幂次长度(n=96, 640)，提升更为显著
在低BLER区域，DE准确预测实际性能

解码复杂度对比 (码字/秒):

长度n	码	R=1/4	R=1/2	R=3/4
96	Polar	1,727,526	1,281,094	1,435,785
	ORCAS	1,927,945	1,543,126	1,509,279
256	Polar	692,095	586,062	604,761
	ORCAS	763,846	695,437	601,917
640	Polar	277,490	225,396	187,966
	ORCAS	299,271	271,726	317,018