在這篇論文中，是在研究如何建構出不同最短周長的半循環式低密度同位元檢查碼。這些半循環式低密度同位元檢查碼是利用一次碰撞序列(one-coincidence sequence; OCS)所構造出來的，我們簡稱它們為OCS-LDPC碼。在這邊研究三種不同的一次碰撞序列，且每一個一次碰撞序列都可以產生出一種半循環式低密度同位元檢查碼。因為對於半循環式低密度同位元檢查碼的效能來說，最短周長是個重要的影響因子，因此如何去構造高值最短周長是我們感興趣的主題。一般來說，在同位元檢查碼中循環架構是由循環式排列矩陣裡的位移值所決定的，而且在Tanner圖中的每一個循環都有一個相對應的循環控制方程式(cycle-governing equation; CGE)。我們提供了一個方法能夠在(j, k) OCS-LDPC碼中，有系統性的找出循環長度為6, 8, 10的循環控制方程式。然後，藉由這些循環控制方程式再搭配一個有效率的演算法可以獲得適當的位移植，以便我們去構造高值最短周長的OCS-LDPC碼。模擬結果證明出OCS-LDPC碼可以藉由提高最短周長使的在可加性高斯白雜訊通道裡有著明顯的訊號雜訊比增益。

In this thesis, the construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes of different girth is investigated. These QC-LDPC codes are derived from the one-coincidence sequence (OCS) families and are named OCS-LDPC codes for brevity. Three different OCS families are investigated, and each OCS family determines a particular family of QC-LDPC codes. Since the girth of the QC-LDPC code is an important factor in determining its performance, how to construct a QC-LDPC code of large girth is an interesting topic. In general, the cycle structures in these LDPC codes are determined by the shift values of circulant permutation matrices, and the existence of cycles in the corresponding Tanner graph is governed by certain cycle-governing equations (CGEs). We provide a method to systematically find out the CGEs for the (j, k) OCS-LDPC codes of girth 6, 8, and 10. Then, an efficient algorithm is used to obtain the proper shift values for constructing the OCS-LDPC codes of large girth. Simulation results show that significant gains in signal-to-noise ratio (SNR) over an additive white-Gaussian noise (AWGN) channel can be obtained by increasing the girth of the OCS-LDPC codes.

[1] R. Gallager, “Low-density parity-check codes,” IRE Trans. Inform. Theory, vol. 8, no. 1, pp. 21-28, Jan. 1962.
[2] 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, Aug. 1996.
[3] N. Alon, M. Luby, “A linear time erasure-resilient code with nearly optimal recovery,” IEEE Trans. Inform. Theory, vol. 42, pp. 1732-1736, Nov. 1996.
[4] D. MacKay, “Good error correcting code based on very sparse matrices,” IEEE Trans. Inform. Theory, vol. 45, pp. 399-431, Mar. 1999.
[5] Y. 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.
[6] 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(12), pp. 2966-2984, Dec. 2004.
[7] C.M. Huang, J.F. Huang; C.C. Yang, “Construction of quasi-cyclic LDPC codes from quadratic congruences,” IEEE Commun. Lett., vol. 12, pp. 313-315, Apr. 2008.
[8] M.P.C. Fossorier, “Quasi-cyclic low density parity check codes from circulant permutation matrices,” IEEE Trans. Inform. Theory, vol. 50, pp. 1788-1794, Aug. 2004.
[9] O. Milenkovic, N. Kashyap, and D. Leyba, “Shortened array codes of large girth,” IEEE Trans. Inf. Theory, vol. 52, no. 8, pp. 3707-3722, Aug. 2006.
[10] J.K. Moura, J. Lu, and H. Zhang, “Structured LDPC codes with large girth,” IEEE Signal Process. Mag., vol. 21, no. 1, pp. 42-55, Jan. 2004.
[11] B. Vasic and O. Milenkovic, “Combinatorial constructions of low-density parity-check codes for iterative decoding,” IEEE Trans. Inf. Theory, vol. 50, no. 6, pp. 1156-1176, Jun. 2004.
[12] S. Kim, J.S. No, H. Chung, and D.J. Shin, “On the girth of Tanner (3, 5) quasi-cyclic LDPC codes,” IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1739-1744, Apr. 2006.
[13] J.-L. Kim, U. Peled, I. Perepelista, V. Pless, and S. Friedland, “Explicit construction of families of LDPC codes with no 4-cycles,” IEEE Trans. Inf. Theory, vol. 50, no. 10, pp. 2378-2388, Oct. 2004.
[14] J.L. Fan, “Array codes as low-density parity-check codes,” in Proc. 2nd Int. Symp. Turbo Codes and Related Topics, Brest, France, Sep. 2000, pp. 553-556.
[15] R. M. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Inf. Theory, vol. 27, no. 5, pp. 533-548, Sep. 1981.
[16] J. Fan, “Array codes as low-density parity-check codes,” in Proc. 2nd Int. Symp. on Turbo Codes & Related Topics, Brest, France, 2000.
[17] R. M. Tanner et. al., “LDPC Block and Convolutional Codes Based on Circulant Matrices,” IEEE Trans. Information Theory, vol. 50, NO. 12, pp. 2966-2984, Dec. 2004.
[18] Z. Li, L. Chen, L. Zeng, S. Lin, and W. Fong, “Efficient encoding of quasi-cyclic low-density parity check codes,” IEEE Trans. Commun., vol. 54, no. 1, pp. 71–81, Jan. 2006.
[19] J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible In-ference. Morgan Kaufmann Publishers, Inc., 1988.
[20] Z. Kostic, E.L. Titlebaum, “The design and performance analysis for several new classes of codes for optical synchronous CDMA and for arbitrary-medium time-hopping synchronous CDMA communication systems,” IEEE Trans. Commun., vol. 42, pp. 2608-2617, Aug. 1994.
[21] C.C. Yang, “Optical CDMA Passive Optical Network Using Prime Code With Interference Elimination,” IEEE Photon. Technol. Lett., vol. 19, no. 7, pp. 516-518, Apr. 2007.
[22] N. Miladinovic and M. Fossorier, “Systematic recursive construction of LDPC codes,” IEEE Commun. Lett., vol. 8, no. 5, pp. 302-304, May. 2004.
[23] Z. Li and B.V.K.V. Kumar, "A class of good quasi-cyclic low-density parity check codes based on progressive edge growth graph," in Proc. IEEE 38th Conf. Signals, Systems and Computers, Pacific Grove, CA, Nov. 2004, pp.1990-1994.
[24] X.-Y. Hu, E. Eleftheriou, and D.-M. Arnold, “Progressive Edge-Growth Tanner Graphs,” IEEE Global Telecommunications Conference 2001, vol. 2, pp. 995-1001, 25–29 November, 2001.