Quality-based dynamic scheduling LDPC decoder
Techniques related to improving power consumption of an LDPC decoder are described. In an example, the LDPC decoder uses a message passing algorithm between variable nodes and check nodes. A check node processing unit that generates check node to variable node messages implements a plurality of check node processing mode. Operation in each mode consumes a certain amount of power while providing a certain accuracy. Depending on a reliability of a variable node to check node message received by the check node processing unit, an appropriate check node processing mode is selected and used to generate a corresponding check node to variable node message. The reliability can be estimated for a set of variable node to check node messages based on, for instance, syndrome-related parameters.
1. A method for decoding a low-density parity-check code (LDPC) codeword, the method implemented on a computing device and comprising:
determining a variable node to check node (V2C) message, wherein the V2C message corresponds to a variable node that is connected to a check node;
determining a reliability of a set of V2C messages comprising the V2C message, the reliability representing a certainty of decoding the LDPC codeword, wherein each V2C message in the set of V2C messages corresponds to a different variable node from a set of variable nodes, and wherein the set of variable nodes corresponds to a variable node circulant matrix;
selecting, based on the reliability, a check node processing mode from a plurality of check node processing modes that have different error correction capabilities;
determining a check node to variable node (C2V) message based on selection of the check node processing mode; and
decoding the LDPC codeword based on the C2V message.
2. The method of claim 1 , further comprising:
during a decoding iteration:
determining a syndrome of the LDPC codeword;
increasing a decoding iteration number;
determining that the increased decoding iteration number does not exceed a maximum number; and
determining that the syndrome of the LDPC codeword is not zero.
3. The method of claim 2 , further comprising:
during a next decoding iteration corresponding to the increased decoding iteration number:
(a) updating the V2C message corresponding to the variable node;
(b) determining that the variable node is associated with a “j” variable node circulant matrix;
(c) determining that the check node connected to the variable node is associated with a “k” check node circulant matrix;
(d) determining the reliability of the set of V2C messages as r k,j =number of ones in S k /CS, where r k,j is the reliability, S k is a partial checksum computed based on the “k” check node circulant matrix, and CS is a checksum determined from the syndrome of the LDPC codeword;
(e) comparing r k,j to a reliability threshold, wherein the check node processing mode is selected based on the comparing; and
(f) updating the partial checksum S k .
4. The method of claim 3 , further comprising:
during the next decoding iteration, repeating steps (a)-(f) for remaining variable node circulant matrices and remaining check node circulant matrices.
5. The method of claim 1 , wherein the reliability of the set of V2C messages is determined based on a syndrome of the LDPC codeword.
6. The method of claim 5 , wherein the reliability of the set of V2C messages is further determined based on a partial syndrome associated with a circulant matrix, wherein the check node is associated with the circulant matrix.
7. The method of claim 1 , wherein the check node is associated with a check node circulant matrix, wherein the reliability is determined based on a syndrome of the LDPC codeword and a partial syndrome, wherein the partial syndrome is computed based on the check node circulant matrix.
8. The method of claim 7 , wherein the reliability is determined as r=number of ones in S k /CS, where r is the reliability, S k is the partial syndrome, and CS is a checksum determined from the syndrome of the LDPC codeword.
9. The method of claim 1 , further comprising:
comparing the reliability to a reliability threshold, wherein the check node processing mode is selected based on the comparing.
10. The method of claim 9 , wherein the plurality of different check node processing modes comprises a first check node processing mode and a second check node processing mode, wherein the first check node processing mode approximates a log likelihood ratio of the variable node based on a first quantization level, wherein the second check node processing mode approximates the log likelihood ratio of the variable node based on a second quantization level, wherein the second quantization level is larger than the first quantization level, wherein the first check node processing mode is selected if the reliability is smaller than the reliability threshold, and wherein the second check node processing mode is selected if the reliability is larger than the reliability threshold.
11. The method of claim 9 , wherein the reliability threshold is defined based on a decoding iteration number.
12. The method of claim 9 , wherein the reliability threshold is defined based on a degree of the variable node.
13. The method of claim 9 , wherein the reliability threshold is defined based on a degree of the check node.
14. A device comprising:
a memory storing a low-density parity-check code (LDPC) codeword; and
a set of processing units configured to:
determine a variable node to check node (V2C) message, wherein the V2C message corresponds to a variable node that is connected to a check node;
determine a reliability of a set of V2C messages comprising the V2C message, the reliability representing a certainty of decoding the LDPC codeword, wherein each V2C message in the set of V2C messages corresponds to a different variable node from a set of variable nodes, and wherein the set of variable nodes corresponds to a variable node circulant matrix;
select, based on the reliability, a check node processing mode from a plurality of check node processing modes that have different error correction capabilities; and
determine a check node to variable node (C2V) message based on selection of the check node processing mode,
wherein the LDPC codeword is decoded based on the C2V message.
15. The device of claim 14 , wherein the set of processing units is further configured to:
during a decoding iteration:
determine a syndrome of the LDPC codeword;
increase a decoding iteration number;
determine that the increased decoding iteration number does not exceed a maximum number; and
determine that the syndrome of the LDPC codeword is not zero.
16. The device of claim 15 , wherein the set of processing units is further configured to:
during a next decoding iteration corresponding to the increased decoding iteration number:
(a) update the V2C message corresponding to the variable node;
(b) determine that the variable node is associated with a “j” variable node circulant matrix;
(c) determine that the check node connected to the variable node is associated with a “k” check node circulant matrix;
(d) determine the reliability of the set of V2C messages as r k,j =number of ones in S k /CS, where r k,j is the reliability, S k is a partial syndrome computed based on the “k” check node circulant matrix, and CS is a checksum determined from the syndrome of the LDPC codeword;
(e) compare r k,j to a reliability threshold, wherein the check node processing mode is selected based on the comparing; and
(f) update the partial syndrome S k .
17. The device of claim 16 , wherein the set of processing units is further configured to:
during the next decoding iteration, repeat steps (a)-(f) for remaining variable node circulant matrices and remaining check node circulant matrices.
18. An error correction (ECC) system comprising:
a set of processing units configured to:
receive an LDPC codeword from a memory;
determine a variable node to check node (V2C) message, wherein the V2C message corresponds to a variable node that is connected to a check node;
determine a reliability of a set of V2C messages comprising the V2C message, the reliability representing a certainty of decoding the LDPC codeword, wherein each V2C message in the set of V2C messages corresponds to a different variable node from a set of variable nodes, and wherein the set of variable nodes corresponds to a variable node circulant matrix;
select, based on the reliability, a check node processing mode from a plurality of check node processing modes that have different error correction capabilities; and
determine a check node to variable node (C2V) message based on selection of the check node processing mode,
wherein the LDPC codeword is decoded based on the C2V message.
19. The ECC system of claim 18 , wherein the reliability of the set of V2C messages is determined based on a syndrome of the LDPC codeword and based on a partial syndrome associated with a circulant matrix, wherein the check node is associated with the circulant matrix.