李文慧, 高俊杰, 李秀麗

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

極化碼是近年來備受關(guān)注的一種糾錯(cuò)碼,它在理論上可用于任何具有低復(fù)雜度的對(duì)稱二進(jìn)制離散無記憶信道[1]。極化碼是目前唯一被嚴(yán)格證明能夠達(dá)到信道容量的編碼方式,這使得極化碼與其他傳統(tǒng)編碼相比有較為明顯的區(qū)別,可用于幫助證明許多理論問題,且極化碼在無線通信中有廣泛應(yīng)用。文獻(xiàn)[1]中的二進(jìn)制極化碼構(gòu)造基于以下結(jié)論:設(shè),對(duì)長(zhǎng)度為N=2n比特的碼塊應(yīng)用變換F?n(其中?n表示n次克羅內(nèi)克冪),并通過BDMC信道的獨(dú)立副本發(fā)送輸出。隨著n逐漸增大,單個(gè)比特對(duì)應(yīng)的信道開始發(fā)生極化現(xiàn)象,一部分接近無噪聲信道,另一部分接近全噪信道。KORADA 等[2]證明了極化是一種普遍現(xiàn)象,并不局限于特定的變換F?n。他們還考慮了G?n形式的變換,其中G是一個(gè)l×l矩陣,l≥3,并給出了B-DMC信道下該矩陣G能夠極化的充要條,證明了任意列排列不是上三角的l×l二進(jìn)制可逆矩陣都可以產(chǎn)生極化。MORI等[3]發(fā)現(xiàn)在域Fq上也有同樣的結(jié)論。在文獻(xiàn)[4]中,學(xué)者們研究了塊長(zhǎng)度為N=3n的二進(jìn)制極化碼核矩陣。本工作主要研究域F3上塊長(zhǎng)為N=3n的三進(jìn)制極化碼核矩陣。與F2上的同階核矩陣相比,它產(chǎn)生的極化碼具有更好的可靠性和極化率。本研究對(duì)三進(jìn)制三階核矩陣的構(gòu)造原理及滿足極化要求的核矩陣選取標(biāo)準(zhǔn)進(jìn)行了闡述,給出了一種核矩陣的構(gòu)造方法和最優(yōu)核矩陣的選取標(biāo)準(zhǔn),為高階核矩陣的構(gòu)造提供了研究思路。

1 信道極化

設(shè)W是一個(gè)q進(jìn)制離散無記憶信道:X→Y,其中X=Fq。

定義1q進(jìn)制輸入信道W:X→Y對(duì)稱容量為

定義2信道W的巴特查里亞參數(shù)(巴氏參數(shù))為

這些參數(shù)分別用作速率和可靠性的度量[5]。I(W)是在信道W間進(jìn)行可靠傳輸?shù)淖罡咚俾?。Z(W)是當(dāng)信道W只被用于傳輸Fq中某一個(gè)元素時(shí)最大似然決策錯(cuò)誤概率的上確界。上面的公式中使用底數(shù)為q的對(duì)數(shù),因此I(W)和Z(W)的取值范圍均為[0,1]。當(dāng)W為對(duì)稱信道時(shí),對(duì)稱容量I(W)等于Shannon容量[6]。

設(shè)G是取值于X的l×l矩陣。考慮一個(gè)在域上是均勻分布的隨機(jī)l維向量,令=,其中乘法運(yùn)算是在域Fq上進(jìn)行的[7]。同樣表示信道W的l次副本的輸入所對(duì)應(yīng)的輸出。和之間的信道轉(zhuǎn)移概率為

其中i=0,1,…,l-1。

W(i):X→Yl×Xi-1是輸入ui,輸出(,的信道,轉(zhuǎn)移概率為

i=0,1,…,l-1。

設(shè){Bi}(i=0,1,…)是一個(gè)獨(dú)立隨機(jī)變量,即對(duì)于任意k=0,…,l-1,Bi=k的概率為。存在一個(gè)隨機(jī)量I∞,當(dāng)n→∞時(shí),絕對(duì)收斂于I∞。在映射G→VG下W(i)的統(tǒng)計(jì)性質(zhì)是不變的,其中V是l×l滿秩上三角矩陣。此外,矩陣G的列排列也不會(huì)改變W(i)的統(tǒng)計(jì)性質(zhì)。任意滿秩矩陣都可以分解成VLP的形式,其中V、L和P分別是上三角、下三角和置換矩陣。這種與可逆矩陣G等價(jià)的主對(duì)角線元素為單位的下三角矩陣被稱為是G的標(biāo)準(zhǔn)形式,記為。在文獻(xiàn)[3]中,作者證明了任意非對(duì)角下三角l×l矩陣,其P(I∞∈{0 ,1})=1。因此,任意列排列不是上三角的l×l三進(jìn)制可逆矩陣都可以使信道發(fā)生極化。這些可以極化信道的l×l矩陣稱為核矩陣。

定義3[5]給定域Fq上的一個(gè)l×l矩陣G=,Di(i=1,2,…,1)的定義為

其中＜gi+1,…,gl＞是由gi+1,…,gl生成的空間;dH(…,…)是指向量間的漢明距離。

定理1[8]設(shè)W是一個(gè)q進(jìn)制輸入離散無記憶信道。設(shè)P(I∞∈ {0 ,1})=1。對(duì)于β＜,

2 F 3 上核矩陣的選取

在以下的討論中,假設(shè)q=3。W:X={0,1,2}→Y是一個(gè)對(duì)稱三進(jìn)制輸入離散無記憶信道。

巴氏參數(shù)為

G是一個(gè)3×3核矩陣,那么3個(gè)三進(jìn)制輸入信道W(i):{0,1,2}→Y3×{0,1,2}i(i=0,1,2)的轉(zhuǎn)移概率如下:

對(duì)于任意給定的T-DMCW,可將(W,W,W)→(W(0),W(1),W(2))寫成以突顯字符串長(zhǎng)度。更一般地說

其中i≥0。

根據(jù)文獻(xiàn)[3,5],對(duì)于核矩陣G的選擇有多種。顯然不同的核矩陣會(huì)導(dǎo)致不同的性能,因此在有限的塊長(zhǎng)度條件下找到一種標(biāo)準(zhǔn)來設(shè)計(jì)一個(gè)好的核矩陣G是非常有必要的。以下討論如何在所有可能的核矩陣中選擇最優(yōu)的核矩陣。

2.1 極化速率

根據(jù)文獻(xiàn)[5],如果矩陣G的指數(shù)更大,則可以更快地完成信道極化,從而獲得更好的性能。因此,如果想找到更好的塊長(zhǎng)度為N=3n的極化碼,我們需要找到盡可能大的指數(shù)的矩陣。對(duì)于3×3核矩陣,指數(shù)最大可能為。

2.2 的可靠性

Z描述的是的可靠性,且每一個(gè)信息位僅由其對(duì)應(yīng)的信道傳輸,因此Z直接決定了性能。核矩陣G決定了的遞歸公式,這啟示盡可能選擇一個(gè)可以提高的可靠性的矩陣。

定理2對(duì)任意的下三角核矩陣G,如果最后一行的非零元素?cái)?shù)是m,則

證明首先考慮m=3的情況。xi是u0,u1,u2的函數(shù),用gi(u0,u1,u2)或gi(xi)表示W(wǎng)(yi|xi),i=0,1,2。那么

因此

u0和g31(非零)取任意值,那么{u0,u0+g31},{u0,u0+2g31}和{u0+g31,u0+2g31}分別取值于{0,1},{0,2}和{1,2};u1和g32(非零)取任意值,那么{u1,u1+g32},{u1,u1+2g32}和{u1+g32,u1+2g32}分別取值于{0,1},{0,2}和{1,2};u0≠u0+g31,u0≠u0+2g31,u0+g31≠u0+2g31;u1≠u1+g32,u1≠u1+2g32,u1+g32≠u1+2g32。經(jīng)過變換,得到

如果一個(gè)變量x在[0,1]中取值,與函數(shù)y=x和y=x2相比,y=x3的值最小。受此啟發(fā),因?yàn)樗械牡娜≈捣秶鸀閇0,1],選擇最后一行有3個(gè)非零元素的矩陣G,對(duì)于每次遞歸,至少可以確保的會(huì)盡可能地小。這也是解決一些優(yōu)化問題常用的方法。由此,可以得到最優(yōu)核矩陣的選取標(biāo)準(zhǔn)為

1) 矩陣的標(biāo)準(zhǔn)形式為下三角矩陣。

2) 最后一行均為非0元素。

矩陣G的標(biāo)準(zhǔn)形式為,因?yàn)榈淖詈笠恍芯鶠?,所以矩陣G滿足上述兩條可以使得三進(jìn)制輸入信道極化的標(biāo)準(zhǔn)。

3 結(jié) 語

極化碼為信道編碼理論研究開辟了新的方向,初步的研究表明,信道極化是一種普遍現(xiàn)象。極化碼對(duì)于信源壓縮、信道編碼、多址接入等典型的通信問題都是漸進(jìn)最優(yōu)的解決方案。但信道極化碼的研究還有待深入,有限碼長(zhǎng)下極化碼的性能還未達(dá)到Tubro碼、LDPC碼的性能。

文中所給出的3階核矩陣的指數(shù)達(dá)到了最大。對(duì)于q元域上的高階(大于3階)核矩陣的探討是一個(gè)有意義的研究課題,但計(jì)算向量間漢明距離時(shí)難度加大,核矩陣指數(shù)計(jì)算復(fù)雜度高。對(duì)高階核矩陣的構(gòu)造與選取、極化碼的編碼構(gòu)造與性能優(yōu)化進(jìn)行深入地研究,豐富其理論基礎(chǔ),對(duì)未來通信技術(shù)的發(fā)展具有重要的意義。