Breaking trapping sets using targeted bit adjustment
In one embodiment, an LDPC decoder performs a targeted bit adjustment method to recover a valid codeword after the decoder has failed. In a first stage, a post processor initializes the decoder by saturating LLR values output by the decoder during the last (i.e., failed) iteration to a relatively small value. Then, two-bit trials are performed, wherein LLR values corresponding to two bits of the codeword are adjusted in each trial. Decoding is performed with the adjusted values, and if the number of unsatisfied check nodes exceeds a specified threshold, then a second stage is performed. The post processor initializes the decoder by saturating the LLR values output by the decoder during the last (i.e., failed) iteration of the first stage to a relatively small value. The second stage then performs single-bit adjustment trials, wherein one LLR value corresponding to one bit of the codeword is adjusted in each trial.
1. A receiver-implemented method for recovering an error correction-encoded codeword, the method comprising:
(a) performing a first stage of error correction decoding on a first set of input values to generate a first set of output values, one or more of which correspond to one or more first-stage unsatisfied check nodes;
(b) performing a second stage of error correction decoding on a second set of input values to generate a second set of output values, one or more of which correspond to one or more second-stage unsatisfied check nodes, wherein:
the second set of input values is based on the first set of output values; and
one or more of the input values of the second set of input values are generated by adjusting one or more corresponding output values of the first set of output values, wherein each of the one or more corresponding output values of the first set of output values is associated with a first-stage unsatisfied check node;
(c) comparing a difference of (i) the number of first-stage unsatisfied check nodes and (ii) the number of second-stage unsatisfied check nodes to a specified threshold value;
(d) selecting a subsequent stage of error correction decoding based on the comparison of step (c); and
(e) performing the selected subsequent stage of error correction decoding.
2. The invention of claim 1 , wherein the selected subsequent stage of error correction decoding is an additional instance of the second stage of error correction decoding, if the difference has a magnitude greater than the specified threshold.
3. The invention of claim 2 , wherein for the additional instance of the second stage:
the second set of input values is based on the first set of output values; and
the one or more corresponding output values of the first set of output values that are adjusted during the additional instance of the second stage are different from the one or more corresponding output values of the first set of output values that are adjusted during other instances of the second stage.
4. The invention of claim 1 , wherein the selected subsequent stage of error correction decoding is a third stage of error correction decoding different from the second stage of error correction decoding, if the difference has a magnitude less than the specified threshold.
5. The invention of claim 4 , wherein the third stage of error correction decoding comprises:
performing error correction decoding on a third set of input values to generate a third set of output values, wherein:
the third set of input values is based on the second set of output values; and
one or more of the input values in the third set of input values are generated by adjusting one or more corresponding output values of the second set of output values, wherein each of the one or more corresponding output values of the second set of output values is associated with a second-stage unsatisfied check node.
6. The invention of claim 5 comprising performing, if the third stage of error correction decoding fails to recover the error correction-encoded codeword, an additional instance of the third stage of error correction decoding, wherein for the additional instance:
the third set of input values corresponds to the second set of output values; and
the one or more corresponding output values of the second set of output values that are adjusted during the additional instance of the third stage are different from the one or more corresponding output values of the second set that are adjusted during other instances of the third stage.
7. The invention of claim 1 , wherein the second stage of error correction decoding is performed after the first stage of error correction decoding fails to recover the error correction-encoded codeword.
8. The invention of claim 1 , wherein the comparison of step (c) is performed after the second stage of error correction decoding fails to recover the error correction-encoded codeword.
9. The invention of claim 1 , wherein:
the one or more input values in step (b) comprise two or more input values in the second set of input values, wherein:
the two or more input values are generated by adjusting two or more corresponding output values of the first set of output values; and
the two or more corresponding output values of the first set of output values are associated with different unsatisfied check nodes of the first stage.
10. The invention of claim 9 , wherein:
the selected subsequent stage of error correction decoding is an additional instance of the second stage of error correction decoding, if the difference has a magnitude greater than the specified threshold; and
for the additional instance of the second stage:
the second set of input values is based on the first set of output values; and
the two or more corresponding output values of the first set of output values that are adjusted during the additional instance of the second stage are different from the two or more corresponding output values of the first set of output values that are adjusted during other instances of the second stage.
11. The invention of claim 1 , wherein generating the second set of input values comprises (i) flipping sign bits of the one or more corresponding output values of the first set of output values and (ii) retaining sign bits of any remaining output values of the first set of output values.
12. The invention of claim 11 , wherein generating the second set of input values further comprises adjusting confidence values of the first set of output values such that magnitudes of the adjusted confidence values of the one or more corresponding output values of the first set of output values are greater than magnitudes of the adjusted confidence values of the remaining output values of the first set of output values.
13. The invention of claim 1 , wherein:
the error correction-encoded codeword is a low-density parity-check-encoded codeword; and
the first, second, and third stages of error correction decoding perform low-density parity-check decoding.
14. Apparatus for recovering an error correction-encoded codeword, the apparatus comprising:
an error correction decoder; and
a controller that controls the error correction decoder, wherein:
the error correction decoder performs a first stage of error correction decoding on a first set of input values to generate a first set of output values, one or more of which correspond to one or more first-stage unsatisfied check nodes;
the error correction decoder performs a second stage of error correction decoding on a second set of input values to generate a second set of output values, one or more of which correspond to one or more second-stage unsatisfied check nodes, wherein:
the second set of input values is based on the first set of output values; and
one or more of the input values of the second set of input values are generated by adjusting one or more corresponding output values of the first set of output values, wherein each of the one or more corresponding output values of the first set of output values is associated with a first-stage unsatisfied check node;
the controller compares a difference of (i) the number of first-stage unsatisfied check nodes and (ii) the number of second-stage unsatisfied check nodes to a specified threshold value;
the controller selects a subsequent stage of error correction decoding based on the comparison; and
the error correction decoder performs the selected subsequent stage of error correction decoding.
15. The invention of claim 14 , wherein the controller selects an additional instance of the second stage of error correction decoding as the subsequent stage of error correction decoding, if the difference has a magnitude greater than the specified threshold, wherein for the additional instance of the second stage:
the second set of input values is based on the first set of output values; and
the one or more corresponding output values of the first set of output values that are adjusted during the additional instance of the second stage are different from the one or more corresponding output values of the first set of output values that are adjusted during other instances of the second stage.
16. The invention of claim 14 , wherein the controller selects a third stage of error correction decoding, different from the second stage of error correction decoding, as the subsequent stage, if the difference has a magnitude less than the specified threshold, wherein for the third stage of error correction decoding:
the error correction decoder performs error correction decoding on a third set of input values to generate a third set of output values, wherein:
the third set of input values is based on the second set of output values; and
one or more of the input values of the third set of input values are generated by adjusting one or more corresponding output values of the second set of output values, wherein each of the one or more corresponding output values of the second set of output values is associated with a second-stage unsatisfied check node.
17. The invention of claim 14 , wherein:
the one or more input values in the second stage of error correction decoding comprise two or more input values in the second set of input values, wherein:
the two or more input values are generated by adjusting two or more corresponding output values of the first set of output values; and
the two or more corresponding output values of the first set of output values are associated with different unsatisfied check nodes of the first stage.
18. The invention of claim 17 , wherein:
the controller selects an additional instance of the second stage of error correction decoding as the subsequent stage of error correction decoding, if the difference has a magnitude greater than the specified threshold; and
for the additional instance of the second stage:
the second set of input values is based on the first set of output values; and
the two or more corresponding output values of the first set of output values that are adjusted during the additional instance of the second stage are different from the two or more corresponding output values of the first set of output values that are adjusted during other instances of the second stage.
19. The invention of claim 14 , wherein generating the second set of input values comprises (i) flipping sign bits of the one or more corresponding output values of the first set of output values and (ii) retaining sign bits of any remaining output values of the first set of output values.
20. The invention of claim 19 , wherein generating the second set of input values further comprises adjusting confidence values of the first set of output values such that magnitudes of the adjusted confidence values of the one or more corresponding output values of the first set of output values are greater than magnitudes of the adjusted confidence values of the remaining output values of the first set of output values.
21. The invention of claim 14 , wherein:
the error correction-encoded codeword is a low-density parity-check-encoded codeword; and
the error correction decoder is and low-density parity-check decoder.