臺灣博碩士論文加值系統

本論文針對二位元相關訊源，利用低密度奇偶查核碼具體實現Slepian-Wolf理論在分散式訊源編碼的應用。訊源相關模型以兩種虛擬通道模型表示，分別是二位元對稱通道與Gilbert通道。針對訊源編碼輸出的校驗子經由雜訊通道傳輸的問題，我們提出基於渦輪碼原則推導的疊代訊源通道解碼。我們將考慮兩種通道碼，低密度奇偶查核碼應用在分散式訊源編碼的校驗子生成以達到資料壓縮效果，而迴旋碼則用於提昇壓縮資料對抗通道雜訊的能力。模擬結果顯示基於低密度奇偶查核碼的分散式訊源編碼機制，配合疊代訊源通道解碼演算法，可同時兼顧高壓縮率及強健性能。

In this thesis, we study the use of low-density parity check (LDPC) codes for distributed source coding (DSC) of correlated binary sources. The Slepian-Wolf theorem states that there is no less in rate to compress two correlated sources using separate encoding, provided that the decoding is done jointly and the source correlation is available to both the encoder and decoder. Source correlation is modeled by two types of virtual channels: binary symmetric channel (BSC) and Gilbert channel. Also proposed is an iterative source-channel decoding (ISCD) algorithm for dealing with the Slepian-Wolf problem over noisy channel. An outer LDPC code is used to perform DSC, and an inner convolution code is used for enhancing the error protecting capability of the compressed data. Simulation results indicate the combined use of ISCD and LDPC-based DSC can provide error robustness as well as channel efficiency.

中文摘要 i
Abstract ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第1章 緒論 1
1.1 研究動機與方向 1
1.2 章節概要 3
第2章 基於LDPC矩陣的通道碼 4
2.1 LDPC矩陣 4
2.2 Tanner圖示法 5
2.3 LDPC矩陣的建構模式 7
2.3.1 Gallager法 7
2.3.2 隨機產生法 8
2.3.3 累進邊際成長演算法 9
2.4 LDPC通道碼的解碼演算法 11
2.4.1 機率域的加乘演算解碼器(Probability-Domain SPA Decoder) 13
2.4.2 對數域的加乘演算解碼器(Log-Domain SPA Decoder) 16
第3章 基於LDPC矩陣的分散式訊源編碼 19
3.1 分散式訊源編碼理論 19
3.2 無記憶性通道假設的Slepian-Wolf 壓縮 20
3.3 記憶性通道假設的Slepian-Wolf 壓縮 22
第4章 雜訊通道下Slepian-Wolf壓縮 28
4.1 擴展式的LDPC碼 28
4.2 迴旋碼與其通道解碼演算法 29
4.2.1 迴旋碼(Convolution Code) 30
4.2.2 BCJR解碼演算法 31
4.3 疊代式訊源通道解碼 33
第5章 實驗模擬與結果分析 38
5.1 傳輸無誤的實驗環境設定 38
5.1.1 BSC虛擬通道 38
5.1.2 Gilbert虛擬通道 40
5.2 傳輸有誤的實驗環境設定 41
5.2.1 BSC虛擬通道 41
5.2.2 Gilbert虛擬通道 43
第6章 結論與未來展望 46
參考文獻 48

[1] R. G. Gallager, “Low-Density Parity-Check Codes,” Cambridge, MA: MIT Press, 1963.
[2] V. Zyablov and M. Pinsker, “Estimation of the Error-Correction Complexity of Gallager Low-Density Codes,” Probl. Pered. Inform., vol. 11, pp. 23–26, Jan. 1975.
[3] G. A. Margulis, “Explicit Construction of Graphs without Short Cycles and Low Density Codes,” Combinatorica, vol. 2, no. 1, pp. 71–78, 1982.
[4] R. M. Tanner, “A Recursive Approach to Low Complexity Codes,” IEEE Trans. Inf.Theory,vol. IT-27, no. 5, pp. 533–547, Sep. 1981.
[5] M. Sipser and D. A. Spielman, “Expander codes,” IEEE Trans. Inform. Theory, vol. 42, pp. 1710–1722, Nov. 1996.
[6] D. J. C. MacKay and R. M. Neal, “Near Shannon Limit Performance of Low Density Parity Check Codes,” Electron. Lett., vol. 32, pp. 1645–1646, Aug. 1996.
[7] D. J. C. MacKay, “Good Error Correcting Codes Based on Very Sparse Matrices,” IEEE Trans. Inf. Theory, vol. 45, no. 2, pp. 399–431, Mar. 1999.
[8] S.Y. Chung, J. G. D. Forney, T. Richardson, and R. Urbanke, “On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit,” IEEE Commun.Lett., vol. 5, no. 2, pp. 58–60, Feb. 2001.
[9] X.Y. Hu, E. Eleftheriou, and D.M. Arnold, “Progressive Edge-Growth Tanner Graphs,” Proc. IEEE Global Telecommunications Conf. (GLOBECOM), San Antonio, TX, Nov. 2001, pp. 995–1001.
[10] X.Y. Hu, E. Eleftheriou, and D.M. Arnold, “Regular and Irregular Progressive Edge-Growth Tanner Graphs,” IEEE Trans. Inf. Theory, vol. 51, no. 1, pp. 386–398, Jan. 2005.
[11] D. Slepian and J. K. Wolf, “Noiseless Coding of Correlated Information Sources,” IEEE Trans. Inform. Theory, vol. 19, pp. 471-480, Jul. 1973.
[12] S. S. Pradhan and K. Ramchandran, "Distributed Source Coding Using Syndromes (DISCUS): design and construction," Proc. of Data Compression Conf.(DCC), pp. 158-167, Mar. 1999.

[13] T. Murayama, “Statistical Mechanics of Linear Compression Codes in Network Communication,” Europhysics Lett., 2001. Preprint

[14] A. D. Liveris, Z. Xiong and C. N. Geoghiades, “Compression of Binary Sources with Side Information Using Low-Density Parity-Check Codes,”2002.
[15] A. W. Eckford, F. R. Kschischang and S. Pasupathy, “Analysis of Low-Density Parity-Check Codes for the Gilbert-Elliott Channel, ” IEEE Trans.Inform. Theory, vol. 51, no. 11, pp. 3872-3889, Nov. 2005.
[16] R. Hu, R. Viswanathan, and J. Li, “A New Coding Scheme for the Noisy-Channel Slepian-Wolf Problem: Separate Design and Joint Decoding,” Proc. Globecom’04, Nov. 2004.
[17] David MacKay’s Gallager code resources, “Source Code for Progressive Edge Growth Parity-Check Matrix Construction, ” [Online]. Available:
http://www.cs.toronto.edu/~mackay/S0.html#PEG_ECC.html.
[18] Peiyu Tan, Kai Xie, and Jing Li, “Slepian-Wolf Coding Using Parity Approach and Syndrome Approach,” in Proceeding of 41st Annual Conference on Information Sciences and Systems, March 14-16 2007, Baltimore, MD, pp. 708-713.
[19] H.S. Wang and N. Moayeri, “Finite-state Markov Channel - A Useful Model for Radio Communication Channels, ” IEEE Trans. Vehicular Tech., vol. 44,no. 1, pp. 163-171, Feb. 1995.
[20] H.S. Wang and P.C. Chang, “On Verifying the First-Order Markovian Assumption for a Rayleigh Fading Channel Model, ” IEEE Trans. Vehicular Tech., vol. 45, no. 2, pp. 353-357, May 1996.
[21] L.R. Bahl, J. Cocke, F. Jeinek and J. Raviv, “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate, ” IEEE Trans. Inform. Theory, vol. IT-20, pp. 248-287, March 1974.
[22] D. J. C. MacKay and M. C. Davey, “Evaluation of Gallager Codes for Short Block Length and High Rate Applications,” Proc. IMA Workshop on Codes, Systems and Graphical Models, pp. 113-130, 1999.
[23] 陳柏強，「基於分散式訊源編碼架構的心電圖儀」，國立交通大學碩士論文，民國一百年。