非二位元低密度同位元檢查區塊/迴旋碼解碼器之設計與實現

Design and Implementation of Nonbinary LDPC-BC/CC Decoders

林佳龍

非二位元低密度同位元檢查碼 ； 迴旋碼 ； 錯誤更正碼 ； 解碼器 ； VLSI ； 低密度同位元檢查碼 ； nonbinary low-density parity-check codes ； convolutional codes ； error correcting codes ； decoder ； VLSI ； low-density parity-check codes

交通大學電子工程系所學位論文

2016年

博士

李鎮宜;張錫嘉

英文

錯誤更正碼在通訊或儲存系統中提供錯誤更正的能力。 在過去數十年中，因為二位元低密度檢查碼的優秀更正能力及高平行度的處理特性，所以該碼廣泛地運用在許多系統或標準中。非二位元低密度檢查碼在多根天線系統以及衰弱通道下擁有更傑出的錯誤更正能力，且可同時更正連續及隨機的錯誤。然而，解碼器的高複雜度及大量的儲存需求使得非二位元低密度檢查碼無法在實際的應用中被採用。許多文獻在演算法及硬體架構上簡化及改善解碼過程，但吞吐量、矽面積使用效率以及能量使用效率仍然跟其它種類的錯誤更正碼相之甚遠。另一方面來說，二位元低密度檢查區塊碼不利提供多種碼長及多種碼率。非二位元低密度檢查迴旋碼不僅具有優秀的錯誤更正能力，並且像迴旋碼一樣能提供多種碼長。然而，該碼卻有些缺點，例如長延遲、低平行度以及一般的吞吐量。除此之外，目前文獻中並無該類解碼器的討論。因此，在此論文中探討並研究非二位元低密度檢查區塊碼/迴旋碼來探索未來通訊系統中該碼的潛力。 非二位元低密度檢查區塊碼方面，此論文提出了兩個完整設計。第一個是運用在類循環非二位元低密度檢查區塊碼的高矽面積使用效率解碼器架構，解碼演算法是根據延伸的最小值-總和演算法(Extended Min-Sum)。藉由提出的雙倍吞吐量的校驗節點單元以及節點單元間的重疊處理來提升吞吐量。訊息隱藏以及簡化的變數節點單元被提出來降低儲存量及運算量。綜合以上技巧，實作了一個GF(64)(112,56)非二位元低密度檢查區塊碼解碼器。在post-layout結果中，core面積是2.24 mm^2，功率是274mW而吞吐量是124.6 Mb/s。第二個設計是針對近年興起的低耗移動裝置或IoT應用。根據trellis min-max演算法，提出了高吞吐量的校驗節點單元以及兩階段的變數節點單元來提升吞吐量和能源效率。為了提供多樣化的通道品質，提出訊息長度切換方法來調整錯誤更正能力來節省能源。為了驗證提出的方法，我們用90nm CMOS實作了一個GF(32)(400,200)的非二位元低密度檢查區塊碼解碼器。在量測結果中，core面積是5.02 mm^2，吞吐量是1.53 Gb/s而功率是434mW。比起過去的研究，此設計具有最高的吞吐量以及最好的能源及矽面積使用效率，並能節省90%以上的能源。 在非二位元低密度檢查迴旋碼方面，提出一個同時考慮到硬體架構及錯誤更正能力的的建碼方式。此碼的特色在簡單的架構以及低連線數。針對所提出的建碼方式，我們也提出了相對應的記憶體基礎之解碼器架構。其中，運算單元及運算排程皆針對能源效率來改進。綜合以上方法，用90nm CMOS實作了一個時變GF(256)(50,2,4)的非二位元低密度檢查迴旋碼解碼器。錯誤更正能力在SNR=0.9dB時達到位元錯誤率10^{-5}，並且藉由穿刺可提供多種碼率。 此論文中針對非二位元低密度檢查區塊碼/迴旋碼在通訊相關系統進行了研究與探討。所提出的研究方法與實作結果在解碼校能跟硬體效率之間有更好的平衡，更有機會應用在實際應用。

Channel codes support an error-correcting capability in communication or storage systems. In the past decades, binary LDPC block codes (LDPC-BCs) are widely adopted in many systems and standards because of its excellent error-correction capability and high parallelism. Nonbinary LDPC-BCs (NB-LDPC-BCs) have even better error correcting performance under MIMO systems and fading channels, and can combat burst and random errors simultaneously. However, the high complexity and huge storage requirement in decoder design prevent NB-LDPC codes in practical applications. Many works in the literature improve and simplify decoding process in algorithm and architecture levels, but the throughput, area-efficiency and energy-efficiency still cannot catch up the other channel codes. In the other hand, LDPC-BCs have weakness for supporting flexible block length and multi-code-rate. NB-LDPC convolutional codes (NB-LDPC-CCs) not only have excellent error-correcting performance, but also support variable block length naturally as convolutional codes. Nevertheless, the codes have serious drawback, such as long latency, low parallelism, and normal throughput. Besides, there is no relative work in the literature before. Hence, this dissertation investigates both NB-LDPC-BCs and NB-LDPC-CCs to explore the potential for the next generation of communication systems. For NB-LPDC-BCs, this dissertation presents two works. The first one is an area-efficient decoder architecture for quasi-cyclic NB-LDPC codes with EMS algorithm. The throughput is improved by not only double-throughput elementary check node unit that processes two combinations within one clock cycle, but also overlapped processing for both check node and variable node units. To reduce memory usage and computing complexity, edge-message hiding and simplified variable node unit (VNU) are proposed as well. With these schemes, the post-layout results of a decoder for a (112,56) NB-LDPC over GF(64) are presented. The core area occupies 2.24 mm^2 and consumes 274 mW with throughput of 124.6 Mb/s. The second one is targeting emerging energy constrained mobile devices or internet-of-things (IoT). We propose high-throughput check node unit with trellis min-max algorithm and two-stage variable node unit to improve the throughput and energy efficiency. Message-length switching is also proposed for adjusting error-correcting capability to fit the diversity of channel, and further saving power consumption. To demonstrate the proposed techniques, a decoder for (400,200) NB-LDPC code over GF(32) is implemented with 90-nm CMOS technology. The core occupies 5.02 mm^2, and the measurement results show that 1.53 Gb/s can be achieved with 434 mW. The implementation result has higher throughput and higher hardware-efficiency than the state-of-the-art designs, and saves more than 90% energy in technology normalized comparison. For NB-LDPC-CCs, a design approach for architecture-aware NB-LDPC-CCs is presented to jointly optimizes the code performance and decoder complexity for achieving high energy-efficiency decoder. The proposed NB-LDPC-CCs feature simple structure and low degree. We also present a corresponding memory-based decoder architecture, where the computation units and the scheduling of the computations are optimized to increase energy efficiency. A time-varying (50,2,4) NB-LDPC-CC over GF(256) is constructed, and associated decoder is implemented in 90nm CMOS. The code can reach BER = 10^{-5} at SNR=0.9dB, and support multi-code-rate with puncturing. NB-LDPC-BCs and NB-LDPC-CCs decoders are investigated for communication relative systems. The proposed design methodologies would make NB-LDPC codes more competitive to the other channel codes.

1. [7] R. Yazdani and M. Ardakani, “Efficient LLR calculation for non-binary modulations over fadingchannels,” IEEE Trans. Commun., vol. 59, no. 5, pp. 1236–1241, 2011.
   連結：
2. [8] R. Peng and R. R. Chen, “Application of nonbinary LDPC cycle codes to mimo channels,” IEEE Trans. Wireless Commun., vol. 7, pp. 2020–2026, 2008.
   連結：
3. [9] D. Declercq and M. Fossorier, “Decoding algorithms for nonbinary LDPC codes over GF(q),” IEEE Trans. Commun., vol. 55, no. 4, pp. 633–643, 2007.
   連結：
4. [10] A. Voicila, D. Declercq, F. Verdier, M. Fossorier, and P. Urard, “Low-complexity decoding for non-binary LDPC codes in high order fields,” IEEE Transactions on Communications, vol. 58, no. 5, pp. 1365–1375, 2010.
   連結：
5. [11] V. Savin, “Min-max decoding for non binary LDPC codes,” in IEEE International Symposium on Information Theory, 2008, pp. 960–964.
   連結：
6. [12] X. Zhang and C. Fang, “Reduced-complexity decoder architecture for non-binary LDPC codes,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 19, no. 7, pp. 1229–1238, 2011.
   連結：
7. [14] C. Fang and Z. Xinmiao, “Relaxed min-max decoder architectures for nonbinary lowdensity parity-check codes,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 21, no. 11, pp. 2010–2023, 2013.
   連結：
8. [15] E. Boutillon, L. Conde-Canencia, and A. A. Ghouwayel, “Design of a GF(64)-LDPC decoder based on the EMS algorithm,” IEEE Trans. Circuits Syst. I, vol. 60, no. 10, pp. 2644–2656, 2013.
   連結：
9. [17] X. Chen, S. Lin, and V. Akella, “Efficient configurable decoder architecture for nonbinary quasi-cyclic LDPC codes,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 59, no. 1, pp. 188–197, 2012.
   連結：
10. [18] X. Chen and C. L. Wang, “High-throughput efficient non-binary LDPC decoder based on the simplified min-sum algorithm,” IEEE Trans. Circuits Syst. I, vol. 59, no. 11, pp. 2784–2794, 2012.
    連結：
11. [19] Y. L. Ueng, C. Y. Leong, C. J. Yang, C. C. Cheng, and K.-H. L. S. W. Chen, “An efficient layered decoding architecture for nonbinary QC-LDPC codes,” IEEE Trans. Circuits Syst. I, vol. 59, pp. 385–398, 2012.
    連結：
12. [20] Y. L. Ueng, K. H. Liao, H. C. Chou, and C. J. Yang, “A high-throughput trellis-based layered decoding architecture for non-binary LDPC codes using max-log-QSPA,” IEEE Transactions on Signal Processing, vol. 61, no. 11, pp. 2940–2951, 2013.
    連結：
13. [21] Y. S. Park, Y. Tao, and Z. Zhang, “A fully parallel nonbinary LDPC decoder with finegrained dynamic clock gating,” IEEE Journal of Solid-State Circuits, vol. 50, no. 2, pp. 464–475, Feb. 2015.
    連結：
14. [22] S. W. Yen, S. Y. Hung, C. L. Chen, H. C. Chang, S. J. Jou, and C. Y. Lee, “A 5.79-gb/s energy-efficient multi-rate ldpc codec chip for ieee 802.15.3c applications,” IEEE J. Solid-State Circuits, vol. 47, no. 9, pp. 2246–2257, 2011.
    連結：
15. [23] C. C. Wong, M. W. Lai, C. C. Lin, H. C. Chang, and C. Y. Lee, “Turbo decoder using contention-free interleaver and parallel architecture,” IEEE J. Solid-State Circuits, vol. 45, no. 2, pp. 422–432, 2010.
    連結：
16. [24] R. Swamy, S. Bates, and T. Brandon, “Architectures for ASIC implementations of low-density parity-check convolutional encoders and decoders,” in IEEE International Symposium on Circuits and Systems (ISCAS), vol. 5, May 2005, pp. 4513–4516.
    連結：
17. [25] S. Bates, Z. Chen, L. Gunthorpe, A. Pusane, K. Zigangirov, and D. Costello, “A lowcost serial decoder architecture for low-density parity-check convolutional codes,” IEEE Transactions on Circuits and Systems I, vol. 55, no. 7, p. 1967V1976, Aug. 2008.
    連結：
18. [26] M. Tavares, E. Matus, S. Kunze, and G. Fettweis, “A dual-core programmable decoder for LDPC convolutional codes,” in IEEE International Symposium on Circuits and Systems (ISCAS), May 2008, pp. 532–535.
    連結：
19. [28] Z. Chen, T. L. Brandon, D. G. Elliott, S. Bates, W. A. Krzymien, and B. F. Cockburn, “Jointly designed architecture-aware LDPC convolutional codes and high-throughput parallel encoders/decoders,” IEEE Trans. Circuits Syst. I, vol. 57, no. 4, pp. 836–849, 2010.
    連結：
20. [29] Y. Ueng, Y. Wang, L. Kan, C. Yang, and Y. Su, “Jointly designed architecture-aware LDPC convolutional codes and memory-based shuffled decoder architecture,” Signal Processing, IEEE Transactions on, vol. PP, no. 99, pp. 1–1, 2012.
    連結：
21. [31] D. J. C. MacKay and R. M. Neal, “Near shannon limit performance of low density parity check codes,” Electron. Lett., vol. 33, pp. 457–458, 1997.
    連結：
22. [32] D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Transactions on Information Theory, vol. 45, no. 2, pp. 399–431, 1999.
    連結：
23. [33] M. C. Davey and D. J. C. MacKay, “Low density parity check codes over GF(q),” in Information Theory Workshop, 1998, pp. 70–71.
    連結：
24. [36] C. L. Chen, Y. H. Lin, H. C. Chang, and C. Y.Lee, “A 2.37-Gb/s 284.8 mW ratecompatible (491,3,6) LDPC-CC decoder,” IEEE J. Solid-State Circuits, vol. 47, no. 4, pp. 817–831, 2012.
    連結：
25. [37] G. Sarkis, S. Mannor, andW. J. Gross, “Stochastic decoding of LDPC codes over gf(q),” in IEEE International Conference on Communications, 2009.
    連結：
26. [38] X. R. Lee, C. W. Yang, C. L. Chen, H. C. Chang, and C. Y. Lee, “An area-efficient relaxed half-stochastic decoding architecture for nonbinary LDPC codes,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 62, no. 3, pp. 301–305, 2015.
    連結：
27. [39] C. Spagnol, E. M. Popovici, and W. P. Marnane, “Hardware implementation of gf(2m) LDPC decoders,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 56, no. 12, pp. 2609–2620, 2009.
    連結：
28. [40] H. Wymeersch, H. Steendam, and M. Moeneclaey, “Log-domain decoding of LDPC codes over GF(q),” in IEEE International Conference on Communications, 2004, pp. 772–776.
    連結：
29. [41] L. Keke, L. Shu, and K. Abdel-Ghaffar, “A revolving iterative algorithm for decoding algebraic cyclic and quasi-cyclic LDPC codes,” IEEE Transactions on Communications, vol. 61, no. 12, pp. 4816–4827, 2013.
    連結：
30. [42] R. J. McEliece, D. J. C. MacKay, and J.-F. Cheng, “Turbo decoding as an instance of Pearl’s belief propagation algorithm,” IEEE Journal on Selected Areas in Communications, vol. 16, no. 2, pp. 140–152, 1998.
    連結：
31. [43] J. L. Fan, Constrained coding and soft iterative decoding. Netherlands: Kluwer Academic, 2001.
    連結：
32. [45] D. Declercq and M. Fossorier, “Extended minsum algorithm for decoding ldpc codes over gf(q),” in International Symposium on Information Theory, 2005, pp. 464–468.
    連結：
33. [46] T. Yaoyu, P. Y. Sung, and Z. Zhengya, “High-throughput architecture and implementation of regular (2, dc) nonbinary LDPC decoders,” in IEEE International Symposium on Circuits and Systems (ISCAS), 2012, pp. 2625–2628.
    連結：
34. [48] C. Poulliat, M. Fossorier, and D. Declercq, “Design of regular (2,dc)-LDPC codes over GF(q) using their binary images,” IEEE Transactions on Communications, vol. 56, no. 10, pp. 1626–1635, 2008.
    連結：
35. [49] A. Voicila, F. Verdier, D. Declercq, M. Fossorier, and P. Urard, “Architecture of a lowcomplexity non-binary LDPC decoder for high order fields,” in International Symposium on Communications and Information Technologies, 2007, pp. 1201–1206.
    連結：
36. [50] E. Boutillon and L. Conde-Canencia, “Bubble check: a simplified algorithm for elementary check node processing in extended min-sum non-binary LDPC decoders,” Electronics Letters, vol. 46, no. 9, pp. 633–634, 2010.
    連結：
37. [52] C. L. Lin, S. W. Tu, C. L. Chen, H. C. Chang, and C. Y. Lee, “An efficient decoder architecture for nonbinary LDPC codes with extended min-sum algorithm,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. PP, no. 99, pp. 1–1, 2016.
    連結：
38. [53] Y. K. Lin, C. L. Chen, Y. C. Liao, and H. C. Chang, “Structured LDPC codes with low error floor based on peg tanner graphs,” in IEEE Int. Sympo. Circuits and Systems, 2008, pp. 1846–1849.
    連結：
39. [54] A. A. Ghouwayel and E. Boutillon, “A systolic llr generation architecture for non-binary LDPC decoders,” IEEE Communications Letters, vol. 15, no. 8, pp. 851–853, 2011.
    連結：
40. [55] L. Jun and Y. Zhiyuan, “An efficient fully parallel decoder architecture for nonbinary LDPC codes,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 22, no. 12, pp. 2649–2660, 2014.
    連結：
41. [56] C. L. Lin, C. L. Chen, H. C. Chang, and C. Y. Lee, “A (50,2,4) nonbinary LDPC convolutional code decoder chip over GF(256) in 90nm cmos,” in IEEE Asian Solid State Circuits Conference, 2012, pp. 201–204.
    連結：
42. [57] ——, “Jointly designed nonbinary LDPC convolutional codes and memory-based decoder architecture,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 62, no. 10, pp. 2523–2532, 2015.
    連結：
43. [58] Z. Hua and N. Goertz, “Cycle analysis of time-invariant LDPC convolutional codes,” in IEEE International Conference Telecommunications, 2010, pp. 23–28.
    連結：
44. [59] A. J. Felstrom and K. S. Zigangirov, “Time-varying periodic convolutional codes with low-density parity-check matrix,” IEEE Trans. Inform. Theory, vol. 45, no. 6, pp. 2181–2191, 1999.
    連結：
45. [60] L. Jun and Y. Zhiyuan, “Efficient shuffled decoder architecture for nonbinary quasicyclic LDPC codes,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 21, no. 9, pp. 1756–1761, 2013.
    連結：
46. [1] H. Uchikawa, K. Kasai, and K. Sakaniwa, “Terminated LDPC convolutional codes over GF(2p),” in Annual Allerton Conference on Communicaion, Control, and Computing, 2010, pp. 195–200.
47. [2] Amendment Text Proposal on Rate Compatible LDPC-Convolutional Codes, IEEE Std. C802.16m-09/0339, 2009.
48. [3] IEEE Standard for Information technology– Local and metropolitan area networks– Specific requirements– Part 11: Wireless LAN Medium Access Control (MAC)and Physical Layer (PHY) Specifications Amendment 5: Enhancements for Higher Throughput, IEEE Std. 802.11n-2009, 2009.
49. [4] 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, 2006.
50. [5] IEEE Standard for Local and Metropolitan Area Networks 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 and 802.16-2004/Cor 1-2005, 2006.
51. [6] Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications, ETSI Std. EN 302 307, Rev. 1.1.2, 2006.
52. [13] J. O. Lacruz, F. Garcia-Herrero, J. Valls, and D. Declercq, “One minimum only trellis decoder for non-binary low-density parity-check codes,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 62, no. 1, pp. 177–184, 2015.
53. [16] L. Jun, S. Jin, W. Zhongfeng, and L. Li, “Efficient decoder design for nonbinary quasicyclic LDPC codes,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 57, no. 5, pp. 1071–1082, 2010.
54. [27] E. Matus, M. Tavares, M. Bimberg, and G. Fettweis, “Towards a GBit/s programmable decoder for LDPC convolutional codes,” in IEEE International Symposium on Circuits and Systems (ISCAS), May 2007, pp. 1657–1660.
55. [30] R. Gallager, “Low-density parity-check codes,” IRE Transactions on Information Theory, vol. 8, no. 1, pp. 21–28, 1962.
56. [34] S. Lin and W. E. Ryan, Channel Codes: Classical and Modern, 1st ed. NY: Cambridge University Press, 2009.
57. [35] IEEE Standard for Information technology - Telecommunications and information exchange between systems - Local and metropolitan area networks - Specific requirements. Part 15.3: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for High Rate Wireless Personal Area Networks (WPANs) Amendment 2: Millimeter-wave-based Alternative Physical Layer Extension, IEEE Std. 802.15.3c-2009, 2009.
58. [44] C. C. Lin, “Channel decoer design and implementation,” Ph.D. dissertation, National Chiao Tung Univ., Hsinchu, Taiwan, 2006.
59. [47] X. Y. Hu and E. Eleftheriou, “Binary representation of cycle tanner-graph GF(2b) codes,” in IEEE International Conference on Communications, vol. 1, 2004, pp. 528–532 Vol.1.
60. [51] ——, “Simplified check node processing in nonbinary LDPC decoders,” in International Symposium on Turbo Codes and Iterative Information Processing, 2010, pp. 201–205.