臺灣博碩士論文加值系統

低密度同位元檢測碼(Low density parity check codes, LDPC)是一種線性區塊碼，且被證實在可加性白色高斯雜訊通道(additive white Gaussian noise channel, AWGN)下，利用遞迴解碼(iterative decoding)可以達到和Shannon Limit相近的效能。因此，在各類通訊系統或資料儲存系統之高可靠度的要求下，LDPC碼變成是渦輪碼(Turbo code)的另一個強力競爭者。目前，LDPC碼被廣泛使用在各種通訊系統上，例如：4G、802.11n、802.16e、MIMO-OFDM…。

但對於實際的應用上，如何設計一個較短且性能好的LDPC碼變成一項重要的課題。目前大部分LDPC碼的設計是利用隨機的建構技術，因此需要較長的碼長才能達到較佳之性能。但由於隨機的建構，使得這類型的碼缺乏結構，而造成很嚴重的問題，如：在編碼與解碼時，必須存取一個相當大的同位元檢測矩陣 ，而造成編碼的複雜度變的相當高。因此，如果能以代數的方法加以建構，將會使得編碼變得容易，且性能分析也會變得簡單。

在此論文中，我們提出一個新的且具有代數結構的LDPC碼，稱之為穿插式類循環低密度同位元檢測碼(Interleaved Quasi-Cyclic Low Density Parity Check Code)。其主要架構是由類循環LDPC碼與假隨機穿插器組合而成，且在建構過程中，我們使用了電腦搜尋方法去避免長度為4的迴路出現。而此建構方式的優點在於其編碼的複雜度比一般隨機建構的複雜度來得低。最後，我們將針對較長的碼長進行效能分析，以及與有限幾何LDPC碼做個效能比較。

Low-density parity check (LDPC) codes are one class of linear block codes and provide near capacity performance with iterative decoding at the AWGN channel when the code length is large. Therefore, LDPC codes have become strong competitors to Turbo codes for error control in many communication and digital storage systems where high reliability is required. Until now, LDPC codes are widely used in many communication systems, for example, 4G, 802.11n, 802.16e, MIMO-OFDM and so on.

However, for the practical applications, how to design short and powerful LDPC codes becomes an important subject. Most methods for designing LDPC codes are based on random construction techniques. But the random LDPC codes usually don’t have sufficient structure to allow simple encoding and a significant amount of memory is needed to store their parity check matrices. Therefore, if these codes could be built by algebraic methods, these problems could be solved.

In the thesis, we construct a new LDPC codes with algebraic structure, called “Interleaved Quasi-Cyclic Low Density Parity Check Codes”. These codes consist of the quasi-cyclic LDPC codes and some pseudo-random Interleavers. And we use computer search to keep that the girth of these codes is larger than four during the construction. The advantage of these codes is that this encoder complexity is lower than that of random construction and these codes also have good performance. Finally, we would focus on the performance of high code length and have a comparison with finite geometry LDPC codes.

論文內容
致謝 i
中文摘要 ii
英文摘要 iii
圖目錄 vi
表目錄 vii

第一章 前言 1
1.1 研究動機 1
1.2 論文架構 2
第二章 低密度同位檢測碼( Low Density Parity-Check codes, LDPC ) 3
2.1 LDPC介紹 3
2.2 LDPC碼表示法 3
2.2.1 矩陣表示法 3
2.2.2 圖像表示法 4
2.3 LDPC碼的建構方法 6
2.3.1 Gallager codes 7
2.3.2 Mackay codes 7
2.3.3 有限幾何碼( Finite Geometry code) 8
2.3.4 陣列碼(Array code) 9
2.3.5 組合式LDPC碼( Combinatorial LDPC code) 9
第三章 具有架構的LDPC碼 11
3.1 穿插式類循環LDPC碼 ( Interleaved Quasi-Cyclic LDPC codes) 11
3.1.1 同位檢測矩陣 之模型 12
3.1.2 同位檢測矩陣 之設計條件 15
3.2權重函數( Weight Enumerating Function, WEF) 18
第四章 遞迴解碼演算法 21
4.1.概述 21
4.2 機率域-和積演算法( Probability-domain SPA decoder) 23
4.3 對數域-和積演算法( Log-domain SPA decoder) 27
4.4 降低複雜度解碼器( Reduced complexity Decoder) 31
4.4.1 最小和解碼器( Min-Sun Decoder) 31
第五章 模擬結果與效能比較 32
第六章 結論與未來發展 50
參考文獻 51
附錄 54

[1]R. G. Gallager, “Low-density parity-check codes,” IRE Trans. Inform. Theory, vol. IT-18, pp. 21-28, Jan. 1962.
[2]R. G. Gallager, Low-Density Parity Check Codes, Cambridge, MA: MIT Press, 1963.
[3]R. M. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inform. Theory, vol. IT-27, pp. 533–547, Sept. 1981.
[4]D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electron. Lett., vol. 32, no. 18, pp. 1645–1646, 1996.
[5]M. C. Davey and D. J. C. MacKay, “Low density parity check codes over GF(q) ,” IEEE Commun. Lett., vol. 2, pp. 165–167, June 1998.
[6]D. J. C. MacKay, “Gallager codes that are better than turbo codes,” in Proc. 36th Allerton Conf. Communication, Control, and Computing, Monticello, IL, Sept. 1998.
[7] , “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, vol. 45, pp. 399–432, Mar. 1999.
[8] T. Richardson, A. Shokrollahi, and R. Urbanke, “Design of capacity-approaching irregular codes,” IEEE Trans. Inform. Theory, vol. 47, pp.619–637, Feb. 2001.
[9] T. Richardson and R. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding,” IEEE Trans. Inform. Theory, vol. 47, pp. 599–618, Feb. 2001.
[10]R. M. Tanner, “A [155,64,20] sparse graph (LDPC) code,” in Proc. IEEE International Symposium on Information Theory, Sorrento, Italy, June 2000.
[11]R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, and D. J. Costello, “LDPC block and convolutional codes based on circulant matrices,” IEEE Trans. Inform. Theory, vol. 50, pp. 2966-2984, Dec. 2004.
[12]Y. Kou, S. Lin, and M. Fossorier, “Low density parity check codes based on finite geometries: A rediscovery,” in Proc. 2000 IEEE Int. Symp. In¬formation Theory, Sorrento, Italy, June 25–30, 2000.
[13] , “Construction of low density parity check codes: A geometric ap¬proach,” in Proc. 2nd Int. Symp. Turbo Codes and Related Topics, Brest, France, Sept. 4–7, 2000, pp. 137–140.
[14]K. Kou, S. Lin, and M. Fossorier, “Low density parity check codes based on finite geometries: A rediscovery and new results,” IEEE Trans. Inform. Theory, vol. 47, pp.2711-2736, Nov. 2001.
[15]J. Rosenthal and P. O. Vontobel, “Construction of LDPC codes using Ramanujam graphs and ideas from Margulis,” in Proc. 38th Allerton Conf. Communications, Control, and Computing, Monticello, IL, Oct. 2000, pp. 248-257.
[16]R. M. Tanner, “On quasi-cyclic repeat accumulate codes,” in Proc. 37th Allerton Conf. Communications, Control, and Computing, Monticello, IL, Oct. 1999, pp. 249-259.
[17]M. Fossorier, “Quasi-cyclic low-density parity-check codes from circulant permutation matrices,” IEEE Trans. Inform. Theory, to be published.
[18]J. L. Fan, “Array codes as low-density parity check codes,” in Proc. 2nd Int. Symp. Turbo codes and Related Topics, Brest, France, Sept. 2000, pp. 543-546.
[19]F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Factor graphs and the sum–product algorithm,” IEEE Trans. Inform. Theory, vol. 47, pp. 498–519, Feb. 2001.
[20]M. Fossorier, M. Mihaljevic, and H. Imai, “Reduced complexity iterative decoding of low density parity check codes,” IEEE Trans. Commun., vol. 47, pp. 673–680, May 1999.
[21]R. Lucas, M. Fossorier, Y. Kou, and S. Lin, “Iterative decoding of one-step majority logic decodable codes based on belief propagation,” IEEE Trans. Commun., vol. 48, pp. 931–937, June 2000.
[22]D. J. C. Mackay, http://wol.ra.phy.cam.ac.uk/mackay.
[23]W. W. Peterson and E. J. Weldon, Jr., Error-Correcting Codes, 2nd ed. Cambridge, MA: MIT Press, 1972.
[24]S. Lin and D. J. Costello, Jr., Error Control Coding: Fundamentals and Applications. Englewood Cliffs, NJ: Prentice-Hall, 1983.
[25]J. L. Massey, Threshold Decoding. Cambridge, MA: MIT Press, 1963.
[26]V. D. Kolesnik, “Probability decoding of majority codes,” Probl. Pered. Inform., vol. 7, pp. 3–12, July 1971.
[27]N. Wiberg, Codes and Decoding on General Graphs. PhD thesis, University of Linkoping, Sweeden, 1996.
[28]E. Eleftheriou and S. Ölçer, “Low-density parity-check codes for digital subscriber lines,” Proc. 2002 Int. Conf. on Comm., pp.1752-1757., April-May, 2002.
[29]B. Vasic, “Combinatorial constructions of low-density parity-check codes for iterative decoding,” Proc. 2002 IEEE Int. Symp. Inf. Theory, p.312, June/July 2002.
[30]S. Johnson and S. Weller, “Construction of low-density parity-check codes from Kirkman triple systems,”Proc. 2001 IEEE GlobeCom Conf., pp. 970-974, Nov. 2001,
[31]R. M. Tanner, D. Sridhara, and T. Fuja, “A class of group-structured LDPC codes,” in Proc. 6th Int. Symp. Commun. Theory and Applications, Ambleside, UK, July, 15-20 2001, pp. 365-370.
[32]Dengsheng Lin, Qiang Li, Shaoqian Li, “Semi-random Construction of Quasi-Cyclic LDPC Codes,” Communications, Circuits and Systems, 2005. Proceedings. 2005 International Conference on Volume1, 27-30 May 2005 Page(s):9-13 Vol. 1.
[33]G. C. Clark, Jr. and J. B. Cain, Error-correction coding for digital communications, Plenum Press, New York, 1981.