臺灣博碩士論文加值系統

Low-density parity check (LDPC) codes have attracted tremendous research interest and many recent communication standards have included LDPC codes, but most of the recent applications are focused only on binary LDPC codes, applications about nonbinary LDPC codes are very limited due to its decoding complexity. In this thesis, a decoder architecture for nonbinary QC-LDPC codes is presented, this decoder architecture is flexible for nonbinary LDPC codes with quasicyclic form. The multiplication over Galois field is efficiently handled through a proposed permutation network for the check node processing. With a proposed filtering method combining with an efficient Minimum Finder architecture, a selective-input implementation for decoding of nonbinary LDPC codes is employed in the architecture design, which can increase the throughput. In order to increase the convergence speed, hence, reduce the numbers of iteration required for achieving a given performance, decoding of nonbinary LDPC codes with layered scheduling is also considered in our architecture design. Using a UMC 90-nm CMOS process, we implement a decoder for (248, 137) nonbinary LDPC code over GF(32) for demonstrating our ideas.

低密度奇偶檢查碼(LDPC codes)已經在各種不同的應用中引起了大家廣泛的研究興趣，並且也被不少的通訊標準所引用與討論，但是大部份目前所涉及到的應用與通訊標準都僅集中於二位元的低密度奇偶檢查碼的討論，而非二位元低密度奇偶檢查碼因為受限於它的解碼複雜度和在硬體實現上的難度，所以目前甚少被提及。但是，非二位元低密度奇偶檢查碼的高效解碼性能卻引起了我們的研究興趣。在本篇論文中，我們提出了一個非二位元類循環低密度奇偶檢查碼的解碼架構，此解碼架構對於任何非二位元類循環低密度奇偶檢查碼都有很高的適應性。在解碼架構中，我們所提出的旋轉網路(permutation network)架構有效的處理了在檢查點(check node)運算中涉及到伽羅瓦代數體(Galois field)的乘法運算，因此大量的減少了硬體架構中在處理乘法運算所需要付出的複雜度。另外，我們也提出了一個最小尋找器的硬體架構，此最小尋找器架構結合所規劃的過濾方法，我們在解碼架構中實現了非二位元類循環低密度奇偶檢查碼的選擇式演算法，進而減少檢查點運算中所需要的處理時間，提高吞吐量。此外，有鑒於希望加快解碼的收斂速度而減少欲達到相同解碼性能所需要的疊代次數，在我們的解碼架構中也引用了分層解碼的方式。最後，我們使用UMC 90-nm CMOS製程實現了一個(248,137),在GF(32)下的非二位元低密度奇偶檢查碼解碼架構來展示我們的構想。

1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Decoding of Nonbinary LDPC Codes 5
2.1 Parity-check constraints for nonbinary LDPC codes . . . . . . . 5
2.2 Reviews of Min-Sum Decoding Algorithm . . . . . . . . . . . . . 6
2.3 Reviews of Min-Max Decoding Algorithm . . . . . . . . . . . . . 8
2.4 Min-Max decoding algorithm using layered scheduling . . . . . . 8
3 Proposed permutator for Selective-input Min-Max Decoding
Algorithm 13
3.1 Challenge of an e±cient implementation of the Min-Max algorithm 13
3.2 Proposed permutator design . . . . . . . . . . . . . . . . . . . . 15
3.3 Selective-input Min-Max decoding Algorithm using the Pro-
posed Permutator . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Proposed Decoder Architecure for Nonbinary QC-LDPC codes 27
4.1 APP memory bank and C2V memory bank . . . . . . . . . . . . 29
4.2 The Iterative Decoding Processor . . . . . . . . . . . . . . . . . 30
4.3 Decoder architecture for the (248; 137) nonbinary LDPC code
over GF(q) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5 Performance Evaluation 38
5.1 Implementation results . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 Comparison with others related work . . . . . . . . . . . . . . . 41
6 Conclusions 44

[1] R. G. Gallager, \Low density parity check codes," IRE Trans. Inform.
Theory, vol. IT-8, pp. 21-28, Jan. 1962.
[2] M. C. Davey and D. J. C. Mackay, \Low-density parity check codes over
GF(q)," IEEE Commun. Lett., vol. 2, no. 6, pp. 165-167, Jun. 1998.
[3] C. Spagnol and W. Marnane, \A class of quasi-cyclic LDPC codes over
GF(2m)," IEEE Trans. Commun., vol. 57, no. 9, pp. 2524-2527, Sept.
2009
[4] L. Zeng, L. Lan, Y. Y. Tai, S. Song, S. Lin, and K. Abdel-Gha®ar, \Con-
structions of nonbinary quasi-cyclic LDPC codes: a ¯nite ¯eld approach,"
IEEE Trans. Commun., vol. 56, no. 4, pp. 545-554, Apr. 2008.
[5] L. Zeng, L. Lan, Y. Y. Tai, B. Zhou, S. Lin, and K. Abdel-Gha®ar,
\Construction of nonbinary cyclic, quasi-cyclic and regular LDPC codes:
a ¯nite geometry approach," IEEE Trans. Commun., vol. 56, no. 3, pp.
378-387, Mar. 2008.
[6] S. Song, B. Zhou, S. Lin, and K. Abdel-Gha®ar, \A uni¯ed approach to
the construction of binary and nonbinary quasi-cycle LDPC codes based
on ¯nite ¯elds ," IEEE Trans. Commun., vol. 57, no. 1, pp. 84-93, Jan.
2009
[7] B. Zhou, J. Kang, Y. Y. Tai, S. Lin, Z. Ding, \High performance non-
binary quasi-cyclic LDPC codes on euclidean geometries," IEEE Trans.
Commun., vol. 57, no. 5, pp. 1298-1311, May 2009.
[8] B. Zhou, J. Kang, S. Song, S. Lin, and K. Abdel-Gha®ar, \Construction
of non-binary quasi-cyclic LDPC codes by arrays and arrays dispersions,"
IEEE Trans. Commun., vol. 57, no. 10, pp. 1652-1662, Jun. 2009.
[9] D. J. C. Mackay, and M. C. Davey, \Evaluation of Gallager codes of short
block length and high rate applications," in Proc. IMA international Conf.
Mathematics its Applications: Codes, Systems Graphical Models, pp. 113-
130, Springer-Verlag, New York, 2000
[10] L. Barnault and D. Declercq, \Fast decoding algorithm for LDPC over
GF(2q)," in ITW2003, Paris, France, March 31-April 4, 2003
[11] H. Song, J. R. Cruz, \Reduced complexity decoding of Q-ary LDPC codes
for magnetic recording," IEEE Trans. Magn., vol. 39, no. 2, pp. 1081-1087,
Mar. 2003.
[12] W. Chang and J. R. Cruz, \Performance and decoding complexity of
nonbinary LDPC codes for magnetic recording," IEEE Trans. Magn., vol.
44, no. 1, pp. 211-216, Jan. 2008.
[13] H. Wymeersch, H. Steendam, and M. Moeneclaey, \Log-domain decoding
of LDPC codes over GF(q)," in Proc. IEEE int. Conf. Commun., Paris,
France, pp. 772-776, Jun. 2004.
[14] D. Declercq and M. Fossorier, \Decoding algorithms for nonbinary LDPC
codes over GF(q)," IEEE Trans. Commun., vol. 55, no. 4, pp. 633-643,
Apr. 2007.
[15] V. Savin, \Min-Max decoding for non binary LDPC codes," in Proc. IEEE
int Symp. Inf. Theory, Toronto, Canada, pp. 960-964, Jul. 2008.
[16] M. M. Mansour and N. R. Shanbhag, \High-throughput LDPC decoders,"
IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 11, no. 6, pp.
976-996, Dec. 2003.
[17] D. E. Hocevar, \A reduced complexity decoder architecture via layered
decoding of LDPC codes," in Proc. IEEE Workshop on Signal Processing
Systems, pp. 107-112, Oct. 2004.
[18] Y. L. Wang, Y. L. Ueng, C. L. Peng, and C. J. Yang, \Processing-task
Arrangement for a Low-complexity Full-mode WiMAX LDPC Codec,"
accepted by IEEE Trans. Circuits Syst. I, Augest 2010.
[19] Y. Liu, J. Ning and J. Yuan, \Modi¯ed min-sum algorithm with threshold
¯ltering for nonbinary LDPC codes over GF(q)," in ISITA2008, Auckland,
New Zealand, 7-10, December, 2008
[20] C. Spagnol, E.Popovici, and W. Marnane, \FPGA implementations of
LDPC over GF(2m) decoders," Proc. IEEE SiPS, 2007, pp. 273-278.
[21] C. Spagnol, E.Popovici, and W. Marnane, \Hardware implementation of
GF(2m) LDPC decoders," IEEE Trans. Circuits Syst. I, vol. 56, no. 12,
pp. 2609-2620, Dec. 2009.
[22] A. Voicila, D. Delercq, F. Verdier, M. Fossorier and P. Urard, \Architec-
ture of a low-complexity non-binary LDPC decoder for high order ¯elds,"
in Proc. IEEE Int. Symp. Commun. and Inf. Technologies(ISCIT), Syd-
ney, Australia, pp. 1201-1206, Oct. 2007.
[23] J. Lin, J. Sha, Z. Wang, and L. Li, \E±cient decoder design for nonbinary
quasicyclic LDPC codes," IEEE. Trans. Circuits Syst. I, vol. 57, no. 5,
pp. 1071-1082, May 2010.
[24] A. Darabiha, A. C. Carusone, and F. R. Kschischang, \A bit-serial ap-
proximate min-sum LDPC decoder and FPGA implementation," Proc.
IEEE ISCAS 2006, Sept 2006.