Optimal LDPC bit flip decision

A solid state storage device comprises a non-volatile memory controller configured to store data in a non-volatile memory, wherein the stored data is encoded using a first error-correcting code and a second Low Density Parity Check (LDPC) code. The non-volatile memory controller includes a hard-decision LDPC decoder to decode encoded data received from the non-volatile memory and provide a decoded data output. The hard-decision LDPC decoder selects a voting scheme at each iteration in a sequence of iterations of decoding to determine when to implement bit flipping at a variable node amongst a plurality of check nodes, each of the plurality of check nodes connected to a plurality of variable nodes.

FIELD OF THE INVENTION

The present disclosure relates to solid-state storage devices and methods that improve the decoding capability of a Low Density Parity Check (LDPC) Decoder

BACKGROUND

Improvements in NAND flash memory technology have led to reduced solid state device geometries and increased bit density of NAND flash memories. However, the increased bit density results in an increase in error rates of data decoded from such memories. Accordingly, there has been an increase in emphasis on improving the error correction capability provided by NAND flash memory controllers. Error correction is necessary due to the nature of the technology where reliability and endurance problems increase as flash memory density increases.

A flash memory is generally organized in units of pages which are the smallest unit which are individually programmable. A block, which is the smallest unit which can be erased, is composed of multiple pages. A page of memory is provided with a spare area, which is used for the extra bits required for error-correcting code ECC, as well as other functions such as bits for keeping track of wear leveling and other metadata. The spare area was originally sized to be large enough to accommodate enough bits to provide for ECC such as BCH (Bose Chaudhuri Hocqenghem) type codes for error correction given the expected error rates of memories at the time. BCH error correction codes are extensively used to correct read errors in NAND flash memories as they can be flexibly designed to correct a precise number of errors in a block of data (meaning that data block of a given size and expected error rate can be exactly reconstructed with certainty), wherever and however they may occur (i.e. randomly distributed, in fixed patterns or in bursts). They are also relatively simple to implement decoders. As such, BCH codes could be specifically designed to work with a given flash memory data page and spare area size.

As long as the number of errors in the memory page does not exceed the correction capability of the BCH code, the original data should be decodable by the BCH code. However, such convergence places a greater requirement burden on the system processor to cope with greater error rates in more dense NAND flash memories, along with greater requirements for longer memory endurance in enterprise computing applications as opposed to consumer applications. This has meant that BCH codes have become incapable of being economically or feasibly scaled to meet the new data requirements with higher error rates. In other words, as NAND densities increase, the bit error rates (BER) in each memory cell also increase accordingly, making BCH decoding less ideal due to the limitation imposed by the maximum error rate correction capability of the BCH code.

SUMMARY OF INVENTION

The present disclosure relates to a data storage device comprising a non-volatile memory controller configured to store data in a non-volatile memory, wherein the stored data is encoded using a first error-correcting code (ECC) and a second Low Density Parity Check (LDPC) error-correcting code code. The non-volatile memory controller including a hard-decision LDPC decoder to decode encoded data received with errors from the non-volatile memory and provide a decoded data output. Further the hard-decision LDPC decoder selecting a voting scheme at each iteration in a sequence of iterations of decoding to determine when to implement bit flipping at a variable node amongst a plurality of check nodes, each of the plurality of check nodes connected to a plurality of variable nodes.

In certain implementations, the hard-decision LDPC decoder reduces the number of errors in the decoded data to give partially decoded data containing errors where the first error-correcting code is capable of fully correcting the errors contained in the partially decoded data. This provides for a hybrid decoder that benefits from hard-decision LDPC decoding and ECC decoding. In other implementations, the solid state storage device further comprises an ECC decoder which completely decodes the partially decoded data containing errors to give fully decoded data containing no errors. In some implementations, the ECC decoder is a Bose-Chaudhuri-Hocquenghem (BCH) decoder.

In certain implementations, the LDPC decoder selects the voting scheme based on majority voting with a vote count offset with an adjustment value. In other implementations, the adjustment value is dependent on an iteration sequence number of the iteration in the sequence of iterations used by the hard-decision LDPC decoder. In some implementations, the adjustment value is predetermined. In certain implementations, the adjustment value for the first iteration is 1, the adjustment value for the last iteration is 0, and the adjustment value for each of the iterations between the first and last iterations is −1.

In some implementations, the hard-decision LDPC decoder flips the vote on a variable node from a previous iteration when 2F>N+1+Vit, wherein F is the number of votes to flip on the check nodes and the variable node connected to the check nodes, N is the number of connected check nodes connected to a variable node, and Vitis an adjustment value at iteration it. In certain implementations, the hard-decision LDPC decoder retains the vote on a variable node from a previous iteration when 2F=N+1+Vit, wherein F is the number of votes to flip on the check nodes and the variable node connected to the check nodes, N is the number of connected check nodes connected to a variable node, and Vitis an adjustment value at iteration it. In other implementations, the hard-decision LDPC decoder does not flip the vote on a variable node from a previous iteration when 2F<N+1+Vit, wherein F is the number of votes to flip on the check nodes and the variable node connected to the check nodes, N is the number of connected check nodes connected to a variable node, and Vitis an adjustment value at iteration it.

The present disclosure also relates to a method of improving the decoding of data encoded with first error-correcting code (ECC) and a second Low Density Parity Check (LDPC) error-correcting code, implemented in a non-volatile memory having a non-volatile memory controller configured to store data in the non-volatile memory. The method comprises selecting a voting scheme at each iteration in a sequence of iterations of hard-decision LDPC decoder of the second LDPC error-correcting code to determine when to implement bit flipping at a variable node amongst a plurality of check nodes, each of the plurality of check nodes connected to a plurality of variable nodes.

In some implementations, the hard-decision LDPC decoder reduces the number of errors in the decoded data to give partially decoded data containing errors which the first error-correcting code can correct. In other implementations, the non-volatile memory further comprises an ECC decoder which completely decodes the partially decoded data containing errors to give fully decoded data containing no errors. In certain implementations, the ECC decoder is a Bose-Chaudhuri-Hocquenghem (BCH) decoder. In some implementations, the LDPC decoder selects the voting scheme based on majority voting with a vote count offset with an adjustment value. In other implementations, the adjustment value is dependent on an iteration sequence number of each iteration in the sequence of iterations used by the hard-decision LDPC decoder. In certain implementations, the adjustment value is predetermined. In certain implementations, the adjustment value for the first iteration is 1, the adjustment value for the last iteration is 0, and the adjustment value for each of the iterations between the first and last iterations is −1.

In some implementations, the hard-decision LDPC decoder flips the vote on a variable node from a previous iteration when 2F>N+1+Vit, wherein F is the number of votes to flip on the check nodes and the variable node connected to the check nodes, N is the number of connected check nodes connected to a variable node, and Vitis an adjustment value at iteration it. In certain implementations, the hard-decision LDPC decoder retains the vote on a variable node from a previous iteration when 2F=N+1+Vit, wherein F is the number of votes to flip on the check nodes and the variable node connected to the check nodes, N is the number of connected check nodes connected to a variable node, and Vitis an adjustment value at iteration it. In other implementations, the hard-decision LDPC decoder does not flip the vote on a variable node from a previous iteration when 2F<N+1+Vit, wherein F is the number of votes to flip on the check nodes and the variable node connected to the check nodes, N is the number of connected check nodes connected to a variable node, and Vitis an adjustment value at iteration it.

Further, the present disclosure also relates to a solid state storage device comprising a non-volatile memory controller configured to store data in a non-volatile memory, wherein the stored data is encoded using a first error-correcting code and a second Low Density Parity Check (LDPC) error-correcting code. The non-volatile memory controller includes a hard-decision LDPC decoder to decode encoded data received from the non-volatile memory to generate partially decoded data which the first error-correcting code can correct. The non-volatile memory controller also includes a decoder of the first error-correcting code that receives the partially decoded data containing errors and generates fully decoded data containing no errors. Further, the non-volatile memory controller includes the hard-decision LDPC decoder selecting a voting scheme at each iteration in a sequence of iterations of decoding to determine when to implement bit flipping at a variable node amongst a plurality of check nodes, each of the plurality of check nodes connected to a plurality of variable nodes.

Variations and modifications will occur to those of skill in the art after reviewing this disclosure. The disclosed features may be implemented, in any combination and subcombination (including multiple dependent combinations and subcombinations), with one or more other features described herein. The various features described or illustrated above, including any components thereof, may be combined or integrated in other systems. Moreover, certain features may be omitted or not implemented.

DETAILED DESCRIPTION

Complex LDPC decoding schemes have been proposed, such as that described in U.S. patent application Ser. No. 14/325,256, the contents of which is hereby incorporated by reference in its entirety. Such decoders use a voting scheme that uses LDPC syndrome values as a way to dynamically adjust a voting algorithm for LDPC decoding. Such dynamic adjustment varies a strength requirement for bit flipping within a hard-decision LDPC decoder. However, the disadvantage of such a decoding scheme is its overall complexity, and that its dependence on the LDPC syndrome value means that the syndrome value needs to be calculated for all check and variable nodes of the LDPC matrix.

FIG. 1illustrates a general solid state drive (SSD) flash memory100communicatively coupled to at least one host device110via an interface bus115(which may be SATA, SCSI, SAS, PCIe or similar). The SSD100comprises a flash memory controller120comprising an error correction encoder and decoder, shown inFIG. 1as error correction encoder125and error correction decoder121. The error correction decoder121comprises an Encryption and Error Correction Code (ECC) decoder122communicatively coupled to a hard-decision LDPC decoder123and a soft-decision LDPC decoder124. The ECC decoder122may also include a BCH error corrector or any other cyclic error corrector. The hard-decision LDPC decoder123may also be provided with voting method adjustment. The error correction decoder125may comprise an LDPC encoder and an ECC encoder. Data to be written to the flash memory bank170is encoded by the encoder125by encoding with an ECC code in a first instance to give ECC-encoded data. The ECC-encoded data is then further encoded with an LDPC code in a second instance to give the fully encoded data. In order to improve the overall decoding capability of the decoder121, the hard-decision LDPC decoder123first decodes the fully encoded data, providing a partially decoded output which still contains errors. This partially decoded output is then passed to the ECC decoder122where any remaining errors are corrected by the ECC decoder122. It will be understood that the hard-decision LDPC decoder123selects a specific voting scheme at each iteration so as to ensure that the ECC decoder122is capable of fully correcting the number of errors in the partially decoded output from the hard-decision LDPC decoder123.

In one implementation, a data page is passed through the hard-decision LDPC decoder123, then a BCH error corrector included in the hard decision LDPC decoder123or alternatively, if required, the soft-decision LDPC decoder124. The interface bus115is coupled to the controller120via a processor130. In turn, the controller120is coupled to a flash memory bank170comprising a plurality of flash memories171-174. The number of flash memory devices may vary according to the storage capacity of the individual devices and the SSD as a whole, but would typically be a power of 2 such as 4, 8, 16, 32 devices and so on.

The flash memory controller120may comprise a single semiconductor device with on-chip ROM for firmware storage150and RAM for working data structures and buffers, but there may also be provided a memory buffer140for additional space for large data translation tables and look-up tables. Alternatively, the on-chip ROM for firmware storage may be a NOR flash150so as to provide upgradeable firmware storage. To provide the various voltages required by the flash memory controller120and external memories171-174, power regulation circuitry160may also be provided and which may also include provision for backup power using large capacitors in order to safely manage the shutdown of the SSD100in the event of sudden power removal or failure.

In a general implementation, upon receipt of a write command from a host device110, the encoder125encodes data d transmitted from the host device110to the SSD100prior to storing the encoded data in the flash memory bank170. In order to encode the data, the encoder125uses a generator matrix G to produce a codeword c, where c=Gd. The codeword is then stored in the flash memories171-174within the flash memory bank170. Upon receipt of a read command from a host device110, a codeword c′ is retrieved from the flash memories171-174. The codeword c′ contains information related to the requested data in the read command. The retrieved codeword c′ is received by the controller120and generally corresponds to an altered version of the codeword c output by the encoder125due to the presence of errors. The retrieved codeword c′ is fed into the decoder121where the decoder uses a parity check matrix H and a decoding scheme iteratively to reduce the errors in the requested data d. The decoding scheme used, and hence the parity check matrix H utilized, is dependent whether the ECC decoder122, the hard-decision LDPC decoder123or the soft-decision LDPC decoder124is used to recover the requested data d. According to an implementation of the present disclosure, hard decision LDPC decoding reduces the errors in the retrieved codeword c′ to give partially decoded codeword c″ where Hc″≠0. The partially decoded codeword c″ is then fully decoded using BCH decoding, to recover data d without any errors.

FIG. 2illustrates communications between variable nodes210-215representing a sampled codeword and check nodes220-224for decoding the codeword according to an implementation of the present disclosure. The variable nodes210-215and the check nodes220-224are connected via connectivity matrix240representing the LDPC parity check matrix H. The values on the variable nodes210-215are selected such that at any given check node220-224the XOR sum of the values (termed the syndrome value) on the variable nodes connected to a check node is 0. For example, for check node220, the values x1, x3and x4, on variable nodes210,212and213, respectively, are such that x1⊕x3⊕x4=0, i.e. the syndrome value at check node220is 0. As a further example, for check node223, the values x1and x6on variable nodes210and215, respectively, are such that x1⊕x6=0, i.e. the syndrome value at check node223is 0.

According to an implementation of the present disclosure, for hard-decision LDPC bit flipping, the hard-bit decision process can be thought of as a set of check nodes connected to a variable node, where each of the check nodes vote to (i) flip the bit on the variable node, (ii) retain the flip (or non-flip) on the variable node from the previous iteration of the LDPC decoding, or (iii) not flip the bit on the variable node and maintain it at its present value. LDPC decoders adopting hard decision bit flipping use majority voting where at each iteration of the decoding process, for each check node, the connectivity matrix240is followed and the XOR sum (i.e. syndrome value) calculated of variable node bits directly connected to the check-node. As previously discussed, if all XOR sums for the current iteration are 0, the decoding process ends with a successful hard decision LDPC decode.

In certain implementations of the present disclosure, the decoding process includes that at each iteration of the decoding process, adjusted majority voting for each variable node is used where the syndrome values on the check nodes directly connected to a variable node in question are used as ‘votes’ to determine if the bit on the variable node should be flipped, maintained at its current value, or non-flipped. For N check nodes connected to a variable node, there will be a total of N+1 votes, N votes from the check nodes and 1 vote from the current flip status of the variable node. Of these there will be F votes in favor of flipping the variable node bit. According to the hard decision LDPC decoding scheme of the present disclosure, for each iteration of the LDPC decoding, a vote on a variable node is flipped at the next iteration if F is greater than an adjusted majority vote, i.e. when
2F>N+1+Vit,  (1)
where Vitis an adjustment value. Further, a vote on the variable node is maintained at the next iteration if
2F=N+1+Vit,  (2)
and a vote on the variable node is not flipped if
2F<N+1+Vit.  (3)
The adjustment value Vitis an integer offset to the simple majority vote for each iteration and is predetermined. Vitmay vary at each iteration of the decoding process.

The hard decision LDPC voting scheme will now be illustrated with respect toFIGS. 3A-C.FIGS. 3A-Cillustrate sequential iterations of a hard decision LDPC decoding process whereFIG. 3Acorresponds to the first iteration,FIG. 3Bcorresponds to the second iteration, andFIG. 3Ccorresponds to the third iteration. The adjustment values Vitfor the three sequential iterations inFIG. 3are {1, 0, −1}.FIG. 3Aillustrates five check nodes301-305connected to a variable node306. The current syndrome values on the check nodes301-305are {1, 1, 0, 0, 1} and the current value of the bit on the variable node306is ‘1’. InFIG. 3Athis bit value is shown as 10to indicate that the bit value of ‘1’ on the variable node306is from the current iteration of decoding. Thus, for Iteration 1 inFIG. 3A, N=5, Vit=1 and F=3. This means that 2F=6 and N+1+Vit=7. According to the adjusted majority voting scheme of the hard bit LDPC decoder of the present disclosure, equation (3) applies and the current value of the bit on the variable node306is returned to a ‘0’ don't flip state. This is shown as 01inFIG. 3Ato indicate that the value of the bit on variable node306is returned to ‘0’ for Iteration 1.

FIG. 3Billustrates the decoding Iteration 2 immediately following that depicted inFIG. 3A. Here, the current value on the variable node306is shown as 01to indicate that the bit value is ‘0’ as set in Iteration 1. For Iteration 2, N=5, Vit=0 and F=3. This means that 2F=6 and N+1+Vit=6. According to the adjusted majority voting scheme of the hard bit LDPC decoder of the present disclosure, equation (2) applies and the current value of the bit on the variable node306is retained at a ‘0’ don't flip state. This is shown as 02inFIG. 3Bto indicate that the value of the bit on variable node306is retained from Iteration 1 (set at 01) at ‘0’.FIG. 3Cillustrates the decoding Iteration 3 immediately following that depicted inFIG. 3B. The current value on the variable node306is shown as 02to indicate that the bit value is ‘0’ as set in Iteration 2. For Iteration 3, N=5, Vit=−1 and F=3. This means that 2F=6 and N+1+Vit=5. According to the adjusted majority voting scheme of the hard bit LDPC decoder of the present disclosure, equation (1) applies and the current value of the bit on the variable node306is flipped to a ‘1’. This is shown as 13inFIG. 3Cto indicate that the value of the bit on variable node306is flipped (set at 13) to ‘1’.

It should be noted that while the syndrome values of the check nodes301-305for Iterations 1-3 inFIGS. 3A-Care shown to be constant at {1, 1, 0, 0, 1}, it may be the case that the syndrome values for check nodes301-305vary from iteration to iteration. This can be seen in the examples shown in Table 1 below.

The adjustment value Vitin the foregoing examples have taken the values of {1, 0, −1} for the three example iterations shown inFIGS. 3A-C. These adjustment values have been shown to be optimum for hard decision LDPC decoding.FIG. 4illustrates simulation results for various adjustment values {2, 1, 0, −1, −2} for seven iterations of LDPC decoding using a FujiXpress Gen2 decoder. The simulations show the variation of frame/page error rates (FER) with hard bit BER for various adjustment values and seven iterations of LDPC decoding. According toFIG. 4, rightmost curve shows the best combination of adjustment values that give the lowest FER. Hence the optimal adjustment values to use are {1, −1, . . . −1, 0} where V=1 for the first iteration, Vit=0 for the last iteration, and Vit=−1 for iterations between the first and last.

As can be seen from equations (1)-(3), the bit flipping LDPC decoding scheme of the present disclosure is based on the simple formulation of decision and optimal iteration specific decision parameters.

A process flow for hard decision LDPC decoding using adjusted majority voting at each iteration of decoding will now be described in relation toFIG. 5. The process500begins at step S510where the adjusted majority vote Q is calculated, where Q=½(N+1+Vit). In step S520, the total vote on the check nodes F is then determined and compared against Q. If F>Q, the bit value on the variable node is flipped. Else, if F<Q, the bit value on the variable node is not flipped, as shown in step S540. Else, if F=Q, as in step S550, the bit value on the variable node is retained from its value on the previous iteration.

The foregoing is merely illustrative of the principles of the disclosure, and the apparatuses can be practiced by other than the described implementations, which are presented for purposes of illustration and not of limitation. Variations and modifications will occur to those of skill in the art after reviewing this disclosure. The disclosed features may be implemented, in any combination and subcombination (including multiple dependent combinations and subcombinations), with one or more other features described herein. The various features described or illustrated above, including any components thereof, may be combined or integrated in other systems. Moreover, certain features may be omitted or not implemented.

Examples of changes, substitutions, and alterations are ascertainable by one skilled in the art and could be made without departing from the scope of the information disclosed herein. All references cited herein are incorporated by reference in their entirety and made part of this application.

Other objects, advantages and embodiments of the various aspects of the present invention will be apparent to those who are skilled in the field of the invention and are within the scope of the description and the accompanying Figures. For example, but without limitation, structural or functional elements might be rearranged consistent with the present invention. Similarly, principles according to the present invention could be applied to other examples, which, even if not specifically described here in detail, would nevertheless be within the scope of the present invention.