Bit flipping decoder using channel information
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 C i from the storage device, where i=0 to N−1 and N is a number of bits of the plurality of bits C i ;
initialize a plurality of bit flip decisions BF i for each bit C i such that BF i =C i ; and
perform a plurality of bit flipping iterations in which a threshold condition for flipping each bit flip decision of the plurality of bit flip decisions BF i is a function of C i ;
wherein the controller is further programmed to perform the plurality of bit flipping iterations by, for each iteration k of the plurality of bit flipping iterations:
(a) determine a number of unsatisfied checks TUSC k for BF i ;
(b) if TUSC k is zero or k meets an iteration threshold, cease performing the plurality of bit flipping iterations; and
(c) if TUSC k is not zero and k does not meet the iteration threshold, for each bit flip decision BF i , flip BF i if a threshold condition is met, the threshold condition being a function of C i .
2. The controller of claim 1 , wherein the threshold condition is a function of (BF i xor C i ).
3. The controller of claim 1 , wherein the controller is further programmed to calculate a bit flip threshold Th k for each iteration k as a function of k, TUSC k , and a number of bits flipped in a previous iteration k−1, the threshold condition being a function of Th k .
4. The controller of claim 3 , wherein the controller is further programmed to calculate Th k according to Algorithm 1; and
wherein the threshold condition is one of Equation (1) and Equation (8).
5. The controller of claim 3 , wherein the controller is further programmed to constrain Th k to be an integer.
6. The controller of claim 5 , wherein Th k is a function of TUSC k .
7. The controller of claim 6 , wherein the controller is further programmed to:
identify a bin range of a plurality of bin ranges including TUSC k ; and
select parameters for the threshold condition corresponding to the bin range.
8. The controller of claim 3 , wherein the threshold condition is a function only of Th k , C i , BF i , and a number of a portion of the unsatisfied checks TUSC k that are connected to bit position i.
9. The controller of claim 8 , wherein the threshold condition is:
(BF i xor C i )+USC i ≥Th k
where USC i is the number of the portion of the unsatisfied checks that are connected to bit position i.
10. A controller for a storage device, the controller being programmed to:
read a plurality of bits C i from the storage device, where i=0 to N−1 and N is a number of bits of the plurality of bits C i ;
initialize a plurality of bit flip decisions BF i for each bit C i such that BF i =C i ; and
perform a plurality of iterations k by, at each iteration k:
(a) determine a number of unsatisfied checks TUSC k for BF i ;
(b) if TUSC k is zero or k meets an iteration threshold, cease performing the plurality of iterations k; and
(c) if TUSC k is not zero and k does not meet the iteration threshold, for each bit position i, flip BF i , if a threshold condition is met, the threshold condition being a function of C i , BF i , and USC i , where USC i is a number of the unsatisfied checks TUSC k that are connected to bit position i in a parity check matrix H.
11. The controller of claim 10 , wherein the threshold condition is a function of (BF i xor C i ).
12. The controller of claim 11 , wherein the threshold condition is
α(γ i ,TUSC k )*(BF i xor C i )+(γ i ,TUSC k )*USC i ≥Th k
where Th k is a bit flip threshold, γ i is a number of non-zero entries of H in column i of H, and α(γ i ,TUSC k ) and β(γ i ,TUSC k ) are predefined parameters.
13. The controller of claim 12 , wherein Th k is a function of one or more of k, γ max , and a Th k−1 , where γ max is equal to a maximum number of ones in any column i of H.
14. The controller of claim 13 , wherein the controller is further programmed to constrain Th k to be an integer.
15. The controller of claim 13 , wherein the controller is further programmed to calculate Th k according to Algorithm 1.
16. The controller of claim 12 , wherein:
(α(γ i ,TUSC k ),β(γ i ,TUSC k ),Th k )=( A T A ) −1 *( A T B )
where
A
=
[
(
BF
1
xor
C
1
)
USC
1
-
1
⋮
⋱
⋮
(
BF
L
xor
C
L
)
USC
L
-
1
]
,
B
=
[
E
1
.
.
E
L
]
where L is a number of training samples, E i , i=1 to L, are errors calculated as E i =−1+2*(C i xor G i ), where G i is originally written data that is read back as C i .
17. The controller of claim 12 , wherein the controller is further programmed to:
identify a bin range of a plurality of bin ranges including TUSC k ; and
select values for α(γ i ,TUSC k ) and β(γ i ,TUSC k ) corresponding to the bin range.
18. The controller of claim 17 , wherein the values for α(γ i ,TUSC k ) and β(γ i ,TUSC k ) corresponding to the plurality of bin ranges are discretized to 2 or fewer fractional bits.
19. The controller of claim 12 , wherein α(γ i ,TUSC k ) and β(γ i ,TUSC k ) are each equal to 1.