[go: up one dir, main page]

WO2008078314A1 - Dispositif, système et procédé de mémoire flash avec répartition aléatoire pour supprimer une erreur - Google Patents

Dispositif, système et procédé de mémoire flash avec répartition aléatoire pour supprimer une erreur Download PDF

Info

Publication number
WO2008078314A1
WO2008078314A1 PCT/IL2007/001514 IL2007001514W WO2008078314A1 WO 2008078314 A1 WO2008078314 A1 WO 2008078314A1 IL 2007001514 W IL2007001514 W IL 2007001514W WO 2008078314 A1 WO2008078314 A1 WO 2008078314A1
Authority
WO
WIPO (PCT)
Prior art keywords
data
retrieved
memory
randomized
original data
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/IL2007/001514
Other languages
English (en)
Other versions
WO2008078314B1 (fr
Inventor
Eran Sharon
Idan Alrod
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Western Digital Israel Ltd
Original Assignee
SanDisk IL Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from US11/808,905 external-priority patent/US8370561B2/en
Priority claimed from US11/808,906 external-priority patent/US8127200B2/en
Application filed by SanDisk IL Ltd filed Critical SanDisk IL Ltd
Priority to KR1020097009421A priority Critical patent/KR101449673B1/ko
Publication of WO2008078314A1 publication Critical patent/WO2008078314A1/fr
Publication of WO2008078314B1 publication Critical patent/WO2008078314B1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11C—STATIC STORES
    • G11C16/00—Erasable programmable read-only memories
    • G11C16/02—Erasable programmable read-only memories electrically programmable
    • G11C16/04—Erasable programmable read-only memories electrically programmable using variable threshold transistors, e.g. FAMOS
    • G11C16/0483—Erasable programmable read-only memories electrically programmable using variable threshold transistors, e.g. FAMOS comprising cells having several storage transistors connected in series
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11C—STATIC STORES
    • G11C16/00—Erasable programmable read-only memories
    • G11C16/02—Erasable programmable read-only memories electrically programmable
    • G11C16/06—Auxiliary circuits, e.g. for writing into memory
    • G11C16/26—Sensing or reading circuits; Data output circuits
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11C—STATIC STORES
    • G11C11/00—Digital stores characterised by the use of particular electric or magnetic storage elements; Storage elements therefor
    • G11C11/56—Digital stores characterised by the use of particular electric or magnetic storage elements; Storage elements therefor using storage elements with more than two stable states represented by steps, e.g. of voltage, current, phase, frequency
    • G11C11/5621—Digital stores characterised by the use of particular electric or magnetic storage elements; Storage elements therefor using storage elements with more than two stable states represented by steps, e.g. of voltage, current, phase, frequency using charge storage in a floating gate
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11C—STATIC STORES
    • G11C16/00—Erasable programmable read-only memories
    • G11C16/02—Erasable programmable read-only memories electrically programmable
    • G11C16/06—Auxiliary circuits, e.g. for writing into memory
    • G11C16/34—Determination of programming status, e.g. threshold voltage, overprogramming or underprogramming, retention
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11C—STATIC STORES
    • G11C16/00—Erasable programmable read-only memories
    • G11C16/02—Erasable programmable read-only memories electrically programmable
    • G11C16/06—Auxiliary circuits, e.g. for writing into memory
    • G11C16/34—Determination of programming status, e.g. threshold voltage, overprogramming or underprogramming, retention
    • G11C16/3418—Disturbance prevention or evaluation; Refreshing of disturbed memory data
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11C—STATIC STORES
    • G11C7/00—Arrangements for writing information into, or reading information out from, a digital store
    • G11C7/10—Input/output [I/O] data interface arrangements, e.g. I/O data control circuits, I/O data buffers
    • G11C7/1006—Data managing, e.g. manipulating data before writing or reading out, data bus switches or control circuits therefor

Definitions

  • the present invention relates generally to flash memory storage systems. Specifically, the present invention, relates to a flash memory storage system in which the flash memory is capable of storing multiple bits per memory cell, and in which certain disturbance effects are minimized.
  • Flash memory devices have been known for many years. Typically, each cell within a flash memory stores one bit of information. Traditionally, the way to store a bit has been by supporting two states of the cell — one state represents a logical "0" and the other state represents a logical "1". In a flash memory cell the two states are implemented by having a floating gate above the cell's channel (the area connecting the source and drain elements of the cell's transistor), and having two valid states for the amount of charge stored within this floating gate.
  • one state is with zero charge in the floating gate and is the initial unwritten state of the cell after being erased (commonly defined to represent the "1" state) and another state is with some amount of negative charge in the floating gate (commonly defined to represent the "0" state).
  • Having negative charge in the gate causes the threshold voltage of the cell's transistor (i.e. the voltage that has to be applied to the transistor's control gate in order to cause the transistor to conduct) to increase.
  • the threshold voltage of the cell's transistor i.e. the voltage that has to be applied to the transistor's control gate in order to cause the transistor to conduct
  • Figure IA shows graphically how this works. Specifically, Figure IA shows the distribution of the threshold voltages of a large population of cells. Because the cells in a flash device are not exactly identical in their characteristics and behavior (due, for example, to small variations in impurity concentrations or to defects in the silicon structure), applying the same programming operation to all the cells does not cause all of the cells to have exactly the same threshold voltage.
  • the threshold voltage is distributed similar to the way shown in Figure IA.
  • Cells storing a value of "1” typically have a negative threshold voltage, such that most of the cells have a threshold voltage close to the value shown by the left peak of Figure IA 5 with some smaller numbers of cells having lower or higher threshold voltages.
  • cells storing a value of "0” typically have a positive threshold voltage, such that most of the cells have a threshold voltage close to the value shown by the right peak of Figure IA 5 with some smaller numbers of cells having lower or higher threshold voltages.
  • MLC Multi Level Cells
  • FIG. 1 shows the threshold voltage distribution for a typical MBC cell. As expected, Figure IB has four peaks, each corresponding to one of the states. As for the SBC case, each state is actually a range of threshold voltages and not a single threshold voltage. " When reading the cell's contents, all that must be guaranteed is that the range that the cell's threshold voltage is in is correctly identified.
  • one way to read the lower bit is first to compare the cell's threshold voltage to a reference comparison voltage V ⁇ and then, depending on the outcome of the comparison s to compare the cell's threshold voltage to either a zero reference comparison voltage or a reference comparison voltage V%.
  • Another way to read the lower bit is to compare the cell's threshold voltage unconditionally to both the zero reference voltage and V % . In either case, two comparisons are needed.
  • MBC devices provide a great advantage of cost — using a similarly sized cell one stores two bits rather than one.
  • MBC flash the average read and write times of MBC memories are longer than of SLC memories, resulting in lower performance.
  • the reliability of MBC is lower than SBC.
  • SBC the differences between the threshold voltage ranges in MBC are much smaller than in SBC.
  • a disturbance in the threshold voltage e.g. leaking of the stored charge causing a threshold voltage drift, interference from operations on neighboring cells, etc.
  • SBC a disturbance in the threshold voltage (e.g. leaking of the stored charge causing a threshold voltage drift, interference from operations on neighboring cells, etc.) that may have gone unnoticed in SBC because of the large gap between the two states, might cause an MBC cell to move from one state to another, resulting in an erroneous bit.
  • the end result is a lower quality specification of MBC cells in terms of data retention time or the endurance of the device to many write/erase cycles.
  • the PD effect causes cells, that are not intended to be written, to unintentionally move from their initial left-most state to some other state.
  • the explanations herein assume the common practice, also used in Figures IA and IB, of drawing the threshold voltage axis such that its left direction represents lower values. This is an arbitrary practice and should not be construed to limit the scope of the present invention in any way).
  • Referring to the two-bit-per-cell example of Figure IB cells that are in the leftmost state corresponding to bit values of "11" (or in other words, to the cell's erased state) and that are supposed to remain in such state, are found to be in the next-to-leftmost state of "10", resulting in one bit out of the two bits stored in such cells to be incorrect.
  • PD effects might turn out not only as a move from the leftmost state to its immediately adjacent state, but also as a move from the leftmost state to more distant states, and also as a move from a state that is not the leftmost state to another state to its right (i.e. having a higher threshold voltage).
  • the case described first above of moving from the leftmost state to its immediately adjacent neighboring state is the most common, and will be used herein for all examples and explanations without limiting the generality of the methods of the present invention.
  • Figure 2 which is identical to Figure 1 of the Chen patent, is a block diagram of a typical prior art flash memory device.
  • a memory cell array 1 including a plurality of memory cells M arranged in a matrix is controlled by a column control circuit 2, a row control circuit 3, a c-source control circuit 4 and a c-p-well control circuit 5.
  • Column control circuit 2 is connected to bit lines (BL) of memory cell array 1 for reading data stored in the memory cells (M), for determining a state of the memory cells (M) during a program operation, and for controlling voltage levels of the bit lines (BL) to promote the programming or to inhibit the programming.
  • BL bit lines
  • Row control circuit 3 is connected to word lines (WL) to select one of the word lines (WL), to apply read voltages, to apply programming voltages combined with the bit line voltage levels controlled by column control circuit 2, and to apply an erase voltage coupled with a voltage of a p- type region on which the memory cells (M) are formed.
  • C-source control circuit 4 controls a common source line connected to the memory cells (M).
  • C-p-well control circuit 5 controls the c-p-well voltage.
  • a page is the smallest unit of a NAND flash device whose cells can be programmed together.
  • a block is the smallest unit of a NAND flash device whose cells can be erased together.
  • the data stored in the memory cells (M) are read out by column control circuit 2 and are output to external I/O lines via an I/O line and a data input/output buffer 6.
  • Program data to be stored in the memory cells are input to data input/output buffer 6 via the external I/O lines, and are transferred to the column control circuit 2.
  • the external I/O lines are connected to a controller 20.
  • Command data for controlling the flash memory device are input to a command interface connected to external control lines that are connected with controller 20.
  • the command data informs the flash memory of what operation is requested.
  • the input command is transferred to a state machine 8 that controls column control circuit 2, row control circuit 3, c-source control circuit 4, c-p-well control circuit 5 and data input/output buffer 6.
  • State machine 8 can output a status data of the flash memory such as READY/BUSY or PASS/FAIL.
  • Controller 20 is connected or connectable with a host system such as a personal computer, a digital camera, a personal digital assistant. It is the host that initiates commands, such as to store or read data to or from, memory array 1, and provides or receives such data, respectively. Controller 20 converts such commands into command signals that can be interpreted and executed by command circuits 7. Controller 20 also typically contains buffer memory for the user data being written to or read from memory array 1.
  • a typical memory system includes one integrated circuit chip 21 that includes controller 20, and one or more integrated circuit chips 22 that each contain a memory array and associated control, input/output and state machine circuits. The trend, of course, is to integrate the memory array and controller circuits of a system together on one or more integrated circuit chips.
  • the memory system may be embedded as part of the host system, or may be included in a memory card that is removably insertable into a mating socket of host systems.
  • a memory card may include the entire memory system, or the controller and memory array, with associated peripheral circuits, may be provided in separate cards.
  • the reason for the PD effect is easy to understand when reviewing the voltages applied to the cells of a NAND flash device when programming a page.
  • a relatively high voltage is applied to the word line connected to the control gates of the cells of the page.
  • What decides whether a certain cell threshold voltage is increased as a result of this control gate voltage is the voltage applied to the bit line connected to that cell.
  • a cell that is not to be written with data (that is — that is to remain erased, representing an all-one state), has its bit line connected to a relatively high voltage level that minimizes the voltage difference across the cell.
  • a cell that is to be written has its bit line connected to low voltage, causing a large voltage difference across the cell, and resulting in the cell's threshold voltage getting increased, thus moving the cell to the right on the voltage axis of Figure IB and causing the cell's state to change.
  • the cells that are not meant to be written still have some voltage difference across them. If the page to be written has some cells that are written to high threshold voltages (for example, to the rightmost state), then the voltage difference across non-programmed cells gets higher. This is because all control gates of all cells of the page get the same voltage applied to them, and the higher the threshold voltage to be reached, the higher is that voltage.
  • PD is an effect in which when programming a page of cells, some cells that are intended to remain in the leftmost erased state end up in another state, resulting in bit errors when reading those cells.
  • PD effects can be empirically and statistically measured, and counter- measures in the form of error correction schemes may be applied to handle them. Flash device manufacturers are aware of this source of potential errors, and they take it into account when recommending to their customers the level of error correction the customers should use. So when a manufacturer of a two-bit-per-cell MBC flash device recommends a 4-bit ECC scheme (meaning that every 512 bytes of user data should be protected against the occurrence of up to four bit errors), he may base this recommendation on a statistical analysis that assumes a random data pattern stored into the device and on the probability that a PD-type error will occur under such circumstances. Obviously, other error sources and types are also taken into account in such calculations.
  • the PD effect is an error source that depends on the user data stored in a flash memory
  • the Back Pattern (BP) phenomenon which is a result of different bit lines BL having different resistances
  • the resistance of a bit line depends on the data stored in the cells along the bit line, i.e. the resistance of a bit line depends on the actual states or voltage levels of the cells along the bit line.
  • the different bit line resistances result in different bit line currents. This can cause different voltage level sensing during the reading of two cells in two different bit lines, even if these two cells are programmed to the exact same voltage level (i.e. the two cells have exactly the same threshold voltage).
  • a random sequence is a sequence with no recognizable patterns or regularities. No element of the sequence can be predicted from knowing other elements of the sequence.
  • randomization is defined herein as an operation that increases the randomness of a highly nonrandom sequence of bits.
  • the bits of a sequence that has been "randomized' are less easily predictable from the other bits of the sequence than are the bits of the sequence prior to randomization.
  • the randomization processes of the present invention are deterministic, the output sequences of these processes are predictable and so are not truly random but only "pseudorandom", in the sense that the patterns or regularities of the output sequences are harder to recognize, and preferably are much harder to recognize, than the patterns or regularities of the input sequences.
  • the "randomized" sequences recited in the appended claims are pseudorandom sequences, not true random sequences.
  • One special case of randomization is “scrambling”. Scrambling is an invertible transformation of an input bit sequence to an output bit sequence, such that each bit of the output bit sequence is a function of several bits of the input bit sequence and of an auxiliary bit sequence.
  • the inverse of randomization is “derandomization”.
  • the inverse of scrambling is "descrambling”.
  • Randomizing is defined similarly for sets of states of memory cells.
  • a first set of states of memory cells is “randomized” relative to a second set of states of the same memory cells if the bit sequence that is represented by the cells when the cells are programmed to the first set of states is more random than the bit sequence that is represented by the cells when the cells are programmed to the second set of states.
  • the various memory cell states appear in approximately equal numbers in a "randomized" set of memory cell states.
  • a “nonrandom” bit sequence is a bit sequence with recognizable patterns and/or regularities.
  • a “nonrandom" set of memory cell states is a set of cell states with recognizable patterns and/or regularities and/or having a non-uniform induced distribution over the cell states.
  • a device for storing data including: (a) a nonvolatile memory; and (b) a controller, of the nonvolatile memory, operative: (i) to randomize original data to be stored in the memory while preserving a size of the original data, thereby providing randomized data, (ii) to store the randomized data in the memory, and (iii) in response to a request for the original data by an entity external to the device: (A) to retrieve the randomized data from the memory, and (B) to derandomize the retrieved randomized data, thereby providing retrieved data substantially identical to the original data, and (C) to export the retrieved data to the entity without authenticating the entity.
  • a device for storing data including: (a) a memory that includes: (i) an array of nonvolatile memory cells, and (ii) circuitry operative: (A) to randomize original data that are to be stored in the memory cells while preserving a size of the original data, thereby providing randomized data, (B) to store the randomized data in at least a portion of the memory cells, (C) to retrieve the randomized data from the at least portion of the memory cells, and (D) to derandomize the retrieved randomized data, thereby providing retrieved data substantially identical to the original data; and (b) a controller operative: (i) in response to a request for the original data from an entity external to the device, to export the retrieved data to the entity without authenticating the entity.
  • a system for storing data including: (a) a first nonvolatile memory; (b) a second nonvolatile memory wherein is stored a driver for the first nonvolatile memory, the driver including: (i) code for randomizing original data to be stored in the first nonvolatile memory while preserving a size of the original data, thereby providing randomized data, (ii) code for storing the randomized data in the first nonvolatile memory, and (iii) code for responding to a request for the original data by: (A) retrieving the randomized data from the first nonvolatile memory, (B) derandomizing the retrieved randomized data, thereby providing retrieved data substantially identical to the original data, and (C) exporting the retrieved data without authenticating the request; and (c) a processor for executing the code of the driver.
  • a computer-readable storage medium having computer-readable code embedded thereon, the computer-readable code being driver code for a memory device, the computer-readable code including: (a) program code for randomizing original data to be stored in a memory of the memory device while preserving a size of the original data, thereby providing randomized data; (b) program code for storing the randomized data in the memory; and (c) program code for responding to a request for the original data by: (i) retrieving the randomized data from the memory, (ii) derandomizing the retrieved randomized data, thereby providing retrieved data substantially identical to the original data, and (iii) exporting the retrieved data without authenticating the request.
  • a device for storing data including: (a) a nonvolatile memory having a sufficient number of memory cells to store original data by programming the memory cells to a set of corresponding states of the memory cells; and (b) a controller, of the nonvolatile memory, operative: (i) to map the original data into a set of states of all the memory cells that is randomized relative to the set of corresponding states, (ii) to instruct the memory to program the memory cells to the randomized set of states, and (iii) in response to a request for the original data by an entity external to the device: (A) to read the memory cells, thereby providing retrieved randomized data, (B) to derandomize the retrieved randomized data, thereby providing retrieved data substantially identical to the original data, and (C) to export the retrieved data to the entity without authenticating the entity.
  • a device for storing data including: (a) a memory that includes: (i) a sufficient number of memory cells to store original data by programming the memory cells to a set of corresponding states of the memory cells, and (ii) circuitry operative: (A) to map the original data into a set of states of all the memory cells that is randomized relative to the set of corresponding states, (B) to program the memory cells to the randomized set of states, (C) to read the memory cells, thereby providing retrieved randomized data, and (D) to derandomize the retrieved randomized data, thereby providing retrieved data substantially identical to the original data; and (b) a controller operative, in response to a request for the original data from an entity external to the device, to export the retrieved data to the entity without authenticating the entity.
  • a system for storing data including: (a) a first nonvolatile memory having a sufficient number of memory cells to store original data by programming the memory cells to a set of corresponding states of the memory cells; (b) a second nonvolatile memory wherein is stored a driver for the first nonvolatile memory, the driver including: (i) code for mapping the original data into a set of states of all the memory cells that is randomized relative to the set of corresponding states, (ii) code for instructing the first nonvolatile memory to program the memory cells to the randomized set of states, and (iii) code for responding to a request for the original data by: (A) instructing the first nonvolatile memory device to read the memory cells, thereby providing retrieved randomized data, (B) derandomizing the retrieved randomized data, thereby providing retrieved data substantially identical to the original data, and (C) exporting the retrieved data without authenticating the request; and (c) a processor for executing the code of the
  • a computer-readable storage medium having computer-readable code embedded thereon, the computer- readable code being driver code for a memory device that includes a sufficient number of memory cells to store original data by programming the memory cells to a set of corresponding states of the memory cells, the computer-readable code including: (a) program code for mapping the original data into a set of states of all the memory cells that is randomized relative to the set of corresponding states; (b) program code for instructing the memory device to program the memory cells to the randomized set of states; and (c) program code for responding to a request for the original data by.
  • a method of storing data including the steps of: (a) randomizing original data while preserving a size of the original data, thereby providing randomized data; (b) storing the randomized data in a nonvolatile memory; and (c) in response to a request for the original data: (i) retrieving the randomized data from the memory, (ii) derandomizing the retrieved randomized data, thereby providing retrieved data substantially identical to the original data, and (iii) exporting the retrieved data to an entity from which the request is received without authenticating the entity.
  • a method of storing data including the steps of: (a) providing a sufficient number of memory cells to store original data by programming the memory cells to a set of corresponding states of the memory cells; (b) mapping the original data into a set of states of all the memory cells that is randomized relative to the set of corresponding states; (c) programming the memory cells to the randomized set of states; and (d) in response to a request for the original data: (i) reading the memory cells, thereby providing retrieved randomized data, (ii) derandomizing the retrieved randomized data, thereby providing retrieved data substantially identical to the original data, and (iii) exporting the retrieved data to an entity from which the request was received without authenticating the entity.
  • the scope of the present invention includes two basic devices and a basic system for storing data.
  • the first basic device includes a nonvolatile memory and a controller.
  • the controller randomizes original data that are to be stored in the memory, while preserving the size of the original data, thereby providing randomized data.
  • the controller stores the randomized data in the memory.
  • the controller retrieves the randomized data from the memory and derandomizes the retrieved randomized data, thereby providing retrieved data substantially identical to the original data. It is greatly preferred that the retrieved data be strictly identical to the original data, but this can not be guaranteed in all cases, because e.g. of errors, in reading the data, that are not corrected by error correction decoding.
  • the retrieved data are exported to the entity without authenticating the entity.
  • the second basic device includes a memory and a controller.
  • the memory includes an array of nonvolatile memory cells and circuitry that performs the randomization, storage, retrieval and derandomization functions of the controller of the first basic device.
  • the controller performs the authentication-free export of the retrieved data that is performed by the controller of the first basic device.
  • either controller applies error correction encoding to the original data prior to the randomization and applies error correction decoding to the retrieved data prior to exporting the retrieved data.
  • the controller of the first device applies error correction encoding to the randomized data prior to storing the randomized data and applies error correction decoding to the retrieved randomized data prior to derandomization.
  • the error correction encoding may be either systematic encoding, in which error correction bits are appended to the encoded data to produce a codeword, or nonsystematic encoding, in which the data being encoded are not recognizable in the codeword.
  • the randomization includes summing the original data, modulo 2, with a fixed, random bit sequence or with a pseudorandom bit sequence
  • the derandomization includes summing the retrieved randomized data, modulo 2, with the random bit sequence or with the pseudorandom bit sequence.
  • the pseudorandom bit sequence is fixed.
  • the pseudorandom bit sequencers generated by the controller of the first device or by the circuitry of the second device, for example using a linear feedback shift register whose seed either is fixed or is a function of the unit number of the unit, from among units into which the memory is partitioned, in which the randomized data are stored.
  • the units may be blocks of the flash memory or pages of the flash memory.
  • the randomization includes scrambling the original data and the derandomization includes descrambling the retrieved randomized data.
  • the circuitry includes a scrambler block for performing the scrambling and a descrambler block for performing the descrambling.
  • the scrambling and descrambling are effected using respective linear feedback shift registers that share a common seed.
  • the seed is fixed.
  • the seed is a function of the unit number of the unit, from among units into which the memory is partitioned, in which the randomized data are stored.
  • the units may be blocks of the flash memory or pages of the flash memory.
  • a basic system of the present invention includes a first nonvolatile memory, a second nonvolatile memory, and a processor.
  • a driver that includes code that is executed by the processor to emulate the controller of the first device of the present invention.
  • the entity that requests the original data typically is a user application running on the system and executing commands, for programming and reading the first nonvolatile memory, that are supported by the driver.
  • linear feedback shift registers may be implemented in hardware, firmware, software or combinations thereof.
  • the scope of the present invention also includes, as a method, the methods used by the devices and the system of the present invention for storing data.
  • the scope of the present invention also includes a computer-readable storage medium having embedded thereon computer-readable code for the driver of the system of the present invention.
  • the method of the present invention is a method of storing original data in a sufficient number of memory cells to be programmed to a set of corresponding states of the memory cells.
  • 512 SBC flash cells or 256 four-state MBC flash cells can be programmed to store 512 bits of data.
  • the original data are mapped into a set of states of all the cells (all 512 SBC cells or all 256 MBC cells in the example) that is randomized relative to the set of corresponding states.
  • the memory cells then are programmed to the randomized set of states rather than to the original set of corresponding states.
  • the numbers of states in the two sets are identical distinguishes the method of the present invention, from this point of view, from similar prior art methods in which the data are stored in compressed form in fewer memory cells than would be needed to store the same data in uncompressed form.
  • the preferred method of mapping the original data into the randomized set of memory cell states is by randomizing the original data.
  • the various memory cell states occur in the randomized set of states in substantially equal numbers.
  • FIG. IA illustrates the threshold voltage distributions of flash cells programmed in 1-bit mode
  • FIG. IB illustrates the threshold voltage distributions of flash cells programmed in 2-bit mode
  • FIG. 2 is a block diagram of a flash memory device
  • FIGs. 3 A and 3B are schematic block diagrams of randomizing/derandomizing and ECC encoding/decoding according to the present invention
  • FIG. 4 illustrates exemplary randomizer and derandomizer blocks that use a fixed random sequence of bits
  • FIG. 5 illustrates exemplary randomizer and derandomizer blocks that use a pseudorandom sequence of bits generated by a liner feedback shift register
  • FIG. 6 illustrates exemplary scrambler and descrambler blocks
  • FIGs. 7-9 are high-level block diagrams of systems of the present invention.
  • the device of the present invention is a multi-bit-per-cell flash memory storage device that eliminates or reduces the dependency between the user data stored in the flash and the raw flash error rates (before ECC decoding). This is done by transforming the user data bits into a pseudorandom bit sequence that then is programmed into the flash memory. As a result, the probability of problematic
  • the suggested solution is not optimal, because switching the erase state with an alternative state makes the alternative state vulnerable to PD errors. For example, consider the previous example, in which we flip all the bits such that the all l's and all O's states are switched. Then if the user data contains large sequences of O's, the programmed page will still suffer from many PD-related errors.
  • the method of the present invention solves the problem of data dependent errors in a much more general way. Enumerating all the problematic data patterns is a very hard (and probably infeasible) task because such an enumeration requires complete understanding of the various physical phenomena occurring in the flash memory and a complete statistical characterization of the user application that generates the data in order to determine which data patterns are stored more frequently than others. Hence, instead of dealing with specific data patterns that are problematic with, respect to a specific phenomenon such as PD, the method of the present invention reduces the probability of any pattern practically to zero by making sure that the bit sequences written to the flash memory are pseudorandom.
  • transformation of the user data bits into a pseudo-random bit sequence is done using a randomizer block (implemented in hardware, firmware or software), according to one of several methods known in the art.
  • the transformation needs to be invertible.
  • the inverse transformation is done using a derandomizer block.
  • the transformation can be done either on the user data bits, before ECC encoding (as shown in Figure 3A) or on the encoded user data bits after ECC encoding (as shown in Figure 3B).
  • the user data bits can be recovered by performing the inverse transformation on the bit sequence that is read from the flash memory after the bit sequence is decoded using an ECC decoder (as shown in Figure 3A).
  • the inverse transformation is performed directly on the bit sequence that is read from the flash memory.
  • the resulting bit sequence is then decoded using an ECC decoder in order to recover the user data bits (as shown in Figure 3B).
  • the randomization is performed by summing the user data bits modulo 2 with a fixed random sequence of bits or with a fixed pseudorandom sequence of bits.
  • the resulting randomized bit sequence is ECC encoded (if needed) and then programmed into the flash memory.
  • the read bit sequence is decoded via an ECC decoder (if needed).
  • the user data bits are recovered by derandomizing the decoded, error free, bit sequence by summing the bit sequence modulo 2 with the known fixed random or pseudorandom bit sequence.
  • An example of the randomizer and derandomizer blocks according to this embodiment is shown in Figure 4.
  • the randomization is performed by summing the ECC encoded user data bits modulo 2 with a fixed random sequence of bits or with a fixed pseudorandom sequence of bits. The resulting randomized bit sequence is then programmed into the flash memory. Upon reading the flash memory, the read bit sequence is derandomized by summing the read bit sequence modulo 2 with the known fixed random or pseudorandom bit sequence. The user data bits are then recovered by ECC decoding the derandomized bit sequence.
  • An example of the randomizer and derandomizer blocks according to this embodiment also is shown in Figure 4.
  • the randomization is performed by summing the user data bits modulo 2 with a pseudo-random sequence of bits.
  • the pseudorandom sequence of bits is generated, for example, using a linear feedback shift register.
  • the feedback shift register is constructed according to a primitive polynomial of a sufficiently large finite field (a Galois field) (S. Golomb, Shift Register Sequences, Agean Park Press, Madison Hills CA USA, 1982).
  • the resulting randomized sequence of bits is ECC encoded (if needed) and then programmed into the flash memory.
  • the read bit sequence is decoded using an ECC decoder (if needed).
  • the user data bits are recovered by derandomizing the decoded, error free bit sequence by summing the bit sequence modulo 2 with the same pseudorandom bit sequence that was used during programming.
  • the same bit sequence is obtained during programming and reading by using the same seed for initialization of the feedback shift register, i.e. by initializing the feedback shift register with the same sequence of bits.
  • the randomization is performed by summing the ECC encoded user data bits modulo 2 with a pseudorandom sequence of bits. The randomized bit sequence is then programmed into the flash. Upon reading the flash memory, the read bit sequence is derandomized by summing the bit sequence modulo 2 with the same pseudo-random bit sequence that was used during programming. The user data bits are then recovered by ECC decoding of the derandomized bit sequence.
  • An example of the randomizer and derandomizer blocks according to this embodiment also is shown in Figure 5.
  • the seed can be constant.
  • the seed can be a function of the unit number of the block or page of the flash memory in which the data are stored.
  • An example of the randomizer and derandomizer blocks according to this embodiment is shown in Figure 5.
  • the pages to which the current data are copies have different page numbers than the pages from which the current data are copied.
  • the change in unit number associated with such garbage collection must be taken into account.
  • One way to ensure that the same seed is used for both programming and reading is to always derandomize data that are to be moved to a new page or to a new block and to rerandomize the data, possibly using a different seed, when writing the data to the new page or to the new block.
  • Another way to ensure that the same seed is used for both programming and reading is to always move data to a new page or to a new block such that the function of unit number that produces the seed produces the same seed for both the old unit number and the new unit number. For example, if the function "page number modulo 8" is used to generate the seed, the garbage collection should always copy a page of data to a new page whose page number, in binary notation, has the same last three bits as the page number of the old page.
  • each page of a NAND flash memory typically includes a main portion that is used to store data and a management portion that is used to store management information.
  • a typical size of such a page is 528 bytes: 512 bytes for storing data and 16 bytes for storing management information.
  • the seed that is used to generate the pseudo-random sequence for randomizing data stored in the main portion of a page is stored in the management portion of the page.
  • the cells that store the seed should be excluded from the randomization process, to guarantee that the seed is read correctly for derandomizing.
  • logical page addresses can be used as seeds for generating pseudo-random sequences.
  • a flash file system provides a system of data storage and manipulation on a flash memory device that allows the device to emulate a magnetic disk.
  • a flash file system enables applications or operating systems interact with a flash memory device not using physical addresses but rather using logical addresses (sometimes called virtual addresses).
  • An intermediary software layer between the software application and the physical memory system provides a mapping between logical addresses and physical addresses.
  • the randomization is performed by passing the user data bits through a scrambler block.
  • the scrambler can be implemented using a linear feedback shift register.
  • the feedback shift register is constructed according to a primitive polynomial of some large enough finite field (a Galois field) (S. Golomb, ibid).
  • the linear feedback shift register is initialized with a predefined seed.
  • the seed can be constant or a function of the unit number of the page or block of the flash memory where the data is stored, or any other parameter that is known when the data are read.
  • the resulting pseudo-random sequence of bits at the output of the scrambler is ECC encoded (if needed) and then programmed into the flash memory.
  • the read bit sequence is decoded using an ECC decoder (if needed).
  • the user data bits are then recovered by derandomizing the decoded, error free bit sequence using a descrambler block initialized with the same seed as the one used in the scrambler block during programming.
  • the scrambler block is implemented by a linear feedback shift register that is constructed based on a polynomial
  • the descrambler block preferably is implemented as linear shift register representing the inverse polynomial.
  • An example of the randomizer and derandomizer blocks according to this embodiment is shown in Figure 6.
  • the randomization is performed by passing the ECC encoded user data bits through a scrambler block.
  • One way to implement the scrambler is using a linear feedback shift register, initialized with a predefined seed.
  • the resulting pseudo-random sequence of bits at the output of the scrambler is programmed into the flash memory.
  • the read bit sequence is derandomized using a descrambler block initialized with the same seed as the one used in the scrambler block during programming.
  • the scrambler block is implemented by a linear feedback shift register that is constructed based on a polynomial
  • the descrambler block preferably is implemented as linear shift register representing the inverse polynomial.
  • the user data bits are then recovered by ECC decoding of the derandomized bit sequence.
  • An example of the randomizer and derandomizer blocks according to this embodiment also is shown in Figure 6. Considerations regarding the interaction of a seed based on unit number with garbage collection are the same as in the case of a randomizer block based on a linear feedback shift register, as discussed above.
  • the first approach to scrambling and descrambling in which scrambling is performed before ECC encoding and descrambling is performed after ECC decoding, is preferred over the second approach in which scrambling is performed after ECC encoding and descrambling is performed before ECC decoding.
  • the randomization is performed serially, bit by bit.
  • the randomization is parallelized, such that the randomizer/derandomizer blocks output several bits simultaneously.
  • the pseudo-random bit sequence produced by the randomization block has as many bits as the original bit sequence that is input to the randomization block. This is an aspect of the present invention that distinguishes the present invention from prior art compression that also randomizes the input data to a certain extent but also outputs fewer bits than are in the input data.
  • the erased state is different from all data states. Specifically, the erased state has a more negative threshold voltage than any of the data states.
  • the cell is programmed (that is — its threshold voltage is increased) to reach the state corresponding to the data value.
  • the erased state is different than the all-ones state, unlike the devices previously referred to.
  • the methods of the present invention can be implemented either by software or by hardware. More specifically, the randomizing of the data during programming and the derandomizing of the data during reading can be implemented by executing software code or by electrical circuitry (such as inverter gates). If the randomizing and derandomizing are implemented by software, they may be implemented either by software executed on the host computer which writes or reads the data (for example, within the software device driver supporting the storage device), or they may be implemented by firmware executed within the memory controller ⁇ e.g. controller 20 of Figure 2) that interacts with the host computer and controls the memory media. If the randomizing and derandomizing are implemented by hardware, they may be implemented either in the memory controller or within the memory media (e.g. in command circuits 7 of Figure 2). This applies whether the memory controller and the memory media are two separate dies or reside on a common die. All the above configurations and variations are within the scope of the present invention.
  • Figure 2 also illustrates two kinds of embodiments of a flash memory device of the present invention.
  • controller 20 performs the ECC encoding and decoding and command circuits 7 perform the randomization and the derandomization.
  • controller 20 performs both ECC encoding/decoding and randomization/derandomization.
  • controller 20 upon receiving a read command from the host of the flash memory device, exports the read data to the host without requiring the host to authenticate itself. In other words, the host is not required to prove to controller 20 that the host is authorized to receive the read data in order for controller 20 to send the read data to the host.
  • Figures 7 and 8 are high-level block diagrams of two systems 40 and 60 that include flash memory device embodiments of the second kind.
  • system 40 a host computer 42 sends read and write instructions to a flash memory device 52 of the present invention.
  • Flash memory device 52 uses a flash controller 44 to manage a flash memory 50 by executing flash management software 46.
  • Flash management software 46 includes a randomization module 48 and a ECC module 49 for performing randomization/derandomization and ECC encoding/decoding, as discussed above, either in the order shown in Figure 3A or in the order shown in Figure 3B.
  • a host computer sends read and write instructions to a flash memory device 72.
  • Flash memory device 72 uses a flash controller 64 to manage a flash memory 70 by executing flash management software 66.
  • Flash controller 64 also includes randomization hardware 68 and ECC hardware 69 for performing randomization/derandomization and ECC encoding/decoding, as discussed above, either in the order shown in Figure 3 A or in the order shown in Figure 3B.
  • FIG 9 is a high-level block diagram of another system 80 of the present invention.
  • System 80 includes a processor 82 and four memory devices: a RAM 84, a boot ROM 86, a mass storage device (hard disk) 88 and a prior art flash memory device 94, all communicating via a common bus 60.
  • Flash memory driver code 90 is stored in mass storage device 88 and is executed by processor 82 to interface between user applications executed by processor 82 and flash memory device 94, and to manage the flash memory of flash memory device 94.
  • Driver code 90 includes a randomization module 92 and a ECC module 93 for performing randomization/derandomization and ECC encoding/decoding, as discussed above, either in the order shown in Figure 3A or in the order shown in Figure 3B.
  • a user application that reads data from flash memory device 94 is not required by driver code 90 to authenticate itself in order to receive the requested data.
  • Driver code 90 typically is included in operating system code for system 80 but also could be freestanding code.
  • Mass storage device 88 is an example of a computer-readable storage medium bearing computer-readable driver code for implementing the present invention.
  • Other examples of such computer-readable storage media include read-only memories such as CDs bearing such code.
  • flash controller 44 or 64 optionally is configured to allow a user of device 52 or 72 to partition flash memory 50 or 70 between a private partition and a public partition. Access to data stored in the private partition requires authentication such as presentation of a password. Access to data stored in the public partition does not require authentication.
  • flash controller 44 or 64 is configured to support a command, from a privileged user, that switches device 52 or 72 between a secure mode, in which access to data stored in flash memory 50 or 70 requires authentication, and an open mode, in which access to data stored in flash memory 50 or 70 does not require authentication. All the present invention requires with regard to access without authentication is that one of the operational modes of a device or system of the present invention must allow the reading of at least some stored data without requiring the entity that requests the data to authenticate itself.

Landscapes

  • Engineering & Computer Science (AREA)
  • Microelectronics & Electronic Packaging (AREA)
  • Computer Hardware Design (AREA)
  • Techniques For Improving Reliability Of Storages (AREA)
  • Read Only Memory (AREA)

Abstract

La présente invention concerne un dispositif et un procédé pour stocker des données comprenant une mémoire non volatile et un contrôleur et/ou un ensemble de circuits qui répartissent de manière aléatoire des données d'origine devant être stockées dans la mémoire tout en préservant la taille des données d'origine, qui stockent les données d'origine dans la mémoire, et qui, en réponse à une requête concernant les données d'origine, retirent, dé-répartissent de manière aléatoire et exportent les données d'origine sans authentifier l'entité effectuant la requête. Un système et un procédé pour stocker des données comprennent une première mémoire non volatile et un processeur qui stocke de manière similaire des données dans la première mémoire non volatile en exécutant un code de pilote stocké dans une seconde mémoire non volatile. Un encodage EEC est appliqué avant ou après la répartition aléatoire; de manière correspondante, un décodage EEC est appliqué avant ou après la dé-répartition aléatoire.
PCT/IL2007/001514 2006-12-24 2007-12-06 Dispositif, système et procédé de mémoire flash avec répartition aléatoire pour supprimer une erreur Ceased WO2008078314A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
KR1020097009421A KR101449673B1 (ko) 2006-12-24 2007-12-06 에러 억제를 위해 랜더마이징하는 플래시 메모리 디바이스, 시스템 및 방법

Applications Claiming Priority (6)

Application Number Priority Date Filing Date Title
US87182006P 2006-12-24 2006-12-24
US60/871,820 2006-12-24
US11/808,905 US8370561B2 (en) 2006-12-24 2007-06-13 Randomizing for suppressing errors in a flash memory
US11/808,906 2007-06-13
US11/808,905 2007-06-13
US11/808,906 US8127200B2 (en) 2006-12-24 2007-06-13 Flash memory device and system with randomizing for suppressing errors

Publications (2)

Publication Number Publication Date
WO2008078314A1 true WO2008078314A1 (fr) 2008-07-03
WO2008078314B1 WO2008078314B1 (fr) 2008-08-14

Family

ID=39268833

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/IL2007/001514 Ceased WO2008078314A1 (fr) 2006-12-24 2007-12-06 Dispositif, système et procédé de mémoire flash avec répartition aléatoire pour supprimer une erreur

Country Status (2)

Country Link
KR (1) KR101449673B1 (fr)
WO (1) WO2008078314A1 (fr)

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2226810A1 (fr) * 2009-03-04 2010-09-08 Apple Inc. Blanchiment de données pour l'écriture et la lecture de données depuis/vers une mémoire non volatile
US8693257B2 (en) 2011-10-18 2014-04-08 Seagate Technology Llc Determining optimal read reference and programming voltages for non-volatile memory using mutual information
US8711619B2 (en) 2011-10-18 2014-04-29 Seagate Technology Llc Categorizing bit errors of solid-state, non-volatile memory
US8737133B2 (en) 2011-10-18 2014-05-27 Seagate Technology Llc Shifting cell voltage based on grouping of solid-state, non-volatile memory cells
US8760932B2 (en) 2011-10-18 2014-06-24 Seagate Technology Llc Determination of memory read reference and programming voltages
US9135109B2 (en) 2013-03-11 2015-09-15 Seagate Technology Llc Determination of optimum threshold voltage to read data values in memory cells
US9134918B2 (en) 2009-12-31 2015-09-15 Sandisk Technologies Inc. Physical compression of data with flat or systematic pattern
CN109643576A (zh) * 2016-09-29 2019-04-16 英特尔公司 用于管理非易失性存储器装置中的漂移的分界电压的确定

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101944793B1 (ko) 2012-09-04 2019-02-08 삼성전자주식회사 플래시 메모리를 포함하는 플래시 메모리 시스템 및 그것의 비정상 워드 라인 검출 방법
KR102636039B1 (ko) * 2016-05-12 2024-02-14 삼성전자주식회사 불휘발성 메모리 장치 및 그것의 읽기 방법 및 카피백 방법
KR102817223B1 (ko) * 2017-01-11 2025-06-05 에스케이하이닉스 주식회사 메모리장치의 에러정정장치 및 에러정정방법과, 에러정정장치를 포함하는 메모리 컨트롤러
US10635400B2 (en) * 2017-12-12 2020-04-28 Western Digital Technologies, Inc. Seed generation

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6279133B1 (en) * 1997-12-31 2001-08-21 Kawasaki Steel Corporation Method and apparatus for significantly improving the reliability of multilevel memory architecture
EP1130600A1 (fr) * 2000-03-01 2001-09-05 Hewlett-Packard Company, A Delaware Corporation Schéma de distribution de données pour mémoires à l'état solide
US20060129751A1 (en) * 1997-08-07 2006-06-15 Guterman Daniel C Novel multi-state memory
US20060181934A1 (en) * 2005-01-19 2006-08-17 Saifun Semiconductors, Ltd. Methods for preventing fixed pattern programming

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4993028A (en) 1988-09-07 1991-02-12 Thinking Machines Corporation Error detection and correction coding

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20060129751A1 (en) * 1997-08-07 2006-06-15 Guterman Daniel C Novel multi-state memory
US6279133B1 (en) * 1997-12-31 2001-08-21 Kawasaki Steel Corporation Method and apparatus for significantly improving the reliability of multilevel memory architecture
EP1130600A1 (fr) * 2000-03-01 2001-09-05 Hewlett-Packard Company, A Delaware Corporation Schéma de distribution de données pour mémoires à l'état solide
US20060181934A1 (en) * 2005-01-19 2006-08-17 Saifun Semiconductors, Ltd. Methods for preventing fixed pattern programming

Cited By (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2226810A1 (fr) * 2009-03-04 2010-09-08 Apple Inc. Blanchiment de données pour l'écriture et la lecture de données depuis/vers une mémoire non volatile
US8589700B2 (en) 2009-03-04 2013-11-19 Apple Inc. Data whitening for writing and reading data to and from a non-volatile memory
US8918655B2 (en) 2009-03-04 2014-12-23 Apple Inc. Data whitening for writing and reading data to and from a non-volatile memory
US9134918B2 (en) 2009-12-31 2015-09-15 Sandisk Technologies Inc. Physical compression of data with flat or systematic pattern
US8693257B2 (en) 2011-10-18 2014-04-08 Seagate Technology Llc Determining optimal read reference and programming voltages for non-volatile memory using mutual information
US8711619B2 (en) 2011-10-18 2014-04-29 Seagate Technology Llc Categorizing bit errors of solid-state, non-volatile memory
US8737133B2 (en) 2011-10-18 2014-05-27 Seagate Technology Llc Shifting cell voltage based on grouping of solid-state, non-volatile memory cells
US8760932B2 (en) 2011-10-18 2014-06-24 Seagate Technology Llc Determination of memory read reference and programming voltages
US9042169B2 (en) 2011-10-18 2015-05-26 Seagate Technology Llc Shifting cell voltage based on grouping of solid-state, non-volatile memory cells
US9135109B2 (en) 2013-03-11 2015-09-15 Seagate Technology Llc Determination of optimum threshold voltage to read data values in memory cells
CN109643576A (zh) * 2016-09-29 2019-04-16 英特尔公司 用于管理非易失性存储器装置中的漂移的分界电压的确定

Also Published As

Publication number Publication date
WO2008078314B1 (fr) 2008-08-14
KR20090108586A (ko) 2009-10-15
KR101449673B1 (ko) 2014-10-13

Similar Documents

Publication Publication Date Title
US8370561B2 (en) Randomizing for suppressing errors in a flash memory
US8127200B2 (en) Flash memory device and system with randomizing for suppressing errors
WO2008078314A1 (fr) Dispositif, système et procédé de mémoire flash avec répartition aléatoire pour supprimer une erreur
US7984360B2 (en) Avoiding errors in a flash memory by using substitution transformations
USRE45697E1 (en) System, method and memory device providing data scrambling compatible with on-chip copy operation
KR101482242B1 (ko) 플래쉬 메모리에 액세스하는 방법 및 연관된 플래쉬 메모리 제어기
KR101563647B1 (ko) 메모리 시스템 및 그것의 데이터 처리 방법
US8451658B2 (en) Method for page- and block based scrambling in non-volatile memory
US8429330B2 (en) Method for scrambling data in which scrambling data and scrambled data are stored in corresponding non-volatile memory locations
USRE45515E1 (en) Built in on-chip data scrambler for non-volatile memory
US7716415B2 (en) Method of avoiding errors in flash memory
US7706181B2 (en) Multi-bit programming device and method using single-bit memory cells
US10417122B2 (en) Data randomization using memory block access counts
CN1437721A (zh) 多数据区段同时编程和在其它指定块中存储物理块特征的闪速eeprom系统
KR101731408B1 (ko) 플래시 메모리에 데이터를 기록하는 방법 및 관련 메모리 장치 및 플래시 메모리
TW201314447A (zh) 具改善資料擾碼之非揮發性記憶體及方法
CN115527587A (zh) 存储系统及其操作方法、存储器控制器和存储器

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 200780045693.4

Country of ref document: CN

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 07827479

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 1020097009421

Country of ref document: KR

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 07827479

Country of ref document: EP

Kind code of ref document: A1