李世寶 高 迅 董振威 劉建航 崔學榮

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

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

1 引言

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

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

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

2 極化碼

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

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

3 基于改進高斯近似的極化碼打孔算法

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

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

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

3.2 信道映射

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

3.3 算法流程

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

表1 GAPPC算法

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

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

4 實驗與結(jié)果分析

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

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

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

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

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

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

表2 4種算法的計算復雜度對比

5 結(jié)束語

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