王士全，候春雷

(山東省聊城市71901部隊，山東聊城252000)

低密度奇偶校驗(LDPC，low-density parity-check)碼［1］是一種基于圖和迭代譯碼的信道編碼方案，在AWGN信道下具有接近香農(nóng)極限的性能，加上其具有較低的差錯平底特性，可實現(xiàn)完全并行操作，譯碼復(fù)雜度低于Turbo碼，適合硬件實現(xiàn)，吞吐量大，極具高速譯碼的潛力，因此受到越來越多的研究者的關(guān)注。

在Gallager提出的規(guī)則LDPC碼的基礎(chǔ)上，Luby等人構(gòu)造了非規(guī)則碼［2］，并證明了非規(guī)則碼的性能優(yōu)于規(guī)則碼。非規(guī)則LDPC碼中，各節(jié)點(diǎn)的度并不相同，譯碼時存在波浪效應(yīng)，度數(shù)高的比特節(jié)點(diǎn)成功譯碼的概率大，因此非規(guī)則LDPC碼具有內(nèi)在的不等錯誤保護(hù)(UEP，unequal error protection)性能。

本文在簡要介紹非規(guī)則LDPC系統(tǒng)編碼的基礎(chǔ)上，分析了非規(guī)則準(zhǔn)循環(huán)00C-LDPC碼的構(gòu)造方法，并將其應(yīng)用到SPIHT壓縮編碼的圖像傳輸中，然后在AWGN信道下進(jìn)行了仿真驗證。

1 非規(guī)則LDCP碼系統(tǒng)編碼

設(shè)M行N列校驗矩陣H可以分成兩個子矩陣A和B，其中A為M×M矩陣，B為M×(N－M)矩陣，即:

H=［A|B］經(jīng)高斯消元后，矩陣H變換為:

H=［A|B］→［I|P］，其中 P=A－1B，I為單位矩陣，相應(yīng)的生成矩陣為:G=［PT|I］，其中T表示矩陣轉(zhuǎn)置，假設(shè)信源經(jīng)系統(tǒng)編碼后的碼字為u=［c|s］，u為生成的碼字，c為校比特，s為信息比特。

所以 I*c'+P*s'=0，I*c'=P*s'(在 GF(2)上)。所以c'=P*s'。再由u=［c|s］即可得到編碼后的碼字。如果高斯消元過程中進(jìn)行了列交換，則只需記錄列交換，并以相反次序?qū)幋a后的碼字同樣進(jìn)行列交換即可。解碼時先求出u，再進(jìn)行列交換得到uu=［c|s］，后面部分即是想要的信息。

由上面的系統(tǒng)編碼過程可以看出，校驗矩陣的左側(cè)對應(yīng)碼字的校驗比特，校驗矩陣的右側(cè)對應(yīng)碼字的信息比特。如果將校驗矩H的節(jié)點(diǎn)按度數(shù)由低到高從左到右排列，重要信息的比特放在矢量s的右側(cè)，則重要信息對應(yīng)校驗矩陣度數(shù)高的節(jié)點(diǎn)，便可得到較高的保護(hù)，從而可對信息進(jìn)行不等差錯保護(hù)。

2 非規(guī)則準(zhǔn)循環(huán)OOC-LDPC碼的構(gòu)造

構(gòu)造具有UEP性能LDPC碼的校驗矩陣H時，通常采用隨機(jī)構(gòu)造的方法，然后進(jìn)行列置換，將校驗矩陣H列重相同的列排在一起然后按列重由低到高進(jìn)行排列。這種方法構(gòu)造的校驗矩陣，沒有一定的編碼結(jié)構(gòu)，不利于硬件實現(xiàn)。而即將介紹的OOC(Optical Orthogonal Code)-LDPC碼既具有碼率和碼長選擇的靈活性又具有循環(huán)或準(zhǔn)循環(huán)結(jié)構(gòu)，編碼遠(yuǎn)比隨機(jī)構(gòu)造的LDPC碼簡單，利于硬件實現(xiàn)。有結(jié)構(gòu)的LDPC碼還可以有效消除雙向圖中的短環(huán)，因此也顯示了比隨機(jī)LDPC碼更好的性能。

2.1 光正交碼的定義與構(gòu)造

光正交碼是為碼分多址光纖設(shè)計的一種碼，它最早由Salehi、Chung 和 Wei［3］提出，并且立刻得到人們關(guān)注的一種實用編碼。

光正交碼定義為:一族(n，ω，λ)光正交碼 V={V(1)，V(2)，…V(p)}，就是由一組互異、長度為n、重量為 ω 的(0，1)序列所組成的集合，并且每個碼字的循環(huán)自相關(guān)函數(shù)和任意兩個互異的碼字和之間的循環(huán)互相關(guān)函數(shù)分別滿足下式:

光正交碼也可用集合的觀點(diǎn)來描述，(n，ω，λ)光正交碼由一組集合組成，每個集合對應(yīng)一個碼字，它有ω個元素，而每個元素取自小于n的全體非負(fù)整數(shù)集Zn，元素值表示光正交碼字的非零位。此時，其相關(guān)特性為:

其中 V(1)、V(2)∈V，s1、s2是任意整數(shù)，并且 s1≠s2(modn)，V(i)+s={(x+s)(modn)|x∈V(i)}。

設(shè)x=(x0，x1，…，xn－1)是漢明重量為 ω 的二元向量，用集合表示為 x={a1，a2，…aω}，ai∈Zn，x 的第 i次鄰集 Xi可定義為:

Xi={xi，1，xi，2，…，xi，ω－i}，其中 xi，j=aj+i－ aj，1≤j＜ω－i。用ΔX表示x的各次鄰集的集合:

ΔX={X1，X2，… Xω－1}={x1，1，x1，2，… x1，ω－1，x2，1，x2，2，…x2，ω－2，xω－1，1}，并且有向量集 V，定義集合 ΔV 為:

(2)取正整數(shù)m和P，讓碼集V={xr}，xr用集合表示為，碼長為 N 漢明重量為 ω 的碼集V有:

(3)正整數(shù)m的選取必須滿足如下的兩個條件:

通過對n0、m和P的不同選擇，便可得到碼字?jǐn)?shù)和碼長都不相同的一族光正交碼，m和x0的選取可通過計算機(jī)搜索得到。

2.2 矩陣行、列分解技術(shù)

設(shè)有行、列重為 δ的 n×n循環(huán)矩陣 G，讓 ω1，ω2，…，ωi是正整數(shù)集，并滿足 ω1+ω2+… + ωt= δ，其中 1≤t≤δ，t稱為列分解因子。G能分解成t個n×n循環(huán)矩陣G1，G2，…Gt，稱這t個矩陣為列分解子矩陣，各列分解子矩陣Gi的行、列重為ω1，ω2，…，ωt。這樣對G進(jìn)行列分解后得到下面新的n×tn階矩陣:

對式(11)中的 D 可以進(jìn)一步進(jìn)行分解。讓 ωi，1，ωi，2，…，ωi，c是正整數(shù)集，并滿足 ωi，1+ ωi，2+ …，ωi，c= ωi。其中，1≤i≤t，1≤c≤max(ωi:1≤i≤t)，c稱為行分解因子。式(11)的矩陣D中的子矩陣Gi能進(jìn)一步分解成c個n×n循環(huán)矩陣 Gi，1，Gi，2，…，Gi，c，這 c 個矩陣稱為 Gi的行分解子矩陣，各行分解子矩陣 Gi，j的行列重為 ωi，1，ωi，2，…，ωi，c。這樣式(11)

2.3 非規(guī)則準(zhǔn)循環(huán)OOC-LDPC碼構(gòu)造

設(shè)新構(gòu)造的 LDPC碼的校驗矩陣 H為 H(1)，H(2)，…，H(m)，H=［H(1)，H(2)，…，H(m)］，H(i)為 n × n 的循環(huán)矩陣。n×n的循環(huán)矩陣可以用矩陣的第一行經(jīng)n－1次循環(huán)得到。校驗矩陣H的列重分布為γ=［γ1，γ2…γm］。其中γi是矩陣H(i)的列重。構(gòu)造過程如下:

(1)根據(jù)校驗矩陣H的碼長及最大列重，選擇不同的n(0)、m、ω和P，構(gòu)造出符合要求的光正交碼。

(2)設(shè)含有P個碼字的(n，ω，1)光正交碼集V用集合表示為 V={V(1)，V(2)，…，V(P)}，其中當(dāng) P≥m 時，取 V(i)中的 γi個元素構(gòu)成循環(huán)矩陣H(i)的第一行1≤i≤m。當(dāng) P ＜m 時，并且有 γi+ γj≤ω(1≤i，j≤m，i≠j)，可將V(i)拆分成兩個集合來構(gòu)成兩個循環(huán)矩陣的第一行。這樣便可構(gòu)造出碼長N=nm碼率為(m－1)/m準(zhǔn)循環(huán)OOC-LDPC碼，當(dāng)校驗矩陣H的各子矩陣H(1)，H(2)，…，H(m)的列重相同時便可構(gòu)造出規(guī)則準(zhǔn)循環(huán)OOC-LDPC碼，列重不同時便可構(gòu)造出非規(guī)則準(zhǔn)循環(huán)OOC-LDPC碼。

(3)如果需要具有不等差錯保護(hù)性能的非規(guī)則OOCLDPC碼，只需按各子矩陣的列重由低到高進(jìn)行排列即可。

(4)以上構(gòu)造的校驗矩陣H的碼率為(m－1/m)，利用矩陣行、列分解技術(shù)，根據(jù)需要取不同的列分解因子t和行分解因子c，對矩陣進(jìn)行行、列分解。

3 非規(guī)則準(zhǔn)循環(huán)OOC-LDPC碼在圖像傳輸中的應(yīng)用

分層小波樹集合分割(SPIHT:Set Partitioning In Hierarchical Trees)圖像壓縮編碼［4］，利用小波變換將圖像低頻信息集中在左上角，并通過層次樹集合劃分，對重要信息進(jìn)行優(yōu)先編碼，這使得編碼后的碼流具有按重要性排序的特性，使信道編碼很容易對重要信息和非重要信息分別編碼。非規(guī)則LDPC碼本身具有不等保護(hù)特性，利用這一性質(zhì)對SPIHT的圖像壓縮編碼進(jìn)行不等保護(hù)，可在不增加額外費(fèi)用的情況下提高系統(tǒng)性能。

3.1 系統(tǒng)設(shè)計方案

圖像傳輸系統(tǒng)框圖如圖1所示，原始圖像使用512×512標(biāo)準(zhǔn)Lena灰度圖像，經(jīng)小波變換后，采用0.3比特/像素的SPIHT壓縮編碼，然后進(jìn)行LDPC編碼，發(fā)送到信道前進(jìn)行BPSK調(diào)制，信道中加入高斯白噪聲，然后是一個逆過程。

圖1 圖像傳輸系統(tǒng)框圖

由于仿真條件限制，仿真中采用的是由(799，7，1)光正交碼構(gòu)造的非規(guī)則準(zhǔn)循環(huán)OOC-LDPC碼，碼率為3/5，碼長為 3995。光正交碼用集合表示為:V={V1，V2，V3，V4，V5，V6}={{0，3，4，12，18，23，25}，{0，28，54，87，118，148，175}，{0，53，104，162，218，273，325}，{0，78，154，237，318，398，475}，{0，103，204，312，418，523，625}，{0，128，254，387，518，648，775}}。先構(gòu)造碼率為4/5，列重分布由低到高排列為 γ ={2，3，3，5，7}的(3995，799)OOC-LDPC 碼，其中 h(i)為:h(1)={0，87};h(2)={0，103，523};h(3)={0，387，775};h(4)={0，78，154，318，475};h(5)={0，3，4，12，18，23，25}，然后取行分解因子c=2分別對h(i)進(jìn)行行分解，右循環(huán)后生成校驗矩陣 H，得到碼率為3/5的(3995，1598)OOC-LDPC碼。

由前面介紹的系統(tǒng)編碼規(guī)則知，前面的1 598比特為校驗比特，后面的2 397比特為信息比特，1 599～2 397比特的度為32 398～3 196比特的度為53 197～3 995比特的度為7。將圖像經(jīng)SPIHT壓縮編碼后的碼流補(bǔ)零為2 397的倍數(shù)，然后平均分為三部分，第一部分為重要部分對應(yīng)度為7的節(jié)點(diǎn)，第二部分為次重要部分對應(yīng)度為5的節(jié)點(diǎn)，第三部分為不重要部分對應(yīng)度為3的節(jié)點(diǎn)。

3.2 仿真結(jié)果

圖2 為列重 γ ={2，3，3，5，7}，碼率為 3/5 的(3 995，1 598)OOC-LDPC碼在AWGN信道下不同度節(jié)點(diǎn)的性能曲線，從圖中可以看出，度高的節(jié)點(diǎn)比度低的節(jié)點(diǎn)在相同信噪比下具有更好的性能，在10－4處度為7的節(jié)點(diǎn)比度為3的節(jié)點(diǎn)大約有0.1 dB的增益。圖3為512×512 Lena原始灰度圖像。圖4和圖5是在信噪比為1.9 dB時，原始圖像經(jīng)0.3比特/像素的SPIHT壓縮編碼，信道編碼分別采用不等保護(hù)和等保護(hù)方案時的重建圖像。從圖中可以看出，采用不等保護(hù)方式時重建圖像質(zhì)量明顯高于等保護(hù)時的重建圖像質(zhì)量，前者的PSNR值比后者高約8 dB左右。采用不等保護(hù)方式時，重建圖像與原始圖像相比，從感官上基本看不出差別，而采用等保護(hù)方式時的重建圖像則模糊的多。

圖2 00C-LDPC碼不同度節(jié)點(diǎn)性能

圖3 原始圖

圖4 UEP PSNR=34.033 1

圖5 EEP PSNR=26.025 3

4 結(jié)束語

非規(guī)則LDPC碼具有不等保護(hù)特性，可以在不增加額外開銷的情況下提高圖像傳輸質(zhì)量。文中介紹的非規(guī)則準(zhǔn)循環(huán)OOC-LDPC碼，具有準(zhǔn)循環(huán)結(jié)構(gòu)，構(gòu)造容易，硬件實現(xiàn)簡單，只需用移位寄存器反饋連接就可實現(xiàn)。仿真結(jié)果顯示，非規(guī)則準(zhǔn)循環(huán)OOC-LDPC碼在中短碼長時便具有較強(qiáng)的糾錯能力，在節(jié)點(diǎn)度數(shù)相差不大或節(jié)點(diǎn)最高度不是很大時便具有較好的不等保護(hù)特性，非常適合無限圖像傳輸。因此可以預(yù)料，文中介紹的非規(guī)則準(zhǔn)循環(huán)OOC-LDPC碼，在數(shù)字視頻廣播(DVB)、無線局域網(wǎng)(Wireless LAN)和下一代移動通信中將具有極好的應(yīng)用前景。

［1］Gallager E.G Low-density Parity-check Codes［J］.IRE Trans on Information Thory，1962.8(1):21 －28.

［2］Luby M G Mitzenmacher M，Shokrollahima.Improved Lowdensity Parity-chek Codes Using Irregular Guaphs［J］.IEEE Trans on Information Theory，2001，47(2):585 －598.

［3］Salehi J.A，Chung F.K，Wei V.K.Optical Orthogonal Codes Design，Analysis and Applications［J］.IEEE Trans.Theory，1989，35(3):595 －604.

［4］全子一.圖像信源壓縮編碼及信道傳輸理論與新技術(shù)［M］.北京:北京工業(yè)大學(xué)出版社，2006.