Non-systematic coded error correction

RELATED APPLICATION

This Application is a Divisional of U.S. application Ser. No. 12/212,905, titled “NON-SYSTEMATIC CODED ERROR CORRECTION,” filed Sep. 18, 2008, now U.S. Pat. No. 8,635,510, issued Jan. 21, 2014, which is a Divisional of U.S. application Ser. No. 11/116,560, filed Apr. 28, 2005, now U.S. Pat. No. 7,444,579, issued Oct. 28, 2008, which are commonly assigned and incorporated herein by reference.

TECHNICAL FIELD

The present invention relates generally to integrated circuits and in particular the present invention relates to data management of Flash memory devices.

BACKGROUND

Memory devices are typically provided as internal storage areas in the computer. The term memory identifies data storage that comes in the form of integrated circuit chips. There are several different types of memory used in modern electronics, one common type is RAM (random-access memory). RAM is characteristically found in use as main memory in a computer environment. RAM refers to read and write memory; that is, you can both write data into RAM and read data from RAM. This is in contrast to read-only memory (ROM), which permits you only to read data. Most RAM is volatile, which means that it requires a steady flow of electricity to maintain its contents. As soon as the power is turned off, whatever data was in RAM is lost.

Computers almost always contain a small amount of ROM that holds instructions for starting up the computer. Unlike RAM, ROM cannot be written to. An EEPROM (electrically erasable programmable read-only memory) is a special type non-volatile ROM that can be erased by exposing it to an electrical charge. EEPROM comprise a large number of memory cells having electrically isolated gates (floating gates). Data is stored in the memory cells in the form of charge on the floating gates. Charge is transported to or removed from the floating gates by specialized programming and erase operations, respectively. Other types of non-volatile memory include, but are not limited to, Polymer Memory, Ferroelectric Random Access Memory (FeRAM), Ovionics Unified Memory (OUM), and Magnetoresistive Random Access Memory (MRAM).

Yet another type of non-volatile memory is a Flash memory. A Flash memory is a type of EEPROM that is typically erased and reprogrammed in blocks instead of one byte at a time. A typical Flash memory comprises a memory array, which includes a large number of memory cells. Each of the memory cells includes a floating gate field-effect transistor capable of holding a charge. The data in a cell is determined by the presence or absence of the charge in the floating gate. The cells are usually grouped into sections called “erase blocks.” The memory cells of a Flash memory array are typically arranged into a “NOR” architecture (each cell directly coupled to a bitline) or a “NAND” architecture (cells coupled into “strings” of cells, such that each cell is coupled indirectly to a bitline and requires activating the other cells of the string for access). Each of the cells within an erase block can be electrically programmed in a random basis by charging the floating gate. The charge can be removed from the floating gate by a block erase operation, wherein all floating gate memory cells in the erase block are erased in a single operation.

Each erase block of a Flash memory device typically contains user data areas and overhead data areas. The overhead data areas contain overhead information for operation of the erase block and/or the user data area the overhead data space is associated with. Such overhead information typically includes, but is not limited to, erase block management (EBM) data, sector status information, or an error correction code (ECC). In some Flash memory devices each erase block is divided into a series of logical sectors, where the logical sectors each generally contain 512 bytes of user data space and an associated control or overhead area. One or more of the logical sectors are each typically written to a single row of the Flash memory array (also known as a physical page) within the erase block.

ECC's allow errors in the data stored in the non-volatile memory to be detected and in many cases corrected. ECC's include block codes, that are associated with a block of stored data, and stream codes, that are typically utilized with streams of transmitted data. ECC's include, but are not limited to, Hamming codes, Reed-Solomon (R-S) codes, Bose-Chaudhuri-Hocquenghem (BCH) codes, circular redundancy codes (CRC-32), Golay codes, Reed-Muller codes, Goppa codes, and Denniston codes. In most memories and memory systems, error detection is accomplished via a dedicated ECC check hardware as the data is read out. Error correction is more difficult and typically requires an involved time consuming algorithmic process. As a result, error correction of any data that has detected as corrupt is generally done by a microprocessor or specialized hardware.

The prevalence of errors in modern memory devices, and in non-volatile and Flash memory devices in particular, are increasing with smaller device sizes, increased array density, and lower operating voltages. In addition, the increased active usage with frequent writes of non-volatile memory devices in electronic devices has tended to increase the incidence of operationally induced failures in these devices over long periods of active use due to physical damage, impurity migration, write fatigue, electrical transients, etc.

A problem with non-volatile memories, and Flash memories in particular, is that each erase block physical row page stores the user data before the overhead information, which includes the error correction codes (ECC codes), in each logical sector or row page. Because of this, an error in one or more physical row pages of an erase block can also affect the overhead data associated with those sectors. This increases the likelihood of a loss of data if the ECC is damaged when a localized error to the overhead data area happens. Furthermore, as a result of this ECC encoding method, the user data is placed directly on the memory system or device in an un-encoded/plaintext mode. This may inadvertently allow access to the stored user data.

In addition, the ECC generation/checking hardware of many Flash memory devices and memory systems tends to be complex and consume a large amount of space on an integrated circuit die where it is implemented.

For the reasons stated above, and for other reasons stated below which will become apparent to those skilled in the art upon reading and understanding the present specification, there is a need in the art for improved ECC apparatus and methods that are less susceptible to localized damage to the stored ECC codes and allow for storage of data in encoded non-plaintext formats.

BRIEF DESCRIPTION OF THE DRAWINGS

<figref idref="DRAWINGS">FIG. 1</figref> details a prior art Flash memory controller output with ECC error check and correction circuits.

<figref idref="DRAWINGS">FIGS. 2A and 2C</figref> detail prior art encoding of user data into a sector of a Flash memory array.

<figref idref="DRAWINGS">FIGS. 2B and 2D</figref> detail encoding of user data into a sector of a Flash memory array in accordance with embodiments of the present invention.

<figref idref="DRAWINGS">FIG. 3A</figref> details a transform matrix of a prior art encoding of input user data to stored user data and ECC.

<figref idref="DRAWINGS">FIG. 3B</figref> details a transform matrix of an encoding of input user data to stored user data and ECC in accordance with embodiments of the present invention.

<figref idref="DRAWINGS">FIGS. 4A and 4B</figref> detail Flash memory controller outputs with ECC error check and correction circuits in accordance with embodiments of the present invention.

<figref idref="DRAWINGS">FIGS. 5A and 5B</figref> detail memory systems with memory and memory controllers in accordance with embodiments of the present invention.

DETAILED DESCRIPTION

In the following detailed description of the preferred embodiments, reference is made to the accompanying drawings that form a part hereof, and in which is shown by way of illustration specific preferred embodiments in which the inventions may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the invention, and it is to be understood that other embodiments may be utilized and that logical, mechanical and electrical changes may be made without departing from the spirit and scope of the present invention. The following detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the claims and equivalents thereof.

Memory devices, control circuitry, or data handling routines, in accordance with embodiments of the present invention, facilitate the detection and correction of data in memory systems or devices by encoding the data bits of a memory row or block in a non-systematic ECC code. In particular, in non-volatile memory devices, such as Flash memory systems and devices. This allows memory embodiments of the present invention to utilize reduced complexity error detection and correction hardware and/or routines to efficiently detect and correct corrupted user data in a segment of memory, such as a sector, word line row, or erase block. Additionally, embodiments of the present invention enable user data to be ECC encoded such that the user data is placed directly in the memory system or device in an encoded/non-plaintext mode. This prevents the stored user data from being placed unencrypted in the memory array so that it can be inadvertently disclosed, allowing for an increased level of data security. Further, in embodiments of the present invention, the ECC code is distributed throughout the stored data in the memory segment, increasing the robustness of the ECC code and its resistance to damage or data corruption.

As stated above, memories typically utilize ECC codes to detect errors in read data, ECC codes also allow for correction of a limited number of these errors. ECC codes, and block ECC codes in particular, are commonly based on specialized polynomial equations, where the stored ECC codes are the generated coefficients of the polynomial for the current data. When the data is read out of a memory, the data integrity is checked by regenerating these coefficients from the read data. If the regenerated and stored ECC codes do not match, an error has been detected. In modern ECC block codes, this typically involves serially running the read data through a hardware ECC generator/checker to regenerate the ECC code, and comparing them against the coefficients in the stored ECC code. In these ECC codes, the read data segment is stored in an un-encrypted/plaintext form in the memory and the ECC code is stored at the end of the read data segment or in a separate overhead data area.

Most modern ECC codes are systematic; in encoding a data segment with an ECC code, the k-bits of the originally input data segment are output unchanged in the output of n-bits, along with generated ECC in the remaining n-k bits. In decoding/checking a data segment with an ECC attached, the data segment containing the original data is read along with the stored ECC, the ECC codes are regenerated and compared against the stored ECC. In decoding/checking a data segment with an ECC attached, the data segment containing the encoded original data and embedded ECC is read, the read data segment is decoded and ECC codes are regenerated and compared against the stored embedded ECC codes.

Once an error in read data is detected, the transfer of the data out of the memory device or system is halted and ECC correction algorithm is started. The ECC correction algorithm, generally speaking, solves for the zeros of the polynomial to locate the data word(s) and bit(s) within the data words that need to be corrected. In doing this, two separate pieces of information (ECC codes) are typically required to allow the ECC algorithm to solve for each single bit error, allowing the algorithm to solve for a byte location and a bit location bitmask to XOR to correct the corrupted bit. Thus for each 2 ECC block codes the ECC block code algorithms are typically able to correct a single bit error in a segment of read data.

Embodiments of the present invention utilize non-systematic ECC encoding and codes. In non-systematic ECC encoding an n-bit data segment is generated that differs from the original k-bit data segment (does not contain the original k input bits in the n-bit output) and encodes the original k data bits within the n-bit output data segment along with an embedded ECC code (the n output bits may be functions of more than one of the k input bits). Unlike systematic ECC encoding, in a stored non-systematic ECC encoded data segment, the original data cannot be directly accessed without going through a decoding process. The ECC codes are also generally encoded in a distributed fashion in the stored non-systematic ECC encoded data segment.

Reed-Solomon error correction block codes are one of a number of block codes commonly utilized in memory device applications. As stated above, with a block code generator, a block of data is fed into the block code generator to generate the ECC code to be stored associated with the data block in the memory device. In implementation in embodiments of the present invention, a Reed-Solomon code generator is fed a data block (a data sector) of 512 bytes and generates six 10-bit symbols that form the ECC code to tag on to the end of the data block. From these six symbols of the ECC code it is possible to detect errors in the data block as it is read from the memory device, and, in one embodiment of the present invention, correct for 3 randomly corrupted single data bits or 3 “bit-pairs” (bit-pair's are the adjacent bits of a data byte grouped as 76 54 32 10, where 7 to 0 are the bit positions in the byte).

A memory embodiment of the present invention utilizes non-systematic ECC hardware and/or routines to detect and correct errors in data segments or blocks. This non-systematic ECC circuitry and/or method facilitates the utilization of non-systematic ECC encoding in the data block or segment being encoded for storage or being read from the memory. This allows for a potentially reduced complexity ECC code generator/data checker hardware over a prior art systematic ECC code generator/data checker. The data segment/block/sector, once encoded, is in an encrypted form with the ECC coding typically distributed throughout the encoded data segment. This allows for data to be stored in a non-plaintext format, increasing the security thereof, and distributing the ECC throughout the encoded data segment, increasing the robustness of the stored ECC to any possible ECC code corruption. In one embodiment, the non-systematic ECC encoding provides better end-to-end ECC protection in a system or a memory system, allowing correction of an error that occurs as the data segment is being read or transferred within the system/memory system and not just those occurring within the memory array. In another embodiment of the present invention, the non-systematic encoding allows for the storage of a smaller amount of data (an overall smaller encoded data segment) than in a systematically encoded counterpart.

<figref idref="DRAWINGS">FIG. 1</figref> shows a simplified diagram of a memory controller output <b>100</b> of the prior art coupled through a memory interface <b>102</b> to one or more Flash memory devices and through a host interface <b>104</b> to an external host (not shown), which typically is a processor or computer system. In the memory controller <b>100</b>, a data buffer <b>106</b> is coupled to serially receive and hold a selected data block that is serially read through the memory interface <b>102</b> from a selected Flash memory device before it is transferred from the data buffer <b>106</b> through the host interface <b>104</b> under control of the host transfer hardware <b>114</b>. The serially streamed data block is also coupled to a Reed-Solomon ECC generator/checker hardware <b>108</b>, which regenerates the ECC codes from the data block and checks them against the stored ECC codes attached at the end of the data block stream. Once the data block is read and evaluated, the Reed-Solomon ECC generator/checker hardware <b>108</b> signals <b>110</b> to the host transfer hardware <b>114</b> to start the data transfer if the data block is correct (the data block ECC codes have been generated and evaluated correctly against the stored ECC codes for the data block, typically generating a string of zeros from the Reed-Solomon ECC generation hardware <b>108</b>). If the data block is corrupted (the generated data block ECC codes have evaluated incorrectly against the stored ECC codes for the data block, typically generating a non-zero value in string of zeros output from the Reed-Solomon ECC generation hardware <b>108</b>) the Reed-Solomon ECC generator/checker hardware <b>108</b> signals <b>112</b> a (typically internal) microprocessor or dedicated ECC correction hardware <b>116</b> to correct the errors by utilizing a Reed-Solomon ECC correction algorithm. The microprocessor <b>116</b> solves the Reed-Solomon polynomial to determine the bits to be corrected in the data block and applies the correction <b>118</b> to the data block contents held in the data buffer <b>106</b>. After applying the correction to the data buffer <b>106</b>, the microprocessor <b>116</b> signals <b>120</b> the host transfer hardware <b>114</b> to begin transferring the data block from the data buffer <b>106</b> out through the host interface <b>104</b>.

<figref idref="DRAWINGS">FIGS. 2A and 2C</figref> detail prior art encoding <b>200</b>, <b>240</b> of user data into a sector of a Flash memory array. In <figref idref="DRAWINGS">FIG. 2A</figref>, a data segment <b>208</b> is shown being input into a memory array <b>202</b> (or into an erase block N <b>202</b> of a memory array). The memory array <b>202</b> contains a series of rows, each row containing a user data area <b>204</b> and an overhead data area <b>206</b>. The overhead data <b>206</b> of each row typically stores one or more ECC codes that are generated for the data segment <b>208</b> that is stored in the user data area <b>204</b>. As the data segment <b>208</b> is input to the memory array <b>202</b> it is stored un-encoded in the user data area <b>212</b> of a selected row m <b>210</b> in a plaintext format. An ECC code is also generated for the input data segment <b>208</b> and stored in the overhead data area <b>214</b> of the selected row m <b>210</b> to allow for detection and correction of errors in the data segment <b>208</b> when it is read at a later time.

In <figref idref="DRAWINGS">FIG. 2C</figref>, a data segment <b>208</b> is shown being input into a memory row <b>242</b> of a memory array. As stated above, many memories support multiple logical sectors or data words within a single physical row page (also known as the physical sector). In particular, NAND architecture Flash memories typically utilize this approach due to their generally higher memory cell density and larger row page sizes. The memory row <b>242</b> contains multiple data sectors <b>244</b>, each data sector <b>244</b> having a user data area <b>246</b> and an overhead data section <b>248</b>. The overhead data <b>248</b> of each data sector <b>244</b> typically stores one or more ECC codes that are generated for the data segment <b>208</b> that is stored in the user data area <b>246</b>. As the data segment <b>208</b> is input to the memory row <b>242</b> it is stored un-encoded in the user data area <b>246</b> of a selected data sector <b>244</b> in a plaintext format. An ECC code is also generated for the input data segment <b>208</b> and stored in the overhead data area <b>248</b> of the selected data sector <b>244</b> to allow for detection and correction of errors in the data segment <b>208</b> when it is accessed.

In an example implementation, the row page <b>242</b> of <figref idref="DRAWINGS">FIG. 2C</figref> contains 2112 bytes of data (4×512 bytes user data+4×8 bytes ECC+32 bytes for overhead) and is formatted to contain four logical sectors <b>244</b> having a user data area <b>246</b> of 512-bytes each, wherein logical operating system (OS) sectors of 512 bytes each or multiple logically addressed data words can be stored within each logical sector <b>244</b>. In addition, space is provided following each 512-byte user data area <b>246</b> for the associated overhead data area <b>248</b> containing an ECC code of 8 bytes each. A further 32 bytes (not shown) is reserved for use by the EBM firmware or other system level usage. The four logical sectors <b>244</b> are sequentially addressed N, N+1, N+2, and N+3, where N is a base logical sector address for the row page <b>242</b>. The overhead data areas/ECC codes <b>248</b> of the physical page <b>242</b> are also sequentially addressed N, N+1, N+2, and N+3 to correspond with their associated logical sector <b>244</b> of the row page <b>242</b>. Each overhead/ECC code area <b>248</b> follows the logical sector <b>244</b> and user data area <b>246</b> it is associated with within the row page <b>242</b> (sector N, ECC N, sector N+1, ECC N+1, etc). It is noted that the row page <b>242</b> is for illustration purposes and that other row page sector formats of differing data sizes, numbers of logical sectors/data words, and relative positioning of sectors are possible.

<figref idref="DRAWINGS">FIGS. 2B and 2D</figref> detail encoding <b>220</b>, <b>260</b> of user data into a sector of a Flash memory array in accordance with embodiments of the present invention. In <figref idref="DRAWINGS">FIG. 2B</figref>, a data segment <b>208</b> is shown being input into a memory array <b>222</b> (or into an erase block N <b>222</b> of a memory array). The memory array <b>222</b> contains a series of rows, each row containing a data area <b>224</b> wherein the non-systematically ECC encoded user data is stored. As the data segment <b>208</b> is input to the memory array <b>222</b> the data segment <b>208</b> is non-systematically encoded with an embedded ECC code. The non-systematically ECC encoded data segment is then stored in its encoded form in the data area <b>228</b> of a selected row m <b>226</b>. No separate ECC code is generated and stored. The stored non-systematically ECC encoded data segment in the data area <b>228</b> of row m <b>226</b> is then un-encoded to output original data segment <b>208</b> and to allow for detection and correction of errors in the stored ECC encoded data segment.

In <figref idref="DRAWINGS">FIG. 2D</figref>, a data segment <b>208</b> is shown being input into a memory row <b>262</b> of a memory array with multiple logical sectors or data words within a single physical row page <b>262</b>. Each of the data sectors <b>264</b> of the row page <b>262</b> having a data area <b>266</b>. As the data segment <b>208</b> is input to a selected data sector <b>264</b> of the row page <b>262</b>, the data segment <b>208</b> is non-systematically encoded with an embedded ECC code. The non-systematically ECC encoded data segment is then stored in its encoded form in the data area <b>266</b> of the selected data sector <b>264</b>. No separate ECC codes are generated and stored. The stored ECC encoded data segment in the data area <b>266</b> of the selected data sector <b>264</b> is then un-encoded to output original data segment <b>208</b> and to allow for detection and correction of errors in the stored ECC encoded data segment.

In an example implementation, the row page <b>262</b> of <figref idref="DRAWINGS">FIG. 2D</figref> contains 2112 bytes of data and is formatted to contain four logical sectors <b>264</b> having a data area <b>266</b> of 520-bytes each (or 518-bytes each in one embodiment, due the efficient coding of the non-systematic ECC) to store an encoded 512-byte data segment <b>208</b> and its ECC encoding. A further 32 bytes (not shown) is reserved for use by the EBM firmware or other system level usage. The four logical sectors <b>264</b> are sequentially addressed N, N+1, N+2, and N+3, where N is a base logical sector address for the row page <b>262</b>. It is noted that the row page <b>262</b> is for illustration purposes and that other row page sector formats of differing data sizes, numbers of logical sectors/data words, and relative positioning of the sectors are possible.

<figref idref="DRAWINGS">FIG. 3A</figref> details a prior art transform matrix <b>300</b> for encoding a data segment into a data segment and associated ECC code. In <figref idref="DRAWINGS">FIG. 3A</figref>, a user data segment <b>306</b> is input to a transform matrix <b>300</b> having a square core matrix <b>302</b> that has the same number of outputs as inputs (a M data word by M square matrix, where M is the number of data words in the input user data segment <b>306</b>), and an ECC generation matrix that contains the ECC generation functions (which vary depending on the block encoding method) and has inputs that match the number of data words of the input user data segment <b>306</b> and outputs that match the number of ECC code data words (a M data word by N data word matrix, where N is the number of generated ECC code data words). After the user data segment <b>306</b> is input, the core matrix <b>302</b> of the transform matrix <b>300</b> outputs <b>308</b> the original input data segment <b>306</b>, and the ECC generation matrix <b>304</b> outputs the associated ECC code <b>310</b> to be stored in the memory.

<figref idref="DRAWINGS">FIG. 3B</figref> details a transform matrix for encoding a data segment to a non-systematically encoded data segment having an embedded ECC in accordance with an embodiment of the present invention. In <figref idref="DRAWINGS">FIG. 3B</figref>, a user data segment <b>326</b> is input to a transform matrix <b>320</b> having a different number of outputs as inputs (a M data word by N data word non-square matrix, where M is the number of data words in the input user data segment <b>326</b> and N is the number of output data words). After the user data segment <b>306</b> is input, the transform matrix <b>320</b> outputs an encoded data and ECC segment <b>328</b>, which contains the encoded input data and a distributed ECC and does not contain the original input data segment <b>326</b>, for storage in the memory.

The prior art transform matrix <b>300</b> of <figref idref="DRAWINGS">FIG. 3A</figref> for encoding a separate ECC code to input user data contains a core matrix <b>302</b> which is of a type known as a “unity matrix”, having 1's on the diagonal and 0's elsewhere. With a prior art unity core matrix <b>302</b>, the original input data segment <b>306</b> is output <b>308</b> unchanged along with the generated ECC code <b>310</b>, thus they encode systematic ECC and data segments. Any other transform matrix <b>320</b>, which contains a core matrix <b>302</b> with values/functions other than just 1's on the diagonal and 0's elsewhere, is not a unity matrix. Embodiments of the present invention utilize transform matrices that do not contain core unity matrices <b>302</b>, thus they are non-systematic and generate non-systematically ECC encoded data segments where the original input data <b>306</b> is encoded and not stored in its original form. Additionally, by manipulation of the values/formulas of the transform matrix, embodiments of the present invention can allow the generated ECC codes to be distributed, moved, or localized in any area of the encoded output data <b>328</b>.

<figref idref="DRAWINGS">FIGS. 4A and 4B</figref> detail simplified Flash memory controller outputs with ECC error check and correction circuits in accordance with embodiments of the present invention. In <figref idref="DRAWINGS">FIG. 4A</figref>, a memory controller <b>400</b> is coupled through a memory interface <b>402</b> to one or more Flash memory devices and through a host interface <b>404</b> to an external host (not shown). In the memory controller <b>400</b>, Reed-Solomon ECC generator/checker hardware <b>408</b> is coupled to serially receive a selected data block that is serially read through the memory interface <b>402</b> from a selected Flash memory device. The Reed-Solomon ECC generator/checker <b>408</b> decodes the non-systematic ECC encoded data block and checks it for errors. The Reed-Solomon ECC generator/checker hardware <b>408</b> is coupled to a data buffer <b>406</b> to store the un-encoded data block before it is transferred from the memory controller through the host interface <b>404</b> under control of the host transfer hardware <b>414</b>. Once the data block is un-encoded and evaluated, the Reed-Solomon ECC generator/checker hardware <b>408</b> signals <b>410</b> to the host transfer hardware <b>414</b> to start the data transfer if the data block is correct (the data block ECC codes have been generated and evaluated correctly).

If the non-systematically ECC encoded data block is corrupted (the generated data block ECC codes have evaluated incorrectly) the Reed-Solomon ECC generator/checker hardware <b>408</b> signals <b>412</b> a (typically internal) microprocessor or dedicated ECC correction hardware <b>416</b> to correct the errors by utilizing a Reed-Solomon ECC correction algorithm. The microprocessor <b>416</b> solves the Reed-Solomon polynomial to determine the bits to be corrected and applies the correction <b>418</b> to the un-encoded data block contents held in the data buffer <b>406</b>. After applying the correction to the data buffer <b>406</b>, the microprocessor <b>416</b> signals <b>420</b> the host transfer hardware <b>414</b> to begin transferring the data block from the data buffer <b>406</b> out through the host interface <b>404</b>. In an alternative embodiment, the microprocessor re-reads the data from the selected data block and applies the correction to the incoming data stream before it is evaluated by the Reed-Solomon ECC generator/checker hardware <b>408</b>.

In <figref idref="DRAWINGS">FIG. 4B</figref>, a memory controller <b>430</b> is coupled through a memory interface <b>402</b> to one or more Flash memory devices and through a host interface <b>404</b> to an external host (not shown). In the memory controller <b>430</b>, a data buffer <b>406</b> is coupled to serially receive and store a selected data block that is serially read through the memory interface <b>402</b> from a selected Flash memory device. A Reed-Solomon ECC generator/checker <b>408</b> is coupled to the data buffer <b>406</b> and decodes the non-systematic ECC encoded data block and checks it for errors as it is being transferred from the memory controller <b>430</b> through the host interface <b>404</b> under control of the host transfer hardware <b>414</b>. Once the data block is un-encoded and evaluated, the Reed-Solomon ECC generator/checker hardware <b>408</b> optionally signals <b>440</b> to the host transfer hardware <b>414</b> that the data block is correct (the data block ECC codes have been generated and evaluated correctly).

If the non-systematically ECC encoded data block is corrupted (the generated data block ECC codes have evaluated incorrectly) the Reed-Solomon ECC generator/checker hardware <b>408</b> signals <b>442</b> a (typically internal) microprocessor or dedicated ECC correction hardware <b>416</b> to cancel/abort the transfer of the data block and correct the errors by utilizing a Reed-Solomon ECC correction algorithm. The microprocessor <b>416</b> solves the Reed-Solomon polynomial to determine the bits to be corrected and applies the correction <b>448</b> to the encoded data block contents still held in the data buffer <b>406</b>. After applying the correction to the data buffer <b>406</b>, the microprocessor <b>416</b> signals <b>450</b> the host transfer hardware <b>414</b> to begin transferring the data block from the data buffer <b>406</b> through the Reed-Solomon ECC generator/checker hardware <b>408</b> and host interface <b>404</b>.

It is noted that the non-systematic ECC encoding and error detection and correction in memory embodiments of the present invention can apply to other memory types and, in particular, to non-volatile memory types including, but not limited to, polymer memory, FeRAM, OUM, NROM, and MRAM and should be apparent to those skilled in the art with the benefit of the present invention.

Because all the cells in an erase block of a Flash memory device are generally erased all at once, one cannot directly rewrite a Flash memory cell without first engaging in a block erase operation. EBM, typically under the control of an internal state machine, an external Flash memory controller, or software driver, provides an abstraction layer for this to the host (a processor or an external memory controller), allowing the Flash device to appear as a freely rewriteable device, including, but not limited to, managing the logical address to physical erase block translation mapping for reads and writes, the assignment of erased and available erase blocks for utilization, and the scheduling erase blocks that have been used and closed out for block erasure. Erase block management also allows for load leveling of the internal floating gate memory cells to help prevent write fatigue failure. Write fatigue is where the floating gate memory cell, after repetitive writes and erasures, no longer properly erases and removes charge from the floating gate. Load leveling procedures increase the mean time between failure of the erase block and Flash memory device as a whole.

Many of the modern computer operating systems, such as “DOS” (Disk Operating System), were developed to support the physical characteristics of hard drive structures; supporting file structures based on heads, cylinders and sectors. The DOS software stores and retrieves data based on these physical attributes. Magnetic hard disk drives operate by storing polarities on magnetic material. This material is able to be rewritten quickly and as often as desired. These characteristics have allowed DOS to develop a file structure that stores files at a given location which is updated by a rewrite of that location as information is changed. Essentially all locations in DOS are viewed as fixed and do not change over the life of the disk drive being used therewith, and are easily updated by rewrites of the smallest supported block of this structure. A sector (of a magnetic disk drive) is the smallest unit of storage that the DOS operating system supports. In particular, a sector has come to mean 512 bytes of information for DOS and most other operating systems in existence. Flash memory systems that emulate the storage characteristics of hard disk drives are preferably structured to support storage in 512 byte blocks along with additional storage for overhead associated with mass storage, such as ECC bits, status flags for the sector or erase block, and/or redundant bits.

In many modern Flash memory device implementations, the host interface and erase block management routines additionally allow the Flash memory device to appear as a read/write mass storage device (i.e., a magnetic disk) to the host. One such approach is to conform the interface to the Flash memory to be identical to a standard interface for a conventional magnetic hard disk drive allowing the Flash memory device to appear as a block read/write mass storage device or disk. This approach has been codified by the Personal Computer Memory Card International Association (PCMCIA), Compact Flash (CF), and Multimedia Card (MMC) standardization committees, which have each promulgated a standard for supporting Flash memory systems or Flash memory “cards” with a hard disk drive protocol. A Flash memory device or Flash memory card (including one or more Flash memory array chips) whose interface meets these standards can be plugged into a host system having a standard DOS or compatible operating system with a Personal Computer Memory Card International Association—Advanced Technology Attachment (PCMCIA-ATA) or standard ATA interface. Other additional Flash memory based mass storage devices of differing low level formats and interfaces also exist, such as Universal Serial Bus (USB) Flash drives.

<figref idref="DRAWINGS">FIG. 5A</figref> is a simplified diagram of a system <b>500</b> that incorporates a Flash memory device <b>504</b> embodiment of the present invention. In the system <b>500</b> of <figref idref="DRAWINGS">FIG. 5A</figref>, the Flash memory <b>504</b> is coupled to a processor <b>502</b> with an address/data bus <b>506</b>. Internally to the Flash memory device, a control state machine <b>510</b> directs internal operation of the Flash memory device; managing the Flash memory array <b>508</b> and updating RAM control registers and tables <b>514</b>. The Flash memory array <b>508</b> contains floating gate memory cells arranged in a sequence of erase blocks <b>516</b>, <b>518</b>. Each erase block <b>516</b>, <b>518</b> contains a series of physical pages, each page containing one or more logical sectors <b>524</b> (shown here for illustration purposes as a single logical sector <b>524</b> per physical page/row) that contain a user data space <b>520</b> and a control/overhead data space <b>522</b>. The overhead data space <b>522</b> contains overhead information for operation of the sector <b>520</b>, such as an error correction code (not shown), status flags, or an erase block management data field area (not shown). The RAM control registers and tables <b>514</b> are loaded at power up from the non-volatile erase block management registers and tables (not shown) by the control state machine <b>510</b>. The user data space <b>520</b> in each logical sector <b>524</b> is typically <b>512</b> bytes long. It is noted that other interfaces to the Flash memory <b>504</b> and formats for the erase blocks <b>516</b>, <b>518</b>, physical pages, and sectors <b>524</b> are possible and should be apparent to those skilled in the art with benefit of the present disclosure. In <figref idref="DRAWINGS">FIG. 5A</figref>, the Flash memory <b>504</b> contains ECC generation and checking hardware <b>512</b> incorporating embodiments of the present invention.

<figref idref="DRAWINGS">FIG. 5B</figref> is a simplified diagram of another system <b>550</b> that incorporates a Flash memory system <b>560</b> embodiment of the present invention. In the system <b>550</b> of <figref idref="DRAWINGS">FIG. 5B</figref>, the Flash memory system <b>560</b>, such as a memory system or Flash memory card, is coupled to a processor <b>552</b> with an address <b>554</b>, control <b>556</b>, and data bus <b>558</b>. Internal to the Flash memory system <b>560</b>, a memory controller <b>566</b> directs internal operation of the Flash memory system <b>560</b>; managing the Flash memory devices <b>562</b>, directing data accesses, updating internal control registers and tables (not shown), and/or directing operation of other possible hardware systems (not shown) of the Flash memory system <b>560</b>. The memory controller <b>566</b> has an internal ECC generation and checking hardware (not shown) that incorporates embodiments of the present invention. The memory controller <b>566</b> may optionally incorporate a small local embedded processor to help manage the Flash memory system <b>560</b>. The memory controller <b>566</b> is coupled to and controls one or more Flash memory devices <b>562</b> via an internal control bus <b>564</b>. It is noted that other architectures Flash memory systems <b>560</b>, external interfaces <b>554</b>, <b>556</b>, <b>558</b>, and manners of coupling the memory controller <b>566</b> to the Flash memory devices <b>562</b>, such as directly coupled individual control busses and signal lines, are possible and should be apparent to those skilled in the art with benefit of the present disclosure.

The Flash memory devices <b>562</b> each contain a sequence of erase blocks <b>516</b>, <b>518</b> in their internal memory arrays. Each erase block <b>516</b>, <b>518</b> contains a series of physical pages, each physical page having one or more logical sectors <b>524</b> that contain a user data space <b>520</b> and a control/overhead data space <b>522</b> (shown here for illustration purposes as a single logical sector <b>524</b> per physical page/row). The overhead data space <b>522</b> contains an ECC code (not shown) and other overhead information for operation of the logical sector <b>520</b>, such as status flags, or an erase block management data field area (not shown).

It is noted that the ECC checking and correction of Flash memory embodiments of the present invention can apply to other non-volatile memory types including, but not limited to, polymer memory, FeRAM, OUM, NROM, and MRAM and should be apparent to those skilled in the art with the benefit of the present invention.

It is also noted that other ECC checking and correction sequences and circuits in memory embodiments of the present invention are possible and should be apparent to those skilled in the art with benefit of the present disclosure.

CONCLUSION

Improved memory devices, circuitry, and data methods have been described that facilitate the detection and correction of data in memory systems or devices by encoding the data bits of a memory row or block in a non-systematic ECC code. This allows memory embodiments of the present invention to utilize reduced complexity error detection and correction hardware and/or routines to efficiently detect and correct corrupted user data in a segment of memory, such as a sector, word line row, or erase block. Additionally, in embodiments of the present invention user data is not stored in a plaintext format in the memory array, allowing for an increased level of data security. Further, in embodiments of the present invention, the ECC code is distributed throughout the stored data in the memory segment, increasing the robustness of the ECC code and its resistance to damage or data corruption.

Although specific embodiments have been illustrated and described herein, it will be appreciated by those of ordinary skill in the art that any arrangement, which is calculated to achieve the same purpose, may be substituted for the specific embodiment shown. This application is intended to cover any adaptations or variations of the present invention. Therefore, it is manifestly intended that this invention be limited only by the claims and the equivalents thereof.