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

何天光，杜　江

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

兩個子信道的轉移概率：

?

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

何天光，杜江

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

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

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

中文引用格式：何天光，杜江.一種高性能低復雜度 Polar Code編解碼算法研究［J］.電子技術應用，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　引言

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

1　Polar Code編碼

1.1編碼原理

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

1.2信道極化

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

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

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

圖1　信道組合模型

則由圖1所示模型的組合信道W2的轉移概率：

兩個子信道的轉移概率：

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

圖2　極化結果仿真圖

1.3信道編碼

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

2　Polar Code譯碼

2.1 SC譯碼算法

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

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

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

由于 SC譯碼算法是Arikan針對極化碼編碼特性而設計出來的，那么它的譯碼結構和它的編碼結構一樣具有極其強的規則性。算法結構圖如圖3所示。

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

圖3　SC譯碼算法結構圖

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

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

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

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

F函數：

其中：

2.1.2LLR存儲結構

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

圖4　LLR存儲結構示意圖

根據部分和的計算規則可知，它的存儲結構與LLR值的存儲結構類似。根據SC譯碼算法的結構和硬判決特點，可知SC譯碼算法的空間復雜度和時間復雜度分別為O（N）和O（NlogN）。

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

2.2SCL（SC List）譯碼算法

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

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

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

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

時，有：

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

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

3　譯碼算法優化

3.1SCL-CRC算法

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

3.2“Lazy Copy”算法

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

4　仿真分析

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

圖6　CRC-SCL譯碼算法仿真結果

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

5　結語

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

［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］王東學，宋雷，張士偉.極化碼 SC譯碼算法的設計［J］.電光系統，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］李純，童新海.極化碼序列連續刪除譯碼算法的改進設計［J］.通信技術，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

四川省科技廳科技創新研發專項——科技支撐計劃資助項目（2014RZ0017）

2016-03-21）

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

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