Oscillation detection and mitigation in bit-flipping decoders
Devices, systems, and methods for detecting and mitigating oscillations in a bit-flipping decoder associated with a non-volatile memory are described. An example method includes receiving a noisy codeword based on a transmitted codeword generated from a low-density parity-check code, performing a first plurality of decoding iterations on the noisy codeword, which comprises performing a message passing algorithm in a first order, computing, based on a completion of the first plurality of decoding iterations, a plurality of checksum values and a plurality of bit flip counts corresponding to the first plurality of decoding iterations, determining that the plurality of checksum values and the plurality of bit flip counts are periodic with a period less than a predetermined threshold, and performing a subsequent decoding iteration on the noisy codeword, the subsequent decoding iteration comprising performing the message passing algorithm in a second order different from the first order.
1. A method for improving a decoding performance of a bit-flipping decoder associated with a non-volatile memory, comprising:
receiving a noisy codeword that is based on a transmitted codeword generated from a low-density parity-check (LDPC) code;
performing a first plurality of decoding iterations on the noisy codeword, at least one of the first plurality of decoding iterations comprising performing a message passing algorithm in a first order;
computing, based on a completion of the first plurality of decoding iterations, a plurality of checksum values and a plurality of bit flip counts corresponding to the first plurality of decoding iterations;
determining that the plurality of checksum values and the plurality of bit flip counts are periodic with a period less than a predetermined threshold (T); and
performing a subsequent decoding iteration on the noisy codeword, the subsequent decoding iteration comprising performing the message passing algorithm in a second order different from the first order.
2. The method of claim 1 , wherein each decoding iteration of the first plurality of decoding iterations comprises passing one or more messages between a plurality of variable nodes and a plurality of check nodes that represent a parity check matrix of the LDPC code.
3. The method of claim 2 , wherein the bit-flipping decoder uses two or more bits to store estimates for each of the plurality of variable nodes.
4. The method of claim 2 , wherein the first order comprises a first decoding order of the plurality of variable nodes in the decoding iteration, and wherein the second order comprises a second decoding order of the plurality of variable nodes in the decoding iteration.
5. The method of claim 1 , wherein the subsequent decoding iteration comprises performing the message passing algorithm N times on each of N circulant columns that comprise a parity check matrix of the LDPC code, and wherein N is an integer.
6. The method of claim 5 , further comprising:
determining the second order based on generating a pseudo-random array of bits of length N, wherein each bit of the pseudo-random array of bits has a value of one with probability p, and wherein the second order comprises flipping a bit when a corresponding bit in the pseudo-random array of bits has a value of one.
7. The method of claim 6 , wherein p=0.8 and T=10.
8. The method of claim 1 , further comprising:
computing a syndrome; and
refraining from performing, after the subsequent decoding iteration, an additional decoding iteration of the bit-flipping decoder upon a determination that a maximum number of iterations has been performed or that the syndrome is equal to zero.
9. The method of claim 1 , wherein the LDPC code is an irregular quasi-cyclic low-density parity-check (QC-LDPC) code.
10. A system for improving a decoding performance of a bit-flipping decoder associated with a non-volatile memory, comprising:
a processor and a memory including instructions stored thereupon, wherein the instructions upon execution by the processor cause the processor to:
receive a noisy codeword that is based on a transmitted codeword generated from an irregular quasi-cyclic low-density parity-check (QC-LDPC) code;
perform a first plurality of decoding iterations on the noisy codeword, at least one of the first plurality of decoding iterations comprising performing a message passing algorithm in a first order;
compute, based on a completion of the first plurality of decoding iterations, a plurality of checksum values and a plurality of bit flip counts corresponding to the first plurality of decoding iterations;
determine that the plurality of checksum values and the plurality of bit flip counts are periodic with a period less than a predetermined threshold (T); and
perform a subsequent decoding iteration on the noisy codeword, the subsequent decoding iteration comprising performing the message passing algorithm in a second order different from the first order.
11. The system of claim 10 , wherein each decoding iteration of the first plurality of decoding iterations comprises passing one or more messages between a plurality of variable nodes and a plurality of check nodes that represent a parity check matrix of the QC-LDPC code.
12. The system of claim 11 , wherein the first order comprises a first decoding order of the plurality of variable nodes in the decoding iteration, and wherein the second order comprises a second decoding order of the plurality of variable nodes in the decoding iteration.
13. The system of claim 10 , wherein the subsequent decoding iteration comprises performing the message passing algorithm N times on each of N circulant columns that comprise a parity check matrix of the QC-LDPC code, and wherein Nis an integer.
14. The system of claim 13 , wherein the instructions upon execution by the processor configure the process to:
determine the second order based on generating a pseudo-random array of bits of length N, wherein each bit of the pseudo-random array of bits has a value of one with probability p, and wherein the second order comprises flipping a bit when a corresponding bit in the pseudo-random array of bits has a value of one.
15. The system of claim 14 , wherein p=0.8 and T=10.
16. A non-transitory computer-readable storage medium having instructions stored thereupon for improving a decoding performance of a bit-flipping decoder associated with a non-volatile memory, comprising:
instructions for receiving a noisy codeword that is based on a transmitted codeword generated from a quasi-cyclic low-density parity-check (QC-LDPC) code;
instructions for performing a first plurality of decoding iterations on the noisy codeword, at least one of the first plurality of decoding iterations comprising performing a message passing algorithm in a first order;
instructions for computing, based on a completion of the first plurality of decoding iterations, a plurality of checksum values and a plurality of bit flip counts corresponding to the first plurality of decoding iterations;
instructions for determining that the plurality of checksum values and the plurality of bit flip counts are periodic with a period less than a predetermined threshold ( 17 ); and
instructions for performing a subsequent decoding iteration on the noisy codeword, the subsequent decoding iteration comprising performing the message passing algorithm in a second order different from the first order.
17. The storage medium of claim 16 , wherein each decoding iteration of the first plurality of decoding iterations comprises passing one or more messages between a plurality of variable nodes and a plurality of check nodes that represent a parity check matrix of the QC-LDPC code, wherein the first order comprises a first decoding order of the plurality of variable nodes in the decoding iteration, and wherein the second order comprises a second decoding order of the plurality of variable nodes in the decoding iteration.
18. The storage medium of claim 17 , wherein the bit-flipping decoder uses two or more bits to store estimates for each of the plurality of variable nodes.
19. The storage medium of claim 16 , wherein the subsequent decoding iteration comprises performing the message passing algorithm N times on each of N circulant columns that comprise a parity check matrix of the QC-LDPC code, and wherein Nis an integer.
20. The storage medium of claim 19 , further comprising:
instructions for determining the second order based on generating a pseudo-random array of bits of length N, wherein each bit of the pseudo-random array of bits has a value of one with probability p, and wherein the second order comprises flipping a bit when a corresponding bit in the pseudo-random array of bits has a value of one.