Iteration dependent bitwise bit flipping decoder
An LDPC decoder receives channel information and performs a bit flipping algorithm to correct unsatisfied checks with respect to a parity matrix H. The threshold condition for determining whether to flip a bit is a function of the channel information itself. A threshold Th k used to evaluate the threshold condition may vary between iterations based on the number of iterations, number of bits flipped in the previous iteration, and number of unsatisfied checks. A threshold Th k i may be calculated for each bit position. Th k i and the threshold condition may be a function of whether bit position i was flipped in a previous iteration. A binning approach for parameters of the threshold condition may be used to reduce hardware complexity.
1. A controller for a storage device, the controller being programmed to:
read a plurality of bits Ci from the storage device, where i=0 to N−1 and N is a number of bits of the plurality of bits Ci;
initialize a plurality of bit flip decisions BFi for each bit Ci such that BFi=Ci; and
perform a plurality of bit flipping, iterations such that, for each bit flipping iteration k of the plurality of bit flipping iterations, a threshold condition for flipping each bit flip decision of the plurality of bit flip decisions BFi is a function of k;
wherein each bit flipping iteration k of the plurality of bit flipping iterations comprises:
a) determine a number of unsatisfied checks TUSCk for BFi with respect to a parity matrix H;
(b) if TUSCk is zero or k meets an iteration threshold, cease performing the plurality of bit flipping iterations; and
(c) if TUSCk is not zero and k does not meet the iteration threshold, for each bit flip decision BFi, flip each bit flip decision BFi if a threshold condition is met, the threshold condition being a function of the each bit flipping iteration k.
2. The controller of claim 1 , wherein the controller is programmed to calculate the threshold condition as a function of a bit flipping threshold Thk, wherein Thk varies periodically with respect to k.
3. The controller of claim 2 , wherein the controller is programmed to reduce Thk to a minimum value every z iterations, where z is an integer greater than 1.
4. The controller of claim 3 , wherein the controller is programmed to set Thk to one or more values above the minimum value when z is not an integer greater than 1.
5. The controller of claim 4 , wherein;
the minimum value is γ_max-2, where γ_max is a greatest number of 1 s in any one column of H; and
wherein the one or more values above the minimum value include γ_max-1.
6. The controller of claim 1 , wherein the controller is programmed to calculate the threshold condition as a function of a bit flipping threshold Thki that is calculated by the controller for each bit flip decision BFi.
7. The controller of claim 6 , wherein Thki is a function of BFi xor Ci.
8. The controller of claim 7 , wherein Thki is a function of TUSCk.
9. The controller of claim 8 , wherein Thki is a function of γ_i, where γ_iis a number of non-zero entries in column i of H.
10. The controller of claim 1 , wherein for a first range of values of TUSCk the threshold condition is a function of BFi xor Ci and for a second range of values of TUSCk the threshold condition is not a function of BFi xor Ci.
11. The controller of claim 1 , wherein the threshold condition is a function of a bit flipping threshold Thk;
wherein the controller is programmed to calculate Thk according to Algorithm 2.
12. The controller of claim 1 , wherein:
the threshold condition is a function of a bit flipping threshold Thk;
the controller is programmed to calculate Thk according to Algorithm 2 for iterations k below an iteration threshold; and
the controller is programmed to calculate Thk according to Algorithm 3 for iterations k above the iteration threshold.
13. The controller of claim 1 , wherein the threshold condition is
where Thk is a bit flip threshold, γ_i is a number of non-zero entries in column i of H, USCi is a number of the unsatisfied checks TUSCk that are connected to bit position i in H, and α(γ_i, _k) and β(γ_i, _k) are predefined parameters.
14. The controller of claim 13 , wherein α(γ_i,_k) and β(γ_i, _k) are each equal to 1.
15. A controller for a storage device, the controller being programmed to:
read a plurality of bits Ci from the storage device, where i=0 to N−1 and N is a number of bits of the plurality of bits Ci:
initialize a plurality of bit flip decisions BFi for each bit Ci such that BFi=Ci; and
perform a plurality of iterations k by, at each iteration k:
(a) determine a number of unsatisfied cheeks TUSCk for BFi with respect to a parity matrix H;
(b) if TUSCk is zero or k meets a maximum iteration threshold, cease performing the plurality of iterations k; and
(c) if TUSCk is not zero and k does not meet the maximum iteration threshold, for each bit position i:
periodically set a bit flip threshold Thk to be a minimum value when TUSCk is below an unsatisfied check threshold;
when TUSCk is not below the unsatisfied check threshold, set Thk to be one or more values higher than the minimum value; and
flip BFi at bit position i, if a threshold condition is met, the threshold condition being a function of Thk.
16. The controller of claim 15 , wherein Thk is a function of one or more of k, γ_max, and a Thk-1, where γ_max is equal to a maximum number of ones in any column i of H.
17. The controller of claim 16 , wherein:
the minimum value is γ_max-2, where γ_max is a greatest number of 1 s in any one column of H.
18. The controller of claim 17 , wherein the one or more values higher than the minimum value include γ_max-1.
19. The controller of claim 15 , wherein the threshold condition is where γ_i is a number of nonzero entries in column i of H, and α(γ_i, _k) and β(γ_i, _k) are predefined parameters.