NAND快閃記憶體(Flash Memories)隨著製程的進步，儲存密度(Storage Density)容量越來越高，但同時也使得儲存資料(Storage Data)受雜訊的影響越嚴重。因此，對儲存資料的可靠度需求與日俱增。為了確保資料的可靠性，必須有更強大的錯誤更正碼(Error Correction Code, ECC)輔助。本篇論文研究近期興起的錯誤更正碼－極化碼(Polar codes)，基於一個儲存單元能夠儲存兩個位元的NAND快閃記憶體，提出一個新穎的方法，四元素伽羅瓦體(Quaternary Galois field, GF(4))的極化碼應用在多層儲存單元(Multi-level cell, MLC) NAND快閃記憶體。
本論文用四階脈波振幅調變(4-level pulse- amplitude modulation, 4-PAM) 以及可加性高斯白雜訊通道(Additive white Gaussian noise, AWGN)來近似MLC NAND快閃記憶體的模型。本論文根據在4-PAM之下，GF(4)極化碼的表現優於GF(2)極化碼，可推論GF(4)極化碼可使資料的可靠性更有保障。
本論文針對GF(4) 極化碼提供三種解碼方案，分別為連續消除解碼(Successive Cancelation, SC)、連續消除翻轉解碼(Successive Cancelation Flip , SCF)與連續消除條列解碼(Successive Cancelation List, SCL)演算法，以更進一步的改善 GF(4) 極化碼的性能。最後，本論文針對多層儲存單元NAND快閃記憶體通道進行極化碼的建構、極化編碼，並與 GF(2) 極化碼比較，得到GF(4)極化碼的位元錯誤率約有1 dB的改善。

Due to the process of technology scaling down, the storage density of the memories increases progressively. However, the storage data is affected more easily by noise at the same time. That effect results in the data reliability reduced. Hence, adding powerful error correction codes (ECCs) is inevitable. In this work, we study the current ECC, polar codes, which get researchers’ attention. Moreover, we propose a novel idea that is the application of the quaternary Galois field (GF(4)) polar codes to the multi-level cell (MLC) NAND flash memories. Under the mechanism of the MLC NAND flash model，We first observe that the simulation results of the GF(4) polar codes with the 4-level pulse-amplitude modulation (PAM4) are better than the GF(2) at the high signal-to-noise ratio(SNR). Therefore, our proposed method can reduce the bit error rate (BER) and improve the reliability of MLC NAND flash memories.

[1] E. Arikan, "Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels," in IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051-3073, July 2009, doi: 10.1109/TIT.2009.2021379.

[2] E. Şaşoğlu, E. Telatar and E. Arikan, "Polarization for arbitrary discrete memoryless channels," 2009 IEEE Information Theory Workshop, Taormina, 2009, pp. 144-148, doi: 10.1109/ITW.2009.5351487.

[3] R. Mori and T. Tanaka, "Source and Channel Polarization Over Finite Fields and Reed–Solomon Matrices," in IEEE Transactions on Information Theory, vol. 60, no. 5, pp. 2720-2736, May 2014, doi: 10.1109/TIT.2014.2312181.

[4] J. Xiao-bo, T. Xue-qing and H. Wei-pei, "Novel ECC structure and evaluation method for NAND flash memory," 2015 28th IEEE International System-on-Chip Conference (SOCC), Beijing, 2015, pp. 100-104, doi: 10.1109/SOCC.2015.7406921.

[5] 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), Garden Grove, CA, 2015, pp. 608-612, doi: 10.1109/ICCNC.2015.7069414.

[6] 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), Dresden, 2012, pp. 521-526, doi: 10.1109/DATE.2012.6176524.
 
[7] O. Afisiadis, A. Balatsoukas-Stimming and A. Burg, "A low-complexity improved successive cancellation decoder for polar codes," 2014 48th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, 2014, pp. 2116-2120, doi: 10.1109/ACSSC.2014.7094848.

[8] I. Tal and A. Vardy, "List Decoding of Polar Codes," in IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2213-2226, May 2015, doi: 10.1109/TIT.2015.2410251.

[9] S. M. Kay, Fundamentals of Statistical Signal Processing: Detection Theory, Vol. II, 1998, Prentice Hall.

[10] Micheloni, Rino, Luca Crippa, and Alessia Marelli. Inside NAND flash memories. 2010, Springer Science & Business Media.

[11] A. Balatsoukas-Stimming, M. B. Parizi and A. Burg, "LLR-Based Successive Cancellation List Decoding of Polar Codes," in IEEE Transactions on Signal Processing, vol. 63, no. 19, pp. 5165-5179, Oct.1, 2015, doi: 10.1109/TSP.2015.2439211.

[12] H. Song, C. Zhang, S. Zhang and X. You, "Polar code-based error correction code scheme for NAND flash memory applications," 2016 8th International Conference on Wireless Communications & Signal Processing (WCSP), Yangzhou, 2016, pp. 1-5, doi: 10.1109/WCSP.2016.7752700.

[13] G. D. Forney and G. Ungerboeck, "Modulation and coding for linear Gaussian channels," in IEEE Transactions on Information Theory, vol. 44, no. 6, pp. 2384-2415, Oct. 1998, doi: 10.1109/18.720542.

[14] 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), Grenoble, France, 2013, pp. 1285-1290, doi: 10.7873/DATE.2013.266.

[15] F. Masuoka, M. Asano, H. Iwahashi, T. Komuro and S. Tanaka, "A new flash E2PROM cell using triple polysilicon technology," 1984 International Electron Devices Meeting, San Francisco, CA, USA, 1984, pp. 464-467, doi: 10.1109/IEDM.1984.190752.

[16] R. Bez, E. Camerlenghi, A. Modelli and A. Visconti, "Introduction to flash memory," in Proceedings of the IEEE, vol. 91, no. 4, pp. 489-502, April 2003, doi: 10.1109/JPROC.2003.811702.

[17] M. Fujiwara et al., "3D Semicircular Flash Memory Cell: Novel Split-Gate Technology to Boost Bit Density," 2019 IEEE International Electron Devices Meeting (IEDM), San Francisco, CA, USA, 2019, pp. 28.1.1-28.1.4, doi: 10.1109/IEDM19573.2019.8993673.

[18] E. Arikan, "Systematic Polar Coding," in IEEE Communications Letters, vol. 15, no. 8, pp. 860-862, August 2011, doi: 10.1109/LCOMM.2011.061611.110862.

[19] G. Sarkis, P. Giard, A. Vardy, C. Thibeault and W. J. Gross, "Fast Polar Decoders: Algorithm and Implementation," in IEEE Journal on Selected Areas in Communications, vol. 32, no. 5, pp. 946-957, May 2014, doi: 10.1109/JSAC.2014.140514.

[20] P. Yuan and F. Steiner, "Construction and Decoding Algorithms for Polar Codes based on 2 × 2 Non-Binary Kernels," 2018 IEEE 10th International Symposium on Turbo Codes & Iterative Information Processing (ISTC), Hong Kong, Hong Kong, 2018, pp. 1-5, doi: 10.1109/ISTC.2018.8625284.

[21] P. Giard and A. Burg, "Fast-SSC-flip decoding of polar codes," 2018 IEEE Wireless Communications and Networking Conference Workshops (WCNCW), Barcelona, 2018, pp. 73-77, doi: 10.1109/WCNCW.2018.8369026.

[22] A. Alamdar-Yazdi and F. R. Kschischang, "A Simplified Successive-Cancellation Decoder for Polar Codes," in IEEE Communications Letters, vol. 15, no. 12, pp. 1378-1380, December 2011, doi: 10.1109/LCOMM.2011.101811.111480.

[23] W. Park and A. Barg, "Polar Codes for Q-Ary Channels, $q=2^{r}$," in IEEE Transactions on Information Theory, vol. 59, no. 2, pp. 955-969, Feb. 2013, doi: 10.1109/TIT.2012.2219035.

[24] S. A. Hashemi, A. Balatsoukas-Stimming, P. Giard, C. Thibeault and W. J. Gross, "Partitioned successive-cancellation list decoding of polar codes," 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Shanghai, 2016, pp. 957-960, doi: 10.1109/ICASSP.2016.7471817.

[25] F. Ercan, C. Condo, S. A. Hashemi and W. J. Gross, "Partitioned Successive-Cancellation Flip Decoding of Polar Codes," 2018 IEEE International Conference on Communications (ICC), Kansas City, MO, 2018, pp. 1-6, doi: 10.1109/ICC.2018.8422464.

[26] X. Wang, T. Wang, J. Li and Y. Zhang, "Improved Multiple Bit-Flipping Fast-SSC Decoding of Polar Codes," in IEEE Access, vol. 8, pp. 27851-27860, 2020, doi: 10.1109/ACCESS.2020.2964904.

[27] C. Xiong, J. Lin and Z. Yan, "Symbol-Decision Successive Cancellation List Decoder for Polar Codes," in IEEE Transactions on Signal Processing, vol. 64, no. 3, pp. 675-687, Feb.1, 2016, doi: 10.1109/TSP.2015.2486750.

[28] M. Bakshi, S. Jaggi and M. Effros, "Concatenated Polar codes," 2010 IEEE International Symposium on Information Theory, Austin, TX, 2010, pp. 918-922, doi: 10.1109/ISIT.2010.5513508.

[29] S. M. Abbas, Y. Fan, J. Chen and C. Tsui, "Concatenated LDPC-polar codes decoding through belief propagation," 2017 IEEE International Symposium on Circuits and Systems (ISCAS), Baltimore, MD, 2017, pp. 1-4, doi: 10.1109/ISCAS.2017.8050835.

[30] Y. Wang, L. Chen, C. Liu and Z. Xing, "An Improved Concatenation Scheme of BCH-Polar Codes With Low-Latency Decoding Architecture," in IEEE Access, vol. 7, pp. 95867-95877, 2019, doi: 10.1109/ACCESS.2019.2929188.

[31] Q. Yu, Z. Shi, X. Li, J. Du, J. Zhang and K. M. Rabie, "On the Concatenations of Polar Codes and Non-Binary LDPC Codes," in IEEE Access, vol. 6, pp. 65088-65097, 2018, doi: 10.1109/ACCESS.2018.2877178.