BIT FLIPPING ALGORITHM FOR DECODING LDPC-ENCODED DATA

• US 20200136644A1
• Filed: 10/25/2018
• Published: 04/30/2020
• Est. Priority Date: 10/25/2018
• Status: Active Grant

• Current Assignee: PetaIO, Inc.
• Original Assignee: PetaIO, Inc.
• Inventors: Zeng, LingQi
• Granted Patent: US 10,965,319 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: H03M 13/1108 Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations

Abstract

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.

Claims

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₂, T₁<

T₂, 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₁ and d_i ′

=r_i; and

flipping a bit d_i in d when K_i>

=T₂ and d_i==r_i.

3. The method of claim 1, further comprising defining a threshold T1 and a threshold T₂, T₁<

T₂;

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₁ and d_i ′

=r_i; and

flipping a bit d_i in d when K_i>

=T₂ 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 di 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₁ and T₂ 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₁ and T₂ 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₁ and T₂ 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₂, T₁<

T₂, 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₁ and d_i ′

=r_i; and

flipping a bit d_i in d when K_i>

=T₂ 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₂, T₁<

T₂;

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₁ and d_i ′

=r_i; and

flipping a bit d_i in d when K_i>

=T₂ 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₁ and T₂ 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₁ and T2 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₁ and T₂ 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 T₁ and T₂ are a function of only predefined static values for one or more iterations of the first iterations according to Algorithm 1.