用數(shù)學(xué)證明的方法證明了簡(jiǎn)化算法的可行性

摘要：

極化碼是目前唯一可以從數(shù)學(xué)角度證明達(dá)到香農(nóng)極限的糾錯(cuò)編碼技術(shù)。但是傳統(tǒng)的譯碼算法、連續(xù)刪除（SC）譯碼和連續(xù)刪除列表（SCL）譯碼算法復(fù)雜度較高，使得譯碼過(guò)程有較大譯碼延時(shí)。經(jīng)過(guò)研究譯碼算法的原理和特點(diǎn)，證明部分節(jié)點(diǎn)的譯碼運(yùn)算是冗余，提出了SC譯碼和SCL譯碼簡(jiǎn)化算法。證明了簡(jiǎn)化的譯碼算法在保證譯碼性能不變的前提下，顯著降低了譯碼的復(fù)雜度。

0 引言

2009年ARIKAN E教授提出了極化碼[1]，并且通過(guò)數(shù)學(xué)方法證明了當(dāng)碼長(zhǎng)無(wú)限長(zhǎng)時(shí)其性能可以達(dá)到香農(nóng)極限。極化碼一經(jīng)提出就在國(guó)際上引起廣泛的關(guān)注，并且在2016年11月3GPP RAN1 #87會(huì)議上確定5G eMBB場(chǎng)景控制信道編碼為極化碼。

極化碼在實(shí)際應(yīng)用中存在著一些缺點(diǎn)。連續(xù)刪除(Successive Cancellation，SC)譯碼對(duì)于長(zhǎng)碼有很好的糾錯(cuò)性能，但是對(duì)中短碼長(zhǎng)譯碼性能有顯著的降低。為了克服這個(gè)問(wèn)題，學(xué)者們提出了許多改進(jìn)方法，如置信傳播（Belief Propagation，BP）譯碼算法[2]、線性規(guī)劃（Linear Programming，LP）譯碼算法[3]等。這些算法雖然可以提高一部分譯碼性能，但是譯碼算法的復(fù)雜度太大。一些算法針對(duì)SC算法進(jìn)行了改進(jìn)，文獻(xiàn)[4]提出了連續(xù)刪除列表(Successive Cancellation List，SCL)譯碼算法，特別是在冗余循環(huán)校驗(yàn)(Cyclic Redundancy Check，CRC)輔助下的SCL的譯碼性能可以超過(guò)最大似然(Maximum Likelihood，ML)譯碼[5]。但同時(shí)SCL譯碼的復(fù)雜度也隨之增加。文獻(xiàn)[6]中提出的堆棧SC（SCStack，SCS）譯碼有和SCL譯碼相同的譯碼性能，此外SCS譯碼的時(shí)間復(fù)雜度遠(yuǎn)低于SCL譯碼，并且在高的信噪比下可以降低搜索寬度L。

本文對(duì)SC譯碼和SCL譯碼進(jìn)行了算法簡(jiǎn)化，降低了算法的復(fù)雜度和時(shí)延。并且用數(shù)學(xué)證明的方法證明了簡(jiǎn)化算法的可行性。

1 極化碼編碼

Polar Code是一種結(jié)構(gòu)性與迭代性極強(qiáng)的信道編碼技術(shù)，其設(shè)計(jì)核心理論是對(duì)信道的極化，信道極化過(guò)程主要包括兩部分[1]：信道聯(lián)合過(guò)程和信道分裂過(guò)程。

1.1 信道極化[1]

信道聯(lián)合：對(duì)已知的二進(jìn)制離散無(wú)記憶信道W進(jìn)行N次迭代復(fù)制WN：XN→YN，N=2n，并對(duì)復(fù)制所得信道進(jìn)行遞推方式組合。WN和WN之間的轉(zhuǎn)移概率關(guān)系為：

圖1所示為在高斯信道下，碼長(zhǎng)為N=4 096的信道極化仿真圖。根據(jù)仿真結(jié)果，可以看出部分信道的信道容量成兩極分化。據(jù)此可以選出I(W)→1的信道傳輸信息比特作為信息位，I(W)→0的信道傳輸固定比特作為凍結(jié)位。

1.2 極化碼編碼

2 SC譯碼算法

把βv傳遞給pv。這時(shí)v節(jié)點(diǎn)的譯碼消息傳遞終止，因?yàn)樵谟嘞伦g碼過(guò)程中將不會(huì)再次激活節(jié)點(diǎn)v。

2.1 簡(jiǎn)化的SC譯碼算法

本節(jié)通過(guò)簡(jiǎn)化傳統(tǒng)譯碼的消息傳遞規(guī)則，簡(jiǎn)化了SC譯碼算法。并且證明簡(jiǎn)化譯碼算法的譯碼性能是與傳統(tǒng)的譯碼性能相同。

(1)Rate-0節(jié)點(diǎn)

對(duì)于Rate-0節(jié)點(diǎn)v，由于它所有后代都是Rate-0節(jié)點(diǎn)，因此當(dāng)v接收到軟信息αv時(shí)，不去激活左右的子節(jié)點(diǎn)而直接計(jì)算βv：

對(duì)于任意dv=n-1的Rate-1節(jié)點(diǎn)一定滿足式(15)。假設(shè)dv=i的Rate-1節(jié)點(diǎn)也滿足(15)，于是對(duì)于dv=i-1的Rate-1節(jié)點(diǎn)v的子節(jié)點(diǎn)dv=i，滿足式(15)。因此，根據(jù)上面的推導(dǎo)可以證明式(12)成立。

②證明式(13)成立：當(dāng)dv=n時(shí)，對(duì)Rate-1節(jié)點(diǎn)，式(13)顯然是成立，因此，可以通過(guò)歸納法證明dv

2.2 算法復(fù)雜度分析

3 SCL譯碼算法

為了提高SC譯碼算法在碼長(zhǎng)較短情況下糾錯(cuò)能力，SCL譯碼算法被提出，L代表搜索寬度。每次必須有一點(diǎn)被估計(jì)，它的可能值0和1都需要被考慮。因?yàn)榇嬖贚組碼字候選，所以每次新的位估計(jì)產(chǎn)生2L組候選路徑，其中一半需要丟棄。因此，路徑度量值(Path Metric，PM)被提出。PM計(jì)算如下：

SCL譯碼算法是從根節(jié)點(diǎn)出發(fā)，按廣度優(yōu)先的方法對(duì)路徑進(jìn)行擴(kuò)展；每一層向下一層擴(kuò)展時(shí)，選擇當(dāng)前層中具有較小PM的L條。當(dāng)沒有到達(dá)葉節(jié)點(diǎn)而搜索寬度已經(jīng)達(dá)到，按照PM的從大到小的排列保留PM小的L條路徑。直到到達(dá)葉節(jié)點(diǎn)，然后選取PM最小路徑作為譯碼結(jié)果。

為了進(jìn)一步提高極化碼的譯碼性能，編碼前在信息比特中添加CRC，然后利用SCL譯碼算法獲得L條搜索路徑，最后借助“正確信息比特可以通過(guò)CRC校驗(yàn)”的先驗(yàn)信息，對(duì)這L條搜索路徑進(jìn)行挑選，從而得到正確譯碼結(jié)果。

4 簡(jiǎn)化的SCL譯碼算法

傳統(tǒng)的SCL譯碼算法每次進(jìn)行路徑擴(kuò)展時(shí)都會(huì)產(chǎn)生2L條路徑，但是對(duì)于凍結(jié)比特，由于譯碼結(jié)果是已知的，因此對(duì)于凍結(jié)比特不進(jìn)行路徑擴(kuò)展，直接判決比特，路徑度量值也不改變，從而減少剪枝算法執(zhí)行的次數(shù)，達(dá)到降低算法復(fù)雜度的目的。

由上述的譯碼過(guò)程分析，式(20)PM的計(jì)算可以改為：

因?yàn)閮鼋Y(jié)比特在譯碼過(guò)程中結(jié)果是已知的，所以不需要去選擇路徑，進(jìn)而PM也不需要計(jì)算。另外，由于分裂次數(shù)的減少，剪枝算法也隨之減少，并最終達(dá)到了降低算法復(fù)雜度的目的。

5 仿真結(jié)果與分析

如圖4所示，在高斯信道下，碼長(zhǎng)為1 024，碼率為0.5，采用二進(jìn)制相移鍵控調(diào)制，譯碼輸出使用24位CRC校驗(yàn)。搜索寬度L分別為1，2，4，8，16，32 的CA-SCL譯碼性能，仿真數(shù)據(jù)是106幀，一幀長(zhǎng)1 024個(gè)比特。仿真結(jié)果表明，隨著L的值增加，誤碼率在逐漸降低，CA-SCL譯碼算法的性能明顯要優(yōu)于SC(L=1)譯碼算法。

6 結(jié)論

極化碼是目前唯一可以通過(guò)數(shù)學(xué)證明達(dá)到香農(nóng)極限的信道編碼技術(shù)，并且已經(jīng)成為5G控制信道的編碼方案。本文詳細(xì)敘述極化碼編譯碼的原理和結(jié)構(gòu)，并提出關(guān)于SC譯碼和SCL譯碼的優(yōu)化算法，在不改變譯碼性能的前提下，降低了算法復(fù)雜度。通過(guò)對(duì)SC譯碼和SCL譯碼的性能進(jìn)行了仿真分析，結(jié)果表明，隨著搜索寬度L的增加，極化碼的譯碼性更優(yōu)，但復(fù)雜度也隨著增加。因此關(guān)于SCL的復(fù)雜度和數(shù)據(jù)吞吐量是下一步研究方向。