崔建明，王慶祥，張小軍，李恒忠

（山東科技大學，山東 青島 266590）

0 引 言

極化碼是一種可以嚴格證明達到香農極限[1]的編碼方案，是5G 信道編碼技術之一。文獻[1]提出串行抵消（Successive Cancellation，SC）譯碼算法，但是SC 譯碼器在有限碼長下，其譯碼算法糾錯性能不理想。為獲得更好的譯碼效果，極化碼串行抵消列表（Successive Cancellation List，SCL）譯碼器[2]，始終保持L條最佳候選路徑，可實現接近最大似然（ML）譯碼的性能，但其列表較大，計算復雜度較高。CRC 輔助SCL（CRC-Aided SCL，CA-SCL）譯碼算法[3]通過在信息比特序列后添加CRC 檢驗，篩選出最優(yōu)的候選路徑，以此提高譯碼性能。在此基礎上，又提出一種分段CRC 輔助SCL 譯碼方案[4]，該方案可顯著降低譯碼復雜度。類似地，CRC 糾錯輔助連續(xù)抵消列表（CRC-EC-SCL）譯碼的基本譯碼方案[5]也從另一角度提高譯碼性能。與CRC-polar codes類似的還有Hash-polar codes[6]，其檢驗位可以分散在信息位里，性能優(yōu)于奇偶檢驗極化碼。

在SC 譯碼過程中，信道噪聲或由于先前錯誤比特引起的錯誤傳播是產生錯誤比特的原因，通過對引起錯誤傳播的第一個錯誤比特翻轉，可獲得較好的性能增益。根據譯碼樹結構，總結出極化碼三種相應的節(jié)點類型[7]，提供節(jié)點合并，以減少譯碼器延遲?；诜D譯碼的思想，一種翻轉譯碼算法[8]被提出，通過對數似然比（Log Likelihood Ratio，LLR）的絕對值大小來確定閾值，作為翻轉譯碼的依據。由于信道中可能存在多比特錯誤，在翻轉1 比特錯誤碼字的基礎上，提出一種改進的翻轉多比特的SC 譯碼器[9]，以此提高譯碼性能。為進一步降低譯碼復雜度，分段SC 比特翻轉譯碼算法[10]被提出。為在翻轉過程中更高效地確定關鍵集合，文獻[11]中闡述了用樹結構確定關鍵集合的方法?；谠摌嬙礻P鍵集合的方法，同樣將比特翻轉用到SCL 譯碼算法中，進而提出一種改進關鍵集合的方法[12]，并根據該構造方法，提出了串行抵消列表比特翻轉（Successive Cancellation List Bit-Flip，SCLF）譯碼算法。

為降低SCLF 譯碼算法的譯碼延遲，基于提出的改進的關鍵集合[12]，本文提出一種分段CRC 輔助串行抵消列表比特翻轉極化碼譯碼（Low-Complexity Segmented CRC-Aided SCL Bit-Flip Decoding of Polar Codes，SCASCLF）算法。根據信息位置序列，該譯碼算法將譯碼過程分為前后兩段，在譯碼失敗情況下嘗試比特翻轉譯碼，并根據每段中的位置信息，采用SCLF 確定關鍵集的方法確定每段中的關鍵集合，在每段譯碼過程中，利用CRC 校驗對譯碼結果進行判斷，每段只保留一條正確的路徑。另外，本文還提出了多比特翻轉錯誤碼字的方法，可使譯碼結果更準確。本文采用多比特翻轉譯碼與分段CRC 輔助SCL 比特翻轉譯碼相結合，大大降低了譯碼復雜度。

1 極化碼

1.1 極化碼編碼和譯碼

極化碼利用K個最可靠的比特信道發(fā)送信息比特，其他信道發(fā)送固定比特。碼長為N的極化碼，信息比特與固定比特混合編碼得到發(fā)送碼字序列uN1=(u1,u2,…,uN)，對應的固定比特集合和非固定比特集合分別用uAC和uA表示。經過信道傳輸后，在接收端得到接收碼字序列yN1=(y1,y2,…,yN)，在譯碼器中完成碼字估計uN1=(u1,u2,…,uN)，W(|y x)表示傳遞概率。如果ui是固定比特，則ui=0；否則，SC 譯碼器計算每個比特信道的對數似然比（LLR）：

譯碼樹中，白色的葉子節(jié)點代表固定比特節(jié)點，黑色的葉子節(jié)點代表信息比特節(jié)點。給定一個譯碼樹節(jié)點V，令vp，vl和vr分別表示父節(jié)點、左孩子節(jié)點和右孩子節(jié)點，圖1 中給出極化碼（16，8）的SC 譯碼樹，節(jié)點V的譯碼單元如實線框中所示。

圖1 極化碼（16，8）譯碼樹

SCL 譯碼器是從所有路徑中選取路徑度量值最大的L條搜索路徑作為候選路徑，并添加CRC 校驗比特來篩選候選路徑。

1.2 關鍵集的構建

關鍵集（Critical Set，CS）選擇最不可靠的信息比特進行構建，通過翻轉CS 中信息比特提升譯碼性能。用該構建關鍵集合方法[11]，確定出最不可靠的葉子節(jié)點集（u7，u9，u10，u12）對應的索引序號作為翻轉譯碼的關鍵集合。根據該方法依次對所有葉子節(jié)點進行篩選，構建比特翻轉關鍵集合。根據確定的關鍵集合進行比特翻轉譯碼。

2 提出的譯碼算法

本文通過采用多比特翻轉譯碼和分段CRC 輔助SCL 比特翻轉譯碼結合以提高譯碼性能。

2.1 CA-SCL 多比特翻轉譯碼算法

根據信道噪聲引起的不同錯誤比特概率的分析，表明1 位錯和2 位錯是影響極化碼譯碼性能的主要原因。因此，本文采用翻轉2 bit譯碼方案，如圖2 所示。

圖2 翻轉2 bit CA-SCL（N，K +r）譯碼器流程圖

2.2 SCA-SCLF 譯碼算法

本文中，CA-SCL（P=x）表示分x段CRC 輔助SCL譯碼算法，SCA-SCLF（P=x，ω）表示分x段CRC 輔助SCL 翻轉ωbit 譯碼算法的情況。在分段極化碼編碼部分，將CRC 分配到每一段中進行極化碼編碼。首先依據各段的信息位置對關鍵集進行分段，各段的關鍵集合用T P1=(T1,T2,…,TP)表示，其對應的索引表示為ρP1=(ρ1,ρ2,…,ρP)。在譯碼中，根據接收到的傳遞結果yN1進行譯碼。分兩段CRC 輔助SCL 翻轉1 bit 的譯碼過程如算法1 所示。

根據各段先后順序，依次進行譯碼（第2 行）。首先進行傳統(tǒng)的CA-SCL 譯碼（第3～4 行），如果譯碼成功且不是最后一段，則保存譯碼結果，然后對后續(xù)的段進行譯碼（第18～19 行）。如果是最后一段，則譯碼正確，結束本幀譯碼（第20～21 行），反之，譯碼失敗，執(zhí)行翻轉1 bit 譯碼過程。根據CS 中的信息比特索引，執(zhí)行比特翻轉，嘗試譯碼（第7 行），如果通過CRC 校驗且不是最后一段，則轉到第2 行進行下一段譯碼，如果是最后一段，則終止譯碼過程（第8～12 行）。如果通過翻轉CS中對應的信息比特后譯碼失敗，程序提前終止，不再執(zhí)行后續(xù)段譯碼（第15～17 行）。

算法1：SCA-SCLF（P=2，1）譯碼算法

極化碼SCA-SCLF（P=2，2）譯碼過程如算法2 所示。應當注意，后一段譯碼是基于前一段中保留的候選路徑，如果翻轉1 bit 譯碼失敗，CS 中的信息位置需要進行非重復索引的成對組合，執(zhí)行翻轉2 bit 譯碼。如果翻轉2 bit 譯碼仍然失敗，譯碼將提前終止，節(jié)省了譯碼等待時間。

算法2：SCA-SCLF（P=2，2）譯碼算法

另外，與原來的譯碼過程相比，分段CRC 輔助SCL翻轉2 bit 譯碼算法，縮小了每段對應的關鍵集合規(guī)模，并減少了嘗試執(zhí)行翻轉2 bit 的組合數量，整體的譯碼復雜度將大大降低。

3 性能仿真及譯碼復雜度分析

本文中采用加性高斯白噪聲（Additive White Gaussian Noise，AWGN）信道和二進制相移鍵控（Binary Phase Shift Keying，BPSK）調制。12 位和24 位的CRC 生成多項式分別為：

3.1 性能仿真

極化碼（256，128+24）和（512，256+24）在L=8 和L=16 時的譯碼性能如圖3 和圖4 所示。在相同的CRC 條件下，翻轉2 bit 比翻轉1 bit 有更好的譯碼性能，分段翻轉譯碼比不分段有更好的譯碼性能。圖3 中，當L=8，誤幀率（Frame Error Rate，FER）為10-1時，對于極化碼（256，128+24），SCA-SCLF（P=2，2）比CA-SCL 獲得0.3 dB 的性能增益；FER 為10-2時，對于極化碼（512，256+24），SCA-SCLF（P=2，2）比CA-SCL 獲得性能增益為0.2 dB。圖4 中，L=16 下，在FER 為10-2時，對于極化碼（256，128+24），SCLF-ω=2 比SCLF-ω=1 可獲得0.1 dB的性能增益，SCA-SCLF（P=2，2）比CA-SCL 獲得性能增益為0.3 dB。

3.2 譯碼復雜度分析

本文通過譯碼過程中更新的節(jié)點次數統(tǒng)計計算復雜度。令sum 代表數據量的大小，compl_SC 表示傳統(tǒng)SC 算法的譯碼復雜度，compl_ave 表示平均計算復雜度，即更新的平均節(jié)點次數：

圖3 極化碼（256，128+24）和（512，256+24）L=8 的誤幀率

圖4 極化碼（256，128+24）和（512，256+24）L=16 的誤幀率

根據式（3）得到圖5 和圖6 的復雜度對比。圖5 中，L=8 時，在EbN0為1.5 dB 下，極化碼（256，128+24）SCASCLF（P=2，1）比SCLF-ω=1 譯碼復雜度可降低47.7%，SCA-SCLF（P=2，2）算法比SCLF-ω=2 譯碼復雜度可降低69.9%；同樣，極化碼（512，256+24）SCA-SCLF（P=2，1）算法比SCLF-ω=1 譯碼復雜度可降低46.3%，SCA-SCLF（P=2，2）比SCLF-ω=2 譯碼復雜度可降低71.9%；圖6中，L=16 下，在EbN0為1.5 dB 下，極化碼（256，128+24）SCA-SCLF（P=2，1）比SCLF-ω=1 譯碼復雜度可降低48.6%；在EbN0為2 dB 下，極化碼（512，256+24）SCASCLF（P=2，2）比SCLF-ω=2 譯碼復雜度可降低62.5%；在EbN0為1 dB 下，SCA-SCLF（P=2，1）算法比SCLF-ω=1譯碼復雜度可降低47.6%，在EbN0為1.5 dB 下，SCASCLF（P=2，2）算法比SCLF-ω=2 譯碼復雜度可降低58.8%。

圖5 極化碼（256，128+24）和（512，256+24）L=8 的平均譯碼復雜度對比

在相同的CRC 條件下，分段翻轉1 bit 譯碼比不分段翻轉1 bit 時復雜度更低；在相同的條件下，分段翻轉2 bit 譯碼比不分段翻轉2 bit 時復雜度更低?；诜侄巫g碼，首先對前一段進行CRC 校驗，如果校驗失敗就會終止譯碼，反之繼續(xù)進行下一段譯碼過程，通過該過程可抑制錯誤傳播，降低譯碼復雜度，其降低的程度與CRC 校驗能力和發(fā)生錯誤的個數有關。高EbN0下，錯誤比特較少，降低復雜度的程度不明顯；低EbN0下，存在更多的錯誤比特且比特翻轉校正能力受到限制。由于原來SCLF 譯碼算法中只能進行糾正1 bit 錯誤碼字，使用SCLF 譯碼算法翻轉2 bit 會造成較高的譯碼延遲，而采用SCA-SCLF 譯碼算法可大大降低譯碼復雜度。

4 結 語

本文提出一種分段CRC 輔助SCL 比特翻轉譯碼算法，該算法可糾正多比特錯誤，具有良好的譯碼性能；針對比特翻轉引起的譯碼復雜度較高的問題，該算法可降低譯碼延遲。仿真結果表明，采用分兩段翻轉2 bit 譯碼算法比使用SCLF 方法進行翻轉2 bit 譯碼算法具有更好的譯碼效果，當L=8，在EbN0=1.5 dB 時，極化碼（512，256+24）SCA-SCLF（P=2，2）比SCLF-ω=2 譯碼算法復雜度降低71.9%。

注：本文通訊作者為張小軍。