POWER IMPROVEMENT FOR LDPC

Abstract

A method for decoding low-density parity check data to decode a codeword is disclosed. The method includes: receiving initial estimates representing a codeword from variable nodes; sending the initial estimates to corresponding check nodes; using all initial estimates to calculate a posteriori probability (APP) values and extrinsic information and sending the APP values and the extrinsic information to the variable nodes; monitoring the extrinsic information (branch information?) received at the check nodes; when the extrinsic information begins to converge, activating a syndrome check for the values at the variable nodes; and when the syndrome check equals zero, activating early termination for the decoding process.

Claims

1. A method for decoding low-density parity check data to decode a codeword, the method comprising: receiving initial estimates representing a codeword from variable nodes; sending the initial estimates to corresponding check nodes; using all initial estimates to calculate a posteriori probability (APP) values and extrinsic information and sending the APP values and the extrinsic information to the variable nodes; monitoring the extrinsic information received at the check nodes; when the extrinsic information begins to converge to a same sign, activating a syndrome check for the initial estimates; and when the syndrome check equals zero, activating early termination for the decoding process.

2. The method of claim 1, wherein when the extrinsic information does not begin to converge, the method further comprises: updating the initial estimates using the received APP values and extrinsic information; sending the updated estimates to the corresponding check nodes; and using all initial estimates to calculate a posteriori probability (APP) values and extrinsic information and sending the APP values and the extrinsic information to the variable nodes.

3. The method of claim 2, wherein the method steps are repeated for a predetermined number of iterations.

4. The method of claim 1, wherein the decoding process uses a sum-product algorithm.

5. A low-density parity check (LDPC) decoder for decoding a codeword, comprising: a channel memory, for storing initial estimates; a subtractor, coupled to the channel memory, for generating a resultant value for updating the initial estimates; a processor, coupled to the subtractor, for generating a posteriori probability (APP) values and extrinsic information; an adder, coupled to the processor and the channel memory, for combining the a posteriori probability (APP) values and the initial estimates to generate updated initial estimates; a low parity detection circuit, coupled to the adder, for detecting the updated initial estimates; an Early Termination (ET) circuit, coupled to the low parity detection circuit, for performing a syndrome check on the updated initial estimates and ending the decoding process when the updated initial estimates pass the syndrome check; and a permutator, coupled between the low parity detection circuit and the ET circuit, wherein when the low parity detection circuit determines that the extrinsic information converges to a same sign, the permutator will send the updated initial estimates to the ET circuit.

6. The LDPC decoder of claim 5, wherein when the LP detection circuit determines that the extrinsic information does not converge to a same sign, the permutator will begin another iteration of the LDPC decoder without sending the updated initial estimates to the ET circuit.

7. The LDPC decoder of claim 6, wherein the method steps are repeated for a predetermined number of iterations.

8. The LDPC decoder of claim 5, wherein the decoding process uses a sum-product algorithm.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0016] FIG. 1 is an illustration of a parity check matrix Tanner graph for low-density parity check decoding.

[0017] FIG. 2 is a diagram of an LDPC decoder according to an exemplary embodiment of the present invention.

DETAILED DESCRIPTION

[0018] An objective of the present invention is to determine a best time for activating the syndrome check in order to save power. The aim is to only perform the syndrome check at a time when the result is likely to equal zero, rather than performing the syndrome check each iteration as in the prior art.

[0019] Two equations are used to illustrate the method of the present invention. As detailed in the ‘Background’ section, when the syndrome is equal to zero, this means the parity check is satisfied and the decoding can be exited. The syndrome is determined by multiplying the variable node values with the parity check matrix, as detailed in equation 1.

H.C.sup.T=S  (1)

[0020] When S=zero, this indicates that the decoder can be terminated and the hard decision output. Otherwise, the decoding will continue for a next iteration.

[0021] The present invention also uses a sum-product decoding algorithm, rather than the bit flipping algorithm, as a means to determine when syndrome check can be activated. In the sum-product algorithm, the messages representing each decision are probabilistic values. In the bit flipping algorithm, although hard decisions are made, what is actually received is real values wherein the sign (0 or 1) represents a positive or negative decision, respectively, and the magnitude of the value represents a level of confidence in the decision. This is known as soft information. Sum-product algorithms can use this soft information by computing an a posteriori probability value APP.sub.j for each bit, which is the probability that a certain bit will equal 1 if all the parity checks are met. An approximation of the APP.sub.j is computed over a series of iterations.

[0022] The iterations follows those of the bit flipping algorithm, except that each time what is calculated is the probability that a parity check equation will be satisfied if the bit is a particular value. Each time the check node returns a probability value, it will also return extrinsic information which is independent of the probability value for that bit which is then used by the variable node as a priori information for the next iteration.

[0023] The relation between the variable node values, the check node values, and the a posteriori probability values for sum-product decoding are represented by equation 2.

APP.sub.j−R.sub.ij=Q.sub.ij  (2)

where APP.sub.j is the a posteriori probability sent by the check node, Q.sub.ij is the response from the variable node and R.sub.ij is the extrinsic information from the check node. Subscript j represents a parity check equation and subscript i represents a bit of the code.

[0024] In the sum-product algorithm, when a codeword is found, APP.sub.j will gradually converge. From equation (2), it can be seen that as APP.sub.j gradually converges into a codeword, R.sub.ij will also converge but will be smaller than APP.sub.j. Further, the sign of Q.sub.ij will be approximately equal to the sign of APP.sub.j as it converges. Therefore, by implementing a detection circuit which determines when the check node values converge to a same sign, the LDPC system can determine at what time the syndrome check should be activated.

[0025] When the syndrome check is then activated, the Q.sub.ij value is put into equation (1) to determine if the parity check constraints are satisfied. Once the codeword meets the parity check, Early Termination can be activated and the decoding process can end without having to go through a maximum number of iterations.

[0026] By turning off the syndrome check until it is determined that extrinsic (soft) information sent from the check node converges to a same sign, power wasted on performing syndrome check for each iteration, even when the codeword is unlikely to meet parity constraints, can be saved. A simple detection circuit can detect the sign of the extrinsic information, which does not require complicated circuitry to be added to the LDPC engine.

[0027] Please refer to FIG. 2, which illustrates an LDPC decoding engine 200 according to an exemplary embodiment of the present invention. The order memory 230 receives log likelihood rations (LLR) corresponding to received symbols and stores them in the form of vectors, which will form channel values. The channel values and corresponding metrics are passed to a subtractor, and D values are sent to the compare circuit 210 for updating the channel values. The D values are also sent to the Dapp memory 250, and are sent to a processer block 290, which outputs modified metrics. The modified channel values and metrics are combined at the adder to generate a new APP value. In the prior art, this new APP value would be directly sent to the permutator 270, which would then activate a syndrome check via the Early Termination (ET) Check circuit 280. As illustrated in FIG. 2, however, the LDPC decoding engine 200 also comprises a low parity (LP) detection module 260, which examines the R.sub.ij values received from the adder to determine when they converge to the same sign and therefore to determine whether the Q.sub.ij value is stable. If this condition is met, the permutator 270 will pass the data to the ET Check circuit 280. If the condition is not satisfied, the permutator 270 will directly start a new iteration without activating a syndrome check.

[0028] The present invention therefore can save power when using a sum-product algorithm for hard decision soft decoding of low-density parity check codes.

[0029] 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.