Granted Patent B2

US 7,484,158 · App. 11/003,940 · Granted Jan 27, 2009

Abstract

Claims (32)

1. A method for decoding a noisy codeword received from a communication channel as the result of transmitting a LDPC codeword having a first number (N) of codeword bits which comprise a second number (K) of information bits and a third number (M) of parity check bits, wherein the product of the LDPC codeword and a predetermined M×N parity check matrix is zero, wherein the parity check matrix represents a bipartite graph comprising N variable nodes connected to M check nodes via edges according to matrix elements of the parity check matrix, the method comprising:

receiving the noisy codeword via said communication channel;

calculating, for each of said N codeword bits of said LDPC codeword, an a-priori estimate (Qv) that the codeword bit has a predetermined value from the received noisy codeword and from predetermined parameters of said communication channel;

storing the calculated estimates (Qv) for each variable node of said bipartite graph corresponding to a codeword bit in a memory as initialization variable node values; and

iteratively calculating messages on all edges of said bipartite graph according to a serial schedule; wherein in each iteration, for each check node of said bipartite graph, for all neighboring variable nodes connected to said check node, input messages to said check node from said neighboring variable nodes and output messages from said check node to said neighboring variable nodes are calculated by means of a message passing computation rule.

2. The method of claim 1 wherein the bipartite graph is a Tanner graph.

3. The method of claim 1 wherein the message passing procedure is a belief propagation algorithm.

4. The method of claim 1 wherein the message passing procedure is a Min-Sum algorithm.

5. The method of claim 1 wherein the calculated a-priori estimates are log-likelihood ratios.

6. The method of claim 1 wherein the calculated a-priori estimates are probabilities.

7. The method of claim 1 wherein a decoding failure is indicated when the number of iterations reaches an adjustable threshold value.

8. An LDPC decoder operable to decode a noisy codeword received from a communication channel as the result of transmitting a LDPC codeword having a first number N of codeword bits which comprises a second number K of information bits and a third number N of parity check bits, wherein the product of the LDPC codeword and a predetermined M×N parity check matrix is zero, and wherein the parity check matrix represents a bipartite graph comprising N variable nodes connected to M check nodes via edges according to matrix elements of the parity check matrix, the LDPC decoder comprising:

(a) a memory operable to store a priori estimates for each codeword bit of the received noisy codeword that said codeword bit has a predetermined value from the received noisy codeword and from predetermined parameters of the communication channel; and

(b) a plurality of check node processing units operable to iteratively calculate messages on all edges of said bipartite graph according to a serial schedule, wherein in each iteration, for each check node of said bipartite graph, for all neighboring variable nodes connected to said check node, input messages to said check node from said neighboring variable nodes and output messages from the check node to said neighboring variable nodes are calculated by means of a message passing computation rule.

9. The LDPC decoder of claim 8 wherein the LDPC decoder comprises a read only memory for storing the bipartite graph.

10. The LDPC decoder of claim 8 wherein the LDPC decoder comprises a further memory operable to temporarily store the output messages.

11. The LDPC decoder of claim 8 wherein the LDPC decoder comprises a convergence testing block operable to indicate whether a decoding process has converged successfully.

12. The LDPC decoder of claim 8 where the LDPC codeword is encoded by multiplying an information bit vector with a K×N generator matrix, wherein the product of said generator matrix and the transposed parity check matrix is zero.

13. A method for decoding a noisy codeword received from a noisy communication channel as a result of a LDPC codeword transmitted through the communication channel, the transmitted LDPC codeword having a plurality of codeword bits which comprise a plurality of information bits and a plurality of parity check bits, the plurality of codeword bits belonging to a low-density parity-check code for which a parity check matrix is represented by a bipartite graph comprising a plurality of variable nodes connected to a plurality of check nodes via edges according to matrix elements of the parity check matrix, the method comprising:

(a) receiving the noisy codeword via said communication channel;

(b) calculating for each of the plurality of codeword bits of said transmitted LDPC codeword an a priori estimate that the codeword bit has a predetermined value from the received noisy codeword and from predetermined parameters of said communication channel;

(c) storing the calculated a priori estimates for each of the plurality of variable nodes of said bipartite graph in a memory as initialization varible node values;

(d) storing check-to-variable messages from each of the plurality of check nodes to all variable nodes of said bipartite graph in said memory, initialized to zero;

(e) iteratively calculating messages on all edges of said bipartite graph according to a serial schedule, in which at each iteration, all of the plurality of check nodes of said bipartite graph are serially traversed and for each of the plurality of check nodes of said bipartite graph the following calculations are performed:

(e1) reading from the memory stored messages and stored check-to-variable messages for all neighboring variable nodes connected to said check node;

(e2) calculating by means of a message passing computation rule, for all neighboring variable nodes connected to said check node, variable-to-check messages as a function of the messages and the check-to-variable messages read from said memory;

(e3) calculating by means of a message passing computation rule, for all neighboring variable nodes connected to said check node, updated check-to-variable messages as a function of the calculated variable-to-check message;

(e4) calculating by means of a message passing computation rule, for all neighboring variable nodes connected to said check node, updated a-posteriori messages as a function of the former messages and the updated check-to-variable messages;

(e5) storing the updated a posteri messages and updated check-to-variable messages back into said memory;

(f) calculating a decoded codeword as a function of the a-posteriori mesaages stored said memory;

(g) checking whether a decoding has converged by checking if the product of the parity check matrix and the decoded codeword is zero; and

(h) outputting the decoded codeword once the decoding has converged or once a predetermined maximum number of iterations has been reached.

Assignments (9)