一種構造低密度奇偶校驗碼校驗矩陣的方法

1、第 15卷 ,第 4期2008年 12月中國傳媒大學學報自然科學版journal o f commun ica t ion un iv er s ity o f ch ina ( sc ience and technolo gy)vo l. 15, no. 4d ec. , 2008一種構造低密度奇偶校驗碼校驗矩陣的方法馮云飛1 ,李建平 1 ,趙力幟 2( 11中國傳媒大學 信息工程學院 ,北京 100024; 21中國航天科技集團公司第五研究院 ,第五一二研究所 ,北京 100086 )摘要 :本文提出一種構造低密度奇偶校驗 (ld pc)碼校驗矩陣的方法 ,該方法通過半隨機產生奇偶校驗矩

2、陣后 ,消去周長為 4的短環(huán)來實現 。仿真結果表明 ,此方法可以有效避免短環(huán)對 ld pc 碼的性能影響 ,使得譯碼性能顯著提 高 ,并且性能隨著碼長的增加而不斷改善 。關鍵詞 :低密度奇偶校驗碼 ;半隨機構造 ;短環(huán) ;碼長 ;對數域內的置信傳播算法中圖分類號 : tn911122 文獻標識碼 : a 文章編號 : 1673 - 4793 ( 2008) 04 - 0052 - 05a m e thod on con struc t ion of ld pc par ity2check m a tr ixfen g yun2fe i1 , l i j ian2p ing1 , zhao l

3、i2zh i2( 11schoo l of info rm a tion enginee ring, comm un ica tion u n ive rsity of ch ina, b e ijing100024, ch ina21no1512 r e sea rch in stitu te, no15 a cadem y, ch ina a e ro sp ace sc ience and techno logy co rpo ra tion, b e ijing 100086 , ch ina)a b stra c t:a m e thod on con struc tion of l

4、d pc pa rity2check m a trix wa s p ropo sed, by removing loop s w ithgirth 4 in a sem i2random p a rity2check m a trix1 sim u la tion re su lts show tha t the p ropo sed m e thod can effec2tive ly avo id the influence on the p e rfo rm ance of ld pc code s exe rted by sho rt loop s, so the decod ing

5、 p e r2fo rm ance is d istinc tive ly imp roved1 fu rthe rmo re,of code length s1key word s: low 2den sity p a rity2check ( ld pc )length s; log2bpthe be tte r p e rfo rm ance can be ob ta ined a s the inc rea singcode s; sem i2random con struc tion; sho rt loop s; code前 ,這方面的研究文獻開始大量地出現 , ld pc 碼已成

6、為編碼領域中的一個研究熱點。理論研究表明 : 在二元輸入 aw gn 信道下 , 采 用碼率為 1 /2 ,碼長為 107 的非規(guī)則 ld pc碼用置信 傳播迭代方法譯碼 ,在錯誤概率為 10 - 6時距離信息 論中的香農限僅差 010045 db 1 ,是目前距離香農限 最近的糾錯碼。大量研究工作證明 , ld pc 碼具有 非常好的特點是 :在許多場合下性能優(yōu)于 tu rbo 碼 ; 具有 較 大 靈 活 性 和 較 低 的 差 錯 平 底 特 性 ( e rro r floo r) ;描述簡單 ,對嚴格的理論分析具有可驗證性 ; 譯碼復雜度低于 tu rbo碼 ,且可實現完全的并行操1

7、引言低密 度 奇 偶 校 驗 ( ld pc, low d en sity pa ritycheck,又稱為 ga llage r碼 ) 碼是 robe rt g1 ga llage r 于 1962年提出的一種性能接近香農 ( shannon)限的 好碼。然而由于各種原因 , 在很長的一段時間里 , ld pc碼并未受到人們的重視 , 直到 1993 年 tu rbo碼提出來以后 , d1j1m ackay, m 1n ea l和 n 1w ibe rg等 人才對 ld pc 碼重新進行了研究 , 他們發(fā)現 ld pc 碼與 tu rbo 一樣具有逼近 shannon 限的性能 。目收稿日期

8、 : 2008 - 06 - 03基金項目 :教育部科學技術重點項目 ( 106042 )作者簡介 :馮云飛 ( 1984 - ) ,男 (漢族 ) ,遼寧沈陽人 ,中國傳媒大學碩士研究生 1e - m a il: p h il cuc1edu1cn作 ,便于硬件實現 ;吞吐量大 ,極具高速譯碼潛力。從k個校驗節(jié)點得到信息。2 ld pc碼的關鍵技術211 校驗矩陣 hld pc碼是一種線性分組碼 , ld pc 碼是由監(jiān)督(校驗 )矩陣 h 定義的 , 不同的 h 矩陣對應不同的 碼字集合 ,所以矩陣 h 的構造是編碼的關鍵。生成 矩陣 g與校驗矩陣 h 相互對應 , 且滿足 ght = 0

9、。原始信息 s = s1 , s2 , 111sm 與生成矩陣 g 相乘就得 到了傳輸碼字 x = x1 , x2 , 111, xn (n m ) 。ld pc 碼可以用稀疏校驗矩陣來描述 , 也就是 說 ld pc 碼的校驗矩陣的矩陣中的元素除一小部分 不為“0 ”外 , 其它絕大多數都為“0 ”, 即“1 ”的密度很低 , 故稱低密度奇偶校驗碼 。通常我們說一個 ( n, j, k )的 ld pc 碼是指其碼長為 n, 其奇偶校驗矩陣每 列包含 j個 1, 其它元素為 0, 即行重為 j; 每行包含 k 個 1, 其它元素為 0, 即列重為 k。并且 j和 k 都遠遠 小于 n, 以滿

10、足校驗矩陣的低密度特性 。校驗矩陣中列和行的個數即 j和 k 為固定值的 ld pc 碼稱為 規(guī)則碼 , 否則稱為非規(guī)則碼。一般來說非規(guī)則的性 能優(yōu)于規(guī)則碼。校驗矩陣 h 有 n 列 m 行 , m 表示碼字的校驗 方程個數 , 且有 2k 個碼字 , 這里 k是消息長度 k = n- m 。碼率 p = k /n = 1 - m /n = 1 - j/ k。由于校驗矩陣的規(guī)律性 , 可以用tanne r圖表現出來 。一組節(jié)點表示 n 個變量比特 (矩陣中的列 ) ,另一組節(jié)點表示 m 個校驗約束 (矩陣中的 行 ) , tanne r圖中的邊根據奇偶校驗方程連接著變量節(jié)點和校驗節(jié)點 。 ta

11、nne r圖中的環(huán)是 指連 接變量節(jié)點和校驗節(jié)點的 , 起始和結束于同一節(jié) 點并且不重復包括同一個節(jié)點的路徑 。環(huán)的長 度也就是邊的數量 ,而 tanne r圖的周長也就是最 小的環(huán)的長度 。212tanne r圖如圖 1 所示的是 ga llage r ( 20 , 3 , 4 )碼的檢驗矩陣。這是一個碼長 n = 20, 碼率 r = 1 / 4, 行重 j = 4,列重 k = 3 的規(guī)則 ld pc 碼 。對于一個 ld pc 碼校 驗矩陣而言 ,每一行對應一個校驗方程 ,每一列對應 碼字中的一個比特。如果分別將列和行作為變量節(jié) 點和校驗節(jié)點這兩類節(jié)點的集合 ,“1 ”代表對應的 兩個

12、節(jié)點存在連通的邊 ,顯然 ,同類節(jié)點之間是不可能有邊的 。這樣校驗矩陣也可以用一個雙向圖 , 即 tanne r圖來表示。圖 1 的 h 矩陣相對應的 tanne r 圖如圖 2所示。圖中變量節(jié)點用圓形表示 ,校驗節(jié) 點用方塊表示。定義一個節(jié)點的度數為與此節(jié)點相 連接的邊的數目。行重量 j表示每個校驗節(jié)點的度數 ,即每個校驗節(jié)點向 j個變量節(jié)點發(fā)送猜想值 ; 列例如 :一個 ld pc 碼( 8 , 2 , 4 ) 的校驗矩陣如下 :01011010001101011100110000111010h =4 8其中 v5 c2 v6 c1 v5 就構成一個長度為 4 的環(huán) 。ld pc 碼校驗矩

13、陣的 tanne r圖的周長 都是偶數 ,而該圖的周長就是 4 ,也是最短的周長 girth。其 tanne r圖如下 :中國傳媒大學學報自然科學版第 15卷54圖 3 ( 8 , 2 , 4 ) ld pc碼的 tanne r圖性和有效性 ,尤其是短環(huán)。環(huán)的長度越小 ,也就是說tanne r的周長越小 ,每次迭代更新的數據的不確定 性減小的越慢 , 防止了 b p 算法收斂到最理想的效 果。如果低密度校驗碼對應的 tanne r圖中存在環(huán) 的話 ,那么由和積算法計算所得的概率并不是真正的后驗概率 (因為迭代過程中獨立性假設不能成立 ) ,因而譯碼并不是最優(yōu)的逐符號最大后驗概率 譯碼。因此 ,

14、環(huán)的存在使得譯碼的最優(yōu)性得不到滿 足。 tanne r圖中長度為 4的環(huán)是很容易從校驗矩陣 直觀地檢測出來 , 以校驗矩陣的非零元素“1 ”為一 個頂點 ,則校驗矩陣中的一個矩形就是一個周長為4 的環(huán) 。但并不是對應 tanne r 圖為無環(huán)時 , ld pc碼的編譯碼性能最優(yōu)。假設無環(huán)情況下 ,當對應碼 的碼率大于 1 /2 時 ,碼的最小距離小于等于 2; 當對 應碼的碼率小于 1 /2 時 ,碼可以由最小距離小于等 于 2 的碼重復某些位生成 ,更進一步 ,記碼率為 r , 則最小距離滿足 dm in 2 /r。因此 ,無環(huán)圖對應的碼 并不是好碼 ,相反環(huán)的存在改善了碼的性能 4 。將奇

15、偶校驗矩陣 h 分解為兩個子矩陣 , h =p dt h h 。相應地 , 將碼字 c分解為 c = p, d , 其中p和d 分別是校驗比特和信息比特 。則pdhc = hp hd ( 311 )= 0其中 , hp 是一個 ( n - k ) ( n - k ) 的方陣 , 稱為校驗位矩陣; hd 是一個 ( n - k ) k 的矩陣 , 稱為信 息位矩陣。hp 是雙對角線形式的上三角子矩陣 , 具有如下形式 , 即100000000110000000011000000001100000000110000000011000000001100000000110000000011p( 312

16、 )h =下面創(chuàng)建 hd 。令 t是一個事先設定的整數 , 且滿足 :( 1 ) n - k可以被 t整除。( 2 ) k t可以被 n - k 整除 。3 一種構造校驗矩陣的方法一個 ld pc碼是從一個隨機產生的奇偶校驗矩陣 h 定義的。為了編碼 , 要將 h 轉換成 hsy s , 即 h 的 等效系統(tǒng)形式 , 可以通過高斯消去法得到。碼率 r= k / n ( k 為信息長度 , n 為編碼長度 ) 時 , h 的大小為 ( n - k ) n。當 n 很大時 , 從存儲和涉及的操作 方面看高斯消去法都是代價高昂的 。另外 , 在編碼器中 , 需要大量存儲器來保存 hsy s , 這個

17、矩陣并不一 定是稀疏的 , 盡管 h 通常被設計為稀疏矩陣。可以運用半隨機技術 , 也就是 , h 僅有一部分是隨機產生 的 ,剩余的部分是確定的 。這種方法可以達到與標準 ld pc編碼方法一樣的性能的 ,而且極大地降低 了編碼的復雜程度 4 。d (將 h 有n - k行 )分成 t個均等的子塊 , 即d1hdh =( 313 )d th在每個子塊 hd i , i = 1, 2, t中 , 每一列創(chuàng)建一個元素 1, 每一行創(chuàng)建 k t / ( n - k ) 個元素 1。式( 313 )中的劃分最大程度增加了編碼中每個比特的 遞歸距離 , 可以直覺感到降低了解碼過程中的相關性 。作為結果

18、 hd 的列權重為 t, 行權重為 k t / ( n -k ) (一個矢量的權重即為其元素中 1的數量 ) 。 基于式 ( 311 ) 和 ( 312 ) , p = pi 可以容易從已知的 d = di 計算出來 , 即 qij ( 0 )( 413 )l ( qij )= logqij ( 1 )p1 = h1 dj , pi = pi - 1 + hij dj (m od2 )dd( 314 )jj ri j ( 0 )與標準 ld pc 碼設計相比 , 上述方法有以下優(yōu)l ( rij )( 414 )= logrij ( 1 )點 :其中= pi , qij ( 0 ) = 1 -

19、pi 。qij ( 1 )式 ( 314 )中的編碼過程比一個完整高斯消去法簡單很多 。( 1 ) 一個隨機 hd 可能是奇異的 , 在實現特定速 率時會造成額外的編程復雜程度; 另外 , 式 ( 311 ) 中 的 hp 總是非奇異的 , 所以新方法可以直接并且準確 地實現任意給定的碼率 。( 2 ) 如果 hd 是稀疏矩陣 (使用較小的 t就能確保這點 ) , 則只需要很少的存儲器來保存 hd 。 在這里我們提出一種為 ld pc 碼的校驗矩陣 h的消除四環(huán)算法。對已經構造為半隨機 ld pc 碼的一個 h 矩陣 , m 行 n 列 ,x記函數 ( x ) = - log tanh ( x

20、 ) = log e+ 1, 并xe2- 1記 aij = sgn (l ( qij ) )為 l ( qij )的符號 ,ij = abs ( qij ) 為l ( q 的絕對值 。ij )具體譯碼算法如下 :( 1 ) 初始化對于等概率輸入的高斯噪聲信道 , 給每個變量 節(jié)點初始化 :2 yi2l ( qij ) =, 為噪聲方差 。( 415 )2( 2 ) 迭代1 ) 校驗點更新第一步 :選取第列 , j = i + 1, i + 2,i列 , i = 1, 2,m 。m ; 再選取第l ( rij ) = ( ij ) (ij )( 416 )b it節(jié)點jirj iirj i式中

21、r 表示與第 j個 check 節(jié)點相連的ij第二步 :把選取的兩列向量對應位置的元素做“與 ”運算 , 記錄下結果向量中 1的位置和總數 s。 第三步 :如果檢測到結果向量中有 1存在 , 比較第 i列和第 j列中 1 的個數 。第四步 :修改 1 個數較多的那一列 l。修改方 法為 :從 l 列的最后一個在結果向量中為 1 的位置 開始反轉 1 為 0。重復此操作 。需要注意的是 , 結 果向量中的第一個 1位不用反轉 。的集合 , ir i表示該集合中不包含第 i個 b it節(jié)點j的其它元素 。2 ) 比特點更新l ( qij ) = l ( ci ) + l ( rji )( 417

22、)jc i i式中 c 表示與第 i個 b it節(jié)點相連的 check 節(jié)點i的集合 , jc i表示該集合中不包含第j個 check 節(jié)j2點的其它元素 , 其中 l ( ci ) =y 。2i( 3 )判決a. 軟判決l (q i ) = l ( ci ) + l ( rij )基于 對數域 的 b e lief p rop aga24( 418 )tion算法ld pc 的譯碼算法有多種 , 本文采用的是基于 對數域的 b e lief p rop aga tion算法 (log - b p) 。該算 法復雜度適中 ,解碼性能也較好 ,比較適合于硬件實 現。該算法的關鍵是迭代計算后驗概率

23、 (a pp) 。定義jc ib. 硬判決1, l (q i ) 00, o therscj =( 419 )( 4 )中止條件計算是否 cht = 0 m od 2。如果是 , 則本次譯碼結束; 若不是 , 判斷是否達到最大迭代次數 lm ax , 如 果已達到最大迭代次數 , 結束譯碼 , 以最后的結果作為輸出; 若沒有達到最大迭代次數 , 轉入步驟 ( 2 ) 。 1 pi = p ( ci = 1 | yi ) =( 411 )1 + e21y i /2p ( ci = 0 | yi ) 1 - pil ( ci ) = log( 412 )= logp ( ci = 1 | yi )

24、pi式中 pi 表示接收為 yi 時發(fā)送為 1的概率 , qij為比特 bi 的更新值 , 傳遞給校驗 cj , rji為校驗 cj 的更新5 仿真中國傳媒大學學報自然科學版第 15卷56(ld pc )碼的校驗矩陣方法的性能 ,本節(jié)通過 ma t2lab 編程進行仿真 。仿真中采用基帶 b psk調制方 式 ,通過二進制加性高斯白噪聲信道 (aw gn )傳輸 , 在接收端用對數域內的置信傳播算法 (log - b e liefp rop aga tion a lgo rithm )進行迭代譯碼 ,最大迭代次數 為 10。該仿真 ,對采用本文提出的消 4 環(huán)前后的 ld pc碼的譯碼性能的進

25、行了比較 。仿真中采用碼長為256 ,校驗矩陣 h 為半隨機矩陣 , 列、行重量分別有3、6。從圖 4 可以看出 ,在高斯白噪聲信道下 ,僅使 用 ( 256 , 3 , 6 )短碼 ,在采用本文提出的消 ld pc的校驗矩陣的 4 環(huán)算法后 , 譯碼性能上有明顯的提高 。在誤碼率為 10 - 4 處 , 采用消 4 環(huán)算法后 , 可獲得大 約有 015 db 的編碼增益。圖 5 相同碼率 r = 2 /5,碼長分別為 16200 和 64800 的 ld pc碼的性能比較的實現步驟 。為了分析采用消 4 環(huán)算法后的 ld pc 碼在譯碼性能方面提高的效果 , 我們進行了仿真。 仿真結果表明 ,在高斯白噪聲信道下 ,使用 ( 256 , 3 ,6 )短碼 ,在誤碼率為 10 - 4處 ,采用消 4 環(huán)算法后 ,可 獲得大約有 015 db 的編碼增益 ,可見譯碼性能有明 顯的提高。之后對相同碼率不同碼長的 ld pc 碼進 行性能仿真 ,得出結論 :碼長是影響 ld pc 碼