0 引言

    在無線通信系統(tǒng)中，信道編碼的目的是使信息在有噪聲干擾的信道中能夠可靠地傳輸。根據香農信息論^[1]可知，任何通信信道的容量都有一個確定值C，如果通信系統(tǒng)中的傳輸速率R在滿足條件R<C時，則存在一種信道編碼，在不犧牲傳輸速率的情況下使信息碼元的誤碼率趨于任意小。為此，許多信道編碼領域的研究學者為達到這一目標做出了許多貢獻。2009年，Arikan等人提出了極化碼(Polar Codes)^[2-5]，是首次被嚴格證明能夠達到香農極限容量的一種信道編碼，而且編譯碼復雜度在隨著碼長增加時只保持對數增加。對于譯碼，連續(xù)抵消(Successive Cancelation，SC)譯碼^[2，6]算法是Arikan針對極化碼編碼結構提出的譯碼方案。但是，SC譯碼算法在碼長有限時的性能與Turbo碼和LDPC碼相比不能體現其優(yōu)越性。因此許多學者在SC譯碼算法的基礎上進行改進，并提出了許多高性能的譯碼方案。這些算法的性能經證明已經優(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也得到了學術界和國內外5G標準化研發(fā)機構的強烈關注。

1 Polar Code編碼

1.1 編碼原理

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

1.2 信道極化

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

    例如當n=1時，兩個獨立的B-DMC信道W通過如圖1所描述的方式組合成一個信道W2，這個過程可解釋為：信道的輸入信息為u₁，u₂∈{0，1}，通過編碼后為x₁，x₂∈{0，1}分別送入兩個子信道，輸出信號為y₁，y₂。

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

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

2 Polar Code譯碼

2.1 SC譯碼算法

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

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

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

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

    譯碼首先從決策層的節(jié)點1開始激活，來計算第一個碼子的LLR值，以此判決出它的譯碼結果，但是計算此處的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值已知，根據蝶形圖結構，可以直接算出第二個譯碼碼子對應的節(jié)點3的LLR值。以此操作，直到計算出所有節(jié)點的LLR值為止。

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

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

2.1.2 LLR存儲結構

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

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

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

2.2 SCL（SC List）譯碼算法

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

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

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

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

3.1 SCL-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譯碼，在路徑擴展時需要進行數據的復制。但是，通過對SC譯碼算法的計算方式的分析，得知這些數據不一定需要進行全部復制。比如由圖3所示，在判決出的值完成之后應該判斷值時，只需要讓在計算對應的節(jié)點的LLR值時所得到節(jié)點5、 7的LLR參與計算，即可得出對應節(jié)點的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。

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

5 結語

    極化碼是信道編碼領域中唯一被嚴格證明能夠達到香農極限容量的編碼技術，目前在國際上也是研究的熱點，優(yōu)秀的性能也使它有望成為5G移動通信系統(tǒng)中新型編碼體制的有力競爭方案之一。本文通過對極化碼編碼和解碼的詳細剖析，可知無論是編碼還是解碼在算法上都有很大的研究空間。比如，雖然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].電光系統(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].通信技術，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.