F 3 上極化碼的核矩陣

李文慧, 高俊杰, 李秀麗

(青島科技大學 數理學院,山東 青島 266061)

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

1 信道極化

設W是一個q進制離散無記憶信道:X→Y,其中X=Fq。

定義1q進制輸入信道W:X→Y對稱容量為

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

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

設G是取值于X的l×l矩陣?？紤]一個在域上是均勻分布的隨機l維向量,令=,其中乘法運算是在域Fq上進行的[7]。同樣表示信道W的l次副本的輸入所對應的輸出。和之間的信道轉移概率為

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

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

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

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

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

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

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

2 F 3 上核矩陣的選取

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

巴氏參數為

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

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

其中i≥0。

根據文獻[3,5],對于核矩陣G的選擇有多種。顯然不同的核矩陣會導致不同的性能,因此在有限的塊長度條件下找到一種標準來設計一個好的核矩陣G是非常有必要的。以下討論如何在所有可能的核矩陣中選擇最優的核矩陣。

2.1 極化速率

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

2.2 的可靠性

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

定理2對任意的下三角核矩陣G,如果最后一行的非零元素數是m,則

證明首先考慮m=3的情況。xi是u0,u1,u2的函數,用gi(u0,u1,u2)或gi(xi)表示W(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。經過變換,得到

如果一個變量x在[0,1]中取值,與函數y=x和y=x2相比,y=x3的值最小。受此啟發,因為所有的的取值范圍為[0,1],選擇最后一行有3個非零元素的矩陣G,對于每次遞歸,至少可以確保的會盡可能地小。這也是解決一些優化問題常用的方法。由此,可以得到最優核矩陣的選取標準為

1) 矩陣的標準形式為下三角矩陣。

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

矩陣G的標準形式為,因為的最后一行均為1,所以矩陣G滿足上述兩條可以使得三進制輸入信道極化的標準。

3 結 語

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

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