Efficient encoding of LDPC codes using structured parity-check matrices

Technical field The present invention relates generally to data encoding and decoding, and in particular to a method and apparatus for encoding and decoding data using LDPC (low-density parity-check) codes.

Background Art [0002] As described in United States Patent Application Serial Number 10/839995, the LDPC (low-density parity check) code is a linear block code defined by the H parity check matrix. In general, the LDPC code is defined over the body Galois GF (q), q> 2. If q = 2, the code is binary code. Linear block codes can be described as the result of multiplying the k-bit information vector s_1xk by the G code matrix_kxn, being the n-bit code word x_1xn, where the code efficiency is r = k / n. The code word x is transmitted through a noisy channel, and the received signal vector y passes through the decoder for estimating the information vector s_1xk.

[0003] In a given n-dimensional space, the rows of the matrix G span the k-dimensional subspace of the codeword C, and the rows of the parity check matrix H_mxn unbutton the m-dimensional dual space where m = nk. That x = sG and GH^T= 0 indicates that xH^T= 0 for all code words in the C subspace, where "T" (or "T") means matrix transposition. In the discussion of LDPC codes, this is usually written as

Hx^T=0^T, (1) where 0 is a horizontal vector containing all zeros and the code word x = [sp] = [s₀, p₁, p_k1 p₀, p₁, p_m-1], where p₀, p₁, p_m-1 are parity check bits, as₀, p₁, p_k-1 are systematic bits that are equal to the information bits from the information vector.

[0004] For the LDPC code, the density of non-zero values ​​in the H matrix is ​​low, i.e. the H matrix contains only a small percentage of ones, which gives better error correction performance and simpler decoding than using the dense H matrix. The parity check matrix can also be described by the graph bipartite. A bipartite graph is not only a graphic description of the code, but also a model for the decoder. In a bisected graph, the code word bit (and therefore each column of the H matrix) is represented by the vertex of the variable on the left, and each parity check equation (and therefore each row of the H matrix) is represented by the control vertex on the right. Each vertex of the variable corresponds to the column of the matrix H, and each control vertex corresponds to the row of the matrix

H, where "variable vertex" and "column" H are interchangeable terms, such as "control vertex" and "row" H. Vertex vertices are connected only to control vertices, and control vertices are connected only to variable vertices. For code on code word bits and parity bits, the vertex of the vi variable is edge-connected to the control vertex c if the i-th bit of the codeword occurs in the j-th control equation, i = 0, 1, n-1, j = 0,

I, m-1. In other words, the i-th vertex of the variable is connected to the j-th control vertex if the hji element of the parity H matrix is ​​1. Reflecting equation (1), the vertices of the variables represent the correct code word if all the vertices of the control have a parity trait. even parity).

[0005] The following is an example illustrating the relationship between the parity check matrix, parity check equations and a bisected graph. Let n = 12, the code with the efficiency 1/2 is determined by

<td>and</td><td> 0</td><td> 1</td><td> 0</td><td> 0</td><td> 0</td><td>And 1</td><td> 1</td><td> 0</td><td> 0</td><td> 0</td><td>0Ϊ</td>

<td> 0</td><td> 1</td><td> 0</td><td> 0</td><td> 1</td><td> 0</td><td>! θ</td><td> 1</td><td> 1</td><td> 0</td><td> 0</td><td> 0</td>

<td> 0</td><td> 0</td><td> 1</td><td> 0</td><td> 0</td><td> 1</td><td>1 ! and</td><td> 0</td><td> 1</td><td> 1</td><td> 0</td><td> 0</td>

<td> 1</td><td> 0</td><td> 0</td><td> 1</td><td> 0</td><td> 0</td><td> !⁰</td><td> 0</td><td> 0</td><td> 1</td><td> 1</td><td> 0</td>

<td> 0</td><td> 1</td><td> 0</td><td> 0</td><td> 1</td><td> 0</td><td>! about AND</td><td> 0</td><td> 0</td><td> 0</td><td> 1</td><td> 1</td>

<td> 0</td><td> 0</td><td> 0</td><td> ]</td><td> 0</td><td> 1</td><td>! and</td><td> 0</td><td> 0</td><td> 0</td><td> 0</td><td>lj</td>

η (2) where the left-hand part corresponds to k (= 6) information bits s, the right-hand part corresponds to m (= 6) p parity bits. When using (1), H in (2) defines the following 6 parity check equations:

Χ_θ + χ₂ + χ₆ + Χ_Ί = Ο *, + \ + *₇ + *₈ = Ο χ₂ + χ₅ + χ₆ + χ₈ + χ₉ = Ο 'η · χ_θ+ χ₃+ χ₉+ χ_1θ= 0 χ, + χ₄ + χ_1θ + χ_η = Ο χ₃ + χ₅ + χ₆ + χ "= Ο

Matrix H also has a corresponding bipartite graph shown in Fig. 1.

[0006] As discussed above, the receiver obtains a disturbed version of the sent code word x. To decode y and determine the original information sequence s, an iterative decoding algorithm based on a bisected graph, such as belief propagation algorithm, is used. Soft information in logarithmic probability (LLR) format the log-likelihood ratio) of the code word bits is transferred between the variable vertex bank and the control vertex bank. Iteration stops either when all control equations are met or when the allowable iteration limit is reached.

[0007] Designing the structured LDPC code begins with a small Hb base matrix with dimensions of m_bxn_b, is made from a copy of the matrix H_b and joins the copies together so that they form a large matrix H with dimensions mxn, where m = m_bxz, n = n_bx. In matrix notation for building H with H_beach one in H_b is replaced by a permutation sub matrix of dimensions zxz, and every zero in H_bis replaced by a zero matrix with dimensions zxz. This procedure basically maps each edge of Hb to a vector edge with a length of H, each vertex of a variable from Hb to the vertex of a vector variable with a length of H, and each control vertex of Hb to a vector control vertex of length with H. Benefits of the vectorization of a small Hb matrix when building a large H matrix they are as follows:

1. By using different z values, kb / nb efficiency codes can be designed based on a single Hb base matrix, where kb = nb-mb, for many different sizes of k = zxkb information sequence.

2. Memory requirements are significantly reduced. In the case of structured LDPC code, only the Hb base matrix and permutations of its ones need to be remembered, as needed

- 3 much less memory, because Hb is usually much smaller than H, and permutation can be very simple.

3. Coding and decoding can be performed on groups of bits instead of single bits. For example, a counting group from a message can be retrieved from memory, permuted and transferred between the vertex of a vector variable and the vector control vertex.

[0008] Although the LDPC structural design philosophy significantly reduces the complexity of implementation, there is no technique for designing the base matrix and assigning a permutation matrix for a given size of the target H matrix that would give an LDPC code with good error correction properties that would be efficiently coded and decoded. Therefore, there is a need for a method and apparatus for designing a structural H matrix and for a method and apparatus for encoding and decoding data using this structural H matrix.

[0009] In the document "LDPC coding for OFDMA PJY" IEEE 802.16 BROADBAND WIRELESS ACCESS WORKING GROUP, 1 May 2004, pp. 0-11, XP002438609, LDPC encoding for OFDMA PHY for the 802.16d standard has been described.

Clauses defining other aspects and useful for understanding the present invention [0010] 1. A transmitter operating method that generates parity bits p = (po, p_m-1) based on the current symbol set s = (p₀, p_k-1), the method comprising the following steps: receiving the current symbol set s = (s0,., sk-1);

using the H matrix to determine the parity check bits; and sending the parity check bits together with the current symbol set;

wherein H is an extension of the base matrix Hb, where Hb comprises the Hb1 member and the Hb2 member, where Hb2 comprises a first portion having a column hb having an odd weight greater than 2, and a second portion H'b2 containing matrix elements for row i, columns j, equal to 1 for i = j, for i = j + 1, in other cases;

wherein the extension of the underlying Hb matrix uses the same sub matrices for ones in each column of the second part of H'b2, and wherein the extension uses the sub matrix matrices for an even number of ones in hb; and

2. The method of clause 1, in which Hb is expanded by replacing each Hb element with a matrix of dimensions zxz to form H.

3. The method of clause 1, in which Hb is extended by replacing each zero Hb element with a zero matrix with dimensions zxz to form H.

4. The method of clause 1, wherein Hb is expanded by replacing each non-zero Hb element with a non-zero sub matrix to form H.

5. The method of clause 1, wherein Hb is expanded by replacing each non-zero Hb element with a non-zero permutation sub matrix to form H.

6. The method of clause 1, in which:

<img file="PL2387157T3_D0001.tif" />

ο

1 1 where the hb vector has odd weight in h&gt; = 3.

7. A device comprising: memory means for storing the H matrix; microprocessor using the H matrix to determine the parity check bits; and a transmitter for sending the parity check bits;

wherein H is the extension of the base matrix Hb, where Hb contains the Hb1 member and the Hb2 member, where Hb2 contains the first part containing the column hb having an odd weight greater than 2, and the second part H'b2 containing the matrix elements for row i, column j , equal for i = j, for i = j + 1, in other cases;

wherein two identical sub matrices are used to expand ones in each H'b2 column, and sub matrix matrices are used to expand the even number of ones in hb.

8. The device according to clause 7, in which:

H_b2 = [H_b IH '_b2]

<td>'A (o)</td><td> 1 ’</td>

<td>A (1)</td><td> 1 1 0</td>

<td></td><td> 1 '·.</td>

<td></td><td> '·. 1</td>

<td></td><td> 0 1 1</td>

<td>Λ ("A,^-1)</td><td> 1</td>

where the hb vector has an odd weight of h&gt; = 3.

9. A device comprising: memory means for storing the H matrix;

receiver for receiving the signal vector y = (y₀ ... y_n-1); and a microprocessor using the H matrix to determine the current set of symbols (p₀, ..., p_k-1), where H is an extension of the base matrix Hb, where Hb contains the Hb1 member and the Hb2 member, where Hb2 contains the first part containing the column hb having an odd weight greater than 2, and the second part H'b2 containing matrix elements for the row i, columns j, equal for i = j, for i = j + 1, in other cases; and

- wherein two identical sub matrices are used to expand ones in each H'b2 column, and sub matrix matrices are used to expand the even number of ones in hb.

10. The device according to clause 9, in which:

<img file="PL2387157T3_D0002.tif" />

ο

1 1 where the hb vector has an odd weight of h&gt; = 3.

Brief description of the figures [0011]

Fig. 1 shows a bipartite graph of matrix H (12, 6).

Fig. 2 shows the relationship between the Hb base matrix, the Hbm model matrix and the final extended H matrix.

Fig. 3 is a block diagram of an encoder.

Fig. 4 is a block diagram of a decoder.

Fig. 5 is a flowchart showing the operation of the encoder of Fig. 3.

Fig. 6 is a flowchart showing the operation of the decoder of Fig. 4.

Detailed description of the drawings [0012] To satisfy the aforementioned demand, a structural parity check matrix H is proposed, wherein the matrix H is an extension of the base matrix Hb and wherein the matrix Hb comprises the member Hb1 and the member Hb2, wherein Hb2 comprises a first part comprising a column hb having odd weight ( odd weight) greater than 2 and the second part H'b2 containing matrix elements for row i, columns j, equal to 1 for i = j, 1 for i = j + 1, 0 in other cases. The extension of the base Hb matrix uses the same sub matrices for ones in each column of the second part of H'b2, and this extension uses the sub matrix matrices for the even number of ones in hb.

[0013] The present invention includes a transmitter operating method that generates the parity bits p = (po, ···, p_m1) based on the current symbol set s = (sb, p_k-1). The method comprises the steps of receiving the current set of symbols s = (p_b, p_k-1) and the use of the H matrix to determine the parity check bits. The parity bits are sent along with the current symbol set. Matrix H is an extension of the base matrix Hb, where Hb contains the member Hb1 and the member Hb2, wherein Hb2 contains the first part containing the column hb, having an odd weight greater than 2, and the second part H'b2 containing the matrix elements for row i, column j , equal to 1 for i = j, 1 for i = j + 1, b in other cases. The extension of the base Hb matrix uses the same sub matrices for ones in each column of the second part of H'b2, and this extension uses the sub matrix matrices for the even number of ones in hb.

[0014] The present invention further includes a method of operating a receiver that estimates the current set of symbols s = (sb, s_k-1). The method includes the steps of receiving a received signal vector y = (y_b ... y_ni) and the use of the H matrix to estimate the current set of symbols s = (p_b, p_k-1). The matrix H is an extension of the base matrix Hb, wherein Hb contains the Hb1 member and the Hb2 member, where Hb2 contains the first part containing the column hb having an odd weight greater than 2 and the second part H'b2 containing the matrix elements for row i, columns j, equal and for i = j, and for i = j + i, b in other cases. The extension of the base Hb matrix uses the same sub matrices for ones in each column of the second part of H'b2, and this extension uses the sub matrix matrices for the even number of ones in hb.

[0015] The present invention further includes a device comprising memory means for storing the H matrix, a microprocessor using the H matrix to determine the parity check bits, wherein H is an extension of the Hb base matrix, wherein Hb comprises the Hbi member and the Hb2 member, wherein Hb2 comprises the first a part containing a column hb having an odd weight greater than 2, and a second part H'b2 containing matrix elements for row i, columns j, equal and for i = j, and for i = j + i, b in other cases. The extension of the base matrix Hb uses the same sub matrices for ones in each column of the second part of H'b2, and this extension uses the sub matrix matrices for the even number of ones in hb.

The present invention includes a device comprising memory means for storing the H matrix, a receiver for receiving the signal vector y = (yb. Yn-i) and a microprocessor using the H matrix to determine the parity check bits (sb,., Sk-i). The H matrix is ​​an extension of the Hb base matrix, where Hb comprises the Hbi member and the Hb2 member, wherein Hb2 comprises a first portion comprising an hb column having an odd weight greater than 2. Hb2 contains the second part of H'b2 containing matrix elements for row i, columns j, equal i for i = j, and for i = j + i, b in other cases. Two identical sub matrices are used to extend ones in each H'b2 column, and sub matrix matrices are used to extend the even number of ones in hb.

[0017] Returning now to the drawing in which similar markings mean similar components, Fig. 3 is a block diagram of a 3bb encoder according to a first embodiment of the present invention. As shown, the 3bb encoder includes a 3bi microprocessor and a 3b3 lookup table. In a first embodiment of the present invention, the 3bi microprocessor includes a digital signal processor (DSP), e.g., but not limited to, MSC83bb and DSP563bb processors. In addition, the 3b3 lookup table serves as storage means for storing the matrix and includes read-only memory; however, those of ordinary skill in the art will recognize that other types of memory may also be used (e.g., random access memory, magnetic memory, etc.). In the second embodiment, the functionality of the 3bi microprocessor and the 3b3 lookup table may be included in the ASIC ( application specific integrated circuit) or FPGA (field programmable gate array). In particular, the lookup table 3b3 can be implemented in the form of a memory corresponding to the presence or absence of signal paths in the circuit.

[0018] As previously discussed, the encoded data is generally output as a number of parity check bits complementing the systematic bits, with the parity check bits and systematic bits forming the code word x. In the first embodiment

- the present invention, the parity check matrix H is stored in the look-up table 303 and is read by the microprocessor 301 to solve equation (1). In particular, the 301 microprocessor determines the proper values ​​of the parity check bits p = (po, p_m-1) based on the current symbol set s = (p₀, p_k.₁) and the parity matrix H. The parity bits and symbol set are then forwarded to the transmitter and transmitted to the receiver.

[0019] Fig. 4 is a block diagram of a decoder 400 in accordance with one embodiment of the present invention. As shown, the decoder 400 includes a microprocessor 401 and a lookup table 403. In a first embodiment of the present invention, the microprocessor 401 includes a digital signal processor (DSP), e.g., but not limited to, MSC8300 and DSP56300. In addition, the look-up table 403 acts as storage means for storing the H matrix and includes read-only memory. However, those of ordinary skill in the art will recognize that other types of memory may also be used (e.g., random access memory, magnetic memory, etc.). In the second embodiment, the functionality of the microprocessor 401 and lookup table 403 may be included in the ASIC or FPGA. In particular, the look-up table 403 may be implemented in the form of a memory corresponding to the presence or absence of signal paths in the circuit.

[0020] The received signal vector (received by the receiver) y = (y0. Yn-1) corresponds to the code word x, transmitted over a noisy channel, wherein the encoded data x, as discussed previously, is a code word vector. In the first embodiment of the present invention, the parity check matrix H is stored in a look-up table 403 and is read by the microprocessor 401 for decoding and estimating the current symbol set s (i.e. the current symbol set (s0,., Sk-1)). In particular, microprocessor 401 estimates the current symbol set (s0, sk-1) based on the received signal vector y = (y0. Yn-1) and the H parity check matrix.

[0021] As is well known in the art, there are many ways in which the decoder 400 can use the H parity check matrix on the 401 microprocessor for decoding. One such method is to perform vector-matrix multiplication with the H matrix to determine the probable error distribution. Another such method is to use the H matrix to build a bipartite graph, in which the edges of the graph correspond to the ones in the H matrix, and iterative y processing on the bipartite graph.

[0022] For the structured LDPC code, the zxz matrix can be a permutation matrix, the sum of the permutation matrix or any type of binary matrix. Because the permutation matrix P has one one in each row and one one in each column, the weight distribution of the extended H matrix is ​​the same as the base matrix Hb if the permutation sub matrix is ​​used. Therefore, the Hb weight distribution is chosen as close as possible to the desired final weight distribution. The following description is an illustration for the case in which Hb elements are replaced by permutation matrices, however any matrices can be used. If the permutation sub-matrix Pzxz of the vector edge has one at position (p (i), i) (row, column), then the i-th edge in the vector edge is permutated to p (i) -th position before joining this vector edge with the vector vertex control. In other words, this permutation connects the i-th node of the variable in the associated vertex of the vector variable with the p (i) -th control vertex in the associated vector control vertex.

[0023] Permutations containing H can be very simple without compromising performance, e.g., cyclic simple

- 8 bit shift and / or inversion. For example, a simple right cyclic shift can be used. With this limitation, each H matrix can be uniquely defined by the Hbm matrix of the dimensions mbxnb, which can be obtained by • replacing every zero in Hb with -1 for denoting zero sub matrices with the dimensions zxz, and • replacing each hij = 1 in Hb by offset cyclical size p (i, j), where p (i, j) is non-negative.

[0024] Since (x mod z) - cyclic shift to the left is the same ((zx) mod z) - cyclic shift to the right, it is appropriate to discuss the cyclic shift to the right and for brevity referring to it as cyclic shift. As discussed above, there is a one-to-one mapping between the H matrix and the Hbm matrix. Therefore - given given from the matrix Hbm is a shorthand representation of the matrix H. In the record, the model matrix is ​​distinguished from the base matrix by the subscript 'bm', and the extended matrix is ​​distinguished by removing the subscript 'bm'. The relationships between these three arrays are illustrated in Fig. 2. Using this structure, the code has an error correction performance similar to a random H matrix of dimensions mxn, while coding and decoding are implemented on a much smaller Hbm matrix.

[0025] For example, the matrix of equation (2) can be used as the base matrix Hb to build the matrix of the Hbm model as follows:

<td> ' ]</td><td> -1</td><td> 0</td><td> -1</td><td> -1</td><td> -1</td><td>! about</td><td> 0</td><td> -1</td><td> -]</td><td> -1</td><td>-1Ϊ</td>

<td> -1</td><td> 2</td><td> -1</td><td> -1</td><td> 0</td><td> -1</td><td>1 ! -and</td><td> 0</td><td> 0</td><td> -1</td><td> -1</td><td> -1</td>

<td> -1</td><td> -1</td><td> 1</td><td> -1</td><td> -1</td><td> 2</td><td> ! ²</td><td> -1</td><td> 0</td><td> 0</td><td> -1</td><td> -1</td>

<td> 2</td><td> -1</td><td> -1</td><td> 1</td><td> -1</td><td> -1</td><td> !^_1</td><td> -1</td><td> -1</td><td> 0</td><td> 0</td><td> -1</td>

<td> -1</td><td> 1</td><td> -1</td><td> -1</td><td> 0</td><td> -1</td><td>! -i |</td><td> -1</td><td> -]</td><td> -1</td><td> 0</td><td> 0</td>

<td> -1</td><td> -1</td><td> -1</td><td> 0</td><td> -1</td><td> 1</td><td>! about</td><td> -1</td><td> -]</td><td> -1</td><td> -1</td><td>oh</td>

ⁿb [0026] If z = 3, the Hbm matrix is ​​replaced by the H matrix in the dimensions (mbxz) x (nbxz) by replacing each -1 by the 3x3 zero sub matrix and each by the Pi matrix, i = 0,1,2, where

<td></td><td>Ί</td><td> 0</td><td> 0'</td><td></td><td> '0</td><td> 1</td><td> 0'</td><td></td><td> '0</td><td> 0</td><td> 1'</td>

<td>Po =</td><td> 0</td><td> 1</td><td> 0</td><td>, p, =</td><td> 0</td><td> 0</td><td> 1</td><td>&gt; p₂ =</td><td> 1</td><td> 0</td><td> 0</td>

<td></td><td> 0</td><td> 0</td><td> 1</td><td></td><td> 1</td><td> 0</td><td> 0</td><td></td><td> 0</td><td> 1</td><td> 0</td>

[0027] It should be noted that P0 is a unit matrix and the columns Pi, and&gt; 0 are columns P0 cyclic shifted to the right.

[0028] For a given vector q = [q0, q1, q2], qP0 = [q0, q1, q2], qP1 = [q2, q0, q1], qP2 = [q1, q2, q0]. In other words, qPi results in a cyclic shift to the right of the vector q. On the other hand, Piq^T results in a cyclic up shift q^T or equivalent cyclic shift to the left q. Similar rules apply when a Q matrix with dimensions zxz is used: QPi results in a cyclical shift to the right of Q columns, PiQ results in a cyclic upward shift of Q rows.

Base matrix H

[0029] For an LDPC code without vectorization, the H matrix with the modified step structure in the H parity part results in efficient coding without sacrificing performance. In general, assuming x = [sp] = [s0, s1,., Sk-1, p0, p1,., Pm-1], the matrix H in the dimensions m by n can be divided into two sub matrices,

Η = [Η, Η₂], (5) where H2 has a modified step structure, and H1 can be a binary matrix with dimensions m by k. The same structure can be used to build the Hb base matrix in the design of the LDPC structured code. Similarly, using the modified step structure, the Hb matrix can be divided into two parts, where Hb1 corresponds to the systematic bits s, Hb2 corresponds to the parity bits p:

<img file="PL2387157T3_D0003.tif" />

[0030] The Hb2 member can later be divided into two members, whereby the hb vector has odd weight h and H'b2 has a stepped structure:

«_b2= [H_b: η;₂]

<td>'A (ο)</td><td> 1</td><td></td>

<td>ad)</td><td> 1 1</td><td> 0</td>

<td></td><td> 1 '</td><td> . 1</td>

<td></td><td> 0</td><td> 1 1</td>

<td>_A ( "and_b-and)</td><td></td><td> 1</td>

[0031] The Hb1 member may have a random structure. Preferably, the entire Hb matrix has a weight distribution as close as possible to the desired weight distribution.

Offset sizes [0032] To convert the base matrix Hb into the matrix of the Hbm model (which extends to H), the size of the cyclic shift p (i, j) must be determined for each one in Hb. The offset sizes can be specified first for H2. Once the offset sizes are already specified for the H2 member, the H1 member offset sizes can be determined so as to achieve good overall H performance. The H1 portion of the base matrix and the offset sizes of the H1 portion of the base matrix (Hbm1 term) can be determined in a variety of ways. For example, offset size values ​​can be selected randomly and confirmed if they do not cause a significant decrease in performance. The decrease in performance may be due to the introduction of an excessive number of small length cycles or low weight code words. Other techniques known in the art for LDPC codes may also be used.

[0033] The cyclic shift sizes p (i, j) for a given target matrix size H should be determined so as to allow efficient coding without reducing decoding performance. To facilitate coding, offsets can be assigned so that all but one matrix

- 1b shifts, corresponding to ones in hb, cancel each other when added to each other, and all vector lines H'b2 cancel each other after adding up. This translates into assigning hb offset sizes in pairs except for one item, and assigning the same offset size to both ones in each column of H'b2. For example, if hb = [1 bb 1 bb 1]^T, as the appropriate column in the model matrix is ​​acceptable hbm = [3 -1 -1 3 -1 -1 -1]^T, because offset size 3 is assigned in pairs. Since all non-zero elements (both ones) in each column in the model matrix are assigned the same offset sizes, any offset size option is equivalent to the offset size b (i.e. unit matrix) plus bit permutation in the vector column. Thus, all H'b2 offset sizes can be zero for convenience, i.e. each one in H'b2 during expansion to H is replaced by a unit matrix with dimensions zxz.

[0034] Due to the occurrence of cycles, the offset dimensions hbm should be determined carefully. To avoid creating short cycles or lightweight code words, certain rules should be used. One of the properties that can be used to avoid cycles is:

If 2c of the edges forms a cycle with a length of 2c in the base matrix Hb, then the corresponding 2c vector edges form cycles with a length of 2c in the extended matrix H if and only if

Xp (') = Σρ ^ ^{mod from}'i = 2 ji = 2 / + 1 y = 0 ..... cl y = O .... cl where z is the expansion coefficient, p (i) is the size of the cyclic edge offset and in the matrix of the H model_bm, and edges 0, 1, 2, ..., 2c-1 (in this order) form a cycle in H_b.

[0035] Due to the structure of Hb2, cycles occur between hb and H'b2. Therefore, any two equal offset sizes in hbm can cause cycle duplication z-fold in the extended H matrix as per the above property. However, if these two offsets are far apart, then the cycles are long and have little effect on iterative decoding. Therefore, in a preferred embodiment, when the hb of the base matrix has three ones, to maximize the length of the cycles two ones that have equal offset sizes assigned can be placed at the top and bottom of hbm (as far apart as possible), leaving one one in the middle of hb with offset size without pair. For example, hbm = [3 -1 3 -1 -1 -1 4]^T would give from cycles 6 between hi H'2, while hbm = [3 -1 4 -1 -1 -1 3]^T would give from cycles 14 between hi H'2, where hi H'2 are the result of hb and H'b2.

[0036] In summary, the Hb2 term is mapped to the model matrix

Hbm? ^— l ^ bm l Hbm?]

<td>ίΎ)</td><td>p (0, k_b + L)</td><td></td><td></td><td></td>

<td>POA)</td><td>peak_b + L)</td><td>p (l *_t+2) p {2, k_b+2) </td><td>. p (m_b-3 n_b-2) p (m_b -2, n_b -2)</td><td>p (m_b - 2, n_b l)</td>

<td>p (m_b-i, k_b)</td><td></td><td></td><td></td><td>/ Ύ —l, n_b l)</td>

- 11 where kb = nb-mb, in hbm there are h (odd, wh&gt; = 3) non-negative elements, and elements -1 in H'bm2 are left blank for brevity. All p (i, kb) values ​​occur even an even number of times in hbm with the exception of one that can be mapped to any non-zero sub matrix. Because wh is odd, all wh offsets can have the same value (e.g., 0). For H'bm2, p (i, j) = p (i + 1, j), j = kb + 1, kb + 2,., Nb-1, i = j-kb-1. In a preferred embodiment, assuming wh = 3, one example has h_bm = [0 -1 ... -1 p_h -1 ... -1 ... 0]^T, p_h mod z # 0 ip (i, j) = p (i + 1, j) = 0, j = k_b+ 1, k_b+2, ..., n_b-1, i = jk_b-1 in the H'bm2 segment.

[0037] Although the above description has focused on the use of sub matrices, which are a cyclic shift of the unit matrix, in general any other sub matrices (which will be represented in the equivalent of the matrix of the base model) may be used. To facilitate coding, the following restrictions apply:

1. In each H'bm2 column, two non-zero sub matrices are equal;

2. wh (odd, wh&gt; = 3) non-zero sub matrices hbm creates pairs (i.e. one sub matrix is ​​identical to another sub matrix), with the exception of one sub matrix, which can be any non-zero matrix.

Coding [0038] Coding is the process of determining the parity sequence p of a given information sequence s. For structuring the LDPC code, each operation is performed on a group of bits instead of on individual bits. Alternatively, vector operations need not be used, and the following equations are implemented in an equivalent scalar form. s is split for encoding into kb = nbmb groups of bits. Let this grouped s be marked by u, u = [u (o) u (l) ··· u (Ą, —1)], (10) where each element of u is the following column vector

4)=[·*« ·*,·_{ζ +}ι - W-iF · ⁽¹¹⁾ [0039] Using the matrix of the Hbm model, the parity sequence p is defined in groups z. Let p grouped be denoted by v, v = [v (0) v (l) ·· y (m_b-1)], (12) where each element v is the following column vector ^v(') = [p, with Piz + i ·· Ρ (ί + ι) ζ-ιΓ · (¹³) [0040] The coding is performed in two stages, (a) initialization, in which v (0) is determined, and (b) recursion, in which v (i + 1) zv (i), 0 &lt;and &lt; m_b-2.

[0041] The expression on v (0) can be derived by adding up the lines of equation (1) to obtain

<img file="PL2387157T3_D0004.tif" />

where x is the index of the hbm line, where the element is non-negative and is used an odd number of times. In a preferred embodiment, the top and bottom elements h_bm are a couple, that's why 1 &lt;x &lt;m_b2. Equation (14) is solved relative to v (0) by multiplying both sides by P. In the particular case under consideration here, in which p (x, kb) represents a cyclic shift, P = P. In other words, v (0) is obtained by

<img file="PL2387157T3_D0005.tif" />

[0042] In general, recursion expressed by equations (16) and (17) can be derived by taking into account the structure of H'b2,

<img file="PL2387157T3_D0006.tif" />

<img file="PL2387157T3_D0007.tif" />

where

Ρ-ι-θ_ζχ_ζ· (18) [0043] Therefore, all parity bits except v (0) are determined by iterative calculation of equations (16) and (17) for 0 &lt;and &lt;mb-2.

[0044] In the preferred embodiment in which all sizes of the ones offset in H'b2 are zero, equations (16) and (17) can be simplified to equations (19) and (20),

<img file="PL2387157T3_D0008.tif" />

<img file="PL2387157T3_D0009.tif" />

[0045] Thus, as in the general case, all parity bits except v (0) are determined by iteratively calculating equations (19) and (20) for 0 &lt;and &lt;mb-2.

[0046] Equations (14), (19) and (20) describe the coding algorithm. These equations also have a direct interpretation in the conditions of standard digital logic architecture. First, because the non-negative elements p (i, j) from Hbm represent the sizes of the cyclic vector shift, all products of the form Pp (i, j) u (j) can be implemented by a barrel shifter of size z. The zero-size cyclic shift does not need to be processed in the cyclic shift register. Because a cyclic shift register that performs all possible shifts

- 13 cyclic, must provide connections from each input bit to all output bits, the speed with which it can work depends on z. For a given z, the complexity can be reduced and the speed increased by allowing only the appropriate subset of all possible cyclic shifts. For example, Hbm can be built of even even cyclic shift sizes. The sums in equations (14), (19) and (20) represent vector XOR operations (excluding OR), which are gated (i.e. not updated) when p (i, j) = -1.

[0047] For the implementation of summation in equations (14), (19) and (20), the elements p (i, j) in H_bm, 0 &lt;and &lt;k_b, 0 &lt;j &lt;m_b1, can be stored in read-only memory (ROM) with a log2 length of + 1 bits. Grouped information sequences can be stored in a z-size memory that can be read sequentially. As each information vector u (j) is read, the corresponding elements from the Hbm ROM can be read, which gives the cyclic shift register instructions regarding the required cyclic shift. After a cyclical shift, the register containing the partial sum is updated. In the case of equation (14), after each internal summation has been completed, the result can be used to update another register containing external summation. After completing the external summation, it can be cyclically shifted by zp (x, kb).

[0048] Assuming that the cyclic register shift can be performed in one clock cycle, the coding can be implemented in approximately (kb + 1) mb clock cycles. This number can be reduced at the expense of additional mb-1 registers of length z by calculating and saving additions from equations (19) and (20), using the results that become available after calculating equation (14).

Matrix extension [0049] The code extension procedure may be applied to structured code to obtain less efficient code. The code with lower efficiency can be used progressively in subsequent transmissions in the incremental redundancy procedure (IR). In particular, if the matrix of the first transmission model is

<img file="PL2387157T3_D0010.tif" />

then the model matrix for the second transmission can be

<img file="PL2387157T3_D0011.tif" />

etc., where for each transmission and the sub matrix H has the form according to (9) and has the size m_b^(L)x mb^(L). The first transmission may send nb⁽¹⁾= Kb + m⁽¹⁾ bit groups, [u (0), u (1), ..., u (kb-1), v⁽¹⁾(0), v⁽¹⁾(1), ..., v⁽¹⁾(mb⁽¹⁾-1)], each group of size z. Decoding after the first transmission is performed using the received signals [u (0), u (1), ..., u (kb-1), v⁽¹⁾(0), v⁽¹⁾(1), ..., v⁽¹⁾(mb⁽¹⁾-1)] and (21). The second transmission may send a different group of bits with size z, [v⁽²⁾(0), v⁽²⁾(1), ..., v⁽²⁾(mb⁽²⁾-1)], where m2 = mb⁽²⁾z, a bits from the first transmission and from the second transmission together, [u (0), u (1), ..., u (kb-1), v⁽¹⁾(0), v⁽¹⁾(1), ..., v⁽¹⁾(mb⁽¹⁾-1), v⁽²⁾(0), v⁽²⁾(1), ..., v⁽²⁾(mb⁽²⁾-1)], are the code word corresponding to (22). Thus, decoding after the second transmission is performed based on (22) and combined signals received from the first transmission and the second transmission. This procedure can be repeated for more transmissions. Decoding after

- 14 the second transmission is based on the code with efficiency k_b/ n_b⁽²⁾= Kb / (nb⁽¹⁾+ mb⁽²⁾), which is smaller than the one from the first transmission. This procedure can be repeated for more transmissions, with each additional transmission using a stronger code with less efficiency.

[0050] Fig. 5 is a flowchart showing the operation of the encoder 300 and in particular the microprocessor 301. The flowchart begins with step 501, in which the current symbol set (s0,., Sk-1) is received by the microprocessor 301. In step 503, the values the parity check bits are determined based on the current symbol set and H. In particular, the parity check bits (p0,., pm-1) are determined as described above, where H is an extension of the base matrix Hb. As discussed, Hb includes a member Hb1 and a member Hb2, wherein Hb2 comprises a first portion comprising a column hb having an odd weight greater than 2, and a second portion H'b2 containing matrix elements for row i, columns j equal to 1 for i = j, 1 for i = j + 1, 0 in other cases. In addition, the extension of the base matrix Hb (for the construction of H) uses the same sub matrices for ones in each column of the second part of H'b2, with the extension using pairs of matrices for the even number of ones in hb. At step 505, the current symbol set and parity bits are transmitted by radio transmission.

[0051] Fig. 6 is a flowchart showing the operation of a decoder 400, and in particular a microprocessor 401. The flowchart begins with step 601, where the signal vector y = (y0. Yn-1) is received. In step 603, estimates of the current symbol set s (i.e., the current symbol set (s0,., Sk-1)) are determined based on H. As discussed, H is an extension of the base matrix Hb, where Hb comprises the Hb1 member and the Hb2 member, where Hb2 contains the first part containing the hb column having an odd weight greater than 2, and the second part H'b2 containing the matrix elements for the row i, column j, equal to 1 for i = j, 1 for i = j + 1, 0 in other cases.

[0052] Although the invention has been detailed and described with reference to a particular embodiment, it will be understood by those skilled in the art that various changes in form and detail can be made therein without departing from the idea and scope of the invention. For example, although the invention is presented with x defined in the order si and pi, a person with average knowledge of the state of the art may notice that a different order of bits in x is possible, since the bits of the codeword can be collected in any order as long as columns H are properly rearranged . In addition, although the above description has been presented in detail and described with reference to binary codes (i.e. codes defined above the body of Galois GF (2)), a person with average knowledge of the state of the art may notice that arbitrary GF may well be used. Although the examples given above are presented in a given form, other forms are possible which allow similar coding and code modification procedure. For example, H lines can be rearranged without affecting the value of the parity check bits. In another example, a modified step structure may be used for a subset of parity check bits. In yet another example, additional steps may be performed when extending the base matrix to the extended matrix. The H matrix can also be used with any type of decoder that involves using a parity matrix. These changes are intended to fall within the scope of the following claims.

- i5 -