臺灣博碩士論文加值系統

在非二位元低密度同位元檢查(Non-Binary Low-Density Parity-Check, NB-LDPC)碼解碼器的架構設計上，運算複雜度相當的高，需要的記憶體用量也相當龐大。因此，如何降低運算複雜度與記憶體用量，也成了目前設計上最重要的一環。
為了降低實作上符元搜索的複雜度，現今的解碼器設計大多使用前向後向解碼方式(Forward-Backward Decoding Scheme)，但是使用此方法，需要大量額外的記憶體面積來儲存暫時資料，而且完成前向、後向、合併三次運算的過程中，也增加了運算時間。為了降低記憶體使用量與計算複雜度，本論文中提出了僅需前向運算的解碼方式，並且藉由最小最大解碼演算法(Min-Max Decoding Algorithm)的特性，回推出適當的解碼結果。另外，為了提升整體解碼速度，此改良式解碼器可降低運算所需次數，並且藉由平行處理的方式來提升整體的運算速度。最後由分析結果可知，所提出之解碼架構可有效的降低整體記憶體的使用量與計算複雜度。

Non-binary low-density parity-check (NB-LDPC) codes have better error correcting ability than binary LDPC codes when the code length is moderate. However, the hardware cost of the NB-LDPC decoder is much larger than that of the binary one. According to the related NB-LDPC decoder designs, memory usually occupies a substantial portion of the total chip area, and the corresponding computational complexity is rather high. Therefore, the most important topic in NB-LDPC decoder design is to find an efficient way to reduce the computational complexity and the memory usage amount.
In related works, The CNU commonly applied the forward-backward decoding scheme to reduce the symbol searching complexity, but it requires extra memory area for storing intermediate messages. Additionally, this method increases the decoding latency due to the long computation time of forward, backward and merging steps. To reduce the computational complexity and memory usage amount, we proposed the max-forward decoding scheme, which only needs to compute the forward steps and calculate the messages by using the properties of min-max decoding algorithm to backtrack the proper value from maximum and second maximum value. The thesis also presented a modified min-max decoder to eliminate the redundant computation and increase the decoding speed by using the concept of parallel processing. Finally, the proposed decoding architecture can reduce the memory usage amount and the computational complexity from our analysis results.

1 Chapter 1 Introduction 1
1.1 Research Motivation 2
1.2 Thesis Organization 3
2 Chapter 2 Background 5
2.1 Digital Communication and Error Control Code 6
2.2 Galois Field 7
2.3 Non-binary Low-density Parity-check Codes 10
2.3.1 Code Structure 11
2.3.2 Parity-Check Matrix 12
2.3.3 Generator Matrix 15
2.4 Encoding of NB-LDPC Codes 16
2.5 Decoding of NB-LDPC Codes 16
2.5.1 Extended Min-Sum Decoding Algorithm 18
2.5.2 Min-max Decoding Algorithm 26
2.5.3 Forward-backward Decoding Scheme 27
2.5.4 Layered Decoding Algorithm 28
3 Chapter 3 Low-complexity NB-LDPC Decoder Architecture 31
3.1 Architecture of Layered Decoding Algorithm 31
3.2 Check Node Computing Unit 34
3.2.1 Computation of Check Node 34
3.2.2 Max-forward Decoding Scheme 35
3.2.3 Parallel Sorting-based Elementary Computation Unit 45
3.3 Vector Adder 55
3.4 Memory Configurations 56
4 Chapter 4 Analysis Results 61
4.1 Analysis of Memory Usage Amount 61
4.2 Analysis of Computational Complexity 65
5 Chapter 5 Conclusion and Future Work 68
5.1 Conclusion 68
5.2 Future Work 69
6 Bibliography 71

[1]R.G. Gallager, “Low-density parity check codes, IRE Tran. Inform. Theory, vol. IT-8, pp.21-28, 1962.
[2]R. Tanner, “A recursive approach to low complexity codes, IEEE Trans. Inform. Theory, vol. 27, no. 5, pp. 533–547, Sep 1981.
[3]S.Y. Chung, G. D. Forney, Jr., T. J. Richardson, and R. Urbanke, “On the design of low density parity check codes within 0.0045 dB of the Shannon limit, IEEE Commun. vol. 5, no. 2, pp. 58-60, Feb, 2001.
[4]WWiSE Proposal: High Throughput extension to the 802.11, IEEE Standard. 11-04-0866-00-000n, 2005.
[5]Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems-Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands and Corrigendum 1, IEEE Std. 802.16e-2005, 2005.
[6]F. Kienle, T. Brack, and N. Wehn, “A synthesizable IP core for DVB-S2 LDPC code decoding, in Proc. IEEE Conf. of Design, Automation and Test in Europe (DATA’05), Mar. 2005, vol. 3, pp. 100–105.
[7]IEEE Standard for Information Technology-Telecommunications and Information Exchange between Systems-Local and Metropolitan Area Networks-Specific Requirements Part 3: Carrier Sense Multiple Access with Collision Detection (CSMA/CD) Access Method and Physical Layer Specifications, IEEE Std. 802.3an-2006 (Amendment to IEEE Std 802.3-2005), 2006
[8]M. Davey and D. J. C. Mackay, “Low-density parity check codes over GF(q), IEEE Commun. Lett., vol. 2, no. 6, pp. 165-167, June 1998.
[9]L. Barnault and D. Declercq, “Fast decoding algorithm for LDPC over GF(2q), in Proc. 2003 IEEE Inform. Theory Workshop, 2003, pp. 70–73.
[10]F. Guo and L. Hanzo, “Low complexity non-binary LDPC and modulation schemes communicating over MIMO channel, in Proc. IEEE Veh. Tech. Conf. (VTC’04), Sept. 2004, vol. 2, pp. 1294–1298.
[11]R. Peng and R. Chen, “Application of nonbinary LDPC cycle codes to MIMO channels, IEEE Trans. Wireless Commun., vol. 7, no. 6, pp. 2020- 2026, June 2008.
[12]A. Marinoni, P. Savazzi, and S. Valle, “Efficient design of non-binary LDPC codes for magnetic recording channels, robust to error bursts, in Proc. 5th Int. Symp. on Turbo Codes and Related Topics, Sept. 1–5, 2008, pp. 288-293.
[13]J. Chen, L. Wang, and Y. Li, “Performance comparison between non-binary LDPC codes and Reed-Solomon codes over noise bursts channels. n Proc. IEEE Int. Conf. Circuit and Syst. (ICCCAS’05), May 2005, pp. 1–4.
[14]S. Brink, G. Kramer, and A. Ashikhmin, “Design of low-density parity-check codes for modulation and detection, IEEE Trans. Commun., pp. 670-678, Apr. 2004.
[15]Z.W. Li, L. Chen, L. Zeng, S. Lin, and W. Fong, “Efficient encoding of quasi-cyclic low-density parity-check codes, in Proc. IEEE Globecom, vol. 3, pp.6, 28, Nov.-2 Dec. 2005.
[16]S. Lin and D. J. Costello, Error Control Coding Fundamentals and Applications Second Edition, 2004.
[17]Z. Li, L. Chen, L. Zeng, S. Lin, and W. H. Fong, “Efficient encoding of quasi-cyclic low-density parity-check codes, IEEE Trans. Commun., vol. 54, no. 1, pp. 71–81, Jan. 2006.
[18]L. Zeng, L. Lan, Y. Y. Tai, B. Zhou, S. Lin, and K. Adbel-Ghaffar, “Construction of nonbinary cyclic, quasi-cyclic and regular LDPC codes: a finite geometry approach, IEEE Trans. Commun., vol. 56, no. 3, pp. 378-387, Mar. 2008.
[19]B. Zhou, J. Kang, S. Song, S. Lin, K. Adbel-Ghaffar, and M. Xu, “Construction of non-binary quasi-cyclic LDPC codes by arrays and array disperations, IEEE Trans. Commun., vol. 57, no. 6, pp. 1652-1662, June 2009.
[20]H. Song and 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.
[21]H. Wymeersch, H. Steendam, and M. Moeneclaey, “Log-domain decoding of LDPC codes over GF(q), in Proc. IEEE Int. Conf. Commun., June 2004, pp. 772-776.
[22]M. Mansour and N. Shanbhag, “A 640-Mb/s 2048-bit programmable LDPC decoder chip, IEEE J. Solid-State Circuits, vol. 41, no. 3, pp. 684-698, Mar. 2006
[23]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.
[24]V. Savin, “Min-max decoding for non binary LDPC codes, in Proc. IEEE Int. Symp. Inform. Theory, July 2008, pp.960-964.
[25]C. Spagnol, E. Popovici, and W. Marnane, “FPGA implementations of LDPC over GF(2m) decoders, in Proc. IEEE Workshop on Signal Processing Syst., Oct. 2007, pp. 273–278.
[26]A. Voicila, D. Declercq, F. Verdier, M. Fossorier, and P. Urard, “Architecture of a low-complexity non-binary LDPC decoder for high order fields, in Proc. IEEE Int. Symp. Commun. and Inform. Tech. (ISCIT’07), Oct. 2007, pp. 1201–1206.
[27]X. Zhang and F. Cai, “Efficient partial-parallel decoder architecture for quasi-cyclic nonbinary LDPC codes, IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 58, no. 2, pp. 402-414, Feb. 2011.
[28]X. Zhang and F. Cai, “Reduced-complexity decoder architecture for non-binary LDPC codes, IEEE Trans. Very Large Scale Integr. (VLSI). Syst., vol. 19, no. 7, pp. 1229–1238, July 2011.
[29]J. Lin, J. Sha, Z. Wang, and L. Li, “Efficient decoder design for nonbinary quasicyclic LDPC codes, IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 57, no. 5, pp. 1071-1082, May 2010.
[30]Y.-L. Ueng, C.-Y. Leong, C.-J. Yang, C.-C. Cheng, K.-H. Liao, and S.-W. Chen, “An efficient layered decoding architecture for nonbinary QC-LDPC codes, IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 59, no. 2, pp. 385–398, Feb. 2012.
[31]X. Chen, S. Lin, and V. Akella, “Efficient configurable decoder architecture for nonbinary quasi-cyclic LDPC codes, IEEE Trans. Circuits Syst. I, Reg. papers, vol. 59, no. 1, pp. 188–197, Jan. 2012.