CN101026436B - A Decoding Method of Low Density Parity Check Code - Google Patents

Abstract

The method obtains estimated value (EV) of transmitted code element (TCE) in current iterative process, and when having determined that current estimated value of TCE does not satisfy check equation, and current iterations is not equal to maximum number of iteration, the method further determines whether fluctuation occurs in current error rate (ER); if yes, considering EV of current TCE as TCE, and ending this flow; otherwise, continuing next iterative process, and stopping iterative process in time when fluctuation occurs in ER in order to raise decoding precision, and reducing decoding time delay. Concretely, whether fluctuation occurred in current ER can be determined by difference value of numbers of nonzero element in EV of TCE obtained from adjacent two iterative procedures; or whether fluctuation occurred in current ER can be determined by difference value of Hamming distances of EV of TCE obtained from adjacent two iterative procedures.

Description

A kind of low density parity check code decoding method

Technical field

The present invention relates to the channel decoding technical field, be specifically related to a kind of low density parity check code decoding method.

Background technology

In communication system, received signal tends to be subjected to the influence that declines in noise, interference and the wireless channel, occurs mistake sometimes.For fear of the received signal mistake, in communication system, adopt the method for chnnel coding usually.At transmitting terminal raw symbol being encoded obtains sending code element, at receiving terminal receiving symbol is deciphered to estimate to send code element.Low density parity check code (LDPC) is because its excellent performance has obtained application more and more widely in practice.LDPC has the following advantages: decoding complexity is lower, and because the computation complexity of an iteration is very low in the LDPC decoding algorithm, therefore can be by changing the optimal compromise that maximum iteration time obtains complexity and performance, and the decoding of LDPC still is highly-parallel; 1 probability is linear to be increased the minimum range of binary system LDPC to approach along with code length; Be easy to the superior LDPC of design performance according to any code length and encoding rate; LDPC does not have " mistake floor " phenomenon, and this is suitable for using the occasion of short frame.

LDPC is a kind of linear block codes, and its name derives from the sparse property of its check matrix, that is: in its check matrix in every row and the every row number of nonzero element very rare, and the position of nonzero element is random distribution.For code length is that n, information bit number are the LDPC of k, and this LDPC can be by its check matrix H_{(n-k) * n}All code element X of LDPC are described_{1 * n}, satisfy XH^T=0.Each line display of check matrix verification constraint, wherein the code element variable x of all nonzero element correspondences_j(j=1,2 ..., n) constitute a checksum set, represent with a check equations; The verification constraint that a code element variable participates in is shown in each tabulation of check matrix, when column element is non-vanishing, represents that this code element variable has participated in the verification constraint of this row.

LDPC is divided into canonical LDPC and non-canonical LDPC.The check matrix H of canonical LDPC satisfies following three conditions: every row of (1) H has λ 1, and λ 〉=3; (2) H's whenever shows ρ 1; (3) compare with the line number (n-k) of code length n and matrix, the value of ρ and λ is all very little.Canonical LDPC can with (n, λ ρ) represent, as: if a canonical LDPC code table is shown (8,4,2), then its check matrix H is:

$H=\left[\begin{array}{cccccccc}1& 0& 1& 0& 1& 0& 1& 0\\ 1& 0& 0& 1& 0& 1& 0& 1\\ 0& 1& 1& 0& 0& 1& 1& 0\\ 0& 1& 0& 1& 1& 0& 0& 1\end{array}\right]$

If the number of " 1 " is not identical entirely in each row of the check matrix H of LDPC or each row, then this LDPC is non-canonical LDPC.Usually, for the convenience that studies a question, the check matrix H of LDPC can utilize the Tanner graph model to be expressed as a bigraph (bipartite graph), as shown in Figure 1, circle point expression variable node among the figure, square dot is represented constraint, that is: every row of the corresponding check matrix H of circular point, every row of the corresponding check matrix H of square dot, the line between circular point and the square dot is represented non-0 element in the check matrix H.

A kind of interpretation method that the LDPC sign indicating number is commonly used is based on the iterative decoding scheme of probability, is exactly in fact belief propagation (BeliefPropagation) iterative decoding algorithm of attention extremely at present, also claims and amasss (Sum-Product) iterative decoding algorithm (SPA).With long-pending iterative decoding algorithm be a kind of iterative decoding algorithm, take turns in the iterative process in each of this algorithm, need between variable node and check-node, transmit about the confidential information of each node.For example: the confidential information combined calculation that the code element variable that is based on the variable node correspondence by variable node to the confidential information of check-node transmission passes in last once iterative process through the observed value behind the channel with by the check-node of adjacency.

For check matrix is H_{M * n}The LDPC sign indicating number, for convenience, provide as giving a definition:

The transmission code element is: U=[u₁, u₂..., u_n];

Receiving symbol is: Y=[y₁, y₂..., y_n];

M (j) ≡ { i:H_{I, j}=1} is illustrated in the set of the check-node that links to each other with variable node j on the bigraph (bipartite graph);

N (i) ≡ { j:H_{I, j}=1} is illustrated in the set of the variable node that links to each other with check-node i on the bigraph (bipartite graph);

M (j) i represent to gather the subclass of removing among the M (j) behind the check-node i;

N (i) j represent to gather the subclass of removing among the N (i) behind the variable node j;

q_{J → i}(x), { 0,1} represents that expression variable node j that variable node j sends to check-node i is 0 or 1 probabilistic information to x ∈;

r_{I → j}(x), { 0,1} represents that expression variable node j that check-node i sends to variable node j is 0 or 1 probabilistic information to x ∈;

The log-likelihood ratio LLR of binary system stochastic variable A is defined as:

$L\left(A\right)=\log \frac{P(A=0)}{P(A=1)}$

Wherein, P (A=x), { 0,1} represents that stochastic variable A gets the probability of x value to x ∈.In addition, also be defined as follows LLRs:

Variable node j is to the likelihood ratio of check-node i:${\mathrm{\λ}}_{j\→i}\left(u_j\right)=\log \frac{q_{j\→i}\left(0\right)}{q_{j\→i}\left(1\right)};$

Check-node i is to the likelihood ratio of variable node j:${\mathrm{\Λ}}_{i\→j}\left(u_j\right)=\log \frac{r_{i\→j}\left(0\right)}{r_{i\→j}\left(1\right)}.$

In above each definition, i=1,2 ..., m, j=1,2 ..., n, and m is the number of check-node, n is the number of variable node.

LDPC decoding is promptly by receiving symbol Y=[y₁, y₂..., y_n] and obtain sending the estimated value of code element according to the LDPC decoding algorithm$\hat{U}=\{{\hat{u}}_1,{\hat{u}}_2,...,{\hat{u}}_n\},$Fig. 2 is existing LDPC decoding flow chart, and as shown in Figure 2, its concrete steps are as follows:

Step 201: set maximum iteration time K, to each variable node j (j=1,2 ..., likelihood ratio n) is carried out initialization, simultaneously variable node is carried out initialization to likelihood ratio, the check-node of check-node to the likelihood ratio of variable node.

Particularly, variable node j (j=1,2 ..., likelihood ratio n) can be initialized as: L (u_{0, j})=log{P (u_{0, j}=0|y_j)/P (u_{0, j}=1|y_j); Simultaneously, to satisfying H_{I, j}=1 (i, j), variable node j (j=1,2 ..., n) to check-node i (i=1,2 ..., likelihood ratio m) can be initialized as: λ_{0, j → i}(u_{0, j})=L (u_{0, j}), check-node i (i=1,2 ..., m) to variable node j (j=1,2 ..., likelihood ratio n) can be initialized as: Λ_{0, i → j}(u_{0, j})=0.

Step 202: record current iteration number of times k.

Step 203: calculate current check-node i (i=1,2 ..., m) to variable node j (j=1,2 ..., likelihood ratio n).

Particularly, for i, j ∈ N (i), current check-node i (i=1,2 ..., m) to variable node j (j=1,2 ..., the computing formula of likelihood ratio n) is:

${\mathrm{\Λ}}_{k,i\→j}\left(u_{k,j}\right)=2{\tanh }^{-1}\left\{\underset{j^{\′}\∈N\left(i\right)/j}{\mathrm{\Π}}\tanh \right[{\mathrm{\λ}}_{k-1,j^{\′}\→i}\left(u_{k-1,j^{\′}}\right)/2\left]\right\}$

Wherein, λ_{K-1, j ' → i}(u_{K-1, j '}) be the variable node j ' that obtains in the k-1 time iterative process likelihood ratio to check-node i.

Step 204: calculate current variable node j (j=1,2 ..., n) to check-node i (i=1,2 ..., likelihood m) when variable node j (j=1,2 ..., n) from likelihood ratio.

Particularly, for i, j ∈ M (j), variable node j (j=1,2 ..., n) to check-node i (i=1,2 ..., the computing formula of likelihood ratio m) is:

${\mathrm{\λ}}_{k,j\→i}\left(u_{k,j}\right)=L\left(u_{k-1,j}\right)+\underset{i^{\′}\∈M\left(j\right)/i}{\mathrm{\Σ}}{\mathrm{\Λ}}_{k-1,i^{\′}\→j}\left(u_{k-1,j}\right)$

Variable node j (j=1,2 ..., the computing formula from likelihood ratio n) is:

${\mathrm{\λ}}_{k,j}\left(u_{k,j}\right)=L\left(u_{k-1,j}\right)+\underset{i\∈M\left(j\right)}{\mathrm{\Σ}}{\mathrm{\Λ}}_{k-1,i\→j}\left(u_{k-1,j}\right)$

Wherein, L (u_{K-1, j}) be the likelihood ratio of the variable node j that obtains in the k-1 time iterative process, Λ_{K-1, i ' → j}(u_{K-1, j}) be the check-node i ' that obtains in the k-1 time iterative process likelihood ratio to variable node j.

Step 205: according to variable node j (j=1,2 ..., n) calculate to send the current estimated value of code element U from likelihood ratio${\hat{U}}_k=\{{\hat{u}}_{k,1},{\hat{u}}_{k,2},...,{\hat{u}}_{k,n}\}.$

Particularly, if λ_{K, j}(u_{K, j}) 〉=0 (j=1,2 ..., n) set up, then u_{K, j}Estimated value${\hat{u}}_{k,j}=0;$Otherwise,${\hat{u}}_{k,j}=1.$

Step 206: judge check equations${\hat{U}}_k{H}^T=0$Whether set up, if,$U={\hat{U}}_k,$This flow process finishes; Otherwise, execution instep 207.

Step 207: judge the maximum iteration time K whether current iteration number of times k equals to set, if,$U={\hat{U}}_k,$This flow process finishes; Otherwise, execution instep 208.

Step 208: go tostep 202 after iterations k added 1.

Find by l-G simulation test: in signal to noise ratio one regularly,, proceed iteration again the error rate is obviously reduced, even the situation of error rate fluctuation can occur when through after the iteration of certain number of times to flow process shown in Figure 2.Therefore, in check equations${\hat{U}}_k{H}^T=0$Be false and the error rate when fluctuation occurring,, not only can not improve the decoding precision, can increase decoding delay on the contrary if proceed iteration.

Summary of the invention

In view of this, main purpose of the present invention is to provide a kind of LDPC interpretation method, deciphers precision to improve, and reduces decoding delay.

For achieving the above object, technical scheme of the present invention is achieved in that

A kind of LDPC interpretation method, this method preestablishes maximum iteration time, calculates the initialization value of iterative decoding likelihood ratio, comprising:

A, record current iteration number of times according to the iterative decoding likelihood that obtains in the preceding iterative process initialization value of iterative decoding likelihood ratio when, calculate current iteration decoding likelihood ratio; Calculate the estimated value of current transmission code element according to current iteration decoding likelihood ratio;

B, judge whether the estimated value of current transmission code element satisfies check equations, if satisfy execution in step C; If do not satisfy, judge whether the current iteration number of times equals maximum iteration time, if equal, execution in step C if be not equal to, judges whether the current error rate fluctuation occurs, if occur, execution in step C if do not occur, goes to steps A;

C, with the estimated value of current transmission code element as sending code element, this flow process finishes.

The described judgement current iteration of step B number of times is not equal to and further comprises after the maximum iteration time: calculate and preserve the number of the nonzero element in the estimated value of current transmission code element,

Step B is described to judge whether the current error rate fluctuation occurs and be specially: judge (Z_k-Z_K-1) * (Z_K-1-Z_K-2Whether set up)＜0, if set up, judges that fluctuation appears in the error rate; If be false, judge that fluctuation does not appear in the error rate,

Wherein, Z_kBe the number of nonzero element in the estimated value of described current transmission code element, Z_K-1Be the number of nonzero element in the estimated value of the transmission code element that obtains in the preceding iterative process, Z_K-2Be the number of nonzero element in the estimated value of the transmission code element that obtains in preceding twice iterative process, k is current iteration number of times and k 〉=3.

The described judgement current iteration of step B number of times is not equal to and further comprises after the maximum iteration time: preserves the estimated value of current transmission code element, calculates the Hamming distance of the estimated value of the transmission code element that obtains in the estimated value of current transmission code element and the preceding iterative process,

Step B is described to judge whether the current error rate fluctuation occurs and be specially: judge (D_k-D_K-1) * (D_K-1-D_K-2Whether set up)＜0, if set up, judges that fluctuation appears in the error rate; If be false, judge that fluctuation does not appear in the error rate,

Wherein, D_kBe the Hamming distance of the estimated value of the transmission code element that obtains in the estimated value of described current transmission code element and the preceding iterative process, D_K-1Be the Hamming distance of the estimated value of the transmission code element that obtains in the estimated value of the transmission code element that obtains in the preceding iterative process and preceding twice iterative process, D_K-2Be the Hamming distance of the estimated value of the transmission code element that obtains in the estimated value of the transmission code element that obtains in preceding twice iterative process and first three time iterative process, k is current iteration number of times and k 〉=4.

The initialization value of described calculating iterative decoding likelihood ratio is specially: the initialization value of the initialization value, variable node that calculates the likelihood ratio of each variable node to the initialization value of the likelihood ratio of check-node and check-node to the likelihood ratio of variable node;

Steps A is described according to the iterative decoding likelihood that obtains in the preceding iterative process initialization value of iterative decoding likelihood ratio when, calculates current iteration decoding likelihood ratio and is specially: calculate the likelihood ratio of current check-node to variable node according to the preceding variable node that once obtains to the likelihood ratio of check-node; According to the preceding check-node that once obtains to the likelihood of the variable node initialization value of variable node likelihood ratio when, calculate current variable node to the likelihood of check-node when current variable node from likelihood ratio;

The described estimated value of calculating current transmission code element according to current iteration decoding likelihood ratio of steps A is specially: calculate the estimated value of current transmission code element according to current variable node from likelihood ratio.

The initialization value of the likelihood ratio of described each variable node of calculating is specially:

L(u_0，j)＝log{P(u_0，j＝0|y_j)/P(u_0，j＝1|y_j)}，j＝1，2，...，n，

Wherein, L (u_{0, j}) be the initialization value of the likelihood ratio of variable node j, y_jBe j receiving symbol value, P (u_{0, j}=0|y_j) represent that j receiving symbol value is y_jThe time j to send symbol value be 0 probability, P (u_{0, j}=1|y_j) represent that j receiving symbol value is y_jThe time j to send symbol value be 1 probability, n is the number of variable node.

Described calculating variable node is specially to the initialization value of the likelihood ratio of check-node:

To satisfying H_{I, j}=1 i, j, variable node j to the initialization value of the likelihood ratio of check-node i is: λ_{0, j → i}(u_{0, j})=log{P{u_{0, j}=0|y_j)/P (u_{0, j}=1|y_j, i=1,2 ..., m, j=1,2 ..., n,

Wherein, H_{I, j}Be capable j the element of i of check matrix, λ_{0, j → i}(u_{0, j}) be the initialization value of variable node j to the likelihood ratio of check-node i, y_jBe j receiving symbol value, P (u_{0, j}=0|y_j) represent that j receiving symbol value is y_jThe time j to send symbol value be 0 probability, P (u_{0, j}=1|y_j) represent that j receiving symbol value is y_jThe time j to send symbol value be 1 probability, n is the number of variable node, m is the number of check-node.

Described calculation check node is specially to the initialization value of the likelihood ratio of variable node:

To satisfying H_{I, j}=1 i, j, check-node i to the initialization value of the likelihood ratio of variable node j is: Λ_{0, i → j}(u_{0, j})=0,

Wherein, H_{I, j}Be capable j the element of i of check matrix, Λ_{0, i → j}(u_{0, j}) being the initialization value of check-node i to the likelihood ratio of variable node j, m is the number of check-node, n is the number of variable node, i=1,2 ..., m, j=1,2 ..., n.

The current check-node of the described calculating of steps A is specially to the likelihood ratio of variable node:

${\mathrm{\Λ}}_{k,i\→j}\left(u_{k,j}\right)=2{\tanh }^{-1}\left\{\underset{j^{\′}\∈N\left(i\right)\backslash j}{\mathrm{\Π}}\tanh \right[{\mathrm{\λ}}_{k-1,j^{\′}\→i}\left(u_{k-1,j^{\′}}\right)/2\left]\right\},j\∈N\left(i\right)$

Wherein, Λ_{K, i → j}(u_{K, j}) be the likelihood ratio of current check-node i to variable node j, λ_{K-1, j ' → i}(u_{K-1, j '}) the variable node j ' that obtains in the preceding iterative process of expression is to the likelihood ratio of check-node i, N (i) is illustrated in the set of the variable node that links to each other with check-node i on the bigraph (bipartite graph), and N (i) j is illustrated in the subclass of removing in the set of the variable node that links to each other with check-node i on the bigraph (bipartite graph) behind the variable node j, m is the number of check-node, and n is the number of variable node, and k is the current iteration number of times, k-1 is a preceding iterations, i=1,2, ..., m, j=1,2, ..., n.

The current variable node of the described calculating of steps A is specially to the likelihood ratio of check-node:

${\mathrm{\λ}}_{k,j\→i}\left(u_{k,j}\right)=L\left(u_{k-1,j}\right)+\underset{i^{\′}\∈M\left(j\right)\backslash i}{\mathrm{\Σ}}{\mathrm{\Λ}}_{k-1,i^{\′}\→j}\left(u_{k-1,j}\right),i\∈M\left(j\right)$

Wherein, λ_{K, j → i}(u_{K, j}) be the likelihood ratio of current variable node j to check-node i, L (u_{K-1, j}) likelihood ratio of the variable node j that obtains in the preceding iterative process of expression, Λ_{K-1, i ' → j}(u_{K-1, j}) the check-node i ' that obtains in the preceding iterative process of expression is to the likelihood ratio of variable node j, M (j) is illustrated in the set of the check-node that links to each other with variable node j on the bigraph (bipartite graph), and M (j) i is illustrated in the subclass of removing in the set of the check-node that links to each other with variable node j on the bigraph (bipartite graph) behind the check-node i, n is the number of variable node, and m is the number of check-node, and k is the current iteration number of times, k-1 is a preceding iterations, i=1,2, ..., m, j=1,2, ..., n.

Being specially of the steps A current variable node of described calculating from likelihood ratio:

${\mathrm{\λ}}_{k,j}\left(u_{k,j}\right)=L\left(u_{k-1,j}\right)+\underset{i\∈M\left(j\right)}{\mathrm{\Σ}}{\mathrm{\Λ}}_{k-1,i\→j}\left(u_{k-1,j}\right)$

The estimated value of the current transmission code element of described calculating is specially:

Judge λ_{K, j}(u_{K, j}) 〉=0, j=1,2 ..., whether n sets up, if,

Otherwise,

Wherein, λ_{K, j}(u_{K, j}) expression current variable node j from likelihood ratio, L (u_{K-1, j}) likelihood ratio of the variable node j that obtains in the preceding iterative process of expression, Λ_{K-1, i → j}(u_{K-1, j}) the check-node i that obtains in the preceding iterative process of expression is to the likelihood ratio of variable node j, M (j) is illustrated in the set of the check-node that links to each other with variable node j on the bigraph (bipartite graph),Be current j estimated value that sends code element, n is the number of variable node, and k is the current iteration number of times, and k-1 is a preceding iterations.

Compared with prior art, provided by the present inventionly in the current iteration process, obtain sending the symbol estimation value, and judging that current transmission symbol estimation value does not satisfy after check equations and current iteration number of times be not equal to maximum iteration time, judge further whether the current error rate fluctuation occurs, if occur, as sending code element, this flow process finishes with the estimated value of current transmission code element; Otherwise, proceed the next iteration process, make when fluctuation appears in the error rate, in time stop iterative process, improved the decoding precision, reduced decoding delay.Particularly, can judge whether the error rate fluctuation occurs by the difference of nonzero element number in the transmission symbol estimation value that obtains in adjacent twice iterative process, the difference of Hamming distance that also can be by the transmission symbol estimation value that obtains in the adjacent iterative process in twos judges whether the error rate fluctuation occurs.

Description of drawings

Fig. 1 is the Tanner schematic diagram of the check matrix of LDPC;

Fig. 2 is existing LDPC decoding flow chart;

Fig. 3 is the flow chart of LDPC decoding provided by the invention;

Fig. 4 is the flow chart of the specific embodiment one of LDPC decoding provided by the invention;

Fig. 5 is the flow chart of the specific embodiment two of LDPC decoding provided by the invention.

Embodiment

The present invention is further described in more detail below in conjunction with drawings and the specific embodiments.

Fig. 3 is the flow chart of LDPC decoding provided by the invention, and as shown in Figure 3, its concrete steps are as follows:

Step 301: set maximum iteration time K, according to receiving symbol Y=[y₁, y₂..., y_n] to each variable node j (j=1,2 ..., likelihood ratio n) is carried out initialization, simultaneously variable node is carried out initialization to likelihood ratio, the check-node of check-node to the likelihood ratio of variable node.

Here, initializing variable node j (j=1,2 ..., likelihood ratio n), variable node j (j=1,2, ..., n) to check-node i (i=1,2 ..., likelihood m) is check-node i (i=1,2 when, ..., m) to variable node j (j=1,2 ..., likelihood ratio n) is same as the prior art.

Step 302: record current iteration number of times k.

Step 303: calculate current check-node i (i=1,2 ..., m) to variable node j (j=1,2 ..., likelihood ratio n).

This step is same as the prior art.

Step 304: calculate current variable node j (j=1,2 ..., n) to check-node i (i=1,2 ..., likelihood m) when variable node j (j=1,2 ..., n) from likelihood ratio.

This step is same as the prior art.

Step 305: according to variable node j (j=1,2 ..., n) calculate to send the current estimated value of code element U from likelihood ratio${\hat{U}}_k=\{{\hat{u}}_{k,1},{\hat{u}}_{k,2},...,{\hat{u}}_{k,n}\}.$

This step is same as the prior art.

Step 306: judge${\hat{U}}_k{H}^T=0$Whether set up, if,$U={\hat{U}}_k,$This flow process finishes; Otherwise, execution in step 307.Wherein, H^TTransposed matrix for check matrix H.

Step 307: judge whether current iteration number of times k equals maximum iteration time K, if,$U={\hat{U}}_k,$This flow process finishes; Otherwise, execution in step 308.

Step 308: judge whether the current error rate fluctuation occurs, if,$U={\hat{U}}_k,$This flow process finishes; Otherwise, execution instep 309.

Step 309: k adds 1 with iterations, goes to step 302 then.

Fig. 4 is the flow chart of the specific embodiment one of LDPC decoding provided by the invention, and as shown in Figure 4, its concrete steps are as follows:

Step 401～405 are identical with step 301～305.

Step 406: judge${\hat{U}}_k{H}^T=0$Whether set up, if,$U={\hat{U}}_k,$This flow process finishes; Otherwise, execution instep 407.

Step 407: judge whether current iteration number of times k equals maximum iteration time K, if,$U={\hat{U}}_k,$This flow process finishes; Otherwise, execution instep 408.

Step 408: record${\hat{U}}_k=\{{\hat{u}}_{k,1}{\hat{u}}_{k,2},...,{\hat{u}}_{k,n}\}$The number Z of middle nonzero element_k

Step 409: judge (Z_k-Z_K-1) * (Z_K-1-Z_K-2)＜0, whether set up k 〉=3, if,$U={\hat{U}}_k,$This flow process finishes; Otherwise, execution instep 410.

Here, Z_K-1Represent to obtain in the k-1 time iterative process

The number of middle nonzero element, Z_K-2Represent to obtain in the k-2 time iterative process

The number of middle nonzero element.

Step 410: go to step 402 after iterations k added 1.

When k＜3, execution instep 409 is not promptly: after the execution ofstep 408, and direct execution instep 410.

Fig. 5 is the flow chart of the specific embodiment two of LDPC decoding provided by the invention, and as shown in Figure 5, its concrete steps are as follows:

Step 501～505 are identical with step 301～305.

Step 506: judge${\hat{U}}_k{H}^T=0$Whether set up, if,$U={\hat{U}}_k,$This flow process finishes; Otherwise, execution instep 507.

Step 507: judge whether current iteration number of times k equals maximum iteration time K, if,$U={\hat{U}}_k,$This flow process finishes; Otherwise, execution instep 508.

Step 508: calculate and preserve

With

Hamming distance D_k

Step 509: judge (D_k-D_K-1) * (D_K-1-D_K-2)＜0, whether set up k 〉=4, if,$U={\hat{U}}_k,$This flow process finishes; Otherwise, execution instep 510.

Here, D_K-1Expression

With

Hamming distance, D_K-2ExpressionWith

Hamming distance.

Step 510: go to step 502 after iterations k added 1.

When k＜4, execution instep 509 is not promptly: after the execution ofstep 508, and direct execution instep 510.

The above only is process of the present invention and method embodiment, in order to restriction the present invention, all any modifications of being made within the spirit and principles in the present invention, is not equal to replacement, improvement etc., all should be included within protection scope of the present invention.

Claims (8)

Translated fromChinese

1.一种低密度奇偶校验码LDPC译码方法，其特征在于，预先设定最大迭代次数，计算迭代译码似然比的初始化值，该方法包括：1. A low-density parity-check code LDPC decoding method is characterized in that, the maximum number of iterations is preset, and the initialization value of the iterative decoding likelihood ratio is calculated, and the method comprises:A、记录当前迭代次数，根据前一次迭代过程中得到的迭代译码似然比及迭代译码似然比的初始化值，计算当前迭代译码似然比；根据当前迭代译码似然比计算当前发送码元的估计值；A. Record the current iteration number, calculate the current iterative decoding likelihood ratio according to the iterative decoding likelihood ratio obtained in the previous iteration process and the initialization value of the iterative decoding likelihood ratio; calculate according to the current iterative decoding likelihood ratio Estimated value of the currently transmitted symbol;B、判断当前发送码元的估计值是否满足校验方程，若满足，执行步骤D；若不满足，判断当前迭代次数是否等于最大迭代次数，若等于，执行步骤D，若不等于，执行步骤C；B. Judging whether the estimated value of the currently transmitted symbol satisfies the verification equation, if it is satisfied, execute step D; if not, judge whether the current iteration number is equal to the maximum iteration number, if it is equal, execute step D, if not, execute step C;C、判断(Z_k-Z_k-1)*(Z_k-1-Z_k-2)＜0是否成立，若是，执行步骤D；否则，转至步骤A；C. Judging whether (Z_k -Z_k-1 )*(Z_k-1 -Z_k-2 )<0 holds true, if so, execute step D; otherwise, go to step A;其中，Z_k为所述当前发送码元的估计值中非零元素的个数，Z_k-1为前一次迭代过程中得到的发送码元的估计值中非零元素的个数，Z_k-2为前两次迭代过程中得到的发送码元的估计值中非零元素的个数，k为当前迭代次数且k≥3；Wherein, Z_k is the number of non-zero elements in the estimated value of the current transmission symbol, Z_k-1 is the number of non-zero elements in the estimated value of the transmission symbol obtained in the previous iteration process, Z_{k -2} is the number of non-zero elements in the estimated value of the transmitted symbol obtained in the previous two iterations, k is the current number of iterations and k≥3;或者，判断(D_k-D_k-1)*(D_k-1-D_k-2)＜0是否成立，若是，执行步骤D；否则，转至步骤A；Alternatively, judge whether (D_k -D_k-1 )*(D_k-1 -D_k-2 )<0 is true, if so, execute step D; otherwise, go to step A;其中，D_k为所述当前发送码元的估计值与前一次迭代过程中得到的发送码元的估计值的汉明距离，D_k-1为前一次迭代过程中得到的发送码元的估计值与前两次迭代过程中得到的发送码元的估计值的汉明距离，D_k-2为前两次迭代过程中得到的发送码元的估计值与前三次迭代过程中得到的发送码元的估计值的汉明距离，k为当前迭代次数且k≥4；Among them,_Dk is the Hamming distance between the estimated value of the current transmitted symbol and the estimated value of the transmitted symbol obtained in the previous iteration process, and Dk_-1 is the estimated value of the transmitted symbol obtained in the previous iteration process The Hamming distance between the value and the estimated value of the transmitted symbol obtained in the first two iterations, D_k-2 is the estimated value of the transmitted symbol obtained in the first two iterations and the transmitted code obtained in the first three iterations The Hamming distance of the estimated value of the element, k is the current iteration number and k≥4;D、将当前发送码元的估计值作为发送码元，本流程结束。D. The estimated value of the current transmitted symbol is used as the transmitted symbol, and this process ends.2.如权利要求1所述的方法，其特征在于，所述计算迭代译码似然比的初始化值具体为：计算各变量节点的似然比的初始化值、变量节点到校验节点的 似然比的初始化值及校验节点到变量节点的似然比的初始化值；2. The method according to claim 1, wherein the initialization value of the iterative decoding likelihood ratio of the calculation is specifically: calculating the initialization value of the likelihood ratio of each variable node, the likelihood ratio of the variable node to the check node The initialization value of the likelihood ratio and the initialization value of the likelihood ratio from the check node to the variable node;步骤A所述根据前一次迭代过程中得到的迭代译码似然比及迭代译码似然比的初始化值，计算当前迭代译码似然比具体为：根据前一次得到的变量节点到校验节点的似然比计算当前校验节点到变量节点的似然比；根据前一次得到的校验节点到变量节点的似然比及变量节点似然比的初始化值，计算当前变量节点到校验节点的似然比及当前变量节点的自似然比；In step A, according to the iterative decoding likelihood ratio obtained in the previous iteration process and the initialization value of the iterative decoding likelihood ratio, the calculation of the current iterative decoding likelihood ratio is specifically: according to the variable node obtained in the previous iteration to check The likelihood ratio of the node calculates the likelihood ratio from the current check node to the variable node; according to the likelihood ratio from the check node to the variable node obtained last time and the initialization value of the variable node likelihood ratio, calculate the current variable node to the check node. The likelihood ratio of the node and the self-likelihood ratio of the current variable node;步骤A所述根据当前迭代译码似然比计算当前发送码元的估计值具体为：根据当前变量节点的自似然比计算当前发送码元的估计值。The calculation of the estimated value of the current transmitted symbol according to the likelihood ratio of the current iterative decoding in step A is specifically: calculating the estimated value of the current transmitted symbol according to the natural likelihood ratio of the current variable node.3.如权利要求2所述的方法，其特征在于，所述计算各变量节点的似然比的初始化值具体为：L(u_0，j)＝log{P(u_0，j＝0|y_j)/P(u_0，j＝1|y_j)}，j＝1，2，...，n，3. The method according to claim 2, wherein the initialization value of the likelihood ratio of each variable node is specifically: L(u_{0, j} )=log{P(u_{0, j} =0| y_j )/P(u_{0, j} =1|y_j )}, j=1, 2,..., n,其中，L(u_0，j)为变量节点j的似然比的初始化值，y_j为第j个接收码元值，P(u_0，j＝0|y_j)表示第j个接收码元值为y_j时第j个发送码元值为0的概率，P(u_0，j＝1|y_j)表示第j个接收码元值为y_j时第j个发送码元值为1的概率，n为变量节点的个数。Among them, L(u_{0, j} ) is the initialization value of the likelihood ratio of variable node j, y_j is the value of the jth received symbol, P(u_{0, j} = 0|y_j ) represents the jth received code The probability that the value of the jth transmitted symbol is 0 when the element value is y_j , P(u_{0, j} = 1|y_j ) means that when the value of the jth received symbol is y_j , the value of the jth transmitted symbol is The probability of 1, n is the number of variable nodes.4.如权利要求2所述的方法，其特征在于，所述计算变量节点到校验节点的似然比的初始化值具体为：4. The method according to claim 2, wherein the initialization value of the likelihood ratio from the calculation variable node to the check node is specifically:对满足H_i，j＝1的i、j，变量节点j到校验节点i的似然比的初始化值为：λ_0，j→i(u_0，j)＝log{P{u_0，j＝0|y_j)/P(u_0，j＝1|y_j}，i＝1，2，...，m，j＝1，2，...，n，For i, j satisfying H_{i, j} = 1, the initialization value of the likelihood ratio from variable node j to check node i is: λ_{0, j→i} (u_{0, j} )=log{P{u_{0, j} = 0|y_j )/P(u_{0, j} = 1|y_j }, i=1, 2,..., m, j=1, 2,..., n,其中，H_i，j为校验矩阵的第i行第j个元素，λ_0，j→i(u_0，j)为变量节点j到校验节点i的似然比的初始化值，y_j为第j个接收码元值，P(u_0，j＝0|y_j)表示第j个接收码元值为y_j时第j个发送码元值为0的概率，P(u_0，j＝1|y_j)表示第j个接收码元值为y_j时第j个发送码元值为1的概率，n为变量节点的个数，m为校验节点的个数。Among them, H_{i, j} is the jth element of the i-th row of the check matrix, λ_{0, j→i} (u_{0, j} ) is the initialization value of the likelihood ratio from the variable node j to the check node i, and y_j is the jth received symbol value, P(u_{0, j} =0|y_j ) represents the probability that the jth transmitted symbol value is 0 when the jth received symbol value is y_j , P(u_{0, j} =1|y_j ) indicates the probability that the value of the jth transmitted symbol is 1 when the value of the jth received symbol is y_j , n is the number of variable nodes, and m is the number of check nodes.5.如权利要求2所述的方法，其特征在于，所述计算校验节点到变量节点的似然比的初始化值，具体为： 5. The method according to claim 2, wherein the initialization value of the likelihood ratio of the calculation check node to the variable node is specifically:对满足H_i，j＝1的i、j，校验节点i到变量节点j的似然比的初始化值为：Λ_0，i→j(u_0，j)＝0，For i, j satisfying H_{i, j} = 1, the initialization value of the likelihood ratio from check node i to variable node j is: Λ_{0, i→j} (u_{0, j} ) = 0,其中，H_i，j为校验矩阵的第i行第j个元素，Λ_0，i→j(u_0，j)为校验节点i到变量节点j的似然比的初始化值，m为校验节点的个数，n为变量节点的个数，i＝1，2，...，m，j＝1，2，...，n。Among them, H_{i, j} is the jth element of the i-th row of the check matrix, Λ_{0, i→j} (u_{0, j} ) is the initialization value of the likelihood ratio from the check node i to the variable node j, and m is The number of check nodes, n is the number of variable nodes, i=1, 2, . . . , m, j=1, 2, . . . , n.6.如权利要求2所述的方法，其特征在于，步骤A所述计算当前校验节点到变量节点的似然比具体为：6. The method according to claim 2, wherein the likelihood ratio of calculating the current check node to the variable node in step A is specifically:

其中，Λ_k，i→j(u_k，j)为当前校验节点i到变量节点j的似然比，λ_{k-1，j′→i}(u_k-1，j′)表示前一次迭代过程中得到的变量节点j′到校验节点i的似然比，N(i)表示在二部图上与校验节点i相连的变量节点的集合，N(i)\j表示在二部图上与校验节点i相连的变量节点的集合中除去变量节点j后的子集合，m为校验节点的个数，n为变量节点的个数，k为当前迭代次数，k-1为前一次迭代次数，i＝1，2，...，m，j＝1，2，...，n。Among them, Λ_{k, i→j} (u_{k, j} ) is the likelihood ratio from the current check node i to the variable node j, λ_{k-1, j′→i} (u_{k-1, j′} ) means the previous The likelihood ratio of the variable node j′ to the check node i obtained in the iterative process, N(i) represents the set of variable nodes connected to the check node i on the bipartite graph, and N(i)\j represents the In the set of variable nodes connected to check node i on the partial graph, the sub-set after removing variable node j, m is the number of check nodes, n is the number of variable nodes, k is the number of current iterations, k-1 is the number of previous iterations, i=1, 2, . . . , m, j=1, 2, . . . , n.7.如权利要求2所述的方法，其特征在于，步骤A所述计算当前变量节点到校验节点的似然比具体为：7. The method according to claim 2, wherein the calculation of the likelihood ratio from the current variable node to the check node in step A is specifically:

其中，λ_k，j→i(u_k，j)为当前变量节点j到校验节点i的似然比，L(u_k-1，j)表示前一次迭代过程中得到的变量节点j的似然比，Λ_{k-1，i′→j}(u_k-1，j)表示前一次迭代过程中得到的校验节点i到变量节点j的似然比，M(j)表示在二部图上与变量节点j相连的校验节点的集合，M(j)\i表示在二部图上与变量节点j相连的校验节点的集合中除去校验节点i后的子集合，n为变量节点的个数，m为校验节点的个数，k为当前迭代次数，k-1为前一次迭代次数，i＝1，2，...，m，j＝1，2，...，n。Among them, λ_{k, j→i} (u_{k, j} ) is the likelihood ratio from the current variable node j to the check node i, and L(u_{k-1, j} ) represents the variable node j obtained in the previous iteration process. Likelihood ratio, Λ_{k-1, i′→j} (u_{k-1, j} ) represents the likelihood ratio from check node i to variable node j obtained in the previous iteration process, and M(j) represents the The set of check nodes connected to variable node j on the graph, M(j)\i represents the sub-set after checking node i is removed from the set of check nodes connected to variable node j on the bipartite graph, and n is The number of variable nodes, m is the number of check nodes, k is the current iteration number, k-1 is the previous iteration number, i=1, 2,..., m, j=1, 2, .. ., n.8.如权利要求2所述的方法，其特征在于，步骤A所述计算当前变量 节点的自似然比具体为：8. method as claimed in claim 2, is characterized in that, the self-likelihood ratio of calculating current variable node described in step A is specifically:

所述计算当前发送码元的估计值具体为：The calculation of the estimated value of the current sending symbol is specifically:判断λ_k，j(u_k，j)≥0，j＝1，2，...，n是否成立，若是， 

否则， 

Judging whether λ_{k, j} (u_{k, j} )≥0, j=1, 2, ..., n is established, if so,

otherwise,

其中，λ_k，j(u_k，j)表示当前变量节点j的自似然比，L(u_k-1，j)表示前一次迭代过程中得到的变量节点j的似然比，Λ_k-1，i→j(u_k-1，j)表示前一次迭代过程中得到的校验节点i到变量节点j的似然比，M(j)表示在二部图上与变量节点j相连的校验节点的集合， 

为当前第j个发送码元的估计值，n为变量节点的个数，k为当前迭代次数，k-1为前一次迭代次数。 Among them, λ_{k, j} (u_{k, j} ) represents the natural likelihood ratio of the current variable node j, L(u_{k-1, j} ) represents the likelihood ratio of the variable node j obtained in the previous iteration, Λ_{k -1, i→j} (u_{k-1, j} ) means the likelihood ratio from the check node i to the variable node j obtained in the previous iteration process, and M(j) means that it is connected to the variable node j on the bipartite graph The set of check nodes,

is the estimated value of the current jth transmitted symbol, n is the number of variable nodes, k is the current iteration number, and k-1 is the previous iteration number.

Images