文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.2016.07.003
中文引用格式： 何天光，杜江. 一種高性能低復(fù)雜度Polar Code編解碼算法研究[J].電子技術(shù)應(yīng)用，2016，42(7)：13-16，25.
英文引用格式： He Tianguang，Du Jiang. An efficient and low-complexity encoding and decoding algorithm of Polar Code[J].Application of Electronic Technique，2016，42(7)：13-16，25.
0 引言
在無(wú)線通信系統(tǒng)中，信道編碼的目的是使信息在有噪聲干擾的信道中能夠可靠地傳輸。根據(jù)香農(nóng)信息論[1]可知，任何通信信道的容量都有一個(gè)確定值C，如果通信系統(tǒng)中的傳輸速率R在滿足條件R<C時(shí)，則存在一種信道編碼，在不犧牲傳輸速率的情況下使信息碼元的誤碼率趨于任意小。為此，許多信道編碼領(lǐng)域的研究學(xué)者為達(dá)到這一目標(biāo)做出了許多貢獻(xiàn)。2009年，Arikan等人提出了極化碼(Polar Codes)[2-5]，是首次被嚴(yán)格證明能夠達(dá)到香農(nóng)極限容量的一種信道編碼，而且編譯碼復(fù)雜度在隨著碼長(zhǎng)增加時(shí)只保持對(duì)數(shù)增加。對(duì)于譯碼，連續(xù)抵消(Successive Cancelation，SC)譯碼[2，6]算法是Arikan針對(duì)極化碼編碼結(jié)構(gòu)提出的譯碼方案。但是，SC譯碼算法在碼長(zhǎng)有限時(shí)的性能與Turbo碼和LDPC碼相比不能體現(xiàn)其優(yōu)越性。因此許多學(xué)者在SC譯碼算法的基礎(chǔ)上進(jìn)行改進(jìn)，并提出了許多高性能的譯碼方案。這些算法的性能經(jīng)證明已經(jīng)優(yōu)于Turbo碼和LDPC碼[7-9]，比如序列列表SC譯碼(List SC，SCL)[8-9]、堆棧SC譯碼(Stack SC，SSC)[10]、循環(huán)冗余校驗(yàn)碼輔助SCL譯碼(CRC-SCL)[11]等算法。隨著全球5G通信系統(tǒng)研究的展開，Polar Code也得到了學(xué)術(shù)界和國(guó)內(nèi)外5G標(biāo)準(zhǔn)化研發(fā)機(jī)構(gòu)的強(qiáng)烈關(guān)注。
1 Polar Code編碼
1.1 編碼原理
極化碼（Polar Codes）是一種結(jié)構(gòu)性與迭代性極強(qiáng)的信道編碼，而且能夠被嚴(yán)格證明它的漸進(jìn)性能夠達(dá)到香農(nóng)極限容量。擁有如此高性能的信道編碼是因?yàn)樗木幋a核心思想：基于信道極化現(xiàn)象，使其信道性能（可靠性）極好的信道傳輸有用信息，反之傳輸雙方約定的固定信息。
1.2 信道極化
對(duì)于任意N=2n(n≥0)個(gè)獨(dú)立的二進(jìn)制對(duì)稱輸入離散無(wú)記憶信道（B-DMC）進(jìn)行遞推方式組合[5]，然后使其分裂后各個(gè)子信道的信道容量趨于兩極化，隨著碼長(zhǎng)N的增大，這些子信道的信道容量趨于兩極化的程度愈加明顯。因此這樣的操作可稱之為信道極化[2]。
例如當(dāng)n=1時(shí)，兩個(gè)獨(dú)立的B-DMC信道W通過(guò)如圖1所描述的方式組合成一個(gè)信道W2，這個(gè)過(guò)程可解釋為：信道的輸入信息為u1，u2∈{0，1}，通過(guò)編碼后為x1，x2∈{0，1}分別送入兩個(gè)子信道，輸出信號(hào)為y1，y2。
由此，可以通過(guò)信道轉(zhuǎn)移概率W(y|x)來(lái)表示B-DMC信道的信道容量：
通過(guò)式(2)、(3)和(4)可知，兩個(gè)子信道的信道容量一個(gè)較好一個(gè)較差，若N越大，極化效果會(huì)更加明顯。通過(guò)信道的極化結(jié)果，可以挑選出性能好的信道傳輸信息，可稱之為信息位；性能差的信道傳輸固定信息，可叫作固定位。
2 Polar Code譯碼
2.1 SC譯碼算法
為了計(jì)算公式更加簡(jiǎn)化和硬件可實(shí)現(xiàn)性，采用對(duì)數(shù)域的似然比(LLR)表示。由似然比進(jìn)行譯碼判決：
2.1.1 LLR（Log-Likelihood Ratio，LLR）計(jì)算方式
由于SC譯碼算法是Arikan針對(duì)極化碼編碼特性而設(shè)計(jì)出來(lái)的，那么它的譯碼結(jié)構(gòu)和它的編碼結(jié)構(gòu)一樣具有極其強(qiáng)的規(guī)則性。算法結(jié)構(gòu)圖如圖3所示。
圖中yi表示信道接收端接收的信號(hào)；
表示接收的信號(hào)yi通過(guò)譯碼器譯碼后的輸出值；λ表示層(Layer)，圖中每一列定義為一層：最左邊λ=3(λmax=log2 N+1)定義為決策層，最右邊λ=1為信道層，其他層統(tǒng)稱為中間層；
表示相位(Phase)，就是譯碼器在每一層計(jì)算節(jié)點(diǎn)的LLR值的順序，比如在本例中決策層的節(jié)點(diǎn)LLR值計(jì)算順序應(yīng)為圖中節(jié)點(diǎn)的(1，3，2，4)。
譯碼首先從決策層的節(jié)點(diǎn)1開始激活，來(lái)計(jì)算第一個(gè)碼子的LLR值，以此判決出它的譯碼結(jié)果，但是計(jì)算此處的LLR值需要右邊下一層節(jié)點(diǎn)5、7的LLR值。若這兩個(gè)節(jié)點(diǎn)的值已知，那么通過(guò)計(jì)算即可得到節(jié)點(diǎn)1的LLR值，否者還需要再下一層(本例中的信道層)的9、10、11、12節(jié)點(diǎn)的LLR值來(lái)決定5、7節(jié)點(diǎn)的LLR值，最終算出節(jié)點(diǎn)1的LLR值。信道層的LLR值的計(jì)算公式：
在計(jì)算出節(jié)點(diǎn)1的LLR值之后，5、7節(jié)點(diǎn)的LLR值已知，根據(jù)蝶形圖結(jié)構(gòu)，可以直接算出第二個(gè)譯碼碼子
對(duì)應(yīng)的節(jié)點(diǎn)3的LLR值。以此操作，直到計(jì)算出所有節(jié)點(diǎn)的LLR值為止。
在譯碼過(guò)程中，當(dāng)計(jì)算出某一個(gè)決策層節(jié)點(diǎn)的LLR值之后，首先需要判斷當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的碼元是否為信息位，如果是則根據(jù)式(6)可判決出當(dāng)前碼子的譯碼結(jié)果，否者該碼子直接判決為0。
以上的描述是SC譯碼算法的LLR值計(jì)算方式和判決流程，下面將要討論每一層(λ>1)各個(gè)節(jié)點(diǎn)的LLR值的計(jì)算公式。通過(guò)對(duì)譯碼結(jié)構(gòu)分析可知在每一層中第
個(gè)節(jié)點(diǎn)的LLR值計(jì)算時(shí)的計(jì)算公式為：
奇數(shù)時(shí)利用F函數(shù)進(jìn)行計(jì)算，?漬為偶數(shù)時(shí)使用G函數(shù)。
2.1.2 LLR存儲(chǔ)結(jié)構(gòu)
在進(jìn)行決策層節(jié)點(diǎn)的LLR值計(jì)算時(shí)會(huì)產(chǎn)生對(duì)應(yīng)中間層節(jié)點(diǎn)的LLR值和部分和數(shù)據(jù)，這些數(shù)據(jù)都是判決一個(gè)碼子的重要依據(jù)。通過(guò)上一小節(jié)描述的譯碼計(jì)算方式中可知信道層和中間層的LLR值和部分和都需要存儲(chǔ)。在LLR存儲(chǔ)時(shí)，根據(jù)LLR計(jì)算特性，以層λ為單元進(jìn)行存儲(chǔ)，第λ層需存儲(chǔ)的數(shù)據(jù)個(gè)數(shù)為n=2m-λ，m=log2 N+1。因此存儲(chǔ)結(jié)構(gòu)如圖4。
根據(jù)部分和的計(jì)算規(guī)則可知，它的存儲(chǔ)結(jié)構(gòu)與LLR值的存儲(chǔ)結(jié)構(gòu)類似。根據(jù)SC譯碼算法的結(jié)構(gòu)和硬判決特點(diǎn)，可知SC譯碼算法的空間復(fù)雜度和時(shí)間復(fù)雜度分別為O(N)和O(NlogN)。
通過(guò)以上對(duì)SC譯碼算法的研究不難發(fā)現(xiàn)，算法的一個(gè)潛在缺點(diǎn)是：判決當(dāng)前碼子
的值時(shí)需要
的參與，那么當(dāng)前碼子的判決結(jié)果會(huì)影響后續(xù)碼子的判決值。
2.2 SCL（SC List）譯碼算法
根據(jù)SC譯碼算法的缺點(diǎn)，將介紹一種改進(jìn)的算法SCL譯碼。SCL譯碼算法中L表示路徑搜索寬度，是算法的一個(gè)重要參數(shù)。SCL算法的思想是：在路徑搜索寬度不大于L的情況下，盡可能保留所有可能的譯碼路徑。例L=4如圖5。
由圖5所示在譯碼進(jìn)行過(guò)程中，每一次判決譯碼時(shí)進(jìn)行軟判決，一條路徑會(huì)擴(kuò)展出兩條支路0和1。由于在這兩條支路所對(duì)應(yīng)的數(shù)據(jù)是父節(jié)點(diǎn)對(duì)應(yīng)的LLR值和部分和的數(shù)據(jù)內(nèi)存，所以在這兩條支路繼續(xù)往下延伸時(shí)需要把父節(jié)點(diǎn)的數(shù)據(jù)復(fù)制到兩條支路之一，以保持兩條支路擁有獨(dú)立的數(shù)據(jù)內(nèi)存，這樣才能使兩條支路獨(dú)立地繼續(xù)向下延伸。當(dāng)譯碼器在譯碼過(guò)程擴(kuò)展出的路徑超過(guò)L時(shí)，就需要對(duì)這些路徑進(jìn)行刪減以保證所保留的譯碼路徑不超過(guò)L條。圖5中L=4，可知譯碼結(jié)束時(shí)，會(huì)產(chǎn)生4條路徑，每條路徑對(duì)應(yīng)如圖4所示的數(shù)據(jù)結(jié)構(gòu)。因此在SCL算法中還需要一個(gè)參數(shù)來(lái)度量當(dāng)路徑超過(guò)L時(shí)哪一條路徑需要?jiǎng)h除和決定哪一條路徑作為最終譯碼輸出結(jié)果，這個(gè)參數(shù)叫作路徑度量值(Path Metrics，PM)。PM值是根據(jù)決策層的LLR值計(jì)算得出的，計(jì)算公式如下：
縱觀整個(gè)SCL譯碼算法，可知它的核心算法是SC譯碼，在SCL算法中每一條譯碼路徑都相當(dāng)于一個(gè)SC譯碼而且都是獨(dú)立運(yùn)行的，所以路徑擴(kuò)展時(shí)需要進(jìn)行中間層LLR值和部分和值數(shù)據(jù)的復(fù)制，以保證每條路徑能夠順利的進(jìn)行計(jì)算譯出對(duì)應(yīng)的碼子結(jié)果，然后根據(jù)路徑度量值選出最優(yōu)的一條路徑作為最終的譯碼輸出。特別地，L=1相當(dāng)于SC譯碼算法。
3 譯碼算法優(yōu)化
3.1 SCL-CRC算法
為了更好地提升極化碼譯碼性能，在進(jìn)行編碼前加入循環(huán)冗余校驗(yàn)碼（Cyclic Redundancy Check，CRC）。在加入CRC后，在SCL譯碼最后的路徑選擇輸出碼子時(shí)可以優(yōu)先檢查CRC的正確性，再考慮PM值的大小。雖然加入CRC校驗(yàn)碼(一般為24位)之后，編碼的冗余度略增加，編碼率由k/N略下降為(k-24)/N，但隨著碼長(zhǎng)增加越不明顯。在顯著提升譯碼性能的前提下，顯然這點(diǎn)代價(jià)是可以付出的。
3.2 “Lazy Copy”算法
在SCL譯碼算法中，為了使每條譯碼路徑能夠獨(dú)立地進(jìn)行SC譯碼，在路徑擴(kuò)展時(shí)需要進(jìn)行數(shù)據(jù)的復(fù)制。但是，通過(guò)對(duì)SC譯碼算法的計(jì)算方式的分析，得知這些數(shù)據(jù)不一定需要進(jìn)行全部復(fù)制。比如由圖3所示，在判決出
的值完成之后應(yīng)該判斷
值時(shí)，只需要讓在計(jì)算
對(duì)應(yīng)的節(jié)點(diǎn)的LLR值時(shí)所得到節(jié)點(diǎn)5、 7的LLR參與計(jì)算，即可得出
對(duì)應(yīng)節(jié)點(diǎn)的LLR值。實(shí)際上，SCL譯碼算法在碼長(zhǎng)和L的值較大時(shí)，采取多條路徑對(duì)應(yīng)數(shù)據(jù)進(jìn)行全部復(fù)制在硬件難以實(shí)現(xiàn)，因此可以在復(fù)制數(shù)據(jù)時(shí)根據(jù)計(jì)算需要，只復(fù)制數(shù)據(jù)的地址以減輕復(fù)制的數(shù)據(jù)量。在新的路徑中需要數(shù)據(jù)參與計(jì)算時(shí)可直接通過(guò)先前復(fù)制的地址直接去尋址得到數(shù)據(jù)，在部分和的數(shù)據(jù)的復(fù)制上也可以采取同樣的方式，這種方法可稱之為“Lazy Copy”。這種算法大大減小了SCL譯碼算法在硬件實(shí)現(xiàn)中的功耗和存儲(chǔ)需求，提高了譯碼算法的可實(shí)現(xiàn)性。
4 仿真分析
Polar Code算法仿真平臺(tái)是基于AWGN信道下，采用碼長(zhǎng)N=1 024，碼率R=0.5，24位CRC碼，分別仿真了L=1，2，4，8，16，32的SCL譯碼算法性能。仿真結(jié)果如圖6。
仿真結(jié)果表明，隨著L的值的增加，誤碼率越低。由L=1和L=2的性能曲線可以看出，SCL譯碼算法的性能明顯優(yōu)于SC(L=1)算法的性能。
5 結(jié)語(yǔ)
極化碼是信道編碼領(lǐng)域中唯一被嚴(yán)格證明能夠達(dá)到香農(nóng)極限容量的編碼技術(shù)，目前在國(guó)際上也是研究的熱點(diǎn)，優(yōu)秀的性能也使它有望成為5G移動(dòng)通信系統(tǒng)中新型編碼體制的有力競(jìng)爭(zhēng)方案之一。本文通過(guò)對(duì)極化碼編碼和解碼的詳細(xì)剖析，可知無(wú)論是編碼還是解碼在算法上都有很大的研究空間。比如，雖然SCL譯碼與SC譯碼相比性能上有了很大的改善，但是算法的復(fù)雜度也由此增大。如何設(shè)計(jì)出更低復(fù)雜度更高效的譯碼算法也是學(xué)者們研究的方向之一。
參考文獻(xiàn)
[1] SHANNON C E.A mathematical theory of communication[J].Bell Syst Tech，1948，27(03)：379-423，623-656.
[2] ARIKAN E.Channel polarization: a method for constructing capacity achieving codes for symmetric binary input memoryless channels[J].IEEE Trans Inf.Theory，2009，55(7)：3051-3073.
[3] TELATAR E.Polar Coding：a brief tour[C].USA：IEEE，2010：1-2.
[4] RYUHEI M，TOSHIYUKI T.Performance and construction of polar codes on symmetric binary-input memoryless channels[C].USA：IEEE，2009：1946-1500.
[5] ARIKAN E.Channel combining and splitting for cut of rate improvement[J].IEEE Trans.Inf.Theory，2006，52(02)：628-639.
[6] 王東學(xué)，宋雷，張士偉.極化碼SC譯碼算法的設(shè)計(jì)[J].電光系統(tǒng)，2014(3)：10-13.
[7] HUANG Z L，DIAO C J，CHEN M.Latency reduced method for modified successive cancellation decoding of polar codes[J].Electronics Letters，2012，48(23)：1506-1506.
[8] 李純，童新海.極化碼序列連續(xù)刪除譯碼算法的改進(jìn)設(shè)計(jì)[J].通信技術(shù)，2015(1)：19-22.
[9] TAL I，VARDY A.List decoding of polar code[C].USA：IEEE ISIT 2011，2011：1-5.
[10] NIU K，CHEN K.Stack decoding of polar codes[J].Electronics Letters，2012，48(12)：695-697.
[11] NIU K，CHEN K.CRC-Aided decoding of polar codes[J].IEEE Communications Letters，2012，16(10)：1668-1671.