基于LPDC碼的分布式多進(jìn)制相關(guān)信源編碼

1、圖1兩種編碼器結(jié)構(gòu)(b 獨立編碼聯(lián)合解碼(a 聯(lián)合編碼聯(lián)合解碼R X >H(X|Y 解碼器編碼器XYYX R X >H(X|Y 解碼器編碼器XX Y 1引言雖然分布式編碼理論早在二十多年前就已經(jīng)提出,但是Slepian-Wolf 理論1和Wyner-Ziv 理論2只給出了信源編碼的理論根據(jù),并沒有給出一種具體的實現(xiàn)方法,因此這方面的進(jìn)展并不顯著。直到近幾年,研究者才找到實現(xiàn)分布式信源編碼的可行方法,發(fā)現(xiàn)了信源編碼和信道編碼的密切關(guān)系。如果信道碼能夠漸近地接近信道容量,那么把它應(yīng)用于分布式信源編碼就能漸近地接近Slepian-Wolf 理論極限,Pradhan 和Ramchan -d

2、ran 提出了分布式編碼的實現(xiàn)方案3,一些具體的實現(xiàn)方案陸續(xù)的提出4-6,從理論上證明了使用Turbo 碼可以接近Selpian-Wolf 編碼效率6,并且證明了使用LDPC 碼可以達(dá)到比Turbo 碼更好的效果7,但以上文獻(xiàn)中都是二進(jìn)制相關(guān)信源,本文要闡述的就是如何把二進(jìn)制LDPC 碼用于的多進(jìn)制相關(guān)信源編碼,并且比較了不同信源模型在無失真壓縮條件下的編碼效率。2分布式編碼的信息論基礎(chǔ)Slepian-Wolf 理論提出:對于互相關(guān)的兩個離散隨機(jī)信號X 、Y ,服從聯(lián)合概率分布p (x ,y,那么在編碼端得不到Y(jié) 的情況下對X 進(jìn)行編碼可以取得編碼效率和在編碼端得到Y(jié) 的情況下對X 進(jìn)行編碼的

3、效率一樣。也就是說,在編碼端可以不需要直接跟Y 通信,X 最少也能以H(X|Y 比特編碼,只要在解碼端可以得到Y(jié) ,那么X 仍能正確解碼。根據(jù)Slepian-Wolf 理論,圖1所示的兩種編碼方案可以取得相同的編碼效率。Slepian-Wolf 理論可以簡單地描述如下:假定X 和Y 是兩個互相關(guān)的離散無記憶信源,對X 和Y 進(jìn)行獨立編碼,H (X ,H (Y 分別是X ,Y 的熵,編碼器X 輸出的碼流是R (X ,編碼器Y 輸出的碼流是R(Y ,在解碼端進(jìn)行聯(lián)合解碼,如果在解碼端可以無失真的恢復(fù)X ,Y 需要滿足式(1式(3。R X H (X|Y (1R Y H(Y|X (2R X +R Y

4、H(X|Y (3Slepian-Wolf 理論的可達(dá)速率域如圖2所示?；贚PDC 碼的分布式多進(jìn)制相關(guān)信源編碼陳睿,王尊亮,李學(xué)明CHEN Rui ,WANG Zun-liang ,LI Xue-ming北京郵電大學(xué)信息處理與智能技術(shù)重點實驗室,北京100876Key Lab of Information Processing and Intelligent Technology ,Beijing University of Posts and Telecommunications ,Beijing 100876,China E-mail :ruichenster CHEN Rui ,WAN

5、G Zun-liang ,LI Xue-ming.Distributed correlated M-ary sources coding using LDPC codes.ComputerEngineering and Applications ,2009,45(15:126-129.Abstract :Distributed source coding is a new hot spot in the wireless sensor network area.This paper introduces the fundamentaltheory of distributed coding ,

6、then LDPC coding and multilevel coding methods applied in distributed coding are given.Finally ,a distributed multilevel coding method is proposed to realize correlated M-ary sources coding and in the case of different correla -tion between two sources the performances of distributed correlated M-ar

7、y sources coding are compared.Key words :distributed coding ;Low Density Parity Check (LPDC ;multilevel coding 摘要:分布式信源編碼是無線傳感器網(wǎng)絡(luò)領(lǐng)域研究的新熱點,闡述了分布式編碼的基礎(chǔ)理論,介紹了應(yīng)用于分布式編碼的LDPC編碼方法和多級編碼方案,最后提出了一種基于LPDC 碼的分布式多級編碼方案實現(xiàn)分布式多進(jìn)制相關(guān)信源編碼,并且比較了不同相關(guān)性下分布式多進(jìn)制信源編碼的性能。關(guān)鍵詞:分布式編碼;低密度檢驗碼;多級編碼文獻(xiàn)標(biāo)識碼:A中圖分類號:TP391基金項目:北京市自然科學(xué)基金(t

8、he Natural Science Foundation of Beijing City of China under Grant No.4072019。作者簡介:陳睿(1984-,男,碩士研究生,主要研究方向為分布式視頻編碼和圖像處理;王尊亮(1981-,男,博士研究生,主要研究方向為視頻編碼和無線多媒體傳輸;李學(xué)明(1969-,男,教授,博士生導(dǎo)師,主要研究方向為圖像處理、視頻編碼與傳輸、計算機(jī)網(wǎng)絡(luò)和數(shù)據(jù)通信。收稿日期:2008-03-17修回日期:2008-07-09圖3Wyner-Ziv 有損分布式編碼結(jié)構(gòu)有損編碼解碼器XY YX 有損編碼解碼器XYX (a 聯(lián)合編碼聯(lián)合解碼(b 獨

9、立編碼聯(lián)合解碼圖4二分圖 ÁÁÁÁÁx 1x 2x 3x 4x 5x 6x 7圖2Slepian-Wolf 編碼碼率區(qū)域RY H (YH (Y|X只要如RX 和RY 的取值范圍在圖中的Slepian-Wolf 壓縮可達(dá)速率的區(qū)域,則在解碼端可以任意小的誤碼率來聯(lián)合解碼。下面舉例來說明這個問題:假設(shè)有兩個相關(guān)的等概率分布的信源X 、Y ,長度為3bit ,漢明距離小于等于1。將3bit 序列分成4組序列對,每組兩個序列的漢明距離為3,即000,111,001,110,010,101,100,011,這4組序列對只需2bit 編碼就可區(qū)分,而X 必

10、居其中之一組。于是可以用序列對的編碼代替X 編碼發(fā)送,加上Y 的3bit ,達(dá)到5bit 速率目標(biāo)。在譯碼端由譯出的Y 便可確定在同時刻接受到的X 序列對中,那一個為與Y 用時發(fā)送的X 。因為同時刻發(fā)送的X 和Y 其漢明距離不會超過1,這就決定了接收到的Y 只能與接收到的X 序列對中的一個相近,而與另一個序列的距離大于1,這樣就完全驗證了Slepian-Wolf 定理的編碼的可行性。在Slepian-Wolf 的無損編碼理論發(fā)表后不久,Wyner-Ziv 就對這個理論進(jìn)行了擴(kuò)充,建立了在解碼端使用輔助信息的有損編碼理論2,見圖3。3基于LDPC 碼的分布式編碼3.1Discus 編碼方案Dis

11、cus(distributed source coding using syndrome 編碼方案3考慮了兩個相關(guān)的信源X 和Y 的獨立編碼和聯(lián)合解碼,在X 和Y 之間想象一條虛擬的信道P(Y|X ,把信源X 看作信道的輸入,把參考信息Y 看作信道的輸出,即把信源Y 看成是信源X 經(jīng)過噪聲污染后的結(jié)果,這樣就可以利用信道碼的糾錯性能來恢復(fù)信源碼字。該方案的關(guān)鍵問題是信源碼字空間的分割,把信源X 的輸出劃分成不同的組,稱之為陪集,這種劃分使得在每一個陪集中的兩個碼字之間的最小距離盡可能的達(dá)到最大,以便在解碼端通過觀察參考信息Y 在陪集中找到和參考信息距離最近的碼字作為解碼結(jié)果,編碼器則通過只傳輸

12、陪集的索引來達(dá)到數(shù)據(jù)壓縮的目的,陪集的這種特性正好與信道碼的特性十分的相似。對于(n ,k 信道分組碼,n 為碼字長度,k 為信息比特長度,這組信道碼正好是在所有碼長為n 的碼字序列中選取的距離盡可能大的2k 個序列,H 為該信道碼的校驗矩陣,對于每一組信道碼的陪集都可以用它的校正子(Syndrome 來表征,定義校正子S =X H ,S 也稱為信道碼的伴隨式,X 是該信道碼中的碼字,每一組信道碼對應(yīng)一個伴隨式,該伴隨式也就是這個陪集的索引。在編碼過程中,把待編碼碼字看作是碼字長度為n 的碼字序列中的一個元素,然后找出這個碼字所在的信道碼,再傳輸該組信道碼的索引(校正子或伴隨式到解碼端,這樣傳

13、輸?shù)拇a字長度就由n 變成了n-k ,節(jié)省了k 個比特。在解碼端,接收到的是編碼碼字所屬陪集的伴隨式,解碼的工作就是利用參考信息Y 在伴隨式S 所指示的信道碼中找到與X 距離最近的碼字,即利用信道碼解碼來恢復(fù)被編碼的碼字。下面利用前面所舉的例子說明這個問題:4組序列對都是(n ,k ,d 分組碼的陪集,這里n 是碼字長度,k 是信息比特數(shù)而d 是碼的最小漢明距離。現(xiàn)在是(3,1,3分組碼,分組碼的校驗矩陣為(n-k ×n 階矩陣,對以上的(3,1,3碼,其校驗矩陣為H =11010 1校正子為S =X H ,可以發(fā)現(xiàn)每一個陪集的兩個碼字的校正子都是一樣的,比如第一組S =0001110

14、00000000000000000001=00S =11111100000000000000001=00其他三組的校正子分別為01,10,11,這四個校正子就是X 編碼輸出的所有可能的碼字。在接收端,解碼器譯出校正子并結(jié)合同時譯出的參考信息Y 就可以正確地恢復(fù)出所發(fā)送的信源X 。3.2使用LDPC 編解碼方法LDPC 碼(Low Density Parity Check ,低密度校驗碼是一種線性分組碼糾錯碼,但是與以往的線性碼不同的是它是由一個稀疏的校驗矩陣H 或者二分圖來描述的,這種稀疏結(jié)構(gòu)是LDPC 碼具有很好的性能的重要特征。LDPC 碼是最小漢明距離隨著碼長的增加而線性增加的漸進(jìn)好碼8

15、,具有小的譯碼錯誤概率和比Turbo 碼更低的線性譯碼復(fù)雜度,性能可以非常接近Shannon 限,因此LDPC 碼也被用于分布式信源編碼中7-9。LDPC 碼可以用一個稀疏的奇偶校驗矩陣來定義,設(shè)碼長為N ,信息位為K ,校驗位為M=N-K ,碼率為R=K /N ,其校驗矩陣H 是一個M ×N 的矩陣。相應(yīng)的二分圖有N 個比特節(jié)點x j :j =1,2,N ,每個比特節(jié)點對應(yīng)碼字的一個比特X =x 1,x 2,x N ,對應(yīng)著H 矩陣的一列;Z =z 1,z 2,z M 表示M 個校驗節(jié)點z i :j =1,2,M ,每個校驗節(jié)點相當(dāng)于一個奇偶校驗等式,對應(yīng)H 矩陣的一行。如果H (

16、i ,j 為1,則二分圖的第j 個信息節(jié)點與第i 個校驗節(jié)點有一條邊相連,例如一個(7,3的LPDC 碼的校驗矩陣如下,二分圖如圖4所示。H =101011001100000000000001在信道編碼中,對于任意屬于該信道碼中的碼字X ,都有X H =0,對于不屬于該信道碼中的碼字X H 0,同時也作為解圖6編解碼系統(tǒng)無失真信道聯(lián)合解碼器編碼器信源XX SS X贊參考信息Y碼率R 1R X碼率R 1R X 碼率R X圖7信源X 和Y 之間建立虛擬信道聯(lián)合解碼器虛擬信道信源X參考信息YX贊X 的壓縮信息S圖8應(yīng)用于分布式編碼的MLC 系統(tǒng)S (2=(S (21,S (22,S (2k 2S (

17、1=(S (11,S (12,S (1k 1S (m =(S (m 1,S (m 2,S (m km X (1=(X (11,X (1n X (2=(X (21,X (2n X (m =(X (m 1,X (m n 信源序列X 序列分組(n ,k 1E 1(n ,k 2E 2(n ,k m E m圖9應(yīng)用于分布式編碼PDL 譯碼系統(tǒng)序列分組參考信息Y 解碼序列X 贊解碼器1解碼器2解碼器3S (1=(S (11,S (12,S (1k 1S (m =(S (m 1,S (m 2,S (m km S (2=(S (21,S (22,S (2k 2Y (1=(Y (11,Y (1n Y (2=(Y

18、 (21,Y (2n Y (m =(Y (m 1,Y (m n 序列合成X 贊(1=(X 贊(11,X 贊(1nX 贊(2=(X 贊(21,X 贊(2n X 贊(m =(X 贊(m 1,X 贊(m n 圖5聯(lián)合后驗概率分布二分圖z 1z 2z i z Mx 1x 2x 3x j x NR ai ,jQ aj ,i碼端是否正確譯碼的判斷條件,而在分布式信源編碼中,編碼端發(fā)送校正子S =X H ,參考信息Y 按傳統(tǒng)的數(shù)據(jù)編碼方法傳輸?shù)浇獯a端,利用參考信息和校正子S 找到與X 距離最近的碼字,是否正確譯碼的判斷條件就是X H 是否等于S 。在接收端迭代概率譯碼算法是較常用的LDPC 譯碼算法是基于置

19、信傳播的迭代譯碼算法,是逐符號判決的譯碼方法。接收端收到的碼字向量集合記為r ,將信息節(jié)點X 滿足包含x j 的所有校驗方程這個事件記為S ,比特x j =1(或x j =0關(guān)于r 和S 的條件概率P r (x j =1|r ,S (或P r (x j =0|r ,S ,若P r (x j =0|r ,S P r (x j =1|r ,S 1(4成立,則接受符號r i 的估值x j =0;若不成立,則x j =1。圖5中,R ai ,j為校驗消息,表示第j 個信息比特x j =a (a 取0或1的情形下,第j 個校驗方程滿足的條件概率。Q aj ,i 為信息消息,表示除第i 個校驗節(jié)點外其他校

20、驗節(jié)點提供信息的情況下第j 個信息比特x j =a 的概率。置信傳播的迭代算法在每次迭代中,每個z i 節(jié)點向其所有x j 節(jié)點分別傳遞R ai ,j 信息,然后每個x j 節(jié)點通過所有z i 節(jié)點傳遞已更新的Q a j ,i 消息,來更新R ai ,j 。如果算法收斂,經(jīng)過足夠次數(shù)的迭代后,將漸進(jìn)求出概率P r (x j =1|r ,S (或P r (x j =1|r ,S ,實現(xiàn)逐符號最大后驗概率(MAP 譯碼。4信源模型和多級編碼系統(tǒng)4.1信源模型考慮圖6所示系統(tǒng),并且信源滿足如下假設(shè):(1信源X =X 1,X 2,X n ,Y =Y 1,Y 2,Y n ,X i ,Y i (0,1,M

21、 -1是離散無記憶等概率分布的M 進(jìn)制隨機(jī)變量。(2X i 和Y i 互相關(guān),并且P X i Y i =p <0.5。(3在聯(lián)合解碼端可在無失真情況下得到Y(jié) ,并盡可能的壓縮信源X ,信源Y 的碼率就是它的熵R 2=H (Y =lb M ,無損壓縮信源X 的理論極限1為R 1H (X|Y =M -1i =0M -1j =0P (Y i X j lb (1/P (Y i |X j 。為了在信源X 、Y 之間利用信道碼進(jìn)行編解碼,可以想象在信源X 和Y 之間有一條虛擬信道,X 作為信道輸入,Y 作為信道輸出,如圖7,本文模擬在X 和Y 之間為加性高斯白噪聲虛擬信道,在該虛擬信道情況下,Y =

22、mod (round (X+N ,M ,Y (0,M -1,N 是均值為0,方差是2的高斯白噪聲。4.2多級編碼系統(tǒng)多級編碼(MLC-Multilevel Codes 自1977年由Imai 提出以來10,得到了廣泛地關(guān)注,具有設(shè)計靈活、能提供不等錯誤保護(hù)度等許多優(yōu)點。采用多級編碼方式把二進(jìn)制LDPC 碼用于多進(jìn)制相關(guān)信源的分布式編碼。多進(jìn)制信源分組成多級的不同權(quán)重的二進(jìn)制比特序列,針對不同權(quán)重的比特序列傳輸可以采用不同傳輸碼率達(dá)到無失真壓縮,從整體上達(dá)到更好的壓縮效果。本文采用的MLC 系統(tǒng)如圖8所示,其基本原理是:首先多進(jìn)制信源X 經(jīng)過分組后得到二進(jìn)制序列X (1,X (2,X (m ,X

23、 (i 長度都為n ,然后分別進(jìn)入m 個LDPC 編碼器E 1,E 2,E m 進(jìn)行編碼,各個編碼器壓縮X (1,X (2,X (m 傳輸其校正子S (1,S (2,S (m ,長度分別為k 1,k 2,k m ,壓縮比分別為R 1=n /k 1,R 2=n /k 2,R m =n /k m 。解碼端采用并行譯碼的方法(Parallel Decoding on levels-PDL,該方法結(jié)構(gòu)簡單,各級之間沒有關(guān)聯(lián),并行獨立譯碼。長度分別為k 1,k 2,k m 的二進(jìn)制校正子序列S (1,S (2,S (m 分別進(jìn)入LDPC 解碼器,利用參考信息Y 和信源X 進(jìn)行相同分組后得到的二進(jìn)制參考信

24、息序列Y (1,Y (2,Y(m 解碼得到長度為n 的信源X 的恢復(fù)序列X 贊(1,X 贊(2,X 贊(m ,最后把該二進(jìn)制序列X 贊(1,X 贊(2,X 贊(m 合成為多進(jìn)制信源X 的估計X贊,如圖9所示。以上描述的多級編碼系統(tǒng)中,M 進(jìn)制信源X 和Y 中不同權(quán)重的比特分別歸為不同的二進(jìn)制序列,對于M =2k ,k =1,2,也就是說信源分組后得到lb M 個二進(jìn)制比特序列。對于多進(jìn)制對稱信道模型的信源X 和Y ,信源分組后不同權(quán)重比特序列的誤碼率基本上是相等的,因此對不同序列可以采用相同的二進(jìn)制LDPC 編碼。對于虛擬信道是加性高斯白噪聲信道的信源X 和Y ,由于不同權(quán)重的比特序列誤碼率相

25、差很大,因此對不同權(quán)重比特序列采用不同的壓縮比才能保證在解碼端無失真恢復(fù)原始信源,同時提高整體壓縮效果,二進(jìn)制比特序列誤碼率越小,能夠壓縮的倍數(shù)越高。5實驗結(jié)果實驗中采用LDPC 碼碼長為32768,對6.5×108個比特仿真,BER <10-6。圖10、圖11分別為AWGN 虛擬信道下四進(jìn)制和八進(jìn)制相關(guān)信源采用多級編碼和不采用多級編碼的性能的比較。不采用多級編碼的多進(jìn)制信源直接把多進(jìn)制數(shù)據(jù)轉(zhuǎn)換為對應(yīng)的二進(jìn)制比特。圖中所示實線和虛線分別表示在無失真的情況下采用多級編碼方法和不采用多級編碼方法的多進(jìn)制相關(guān)信源分布式編碼性能,可見采用多級編碼方法比不采用多級編碼方法的傳輸碼率要更接

26、近Slepian-Wolf 極限。在多進(jìn)制相關(guān)信源之間引入一個新的虛擬信道模型多進(jìn)制對稱信道,轉(zhuǎn)移概率為P ,如圖12所示。比較了本文提出的方案在不同相關(guān)性下進(jìn)行分布式多進(jìn)制相關(guān)信源編碼的性能,如圖13、圖14所示,因為多進(jìn)制對稱信道內(nèi)引起的誤碼在信源不同權(quán)重比特上分布比AWGN 信道均勻很多,因此多進(jìn)制相關(guān)信源無失真條件下在對稱信道情況下進(jìn)行分布式編碼比AWGN 信道情況下編碼有更好的性能,其傳輸碼率更接近Slepian-Wolf 極限。6結(jié)論提出了一種基于二進(jìn)制LPDC 碼的分布式多級編碼方案實現(xiàn)分布式多進(jìn)制相關(guān)信源編碼,并且表明在無失真條件下采用多級編碼方法比不采用多級編碼方法的分布式編

27、碼性能要好,指出多進(jìn)制相關(guān)信源在無失真條件下的分布式編碼在對稱信道情況下編碼比AWGN 信道情況下編碼性能要好,其傳輸碼率更接近Slepian-Wolf 極限。參考文獻(xiàn):1Slepian J ,Wolf J.Noiseless coding of correlated information sourcesJ.IEEE Transactions on Information Theory ,1973,7(19:471-480.2Wyner A ,Ziv J.The rate-distortion function for source coding withside information a

28、t the decoderJ.IEEE Transactions on Information Theory ,1976,1(22:1-10.3Pradhan S ,Ramchandran K.Distributed source coding using syn -dromes (DISCUS :Design and constructionJ.IEEE Transactions on Information Theory ,2003,49(3:626-643.4Garc ía-Fr ías J.Compression of correlated binary sources using tur -bo codesJ.IEEE Commun Lett ,2001,5(10:417-419.5Aaron A ,Girod B.Compression with side information using turbocodesC/Proc Data Compression Conf ,DCC 2002,2002:252-261.6Mitran P ,Bajcsy J.Near Shannon limit coding for the Slepian-Wolfproblem C/Proc 21st Biennial Symposiu