極化碼在快閃記憶體中更正能力提升之主動式通道調整策略

Proactive Channel Adjustment to Improve Polar Code Capability for Flash Storage Devices

10.6342/NTU201701566

徐堃程

儲存系統 ； 可靠性 ； 極化碼 ； 通道調整 ； 超大規模快閃記憶體 ； storage system ； reliability ； polar code ； channel adjustment ； ultra-scale flash memory

國立臺灣大學資訊工程學系學位論文

2017年

碩士

郭大維

英文

Low-density parity-check (LDPC) codes have made a great success on correcting errors in flash storage devices, but its hardware cost and error correction time keeps increasing as the error rate of flash memory keeps increasing. To improve the lifetime of devices, researchers are seeking alternative methods. Fortunately, with the low encoding/ decoding complexity and the high error correction capability, polar code with the support of list-decoding and cyclic redundancy check can outperform LDPC code in the area of data communication. Thus, it also draws a lot of attentions on how to adopt and enable polar codes in storage applications. However, the code construction and encoding length limitation issues obstruct the adoption of polar codes in flash storage devices. To enable polar codes in flash storage devices, we propose a proactive channel adjustment design to extend the effective time of a code construction to improve the error correction capability of polar codes. This design pro-actively tunes the quality of the desirable flash cells to maintain the correctness of the code construction and relax the constraint of encoding length limitation. A series of experiments was conducted to evaluate the efficacy of the proposed design. It shows that the proposed design can effectively improve the error correction capability of polar codes in flash storage devices.

1. [1] E. Arikan. Channel polarization: A method for constructing capacity achieving codes for symmetric binary-input memoryless channels. 55(7):3051–3073, Jul 2009.
   連結：
2. [2] Raj Chandra Bose and Dwijendra K Ray-Chaudhuri. On a class of error correcting binary group codes. Information and control, 3(1):68–79, 1960.
   連結：
3. [3] Yu Cai, Erich F Haratsch, Onur Mutlu, and Ken Mai. Error patterns in mlc nand flash memory: Measurement, characterization, and analysis. In Proceedings of the Conference on Design, Automation and Test in Europe, pages 521–526. EDA Consortium, 2012.
   連結：
4. [4] Yu Cai, Erich F Haratsch, Onur Mutlu, and Ken Mai. Threshold voltage distribution in mlc nand flash memory: Characterization, analysis, and modeling. In Design, Automation & Test in Europe Conference & Exhibition (DATE), 2013, pages 1285–1290. IEEE, 2013.
   連結：
5. [5] Jaewon Cha and Sungho Kang. Data Randomization Scheme for Endurance Enhancement and Interference Mitigation of Multilevel Flash Memory Devices . ETRI Journal, 35(1):166–169, Feb 2013.
   連結：
6. [7] M Darnell. Error control coding: Fundamentals and applications. In IEE Proceedings F-Communications, Radar and Signal Processing, volume 132, page 68. IET, 1985.
   連結：
7. [8] Bertrand Le Gal, Camille Leroux, and Christophe Jego. Multi-Gb/s Software Decoding of Polar Codes. IEEE Transactions on Signal Processing, 63:349–359, Jan 2015.
   連結：
8. [9] Robert Gallager. Low-density parity-check codes. IRE Transactions on information theory, 8(1):21–28, 1962.
   連結：
9. [10] Pascal Giard, Gabi Sarkis, Claude Thibeault, and Warren J Gross. 237 gbit/s unrolled hardware polar decoder. Electronics Letters, 51(10):762–763, 2015.
   連結：
10. [12] Chien-Chung Ho, Yu-Ping Liu, and Yuan-Hao Chang. Antiwear Leveling Design for SSDs With Hybrid ECC Capability. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 25:488–501, Feb 2017.
    連結：
11. [14] Jung-Hoon Kim, Sang-Hoon Kim, and Jin-Soo Kim. Subpage programming for extending the lifetime of nand flash memory. In Design, Automation & Test in Europe Conference & Exhibition (DATE), 2015, pages 555–560. IEEE, 2015.
    連結：
12. [16] Liping Li, Wenyi Zhang, and Yanjun Hu. On the error performance of systematic polar codes. arXiv preprint arXiv:1504.04133, 2015.
    連結：
13. [18] Kai Niu, Kai Chen, Jiaru Lin, and QT Zhang. Polar codes: Primary concepts and practical decoding algorithms. IEEE Communications magazine, 52(7):192–203, 2014.
    連結：
14. [20] I. Tal and A. Vardy. How to construct polar codes. Sept 2010.
    連結：
15. [22] H. Vangala and E. Viterbo. A comparative study of polar code constructions for the awgn channel, 2015.
    連結：
16. [23] Jiadong Wang, Thomas Courtade, Hari Shankar, and Richard D. Wesel. Soft Information for LDPC Decoding in Flash: Mutual-Information Optimized Quantization. IEEE Global Telecommunications Conference(GLOBECOM), pages 1–6, Dec 2011.
    連結：
17. [24] Kai Zhao, Wenzhe Zhao, Hongbin Sun, Tong Zhang, Xiaodong Zhang, and Nanning Zheng. Ldpc-in-ssd: Making advanced error correction codes work effectively in solid state drives. In Proceedings of the 11th USENIX Conference on File and Storage Technologies, FAST’13, pages 243–256, Berkeley, CA, USA, 2013. USENIX Association.
    連結：
18. [6] Radjendirane Codandaramane. How ldpc enables new nand flash for enterprise ssds, 2015.
19. [11] S Hamed Hassani and Rudiger Urbanke. Universal polar codes. In Information Theory(ISIT), 2014 IEEE International Symposium on, pages 1451–1455. Ieee, 2014.
20. [13] Yu-Ming Huang, Hsiang-Pang Li, and Hsie-Chia Chang. Length-compatible extended polar codes, July 8 2015. US Patent App. 14/794,059.
21. [15] Jiangpeng Li, Kai Zhao, Xuebin Zhang, Jun Ma, Ming Zhao, and Tong Zhang. How Much Can Data Compressibility Help to Improve NAND Flash Memory Lifetime? File and Storage Technologies(FAST), Feb 2015.
22. [17] Yue Li, Hakim Alhussien, Erich F Haratsch, and Anxiao Andrew Jiang. A study of polar codes for mlc nand flash memories. In Computing, Networking and Communications(ICNC), 2015 International Conference on, pages 608–612. IEEE, 2015.
23. [19] 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, 32(5):946–957, 2014.
24. [21] Ido Tal and Alexander Vardy. List decoding of polar codes. In Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on, pages 1–5. IEEE, 2011.