一種多核極化碼的縮短核矩陣構(gòu)造方法

胡利港，許麗卿，譚曉青，劉 凌，呂善翔

(1.暨南大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，廣東 廣州 510632；2.深圳大學(xué) 計(jì)算機(jī)與軟件學(xué)院，廣東 深圳 518060)

盡管上述穿孔方法能得到更加靈活長度的極化碼，但維度較大時，穿孔過多會導(dǎo)致譯碼復(fù)雜度上升且影響核矩陣的指數(shù)。因此，筆者提出了一種基于列權(quán)重的縮短方法，并針對縮短后的核矩陣可能會出現(xiàn)部分距離超出對應(yīng)上界的情況，提出了一種基于漢明距離的消除算法。首先，通過選取大指數(shù)的因子矩陣進(jìn)行多核構(gòu)造；然后根據(jù)部分距離的特性對得到的極化矩陣進(jìn)行縮短操作。該方法構(gòu)造的5階核矩陣譯碼方法為多核極化碼提供了更加靈活的碼長。實(shí)驗(yàn)結(jié)果表明，該方法能以較低的復(fù)雜度得到任意維度的核矩陣，且得到的一些合數(shù)維核矩陣的指數(shù)高于由克羅內(nèi)克乘積方法得到的指數(shù)。該方法與文獻(xiàn)[15]中的工作相比，能夠解決核矩陣最后一行全為1的情況；與同類型的縮短方法[13-14]相比，得到的核矩陣有著較大的指數(shù)。

1 極化矩陣與部分距離

在極化碼中，擁有極化現(xiàn)象的生成矩陣稱為極化矩陣，但不是所有的矩陣都有極化現(xiàn)象。給定一個l維的矩陣Gl，判斷其是極化矩陣的充要條件是：Gl是非奇異矩陣且經(jīng)過任意列變換不成上三角[16]。

Di=dH(gi，〈gi+1，…，gl〉)，i=1，2，…，l-1 ，

(1)

Dl=dH(gl，0) ，

(2)

其中，Di表示部分距離序列中的第i個元素，〈gi+1，…，gl〉表示括號中向量經(jīng)過線性運(yùn)算得到的所有向量的集合，0表示全零向量，函數(shù)dH表示漢明距離，D(Gl)表示部分距離序列。Gl的指數(shù)[17]定義如下：

(3)

(4)

在核矩陣的構(gòu)造過程中，部分距離不能超過其上界[17]。設(shè)部分距離為Di，有Di≤dmax[l，l-i+1]，其中dmax[l，k]，1≤k≤l，表示長度為l，維度為k的二進(jìn)制線性碼最大的最小漢明距離。

克羅內(nèi)克積多核構(gòu)造就是利用不同維度矩陣或者同維度的不同矩陣通過克羅內(nèi)克乘積運(yùn)算進(jìn)行核矩陣的構(gòu)造。設(shè)vij(1≤j≤n)表示矩陣V的第i行和第j列的元素。V?U如下所示：

(5)

其中，V和U表示克羅內(nèi)克積多核構(gòu)造的因子矩陣。

2 極化碼的核矩陣構(gòu)造

2.1 極化碼的編碼

(6)

其中，GN表示生成矩陣。多核極化碼的生成矩陣由因子矩陣及克羅內(nèi)克乘積的順序所決定，編碼過程在tanner圖上執(zhí)行，如圖1所示。tanner圖有s個階段，表示構(gòu)造GN=Gn1?Gn2?…?Gns需要核矩陣的數(shù)量，每個階段由N/nk個框組成，每個框都是描述核矩陣Gnk的nk×nk塊。圖1中P1稱為連接編碼位和階段1的排列，P2稱為連接階段1和2的排列，LLR(vij)表示i階段的第j個比特的似然比(Log-likelihood Ratio，LLR)的值。

圖1 多核極化碼的tanner圖

2.2 因子矩陣的選擇

在多核極化碼中，因子矩陣的選擇直接關(guān)系到生成矩陣的性能。A和B表示極化矩陣，通過克羅內(nèi)克乘積運(yùn)算得到指數(shù)

(7)

從式(7)中能夠得出

min (E(A)，E(B))≤E(A?B)≤max (E(A)，E(B)) 。

(8)

式(8)表明，因子矩陣A和B的指數(shù)越大，A?B的指數(shù)越大。

例2分別使用矩陣G2，G12和G3，G8構(gòu)造24維矩陣。由文獻(xiàn)[6]知E(G2)=0.5，E(G3)=0.420 620，E(G8)=0.5，E(G12)=0.492 100，因此有

2.3 基于列權(quán)重的縮短方法

基于列權(quán)重的縮短方法首先計(jì)算出矩陣中每一列1的權(quán)重，然后尋找除最后一列以外1的權(quán)重最低的一列。由于最后一行的部分距離較大，刪除最后一行一列會對矩陣的指數(shù)產(chǎn)生較大影響，故將這種情況排除。若1的權(quán)重最少的一列惟一，設(shè)為第i列，則刪除第i行第i列；若1的權(quán)重最少的一列不惟一，設(shè)靠前的一列為第j列，則刪除第j行第j列?；诹袡?quán)重的縮短方法流程圖如圖2所示。

圖2 基于列權(quán)重的縮短方法流程圖

在構(gòu)造核矩陣的過程中，以文獻(xiàn)[6]中的矩陣作為因子矩陣，通過克羅內(nèi)克乘積運(yùn)算得到的矩陣仍然是下三角矩陣。故對極化矩陣Gl，有1≤Hmin≤2和h(l-1)≤2。其中Hmin=mini∈[1，l-1]h(i)，表示1的權(quán)重最少的一列，h(i)表示第i列中1的權(quán)重。

當(dāng)Hmin=h(j)=1時，設(shè)極化矩陣Gl的部分距離序列D(Gl)={D1，D2，…，Dl}。極化矩陣Gl刪除第i行和第i列得到的矩陣設(shè)為G′l-1，部分距離序列為D(G′l-1)={D′1，…，D′l-1}。則有

D′k=Dk+1，j≤k≤l-1 ，

(9)

D′k≥Dk， 1≤k≤j-1 。

(10)

因?yàn)镚l是下三角矩陣，故對角線元素全為1。若Hmin=h(j)=1，則在第j列中，除了第j行的元素均為0。根據(jù)圖2的方法，刪除第j行和第j列。由式(1)知，刪除第j行不影響其后所有行的部分距離。故可得出式(9)。當(dāng)k≤j時，因?yàn)榇a字C′=〈g′k，…，g′l-1〉的漢明距離是通過縮短C=〈gk，…，gl〉得來的，所以有D′k≥dmin(C′)≥dmin(C)=Dk，故可得出式(10)。

當(dāng)Hmin=1時，由式(9)和式(10)可知，縮短后的矩陣的部分距離序列至少不比縮短前差。當(dāng)Hmin=2的時候，該方法會影響到矩陣的部分距離序列，但由于列向量中的1較少，產(chǎn)生的影響較小。

例3對矩陣

(11)

根據(jù)基于列權(quán)重的縮短方法刪除第4行第4列，得到的部分距離序列為D(G′7)={1，2，2，2，3，3，7}，指數(shù)為E(G′7)≈0.456 825。通過窮舉法得到7階最大指數(shù)矩陣的部分距離序列為D(G7)={1，2，2，2，4，4，4}，指數(shù)為E(G7)≈0.457 981。當(dāng)需要的矩陣維度較大時，窮舉不切合實(shí)際。

2.4 基于漢明距離的消除算法

E(G′l)≥E(Gl) ，

(12)

D′k+1>D′k。

(13)

構(gòu)造核矩陣的過程中，基于漢明距離的消除算法能夠解決部分距離超出其對應(yīng)上界的問題。該算法通過將行向量中的1替換成0，以改變行向量的部分距離，得到滿足部分距離上界的行向量。具體描述如下：

③ ifD1≤S1，D2≤S2，…，Dk≤Sk

④ returnD(Gl1?Gl2)=(D1，D2，…，Dk)

⑤ else

⑥ 若Di>Si(1≤i≤k)

⑦ 將gi中的1替換成0，得到g′i，wt(g′i)表示g′i的漢明距離，D′i表示g′i的部分距離，且滿足wt(g′i)=Si

⑧ returnD′(Gl1?Gl2)=(D1，D2，…，D′i，…，Dk)

⑨ end if

根據(jù)式(1)能夠得出Di≤wt(gi)，故D′i≤wt(g′i)=Si。步驟⑦中將1替換成0，存在以下兩種方法：

方法1 從左往右將1替換成0，從而減少行向量gi中1的權(quán)重，得到g′i，且滿足wt(g′i)=Si。

方法2 從右往左將1替換成0(不改變矩陣下三角的性質(zhì))，從而減少行向量gi中1的權(quán)重得到g′i，且滿足wt(g′i)=Si。

不改變矩陣下三角的性質(zhì)即不將矩陣對角線上的1替換成0，目的是為了保證矩陣的極化性質(zhì)。由標(biāo)準(zhǔn)型矩陣的特征以及式(1)可知，方法2對第i行之前的行向量部分距離影響較大，得到的指數(shù)低于方法1。故步驟⑦采用方法1。

例4選取通過縮短方法得到的19維矩陣的前6行：

(14)

2.5 多核極化碼的譯碼

在實(shí)際應(yīng)用中，編碼方法需要一種有效的譯碼方法。類似文獻(xiàn)[20]，多核極化碼的譯碼[5]是通過SC譯碼算法在tanner圖上進(jìn)行的，其譯碼算法由核矩陣的譯碼規(guī)則所確定。

傳統(tǒng)極化碼的G2核描述[1]如下：

(15)

多核極化碼的性能取決于因子矩陣及其乘積順序，在不考慮乘積順序的情況下，因子矩陣本身就顯得尤為重要。不同維度核矩陣的譯碼方法使多核極化碼的碼長有了更多的選擇。圖1中G5核的描述如下：

根據(jù)式(6)，有(u0，u1，u2，u3，u4)×G5=(x0，x1，x2，x3，x4)，其中

(16)

因此，硬決策的更新規(guī)則為x0=u0⊕u1⊕u2⊕u3⊕u4，x1=u1，x2=u2⊕u4，x3=u3⊕u4，x4=u4。由此可得u0=x0⊕x1⊕x2⊕x3⊕x4，u1=x1=u0⊕x0⊕x2⊕x3⊕x4，u2=x2⊕x4=u0⊕u1⊕x0⊕x3，u3=x3⊕x4=u0⊕u1⊕u2⊕x0⊕x4，u4=x4=u2⊕x2=u3⊕x3=u0⊕u1⊕u2⊕u3⊕x0。最后得到消息更新方程式：

ε0=l0⊙l1⊙l2⊙l3⊙l4，

(17)

ε1=l1+(-1)u0(l0⊙l2⊙l3⊙l4) ，

(18)

ε2=l2⊙l4+(-1)u0⊕u1(l0⊙l3) ，

(19)

ε3=l3⊙l4+(-1)u0⊕u1⊕u2(l0⊙l4) ，

(20)

ε4=l4+(-1)u2l2+(-1)u3l3+(-1)u0⊕u1⊕u2⊕u3l0。

(21)

根據(jù)G2核的消息更新方程式有LLR(v10)=LLR(v00)⊙LLR(v05)，LLR(v12)=LLR(v01)⊙LLR(v06)，LLR(v14)=LLR(v02)⊙LLR(v07)，LLR(v16)=LLR(v03)⊙LLR(v08)，LLR(v18)=LLR(v04)⊙LLR(v09)。根據(jù)上式計(jì)算出LLR(v20)，然后對u0進(jìn)行硬判決，最后完成對u0的譯碼。以此類推下去能夠相繼譯出u1至u9。

3 數(shù)值分析

表1比較了由克羅內(nèi)克乘積運(yùn)算和基于列權(quán)重的縮短方法得到的極化矩陣的指數(shù)。其中第2列的“/”表示無法通過克羅內(nèi)克乘積運(yùn)算得到的素?cái)?shù)維矩陣的指數(shù)，第3列中的“/”表示未使用基于列權(quán)重的縮短方法，指數(shù)通過克羅內(nèi)克乘積運(yùn)算得出。從表1中可以看出，克羅內(nèi)克乘積運(yùn)算不能得到的素?cái)?shù)維矩陣，基于列權(quán)重的縮短方法能夠通過縮短高出一維的矩陣得出，例如17，19，23，29，31維矩陣。一些能夠通過克羅內(nèi)克乘積運(yùn)算得到的合數(shù)維矩陣，同樣能夠通過該方法得出，且有更大的指數(shù)，例如21，25，27維矩陣。其中19維矩陣的D6經(jīng)過行變換之后超出了上界3，通過基于漢明距離的消除算法得出最后的指數(shù)。

表1 文獻(xiàn)[4]與文中方法的指數(shù)比較

為了體現(xiàn)基于列權(quán)重的縮短方法的優(yōu)越性，圖3比較了通過不同方法縮短多核極化矩陣得到素?cái)?shù)維極化矩陣(5

圖3 不同縮短方法對多核極化矩陣的指數(shù)比較

圖4 不同縮短方法對窮舉極化矩陣的指數(shù)比較

與傳統(tǒng)的穿刺/縮短方法相比，多核極化碼的譯碼長度較小，譯碼復(fù)雜度更低。通過SC或SCL譯碼算法的穿刺/縮短的極化碼是在其母碼的tanner圖上執(zhí)行的，即譯碼復(fù)雜度取決于母碼長度?；诹袡?quán)重的縮短方法與多核極化碼有著相同的譯碼復(fù)雜度，即譯碼復(fù)雜度低于傳統(tǒng)的穿刺/縮短極化碼。傳統(tǒng)的穿刺/縮短極化碼的譯碼復(fù)雜度為N′lbN′，其中N′表示母碼的長度。因此當(dāng)N=19和N′=32時，需要計(jì)算160個LLRs。基于列權(quán)重的縮短方法在G20=G2?G2?G5的基礎(chǔ)上縮短，僅需計(jì)算60個LLRs。

4 結(jié)束語

筆者提出了一種多核極化碼的縮短核矩陣構(gòu)造方法。該方法在多核構(gòu)造的基礎(chǔ)上，充分考慮了縮短核矩陣過程中1的權(quán)重對核矩陣指數(shù)的影響，得到的核矩陣有著較大指數(shù)，打破了多核極化碼不能構(gòu)造素?cái)?shù)維矩陣的局限性。同時，針對構(gòu)造核矩陣的過程中出現(xiàn)的部分距離超出其對應(yīng)的上界的情況，筆者還提出了一種基于漢明距離的消除算法。該方法構(gòu)造的5階核矩陣譯碼方法使多核極化碼有著更靈活的碼長。實(shí)驗(yàn)表明，基于列權(quán)重的縮短方法能夠彌補(bǔ)克羅內(nèi)克積多核構(gòu)造無法構(gòu)造素?cái)?shù)維核矩陣的缺陷，并且與同類型的縮短方法相比，該方法在指數(shù)和譯碼復(fù)雜度方面具有優(yōu)勢。