极化码的SC译码使用对数似然比（logarithm likelihood ratio，LLR）进行译码运算．对于长度N=2 ⁿ ( n∈N^*)的极化码，设u=( u ₁， u ₂，⋯， u_N )为发送信号．SC译码算法先使用接收到的信号序列的对数似然比y ^N₁计算u ₁对应的估计值û1，随后利用( y^N₁ ，û1 )估计û2，再用( y^N₁ ，û21 )估计û3，以此类推并最终得到估计的发送信号û=(û1，û2，⋯，ûN )．其中，ûi1为信道序号1到i的译码结果．信道序号值为i的节点的估计值为

其中， )为节点i的对数似然比，定义为

这里， W ( )iN ( y ^N₁， ûi-11 |0 )和W ( )iN ( y ^N₁， ûi-11 |1)分别是已知y ^N ₁和ûi-11 时ûi为0和1的条件概率．A和A ^c为信息信道编号集合和冻结信道编号集合，由收发端事先约定．当i∈A^c时，译为双方约定的比特值，一般为0；当i∈A时，则通过判决函数

得到节点i的译码结果ûi．

SC译码算法结构如图1．其中，信道i接收到的信号r_i转换为LLR值的转换公式为

这里，σ为噪声方差．图1中虚线和实现箭头分别为式（5）和式（6）的f操作和g操作；每个节点代表1个LLR值，最右侧节点的LLR值与接收端信道的LLR值相等，既L ^{( i )}1 =y _i，其余节点的LLR值可通过递归公式计算得到，再使用式（1）估计对应节点的值，则最左侧节点组成的序列即译码结果．

图1 SC译码算法结构Fig. 1 Structure of SC decoding algorithm.

每个计算基本单元如图2所示．基本单元运算可分为两部分：

图2 SC译码基本单元Fig. 2 Basic unit of SC decoding.

1） f操作．从右往左计算左上节点的LLR值，并使用式（1）估计该节点的比特值为u₁.

其中，L₁和L₂为图2中右边2个节点的LLR值．

2） g操作．采用式（6）计算左下节点的LLR值，再使用式（1）估计该节点的比特值．

g ( L ( 1 )1 ，L ( 1 )2 ，u ₁ )=( 1-2 u ₁ ) _L ( )11 +L ( )21（6）

为减少仿真计算的复杂度，将式（2）简化^[14]为

SC译码算法迭代过程的伪代码见图3．其中， uⁱ_1，e和uⁱ_1，o分别为uⁱ₁中的偶数位和奇数位；符号⊕表示模2加法；冻结比特约定译码为0．

图3 SC译码算法的伪代码Fig. 3 Pseudocode of SC decoding algorithm.

SCL译码在SC译码的基础上保留了L条具有最小路径度量（path metric，PM）值的路径，增加了译码的可靠性．对于长度为N=2ⁿ(n∈N^*)的极化码， SCL译码中第l条(l=1， 2，⋯，L )路径上的第i位(i=1， 2，⋯， N )的路径度量为

其中，ûj[l]为第l个分支中第j个节点的译码比特值．由式（1）可得路径l的LLR为

PM值越小，路径越可靠．每个节点译码最多保留L条路径，拓展路径条数超过L后将保留L条具有最小PM值的路径，其余路径将被剪枝删除．因此，迭代完成后会得到L条分支，再按照PM值从小到大排序，取第1条分支作为结果并输出．

CA-SCL是信道传输中差错检验的常见技术，通过加入冗余校验位，可更充分利用SCL的译码路径．CA-SCL译码算法将译码路径按PM值从小到大排序，再依次进行校验，并取第1个通过路径作为译码结果输出，若都不通过则译码失败．CA-SCL算法的准确性比SCL算法有明显提高^[7]．

Fast-SC算法将译码树分成若干种特殊节点，然后根据节点的长度，迭代计算出相应层数的对数似然比值．图4展示了4种特殊节点的结构，使用该结构时其准确性与SC译码算法基本相同^[15]．特殊节点包含但不限于以下4种结构：

图4 SC快速译码特殊节点Fig. 4 Special nodes of Fast-SC decoding.

1）码率0（rate 0，R0），所有信源比特全是冻结比特，所有比特译码为0，即β=（0，0，⋯，0）．

2）重复（repetition，Rep）码，除最后一位外其他位全为冻结位．记 若S≥0，则β=(0，0，⋯，0)_；否则，β=(1，1，⋯，1)_．

3）单偶校验（single parity check，SPC）码，除了u₁是冻结比特，其余都是信息比特．硬判决为为1 ，即⊕^N_i=1 β _i=1时，使用比特翻转思想^{[1 6]}，取p=arg ( min1≤i≤N ||y_i )，进行β_p=β_p⊕1操作，得到的β为译码结果．

当SPC译码结果β=( β ₁，β _2，⋯，β _N )的异或和

4）码率1（rate 1，R1），所有的信源比特都为信息比特，直接使用式（8）进行硬判决．

这4种节点都可由L L R序列( y ₁， y ₂，⋯， y_N )直接估计极化码码字序列β=( β ₁，β _2，⋯，β_N )，无需使用SC译码迭代至叶节点．但是，R0节点的译码没有使用接收序列，在优化后的Fast-SC译码算法中，需先辨认特殊节点是否为R0节点，若是，则返回全0比特；否则，计算下一层LLR时再使用对应的译码规则．

表2对比了当N=1 024时，SC、Fast-SC和优化Fast-SC译码算法中f函数执行次数和对应的误帧率（frame error rate，FER）．由表1可见，优化Fast-SC译码比Fast-SC算法在效率上约有7%的提升．

表2 不同译码算法f函数执行效率和误帧率（N=1 024） Table 2 Comparison of f function execution efficiency of different algorithms (N=1 024)

若CA-SCL算法保留的路径数L太大，会产生很大时延，但若L太小，则可选择的译码器很少，且算法误帧率高、可靠性低．图5给出了CA-SCL算法中保留路径数对误帧率的影响．其中，图注中括号内数值分别为码长和信息值；信噪比（signal to noise ratio，SNR）分别为1. 5、2. 0、2. 5 dB. 由图5可见，随着L的增大，算法译码的准确性上升，特别是在L=[2，16]时， FER下降最快．当L≥8时，FER的变化趋于平缓．因此，本研究取L=8作为保留路径数．

图5 CA-SCL译码算法保留路径数与误帧率的关系Fig. 5 The relationship between reservation path and frame error rate of CA-SCL decoding algorithm.

自适应信道的preFast-SCL译码算法流程和主要模块如图6．

图6 preFast-SCL译码流程图Fig. 6 Flow chart of preFast-SCL.

得到对数似然比序列后，配合信息位集合A和使用的特殊节点类型node_type进行Fast-SC译码中，得到译码序列ûN1，并对该结果进行CRC校验．若通过校验，则作为最终结果输出；否则，使用CA-SCL译码器进行译码，提高译码结果可靠性．当信道条件较好时候，Fast-SC有较高通过率，可大幅提升译码效率．当Fast-SC译码结果出现差错，校验不通过时，仍有CA-SCL译码器兜底，有效提升了译码结果的可靠性．preFast-SCL译码算法的伪代码见图7．其中，CRC(ûN1 )为ûN1进行CRC校验， ûN1，L存储了所有L条路径的译码结果； ûN1，L [l]为第l条路径的译码结果．

下面将讨论的最大和平均时间复杂度，以及空间复杂度的推导．

1） preFast-SCL最大复杂度是O ( LN lb N )

Fast-SC算法的时间复杂度为O ( N lb N )_；CA-SCL译码时间复杂度为O ( N lb N )_；CRC校验时间复杂度O (m)_．其中，L为CA-SCL算法的保留路径数；m为CRC校验位长度．最差的情况是执行快速译码后，检验失败，而在执行CA-SCL译码算法时候，检测到最后一条路径才结束进行输出，此时有最大时间复杂度为

2）平均时间复杂度是O(1+P_e (γ)L)N lb N

P_e (γ)是SC算法在信噪比E_b/N₀=γ时的误帧率．其中，E_b为平均比特符号能量；N₀为噪声功率频谱．算法总会执行1次Fast-SC译码算法，但仅在不通过CRC校验情况下才执行CA-SCL算法，因此，平均时间复杂度为

图7 preFast-SCL译码算法伪代码Fig. 7 PreFast-SCL decoding algorithm pseudo code.

其中， P _e ( γ )为极化码误帧率满足P _e≤O ( 2^-Nβ )， β为极化率^[17]，即码长越长，preFast-SCL的译码时间复杂度比起SCL算法，下降得明显．

3） preFast-SCL算法的空间复杂度为O ( LN )

Fast-SC译码算法与SC算法的空间复杂度相同，只需O( N )空间，而CA-SCL算法使用懒复制（lazy copy）策略^[6]，只需O ( LN )空间．preFast-SCL空间复杂度为

为探究preFast-SCL算法译码性能，本研究在加性高斯噪声信道下进行仿真，仿真参数设置如下：CA-SCL、adaptive-SCL^[13]和preFast-SCL算法使用的CRC生成多项式均为g ( x)=x¹⁶+x¹⁵+x²+1，采用二进制相移键控（binary phase shift keying， BPSK）调制方式，极化码构造采用改进高斯估计法^[18]，码率为0. 5，BP译码最大迭代数为50次．

图8对比了preFast-SCL、adaptive-SCL^[13]和CA-SCL译码算法在N分别为512和1 024，信息位分别为256和512时的性能．其中，图注中括号内容表示信息比特序列长度和码长，如(512，1 024)表示信息比特序列长度为512，码长为1 024．

图8 信道适应译码算法与CA-SCL性能对比（a）可靠性；（b）耗时Fig. 8 Performance comparison between channel adaptive decoding algorithm and CA-SCL for (a) reliability and (b) time consuming.

由图8（a）可见，信道适应算法preFast-SCL和adaptive-SCL都不会造成FER性能损失，可靠性与CA-SCL算法基本相等．由图8（b）可得，在E_b/N₀=0～1. 5 dB时，preFast-SCL和adative-SCL算法的复杂度比CA-SCL算法更高，但在E_b/N₀>1. 5 dB时， preFast-SCL和adative-SCL算法的时间复杂度比CA-SCL算法都有大幅降．其中，preFast-SCL算法的时间性能优于adaptive-SCL算法．

图9对比了preFast-SCL译码算法在不同码长和信噪比条件下的FER和时间效率性能．由图9可见，在低信噪比条件下，preFast-SCL译码算法的长码译码速率低于短码译码速率．码长为N的码字，单位比特译码时间的复杂度为O(lb N )，即码字越长，译码速率越低．但另一方面，当相同信噪比时，码长增长，则码长较长的极化码的P_e (γ)值会降低．由式（12）可得，preFast-SCL译码算法的平均复杂度会下降，随着信噪比提升，长码译码的复杂度会有很大改善．

图9 信噪比与码长对preFast-SCL性能影响（a）可靠性；（b）译码耗时Fig. 9 Influence of SNR and code length on the performance of preFast-SCL for (a) reliability and (b) time consuming.

图 10为preFast-SCL算法、BP算法和SC算法的在码长N分别为256、512和1 024时的可靠性仿真对比．由图 10可见，preFast-SCL算法比传统的SC和BP算法，可靠性能上有较大提升．

图 11给出了在码长N分别为512和1 024时， preFast-SCL、SC、CA-SCL和Fast-SC算法的复杂度比较．N=512，E_b/N₀=2. 0 dB时，preFast-SCL算法需执行的操作数约为CA-SCL算法的45%，而在N=1 024，E_b/N₀=2. 0 dB时， preFast-SCL算法需执行的操作数仅是CA-SCL算法的30%，且该值随着信噪比和码长的增加仍会继续降低．

图 10 PreFast-SC与传统算法可靠性对比Fig. 10 Reliability comparison between preFast SC and traditional algorithms.

图 11 PreFast-SCL与传统算法时间性能对比（a）N=512；（b）N=1 024 Fig. 11 Time performance comparison between preFast-SCL and traditional algorithms for (a) N=512 and (b) N=1 024.