Report

The Performance of Polar Codes for Multi-level Flash Memories Yue Li joint work with Hakim Alhussien, Erich F. Haratsch, and Anxiao (Andrew) Jiang March 10th, 2014 NAND Flash Memory … … … The circuit board of a SSD Blocks … 4 pages/WL 2 Multi-Level Cells 10 00 01 11 2 bits/cell • Four different kinds of pages: • Lower even • Lower odd • Upper even • Upper odd 3 Why Polar Codes? • Desire for optimal ECCs. • Excellent properties – Capacity-achieving – Theoretical guarantee of error floor performance – Efficient encoding and decoding algorithms 4 Encoding Input User Bits Frozen bits Polar Codeword Flash channels Frozen Channels G Noisy Codeword Information Bits Erdal Arıkan, “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels," IEEE Transactions on Information Theory, 2009. confidential 5 Successive Cancellation Decoding Frozen Channels Estimated user bits Noisy Codeword Erdal Arıkan, “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels," IEEE Transactions on Information Theory, 2009. confidential 6 Successive Cancellation Decoding Frozen Channels Estimated user bits Noisy Codeword Erdal Arıkan, “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels," IEEE Transactions on Information Theory, 2009. confidential 7 Successive Cancellation Decoding Frozen Channels Estimated user bits Noisy Codeword Erdal Arıkan, “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels," IEEE Transactions on Information Theory, 2009. confidential 8 Is polar code suitable for flash memories? 1 • Make polar code work in flash memory 2 • Performance evaluations 3 • Adaptive decoding Code Length Adaptation • Polar codes have length N = 2m • The code lengths in flash memory need to be flexible. 10 Shortening M K – K’ C K’ N – K’ Noisy C Est. M N – K’ K – K’ K’ 11 (N, K, K’)-Shortened Polar Code (x1, x2, …, xN-k’+1, …, xN)=(u1, u2, …, uN-k’+1, …, uN) G (x1, x2, …, 0, …, 0)=(u1, u2, …, 0, …, 0) G 1 K’ 0 … 0 0 … 0 … 0 … 1 0 1 ç (u1, u2, …, uN-k’+1, …, uN) 0 1 ç K’ 12 Evaluation with Random Data Pseudo-random Data (0, 1, 1, 0, …, 1) (1, 0, 1, 0, …, 1) … (1, 0, 1, 0, …, 1) Cycling / Retention Not generated by polar encoder (0, 0, 1, 1, …, 1) (1, 0, 0, 0, …, 1) … (0, 0, 1, 1, …, 1) 13 Treating Random Data as Codewords (u1, u2, …, uN) = (x1, x2, …, xN) G-1 Invertible Input Output Channel parameters Construct codes Frozen Bits 14 Hard and Soft Sensing Reference threshold voltages 11 01 00 10 Cell Voltage P( V | bit = 0 ) ___________________ LLR = log P( V | bit = 1 ) 15 2 •Performance Evaluation 16 Experimental Setup • Construct one polar code for each kind of page. • List successive cancellation decoding [Tal and Vardy 2011] – List size = 32 with CRC • Block length – 7943 bits shortened from 8192 bits • Code rates – 0.93, 0.94, 0.95 • Flash data – obtained by characterizing 2X-nm MLC flash chips – 6-month retention 17 Hard and Soft Decoding Hard Decoding Soft Decoding 18 Different Block Lengths 19 Asymmetric and Symmetric Errors 20 3 •Adaptive Decoding 21 Code Rate Switching Is repetitive code construction needed at rate-switching PECs? BER Correction Capability 0 R1 pec1 R2 pec2 R2 pec3 PEC 22 Why Code Reconstruction is Not Needed? 23 With and Without Code Reconstruction Upper odd page Average 24 Summary • On the flash data – Polar codes are comparable to LDPC codes using hard and soft sensing – Larger block lengths do not improve decoding performance a lot – More symmetric, better decoding performance – Repetitive code construction is not necessary for adaptive decoding 25 Future Directions • Error floor performance • Comparing with LDPC decoder with the same hardware latency • Efficient hardware implementations 26