研究生: |
龔鼎元 Ting-Yuan Kung |
---|---|
論文名稱: |
基於位元節點為中心循序排程演算法之低密度奇偶檢查碼解碼器之線路設計 LDPC Decoder Architecture Using Variable-node-centric Sequential Scheduling Algorithm |
指導教授: |
韓永祥
Yunghsiang S. Han |
口試委員: |
陳伯寧
Po-Ning Chen 謝欣霖 Shin-Lin Shieh 白宏達 Hung-Ta Pai 曾德峰 Der-Feng Tseng |
學位類別: |
碩士 Master |
系所名稱: |
電資學院 - 電機工程系 Department of Electrical Engineering |
論文出版年: | 2012 |
畢業學年度: | 100 |
語文別: | 中文 |
論文頁數: | 45 |
中文關鍵詞: | 低密度奇偶檢查碼解碼器 、解碼演算法 、快閃記憶體 |
外文關鍵詞: | LDPC Decoder, Decoding Algorithm, NAND Flash Memory |
相關次數: | 點閱:513 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
由於快閃記憶體的製程進步以及成本降低,使得相關產品在市場普及化。逐漸地快閃記憶體產品轉以控制晶片的技術規格為導向,而錯誤更正碼的演算法為其中關鍵技術之一。BCH碼是運用在NAND型快閃記憶體的錯誤控制上傳統主流的演算法,然而面對新一代的NAND型快閃記憶體系統的高錯誤特性,工業界必須尋找更強大且有效率的錯誤更正碼來更正錯誤。而低密度奇偶檢查碼就是很好的選擇,尤其當使用軟性資訊來解碼時,更能達到高效能。
本論文主要是實現低密度奇偶檢查碼的解碼演算法硬體線路。於數種已知的低密度奇偶檢查碼的解碼演算法中我們選擇採用位元節點為中心之循序排程演算法來降低演算法的硬體複雜度。此演算法屬於一種分組曳步解碼的演算法,也就是結合並行與串列的解碼方式。使用此方式可以減少解碼疊代次數,而不會使效能損失。同時它可以降低線路的連線數以利繞線,在解碼器中的檢查節點單元與位元節點單元也可以有效的被簡化。最後我們使用UMC 0.11um SP製程,來合成我們所實現的電路。
With advances in the flash memory process technology and reduction of manufacturing costs, flash memory has been used in many popular products recently. The controller IC technology is the critical one making flash memory function well. Error control coding is one of the key components in the controller IC. BCH code has been adopted for the error control on the NAND flash memory for many years. However, due to high error characteristic of the new-generation NAND flash memory system, the industry must find more powerful and efficient error correction codes to perform error correction. Low-density parity-check codes (LDPC codes) are good candidates, especially, when soft information is used to decode. LDPC codes usually result in good bit error performance.
This thesis is mainly focus on implementing the hardware architecture of decoding algorithm for LDPC codes. After investigating several well-known decoding algorithms, the variable-node-centric sequential scheduling algorithm is adopted to reduce the hardware complexity of the decoder. This algorithm is one kind of group shuffled scheduling algorithms, which combine the parallel and serial decoding features to reduce the hardware complexity. By using this algorithm one can reduce the connection number of the hardware architecture to make routing easier. Moreover, the check node units and variable node units in the decoder can be simplified efficiently. The proposed LDPC decoder circuit is synthesized with UMC 0.11 μm standard process and the size of gate count is provided.
[1] S. Lin and D. J. Costello, Error Control Coding, Prentice-Hall, Second Edition (2004)
[2] R. G. Gallager, Low-Density Parity-Check Codes, Cambridge, MA, MIT Press, (1963) (Also,pp. R. G. Gallager, “Low density parity-check codes,” IRE Trans. Information Theory, vol. 8, no. 1, 21–28, January (1962))
[3] R. M. Tanner, “A recursive approach to low complexity codes,” IEEE Trans. Information Theory, vol. 27, no. 9, pp. 533–547, September (1981)
[4] D. MacKay and R. Neal, “Good codes based on very sparse matrices,” Cryptography and Coding, 5th IMA Conf., C. Boyd, Ed., Berlin, Springer-Verlag, October (1995)
[5] D. MacKay, “Good error correcting codes based on very sparse matrices,” IEEE Trans. Information Theory, vol. 45, no. 3, pp. 399–431, March (1999)
[6] N. Alon and M. Luby, “A linear time erasure-resilient code with nearly optimal recovery,” IEEE Trans. Information Theory, vol. 42, no. 11, pp. 1732–1736, November (1996)
[7] J. Byers, M. Luby, M. Mitzenmacher, and A. Rege, “A digital fountain approach to reliable distribution of bulk data,” ACM SIGCOMM Computer Communication Rev., Vol. 28, issue 4 (1998)
[8] W. E. Ryan and S. Lin, Channel Codes: Classical and Modern, Cambridge University Press, New York (2009)
[9] Joe E. Brewer, Manzur Gill , Nonvolatile Memory Technologies with Emphasis on Flash - A Comprehensive Guide to Understanding and Using NVM Devices, Wiley-IEEE Press, Canada (2008)
[10] R. Micheloni, A. Marelli and R. Ravasio, Error Correction Codes for Non-Volatile Memories, Springer, Italy (2008)
[11] Idan Alrod, Eran Sharon, Simon Litsyn, Menahem Lasser, “Soft decoding of hard and soft bits read from a flash memory,” U.S. Pat., 7814401 (2010)
[12] C. Chen, “A 11.5-Gbps LDPC Decoder Based on CP-PEG Code Construction,” IEEE ESSCIRC 2009 Conf., pp. 412-415. (2009)
[13] Kin-Chu Ho, “Design and Implementation of a (9153,8256) LDPC Decoder with 2-bit Soft Input for NAND Flash Memory,” Master thesis, National Chiao Tung University, Hsinchu, Taiwan (2010)
[14] J. Zhang and M. Fossorier, "Shuffled iterative decoding," IEEE Transactions on Communications , vol. 53, no. 2, pp. 209-213 (2005)
[15] Xiaofei Huang, “Single-Scan Min-Sum Algorithms for Fast Decoding of LDPC Codes,” Proceedings of 2006 IEEE Information Theory Workshop (ITW’06), pp. 140–143 (2006)
[16] C.-C. Lin, K.-L. Lin, H.-Ch. Chang, and C.-Y. Lee, “A 3.33Gb/s (1200,720) low-density parity check code decoder,” in Proc. ESSCIRC 2005, 211-214 (2005)
[17] Zion Kwok, Scott Nelson, “LDPC Test Methodology,” Intel (2011)