Patent Publication Number: US-8527840-B2

Title: System and method for restoring damaged data programmed on a flash device

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of U.S. Provisional Patent Application Ser. No. 61/321,310, filed on Apr. 6, 2010, which is incorporated in its entirety by reference herein. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates generally to systems and methods of retrieving data from a Flash memory, and in particular, to systems and methods of retrieving damaged data from a Flash memory. 
     BACKGROUND OF THE INVENTION 
     A storage device such as a flash memory module stores encoded data. The encoded data is expected to be decoded by a memory controller. The memory controller is expected to successfully decode the encoded data during the lifespan of the flash memory module. A failure of the memory controller to decode encoded data, for example, when the amount of errors in a memory are beyond the ability of the controller to correct, renders the encoded data invalid, and the controller responds to a retrieval request with an error message. Such a failure may occur, for example, when the flash memory is exposed to high temperatures, or for other reasons. 
     Memory controllers are expected to be relatively cheap and are required to read and decode encoded information in real time. Accordingly, these requirements may impose a low sampling rate of the encoded data and a use of a decoding scheme that has limited error correction capabilities. Typically, memory controllers use “hard” decoding techniques, i.e., provide a definite determination of the data stored on each cell. However, such techniques may be insufficient to retrieve damaged data. 
     SUMMARY OF THE INVENTION 
     According to embodiments of the invention, a system and method are provided for restoring damaged data programmed on a memory. A system may include a memory controller associated with a memory, the memory controller adapted to perform a first decoding algorithm having a first error correction capability on a portion of encoded data stored on the memory, wherein in the event of a failure of the first decoding algorithm to decode the portion of encoded data, the memory controller is adapted to send a failure notification. The system may further include a recovery module associated with a processor, said recovery module being adapted to receive the failure notification, send a request for soft sampling of the portion of encoded data stored on the memory. The memory controller may be further adapted to receive the request for soft sampling of the portion of encoded data stored on the memory, perform the soft sampling of the portion of encoded data accordingly, and send the results of the soft sampling to the recovery module. The recovery module may be adapted to receive the results of the soft sampling and perform thereon a second decoding algorithm having a second error correction capability, wherein the second error correction capability exceeds the first error correction capability. 
     A method for restoring damaged data programmed on a memory according to embodiments of the invention may include receiving an indication from a memory controller associated with a memory that a first decoding algorithm having a first error correction capability has failed to decode a portion of encoded data stored on the memory, sending a request for soft sampling of the portion of encoded data stored on the memory, receiving the results of the soft sampling from the memory controller, and performing on the results of the soft sampling a second decoding algorithm having a second error correction capability, wherein the second error correction capability exceeds the first error correction capability. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The subject matter regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of operation, together with objects, features, and advantages thereof, may best be understood by reference to the following detailed description when read with the accompanying drawings in which: 
         FIG. 1  schematically illustrates a system according to an embodiment of the invention; 
         FIG. 2  is a flow diagram showing an example of a method performed by a storage device according to an embodiment of the invention; and 
         FIG. 3  is a flow diagram showing an example of a method performed by a recovery module according to an embodiment of the invention. 
     
    
    
     It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity. Further, where considered appropriate, reference numerals may be repeated among the figures to indicate corresponding or analogous elements. 
     DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION 
     In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the invention. However, it will be understood by those skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known methods, procedures, and components have not been described in detail so as not to obscure the present invention. 
     The subject matter regarded as the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of operation, together with objects, features, and advantages thereof, may best be understood by reference to the following detailed description when read with the accompanying drawings. 
     It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity. Further, where considered appropriate, reference numerals may be repeated among the figures to indicate corresponding or analogous elements. 
     Embodiments of the invention may be applicable to various types of memory, including, for example, Secure Digital (SD) cards, solid-state drive (SSD) devices, as well as to other storage devices as hard-drives, optical media, magnetic tapes, etc. 
       FIG. 1  schematically illustrates system  100  according to an embodiment of the invention. 
     System  100  includes a storage device  110  (such as but not limited to an SD card) that includes a memory controller  111  and memory  112  and a computer  120 . Memory  112  can be a flash memory module or other non-volatile memory module, and may include multiple memory blocks, each including multiple memory pages. Different memory pages may share physical memory rows. 
     Computer  120  may be connected to storage device  20  (and more specifically, to memory controller  111 ) through a wired or wireless link, over a network, or any other communication link. Computer  120  can be a remote server, a desktop computer, a laptop computer, a personal digital assistant (PDA), a tablet computer, and the like. 
     Although in the illustrated embodiment, computer  120  is depicted as being connected to the memory controller  111  via a wired link  130 , it will be understood that computer  120  can be connected to memory controller  111  via one or more wireless links, or a combination of wired and wireless links. Computer  120  can be communicatively connected to memory controller  111  directly, or via a network, etc. 
     In some embodiments of the invention, memory controller  111  may be a small and inexpensive processor, and may have limited computing power, and therefore, limited decoding abilities. According to a mode of operation of embodiments of the invention, memory controller  111  may attempt to retrieve encoded data stored on memory  112 , for example, a codeword, a portion of a codeword, or more than a single codeword. Memory controller  111  may first apply a first decoding algorithm that has a certain error correction capability, for example, a hard decoding algorithm. If memory controller  111  fails to successfully decode data stored on memory  112 , it may determine that the data is damaged and enter a damaged data restoration mode. 
     In some embodiments of the invention, a data decoding failure event may be detected by the memory controller  111 . For example, memory controller  111  may determines that it failed to successfully decode the encoded data if, for example, it detects that a number of errors in the encoded data exceeds the number of errors that can be amended by the memory controller  111 . It will be understood that in some embodiments, the failure to decode encoded data may be detected by an application or a process that uses the decoded data, for example, an application or process executed by or on computer  120 . For example, a decoding failure event may be detected by the application or process if the content of the decoded data differs from an expected content. 
     An indication of failure to successfully decode data encoded and stored on memory  112  may be generated, for example, by memory controller  111 . A failure event indication may be sent to computer  120  which may respond by initiating a data restoration or recovery process. 
     Computer  120  may include interface  122 , and a recovery module  121 . It will be recognized that according to embodiments of the invention, the recovery module differs from the memory controller, for example, it may be part of a computer having more processing power than the memory controller. The recovery module  121  may include hardware, software and a combination thereof. Recovery module  121  may instruct memory controller  111  to operate in a data restoration mode. In this mode, the memory controller  111  may sample or retrieve the raw or (“hard”) encoded data (e.g., voltage levels, etc.), and provide a representation of the encoded data in soft format to computer  120 . 
     In some embodiments of the invention, the memory controller  111  may first provide certain physical memory information to controller  120 . For example, the physical memory information may include one or all of: an identity of a page storing the encoded data, an identity of the memory block storing the encoded data, an identity of a die storing the encoded data, a cycle count of the memory block storing the encoded data, an indication about an existence of an old version of the encoded data on storage device  112 , one or more coding parameters of the encoded data, scrambling information of the encoded data, and the like. 
     Computer  120  may instruct the memory controller  111  to sample and retrieve the encoded data stored in storage device  112 . The sampling may involve obtaining the encoded data at a fine resolution using, for example, majority sampling. Thus, for a given voltage threshold value, the memory controller  111  can sample the encoded data multiple (k) times to provide multiple sets of k samples and then process each set of k samples to provide a soft sample. For example, the memory controller  111  can process each set of k samples by selecting a median value of the set. In some embodiments of the invention, computer  120  may determine the sampling resolution to be used and communicate the sampling parameters to memory controller  111 . This determination may be responsive to the encoded data physical information provided by memory controller  111 . 
     Upon obtaining and/or processing the soft samples, memory controller  111  may send the soft samples to computer  120 , for example, by way of interface  122 . Computer  120  may decode the soft samples of the encoded data, for example, by applying a second decoding algorithm having a higher or better error correction capability than the error correction capability of the first decoding algorithm applied by the memory controller  111 . In some embodiments of the invention, the second decoding algorithm may be a soft decoding algorithm. For example, the soft decoding algorithm applied as the second decoding algorithm may be a soft version of the first decoding algorithm, or it may be another soft decoding algorithm. In some embodiments of the invention, the second decoding algorithm may be a hard decoding algorithm having better error correction capability than the first decoding algorithm. 
     According to some embodiments of the invention, the determination of the parameters of the second decoding algorithm may be responsive to one or more of the following: (i) threshold values shift along a memory block that stores the encoded data; (ii) decoded bits stored in another memory page of the storage device, wherein the other memory page and the memory page that stores the encoded data share memory rows; this can include decoded bits that belong to another logical layer such as most significant bit, least significant bit and CSB; (iii) soft samples obtained while supplying different bias voltage to the memory page that stores the encoded data; and (iv) an old version of the encoded data that may be stored in another memory page. 
     According to some embodiments, second decoding algorithm may be very involved or time-consuming Accordingly, computer  120  may apply the second decoding algorithm over long periods of time (in comparison to the decoding period of the memory controller  111 ) and by using stronger computational resources. Increased decoding time and/or computational resources may increase the probability of successful decoding using the second decoding algorithm by computer  120 . According to some embodiments of the invention, by applying the second decoding algorithm, the reliability of the storage device may increase by an order of magnitude. For example, the raw Bit Error Rate can be increased by tenfold (i.e., the SNR gain may be 1-3 dB). See, e.g., R. Kotter and A. Vardy, “Algebraic soft decision decoding of Reed-Solomon codes”,  IEEE Trans. Inform. Theory , vol 49, No. 11, pp. 2809-2825, November 2003 (demonstrating performance differences between hard and soft decoding using Kotter-Vardy algorithm). 
       FIG. 2  is a flow diagram showing an example of a method  200  performed by a storage device according to an embodiment of the invention. 
     At stage  210 , storage device may attempt to decode encoded data stored in a memory, for example, by operating a memory controller employing a first decode algorithm, for example, a “hard” decoding algorithm. At stage  220 , a failure of the first decoding algorithm may be detected, for example, by the memory controller, or by an application operating on a computer requesting data from the storage device. 
     At stage  230 , a failure indication may be sent, for example, to a recovery module on a computer. 
     In some embodiments of the invention, after stage  230 , the method may proceed to stage  240  or bypass stages  240 - 260  and proceed directly to stage  270 . At stage  240 , the storage device may receive a request, for example, from the recovery module, requesting certain physical information pertaining to the encoded data that could not be recovered. The encoded data physical information may include one or more of: (i) a cycle count of a memory block that stores the encoded data, (ii) coding parameters of the memory block that stores the encoded data, (iii) scrambling information of the encoded data, (iv) an identifier of the memory block that stores the encoded data, and (v) an existence of a older version of the encoded data in the storage device. At stage  250 , the memory controller may obtain the requested physical information, and at stage  260 , it may send the requested information to the recovery module. 
     At stage  270 , the memory controller may receive parameters for performing soft sampling of the encoded data. If stages  240 - 260  were bypassed, the recovery module may determine the soft sampling parameters based on preset values. In other instances, the recovery module may use the physical information to determine the soft sampling parameters to be used by memory controller in performing the soft sampling. 
     The soft sampling parameters or instructions may include any of a variety of different parameters or instructions. For example, in some embodiments, the memory controller may be instructed to sample each bit of the encoded data multiple times to provide a set of samples and to process the set of samples to provide the soft samples of the encoded data. In some embodiments, the memory controller may be instructed to sample each bit of the encoded data multiple times to provide a set of samples and to return as a soft sample of the bit of the encoded data a median value of the set of samples. In some embodiments, the memory controller may be instructed to generate soft samples of the encoded data and to generate soft samples of at least one additional encoded data stored at the storage device. In some embodiments, the memory controller may be instructed to generate a first set of soft samples of the encoded data that is generated by performing a read process that involves providing a first bias voltage and to generate a second set of soft samples of the encoded data that is generated by performing a read process that involves providing a second bias voltage that differs from the first bias voltage. 
     At stage  280 , the memory controller may perform soft sampling of the encoded data. If stages  230 - 270  were bypassed, the memory controller may use preset parameters to perform the soft sampling. In other embodiments, the memory controller may use the soft sampling parameters communicated to it by the recovery module at stage  270 . 
     The soft sampling may be performed in any of a variety of different methods. In some embodiments of the invention, each bit of the encoded data may be sampled multiple times to provide a set of samples and to process the set of samples to provide the soft samples of the encoded data. In some embodiments, each bit of the encoded data may be sampled multiple times to provide a set of samples and to return as a soft sample of the bit of the encoded data a median value of the set of samples. Some embodiments of the invention may include generating soft samples of the encoded data and generating soft samples of at least one additional encoded data stored at the storage device. Some embodiments of the invention may include generating a first set of soft samples of the encoded data that is generated by performing a read process that involves providing a first bias voltage and generating a second set of soft samples of the encoded data that is generated by performing a read process that involves providing a second bias voltage that differs from the first bias voltage. The generating is not limited to two sets of soft samples that are generated by providing two different bias voltages and more that a pair of sets can be generated by providing more than a pair of bias voltages. 
     At stage  290 , the soft samples may be sent to the recovery module for decoding using a second decoding algorithm. According to embodiments of the invention, and as described in connection with the method performed by the recovery module, if a second decoding algorithm performed by the recovery module was unsuccessful, the memory controller may be provided with additional or different soft sampling parameters or instructions, and accordingly, may repeat at least one of stages  270 - 290 . 
       FIG. 3  is a flow diagram showing an example of a method  300  performed by a recovery module according to an embodiment of the invention. 
     At stage  310 , the recovery module may receive an indication of failure of a first decoding algorithm (e.g., sent at stage  230 ). In some embodiments of the invention, the method may bypass stages  320 - 330  or  320 - 340  and proceed to stage  350  (described below). At stage  320 , the recovery module may request certain physical information pertaining to the encoded data to be recovered. At stage  330 , the requested information may be received. At stage  340 , the recovery module may determine, for example, based on information obtained at stage  330 , or based on preset defaults, the soft sampling recovery scheme to be performed, and the parameters required for the memory controller to perform the required sampling. 
     At stage  350 , the recovery module may instruct the memory controller to perform soft sampling of the encoded data to provide soft samples of the encoded data. If stage  340  was performed, the instruction may include parameters obtained at stage  340 . 
     At stage  360 , the requested soft sampling data may be obtained from the memory controller. 
     At stage  370  the recovery module may apply a second (“soft”) decoding algorithm on the soft samples of the encoded data provided, in order to provide restored data. The second decoding algorithm may have an error correction capability that exceeds an error correction capability of the first decoding algorithm. The second decoding algorithm can be a soft version of the first decoding algorithm. Soft sampling of data can reduce the error probability of a given code that uses the soft sampled data. Moreover, substantially all commonly used codes (e.g., RS/BCH codes, LDPC codes, Turbo codes, etc.) have feasible soft-decoding algorithms that use soft data sampling to reduce the error probability, as illustrated by: (i) R. Kotter and A. Vardy, “Algebraic soft decision decoding of Reed-Solomon codes,”  IEEE Trans. Inform. Theory , vol 49, No. 11, pp. 2809-2825, November 2003; (ii) M. Fossorier, M Mihaljevi&#39;c, and H. Imai, “Reduced Complexity Iterative Decoding of Low-Density Parity Check Codes Based on Belief Propagation,”  IEEE Trans. Comm ., vol. 47, No. 5, pp. 673-680, May 1999; and (iii) C. Berrou, and A. Glavieux, “Near optimum error correcting coding and decoding: turbo codes,” IEEE Trans. Comm vol. 44, No. 10, pp. 1261-1271, October 1996. 
     It will be understood that in some embodiments of the invention, the second decoding algorithm performed on the soft sampled data may be based on the encoded data physical information. For example, based on the additional physical information provided on a codeword that could not be “hard” decoded, the restoration algorithm can employ different strategies during its operation, e.g., (a) the amount of cycles the physical page experienced can suggest which programming parameters were used to program this page, what is the expected mean and STD (standard deviation) of each cell and other statistical parameters which are correlated to the cycling count of the block; (b) the coding parameters are needed when the correct decoding scheme is activated (some controllers can change the encoder&#39;s parameters based on bit type value, cycle count and other physical parameters); (c) the scrambling parameters are needed to produce the correct data. Usually, the data is scrambled just before the encoding phase. In order to produce the original data de-scrambling is done just after the decoding phase therefore the restoration process might need the scrambling parameters; and (d) the exact location of the pages within the block can suggest what were the drifts (shifts) in threshold values along the block were, which in turn can improve the estimation of the optimal thresholds needed to read the page. Moreover, using decoupling techniques one can read adjacent rows and use that information to reduce the coupling effect imposed on the erroneous page/s. 
     The second decoding algorithm may be applied based on the provided information. For example, reading and decoding other page data in the same physical row (e.g., different bit layers of the row) can help to identify programming errors (e.g., errors occurred when the upper bit layer is read erroneously as part of the programming process). In another example, older versions of the information can help to identify error bits. 
     At stage  380 , the recovery module determines whether the second decoding algorithm successfully decoded the sampled data. If so, the method may proceed to stage  390 . If not, the recovery module may determine that another attempt may be more successful, and may repeat some previous stages. For example, the recovery module may optionally repeat stage  340 , determining a different soft sampling recovery scheme to be performed, and the parameters required for the memory controller to perform the required sampling. These may be requested and received at repeated stages  350  and  360 , and another decoding process performed at stage  370 . A number of repetitions of stages  340 - 370  or  350 - 370  may be repeated until success is achieved, or until a stop condition is reached, e.g., maximum number of tries, etc. 
     Finally, at stage  390 , the data recovered by the second decoding algorithm may be used. For example, the data may be displayed, stored, transmitted, etc. 
     In some instances, after recovery of damaged data, use of the card may continue. For example, the memory controller may declare that the block where the first decoding algorithm failed is a bad block, and continue working with the card while refraining from using that block. In another instance, the recovery process may result in a recommendation to stop using the storage device altogether, for example, due to its excessively high bit-error-rate. 
     While certain features of the invention have been illustrated and described herein, many modifications, substitutions, changes, and equivalents will now occur to those of ordinary skill in the art. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the invention.