簡易檢索 / 詳目顯示

回結果列表
研究生： 曾逸夫
Tseng, Yi-Fu
論文名稱： 應用於快閃記憶體之低延遲接續消去極碼解碼器設計
Low Latency Successive-Cancellation Polar Decoder Design for NAND Flash Memory
指導教授： 謝明得
Shieh, Ming-Der
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 電機工程學系
Department of Electrical Engineering
論文出版年： 2020
畢業學年度： 108
語文別： 英文
論文頁數： 62
中文關鍵詞： NAND型快閃記憶體 、資料可靠度 、多層級錯誤更正碼 、系統性極碼 、簡化接續消去 、低延遲 、rate-0/rate-1碼
外文關鍵詞： NAND flash memory, data reliability, Multi-ECC, Systematic Polar codes, Simplified Successive cancellation, low-latency, Rate-0/Rate-1 codes
相關次數： 點閱：79  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 隨著NAND型快閃記憶體的儲存密度增加，在快閃記憶體製程的微縮和多階層儲存單元技術的發展之下，資料可靠度造成嚴重的研究。本篇論文提出了一種用於NAND型快閃記憶體的錯誤檢查更正機制，和低延遲極性解碼器的設計。
    本論文有兩個主要研究主題：在NAND型快閃記憶體中應用極碼的錯誤更正機制和對應的低延遲SC解碼器設計。在第一個主題中，我們提出了一種具有系統極碼的多層級錯誤更正碼方案，用來解決資料可靠度和NAND型快閃記憶體耐久性的問題。在第二個主題中，提出一種低延遲的具代碼調整結構、行列狀的2位元SSC解碼器架構。為了節省多次感測方案的時間和連續取消解碼算法的自然性長延遲，採用p節點，rate-0節點和rate-1節點的概念來簡化解碼複雜度並降低解碼時間。基於蒙特卡洛信道估計和SC樹結構，我們可以選擇重新排列信息位和凍結位位置的模式，稱之為代碼調整構造，以減少解碼延遲。最後實驗結果顯示，與2Y-nm MLC快閃記憶體的公稱壽命相比，錯誤更正機制可以提升至原壽命的6.5倍時間。由於採用建議的簡化算法和代碼構造模式的SC解碼器的硬件實現，最多將解碼週期減少到8.1％的原始解碼週期。

    As the increasing of storage density of NAND flash memories, data reliability becomes a severe problem under the scaling of NAND flash and multi-level cell technology. In this thesis, the mechanisms are proposed to detect and correct errors with the low-latency design of polar decoder for NAND flash memory.
    There are two main research topics in this thesis : error correction mechanisms with polar code applied in NAND flash memory and low latency design of SC decoder. In the first topic, we propose a Multi- ECC scheme with systematic polar code to address the data reliability and the endurance of NAND flash memory issues. In the second topic, a line-based 2-bit SSC decoder architecture with bit-permutation construction is proposed for low-latency design. To save the time from the multi-sensing scheme and the natural of long-latency successive-cancellation decoding algorithm, the concept of p-node, rate-0 node, and rate-1 node are employed to simplify the decoding complexity and reduce the decoding latency. Base on the monte carlo channel estimation and the SC tree architecture, we could choose the pattern with rearrange the position of information bits and frozen bits which is called bit-permutation code construction, to reduce decoding latency as well. Finally, the experimental results show that the Multi-ECC scheme can reach about 6.5 times lifetime of 2Y-nm MLC flash memory compared with the nominal lifetime. As the hardware implementation of SC decoder with proposed simplified algorithm and code construction pattern, reduce the decoding cycle at most to 8.1% of original decoding cycles.

    摘 　 要 i ABSTRACT iii 誌謝 v Content vi List of Tables ix List of Figures x Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Thesis organization 3 Chapter 2 Background 4 2.1 Basics of NAND Flash Memory 4 2.1.1 Basic Operations 6 2.1.2 NAND Flash Device Organization 10 2.2 Data Reliability Issues 12 2.2.1 Program/Erase Cycle and Endurance 13 2.2.2 Cell-to-Cell Interference 14 2.2.3 Data Retention Error 16 2.3 Channel polarization 17 2.4 Construction of polar codes 18 2.4.1 Channel combining 18 2.4.2 Channel splitting 19 2.4.3 Recursive channel transformations 20 2.4.4 Bit-reversed indexing 20 2.5 Successive-cancellation decoding 21 2.6 Architecture of SC decoder 22 2.6.1 Fully-parallel architecture 23 2.6.2 Tree architecture 24 2.6.3 Line architecture 25 2.7 Simplified SC decoder 26 2.7.1 Min-sum approximation 26 2.7.2 P-node scheme 27 2.7.3 Rate-0 and rate-1 nodes 29 2.8 Systematic Polar Code 31 2.8.1 The Arıkan Systematic Encoder [4] 31 2.8.2 The Gabi Sarkis’s Systematic Polar code [13] 32 Chapter 3 Proposed Multi-ECC scheme and Bit Permutation of SSC decoder for MLC NAND Flash memory 33 3.1 Proposed Multi-ECC scheme 33 3.1.1 The flow of Multi-ECC mechanism 34 3.1.2 Direct output with CRC-check 35 3.1.3 Systematic polar code with hard-decision information 36 3.1.4 Systematic polar code with Quantized-soft information 37 3.2 Proposed Bit Permutation of SSC decoder for (1024, 922) polar codes 38 3.2.1 Monte Carlo Channel estimation 39 3.2.2 Bit Permutation of SSC architecture 40 3.2.3 The 2-bit simplified SC decoding algorithm flow 42 3.2.4 The simplification of g function 43 3.2.5 256-bits encoder for the implementation of rate-1 node 45 Chapter 4 Experimental Results and Complexity Analysis 47 4.1 Modeling of NAND Flash Memory Channel 47 4.2 Performance and Lifetime Evaluation 51 4.3 Hardware performance and complexity analysis 54 4.3.1 Line-based 2b SC decoder 54 4.3.2 Latency analysis for bit permutation of (1024, 922) SSC decoder 55 Chapter 5 Conclusion and Future Work 57 5.1 Conclusion 57 5.2 Future work 58 References 59

    [1] Erdal. Arıkan, " Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels," IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051–3073, July 2009.
    [2] Kai Niu, Kai Chen, Jiaru Lin and Q. T. Zhang, " Polar codes: Primary concepts and practical decoding algorithms," IEEE Communications Magazine, vol. 52, no. 7, pp. 192 - 203, July 2014.
    [3] Camille Leroux, Alexandre J. Raymond, Gabi Sarkis, and Warren J. Gross, " A semi-parallel successive-cancellation decoder for polar codes," IEEE Transactions on Signal Processing, vol. 61, no. 2, pp. 289 - 299, January 2013.
    [4] Erdal Arıkan, " Systematic Polar Coding," IEEE Communications Letters, vol. 15, no. 8, pp. 860 - 862, August 2011.
    [5] Gabi Sarkis, Ido Tal, Pascal Giard, Alexander Vardy, Claude Thibeault, and Warren J. Gross, " Flexible and Low-Complexity Encoding and Decoding of Systematic Polar Codes," IEEE Transactions on Communications, vol. 64, no. 7, pp. 2732 - 2745, July 2016.
    [6] Camille Leroux, Ido Tal, Alexander Vardy, and Warren J. Gross, "Hardware Architectures for Successive Cancellation Decoding of Polar Codes," in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1665-1668, May 2011.
    [7] Chuan Zhang and Keshab K. Parhi, " Low-Latency Sequential and Overlapped Architectures for Successive Cancellation Polar Decoder," IEEE Transactions on Signal Processing, vol. 6, no. 10, pp. 2429 - 2441, March 2013.
    [8] Bo Yuan and Keshab K. Parhi, " Low-Latency Successive-Cancellation Polar Decoder Architectures Using 2-Bit Decoding," IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 61, no. 4, pp. 1241 - 1254, April 2014.
    [9] A. Mishra, A. Raymond, L. Amaru, G. Sarkis, C. Leroux, P. Meinerzhagen, A. Burg, and W. J. Gross, “ A successive cancellation decoder ASIC for a 1024-bit polar code in 180nm CMOS,” IEEE Asian Solid-State Circuits Conference(A-SSCC), November 2012.
    [10] Amin Alamdar-Yazdi and Frank R. Kschischang, " A Simplified Successive-Cancellation Decoder for Polar Codes," IEEE Communications Letters, vol. 15, no. 12, pp. 1378 - 1380, December 2011.
    [11] Gabi Sarkis and Warren J. Gross, " Increasing the Throughput of Polar Decoders," IEEE Communications Letters, vol. 17, no. 4, pp. 725 - 728, April 2013.
    [12] Chuan Zhang and Keshab K. Parhi, " Latency Analysis and Architecture Design of Simplified SC Polar Decoders," IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 61, no. 2, pp. 115 - 119, February 2014.
    [13] Gabi Sarkis, Pascal Giard, Alexander Vardy, Claude Thibeault and Warren J. Gross, " Fast Polar Decoders: Algorithm and Implementation," IEEE Journal on Selected Areas in Communications, vol. 32, no. 5, pp. 946 - 957, May 2014.
    [14] Chenrong Xiong, Jun Lin and Zhiyuan Yan, " Error performance analysis of the symbol-decision SC polar decoder," IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), March 2016.
    [15] Guillaume Berhault, Camille Leroux, Christophe Jego and Dominique Dallet, " Partial sums generation architecture for successive cancellation decoding of polar codes," IEEE Workshop on Signal Processing Systems, October 2013.
    [16] Y. Li, H. Alhussien, E. F. Haratsch and A. A. Jiang, "A study of polar codes for MLC NAND flash memories," 2015 International Conference on Computing, Networking and Communications (ICNC), pp. 608-612 , 2015
    [17] Y. Cai, E. F. Haratsch, O. Mutlu and K. Mai, "Error patterns in MLC NAND flash memory: Measurement, characterization, and analysis," 2012 Design, Automation & Test in Europe Conference & Exhibition (DATE), pp. 521-526 , 2012
    [18] Y. Cai, E. F. Haratsch, O. Mutlu and K. Mai, "Threshold voltage distribution in MLC NAND flash memory: Characterization, analysis, and modeling," 2013 Design, Automation & Test in Europe Conference & Exhibition (DATE), pp. 1285-1290, 2013
    [19] A.Maislos et al. , “A New Era in Embedded Flash Memory” ,in Proc. of Flash Memory Summit, 2011
    [20] C.Marelli Rino, M. Luca, “Inside NAND Flash Memories,” Springer, New York, 2010.
    [21] N. Mielke et al., "Bit error rate in NAND Flash memories," 2008 IEEE International Reliability Physics Symposium, pp. 9-19 , 2008
    [22] Y. Cai et al., "Flash correct-and-refresh: Retention-aware error management for increased flash memory lifetime," 2012 IEEE 30th International Conference on Computer Design (ICCD), pp. 94-101, 2012
    [23] Y. Cai, O. Mutlu, E. F. Haratsch and K. Mai, "Program interference in MLC NAND flash memory: Characterization, modeling, and mitigation," 2013 IEEE 31st International Conference on Computer Design (ICCD), pp. 123-130, 2013
    [24] “NAND Flash Memory MT29F64G08CBAA, 64Gb, 128Gb, 256Gb, 512Gb Asynchronous/Synchronous NAND ”, Micron Technology Inc. , .
    [25] K. Hsu, C. Tsao, Y. Chang, T. Kuo and Y. Huang, "Proactive Channel Adjustment to Improve Polar Code Capability for Flash Storage Devices," 2018 55th ACM/ESDA/IEEE Design Automation Conference (DAC), pp. 1-6 , 2018
    [26] H. Choi, W. Liu and W. Sung, "VLSI Implementation of BCH Error Correction for Multilevel Cell NAND Flash Memory," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 18, no. 5, pp. 843-847, May 2010
    [27] J. Bian, S. Zhao and L. Kong, "Rate-adaptive Polar Codes Design for MLC NAND Flash Memory," 2018 IEEE 4th International Conference on Computer and Communications (ICCC), pp. 11-16 , 2018
    [28] Kang-Deog Suh et al., "A 3.3 V 32 Mb NAND flash memory with incremental step pulse programming scheme," in IEEE Journal of Solid-State Circuits, vol. 30, no. 11, pp. 1149-1156, Nov. 1995
    [29] Daesung Kim, Jinho Choi and Jeongseok Ha, "On the soft information extraction from hard-decision outputs in MLC NAND flash memory," 2012 IEEE Global Communications Conference (GLOBECOM), pp. 3208-3213, 2012
    [30] K. Park et al., "A Zeroing Cell-to-Cell Interference Page Architecture with Temporary LSB Storing Program Scheme for Sub-40nm MLC NAND Flash Memories and beyond," 2007 IEEE Symposium on VLSI Circuits, pp. 188-189, 2007
    [31] Jae-Duk Lee, Sung-Hoi Hur and Jung-Dal Choi, "Effects of floating-gate interference on NAND flash memory cell operation," in IEEE Electron Device Letters, vol. 23, no. 5, pp. 264-266, May 2002
    [32] M.P.C. Fossorier, M. Mihaljevic, and H. Imai, “Reduced complexity iterative decoding of low-density parity check codes based on belief propagation,” IEEE Trans. on Comm., vol. 47, no. 5, pp. 673 –680, May. 1999.
    [33] H. C. Song et al.” Polar-coded forward error correction for MLC NAND flash memory polar FEC for NAND flash memory” 2018 [online] Available: https://arxiv.org/abs/1802.04576.
    [34] J. Kim and W. Sung "Low-energy error correction of NAND Flash memory through soft-decision decoding" Eurasip J. Adv. Signal Process. vol. 2012 no. 1 pp. 195 Sep. 2012.
    [35] Kim, C., Yun, H., Ajaz, S., and Lee, H., “High-Throughput Low-Complexity Successive-Cancellation Polar Decoder Architecture using One's Complement Scheme.” Journal of Semiconductor Technology and Science, pp. 427-435, 2015

    下載圖示 校內：2024-08-27公開
    校外：2024-08-27公開
    QR CODE