分段CRC 輔助極化碼SCL 比特翻轉(zhuǎn)譯碼算法

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

（山東科技大學(xué)，山東 青島 266590）

0 引 言

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

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

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

1 極化碼

1.1 極化碼編碼和譯碼

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

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

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

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

1.2 關(guān)鍵集的構(gòu)建

關(guān)鍵集（Critical Set，CS）選擇最不可靠的信息比特進(jìn)行構(gòu)建，通過翻轉(zhuǎn)CS 中信息比特提升譯碼性能。用該構(gòu)建關(guān)鍵集合方法[11]，確定出最不可靠的葉子節(jié)點(diǎn)集（u7，u9，u10，u12）對(duì)應(yīng)的索引序號(hào)作為翻轉(zhuǎn)譯碼的關(guān)鍵集合。根據(jù)該方法依次對(duì)所有葉子節(jié)點(diǎn)進(jìn)行篩選，構(gòu)建比特翻轉(zhuǎn)關(guān)鍵集合。根據(jù)確定的關(guān)鍵集合進(jìn)行比特翻轉(zhuǎn)譯碼。

2 提出的譯碼算法

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

2.1 CA-SCL 多比特翻轉(zhuǎn)譯碼算法

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

圖2 翻轉(zhuǎn)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 翻轉(zhuǎn)ωbit 譯碼算法的情況。在分段極化碼編碼部分，將CRC 分配到每一段中進(jìn)行極化碼編碼。首先依據(jù)各段的信息位置對(duì)關(guān)鍵集進(jìn)行分段，各段的關(guān)鍵集合用T P1=(T1,T2,…,TP)表示，其對(duì)應(yīng)的索引表示為ρP1=(ρ1,ρ2,…,ρP)。在譯碼中，根據(jù)接收到的傳遞結(jié)果yN1進(jìn)行譯碼。分兩段CRC 輔助SCL 翻轉(zhuǎn)1 bit 的譯碼過程如算法1 所示。

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

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

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

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

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

3 性能仿真及譯碼復(fù)雜度分析

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

3.1 性能仿真

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

3.2 譯碼復(fù)雜度分析

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

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

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

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

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

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

4 結(jié) 語

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

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