蔡麗萍, 孫 悅

(中國石油大學(xué)(華東) 計算機與通信工程學(xué)院, 青島 266555)

基于極化碼的分布式信源編碼①

蔡麗萍, 孫 悅

(中國石油大學(xué)(華東) 計算機與通信工程學(xué)院, 青島 266555)

介紹了分布式信源編碼的基本思想和經(jīng)典的分布式信源編碼的構(gòu)造實現(xiàn)方法. 討論了聯(lián)合信道-分布式信源編碼方法, 通過新興的極化碼, 實現(xiàn)了聯(lián)合極化碼-分布式無損信源編碼系統(tǒng), 并將其應(yīng)用到圖像傳輸當(dāng)中, 實驗仿真驗證了其可行性.

分布式信源編碼; 聯(lián)合信道-分布式信源編碼; 極化碼; 聯(lián)合極化碼-分布式無損信源編碼; 圖像傳輸

分布式信源編碼是信息論中的一個傳統(tǒng)問題, 它的基本思想是編碼端多信源分別獨立編碼、解碼端聯(lián)合解碼, 適用于編碼端資源非常有限的場合. 與傳統(tǒng)的信源聯(lián)合編碼相比, 分布式信源編碼降低了編碼端運算、內(nèi)存等資源消耗, 并且在解碼端利用冗余聯(lián)合解碼, 可以獲得和聯(lián)合編解碼方式相近的編碼效率.

分布式編碼方法的理論基礎(chǔ)是Slepian-Wolf理論[1]和Wyner-Ziv理論[2], 前者是無損分布式編碼, 后者是有損分布式編碼. 目前很多種分布式編碼的實現(xiàn)框架被提出, 文獻[3]中提出了一種基于Slepian-Wolf理論的構(gòu)造方案. 其思想是使用卷積碼進行信道編碼得到分布式信源編碼器的輸入, 并且在每一路信道只傳輸部分碼流, 在解碼端利用伴隨式譯碼的方法實現(xiàn)重建, 相當(dāng)于聯(lián)合了信道編碼的方式降低了單路信號的碼流, 實現(xiàn)了分布式編碼.

由于分布式信源編碼的構(gòu)造實現(xiàn)方式和信道碼的特點十分的相似, 目前國內(nèi)外主要是采用LDPC碼[4]和Turbo碼[5]來實現(xiàn)分布式信源編碼. 新興的極化碼相比起LDPC碼和Turbo碼, 編譯碼的復(fù)雜度更低, 并且可以無限的接近香農(nóng)容量, 因此本文采用極化碼來實現(xiàn)聯(lián)合信道-信源編碼.

本文的主要工作是介紹了分布式信源編碼和極化碼的相關(guān)原理, 然后實現(xiàn)了聯(lián)合極化碼-分布式無損信源編碼系統(tǒng), 最后提出了一種方案將這一方法應(yīng)用到圖像傳輸中.

1 相關(guān)原理

1.1 Slepian-Wolf分布式編碼原理

Slepian-Wolf分布式編碼在編碼端對相關(guān)信源進行獨立編碼, 在解碼端利用相關(guān)性進行聯(lián)合解碼. 如圖1所示.

圖1 Slepian-Wolf示例框圖

根據(jù)信息論可知, 傳統(tǒng)的信源編碼當(dāng)碼率符合以下條件時:

即總碼率滿足以下條件時:

解碼端可以無差錯的恢復(fù)信息. 而分布式信源編碼的目標是在總碼率低于每個碼率的熵的和情況下可以任意小的差錯概率無損重建信息.

通過分析無損編碼器傳輸碼率可知碼率如下:

因此, 分布式無損信源編碼理論可以獲得和傳統(tǒng)的信源編碼相同的編碼效率.

1.2 Wyner-Ziv有損分布式編碼原理

與Slepian-Wolf理論不同的是, Wyner-Ziv的主要研究是在邊信息存在的情況下進行分布式信源編碼, 即在解碼端邊信息Y存在的情況下, Wyner-Ziv給出了如何在可接受失真d的情況下實現(xiàn)分布式有損信源編碼.圖2是一個Wyner-Ziv有損編碼器.

圖2 Wyner-Ziv有損編碼框圖

Wyner-Ziv有損編碼器可以看做是矢量量化器和無損信源編碼器的結(jié)合. 可以看出, 在整個Wyner-Ziv編碼過程中, 量化器的選擇影響了整個編碼器的性能和編碼速率.

1.3 分布式信源編碼的實現(xiàn)方法

分布式信源編碼原理雖然早已提出, 但理論上并沒有給出具體的碼字構(gòu)造, 直到最近十幾年才出現(xiàn)具體的方案, 其中最主要是利用陪集, 即Pradhan和Ramchandran提出的DISCUS[6]的方法來構(gòu)造實現(xiàn)的,編碼器只需要通過邊信息和陪集的索引即可恢復(fù)信源.由于這種陪集的劃分與信道碼的特性十分的相似, 因此可以利用信道碼來實現(xiàn)陪集的構(gòu)造和信源的分割.

假定一個線性分組碼(n, k), 它的生成矩陣為G, 校驗矩陣為H. 對于每一組信道碼的陪集都可以用它的伴隨式(Syndrome)來表示, 定義伴隨式為S=XH’, X是該信道碼中的碼字, 每一組信道碼對應(yīng)一個伴隨式, 該伴隨式也就是這個陪集的索引, 在編碼過程中傳輸該信道碼的索引到解碼端, 在解碼端利用參考信息在伴隨式所指示的信道碼中找到與距離最近的碼字, 即解碼結(jié)果.

近年來對于分布式信源編碼的研究主要是基于DISCUS方法利用LDPC碼和Turbo碼來實現(xiàn)的. 而本文采用的極化碼, 因為編譯碼的復(fù)雜度低, 并且可以無限接近香農(nóng)容量, 因此在分布式信源編碼中也有很好的應(yīng)用.

1.4 極化碼

極化碼最早是由Arikan在2009年提出的[7], 它是基于信道極化原理[7]實現(xiàn)的一種新型線性分組碼. 極化碼的編譯碼復(fù)雜度低, 并且可以無限的接近信道容量, 因此一經(jīng)提出便成了研究熱點.

1.4.1 信道極化

信道極化是對于任意的N個獨立二進制無記憶信道, 其輸入比特經(jīng)過一系列的變換后, 輸入信道傳輸,除了一小部分信道外, 其余的信道都會表現(xiàn)為信道容量趨向于1或者是0的現(xiàn)象.

信道極化包含信道組合和信道分裂兩個過程. 信道組合是將N個相同的信道W經(jīng)過一系列變換之后, 產(chǎn)生一個向量信道WN, 而信道分裂則是將已經(jīng)合成的信道分成N個一維并且信道容量不同的信道.

1.4.2 極化碼編碼

1.4.3 極化碼譯碼

極化碼的譯碼方法主要有連續(xù)刪除譯碼(SC)[8]和置信譯碼(BP)[9]等. 其中, SC譯碼方法是在已知接收端接收到的信息、固定信息位置和凍結(jié)位置的比特的情況下, 通過計算似然比進行判決, 最后得到輸入的比特估計. 過程如下文所述.

2 聯(lián)合極化碼-分布式無損信源編碼的實現(xiàn)

本文根據(jù)分布式無損信源編碼原理, 極化碼原理和DISCUS算法實現(xiàn)了一種聯(lián)合極化碼-分布式無損信源編碼[10]的方法.

2.1 分布式無損編碼系統(tǒng)實現(xiàn)

根據(jù)分布式無損信源編碼的原理, 實現(xiàn)了一種分布式無損信源編碼器. 過程如下:

(1) 隨機產(chǎn)生一組長度為N的序列X和一組長度為N的與X相關(guān)的序列Y.

(2) 對X和Y進行分割: 令X=[Xa, Xb], Y=[Ya, Yb], 長度分別為k和N-k.

(3) 對長度為k的Xa和Xb進行分割, 令Xa=[Xa1, Xa2],Ya=[Ya1, Ya2], 長度分別為k1和k-k1.

(4) 計算X和Y的伴隨式Sx和Sy, 長度為N-k.

(5) 將[Xa1, Sx]和[Ya2, Sy]作為兩個獨立信道編碼器的輸入.

(6) 在解碼端利用以下公式進行解碼:

過程如圖3所示.

圖3 分布式無損信源編碼框圖

其中, 解碼器是利用伴隨式進行伴隨式譯碼得到分布式信源編碼器輸入端口的信息比特, 最后利用解碼公式進行解碼得到全部輸入序列.

2.2 對稱極化碼的實現(xiàn)

標準的極化碼是不對稱的極化碼, 是無法用上文設(shè)計的解碼方法實現(xiàn)無損分布式信源解碼的. 因此, 首先要將標準的不對稱極化碼轉(zhuǎn)換成對稱的極化碼[11]. 過程如下:

(1) 隨機產(chǎn)生一組長度為N的0, 1序列u.

(2) 對于信息位位置集合A進行比特翻轉(zhuǎn)得到集合B.

(3) 將生成矩陣G進行矩陣分割:

(4) 利用以下公式將不對稱的極化碼轉(zhuǎn)換成對稱的極化碼:

2.3 聯(lián)合極化碼-分布式信源編碼系統(tǒng)實現(xiàn)

將轉(zhuǎn)換后的對稱極化碼和無損分布式信源編碼系統(tǒng)進行聯(lián)合. 設(shè)置初始值如下:

最后利用下式進行解碼:

2.4 方法可行性分析

對上文設(shè)計的編碼系統(tǒng)的碼率和熵進行計算得到:

可以看出, 該編碼系統(tǒng)采用了獨立編碼, 利用相關(guān)性進行聯(lián)合解碼的方法, 碼率和熵符合分布式無損信源編碼的碼率界限. 因此該方法是可行有效的. 由于極化碼的編譯碼復(fù)雜度低, 因此相比于傳統(tǒng)的利用LDPC等實現(xiàn)的分布式信源編碼, 該方法對于傳輸相關(guān)多信源數(shù)據(jù)的效率更高.

3 聯(lián)合極化碼-分布式無損信源編碼在灰度圖像傳輸中的應(yīng)用

3.1 方法設(shè)計

本文提出了一種利用聯(lián)合極化碼-分布式無損信源編碼的系統(tǒng)來實現(xiàn)無損圖像傳輸. 這里的圖像我們采用的是灰度圖像.

(1) 隨機選取一張灰度圖像.

(2) 讀入圖像, 得到像素矩陣集合X.

(3) 將X作為極化碼編碼器的輸入, 利用不對稱極化碼轉(zhuǎn)換成對稱極化碼的方法轉(zhuǎn)換成X’.

(4) 將X’經(jīng)過一組虛擬的噪聲信道產(chǎn)生于X’相關(guān)的序列Y.

(5) 將X’和Y作為分布式無損信源編碼的輸入X和Y進行分布式無損信源編碼.

(6) 將分布式信源編碼的輸出經(jīng)過運算得到原始圖像矩陣集合的估計X_estimate.

(7) 將估計值X_estimate恢復(fù)成灰度圖像, 并與初始的灰度圖像作對比.

3.2 方法可行性分析

通過實驗仿真分析, 利用該聯(lián)合極化碼-分布式無損信源編碼系統(tǒng)得到了與原始圖像相同的圖像, 驗證了該方法的可行性.

4 實驗結(jié)果與分析

4.1 聯(lián)合極化碼-分布式無損信源編碼系統(tǒng)的實驗結(jié)果與分析

通過Matlab仿真, 分別設(shè)置了不同的碼長N和不同的信息位傳輸碼字個數(shù)k1, 結(jié)果如表1和表2所示.

通過表1可以分析出: 利用任意碼長的極化碼均可以實現(xiàn)分布式無損信源編碼, 即誤碼比特為0的目標, 即聯(lián)合極化碼-分布式無損信源編碼系統(tǒng)是可行有效的.

表1 不同碼長(N)的信息位個數(shù)(K)和傳輸誤碼比特數(shù)(ERR)

通過表2可以分析出: 只要傳輸碼率在SW分布式信源編碼理論碼率界限之內(nèi), 傳輸任意的信息位比特都可獲得和傳統(tǒng)的信源編碼相同的編碼效率.

表2 當(dāng)N=512時, 不同K1的誤碼比特數(shù)

4.2 聯(lián)合極化碼-分布式無損信源編碼系統(tǒng)在灰度圖像傳輸應(yīng)用中的實驗結(jié)果與分析

基于上述聯(lián)合極化碼-分布式無損信源編碼系統(tǒng)應(yīng)用到灰度圖像傳輸中, 并利用軟件進行了仿真. 這里我們的原始圖像采用的是一張大腦內(nèi)部灰度圖像.

通過實驗仿真得到了和原始圖像像素矩陣相同的重建圖像像素矩陣, 并通過圖像觀察可以發(fā)現(xiàn)該方法實現(xiàn)了灰度圖像的無損傳輸. 相比于傳統(tǒng)的獨立編解碼的方式, 該方法減少了編碼器的運算量, 對于傳輸數(shù)據(jù)量大的圖像更有優(yōu)勢. 相比于聯(lián)合LDPC-分布式無損信源編碼方法[12], 該方法的編譯碼復(fù)雜度更低. 這一結(jié)果的實現(xiàn)對于其他更加復(fù)雜的圖像(如多光譜圖像,高光譜圖像等)的壓縮傳輸提供了新的研究思路.

圖4 原始圖像和重建圖像對比圖

4 結(jié)語

本文實現(xiàn)了一種聯(lián)合極化碼-分布式無損信源編碼系統(tǒng), 并提出了一種方法將這一聯(lián)合信源-信道碼應(yīng)用到灰度圖像傳輸技術(shù)中. 文中詳細闡述了實驗的具體實現(xiàn)方式, 內(nèi)容詳細, 步驟完整, 并通過仿真工具進行了實驗的驗證. 下一步的主要工作是將該方案應(yīng)用到高光譜圖像傳輸中.

1Slepian D, Wolf J. Noiseless coding of correlated information sources. IEEE Trans. on Information Theory,1973, 19(4): 471–480. [doi: 10.1109/TIT.1973.1055037]

2Wyner A, Ziv J. The rate-distortion function for source coding with side information at the decoder. IEEE Trans. on Information Theory, 1976, 22(1): 1–10. [doi: 10.1109/TIT.1976.1055508]

3Gehrig N, Dragotti PL. Symmetric and asymmetric Slepian-Wolf codes with systematic and nonsystematic linear codes.IEEE Communications Letters, 2005, 9(1): 61–63. [doi:10.1109/LCOMM.2005.1375242]

4許迪佳. 基于LDPC的分布式信源編碼關(guān)鍵技術(shù)研究[碩士學(xué)位論文]. 北京: 北京郵電大學(xué), 2015.

5吳憲云. 分布式信源編碼關(guān)鍵技術(shù)研究[博士學(xué)位論文]. 西安: 西安電子科技大學(xué), 2012.

6Pradhan SS, Ramchandran K. Distributed source coding using syndromes (DISCUS): Design and construction. IEEE Trans. on Information Theory, 2003, 49(3): 626–643. [doi:10.1109/TIT.2002.808103]

7Arikan E. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Trans. on Information Theory,2009, 55(7): 3051–3073. [doi: 10.1109/TIT.2009.2021379]

8宋雷. 極化碼SC譯碼算法研究[碩士學(xué)位論文]. 哈爾濱: 哈爾濱工業(yè)大學(xué), 2015.

9陳國泰, 張朝陽, 張亮, 等. 系統(tǒng)極化碼的置信傳播譯碼性能分析. 電訊技術(shù), 2016, 56(8): 839–843.

10?nay S. Polar codes for distributed source coding. Turkey:Bilkent University, 2014.

11Arikan E. Systematic polar coding. IEEE Communications Letters, 2011, 15(8): 860–862. [doi: 10.1109/LCOMM.2011.061611.110862]

12馬丕明, 袁東風(fēng), 楊秀梅, 等. 低密度校驗碼及其在圖像傳輸中的應(yīng)用. 電子與信息學(xué)報, 2004, 26(8): 1269–1275.

Distributed Source Coding Using Polar Codes

CAI Li-Ping, SUN Yue
(College of Computer and Communication Engineering, China University of Petroleum, Qingdao 266555, China)

This paper introduces the basic idea of distributed source coding and the construction method of classical distributed source coding. It discusses the joint channel distributed source encoding method with the new polar code. It realizes the joint polar code-distributed lossless source encoding system and finally applies the method to the image transmission and the simulation experiment proves its feasibility.

distributed source coding; joint channel-distributed source coding; polar code; joint polar code-distributed loseless source coding; image transmission

蔡麗萍,孫悅.基于極化碼的分布式信源編碼.計算機系統(tǒng)應(yīng)用,2017,26(7):273–277. http://www.c-s-a.org.cn/1003-3254/5862.html

2016-11-08; 收到修改稿時間: 2016-12-15