基因演算法輔助之高效能奇偶校驗碼解碼演算法以及其解碼器架構之設計

Design of High-Performance LDPC Decoders Based on a New Genetic-Aided Message Passing Decoding Algorithm

呂怡德(Yi-Te Lu)

指導教授 ： 陳紹基

國立交通大學/電機學院/電子工程系所/碩士(2011年)

https://doi.org/10.6842/NCTU.2011.00918

摘要

低密度奇偶校驗碼(Low-Density Parity-Check Code)最早是由R.G. Gallager博士在1962於其博士論文發表，其解碼效能十分的逼近向農極限 (Shannon limit)。因此近年來，LDPC逐漸被許多通訊標準所指定採用的錯誤更正碼技術。
在LDPC解碼演算法方面，MP (Message Passing) algorithm family 的效能雖然已經很好，但仍與最大相似解碼的解碼效能有段差距，本論文運用基因演算法的概念搭配MP演算法，提出了一個GA-MP演算法，它的解碼效能在不同的parity check matrices下都能逼近最大相似解碼。此外，因為最大相似解碼的運算複雜度很高，因此不容易從模擬中快速得到。為了在模擬中能快速獲得最大相似解碼的效能，本論文也提出了一個理想的最大相似解碼，此理想的最大相似解碼的效能一般情形下會優於最大相似解碼。我們在EG-LDPC (63, 37, 8, 8)的模擬下發現GA-MP演算法的解碼效能幾乎完全逼近理想的最大相似解碼。因此在此EG-LDPC (63, 37, 8, 8)代表我們的GA-MP演算法的解碼效能有可能已經超越最大相似解碼的解碼效能。另外在802.16e (576,288)模擬下，GA-MP演算法世代數設為1000可獲得0.5dB的效能提升。且它的解碼效能會隨世代數上升不斷提高，克服了一般MP algorithm在iteration數上升至一定程度後，解碼效能就不能繼續提升的問題。
除此之外，目前現存文獻中所提出的逼近最大相似解碼的演算法皆難以在可接受的硬體面積需求內實現。我們提出的GA-MP有著高效能與低複雜度的優點，且針對EG-LDPC (63, 37, 8, 8)，實現了一個GA-MP解碼器，在UMC 90 製程與200MHz時脈下，其chip gate count為379k，功率消耗為67.556 mW。且其解碼效能十分接近floating-point 之模擬結果。

關鍵字

基因演算法 ； 奇偶校驗碼解碼演算法

並列摘要

Low-Density parity check (LDPC) code was first introduced by Gallager, which can achieve performance close to Shannon bound. In the recent years, LDPC codes have been adopted by many communication systems.
In the decoding algorithm of LDPC codes, although MP (Message Passing) algorithm family has already a good decoding performance, it does not perform as well as maximum likelihood (ML) decoding. This thesis proposed a GA-MP algorithm based on the concept of genetic algorithm and MP algorithm. The decoding performance of GA-MP decoding is close to the ML decoding for different parity check matrices. Besides, due to the high computational complexity of ML decoding, the solution of ML decoding is hard to obtain in simulation. In order to obtain the solution of ML decoding in simulation rapidly, this thesis proposed a fast obtainable super ML decoding to approximate the ML decoding. The decoding performance of proposed super ML decoding is better than or equal to ML decoding but with low computation complexity. We find that the decoding performance of GA-MP decoding is almost completely close to the super ML decoding for EG-LDPC (63, 37, 8, 8). In addition, with the generations set to 1000 for GA-MP algorithm, GA-MP algorithm has about 0.5 dB performance improvement from the original MP algorithm for 802.16e(576, 288). The decoding performance of GA-MP decoding gets better when the maximum number of generations (iterations) goes larger. It solves the problem that when the iteration number of a MP algorithm increases to some extent, the decoding performance is no longer improved as the iteration number increases.
Besides, at present, there is no proposed algorithm of extent literature approaching to the maximum likelihood decoding can be implemented for the acceptable area of hardware design. The proposed GA-MP decoder design has the advantages of high decoding performance and low complexity. In this thesis, we implemented the GA-MP decoder for EG-LDPC (63, 37, 8, 8). By using UMC 90 and setting the maximum clock frequency to 200MHz, the total gate count of the proposed design is about 379K, the power consumption is about 67.551(mW), and the decoding performance is very close to the decoding performance of floating-point.

並列關鍵字

LDPC ； MP ； GA

參考文獻

[2] Air Inference for fixed and mobile broadband wireless access systems, IEEE Std.802.16e, 2005.

system --Local and metropolitan area networks, IEEE Std. 802.11n, 2007.

[4] I.C. Park and S.H. Kang, “Scheduling algorithm for partially parallel architecture of LDPC decoder by matrix permutation,” IEEE ISCAS, pp. 5778-5781, May 2005.

[5] D. J. C. Mackay, “Good error-correcting codes based on very sparse matrices,”IEEE Trans. Inform. Theory, vol. 45, pp. 399-431, Mar. 1999.

[6] X. Y. Hu, E. Eleftheriou, D. M. Arnold, and A. Dholakia, “Efficient implementation of the sum-product algorithm for decoding LDPC codes,” IEEE GLOBECOM’01, vol. 02, pp. 1036-1036E, Nov. 2001.