READ/WRITE OPERATIONS IN SOLIDSTATE STORAGE DEVICES

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
10Forward
Citations 
0
Petitions 
1
Assignment
First Claim
1. A method for reading and writing data in qlevel cells of solidstate memory, where q>
 2, the method comprising;
encoding input data into codewords having N q^{ary }symbols, wherein the symbols of each codeword satisfy a singleparitycheck condition;
writing each symbol in a respective cell of the solid state memory by setting the cell to a level dependent on the q^{ary }value of the symbol;
reading memory cells to obtain read signals corresponding to respective codewords; and
detecting the codewords corresponding to respective read signals by relating the read signals to a predetermined set of Nsymbol vectors of one of which each possible codeword is a permutation.
1 Assignment
0 Petitions
Accused Products
Abstract
Methods and apparatus are provided for reading and writing data in qlevel cells of solidstate memory, where q>2. Input data is encoded into codewords having N q^{ary }symbols, wherein the symbols of each codeword satisfy a singleparitycheck condition. Each symbol is written in a respective cell of the solid state memory by setting the cell to a level dependent on the q^{ary }value of the symbol. Memory cells are read to obtain read signals corresponding to respective codewords. The codewords corresponding to respective read signals are detected by relating the read signals to a predetermined set of Nsymbol vectors of one of which each possible codeword is a permutation.
12 Citations
View as Search Results
DETECTING CODEWORDS IN SOLIDSTATE STORAGE DEVICES  
Patent #
US 20130086457A1
Filed 09/19/2012

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

READDETECTION IN SOLIDSTATE STORAGE DEVICES  
Patent #
US 20130227380A1
Filed 02/01/2013

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

Detecting codewords in solidstate storage devices  
Patent #
US 8,930,803 B2
Filed 09/19/2012

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

Readdetection in solidstate storage devices  
Patent #
US 8,938,665 B2
Filed 02/01/2013

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

Linear programming based decoding for memory devices  
Patent #
US 9,424,945 B2
Filed 11/14/2014

Current Assignee
Empire Technology Development LLC

Sponsoring Entity
Empire Technology Development LLC

Page allocation for flash memories  
Patent #
US 9,448,921 B2
Filed 01/11/2013

Current Assignee
Empire Technology Development LLC

Sponsoring Entity
Empire Technology Development LLC

Data encoding in solidstate storage apparatus  
Patent #
US 9,502,138 B2
Filed 09/25/2014

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

Lowcomplexity flash memory dataencoding techniques using simplified belief propagation  
Patent #
US 9,859,925 B2
Filed 12/13/2013

Current Assignee
Empire Technology Development LLC

Sponsoring Entity
Empire Technology Development LLC

Estimation of levelthresholds for memory cells  
Patent #
US 9,928,923 B2
Filed 09/18/2014

Current Assignee
GlobalFoundries Inc.

Sponsoring Entity
GlobalFoundries Inc.

Apparatus and method for mapping binary to ternary and its reverse  
Patent #
US 10,454,495 B2
Filed 09/18/2014

Current Assignee
Intel Corporation

Sponsoring Entity
Intel Corporation

Advanced Bitwise Operations and Apparatus in a MultiLevel System with Nonvolatile Memory  
Patent #
US 20110302475A1
Filed 06/04/2010

Current Assignee
Ovonyx Memory Technology LLC

Sponsoring Entity
Storage Genetics Inc.

Data encoding in solidstate storage devices  
Patent #
US 8,578,246 B2
Filed 04/29/2011

Current Assignee
GlobalFoundries Inc.

Sponsoring Entity
International Business Machines Corporation

16 Claims
 1. A method for reading and writing data in qlevel cells of solidstate memory, where q>
 2, the method comprising;
encoding input data into codewords having N q^{ary }symbols, wherein the symbols of each codeword satisfy a singleparitycheck condition; writing each symbol in a respective cell of the solid state memory by setting the cell to a level dependent on the q^{ary }value of the symbol; reading memory cells to obtain read signals corresponding to respective codewords; and detecting the codewords corresponding to respective read signals by relating the read signals to a predetermined set of Nsymbol vectors of one of which each possible codeword is a permutation.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
 2, the method comprising;
 16. An apparatus for reading and writing data in qlevel cells of solidstate memory, where q>
 2, the apparatus comprising;
an encoder for encoding input data into codewords having N q^{ary }symbols, wherein the symbols of each codeword satisfy a singleparitycheck condition; a read/write controller for writing each symbol in a respective cell of the solid state memory by setting the cell to a level dependent on the q^{ary }value of the symbol, and for reading memory cells to obtain read signals corresponding to respective codewords; and a detector for detecting the codewords corresponding to respective read signals by relating the read signals to a predetermined set of Nsymbol vectors of one of which each possible codeword is a permutation.
 2, the apparatus comprising;
1 Specification
1. Technical Field
This invention relates generally to read/write operations in solidstate storage devices (SSSDs) and, more particularly, to methods and apparatus for reading and writing data in multilevel cells of solidstate memory.
2. Related Art
In solidstate memory such as flash memory and phase change memory (PCM), the fundamental storage unit (the “cell”) can be set to a number of different states, or “levels”, which exhibit different electrical characteristics. These different levels can be used to store information. To readout stored information, celllevel is detected via measurements which exploit the differing electrical characteristics to differentiate between different levels. In socalled “singlelevel cell” (SLC) devices, the memory cells can be set to only two levels and so can record only binary values. Other devices have socalled “multilevel cells” which can be set to q different levels, where q>2. Multilevel NOR flash memories, for instance, can store 4 levels, i.e. 2 bits, per cell. Multilevel cell (MLC) NAND flash memory chips that can store 3 bits of data per single flash cell using 25 nm process technology are currently available. Storage of 2 bits per cell in PCM chips has also been demonstrated.
When writing information to multilevel cells, each cell can be used to store a qary symbol with each of the q possible symbol values being represented by a different cell level. On readout of multilevel cells, the read signal level is compared with a set of reference signal levels indicative of the q celllevels in order to determine which level each cell is set to and thus detect the stored symbol value. However, a problem in multilevel SSSDs is that the physical quantity measured during cell readout, such as electrical resistance in PCM devices, is liable to drift. In particular, the electrical resistance of PCM cells drifts upwards with time in a stochastic manner. This drift can be datadependent, i.e. may vary for different cell levels. As another example, in flash memory cells the physical quantity measured is the transistor'"'"'s threshold voltage, and this drifts upwards as a function of the number of write/erase cycles the cell is subjected to. For any given stored symbol value and hence cell level, therefore, the actual read signal level obtained on cellreadout is variable.
Drift is a serious problem for multilevel storage in that it severely compromises reliability. The readback values of neighboring levels may interfere over time, due to upward drift of the lower level towards the upper level, causing a detection error. The closer the initial spacing between levels, the more susceptible they are to drift. Hence, packing higher numbers of levels per memory cell becomes more difficult due to the increased likelihood of error during cellstate detection. On the other hand, packing more bits per cell is a crucial requirement for all memory technologies, being the best known way of reducing manufacturing cost per bit.
A few techniques have been proposed to tackle the problem of drift, but most remain at the academic interest level. One proposal is to use a certain part of the memory cell array as a reference pool of cells. These cells are written with known signal levels, and are continuously monitored during device operation, to obtain estimates of drift. The estimated drift values can then be used to update the reference levels used for level detection on readback. However, drift is a statistical phenomenon and there is significant variability between cells in the array, so reference cells may not be representative and the effectiveness of the proposed referencecell based approaches will vary substantially over time and over different portions of the memory array. Other drawbacks of this method include: the overhead it entails, which translates to a loss of memory capacity; the penalty in terms of controller complexity and latency due to the readout of the extra cells, and issues related to the management of the pool of reference cells, e.g. wearleveling issues.
Modelbased drift cancellation techniques seek to model drift based on key parameters such as temperature, time and wear, and compensate accordingly. It is, however, difficult to obtain an accurate cell history for the key parameters. There are also fluctuations from cell to cell and there is no wellestablished analytical model available for shortterm drift.
Techniques based on coding have been proposed to address other problems in multilevel memories. For example, rank modulation has been proposed to address endurance problems and overshoot errors in flash memories (see “Rank Modulation for Flash Memories”, Jiang et al., IEEE Trans. Inf. Theory, vol. 55, no. 6, June 2009; and US Patent Application Publications No'"'"'s. 2009/0132895A1 and 2009/0132758A1). While rank modulation may offer some drift benefits, it has two severe drawbacks, namely: (i) it offers only low code rate for a given number of levels; and (ii) it lacks an efficient mapping of data bits into codewords. Hence, rank modulation does not provide a practical solution and is mostly of theoretical interest.
A technique based on coding, and aimed specifically at drift, is detailed in our copending US Patent Application Publication No. 2011/0296274A1. This technique encodes input data as Nsymbol codewords of a socalled “translationstable code”. Each codeword symbol can take one of q symbol values and is recorded in a respective qlevel cell by setting the cell to a level dependent on the qary symbol value. The translationstable code is such that each possible input data word is mapped by the coding scheme to a codeword with a unique sequence of relative symbol values. Such a code can be constructed from codewords in a set of one or more permutation codes. Each codeword of a permutation code is a particular permutation of a predefined vector (the “initial vector”) which has N qary symbols arranged in order of increasing symbol value. Detection of codewords on readback can be performed by relating the read signals for codewords to the initial vectors for the code. With a translationstable code, information is effectively encoded in the relative, as opposed to the absolute, read signal component levels. This feature obviates primary effects of drift on detection accuracy, whereby translationstable codes can be considered effectively driftinvariant. Translationstable codes also offer higher code rates than rank modulation schemes for a given number of levels. However, the construction of good translationstable codes with large minimumdistance and high rates is based on a casebycase study as there is no systematic approach to design of such codes. Moreover, there is no known simple mapping of data bits into translationstable codewords and vice versa.
Our copending European Patent Application no. 11183336.4, filed 29 Sep. 2011, discloses a driftresistant technique for readdetection of permutationbased codes in multilevel SSSDs. The detection system exploits the fact that all codewords are permutations of a known set of vectors, e.g. the initial vectors for a union of permutation codes. The N qary symbols of each codeword are again recorded in respective qlevel cells by setting the celllevel in accordance with symbol value. Memory cells are read in batches to obtain read signals corresponding to a group of codewords. Each read signal has N signal components corresponding to respective symbols of a codeword, and these components are ordered according to signal level to obtain an ordered read signal for each codeword. Components of these ordered read signals are related to symbols of the known set of initial vectors via a process which involves averaging ordered read signals and relating the average components to symbol values using predefined probabilities of occurrence of different symbol values at different symbol positions as derived from the initial vectors. In this way, reliable estimates can be obtained for the reference signal levels for the qlevel cells in the current batch. These reference levels can then be used in codeword detection for the current batch. This selfadaptive technique thus uses the actual cells storing encoded data to estimate the reference levels for those cells on readback, thereby accounting for drift effects on a dynamic basis. The technique is also robust and lends itself to simple, fast decoder implementation. Good, practical encoding schemes for use in such systems nonetheless remain a matter for casebycase study.
An embodiment of one aspect of the present invention provides a method for reading and writing data in qlevel cells of solidstate memory, where q>2. The method comprises:
encoding input data into codewords having N q^{ary }symbols, wherein the symbols of each codeword satisfy a singleparitycheck condition;
writing each symbol in a respective cell of the solid state memory by setting the cell to a level dependent on the q^{ary }value of the symbol;
reading memory cells to obtain read signals corresponding to respective codewords; and
detecting the codewords corresponding to respective read signals by relating the read signals to a predetermined set of Nsymbol vectors of one of which each possible codeword is a permutation.
Methods embodying this invention encode data for storage in multilevel cells using lengthN, q^{ary}symbol codes in which the symbols of each codeword satisfy a singleparitycheck (SPC) condition. The SPC condition may apply to the symbols as a whole or to subsymbols thereof as discussed further below. Methods embodying the invention are predicated on the realization that, because the result of a single parity check is invariant under permutation of its arguments, the codewords of such SPCbased codes are all permutations of an identifiable set of Nsymbol vectors (where this set of vectors may in general contain one or more vectors). This permutation feature can be exploited to enable codeword detection. Thus, a practical decoder implementation is available, and advantage can be taken of the benefits offered by SPCbased codes. In particular, SPCbased codes provide good, highrate codes with large minimum distance. This, in conjunction with efficient permutationbased decoding, offers excellent performance in read/write systems embodying the invention. In addition, many SPCbased codes have simple encoders with efficient mapping of data bits into codewords.
This can be exploited in preferred embodiments for exceptionally efficient implementations. In general, the ability to use SPCbased codes in multilevel SSSDs by exploiting the permutation property for decoding offers a systematic approach to the construction of highrate codes for multilevel SSSDs with simple encoding of user data and good tradeoff between gains in minimum distance and rate loss. Moreover, the permutation property of SPCbased codes allows driftresistant techniques to be implemented as discussed earlier. For instance the readdetection technique of EP 11183336.4 referenced above can be employed in embodiments of the invention. Particularly preferred embodiments employ SPCbased codes which are also translationstable and hence driftinvariant. Overall, therefore, methods embodying the invention offer very significant advantages in multilevelcell storage devices.
The singleparitycheck condition which the symbols of each codeword satisfy may be that the q^{ary }symbols as a whole, or subsymbols of these q^{ary }symbols, satisfy a singleparitycheck equation. In particular, the SPCbased code may be a singlelevel code in some embodiments. The codewords may, for example, be codewords of a lengthN SPC code. Alternatively the codewords may be codewords of a coset of such an SPC code. In other embodiments, the SPCbased code may be a multilevel code whereby the codeword symbols each comprise a plurality of subsymbols corresponding to respective code levels. In this case, in each codeword, the N subsymbols of at least one code level may comply with one of a lengthN SPC code or a coset thereof. That is, for at least one code level, each group of N subsymbols forms a codeword of an SPC code (or coset). Thus, there can be multiple single parity checks each applying to a different code level. Examples of these various SPCbased codes will be given below. With all such codes, preferred embodiments can take advantage of the SPCbased code to perform simple and efficient encoding of input user data. This is discussed further below.
The set of possible (i.e. permitted or “valid”) codewords used in the system need not necessarily include all codewords encompassed by the SPCbased code in question. In particular, some embodiments may employ a limited codeword set obtained from a reduced set of basic vectors from which one or more vectors has been eliminated. This is explained in detail below. While this increases encoder complexity, it may be desirable in some embodiments as the reduced vector set simplifies decoding and so may enhance error performance.
The permutation property of the SPCbased codes is exploited for detection purposes by relating the read signals for codewords to the set of vectors of which all codewords are permutations. The particular detection process, and the particular way in which read signals are related to the set of basic vectors during this process, can vary in different embodiments, e.g. depending on the particular SPCbased code employed. The detection process typically involves an ordering of the components of read signals. Specifically, each read signal may comprise N signal components corresponding to respective symbols of a codeword. The components of each read signal are ordered according to signal level to produce an ordered read signal. The components of ordered read signals are then related to symbols of the set of vectors during detection. The details of this process may depend on the particular code, e.g. whether the code is translation stable or not and the number of vectors in the aforementioned set. For codes with a plurality of basic vectors, the relating of read signal components to vector symbols may be performed via an averaging process over a group of ordered read signals, generally as in the permutationbased detection system of EP11183336.4 referenced above. Here, the average components can be related to corresponding symbols in the basic vectors, using the aforementioned probabilities, to derive estimates for the reference signal levels for the q celllevels. The process can also involve one or more further stage(s) of relating ordered read signals to basic vectors, e.g. via a clustering process, and/or a trellis decoding stage. Detection techniques for various scenarios will be described in more detail below.
An embodiment of a second aspect of the invention provides apparatus for reading and writing data in qlevel cells of solidstate memory, where q>2. The apparatus comprises:
an encoder for encoding input data into codewords having N q^{ary }symbols, wherein the symbols of each codeword satisfy a singleparitycheck condition;
a read/write controller for writing each symbol in a respective cell of the solid state memory by setting the cell to a level dependent on the q^{ary }value of the symbol, and for reading memory cells to obtain read signals corresponding to respective codewords; and
a detector for detecting the codewords corresponding to respective read signals by relating the read signals to a predetermined set of Nsymbol vectors of one of which each possible codeword is a permutation.
In general, where features are described herein with reference to a method embodying the invention, corresponding features may be provided in apparatus embodying the invention, and vice versa.
Preferred embodiments of the invention will now be described, by way of example, with reference to the accompanying drawings in which:
Each of the PCM cells in memory 2 can be set to one of q>2 nominal levels designated I_{0 }to I_{q1 }herein. Read/write controller 4 can set a cell to a particular level by adjusting the resistance of the cell in known manner. To read a cell, controller 4 applies a small probing signal to obtain a readback signal indicative of the cell'"'"'s resistance. During write and read operations, controller 4 addresses individual cells in known manner by applying appropriate voltage signals to an array of word and bit lines in memory ensemble 2.
In operation of device 1, the input data to be recorded in memory 2 is supplied to encoder 3. The encoder 3 encodes input data into codewords which have N qary symbols s_{n}, n=1, 2, . . . , N, where in general N≧q. Hence, the symbols of a codeword can each take one of q possible values (s_{n }ε {0, 1, . . . , q−1}). The q possible symbol values correspond to respective predetermined levels I_{0 }to I_{q1 }of the qlevel cells in memory 2. In this example, a direct correspondence between symbol values 0, 1, . . . , q−1 and cell levels I_{0 }to I_{q1 }is assumed for simplicity. Controller 4 stores the N symbols of each codeword output by encoder 3 in respective cells of memory 2 by setting each cell to a level dependent on the symbol value to be stored in accordance with the predefined correspondence between symbol values and cell levels. (Note that, when setting a cell to a given level, the actual resistance value x assumed by the cell may lie within a small interval around the nominal resistance value/for the level due to write noise).
Encoder 3 implements an SPCbased code such that the N symbols of each codeword satisfy a parity condition. The SPCbased code may in general be a singlelevel code or a multilevel code.
In some embodiments, the SPCbased code used in encoder 3 may be a lengthN singleparitycheck code or a coset of such a code. These are singlelevel codes. A lengthN SPC code over the ring of integers modulo q is defined by the singleparitycheck equation:
c_{1}+c_{2}+ . . . +c_{N}=0(modulo q)
where c_{1 }to c_{N }are the N q^{ary }symbols of a codeword. The cosets of this code are defined by the singleparitycheck equation:
c_{1}+c_{2}+ . . . +c_{N}=p(modulo q)
where p is a predetermined integer between 1 and q−1. Such SPC codes (or cosets) have a rate of (N−1)/N and a minimum Hamming (and Lee) distance of d_{H}=d_{L}=2. In operation of the
A particular example of the foregoing is provided by length9 SPC code over the ring of integers modulo q=5. Such a code can be used with PCM cells for which q=5 nominal celllevels are defined for data storage. This code is defined by the singleparitycheck equation:
c_{1}+c_{2}+ . . . +c_{9}=0(modulo 5).
With this code, binary symbol converter 8 applies a base change from binary to 5^{ary }symbols based on the fact that 2^{9}≦5^{4}. Applying this base change twice (i.e. once to each of two groups of nine input bits), the symbol converter 8 maps eighteen bits into the eight 5^{ary }input symbols (c_{1}, c_{2}, . . . , c_{8}) which are output to parity encoder 9. The parity encoder is implemented as a simple rate8/9 encoder which maps 5^{ary }data symbols into codewords according to the linear mapping:
(c_{1},c_{2}, . . . , c_{8})→(c_{1},c_{2}, . . . , c_{8},−(c_{1}+c_{2}+ . . . +c_{8})).
The encoder 9 thus simply adds a parity symbol c_{9}=−(c_{1}+c_{2}+ . . . +c_{8}) to the eight 5^{ary }input symbols (c_{1}, c_{2}, . . . , c_{8}). This code has rate 2.06 bit/cell and minimum Hamming distance d_{H}=2. Comparing this code to the closest equivalent uncoded storage (which uses q_{0}=4 nominal celllevels distributed over the same programming window), the code has an asymptotic coding gain of:
s×d^{2}_{min}=9/16×2=1.125(=0.51 dB)
where s is the loss factor for the signalset expansion from q_{b}=4 to q=5 equally spaced levels in the interval [0, 1] given by:
s=[d_{min}(q_{0})/d_{min}(q)]^{2}=[(q_{0}−1)/(q_{0}−1)]^{2}.
This code is particularly advantageous in that it is also a translationstable code. This is discussed further below.
In other embodiments, the SPCbased code used in encoder 3 may be a multilevel code. In this case, the codeword symbols each comprise a group of subsymbols which correspond to respective code levels. The SPC condition can be imposed here in that the N subsymbols of at least one code level form a codeword of a lengthN SPC code or coset thereof. Two such codes which can be employed in encoder 3 are described in the following.
The first multilevel code is a twolevel code of length N=8 using q=4 celllevels 0, 1, 2, 3 with binary labeling 000, 101, 210, 311 defining the 4^{ary }symbol values for the code. The code has a multilevel construction with first and second code levels whose subsymbols correspond to the mostsignificant bit (MSB) and least significant bit (LSB) respectively of the 2bit symbols defined by the labeling scheme. The celllevels that differ in the MSB only of the corresponding symbol value are 0 and 2, and 1 and 3. In both cases the distance between these levels is two. Hence a code with a squared minimum distance of 2 can be obtained by imposing a singleparity constraint on the subsymbols of the second code level, i.e. the LSBs, only. The codeword construction for the N=8 code is given by
(c′_{1}c″_{1},c′_{2}c″_{2}, . . . , c′_{8}c″_{8})
where:
eight uncoded data bits form the eight most significant bits c′_{1 }to c′_{8 }of the first code level; seven uncoded data bits form the first seven bits c″_{1 }to c″_{7 }of the second code level; and c″_{8 }is the parity bit calculated such that c″_{1}+c″_{2}, . . . , +c″_{8}=0 (mod 2).
With this twolevel code, the data conversion required in symbol converter 8 of
The second multilevel code is another twolevel code of length8 and is similar to the code just described except that a singleparity constraint is imposed on both code levels. Here, therefore, both the eight LSBs and the eight MSBs comply with a length8 SPC code (or coset). The codeword construction is again given by
(c′_{1}c″_{1},c′_{2},c″_{2}, . . . , c′_{8}c″_{8})
where:
in level 1, seven data bits c′_{1 }to c′_{7 }determine the parity bit c′_{8}; and
in level 2, seven data bits c″_{1 }to c″_{7 }determine the parity bit c″_{8}.
With this code, the data conversion required in symbol converter 8 is a trivial mapping of fourteen input bits to 4^{ary }symbols c′_{1}c″_{1 }to c′_{7}c″_{7}. Parity encoder 9 then performs simple linear encoding of these fourteen bits into a length8, 4^{ary }codeword by calculating and adding the parity bits c′_{8 }c″_{8 }as the final codeword symbol. This code has a rate of 14/8=1.75 bits/cell, and a minimum squared Euclidean distance d^{2}_{min}=2×d^{2}(0,1). There is a 3 dB asymptotic gain in exchange for a slight loss in rate from 2 to 1.75 bit/cell. Although the code rate is lower due to parity coding of both code levels, the resulting code has a smaller set of initial vectors which are exploited in the decoding process discussed below. This reduces the likelihood of error in the decoding process, offering improved accuracy on readback.
While particular examples of single and multilevel SPCbased codes are given above, similar principles can be applied to obtain numerous other useful SPCbased codes for embodiments of the invention. The principles of such multilevel codes are generally known from communications theory, and similar principles can be applied here to obtain codes for use in multilevel storage device 1. In general, provided q is not prime, the q^{ary }alphabet of a code can be decomposed into a Cartesian product of subalphabets for the different code levels which can be endowed with a field or additive group structure. For example, a q^{ary }alphabet can be decomposed into a binary and a ternary subalphabet, which results in the algebraic structure Z/2Z×Z/3Z. Thus in general for multilevel codes, encoder 3 maps binary data to groups of subsymbols, with respective subalphabets, which in combination represent a q^{ary }value. A singleparity constraint can be imposed on one or more of the different code levels. For any code level having a parity constraint, encoder 3 encodes groups of (N−1) subsymbols of that code level into the N subsymbols of that level in respective codewords of the overall SPCbased code.
It will be seen that the above paritybased codes offer highrate codes with good minimum distances and can be implemented in a simple manner using a base change and simple linear encoding. The codes thus provide a simple mapping of input data to codewords and simple encoder construction. Moreover, consideration of these SPCbased codes shows that the codes are invariant under permutation of their arguments, the parity condition being satisfied for all permutations of the symbol set (c_{1}, c_{2}, . . . , c_{N}). It follows that all codewords of such a code are permutations of an identifiable subset of the codewords. This subset constitutes a set of Nsymbol vectors for the code such that each possible codeword is a permutation of one vector in the set. Hence, these codes can be viewed as a union of permutation codes. A permutation code is characterized by a real vector of lengthN (the “initial vector”) on which the permutation group of N letters operates. The code is completely determined by its lengthN and the initial vector X0 which has N components (symbols). The codewords consist of all lengthN vectors that are obtained through a permutation of the components of the initial vector. The SPCbased codes described above can be viewed as a union of lengthN permutation codes, whereby each possible codeword is a permutation of one of a set of Nsymbol vectors being the set of initial vectors of the permutation codes.
The permutation property of the SPCbased codes described herein provides the basis for efficient decoding of these codes. In particular, the read signals obtained for codewords on readback can be related to the predetermined set of Nsymbol vectors for the code as the basis of the codeword detection process. The relating of read signals to vectors can be performed in a variety of ways depending on the particular code employed and the overall detection process in which is it used. Examples of preferred detection techniques are described in the following. These are based on the driftresistant techniques described in our European Patent Application no. 11183336.4, referenced above, the relevant content of which is incorporated herein by reference. The detection methods to be described are performed by codeword detector 6 of device 1. The codeword detector comprises control logic for implementing the various steps of the codeword detection process, and this control logic may be embodied in hardware or software or a combination of hardware and software components. Suitable implementations will be readily apparent to those skilled in the art from the description of operation herein.
For the first detection method to be described, blocks of codewords are written/read substantially simultaneously to memory 2 by read/write controller 4. In a read operation, the memory cells storing a group of B codewords are read to obtain B realvalued read signals y each having N signal components y_{n}, n=1, 2, . . . , N, indicating the readback resistance values of the sequence of cells storing the N symbols of a codeword. The read signals y are supplied to codeword detector 6. The signal components y_{1}, . . . y_{N }of each read signal correspond to respective symbols S_{1}, . . . s_{N }of a stored codeword. The readback resistance levels y corresponding to a given symbol value s are variable due to drift and noise effects. Drift is of stochastic nature and is modeled here as a deterministic part f (average trend due to drift) and a stochastic part g (drift and noise) which is datadependent:
y=f(x,t)+g(x,t)
where y is the drifted level, x is the original stored value, t is time, f(x,t) is a monotonic function of x for all fixed t (i.e. levels maintain their order over time), and g(x,t) is a random process capturing the datadependent nature of noise. For fixed x and t, additive noise is modeled as Gaussian with zero mean and datadependent variance:
g(x,t)˜N(0,σ(x))
Hence, the readback resistance level distributions shift in time, with changing means and potentially variances, and are leveldependent, having datadependent means and variances. For accurate detection of codewords from read signals y, codeword detector 6 must account for the variable resistance level distributions. Most fundamentally, the codeword detector requires estimates for the reference signal levels which correspond to the different cell levels I_{0 }to I_{q1}, and hence to the different symbol values, for the read operation. These reference signal levels can then be used for codeword detection. An overview of the codeword detection process is given below with reference to the flow diagram of
z^{i}=[y_{k}_{1}^{i},y_{k}_{2}^{i}, . . . , y_{k}_{N}^{i}],y_{k}_{i}^{i}≦y_{k}_{2}^{i}≦ . . . ≦y_{k}_{N}^{i}, where i=1, . . . , B (1)
This ordering process defines a permutation (k_{1 }to k_{N}) of the signal components for each read signal y. The resulting ordered read signals are stored in codeword detector 6. Next, in step 12, the detector logic averages corresponding components of the ordered read signals to obtain an “average” read signal 5, at time t:
Thus, the first, second, . . . , Nth components of the ordered read signals are averaged over the B signals to produce the average read signal
X^{0}=[X_{k1},X_{k2}, . . . , X_{kN}] with X_{k1}≦X_{k2}≦ . . . ≦X_{kN }
the stochastic (N×q)matrix P=[p_{nm}] is defined as:
p_{nm}=prob{X^{0}_{n}=S_{m}}
where n=1 to N, m=0 to q−1, and S_{1}, S_{2}, . . . , S_{q1 }are the symbol values 0, 1, . . . , q−1 respectively. Such a matrix can be defined for any code C based on the known code structure, i.e. the set of valid codewords for the code. This will be illustrated by example below.
Assuming that, at each memorywrite operation, B codewords are selected randomly from the code and written simultaneously to the PCM array as described above, then the recorded signals x=[x_{1}, x_{2}, . . . , x_{n}] for the B codewords (if rearranged as their ordered versions x^{0}=[x_{k1}, x_{k2}, . . . , x_{kn}] with x_{k1}≦x_{k2}≦ . . . ≦x_{kn}) satisfy the relation:
where x^{(i)o }is the set of ordered write signals and the superscript T denotes the vector transpose. Note that if all codewords are used the error vector is essentially zero. On readback, the resulting read signals y are ordered and averaged as described in steps 11 and 12 of
(where, if the group B consists of all codewords, then the error e is the average (component by component) of the zeromean noise samples vector g, which is expected to be essentially zero). Equation (4) represents an overdetermined system of N linear equations which can be solved in known manner for the q unknowns {λ_{0}, λ_{2}, . . . , λ_{q1}}.
The above process will now be illustrated for an exemplary code based on the union of four permutation modulation codes with initial vectors c^{(j) }given below. (Note that this code is not itself an SPCbased code and is used simply to illustrate the reference level estimation technique described).
c^{(1)}=[0112233] #Π(c^{(1)})=630
c^{(2)}=[0011223] #Π(c^{(2)})=630
c^{(3)}=[0001233] #Π(c^{(3)})=630
c^{(4)}=[0012333] #Π(c^{(4)})=630
There are 2100 codewords, consisting of a number of permutations of each initial vector as indicated by #Π(c^{(j)}). Assuming all codewords are equally likely, then the probabilities defining the probability matrix P described above depend on the structure of the initial vectors and the number #Π(c^{(j)}) of codewords which are permutations of each vector. In particular, the probabilities p_{j}(j=1, . . . , L) of occurrence of the initial vectors c^{(j) }can be easily calculated as:
p1=p2=63/210;
p3=p4=42/210.
If we denote the initial vectors at time t as
u^{(f)}=F{c^{(f)}}=[u_{1}^{(f)}, . . . , u_{N}^{(f)}],f=1, . . . , L
then, based on equation (1) above, the components z_{n }of the average read signal can be expressed as:
This equation can be rewritten in matrix form, corresponding to equation (4) above, as:
where
As N≧q, this set of linear equations can be solved in known manner for the unknown reference levels λ_{0}, . . . , λ_{3}. In this preferred embodiment, detector 6 solves the equations using a leastsquares method as is well known to those skilled in the art.
It will be seen that, in the above process, the ordered read signals for codewords are related to symbols of the set of initial vectors via an averaging process over a group of ordered read signals using the predefined probabilities of occurrence of each symbol value at each symbol position in a said codeword whose symbols are ordered according to symbol value. These probabilities depend on the values of symbols of the initial vectors at positions corresponding to respective components of the average read signal, and thus inherently involve relating the ordered read signal components to initial vectors as described above. This relation is used to obtain estimates of the reference levels from the ordered averaged read signals. The resulting estimates for the reference signal levels λ_{0}, . . . , λ_{3 }for the q celllevels can then be used to detect the current batch of codewords. In some embodiments, the reference signal levels λ_{0 }to λ_{3 }could be used directly for codeword detection by comparing the components y_{n }of each read signal y with these levels to identify the particular cell level, and hence symbol value, to which each read signal component corresponds. However, preferred embodiments offer improved detection accuracy by using the reference signal levels λ_{0 }to λ_{3 }to identify the initial vector of which the codeword corresponding to each read signal is a permutation. In effect, the read signals are divided into clusters, each cluster containing read signals representing codewords which are permutations of the same initial vector. Examples of such techniques will now be described with reference to
c^{(j)}→F{c^{(j)}}=u^{(j)}=[u_{1}^{(j)}, . . . , u_{N}^{(f)}],f=1, . . . , L
That is, the ith component c_{i}^{(j) }of c^{(j) }is mapped into u_{i}^{(j) }using the current reference level estimates λ_{m}=f((l_{m},t), m=0, 1, . . . , q−1. The resulting vector signals u(j) are then used to divide the group of B ordered read signals z^{t }(from step 11 of
closest initial vector c^{(r)}=[c_{1}^{(r)}, . . . , c_{N}^{(r)}],r=arg min_{j}{z^{i}−u^{(f)}},
where j=1, . . . , L. The minimum can be assessed here using any convenient minimum distance criterion, e.g. using a simple Euclidean distance metric. Next, in step 23, the detector logic calculates statistical data for the distribution of the read signal component levels corresponding to each of the q nominal levels of the memory cells. In particular, by relating the ordered read signal components to the symbols of the initial vectors in the various clusters, the read signal level distributions for each of the q celllevels are obtained. These distributions are then processed to obtain the means and variances in each case. The mean values so obtained for the q celllevels are denoted by λ′_{0 }to λ′_{0 }and represent updated values for the reference signal levels λ used in initial clustering step 22. The variances for each level distribution are denoted by σ. In step 24 of
The codeword detected in step 24 for each of the group of B read signals is then output by codeword detector 6 in step 25 of
an ML technique being employed here where:
where: z_{n}^{i }are the components z_{1}^{i}, z_{2}^{i}, . . . , z_{N}^{i }of ordered read signal z^{i};
μ_{n}^{(ν) }corresponds to initial vector c^{(v) }with symbols replaced by the corresponding mean reference levels λ′; and
σ_{n}^{(ν) }represents the standard deviation of the distribution for the reference level with mean λ′ which corresponds to each component of μ_{n}^{(ν)}.
Having effectively reclustered the read signals y according to the initial vector identified using the statistical data in step 25, in step 27 the detector logic can detect the codeword corresponding to each read signal by applying an inverse permutation to the initial vector identified for the read signal. For a given read signal, the inverse permutation is simply the inverse of the permutation (k_{1 }to k_{N}) of that read signal which produced the ordered read signal via (1) above. The resulting codeword for each read signal (or an erasure signal if no valid codeword is detected) is then output in step 28, and the process is complete.
The above techniques exploit the permutation property of SPCbased codes to achieve efficient, driftresistant decoding in device 1. In particular, the detection process is independent of underlying drift characteristics (as long as drift does not reorder the resistance levels), and also accounts for datadependent noise whereby different celllevels are subject to differing noise effects. Moreover, some SPCbased codes are also translationstable codes and as such are fundamentally driftinvariant. Translationstable codes are defined and described in US 2011/0296274A1, mentioned earlier, the relevant content of which is incorporated herein by reference. Briefly, however, with a translationstable encoding scheme, each data word in the set of all possible input data words is encoded as a codeword with a unique sequence of relative symbol values. This can be understood by considering the simple translationstable code of
(c+Rt)∩C=c
where R is the set of real numbers. This provides the definition of a “translationstable” code herein for any Nsymbol, qary alphabet code C{0, 1, . . . , q−1}^{N}R^{N}. While
C⊂Π(c^{(1)})∪Π(c^{(2)}) . . . ∪Π(c^{(L)})
where c^{(1)}, c^{(L) }are L unique initial vectors; Π(c^{(L)}) denotes the permutation modulation code with initial vector c^{(j)}; and C∩∪Π(c^{(j)})≠Ø. With translationstable codes, because each possible dataword maps to a codeword with a unique sequence of relative symbol values, input data is effectively encoded in the relative, as opposed to the absolute, symbol values. The correspondence between symbol values and memory cell levels means that codewords will be recorded as correspondingly unique sequences of relative levels in memory 2. Provided any driftinduced shift in the cell levels does not change the basic level order, this shift will not change the relative level sequences and so will not affect the information recorded. By detecting the relative level sequences on readback, the correct codewords and hence data words can be recovered regardless of the driftinduced shift. Translationstable codes are thus highlyadvantageous, being particularly robust to drift effects. Hence, SPCbased codes which are also translationstable codes can be selected for use in some embodiments of device 1, providing benefits associated with both of these codetypes. The length9, 5^{ary }SPC code detailed earlier is a particular example of such a translationstable SPCbased code. Other translationstable codes can be readily identified, for example, by considering codes for which the codelength is an odd number N=2 m+1 with the requirement that the sum of the N symbols is zero (modulo q).
In the above embodiments using the simple encoder construction of
Where the codeword set of the SPCbased code is limited as above, the encoder 3 must perform coding by mapping input data into the remaining codewords. This could be implemented, for example, by using a lookup table, in particular for small codes, or using the wellknown technique of enumerative source coding for more efficient operation with large codes. Decoding of this type of code can be performed, for example, using the detection process of
Performance results for an exemplary SPCbased code are discussed below in connection with
It will be seen from the foregoing that embodiments of the invention provide significant improvements in multilevel solidstate storage devices. The use of SPCbased codes offers a systematic approach to the construction of highrate codes with simple encoding of user data, which provide a good tradeoff between minimum distance and rate loss. The permutation property of these codes can be exploited to achieve efficient, drift resistant decoding. Moreover, translationstable codes which are inherently driftinvariant can be easily constructed based on the principles described.
It will of course be appreciated that many changes and modifications can be made to the particular embodiments detailed above. For example, other ways might be envisaged for relating read signals to the set of initial vectors to exploit the permutation property of the SPCbased codes for codeword detection. Also, while memory 2 uses PCM cells, the techniques described can be applied to other multilevel solid state memory cells, such as flash memory cells, where similar considerations apply. Many other changes and modifications can be made to the above embodiments without departing from the scope of the invention.