Abstract:
A uniform coding system for a flash memory is disclosed. A statistic decision unit determines a coding word according to a plurality of inputs. An inverse unit controllably inverts input data to be encoded. The input data are then encoded into encoded data according to a statistic determined by the statistic decision unit.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention generally relates to a flash memory, and more particularly to uniform coding for a multi-level cell (MLC) flash memory. 
     2. Description of the Prior Art 
     Flash memory is a non-volatile solid state memory device that can be electrically erased and reprogrammed, and is a specific type of electrically erasable programmable read-only memory (EEPROM) device. Conventional flash memory stores a single bit of information in each memory cell such that each memory cell can be programmed to assume two possible states. The conventional flash memory is thus commonly referred to as single-level cell (SLC) flash memory or single-bit cell (SBC) flash memory. Modern flash memory is capable of storing two or more bits of information in each memory cell such that each memory cell can be programmed to assume more than two possible states. The modern flash memory is thus commonly referred to as multi-level cell (MLC) flash memory or multi-bit cell (MBC) flash memory. 
     In the flash memory, data of different state are written to the flash memory (which is commonly referred as programming the flash memory) by storing different amount of charge in the floating gate of the flash memory. As the charge in the floating gate specifically determines the corresponding threshold voltage, the data can then be read from the flash memory according to their different threshold voltage. Due to variations among the memory cells during the manufacture, operation or according to other factors, the threshold voltage of each state is not a constant value but a range.  FIG. 1A  shows a common distribution of the threshold voltage for a typical MLC flash memory (a two-bit cell flash memory is exemplified here). The entire voltage range is divided into a number of regions (e.g., four regions in the example), each region corresponding to one state. The number of cells of each threshold voltage is collected as illustrated. When the flash memory is being read, the threshold voltage of a cell is compared to reference voltages or read thresholds (e.g., V 1 , V 2  and V 3  in the figure) to determine its state. Specifically, the threshold voltage is firstly compared with a low-byte read threshold (e.g., V 2  in the exemplary figure), followed by subsequently comparing with high-byte read thresholds (e.g., V 1  and V 3  in the exemplary figure). 
     However, partial distribution of threshold voltages may become widened, such as the state (0,0) shown in  FIG. 1B , when the low-byte data and the high-byte data in the same word line have substantially the same value. As a result, the read margin decreases and error rate increases. 
     For the reason that conventional flash memory, particularly the MLC flash memory, could probably result in read errors due to widened distribution of threshold voltages of one or more states, a need has arisen to propose some novel schemes to cause the threshold voltages more uniformly distributed. 
     SUMMARY OF THE INVENTION 
     In view of the foregoing, it is an object of the embodiments to provide uniform coding for a flash memory in order to prevent threshold distribution widening due to non-uniform data stored in the flash memory. 
     According to a first embodiment, a data divider divides a data section of input data into multiple data parts. A statistic decision unit determines a coding word according to the data parts. The statistic decision unit performs following steps on the data parts: counting to derive a counted number of bits “ 0 ” or bits “ 1 ” in each of the data parts; determining deviations of the counted number and a predetermined mean for the data parts respectively; and determining one or more of the data parts that need be inverted such that a sum of the deviations approaches zero, wherein inversion and non-inversion of the data parts collectively generate the coding word. An inverse unit inverts bits of the data part or parts that need be inverted, while the other data part or parts remain unchanged, thereby resulting in encoded data. 
     According to a second embodiment, an inverse unit controllably inverts input data to be encoded, wherein the inverse unit subjects the input data to exclusive-OR logical operation with multiple candidate words (or pseudo random numbers) respectively, thereby resulting in a plurality of exclusive-ORed input data. A statistic decision unit determines a coding word according to the multiple exclusive-ORed input data. The statistic decision unit performs following steps: counting bits “ 0 ” and bits “ 1 ” for each of the exclusive-ORed input data; and selecting the candidate word corresponding to the exclusive-ORed input data having approximately equal bits “ 0 ” and bits “ 1 ” as the coding word, and the associated exclusive-ORed input data as encoded data. 
     According to a third embodiment, a statistic decision unit determines a coding word according to input data The statistic decision unit performs following steps on the input data: determining occurring probabilities of data code combinations respectively; ranking the probabilities; and assigning more uniform code word to the data code combination with higher probability, and assigning less uniform code word to the data code combination with less probability, wherein the data code combinations and the associated code words therefore result in a probability coding table. An inverse unit controllably inverts at least part of the input data according to the associated code word as the coding word, thereby resulting in the encoded data. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1A  shows a common distribution of the threshold voltage for a typical MLC flash memory; 
         FIG. 1B  shows a threshold distribution with a widened state; 
         FIG. 2  is a block diagram that illustrates a uniform coding system for a flash memory according to one embodiment of the present invention; 
         FIG. 3A  shows a detailed block diagram of the uniform encoder of  FIG. 2  according to a first embodiment of the present invention; 
         FIG. 3B  shows a detailed block diagram of the uniform decoder of  FIG. 2  according to the first embodiment of the present invention; 
         FIG. 4A  shows a detailed block diagram of the uniform encoder of  FIG. 2  according to a second embodiment of the present invention; 
         FIG. 4B  shows a detailed diagram of the uniform decoder of  FIG. 2  according to the second embodiment of the present invention; 
         FIG. 5  shows a detailed block diagram of the uniform encoder of  FIG. 2  according to an alternative second embodiment of the present invention; 
         FIG. 6A  shows a detailed block diagram of the uniform encoder of  FIG. 2  according to a third embodiment of the present invention; and 
         FIG. 6B  shows a detailed block diagram of the uniform decoder of  FIG. 2  according to the third embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       FIG. 2  is a block diagram that illustrates a uniform coding system for a flash memory  10  according to one embodiment of the present invention. Although a multi-level cell (MLC) flash memory is illustrated in the embodiment, the present embodiment, however, may be adapted to a single-level cell (SLC) flash memory as well. It is appreciated that each block of the uniform coding system in the embodiment may be implemented by hardware such as circuitry or by software or their combination. 
     In the embodiment, before data are written (or programmed) to the flash memory  10 , the data are uniformly encoded by a uniform encoder  12  such that the bits “ 0 ” and “ 1 ” of the encoded data may be uniformly distributed accordingly. In other words, the number of bits “ 0 ” in a page or a word line, for example, may be substantially equal to the number of bits “ 1 ” in the same page or word line. Furthermore, the bits “ 0 ” may be evenly scattered in the page or word line, and the bits “ 1 ” may be evenly scattered in the same page or word line. With respect to, for example, a 2-bit MLC flash memory, low-byte data (i.e., the data firstly programmed into the 2-bit MLC flash memory  10 ) as well as high-byte data (i.e., the data secondly or subsequently programmed into the 2-bit MLC flash memory  10 ) may be uniformly encoded by the uniform encoder  12 . When the (encoded) data are read from the flash memory  10 , the (encoded) data are uniformly decoded by a uniform decoder  14  that applies an inverse of the encoding operation performed in the uniform encoder  12 , such that the original data may be faithfully recovered. 
       FIG. 3A  shows a detailed block diagram of the uniform encoder  12  of  FIG. 2  according to a first embodiment of the present invention. In the embodiment, the uniform encoder  12  primarily includes a statistic decision unit  120  and an inverse unit  122 . Before the data are forwarded to the statistic decision unit  120 , the data are divided, by a data divider  124 , into multiple parts (e.g., part 1 to part 8) that are preferably equal or approximately equal in size. Table 1 shows one exemplary 512-byte section of low-byte data that is divided into eight parts each having 512 bits in size. It is appreciated that the size of the data section and the number of the data parts shown here are for illustration purpose only. Generally speaking, smaller size of the data section or/and larger number of the data parts leads to more uniformity in the coding. 
     
       
         
               
               
               
               
               
               
               
               
               
             
               
               
             
               
               
               
               
               
               
               
               
               
             
               
               
             
               
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 part 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
               
               
                   
               
             
             
               
                 size 
                 512 
                 512 
                 512 
                 512 
                 512 
                 512 
                 512 
                 512 
               
               
                   
                 bits 
                 bits 
                 bits 
                 bits 
                 bits 
                 bits 
                 bits 
                 bits 
               
               
                 count of 
                 270 
                 265 
                 253 
                 261 
                 266 
                 259 
                 247 
                 275 
               
               
                 “0” 
                   
                   
                   
                   
                   
                   
                   
                   
               
               
                 deviation 
                 14 
                 9 
                 −3 
                 5 
                 10 
                 3 
                 −9 
                 19 
               
               
                 (i.e., 
                   
                   
                   
                   
                   
                   
                   
                   
               
               
                 count-256) 
                   
                   
                   
                   
                   
                   
                   
                   
               
             
          
           
               
                 sum of 
                 48 
               
               
                 deviations 
                   
               
             
          
           
               
                 deviation 
                 
                           
                 
                 9 
                 −3 
                 5 
                 
                           
                 
                 3 
                 −9 
                 19 
               
               
                 after 
                   
                   
                   
                   
                   
                   
                   
                   
               
               
                 inverse 
                   
                   
                   
                   
                   
                   
                   
                   
               
             
          
           
               
                 New sum 
                 0 
               
               
                 of 
                   
               
               
                 deviations 
                   
               
             
          
           
               
                 coding bit 
                 0 
                 1 
                 1 
                 1 
                 0 
                 1 
                 1 
                 1 
               
               
                   
               
             
          
         
       
     
     Subsequently, the low-byte data are forwarded to the statistic decision unit  120 , which counts to derive the number of bits “ 0 ” (or counts to derive the number of bits “ 1 ” in other embodiment) in each part, for example, by a counter (not shown). Next, deviations (i.e., the difference between the counted numbers and an ideal (or predetermined) mean, e.g., 256 (or 512/2) in this example) for each data part are calculated respectively. The deviations are then summed up. As shown in Table 1, the positive value, 48, of the sum of deviations indicates that there are more bits “ 0 ” than bits “ 1 ” in the whole data section. 
     Thereafter, the inverse unit  122  inverts the bits of one or more data parts according to the result of the statistic decision unit  120 , such that the sum of deviations becomes or approaches zero, therefore uniformly distributing the bits “ 0 ” and “ 1 ” in the encoded data. In the example illustrated in Table 1, all the bits in the part 1 and all the bits in the part 5 are inverted (that is, bits “ 0 ” are changed to “ 1 ” and bits “ 1 ” are changed to “ 0 ”) while the other parts remain unchanged. The result of the statistic decision unit  120  is also outputted as a coding word that may be used later in a decoding operation. In the example, one index bit is reserved for one data part to indicate whether the associated data part has been inverted (“0”) or has not been inverted (“1”). It is noted that the size of the coding “word” in the specification may be any length as required. 
     The coding operation described above may be applied to the high-byte data as well. It is noted that, with respect to each data part, a deviation between the counted number of “0,1” and the ideal mean (e.g., 128) is subtracted from another deviation between the counted number of “0,0” and an ideal mean (e.g., 128). In the example illustrated in Table 2, all the bits in the part 2 and all the bits in the part 5 are inverted while the other parts remain unchanged, such that the sum of deviations becomes or approaches zero, therefore uniformly distributing the bits “ 0 ” and “ 1 ” in the encoded high-byte data. Further, the statistic decision unit  120  also outputs another coding word that may be used later in decoding the high-byte data. In the example, one index bit is reserved for one data part to indicate whether the associated data part has been inverted (“0”) or has not been inverted (“1”). 
     
       
         
               
               
               
               
               
               
               
               
               
             
               
               
             
               
               
               
               
               
               
               
               
               
             
               
               
             
               
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 2 
               
               
                   
               
               
                 part 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
               
               
                   
               
             
             
               
                 size of low-byte 
                 512 
                 512 
                 512 
                 512 
                 512 
                 512 
                 512 
                 512 
               
               
                   
                 bits 
                 bits 
                 bits 
                 bits 
                 bits 
                 bits 
                 bits 
                 bits 
               
               
                 size of high-byte 
                 512 
                 512 
                 512 
                 512 
                 512 
                 512 
                 512 
                 512 
               
               
                   
                 bits 
                 bits 
                 bits 
                 bits 
                 bits 
                 bits 
                 bits 
                 bits 
               
               
                 deviation (i.e., count of 
                 9 
                 13 
                 −3 
                 5 
                 10 
                 2 
                 18 
                 −8 
               
               
                 (“0, 0”-128) − (“0, 1”-128)) 
                   
                   
                   
                   
                   
                   
                   
                   
               
             
          
           
               
                 sum of deviations 
                 46 
               
             
          
           
               
                 deviation after inverse 
                 9 
                 
                           
                 
                 −3 
                 5 
                 
                           
                 
                 2 
                 18 
                 −8 
               
             
          
           
               
                 New sum of deviations 
                 0 
               
             
          
           
               
                 coding bit 
                 1 
                 0 
                 1 
                 1 
                 0 
                 1 
                 1 
                 1 
               
               
                   
               
             
          
         
       
     
       FIG. 3B  shows a detailed block diagram of the uniform decoder  14  of  FIG. 2  according to the first embodiment of the present invention. In the embodiment, the uniform decoder  14  primarily includes a re-inverse unit  142  that inverts the bits of each data part again according to the associated bit of the coding word. For example, the bits of the data part or parts are inverted again if the associated bit of the coding word is “0”, and the other data parts remain unchanged if the associated bit of the coding word is “1”. Subsequently, the outputs of the data parts from the re-inverse unit  142  are combined by a combining unit  144  to form an entire data section. 
       FIG. 4A  shows a detailed block diagram of the uniform encoder  12  of  FIG. 2  according to a second embodiment of the present invention. The uniform encoder  12  primarily includes an inverse unit  122 B and a statistic decision unit  120 B. In the exemplary embodiment, four bits of the data are processed by the inverse unit  122 B at a time. Specifically, the data bits are subjected to exclusive-OR (XOR or designated as ⊕) logical operation with (candidate) coding word (e.g., 0000, 0001, 0010 . . . or 1111 in the example). It is appreciated that the set of coding words need not be complete, and the number of coding bits in each coding word is not limited to four. Generally speaking, more coding words lead to more uniformity in the coding. Table 3 shows an XOR truth table of the data bit and the coding bit. 
     
       
         
               
               
               
               
               
             
           
               
                   
                 TABLE 3 
               
               
                   
                   
               
               
                   
                   
                   
                 encoded 
                   
               
               
                   
                 original 
                   
                 data bit 
                   
               
               
                   
                 data bit 
                 coding bit 
                 (XOR) 
               
               
                   
                   
               
             
             
               
                   
                 0 
                 0 
                 0 
                 data bit 
               
               
                   
                 1 
                 0 
                 1 
                 unchanged 
               
               
                   
                 0 
                 1 
                 1 
                 data bit 
               
               
                   
                 1 
                 1 
                 0 
                 inverted 
               
               
                   
                   
               
             
          
         
       
     
     In the embodiment, the data bit is inverted when the corresponding coding bit is logic “1”, and the data bit remains unchanged when the corresponding coding bit is logic “0”. Although the data bits are exclusive-ORed with the coding words in parallel in this example, it is appreciated that the logical operations XOR may be performed in sequence in other embodiment. 
     The outputs of the inverse unit  122 B are forwarded to the statistic decision unit  120 B, which counts, for example, by a counter (not shown), to derive the number of bits “ 1 ” (or the bits “ 0 ”) of each output of the inverse unit  122 B. The statistic decision unit  120 B then determines one of the candidate coding words as the coding word based on the corresponding optimal output of the inverse unit  122 B. For example, the output with equal number of bits “ 0 ” and the bits “ 1 ” is regarded as the optimal output in the embodiment. The coding operation described above may be applied to the high-byte data as well as the low-byte data. 
       FIG. 4B  shows a detailed diagram of the uniform decoder  14  of  FIG. 2  according to the second embodiment of the present invention. In the embodiment, the uniform decoder  14  primarily includes a re-inverse unit  142 B that inverts the data bits according to the associated coding bit. For example, the re-inverse unit  142 B in the embodiment includes a logic XOR operation performed on the coding bit and the encoded data bit, thereby resulting in the decoded data bit, as shown in Table 4, that is equal to the original data bit. 
     
       
         
               
               
               
             
           
               
                 TABLE 4 
               
               
                   
               
               
                   
                   
                 decoded 
               
               
                 encoded 
                   
                 data bit 
               
               
                 data bit 
                 coding bit 
                 (XOR) 
               
               
                   
               
             
             
               
                 0 
                 0 
                 0 
               
               
                 0 
                 1 
                 1 
               
               
                 1 
                 0 
                 1 
               
               
                 1 
                 1 
                 0 
               
               
                   
               
             
          
         
       
     
       FIG. 5  shows a detailed block diagram of the uniform encoder  12  of  FIG. 2  according to an alternative second embodiment of the present invention. In the embodiment, the candidate coding words in  FIG. 3A  is now replaced with pseudo-random number (PN) codes generated by pseudo random number generators  1220 B respectively. It is appreciated that the set of coding words (i.e., the PN codes) need not be complete, and the number of coding bits in each coding word may be any length as required. Generally speaking, more coding words lead to more uniformity in the coding. 
       FIG. 6A  shows a detailed block diagram of the uniform encoder  12  of  FIG. 2  according to a third embodiment of the present invention. The uniform encoder  12  primarily includes a statistic decision unit  120 C and an inverse unit  122 C. In the exemplary embodiment, the statistic decision unit  120 C determines the occurring frequency or probability of each data code combination. After the data codes are ranked according to their respective probabilities as shown in Table 5, the data code with higher probability are encoded with more uniform code, and vice versa, thereby resulting in a probability coding table. For example, as shown in Table 5, the data code “0110” with the highest probability is encoded as highly uniform code “0101” while the data code “0000” with least probability is encoded as least uniform code “1111”. The inverse unit  122 C then inverts the data bits, when necessary, according to the probability coding table.  FIG. 6B  shows a detailed block diagram of the uniform decoder  14  of  FIG. 2  according to the third embodiment of the present invention. In the embodiment, the uniform decoder  14  primarily includes a re-inverse unit  142 C that inverts the encoded data bits, when necessary, according to the probability coding table shown in Table 5. For example, encoded data bits “0001” is decoded as “1011” according to the probability coding table. 
     
       
         
               
               
               
               
               
             
           
               
                   
                 TABLE 5 
               
               
                   
                   
               
               
                   
                 original code 
                 probability 
                 rank 
                 encoding 
               
               
                   
                   
               
             
             
               
                   
                 0110 
                 0.12 
                  1 
                 0101 
               
               
                   
                 0111 
                 0.11 
                  2 
                 1010 
               
               
                   
                 0011 
                 0.10 
                  3 
                 0011 
               
               
                   
                 1100 
                 0.09 
                  4 
                 0110 
               
               
                   
                 0101 
                 0.08 
                  5 
                 1001 
               
               
                   
                 1010 
                 0.08 
                  6 
                 1100 
               
               
                   
                 1011 
                 0.07 
                  7 
                 0001 
               
               
                   
                 0100 
                 0.06 
                  8 
                 1110 
               
               
                   
                 1000 
                 0.05 
                  9 
                 0100 
               
               
                   
                 1001 
                 0.05 
                 10 
                 1011 
               
               
                   
                 1110 
                 0.05 
                 11 
                 0010 
               
               
                   
                 1111 
                 0.05 
                 12 
                 1101 
               
               
                   
                 0010 
                 0.03 
                 13 
                 0111 
               
               
                   
                 1101 
                 0.03 
                 14 
                 1000 
               
               
                   
                 0001 
                 0.02 
                 15 
                 0000 
               
               
                   
                 0000 
                 0.01 
                 16 
                 1111 
               
               
                   
                   
                 1.00 
               
               
                   
                   
               
             
          
         
       
     
     Although specific embodiments have been illustrated and described, it will be appreciated by those skilled in the art that various modifications may be made without departing from the scope of the present invention, which is intended to be limited solely by the appended claims.