News Column

Patent Issued for Apparatus and Method for Enhancing Flash Endurance by Encoding Data

July 3, 2014



By a News Reporter-Staff News Editor at Computer Weekly News -- From Alexandria, Virginia, VerticalNews journalists report that a patent by the inventors Sharon, Eran (Rishon Lezion, IL); Litsyn, Simon (Giv'at Shmuel, IL); Alrod, Idan (Herzliya, IL), filed on February 11, 2010, was published online on June 17, 2014.

The patent's assignee for patent number 8756365 is Ramot at Tel Aviv University Ltd. (Tel Aviv, IL).

News editors obtained the following quote from the background information supplied by the inventors: "The present invention relates to the storage of data in memory devices such as flash memory devices.

"A Discussion of Flash Memory Device Architecture

"FIG. 1A is a block diagram of a flash memory storage device 260 (prior art). The flash memory storage device includes a flash memory 270 and a flash controller 280 operative to read data and to write data to the flash memory 270. The terms 'program', 'programming', 'programmed', and 'programmable' are used herein interchangeably with the terms 'write', 'writing', 'written', and 'writable', respectively, to denote the storing of data in a flash memory.

"One example of a flash memory storage device is a 'peripheral flash storage device.' Peripheral flash storage devices are well-known in the art of computing, in form factors such as USB flash drives (UFD); PC-cards; and small storage cards used with digital cameras, music players, handheld and palmtop computers, and cellular telephones.

"FIG. 1B is a block diagram of a peripheral flash memory storage device 260* (the asterisk indicates that the flash memory storage device is a peripheral flash storage device) that is 'coupled with' or configured to exchange data with a host device 310 (for example, a laptop or desktop or handheld computers, digital camera, mobile telephone, music player, and video game consoles) via device-side interface 250. Peripheral flash memory storage device 260* and host device 310 communicate with each other via communications link 300 using host-side interface 350 and device-side interface 250 (for example, respective USB or SD interfaces).

"In one example, flash memory storage device 260* provides data-reading and data-writing services to host device 310. Data received by flash memory storage device 260* from host device 310 is written to flash memory 270 by flash controller 280. Furthermore, in response to 'data read' requests received by flash memory storage, flash controller 280 reads data from flash memory 270.

"Errors may be corrected in the read data at 'read time' or at any later time. The error-correction may be carried out at least in part by flash controller 280, at least in part by host device 310 (for example, by execution of executable code 340 in RAM 330 by host-side processor 320 or in any other manner), and any other location and in any other manner.

"The skilled artisan will appreciate that 'peripheral flash storage devices' are not the only class of flash memory storage devices. For example, certain mobile phones, desktop or laptop computers, PDA devices or other electronic devices may also include flash memory and a flash controller, and may not necessarily be configured to couple with a host device and/or provide data reading services and/or data writing service for a host device.

"The skilled artisan will appreciate that the flash memory devices described in FIGS. 1A-1B are just one class of peripheral storage memory device, and other memory devices may include other types of volatile memory, such as magnetic memory (for example, magnetoresistive random-access memory (MRAM) or hard disk platters). Furthermore, it is appreciated that the some peripheral storage devices may use volatile memory instead of, or in addition to, flash memory 270.

"Flash Memory Endurance

"Flash memories have limited endurance to Write/Erase (W/E) cycles. As the number of W/E cycles performed in the Flash increases, the probability of failures increases. These failures are usually related to wearing of the oxide insulation layer due to electrons passing through it during W/E cycles and generating electron trap sites. The failures can be manifested in several ways; such has failure to erase or program a block, or reduced data retention ability of the cells after they exhibited cycling.

"In new Flash fabrication processes, as the cell dimensions shrink, the W/E cycling endurance is expected to reduce and become a limiting factor that may affect the commercial viability of the flash memory.

"SLC and MLC Flash

"Two common forms of non-volatile memory exist. One form is 'binary' memory (in the case of flash, single level flash cells or 'SLC') in which data is represented as one single binary bit per memory cell, the bit normally representing a binary '1' or '0'.

"Another form is multi-level cell (MLC) memory in which one cell is used to store more than one binary bit.

"Binary memory cells store charge on a floating gate of a floating gate transistor where different charge distributions (or, equivalently, different threshold voltage distributions) correspond to the two different stored bit configurations. FIG. 1C. is a charge plot illustrating charge distributions for the two states of such a binary non-volatile (`NVM`) cell. These two configurations or states are illustrated as a '1' (erased) and a '0' (programmed). Note that this is only a convention and a '1' could instead represent a programmed bit and a '0' could likewise represent an erased bit. Accordingly, the 1=erased, 0=programmed convention will be used herein throughout. These two states are the two possible 'cell states' of a SLC cell.

"MLC memory cells likewise store charge on a floating gate of a floating gate transistor where different charge distributions correspond to different stored bit configurations. For example, in a two-level MLC Flash memory two bits are stored in the cell and the two bits are referred to as an upper page bit (upage) and a lower page bit (lpage). Four charge distributions (or, equivalently, four threshold voltage distributions) represent the four possible states of the upper and lower page bits. FIG. 1D is a charge plot illustrating charge distributions for the various states of a 2-bit MLC NVM cell. In FIG. 1D, the four charge distributions are illustrated as a '11', '10', '00' and '01'. The '11' state is called the 'erased' state. The remaining states are 'programmed' states. All four states collectively are the 'cell states' of a 2-bit MLC cell. (As discussed above with respect to binary memories, this is only a convention. If desired, the bit to state mapping may be interchanged).

"Initially the cell is in the erased state. When the bits are programmed, the distribution is moved from the erased state on the left of FIGS. 1C and 1D to a programmed state on the right. Physically this corresponds to charge being stored on the floating gate. This is normally accomplished using a hot electron injection mechanism or a tunneling mechanism to force channel electrons across an, insulator onto the floating gate. Cell erasure is normally achieved through a tunneling mechanism to remove electrons from the floating gate. The transition of a cell from the erased state to a programmed state and back to the erased state is called a 'write/erase cycle'. Each write/erase cycle causes 'wear' on the cell and once a cell has accumulated enough wear, it may experience a failure mode. A cell already in the erased state experiences little or no wear when repeatedly erased.

"From another point of view, FIGS. 1C and 1D illustrate two different mappings of bit patterns to cell states. The mapping in FIG. 1C is

"TABLE-US-00001 BIT PATTERN CELL STATE 1 1 0 2

"The mapping in FIG. 1D is

"TABLE-US-00002 BIT PATTERN CELL STATE 11 1 10 2 00 3 01 4

"In flash memories, higher cell states correspond to higher threshold voltages.

"It would be desirable to further improve the longevity and reliability of SLC and/or MLC memory cells."

As a supplement to the background information on this patent, VerticalNews correspondents also obtained the inventors' summary information for this patent: "One embodiment provided herein is a method of storing a first plurality of input bits in a plurality of memory cells, including: (a) providing a first mapping of bit patterns to cell states of the memory cells; (b) mapping the first plurality of input bits to a first plurality of transformed bits that is larger in number than the first plurality of input bits, using a first shaping encoding that has a downward asymptotic bias with respect to the first mapping of bit patterns to cell states; programming at least a portion of the first sub-plurality of the memory cells to store the first plurality of transformed bits according to the first mapping of bit patterns to cell states; and (d) erasing the at least portion of the first sub-plurality of the memory cells before programming the at least portion of the first sub-plurality of the memory cells to store any other bits.

"Another embodiment provided herein is a memory controller, for a memory that includes a plurality of memory cells, that is operative: (a) to provide a mapping of bit patterns to cell states of the memory cells; (b) to store a plurality of bits in the memory cells, by: (i) mapping the plurality of input bits to a plurality of transformed bits that is larger in number than the plurality of input bits, using a shaping encoding that has a downward asymptotic bias with respect to the mapping of bit patterns to cell states, and (ii) programming at least a portion of the memory cells to store the plurality of transformed bits according to the mapping of bit patterns to cell states; and to erase the at least portion of the plurality of memory cells before programming the at least portion of the plurality of memory cells to store any other bits.

"Another embodiment provided herein is a system for storing a plurality of input bits, including: (a) a first memory including a plurality of memory cells; and (b) a host, of the first memory, including: (i) a second memory for storing code for managing the first memory by: (A) providing a mapping of bit patterns to cell states of the memory cells, (B) mapping the plurality of input bits to a plurality of transformed bits that is larger in number than the plurality of input bits, using a shaping encoding that has a downward asymptotic bias with respect to the mapping of bit patterns to cell states, (C) programming at least a portion of the memory cells to store the transformed bits according to the mapping of bit patterns to cell states, and (D) erasing the at least portion of the plurality of memory cells before programming the at least portion of memory cells to store any other bits, and (ii) a processor for executing the code.

"Another embodiment provided herein is a computer-readable storage medium having embedded thereon computer-readable code for storing a plurality of input bits in a memory that includes plurality of memory cells, the computer-readable code including: (a) program code for mapping the plurality of input bits to a plurality of transformed bits that is larger in number than the plurality of input bits, using a shaping encoding that has a downward asymptotic bias with respect to a mapping of bit patterns to cell states; (b) program code for programming at least a portion of the memory cells to store the transformed bits according to the mapping of bit patterns to cell states; and program code for erasing the at least portion of the plurality of memory cells before programming the at least portion of memory cells to store any other bits.

"According to a basic method of storing a first plurality of input bits in a plurality of memory cells, a first mapping of bit patterns to cell states of the memory cells is provided. A first shaping encoding is used to map the first plurality of input bits to a first plurality of transformed bits that is larger than the first plurality of input bits. The first shaping encoding has a downward asymptotic bias with respect to the first mapping of bit patterns to cell states. At least a portion of the first sub-plurality of the memory cells is programmed to store the first plurality of transformed bits according to the first mapping of bit patterns to cell states. The at least portion of the first sub-plurality of memory cells is erased before the at least portion of the first sub-plurality of memory cells is again programmed to store any other bits.

"Note that it is not necessary for all possible input bit pluralities to be mapped to larger transformed bit pluralities by the first shaping encoding, as long as the first shaping encoding is such that at least some input bit pluralities are mapped to larger transformed bit pluralities.

"Preferably, the first shaping encoding has a downward asymptotic bias towards a lower half of the cell states.

"Preferably, the first shaping encoding is non-linear, for example a variable length encoding, or a reverse enumerative source encoding. Alternatively, the first shaping encoding is a trellis shaping encoding. Most preferably, if the first shaping encoding is a variable length encoding then the first shaping encoding is a prefix encoding such as a reverse Huffman encoding.

"Preferably, before the first plurality of input bits is mapped to the first plurality of transformed bits, a maximum number of the memory cells of the first sub-plurality needed to store the first plurality of transformed bits is estimated, and that number of memory cells of the first sub-plurality is reserved for storing the first plurality of transformed bits. If it turns out that the estimated maximum number of the memory cells is too low, then either the first plurality of input bits itself, rather than the first plurality of transformed bits, is stored in at least a portion of the first sub-plurality of memory cells, or the first plurality of input bits is scrambled to provide a plurality of scrambled bits. In the latter case, the scrambling is followed by using the first shaping encoding to map the scrambled bits to a plurality of transformed scrambled bits.

"Preferably, the first shaping encoding is selected in accordance with a desired shaping scheme of the first sub-plurality of the memory cells. Note that different shaping schemes may have the same downward bias.

"Preferably, a second mapping of bit patterns to cell states of the memory cells is provided. A second shaping encoding that is different from the first shaping encoding is used to map a second plurality of input bits to a second plurality of transformed bits. Note that the second shaping encoding could be an identity mapping, in which case the second plurality of transformed bits is identical to the second plurality of input bits. At least a portion of a second sub-plurality of the memory cells is programmed to store the second plurality of transformed bits according to the second mapping of bit patterns to cell states. The first and second mappings of bit patterns to cell states may be either identical or different. For example, if the first mapping of bit patterns to cell states is used for caching input data that later will be copied to long-term storage then the two mappings normally are different.

"Usually, the second shaping encoding has a downward asymptotic bias with respect to the cell states of the second mapping of bit patterns to cell states.

"Most preferably, the first and second shaping encodings are selected in accordance with respective properties of the first and second sub-pluralities of the memory cells. Exemplary respective properties include respective numbers of programming cycles endured by the first and second sub-pluralities of the memory cells.

"Preferably, the method also includes reading at least a portion of the first sub-plurality of memory cells, thereby obtaining a recovered first plurality of transformed bits. The recovered first plurality of transformed bits is decoded relative to the first shaping encoding, whereby a recovered first plurality of input bits is obtained. At least a portion of a second sub-plurality of the memory cells then is programmed to store the recovered first plurality of input bits.

"More preferably, the method also includes systematic error-correction-encoding of the first plurality of transformed bits, thereby providing one or more redundancy bits. At least a portion of a second sub-plurality of the memory cells is programmed to store the redundancy bit(s). Then, most preferably, the at least portion of the first sub-plurality of the memory cells is read, whereby a recovered first plurality of transformed bits is obtained, and the at least portion of the second sub-plurality of the memory cells is read, whereby one or more recovered redundancy bits is/are obtained. The recovered first plurality of transformed bits is systematic error-correction-decoded according to the recovered redundancy bit(s). The systematic error-correction-decoding is based at least in part on the first shaping encoding.

"Alternatively, the first shaping encoding includes non-systematic error-correction-encoding. Then, most preferably, the at least portion of the first sub-plurality of the memory cells is read, whereby a recovered first plurality of transformed bits is obtained. The recovered first plurality of transformed bits is non-systematic error-correction-decoded relative to the first shaping encoding.

"Preferably, the number of transformed bits is at most about 1.29 times the number of input bits.

"Preferably, the downward asymptotic bias exceeds 75%.

"The scope of the appended claims includes a memory controller that uses the basic method to control a memory that includes a plurality of memory cells, and a memory device that includes such a controller and such a memory.

"The scope of the appended claims also includes a system for storing a plurality of bits. The system includes a first memory that includes a plurality of memory cells and a host of the first memory. The host includes a second memory for storing code for implementing the basic method and a processor for executing the code. The scope of the appended claims also includes a computer-readable storage medium having embedded thereon computer-readable code for implementing the basic invention."

For additional information on this patent, see: Sharon, Eran; Litsyn, Simon; Alrod, Idan. Apparatus and Method for Enhancing Flash Endurance by Encoding Data. U.S. Patent Number 8756365, filed February 11, 2010, and published online on June 17, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.htm&r=1&f=G&l=50&s1=8756365.PN.&OS=PN/8756365RS=PN/8756365

Keywords for this news article include: Ramot at Tel Aviv University Ltd.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Computer Weekly News


Story Tools






HispanicBusiness.com Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters