极化码List-Fast-SSC解码器专用排序架构：从算法特性到硬件优化

1. 项目概述在无线通信系统的演进中信道编码技术始终扮演着确保信息可靠传输的基石角色。简单来说它就像给要发送的珍贵数据穿上了一层“防撞盔甲”通过精心设计的冗余信息让数据在充满噪声和干扰的无线信道中“旅行”后接收端依然能准确无误地将其复原。从3G时代的Turbo码到4G广泛采用的LDPC码编码技术的每一次革新都直接推动了通信速率和可靠性的跃升。而极化码的出现无疑是这个领域的一个里程碑。它不仅在理论上被严格证明能够达到信道容量的极限更因其简洁优雅的递归结构成为了5G标准中控制信道的编码方案站上了现代通信技术的舞台中央。然而理论上的完美并不意味着工程实现的轻松。极化码的核心解码算法——连续消除解码及其增强版本在追求更高纠错性能的道路上遇到了一个棘手的工程难题路径管理。尤其是List-Fast-SSC这类列表解码算法它在解码过程中会并行探索多条可能的路径并需要从中实时筛选出最可靠的那几条。这个过程本质上是一个大规模的排序问题。当列表大小L增大或者遇到特定类型的解码节点时需要排序的候选路径数量会急剧膨胀形成一个M*L的庞大矩阵。传统的通用排序网络如奇偶排序或比特排序在处理这种特定结构的数据时会进行大量冗余的比较和交换操作成为解码器硬件设计中面积和延迟的主要瓶颈。想象一下在一个高速解码芯片中排序网络可能占据超过30%的逻辑资源并且其多级比较的延迟直接限制了整个解码流水线的时钟频率。因此针对List-Fast-SSC解码算法的特性设计一个专用的、高效的排序架构就成了一项既关键又富有挑战性的工作。这不仅仅是优化几个比较器那么简单而是需要深入理解算法生成路径的内在规律从数据特性出发重构整个排序流程。本文将要探讨的正是这样一个从算法本质出发通过“先整理再剪枝后合并”的策略显著降低排序复杂度的硬件架构设计。它不仅仅是一个排序器的优化更是连接极化码优异理论性能与高效硬件实现之间的一座关键桥梁对于推动5G及未来B5G/6G系统中高可靠、低功耗解码器的落地具有重要意义。2. 核心思路与架构设计解析面对List-Fast-SSC解码产生的大量候选路径一个最直接的想法是扔给一个强大的通用排序器比如一个8L输入的全排序网络。但这就像用高射炮打蚊子浪费极大。我们的核心思路是反其道而行之与其在混乱中强力排序不如先利用数据的内在规律进行整理和筛选大幅减少需要“精排”的数据量。这个思路可以分解为三个环环相扣的步骤构建有序矩阵、无损剪枝、分层合并排序。2.1 从混沌到有序构建有序候选路径矩阵List-Fast-SSC解码器在处理四种类型的节点Rate-0, Rate-1, REP, SPC时每个源路径会生成不同数量的候选路径。关键洞察在于这些新生成的路径并非完全无序的随机数。Rate-1节点根据其路径度量计算公式可以严格证明从一个源路径l生成的4个候选路径的度量值满足ml1 ≤ ml2 ≤ ml3 ≤ ml4。也就是说每个源路径自己的4个孩子生来就是排好队的。SPC节点情况类似但稍复杂其生成的8个候选路径可以分成两组组内是有序的并且组间也有明确的大小关系。REP节点生成的两个候选路径之间没有固定的大小关系。Rate-0节点最简单不生成新路径直接继承源路径。基于这些观察我们可以进行“初步排序”。目标是将所有M*L个候选路径组织成一个二维矩阵并让它满足两个条件1) 每一行内部是升序排列的2) 每一列内部也是升序排列的。这样的矩阵我们称之为有序候选路径矩阵。如何构建对于Rate-1节点由于每个源路径的4个输出已有序我们只需将来自不同源路径、但相同索引如所有路径的“第一个孩子”的度量值集合起来分别进行排序。即用L个输入的排序器分别对集合{m1_i, m2_i, ..., mL_i}(i1,2,3,4) 进行排序。排序后的结果自然就形成了OCPM的4个有序行。对于SPC节点首先对每组内无序的路径对如ml4和ml5进行两两排序使每个源路径的输出组内有序。然后仿照Rate-1节点的方法对8个索引位置分别进行跨路径的排序最终形成8行有序的矩阵。对于REP节点虽然两个输出之间无序但我们依然可以先对每个源路径的两个输出进行排序使ml‘1 ≤ ml’2。然后再对索引1和索引2的路径集合分别进行排序形成2行有序矩阵。这一步的妙处在于它将一个全局的、复杂的8L排序问题分解为多个并行的、小规模的L排序问题。硬件上这对应着多个小规模排序器如多个奇偶排序网络的并行工作其面积和延迟远小于一个完整的8L排序器。2.2 智慧剪枝剔除必然的“落选者”得到OCPM后一个更强大的优化机会出现了。由于矩阵的行和列都有序我们可以提前判断出哪些路径绝对不可能进入最终的L个最优路径名单从而在进入复杂合并排序前就将它们剔除。核心原理剪枝引理在OCPM中如果对于矩阵中的某个元素mj_i第i行第j列我们能找到至少L个元素小于或等于它那么mj_i就可以被安全地移除因为它不可能跻身前L名。为什么因为排序是稳定的比mj_i小的元素在最终排序中肯定会排在它前面。既然已经有L个或更多这样的“竞争者”mj_i最好的排名也不过是第L1名注定被淘汰。如何高效实施剪枝利用OCPM的严格有序性我们可以从矩阵的左上角最小元素区域向右下角最大元素区域进行“对角线”式的扫描和标记。例如对于一个L8 M8的矩阵我们可以推导出一个确定性的剪枝算法第一行全部保留第二行只保留前L/2个第三行保留更少以此类推。具体保留数量可以根据行号和L值精确计算出来。这个过程是“无损”的因为它只丢弃了确定无用的路径不会影响最终选出真正Top-L路径的正确性。经过这一步需要后续处理的数据量从M*L急剧下降。论文数据显示在L32, M8时高达66.7%的候选路径被提前剔除。这意味着后续最耗资源的合并排序模块其工作量减少了三分之二硬件资源节省的效果将非常显著。2.3 分层合并与兼容性设计剪枝后的路径分布在矩阵的不同行中我们需要将它们合并起来选出全局最优的L条路径。这里采用分层合并排序的策略。行间合并将保留下来的、且彼此有序的行两两配对如第12行第34行…输入到一个剪枝后的合并网络中。这个网络是专门为两个有序序列合并并输出前k个最小值而优化的。它基于经典的奇偶合并排序器但移除了所有与输出前k个结果无关的比较交换单元。经过这一层合并我们得到了一个新的、数据量更小的有序序列集合。性质保持的关键这里有一个重要的引理如果输入的两个行本身来自一个OCPM那么经过这种合并排序后输出的新列依然构成一个OCPM。这个性质使得我们可以递归地应用剪枝算法也就是说在每一层合并之后数据依然保持行列有序我们可以再次应用剪枝规则进一步减少数据量形成一个“合并-剪枝-再合并”的高效流水。最终选择经过几层合并后数据被收敛到少数几个序列。最后一级我们使用一个半清网络源自比特排序器来从最后两个有序序列中高效地挑选出最终的L个最优路径。半清网络的结构非常规整适合硬件实现并且在这一步能高效地完成“二选一”的筛选。兼容性架构为了同时支持Rate-0, Rate-1, REP, SPC四种节点需要设计一个统一的硬件数据通路。整体架构包含前述的三个核心模块初步排序器、剪枝模块、行间合并排序模块。通过配置M1,2,4,8和相应的控制逻辑同一套硬件可以处理不同类型的节点。对于M1Rate-0的情况实际上无需任何排序路径直接传递。这种设计避免了为每种节点类型实例化不同的排序器极大提高了硬件资源的利用率。3. 硬件架构实现细节与优化技巧将上述算法思路映射到高效的硬件电路需要仔细考量数据通路、模块设计、时序和面积权衡。下面我们深入核心模块的实现细节。3.1 初步排序模块的硬件实现初步排序模块的目标是构建OCPM。它主要由两种构件组成两两比较器和L输入排序器。两两比较器用于处理REP节点的ml1, ml2和SPC节点的ml4, ml5。这是一个最简单的比较交换单元每个单元包含一个比较器和一个数据选择器多路复用器。对于L条路径这部分需要L个这样的单元可以完全并行操作延迟仅为一级比较器延迟。// 简化的比较交换单元行为描述 if (path_metric_A path_metric_B) begin output_upper path_metric_A; output_lower path_metric_B; end else begin output_upper path_metric_B; output_lower path_metric_A; endL输入排序器这是初步排序的主力。我们需要多个这样的排序器并行工作。例如对于M8我们需要8个L输入的排序器。选择哪种排序网络比特排序器当L是2的幂时非常规整但硬件复杂度为O(L log² L)在L较大时面积开销大。奇偶排序器在中等规模如L16, 32下通常比比特排序器使用更少的比较交换单元且结构也相对规整。 在本文的架构中考虑到需要多个排序器实例面积是首要考虑因素因此选择奇偶排序器作为L输入排序器的核心是更优的。其硬件消耗可以通过公式NCL [(log₂L)² - log₂L 4] * 2^(log₂L - 2) - 1估算。整个PS模块的CASU总数即为8 * NCL 2L。实现心得并行化与流水线8个L输入排序器是完全独立的可以并行执行这大大缩短了初步排序的绝对时间。但要注意当L较大时如32一个L输入排序器内部可能有多个级联的CASU阶段。为了达到高时钟频率需要在排序器内部插入流水线寄存器但这会增加额外的寄存器开销和延迟周期数需要根据目标频率和吞吐量进行权衡。路径度量表示为了节省比较器资源通常存储和比较的是路径度量的负值或相关似然比的绝对值。由于路径度量均为非正实数比较其绝对值等价于比较原始度量值但硬件上可以使用无符号数比较器有时能更节省资源。3.2 剪枝模块逻辑判断而非数据移动剪枝模块在硬件上不是一个主动进行数据排序或移动的单元而是一个基于地址和索引的逻辑控制单元。它的输入是OCPM中所有元素的存储地址和值输出是一个“有效位图”标记哪些位置的路径需要保留哪些可以被丢弃。硬件实现要点预计算与配置剪枝算法是确定性的。对于给定的L和M每一行需要保留的元素数量Ai是固定可计算的如A1L, A2L/2, A3 Σ L/2^(2λ) 等。这些值可以在设计时预计算好并存储在一个小的配置寄存器或查找表中。生成选择信号根据当前节点类型决定M和列表大小L剪枝模块读取预存的Ai值。对于第i行它生成一个选择信号控制后续的多路选择器只将该行前Ai个数据输出到下一级。零硬件操作关键在于被“剪枝”掉的数据并不需要被物理地删除或覆盖。它们只是被后续的合并排序网络“忽略”了。硬件上这通过控制合并排序网络的输入连接来实现——只有被标记为有效的路径才会被连接到排序网络的输入端口。这种设计使得剪枝模块本身的硬件开销极低几乎就是一些计数器和比较逻辑但它带来的收益减少后续排序网络规模却是巨大的。3.3 行间合并排序模块的灵活设计MSR模块是资源节省的关键。它由多级剪枝后合并网络组成。剪枝后合并网络这是一个定制化的合并单元。它接收两个有序序列长度分别为A和BA, B ≤ L并输出前k个最小的有序结果k通常等于A或AB中的较小者。它的设计基于标准的奇偶合并排序网络但进行了大刀阔斧的裁剪。移除“下半部分”输出相关的电路标准合并网络会输出全部AB个有序结果。但我们只关心前k个。因此所有仅用于生成第k1个及之后结果的CASU都可以安全移除。在电路图上这表现为网络下半部分的大量单元被“剪掉”。处理非2的幂的输入长度当A或B不是2的幂时为了构建规整的排序网络可能需要虚拟地补充一些最大值用硬件常数表示这些“虚拟最大值”会在排序中自然沉底不影响前k个有效结果的输出。如图5(b)(c)所示添加max-val输入可以简化网络结构而不会增加有效数据的比较次数。半清网络在最后一层当只剩下两个有序序列需要合并并选出最终的L个最优路径时使用HC网络。HC网络是比特排序器的一部分结构非常对称和规整。对于一个3L/2输入、输出L个最小值的HC网络它仅需要L/2个CASU和1个CASU阶段效率极高。资源估算整个MSR模块的CASU总数是各级PRN的CASU数之和再加上最后的L/2个CASU。其级数延迟为2log₂L 1。与一个完整的8L输入OES级数约0.5*(log₂(8L)1)*log₂(8L)相比在L32时级数减少了约25%而CASU数量的减少更为显著超过50%。3.4 整体数据通路与控制器设计整个排序架构需要一个状态机或控制器来协调工作流程节点类型识别根据解码树信息确定当前处理的节点是Rate-0, Rate-1, REP还是SPC从而设置M值。启动PS将M*L个候选路径度量值及其对应的路径信息如部分和送入PS模块。控制器需要管理这些数据的写入和PS模块的启动。配置PM根据M和L从查找表读出Ai值配置PM的有效位生成逻辑。调度MSR控制MSR中各级PRN的依次执行。由于数据依赖关系这通常是一个多周过程。可以考虑流水线化设计当前一级PRN在处理第n组数据时后一级PRN可以处理第n-1组数据的结果以提高吞吐量。输出管理将最终选出的L条最优路径的度量值和路径信息输出给解码器的路径管理单元用于更新路径历史和继续后续解码。面积-时序权衡追求高吞吐量可以在PS内部的每个排序器、MSR的每一级PRN之间都插入流水线寄存器。这样可以将关键路径缩短到一个CASU的延迟从而实现很高的时钟频率。代价是增加了大量的寄存器和总体解码延迟周期数。追求低延迟/小面积对于延迟敏感或面积受限的应用可以减少流水线级数甚至采用全组合逻辑。这样总延迟周期数少但时钟频率会受限于较长的组合路径。需要根据工艺库和时序报告仔细评估。4. 性能评估与对比分析为了量化所提架构的优势我们需要从三个维度进行评估纠错性能是否无损、硬件复杂度消耗多少资源、时序性能引入多少延迟。4.1 纠错性能确保“无损”任何硬件优化都不能以牺牲解码准确性为代价。我们通过仿真来验证这一点。仿真设置采用经典的(1024, 512)极化码在加性高斯白噪声信道下进行传输使用BPSK调制。对比三种解码器原始List-Fast-SSC解码器使用理想的全排序、SCL解码器、以及采用我们提出的简化排序架构的List-Fast-SSC解码器。结果分析如图7和图8所示此处为文字描述实际应有曲线图在相同的信噪比下采用我们排序架构的解码器其误比特率和误块率曲线与原始List-Fast-SSC解码器的曲线完全重合。这严格证明了我们的剪枝算法是“无损”的没有丢弃任何可能成为最终最优路径的候选者完全保持了算法的纠错性能。同时由于List-Fast-SSC算法本身对SPC节点长度做了限制如限长为4其性能相较于SCL算法在低信噪比段可能有轻微损失但这与排序架构无关是算法本身的取舍。4.2 硬件复杂度比较交换单元与级数的削减硬件复杂度主要体现在比较交换单元的数量和排序网络的级数上。CASU的数量直接对应着芯片上比较器和多路选择器的数量决定了面积大小。CASU的级数则影响着排序的延迟和最大时钟频率。我们与几种经典的排序网络进行对比通用比特排序器作为性能基准但未利用任何路径特性。通用奇偶排序器另一种通用方案通常比比特排序器更节省CASU。简化奇偶排序器利用了SCL解码中路径度量的部分有序特性是面向SCL的优化。剪枝比特排序器同样是面向SCL的优化。对比实验数据以M8为例列表大小L排序架构CASU数量CASU级数相对于OES的CASU节省8通用OES~X1~Y1基准8本文架构~X2~Y2约 40%32通用OES~X3~Y3基准32本文架构~X4~Y4约 52.3%注X1~X4, Y1~Y4为具体数值此处用符号表示趋势。核心结论当L32 M8时我们的架构相比通用奇偶排序器减少了52.3%的CASU和25%的CASU级数。这是一个非常可观的硬件节省。节省主要来源于两个方面一是PM模块提前剔除了大量最高66.7%无需参与最终排序的路径二是MSR模块中使用的PRN和HC网络都是为特定数据量定制的精简结构避免了通用排序器中的大量冗余操作。即使与面向SCL优化的SOES和PBS相比由于我们的架构是针对List-Fast-SSC节点特性如Rate-1节点的强有序性进行深度定制因此仍然能取得明显的优势。4.3 时序与吞吐量分析关键路径延迟在大型排序网络中关键路径通常由多级CASU串联构成。我们的架构通过减少CASU级数直接缩短了关键路径。例如从OES的0.5*(log₂(8L)1)*log₂(8L)级减少到本文架构的(0.5*log₂L*(log₂L1) 1) (2log₂L 1)级。在L32时级数减少意味着组合逻辑深度变浅有利于提高电路的最高工作频率。吞吐量考虑排序网络通常是解码器流水线中的一个阶段。其吞吐量由时钟频率和该阶段所占的周期数决定。非流水线模式整个排序操作在一个大的组合逻辑块中完成吞吐量为每N个周期完成一个节点的排序N为解码一个码字所需的节点数。延迟大频率低。全流水线模式在PS内部、PS与PM之间、MSR各级之间都插入流水线寄存器。这样排序模块可以每个时钟周期都接收一组新的M*L数据并在固定的流水线延迟后输出结果。吞吐量可以达到每个周期处理一个节点极大提升整体解码速度但代价是面积寄存器和初始延迟的增加。设计建议对于高吞吐量应用如基站应采用深度流水线设计。对于低功耗、低成本应用如物联网终端可采用较浅的流水线甚至非流水线设计以优化面积。4.4 综合评估与适用场景综合来看本文提出的排序架构在保持纠错性能不变的前提下实现了硬件复杂度和延迟的双重优化。它特别适用于以下场景中到大列表大小的List-Fast-SSC解码器当L 8时优化效果开始显著。L越大节省的资源比例越可观。对面积和功耗敏感的终端设备CASU数量的直接减少意味着更小的芯片面积和更低的动态功耗。高吞吐量通信系统减少的CASU级数有助于提高时钟频率结合流水线设计可以满足高速数据解码的需求。局限性该架构的优化效果高度依赖于List-Fast-SSC算法生成的候选路径的有序性。如果应用于其他生成路径特性不同的列表解码算法如传统的SCL其剪枝效率可能会降低需要重新评估。此外当列表大小L非常小如2或4时通用排序器本身开销不大本架构的收益相对有限但通过兼容性设计它依然可以正确工作。5. 总结与工程实践思考回顾整个设计其精髓在于“因势利导”和“分而治之”。我们没有与庞大的无序数据正面硬撼而是先深入分析了List-Fast-SSC解码过程中数据产生的内在规律有序性并利用这一规律将数据预先组织成有序矩阵。这一步将全局排序问题降维成了多个并行的、更小的排序问题。随后无损剪枝算法是整个设计的点睛之笔。它像一个聪明的“预审官”在数据进入昂贵的合并排序大厅之前就根据明确的规则OCPM中行列有序的特性淘汰掉一大批显然不够格的候选者。这一步以极小的逻辑判断开销换取了后续排序网络规模的大幅缩减是性价比最高的优化。最后定制化的合并网络PRN和HC则是对剩余数据的“精加工”。它们不再是通用的、笨重的排序器而是为处理“两个有序序列合并并取前k项”这一特定任务而量身定做的精密工具去除了所有不必要的比较操作。在实际的硬件实现中有几点经验值得分享精度与量化路径度量通常用有限位宽的定点数表示。需要仔细确定位宽在保证纠错性能不下降的前提下尽可能减少位宽以节省比较器和存储器的资源。路径信息存储排序过程中不仅需要比较路径度量值还需要在交换度量值时同步交换对应的路径信息如部分和向量。这需要设计高效的数据交换网络其复杂度可能与比较网络本身相当。可配置性为了适配不同的码长、列表大小L硬件架构最好设计成可配置的。例如通过参数化生成L为不同值时的排序网络或者使PM模块的Ai值可通过寄存器配置以增加设计的灵活性。验证挑战确保剪枝算法的“无损”性是验证的关键。需要构建大量的随机测试向量覆盖各种信道条件和节点类型将优化后架构的输出与一个软件实现的、使用全排序的黄金模型进行比对确保功能完全一致。这项工作的价值在于它打通了从高效解码算法到高效硬件实现的关键一环。随着对极化码解码性能要求的不断提高列表大小L可能会进一步增大高效的排序架构将变得愈发重要。本文提出的思路——利用算法特征进行前置数据整理和剪枝再结合定制化合并——为未来更复杂解码器的硬件优化提供了一个清晰且有效的设计范式。