Abstract:
A method includes, in one aspect, performing a read operation on a wordline of a memory device, wherein the wordline comprises a plurality of cells that are expected to be in a first state; based on the read operation, identifying one or more of the plurality of cells that are determined to be in a second state that differs from the first state; encoding data using information pertaining to the identified cells to generate a codeword comprising a plurality of bits to be written to the wordline, with at least one of the plurality of bits, which are to be written to at least one of the identified cells, having a value corresponding to the second state; and writing the generated codeword to the wordline

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the benefit of priority under 35 U.S.C. §119(e) to provisional U.S. Patent Application No. 62/071,698 filed on Sep. 30, 2014, the entire contents of which are hereby incorporated by reference. 
     
    
     BACKGROUND 
       [0002]    The present disclosure relates to reducing errors caused by inter-cell interference in a memory device. 
         [0003]    Storage density of a memory device can be increased by decreasing the size of individual memory cells, decreasing the distance between adjacent (neighboring) memory cells, or both. However, decreasing the size of individual memory cells or decreasing the distance between adjacent memory cells may increase inter-cell interference (ICI) between adjacent memory cells. 
       SUMMARY 
       [0004]    The present disclosure describes systems and methods for reducing errors caused by inter-cell interference in a memory device. In one aspect, a method includes performing a read operation on a wordline of a memory device, wherein the wordline comprises a plurality of cells that are expected to be in a first state. Based on the read operation, one or more of the plurality of cells that are determined to be in a second state that differs from the first state is identified. Data is encoded using information pertaining to the identified cells to generate a codeword that includes a plurality of bits to be written to the wordline, with at least one of the plurality of bits, which are to be written to at least one of the identified cells, having a value corresponding to the second state. The generated codeword is written to the wordline. 
         [0005]    Implementations of the disclosure can include one or more of the following features. Performing the read operation on the wordline of the memory device may include performing a pre-read operation using a pre-read voltage on the wordline of the memory device, wherein the plurality of cells of the wordline are expected to be in a first state, and identifying the one or more of the plurality of cells comprises identifying the one or more of the plurality of cells that are determined to be in a second state by determining that a threshold voltage of the one or more of the plurality of cells is higher than the pre-read voltage. The pre-read voltage may differ from a voltage used to read data previously written to the memory device. The memory device may include a flash memory device, and the method may include receiving the data to be written to the wordline of the flash memory device. The flash memory device may include a single-level cell flash memory device, and the method may include receiving the data to be written to the wordline of the single-level cell flash memory device. The memory device may include a phase change memory device, and the method may include receiving the data to be written to the wordline of the phase change memory device. The memory device may include a resistive memory device, and the method may include receiving the data to be written to the wordline of the resistive memory device. Encoding the data may include generating the codeword using a partitioned linear block code. Encoding the data may include determining whether a first parity vector for generating the at least one of the plurality of bits based on locations of all of the one or more identified cells exists; when the first parity vector exists, determining the first parity vector based on the locations of all of the one or more identified cells; when the first parity vector does not exist, selecting a subset of the one or more identified cells; and determining a second parity vector for generating the at least one of the plurality of bits based on locations of the selected subset of the one or more identified cells. A number of elements in the selected subset may be less than a minimum distance for masking defects of a partitioned linear block code. Determining the first or second parity vector for masking defects may include determining the first or second parity vector for masking defects using 
         [0000]        G   0   Ψ   d=G   1   Ψ   m −( s   + ) Ψ ,
 
         [0000]    where Ψ indicates the locations of all of the one or more identified cells or the locations of the selected subset, G 0   Ψ  is a first generator matrix, G 1   Ψ  is a second generator matrix, (s + ) Ψ  represents side information corresponding to the locations, m is the data to be encoded, and d denotes the first or second parity vector for generating the at least one of the plurality of bits. 
         [0006]    All or part of the foregoing may be implemented as a computer program product including instructions that are stored on one or more non-transitory machine-readable storage media, and that are executable on one or more processing devices. All or part of the foregoing may be implemented as an apparatus, method, or system that may include one or more processing devices and memory to store executable instructions to implement the stated functions. 
         [0007]    The details of one or more implementations are set forth in the accompanying drawings and the description below. While specific implementations are described, other implementations exist that include operations and components different than those illustrated and described below. Other features, objects, and advantages will be apparent from the description, the drawings, and the claims. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]      FIG. 1  is a schematic drawing showing an example of a memory block in a flash memory device. 
           [0009]      FIG. 2  is a graph showing an example of threshold voltage distribution of memory cells in a single-level cell flash memory device. 
           [0010]      FIG. 3  is a graph showing an example of threshold voltage distribution of memory cells in a multi-level cell flash memory device. 
           [0011]      FIG. 4  is a diagram showing an example of inter-cell interference between adjacent cells in a memory device. 
           [0012]      FIG. 5  is a graph showing an example of threshold voltage distribution of memory cells in the i-th WL before writing the (i−1)-th WL of the memory device shown in  FIG. 4 . 
           [0013]      FIG. 6  is a graph showing an example of threshold voltage distribution of memory cells in the i-th WL after writing the (i−1)-th WL and before writing the i-th WL of the memory device shown in  FIG. 4 . 
           [0014]      FIG. 7  is a diagram showing an example of a channel model for a memory having defective cells. 
           [0015]      FIG. 8  is a block diagram showing an example of a system for reducing errors caused by ICI in a memory device. 
           [0016]      FIG. 9  is a flowchart of an example of a process for reducing errors caused by ICI in a memory device. 
       
    
    
     DETAILED DESCRIPTION 
       [0017]      FIG. 1  is a schematic drawing showing an example of a memory block  100  in a flash memory device. As shown in  FIG. 1 , the memory block  100  is a two-dimensional array of memory cells, including a memory cell  102 , connected to a page buffer  104 . Each cell is connected to a string select line (SSL), a wordline (WL), a ground select line (GSL), or a common source line (CSL). Each cell is also connected to a bitline (BL). Although a typical flash memory block can include 64 WLs, any suitable number of WLs is possible. 
         [0018]    Each memory cell may be a floating gate transistor having a threshold voltage that can be configured by controlling the amount of electron charges in the floating gate. Increasing the electron charges in the floating gate will increase the cell&#39;s threshold voltage. For a B-bits per cell memory device, each WL stores B-pages of data. To store B-bits per cell, each cell&#39;s threshold voltage distribution is divided into 2 B  states. 
         [0019]      FIG. 2  is a graph  200  showing an example of threshold voltage distribution of memory cells of 1-bit per cell flash memory device, also referred to as a single-level cell (SLC) flash memory device. In graph  200 , the x-axis represents the voltage threshold distribution and the y-axis represents the normalized cell count of the flash memory device. Initially, all memory cells are erased, so their threshold voltage is in the lowest state S 0 , also referred to as an erased state. To store data, a cell in state S 0  is programmed (or written) so that its threshold voltage is in a higher state S 1 , also referred to as a programmed state. 
         [0020]      FIG. 3  is a graph  300  showing an example of threshold voltage distribution of memory cells in a multi-level cell (MLC) flash memory device. A MLC flash memory device stores two or more bits per cell. In graph  300 , the x-axis represents the voltage threshold distribution and the y-axis represents the normalized cell count of the flash memory device. Initially, all memory cells are erased, so their threshold voltage is in the lowest state S 0 . A cell can be programmed so that its threshold voltage is in one of the programmed states S 1 , S 2 , . . . , S 2     B     -1 . 
         [0021]    Referring again to  FIG. 1 , a page of data (within a WL) can be written or read. To perform a write (or program) operation on a memory cell, incremental step pulse programming (ISPP) can be applied to the memory cell with each incremental step resulting in a slight increase of the cell&#39;s threshold voltage. The ISPP is based on repeated program and verify cycles with the staircase program voltage V pp . Each program state associates with a verify level that is used in the verify operation. During each program and verify cycle, the floating gate threshold voltage is boosted by up to the incremental step voltage ΔV pp  and then compared with the corresponding verify level. If the threshold voltage of the memory cell is still lower than the verify level, the program and verify iteration continues. Otherwise, further programming of this cell is disabled. 
         [0022]    The positions of program states are determined by verify levels, and the tightness of each program state depends on the incremental step voltage ΔV pp . By reducing ΔV pp , the threshold voltage distribution can be made tighter, but the write time may increase. 
         [0023]    To perform a read operation, the threshold voltages of cells in the same WL are compared with a given read level. After the read operation, a page of binary data is transferred to the page buffer  104 . The binary data indicates whether the threshold voltage of each cell in the WL is lower or higher than the read level. Because the read operation of flash memory is a binary decision, multiple read operations are required to obtain a soft decision value, which lowers the read speed. The degradation of read speed may be a challenge for soft decision decoding and signal processing. 
         [0024]    The threshold voltage of a flash memory cell can be reduced by an erase operation. In a flash memory device, all memory cells in the same flash memory block, e.g., block  100 , may be erased at the same time. The erase operation moves the threshold voltage of the cells into the lowest state S 0 . 
         [0025]    As described above, a page of data (within a WL) can be written, and a block of data can be erased at the same time. In addition, the threshold voltage of cell is moved into the lowest state S 0  by an erase operation, whereas a slight increase of threshold voltage is possible by ISPP during a write operation. These unique properties of flash memory cause asymmetry between write and erase operations. 
         [0026]    In flash memory, the threshold voltage shift of one cell, e.g., as a result of being programmed, affects the threshold voltage of its adjacent cell because of inter-cell interference (ICI). The ICI may be attributed to parasitic capacitances coupling effect between adjacent cells.  FIG. 4  is a diagram  400  showing an example of the ICI between adjacent cells in a flash memory device. V (i,j)  is the threshold voltage of the (i,j) cell which is situated at the i-th WL and the j-th BL. γ x  is the t-directional coupling ratio between a BL and an adjacent BL. Also, γ y  is the y-directional coupling ratio between a WL and an adjacent WL. Finally, γ xy  is the xy-directional (diagonal) coupling ratio. These coupling ratios depend on parasitic capacitances between adjacent cells. As the cell size becomes smaller or the distances between cells become smaller, the parasitic capacitances may become larger. The increase of parasitic capacitances causes the increase of the coupling ratios. 
         [0027]    The threshold voltage shift Δ ICI V (i,j)  of the (i,j) cell due to the ICI may be given by 
         [0000]      Δ ICI   V   (i,j) =γ x (Δ V   (i,j−1)   +ΔV   (i,j+1) )+γ y (Δ V   (i−1,j)   +ΔV   (i+1,j) )+γ xy (Δ V   (i−1,j−1)   +ΔV   (i−1,j+1)   +ΔV   (i+1,j−1)   +ΔV   (i+1,j+1) )
 
         [0000]    where ΔV (i±1,j±1)  in the right hand side of the above equation represent the threshold voltage shifts of adjacent cells after the (i,j) cell has been programmed. The ICI that happens before writing to the (i,j) cell can be compensated by several write schemes so long as the (i,j) cell is being written into a programmed state. Note that the ICI to the (i,j) cell that is to remain in state S 0  cannot be compensated by these write schemes since a cell that is to remain in S 0  is never programmed. 
         [0028]      FIG. 5  is a graph  500  showing an example of threshold voltage distribution of single-level memory cells in the i-th WL before writing the (i−1)-th WL of the memory device shown in  FIG. 4 . In graph  500 , the x-axis represents the voltage threshold distribution and the y-axis represents the normalized cell count of the memory device. The dashed curve  502  represents the designated threshold voltage distributions for state S 1 . The solid curve  504  represents a current threshold voltage distribution for state S 0 . Initially, all cells in the i-th WL have threshold voltages in the erased state S 0 . 
         [0029]      FIG. 6  is a graph  600  showing an example of threshold voltage distribution of the single-level memory cells in the i-th WL after writing the (i 1)-th WL and before writing the i-th WL of the memory device shown in  FIG. 4 . In graph  600 , the x-axis represents the voltage threshold distribution and the y-axis represents the normalized cell count of the memory device. The dashed curve  602  represents the designated threshold voltage distributions for state S 0 . The dashed curve  604  represents the designated threshold voltage distributions for state S 1 . The solid curve  606  represents a current threshold voltage distribution for state S 0 . After writing the adjacent (i−1)-th WL, the threshold voltages of cells in the i-th WL will be distorted, as shown by the curve  606 , due to the ICI from the (i−1)-th WL. Thus, the threshold voltages of some cells in the i-th WL may be higher than the given read level η though the i-th WL has yet to be written. 
         [0030]    In a memory device where state S 0  denotes the data “0” and state S 1  denotes the data “1”, only a “1” can be written into a cell. If a “0” is attempted to be written to a cell, an error will result. Thus, the threshold voltage of flash memory cells cannot be reduced using a write operation. To decrease the threshold voltage of a cell in the i-th WL, an erase operation may be performed on the whole flash memory block that includes the i-th WL, which may not be desirable. Thus, cells in the i-th WL with threshold voltages that are higher than the read level η cannot be programmed into state S 0  and are thus always in state S 1 . Such cells may be regarded as stuck-at 1 defects. 
         [0031]    A binary memory cell may be called a defective cell if its cell value is stuck-at a particular value regardless of the channel input.  FIG. 7  is a diagram showing an example of a channel model  700  for a memory having defective cells. The channel model  700  has a ternary defect information S + ε{0,1,λ} whereas the channel input X and output Y are binary. The state S + =0 corresponds to a stuck-at 0 defect that always outputs a 0 independent of its input value, the state 5 + =1 corresponds to a stuck-at 1 defect that always outputs a 1, and the state S + =λ corresponds to a normal cell that can be modelled by a binary symmetric channel (BSC) with crossover probability p. The probabilities of these states (namely 0, 1, and λ) are ε 0 ,ε 1 , and 1−ε 0 −ε 1 , respectively. 
         [0032]      FIG. 8  is a block diagram showing an example of a system  800  for reducing errors caused by ICI in a memory device. The system  800  includes an encoder  802 , a decoder  804 , a channel  806 , and a pre-read unit  808 .  FIG. 8  will be described in conjunction with  FIG. 9 , which is a flowchart of an example of a process  900  for reducing errors caused by ICI in a memory device. The process  900  may be performed by the system  800  shown in  FIG. 8 . 
         [0033]    Suppose that S n  represents the ICI of n memory cells. Because it may be a challenge to determine S n  due to properties of the memory device, the channel  806  with the ICI may be modelled using a channel with defective cells. The encoder  802  may use the side information of defects (S + ) n , rather than the side information of ICI S n , to improve the decoding failure probability. 
         [0034]    The side information of defects (S + ) n  for the i-th WL may be obtained by a pre-read operation performed by the pre-read unit  808  ( FIG. 9  at  904 ). The pre-read operation may be performed after receiving data and before writing the data to the i-th WL ( FIG. 9  at  902 ). The pre-read operation is performed at a given read level. When the read level for the pre-read operation, referred to as the pre-read level η pre , is the same as the read level η for reading data, the cells having threshold voltages that are higher than the read level η, and thus regarded as stuck at state S 1 , can be identified by the pre-read operation ( FIG. 9  at  906 ). The pre-read unit  808  provides the side information of defects (S + ) n  to the encoder  802 . Because the pre-read unit  808  obtains the side information through a single read operation of the wordline, the system  800  does not experience a degradation of read speed. 
         [0035]    The side information of defects (S + ) n  may contain partial information about the ICI of n memory cells, referred to as S n . (S + ) n  is binary because it is obtained from one pre-read operation. In addition, (S + ) n  does not reveal the ICI from the (i+1)-th WL and the x-directional ICI, which are subsequent ICI since the pre-read operation is performed before the write operation of the i-th WL and the (i+1)-th WL. However, this partial knowledge of (S + ) n  may improve the probability of decoding failure. 
         [0036]    Referring to  FIG. 6 , the ICI from the (i+1)-th WL and the x-directional ICI may be compensated by changing the read level η pre  for the pre-read operation, e.g., selecting the pre-read level η pre  to be lower than the read level η. A cell whose threshold voltage is between η pre  and η is a vulnerable cell though it is not a stuck-at 1 defect. When the data “0” is written to this cell, the ISPP cannot change the threshold voltage of this cell and its threshold voltage is near η. Thus, it may be vulnerable to the subsequent ICI and read noise. On the other hand, the cell&#39;s threshold voltage will be higher than a verify level of S 1  by the ISPP when the data “1” is written to this cell. Note that the verify level of S 1  is higher than the read level η. Thus, by setting a pre-read level such that η pre &lt;η, the cells whose threshold voltages are higher than the pre-read level η pre  may be regarded as stuck-at 1 defects. By selecting a lower pre-read level, more noise margin between S 0  and S 1  may be obtained and the subsequent ICI and read noise may be prevented. 
         [0037]    Referring again to  FIG. 8 , the encoder  802  encodes the data to generate a codeword ( FIG. 9  at  908 ). The encoder  802  may use an additive encoding approach to mask defects by adding a selected binary vector. Masking defects refers to selecting a codeword whose values at the locations of defects match the stuck-at values of the defects at those locations, e.g., only the data “1” will be written to the cells with the stuck-at 1 defects. Additive encoding may be implemented using [n,k,l] partitioned linear block codes (PLBC) that mask stuck-at defects and correct random errors. Although [n,k,l] PLBC for flash memory will be described, other suitable encoding techniques that mask defects may be used. After generating the codeword, the codeword is written to the wordline of the memory device ( FIG. 9  at  910 ). 
         [0038]    By using one pre-read operation before writing, the flash memory channel  806  with the ICI may be represented by the following channel model of binary memory with defective cells: 
         [0000]    
       
      
       Y=X∘S 
       + 
       +Z  
      
     
         [0000]    where X, Y, and Z are the binary channel input, output, and additive noise, respectively. The binary channel input X and the ternary defect information S 1  are shown in  FIG. 7 . Let ∘ denote the operator ∘:{0,1}×{0,1,λ}→{0,1} by 
         [0000]    
       
         
           
             
               x 
               ∘ 
               
                 s 
                 + 
               
             
             = 
             
               { 
               
                 
                   
                     
                       x 
                       , 
                     
                   
                   
                     
                       
                         
                           if 
                            
                           
                               
                           
                            
                           
                             s 
                             + 
                           
                         
                         = 
                         λ 
                       
                       ; 
                     
                   
                 
                 
                   
                     
                       
                         s 
                         + 
                       
                       , 
                     
                   
                   
                     
                       
                         if 
                          
                         
                             
                         
                          
                         
                           s 
                           + 
                         
                       
                       ≠ 
                       λ 
                     
                   
                 
               
             
           
         
       
     
         [0000]    where xεX and s + εS + . 
         [0039]    Referring to  FIG. 8 , the vector version of the output Y of the channel  806  for an n-cell memory is given by 
         [0000]    
       
      
       y=x∘s 
       + 
       +z  
      
     
         [0000]    where x,y,zε{0,1} n  are the binary channel input vector (e.g., the data vector to be stored in the memory), output vector, and random error vector, respectively. Also, the defect vector s + ε(S + ) n  represents the side information, or channel state information, of defect locations and stuck-at values. Both ∘ and + are the vector component-wise operators. + denotes the addition over Galois field (GF) which may be replaced by XOR. 
         [0040]    The number of defects in n cells is equal to the number of non-λ components in s + . The number of errors due to defects is given by 
         [0000]      ∥ x∘s   +   −x∥ 
 
         [0000]    where ∥·∥ is the Hamming weight (the number of non-zero elements) of the vector. The [n,k,l] PLBC is a pair of linear subspaces            1 ⊂{ 0 , 1 } n  and            0 ⊂{0,1} n  of dimension k and l such that            1 ∩           0 ⊂{0}. Then the direct sum is given by 
         [0000]                =           1 +           0   ={c=c   1   +c   0   |c   1 ε           1   ,c   0 ε           0 }.
 
         [0041]    The encoder  802  encodes a message M represented by vector mε{0,1} k  to a corresponding codeword X represented by vector cε          using 
         [0000]    
       
         
           
             c 
             = 
             
               
                 
                   
                     G 
                     1 
                   
                    
                   m 
                 
                 + 
                 
                   
                     G 
                     0 
                   
                    
                   d 
                 
               
               = 
               
                 
                   
                     [ 
                     
                       
                         G 
                         1 
                       
                        
                       
                           
                       
                        
                       
                         G 
                         0 
                       
                     
                     ] 
                   
                    
                   
                     [ 
                     
                       
                         
                           m 
                         
                       
                       
                         
                           d 
                         
                       
                     
                     ] 
                   
                 
                 = 
                 
                   
                     G 
                     ~ 
                   
                    
                   
                     [ 
                     
                       
                         
                           m 
                         
                       
                       
                         
                           d 
                         
                       
                     
                     ] 
                   
                 
               
             
           
         
       
     
         [0000]    where c 1 =G 1 mε           1  and c 0 =G 0 dε           0 . The generator matrix G 1  is an n×k matrix, and the generator matrix G 0  is an n×l matrix. Thus,           can be regarded as an [n,k,l] linear block code (LBC) with the generator matrix {tilde over (G)}=[G 1 G 0 ]. 
         [0042]    The parity vector dε{0,1} l  for masking defects determines the binary vector c 0  masking stuck-at defects. The encoder  802  may select d by considering both c 1  and s + . The optimal d may be selected to minimize the number of errors due to defects, given by ∥c∘s + −c∥ where ∥z∥ denotes the number of nonzero elements in z. 
         [0043]    A pair of minimum distances (d 1 ,d 0 ) of an [n,k,l] PLBC are given by 
         [0000]    
       
         
           
             
               d 
               1 
             
             = 
             
               
                 
                   min 
                   
                     m 
                     ≠ 
                     0 
                   
                 
                 
                   
                     
                       
                         H 
                         ~ 
                       
                       T 
                     
                      
                     x 
                   
                   = 
                   0 
                 
               
                
               
                  
                 c 
                  
               
             
           
         
       
       
         
           
             
               d 
               0 
             
             = 
             
               
                 
                   min 
                   
                     c 
                     ≠ 
                     0 
                   
                 
                 
                   
                     
                       G 
                       0 
                       T 
                     
                      
                     c 
                   
                   = 
                   0 
                 
               
                
               
                  
                 c 
                  
               
             
           
         
       
     
         [0000]    where d 1  is greater than or equal to the minimum distance of the [n,k+l] LBC with parity check matrix H, while d 0  is the minimum distance of the [n,k+r] LBC with parity check matrix G 0 . The minimum distance d 1  may be used to correct random errors, and the minimum distance d 0  may be used to mask defects. An [n,k,l] PLBC with minimum distances (d 1 ,d 0 ) is a u defect, t error correcting code if u&lt;d 0  and 2t&lt;d 1  or if u≧d 0  and 2(u+t+1−d 0 )&lt;d 1 . If u&lt;d 0 , all defects will be successfully masked and ∥c∘s + −c∥=0. Otherwise, it may be that ∥c∘s + −c∥≠0 which may result in a masking failure. The unmasked defects may be regarded as random errors in the decoder  804 . 
         [0044]    The encoding of PLBC includes an implicit optimization problem where d may be found by solving 
         [0000]        G   0   Ψ     u     d=G   1   Ψ     u     m −( s   + ) Ψ     u    
 
         [0000]    where Ψ u ={i 1 , . . . , i u } indicates the set of locations of u defects obtained from the side information (s + ) ψ     u   =(s i     n   , . . . ,s i     n   ). Also, 
         [0000]    
       
         
           
             
               
                 G 
                 0 
                 
                   Ψ 
                   u 
                 
               
               = 
               
                 
                   
                     [ 
                     
                       
                         
                           
                             g 
                             
                               0 
                               , 
                               
                                 i 
                                 1 
                               
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             g 
                             
                               0 
                               , 
                               
                                 i 
                                 u 
                               
                             
                           
                         
                       
                     
                     ] 
                   
                    
                   
                       
                   
                    
                   and 
                    
                   
                       
                   
                    
                   
                     G 
                     1 
                     
                       Ψ 
                       u 
                     
                   
                 
                 = 
                 
                   [ 
                   
                     
                       
                         
                           g 
                           
                             1 
                             , 
                             
                               i 
                               1 
                             
                           
                         
                       
                     
                     
                       
                         ⋮ 
                       
                     
                     
                       
                         
                           g 
                           
                             1 
                             , 
                             
                               i 
                               u 
                             
                           
                         
                       
                     
                   
                   ] 
                 
               
             
              
             
                 
             
           
         
       
     
         [0000]    where g 0,i  and g 1,i  are the i-th row of G 0  and G 1 , respectively. If the number of defects u&lt;d 0 , the optimal d may be found by Gaussian elimination or another suitable method for linear equations. However, the PLBC encoding algorithm for more than d 0 −1 defects is an optimization problem with exponential computational complexity. 
         [0045]    Since the computational complexity for finding the optimal d may be exponential, the encoder  802  may use the following two-step encoding scheme for determining d: 
         [0046]    Step 1:
       Try to solve G 0   Ψ     u   d=G 1   Ψ     u   m−(s + ) Ψ     u    
           If d exists, go to end.   Otherwise, go to step 2.   
               
 
         [0050]    Step 2:
       Select d 0 −1 locations among u defects and define Ψ d     0     -1 ={i 1 , . . . ,i d     0     -1}.      Solve       
 
         [0000]    
       
         
           
             
               
                 G 
                 0 
                 
                   Ψ 
                   
                     
                       d 
                       0 
                     
                     - 
                     1 
                   
                 
               
                
               d 
             
             = 
             
               
                 
                   G 
                   1 
                   
                     Ψ 
                     
                       
                         d 
                         0 
                       
                       - 
                       1 
                     
                   
                 
                  
                 m 
               
               - 
               
                 
                   ( 
                   
                     s 
                     + 
                   
                   ) 
                 
                 
                   Ψ 
                   
                     
                       d 
                       0 
                     
                     - 
                     1 
                   
                 
               
             
           
         
       
     
         [0053]    End 
         [0054]    If d is found in step 1, the number of unmasked defects will be zero and ∥c∘s + −c∥=0. If d is found in step 2, 0&lt;∥c∘s + −c∥&lt;u−(d 0 −1). The d 0 −1 locations may be selected in descending order from higher degree element because unmasked defects of higher degree than G 0  result in error multiplication during the decoding operation. 
         [0055]    To decode the codeword, the decoder  804  retrieves Y represented by the vector y=x∘s + +z where x=c and where z denotes the random errors. The decoder  804  computes the syndrome w−{tilde over (H)} T y (where superscript T denotes transpose) and selects {circumflex over (z)}ε{0,1} n  which minimizes ∥z∥ subject to {tilde over (H)} T z=w. Then the decoder  804  computes an estimated message {circumflex over (M)} represented by the vector {circumflex over (m)}={tilde over (G)} 1   T ĉ where ĉ=y+{circumflex over (z)}. The parity check matrix {tilde over (H)} is an n×r matrix such that {tilde over (H)} T {tilde over (G)}= 0   r,k+l  (the r×(k+l) zero matrix) and k+l+r=n. The message inverse matrix {tilde over (G)} 1  is defined as an n×k matrix such that {tilde over (G)} 1   T G 1 =I k  (the k-dimensional identity matrix) and {tilde over (G)} 1   T G 1 =0 k,l . 
         [0056]    Interference can happen in nonvolatile memory devices as well as other high-density data storage systems. For example, phase change memories suffer from thermal interference between adjacent cells. Also, magnetic recording systems suffer from inter-symbol interference, which is similar to ICI. Thus, the techniques described in this specification can be applied to any data storage system suffering from interference, such as flash memory, phase change memory, and resistive memory. 
         [0057]    Systems can be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or in combinations thereof. An apparatus can be implemented in a computer program product tangibly embodied or stored in a machine-readable storage device for execution by a programmable processor; and method actions can be performed by a programmable processor executing a program of instructions to perform functions by operating on input data and generating output. The implementations described herein, and other implementations, can be implemented advantageously in one or more computer programs that are executable on a programmable system including at least one programmable processor coupled to receive data and instructions from, and to transmit data and instructions to, a data storage system, at least one input device, and at least one output device. Each computer program can be implemented in a high-level procedural or object oriented programming language, or in assembly or machine language if desired; and in any case, the language can be a compiled or interpreted language. 
         [0058]    Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read-only memory or a random-access memory or both. The essential elements of a computer are a processor for executing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. Computer readable media for embodying computer program instructions and data include all forms of non-volatile memory, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and CD ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in special purpose logic circuitry. Any of the foregoing can be supplemented by, or incorporated in, ASICs (application-specific integrated circuits). 
         [0059]    Other implementations are within the scope and spirit of the description and the claims. Additionally, due to the nature of software, functions described above can be implemented using software, hardware, firmware, hardwiring, or combinations of any of these. Features implementing functions may also be physically located at various positions, including being distributed such that portions of functions are implemented at different physical locations. The use of the term “a” herein and throughout the application is not used in a limiting manner and therefore is not meant to exclude a multiple meaning or a “one or more” meaning for the term “a.” Additionally, to the extent priority is claimed to a provisional patent application, it should be understood that the provisional patent application is not limiting but includes examples of how the techniques described herein may be implemented.