ECC and RAID-type decoding

A device includes a memory and a controller. The controller is configured to read codewords of a data structure from the memory. The codewords include a number of undecodable codewords that are undecodable at an error correction coding (ECC) decoder according to a first correction scheme. The controller includes a stripe generator and a stripe decoder. The stripe generator is configured, in response to the number of undecodable codewords exceeding an erasure correction capacity of a stripe correction scheme, to generate trial data for a stripe of the data structure, the trial data including at least one element that corresponds to erased data and at least another element that is associated with an undecodable codeword and that corresponds to valid data of the stripe. The stripe decoder is configured to initiate a stripe decode operation of the trial data.

FIELD OF THE DISCLOSURE

This disclosure is generally related to data storage devices and more particularly to data encoding and recovery using error correction coding (ECC) techniques and redundant array of independent disks (RAID)-type techniques.

BACKGROUND

Non-volatile data storage devices, such as flash solid state drive (SSD) memory devices or removable storage cards, have allowed for increased portability of data and software applications. Flash memory devices can enhance data storage density by storing multiple bits in each flash memory cell. For example, Multi-Level Cell (MLC) flash memory devices provide increased storage density by storing 2 bits per cell, 3 bits per cell, 4 bits per cell, or more. Although increasing the number of bits per cell and reducing device feature dimensions may increase a storage density of a memory device, a bit error rate of data stored at the memory device may also increase.

Error correction coding (ECC) is often used to correct errors that occur in data read from a memory device. Prior to storage, data may be encoded by an ECC encoder to generate redundant information (e.g., “parity bits”) that may be stored with the data as an ECC codeword. As more parity bits are used, an error correction capacity of the ECC increases and a number of bits required to store the encoded data also increases. Using a sufficient number of parity bits to provide “worst-case” error correction capability for all data stored in a memory device reduces the storage density of the memory device in order to protect against an amount of data corruption that is statistically unlikely to occur before the memory device reaches the end of its useful life.

SSD devices may also incorporate a redundant array of independent dies (RAID)-type storage scheme that may use parity bits to enable data recovery in case of memory defects and device failures, which cannot be recovered by the ECC which is aimed at handling random errors (e.g., due to program disturb, read disturb, charge loss due to data retention, etc.). ECC may not be able to recover the data in case of memory defects or complete failure, which may result in very high error rates that exceed the ECC capability. Hence, additional RAID-type protection may be required for protecting against such memory defects. For example, a RAID 6 storage scheme may distribute data, a first parity for the data, and a second parity for the data in a “stripe” across multiple non-volatile memories (e.g., across multiple SSDs or across multiple NAND flash memories in a single SSD). The first parity (or the second parity) may enable recovery of the data in the stripe in case of erasures due to failure of one of the data-storing non-volatile memories, and the first parity and the second parity together may enable recovery of the data in the stripe in case of erasures due to failure of two of the data-storing non-volatile memories. However, data in such storage schemes may not be recoverable if three or more of the data-storing non-volatile memories fail. Note that although the name RAID may suggest that RAID parity is stored in a redundant die, this is not mandatory. In some cases, a redundant plane, redundant block or redundant word lines (WLs) or pages within a block may be used for storing the RAID parity. For example, the RAID stripe may be implemented across dies, planes, blocks or pages within a block of the non-volatile memory.

The two protection levels, ECC for random errors and RAID for memory defects and failures, may require memory overprovisioning for storing the ECC and RAID parity.

DETAILED DESCRIPTION

A data storage device is configured to perform error correction code (ECC) and RAID-type decoding. Memory overprovisioning may be used for storing the ECC and RAID parity to provide the two protection levels: ECC for random errors and RAID for memory defects and failures. In order to efficiently utilize the allocated overprovisioning and to improve or maximize the random error correction capability given the overall allocated overprovisioning, joint ECC and RAID decoding can be performed, leveraging the unused RAID overprovisioning for random error correction, whenever there are no memory defects or when the number memory defects is less than the RAID correction capability.

The data storage device may include a controller coupled to a memory. The memory may store a data structure including a plurality of codewords. The data structure may also include parity codewords. Each of the codewords may be stored at separate pages of the memory. The data structure may be configured to enable each of the codewords to be decodable independently of the other codewords. Portions of the codewords may correspond to multiple stripes of the data structure. For example, first portions of the codewords may correspond to a first stripe of the data structure and second portions of the codewords may correspond to a second stripe of the data structure.

The controller may read the codewords from the memory. The codewords may include a number of undecodable codewords that are undecodable at an ECC decoder according to a first correction scheme (e.g., a low-density parity check (LDPC) scheme). The ECC decoder may generate trial data for a stripe of the data structure such that at least one of the undecodable codewords corresponds to erased data of the stripe and at least another of the undecodable codewords corresponds to valid data of the stripe. The ECC decoder may initiate a stripe decode operation of the trial data using a stripe correction scheme. The ECC decoder may, for each undecoded stripe of the data structure, test different combinations of the undecodable codewords as erased data until the stripe is decoded or until all distinct combinations of the undecodable codewords as erased data have been tested.

Particular examples in accordance with the disclosure are described below with reference to the drawings. In the description, common features are designated by common reference numbers. As used herein, “exemplary” may indicate an example, an implementation, and/or an aspect, and should not be construed as limiting or as indicating a preference or a preferred implementation. Further, it is to be appreciated that certain ordinal terms (e.g., “first” or “second”) may be provided for identification and ease of reference and do not necessarily imply physical characteristics or ordering. Therefore, as used herein, an ordinal term (e.g., “first,” “second,” “third,” etc.) used to modify an element, such as a structure, a component, an operation, etc., does not necessarily indicate priority or order of the element with respect to another element, but rather distinguishes the element from another element having a same name (but for use of the ordinal term). In addition, as used herein, indefinite articles (“a” and “an”) may indicate “one or more” rather than “one.” As used herein, a structure or operation that “comprises” or “includes” an element may include one or more other elements not explicitly recited. Further, an operation performed “based on” a condition or event may also be performed based on one or more other conditions or events not explicitly recited.

FIG. 1depicts an illustrative example of a system100that includes a data storage device102and an access device170(e.g., a host device or another device). The data storage device102includes an ECC engine136that is configured to encode stripes of a data structure110and to decode data of the data structure110according to a first correction scheme150(e.g., a LDPC correction scheme) and a second correction scheme152(e.g., a stripe correction scheme). If a number of rows (e.g., LDPC codewords) of the data structure110that are uncorrectable using the first correction scheme150exceeds an erasure correction capability of the stripe correction scheme152, multiple trials of stripe decoding may be performed for each stripe of the data structure110by selecting different combinations of the uncorrectable rows as representing erased data of the stripe or as representing valid data of the stripe. As a result, one or more stripes of the data structure110may be decoded even though the erasure correction capacity is exceeded.

The data storage device102and the access device170may be coupled via a connection (e.g., a communication path180), such as a bus or a wireless connection. The data storage device102may include a first interface132(e.g., an access device or host interface) that enables communication via the communication path180between the data storage device102and the access device170.

The data storage device102may include or correspond to a solid state drive (SSD) which may be included in, or distinct from (and accessible to), the access device170. For example, the data storage device102may include or correspond to an SSD, which may be used as an embedded storage drive (e.g., a mobile embedded storage drive), an enterprise storage drive (ESD), a client storage device, or a cloud storage drive, as illustrative, non-limiting examples. In some implementations, the data storage device102is coupled to the access device170indirectly, e.g., via a network. For example, the network may include a data center storage system network, an enterprise storage system network, a storage area network, a cloud storage network, a local area network (LAN), a wide area network (WAN), the Internet, and/or another network. In some implementations, the data storage device102may be a network-attached storage (NAS) device or a component (e.g., a solid-state drive (SSD) device) of a data center storage system, an enterprise storage system, or a storage area network.

In some implementations, the data storage device102may be embedded within the access device170, such as in accordance with a Joint Electron Devices Engineering Council (JEDEC) Solid State Technology Association Universal Flash Storage (UFS) configuration. For example, the data storage device102may be configured to be coupled to the access device170as embedded memory, such as eMMC® (trademark of JEDEC Solid State Technology Association, Arlington, Va.) and eSD, as illustrative examples. To illustrate, the data storage device102may correspond to an eMMC (embedded MultiMedia Card) device. As another example, the data storage device102may correspond to a memory card, such as a Secure Digital (SD®) card, a microSD® card, a miniSD™ card (trademarks of SD-3C LLC, Wilmington, Del.), a MultiMediaCard™ (MMC™) card (trademark of JEDEC Solid State Technology Association, Arlington, Va.), or a CompactFlash® (CF) card (trademark of SanDisk Corporation, Milpitas, Calif.). Alternatively, the data storage device102may be removable from the access device170(i.e., “removably” coupled to the access device170). As an example, the data storage device102may be removably coupled to the access device170in accordance with a removable universal serial bus (USB) configuration.

The data storage device102may operate in compliance with an industry specification. For example, the data storage device102may include a SSD and may be configured to communicate with the access device170using a small computer system interface (SCSI)-type protocol, such as a serial attached SCSI (SAS) protocol. As other examples, the data storage device102may be configured to communicate with the access device170using a NVM Express (NVMe) protocol or a serial advanced technology attachment (SATA) protocol. In other examples, the data storage device102may operate in compliance with a JEDEC eMMC specification, a JEDEC Universal Flash Storage (UFS) specification, one or more other specifications, or a combination thereof, and may be configured to communicate using one or more protocols, such as an eMMC protocol, a universal flash storage (UFS) protocol, a universal serial bus (USB) protocol, and/or another protocol, as illustrative, non-limiting examples.

The access device170may include a memory interface (not shown) and may be configured to communicate with the data storage device102via the memory interface to read data from and write data to the memory device103of the data storage device102. For example, the access device170may be configured to communicate with the data storage device102using a SAS, SATA, or NVMe protocol. As other examples, the access device170may operate in compliance with a Joint Electron Devices Engineering Council (JEDEC) industry specification, such as a Universal Flash Storage (UFS) Access Controller Interface specification. The access device170may communicate with the memory device103in accordance with any other suitable communication protocol.

The access device170may include a processor and a memory. The memory may be configured to store data and/or instructions that may be executable by the processor. The memory may be a single memory or may include multiple memories, such as one or more non-volatile memories, one or more volatile memories, or a combination thereof. The access device170may issue one or more commands to the data storage device102, such as one or more requests to erase data, read data from, or write data to the memory device103of the data storage device102. For example, the access device170may be configured to provide data, such as data182, to be stored at the memory device103or to request data to be read from the memory device103. The access device170may include a mobile telephone, a computer (e.g., a laptop, a tablet, or a notebook computer), a music player, a video player, a gaming device or console, an electronic book reader, a personal digital assistant (PDA), a portable navigation device, a computer, such as a laptop computer or notebook computer, a network computer, a server, any other electronic device, or any combination thereof, as illustrative, non-limiting examples.

The memory device103of the data storage device102may include one or more memory dies (e.g., one memory die, two memory dies, eight memory dies, or another number of memory dies). The memory device103includes a memory104, such as a non-volatile memory of storage elements included in a memory die of the memory device103. For example, the memory104may include a flash memory, such as a NAND flash memory, or a resistive memory, such as a resistive random access memory (ReRAM), as illustrative, non-limiting examples. In some implementations, the memory104may include or correspond to a memory die of the memory device103. The memory104may have a three-dimensional (3D) memory configuration. As an example, the memory104may have a 3D vertical bit line (VBL) configuration. In a particular implementation, the memory104is a non-volatile memory having a 3D memory configuration that is monolithically formed in one or more physical levels of arrays of memory cells having an active area disposed above a silicon substrate. Alternatively, the memory104may have another configuration, such as a two-dimensional (2D) memory configuration or a non-monolithic 3D memory configuration (e.g., a stacked die 3D memory configuration).

Although the data storage device102is illustrated as including the memory device103, in other implementations the data storage device102may include multiple memory devices that may be configured in a similar manner as described with respect to the memory device103. For example, the data storage device102may include multiple memory devices, each memory device including one or more packages of memory dies, each package of memory dies including one or more memories such as the memory104. Data striping and error recovery as described with respect to pages of the memory104may be extended to include data striping and error recovery across multiple dies, across multiple packages, across multiple memory devices, or any combination thereof.

The memory104may include one or more blocks, such as a NAND flash erase group of storage elements. Each storage element of the memory104may be programmable to a state (e.g., a threshold voltage in a flash configuration or a resistive state in a resistive memory configuration) that indicates one or more values. Each block of the memory104may include one or more word lines. Each word line may include one or more pages, such as one or more physical pages. In some implementations, each page may be configured to store a codeword. A word line may be configurable to operate as a single-level-cell (SLC) word line, as a multi-level-cell (MLC) word line, or as a tri-level-cell (TLC) word line, as illustrative, non-limiting examples.

The memory device103may include support circuitry, such as read/write circuitry105, to support operation of one or more memory dies of the memory device103. Although depicted as a single component, the read/write circuitry105may be divided into separate components of the memory device103, such as read circuitry and write circuitry. The read/write circuitry105may be external to the one or more dies of the memory device103. Alternatively, one or more individual memory dies of the memory device103may include corresponding read/write circuitry that is operable to read data from and/or write data to storage elements within the individual memory die independent of any other read and/or write operations at any of the other memory dies.

The memory104includes the data structure110. The data structure110includes multiple codewords (e.g., “S” codewords, where S is an integer greater than one), such as a first codeword160and one or more additional codewords, including an Sthcodeword162. The data structure110also includes a first parity codeword164on a first page and a second parity codeword166on a second page of the memory104. For example, each of the codewords160-166may be stored at separate pages of the memory104. The data structure110is configured to enable each of the codewords160-166to be decodable independently of the other codewords160-166. For example, the first codeword160includes parity bits that may be used by the ECC engine136to correct bit errors up to the correction capability of the first correction scheme150. In the event that one or more of the codewords160-162contain a number of bit errors that exceeds the correction capability of the first correction scheme150, one or more of the first parity codeword164and the second parity codeword166may be used to generate error-corrected data corresponding to one or more stripes of the data structure110, such as a first stripe codeword191corresponding to a first stripe197and a second stripe codeword192corresponding to a Kthstripe199, where K indicates a number of stripes in the data structure110and is an integer greater than one.

To illustrate, the first stripe codeword191includes a first portion171of the first codeword160and a first portion of one or more of the other codewords, including a first portion173of the Sthcodeword162. The first portions171-173of the codewords160-162may be encoded using a stripe encoding scheme (e.g., a Reed-Solomon (RS)) scheme) to generate first parity data corresponding to the first stripe197. A first portion175of the first parity data corresponding to the first stripe197is included in the first parity codeword164and a second portion177of the first parity data corresponding to the first stripe197is included in the second parity codeword166. The second stripe codeword192includes a second portion181of the first codeword160and a second portion of one or more other codewords of the data structure110, including a second portion183of the Sthcodeword162. The second stripe codeword192also includes a first portion185of second parity data corresponding to the Kthstripe199and a second portion187of the second parity data that corresponds to the Kthstripe199.

The controller130is coupled to the memory device103via a bus120, an interface (e.g., interface circuitry, such as a second interface134), another structure, or a combination thereof. For example, the bus120may include one or more channels to enable the controller130to communicate with a single memory die of the memory device. As another example, the bus120may include multiple distinct channels to enable the controller130to communicate with each memory die of the memory device103in parallel with, and independently of, communication with other memory dies of the memory device103.

The controller130is configured to receive data and instructions from the access device170and to send data to the access device170. For example, the controller130may send data to the access device170via the first interface132, and the controller130may receive data from the access device170via the first interface132. The controller130is configured to send data and commands to the memory104and to receive data from the memory104. For example, the controller130is configured to send data and a write command to cause the memory104to store data to a specified address of the memory104. The write command may specify a physical address of a portion of the memory104(e.g., a physical address of a word line of the memory104) that is to store the data. The controller130may also be configured to send data and commands to the memory104associated with background scanning operations, garbage collection operations, and/or wear leveling operations, etc., as illustrative, non-limiting examples. The controller130is configured to send a read command to the memory104to access data from a specified address of the memory104. The read command may specify the physical address of a portion of the memory104(e.g., a physical address of a word line of the memory104).

The ECC engine136is configured to receive data to be stored to the memory104and to generate a codeword. For example, the ECC engine136may include an encoder configured to encode data using an ECC scheme, such as a Reed Solomon encoder, a Bose-Chaudhuri-Hocquenghem (BCH) encoder, a low-density parity check (LDPC) encoder, a Turbo Code encoder, an encoder configured to encode one or more other ECC encoding schemes, or any combination thereof. The ECC engine136may include one or more decoders configured to decode data read from the memory104to detect and correct, up to an error correction capability of the ECC scheme, any bit errors that may be present in the data.

For example, the ECC engine136may include a first decoder, such as an ECC decoder154, to decode codewords (e.g., codewords160-166) according to the first correction scheme150. The ECC engine136may include a second decoder, such as a stripe decoder156, to correct erasures in the stripe codewords of the data structure110(e.g., stripe codewords191-192) according to the second correction scheme152. As a non-limiting example, each of the codewords160-166may be encoded using a first encoding scheme (e.g., LDPC), each of the stripes190-192may be encoded using a second encoding scheme (e.g., Reed Solomon), the first correction scheme150may include a LDPC correction scheme, and the second correction scheme152may include a Reed Solomon erasure correction scheme. Although LDPC and Reed Solomon are provided as non-limiting examples, each of the codewords160-166may be encoded using a different encoding scheme (e.g., a BCH scheme), and each of the stripes190-192may be encoded using a different stripe encoding scheme (e.g., another BCH scheme).

The controller130is configured to receive the data182from the access device170and to encode the data182into multiple codewords and multiple stripe codewords to generate the data structure110to be stored in the memory104. For example, the controller130may be configured to partition the data182into S data words. To illustrate, first data140may correspond to a first data word of the data182and Sthdata142may correspond to a last data word of the data182. The controller130is configured to encode first data140to generate a first codeword160that is decodable using the first correction scheme150. To illustrate, the first codeword160may include the first data140and first parity bits (P1)141based on the first data140. The controller130is further configured to encode second data142(e.g., the Sthdata) to generate the second codeword162(e.g., the Sthcodeword). The second codeword162includes the second data142and also includes second parity bits (e.g., “PS” parity bits for the Sthdata)143based on the second data142. AlthoughFIG. 1illustrates two data words140and142and two codewords160and162, it should be understood that any number of data words and codewords may be used to generate the data structure110. For example, S may have a value of 2, 3, 4, 16, 32, 128, or any other integer value greater than one.

The first codeword160and the second codeword162may be stored in a memory138(e.g., a random access memory (RAM) within the controller130or RAM (e.g., double data rate type 3 (DDR3) synchronous dynamic RAM (SDRAM)) that is coupled to the controller130) to enable ECC processing on one or more stripes of the data140-142to generate stripe parity data. The controller130may be configured to cause the ECC engine136to encode multiple stripes of data (e.g., stripes 1 to K (or 0 to K−1), corresponding to multiple columns of multiple bits) from each of the S codewords160-162to be encoded using the composite generator function156to generate parity bits for each stripe197-199. The parity bits for each stripe197-199are inserted into a first set of parity data144and a second set of parity data146at locations corresponding to the respective stripes. For example, the controller130is configured to generate first parity data that corresponds to the first stripe codeword191by encoding the first portions171-173of the codewords160-162. The controller130is further configured to store the first portion175of the first parity data corresponding to the first stripe197in a first page of the memory104and to store the second portion177of the first parity data in the second page of the memory104. AlthoughFIG. 1illustrates two stripes197and199, it should be understood that any number of stripes may be used. For example, K may have a value of 2, 3, 4, 16, 32, 128, or any other integer value greater than one.

The ECC engine136may encode each stripe until the sets of parity data for each stripe have been generated and stored in the memory138. The ECC engine136is configured to encode the first sets of parity data144to generate the first parity codeword164that includes the first set of parity data144and parity bits (PA)145. The ECC engine136is further configured to encode the second set of parity data146to generate the second parity codeword166that includes the second set of parity data146and parity bits (PB)147.

The controller130may be configured to transfer the codewords160-166from the memory138for storage into the memory104of the memory device103to form the data structure110in the memory104. For example, the controller130may be configured to sequentially write the codewords160-166to consecutively-addressed pages of the memory104so that the data structure110is aligned in a row-and-column format as depicted inFIG. 1, with the codewords160-166forming rows and the stripes197-199forming columns in the memory104. However, in other implementations, the codewords160-166may not have any particular alignment or physical relationship to each other in the memory104, and locations of each of the codewords160-166of the data structure110may be tracked and maintained by the controller130. For example, the controller130may include a table (not shown) that indicates the physical addresses of each of the S codewords160-162and the parity codewords164-166. The controller130may populate the table when the data structure110is stored to the memory104and may update the table if any of the codewords160-166change physical addresses, such as due to garbage collection, wear leveling, or one or more other maintenance operations. The controller130may access the table to retrieve physical addresses of the codewords160-166in response to one or more of the codewords160-162being undecodable using the first correction scheme150.

Bit errors occurring in one or more of the codewords160-162read from the memory104may exceed an error correction capacity of the ECC decoder154. As described in further detail with respect toFIG. 2, the ECC engine136may read the remaining codewords of the data structure110from the memory104to the memory138and may attempt decoding of the remaining codewords at the ECC decoder154. If a number of failed codewords (e.g., that are undecodable at the ECC decoder154due to too many errors) is less than or equal to an erasure correction capability of the stripe decoder156, then the stripe decoder156may be used to correct each stripe, thereby correcting the failed codewords. However, if the number of failed codewords exceeds the erasure correction capability of the stripe decoder156, then the stripe generator190may be used to generate one or more trial versions192of one or more of the stripes by selecting different combinations of the failed codewords as corresponding to either valid data or erased data, as explained in further detail with reference toFIGS. 2-3.

Because the data structure110includes the sets of stripe parity bits generated by the ECC engine136, and because the stripe generator190may be used to perform stripe correction that exceeds an erasure capability of the stripe decoder156, additional error correction capability is provided for the codewords160-162beyond the error correction capability provided by the codeword parity (e.g., parity P1141and P2143). The codewords160-162may therefore be formed using fewer parity bits than would otherwise be required for “worst-case” error handling, reducing power consumption during decoding of the codewords160-162.

Referring toFIG. 2, a particular implementation of a method200that may be performed by the controller130of the data storage device102ofFIG. 1is depicted. Although the method200is described with reference to the data storage device102ofFIG. 1, in other implementations the method200may be performed by a device other than the data storage device102ofFIG. 1.

The method200may be used in response to a request to read a particular codeword, CWn. The method200includes reading CWnfrom the memory104, at202. For example, CWnmay correspond to the first codeword160ofFIG. 1. A determination may be made, at203, as to whether CWnis decodable. For example, the controller130may route the representation of the first codeword160that is read from the memory104to the ECC engine136to initiate decoding according to the first correction scheme150. In response to detecting that the CWnis decodable, an error corrected version of the data of CWnmay be provided to the requestor, such as the access device170ofFIG. 1, and the method200may end, at204.

In response to determining that CWnis not decodable, a determination may be made whether the remaining codewords of the data structure110have been read from the memory104, at205. If the remaining codewords have been read from the memory, a loop counter “i” is initialized (e.g., i=0), at212. Otherwise, if the remaining codewords of the data structure110have not been read from the memory104, the remaining codewords of the data structure110may be read from the memory104, at206. The remaining codewords are designated as codewords CW0-CWS-1, where S indicates the number of non-parity codewords in the data structure110. The codewords that are read from the memory104may be stored at a memory of the controller130, such as the memory138, for access by the ECC engine136during decode operations. Alternatively, one or more of the codewords may be retrieved from the memory104on an as-needed basis, such as if the memory138does not have sufficient capacity to store all of the codewords CW0-CWS-1. A first parity page (e.g., the first parity codeword164ofFIG. 1) may be read from a first page of the memory104, such as a flash memory, at208, and a second parity page, such as the second parity codeword166ofFIG. 1, may be read from a second page of the memory104, at210. Processing continues with setting the loop counter “i” to the initial value (e.g., 0), at212.

A determination is made whether i=n, at214. If i=n, then i is incremented, at216. In response to determining that i is not equal to n, at214, a determination is made whether i is equal to S, at218. In response to determining that i is not equal to S, at218, the controller130may attempt to decode the ithcodeword (CWi), at220. For example, attempting to decode CWimay include determining whether CWihas been decoded, and if CWihas not been decoded, providing a representation of the ithcodeword to the ECC engine136to perform a decode operation according to the first correction scheme150. After attempting to decode CWi, i is incremented, at216.

When i=S, at218, a decoding operation has been attempted for each of the (non-parity) codewords of the data structure110. The controller130then attempts decoding of the first parity data, at222. For example, if the first parity codeword164has not been decoded, the controller130may provide the first parity codeword164that is read from the memory104to the ECC engine136to attempt to decode the first parity codeword164. The controller130also attempts decoding of the second parity data, at224. For example, if the second parity codeword166has not been decoded, the controller130may provide the representation of the second parity codeword166that is read from the memory104to the ECC engine136. The ECC engine136attempts a decoding operation to detect and correct errors in the second parity codeword166according to the first correction scheme150.

After decode processing of each of the undecoded codewords160-166of the data structure110, a number of undecoded codewords of the codewords CW1-CWS, the first parity data codeword, and the second parity data codeword is compared to an erasure correction capacity of the second correction scheme152ofFIG. 1, at226. In response to the number of undecoded codewords not exceeding the erasure correction capacity, each stripe is processed to correct erasures from the undecoded codewords using a portion or all of the stripe parity for the stripe, at228. For example, if a single codeword (e.g., the first codeword160ofFIG. 1) is undecoded, the first portion175or the second portion177of the stripe parity for the first stripe codeword191ofFIG. 1may be used to determine the first portion171of the first codeword160. After erasure correction of each stripe, the error corrected version of the data of CWnmay be provided to the requestor, such as the access device170ofFIG. 1, and the method200may end, at204.

Otherwise, if the number of undecoded codewords exceeds the erasure correction capacity, at226, one or more trial codewords for each stripe may be generated using combinations of the failed codewords as erasure data and are processed using second correction scheme154to perform random error correction in a stripe-by-stripe, row-by-row iterative decoding process. To illustrate, another loop counter “k” is initialized to an initial value, e.g., k=0, at230. The loop counter k may indicate a stripe index of stripes of the data structure110. For example, the first stripe197may correspond to k=0, the second stripe199may correspond to k=1, etc. If the kthstripe is decodable using the stripe decoder156(e.g., if the stripe decoder156can correct up to Z erasures or Z/2 errors in a stripe, and the kthstripe has Z/2 or fewer errors), then the errors in the kthstripe are corrected by the stripe decoder156. Otherwise, one or more trial codewords for the kthstripe may be generated based on the kthportion of each of the codewords CW0-CWS-1, the kthportion of the first parity data, and the kthportion of the second parity data, using different combinations of the failed codewords as erased data, at232.

To illustrate, if the number of failed codewords is three (e.g., CW1, CWs, and Parity CW1), and the erasure correction capability is two, three trial versions of the first stripe codeword191ofFIG. 1may be generated for the first stripe197based on the first portions of each of the codewords160-162and the first portion175and the second portion177of the first parity data. In trial data corresponding to a first trial stripe codeword, the first portion of CW1may be included as valid data but the first portion of CWsand Parity CW1may be omitted or designated as erased data. In trial data corresponding to a second trial stripe codeword, the first portion of CWsmay be included as valid data but the first portion of CW1and Parity CW1may be omitted or designated as erased data. In trial data corresponding to a third trial stripe codeword, the first portion of Parity CW1may be included as valid data but the first portion of CW1and CWsmay be omitted or designated as erased data. Thus, multiple trial stripe codewords generated using different combinations of the failed codewords taken Z at a time, where Z is the erasure correction capability of the second ECC scheme154, may be attempted for each stripe. Because portions of failed codewords may be error-free, one or more of the trial versions of each of the stripes may be decodable (if a total number of erroneous symbols in the stripe is less than or equal to Z). An example of a method of stripe decoding using different combinations of failed codewords is described with reference toFIG. 3.

A determination is made as to whether any of the trial codewords for the kthstripe are decodable, at234. For example, one or more trial versions of the first stripe codeword191may be provided to the ECC engine136to attempt a decoding operation at the stripe decoder156, at234. A determination is made, at236, as to whether all stripes of the data structure110have been processed (i.e., if k equals the number of stripes (K) in the data structure110). If any stripes have not been processed, then the loop counter k is incremented, at238, and processing returns to generating the codeword for the next stripe, at232. Otherwise, processing returns to203to determine whether the codeword n is decodable, at203.

By first attempting decoding of each of the codewords and next attempting decoding of each stripe, individual sections of the various codewords may be error corrected. For example, correction of errors in a stripe may improve the likelihood of decoding success for one or more of the codewords160-162. Likewise, successful decoding of one of the codewords160-162further increases the probability of successful decoding of one or more of the stripes of the data structure110. Iteratively alternating between decoding columns (e.g., stripes) and decoding rows (e.g., codewords) of the data structure110enables correction of errors in one or more of the columns to increase a likelihood that one or more of the rows will become decodable. Similarly, correction of errors in one or more of the rows increases a likelihood that one or more of the columns will become decodable. Iteratively alternating between decoding columns (e.g., stripes) and decoding rows (e.g., codewords) of the data structure110can result in correction of a sufficient number of bits in the nthcodeword to enable decoding of the nthcodeword and sending of an error corrected version of the requested data to the access device170ofFIG. 1.

Referring toFIG. 3, a particular illustrative example of a method of stripe decoding using different combinations of failed codewords is depicted and generally designated300. The method300may be performed at a data storage device, such as at the data storage device102ofFIG. 1. One or more operations of the method200may be performed or initiated by the controller130, such as in response to a data write request from the access device170ofFIG. 1. As an example, the method300may be performed during generation of trial codewords and attempting erasure correction of the trial codewords at232-234of the method200ofFIG. 2.

The method300includes selecting a first combination of two failed codewords, at302. An erasure correction for the kthstripe is attempted using the selected combination of failed codewords as erasures, at304. For example, the stripe generator190ofFIG. 1may track the number “Y” of failed codewords of the data structure110that are “undecodable” by the ECC decoder154(e.g., by having a number of bit errors that exceeds an error correction capability of the ECC decoder154). The stripe generator190may select Z of the Y failed codewords as corresponding to erased data and may designate the remaining (Z−Y) failed codewords as corresponding to valid data. The resulting trial stripe data generated by the stripe generator190may be provided to the stripe decoder156for decoding.

To illustrate, an example data structure330includes five codewords and four stripes. Codeword A includes data errors at portions A1and A3, rendering codeword A undecodable at the ECC decoder154. Codeword B is error-free. Codeword C includes data errors at portions C1, C2, and C3. Codeword D includes data error at portions D2, D3and D4. Codeword E is error-free. Because codewords A, C, and D have more errors than an error correction capacity of the ECC decoder154, codewords A, C, and D are failed codewords. Thus, the number of failed codewords (Y=3) may exceed the erasure correction capacity of the stripe decoder156(Z=2). For example, designating elements of the first stripe332that correspond to failed codewords (e.g., elements A1, C1, and D1) as erased data cause the first stripe332to be undecodable by the stripe decoder156.

The stripe generator190may generate a first trial version of the first stripe by selecting failed codeword A as contributing valid data (e.g., as if A1is error-free) and designating codewords C and D as erasures to generate first trial data340. The first trial data340includes an element350that is associated with codeword A320, an element352that is associated with codeword B322, an element354that is associated with codeword C324, an element356that is associated with codeword D326, and an element358that is associated with codeword E328. The first trial data340includes at least one element that corresponds to erased data and at least another element that is associated with a failed codeword and that corresponds to valid data of the stripe. To illustrate, elements354and356correspond to erased data, and element350is associated with a failed codeword (codeword A320) but corresponds to valid (e.g., non-erased, as if A1is error-free) data of the stripe. The stripe generator190may generate a second trial version of the first stripe by selecting failed codeword C as contributing valid data (e.g., as if C1is error-free) and designating codewords A and D as erasures to generate second trial data342. The stripe generator190may generate a third trial version of the first stripe by selecting failed codeword D as contributing valid data (e.g., as if D1is error-free) and designating codewords A and C as erasures to generate third trial data344.

Because the first trial data340includes one or more errors in non-erased data (in A1) and the second trial data342also includes one or more errors in non-erased data (in C1), decoding of the first trial data340and the second trial data342fails at the stripe decoder156. However, because the third trial data344has no errors in non-erased data, the third trial data (and therefore the first stripe) is decodable at the stripe decoder156. The elements of the decoded stripe 1334are error-free, including an error-corrected version of the portion A1362and an error-corrected version of the portion C2. Codewords A and C may be updated by replacing erroneous portions A1and C1with the error-corrected versions362and364, respectively.

The method300may include determining whether the trial stripe data was corrected, at306. If the trial stripe data was corrected, a next stripe is processed, at308. Otherwise, a determination of whether all distinct combinations of the failed codewords have been tested, at310. If all distinct combinations of the failed codewords for the kthstripe have been tested (e.g., stripe decoding of each of the trial data340,342, and344has been attempted), processing advances to the next stripe, at308. Otherwise, a next combination of two failed codewords is selected, at312, and a next trial version of the kthstripe is processed at the stripe decoder156.

By generating trial versions of each of the stripes based on using different combinations of failed codewords, stripes may decoded even though the number of failed codewords (Y) exceeds the erasure correction capacity (Z). For example, stripe 1 can be decoded by designating failed codeword D as corresponding to valid data (portion D1) and failed codewords A and C as corresponding to erasure data (portions A1and C1). Stripe2can be decoded by designating failed codeword A as corresponding to valid data (portion A2) and failed codewords C and D as corresponding to erasure data (portions C2and D2). Stripe3cannot be decoded, and stripe 4 can be decoded via random error correction because the number of erroneous data portions (a single portion D4) is equal to Z/2. As a result, three of the four stripes can be corrected, leaving erroneous data remaining only in stripe 3. Because each of the modified codewords A, C, and D have a single erroneous portion (after updating data portions of the codewords based on the stripe corrections), each of the modified codewords A, C, and D are correctable at the ECC decoder154.

Although the above example uses 5 codewords, 4 stripes, Y=3, and Z=2, in other implementations any other number of codewords, number of stripes, and erasure correction capability (Z) may be used. For example, iterative information exchange as described with respect to the examples ofFIGS. 1-3may be performed between Reed-Solomon (RS) RAID decoding and LDPC decoding, and the RS RAID may be configured to recover up to Z failing pages (Z=1, 2, 3, or any other number).

In case Y>Z pages have failed LDPC decoding, a joint iterative decoding process between the LDPC and the RS RAID may be performed. For example, a RS decoding operation may be performed that traverses all the RS code stripes in a data structure. For each RS stripe with less than floor(Z/2) erroneous symbols, the errors are corrected by the RS decoder. If the RS decoding fails, then an additional step may be performed by performing up to

(YZ)=Y!Z!⁢(Y-Z)!
(where “!” indicates the factorial function) RS decoding attempts. In each such decoding attempt a different set of Z symbols out of the Y failing pages will be marked as erased. If the number of erroneous symbols in the RS stripe is less than or equal to Z, then one of these decoding attempts will succeed.

Once the “horizontal” RS decoding operation has performed the above decoding procedure on all the RS stripes, one or more of the RS stripes may have decoded successfully. In this case, the overall BER observed by the LDPC codes is reduced. Then a next “vertical” decoding operation may be initiated to traverse all the pages (e.g., rows of the data structure110or330) and performing LDPC decoding.

Once the vertical LDPC decoding operation has completed, one or more of the LDPC decodings may have reduced the BER. In this case, a next horizontal RS decoding operation may be performed. This iterative process between the horizontal RS operations and the vertical LDPC operations may continue as long as BER is reduced in each step up to full convergence and decoding of all the data pages.

Referring toFIG. 4, a particular illustrative example of a method of encoding data is depicted and generally designated400. The method400may be performed at a data storage device, such as at the data storage device102ofFIG. 1. One or more operations of the method400may be performed or initiated by the controller130, such as in response to a data write request from the access device170ofFIG. 1.

The method400includes reading codewords of a data structure from the memory, at402. For example, the controller130ofFIG. 1may read codewords of the data structure110from the memory104, as described with reference toFIG. 1. To illustrate, the controller130may route a representation of one or more of the codewords160-166to the ECC engine136. The codewords160-166may include undecodable codewords that are undecodable at the ECC decoder154according to the first correction scheme150, as described with reference toFIG. 1. At least one of the codewords (e.g., the first parity codeword164, the second parity codeword166, or both) may include parity data for multiple stripes (e.g., the first stripe197and the second stripe199) of the data structure110. In a particular aspect, the controller130ofFIG. 1may read the codewords in response to receiving a request for data from the access device170. The data may be encoded in a particular codeword (e.g., the first codeword160) of the undecodable codewords.

The method400also includes determining that a number of the undecodable codewords exceeds an erasure correction capacity of a stripe correction scheme, at404. For example, the stripe generator190ofFIG. 1may determine that a number of the undecodable codewords exceeds an erasure correction capacity of the second correction scheme152, as described with reference toFIG. 1.

The method400further includes generating trial data for a stripe of the data structure, at406. The trial data includes at least one element that corresponds to erased data and at least another element that is associated with an undecodable codeword and that corresponds to valid data of the stripe. For example, the first trial data340ofFIG. 3includes elements354and356that correspond to erased data and at least another element (element350) that is associated with a failed codeword (codeword A320) and corresponds to valid (e.g., non-erased, as if A1is error-free) data of the stripe. As another example, the stripe generator190ofFIG. 1may generate trial data for the first stripe197of the data structure110such that at least one of the undecodable codewords (e.g., the first codeword160) corresponds to erased data (e.g., the first portion171) of the first stripe197and at least another of the undecodable codewords (e.g., the Sthcodeword162) corresponds to valid data (e.g., the first portion173) of the first stripe197, as described with reference toFIG. 1. Generating the trial data may include grouping the first portion171and a first portion of one or more other codewords, including the first portion173of the Sthcodeword162to form the first stripe codeword191, as described with reference toFIG. 1. The stripe generator190may select a second number of the undecodable codewords to correspond to the erased data and may designate the first portion from the selected codewords as being erased, as described with reference toFIG. 1. The second number may equal the erasure correction capacity of the second correction scheme152.

The method400also includes initiating a stripe decode operation of the trial data using the stripe correction scheme, at408. For example, the stripe decoder156ofFIG. 1may initiate a stripe decode operation of the trial data using the second correction scheme152, as described with reference toFIG. 1.

The ECC decoder154may alternate between codeword processing using the first correction scheme150and stripe processing using the second correction scheme152. Such alternating between codeword processing and stripe processing may continue until the particular codeword (e.g., the first codeword160) is decoded, as described with reference toFIG. 1. The first correction scheme150may include a LDPC scheme, and the second correction scheme152may include the Reed-Solomon scheme. The ECC decoder154may, for each undecoded stripe (e.g., the first stripe197) of the data structure110, test different combinations of the undecodable codewords as erased data until the stripe (e.g., the first stripe197) is decoded or until all distinct combinations of the undecodable codewords as erased data have been tested.

The ECC decoder154may, in response to at least one stripe (e.g., the first stripe197) being undecodable after decode processing of the stripes (e.g., the first stripe197and the second stripe199) of the codeword (e.g., the first codeword160), initiate a decode operation of a modified version of a first undecoded codeword (e.g., the first codeword160) of the undecoded codewords according to the first correction scheme150. The modified version may include an error-corrected version of a portion (e.g., the first portion171or the second portion181) of the first undecoded codeword (e.g., the first codeword160), as described with reference toFIG. 1. For example, the decoded stripe 1334ofFIG. 3includes an error-corrected version362of the first portion (A1) of codeword A320. A modified version of codeword A320may include the error-corrected version362of the first portion (A1).

Although the controller130and certain other components described herein are illustrated as block components and described in general terms, such components may include one or more microprocessors, state machines, and/or other circuits configured to enable the data storage device102(or one or more components thereof) to perform operations described herein. Components described herein may be operationally coupled to one another using one or more nodes, one or more buses (e.g., data buses and/or control buses), one or more other structures, or a combination thereof. One or more components described herein may include one or more physical components, such as hardware controllers, state machines, logic circuits, one or more other structures, or a combination thereof, to enable the data storage device102to perform one or more operations described herein.

Alternatively or in addition, one or more aspects of the data storage device102may be implemented using a microprocessor or microcontroller programmed (e.g., by executing instructions) to perform one or more operations described herein, such as one or more operations of the methods200-400. In a particular embodiment, the data storage device102includes a processor executing instructions (e.g., firmware) retrieved from the memory device103. Alternatively or in addition, instructions that are executed by the processor may be retrieved from memory separate from the memory device103, such as at a read-only memory (ROM) that is external to the memory device103.

It should be appreciated that one or more operations described herein as being performed by the controller130may be performed at the memory device103. As an illustrative example, in-memory ECC operations (e.g., encoding operations and/or decoding operations) may be performed at the memory device103alternatively or in addition to performing such operations at the controller130.

To further illustrate, the data storage device102may be configured to be coupled to the access device170as embedded memory, such as in connection with an embedded MultiMedia Card (eMMC®) (trademark of JEDEC Solid State Technology Association, Arlington, Va.) configuration, as an illustrative example. The data storage device102may correspond to an eMMC device. As another example, the data storage device102may correspond to a memory card, such as a Secure Digital (SD®) card, a microSD® card, a miniSD™ card (trademarks of SD-3C LLC, Wilmington, Del.), a MultiMediaCard™ (MMC™) card (trademark of JEDEC Solid State Technology Association, Arlington, Va.), or a CompactFlash® (CF) card (trademark of SanDisk Corporation, Milpitas, Calif.). The data storage device102may operate in compliance with a JEDEC industry specification. For example, the data storage device102may operate in compliance with a JEDEC eMMC specification, a JEDEC Universal Flash Storage (UFS) specification, one or more other specifications, or a combination thereof.

The memory device103may include a three-dimensional (3D) memory, such as a resistive random access memory (ReRAM), a flash memory (e.g., a NAND memory, a NOR memory, a single-level cell (SLC) flash memory, a multi-level cell (MLC) flash memory, a divided bit-line NOR (DINOR) memory, an AND memory, a high capacitive coupling ratio (HiCR) device, an asymmetrical contactless transistor (ACT) device, or another flash memory), an erasable programmable read-only memory (EPROM), an electrically-erasable programmable read-only memory (EEPROM), a read-only memory (ROM), a one-time programmable memory (OTP), or a combination thereof. Alternatively or in addition, the memory device103may include another type of memory. In a particular embodiment, the data storage device102is indirectly coupled to an access device (e.g., the access device170) via a network. For example, the data storage device102may be a network-attached storage (NAS) device or a component (e.g., a solid-state drive (SSD) component) of a data center storage system, an enterprise storage system, or a storage area network. The memory device103may include a semiconductor memory device.

The semiconductor memory elements located within and/or over a substrate may be arranged in two or three dimensions, such as a two dimensional memory structure or a three dimensional memory structure. In a two dimensional memory structure, the semiconductor memory elements are arranged in a single plane or a single memory device level. Typically, in a two dimensional memory structure, memory elements are arranged in a plane (e.g., in an x-z direction plane) which extends substantially parallel to a major surface of a substrate that supports the memory elements. The substrate may be a wafer over or in which the layer of the memory elements are formed or it may be a carrier substrate which is attached to the memory elements after they are formed. As a non-limiting example, the substrate may include a semiconductor such as silicon.

A three dimensional memory array is arranged so that memory elements occupy multiple planes or multiple memory device levels, thereby forming a structure in three dimensions (i.e., in the x, y and z directions, where the y direction is substantially perpendicular and the x and z directions are substantially parallel to the major surface of the substrate). As a non-limiting example, a three dimensional memory structure may be vertically arranged as a stack of multiple two dimensional memory device levels. As another non-limiting example, a three dimensional memory array may be arranged as multiple vertical columns (e.g., columns extending substantially perpendicular to the major surface of the substrate, i.e., in they direction) with each column having multiple memory elements in each column. The columns may be arranged in a two dimensional configuration, e.g., in an x-z plane, resulting in a three dimensional arrangement of memory elements with elements on multiple vertically stacked memory planes. Other configurations of memory elements in three dimensions can also constitute a three dimensional memory array.

One of skill in the art will recognize that this disclosure is not limited to the two dimensional and three dimensional exemplary structures described but cover all relevant memory structures within the spirit and scope of the disclosure as described herein and as understood by one of skill in the art. The illustrations of the embodiments described herein are intended to provide a general understanding of the various embodiments. Other embodiments may be utilized and derived from the disclosure, such that structural and logical substitutions and changes may be made without departing from the scope of the disclosure. This disclosure is intended to cover any and all subsequent adaptations or variations of various embodiments. Those of skill in the art will recognize that such modifications are within the scope of the present disclosure.