一種基于增強(qiáng)奇偶校驗(yàn)碼級聯(lián)極化碼的新型編譯碼方法

王燕，劉順蘭，奚珍珍，包建榮

（杭州電子科技大學(xué)電子信息學(xué)院，浙江 杭州 310018）

1 引言

極化碼（Polar碼）于2009年由Arikan E首次提出，是第一種理論上能達(dá)到香農(nóng)極限的信道編碼方法[1]，并且由于其較低的編碼、譯碼復(fù)雜度等優(yōu)勢，受到了廣泛的關(guān)注，成功入選5G標(biāo)準(zhǔn)，作為增強(qiáng)移動寬帶場景中控制信道的編碼方案[2-3]。當(dāng)極化碼的長度趨于無窮時(shí)，才能更好地達(dá)到信道容量，然而在中短碼長時(shí)性能較差。為了提高極化碼的糾錯性能，先后提出了許多不同的譯碼方法。參考文獻(xiàn)[1]提出采用串行抵消（successive cancellation，SC）譯碼算法，由于SC譯碼算法是一種次優(yōu)的譯碼算法，在有限長碼長中性能有待提升。在SC譯碼算法的基礎(chǔ)上，參考文獻(xiàn)[4]提出串行抵消列表（successive cancellation list，SCL）譯碼算法，該算法通過擴(kuò)張譯碼路徑，增大了譯碼結(jié)果正確的可能性。參考文獻(xiàn)[5]提出引入循環(huán)冗余校驗(yàn)碼與極化碼級聯(lián)，即CRC輔助SCL譯碼算法（CRC aided SCL，CA-SCL），有助于在SCL譯碼的列表中挑選出正確的譯碼結(jié)果。此后，參考文獻(xiàn)[6]提出的奇偶校驗(yàn)碼級聯(lián)極化碼引入校驗(yàn)比特，在譯碼過程中能夠?qū)崟r(shí)校驗(yàn)譯碼路徑，性能可優(yōu)于CRC級聯(lián)極化碼，不過使用的蒙特卡洛構(gòu)造方法使得復(fù)雜度嚴(yán)重增加。CRC輔助的Polar碼和PC輔助的Polar碼已被納入5G極化碼標(biāo)準(zhǔn)實(shí)現(xiàn)方案[3]。

Polar碼在不同譯碼算法下的糾錯性能具有差異，但Polar碼本身的糾錯性能在很大程度上受碼構(gòu)造的影響，即信息位和凍結(jié)位的選取。目前，針對AWGN信道還沒有精確的Polar碼構(gòu)造方法，只能對AWGN比特信道的可靠度進(jìn)行估計(jì)。常用的方法包括蒙特卡洛構(gòu)造[1]、密度進(jìn)化（density evolution，DE）構(gòu)造[7]、高斯近似（gaussian approximation，GA）構(gòu)造[8]、極化權(quán)重（polarization weight，PW）構(gòu)造[9]、量化方法[10]等。由于密度進(jìn)化構(gòu)造和高斯近似構(gòu)造都依賴構(gòu)造時(shí)AWGN信道的信噪比，針對不同信噪比的構(gòu)造結(jié)果存在差異。為了得到統(tǒng)一的Polar碼構(gòu)造序列，華為公司提出的極化權(quán)重方法是一種獨(dú)立于信噪比的構(gòu)造方法，相對于傳統(tǒng)的密度進(jìn)化和高斯近似，構(gòu)造結(jié)果具有嵌套性、復(fù)雜度較低。

CRC校驗(yàn)比特只能在譯碼結(jié)束后選擇通過校驗(yàn)的路徑，不能在譯碼過程中提高路徑選擇的可靠度，而PC校驗(yàn)比特可以彌補(bǔ)這一不足。參考文獻(xiàn)[11]提出將兩種級聯(lián)方案結(jié)合形成基于CRC輔助的PC碼級聯(lián)極化碼方案。本文在參考文獻(xiàn)[11]的基礎(chǔ)上，在奇偶校驗(yàn)位后添加一位重復(fù)碼校驗(yàn)位。在譯碼過程中，對于奇偶校驗(yàn)多次不通過的路徑及時(shí)刪除，相對于原有的PC碼輔助的CA-SCL譯碼算法降低了復(fù)雜度，對信道容量較低的信息比特再次進(jìn)行重復(fù)碼校驗(yàn)，輔助路徑度量篩選可靠性更高的路徑，譯碼結(jié)束后，采用CRC校驗(yàn)得到最優(yōu)路徑。

2 極化碼和其級聯(lián)方案

極化碼是一種基于信道極化理論的信道編碼方式。當(dāng)碼長不斷增加，編碼端通過碼字構(gòu)造方法后，各個(gè)子信道的信道容量呈現(xiàn)出兩級分化的現(xiàn)象：一部分信道的信道容量趨于1，而另一部分的信道容量趨于0。對于信道容量趨于1即可靠度比較高的信道傳輸信息比特，而信道容量趨于0即可靠度較低的信道傳輸凍結(jié)比特。

對于給定的碼長N，極化碼的編碼方式如下：

其中，GN(A)表示由 中元素對應(yīng)的行構(gòu)成的GN的子矩陣，GN(Ac)同理，⊕表示模2加。

上述的SC譯碼過程是串行進(jìn)行的，因此容易存在錯誤傳播現(xiàn)象。SCL譯碼算法在SC算法的基礎(chǔ)上引入了保留L條路徑的思想，對于每條路徑計(jì)算路徑度量（path metric，PM）[12]：

其中，l表示第l條路徑索引值，表示第l條路徑中第k個(gè)譯碼比特估計(jì)值，表示第l條路徑的對數(shù)似然比，l∈ {1,2,3,…,L}，在每條路徑擴(kuò)展后都在不可靠的路徑上加上一個(gè)懲罰值因此當(dāng)譯碼結(jié)束后得到L個(gè)譯碼序列，選取路徑度量最小的序列為最終的譯碼結(jié)果。

參考文獻(xiàn)[11]提出的基于CRC的PC碼級聯(lián)極化碼（CRC-PC-Polar）方案，如圖1所示，CRC和PC碼作為外碼，極化碼作為內(nèi)碼進(jìn)行編碼，信息比特經(jīng)過CRC編碼器，得到帶有C位的循環(huán)冗余校驗(yàn)比特的信息序列其次經(jīng)過PC編碼，得到 外碼 碼字極 化碼的信息位上放置外碼碼字，凍結(jié)位放置凍結(jié)比特，極化碼編碼后得到碼字

3 基于增強(qiáng)奇偶校驗(yàn)的級聯(lián)極化碼

基于CRC的增強(qiáng)奇偶校驗(yàn)碼級聯(lián)極化碼（CRC-EPC-Polar）如圖2所示，其中編碼主要由3部分——CRC編碼、增強(qiáng)PC編碼、Polar碼編碼組成，外碼碼字結(jié)構(gòu)如圖3所示。譯碼主要采用本文提出的增強(qiáng)PC輔助的CA-SCL譯碼算法。下文主要從編碼和譯碼兩個(gè)方面詳細(xì)闡述本文提出的新型編譯碼方法。

圖1 CRC-PC-Polar級聯(lián)方案

3.1 編碼

極化碼的構(gòu)造是編碼之前的一個(gè)重要部分。本文采取PW算法構(gòu)造估計(jì)信道的可靠性，挑選可靠性較高的信道進(jìn)行信息比特的傳輸。設(shè)極化信道序號為i，令i的二進(jìn)制展開為該極化信道的極化重量被定義為：

即該信道的可靠度度量值，其中極化重量越大，表示信道可靠度越高。對任意長度N，依次計(jì)算W0,W1,…,WN-1，并按照從小到大的順序排列，取其下標(biāo)就是可靠度由低到高的信道。例如，當(dāng)碼長為8時(shí)，n= lb8 =3，當(dāng)3.603 4。根據(jù)上述所得到的信道可靠性排序后，從中挑選M+C+Q個(gè)可靠性較高的信道傳輸非固定比特，其中Q=K+R，K為奇偶校驗(yàn)比特總數(shù)，R為增強(qiáng)校驗(yàn)比特總數(shù)，一般R=K，其余信道傳輸凍結(jié)比特。

其中，kp表示第k個(gè)PC校驗(yàn)比特在外碼碼字中的索引，集合Sk表示參與第k個(gè)校驗(yàn)方程的信息比特索引集合，本文中取從第一個(gè)信息比特到第k個(gè)PC校驗(yàn)比特之間所有的信息比特的集合。第r個(gè)重復(fù)校驗(yàn)比特編碼計(jì)算式為：

其中，tr表示第r個(gè)重復(fù)校驗(yàn)比特在外碼碼字中的索引，Skr表示第r個(gè)重復(fù)校驗(yàn)比特對應(yīng)的Sk，j為第r個(gè)校驗(yàn)方程中PW最小的信息比特索引，即在進(jìn)行奇偶校驗(yàn)時(shí)所需校驗(yàn)方程中信道可靠性最低的信息比特。將外碼碼字與凍結(jié)比特混合，外碼碼字映射到可靠度較高的信道，其余信道為凍結(jié)位，得到長度為N的序列。根據(jù)生成矩陣對編碼器的輸入序列進(jìn)行極化碼編碼，得到級聯(lián)碼字編碼完成。

3.2 譯碼

圖2 CRC-EPC-Polar級聯(lián)方案

圖3 外碼碼字結(jié)構(gòu)

CRC輔助的SCL譯碼算法只有在譯碼結(jié)束后進(jìn)行校驗(yàn)，基于增強(qiáng)奇偶校驗(yàn)的級聯(lián)極化碼譯碼算法彌補(bǔ)了這一不足，在譯碼過程中通過引入PC校驗(yàn)比特和重復(fù)校驗(yàn)比特，當(dāng)譯碼校驗(yàn)比特時(shí)，是根據(jù)校驗(yàn)比特所在的校驗(yàn)方程得到的，相當(dāng)于一類動態(tài)的凍結(jié)比特。對于奇偶校驗(yàn)不通過的路徑，記錄該條路徑的累計(jì)錯誤值，若該條候選路徑的累計(jì)錯誤值達(dá)到了所有候選路徑累計(jì)錯誤平均值，則該條候選路徑被刪除，相對于原有的PC碼輔助的SCL譯碼算法降低了復(fù)雜度。其次進(jìn)行重復(fù)比特校驗(yàn)，輔助路徑度量值在譯碼過程中進(jìn)行路徑選擇。假設(shè)該路徑出現(xiàn)了偶數(shù)個(gè)譯碼錯誤，即使通過了奇偶校驗(yàn)，重復(fù)校驗(yàn)比特也有可能將該條路徑判決為錯誤，導(dǎo)致該條路徑的路徑度量值變大，在后續(xù)的路徑選擇中很容易被刪除，從而達(dá)到糾錯的目的。基于上述分析，基于增強(qiáng)校驗(yàn)的級聯(lián)極化碼譯碼算法與CRC輔助的SCL譯碼算法具有近似的復(fù)雜度，并且在其譯碼過程中及時(shí)將錯誤路徑進(jìn)行了刪除，因此復(fù)雜度幾乎沒有增加。基于增強(qiáng)奇偶校驗(yàn)碼級聯(lián)極化碼譯碼算法流程如圖4所示。

圖4 基于增強(qiáng)奇偶校驗(yàn)碼級聯(lián)極化碼譯碼算法流程

3.3 復(fù)雜度分析

在編碼端，CRC-EPC-Polar級聯(lián)方案比CRC-PC-Polar級聯(lián)方案多了增強(qiáng)校驗(yàn)比特的確定，即選擇前一段信息比特中可靠性最低的比特，由于不涉及復(fù)雜的運(yùn)算，所以編碼復(fù)雜度只是微量地增加，相對于性能的提升是可以接受的。

在譯碼端，對于奇偶校驗(yàn)多次不通過的路徑及時(shí)進(jìn)行刪除，提前終止錯誤路徑的傳播，從而避免了這些路徑的后續(xù)譯碼過程，而CRC-PC-Polar的譯碼算法只是通過PC校驗(yàn)比特影響路徑度量值，在整個(gè)譯碼過程中還是保留了L條路徑，因此CRC-EPC-Polar譯碼算法節(jié)省了一部分存儲空間，譯碼復(fù)雜度有所降低。

4 仿真結(jié)果和分析

本文在加性高斯白噪聲信道下對比了3種不同方案的糾錯性能。仿真參數(shù)見表1。

表1 不同方案的仿真參數(shù)

其中，CRC-EPC-Polar表示本文提出的基于CRC輔助的增強(qiáng)奇偶校驗(yàn)碼級聯(lián)極化碼方案，CRC-Polar表示參考文獻(xiàn)[5]提出的CRC輔助的極化碼方案，CRC-PC-Polar表示參考文獻(xiàn)[11]提出的CRC輔助的基于奇偶校驗(yàn)碼級聯(lián)極化碼方案。在譯碼過程中，保留路徑L=16，保證每種方案的有效碼率相同，即真實(shí)的信息比特與碼長的比值相同，最后根據(jù)譯碼判決結(jié)果統(tǒng)計(jì)不同方案的誤碼率（bit error rate，BER）。

圖5～圖7分別是碼長為128、256、512，碼率不同時(shí)在高斯白噪聲信道下的性能比較。由圖5～圖7可以看出，在碼長相同、碼率不同時(shí)，本文提出的基于增強(qiáng)奇偶校驗(yàn)級聯(lián)極化碼方案均體現(xiàn)出較優(yōu)異的性能。由圖5看出，在碼長為128、碼率為1/2、誤碼率為 10-3時(shí)，本文提出的新型編譯碼方案比基于CRC-PC碼輔助的級聯(lián)極化碼獲得了0.3 dB的增益，比CRC輔助的級聯(lián)極化碼獲得了0.4 dB的增益；由圖6看出，在碼長為256、碼率為1/2、誤碼率為 10-3時(shí)，本文提出的新型級聯(lián)方法較CRC-PC級聯(lián)的極化碼獲得了0.2 dB的增益，較CRC輔助的級聯(lián)極化碼獲得了0.3 dB的增益；由圖7看出，在碼長為512，碼率、誤碼率相同時(shí)，本文提出的CRC-EPC-Polar方案比CRC-PC-Polar、CRC-Polar方案均有著接近0.1 dB的增益，在復(fù)雜度不明顯增加的情況下，本文的方案仍然可以借鑒。同時(shí)碼長相同，碼率越大，誤碼率也會越高。

圖5 碼長為128、碼率不同時(shí)在高斯白噪聲信道下的性能比較

圖6 碼長為256、碼率不同時(shí)在高斯白噪聲信道下的性能比較

圖7 碼長為512、碼率不同時(shí)在高斯白噪聲信道下的性能比較

圖8是碼率為1/2、碼長不同時(shí)3種級聯(lián)方案性能對比。由圖8可以看出，同種方案下，碼率相同，碼長越長，信道極化效果越好，誤碼率相對越低。總體而言，本文提出的CRC-EPC-Polar級聯(lián)方案比CRC-Polar、CRC-PC-Polar方案性能更優(yōu)異。

圖8 碼率為1/2、碼長不同時(shí)在高斯白噪聲信道下的性能比較

圖9是碼長為256，碼率分別為1/3、1/2、2/3時(shí)在二進(jìn)制刪除信道（binary erasure channel，BEC）中CRC-EPC-Polar級 聯(lián) 方 案 和CRC-PC-Polar級聯(lián)方案的性能比較，其中擦除概率取0.5。由圖9可以看出，在BEC中，本文提出的級聯(lián)方案相對于CRC-PC-Polar級聯(lián)方案仍然具有較優(yōu)異的性能。

圖9 碼長為256、碼率不同時(shí)在BEC下的性能比較

5 結(jié)束語

基于CRC輔助的極化碼和PC碼輔助的極化碼，本文提出了一種增強(qiáng)PC碼輔助的極化碼級聯(lián)方案，仿真結(jié)果顯示，在相同信道、相同碼長碼率下，本文提出的級聯(lián)極化碼比CRC級聯(lián)極化碼、CRC-PC級聯(lián)極化碼更優(yōu)異，誤碼性能得到了明顯的提升，為解決有限碼長性能不佳的問題提供了新思路。