Bit flipping algorithm for decoding LDPC-encoded data
A bit flipping algorithm for an LDPC decoder evaluates a data sequence d with respect to a parity code matrix H. Where one or more checks fail, bits of d are flipped such that for some iterations, the bits are flipped with bias toward and original data sequence r. For example, for some iterations, where the number of failed checks are below a first threshold T1, bits are only permitted to flip back to the value of that bit in the original data sequence r. In such iterations, bits are permitted to flip from the value in the original data sequence r only when the number of failed checks is greater than a second threshold T2, T2>T1. Values for thresholds may be based on a number of flipped bits from a previous iteration and may be calculated using a syndrome s=Hd from a previous iteration.
1. A method comprising, by a computing device:
receiving an original data sequence r;
setting a current data sequence d to be the original data sequence;
performing a plurality of iterations, each iteration of the plurality of iterations including:
(a) evaluating d according to a low density parity code matrix H;
(b) when (a) indicates one or more failed checks according to H, flipping one or more bits in d such that for first iterations of the plurality of iterations one or more bits in d are flipped with biasing toward the original data sequence r; and
(c) repeating (a) and (b) until at least one of (i) (a) indicates there are no failed checks in d and (ii) a number of times (a) and (b) have been performed meets a predefined threshold.
2. The method of claim 1 , further comprising defining a threshold T1 and a threshold T 2 , T 1 <T 2 , wherein:
(a) comprises:
calculating a syndrome s=Hd; and
for each value s i in s, set a value K i in a vector K equal to a number of ones in column i of H if s i is nonzero;
(b) for each first iteration of the first iterations comprises performing:
flipping a bit d i in d when K i >=T 1 and d i !=r i ; and
flipping a bit d i in d when K i >=T 2 and d i ==r i .
3. The method of claim 1 , further comprising defining a threshold T1 and a threshold T 2 , T 1 <T 2 ;
performing (a) for each iteration of the plurality of iterations by:
calculating a syndrome s=Hd; and
for each value s i in s, set a value K i in a vector K equal to a number of ones in column i of H if s i is nonzero;
performing (b) for each first iteration of the first iterations comprises:
flipping a bit d i in d when K i >=T 1 and d i !=r i ; and
flipping a bit d i in d when K i >=T 2 and d i ==r i ;
performing (b) for each second iteration of second iterations of the plurality of iterations comprises:
calculating a threshold T=max(K); and
flipping each bit d i in d in which K i >=T.
4. The method of claim 3 , further comprising performing the first iterations interleaved with the second iterations.
5. The method of claim 4 , further comprising interleaving the first iterations with the second iterations such that a frequency of occurrence of the first iterations increases with later iterations of the plurality of iterations.
6. The method of claim 5 , wherein the first iterations occur only in a later half of the plurality of iterations.
7. The method of claim 3 , wherein T 1 and T 2 for each first iteration are a function of K from a preceding iteration of the plurality of iterations.
8. The method of claim 3 , wherein T 1 and T 2 for each first iteration of the first iterations are a function of s from an iteration of the plurality of iterations that preceded the each first iteration.
9. The method of claim 3 , wherein T 1 and T 2 for each first iteration of the first iterations are a function of a number of bits flipped in an iteration of the plurality of iterations that preceded the each first iteration.
10. The method of claim 3 , wherein T1 and T2 are a function of only predefined static values for one or more iterations of the first iterations.
11. A system comprising:
a memory;
a controller programmed to:
receive an original data sequence r;
store r in the memory
set a current data sequence d to be the original data sequence in the memory;
perform a plurality of iterations, each iteration of the plurality of iterations including:
(a) evaluating d according to a low density parity code matrix H;
(b) when (a) indicates one or more failed checks according to H, flipping one or more bits in d such that for first iterations of the plurality of iterations one or more bits in d are flipped with biasing toward the original data sequence r; and
(c) repeating (a) and (b) until at least one of (i) (a) indicates there are no failed checks in d and (ii) a number of times (a) and (b) have been performed meets a predefined threshold.
12. The system of claim 11 , wherein the controller is further programmed to:
define a threshold T1 and a threshold T 2 , T 1 <T 2 , wherein:
perform (a) by:
calculating a syndrome s=Hd; and
for each value s i in s, set a value K i in a vector K equal to a number of ones in column i of H if s i is nonzero;
perform (b) for each first iteration of the first iterations by:
flipping a bit d i in d when K i >=T 1 and d i !=r i ; and
flipping a bit d i in d when K i >=T 2 and d i ==r i .
13. The system of claim 11 , wherein the controller is further programmed to:
define a threshold T1 and a threshold T 2 , T 1 <T 2 ;
perform (a) for each iteration of the plurality of iterations by:
calculating a syndrome s=Hd; and
for each value s i in s, set a value K i in a vector K equal to a number of ones in column i of H if s i is nonzero;
perform (b) for each first iteration of the first iterations by:
flipping a bit d i in d when K i >=T 1 and d i !=r i ; and
flipping a bit d i in d when K i >=T 2 and d i ==r i ;
perform (b) for each second iteration of second iterations of the plurality of iterations by:
calculating a threshold T=max(K); and
flipping each bit d i in d in which K i >=T.
14. The system of claim 13 , wherein the controller is further programmed to perform the first iterations interleaved with the second iterations.
15. The system of claim 14 , wherein the controller is further programmed to interleave the first iterations with the second iterations such that a frequency of occurrence of the first iterations increases with later iterations of the plurality of iterations.
16. The system of claim 15 , wherein the controller is further programmed to cause the first iterations to occur only in a later half of the plurality of iterations.
17. The system of claim 13 , wherein T 1 and T 2 for each first iteration are a function of K from a preceding iteration of the plurality of iterations.
18. The system of claim 13 , wherein T 1 and T 2 for each first iteration of the first iterations are a function of s from an iteration of the plurality of iterations that preceded the each first iteration.
19. The system of claim 13 , wherein T 1 and T 2 for each first iteration of the first iterations are a function of a number of bits flipped in an iteration of the plurality of iterations that preceded the each first iteration.
20. The system of claim 13 , wherein T1 and T2 are a function of only predefined static values for one or more iterations of the first iterations according to Algorithm 1.