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

馬奎明，李秀麗

(青島科技大學(xué) 數(shù)理學(xué)院，山東 青島 266061)

極化碼是近年來(lái)備受關(guān)注的一種糾錯(cuò)碼，是通過(guò)信道極化(channel polarization)，在編碼側(cè)使子信道呈現(xiàn)出不同的可靠性，當(dāng)碼長(zhǎng)N持續(xù)增長(zhǎng)時(shí)，部分信道將趨向于容量近于1的完美信道，另一部分信道趨向于容量接近于0的純?cè)胄诺赖男滦途幋a方式。

極化碼在理論上可用于任何具有低復(fù)雜度[1]的對(duì)稱(chēng)二進(jìn)制離散無(wú)記憶信道，是目前唯一被嚴(yán)格證明能夠達(dá)到信道容量的編碼方式，與其他傳統(tǒng)編碼有較為明顯的區(qū)別，可用于證明許多理論問(wèn)題， 在無(wú)線通信中有廣泛應(yīng)用。

1 預(yù)備知識(shí)

記W:X→Y表示一般的二進(jìn)制輸入離散無(wú)記憶信道，其中X表示輸入字符的集合，Y表示輸出字符的集合。

定義1：如果存在一個(gè)置換π:Y→Y，對(duì)所有的y∈Y都有π(y)=π-1(y)且W(y|1)=W(π(y)|0)，那么稱(chēng)這個(gè)二進(jìn)制輸入離散無(wú)記憶信道(B-DMC)W:{0,1}→Y是對(duì)稱(chēng)的。如果對(duì)任意y∈Y有W(y|0)W(y|1)=0或W(y|0)=W(y|1)，那么稱(chēng)其為二進(jìn)制刪除信道(BEC)[5]。

對(duì)極化碼的研究，還需要兩個(gè)重要的信道參數(shù)：

對(duì)稱(chēng)容量：

巴氏參數(shù)：

這些參數(shù)分別被用作信道傳輸速率和傳輸可靠性的度量。I(W)是等概率情況下在信道W之間進(jìn)行可靠通信的最高速率。Z(W)是信道W僅用于傳輸0或1時(shí)的最大似然決策下錯(cuò)誤概率的上界。在上述公式中，均使用以2為底的對(duì)數(shù)，因此I(W)和Z(W)都取值于[0,1]。

其中，i=0,1,…,-1，且令Z(i)表示巴氏參數(shù)：

定義3[3]：對(duì)任意0

E(G)也稱(chēng)為矩陣G的指數(shù)。

指數(shù)的定義為極化碼提供了在串行相消譯碼策略[7]下一個(gè)有意義的性能度量。事實(shí)上，指數(shù)與信道無(wú)關(guān)。指數(shù)E(G)也可以表示為W的距離的函數(shù)。

定義4[3]給定×階矩陣偏序距離Di(i=1,2,…,)為

其中dH(…,…)表示漢明距離；是由gi+1,…,g生成的空間。

2 核矩陣的選擇

在這一部分，主要討論四階核矩陣，換句話說(shuō)極化碼塊長(zhǎng)度為N=4n。

令W:{0,1}→Y是二進(jìn)制輸入離散無(wú)記憶信道，G是一個(gè)4×4階核矩陣。給定4個(gè)二進(jìn)制輸入信道W(i):{0,1}→Y4×{0,1}i(i=0,1,2,3)如下：

Arikan[1]的研究表明對(duì)核矩陣G會(huì)有多種選擇。顯然，不同的核矩陣會(huì)導(dǎo)致不同的性能，因此有必要尋找一種策略來(lái)設(shè)計(jì)一個(gè)適合的有限塊長(zhǎng)度的G。對(duì)于任意的核矩陣都有一些通用的策略[8]，我們首先討論如何從所有可能的核矩陣中選擇一個(gè)好的。

2.1 極化率

Arikan[1]認(rèn)為，矩陣G的指數(shù)越大，實(shí)現(xiàn)信道極化的程度越徹底，性能越好。因此，如果想找到塊長(zhǎng)度為N=4n時(shí)的最佳極化碼，那么就需要找到指數(shù)最大的核矩陣。根據(jù)Arikan做的工作，當(dāng)≤10時(shí)，不存在指數(shù)大于的矩陣。事實(shí)上，我們可以找到指數(shù)等于的四階核矩陣。

證明首先考慮m=4的情況，這意味著最后一行的所有項(xiàng)都是1。xi是u0,u1,u2,u3的函數(shù)，因此用gi((u0,u1,u2,u3)G)[9]來(lái)表示W(wǎng)(yi|xi),i=0,1,2,3。那么

根據(jù)遞歸結(jié)構(gòu)，有

這里⊕是模2的和。這個(gè)方程可以通過(guò)一個(gè)簡(jiǎn)單的例子來(lái)驗(yàn)證，例如N=4。

證明：

顯然成立，證畢。

根據(jù)遞歸結(jié)構(gòu)，有

如果W是BEC，等式成立。

證明：首先，給出對(duì)遞歸信道表達(dá)式有用的方程。

下面，使用不等式

當(dāng)abcd=0或a=d或b=c時(shí)，等號(hào)成立。

=4Z(W)2-4Z(W)3+Z(W)4,

+(β0δ0+β1δ1+β1δ0+β0δ1)

+(β0δ0+β1δ1+β1δ0+β0δ1)

=4Z(W)-2Z(W)2。

3 結(jié)語(yǔ)

Arikan引入的核矩陣G2是唯一的，然而塊長(zhǎng)度為N=4n的極化碼對(duì)G4有多種選擇，因此其提供了很大的靈活性，但問(wèn)題是如何找到一種策略來(lái)設(shè)計(jì)一個(gè)好的G4。當(dāng)然，對(duì)齊為任意整數(shù)，且≥3所有G，都具有這樣的特性。但是隨著的增大，這個(gè)問(wèn)題就越來(lái)越難解決了。因此我們關(guān)注最簡(jiǎn)單的情況，并提出從所有可能的G4中選擇一個(gè)好的G4的策略。該策略基于的遞歸公式，因?yàn)檫@些公式直接決定了性能。然而，有些遞歸公式只提供了上限，而不是確切的值，如果信道W不是BEC，那么我們所做的只是一些近似的分析。