基于3×3高維核矩陣的終止極化碼研究

文 豪，曹 陽

重慶理工大學電氣與電子工程學院，重慶400054

極化碼是一種理論上證明在離散無記憶信道中可以達到信道容量的編碼方案，并且其編譯碼復雜度較低[1]。傳統(tǒng)極化碼是基于2×2 核矩陣構造的，其碼長只能為2n，研究表明由l×l(l＞2)生成核矩陣構造的極化碼有望實現更好的糾錯性能[2-3]。文獻[4-5]表明：極化核矩陣要滿足矩陣可逆且置換后非上三角矩陣，同時給出極化碼的漸進性能為PE(N)＜2-lnE(G)，其中E(G) 為矩陣G的極化率。文獻[6]進一步研究不同3×3 極化核矩陣編譯碼的復雜度。文獻[7-8]利用RS 碼、代數幾何編碼作極化核矩陣，進一步提高了極化碼的漸進性能。文獻[9]提出歸一化極化距離的概念，分析不同核矩陣下的極化碼性能，并給出3×3 與4×4 核矩陣構造極化碼的誤塊率（block error rate,BLER）上界。上述文獻表明只要滿足相應的約束條件，高維核矩陣也可作為極化碼的編碼生成矩陣，但會造成更高的計算復雜度和譯碼延遲。

針對極化碼的高計算復雜度和譯碼延遲問題，專家與學者對極化碼的構造進行了以下研究：文獻[1]提出以巴氏參數的方法遞歸構造極化碼，通過提出巴氏參數來衡量比特信道質量；文獻[10]引入密度進化法（density evolution,DE）計算極化后每個比特信道的錯誤傳輸概率，繼而確定其比特信道的可靠性；文獻[11]引入高斯近似法（Gaussian approximation,GA）進而通過估計近似值來降低密度演進方法的計算復雜度。文獻[12]將高斯近似與蒙特卡羅相結合，提出一種基于蒙特卡羅的兩階段極化碼構造方法。文獻[13]將通用偏序應用于大氣弱湍流信道中，提出一種適用于大氣弱湍流信道的低編碼復雜度的構造法。雖然上述極化碼構造方法優(yōu)勢明顯，但對計算復雜度的降低還有一定的提升空間。文獻[14-15]引入終止極化的思想，終止極化是當信道極化到一定程度后部分信道已經足夠好或非常差，于是停止該部分信道繼續(xù)極化的操作，其計算復雜度能減少19.4%～23.7%，但其理論證明僅限于2×2 核矩陣。

本文針對高維核矩陣構造的極化碼以計算復雜度換取糾錯性能的問題，將終止極化思想應用于高維核矩陣構造的極化碼，提出基于3×3 高維核矩陣終止極化碼的構造方案。不同于2×2 核矩陣只有一種形式，3×3 核矩陣具有多種形式，本文首先基于文獻[16]將3×3 核矩陣進行分類，以此表示出不同核矩陣巴氏參數公式的形式；再針對不同3×3 核矩陣構造的終止極化碼性能可能不同的問題，列出滿足信道極化條件的所有3×3 核矩陣及其極化率，以具有最高極化率核矩陣G531進行終止極化碼的構造，理論證明其糾錯性能優(yōu)于傳統(tǒng)完全極化碼；最后在二進制擦除信道（binary erasure channel,BEC）上推導出G531終止極化碼復雜度降低比（complexity reduction ratio,CRR）的上下界，并驗證了其合理性，在保證3×3 高維核矩陣極化碼的誤碼率性能的同時又保證其計算復雜度較低。

1 極化碼構造原理

1.1 信道極化

極化碼是基于信道極化的，信道極化包括信道組合及信道分裂。將信道W復制N次形成N條獨立同分布信道，N條信道經過信道組合形成合成信道WN，再將WN進行信道分裂得到N條具有前后依賴關系的子信道，子信道i表示為WiN。經過以上極化操作，一部分子信道信道容量I(W) 趨為1，這部分信道稱為好信道，表示為GN(W,β)，用來傳輸載有有用信息的比特位；另一部分子信道信道容量趨為0，這部分信道稱為差信道，表示為BN(W,β)，用來傳輸收發(fā)雙發(fā)都已知的凍結位，其中β為正常數，且滿足β＜1/2。X和Y分別表示二元離散無記憶信道的輸入輸出符號集，X={0,1}，若信道為BEC，則Y={0,q,1}，其中q為擦除概率。為了構造極化碼，需要對巴氏參數Z(W) 進行信息位的選取

式中：Z(W) 用來衡量子信道的可靠性，Z(W) 越大表示子信道的可靠性越低。W(y|x) 為信道的轉移概率，且x ∈X,y ∈Y。

二元無記憶對稱（binary memoryless symmetric,BMS）信道，信道W的錯誤概率為

BMS 信道錯誤概率上界與巴氏參數需滿足以下條件[16]

在進行極化碼信息位選取時，選取巴氏參數小或錯誤概率低的好信道進行信息傳輸。好信道集合表示為

當常數β＜1/2 時，BMS 信道中的W滿足

即當碼長足夠大時，信息傳輸速率能達到信道容量，實現無錯傳輸。

1.2 3×3 核矩陣的巴氏參數

3×3 核矩陣的構造形式多樣，列出每個核矩陣對應的巴氏參數公式太過贅述，因此首先對G3進行分類，再給出每類的巴氏參數計算公式。

當G3核矩陣最后一行“1”的個數為1，即m=1 時，滿足信道極化的3×3 核矩陣Gm=1有4 種形式[5]，其巴氏參數為

當m=2 時，滿足信道極化的核矩陣有9 種。這9 種核矩陣的巴氏參數有兩種形式：一種為Gm=2，其巴氏參數公式與Gm=1相同；另一種巴氏參數為

當m=3 時，滿足信道極化的核矩陣Gm=3有4 種[5]，其巴氏參數為

若信道為BEC 信道，則式(14) 等號成立。3×3 核矩陣形式不唯一，其極化率也不同，根據文獻[3]所述，3×3 矩陣核的極化率可表示為

式中：Di為核矩陣的部分距離。Gabc為某一核矩陣，Eabc(G) 為對應核矩陣的極化率，a、b、c分別為核矩陣第1、2、3 列的十進制表示形式。例如極化率為0 的G421=表示為E421(G)。不同核矩陣極化率如表1所示。

表1 3×3 核矩陣極化率Table 1 Polarizability of 3×3 nuclear matrix

2 l=3 終止極化碼

2.1 終止極化原理

信道經過t次極化后，部分信道已經足夠好，這部分信道不需要繼續(xù)進行極化。通過設置終止門限Tg停止該部分信道極化

式中：ER為目標誤幀率，N為極化碼碼長，E(G) 為對應核矩陣極化率。設置Tb=Tg-1 為差信道終止門限，若信道WiN滿足Z(WiN) ≤Tg，則表示信道已經足夠好，不需要繼續(xù)極化，相應的節(jié)點稱為好信道終止節(jié)點；若信道WiN滿足Z(WiN)≥Tb，則表示信道已經足夠差，也不需要繼續(xù)極化，相應的節(jié)點稱為差信道終止節(jié)點。若父節(jié)點為終止節(jié)點，則直接將子節(jié)點錯誤概率值設為父節(jié)點的錯誤概率值，即終止節(jié)點的子節(jié)點為終止節(jié)點。

根據目標誤幀率ER構造終止極化碼，并使用串行抵消（successive cancellation,SC）譯碼，由式（2）可知譯碼后其實際誤幀率滿足

式中：Γ表示好信道集合，碼長為N=3n。

2.2 終止極化碼糾錯性能分析

下面說明式（4）的證明過程。

核矩陣G531為為便于證明，令?i=min{W(y|0),W(y|1)},ηi=max{W(y|0),W(y|1)}。根據式(1) 有因此BEC每個信道的錯誤概率均可計算得到。在不引起誤解的前提下將每個信道的錯誤概率E(WiN)表示為E?；诤司仃嘒531的極化碼在進行極化時，其組合信道與原始信道的轉換關系為(x1,x2,x3)=(u1,u2,u3)G531，表2為其具體的轉化結果。

表2 G531 核矩陣轉換結果Table 2 G531 kernel matrix conversion results

子信道的轉移概率為

不失一般性，設WiN(y1|0) 為?i，WiN(y1|1) 為ηi，則信道的轉移概率可以表示為

或

通過計算與比較得

所以子信道為

其錯誤概率為

經計算，子信道為

則有

子信道的錯誤概率為

定義?F為完全極化碼的比特錯誤概率，可以寫為

終止極化碼的比特錯誤概率?S為

令

則

因為E(WiN)＜0.5，即E＜0.5，所以Δ＞0。因此，式(4) 成立，進一步得出基于3×3核矩陣G531的終止極化碼的糾錯性能要優(yōu)于完全極化碼。如果按照上述推導過程，假設終止極化碼差信道集合表示為(,β)，其含義如同完全極化碼里BN(W,β) 的定義，類似好信道推導過程，同樣可以推導出終止極化碼差信道的糾錯性能要優(yōu)于完全極化碼，即有

2.3 CRR 的上下界分析

對于終止極化碼的好信道，其終止門限為Tg，t層極化后最小巴氏參數為Z3t,t=p3t，p為擦除概率。如圖1所示，當信道經過tg-1 次極化后，比特信道巴氏參數Zi,tg-1均大于Tg，而經過tg次極化后，至少有一個比特信道的巴氏參數小于Tg，即tg次極化后最右邊子節(jié)點v3tg,tg的巴氏參數小于Tg，此時該節(jié)點不需要極化，后續(xù)(n-tg)2n-tg的極化步驟可以跳過。于是終止極化碼好信道的CRR 上界為

圖1 復雜度降低上界Figure 1 Upper bound of complexity reduction

對于任一極化層t,設定閾值B,GB,t表示極化第t層所有比特信道的集合，且任一比特信道的巴氏參數都不超過B，即GB,t={i:Zi,t≤B}，存在定理1。

定理1對于任意閾值B，令tb=若極化層tγ≥tb，其中γ=則終止極化碼好信道復雜度降低比的下界為

證明因為tγ≥tb，所以集合GB,tγ非空。在極化層tγ中，對于GB,tγ中任一個節(jié)點，若至少存在一個子節(jié)點的巴氏參數小于Tg，即GB,tγ中任一個節(jié)點最右邊的子節(jié)點的巴氏參數最大可為B3tγ，且B3tγ≤T，則在極化層tγ+tr，至少有γ3γ=|GB,tγ|個節(jié)點的巴氏參數小于Tg。每個節(jié)點終止極化可跳過的極化步驟數共為

于是總共可跳過γ3tγS步極化步驟，與原極化步驟數比值為γ3tγS/(n3n)，所以復雜度降低比的下界為γ3-tr(n-tr-tγ)/n。

圖2 復雜度降低比的下界Figure 2 Lower bound of complexity reduction

3 仿真與結果

為驗證所提的基于3×3 高維核矩陣的終止極化碼的可行性，本文以下列模擬參數進行實驗仿真。

表3 模擬參數Table 3 Simulation parameters

基于以上的分析與證明，在碼長為N=37的情況下，設定目標誤幀率為10-5，由表1知G531的極化率為0.754，根據式(3) 計算出終止極化碼好信道的終止門限Tg為6.064×10-9。在BEC 信道上構造終止極化碼，運用Matlab 仿真出終止極化碼復雜度降低比與擦除概率p的關系。計算CRR 的上下界，令如圖3為終止極化碼CRR 與其上下界的對比。

圖3 當目標FER 為10-5 時終止極化碼好信道復雜度降低比Figure 3 Terminal polarization code good channel complexity reduction ratio when target FER is 10-5

圖3中UB 表示CRR 上界，LB 表示CRR 下界。仿真表明終止極化碼好信道的CRR可以用其上下界來表征，當目標FER 為10-5時甚至可以實現高達71.43% 的復雜度降低比。隨著p的增大，好信道的CRR 逐漸減小。這是由于p增大，信道極化到足夠好需要極化的次數更多，能夠跳過的極化步驟就更少，所以CRR 減小。差信道終止門限Tb=1-Tg，且差信道對改善FER 不起作用，而給出的目標FER 是相對于全部信道，下面給出全部信道在FER=10-5時終止極化碼的復雜度降低比。圖4中曲線AC 表示終止極化碼全部比特信道的CRR 隨p發(fā)生的改變，GR 表示好比特信道的CRR 隨p發(fā)生的變化。

圖4 當目標FER=10-5 時終止極化碼復雜度降低比Figure 4 Complexity reduction ratio of termination polarization code when target FER=10-5

圖4中曲線AC 能夠反映出終止極化碼全部比特信道的CRR 隨擦除概率p發(fā)生的改變，GR 反映了好比特信道CRR 隨p發(fā)生的變化。仿真表明在目標誤幀率為10-5時，G531核矩陣構造的終止極化碼在p=0.5 附近時其復雜度降低比最小。這是因為雖然差信道對改善譯碼FER 不起作用，但隨著p的增大，達到差信道終止閾值需要的極化操作就越少，可以省去的極化步驟越多，所以全部比特信道的CRR 隨著p的增大呈現圖中AC 線條的走勢。AC的仿真表明，在BEC 信道上終止極化碼可以大大降低編譯碼計算量，從而降低串行抵消譯碼因順序計算而造成的時延。

本文提出的終止極化碼是根據譯碼后需滿足的目標FER，設定相應的終止門限T，減少不必要的極化操作步驟，從而降低編譯碼的計算復雜度。在BEC 信道上設定需要達到的不同目標FER 時，終止極化碼好信道可以實現的復雜度降低比如圖5所示。

圖5 不同目標誤幀率下的復雜度降低比Figure 5 Frame error rate complexity reduction ratio for different targets

仿真表明：隨著擦除概率p的增大，終止極化碼好信道的CRR 逐漸變小，即終止極化碼好信道計算復雜度降低的能力逐漸變小。且隨著要求所需達到的目標誤幀率越小，CRR 也逐漸減小，如圖5所示，在BEC 上擦除概率相同的情況下，目標誤幀率為10-3時的CRR 最大，目標誤幀率為10-5時次之，目標誤幀率為10-7時復雜度降低比最小。因此，在實際應用中，可根據通信鏈路條件和所需達到的通信質量來設定終止閾值，從而設計出滿足不同需求的通信鏈路系統(tǒng)。

為證明3×3 高維核矩陣終止極化碼的誤碼率性能，本文采用3×3 高維核矩陣的終止極化碼與兩種不同構造方法的極化碼（巴氏參數構造的3×3 高維核矩陣極化碼和2×2 核矩陣的終止極化碼）進行SC 譯碼分析對比。如圖6所示，2×2 核矩陣的終止極化碼與3×3 高維核矩陣的終止極化碼采用的碼長分別為（1 024,2 048）、（1 093,2 087），兩種方法的碼長比較接近，以保證其BER 性能對比的公正性。當誤碼率為10-2時，3×3 高維核矩陣極化碼較2×2 核矩陣的終止極化碼有0.3 dB 的性能增益，3×3 高維核矩陣的終止極化碼誤碼率性能明顯優(yōu)于2×2 核矩陣的終止極化碼。同時，傳統(tǒng)構造方法（巴氏參數）的3×3 高維核矩陣極化碼與3×3 高維核矩陣的終止極化碼的譯碼性能幾乎一致。因此，3×3 高維核矩陣的終止極化碼在保證3×3 高維誤碼率性能的同時其計算復雜度也較低。

圖6 高維核矩陣的終止極化碼SC 譯碼性能Figure 6 SC decoding performance of the terminating polarization code of the high-dimensional kernel matrix

4 結 語

本文提出了3×3 極化核構造終止極化碼的方案，并嚴格證明了所提方案的可行性，給出了終止極化碼復雜度降低比的上下界值，定量地分析了終止極化碼對編譯碼計算復雜度的降低比。文中給出的CRR 上下界比較寬松，在之后的工作中可進一步使兩值逼近。最后，對所構造的終止極化碼進行仿真驗證，結果表明，根據所需達到的目標誤幀率不同而設定相應閾值，終止極化碼在不影響性能的情況下能不同程度地降低復雜度。