POWER SAVING FOR BIT FLIPPING DECODING ALGORITHM IN LDPC DECODER

Abstract

A method for determining when to end a bit flipping algorithm during hard decision soft decoding in a low density parity check (LDPC) decoder includes: selecting a certain number of iterations as a first threshold; when the first threshold is reached, determining a highest variable node codeword for each iteration performed so far; comparing the highest variable node codewords with a second threshold; and when the value of the highest variable node codewords is less than or equal to the second threshold, ending the bit flipping algorithm.

Claims

1. A method for determining when to end a bit flipping algorithm during hard decision soft decoding in a low density parity check (LDPC) decoder, the method comprising: selecting a certain number of iterations as a first threshold; when the first threshold is reached, determining a highest variable node codeword for each iteration performed so far; comparing the highest variable node codewords with a second threshold; and when the value of the highest variable node codewords is less than or equal to the second threshold, ending the bit flipping algorithm.

2. The method of claim 1, wherein the first threshold is dynamic.

3. The method of claim 1, further comprising: when the value of the highest variable node codewords is greater than the second threshold, continuing the bit flipping algorithm for one more iteration.

4. The method of claim 1, wherein the second threshold is a column weight of the highest variable node for the current iteration divided by 2.

5. The method of claim 1, wherein the step of ending the bit flipping algorithm further comprises: utilizing another soft decoding hard decision algorithm in the LDPC decoder.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0012] The FIGURE illustrates a parity check matrix H and a Tanner graph.

DETAILED DESCRIPTION

[0013] As described above, the aim of the present invention is to prevent the bit flipping algorithm from going through too many useless iterations, and to provide a clear point at which the decoding algorithm should be switched for hard decision soft decoding.

[0014] The present invention therefore provides a dynamic bit flipping method wherein there is no predetermined number of iterations. Instead, a performance parameter is used as a benchmark for determining a maximum number of iterations.

[0015] During bit flipping, the variable nodes use majority rule to determine correct information by finding the largest variable node, flipping the original bit and determining whether the check node becomes zero. After a certain number of iterations, all check nodes should be zero, unless there are uncorrectable errors which require a different decoding algorithm.

[0016] The column weight of a variable node is defined as the number of ‘ONES’ in a column of the parity check matrix illustrated in the FIGURE, and therefore represents the greatest error at the variable node. As shown in the FIGURE, the column weight also represents how many check nodes each variable node is coupled to. Column weight is used herein as a measure for determining when to terminate bit flipping.

[0017] A value, t, is used to set a minimum number of iterations performed before the column weight is used to measure performance. In the example given herein, t is selected as 3. This is because the codeword is unlikely to be satisfied in a first or even second iteration. The exact value of t is not fixed, however, and can be changed according to different requirements. Taking t as 3, and taking an iteration at which the column weight is first used to measure performance as i (a current iteration), the decoder will undergo a first iteration i−2 and a second iteration i−1.

[0018] As described above, the bit flipping algorithm considers the largest codeword at the variable nodes and flips an original bit. At this point, the system will also compare a value of the largest variable node codeword for the first iteration i−2, the second iteration i−1, and the current iteration i, respectively, with the corresponding column weight divided by 2. If the value for each iteration is less than or equal to the corresponding column weight divided by 2, this indicates that the decoding mode should switch. If the value is higher, the bit flipping algorithm can go through another iteration. This is illustrated below.

If [m.sub.i−t, . . . , m.sub.i]<floor (column weight/2) then terminate bit flipping.

[0019] From the above, m.sub.i is the maximum threshold (largest variable codeword) at the i-th iteration, and t describes the number of iterations which are considered, wherein t is adjustable.

[0020] Once it is determined that the highest variable node codewords are less than or equal to the column weight divided by 2 for a set number of iterations, this represents that the bit flipping algorithm has reached an unresolvable number of error bits and that the decoding algorithm should be switched.

[0021] The present scheme therefore offers a chance to save power during bit flipping by only performing the algorithm for a certain number of iterations. By using column weight as a performance parameter, a time for ending the bit flipping can be quickly determined, and another decoding algorithm can be selected.

[0022] Those skilled in the art will readily observe that numerous modifications and alterations of the device and method may be made while retaining the teachings of the invention. Accordingly, the above disclosure should be construed as limited only by the metes and bounds of the appended claims.