一種基于高斯近似的極化碼打孔算法

李世寶 高 迅 董振威 劉建航 崔學(xué)榮

①(中國石油大學(xué)(華東)海洋與空間信息學(xué)院 青島 266580)

②(中國石油大學(xué)(華東)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 青島 266580)

1 引言

極化碼是目前已知唯一的一種被嚴(yán)格證明達(dá)到信道容量的信道編碼方法[1]，但是由于極化碼編碼器是基于克羅內(nèi)克積生成的[1-3]，極化碼的長度總是被限制為 2n，在實(shí)際應(yīng)用中，傳輸碼字的長度不一定都是 2n，經(jīng)常出現(xiàn)可變碼長的實(shí)際需求。打孔算法是構(gòu)造碼長可變和碼率靈活極化碼的重要途徑，近年來獲得了研究者的廣泛關(guān)注。

文獻(xiàn)[4]首次提出極化碼打孔算法，包括隨機(jī)打孔和停止樹打孔兩種基本打孔算法，滿足了碼長可變的要求。文獻(xiàn)[5]提出了一種基于刪除極化矩陣的打孔算法，通過刪除分別對(duì)應(yīng)于打孔位和凍結(jié)位的列和行之后分析簡化的極化矩陣，相對(duì)于隨機(jī)打孔算法可以獲得1.0～5.0 dB的性能增益。文獻(xiàn)[6]提出了準(zhǔn)均勻打孔方案，通過比特倒置排序使得打孔比特準(zhǔn)均勻分布，操作簡單且具有較好的譯碼性能。文獻(xiàn)[7]在文獻(xiàn)[6]的基礎(chǔ)上，提出一種倒置準(zhǔn)均勻打孔方案，在高碼率下獲得更好的性能。文獻(xiàn)[8]基于比特倒置策略和前向序列打孔提出一種新的打孔算法，提升了不同碼率下的打孔性能。文獻(xiàn)[9]提出一種適用于乘積極化碼的打孔算法，性能相對(duì)于先前打孔的乘積極化碼和單極性碼更優(yōu)。文獻(xiàn)[10]提出并驗(yàn)證了使用二進(jìn)制控制可以確定極化碼的打孔比特集合。文獻(xiàn)[11]結(jié)合碼字重復(fù)技術(shù)提出分區(qū)打孔的思路，獲取了一個(gè)更有效的信息比特集合。文獻(xiàn)[12]將里德-所羅門(Reed-Solomon, RS)碼作為極化碼的外碼，提出了一種平均分布打孔算法，構(gòu)造了一種RS-極化碼打孔方案，擴(kuò)展了打孔極化碼的應(yīng)用范圍。文獻(xiàn)[13]提出了一種在打孔之后使用高斯近似(Gaussian Approximation, GA)對(duì)子信道進(jìn)行重構(gòu)的打孔算法，進(jìn)一步提升了打孔算法的性能。上述的打孔算法均需要在打孔之后進(jìn)行重新構(gòu)造，但是重構(gòu)使得算法復(fù)雜度增加。針對(duì)這一問題，文獻(xiàn)[14]提出了一種低復(fù)雜度的打孔(Low-Complexity Puncturing, LCP)算法，在極化碼構(gòu)造一次的情況下使用了準(zhǔn)均勻的打孔策略進(jìn)行打孔。文獻(xiàn)[15]提出了一種最差質(zhì)量打孔(Worst-Quality Puncturing, WQP)算法，在固定信息集合下對(duì)最差質(zhì)量信道進(jìn)行打孔從而獲取更好的打孔性能。

現(xiàn)有算法沒有考慮信道構(gòu)造環(huán)節(jié)對(duì)極化碼打孔性能的影響，限制了極化碼打孔性能的進(jìn)一步提升。本文從信道構(gòu)造出發(fā)，聯(lián)合考慮打孔的特點(diǎn)，提出一種基于改進(jìn)高斯近似的極化碼打孔(Puncturing Polar Code based on Gaussian Approximation, GAPPC)算法。

2 極化碼

高斯近似函數(shù)的近似推導(dǎo)和提出第1次出現(xiàn)在文獻(xiàn)[18]，然后該函數(shù)被應(yīng)用于極化碼的高斯近似構(gòu)造中。現(xiàn)在基于高斯近似構(gòu)造的極化碼算法都基本上沿用了該公式，該高斯近似函數(shù)如式(4)所示

圖1 基礎(chǔ)的蝶形計(jì)算結(jié)構(gòu)

3 基于改進(jìn)高斯近似的極化碼打孔算法

GAPPC算法主要思想是通過改進(jìn)信道構(gòu)造環(huán)節(jié)，提升打孔算法性能。首先引入高斯修正因子，改進(jìn)高斯近似函數(shù)，得到子信道的可靠性排序集合。其次依據(jù)信道容量關(guān)系推導(dǎo)出改進(jìn)的信道映射規(guī)則，對(duì)選出的無能力比特集合進(jìn)行映射得到打孔比特集合，并結(jié)合可靠性排序集合完成打孔極化碼構(gòu)造，最后給出GAPPC具體算法流程。

3.1 改進(jìn)高斯近似函數(shù)

另外，式(6)中的λ0,λ1對(duì)α的求導(dǎo)結(jié)果為

3.2 信道映射

圖2 蝶形計(jì)算中信道容量關(guān)系

3.3 算法流程

將MGA引入構(gòu)造，得到MGA構(gòu)造，將MGA構(gòu)造出的子信道按照升序排序得到的序列集合設(shè)為RMGA。結(jié)合MGA構(gòu)造和推導(dǎo)出的映射規(guī)則，提出GAPPC算法，算法具體如表1所示。

表1 GAPPC算法

在GAPPC算法中，首先對(duì)N長的極化碼進(jìn)行MGA構(gòu)造，按照LLR值升序得出子信道的可靠性序列RMGA。 選出無能力打孔位置集合Q={1,2,...,P}，即uN1的前P比特作為無能力比特，P=N ?M，應(yīng)用Q和改進(jìn)的映射規(guī)則在極化碼編碼結(jié)構(gòu)中迭代，找出打孔比特集合P。根據(jù)RMGA和Q，獲取無能力比特之外的最不可靠的M?K比特，作為剩余凍結(jié)集合QC。根據(jù)QC和Q可 以得到凍結(jié)比特集合AC和信息比特集合A，完成對(duì)打孔極化碼的構(gòu)造。

在完成極化碼構(gòu)造之后，對(duì)N長碼字uN1進(jìn)行編碼得到xN1，并運(yùn)用打孔比特集合P對(duì)編碼后碼字進(jìn)行打孔得到M長傳輸碼字y1M，得到(N,M,K)打孔極化碼，碼率為K/M。在傳輸過程中打孔比特不會(huì)被發(fā)送，在接收端，譯碼器會(huì)將打孔比特的LLR值設(shè)置為0并完成最終譯碼。

4 實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)采用二進(jìn)制相移鍵控調(diào)制信號(hào)源信號(hào)，傳輸信道采用AWGN信道，極化碼譯碼采用串行抵消譯碼算法。實(shí)驗(yàn)中對(duì)比了LCP算法、WQP算法、文獻(xiàn)[10]的打孔算法(BD算法)以及所提GAPPC算法之間的誤碼率(Bit Error Rate, BER)和誤幀率(Frame Error Rate, FER)性能。實(shí)驗(yàn)中使用的極化碼碼長為512和256，使用的碼率為2/3,1/2和1/4。另外，每次實(shí)驗(yàn)的最大模擬幀數(shù)為 107，如果有1000個(gè)錯(cuò)誤幀或共傳輸了 107幀，實(shí)驗(yàn)將會(huì)停止。

圖3展示了碼率為1/2，碼長分別為512和256下，4種極化碼打孔算法的FER和BER性能對(duì)比。圖3(a)顯示了極化碼碼長為512，打孔后碼長為372，碼率為1/2時(shí)，GAPPC算法與LCP算法、WQP算法和BD算法的性能對(duì)比。相對(duì)于WQP算法、LCP算法和BD算法，GAPPC算法的BER性能在SNR為1～4 dB時(shí)均有一定的提升，且BER在10?3可以獲得至少0.3 dB的性能增益。而GAPPC算法的FER性能明顯優(yōu)于其他3種打孔算法，F(xiàn)ER在1 0?2至少獲得0.75 dB的性能增益。圖3(b)顯示了在極化碼碼長為256，打孔后碼長為186，碼率同樣為1/2時(shí)，GAPPC算法的FER和BER性能均明顯優(yōu)于其他3種算法，BER在10?2至少可以獲0.25dB的性能增益，F(xiàn)ER在1 0?2至少可以獲得0.5 dB的性能增益。GAPPC算法在選擇信息集合和凍結(jié)集合時(shí)使用的是基于MGA構(gòu)造的子信道，依據(jù)子信道的LLR值獲得可靠性排序集合，選擇可靠性高的信道傳輸信息比特。這樣構(gòu)造出來的極化碼能降低打孔帶來的信道降級(jí)影響，從而可以獲得更好的性能。由以上分析可知，在不同碼長相同碼率下GAPPC算法具有顯著的性能提升，且極化碼碼長越大，算法性能提升越多。

圖4展示在碼長為512，碼率分別為2/3和1/4時(shí)，4種算法之間的FER和BER性能對(duì)比。圖4(a)顯示了在極化碼碼長為512，打孔后碼長為360，碼率為2/3時(shí)，GAPPC算法與LCP算法、WQP算法和BD算法的性能對(duì)比。在SNR為1～3 dB時(shí)，GAPPC算法與WQP算法的BER相近，明顯優(yōu)于LCP算法和BD算法；而在SNR為4 dB時(shí)，GAPPC算法的BER性能優(yōu)于另外3種算法。而對(duì)于FER性能，GAPPC算法在SNR為1～4 dB時(shí)均具有顯著的性能優(yōu)勢。圖4(b)顯示了在極化碼碼長為512，打孔后碼長為400，碼率為1/4時(shí)，GAPPC算法的BER與FER性能具有顯著的提升。在SNR為4dB時(shí)，GAPPC算法的FER可以達(dá)到 5×10?5，BER達(dá)到6×10?6，相對(duì)于LCP算法、WQP算法和BD算法，GAPPC算法性能提升10倍以上。再結(jié)合圖3(a)的實(shí)驗(yàn)結(jié)果可知，在相同碼長不同碼率下，GAPPC算法均可以獲得顯著性能增益，且碼率越小，性能增益越大。

圖3 不同碼長相同碼率下的4種極化碼打孔算法性能對(duì)比

圖4 相同碼長不同碼率下的4種極化碼打孔算法性能對(duì)比

表2顯示了不同打孔情況下，WQP算法的復(fù)雜度略高于LCP算法的復(fù)雜度，BD算法與LCP算法復(fù)雜度一致，而GAPPC算法的復(fù)雜度在4種算法中最高，其中LCP算法、WQP算法和BD算法都需要GA構(gòu)造和比特倒置排序。由文獻(xiàn)[16]可知，GA構(gòu)造的復(fù)雜度為O(NlgN)。LCP算法中，通過比特倒置排序得到的打孔比特集合會(huì)被預(yù)先設(shè)定，LCP算法只需要進(jìn)行選擇即可獲得打孔比特集合，因此算法復(fù)雜度為O(NlgN)+O(1)。而WQP算法選取S位無能力比特后進(jìn)行比特倒置操作，因此算法復(fù)雜度為O(NlgN)+O(S),S=N ?M。BD算法與LCP算法相似，同樣只需對(duì)預(yù)設(shè)集合進(jìn)行選擇即可獲取打孔比特集合，因此BD算法的復(fù)雜度與LCP算法一致。二者的區(qū)別在于BD算法的預(yù)設(shè)集合是利用二進(jìn)制控制特性[10]排序后經(jīng)過比特倒置操作獲得的，而LCP算法的預(yù)設(shè)集合則是利用自然序與比特倒置操作獲取的。預(yù)設(shè)集合在算法進(jìn)行前完成設(shè)定，因此不計(jì)入算法復(fù)雜度。GAPPC算法的復(fù)雜度主要來自MGA構(gòu)造以及信道映射，MGA構(gòu)造的復(fù)雜度與GA構(gòu)造的復(fù)雜度相同，都是O(NlgN)，而信道映射的復(fù)雜度為O(SlgN)，因此算法的復(fù)雜度為O(NlgN)+O(SlgN)。根據(jù)上述分析可知，相比于其他3種算法，GAPPC算法由于信道映射而具有更高的復(fù)雜性。

表2 4種算法的計(jì)算復(fù)雜度對(duì)比

5 結(jié)束語

為了進(jìn)一步提升極化碼打孔算法的性能，在極化碼打孔算法中聯(lián)合考慮打孔和構(gòu)造，提出高斯修正因子，并推導(dǎo)出最優(yōu)的高斯修正因子和相應(yīng)的MGA，依據(jù)信道容量的關(guān)系推導(dǎo)出改進(jìn)的信道映射規(guī)則，找到打孔比特集合?；贛GA構(gòu)造和改進(jìn)的信道映射規(guī)則，設(shè)計(jì)了GAPPC算法并進(jìn)行相關(guān)的實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果顯示，在不同的碼長和碼率下，與LCP算法、WQP算法和BD算法相比，本文所提GAPPC算法的FER和BER性能均有顯著提升，且碼率越低碼長越大獲得的性能增益越多，但算法的復(fù)雜度會(huì)略有增加。