極化碼連續刪除算法的改進*

李 純，關成濤

(西昌衛星發射中心，海南 文昌 571300)

極化碼連續刪除算法的改進*

李 純，關成濤

(西昌衛星發射中心，海南 文昌 571300)

提出一種改進的連續刪除算法，通過添加監督節點來改善譯碼性能。具體的，根據發送序列里節點類型的不同，添加固定監督節點和信息監督節點來加強信息傳輸的可靠度，以提高譯碼的精度。仿真結果表明，與原始的連續刪除算法相比，改進算法通過增加監督節點譯碼的計算量，從而提高了其譯碼的性能。

連續刪除算法；可靠度；監督節點；極化碼

0 引 言

通過信道極化的理論分析[1-2]，Arikan證明極化碼可以獲得Shannon理論極限性能，并且保持對數編譯碼復雜度。然而，研究表明，和傳統的Turbo碼、LDPC碼相比，極化碼在碼長受限時，誤碼性能還不理想。為了推進極化碼在工程上的應用，許多高性能譯碼算法被相繼提出。

連續刪除（Successive Cancellation，SC）算法由Arikan首次提出，利用比特信道似然概率的硬判決值輸出譯碼序列，根據信道的拆分進行迭代計算。目前，所提出的譯碼算法主要分為兩類：一類是基于SC的改進算法，如簡化的SC（Simplified SC，SSC）、基于堆棧SC（SC Stack，SCS）、基于序列的SC（SC List,SCL）以及基于循環冗余校驗（Cyclic Redundancy Check）輔助的SCL（CRC-SCL）串行譯碼算法；另一類是基于置信度傳播（Belief Propagation，BP）的并行譯碼算法[3-7]。

傳統的SC譯碼算法具有延遲大、精度不高等

缺陷，性能并不理想。改進的SC算法通過添加監督節點的方法來提高信息傳輸的可靠性，改善誤碼性能，并通過建立可靠條件，對碼字進行信息糾錯，一定程度上抑制了突發錯誤的出現。

1 極化碼

極化碼的待編碼序列u1N由兩部分構成：一部分為有效信息序列（uA）；一部分為對于編譯碼均已知的固定序列（）。固定序列的元素取值已知，根據信道極化理論，信道容量高的子信道發送信息位，信道容量低的子信道發送凍結比特。因為凍結比特的元素取值已知，所以Polar編碼器某些中間節點也是已知的。圖1為碼長N=8的編碼器結構，左邊為編碼輸入端，右邊為編碼輸出端，信息序列和固定比特序列分別為：uA={u4,u6,u7,u8}和={u1,u2,u3,u5}={0,0,0,0}；節點p(0,1)、p(0,2)、p(0,3)、p(0,5)、p(1,1)、p(1,5)取值已知。其中，p(1,1)、p(1,5)凍結比特產生中間節點。由于極化碼生成矩陣GN逆矩陣等于本身[1]，所以極化碼譯碼器具有與編碼器相同的結構。受固定節點的影響，Polar譯碼器同樣存在固定節點。

圖1 N=8的Polar編碼器

2 連續刪除算法

SC算法是一種串行譯碼方法，其第i次譯碼依賴于前i-1次的譯碼結果。譯碼結束時，需要更新訪問O(Nlog2N)個節點，算法的時間和空間復雜度均為O(Nlog2N)。整個譯碼過程可以分為三個階段。

階段1：初始化。經過噪聲干擾后，接收端y=(y1,y2,…,yn)碼字序列，每一個子信道都有一個似然比

階段2：按照串行譯碼順序，計算第i個比特信道的概率：

3 改進的連續刪除算法

改進的SC譯碼算法基于固定序列，對于這個編譯碼序列是已知的，獨立于整個譯碼過程。只要碼率R＜1，Polar譯碼器就會存在已知的凍結比特，在SC譯碼無誤的情況下，這些固定節點[8]需滿足條件：

根據式（5）能夠判斷vi節點是否正確。為了便于表示，下文稱式（5）為可靠度條件[9]。

在SC譯碼過程中，固定節點消息與信息節點消息同時進行迭代更新。迭代的同時，固定節點消息值同樣會隨著信道觀測序列變化。由于高斯噪聲的干擾，固定節點一定會出現不滿足上述可靠度條件的情況，從而導致錯誤積累，影響后面譯碼的準確性。因此，本文提出給SC譯碼器中每個處理節點增加一個監督節點，用于修正每個節點的可靠性，提高譯碼的準確性，如圖2所示。

圖2 碼長為8添加監督節點的Polar譯碼器

按照被發送序列中存在的不同類型節 點，監督節點分為兩類：黑色節點為固定序列的監督節點，白色節點為信息序列的監督節點。監督節點自身消息固定且不能進行迭代更新。通過監督節點修正后，奇數時，迭代關系式如式（6）；偶數時，迭代關系式如式（7）。

添加的監督節點用以加強可靠度條件，因此固定序列的監督節點必須滿足條件：

通過分析，存在關系式：

圖3 SC譯碼算法路徑搜索過程

信息監督節點不像固定監督節點，能夠通過可靠度條件來檢測消息節點消息是否存在錯誤，并通過加強固定序列的可靠性提升信息序列的譯碼能力。所以，在定義信息監督節點時應該滿足：

通過式（10）可知，信息監督節點沒有影響信息節點的似然比，不會影響信息節點消息的可靠度。

可見，在整個串行譯碼過程中，通過添加監督節點可加強固定序列的可靠度，從而保持信息序列的可靠度。一定程度上，監督節點的信息糾錯能力提升了譯碼性能。

4 仿真結果

仿真中，物理信道假設為AWGN信道，采用BPSK調制方法，碼長為N=32，碼率R=0.5，設定一個信噪比為一次仿真實驗，接收端按照數據幀來統計誤比特率，每幀數據長度為碼字的信息比特長度。每次實驗的錯誤比特數不少于100，幀數少于100 000。為了評估所提算法的性能，對原始SC算法進行仿真，仿真結果如圖4所示。

圖4 不同譯碼算法對比

由圖4可見，改進的SC算法的誤比特率優于SC算法，表明增加監督節點能夠有效提高SC消息傳播的可靠度。通過提高凍結比特的可靠度，在迭代譯碼過程中保證了固定節點消息值不受信道觀測序列的變化影響，始終滿足從而提高譯碼性能。同時，監督節點通過式（9）修正，僅僅通過分子分母同時相乘校正因子來提高硬判結果，并沒有改變迭代算法的復雜度，每次譯碼訪問的節點數仍為O(Nlog2N)。該算法能夠提升極化碼SC的譯碼性能，但是依賴于監督節點的消息。

5 結 語

極化碼是編碼領域較新的一個課題，是目前唯一能夠在BDMC上證明達到Shannon極限的碼字，代表了未來通信發展的一個方向。增加監督節點連續刪除算法在犧牲計算量的基礎上，譯碼性能得到了一定提升，通過固定監督節點的可靠性消息的傳播來保證譯碼的正確性。仿真結果表明，改進的SC算法的譯碼性能比原SC算法好。本文只是討論了固定序列的可靠性條件，對消息序列的可靠性條件尚未開展討論，下一步工作將在于如何確定所有的凍結比特始終能夠滿足可靠度條件。

[1] ArikanE. Channel Polarization: A Method for Constructing Capacity-achieving Codes for Symmetric Binary-input Memoryless Channels [J].IEEE Transactions onInformation Theory,2009,52(02):3051-3073.

[2] Arikan E.Channel Combining and Splitting for Cutoff Rate Improvement[C].In Proc. of IEEE Int. Symp. Inf. Theory2005,2005:671-675.

[3] 李斌,王學東,王繼偉.極化碼原理及應用[J].通信

技術,2012,45(10):21-23. LI Bin,WANG Xue-dong,WANG Ji-wei.Theory and Application of Polar Code[J].Communications Technology,2012,45(10):21-23.

[4] I Tal,A Vardy. List Decoding of Polar Codes[C]. IEEE International Symposium on Information Theory,2012,61(05):1-5.

[5] K Niu,K Chen. CRC-Aided Decoding of Polar Codes [J]. IEEE Communications Letters,2012,16(10):1668-1671.

[6] K Niu,K Chen.Stack Decoding of Polar Codes [J]. Electronics Letters,2012,48(12):695-697.

[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] Leroux C.,Raymond A.J.,Sarkis G.A.Vardy and Hardware Implementation of Successive-cancellation Decoders for Polar Codes [J].Journal of Signal Processing Systems,2012,69(03):305-315.

[9] Zhang Y.X.,Liu A.J. A Modified Belief Propagation Polar Decoder[J].IEEE. Communications Letters 2014,18(07):1091-1094.

李 純（1989—），男，碩士，助理工程師，主要研究方向為衛星通信；

關成濤（1982—），男，學士，工程師，主要研究方向為現代通信技術。

A Modified Successive Cancellation Polar Decoder

LI Chun,GUAN Cheng-tao
(Xichang Satellite Launch Center,WenchangHainan571300,China)

In this paper, a modified successive cancellation (SC) polar decoder is proposed. Unlike the original SC polar decoders, a check node is added to each node of the proposed decoder. Both categories are augmented with a check node, referred to as a frozen check (FC) node or an information check node, depending on the type of the node to be checked. In the modified SC decoding, the messages passed from a node will be modified by multiplying the messages from the check node, so as to enhance the reliability of the propagated messages and to increase the decoding accuracy.The main consideration of our work is how to ensure that all the frozen nodes satisfy the reliability condition. Simulation results are given to show that the proposed decoder achieves better performance than of the original SC decoders, only at the expense of some additional multiplications, which reinforce its effectiveness.

Successive cancellation (SC) decoding;Reliability condition;Check node;Polar codes;

TN911.3

：A

：1002-0802(2016)-06-0683-04

10.3969/j.issn.1002-0802.2016.06.007

2016-02-03;

：2016-05-02 Received date:2016-02-02;Revised date:2016-05-02