专利摘要

本发明公开了一种适用于极化码串行抵消列表译码算法的硬件排序器，包括输入模块、桶排序模块、半清洁器模块和输出模块；输入模块，用于输入待排序的2L条译码路径；译码路径包括L条原始译码路径和L条分裂译码路径；其中，L取值为2n，n≧1且n为整数，分裂前的L条原始译码路径已经排好序；桶排序模块，用于对L‑1条分裂译码路径进行优劣排序；半清洁器模块，根据选择策略，在原始路径与桶排序模块输出的译码路径集合中，选择最优的L条路径；输出模块，用于输出经半清洁器模块选择后的最优的L条路径。本发明中输入路径L的数量对排序器的延迟时间影响很小，当路径L较大时排序器具有较低的译码延迟。

权利要求

1.一种适用于极化码串行抵消列表译码算法的硬件排序器，其特征在于：包括输入模块、桶排序模块、半清洁器模块和输出模块；

所述输入模块，用于输入待排序的2L条译码路径；所述译码路径包括L条原始译码路径和L条分裂译码路径；其中，L取值为2n，n≧1且n为整数，分裂前的L条原始译码路径已经排好序；

所述输入模块还包括一译码模块，所述译码模块利用SCL算法对信息比特进行译码，每译码到一个信息比特，信息比特的初始译码路径分裂为与初始译码路径相同的原始译码路径和与初始译码路径不同的分裂译码路径，所述译码模块对信息比特进行译码而生成输入到所述输入模块的2L条译码路径；

每条译码路径均包括一个用于评价路径优劣特性的度量值，所述度量值越小则表示所述译码路径越优，分裂前的初始译码路径的度量值集合被定义为：

m'＝[m1,m3,...,m2L-1]；

且对集合m'有m2i-1≤m2i+1,1≤i≤L-1，即L条原始译码路径已经按从小到大的排好顺序；

分裂后的原始译码路径和分裂译码路径的度量值集合被定义为

m＝[m1,m3,...,m2L-1,m2,m4...,m2L]；

其中，任一初始译码路径i的度量值为m'2i-1，分裂后的原始译码路径度量值为m2i-1，分裂后的分裂译码路径度量值为m2i，其中i∈L，且m2i-1＝m'2i-1，m2i＝m'2i-1+|αk|，|αk|为是第k个信息比特的对数似然比的绝对值；其中k为整数，且0<k<N，N为包含所述L个信息比特的当前发送数据的位数，k为当前发送数据中的信息比特的位数；

所述桶排序模块，用于对L-1条分裂译码路径进行优劣排序；

所述桶排序器模块对输入的L-1条分裂译码路径进行优劣排序，具体实现包括以下步骤：

步骤1：比较；

以译码路径度量值为基准，使用比较器对输入的L-1条分裂译码路径进行两两比较，并将比较结果储存在寄存器R中；比较结果中，由“1”表示当前译码路径的度量值大于对应比较的译码路径度量值，“0”表示当前译码路径的度量值小于等于对应比较的译码路径度量值；

步骤2：计算；

基于步骤1，将寄存器R中的比较结果进行累加计算，得到译码路径i在L-1条分裂译码路径中的秩序Sum值；

步骤3：排序；

使用选择器，根据输入的L-1条路径和L-1个秩序Sum值，以秩序Sum值为基准，对输入的译码路径由优到劣进行排序；

所述半清洁器模块，根据选择策略，在原始路径与桶排序模块输出的译码路径集合中，选择最优的L条路径；

所述半清洁器，通过使用比较器比较原始译码路径L-i+1与分裂译码路径L+i，若原始译码路径L-i+1的路径度量值大于分裂译码路径L+i的路径度量值，则交换两条译码路径在集合中的位置，经过L/2次比较之后，选择集合中前L条译码路径作为最优译码路径输出；其中i＝1,2,....,L/2；

所述输出模块，用于输出经半清洁器模块选择后的最优的L条路径。

说明书

技术领域

本发明属于通信技术领域，涉及系统中的信道译码技术，更为具体的来说，是涉及基于串行抵消列表的极化码译码中一种低时延高效率的排序器的设计。

背景技术

2008年在国际信息论ISIT会议上，Arikan首次提出了信道极化的概念，基于该理论，他给出了人类已知的第一种能够被严格证明达到信道容量的信道编码方法，并命名为极化码。极化码具有明确而简单的编码及译码算法。串行抵消(SC，SuccessiveCancellation)译码算法是一种低复杂度，译码结构简单的译码算法。串行抵消列表(SCL，Successive Cancellation List)译码算法是SC译码算法的优化算法，以复杂度为代价，提升译码性能。SCL译码算法在信息比特对译码路径进行分裂，当分裂路径总数达到2L时，通过排序器对每条路径的度量值(PM，Path Metric)进行排序，筛选出2L条路径中L条PM值最小的路径，保证计算的过程中路径总数不超过L条。SCL译码算法中，每一个信息比特都需要进行一次排序，因此增加了算法复杂度和译码的总时延，因此低时延、低复杂度的排序方法是降低极化码译码时延和复杂度的关键。

SCL译码算法中，当分裂路径总数达到2L时，需要通过排序器对2L条路径进行排序，双调排序器(bitonic sorter)和奇偶排序器(odd–even sorter)用于输出2L个有序路径。同时基于双调排序器和奇偶排序器提出了简化的双调排序器(simplified bitonicsorter)和简化的奇偶排序器(simplified odd-even sorter)来对2L条路径进行排序，减少了排序器的比较单元和排序器阶数。

为了进一步降低排序器的译码延迟，提升SCL译码算法的数据传输效率，V.Bioglio等人提出排序器可以只筛选出L条PM值最小的路径，其顺序可以在译码的其他过程中并行排好序。基于这种排序思想提出了最优双调排序器(optimized bitonic sorter)和混合排序器(hybrid sorter)，以及优化的两两排序器(half-sorted pairwise metricsorter)，筛选出L条未排序的PM值，将排序过程放入译码的其他步骤中提升SCL译码算法的数据吞吐量。但是当需要排序的路径L变大时，排序器所消耗的逻辑资源会显著提升，并且排序器的延迟会增大。

发明内容

针对现有排序器有较高延迟，同时由于输入路径增大时其排序器时钟频率显著降低，且逻辑资源大幅提升的情况，本发明提出了一种基于桶排序器的混合排序器，利用桶排序器的时间复杂度对输入数据规模基本无关的特性，设计一种低时延，低复杂度的排序器，进一步降低由排序器所引起的译码延迟。

本发明所采用的技术方案是：一种适用于极化码串行抵消列表译码算法的硬件排序器，其特征在于：包括输入模块、桶排序模块、半清洁器模块和输出模块；

所述输入模块，用于输入待排序的2L条译码路径；所述译码路径包括L条原始译码路径和L条分裂译码路径；其中，L取值为2ⁿ，n≧1且n为整数，分裂前的L条原始译码路径已经排好序；

所述桶排序模块，根据每条路径的度量值(即SCL译码中的PM值，PM初始值为0，PM值由极化码的信息比特和固定比特组成的集合及相应译码位置的对数似然比计算得出)，对L条分裂译码路径进行优劣排序，因为第L条分裂路径由第L条原始路径分裂得出，且所有原始路径已排好顺序，同时分裂路径的度量值大于等于原始路径的度量值，所以第L条分裂路径不属于最优的L条路径中，故不需送入桶排序器；

所述半清洁器模块，根据选择策略，在原始路径与桶排序模块输出的译码路径集合中，选择最优的L条路径；

所述输出模块，用于输出经半清洁器模块选择后的最优的L条路径。

作为优选，所述输入模块还包括一译码模块，所述译码模块利用SCL算法对信息比特进行译码，每译码到一个信息比特，信息比特的初始译码路径分裂为与初始译码路径相同的原始译码路径和与初始译码路径不同的分裂译码路径，所述译码器对信息比特进行译码而生成输入到所述输入模块的2L条译码路径。

作为优选，每条译码路径均包括一个用于评价路径优劣特性的度量值，所述度量值越小则表示所述译码路径越优，分裂前的初始译码路径的度量值集合被定义为：

m’＝[m₁,m₃,...,m_2L-1]；

且对集合m'有m_2i-1≤m_2i+1,1≤i≤L-1，即L条原始译码路径已经按从小到大的排好顺序；

分裂后的原始译码路径和分裂译码路径的度量值集合被定义为m＝[m₁,m₃,...,m_2L-1,m₂,m₄...,m_2L]；

其中，任一初始译码路径i的度量值为m'_2i-1，分裂后的原始译码路径度量值为m_2i-1，分裂后的分裂译码路径度量值为m_2i，其中i∈L，且m_2i-1＝m'_2i-1，m_2i＝m'_2i-1+|α_k|，|α_k|为是第k个信息比特的对数似然比(LLR，log-likelihood ratio)的绝对值；其中k为整数，且0＜k＜N，N为包含所述L个信息比特的当前发送数据的位数，k为当前发送数据中的信息比特的位数。

SCL译码中的度量值即PM值，PM值初始为0，PM值的计算由极化码中的固定比特集和对应译码位置的对数似然比决定分为三种情况：

1.译码位置为固定位：

2.译码位置为信息位，且译码值译为0：

3.译码位置为信息位，且译码值译为1：

根据相应PM值更新策略，完成一次SCL译码后，选择出PM值最大的一组，作为最后计算的结果。

作为优选，所述桶排序器模块对L-1条译码路径进行优劣排序，具体实现包括以下步骤：

步骤1：比较；

以译码路径度量值为基准，使用比较器对输入的L-1条译码路径进行两两比较，并将比较结果储存在寄存器R中；一共需要(L-1)*(L-2)/2个比较器和(L-1)*(L-2)/2个结果存储器R，其时延为Tcom。

比较结果中，由“1”表示当前译码路径的度量值大于对应比较的译码路径度量值，“0”表示当前译码路径的度量值小于等于对应比较的译码路径度量值；

步骤2：计算；

基于步骤1，将寄存器R中的比较结果进行累加计算，得到译码路径i在L-1条译码路径中的秩序Sum值；

步骤3：排序；

使用选择器，根据输入的L-1条路径和L-1个秩序Sum值，以秩序Sum值为基准，对输入的译码路径由优到劣进行排序。

作为优选，所述半清洁器，使用比较器比较原始译码路径L-i+1与分裂译码路径L+i，若原始译码路径L-i+1的路径度量值大于分裂译码路径L+i的路径度量值，则交换两条译码路径在集合中的位置，经过L/2次比较之后，选择集合中前L条译码路径作为最优译码路径输出；其中i＝1,2,....,L/2。

L-1条分裂路径的PM值经过桶排序器排序之后，可以得到桶排序器输出的L/2条路径的PM值，因排序后分裂路径的后L/2条路径不是最优的L条路径中的PM值，故桶排序器只需输出排序后分裂路径的前L/2条PM值，同时因为L条原始路径已经排好顺序，所以原始路径的前L/2条路径的PM值一定是最优的L条路径中的值。因此只需将原始路径的后L/2条路径和桶排序器输出的L/2条路径输入到半清洁器中，选择剩余的L/2条路径，需要L/2个比较器，其时延为Tnetwork。

通过半清洁器输出的L/2个路径，和原始路径的前L/2条路径即为需要从2L条路径中选择的L条最优的路径。

排序器的时延为T＝Tcom+Tsum+Tsel+Tnetwork。

排序器的需要的比较器个数为CMP＝(L-1)*(L-2)/2+L/2。

与现有技术相比，本发明具有如下优点和有益效果：

(1)本发明相对于之前的硬件排序器，排序器算法设计由将2L条路径排序后选择出L条PM值最小的路径优化为只需筛选出2L条路径中L条PM值最小的路径。在极化码译码过程中，将对固定比特位的L条路径排序与F、G运算并行执行，节省在信息比特的排序逻辑资源，同时不会明显增大F、G运算的延迟。

(2)本发明设计的排序器在极化码译码过程中，输入的路径L数量对排序器的延迟时间影响很小，当路径L较大时仍具有较低的译码延迟。同时当路径L相同时，相比其他同功能排序器，本发明设计的排序器所消耗的逻辑资源较少。

附图说明

图1是本发明实施例输入的2L个路径时的排序器设计方案整体架构示意图；

图2是本发明实施例同排序器第i个输出数据的选择器示意图；

图3是本发明实施例半清洁器示意图。

具体实施方式

为了便于本领域普通技术人员理解和实施本发明，下面结合附图及实施例对本发明作进一步的详细描述，应当理解，此处所描述的实施示例仅用于说明和解释本发明，并不用于限定本发明。

请见图1，本发明提供的一种适用于极化码串行抵消列表译码算法的硬件排序器，包括输入模块、桶排序模块、半清洁器模块和输出模块；

输入模块，用于输入待排序的2L条译码路径；译码路径包括L条原始译码路径和L条分裂译码路径；其中，L取值为2ⁿ，n≧1且n为整数，分裂前的L条原始译码路径已经排好序；

桶排序模块，根据每条路径的度量值(即SCL译码中的PM值，PM初始值为0，PM值由极化码的信息比特和固定比特组成的集合及相应译码位置的对数似然比计算得出)，对L条分裂译码路径进行优劣排序，因为第L条分裂路径由第L条原始路径分裂得出，且所有原始路径已排好顺序，同时分裂路径的度量值大于等于原始路径的度量值，所以第L条分裂路径不属于最优的L条路径中，故不需送入桶排序器；

半清洁器模块，根据选择策略，在原始路径与桶排序模块输出的译码路径集合中，选择最优的L条路径；输出模块，用于输出经半清洁器模块选择后的最优的L条路径。

本实施例的输入模块还包括一译码模块，译码模块利用SCL算法对信息比特进行译码，每译码到一个信息比特，信息比特的初始译码路径分裂为与初始译码路径相同的原始译码路径和与初始译码路径不同的分裂译码路径，译码器对信息比特进行译码而生成输入到输入模块的2L条译码路径。

本实施例以L＝8为例，L条原始译码路径PM值为m₁'＝[2,5,7,12,13,15,18,21]，经过路径分裂，得到L条分裂译码路径m₂＝[3,18,8,14,20,15,28,21]，所以输入排序器的2L条路径的PM值数据为m＝[2,5,7,12,13,15,18,21,3,18,8,14,20,15,28,21]，一共16个数说明排序器的具体实施过程。

对于原始译码路径，输入的数据为已排好序的8个PM值为[m₁，m₃，m₅，m₇，m₉，m₁₁，m₁₃，m₁₅]＝[2，5，7，12，13，15，18，21]，对于分裂译码路径，输入排序器的为未排好顺序的8个PM值，[m₂，m₄，m₆，m₈，m₁₀，m₁₂，m₁₄，m₁₆]＝[3，18，8，14，20，15，28，21]，对于16个PM值满足以下条件：

m_2i-1≤m_2i,1≤i≤L；

m_2i-1≤m_2i+1,1≤i≤L-1；

由以上条件可知，由m₁₅分裂得出的m₁₆一定不属于最优的L条路径，因此无需送入桶排序器中。所以对于分裂译码路径，送入桶排序器中的为分裂路径中前L-1条路径对应的7个PM值[m₂，m₄，m₆，m₈，m₁₀，m₁₂，m₁₄]＝[3，18，8，14，20，15，28]。

对于桶排序器，其比较阶段与计算阶段如表1所示。经过比较阶段可得[Sum₁，Sum₂，Sum₃，Sum₄，Sum₅，Sum₆，Sum₇]＝[0，4，1，2，5，3，6]。在比较过程中，设两个输入参与比较的数据为m_i与m_j(i≠j)，当比较出m_i是否大于等于m_j之后，m_j与m_i之间的关系可以通过取非操作得到，如表1中的斜体部分所示。

表1

对于桶排序器，其选择阶段如图2所示。通过L/2个如图2所示的选择器，可以输出L/2个数据的顺序。设其输出为s_i，那么经过L/2个选择器，则有[s₉，s₁₀，s₁₁，s₁₂]＝[3，8，14，15]。

即经过桶排序之后，其输出序列S为[s₁，s₂，s₃，s₄，s₅，s₆，s₇，s₈，s₉，s₁₀，s₁₁，s₁₂]＝[2，5，7，12，13，15，18，21，3，8，14，15]。将序列s输入到半清洁器中。

在半清洁器中其选择过程如图3所示，只比较L/2个数据，即s₅与s₁₂，s₆与s₁₁，s₇与s₁₀，s₈与s₉之间的大小关系，选择最优的路径输出。s₅与s₁₂的比较结果输出为h₅(13)，s₆与s₁₁的比较结果输出为h₁₁(14)，s₇与s₁₀的比较结果输出为h₁₀(8)，s₈与s₉的比较结果输出为h₉(3)。

通过本发明设计的排序器之后，将输入的16个数据[m₁，m₃，m₅，m₇，m₉，m₁₁，m₁₃，m₁₅，m₂，m₄，m₆，m₈，m₁₀，m₁₂，m₁₄，m₁₆]＝[2，5，7，12，13，15，18，21，3，18，8，14，20，15，28，21]输出为[h₁，h₂，h₃，h₄，h₅，h₆，h₇，h₈]＝[2，5，7，12，13，14，8，3]，即从输入的2L个m序列中找到了L个最小的h序列。

应当理解的是，本说明书未详细阐述的部分均属于现有技术，本文独创技术均已介绍完毕。上述针对较佳实施例的描述较为详细，并不能因此而认为是对本发明专利保护范围的限制，本领域的普通技术人员在本发明的启示下，在不脱离本发明权利要求所保护的范围情况下，还可以做出替换或变形，均落入本发明的保护范围之内，本发明的请求保护范围应以所附权利要求为准。

一种适用于极化码串行抵消列表译码算法的硬件排序器专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。