何天光，杜　江

（成都信息工程大學(xué) 通信工程學(xué)院，四川 成都 610225）

兩個子信道的轉(zhuǎn)移概率：

?

一種高性能低復(fù)雜度Polar Code編解碼算法研究*

何天光，杜江

（成都信息工程大學(xué) 通信工程學(xué)院，四川 成都 610225）

極化碼（Polar Codes，PC）是一種全新的高性能信道編碼技術(shù)，是5G移動通信系統(tǒng)的一個研究熱點，得到了廣泛的關(guān)注。傳統(tǒng)的連續(xù)刪除（Successive Cancelation，SC）譯碼算法在碼長有限的情況下的性能較差，為了提高極化碼的性能，從計算方式和存儲結(jié)構(gòu)兩個方面研究了SC譯碼算法的原理和結(jié)構(gòu)，提出一種SC譯碼算法的改進型算法CRC-SCL譯碼算法。為了降低該算法的復(fù)雜度，引入了“Lazy Copy”算法。仿真結(jié)果表明，CRC-SCL算法與SC算法相比，性能得到了顯著的提高。

極化碼；SC譯碼；SCL譯碼；Lazy Copy

中文引用格式：何天光，杜江.一種高性能低復(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　引言

在無線通信系統(tǒng)中，信道編碼的目的是使信息在有噪聲干擾的信道中能夠可靠地傳輸。根據(jù)香農(nóng)信息論［1］可知，任何通信信道的容量都有一個確定值C，如果通信系統(tǒng)中的傳輸速率R在滿足條件R＜C時，則存在一種信道編碼，在不犧牲傳輸速率的情況下使信息碼元的誤碼率趨于任意小。為此，許多信道編碼領(lǐng)域的研究學(xué)者為達到這一目標(biāo)做出了許多貢獻。2009年，Arikan等人提出了極化碼（Polar Codes）［2-5］，是首次被嚴格證明能夠達到香農(nóng)極限容量的一種信道編碼，而且編譯碼復(fù)雜度在隨著碼長增加時只保持對數(shù)增加。對于譯碼，連續(xù)抵消（Successive Cancelation，SC）譯碼［2，6］算法是Arikan針對極化碼編碼結(jié)構(gòu)提出的譯碼方案。但是，SC譯碼算法在碼長有限時的性能與Turbo碼和LDPC碼相比不能體現(xiàn)其優(yōu)越性。因此許多學(xué)者在SC譯碼算法的基礎(chǔ)上進行改進，并提出了許多高性能的譯碼方案。這些算法的性能經(jīng)證明已經(jīng)優(yōu)于 Turbo碼和 LDPC碼［7-9］，比如序列列表 SC譯碼（List SC，SCL）［8-9］、堆棧 SC譯碼（Stack SC，SSC）［10］、循環(huán)冗余校驗碼輔助 SCL譯碼（CRC-SCL）［11］等算法。隨著全球 5G通信系統(tǒng)研究的展開，Polar Code也得到了學(xué)術(shù)界和國內(nèi)外5G標(biāo)準(zhǔn)化研發(fā)機構(gòu)的強烈關(guān)注。

1　Polar Code編碼

1.1編碼原理

極化碼（Polar Codes）是一種結(jié)構(gòu)性與迭代性極強的信道編碼，而且能夠被嚴格證明它的漸進性能夠達到香農(nóng)極限容量。擁有如此高性能的信道編碼是因為它的編碼核心思想：基于信道極化現(xiàn)象，使其信道性能（可靠性）極好的信道傳輸有用信息，反之傳輸雙方約定的固定信息。

1.2信道極化

對于任意N=2n（n≥0）個獨立的二進制對稱輸入離散無記憶信道（B-DMC）進行遞推方式組合［5］，然后使其分裂后各個子信道的信道容量趨于兩極化，隨著碼長N的增大，這些子信道的信道容量趨于兩極化的程度愈加明顯。因此這樣的操作可稱之為信道極化［2］。

例如當(dāng)n=1時，兩個獨立的B-DMC信道W通過如圖1所描述的方式組合成一個信道W2，這個過程可解釋為：信道的輸入信息為u1，u2∈｛0，1｝，通過編碼后為 x1，x2∈｛0，1｝分別送入兩個子信道，輸出信號為 y1，y2。

由此，可以通過信道轉(zhuǎn)移概率W（y|x）來表示B-DMC信道的信道容量：

圖1　信道組合模型

則由圖1所示模型的組合信道W2的轉(zhuǎn)移概率：

兩個子信道的轉(zhuǎn)移概率：

通過式（2）、（3）和（4）可知，兩個子信道的信道容量一個較好一個較差，若N越大，極化效果會更加明顯。通過信道的極化結(jié)果，可以挑選出性能好的信道傳輸信息，可稱之為信息位；性能差的信道傳輸固定信息，可叫作固定位。

圖2　極化結(jié)果仿真圖

1.3信道編碼

通過極化現(xiàn)象，可得uN1=（u1，u2，u3，…，uN）的信息向量，向量由信息位和固定位組成。再由編碼生成矩陣GN可得極化碼編碼公式為式中表示比特反轉(zhuǎn)換序矩陣，中?表示Kronecker矩陣乘法?？梢暈?n個信道按照圖1所示的模型進行信道組合的數(shù)學(xué)抽象表示。如表示W(wǎng)2信道，兩個獨立的W2信道通過組合得一個W4信道，可表示為因此GN為F?n的子集。

2　Polar Code譯碼

2.1 SC譯碼算法

SC（Successive Cancelation）譯碼算法是 Arikan根據(jù)極化碼編碼結(jié)構(gòu)的特性所設(shè)計出來的算法。通過上一節(jié)所述的編碼公式可以提取出（N，K，，u∧C）的線性陪集碼，N表示為碼長，K為信息位長度（向量的元素個數(shù)），那么向量的元素是指定了信息向量中的信息位，uC表示固定位的值一般為0。由圖1所示譯碼的目的就是通過接收的信息重新生成的一個估值，顯然，、和是已知。由于在編碼時讓向量u∧C的值為發(fā)送和接收雙發(fā)都可知的固定值，所以在譯碼器中直接設(shè)置來避免在固定位的部分的譯碼錯誤。因此譯碼器的設(shè)計重點將放在怎么生成信息位u是估計值

似然比（Likelihood Ratio，LR）的定義為：

2.1.1LLR（Log-Likelihood Ratio，LLR）計算方式

由于 SC譯碼算法是Arikan針對極化碼編碼特性而設(shè)計出來的，那么它的譯碼結(jié)構(gòu)和它的編碼結(jié)構(gòu)一樣具有極其強的規(guī)則性。算法結(jié)構(gòu)圖如圖3所示。

為了計算公式更加簡化和硬件可實現(xiàn)性，采用對數(shù)域的似然比（LLR）表示。由似然比進行譯碼判決：

圖3　SC譯碼算法結(jié)構(gòu)圖

圖中 yi表示信道接收端接收的信號；u?i表示接收的信號yi通過譯碼器譯碼后的輸出值；λ表示層（Layer），圖中每一列定義為一層：最左邊λ=3（λmax=log2N+1）定義為決策層，最右邊 λ=1為信道層，其他層統(tǒng)稱為中間層；φ表示相位（Phase），就是譯碼器在每一層計算節(jié)點的LLR值的順序，比如在本例中決策層的節(jié)點LLR值計算順序應(yīng)為圖中節(jié)點的（1，3，2，4）。

譯碼首先從決策層的節(jié)點1開始激活，來計算第一個碼子的LLR值，以此判決出它的譯碼結(jié)果，但是計算此處的LLR值需要右邊下一層節(jié)點5、7的LLR值。若這兩個節(jié)點的值已知，那么通過計算即可得到節(jié)點1的LLR值，否者還需要再下一層（本例中的信道層）的 9、10、11、12節(jié)點的 LLR值來決定 5、7節(jié)點的 LLR值，最終算出節(jié)點1的LLR值。信道層的LLR值的計算公式：在計算出節(jié)點1的LLR值之后，5、7節(jié)點的LLR值已知，根據(jù)蝶形圖結(jié)構(gòu)，可以直接算出第二個譯碼碼子u?3對應(yīng)的節(jié)點3的LLR值。以此操作，直到計算出所有節(jié)點的LLR值為止。

在譯碼過程中，當(dāng)計算出某一個決策層節(jié)點的LLR值之后，首先需要判斷當(dāng)前節(jié)點對應(yīng)的碼元是否為信息位，如果是則根據(jù)式（6）可判決出當(dāng)前碼子的譯碼結(jié)果，否者該碼子直接判決為0。

以上的描述是SC譯碼算法的LLR值計算方式和判決流程，下面將要討論每一層（λ＞1）各個節(jié)點的LLR值的計算公式。通過對譯碼結(jié)構(gòu)分析可知在每一層中第φ個節(jié)點的LLR值計算時的計算公式為：φ奇數(shù)時利用F函數(shù)進行計算，φ為偶數(shù)時使用G函數(shù)。

F函數(shù)：

其中：

2.1.2LLR存儲結(jié)構(gòu)

在進行決策層節(jié)點的LLR值計算時會產(chǎn)生對應(yīng)中間層節(jié)點的LLR值和部分和數(shù)據(jù)，這些數(shù)據(jù)都是判決一個碼子的重要依據(jù)。通過上一小節(jié)描述的譯碼計算方式中可知信道層和中間層的LLR值和部分和都需要存儲。在LLR存儲時，根據(jù)LLR計算特性，以層λ為單元進行存儲，第 λ層需存儲的數(shù)據(jù)個數(shù)為 n=2m-λ，m=log2N+1。因此存儲結(jié)構(gòu)如圖4。

圖4　LLR存儲結(jié)構(gòu)示意圖

根據(jù)部分和的計算規(guī)則可知，它的存儲結(jié)構(gòu)與LLR值的存儲結(jié)構(gòu)類似。根據(jù)SC譯碼算法的結(jié)構(gòu)和硬判決特點，可知SC譯碼算法的空間復(fù)雜度和時間復(fù)雜度分別為O（N）和O（NlogN）。

通過以上對SC譯碼算法的研究不難發(fā)現(xiàn)，算法的一個潛在缺點是：判決當(dāng)前碼子u?i的值時需要u?i-1的參與，那么當(dāng)前碼子的判決結(jié)果會影響后續(xù)碼子的判決值。

2.2SCL（SC List）譯碼算法

根據(jù)SC譯碼算法的缺點，將介紹一種改進的算法SCL譯碼。SCL譯碼算法中L表示路徑搜索寬度，是算法的一個重要參數(shù)。SCL算法的思想是：在路徑搜索寬度不大于L的情況下，盡可能保留所有可能的譯碼路徑。例L=4如圖5。

圖5　SCL（L=4）譯碼的二叉樹路徑擴展模型

由圖5所示在譯碼進行過程中，每一次判決譯碼時進行軟判決，一條路徑會擴展出兩條支路0和1。由于在這兩條支路所對應(yīng)的數(shù)據(jù)是父節(jié)點對應(yīng)的LLR值和部分和的數(shù)據(jù)內(nèi)存，所以在這兩條支路繼續(xù)往下延伸時需要把父節(jié)點的數(shù)據(jù)復(fù)制到兩條支路之一，以保持兩條支路擁有獨立的數(shù)據(jù)內(nèi)存，這樣才能使兩條支路獨立地繼續(xù)向下延伸。當(dāng)譯碼器在譯碼過程擴展出的路徑超過L時，就需要對這些路徑進行刪減以保證所保留的譯碼路徑不超過L條。圖5中L=4，可知譯碼結(jié)束時，會產(chǎn)生4條路徑，每條路徑對應(yīng)如圖4所示的數(shù)據(jù)結(jié)構(gòu)。因此在SCL算法中還需要一個參數(shù)來度量當(dāng)路徑超過L時哪一條路徑需要刪除和決定哪一條路徑作為最終譯碼輸出結(jié)果，這個參數(shù)叫作路徑度量值（Path Metrics，PM）。PM值是根據(jù)決策層的LLR值計算得出的，計算公式如下：

若 ui∈u∧或固定位ui=0，且

時，有：

若ui為固定位，且取值錯誤時，有：

縱觀整個SCL譯碼算法，可知它的核心算法是SC譯碼，在SCL算法中每一條譯碼路徑都相當(dāng)于一個SC譯碼而且都是獨立運行的，所以路徑擴展時需要進行中間層LLR值和部分和值數(shù)據(jù)的復(fù)制，以保證每條路徑能夠順利的進行計算譯出對應(yīng)的碼子結(jié)果，然后根據(jù)路徑度量值選出最優(yōu)的一條路徑作為最終的譯碼輸出。特別地，L=1相當(dāng)于SC譯碼算法。

3　譯碼算法優(yōu)化

3.1SCL-CRC算法

為了更好地提升極化碼譯碼性能，在進行編碼前加入循環(huán)冗余校驗碼（Cyclic Redundancy Check，CRC）。在加入CRC后，在SCL譯碼最后的路徑選擇輸出碼子時可以優(yōu)先檢查CRC的正確性，再考慮PM值的大小。雖然加入CRC校驗碼（一般為24位）之后，編碼的冗余度略增加，編碼率由 k/N略下降為（k-24）/N，但隨著碼長增加越不明顯。在顯著提升譯碼性能的前提下，顯然這點代價是可以付出的。

3.2“Lazy Copy”算法

在SCL譯碼算法中，為了使每條譯碼路徑能夠獨立地進行SC譯碼，在路徑擴展時需要進行數(shù)據(jù)的復(fù)制。但是，通過對SC譯碼算法的計算方式的分析，得知這些數(shù)據(jù)不一定需要進行全部復(fù)制。比如由圖3所示，在判決出u?1的值完成之后應(yīng)該判斷u?3值時，只需要讓在計算u?1對應(yīng)的節(jié)點的LLR值時所得到節(jié)點5、7的LLR參與計算，即可得出u?3對應(yīng)節(jié)點的LLR值。實際上，SCL譯碼算法在碼長和L的值較大時，采取多條路徑對應(yīng)數(shù)據(jù)進行全部復(fù)制在硬件難以實現(xiàn)，因此可以在復(fù)制數(shù)據(jù)時根據(jù)計算需要，只復(fù)制數(shù)據(jù)的地址以減輕復(fù)制的數(shù)據(jù)量。在新的路徑中需要數(shù)據(jù)參與計算時可直接通過先前復(fù)制的地址直接去尋址得到數(shù)據(jù)，在部分和的數(shù)據(jù)的復(fù)制上也可以采取同樣的方式，這種方法可稱之為“Lazy Copy”。這種算法大大減小了SCL譯碼算法在硬件實現(xiàn)中的功耗和存儲需求，提高了譯碼算法的可實現(xiàn)性。

4　仿真分析

Polar Code算法仿真平臺是基于 AWGN信道下，采用碼長N=1 024，碼率R=0.5，24位CRC碼，分別仿真了L=1，2，4，8，16，32的SCL譯碼算法性能。仿真結(jié)果如圖6。

圖6　CRC-SCL譯碼算法仿真結(jié)果

仿真結(jié)果表明，隨著L的值的增加，誤碼率越低。由L=1和L=2的性能曲線可以看出，SCL譯碼算法的性能明顯優(yōu)于SC（L=1）算法的性能。

5　結(jié)語

極化碼是信道編碼領(lǐng)域中唯一被嚴格證明能夠達到香農(nóng)極限容量的編碼技術(shù)，目前在國際上也是研究的熱點，優(yōu)秀的性能也使它有望成為5G移動通信系統(tǒng)中新型編碼體制的有力競爭方案之一。本文通過對極化碼編碼和解碼的詳細剖析，可知無論是編碼還是解碼在算法上都有很大的研究空間。比如，雖然SCL譯碼與SC譯碼相比性能上有了很大的改善，但是算法的復(fù)雜度也由此增大。如何設(shè)計出更低復(fù)雜度更高效的譯碼算法也是學(xué)者們研究的方向之一。

［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］.電光系統(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ù)刪除譯碼算法的改進設(shè)計［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.

An efficient and low-complexity encoding and decoding algorithm of Polar Code

He Tianguang，Du Jiang
（School of Communication Engineering，Chengdu University of Information Technology，Chengdu 610225，China）

Polar Codes，a new high-performance coding technology，is a research focus in the 5G mobile communication system，and has been widely concerned.The performance of traditional Successive Cancelation（SC）decoding at short to moderate block lengths is disappointing，in order to improve the performance of polar codes，this paper studies the principle and structure of SC decoding algorithm from two aspects of calculation and storage structure，a modified algorithm of SC decoding called CRC-SCL decoding algorithm.For the aims of decreasing the complexity of the algorithm，this paper introduces the"Lazy Copy"algorithm.The simulation results show that compared with the SC algorithm，the SCL algorithm has significantly improve performance.

Polar Codes；SC；SCL；Lazy Copy

TN911.3

A

10.16157/j.issn.0258-7998.2016.07.003

四川省科技廳科技創(chuàng)新研發(fā)專項——科技支撐計劃資助項目（2014RZ0017）

2016-03-21）

何天光（1991-），男，碩士研究生，主要研究方向：無線通信技術(shù)與應(yīng)用。

杜江（1969-），男，博士后，教授，主要研究方向：新一代無線通信技術(shù)的理論及其芯片設(shè)計。