極化碼(polar codes)被證明可用於實現通道容量，為現今編碼理論的突破，而接續消除(successive-cancellation, SC)解碼為最基本的解碼方式，接續消除列表(successive-cancellation list, SCL)解碼可以改善SC解碼的更正能力，為現有解碼方案中主要做法。另一方面，簡化接續消除(simplified successive-cancellation, SSC)解碼中利用比率-0(rate-0)節點和比率-1(rate-1)節點特性來減少解碼週期。
NAND型快閃記憶體因其高通量和低功率特性，廣泛應用在儲存裝置。其中如何為持資料可靠性為重要的課題。
本論文將極化碼應用於快閃記憶體，實現快閃記憶體的特性與極化碼解碼方式來比較性能表現。本論文提出改變極化碼位元排列的方法，為了將訊息位元和凍結位元交換後達到降低解碼延遲的效果，同時要考量對性能的影響。
本文針對(1024,922)極化碼改變位元排列並應用於快閃記憶體中，使用量化軟決策和SC解碼方式。改變位元排列後，解碼延遲可以減少19.56%，快閃記憶體使用壽命則從19.5K P/E cycles降到18K P/E cycles。

Polar codes are the latest breakthrough in coding theory, as they provably achieve the channel capacity. Successive-cancellation (SC) decoding is the basic decode method. Successive-cancellation list (SCL) decoding can improve the correction ability of SC decoding, which is the main method in the existing decoding scheme. Rate-0 and rate-1 nodes are used to reduce the decoding cycles in simplified successive-cancellation (SSC) decoding.
NAND flash memory has been widely used for data storage due to its high throughput and low power. How to maintain the data reliability is an important issue.
We apply polar codes to flash memory. We implement the characteristics of flash memory and polar decoding method. After that we compare the performance of different methods. We propose a method to change the bit permutation of polar codes. We exchange the location of information bits and the location of frozen bits in order to reduce the decoding cycles. Simultaneously, we need to consider the influence of performance.
We change the bit permutation of (1024, 922) polar code and then apply it to flash memory. We use quantized soft decoding method and SC decoder to simulate. After we change the permutation, the decoding cycles can be reduced by 19.56%, and the lifetime of the flash memory is reduced from 19.5K P/E cycles to 18K P/E cycles.

[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, July 2009.
[2] Camille Leroux, Ido Tal, Alexander Vardy, and Warren J. Gross, “Hardware architectures for successive cancellation decoding of polar codes,” in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.1665-1668, May 2011.
[3] Ido Tal and Alexander Vardy, “List Decoding of Polar Codes,” IEEE Transactions on Information Theory, vol. 61, no. 5, May 2015.
[4] Bo Yuan and Keshab K. Parhi, “Successive cancellation list polar decoder using log-likelihood ratios,” in Proceedings of 48th Asilomar Conference on Signals, Systems and Computers, November 2014.
[5] Amin Alamdar-Yazdi and Frank R. Kschischang, “A Simplified Successive-Cancellation Decoder for Polar Codes,” IEEE Communications Letters, vol. 15, no. 12, December 2011.
[6] 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 & Test in Europe Conference & Exhibition (DATE), pp 521-526, 2012.
[7] Yu Cai, Erich F. Haratsch, Onur Mutlu and Ken Mai, “Threshold Voltage Distribution in MLC NAND Flash Memory: Measurement, Characterization, and Analysis,” in Proceedings of the Conference on Design, Automation & Test in Europe Conference & Exhibition (DATE),pp. 1285-1290, 2013.
[8] Yu Cai, Erich F. Haratsch, Onur Mutlu and Ken Mai, “Neighbor-Cell Assisted Error Correction for MLC NAND Flash Memories,” in Proceedings of the Conference on The 2014 ACM international conference on Measurement and modeling of computer systems, pp.491-504, 2014.
[9] Yu Cai, Onur Mutlu, Erich F. Haratsch and Ken Mai, “Program Interference in MLC NAND Flash Memory: Measurement, Characterization, and Analysis,” in Proceedings of the Conference on 2013 IEEE 31th International Conference on computer Design, ICCD , pp. 123-130 , 2013.
[10] Yu Cai, Gulay Yalcin, Onur Mutlu, Erich F. Haratsch, Adrian Cristal, Osman S. Unsal and Ken Mai, "Flash correct-and-refresh: Retention-aware error management for increased flash memory lifetime," in Proceedings of the Conference on 2012 IEEE 30th International Conference on Computer Design (ICCD), pp. 94-101, 2012
[11] “64Gb, 128Gb, 256Gb, 512Gb Asynchronous/Synchronous NAND Features,” Micron Technology Inc., 2010.
[12] Haochuan Song, Frankie Fu, Cloud Zeng, Jin Sha, Zaichen Zhang, Xiaohu You and Chuan Zhang, “Polar-Coded Forward Error Correction for MLC NAND Flash Memory Polar FEC for NAND Flash Memory,” arXiv:1802.04576, Feb. 2018.
[13] Kun-Cheng Hsu, Che-Wei Tsao, Yuan-Hao Chang, Tei-Wei Kuo, Yu-Ming
Huang, “Proactive Channel Adjustment to Improve Polar Code Capability for Flash Storage Devices,” in Proceedings of the Conference on 2018 55th ACM/ESDA/IEEE Design Automation Conference(DAC), 2018.
[14] Bingli Jiao, Yuli Yang and Mingxi Yin, “Cocktail BPSK: Achievable Data Rate beyond Channel Capacity”, arXiv:1901.06122, Jan. 2019.
[15] C. Zhang and K. 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, Feburary 2014.
[16] J. Lee, Sung-Hoi Hur, and Jung-Dal Choi, “Effects of Floating-Gate Interference on NAND Flash Memory Cell Operation,” IEEE Electrons Device Letters, vol. 23, no. 5, MAY 2002.