Title

一種應用於NAND快閃記憶體的低複雜度低密度奇偶檢查碼之編解碼器

Translated Titles

A Low-Complexity LDPC Codec for NAND Flash Memory

DOI

10.6843/NTHU.2013.00077

Authors

周學志

Key Words

低密度奇偶檢查碼 ; NAND快閃記憶體 ; LDPC ; NAND Flash Memory

PublicationName

清華大學電機工程學系所學位論文

Volume or Term/Year and Month of Publication

2013年

Academic Degree Category

碩士

Advisor

翁詠祿

Content Language

英文

Chinese Abstract

傳統單層式儲存架構之NAND快閃記憶體多使用Hamming或是BCH碼等硬式決策技術來減緩因記憶格的錯誤而造成的影響,但由於電路越做越小的趨勢,隨著製程的逐漸縮小以及多層式儲存的技術的發展下,這些硬式決策技術的效能也地逐漸變差,以至於需要更強力的錯誤更正的方法來改善其效能,而低密度奇偶檢查碼即是一種擁有不錯的錯誤更正效能的軟式決策技術。在NAND快閃記憶體的應用上,高碼率和低成本的解碼器是不可或缺的。不規則的(18624, 16704)和(18432, 16704)碼率分別為0.896和0.906的準循環低密度奇偶檢查碼被用於本作中。我們以兩層式編碼器和一種低成本解碼架構來呈現應用於NAND快閃記憶體的低複雜度奇偶檢查碼的編解碼器。除此之外,編碼器-解碼器的共用得以降低實作複雜度。最後我們提出一種用於解碼器的低複雜度的檢查節點單元在不影響錯誤更正效能的前提下來最佳化檢查至變數節點訊息以降低儲存複雜度。此低密度奇偶檢查碼之編解碼器以TSMC 90奈米技術實現,在操作頻率166 MHz下編碼器可以達到4.03 Gb/s同時解碼器可以達到2.35 Gb/s的吞吐量。

English Abstract

Conventional NAND Flash memory with single-level cell architecture is implemented in hard-decision techniques such as Hamming or BCH codes to mitigate the effect of memory cell errors. However, it needs much more powerful error correction technique as these hard-decision techniques are not sufficient for multilevel technique and continuously scaled down cell size gradually. Low-density parity-check(LDPC) codes is a soft-decision technique with splendid error-rate performance. For NAND Flash applications, high-rate and low-cost decoders are required. Irregular (18624, 16704) and (18432, 16704) Quasi-Cyclic LDPC (QC-LDPC) code that has a code rate of 0.896 and 0.906 is used respectively. We presented a low-complexity LDPC Codec for NAND Flash implemented in two-stage encoder and a low-cost decoding architecture. In addition, encoder-decoder sharing is also implemented to reduce implementation complexity. Finally, we proposed a low-complexity check-node unit for decoder to optimize check-to-variable message to reduce storage complexity without error-rate performance loss. The LDPC Codec is implemented in TSMC 90-nm CMOS technology and the Two-Stage Encoder and the Decoder can achieve a throughput of 4.03Gb/s and throughput of 2.35Gb/s respectively at a clock frequency 166 MHz.

Topic Category 電機資訊學院 > 電機工程學系所
工程學 > 電機工程
Reference
  1. [1] E. Yaakobi, L. Grupp, P.H. Siegel, S. Swanson, and J.K.Wolf, "Character-
    連結:
  2. ization and error-correcting codes for TLC
    連結:
  3. ash memories" Proc. IEEE
    連結:
  4. ash memories" IEEE
    連結:
  5. Correction Systems for Multilevel NOR and NAND Flash Memories" IET
    連結:
  6. error correction scheme for NAND
    連結:
  7. ash memory" Proc. IEEE VLSI Test
    連結:
  8. [6] R. G. Gallager, "Low-density parity-check codes" IRE Trans. Inf. Theory,
    連結:
  9. [7] Digital Video Broadcasting (DVB); Second Generation Framing Struc-
    連結:
  10. tion Comment 2004, IEEE C802.16e-04/141r2.
    連結:
  11. PHY. IEEE P802.11 Wireless LANs 2006, IEEE 802.11-05/1102r4.
    連結:
  12. High-Rate QC-LDPC Codes" NTHU Master Thesis.
    連結:
  13. [12] D. J. C. MacKay, "Good error-correcting codes based on very sparse ma-
    連結:
  14. trices" IEEE Trans. Inf. Theory, Vol. 45, No. 2, pp. 399-431, Mar. 1999.
    連結:
  15. [13] D. Hocevar, "A reduced complexity decoder architecture via layered de-
    連結:
  16. [14] M. M. Mansour and N. R. Shanbhag, "High-throughput LDPC decoders"
    連結:
  17. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol.
    連結:
  18. decoding of low-density parity-check codes based on belief propagation"
    連結:
  19. "Reduced complexity decoding of LDPC codes" IEEE Trans. Commun.,
    連結:
  20. based decoding algorithms of LDPC codes" IEEE Commum. Lett., vol.
    連結:
  21. 6, pp.208-210, May 2002.
    連結:
  22. of Regular and Irregular LDPC Codes" In Proc. 3nd International Sym-
    連結:
  23. September 2003.
    連結:
  24. [19] O. Daesun and K. Parhi, "Min-sum decoder architectures with reduced
    連結:
  25. 661-V2-663, 21-24 May 2010.
    連結:
  26. [21] Chen, Rong, and Yi-ming Wang., "Modified Normalized Min-Sum decod-
    連結:
  27. Conference on. IEEE, 2008.
    連結:
  28. "Novel modified min-sum decoding algorithm for low-density paritycheck
    連結:
  29. [23] Valentin Savin, "Self-corrected min-sum decoding of LDPC codes" Proc.
    連結:
  30. [24] T. Mohsenin, D. Truong, and B. Baas, "A low-complexity message-
    連結:
  31. passing algorithm for reduced routing congestion in LDPC decoders,"
    連結:
  32. IEEE Trans. Circuits Syst. I, vol. 57, no 5, pp. 1048-1061, May 2010.
    連結:
  33. techniques for LDPC decoders," IEEE J. Solid-State Circuits, vol. 43, no
    連結:
  34. design for high-rate quasi-cyclic low-density parity-check codes in mag-
    連結:
  35. decoder for error correction of NAND Flash memories" in Proc. IEEE
    連結:
  36. Int. Midwest Symp. Circuits Syst., Aug. 2011, pp. 14.
    連結:
  37. Int. Conf. Comput., Netw. Commun., Maui, HI, pp. 486-491, Jan-Feb.
  38. 2012.
  39. [2] W. Liu, J. Rho, and W. Sung, "Low-power high-throughput BCH error
  40. correction VLSI design for multi-level cell NAND
  41. Workshop on Signal Processing Systems (SIPS), pp. 303-308, 2006.
  42. [3] R. Micheloni, R. Ravasio, A. Marelli, E. Alice, V. Altieri, A. Bovino,
  43. L. Crippa, E. D. Martino, L. D. Onofrio, A. Gambardella, E. Grillea,
  44. G. Guerra, D. Kim, C. Missiroli, I. Motta, A. Prisco, G. Ragone, M.
  45. Romano, M. Sangalli, P. Sauro, M. Scotti and S. Won, "A 4Gb 2b/cell
  46. NAND
  47. ash memory with embedded 5b BCH ECC for 36MB/s system
  48. read throughput" Proc. Intl Solid-State Circuits Conference, pp. 497-
  49. 506, Feb 2006.
  50. [4] F. Sun, S. Devarajan, K. Rose, and T. Zhang, "Design of On-Chip Error
  51. Circuits, Devices and Systems, Vol.1, No.3, pp.241-249, June 2007.
  52. [5] T.-H. Chen, Y.-Y. Hsiao, Y.-T. Hsing, and C.-W. Wu, "An adaptive-rate
  53. Symp. (VTS), pp. 53-58, May 2009.
  54. Vol. IT-8, pp. 21-28, Jan. 1962.
  55. ture, Channel Coding and Modulation Systems for Broadcasting, Interac-
  56. tive Services, New Gathering and Other Broadband Satellite Applications
  57. 2004.
  58. [8] LDPC coding for OFDMA PHY. 802.16REVe Sponsor Ballot Recircula-
  59. [9] Joint Proposal: High Throughput Extension to the 802.11 Standard:
  60. [10] Yeong-Luh Ueng, Jyun-Kai Hu, and Hsueh-Chih Chou, "Layered Decod-
  61. ing Architecture with Reduced Number of Hardware Buers for LDPC
  62. Codes".
  63. [11] Jyun-Kai Hu, "A Reduced-Complexity Layered Decoder Architecture for
  64. coding of LDPC codes" 11. IEEE Workshop on Signal Processing Sys-
  65. tems, 2004, SIPS 2004, pp. 107-112, Oct. 2004.
  66. 11, pp. 976996, Dec. 2003.
  67. [15] M. Fossorier, M. Mihaljevic, and H. Imai, "Reduced complexity iterative
  68. IEEE Trans. Commum., vol. 47, no. 5, pp. 673-680, May 1999.
  69. [16] Chen, A. Dholakia, E. Eleftheriou, M. P. C. Fossorier, and X.-Y. Hu,
  70. vol. 53, no. 8, pp. 1288-1299, Aug. 2005.
  71. [17] J. Chen and M. P. C. Fossorier, "Density evolution for two improved BP-
  72. [18] F. Guilloud, E. Boutillon, and J.L. Danger, "λ-Min Decoding Algorithm
  73. posium on Turbo Codes & Related Topics, pages 451454, Brest, France,
  74. word length for LDPC codes" IEEE Trans. Circuits Syst. I, Reg. Papers,
  75. vol. 57, no. 1, pp. 105115, Jan. 2010.
  76. [20] Xiaofu Wu, Yue Song, Long Cui, Ming Jiang, and Chunming Zhao,
  77. "Adaptive-normalized min-sum algorithm" Future Computer and Com-
  78. munication (ICFCC), 2010 2nd International Conference, vol.2, pp.V2-
  79. ing of LDPC codes" Signal Processing, 2008. ICSP 2008. 9th International
  80. [22] L. Hai-yang, Q. U. Wen-ze L.Bin, L. Jiang-peng,L.Shi-dong, and C. Jie,
  81. codes" The Journal of China Universities of Posts and Telecommunica-
  82. tions, vol. 17, pp. 1 -5, August 2010.
  83. IEEE ISIT, pp. 146-150, Jul. 2008.
  84. [25] A. Darabiha, A. C. Carusone, and F. R. Kschischang, "Power reduction
  85. 8, pp. 1835-1845, Aug. 2008.
  86. [26] Kin-Chu Ho, Po-Chao Fang, Hsiang-Pang Li, C.-Y.M. Wang, and Hsie-
  87. Chia Chang. "A 45nm 6b/cell Charge-Trapping Flash Memory Using
  88. LDPC-Based ECC and Drift-Immune Soft-Sensing Engine" In Solid-State
  89. Circuits Conference Digest of Technical Papers (ISSCC), 2013 IEEE In-
  90. ternational, pages 222223, 2013.
  91. [27] H. Zhong, W. Xu, N. Xie, and T. Zhang, "Area-ecient min-sum decoder
  92. netic reording" IEEE Trans. Magn., vol. 43, no. 12, pp. 41174122, Dec.
  93. 2007.
  94. [28] J. Kim, J. Cho, and W. Sung, "A high-speed layered min-sum LDPC
Times Cited
  1. 謝家瑋(2015)。實施現股當日沖銷制度對臺灣股票市場品質之影響。淡江大學會計學系碩士班學位論文。2015。1-96。 
  2. 林清默(2015)。以三種不同方法探討銀行流動性風險 — 台中商業銀行為例。中興大學高階經理人碩士在職專班學位論文。2015。1-48。 
  3. 張眾卓(Chong-Chuo Chang)(2014)。信用交易隱含之日內資訊。證券市場發展季刊。26(2)。91-150。