Bit flipping decoder based on soft information

Methods, systems, and apparatuses include receiving a codeword stored in a memory device. Energy function values are determined for bits of the codeword based on soft information for the bits of the codeword. A bit of the codeword is flipped when the energy function values for a bit of the codeword satisfies a bit flipping criterion. A corrected codeword that results from the flipping of the bits is returned.

TECHNICAL FIELD

The present disclosure generally relates to error correction in memory devices, and more specifically, relates to bit flipping decoders based on soft information.

BACKGROUND ART

DETAILED DESCRIPTION

A memory device can be a non-volatile memory device. A non-volatile memory device is a package of one or more dice. One example of non-volatile memory devices is a negative-and (NAND) memory device. Other examples of non-volatile memory devices are described below in conjunction withFIG.1. The dice in the packages can be assigned to one or more channels for communicating with a memory subsystem controller. Each die can consist of one or more planes. Planes can be grouped into logic units (LUN). For some types of non-volatile memory devices (e.g., NAND memory devices), each plane consists of a set of physical blocks, which are groups of memory cells to store data. A cell is an electronic circuit that stores information.

Depending on the cell type, a cell can store one or more bits of binary information, and has various logic states that correlate to the number of bits being stored. The logic states can be represented by binary values, such as “0” and “1”, or combinations of such values. There are various types of cells, such as single-level cells (SLCs), multi-level cells (MLCs), triple-level cells (TLCs), and quad-level cells (QLCs). For example, a SLC can store one bit of information and has two logic states.

Low-Density Parity Check (LDPC) codes are commonly used for enabling error correction in memory subsystems. LDPC codes are a class of highly efficient linear block codes that include single parity check (SPC) codes. LDPC codes have a high error correction capability and can provide performance close to Shannon channel capacity. LDPC decoders utilize a “belief propagation” algorithm, which is based on the iterative exchange of reliability information, e.g., “beliefs.” The MinSum algorithm (MSA), which is a simplified version of the belief propagation algorithm, can be used for decoding LDPC codes. MSA-based decoders use a relatively high amount of energy per bit (e.g., pico-joule per bit) for decoding codewords and hence are not well suited for energy conscious applications (such as mobile applications). Bit Flipping (BF) decoders have been introduced to address this problem. BF decoders use less energy per bit. However, BF decoders provide lower error correction capability when compared to the error correction capability of MSA-based decoders.

A hard read is a read operation to distinguish between the multiple states to which a memory cell may be programmed A hard read returns hard data, e.g., a digit (“0” or “1”) corresponding to the state determined by the read operation. Soft data associated with a read can be data other than the hard data obtained from the read operation. Some error-correcting code schemes use hard data (e.g., the bits of the codeword itself) to detect and correct errors in a codeword. Other error-correcting code schemes can use hard and soft data to decode a codeword. For example, a typical flow of error correction can include: 1) using a BF decoder on hard data bits (i.e., the codeword as obtained from a hard read), 2) followed with using an MS-based decoder with the hard data bits if the BF decoder fails to correct the codeword, 3) followed with using another error handling process with hard data bits when the MS-based decoder fails, and 4) finally using the MS-based decoder with soft information when the error handling process fails. In other words, soft information is not used until last stages of the error correction flow as it is costly to generate and retrieve the soft information due to the number of reads needed for the generation and the amount of information that needs to be transferred from the memory device through a single channel that is shared between multiple dice. Thus, the use of soft information in error correction can slow down the error correction process, consume bandwidth and impact memory throughput. Further, BF decoders use hard data for decoding codewords and do not use soft data.

Aspects of the present disclosure address the above and other deficiencies by improving the error correction capability of BF decoders. The codeword error rate (CWER) is significantly reduced where CWER refers to the rate (probability) at which a BF decoder fails to correct errors and a sequence of error recovery steps is triggered. Embodiments described herein improve error correction capabilities of BF decoders by using soft information. In some embodiments, the BF decoders use less bits of soft information than the number of bits of the codeword for decoding the codeword, consequently avoiding consumption of large amounts of bandwidth for the transfer of the soft information from the memory device and without major impact on the memory subsystem's throughput.

A memory subsystem controller115(or controller115for simplicity) can communicate with the memory devices130to perform operations such as reading data, writing data, or erasing data at the memory devices130and other such operations (e.g., in response to commands scheduled on a command bus by controller115). The memory subsystem controller115can include hardware such as one or more integrated circuits and/or discrete components, a buffer memory, or a combination thereof. The hardware can include digital circuitry with dedicated (i.e., hard-coded) logic to perform the operations described herein. The memory subsystem controller115can be a microcontroller, special purpose logic circuitry (e.g., a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), etc.), or another suitable processor.

The memory subsystem110includes an error corrector113that can perform error correction based on a bit flipping mechanism which considers soft data. In some embodiments, the controller115includes at least a portion of the error corrector113. For example, the controller115can include a processor117(processing device) configured to execute instructions stored in local memory119for performing the operations described herein. In some embodiments, an error corrector113is part of the host system120, an application, or an operating system.

In some embodiments, the error corrector113is operative to encode and decode data stored in the memory device (e.g., an encoder and/or decoder). Encoding data using an error correcting code (ECC) allows for correction of erroneous data bits when the data is retrieved from the memory device. For example, the error corrector113can encode data received from the host system120and store the data and parity bits as codewords in the memory device130. The error corrector113can further be operative to decode data stored in the memory device130to identify and correct erroneous bits of the data before transmitting corrected data to the host system120. Although illustrated as a single component that can perform encoding and decoding of data, the error corrector113can be provided as separate components. In some embodiments, the error corrector113is operative to encode data according to a Low-density parity-check (LDPC) code. The error corrector113is operative to decode the codewords stored in the memory device130based on a BF decoder. As described below, the error corrector113implements an enhanced BF decoder that can perform bit flipping decoding based on soft data.

In one embodiment, the error corrector113receives a codeword stored in a memory device. The error corrector113error corrects the codeword in a set of iterations, e.g., by flipping bits for one or more iterations. The bits are flipped according to soft data for the bits and a bit flipping criterion. Further details with regards to the operations of the error corrector113are described below.

In some embodiments, a BF decoder defines an energy function for a bit of a codeword. An energy function assigns an energy function value to each codeword bit. An energy function value of a codeword bit can be considered an indication of reliability information for the codeword bit. In some embodiments, an energy function value of a codeword bit can be determined based on a number of parity violations per codeword bit and channel information. The channel information is determined based on a current state of the bit (after one or more iterations of the BF decoder) versus the bit that was read from a memory device (also referred to as hard bit). In some embodiments, a high energy function value of a bit (e.g., an energy function value that is greater than or equal to a threshold) is indicative of a more reliable bit and a low energy function value of a bit (e.g., an energy function value that is less than the threshold) is indicative of a less reliable bit. In some embodiments, an energy function is defined such that when the current state of the bit agrees with the bit that was read from the memory device, the bit is considered to be more reliable (e.g., the energy function value of that bit is increased based on whether the current state of the bit and the hard bit agree) and when the current state of the bit does not agree with the bit that was read from the memory device, the bit is considered to be less reliable (e.g., the energy function value of that bit is decreased). A BF decoder flips least reliable bits first. While embodiments will be described with a BF decoder where high energy function values of bits are indicative of high reliable bits and low energy function values are indicative of less reliable bits and the BF decoder flips bits that have lower energy function values, other embodiments can be contemplated. For example, in some instances, high energy function values of bits can be indicative of less reliable bits and low energy function values are indicative of high reliable bits. In this exemplary embodiment, a BF decoder flips least reliable bits first, i.e., bits that have higher energy function values. As it will be described in further detail below, the error corrector113implements a BF decoder that is operative to use soft information to error correct codewords.

At operation205, the processing device receives a codeword from a memory device. In some embodiments, the codeword is received as a result of a read operation from a host system120. The codeword can include a combination of data bits and parity check bits. The parity check bits are stored in the memory device for the data bits. The data bits and parity check bits are hard data bits that result from a hard read on a memory cell to determine the state of the memory cell (e.g., “0” or “1”).

At operation210, the processing device optionally receives soft information for the codeword. The soft information can include bits received from the memory device in addition to the bits of the codeword. In some embodiments, the memory device is operative to determine soft information for a hard read. In other embodiments, the memory device does not generate and does not transmit the soft information to the processing device. In some embodiments, the memory device generates and transmits soft information for some but not all codewords it transmits to the processing device. Soft information can indicate a confidence level with regards to a hard data bit. For example, soft information can indicate that there is a high confidence level with regards to a hard data bit and the hard data bit can be referred to as a strong bit. Alternatively, soft information can indicate that there is a low confidence level in the hard data bit and the hard data bit is referred to as a weak bit. In some embodiments, soft information can be indicative of a particular voltage to which the memory cell is charged (where the memory cell is the one from which the hard data bit is read). In these embodiments, a hard data bit is less reliable (i.e., a weak bit) when its associated soft information is indicative of the memory cell is charged to a particular voltage that is near a boundary between two states; and a hard data bit is more reliable (i.e., a strong bit) when its associated soft information indicates that the memory cell is charged to a particular voltage near the center of a voltage range corresponding to a state (“0” or “1”). In some embodiments, the soft information can include at most a soft bit for each bit of the hard data bit of the codeword. The soft bit of a hard data bit is indicative of whether the hard data bit is a strong or a weak bit. For example, the soft bit can be “0” when its associated hard data bit is weak and “1” when its associated hard data bit is strong. In some embodiments, the number of bits of soft information for a codeword is strictly less than the number of bits of the codeword. For example, the processing device can receive the indices of the strong bits in the codeword. Alternatively, the processing device can receive the indices of the weak bits in the codeword to reduce the amount of information transferred from memory device140to error corrector113. In some embodiments, the soft information can include more than one soft bit for each bit of the hard data bit of the codeword. For example, when the soft information includes two soft bits, this results in four reliability levels for a bit such as very weak, weak, strong, and very strong.

At operation215, the processing device determines whether the soft information is available for the codeword. The soft information is available for the codeword when the processing device receives the soft information from the memory device. The soft information is not available for the codeword when they are not received from the memory device. In response to determining that soft information is available for the codeword, the flow of operations moves to operation220. Alternatively, in response to determining that soft information is not available for the codeword, the flow of operations moves to operation240.

At operation240, the processing device determines energy function values for bits of the codeword without soft information for the bits of the codeword. An energy function of a codeword bit can be considered an indication of reliability information for the bit. The processing device can determine an energy function value for a bit of the codeword based on the number of satisfied parities for the bit and channel information for that bit. In some embodiments, a higher number of satisfied parities for a bit is an indication of a more reliable bit and results in a higher energy function value for the bit. Additionally, a lower number of satisfied parities for the bit is an indication of a less reliable bit and results in a lower energy function value for the bit. The channel information is determined based on a current state of the bit as compared to the state of the bit when it was read from a memory device. For example, the channel information of a bit can be defined as an XOR of the current state of the bit, which may have been flipped during one or more iterations of decoding, and the bit read from the memory device. When the current state of the bit agrees with the bit that was read from the memory device, the bit is considered to be more reliable. Therefore, an energy function value of a bit is greater when the current state of the bit agrees with the hard bit received from the memory device than when the current state of the bit does not agree with the hard bit. In some embodiments, an energy function of a bit can be determined by adding a number of satisfied parities of the bit with channel information for the bit. In a non-limiting example, an energy function can be determined according to equation (1):
e(bit)=NumberSatisfiedParities(bit)+Channel information(bit)  (1)

Where higher e(bit) indicates a more reliable bit and lower e(bit) indicates a less reliable bit.

In one embodiment, the processing device determines the energy function value of a bit of the codeword by retrieving the energy function value from a look up table based on the number of satisfied parity bits and whether there is a match or a mismatch between the current state of a bit and the hard bit received from the memory device.FIG.3illustrates a block diagram of an exemplary lookup tables that can be used for determining energy function values of a bit of a codeword, in accordance with some embodiments. AlthoughFIG.3illustrates particular examples of number of satisfied parities and energy function values of a bit of a codeword, the illustrated examples should be understood only as examples, other energy function values and/or satisfied parity numbers are possible. Table330includes exemplary energy function values that can be used for bits of a codeword without soft information. The processing device determine an energy function value for a bit based on its associated number of satisfied parities and channel information. For example, if a bit of the codeword has 4 satisfied parities and its current state is mismatched with the hard bit received from the memory device, the processing device determines that the energy function value of the bit is 10. In another example, if a bit of the codeword has 4 satisfied parities and its current state matches with the hard bit received from the memory device, the processing device determines that the energy function value of the bit is 12. In some embodiments, the energy function values associated without soft information are considered default energy function values.

Returning to the operations ofFIG.2, when the processing device determines that soft information is available for the codeword, the flow of operations moves to operation220. At operation220, the processing device determines energy function values for the bits of the codeword based on soft information. The processing device can determine an energy function value for a bit of the codeword based on the number of satisfied parities for the bit, channel information for that bit, and further based on the soft information associated with the bit. In some embodiments, an energy function value of a bit can be determined as described above and adjusted according to the soft information and the channel information. For example, the energy function value of a bit e(bit) can be determined according to equation (1) and the processing device determines based on whether the current state of the bit matches or not the hard bit whether to add an offset, subtract an offset, or not apply the offset. In one embodiment, the offset is added to the default energy function for a bit to increase the energy function value when the soft information indicates that the bit is strong, and the current state of the bit matches the hard bit that is received from the memory device. Additionally, the offset is subtracted from the default energy function value when the soft information indicates that the bit is strong, and the current state of the bit does not match the hard bit. Further, when the soft information indicates that the bit is weak, no offset is applied, and the energy function value of the bit is the default energy function value. While embodiments are described with an offset applied when the soft information indicates that a bit is strong, in other embodiments, the offset is applied with the soft information indicates that a bit is weak.

In one embodiment, the processing device determines the energy function value of a bit of the codeword by retrieving the energy function value from a look up table based on the number of satisfied parity bits, whether there is a match or a mismatch between the current state of a bit and the hard bit received from the memory device, and further based on the soft information associated with the bit. Table320ofFIG.3includes exemplary energy function values that can be used for bits of a codeword based on soft information. The processing device determines an energy function value for a bit based on its associated number of satisfied parities, whether the state of bit matches or not the hard bit, and based on whether the soft information indicates that the hard bit is strong or weak. In the illustrated example, the energy function values associated with weak bits are the default energy function values (that correspond to the energy function values of table320). Thus, when the hard bit is weak, the energy function value of the bit is determined based on the number of satisfied parities and whether there is a match or mismatch. For example, if a bit of the codeword has 4 satisfied parities and its current state is mismatched with the hard bit received from the memory device and its soft information indicates that it is weak, the processing device determines that the energy function value of the bit is 10. In another example, if a bit of the codeword has 4 satisfied parities, its current state matches with the hard bit received from the memory device and its soft information indicates that it is weak, the processing device determines that the energy function value of the bit is 12. In contrast, the energy function values associated with strong bits are adjusted by adding or subtracting an offset to the default energy function values. When the hard bit is strong, the processing device determines the energy function value of the bit by adding the offset to the default energy function value when there is a match between the hard bit and the current state of the bit. Additionally, when the hard bit is strong, the processing device determines the energy function value of the bit by subtracting the offset from the default energy function value when there is a mismatch between the hard bit and the current state of the bit. For example, if a bit of the codeword has 4 satisfied parities and its current state is mismatched with the hard bit received from the memory device and its soft information indicates that it is strong, the processing device determines that the energy function value of the bit is 8 (which is the default energy function value 10 from which an offset of 2 is subtracted). In another example, if a bit of the codeword has 4 satisfied parities, its current state matches with the hard bit received from the memory device and its soft information indicates that it is strong, the processing device determines that the energy function value of the bit is 14 (which corresponds to the default energy function value 10 to which an offset of 2 is added). Adjusting the energy function value of a bit based on the soft information for the bit allows the processing device to distinguish between strong bits and weak bits and reinforces the reliability of the strong bits. For example, increasing the energy function of a strong bit when there is match increases the reliability of the bit and is likely to cause the processing device to not flip that bit and decreasing the energy function of the strong bit when there is mismatch decreases the reliability of the bit and can cause the decoder to flip that bit. The adjustment of the energy function values based on soft information increases correction capability of a BF decoder.

At operation225, the processing device flips zero or more bits of the codeword when the energy function values for a bit of the codeword satisfies a bit flipping criterion. The processing device traverses the codeword according to a predetermined order and evaluates each bit of the codeword based on its associated energy function value to determine whether to flip the bit or not. When the energy function value of a bit of the codeword does not satisfy the bit flipping criterion, the processing device does not flip the bit. When the energy function value of a bit of codeword satisfies the bit flipping criterion, the processing device flips the bit. In some embodiments, the bit flipping criterion is a bit flipping threshold. The processing device determines to flip a bit when the energy function value of the bit satisfies the bit flipping threshold. For example, the processing device can determine to flip a bit when the energy function value of the bit is less than or equal to the bit flipping threshold and to not flip the bit when the energy function value of the bit is greater than the bit flipping threshold.

At operation230, the processing device determines whether a stop criterion is satisfied. A stop criterion can include an indication that no errors are detected for the codeword. In some embodiments, the stop criterion can include a null syndrome (i.e., zero unsatisfied parities) indicating that the codeword no longer includes erroneous bits. In some embodiments, the stop criterion can include a maximum number of iterations or a maximum amount of time. For example, the processing device is operative to perform the maximum number of iterations (e.g., 30 iterations, 40 iterations, 100 iterations, etc.), and when this number of iterations is reached, the processing device outputs the resulting corrected codeword. When the stop criterion is not satisfied, the processing device performs another iteration. For example, when the stop criterion is not satisfied, the processing device moves to operation215, at which it determines if soft information is available for the codeword before the subsequent iteration. When soft information is available, the processing device performs operations220,225, and230as described above. In another example, the processing device can use the previous determination at operation215and return either to operation220or operation240, depending on the availability of soft information, and proceed with the next iteration. When the stop criterion is satisfied, the flow of operations moves to operation235. At operation235, the processing device outputs the corrected codeword (or an indication of failure if the processing device was unable to decode the codeword). For example, the processing device can transmit the corrected codeword or the indication of failure to the host120.

At operation405, the processing device receives a codeword from a memory device. In some embodiments, the codeword is received as a result of a read request from a host system120. The codeword can include a combination of data bits and parity check bits. The parity check bits are stored in the memory device for the data bits. The data bits and parity check bits are hard data bits that result from a hard read on a memory cell to determine the state of the memory cell (e.g., “0” or “1”). In some embodiments, the processing device also receives soft information for the codeword as described above.

At operation410, the processing device determines energy function values for bits of the codeword based on soft information for the bits of the codeword. In some embodiments, the energy function value of a bit can be determined according to a default energy function value that is adjusted or not based on whether the bit is a strong bit or a weak bit. The energy function value of a bit can be adjusted by adding an offset, subtracting an offset, or not applying the offset. In one embodiment, the offset is added to the default energy function for a bit to increase the energy function value when the soft information indicates that the bit is strong, and the current state of the bit matches the hard bit that is received from the memory device. Additionally, the offset is subtracted from the default energy function value when the soft information indicates that the bit is strong, and the current state of the bit does not match the hard bit. Further, when the soft information indicates that the bit is weak, no offset is applied, and the energy function value of the bit is the default energy function value. The determination of the energy function values can be performed as described above.

At operation415, the processing device flips a bit of the codeword when the energy function values for a bit of the codeword satisfies a bit flipping criterion. Flipping the bits can be performed as described above. When a bit of codeword does not satisfy the bit flipping criterion, the bit is not flipped. When a bit of codeword does satisfies the bit flipping criterion, the bit is flipped.

At operation420, the processing device returns a corrected codeword that results from the flipping of the bits of the codeword. In some embodiments, the corrected codeword is output to a host in response to a request to read data from the memory device. In other embodiments, the corrected codeword can be used in another iteration of the BF decoder. For example, operation410,415, and420are part of an iteration of the BF decoder and return the corrected codeword. The corrected codeword can be processed in a subsequent iteration of the BF decoder, which would include similar operations410,415, and420performed on the corrected codeword to obtain a subsequent corrected codeword. In some embodiments, the iterations can continue until a stop criterion is satisfied, as described above.