具有4階核矩陣極化碼的構(gòu)造和譯碼研究

馬奎明,李文慧,李秀麗

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

香農(nóng)(Shannon)指出:任何一個(gè)通信信道都有確定的信道容量C,如果通信系統(tǒng)所要求的傳輸速率R＜C,則存在一種編碼方法,當(dāng)碼長(zhǎng)N足夠大時(shí),應(yīng)用最大似然譯碼MLD(maximum likelihood decoding),信息的錯(cuò)誤概率可以達(dá)到任意小[1]。這就是著名的有噪信道編碼定理,它奠定了糾錯(cuò)編碼理論的基石。然而它沒有給出如何構(gòu)造實(shí)際上可實(shí)現(xiàn)的、具有上述性能的這類碼。這正是信道編碼要解決的問題。信道編碼的目的是尋找實(shí)際中易于實(shí)現(xiàn)且能達(dá)到有效而可靠通信的編譯碼方法。

在過去的50年里,編譯碼學(xué)家們提出了多種校驗(yàn)糾錯(cuò)碼技術(shù),例如RS碼、卷積碼,Turbo碼等,并廣泛地使用到各種通信系統(tǒng)中。然而,所有的編碼方法都不能達(dá)到香農(nóng)極限(也稱為香農(nóng)邊界)。2008年,在國際信息理論會(huì)議(ISIT)上,土耳其畢爾肯大學(xué)埃達(dá)爾.阿利坎(Erdal ARIKAN)教授首次提出了信道極化的概念。在這一理論的基礎(chǔ)上,他給出了第一種已知能夠被嚴(yán)格證明能夠達(dá)到任意對(duì)稱二進(jìn)制輸入離散無記憶信道(BI-DMC)信道容量的新型編碼方式,并命名為極化碼(polar code)。

極化碼具有明確且簡(jiǎn)單的編碼和譯碼算法,其主要的思想是信道分裂和信道組合,經(jīng)過信道的組合和拆分可將N個(gè)獨(dú)立的,有相同參數(shù)的信道變成N個(gè)具有相關(guān)性且信道容量分布發(fā)生變化的信道,信道總?cè)萘勘３植蛔僛2]。信道容量發(fā)生極化:一部分信道容量增大,一部分信道容量減小。這給信道編碼提供了很好的理論基礎(chǔ)依據(jù)。

不同的核矩陣會(huì)導(dǎo)致不同的性能,而核矩陣階數(shù)越高,所構(gòu)造的極化碼塊長(zhǎng)度也越大,實(shí)現(xiàn)信道極化的程度更徹底,性能更好,因此如何構(gòu)造具有高階核矩陣的極化碼是一個(gè)非常具有研究意義和實(shí)用性的課題。本研究對(duì)于一般情況,以偏序法為例,詳細(xì)闡述了具有4階核矩陣的極化碼構(gòu)造原理和過程,并采用串行相消譯碼器,對(duì)其譯碼過程進(jìn)行了討論。最后,對(duì)極化碼潛在的研究方向、意義和可能遇到的困難點(diǎn)進(jìn)行了總結(jié)。

1 信道極化

1.1 基本原理

極化碼主要研究的是二進(jìn)制離散無記憶信道(B-DMC),也主要對(duì)二進(jìn)制離散無記憶信道說明其基本的極化原理。用X、Y分別代表B-DMC信道W的輸入和輸出符號(hào)集,X∈{0,1},W的傳輸概率是W(y|x),x∈X,y∈Y。當(dāng)輸入符號(hào)X等概率的取{0,1}時(shí),它的對(duì)稱信道容量,可表示為

信道容量是指信道能夠傳輸?shù)淖畲笮畔⒘?它僅由信道自身的性質(zhì)決定,與信源和信宿無關(guān)。在信道編碼領(lǐng)域中,信道容量是一個(gè)非常重要的研究量。從信道容量的定義式中可以看出,只要信道的傳輸概率確定了,那么信道容量也就確定了[2]。

極化碼是根據(jù)子信道的信道容量大小進(jìn)行編碼構(gòu)造的。通過信道變換導(dǎo)致部分子信道信道容量發(fā)生改變,從而容量大的信道傳輸包含信息的信息比特,容量小的信道傳輸發(fā)收端均已知的固定比特,這就是極化思想。它充分利用了信道變換這一特點(diǎn),實(shí)現(xiàn)了信道極化,再根據(jù)信道變換結(jié)構(gòu)的特點(diǎn)構(gòu)造出相應(yīng)的編碼方案,從而得到一種復(fù)雜度低的、質(zhì)量高的信道編碼方案。

1.2 信道的組合和分裂

信道組合就是將B-DMCW遞歸操作組合起來形成W N,其中N＝2n,n≥0。當(dāng)n＝0時(shí),信道復(fù)制一次,W1＝W。當(dāng)n＝1時(shí),復(fù)制的信道進(jìn)行組合得到信道W2,如圖1所示。

圖1 W 2的信道組合Fig.1 Channel combination of W 2

當(dāng)n＝2時(shí),信道進(jìn)行組合得到W4,如圖2所示。

圖2 W 4的信道組合Fig.2 Channel combination of W 4

當(dāng)n＝3時(shí),信道進(jìn)行組合得到W8,如圖3所示。

圖3 W 8的信道組合Fig.3 Channel combination of W 8

以此類推,可以得到n＝n－1時(shí),組合信道W N,如圖4所示。

圖4 W N的信道組合Fig.4 Channel combination of W N

對(duì)輸入序列u進(jìn)行線性變換后可得到編碼序列x,其變換操作可用生成矩陣GN來表示

此時(shí)信道的傳輸概率為

信道分裂是信道組合的逆過程,將組合信道W N再拆成N個(gè)二進(jìn)制輸入信道W(i)N,其對(duì)應(yīng)的轉(zhuǎn)換概率為

2 偏序構(gòu)造法

滿足標(biāo)準(zhǔn)的4階核矩陣不止一個(gè),例如

定義1[5]設(shè)R是集合A上的一個(gè)二元關(guān)系,若R滿足:

(1)自反性:對(duì)任意x∈A,有xRx。

(2)反對(duì)稱性:對(duì)任意x,y∈A,若xRy,且yRx,則x＝y(tǒng)。

(3)傳遞性:對(duì)任意x,y,z∈A,若xRy,且yRz,則x＝y(tǒng)。

則稱R是A上的偏序關(guān)系。

偏序法的研究基于以下結(jié)論:如果j是通過在i的二進(jìn)制擴(kuò)展中將較高的1與較低的0交換而獲得的,則W N(j)隨機(jī)退化為W N(i)。

定義2[5]設(shè)W1,W2分別為相同的二進(jìn)制輸入信道X1→Y1,X2→Y2。如果概率分布p(y1|y2)存在

在m個(gè)字母上的排列是Zm到自身的雙射。在m個(gè)字母上的排列π的置換矩陣是元素在{0,1}中唯一滿足以下條件的m×m矩陣P。

對(duì)所有矢量x,都有

定義3設(shè)π是m個(gè)字母的排列。對(duì)2m個(gè)字母的排列sπ稱為位顯著排列。

其被定義為k→k′的映射,其中k′是l進(jìn)制(l≥2)的整數(shù),表示為

這里k0,k1,…,km－1表示k的l進(jìn)制。

BN表示N個(gè)字母的位反轉(zhuǎn)排列矩陣[6]。Gl為l×l階二進(jìn)制非上三角矩陣。設(shè)GN＝BNG?nl,其中?運(yùn)算是二進(jìn)制域GF(2)上的克羅內(nèi)克積。

設(shè)信道Xi→Yi,i∈ZN是獨(dú)立且均勻分布二進(jìn)制輸入信道W。定義[3]

塊長(zhǎng)度N趨于無限大時(shí),無噪信道的比例接近I(W),全噪信道的比例接近1－I(W)[7]。

推論2記GN＝QGNP－1,其中P是任意N×N階位顯著排列矩陣,Q＝BNPB－1N是一個(gè)置換矩陣。

定義4[8]令i,j∈ZN,sπ是N個(gè)字母上的位顯著排列。如果滿足

表1 i和sπ(i)對(duì)應(yīng)關(guān)系Table 1 i and sπ(i)corresponding relationship

證明在評(píng)估作為ML譯碼[9]在子信道W(i)N上的錯(cuò)誤概率P(W(i)N)時(shí),因?yàn)樾诺繵是對(duì)稱的,則假設(shè)所有零信息都會(huì)被傳輸。設(shè)a(i)N表示傳輸所有的零信息時(shí),logL(i)N(yN－10,0i0)的概率密度函數(shù)。計(jì)算密度的規(guī)則如下:

這里a(0)＝aW是發(fā)送0時(shí),原始信道W的的概率密度函數(shù),*和?是在可變節(jié)點(diǎn)域和校驗(yàn)節(jié)點(diǎn)域上的卷積運(yùn)算。

定理1[10]偏序有3個(gè)重要的性質(zhì):

1)嵌套:碼長(zhǎng)為N,xy意味著在碼長(zhǎng)為4N中,xy也成立。

2)乘法:碼長(zhǎng)為N,xy意味著當(dāng)碼長(zhǎng)為4N,(4x＋i)(4y＋i)成立,i＝0,1,2,3

3)對(duì)稱性:xy和N－1－xN－1－y是塊長(zhǎng)為N的極化碼的一對(duì)

證明 嵌套的性質(zhì)很容易證明。因?yàn)殚L(zhǎng)度為N＝4n的4進(jìn)制(xn－1…x1x0)4表示為長(zhǎng)度為4N的(0xn－1…x1x0)4,這并不影響1和2。

證明乘法性質(zhì),設(shè)N＝4n,x和y的4進(jìn)制表示分別為(xn－1…x1x0)4和(yn－1…y1y0)4。如果x1y,那么存在某些t∈Zn,當(dāng)k∈Zn,t≠k時(shí),xt＜yt且xk＝y(tǒng)k。則4x＝(xn－1…x1x00)4,4y＝(yn－1…y1y00)4。明顯,當(dāng)塊長(zhǎng)為4N時(shí),4x14y。同樣的,當(dāng)塊長(zhǎng)為4N,有4x＋14y＋1,4x＋24y＋2和4x＋34y＋3。對(duì)于2,同樣成立。

3 譯 碼

Arikan采用串行對(duì)消譯碼器對(duì)極化碼進(jìn)行譯碼。將在本節(jié)介紹具有4階核矩陣的極化碼的譯碼原理及過程。

這樣,單個(gè)長(zhǎng)度為N的信道的似然比(LR)[4]的計(jì)算就簡(jiǎn)化為4個(gè)長(zhǎng)度為N/4的信道的似然比的計(jì)算。這個(gè)遞歸可以應(yīng)用到塊長(zhǎng)為1的信道,此時(shí)似然比的形式為

它是可以直接計(jì)算的,那么需要計(jì)算的似然比總數(shù)為N(1＋lgN)。

4 結(jié) 語

從代數(shù)編碼和概率編碼的角度來說,極化碼具備了兩者獨(dú)有的特點(diǎn)。首先,只要給定編碼長(zhǎng)度,極化碼的編譯碼結(jié)構(gòu)就唯一確定了,而且可以通過生成矩陣的形式完成編碼過程,這一點(diǎn)和代數(shù)編碼的常見思維是一致的。其次,極化碼在設(shè)計(jì)時(shí)并沒有考慮最小距離特性,而是利用了信道組合(channel combination)與信道分裂(channel splitting)的過程來選擇具體的編碼方案,而且在譯碼時(shí)也是采用概率算法,這一點(diǎn)比較符合概率編碼的思想。

偏序法是一種簡(jiǎn)單直觀的方法,但由于其本身就是亂序的,因此不能對(duì)信道進(jìn)行完全的排序。其它的構(gòu)造方法也各有優(yōu)劣,例如:密度演化方法可以對(duì)信道進(jìn)行完整的排序,但計(jì)算量大,計(jì)算復(fù)雜;廣義極化權(quán)重法可以對(duì)信道進(jìn)行完全的分類,但是不同類型的信道需要確定不同的β;高斯近似方法可以對(duì)信道進(jìn)行完全排序,并且具有與Arikan啟發(fā)式方法相同的復(fù)雜度,相對(duì)來說性能有所提高,但只適用于高斯白噪聲信道(AWGN)。

除此之外,極化碼想要得到更多應(yīng)用還要克服高速率通信下的時(shí)延和吞吐率[11]問題,這是極化碼在應(yīng)用上最大的問題。