CN1713530A - LDPC Decoder for Decoding Low Density Parity Check (LDPC) Codewords - Google Patents

Abstract

LDPC decoder for decoding a code word (Y) received from a communication channel as the result of transmitting a Low Density Parity Check (LDPC) code word (b) having a number (N) of code word bits which consists of K information bits and N parity check bits, which comprises: (a) a memory (3) for storing for each codeword bit of the received noisy codeword (Y) a priori estimates (Qv) that said codeword bit has a predetermined value from the received noisy codeword (Y) and from predetermined parameters of the communication channel; (b) generalized check node processing units (5) for calculating iteratively messages on all edges of said bipartite graph according to a serial schedule wherein in each iteration, for each check node (C) of said bipartite graph, for all neighboring variable nodes (V) connected to said check node (C) input messages (QVC) to said check node (C) from said neighboring variable nodes (V) and output messages (RCV) from the check node (C) to said neighboring variable nodes (V) are calculated by means of a message passing computation rule.

Description

LDPC Decoder for Decoding Low Density Parity Check (LDPC) Codewords

technical field

The present invention relates to the field of data communication, in particular, to redundant coding for error correction and error detection.

Background technique

Low-density parity-check codes (LDPCs) are a class of linear block codes that provide near capacity performance for larger sets of data transmission and storage channels, while allowing achievable encoding and decoding strategies. LDPC codes were first proposed by Gallager in his doctoral dissertation in 1960 (R. Gallager: "Low-density parity check codes", IRE Transformation Series pp. 21-28, January 1962). From a practical point of view, the most notable feature of Gallager's work is the citation of an iterative decoding algorithm, for which he has shown that, when applied to sparse parity-check matrices, it is possible to A significant portion of the channel capacity is achieved.

LDPC codes are defined using a sparse parity check matrix comprising a small number of non-zero entries. For each parity check matrix H, there exists a corresponding bipartite Tannergraph, with variable nodes (V) and check nodes (C). When the element h _ij of the parity check matrix H is 1, the check node C is connected to the variable node V. The parity check matrix H includes M rows and N columns. The number N of columns corresponds to the number N of codeword bits within an encoded codeword b. The codeword includes K information bits and M parity bits. The number of rows in the parity check matrix H corresponds to the number M of parity bits in the codeword. In the corresponding Tanner graph, there are M=NK check nodes C, one for each check equation, and N variable nodes, one for each code bit of the codeword.

Figure 1 shows an example of a sparse parity-check matrix H and the corresponding bipartite Tanner graph.

A regular (d _v , d _c )-LDPC code is defined using a regular bipartite graph. Each left node (called a variable node and denoted v) emits a d _v edge for each parity check in which the corresponding bit participates. Each right node (called a check node and denoted c) emits a d _c edge to each variable node v participating in the corresponding parity check.

Therefore, in the bipartite graph, there are N* _dv =M* _dc edges, and the design rate R of the LDPC code is given by the following equation:

$\mathrm{<span\; class="notranslate">\; R</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; K</span>}<span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\frac{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; v</span>}}}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}}<span\; class="notranslate">\; .</span>$

Since parity can be correlated, the actual rate R for a given LDPC code from the overall regular (d _v , d _c )-LDPC code can be higher.

Regular LDPC codes can be generalized to irregular LDPC codes, which exhibit better performance than regular LDPC codes. (λ(χ), ρ(χ))-irregular LDPC codes are represented by an irregular bipartite graph, where the degree of each left and right node can be different. The population of irregular LDPC codes is defined by left and right degree distributions.

in $\mathrm{\&lambda;}\left(x\right)={\mathrm{\&Sigma;}}_{i=2}^{d_v}{\mathrm{\&lambda;}}_i{x}^{i-1}$ and $\mathrm{\&rho;}\left(x\right)={\mathrm{\&Sigma;}}_{i=2}^{d_c}{\mathrm{\&rho;}}_i{x}^{i-1}$ are the generating functions of the degree distributions of variable and check nodes, respectively, where λ _i and ρ _i are the fractions of the edges of variable node v and check node c belonging to order i respectively, and d _v and d _c are the maximum left and The right times, then the design rate R of the LDPC code is given by the following equation:

$\mathrm{<span\; class="notranslate">\; R</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\frac{{<span\; class="notranslate">\; \&Integral;</span>}_{\mathrm{<span\; class="notranslate">\; 0</span>}}^{\mathrm{<span\; class="notranslate">\; 1</span>}}\mathrm{<span\; class="notranslate">\; \&rho;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; dx</span>}}{{<span\; class="notranslate">\; \&Integral;</span>}_{\mathrm{<span\; class="notranslate">\; 0</span>}}^{\mathrm{<span\; class="notranslate">\; 1</span>}}\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span>\mathrm{<span\; class="notranslate">\; dx</span>}}<span\; class="notranslate">\; .</span>$

In order to generate capacity close to LDPC codes, the order distribution can be optimized.

LDPC codes can utilize an iterative message passing decoding algorithm to achieve a significant portion of the channel capacity with relatively low complexity. These algorithms are based on Tanner graph representations of encodings, where the decoding understands message passing between variable nodes V and check nodes C in a Tanner graph as shown in FIG. 1 .

How LDPC codes and their message-passing decoding algorithms work is best illustrated with simple examples as shown in Figures 2 and 3.

Figure 2 shows a simple Tanner graph for an LDPC code, with four variable nodes V ₁ , V ₂ , V ₃ , V ₄ and two check or constraint nodes C ₁ , C ₂ . Therefore, the block length of the codeword is N=4 and the number of parity check bits M=2. As a result, the number k of information bits is NM=2.

The code rate R (R=k/N), defined as the ratio between the number of information bits k and the block length N, is 1/2 in this example.

A parity check matrix H corresponding to a bipartite Tanner graph is shown in FIG. 2 .

For LDPC codes, there is a generator matrix G such as:

G H ^T = (1)

That is, the product of the generator matrix G and the transposed corresponding parity check matrix H ^T is zero.

Figure 3 shows two transceivers connected by an additive white Gaussian noise (AWGN) channel. LDPC codes can be applied to any possible communication channel. During data transmission, the communication channel corrupts the transmitted codeword, changing ones to zeros, or vice versa. In order to reduce the bit error rate BER, as shown in FIG. 3, the transmitting transceiver includes an LDCP encoder for multiplying an information bit vector i with K=2 information bits by a generator matrix G of an LDPC code. In the example of Figure 2, the LDCP encoder outputs an encoded bit vector b modulated by a modulator within the transceiver. In the given example, the modulator transforms a low logic value zero of the encoded bit vector b into a transmitted bit X=1, and a logic high value of the encoded bit vector b into X=-1. The transmitting transceiver transmits the modulated codeword X to the receiving transceiver through the communication channel, as shown in FIG. 3 . In the given example, the communication channel is a binary input AWGN channel with a one-sided spectral noise density N=8.

The receiving transceiver receives a codeword Y from a communication channel having a value N.

The codeword Y is formed by adding noise to the transmitted vector X:

Y＝X+noise (2)

The received codeword Y is demodulated and the log-likelihood ratios (LLRs) of the received codeword bits are calculated. For the binary input AWGN channel, the log likelihood ratio LLR is calculated according to the following formula:

${\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; ln</span>}<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; PR</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; /</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; PR</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; /</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 4</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}\mathrm{<span\; class="notranslate">\; 0</span>}}{\mathrm{<span\; class="notranslate">\; Y</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

FIG. 3 shows the log-likelihood ratios for N ₀ =8, where each received codeword value is divided by two. The log-likelihood ratio LLR gives an a priori estimate that the received codeword bits have a predetermined value.

These estimates are forwarded into an LDPC decoder within the transceiver for performing the LDPC decoding process.

Traditional LDPC decoders use a standard message-passing schedule to decode LDPC codes, known as the flooding schedule, as in R. Gallager: "Low-density parity check codes", IRE Transformation Series pp. 21-28, 1962 described in January.

A schedule is an update rule that enforces the order in which messages are passed between nodes in a Tanner graph. Conventional LDPC decoders according to the state of the art employ message passing procedures such as the overflow-scheduled based concise propagation algorithm BP.

Fig. 4 shows a flowchart of the concise propagation BP process with overflow scheduling according to the state of the art.

FIG. 5 shows the concise propagation BP decoding process using the standard overflow procedure as shown in FIG. 4 for the example of FIG. 3 .

As can be seen in Figure 4, the received codeword Y is demodulated and the log-likelihood ratio LLR is calculated.

In initialization step S1, the message _Rcv from check node C to variable node V is set to zero for all check nodes and for all variable nodes. In addition, the message Q _vc from the variable node to the check node in the Tanner diagram is initialized by using the calculated prior estimate P _v or the log likelihood ratio.

Additionally, as shown in Figure 4, the iteration counter path is set to zero.

In step S2, the message R _cv from the check node to the variable node QVC is updated. This calculation is performed by the check node processor, as shown in FIG. 7 .

The computation performed by a check node processor can be described as the following equation:

For all v ∈ N(c):

in,

where the sign function is defined as

$\mathrm{<span\; class="notranslate">\; sign</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\left\{\begin{array}{cc}\mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; \&Greater\; Equal;</span>\mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; 1</span>}& \mathrm{<span\; class="notranslate">\; x</span>}<span\; class="notranslate">\; <</span>\mathrm{<span\; class="notranslate">\; 0</span>}\end{array}\right\}$

In step S3, the message Q _VC from the variable node V to the check node C is updated by the variable node processor, as shown in FIG. 8 .

The updating of variables to the check message Q _VC can be described as follows:

${\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; V</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; V</span>}}<span\; class="notranslate">\; +</span>\underset{\mathrm{<span\; class="notranslate">\; C</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; cv</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; )</span>$

For all C∈N(v)

Q _VC ＝ Q _V -R _CV

In step S4, the estimated vector  is calculated from Q _V according to the definition of the sign function, and the syndrome vector S is calculated by multiplying the parity check matrix H with the calculated estimated vector  :

 = sign(Q) (6)

s = H 

In step S5, an iteration counter iter is incremented.

In step S6, it is checked whether the iteration counter has reached a predetermined maximum iteration value, ie a threshold value, or whether the syndrome vector S is zero. If the result of the check at step S6 is negative, the process continues with the next iteration.

On the contrary, if the check result of step S6 is affirmative, it is checked in step S7 whether the syndrome vector S is zero. If the syndrome vector S is non-zero, the iteration has stopped because the maximum number of iterations has been reached (interpreted as a decoding failure). Accordingly, the LDPC decoder outputs a signal indicating failure of decoding. On the other hand, if the syndrome vector S is zero, the decoding is successful, ie the decoding process has converged. In this case, the LDPC decoder outputs the final calculated estimated vector  as the correct decoded codeword.

Fig. 5 shows the calculated check-to-variable message R _CV and variable-to-check message Q _VC after each iteration until the decoder converges.

For the given example of Fig. 3, the LDPC decoder of the receiving transceiver outputs the estimated vector φ = (1010) ^T and indicates that the decoding has been performed successfully. Note that the decoded estimated vector φ corresponds to the output of the LDPC encoder within the transceiver.

Fig. 6 shows a block diagram of a conventional LDPC decoder employing the concise propagation BP decoding algorithm and using standard overflow scheduling according to the state of the art.

The LDPC decoder according to the state of the art as shown in FIG. 6 receives the calculated log-likelihood ratio LLR from the demodulator through an input (IN) and temporarily stores it in RAM as an initialization value.

This RAM is connected to multiple variable node processors, as shown in Figure 8. The output of the variable node processor is connected to another RAM set up for Q _VC messages. The addressing of the _QVC random access memory is done by means of a ROM which stores the coded graph structure. The ROM also controls the switching unit on the output side of the _QVC -RAM. The output of the switching unit is connected to multiple check node processors, as shown in FIG. 7 , for updating the check variable message R _CV . Store the updated R _CV message in another RAM, as shown in Figure 6. Addressing of the R _CV random access memory is performed with a second ROM storing the coded graphics structure. The ROM also controls the switching unit on the output side of the _RCV -RAM. The output to the switching unit is connected to the variable node processor.

The check node processor performs the check to the update of the variable message _RCV as described in connection with step S2 in the flowchart shown in FIG. 4 . Temporarily store the updated checksum variable message R _CV in R _CV -RAM, as shown in FIG. 6 .

The variable node processor performs the updating of variables to the check message Q _VC as described in connection with step S3 of the flowchart shown in FIG. 4 . Temporarily store the updated variable to the check message Q _VC in Q _VC -RAM.

A conventional LDPC decoder as shown in FIG. 6 also includes RAM for the output _QV message computed by the variable node processor.

The convergence test block calculates the estimate ϕ and calculates the syndrome vector S, as described in connection with step S4 of the flowchart of FIG. 4 . In addition, the convergence test block performs these checks according to steps S5, S6, S7 and indicates whether the decoding has been successful, ie the decoder is converged. In the case of successful decoding, the last calculated estimate is output by the LDPC decoder.

Conventional LDPC decoders employing an overflow update schedule as shown in FIG. 6 have several drawbacks.

The number of iterations required until the decoding process has converged is quite high. Correspondingly, the decoding time of conventional LDPC decoders with overflow scheduling is high. The performance of LDPC decoders according to the state of the art deteriorates when the number of decoding iterations defined by a threshold is limited.

Another disadvantage of the traditional LDPC decoding method and the corresponding LDPC decoder shown in FIG. 6 is that: to check whether the decoding is converged, a separate convergence test block is required to perform the convergence test. The convergence test block of the conventional LDPC decoder as shown in Fig. 6 calculates the syndrome vector S by multiplying the parity check matrix H with the estimated vector ϕ .

Another disadvantage of the traditional LDPC decoding method using overflow scheduling and the corresponding LDPC decoder shown in FIG. 6 is that the required storage size is relatively high. The LDPC decoder shown in FIG. 6 includes four random access memories (RAMs), namely, a RAM for input PV messages, a RAM for output Q _V messages, another RAM for Q _VC messages, and a RAM for R _{CV messages} . The last RAM of the message. In addition, the LDPC decoder includes two read-only memories (ROMs) for storing the structure of the Tanner diagram.

Contents of the invention

Therefore, the object of the present invention is to propose an LDPC decoder which overcomes the above-mentioned drawbacks, in particular an LDPC decoder which requires a small number of iterations to decode received codewords.

In addition, another object of the present invention is to describe a low-complexity common encoder/decoder structure to implement encoding/decoding of LDPC codes of various rates and lengths with the same hardware.

This object is achieved by an LDPC decoder having the features of claim 1 and claim 12 .

The present invention proposes a method for receiving from a noisy communication channel as a result of transmitting a codeword (b) having a number (N) of codeword bits belonging to a length (N) LDPC code over a noisy channel. The LDPC decoder for decoding the noisy codeword (y) obtained, wherein for the low density parity check code, a (M×N) parity check matrix H is set and satisfies H*b ^T =0, where The codeword (Y) has a plurality of (N) codeword bits composed of K information bits and M check bits, wherein the parity check matrix H represents the matrix element h _ij according to the parity check matrix H, via A bipartite graph of N variable nodes (V) whose edges are connected to M check nodes (C),

Wherein said LDPC decoder performs the following decoding steps:

(a) receiving a noisy LDPC codeword (Y) over said communication channel;

(b) For each codeword bit (V) of the transmitted LDPC codeword (b), the codeword bit (V) is received with predetermined information from the received noisy codeword (Y) and from the communication channel an a priori estimate of the predetermined value of the parameter (Q _v );

(c) for each variable node (V) of the bipartite graph, the calculated prior estimate ( _Qv ) corresponding to the codeword bit (V) is stored in the memory as the initialization variable node value;

(d) storing in said memory a check-to-variable message (R _CV ) initialized to zero from each check node (c) to all variable nodes (V) of said bipartite graph;

(e) Iteratively calculate messages on all edges of the bipartite graph according to a serial schedule, wherein in each iteration, pass through all check nodes (c) of the bipartite graph serially, and for the bipartite graph Each check node (C) of the graph performs the following calculations:

(e1) reading the stored message (Q _V ) and the stored check-to-variable message (R _CV ) from memory for all adjacent variable nodes (V) connected to said check node (c);

(e2) Through the message passing calculation rule, for all adjacent variable nodes (V) connected to the check node (C), as the message (Q _V ) read from the memory and the check-to-variable message ( R _CV ) function to calculate variable to check message (Q _vc );

(e3) Compute the updated checksum as a function of the calculated variable to the checksum message (Q _vc ) for all adjacent variable nodes (V) connected to said checkpoint (C) by message passing calculation rules to variable message(R _CV ^new );

(e4) Through the message passing calculation rule, for all adjacent variable nodes (V) connected to the check node (C), as the aforementioned message (Q _V ) and the updated check-to-variable message (R _CV ^new ) function to calculate the updated posterior message (Q _V ^new );

(e5) storing the updated a posteriori message (Q _V ^new ) and the updated check-to-variable message (R _CV ^new ) back into said memory;

(f) computing the decoded codeword (b ^* ) as a function of the a posteriori message (Q) stored in said memory;

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

(h) outputting a decoded codeword (b ^* ) once said decoding has converged or once a predetermined number of iterations has been reached.

The main advantage of the LDPC decoder according to the present invention is that the LDPC decoder converges in about half the number of iterations (as shown in Figures 13A and 14A). As a result, when the number of decoder iterations is limited in any practical application (as shown in Figures 13B and 14B), the performance of LDPC decoders with serial scheduling is better than that of LDPC decoders with overflow scheduling. Alternatively, for a given performance and decoder throughput, an LDPC decoder with serial scheduling requires approximately half the processing hardware compared to an LDPC decoder with overflow scheduling.

Another advantage of the LDPC decoder according to the invention is that the memory size of the LDPC decoder according to the invention is approximately half its size.

The decoding method adopted by the LDPC decoder according to the present invention can be applied to generalized LDPC codes, for which the left and right nodes in the bipartite graph represent constraints with arbitrary codes.

In a preferred embodiment of the decoder according to the invention, the codes to which the decoding is applied are LDPC codes, the left nodes representing constraints according to repeated nodes and the right nodes representing constraints according to parity nodes. In a preferred embodiment of the LDPC decoder according to the invention, the message-passing computation rule process employed is the concise propagation (BP) computation rule, also known as the sum-product process.

A preferred embodiment of a generalized check node processor is shown in FIG. 19 .

In an alternative embodiment, the message passing calculation rule employed is a minimum sum procedure.

In a preferred embodiment of the LDPC decoder for decoding low-density parity-check codewords according to the invention, the calculated a priori estimate is a log-likelihood ratio (LLR).

In an alternative embodiment, the calculated a priori estimates are probabilities.

In a preferred embodiment of the LDPC decoder for decoding low density parity-check codewords, a decoding failure is indicated when the number of iterations reaches an adjustable threshold.

Description of drawings

Hereinafter, a preferred embodiment of an LDPC decoder for decoding a low density parity check codeword will be described with reference to the accompanying drawings.

Figure 1 shows an example of a sparse parity-check matrix H and a corresponding bipartite Tanner graph according to the state of the art;

Figure 2 shows a simple example of a bipartite Tanner diagram according to the state of the art;

FIG. 3 shows a transceiver connected by a data communication channel, including an LPDC encoder and an LDPC decoder for decoding an LDPC code defined by a bipartite Tanner graph as shown in FIG. 2 .

Fig. 4 shows a flowchart of a concise propagation (BP)-LDPC decoder employing overflow scheduling according to the state of the art;

Figure 5 shows a number of iterative steps for a concise propagation LDPC decoder utilizing standard overflow scheduling according to the state of the art;

Figure 6 shows a block diagram of a conventional LDPC decoder according to the state of the art;

FIG. 7 shows a circuit diagram of a check node processor in the conventional LDPC decoder as shown in FIG. 6;

Figure 8 shows a circuit diagram of a variable node processor arranged in an LDPC decoder according to the state of the art as shown in Figure 6;

Fig. 9 shows the flowchart of the concise propagation (BP)-LDPC decoder utilizing the serial scheduling according to the present invention;

Fig. 10 shows for the simple example of Fig. 2, 3, a plurality of iterative steps according to the LDPC decoding method of the present invention;

FIG. 11 shows a flow chart of a generic message passing LDPC decoder using serial scheduling according to the present invention;

12 shows a table comparing the LDPC decoding process utilizing conventional overflow scheduling with the LDPC decoding method utilizing efficient serial scheduling according to the present invention;

Fig. 13A shows when the decoder is limited to 10 iterations, the simulation results of the average number of iterations required by the traditional LDPC decoder using overflow scheduling and the LDPC decoder using serial scheduling according to the present invention;

Fig. 13B shows the simulation results of the block error rate of the traditional LDPC decoder using overflow scheduling according to the state of the art and the LDPC decoder using serial scheduling according to the present invention when the decoder is limited to 10 iterations;

Fig. 14A shows when the decoder is limited to 50 iterations, the simulation results of the average number of iterations of the conventional overflow-scheduled LDPC decoder and the LDPC decoder using serial scheduling according to the present invention;

Fig. 14B shows that when the decoder is limited to 50 iterations, the block error rate of the traditional overflow-scheduled LDPC decoder compared with the LDPC decoder of the present invention using serial scheduling;

Figure 15a shows a transceiver comprising an LDPC encoder/decoder according to the present invention;

Figure 15b shows an efficient message passing decoder structure according to the present invention;

Figure 16 shows an example of the structure of a preferred LDPC code suitable for the decoder structure according to the present invention as shown in Figure 15b;

Fig. 17 shows the LDPC decoder structure according to the first embodiment of the present invention;

FIG. 18 shows a specific example of the realization of the LDPC decoder according to the first embodiment of the present invention using the LDPC code of the example shown in FIG. 16;

Figure 19 shows a generalized check node processor used by an LDPC decoder according to the present invention;

FIG. 20 shows a preferred implementation of a generalized check node processor disposed within an LDPC decoder according to an embodiment of the present invention;

Fig. 21 shows the block diagram of the LDPC decoder according to the second embodiment of the present invention;

FIG. 22 shows a block diagram of a generalized check node processor used in the LDPC decoder in the second embodiment of the present invention as shown in FIG. 21;

Fig. 23 shows the realization of the QR block in the generalized check node processor of the LDPC decoder according to the second embodiment as shown in Fig. 22;

Fig. 24 shows the implementation of the S block in the generalized check node processor of the LDPC decoder according to the second embodiment of the present invention as shown in Fig. 22;

Fig. 25 shows the preferred embodiment of the convergence test block in the LDPC decoder according to the present invention as shown in Fig. 15;

Fig. 26 shows the example according to the parity check matrix structure in the LDPC decoder of the present invention;

Figure 27 shows a preferred embodiment of a message passing encoder according to the present invention.

Detailed ways

As can be seen from FIG. 9, the method for decoding a low-density parity-check codeword according to the present invention is performed based on received channel observations (i.e., estimates or estimates indicating that the received codeword bits have predetermined values). method. These estimates are computed from the received codeword Y and predetermined parameters of the communication channel. The predetermined parameters of the communication channel are known. In an alternative embodiment of the invention, if the parameters of the communication channel are unknown, the minimum sum message passing calculation rule may be used, for which no parameters of the communication channel are required.

A general message passing decoding process covering all embodiments is shown in FIG. 11 . In the preferred embodiment, these estimates are log-likelihood ratios (LLRs) of the received bits.

Fig. 15b shows a block diagram of a preferred embodiment of an LDPC decoder 1A according to the invention. The LDPC decoder 1A has an input 2a and receives an a priori estimate based on channel observations from the demodulator. In a first embodiment, the a priori estimate is a calculated a priori log-likelihood ratio (LLR). In an alternative embodiment, the calculated estimates are a priori probabilities.

As shown in FIG. 9, in the initialization step S1, the calculated log-likelihood ratio or probability is temporarily stored as an initialization value in a random access memory (RAM) 3 within the LDPC decoder 1A. The memory 3 is connected to a block including a plurality of generalized check node processors through a switching unit 4 . The generalized check node processor 5 is also connected to a random access memory 7 . The memory 3 and the switching unit 4 are controlled by a read-only memory 6 storing the bipartite Tanner graph of the LDPC code used. The generalized check node processor 5 is used to update messages between nodes of the Tanner graph. The generalized check node processor is provided with R _CV messages from memory 7 and _QV messages from memory 3 via switching unit 4 . The generalized check node processor 5 computes new update values for the _RCV and _QV messages. The updated _RCV message is stored back into the memory 7, and the updated _QV message is stored back into the memory 3 through the switching unit 4.

In a preferred embodiment of the present invention, for each check node of the bipartite Tanner graph, the generalized check node processor 5 outputs the sign bit S _sign , which is checked by the convergence test block 8 to check the LDPC decoder 1 whether it has converged. In an alternative embodiment of the present invention, a standard convergence test block may be used, as shown in step S4 in FIG. 9 (the option on the right). When the convergence test block 8 realizes that the LDPC decoding process has converged, it indicates this by outputting a success indication signal via the output 9 of the LDPC decoder 1 . In case convergence has not been achieved, the LDPC decoder 1 indicates such failure via output 9 . In case of success, the LDPC decoder 1 outputs the decoded codeword calculated in the last iteration step via the data output 10a.

The generalized check node processors 5 in FIG. 15b are shown in more detail in FIG. 19, where each generalized check node processor 5 includes the traditional check node processor shown in FIG. Summing device.

In the initialization step S1 shown in Fig. 9, the check-to-variable message R _CV is initialized with the value zero for all check nodes and all variable nodes. Also, set the iteration counter i to zero. Another counter (valid) is also initialized to zero.

In step S2, the number of check nodes c is calculated according to the iteration counter i in the Tanner graph and the number of check nodes M:

c＝i·mod m (7)

In step S3, the generalized check node processor 5 performs a message update corresponding to the check node c. In a preferred embodiment of the present invention, the generalized check node processor implements the BP calculation rule according to the following equation:

For all v ∈ N(C), where N(C) is the set of neighbors of check node c, and where,

in,

and among them

In an alternative embodiment of the invention, the generalized check node processor implements a minimum sum calculation rule according to the following equation:

${\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; VC</span>}}^{\mathrm{<span\; class="notranslate">\; temp</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; V</span>}}^{\mathrm{<span\; class="notranslate">\; old</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; cv</span>}}^{\mathrm{<span\; class="notranslate">\; old</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 10</span>}<span\; class="notranslate">\; )</span>$

For all v ∈ N(C),

$\begin{array}{c}{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; cv</span>}}^{\mathrm{<span\; class="notranslate">\; new</span>}}<span\; class="notranslate">\; =</span>\underset{{\mathrm{<span\; class="notranslate">\; v</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; v</span>}}{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}{<span\; class="notranslate">\; (</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; sign</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{{\mathrm{<span\; class="notranslate">\; v</span>}}^{<span\; class="notranslate">\; \&prime;</span>}\mathrm{<span\; class="notranslate">\; c</span>}}^{\mathrm{<span\; class="notranslate">\; temp</span>}}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; min</span>}}_{{\mathrm{<span\; class="notranslate">\; v</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; v</span>}}<span\; class="notranslate">\; \{</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{{\mathrm{<span\; class="notranslate">\; v</span>}}^{<span\; class="notranslate">\; \&prime;</span>}\mathrm{<span\; class="notranslate">\; c</span>}}^{\mathrm{<span\; class="notranslate">\; temp</span>}}<span\; class="notranslate">\; \}</span>\\ {\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; V</span>}}^{\mathrm{<span\; class="notranslate">\; new</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; VC</span>}}^{\mathrm{<span\; class="notranslate">\; temp</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; cv</span>}}^{\mathrm{<span\; class="notranslate">\; new</span>}}\end{array}$

For each check node c of the bipartite Tanner graph and for all adjacent nodes connected to the check node c, the input message Q _VC from the adjacent variable node v to the check node is calculated by the message passing calculation rule and Output message R _CV from said check node c to said adjacent variable node v. As an alternative to computing all messages Q _VC from variable node V to check node c and then R _CV from check node c to variable node v as performed in an overflow-scheduled LDPC decoder according to the state of the art . For each check node c, the decoding method according to the present invention serially calculates all messages Q _VC entering the check node C, and then calculates all messages R _CV going out of the check node c.

The serial schedule according to the present invention is able to propagate messages instantaneously compared to an overflow schedule where messages are propagated only in the next iteration step.

Message Q _VC is not stored in memory. Instead it is easily calculated from the stored R _CV and Q _V messages according to Q _VC =Q _V −R _CV .

In the method according to the present invention, all check nodes c that have no common neighboring variable nodes can be updated simultaneously.

After these messages have been updated by the check node processor 5 in step S3, an iteration counter i is incremented in step S4.

In a preferred embodiment of the present invention, in step S3, the check node processor 5 calculates the indicator Indicates whether the checksum is valid. In step S4, if S _sign =1 (check is invalid), reset the valid counter (valid=0). On the contrary, when the check is valid (S _sign =0), the valid counter is incremented in step S4.

In another embodiment of the present invention, a standard convergence testing mechanism is used, as shown in FIG. 16 , wherein in step S4, the syndrome s =H  is calculated, where  =sign( Q ).

In step S5, it is checked whether the number of iterations (i/m) is higher than a predetermined maximum iteration value (ie, threshold), or whether the valid counter has reached the number of check nodes m. If the result of the check in step S5 is negative, the process returns to step S2. If the result in step S5 is positive, it is checked in step S6 whether the validity counter is equal to the number M of check nodes. If this is not the case (i.e. the iteration has stopped because the maximum iteration value MaxIter has been reached, the LDPC decoder 1 outputs a failure indication signal via output 9. Conversely, when the valid counter has reached the number of check nodes M, the decoding is successful , and LDPC decoder 1 outputs the latest estimate  as the decoded value of the received codeword.

 =Sign(Q)

Fig. 10 shows, for the simple example of Figs. 2, 3, the concise propagation decoding process performed by the LDPC decoder 1 according to the invention using the algorithm shown in Fig. 9 .

The calculated log-likelihood ratio LLR output by the demodulator P=[-0.7 0.9-1.65-0.6] is stored in the memory 3 of the LDPC decoder 1 as a decoder output. In an initialization step S1, the memory 7 storing the check-to-variable message R _CV is initialized to zero.

In the given example of FIG. 10 , the LDPC decoder 1 performs one additional iterative step (iteration 1 ) before convergence of the decoder 1 is reached. For each check node c1, c2, a variable is calculated or extrapolated to the check message _QVC for each variable node V constituting the neighboring nodes of said check node c. Then, for each variable node that is a neighboring node of the check node c, the above equation in step S3 of the decoding method is used to update the checked variable message R _CV and the prior message Q _V , and store them in In memory 7 and memory 3.

The convergence test block 8 counts valid checks according to the sign value S _sign received from the generalized check node processor. If S _sign =0, the check is valid. Once M consecutive valid checks have been counted (M consecutive S _sign variables equal to 0), it is determined that the decoding process has converged and the actual estimated value  =Sign(Q) is output via terminal 10 of the LDPC decoder 1 .

Alternatively, the standard convergence test blocks used by state-of-the-art overflow decoders can also be used for serial decoders. The standard convergence test block computes the syndrome vector s=Hb ^T at the end of each iteration, where b=sign(Q). If the syndrome vector is equal to the 0 vector, the decoder converges. In the given example, the serial decoder converges after one iteration.

By comparing Fig. 10 with Fig. 5, it is clear that the decoding method according to the present invention (Fig. 10) requires only one iterative step, while the conventional LPDC decoding method (Fig. 5) using this overflow schedule requires Two iteration steps.

Accordingly, one of the main advantages of the LPDC decoding method according to the invention is that the average number of iterations required by the LPDC decoder 1 according to the invention is approximately half of that required by conventional LPDC decoders using overflow scheduling.

Figures 13A, 14A show the simulation results for block length N=2400 and irregular LPDC codes on a Gaussian channel for 10 and 50 iterations. It is evident from Figs. 13A, 14A that the required number of iterations of the LPDC decoder 1 according to the present invention using serial scheduling is significantly lower than that of conventional LPDC decoders using overflow scheduling.

Furthermore, the performance of the LPDC decoder 1 according to the present invention is better than that of conventional LPDC decoders using overflow scheduling. Figures 13B, 14B show the simulation results of the block error rate BLER of LPDC decoder 1 compared with conventional LPDC decoders for 10 and 50 iterations. As can be seen from Figures 13B, 14B, when the number of iterations the decoder is allowed to perform is limited, the BLER performance of the LPDC decoder 1 according to the present invention is significantly better than that of the conventional LPDC decoder using overflow scheduling BLER performance.

Another advantage of the LPDC decoder 1 according to the present invention as shown in Figure 15b is that the storage size of the memories 3, 7 in the LPDC decoder 1 according to the present invention is significantly lower than that of the prior art shown in Figure 6 The memory size (half the memory size) of the random access memory (RAM) in the LPDC decoder of the state. Since serial scheduling is employed in LPDC decoder 1, no memory for Q _VC messages needs to be provided. Since the same memory initialized with the message P _v will also be used to store the message Q _V , the LPDC decoder 1 with a structure based on serial scheduling needs only memory for E+N messages (while the prior art as shown in FIG. 6 A stateful LPDC decoder requires memory for 2E+2N messages), where E is the number of edges in the Tanner graph of the code (in general, 3N<E<4N for good LPDC codes).

Another advantage of the LPDC decoder 1 employing the decoding method according to the invention is that only one data structure containing N(C) is required for all check nodes cεC. In a standard implementation of a conventional LPDC decoder using overflow scheduling, two different data structures have to be set up, requiring twice the memory size due to storing the bipartite Tanner graph of the code. If only a single data structure is utilized to implement an LPDC decoder using conventional overflow scheduling, the iterations must be divided into two non-overlapping computation stages. However, this results in hardware inefficiencies and increases hardware size.

It is known that an LPDC code close to the channel capacity can be designed with an appropriate number of concatenations, ie check node c has a constant or almost constant number. In such cases, only the variable node degrees are different. Whereas conventional overflow LPDC decoders for such irregular codes require more complex circuitry due to the need for computational units for handling the varying number of inputs. Even for such irregular codes, the LPDC decoder implemented according to the invention maintains the same circuit complexity. The reason is that the LPDC decoder 1A employing serial scheduling only needs a check code calculation unit for processing a constant number of inputs.

Another advantage of LPDC decoder 1A over conventional LPDC decoders is that a simpler convergence testing mechanism can be used. Whereas LPDC decoders according to the state of the art have to compute the syndrome vector S, the indicator S _sign of the LPDC decoder 1 is a by-product of the decoding process. In the conventional test block 8 of the LPDC decoder 1 according to the present invention, only for M consecutive check nodes, it is checked whether the sign of the variable S _sign is positive. And there is no need to perform the multiplication of the decoded word by the parity check matrix H at the end of each iteration step in order to check whether convergence has been reached.

The iterations of the LPDC decoder with overflow scheduling can be fully parallelized, ie all variables and check node messages are updated simultaneously. However, the decoding method according to the invention is serial, and the updates from the collection of nodes can be done in parallel. When the check nodes are divided into subsets so that any two check nodes in the subset are not connected to the same variable node V, the check nodes in each subset can be updated at the same time.

Fig. 12 includes a table showing overflow scheduling used by a conventional LPDC decoder compared to an efficient serial scheduling strategy as employed by the LPDC decoding method according to the present invention.

Figure 15a shows a transceiver comprising an LPDC encoder/decoder according to the present invention. The transceiver includes a forward error correction layer (FEC layer), implemented by an LPDC encoder/decoder as shown in Figure 15a. An LPDC decoder 1A according to the invention is shown in more detail in FIG. 15b, while a preferred embodiment of an LPDC encoder 1B is shown in FIG. The LPDC encoder/decoder 1 according to the invention allows encoding and decoding of codes of various rates and lengths to be performed on the same hardware. In a preferred embodiment, the LPDC encoder/decoder 1 implements a multi-rate and length LPDC code. In a preferred embodiment, the LPDC encoder/decoder 1 according to the invention is switchable between different LDPC codes stored in the memory of the device. The LPDC encoder/decoder 1 is connected to a communication channel 13 via a signal processing unit 11 and a transceiver front end 12 . Signal processing unit 11 and transceiver front end 12 employ the encoded codeword at the output of LPDC encoder 1B for transmission on a given communication channel 13 . In addition, the signal processing unit 11 and the transceiver front end 12 process the received signal from a given communication channel 13 and provide an a priori estimate of the transmitted bits to the LPDC decoder 1A. In a preferred embodiment of the invention, the a priori estimate of the transmitted bits is an a priori LLR. The encoded codeword is transmitted by the transceiver via the data transmission channel 13 to the remote transceiver, which decodes the encoded codeword by its LPDC decoder 1A.

Fig. 15b shows a block diagram of an LPDC decoder 1A according to the invention. The LPDC decoder 1A receives via input 2A an a priori estimate based on channel observations from the demodulator. The a priori estimate is formed either from a priori likelihood ratios (LLRs) or from a priori probabilities.

The a priori estimates are temporarily stored as initialization values in the random access memory 3 of the LPDC decoder 1A according to the invention as shown in Fig. 15b. Set up QRAM-3 to hold Q _V messages.

QRAM-3 is connected to a processing block including Z generalized check node processors 5-i via switching unit 4.

The serial decoding according to the present invention is serial in nature, however, the set of check node messages can be updated in parallel. Divide the check nodes into sets B ₁ ,..., B _m , so that any two check nodes c and c' in the set B _i are not connected to the same variable node, namely

As a result, check nodes c in each set B _i can be updated simultaneously. The partially serial nature of serial scheduling is not limiting since fully parallel computations are generally not possible due to complex interconnections between computing nodes c. Furthermore, when the check nodes c are divided into enough sets B _i , the performance of LPDC decoder 1A is very close to that of serial scheduling even though set B _i does not maintain the above property (11). Therefore, in a preferred embodiment, by dividing the check node c into $m=\frac{m}{Z}$ Sets B ₁ , ... , B _m of equal size of size Z, serial scheduling can be performed, and by simultaneously updating all check nodes c in set B ₁ and then simultaneously updating all check nodes in set B ₂ And so on until the set B _i , to perform the iteration.

步骤构成，其中，在每一个步骤中，由Z个一般化校验节点处理器5来处理Z个校验节点的消息。当前正在处理校验节点c的处理器5-i读取针对所有v∈N(c)的消息Q_V和R_CV消息，执行计算，并且将更新的消息写回到存储器3、7。消息Q_V、R_CV的读取、计算和写回构成了三个处理阶段。由于一般化校验节点处理器5不能在一般化校验节点处理器5的单个时钟周期中完成这三个处理阶段，因此提供了数据处理管道。在可选实施例中，QRAM-3和R-RAM 7允许同时读取和写入。在该实施例中，一般化校验节点处理器5在每一个时钟周期中读取新的消息集合，并且利用每一个时钟写回已经更新的消息集合。在该实施例中，解码迭代将需要M/Z个时钟周期。A generalized check node processor 5 according to the present invention as shown in Fig. 15b is used to update messages between nodes in the graph. The generalized check node processor 5 receives the _RCV message from the R-RAM 7 and provides it with the _QV message from the QRAM-3 via the switching unit 4 . The generalized check node processor 5 computes new update values for the _RCV and _QV messages. The updated _RCV message is stored back into R-RAM 7, and the updated _QV message is stored back into QRAM-3 via switching unit 4. Switching information for the switching unit 4 is read from a read-only memory (ROM 6 ) in which the LDPC code structure is stored. Z generalized check node processors 5-i are set to perform simultaneous computation on the messages of the Z check nodes. The decoding iterations performed by the generalized check node processor 5 are given by

The steps are constituted, wherein, in each step, the messages of Z check nodes are processed by Z generalized check node processors 5 . The processor 5-i currently processing the check node c reads the messages _QV and _RCV messages for all vεN(c), performs calculations, and writes the updated messages back to the memory 3,7. The reading, calculation and writing back of messages Q _V , R _CV constitute three processing stages. Since the generalized check node processor 5 cannot complete these three processing stages in a single clock cycle of the generalized check node processor 5, a data processing pipeline is provided. In an alternative embodiment, QRAM-3 and R-RAM 7 allow simultaneous reading and writing. In this embodiment, the generalized check node processor 5 reads a new message set every clock cycle, and writes back an updated message set every clock cycle. In this embodiment, decoding iterations will require M/Z clock cycles.

The generalized check node processor 5 outputs an indicator S _sign for each check node c of the bipartite graph to check whether the LPDC decoder 1A has converged. As can be seen from FIG. 15 b , the generalized check node processor 5 forwards the individual syndrome bits S _sign to the convergence test block 8 . A preferred embodiment of the convergence test block 8 is shown in FIG. 25 . The convergence test block 8 realizes that the LDPC decoding process has converged and indicates this by outputting a success indication signal via the output 9 of the LPDC decoder 1 .

FIG. 15b shows the general structure of LPDC decoder 1A performing serial scheduling according to the present invention as shown in FIG. 9 . The implementation of an LPDC decoder for random unstructured LDPC codes entails high complexity. The decoder 1A according to the invention has many messages that have to be read from and written back to the memories 3 , 7 even at relatively low decoding rates. As a result, this requires memories 3, 7 to be formed from multi-ported memories with complex addressing schemes. Furthermore, a complex switching unit 4 is required to route messages from the memory 3 , 7 to the generalized check node processor 5 . In order to make the implementation of the LPDC decoder 1A according to the invention simple, it is preferable to use an LDPC aware of the structured architecture. This can simplify the addressing mechanism of the memories 3 , 7 and the routing of messages via the switching unit 4 . According to a preferred embodiment, the LPDC decoder 1A uses an LDPC code based on a lifting graph that generates a parity check matrix composed of permutation matrices.

In the following, the structure of an LDPC code based on a lifting graph generating a parity check matrix constituted by a permutation matrix is described. The structured LDPC code considerably simplifies the implementation of the LPDC decoder 1 according to the invention.

When using K=R*N information bits and M=(1-R)·N parity bits to form an LDPC code with a rate of R and a code length N and form an M*N parity check matrix H, LDPC The M*N parity check matrix H of the code is composed of M _b *N _b block matrices H _b , where $m_b=\frac{m}{Z}$ and $N_b=\frac{N}{Z}.$

Each data entry into the block matrix is either Z*Z zero matrices or Z*Z permutation matrices. The preferred embodiment preferably uses a limited variety of permutations, which can be easily implemented.

In a preferred embodiment, these substitutions are limited to cyclic substitutions denoted P ⁰ , ..., P ^Z-1 , where

并且

and

The permutation size Z is a function of the latency or throughput required by the LPDC decoder 1A.

Graph lifting can be used to explain the underlying graph of an LDPC code constructed in this way. The small graph with N _b variable nodes and M _b check nodes is lifted or copied Z times, thereby obtaining Z small discrete graphs. Each edge of the gizmo appears Z times. Then, each such set of Z edges is permuted in Z copies of the graph, resulting in a single large graph with N variable nodes and M and check nodes.

Fig. 16 shows a simple example of a small [24,12] LDPC code. Fig. 16 shows LDPC codes before and after permutation. If the small _Mb × _Nb graph represents a (λ(χ), ρ(χ))-irregular LDPC code, the resulting large M×N graph also represents a (λ(χ), ρ(χ))-irregular LDPC code. Regular LDPC codes.

个块行，来执行解码迭代。利用d_c个非零块条目来处理矩阵H的块行涉及从Q-RAM 3和R-RAM 7中读取Q_V和R_CV消息的d_c尺寸的Z个块。然后，将这些消息路由到Z个一般化校验节点处理器5，所述一般化校验节点处理器5同时处理与该块行相对应的Z个奇偶校验。然后，将更新的消息写回到存储器3、7。将与奇偶校验矩阵H的块列相对应的Z个Q_V消息的每一个集合包含在QRAM-3的单个存储单元中。将这些消息一起从QRAM-3中读出，然后通过执行根据H块矩阵的适当置换，将其路由到Z个不同的一般化校验节点处理器5。The LDPC code based on the permuted block matrix as described above enables simple implementation of the LPDC decoder 1A supporting high-level parallelization. The parity-check matrix H can be processed one by one serially by

block rows to perform decoding iterations. Processing a block row of matrix H with _dc nonzero block entries involves reading _dc sized Z blocks of _QV and R _CV messages from Q-RAM 3 and R-RAM 7 . These messages are then routed to Z generalized check node processors 5 which simultaneously process Z parities corresponding to the block row. Then, the updated message is written back to the memory 3,7. Each set of Z _QV messages corresponding to the block columns of the parity-check matrix H is contained in a single storage unit of QRAM-3. These messages are read out of QRAM-3 together and then routed to Z different generalized check node processors 5 by performing appropriate permutations according to the H-block matrix.

Fig. 17 shows a first embodiment of an LPDC decoder 1A according to the present invention.

FIG. 18 shows an example of the LPDC decoder 1A according to the first embodiment shown in FIG. 17 for the parity check matrix H constructed as shown in FIG. 16 .

In the example shown in FIG. 18 , the LPDC decoder 1A is set for an LPDC code of small length 24. Also shown in Figure 18 are the initialization values of R-RAM 7 and QRAM-3.

个时钟周期中执行解码迭代。Since a row of matrix H with dc nonzero block entries is processed in dc clock cycles, so that in each clock cycle a message is read corresponding to a single nonzero block entry in the row, then in

The decoding iterations are performed in clock cycles.

If the LPDC decoder 1A according to the invention is required to support higher decoder data rates, a larger number of Z generalized check node processors 5 are required within the LPDC decoder 1A. This produces a very small The H _b matrix, due to the limited degrees of freedom in designing the matrix H, may result in weak LDPC codes. In addition, the generalized check node processor 5 cannot finish processing the check procedure until all d _c messages have been read into the processor 5 . As a result, the execution pipeline per generalized check node processor 5 is at least d _c , which may be higher for high-rate encoding. This can substantially increase the amount of registers required for the execution pipeline of each processor 5, resulting in an increase in logic areas and an increase in decoder power consumption.

个时钟周期，这允许更小的置换块尺寸Z，结果，在设计H_b时允许更大的块矩阵H_b和增加的自由度。另外，每一个一般化校验节点处理器5的执行管道的长度不再是d_c的函数，从而其可以小得多。Assuming that the number of rows in matrix H is constant (and nearly constant), then if additional structure is included in matrix H for all d _c blocks capable of reading Z messages from d _c different RAM cells simultaneously, These drawbacks can be avoided. In this way, each row of the H matrix is processed in a single clock cycle, thus decoding iterations cost

clock cycles, which allows a smaller permutation block size Z and, consequently, a larger block matrix _Hb and increased degrees of freedom in designing _Hb . In addition, the length of the execution pipeline of each generalized check node processor 5 is no longer a function of _dc , so it can be much smaller.

In a preferred embodiment, to support simultaneous reading of all row messages in a single clock cycle, additional structure is included into the H-matrix of the LDPC code. In a preferred embodiment, the even check matrix H of the odd LDPC code is constructed in the following manner. Divide the block columns of the parity-check matrix H into d _c sets (or more than d _c sets, however not more than N _b sets). Each block row of the parity-check matrix H needs to contain d _c nonzero block entries from d _c different sets. This enables the partitioning of _{the QV message} into dc Q-RAMs 7 (or even more) based on partitioning the block columns of the parity-check matrix H into _dc (or more) sets. As a result, it is ensured that when processing block rows of the parity-check matrix H, _dc sets of Z _QV messages that need to be read are stored in different _dc (or more) RAM cells and can be read together fetch (without setting up multi-port RAM). The corresponding structure of the LPDC decoder 1A forms the second embodiment as shown in FIG. 21 .

When comparing the LPDC decoder 1A according to the first embodiment of the present invention shown in FIG. 17 with the LPDC decoder 1A of the second embodiment shown in FIG. 21 , the LPDC decoder 1A according to the first embodiment With increased complexity, more chip area is required as a result. In addition, when compared with the LPDC decoder 1A of the second embodiment shown in FIG. 21 , the LPDC decoder 1A according to the first embodiment shown in FIG. 17 has increased power consumption because the first implementation The example LPDC decoder 1A has more registers in the execution pipeline of the processor 5 . On the contrary, the main advantage of the LPDC decoder 1A according to the first embodiment of the present invention as shown in FIG. 17 is that it is more general than the LPDC decoder 1A of the second embodiment shown in FIG. 21 . The reason is that the LPDC decoder 1A according to the first embodiment shown in FIG. 17 is not limited to the fact that the number of times d _c of check nodes is fixed. As a result, this LPDC decoder 1A is also capable of decoding LDPC codes with various check node numbers while remaining highly efficient.

In the LPDC decoder 1A of both embodiments, reading and writing are performed from the Q-RAM 3 and the R-RAM 7 in every clock cycle. Therefore, these RAM memories are formed of dual-port RAM. In the LPDC decoder 1A of both embodiments, the complexity of the R-RAM 7, which is typically a large RAM, can be simplified by considering sequential addressing of the R-RAM 7. By employing sequential addressing, a memory with a simplified addressing scheme and reduced complexity can be used since random access is not required. Additionally, due to sequential addressing, in a preferred embodiment, the R-RAM 7 can be divided into two RAMs, one R-RAM 7a containing odd addresses and the other R-RAM 7b containing even addresses. Thus, in each clock cycle, a message is read from one R-RAM and written back to the other R-RAM. In this preferred embodiment, a single-port RAM of high complexity can be used for the R-RAM 7.

In the following, a possible implementation of a generalized check node processor 5 for two embodiments is described. The BP generalized check node processor 5 currently processing check node c reads the messages Q _V and R _CV for all v ∈ N(c), and performs the following computation:

For all v ∈ N(c),

Q _temp ←Q _v -R _cv

R _cv ← ^-1 (S-(Q _temp ))

Q _v ← Q _temp + R _cv

end of loop

The check node processor writes the updated message back to the memory 3,7.

Note that in an alternative embodiment, the generalized check node processor 5 implements a calculation rule different from BP (Brief Propagation).

For example, the check node processor implements sub-optimal, low-complexity min-sum calculation rules as follows:

For all v ∈ N(c),

${\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; vc</span>}}^{\mathrm{<span\; class="notranslate">\; temp</span>}}<span\; class="notranslate">\; \&LeftArrow;</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; v</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; cv</span>}}$

end of loop

For all v ∈ N(c),

${\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; cv</span>}}<span\; class="notranslate">\; \&LeftArrow;</span>\mathrm{<span\; class="notranslate">\; \&Pi;</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; v</span>}{<span\; class="notranslate">\; (</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; sign</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{{\mathrm{<span\; class="notranslate">\; v</span>}}^{<span\; class="notranslate">\; \&prime;</span>}\mathrm{<span\; class="notranslate">\; c</span>}}^{\mathrm{<span\; class="notranslate">\; temp</span>}}<span\; class="notranslate">\; )</span>}\mathrm{<span\; class="notranslate">\; min</span>}{\mathrm{<span\; class="notranslate">\; v</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; /</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; \{</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{{\mathrm{<span\; class="notranslate">\; v</span>}}^{<span\; class="notranslate">\; \&prime;</span>}\mathrm{<span\; class="notranslate">\; c</span>}}^{\mathrm{<span\; class="notranslate">\; temp</span>}}<span\; class="notranslate">\; \}</span>$

${\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; v</span>}}<span\; class="notranslate">\; \&LeftArrow;</span>{\mathrm{<span\; class="notranslate">\; Q</span>}}_{\mathrm{<span\; class="notranslate">\; vc</span>}}^{\mathrm{<span\; class="notranslate">\; temp</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; cv</span>}}$

end of loop

FIG. 20 shows a schematic circuit diagram of the BP generalized check node processor 5 for Embodiment 1. FIG. 22 shows a schematic circuit diagram of the BP generalized check node processor 5 for Embodiment 2. Implementations of QR blocks and S blocks are shown in FIGS. 23 and 24 .

Preferably, the [phi] and [phi] ^-1 transformations are implemented using a LUT. In the preferred embodiment of the BP generalized check node processor, computations with LLRs are performed in full representation of 2, and computations with [phi](LLR) are performed in sign/magnitude representation. Save these messages as LLRs in the implemented representation of 2. All calculations to be performed between the [phi] and [phi] ^-1 transformations are performed in sign/magnitude representation. The conversion between the two representations can be included into the [phi] and [phi] ^-1 transformations.

Since saving of the _Qvc message is avoided in LPDC decoder 1A, it is easily calculated according to the following equation:

_Qvc ＝ _Qtemp ＝ _Qv - _Rcv

In a fixed-point implementation, _QV messages have a larger dynamic range than _RCV messages in a preferred embodiment in order to avoid losing _Qvc information. Sufficiently, _QV messages are represented with additional bits. However, as a result, once the _QV message has reached its maximum value, it should no longer be updated. This is maintained using the "Check Saturation" block shown in Figures 20 and 23 . This proves to be an advantage since it reduces logic power consumption.

个连续块校验所有处理器5中的S变量的符号为正，作为解码处理的副产品来执行该操作，如图25所示。一旦检测到收敛，则清空处理器5的执行管道，并且驻留在Q-RAM 3中的Q_V变量的符号位构成了已解码码字。将收敛测试机制包括到如图17和21所示的控制单元9中。Unlike the standard overflow schedule, where the convergence test is performed at the end of each iteration by computing the syndrome, the serial schedule according to the invention allows a simple convergence check during the decoding process. by targeting

Consecutive blocks check that the signs of the S variables in all processors 5 are positive, which is performed as a by-product of the decoding process, as shown in FIG. 25 . Once convergence is detected, the execution pipeline of the processor 5 is emptied and the sign bit of the _QV variable residing in the Q-RAM 3 constitutes the decoded codeword. A convergence testing mechanism is incorporated into the control unit 9 as shown in FIGS. 17 and 21 .

With the LDPC decoder 1A of the first embodiment, various code rates R and code lengths N are realized on the same liquid crystal by storing various matrices H in the ROM 6. Since the block matrix description is very concise, the overhead of saving multiple matrices is small.

In the LDPC decoder 1A of the second embodiment, a fixed number of times d _c of check nodes is assumed. The node number d _c is set according to the highest code rate that must be supported and has the highest check node number. Then, a lower code rate is achieved by canceling some of the d _c check node processor inputs.

块矩阵H_b构成的码率为1/2的基本LDPC码时，对该矩阵进行设计，从而使针对i＝1、……、 的块行i和块行

没有重叠的非零块条目。然后，将H的块行划分为对，即，针对1、……、

将块行i与块行

匹配。然后，通过对块行对的α一起求和(其中α是1和 之间的数)，实现了与速率 LDPC码相对应的更小的

块矩阵H_b。An alternative to realize multiple code rates R on the same liquid crystal, which can be used for both LDPC decoder embodiments, is to obtain various code rates from a single block matrix _Hb by row combining. A higher rate LDPC code is constructed from a single basic block matrix _Hb by summing the block rows of matrix _Hb with no non-zero overlapping block entries. This results in a parity check matrix H of fewer dimensions corresponding to higher rate codes. For example, when using the

When the basic LDPC code of code rate 1/2 that the block matrix H _b forms, this matrix is designed, thereby make for i=1,..., block row i and block row

There are no overlapping non-zero block entries. Then, the block rows of H are divided into pairs, i.e., for 1, ...,

Combine block row i with block row

match. Then, by summing the α of block row pairs together (where α is 1 and between the number), achieved with the rate LDPC codes correspond to smaller

Block matrix H _b .

In this way, an LDPC code for any rate between 1/2 and 3/4 can be obtained. This structure of constructing higher rate LDPC codes from basic LDPC codes is advantageous since the constructed LDPC codes can be decoded using the same decoder hardware. The new parity check matrix that is the result of summing the block row pairs in the basic parity check matrix H is processed by reading messages corresponding to two clock rows into the processor 5 within two clocks Rows in H so that processor 5 treats all messages as if they belonged to the same check. The mechanisms required to support row merging are included in the S-block and QR-block as shown in FIG. 23 and FIG. 24 . The control signal MergeRows in Figures 23, 24 and 25 enables row merging each time when merging two consecutive rows. The processing of merged rows takes twice as long (two clocks instead of one), however, the number of rows to be processed is correspondingly reduced, so the decode time remains the same. The advantage of this method is that many code rates R are obtained using a single matrix, however, the obtained LDPC codes are not optimal.

Various code rates R and code lengths N can also be supported using a shortening and puncturing mechanism or a combination of shortening and puncturing. Shortening reduces the code rate R while puncturing increases the code rate R. At the LDPC encoder 1B, the shortened bits (as information bits) are set to zero, and then encoding is performed. Shortening and piercing bits are not transmitted. At LDPC decoder 1A, the shortened bits are initialized with a "0" message (zero sign bit and maximum reliability), and the punctured bits are initialized with an erase message (no sign bit and zero reliability involved), then Perform decoding. The decoding time of a shortened/punctured LDPC code remains the same as that of a full LDPC code (since LDPC decoder 1 operates on full codes), even though the LDPC code will be shorter.

……、N的LDPC码。例如，如果要获得长度为

的LDPC码，则块矩阵H_b由尺寸为 的置换块构成。这意味着：在LDPC解码器1处，每一个Q-RAM存储单元仅包含Z个消息中的 个消息，并且仅

个处理器5用于解码。与缩短/穿孔方法类似，短LDPC码的解码时间与基本LDPC码的解码时间保持相同。在流模式中，通过使用未使用的硬件来解码下一码字，能够对此进行避免。Various code lengths N can be obtained by compacting the ZxZ permutation block and thus the parity check matrix H of the code. In this way, the length can be obtained as

..., the LDPC code of N. For example, if you want to get the length of

LDPC code, then the block matrix H _b has a size of The replacement block composition. This means: At LDPC decoder 1, each Q-RAM cell contains only messages, and only

A processor 5 is used for decoding. Similar to the shortening/puncturing method, the decoding time of the short LDPC code remains the same as that of the basic LDPC code. In streaming mode, this can be avoided by using unused hardware to decode the next codeword.

To achieve a decoding time linear in code length N, smaller H block matrices are used for shorter LDPC codes, so that all matrices contain Z×Z permuted blocks. Therefore, realizing each additional code length N requires only an additional ROM 6 to hold the H matrix (requires a smaller ROM due to its compact description), and does not require changes in the hardware of the LDPC decoder 1A.

Linear coding complexity can be achieved by enforcing additional structures to structured LDPC codes. The constructed LDPC code is symmetric, so that the first $K_b=\frac{K}{Z}$ The blocks contain information bits and the last M _b contain parity bits. The last M _b block columns of H form a block lower triangular matrix or almost a block lower triangular matrix. In order to support simple coding for various code rates R obtained by row combining as explained above, the last M _b block columns of matrix H may have the structure as shown in FIG. 26 . Where M ₁ ≤ _{M 2} and M _b1 =M ₁ /Z is equal to the maximum number of block rows combined to generate the highest supported rate code.

Figure 27 shows a preferred embodiment of the LDPC encoder 1B within the transceiver as shown in Figure 15a. Comparing FIG. 27 with a structure showing the LDPC decoder 1A, it can be seen that the LDPC encoder 1B according to the present invention is realized by the same hardware.

The LDPC encoder 1B includes a RAM 3, a switching unit 4, an array of generalized check node processors 5, and a read-only memory 6. It is not necessary to set up RAM 7 and switch test unit 8. Since the LDPC encoder 1B and the LDPC decoder 1A are implemented by the same hardware, it is possible to set up two units 1A, 1B connected in parallel as shown in FIG. encoding process), to form the encoder/decoder 1. In an alternative embodiment, a unit having a circuit structure as shown in Fig. 15b is switched between an encoding mode for performing an encoding process and a decoding mode for performing a decoding process. This embodiment has the advantage that only less circuitry has to be implemented on the chip. Even when the FEC layer 1 is realized by setting a separate LDPC encoder 1B and a separate LDPC decoder 1A having the same hardware, there is an advantage in that two units are formed from the same hardware when designing a chip.

In the following, a preferred embodiment for performing encoding is described, where i = [i ₁ i ₂ ... i _Kb ] denotes a block of information bits divided into Kb sets of Z bits, i.e., i _j = [ _{j; 1} ... i _{j; z} ] ^T is a column of Z consecutive information bits,

Among them, P=[P ₁ P ₂ ... P _Mb ] represents the parity block divided into M _b sets of Z bits, that is, P _j = [P _{j; 1} ... P _{j; z} ] ^T is the number of Z consecutive parity bits List,

where c=[ip] denotes a block of codewords divided into N _b sets of Z bits, and where,

A(i;j) represents the (i;j)Z×Z block of the block matrix A shown in FIG. 26 .

Encoding is performed by the LDPC encoder 1B shown in FIG. 27 as follows:

1. Calculate $P_j={\mathrm{\&Sigma;}}_{l=1}^{K_b+j-i}A(j,l)c_l,$ For j=1,..., M _b1 ,

2. Calculate ${\mathrm{the\; s}}_j={\mathrm{\&Sigma;}}_{l=1}^{K_b+m_{\mathrm{bl}}}B(j,l)c_l,$ For j=1, . . . , M _b2 ,

3. Calculate $P_{m_{\mathrm{bl}+1}}={\mathrm{\&Sigma;}}_{j=1}^{m_{\mathrm{<figure-callout\; id="2"\; label="b"\; filenames="A20051007944400371.png,A20051007944400491.png"\; state="\{\{state\}\}">b</figure-callout>}2}}{\mathrm{the\; s}}_j$

4. Calculate $P_{m_{\mathrm{bl}+1}}{=\mathrm{the\; <figure-callout\; id="1"\; label="s"\; filenames="A20051007944400371.png,A20051007944400401.png"\; state="\{\{state\}\}">s</figure-callout>}}_1+T\left(\mathrm{1,1}\right)P_{m_{\mathrm{bl}+1}}$

5. Calculate $P_{m_{\mathrm{bl}+j+1}}={\mathrm{the\; s}}_j+T(j,1)P_{m_{\mathrm{bi}+1}}+P_{m_{\mathrm{bl}+1}}$ For j=2, . . . , M _b2 -1.

The same data path used by LDPC decoder 1A can be used for LDPC encoder 1B. Therefore, encoding can be performed on the same hardware used for the LDPC decoder 1A. If an LDPC code is constructed using a lower-order triangular H _b matrix, encoding can be performed with a decoder. A _QV message corresponding to K information bits is initialized with information bits (±maximum _QV message value, indicating total bit reliability), and M parity Bits corresponding to the Q _V message are initialized. Decoding is performed and the erased parity bits are recovered after a single iteration.

In order to reduce energy consumption, calculations performed during encoding are preferably performed only on the sign bit of the message, since encoding requires only an exclusive OR (xor) operation. The processor 5 can distinguish between erased bits and known bits by means of bits representing message duplication. The encoding is then simply performed by applying the following rule: each processor 5 reads only one unknown bit, and sets the unknown bit to the exclusive-or of all other known bits in the parity (the exclusive-or mechanism already exists in the processor middle).

The hardware required for implementing the LDPC encoder-decoder system 1 depends on code parameters, system parameters and required performance. Performance is measured as the number of iterations the LDPC decoder 1 is allowed to perform under a given latency or throughput constraint. Assume BP decoding.

Basic code parameters:

N-code length

d _v - the average number of bits (the average number of checks in which a bit participates - usually $d_v\&cong;3.5$ )

R _max - the maximum bit rate supported by the system.

d _c - the maximum number of checksums

For the right regular code:

${\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; v</span>}}}{\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}}<span\; class="notranslate">\; .</span>$

Encoder-decoder parameters:

f _c - encoder-decoder clock [Mhz]

bpm - bits per message

bpm ₂ - bits per message after  conversion

Z—the number of processors 5 for embodiment 1, or the number of QR blocks for embodiment 2.

${\mathrm{<figure-callout\; id="2"\; label="Z"\; filenames="A20051007944400371.png,A20051007944400491.png"\; state="\{\{state\}\}">Z</figure-callout>}}_2=\frac{Z}{d_c}$ - Number of processors in embodiment 2.

decoder performance

R _cn - channel bit rate (uncoded) [Mbps]

$I_{\mathrm{stray}\min g}=\frac{{\mathrm{Zf}}_c}{d_v{R}_{\mathrm{ch}}}$ - number of iterations supported in stream mode

L - maximum decoding wait time [microseconds]

$I_L=\min \{\frac{{\mathrm{Zf}}_c}{{\mathrm{Nd}}_v},I_{\mathrm{stray}\min g}\}$ - The number of iterations supported by the decoding latency L.

Encoder-decoder complexity of the first embodiment

Logic: BP processor ~ Z0.6K gates

RAM: 1, R-RAM 7: $\left(\frac{N_{\mathrm{dv}}}{Z}\right)\&times;\left(\mathrm{Zbpm}\right)$ Bit dual-port RAM with reduced addressing requirements (sequentially read/write addresses).

2. Q-RAM 3: $\left(\frac{N}{Z}\right)\&times;\left(Z(\mathrm{bpm}+1)\right)$ DPRAM

3. zx((9+d _c )(bpm+1)+(3+d _c )bmp ₂ ) 1-bit registers for pipeline buffering and read/write permutation buffers.

ROM 6 $\frac{{\mathrm{Nd}}_v}{Z}\left(\right[{\log }_2\left(N\right)]+1)$ Address ROM

Encoder-decoder complexity of the second embodiment

Logic: BP processor - ~ Z0.6K gates

RAM: 1, R-RAM 7: $\left(\frac{N_{\mathrm{dv}}}{Z}\right)\&times;\left(\mathrm{Zbpm}\right)$ Bit dual-port RAM with reduced addressing requirements (sequentially read/write addresses).

2. Q-RAM 3: d _c dual-port RAM cells, each of size $\frac{N}{Z}\&times;\frac{Z}{d_c}(\mathrm{bpm}+1)$ bit

3. z×(12(bpm+1)+6bmp ₂ −2) 1-bit registers and read/write permutation buffers for pipeline buffering.

ROM6: $\frac{{\mathrm{Nd}}_v}{Z}\&times;d_c\left(\right[{\log }_2\left(\frac{N}{d_2}\right)]+1)$ Address ROM

The RAMs used are Dual Port RAMs (TPRAMs). For R-RAM 7, single-port RAM can be used.

Claims (29)

1. An Low Density Parity Check (LDPC) decoder for decoding a codeword (Y) received from a communication channel as a result of transmitting a LDPC codeword (b) having a number (N) of codeword bits consisting of K information bits and N parity check bits, wherein the product of the LDPC codeword (b) and a predetermined (mxn) parity check matrix H is zero (H b)^T0), where the (M × N) parity check matrix H represents a bipartite graph including N variable nodes (V) connected to M check nodes (C) via edges according to matrix elements hij of the parity check matrix H,

wherein the LDPC decoder (1A) comprises:

(a) a memory (3) for storing, for each codeword bit of the received noisy codeword (Y), an a priori estimate (Qv) of the codeword bit having a predetermined value from the received noisy codeword (Y) and from a predetermined parameter of the communication channel;

(b) a generalized check node processing unit (5) for iteratively calculating messages on all edges of the bipartite graph according to a serial schedule, wherein in each iteration an input message (Q) from the neighboring variable node (V) to the check node (C) is calculated by a message passing calculation rule for each check node (C) of the bipartite graph, for all neighboring variable nodes (V) connected to the check node (C)_vc) And an output message (R) from the check node (C) to said neighboring variable node (V)_CV)。

2. LDPC-decoder according to claim 1, wherein the LDPC-decoder (1A) comprises a read-only memory (6) for storing at least one bipartite graph.

3. LDPC-decoder according to claim 1 characterized in that the LDPC-decoder (1A) comprises a further memory (7) for temporarily storing a pair variable message (R)_CV) And (4) verifying.

4. LDPC-decoder according to claim 1, characterized in that the LDPC-decoder (1A) comprises a convergence test block (8) for indicating whether the decoding process has successfully converged.

5. LDPC-decoder according to claim 1 wherein the bipartite graph is a tanner graph.

6. LDPC-decoder according to claim 1 wherein the message passing computation rule is a Belief Propagation (BP) computation rule.

7. LDPC-decoder according to claim 1 wherein the message passing computation rule is a min-sum computation rule.

8. LDPC-decoder according to claim 1 wherein the calculated a priori estimates are log-likelihood ratios (LLRs).

9. LDPC-decoder according to claim 1 wherein the calculated a priori estimates are probabilities.

10. LDPC-decoder according to claim 1, wherein a decoding failure is indicated by the LDPC-decoder (1A) when the number of iterations reaches an adjustable threshold.

11. LDPC decoder for decoding a noisy codeword (y) received from a noisy communication channel as a result of transmitting the codeword (b) having a number (N) of codeword bits belonging to a length (N) low density parity check code for which an (MxN) parity check matrix H is set and H x b is satisfied over the communication channel^T0, wherein the (M × N) parity check matrix H consists of matrix elements H according to the parity check matrix H_ijRepresented by a bipartite graph of N variable nodes (V) connected via edges to M check nodes (C),

wherein the LDPC decoder (1A) comprises:

(a) an input (2A) for receiving, for each codeword bit (V) of the transmitted LDPC codeword (b), the codeword bit (V) with an a priori estimate (Q) of a predetermined value from the received noisy codeword (Y) and from a predetermined parameter of the communication channel_v)；

(b) A first memory (3) for storing, for each variable node (V) of the bipartite graph, a calculated a priori estimate (Q) corresponding to a codeword bit (V)_v) As initialization variable node values;

(c) a second memory (7) for each correction initialized to zeroCheck-to-variable messages (R) of a check node (c) to all variable nodes (V) of the bipartite graph_CV)；

(d) Wherein a generalized check node processor (5) iteratively computes messages on all edges of the bipartite graph according to a serial schedule, wherein in each iteration all check nodes (C) of the bipartite graph are serially traversed and for each check node (C) of the bipartite graph the following computations are performed by the respective generalized check node processor (5-i):

(d1) reading the stored messages (Q) from the first memory (3) for all the neighbouring variable nodes (V) connected to the check node (c)_V) And reading the stored check-to-variable message (R) from the second memory (7)_CV)；

(d2) As a message (Q) read from the memory (3; 7) for all neighboring variable nodes (V) connected to the check node (C) by means of message passing calculation rules_V) And check to variable message (R)_CV) To calculate a variable to check message (Q)_vc)；

(d3) As calculated variable-to-check messages (Q) for all neighboring variable nodes (V) connected to the check node (C) by means of message-passing calculation rules_vc) Calculating an updated check to variable message (R)_CV ^new)；

(d4) As the aforementioned message (Q) for all neighboring variable nodes (V) connected to the check node (C) by means of message passing calculation rules_V) And updated check to variable message (R)_CV ^new) Calculating an updated a posteriori message (Q)_V ^new)；

(d5) Wherein the updated a posteriori message (Q)_V ^new) And updated check to variable message (R)_CV ^new) Is stored back in the memory (3; 7) performing the following steps;

(d6) calculating a decoded estimated codeword (b) as a function of the a posteriori messages (Q) stored in said first memory (3)^*)；

(e) A convergence test unit (8) for passing the check parity check matrix H anddecoded estimate (b)^*) Whether the product of the codewords is zero to check whether the decoding has converged;

(f) outputting (10A) a decoded estimation codeword (b) once the decoding has converged or once a predetermined number of iterations has been reached^*)。

12. LDPC-decoder according to claim 2 wherein the read only memory (6) stores a plurality of bipartite graphs for different LDPC-codes.

13. LDPC decoder according to claim 13, characterized in that the LDPC decoder (1A) is switchable between different LDPC codes.

14. LDPC-decoder according to claim 14 wherein the LDPC-codes comprise different code rates (R).

15. LDPC-decoder according to claim 1 characterized in that the LDPC-decoder (1A) is a multi-rate decoder for decoding LDPC-codes with different code rates (R).

16. LDPC-decoder according to claim 11, characterized in that a switching unit (4) is provided for routing messages from the memories (3, 7) to the generalized check node processors (5).

17. LDPC decoder according to claim 16, characterized in that the parity check matrix (H) is composed of permutated blocks, thereby simplifying message routing between the memory (3) and the generalized check node processor (5).

18. LDPC-decoder according to claim 11 wherein each generalized check node processing unit (5) comprises at least one QR-block (5a) for updating the Q_vAnd R_CVA message, and an S block (5b) for calculatingSoft parity (S).

19. LDPC decoder according to claim 18, characterized in that the QR block (5a) and the S block (5b) perform row merging in response to a control signal.

20. LDPC decoder according to claim 11, characterized in that the first memory (3) is formed by a dual port random access memory (TPRAM).

21. LDPC decoder according to claim 11, characterized in that the second memory (7) is formed by a Random Access Memory (RAM).

22. LDPC decoder according to claim 21, characterized in that the second memory (7) is divided into a first single-port RAM (7a) containing odd addresses and a second single-port RAM (7b) containing even addresses.

23. LDPC decoder according to claim 21, characterized by said second memory (7) and a dual port random access memory (TPRAM).

24. An LDPC decoder/encoder (1) characterized by comprising an LDPC decoder (1A) according to claim 1 and an LDPC encoder (1B) having the same hardware structure as the LDPC decoder (1A).

25. LDPC-decoder according to claim 11 wherein each generalized check node processor (5) comprises a check saturation block such that Q can be stored using only one additional bit_vA message.

26. LDPC decoder according to claim 11, characterized in that the switching unit (4) performs permutations of various sizes, enabling decoding of codes of various lengths.

27. LDPC decoder according to claim 12, characterized in that codes of various rates are decoded by row merging of rows in a parity check matrix (H) stored in the read only memory (6) in response to row merging control signals.

28. An LDPC encoder (1B) in which codewords are encoded by the LDPC encoder (1B) directly from a parity check matrix (H) stored in memory, thereby enabling codes of various rates to be encoded using the same hardware.

29. An LDPC encoder (1B) wherein a codeword (y) is encoded by multiplying an information bit vector (i) with a (KxN) generator matrix G, wherein the generator matrix G and a transposed parity check matrix H^TThe product of (c) is zero (G x H)^T＝0)。

Images