系統(tǒng)極化碼的置信傳播譯碼性能分析*

陳國泰，張朝陽，張 亮，陳平平

系統(tǒng)極化碼的置信傳播譯碼性能分析*

陳國泰1，2，張朝陽**2，張 亮2，陳平平3

（1.福建師范大學(xué)福清分校電信學(xué)院，福州 350300；2.浙江大學(xué)信息與通信工程研究所，杭州 310027；3.福州大學(xué)物理與信息工程學(xué)院，福州 350116）

置信傳播（BP）算法可以為系統(tǒng)極化碼提供軟信息作為判決依據(jù)，也可以為系統(tǒng)極化碼在級聯(lián)迭代譯碼中提供交換軟信息。在詳細(xì)描述基于信道極化結(jié)構(gòu)的置信傳播算法基礎(chǔ)上，比較了系統(tǒng)極化碼在軟信息判決方法和極化編碼判決方法下錯(cuò)誤率性能的差異。仿真結(jié)果表明，軟信息判決方法可以提高系統(tǒng)極化碼的誤比特率，在高信噪比下誤幀率方面也略有提高。

系統(tǒng)極化碼；級聯(lián)碼；置信傳播算法；軟信息判決；譯碼性能

1　引 言

由于Arikan最初提出的極化碼是非系統(tǒng)極化碼（Nonsystematic Polar Codes，NSPC），為了便于實(shí)現(xiàn)類似Turbo碼的并行級聯(lián)碼，2011年Arikan在非系統(tǒng)極化碼的信道極化結(jié)構(gòu)上構(gòu)造出系統(tǒng)極化碼（Systematic Polar Codes，SPC）［6］，并仿真得到比非系統(tǒng)極化碼更好的誤比特率性能。這些作者在分析系統(tǒng)極化碼的錯(cuò)誤率時(shí)，先將信道接收的信息按非系統(tǒng)極化碼進(jìn)行譯碼并判決，再將判決的非系統(tǒng)極化碼字經(jīng)極化編碼獲得系統(tǒng)極化碼的譯碼判決（本文稱之為極化編碼判決方法）。

置信傳播（Belief Propagation，BP）算法在極化碼譯碼時(shí)可以得到軟信息并可用作級聯(lián)碼中迭代譯碼時(shí)的交換信息［7-8］，因此BP算法在極化碼中也是備受關(guān)注的譯碼算法。文獻(xiàn)［9］最先利用BP算法分析極化碼的性能，文獻(xiàn)［10-11］分別分析了基于信道極化結(jié)構(gòu)上的BP算法，這些研究工作是針對非系統(tǒng)極化碼的。本文在［10-11］的基礎(chǔ)上給出了詳細(xì)的BP算法步驟，并用該算法對系統(tǒng)極化碼的譯碼性能進(jìn)行分析，比較了在軟信息判決方法和極化編碼判決方法下的錯(cuò)誤率性能差異。

2　極化碼

N（=2n）個(gè)相互獨(dú)立且具有信道容量I（W）的信道W，經(jīng)過信道合并和信道分離，可以使這N個(gè)獨(dú)立的信道形成新的N個(gè)信道，而這新的N個(gè)信道前后存在依賴關(guān)系，當(dāng)N→∞時(shí)，占總數(shù)比例為I（W）的信道趨于無噪信道（“好”信道），比例為1-I（W）的信道趨于全噪信道（“壞”信道）。

圖1是信道極化的過程。首先右端N個(gè)信道進(jìn)行合并：

式中：G=F?n是F的n次Kronecker冪；u=（u0，u1，…，uN-1）為輸入比特信息；x=（x0，x1，…，xN-1）為極化碼碼字；y=（y0，y1，…，yN-1）為信道接收的信息。信道分離是根據(jù)式（1）所示的信道轉(zhuǎn)移概率實(shí)現(xiàn)：

根據(jù)轉(zhuǎn)移概率可以計(jì)算出Bhattacharyya參數(shù)來評價(jià)分離后的比特信道的“好壞”程度（或其他方法來評價(jià)比特信道的“好壞”程度，可參見文獻(xiàn)［12］及其所列文獻(xiàn)）。

為了構(gòu)造系統(tǒng)極化碼，使用戶傳輸?shù)谋忍匦畔⒆鳛榇a字中的一部分，Arikan在靠近信道這一端（如圖1中的右端）選擇與左端非凍結(jié)比特信道具有相同索引值的比特位用于配置用戶比特信息，并基于圖1的結(jié)構(gòu)推算出右端其他未知的比特（如圖1中帶“？”的比特），這些未知比特與用戶比特信息形成一個(gè)極化碼碼字。關(guān)于系統(tǒng)極化碼的編碼方案，可參見文獻(xiàn)［13］及其文獻(xiàn)列表。

圖1　N=8的信道極化過程Fig.1　Channel polarization and polar encoder with N=8

3　極化碼的置信傳播（BP）算法

Arikan在提出極化碼時(shí)采用一種SC算法作為極化碼的譯碼算法，但是由于SC算法在有限碼長下不能得到理想的極化碼譯碼性能，在文獻(xiàn)［9］中，Arikan采用經(jīng)典BP算法（即基于校驗(yàn)矩陣實(shí)現(xiàn)置信傳播譯碼）對RM碼和非系統(tǒng)極化碼的性能進(jìn)行比較分析。在文獻(xiàn)［10-11］中，研究工作者研究了基于信道極化結(jié)構(gòu)（如圖2）的BP算法（本文稱為極化碼BP算法）。其中，Zhang等人［10］的研究結(jié)果表明了極化碼BP算法在譯碼性能上可優(yōu)于經(jīng)典BP算法。由于系統(tǒng)極化碼和非系統(tǒng)極化碼具有相同的信道極化結(jié)構(gòu)，極化碼BP算法同樣適用于系統(tǒng)極化碼，而且BP算法可以為系統(tǒng)極化碼產(chǎn)生軟信息作為迭代譯碼中的交換信息。本節(jié)在現(xiàn)有研究成果的基礎(chǔ)上，闡述了極化碼BP算法的詳細(xì)步驟，特別是對初值設(shè)置、信息輸出（譯碼判決以及用于信息交換的軟信息）加以說明。

對于長度為N（=2n）的極化碼，根據(jù)信道極化層次從左到右分為層次0至層次n-1（如圖2），極化碼BP算法從信道接收到的信息開始從右向左進(jìn)行置信傳播（如圖2上方所示），再從左向右進(jìn)行置信傳播（如圖2下方所示）形成一次迭代。注意，圖2是在圖1的信道極化結(jié)構(gòu)做了位置置換。為了節(jié)省譯碼的計(jì)算量，在BP算法譯碼之前將凍結(jié)位從左向右推算，將確定性的節(jié)點(diǎn)也作為凍結(jié)位處理（如圖2斜線圓點(diǎn)所示）。

圖2　極化碼的BP算法譯碼流程圖（N=8）Fig.2　Decoding process of BP algorithm for polar codes（N=8）

（3）從左端向右端開始 由R（k）和L（k+1）推算出R（k+1）（k=0，1，…，n-2），對于系統(tǒng)極化碼，根據(jù)硬判決或者軟信息交換的需要決定是否進(jìn)一步推算出R（n），否則可以不需要計(jì)算以節(jié)省運(yùn)算量；系統(tǒng)極化碼的軟信息輸出為R（n）+L（n）；步驟2和3形成一次迭代；

（4）重復(fù)步驟2～3直至滿足迭代停止條件為止，比如達(dá)到最大迭代次數(shù)。

在極化碼BP算法中，置信傳播分為處理單元（Processing Element，PE）內(nèi)部置信傳播和處理單元間置信傳遞。處理單元間置信傳遞實(shí)際上是一個(gè)位置置換的過程，可以參照快速傅里葉變換的蝶形結(jié)構(gòu)中的位置置換（如圖2所示），這里不展開說明。對于處理單元來說，根據(jù)處理單元左端的凍結(jié)情況，可以分為4種情況來處理，如圖3所示。在圖3（c）情況下，由于信息已知而無需進(jìn)行置信傳播，圖3（d）情況是不可能發(fā)生的情況，因?yàn)榻?jīng)過信道極化后，下方的信道必被提升而“好”于上方的信道。

圖3　極化碼BP算法中的4種不同處理單元Fig.3　Four types of processing element in BP algorithm for polar codes

圖3（a）情況的置信傳播分向左傳播和向右傳播。向左置信傳播按式（3）進(jìn)行：

而向右置信傳播的計(jì)算式子如下：

圖3（b）情況由于2j位被凍結(jié)（假定被設(shè)置為0），則向左置信傳播的式子為

而向右傳播的表達(dá)式為

以上式子中，?的具體運(yùn)算如下：

對于圖3（b）情況，由于2j位被凍結(jié)而不需要置信傳播，因此式（5）也可以不進(jìn)行計(jì)算?？梢钥吹剑趫D3（b）情況下置信更新的計(jì)算量很小。

通常，系統(tǒng)極化碼的判決方式為：以非系統(tǒng)極化碼方式進(jìn)行譯碼，得到，通過式（1）得到系統(tǒng)極化碼碼字，從中提取信息位（如N=8時(shí)x3、x5、x6、x7的信息值）作為系統(tǒng)極化碼的判決。在前面所描述的BP算法中，步驟3所得到的軟信息R（n）+ L（n）也可以依據(jù)進(jìn)行硬判決作為系統(tǒng)極化碼的判決結(jié)果。遺憾的是，這種方法得到的判決不一定是極化碼碼字。

當(dāng)系統(tǒng)極化碼作為級聯(lián)子碼［7-8］時(shí)，R（n）將作為外部信息傳遞給其他譯碼模塊。

4　性能仿真與分析

為了比較在BP算法下不同判決方法在錯(cuò)誤率上的性能差異，本節(jié)給出了碼率為1/2、長度為1 024（210）系統(tǒng)極化碼在加性高斯白噪聲（Additive White Gaussian Noisy，AWGN）信道下的仿真結(jié)果。其中，采用二進(jìn)制移相鍵控（BPSK）進(jìn)行調(diào)制｛0→+1，1→-1｝，每個(gè)信噪比點(diǎn)的仿真幀數(shù)為200 000。本節(jié)還提供了非系統(tǒng)極化碼的仿真結(jié)果，考慮了在串行抵消（SC）算法以及串行抵消列表（SC List Decoding，SCL）譯碼算法下的仿真性能。其中在BP算法中最大迭代次數(shù)設(shè)定為60次，在SCL算法中路徑保留條數(shù)L設(shè)定為32。

圖4是在上述仿真參數(shù)下的誤比特率和誤幀率性能。其中，“using NSPC”表示系統(tǒng)極化碼采用極化編碼判決方法，而“using Soft-decision”表示系統(tǒng)極化碼采用軟信息判決方法。另外，在SC算法和SCL算法中，系統(tǒng)極化碼是采用極化編碼判決方法。

圖4顯示，系統(tǒng)極化碼的誤比特率總優(yōu)于非系統(tǒng)極化碼的誤比特率。在BP算法中，利用軟信息判決的系統(tǒng)極化碼的誤比特率略優(yōu)于通過非系統(tǒng)極化碼所得的性能。由于軟信息做出的判決有時(shí)不是一個(gè)極化碼碼字，因此在誤幀率方面會(huì)略差；但在高信噪比時(shí)，軟信息判決的誤幀率略優(yōu)于非系統(tǒng)極化碼做出的判決。

圖4　N=1 024系統(tǒng)極化碼的譯碼性能Fig.4　Performance of systematic polar codes with N=1 024

由圖4中可以看到，BP算法的性能優(yōu)于SC算法，但SCL算法可以獲得比BP算法更好的性能，其原因之一是SCL算法能較好地利用信道極化的特點(diǎn)進(jìn)行譯碼。

5　結(jié)束語

系統(tǒng)碼是構(gòu)造并行級聯(lián)碼的子碼，BP算法可以為系統(tǒng)極化碼提供軟信息以實(shí)現(xiàn)級聯(lián)碼中迭代譯碼的信息交換。本文詳細(xì)描述了基于信道極化結(jié)構(gòu)上的BP算法，并在該算法下比較了在軟信息判決方法和極化編碼判決方法下的系統(tǒng)極化碼譯碼性能。

仿真結(jié)果表明在軟信息判決方法下，系統(tǒng)極化碼可以獲得更好的誤比特率性能。由于BP算法未能較好地利用極化碼的極化特性，在譯碼性能上劣于串行抵消列表譯碼法。如何將極化碼的極化特性融合到BP算法中以提高BP算法在系統(tǒng)極化碼的譯碼性能是值得研究的一個(gè)問題，本文提供的算法步驟可以為深入探討該問題提供有益的參考。

［1］ ARIKAN E.Channel polarization：a method for construc-ting capacity-achieving codes for symmetric binary-input memoryless channels［J］.IEEE Transactions on Information Theory，2009，55（7）：3051-3073.

［2］ TAL I，VARDY A.List decoding of polar codes［J］.IEEE Transactions on Information Theory，2015，61（5）：2213-2226.

［3］ NIU K，CHEN K.CRC-aided decoding of polar codes［J］. IEEE Communications Letters，2012，16（10）：1668-1671.

［4］ 包昕，王達(dá)，劉婉月.利用軟解調(diào)序列的LDPC碼閉集識別方法［J］.電訊技術(shù)，2015，55（1）：55-60.

BAO Xin，WANG Da，LIU Wanyue.A finite set recognition algorithm of LDPC coding by using soft-demodulation sequence［J］.Telecommunication Engineering，2015，55（1）：55-60.（in Chinese）

［5］ 肖創(chuàng)創(chuàng)，郭榮海，李際平，等.直升機(jī)衛(wèi)星通信系統(tǒng)Turbo碼外交織器設(shè)計(jì)與仿真［J］.電訊技術(shù)，2014，54（4）：486-490.

XIAO Chuangchuang，GUO Ronghai，LI Jiping，et al.Design and simulation of Turbo codes'interleaver in helicopter satellite communication system［J］.Telecommunication Engineering，2014，54（4）：486-490.（in Chinese）

［6］ ARIKAN E.Systematic polar coding［J］.IEEE Communications Letters，2011，15（8）：860-862.

［7］ ZHANG Q，LIU A，ZHANG Y，et al.Practical design and decoding of parallel concatenated structure for systematic polar codes［J］.IEEE Transactions on Communications，2016，64（2）：456-466.

［8］ LIU A，WU D，ZHANG Q，et al.Parallel concatenated systematic polar codes［J］.Electronics Letters，2016，52（1）：43-45.

［9］ ARIKAN E.A performance comparison of polar codes and Reed-Muller codes［J］.IEEE Communications Letters，2008，12（6）：447-449.

［10］ ZHANG Y，LIU A，PAN X，et al.A modified belief propagation polar decoder［J］.IEEE Communications Letters，2014，18（7）：1091-1094.

［11］ YUAN B，PARHI K.Architectures for polar BP decoders using folding［C］//Proceedings of 2014 IEEE International Symposium on Circuits and Systems（ISCAS）. Melbourne，Australia：IEEE，2014：205-208.

［12］ VANGALA H，VITERBO E，HONG Y.A comparative study of polar code constructions for the AWGN channel［J］.Mathematics，2015（1）：1-7.

［13］ CHEN G T，ZHANG Z，ZHONG C，et al.A low complexity encoding algorithm for systematic polar codes［J］.IEEE Communications Letters，2016，20（7）：1277-1280.

陳國泰（1975—），男，福建莆田人，2009年于福州大學(xué)獲博士學(xué)位，現(xiàn)為福建師范大學(xué)福清分校電子與信息工程學(xué)院副教授，主要研究方向?yàn)樾旁葱诺谰幋a、無線通信技術(shù)；

CHEN Guotai was born in Putian，F(xiàn)ujian Province，in 1975.He received the Ph.D.degreed from Fuzhou University in 2009.He is now an associate professor.His research concerns source coding，channel coding and wireless communications.

Email：chenguot@163.com

張朝陽（1973—），男，湖北蘄春人，1998年于浙江大學(xué)獲博士學(xué)位，現(xiàn)為浙江大學(xué)教授、信息與通信工程系主任、浙江省信息處理與通信網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室主任、中國電子學(xué)會(huì)信息論分會(huì)副主任委員，主要研究方向?yàn)樾畔⒄撆c編碼理論、信號處理技術(shù)及無線通信與網(wǎng)絡(luò)；

ZHANG Zhaoyang was born in Qichun，Hubei Province，in 1973.He received the Ph.D.degree from Zhejiang University in 1998.He is now a professor，the Chair of the Department of Information and Communication Engineering，and the Director of Zhejiang Provincial Key Laboratory of Information Processing，Communication and Networking.He also serves as the Deputy Director of the Information Theory Society of the Chinese Institute of Electronics（CIE）.His research concerns information theory and coding theory，signal processing techniques，and wireless communications and networking.

Email：ning_ming@zju.edu.cn

張 亮（1988—），男，河南鄭州人，2011年于浙江大學(xué)獲學(xué)士學(xué)位，現(xiàn)為浙江大學(xué)博士研究生，主要研究方向?yàn)闊o線通信與信道編碼；

ZHANG Liang was born in Zhengzhou，Henan Province，in 1988.He received the B.S.degree from Zhejiang University in 2011.He is currently working toward the Ph.D.degree.His research concerns wireless communications and channel coding.

陳平平（1986—），男，福建泉州人，2012年于廈門大學(xué)獲博士學(xué)位，現(xiàn)為福州大學(xué)講師，主要研究方向?yàn)樾诺谰幋a理論、網(wǎng)絡(luò)編碼與無線通信。

CHEN Pingping was born in Quanzhou，F(xiàn)ujian Province，in 1986.He received the Ph.D.degree from Xiamen University in 2012.He is now a lecturer.His research concerns channel coding theory，network coding and wireless communications.

Performance Analysis of Systematic Polar Codes with Belief Propagation Algorithm

CHEN Guotai1，2，ZHANG Zhaoyang2，ZHANG Liang2，CHEN Pingping3
（1.School of Electronics and Information，F(xiàn)uqing Branch of Fujian Normal University，F(xiàn)uzhou 350300，China；
2.Institute of Information and Communication Engineering，Zhejiang University，Hangzhou 310027，China；
3.College of Physics and Information Engineering，F(xiàn)uzhou University，F(xiàn)uzhou 350116，China）

Belief propagation（BP）algorithm can generate soft information for systematic polar codes（SPC）to make decoding decisions and the soft information also can be used as extrinsic information in turbo decoding.This paper first provides a detailed description of BP algorithm based on the structure of channel polarization.Then，it introduces two decision methods，one of which is by exploiting the soft information while the other one is by using polar encoding.The decoding performance under these two methods are compared by simulation，and the simulation results demonstrate that a better bit error rate（BER）performance can be obtained if the soft information is used，while the frame error rate（FER）performance is slightly improved as well in high signal-to-noise ratio（SNR）regime.

systematic polar codes；concatenated codes；belief propagation algorithm；soft decision；decoding performance

The National Basic Research Program of China（973 Program）（2012CB316104）；The National High-tech R&D Program of China（863 Program）（2014AA01A702）；The National Natural Science Foundation of China（No.61371094，61401391，61401099）；The Research Fund of Education Department of Fujian Province（JA12350，JA14339）

**通信作者:ning_ming@zju.edu.cn ning_ming@zju.edu.cn

TN911.22

A

1001-893X（2016）08-0839-05

10.3969/j.issn.1001-893x.2016.08.002

2016-01-08；

2016-05-05

date:2016-01-08；Revised date:2016-05-05

國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（973計(jì)劃）項(xiàng)目（2012CB316104）；國家高技術(shù)研究發(fā)展計(jì)劃（863計(jì)劃）項(xiàng)目（2014AA01A702）；國家自然科學(xué)基金資助項(xiàng)目（61371094，61401391，61401099）；福建省教育廳中青年教育科研項(xiàng)目（JA12350，JA14339）

引用格式:陳國泰，張朝陽，張亮，等.系統(tǒng)極化碼的置信傳播譯碼性能分析［J］.電訊技術(shù)，2016，56（8）：839-843.［CHEN Guotai，ZHANG Zhaoyang，ZHANG Liang，et al.Performance analysis of systematic polar codes with belief propagation algorithm［J］.Telecommunication Engineering，2016，56（8）：839-843.］