一種構(gòu)造低密度奇偶校驗(yàn)碼校驗(yàn)矩陣的方法

1、第 15卷 ,第 4期2008年 12月中國(guó)傳媒大學(xué)學(xué)報(bào)自然科學(xué)版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一種構(gòu)造低密度奇偶校驗(yàn)碼校驗(yàn)矩陣的方法馮云飛1 ,李建平 1 ,趙力幟 2( 11中國(guó)傳媒大學(xué) 信息工程學(xué)院 ,北京 100024; 21中國(guó)航天科技集團(tuán)公司第五研究院 ,第五一二研究所 ,北京 100086 )摘要 :本文提出一種構(gòu)造低密度奇偶校驗(yàn) (ld pc)碼校驗(yàn)矩陣的方法 ,該方法通過(guò)半隨機(jī)產(chǎn)生奇偶校驗(yàn)矩

2、陣后 ,消去周長(zhǎng)為 4的短環(huán)來(lái)實(shí)現(xiàn) 。仿真結(jié)果表明 ,此方法可以有效避免短環(huán)對(duì) ld pc 碼的性能影響 ,使得譯碼性能顯著提 高 ,并且性能隨著碼長(zhǎng)的增加而不斷改善 。關(guān)鍵詞 :低密度奇偶校驗(yàn)碼 ;半隨機(jī)構(gòu)造 ;短環(huán) ;碼長(zhǎng) ;對(duì)數(shù)域內(nèi)的置信傳播算法中圖分類(lèi)號(hào) : tn911122 文獻(xiàn)標(biāo)識(shí)碼 : a 文章編號(hào) : 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前 ,這方面的研究文獻(xiàn)開(kāi)始大量地出現(xiàn) , ld pc 碼已成

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、 (a pp) 。定義jc ib. 硬判決1, l (q i ) 00, o therscj =( 419 )( 4 )中止條件計(jì)算是否 cht = 0 m od 2。如果是 , 則本次譯碼結(jié)束; 若不是 , 判斷是否達(dá)到最大迭代次數(shù) lm ax , 如 果已達(dá)到最大迭代次數(shù) , 結(jié)束譯碼 , 以最后的結(jié)果作為輸出; 若沒(méi)有達(dá)到最大迭代次數(shù) , 轉(zhuǎn)入步驟 ( 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 時(shí)發(fā)送為 1的概率 , qij為比特 bi 的更新值 , 傳遞給校驗(yàn) cj , rji為校驗(yàn) cj 的更新5 仿真中國(guó)傳媒大學(xué)學(xué)報(bào)自然科學(xué)版第 15卷56(ld pc )碼的校驗(yàn)矩陣方法的性能 ,本節(jié)通過(guò) ma t2lab 編程進(jìn)行仿真 。仿真中采用基帶 b psk調(diào)制方 式 ,通過(guò)二進(jìn)制加性高斯白噪聲信道 (aw gn )傳輸 , 在接收端用對(duì)數(shù)域內(nèi)的置信傳播算法 (log - b e liefp rop aga tion a lgo rithm )進(jìn)行迭代譯碼 ,最大迭代次數(shù) 為 10。該仿真 ,對(duì)采用本文提出的消 4 環(huán)前后的 ld pc碼的譯碼性能的進(jìn)

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