李 純，關(guān)成濤

(西昌衛(wèi)星發(fā)射中心，海南 文昌 571300)

極化碼連續(xù)刪除算法的改進(jìn)*

李 純，關(guān)成濤

(西昌衛(wèi)星發(fā)射中心，海南 文昌 571300)

提出一種改進(jìn)的連續(xù)刪除算法，通過(guò)添加監(jiān)督節(jié)點(diǎn)來(lái)改善譯碼性能。具體的，根據(jù)發(fā)送序列里節(jié)點(diǎn)類(lèi)型的不同，添加固定監(jiān)督節(jié)點(diǎn)和信息監(jiān)督節(jié)點(diǎn)來(lái)加強(qiáng)信息傳輸?shù)目煽慷龋蕴岣咦g碼的精度。仿真結(jié)果表明，與原始的連續(xù)刪除算法相比，改進(jìn)算法通過(guò)增加監(jiān)督節(jié)點(diǎn)譯碼的計(jì)算量，從而提高了其譯碼的性能。

連續(xù)刪除算法；可靠度；監(jiān)督節(jié)點(diǎn)；極化碼

0 引 言

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

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

傳統(tǒng)的SC譯碼算法具有延遲大、精度不高等

缺陷，性能并不理想。改進(jìn)的SC算法通過(guò)添加監(jiān)督節(jié)點(diǎn)的方法來(lái)提高信息傳輸?shù)目煽啃?，改善誤碼性能，并通過(guò)建立可靠條件，對(duì)碼字進(jìn)行信息糾錯(cuò)，一定程度上抑制了突發(fā)錯(cuò)誤的出現(xiàn)。

1 極化碼

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

圖1 N=8的Polar編碼器

2 連續(xù)刪除算法

SC算法是一種串行譯碼方法，其第i次譯碼依賴(lài)于前i-1次的譯碼結(jié)果。譯碼結(jié)束時(shí)，需要更新訪問(wèn)O(Nlog2N)個(gè)節(jié)點(diǎn)，算法的時(shí)間和空間復(fù)雜度均為O(Nlog2N)。整個(gè)譯碼過(guò)程可以分為三個(gè)階段。

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

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

3 改進(jìn)的連續(xù)刪除算法

改進(jìn)的SC譯碼算法基于固定序列，對(duì)于這個(gè)編譯碼序列是已知的，獨(dú)立于整個(gè)譯碼過(guò)程。只要碼率R＜1，Polar譯碼器就會(huì)存在已知的凍結(jié)比特，在SC譯碼無(wú)誤的情況下，這些固定節(jié)點(diǎn)[8]需滿(mǎn)足條件：

根據(jù)式（5）能夠判斷vi節(jié)點(diǎn)是否正確。為了便于表示，下文稱(chēng)式（5）為可靠度條件[9]。

在SC譯碼過(guò)程中，固定節(jié)點(diǎn)消息與信息節(jié)點(diǎn)消息同時(shí)進(jìn)行迭代更新。迭代的同時(shí)，固定節(jié)點(diǎn)消息值同樣會(huì)隨著信道觀測(cè)序列變化。由于高斯噪聲的干擾，固定節(jié)點(diǎn)一定會(huì)出現(xiàn)不滿(mǎn)足上述可靠度條件的情況，從而導(dǎo)致錯(cuò)誤積累，影響后面譯碼的準(zhǔn)確性。因此，本文提出給SC譯碼器中每個(gè)處理節(jié)點(diǎn)增加一個(gè)監(jiān)督節(jié)點(diǎn)，用于修正每個(gè)節(jié)點(diǎn)的可靠性，提高譯碼的準(zhǔn)確性，如圖2所示。

圖2 碼長(zhǎng)為8添加監(jiān)督節(jié)點(diǎn)的Polar譯碼器

按照被發(fā)送序列中存在的不同類(lèi)型節(jié) 點(diǎn)，監(jiān)督節(jié)點(diǎn)分為兩類(lèi)：黑色節(jié)點(diǎn)為固定序列的監(jiān)督節(jié)點(diǎn)，白色節(jié)點(diǎn)為信息序列的監(jiān)督節(jié)點(diǎn)。監(jiān)督節(jié)點(diǎn)自身消息固定且不能進(jìn)行迭代更新。通過(guò)監(jiān)督節(jié)點(diǎn)修正后，奇數(shù)時(shí)，迭代關(guān)系式如式（6）；偶數(shù)時(shí)，迭代關(guān)系式如式（7）。

添加的監(jiān)督節(jié)點(diǎn)用以加強(qiáng)可靠度條件，因此固定序列的監(jiān)督節(jié)點(diǎn)必須滿(mǎn)足條件：

通過(guò)分析，存在關(guān)系式：

圖3 SC譯碼算法路徑搜索過(guò)程

信息監(jiān)督節(jié)點(diǎn)不像固定監(jiān)督節(jié)點(diǎn)，能夠通過(guò)可靠度條件來(lái)檢測(cè)消息節(jié)點(diǎn)消息是否存在錯(cuò)誤，并通過(guò)加強(qiáng)固定序列的可靠性提升信息序列的譯碼能力。所以，在定義信息監(jiān)督節(jié)點(diǎn)時(shí)應(yīng)該滿(mǎn)足：

通過(guò)式（10）可知，信息監(jiān)督節(jié)點(diǎn)沒(méi)有影響信息節(jié)點(diǎn)的似然比，不會(huì)影響信息節(jié)點(diǎn)消息的可靠度。

可見(jiàn)，在整個(gè)串行譯碼過(guò)程中，通過(guò)添加監(jiān)督節(jié)點(diǎn)可加強(qiáng)固定序列的可靠度，從而保持信息序列的可靠度。一定程度上，監(jiān)督節(jié)點(diǎn)的信息糾錯(cuò)能力提升了譯碼性能。

4 仿真結(jié)果

仿真中，物理信道假設(shè)為AWGN信道，采用BPSK調(diào)制方法，碼長(zhǎng)為N=32，碼率R=0.5，設(shè)定一個(gè)信噪比為一次仿真實(shí)驗(yàn)，接收端按照數(shù)據(jù)幀來(lái)統(tǒng)計(jì)誤比特率，每幀數(shù)據(jù)長(zhǎng)度為碼字的信息比特長(zhǎng)度。每次實(shí)驗(yàn)的錯(cuò)誤比特?cái)?shù)不少于100，幀數(shù)少于100 000。為了評(píng)估所提算法的性能，對(duì)原始SC算法進(jìn)行仿真，仿真結(jié)果如圖4所示。

圖4 不同譯碼算法對(duì)比

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

5 結(jié) 語(yǔ)

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

[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] 李斌,王學(xué)東,王繼偉.極化碼原理及應(yīng)用[J].通信

技術(shù),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—），男，碩士，助理工程師，主要研究方向?yàn)樾l(wèi)星通信；

關(guān)成濤（1982—），男，學(xué)士，工程師，主要研究方向?yàn)楝F(xiàn)代通信技術(shù)。

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