低密度同位元檢查碼是一種線性方塊碼。其擁有的低密度同位元檢查矩陣，使得此種編碼能夠有相當好的反覆解碼機制，已有研究證明，當碼長接近於無限大時，其效能能夠貼近省農限制。但由於其最佳化演算法“和積演算法”需要使用到非線性函式，使得和積演算法在硬體實現上有一定的難度，於是“最小和演算法”被提出，其省略和積演算法中非線性函式，降低了不少的複雜度，但是相對的，其性能也降低了不少。近幾年來，有許多的研究專注在於進而改善最小和演算法，使其效能逼近最佳化演算法，例如：正規化最小和演算法、補償式最小和演算法、適應性正規化最小和演算法…等等。本篇論文提出一種適應性補償式最小和演算法，在不增加太多複雜度的情形下，其性能優於最小和演算法，跟上述改進演算法比較之下，更能有效的貼近和積演算法。

The family of low density parity check codes belongs to linear block codes. Due to its sparse parity check matrix, it can be easily decoded by iterative decoding. It has been proved that when the code lengths approach infinite, it provides performance near Shannon limit. But the optimal decoding algorithm, which we call “Sum Product Algorithm”, needs to calculate a logarithmic function. However it’s difficult to implement the logarithmic function in hardware. The sub-optimal algorithm, called “Min-Sum algorithm”, omits the logarithmic function used in the Sum-Product Algorithm. It reduces some complexity in implementing the logarithmic function, but it also results in performance degradation. In recent years, much works are concentrate on improving the Min-Sum Algorithm such that its performance can be more close to the Sum-Product Algorithm. For example: Normalized Min-Sum algorithm (NMS), Offset Min-sum algorithm (OMS) and Adaptive Normalized Min-sum algorithm (ANMS). In this thesis, we propose a scheme called Modified Adaptive offset Min-sum algorithm (MAOMS). Without increasing too much complexity, the MAOMS algorithm outperforms the MS algorithm. Comparing with the above methods, the MAOMS
algorithm performs more closely to the Sum-product algorithm.

[1] C.E. Shannon, A Mathematical Theory of Communication, Bell Syst. Tech. J., pp. 379-423 (Part1); pp. 623-56 (Part 2). July 1948.

[2] R. G. Gallager, Low Density Parity Check Codes, MIT Press, Cambridge, MA, 1963.

[3] R. M. Tanner, “ A recursive approach to low complexity codes.” IEEE Tras. Inform. Theory, vol. IT-27, no. 5, pp.399-431, Sept 1981.

[4] N. Wiberg, “Codes and decoding on general graphs,” Ph.D. dissertation, Linkoping University, Sweden, 1996.

[5] J. Chen and M. P. C. Fossorier, “Near-optimum universal belief propagation based decoding of low-density parity check codes,” IEEE Trans. Commun., vol. 50, no. 3, pp 406-414, Mar. 2002.

[6] M. Jiang, C. Zhao, L. Zhang, and E. Xu, “Adaptive Offset Min-Sum Algorithm for Low-Density Parity Check Codes.” , IEEE Commun. Letters, vol. 10, no. 6, June 2006.

[7] Y. C. Liao, C. C. Lin, C. W. Liu, and H. C. Chang, “A Dynamic Normalization Technique for Decoding LDPC Codes.”, IEEE SIPS 2005.

[8] R. M. Tanner, D. Sridhara, and T. Fuja, “ A class of group-structured LDPC codes,” in Proc. ISTA, Ambleside, England, 2001.

[9] 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.

[10] M. P. C. Fossorier, “Quasi-Cyclic Low-Density Parity Check Codes From Circulant Permutation Matrices,” IEEE Trans Information Theory, VOl. 50, N0. 8, pp. 1788-1793, Aug. 2004.

[11] D. J. C. Mackay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” VOL. 32, pp. 1645-1646, July 12, 1996.

[12] D. J. C. Mackay and M.C. Davey, Evalution of Gallager for short block length and high rate applications, VOL. 123, ch.5, pp.113-130, IMA Volumes in Mathematics and its Applications, 2001.