Description

Title of Invention: CHANNEL-ENCODING/DECODING APPARATUS AND METHOD USING LOW-DENSITY PARITY- CHECK CODES

Technical Field

[1] The present invention relates to data processing technology using an error correcting code, and more particularly, to a channel encoding/decoding apparatus and method using a Low-Density Parity-Check (LDPC) code. Background Art

[2] In a wireless communication system, the performance of a link can be significantly deteriorated due to a variety of causes, such as Inter-Symbol Interference (ISI), various noises, and fading phenomena of a channel. It is necessary to develop technology in order to resolve the problems caused by noises, fading, and ISI in order to implement high-speed digital communication systems that require a large amount of data processing and a high reliability of data, such as next generation mobile communication systems, digital broadcasting systems, and mobile Internet communication systems. Active research has recently been conducted on the utilization of an error- correction code as a method for efficiently restoring the distorted information and enhancing the reliability of communication.

[3] The Low-Density Parity-Check (LDPC) code, first introduced by Gallager in the

1960's, has been underutilized due to its complexity of implementation, which far surpassed the technology available at that time. However, as a turbo code discovered by Berrou, Glavieux, and Thitimajshima in 1993 shows the performance approaching Shannon's channel capacity, extensive analytical research has been performed on the performance and characteristics of the turbo code. Research has also been conducted on channel encoding based on iterative decoding and graphs. The research as described above has led to the resurgence of the LDPC code in the late 1990's. The resurgence showed that the performance of the LDPC code approaches Shannon's channel capacity when decoding is performed by applying the iterative decoding based on a sum-product algorithm on a Tanner graph (a special case of a factor graph) corresponding to the LDPC code. Disclosure of Invention

Technical Problem

[4] The present invention has been made in view of the above problems, and provides a method and apparatus that sub-optimizes cycle characteristics of the Low-Density Parity-Check (LDPC) code during the LDPC code design and thus leads to the efficient design of the parity check matrix of the LDPC code.

[5] The present invention further provides a method and apparatus that generates a

LDPC code having different block lengths from the parity check matrix of a LDPC code that is designed by sub-optimizing cycle characteristics of a LDPC in order to increase the storage efficiency of a memory that stores LDPC codes. Solution to Problem

[6] In accordance with an embodiment, the present invention provides a method for encoding an LDPC code including extracting basic column group information, serving a set of information regarding positions of rows with weight 1, from a reference column in each column group of a predetermined parity-check matrix; generating column group information that transforms the positions of rows with weight 1 in the reference column of each column group in the extracted basic column group information into to positions whose lengths are within a required parity length; generating a parity-check matrix using the generated column group information; and encoding data using the generated parity-check matrix.

[7] In accordance with another embodiment, the present invention provides a method for decoding an LDPC code including extracting basic column group information, serving a set of information regarding positions of rows with weight 1, from a reference column in each column group of a predetermined parity-check matrix; generating column group information that transforms the positions of rows with weight 1 in the reference column of each column group in the extracted basic column group information into to positions whose lengths are within a required parity length; generating a parity-check matrix using the generated column group information; and decoding data using the generated parity-check matrix.

[8] In accordance with another embodiment, the present invention provides an apparatus for encoding an LDPC code including an LDPC code parity-check matrix extracting part that extracts basic column group information, serving a set of information regarding positions of rows with weight 1, from a reference column in each column group of a predetermined parity-check matrix; generates column group information that transforms the positions of rows with weight 1 in the reference column of each column group in the extracted basic column group information into to positions whose lengths are within a required parity length; and generates a parity-check matrix using the generated column group information; and an LDPC encoder that encodes data using the generated parity-check matrix.

[9] In accordance with another embodiment, the present invention provides an apparatus for decoding a LDPC code including an LDPC code parity-check matrix extracting part that extracts basic column group information, serving a set of information regarding positions of rows with weight 1, from a reference column in each column group of a predetermined parity-check matrix; generates column group information that transforms the positions of rows with weight 1 in the reference column of each column group in the extracted basic column group information into to positions whose lengths are within a required parity length; generates a parity-check matrix using the generated column group information; and an LDPC decoder that decodes data using the generated parity-check matrix.

Advantageous Effects of Invention

[10] As described above, the method and apparatus, according to the present invention, can efficiently design LDPC codes whose codeword is relatively long from a relatively small size of parity check matrix, while retaining the cycle characteristics on the sub- optimized Tanner graph, thereby designing the parity check matrix of LDPC codes whose codeword is relatively long.

[11] The method and apparatus, according to the present invention, can generate LDPC codes having a variety of block lengths using information regarding a given parity check matrix in a communication system using the LDPC codes. Since the method and apparatus, according to the present invention, can support the LDPC codes having a variety of block lengths using a single parity check matrix, it can efficiently store information regarding the parity check matrix and allow for the easy extension of the system. Brief Description of Drawings

[12] The features and advantages of the present invention will become more apparent from the following detailed description in conjunction with the accompanying drawings, in which:

[13] FIG. 1 shows a parity-check matrix of a LDPC code with a length of 8;

[14] FIG. 2 is a diagram illustrating a Tanner graph of the parity-check matrix corresponding to the LDPC code with a length of 8;

[15] FIG. 3 is a diagram illustrating a structure of a DVB-S2 LDPC code;

[16] FIG. 4 is a diagram illustrating a parity-check matrix of an LDPC code in the form of

DVB-S2;

[17] FIG. 5 is a flow chart describing a method for generating an LDPC code with a variable length from a parity-check matrix of a given LDPC code, according to an embodiment of the present invention;

[18] FIG. 6 shows a parity-check matrix that describes a method for designing a DVB-S2

LDPC code, according to the present invention;

[19] FIG. 7 shows a parity-check matrix that describes a method for designing a DVB -S2 LDPC code, according to the present invention;

[20] FIG. 8 shows a parity-check matrix that describes a method for designing a DVB -S2

LDPC code, according to the present invention;

[21] FIG. 9 is a block diagram illustrating a communication system using an LDPC code, according to an embodiment of the present invention;

[22] FIG. 10 is a block diagram illustrating a transmitter using an LDPC code, according to an embodiment of the present invention;

[23] FIG. 11 is a block diagram illustrating a receiver using an LDPC code, according to an embodiment of the present invention; and

[24] FIG. 12 is a flow chart describing a method for performing receiving operations in a receiver using an LDPC code, according to an embodiment of the present invention. Mode for the Invention

[25] Hereinafter, embodiments of the present invention are described in detail with reference to the accompanying drawings. The same reference numbers are used throughout the drawings to refer to the same or similar parts. Detailed descriptions of well-known functions and structures incorporated herein may be omitted to avoid obscuring the subject matter of the present invention.

[26] A Low-Density Parity-Check (LDPC) code is usually represented using a graph representation method. The characteristics of the LDPC code can be analyzed using a variety of methods based on graph theory, algebra, and probability theory. In general, a graph model is useful for describing a channel code. That is, when information regarding encoded bits is mapped to the vertexes in a graph and the relationship among the respective encoded bits corresponds to edges in the graph, the graph model may be considered a communication network where the vertexes exchange predetermined messages through the edges. Therefore, a decoding algorithm can be naturally derived from the graph model. For example, examples of a decoding algorithm derived from a Trellis, a type of graph, are a Viterbi algorithm and a Bahl, Cocke, Jelinek, and Raviv (BCJR) algorithm.

[27] The LDPC code is typically defined by a parity-check matrix, and can be represented using a bipartite graph commonly called a Tanner graph. In the bipartite graph, vertexes are divided into two different types. The LDPC code is represented by the bipartite graph composed of vertexes called 'variable nodes' and 'check node.' The variable nodes correspond to encoded bits, respectively.

[28] A description is provided for a graph representation method of the LDPC code, referring to FIGS. 1 and 2.

[29] FIG. 1 shows an example of a parity-check matrix H ₁ of an LDPC code. In an embodiment of the present invention, the parity-check matrix H ₁ is a 4x8 matrix. Referring to FIG. 1, since the matrix H ₁ has 8 columns, an LDPC code generates a codeword with a length of 8, and each column corresponds to 8 encoded bits.

[30] FIG. 2 is a diagram illustrating a Tanner graph corresponding to the parity-check matrix H ₁ of the LDPC code with a length of 8.

[31] Referring to FIG. 2, the Tanner graph of the LDPC code includes eight variable nodes x ₁ (202) _, x ₂ (204) _, x ₃ (206) _, X ₄ (208) _, X ₅ (210) _, x ₆ (212) _, x ₇ (214) _, and x ₈ (216) _, and four check nodes 218, 220, 222, and 224. The i" ¹ column and j" ¹ row in the parity-check matrix H ₁ Of the LDPC code correspond to the variable node X ₁ and the j" ¹ check node, respectively. In addition, a value of 1, i.e., a non-zero value, at the point where an ith column and a j^row in the parity-check matrix H ₁ of the LDPC code cross each other, indicates that there is an edge between the variable node X ₁ and the j ^ check node on the Tanner graph shown in FIG. 2.

[32] In the Tanner graph of the LDPC code, the degree of the variable node and the check node indicates the number of edges linked to respective nodes. That is, the degree is equal to the number of non-zero entries in a column or row corresponding to a node in the parity-check matrix of the LDPC code. For example, as shown in FIG. 2, the degrees of the variable nodes XK202), x ₂ (204), x ₃ (206), x ₄ (208), x _s (210), x ₆ (212), X ₇ (214), and x ₈ (216) are 4, 3, 3, 3, 2, 2, 2, and 2, respectively. The degrees of check nodes 218, 220, 222, and 224 are also 6, 5, 5, and 5, respectively. Furthermore, the numbers of non-zero entries in the columns of the parity-check matrix H ₁ of FIG. 1, which correspond to the variable nodes of FIG. 2, are consistent with the degrees 4, 3, 3, 3, 2, 2, 2, and 2, respectively. Similarly, the numbers of non-zero entries in the rows of the parity-check matrix H ₁ of FIG. 1, which correspond to the check nodes of FIG. 2, are also consistent with the degrees 6, 5, 5, and 5, respectively.

[33] In order to express the distribution of the degree of nodes with respect to the LDPC code, a ratio of the number of degree-i variable nodes to the total number of variable nodes is defined as f,, and a ratio of the number of degree-j check nodes to the total number of check nodes is defined as g _r For example, in the LDPC code corresponding to FIGS. 1 and 2, f ₂ =4/8, f ₃ =3/8, f ₄ =l/8, and f ₁₌ θ for i≠2, 3, and 4, and g ₅ =3/4, g ₆ =l/4, and g _j =O for j≠5, and 6. When a length of the LDPC code, i.e., the number of columns, is defined as N, and the number of rows is defined as N/2, the density of non-zero entries in the entire parity-check matrix having the distribution of the degree described above is calculated as shown in Equation (1).

^[34] 2f ₂ N+Zf,N+±f,N_ ^25 N' N/2 N (1)

[35] In Equation (1), if N increases, the density of l's in the parity-check matrix decreases. In general, since the density of non-zero entries is inversely proportional to the code length N, the LDPC code with a relatively large length N has a very low density of non-zero entries. The term 'low-density' in the name of the low-density parity-check code originates from the above-mentioned relationship.

[36] FIG. 3 is a diagram illustrating a structure of a DVB-S2 LDPC code. A description is provided for the characteristics of the parity-check matrix of the LDPC code having a particular structure referring to FIG. 3, where the LDPC code has been adopted as the standard technology in Digital Video Broadcasting-Satellite transmission 2 ^nd generation (DVB-S2), which is one of the European digital broadcasting standards.

[37] Referring to FIG. 3, Ni denotes a length of an LDPC codeword, K ₁ a length of an information word, and (Ni-K ₁ ) a parity length. Integers, M ₁ and q, are determined to satisfy q=(N ₁ -K ₁ )/M ₁ . Preferably, K ₁ ZM ₁ should also be an integer. For convenience, the parity-check matrix of FIG. 3 is called a first parity-check matrix H ₁ .

[38] As shown in FIG. 3, a parity portion, i.e., K ₁ " ¹ through (N ₁ -I) ¹¹¹ columns, in the parity- check matrix, forms a dual diagonal shape. Therefore, in the distribution of the degree of columns corresponding to the parity portion, all columns have a degree '2', except for the last column having a degree T.

[39] A portion corresponding to information word, i.e., 0 ^th through (K ₁ -I) ¹¹¹ columns, in the parity-check matrix, satisfies the following Rules 1 and 2.

[40] Rule 1

[41] The portion generates a total of KJM ₁ column groups by grouping K ₁ columns corresponding to the information word in the parity-check matrix into multiple groups each including M ₁ columns. A method for forming columns belonging to each column group follows Rule 2 below.

[42] Rule 2

[43] The portion determines positions of Ts in each 0 ^th column in I ^th column group (i=l, .

. . , KJM ₁ -1). The degree of a 0 ^th column in each i ¹¹¹ column group is hereinafter denoted by D ₁ . If it is assumed that positions of rows with 1 are R _1>0 ⁽¹⁾ , R _h o ⁽² \... , R ₁ / ¹ ^, positions R ₁₀ W (k=l, 2, . . . , D ₁ ) of rows with 1 are defined as shown in Equation (2), in a j ¹¹¹ column (j=l, 2, . . . , M ₁ -I) in an I ^th column group.

[44] R ₁ / ⁾ = R _110-1 )OO + q UiOd(N ₁ -K ₁ ) (2)

[45] Where k=l, 2, . . . , D ₁ , i=l, . . . , KJM ₁ -1, and j=l, 2, . . . , M ₁ -I.

[46] According to Rules 1 and 2, the degrees of columns belonging to an i ¹¹¹ column group are all equal to D ₁ .

[47] Through an example, the structure of the LDPC code, as shown in FIG. 3, is explained in detail that stores information regarding the parity-check matrix according to rules 1 and 2.

[48] For example, if N ₁ =SO, K ₁ =IS, M]=5, and q=3, information regarding the positions of rows with weight 1 in the 0 ^th columns in 3 column groups can be expressed as follows:

[49] R ₁ / ⁾ = 0, R ₁ ^ ⁾ = I, Ri/ ³⁾ = 2

[50] R ₂ / ¹⁾ = 0, R ₂ / ²⁾ = 11, R ₂ / ³⁾ = 13

[51] R ₃ / ¹⁾ = 0, R ₃ / ²⁾ = 10, R ₃ / ³⁾ = 14

[52] A set of information regarding the positions of rows with weight 1 in reference columns in each column group can be called column group information. For convenience, in an embodiment of the present invention, the 0 ^th column represents the reference column in each column group. It should be understood that other columns, for example, the 1 ^st columns in each column group, may be a reference column. In that case, column group information may contain information regarding the positions of rows with weight 1 in the 1 ^st column in each column group. It will be appreciated that information regarding the positions of rows with weight 1 in the 0 ^th columns and other columns in each column group can be extracted by the same method.

[53] Regarding the rows with weight 1 in the 0 ^th columns in each column group, only the corresponding position information is expressed for each column group as follows:

[54] [0, 1, 2]

[55] [0, 11, 13]

[56] [0, 10, 14]

[57] The I ^th column sequence sequentially represents information regarding the positions of rows with weight 1 in the 0 ^th column in the i" ¹ column group.

[58] FIG. 4 is a diagram illustrating a parity-check matrix of an LDPC code in the form of

DVB-S2.

[59] If a parity-check matrix is formed by using the information corresponding to the detailed example and Rules 1 and 2, as described above, it is possible to generate an LDPC code, as shown in FIG. 4, having the same concept as that of the DVB -S2 LDPC code of FIG. 3.

[60] It is well known that the performance of an LDPC code is closely related to cycle characteristics of a Tanner graph. If the number of short cycles is numerous on a Tanner graph, it has been empirically proven that performance aging may occur in the LDPC code. It should be considered characteristic of the cycles on the Tanner graph in order to design an LDPC code having a preferable performance.

[61] It is, however, difficult to design a parity-check matrix of the LDPC code whose codeword length is a few tens of bits by considering the characteristics of cycles on a Tanner graph. A method has not yet been developed to enhance the characteristics of cycles of the LDPC code having the structure shown in FIG. 3. A DVB-S2 LDPC code employing the structure of the LDPC code does not take into account the optimization of the characteristics of cycles on a Tanner graph, and thus shows an error flow phenomenon with a high Signal to Noise Ratio (SNR). [62] Therefore, in order to design an LDPC code having the structure shown in FIG. 3, a method is required to improve the characteristics of cycles and design a parity-check matrix.

[63] The DVB-S2 standard using the LDPC code is disadvantageous in that the LDPC code has only two block lengths due to code use limitation and the storage of different types of parity-check matrixes to support the two block lengths.

[64] In order to apply an LDPC code to a real communication system, an LDPC code needs to be designed to comply with the data transmission amount that the real communication system requires. In particular, an LDPC code having a variety of block lengths is needed to support a variety of data transmission amounts according to a user's request in an adaptive communication system and a communication supporting a variety of broadcasting services. The adaptive communication system employs a Hybrid Automatic Retransmission reQuest (HARQ), an adaptive modulation and coding (AMC), etc.

[65] The storage efficiency of a memory deteriorates if the memory stores independent parity-check matrixes with respect to each block length of an LDPC code. Therefore, a method is required to efficiently support a variety of block lengths from the existing parity-check matrix without designing a new parity-check matrix.

[66] The present invention provides a method that designs a parity-check matrix with a large LDPC code from a parity-check matrix of an existing small LDPC code. It also provides an apparatus and method that supports a variable block length in a communication system using a particular form of LDPC code.

[67] For convenience, it is assumed that an LDPC code is given that has a particular structure identical to that of the LDPC code that was designed based on Rules 1 and 2, as shown in FIG. 3. A parity-check matrix of the given LDPC code is referred to as a first parity-check matrix H ₁ . Lengths of a codeword and an information word of the matrix H ₁ are represented by N ₁ and K ₁ , respectively. (N ₁ -K ₁ ) is a parity length. Integers M ₁ and q are determined to satisfy q=(N ₁ -K ₁ )/M ₁ . K ₁ ZM ₁ is also an integer.

[68] It is also assumed that the positions of l's in each 0 ^th column in the i" ¹ column group

(i=0, 1, . . . , K ₁ ZM ₁ -1), indicating information regarding the matrix H ₁ , are represented by R _1>0 ⁽¹⁾ , R ₁ / ²⁾ ,... , Ri,o ^(Dl) - The symbol D ₁ is the degree of 0 ^th column in each i" ¹ column group.

[69] The present invention provides a method that designs a second parity-check matrix H

₂ , satisfying the following Rules 3 to 6. It is assumed that the lengths of a codeword and an information word of the matrix H ₂ are represented by N ₂ and K ₂ , respectively.

[70] Rule 3

[71] A positive integer p has a relation as follows: N ₂ =PN ₁ , K ₂ =PK ₁ , and M ₂ =PM ₁ .

Therefore, K ₂ ZM ₂ =K ₁ ZM ₁ is achieved, so that the number of column groups with respect to the information word portion are identical to each other. In addition, (N ₂ -K ₂ )/M ₂ = q = (N ₁ -K ₁ )M ₁ is also established.

[72] Rule 4

[73] The distribution of the degrees of information word portions between the parity- check matrixes H ₁ and H ₂ are equal to each other. It is assumed that the position of l's in each 0 ^th column in the i" ¹ column group (i=0, 1, . . . , K ₁ ZM ₁ -1) representing the parity-check matrix H ₂ is S _{l 0} ^(k) , where k=l, 2, ..., D ₁ . The symbol D ₁ is the degree of 0 ^th column in each i" ¹ column group.

[74] Rule 5

[75] The characteristics of cycles on a Tanner graph of the matrix H ₂ must not be worse than that of the matrix H ₁ .

[76] Rule 6

[77] A matrix H ₁ can be generated from information regarding a matrix H ₂ .

[78] FIG. 5 is a flow chart describing a method for generating an LDPC code with different block lengths from a parity-check matrix of a given LDPC code, according to an embodiment of the present invention.

[79] In step 510 the method determines a basic parameter of the parity-check matrix H ₂ that will be generated. In step 520 the method defines a partial matrix corresponding to the parity bits of H ₂ by the predetermined structure. In step 530 the method loads the sequence corresponding to the information bits of the given parity-check matrix H ₁ . In step 540 the method determines the sequence corresponding to the information word bits of H ₂ , from the sequence indicating H ₁ through the predetermined process.

[80] Referring to FIG. 5, it is assumed that the parity-check matrix H ₂ of an LDPC code satisfies Rules 3 to 6 described above and thus

D ₀ ≤ - < D _KJMr2 < D _Ki/Mrl is achieved.

[81] Method for designing DVB-S2 LDPC code

[82] Step 1: establish a matrix of (N ₂ -K ₂ )X(N ₂ -K ₂ ), having the same structure as a partial matrix corresponding to the parity portion, to a partial matrix corresponding to a parity portion of the parity-check matrix H ₂ . [83] Step 2: initialize i=0.

[84] Step 3: define a set A ₁ W composed of p sequences as shown in Equation (3), with respect to a sequence R _1>0 ^(k) (k=l, 2, ..., D ₁ ) representing information regarding the i" ¹ column group corresponding to information bits of the parity-check matrix H ₁ . p is a value defined by Rule 3.

[85] A« = { R ₁₁₀ W R ₁₁₀ W + (N ₁ -K ₁ ), ..., R _1>0 « + (P-I)X(N ₁ -K ₁ )) (3)

[86] Step 4: assuming that there is no information word column group corresponding to { (N ₂ -K ₂ )/M ₂ - 1 I ^th column group from (i+ 1 ) ^th column group in the parity-check matrix H

₂ , acquire a sequence S _{l 0} ^(k) (k=l, 2, ..., D ₁ ), sequentially, satisfying the following

Conditions 1 and 2. [87] Condition 1

[88] S _1>0 « e A«, where k=l, 2, ..., D ₁ .

[89] Condition 2

[90] Select one of the sequences satisfying Condition 1, which has the best characteristics of cycles on the Tanner graph. If a number of sequences contain the best characteristics of cycles, an arbitrary one can be selected. [91] Step 5: repeat steps 3 and 4 for i=l, ..., (N ₂ -K ₂ )M ₂ -I

[92] FIGS. 6 to 8 are diagrams describing embodiments of a method for designing an

LDPC code in the form of DVB S2, according to the present invention. [93] Referring to FIG. 6, variables are set as follows: M ₁₌ 3, p=2, M ₂ =PM ₁ =O, (N ₁ -K ₁ )=^ and q=(Ni-Ki)/3=3. Information of the positions of rows with weight 1 for the Oth column in one column group shown in FIG. 6 is :0, 5, 7. [94] That is, in the Oth column in the one column group, only the Oth, fifth, and seven rows have weight 1. It will be easily noted that the first and second columns in the given column group can be acquired by cyclically shifting the positions of weight 1 in the Oth column by q=3, modulo (Ni-Ki)=9. In FIG. 6, the degrees of all columns in the column group are all 3 and the degrees of rows are all 1. [95] FIG. 7 shows a structure of the Oth column in a new group that can be acquired from the given column group of FIG. 6 by the method for designing DVB-S2 LDPC code.

Since the information regarding the positions of rows with weight 1 in the Oth column shown in FIG. 6 is 0, 5, and 7, information regarding the positions of rows with weight

1 in the Oth column in the new column group can be expressed as one of the eight candidates, as follows, of Step 1 through Step 3 of the method for designing the DVB-

S2 LDPC code: [96] {0, 5, 7}, {0, 5, 16}, {0, 7, 14}, {0, 14, 16}, {5, 7, 9}, {5, 9, 16}, {7, 9, 14}, {9, 14,

16} [97] The columns of the information regarding the positions of 8 rows are sequentially shown in FIG. 7. [98] It is assumed that a sequence satisfying Conditions 1 and 2 is determined as the second one of the 8 candidates, {0, 5, 16}, Step 4 of the method for designing the

DVB-S2 LDPC code. In that case, the Oth column of a new column group can be defined as a column where the length of rows is 16, and each of the Oth, fifth and 16th columns has weight 1. [99] The 1st column to 5th (=M ₂ -1) column can be formed by applying the method for generating an LDPC code shown in FIG. 3 to the new Oth column. If cyclic shift is applied to the positions of weight 1 in the Oth column, by q=3, modulo (Ni-Ki)=9, according to the method for generating an LDPC code shown in FIG. 3, the remainder of the columns can be easily acquired. The process of the cyclic shift is illustrated in FIG. 8.

[100] Referring to FIG. 8, it will be noted that the degrees of all columns in the column group are all 3, and the degrees of rows are all 1. That is, the distribution of the degree of information word portions in the embodiment of FIG. 8 is the same as the embodiment of FIG. 6.

[101] The method for designing a DVB-S2 LDPC code satisfies Rules 3 to 6, as follows.

[102] First, the method obviously satisfies Rules 3 and 4 according to its basic assumption.

[103] In order to check the method with respect to Rule 5, it is assumed that S _li0 * = Ri _, o ^(k) for all i and k is fixed at Step 4 of the method for designing a DVB-S2 LDPC code. In this case, since the parity-check matrix H ₂ is processed with the same structure as the parity-check matrix Hi, the matrix H ₂ has the same characteristics of cycles of a Tanner graph as the matrix Hi. Therefore, the method for designing a DVB -S2 LDPC code obviously does not violate rule 5.

[104] Since a sequence having the best characteristics of cycles on a Tanner graph is selected in the method for designing a DVB-S2 LDPC code, the selected sequence has the same or better characteristics of cycles than the case, S _1>0 ^(k) = Ri,o ^(k) for all i and k. That is, it will be noted that the worst case does not occur where the characteristics of cycles between the matrixes H ₁ and H ₂ are guaranteed to be the same and simultaneously are not deteriorated. Therefore, the method for designing a DVB-S2 LDPC code satisfies Rule 5 through Step 4.

[105] The method for designing a DVB-S2 LDPC code is checked with respect to Rule 6. Information regarding column groups representing the parity-check matrix H ₂ , designed by the method for designing a DVB-S2 LDPC code, is defined as S _{l 0} ^(k) (where i = 0, 1, ..., (N ₂ -K ₂ )ZM ₂ -I, and k=l, 2, ..., D ₁ ).

[106] The sequence S _1>0 ^(k) certainly takes a form of S _1>0 ^(k) = R _11O * + Ix(N ₁ -K ₁ ) for an integer 1 according to Step 3 of the method for designing a DVB-S2 LDPC code. Since N ₁ and K ₁ are known, R _1>0 ^(k) can be easily derived from S _li0 * as shown in Equation (4).

[107] S ₁₁₀ W = R ₁₁₀ W UiOd(N ₁ -K ₁ ) (4)

[108] Equation (4) describes that R _1>0 ^(k) does not need to be stored but can be easily acquired by modulo operation of (N ₁ -K ₁ ) if information is available regarding column groups for the parity-check matrix H ₂ . Since the value q is the same with respect to the matrixes H ₁ and H ₂ , the matrix H ₁ can be acquired from the value of R _11O * that is acquired from S _1>0 ^(k) . Therefore, the method for designing a DVB-S2 LDPC code satisfies Rule 6.

[109] In an embodiment of the present invention, the method for designing a DVB-S2 LDPC code is explained in such a way that the parity-check matrix H ₂ is acquired from the parity-check matrix H ₁ . If the method for designing a DVB-S2 LDPC code is repeatedly performed, a larger parity-check matrix can also be acquired.

[110] It is possible to efficiently design a parity-check matrix as the method for designing a DVB-S2 LDPC code is repeatedly applied to the parity-check matrixes H ₁ , H ₂ , H ₃ , ..., H _s satisfying Equations (5), (6), and (7),

[111] N ₁ IN ₂ L-JN ₈ (5)

[112] K ₁ IK ₂ L ₁ JK ₈ (6)

[113] M ₁ IM ₂ L ₁ JM ₈ (7)

[114] where N ₁ , K ₁ , and M ₁ refer to a codeword length of H ₁ , an information word length of H ₁ , and a unit of column group of H ₁ at rule 1, respectively.

[115] It is also possible to form the parity-check matrixes H ₁ , H ₂ , ..., H^ ₁ if information regarding the parity-check matrix H _s , acquired by the method for designing a DVB-S2 LDPC code, is known.

[116] It will be appreciated that a plurality of various sized parity-check matrixes can be generated from one parity-check matrix as the parity-check matrix of an LDPC code satisfies Rule 6. The size of the parity-check matrix refers to the codeword length of an LDPC code. Therefore, it will be noted that the LDPC code, designed by the method of the present invention, can support LDPC codes that have a variety of block lengths through Equation (4). Although the method according to the present invention supports LDPC codes having a various sizes of block lengths, it stores only one piece of information regarding the parity-check matrix in a memory, thereby enhancing the storage efficiency of the memory.

[117] The following Tables 1 to 4 are examples of a parity-check matrix H ₂ designed as the method for designing a DVB-S2 LDPC code is applied to a parity-check matrix H ₁ composed of variables described in Equation (8).

[118] M ₁ =I, N ₁ =ISO, K ₁₌ 120, q=60, p=360, M ₂ =360, N ₂ =64800, and K ₂ =43200 (8)

[119]

Table 1

126424632556307 3437012739154181612*t 1980719841210102112521 171

1131852313249% 59759197965511694134801761318031202θ620346

444360137225295 7401854590281060811 82814216155852001220577

902079680671627889109691171813211139631430015009193792048 7

2281432257426974753789031326813439 1774719986203122138821514

271125817201865 4339741681988276983214358155531592319689

467336738404942 685275258146126481479416503174261832719041

13711602116551261114689153601558416<Ji3182101835718680 1873 _^ 5 19418

3500718173327679939910942112051251 _' I 1705717928182451826420196

187961 180334393/9445188365112011402315238161361948720296

455454452417450 9100116061194814433 1487415628160821770419351

695192953465497 7349120461735717372 1763118109182671347519273

1298295117635

495650 Ild77

653622214805

227496O09743 112971256614567 72811765418609 2473 492314331

87&01404416012 8090814619442 34491289014460 83962337840

805ό 1293315269 84931036612434 701964919076 1398 1027013605

4243933912774 3696769615628 243313011099 2097 464911467

23121202420290 26161713196 7141968410778 3530 57658743

4289718716359 2958533416260 105221142513137 154751690219208

1641928417750 168451770119088 50561746421164 6993 1252113333

72041285414335 25521607821113 542495218819 5740 I 208319726

7387840014186 35171945120524 2616443517063 3732 64407141

138181653317156 115431210912852 3348578120818 9088 915412468

167718163263 54791353818909 70871193317417 2S69 43968334

131501330319272 28121059411226 2812381017336 6532 945714387

443316449173°7 00671365919220 43281105116035 1824 1524420490

218853996750 60521520517475 143741535519910 4762 587412092

1625780813669 3867865017070 78625207181 3231 827811367

15501388417080 125532080321588 179491826319304 6171 5632558

39718017368 241130513354 5927 S04813352 1341 11560020409

2078630214741 124541822418506 5047858109O8 3199 1042211726

1153218212546 47641231316627 51351335013392 889787017425

89161051912615 2562884913143 3267558121485 255467920435

22551078510851 68871401518545 23181094216588 4184 515319022

118621599119165 101911051913960 14601951621166 4031 585918296

105941308318567 87801121218703 42481488419339 2069 301413605

9fi591331519220 44511012619926 3565936219476 4761 795614946

44111306116858 273607516827 703429120357

3702770216415 51881183221198 1154608620199

442058258937 66311258517797 3537 I 42571?073 Table 2

19704567493358S4601077761043111744 13263151851541818761 19939

203156627353l3ϋ 334644346552921392209655101921155112377

554558056a88767 C 773710O08108211374! .1015516472166441812? I 18901

131166024872683 992.0115461417817549 17589189391899020090 20602

827698875598262 8543915712214135011470214886176121956820174

319294931764458 4660469365169358963812451173631907220465

224736855887 E220101611184611866124231696819Q&7199322007421262

712475538280541 1157123901398014600 15104152311553316538 17929

20642819447648829394116601294814705 515977199652017220801 20859

18735625813704451860798563869810276103451054112463184b7

4555844674592078101040811606123081 548416653178821821119101

329 I5όϋ 20263<J2? 6673959510251 124091 735718729189921995520017

2635339812371

49565019537

88651114214333

130501409420783 92661129721407 31411765418609 2473 492321591

87601271218364 6646809011522 3449696019670 830707311080

2729991619353 2866469420733 16605981 10196 1398 361020085

5259862312774 36961195615388 3130893921543 2097 464911467

21701095221564 6171472121296 7141968416118 3530 732510063

2129754710119 2958533416260 7ol71394521502 154751690219208

87211018417750 128251908819681 50561746418584 573526113333

104951285421364 104381463318512 54249521005 ^Q 106001208319726

408759θό 8400 64841683719451 2616443520843 2120 37329721

76161737319278 54491285216223 29881334120818 9088 927412048

1816842320097 30791353818909 42531332717417 4396 833414869

131501468319272 107461155411692 13121335017336 6532 1335714387

44331644917397 6067729912860 43281105116035 1410 182415244

6750779917848 152051759521052 124101535518334 562587412092

78081630916745 30 O67011367 34011728610020 3231 1733821387

136001391018384 7488994-312433 743176241 ^Q 08O 6171 5639938

330119057211o8 2411335415051 5927804818092 1341 11560020409

73011749820702 3524483413406 109981334415958 3199 478217486

75221254015253 123131662718444 47751335013392 7870 1402917425

35761051912555 106621488317849 5581908721485 8039 1087520435

111562259591 14751396718545 2318584216588 5153 1792419022

119711246214005 107801147915231 7480884019516 1976 789915311

6334872710383 4721474317420 17281422419339 2069 301413605

14359659152eϋ 4126445119926 93621364510476 2241 795614946

4781 Oi 1812691 91531249516827 42911606320357

105951676220022 91481183221198 1154621913646

89371266515700 4951574514797 10571235717073 Table 3

259929983291 3793456756447476894592501163012041 123441998; 3

113594666407426 75771023310831 123351567215976179952015220514

194433154108011 76601 8745105081060810821 11636122121514519082

554978991094611 9o21209017083178471844019631 20039200892058921258

239372674687981 10028113171246215272 1774719262194032017421514

5632018343«? 4&93 545870569391 96659832 105o9130761459818340

467560756656934 8062970610101 105721228815067160831752020906

311 148927903597 1482015231 1525515398 73331804218224186801 9454

23994145417θ 4o59619 ^" ? 112051251412620 7261 17928202922138421442

271637946478 ?567100831034510541 13543 10501 16638 1787019459 19487

2034300462849100116Oo 1239313821 14548 14731 15790 Io20819442 21095

69580536065787 tyfl 723273577546 1351? 1440 ^Q 17631 1808918109

IS^l 17078 17035

650349519537

1325314562214o5

170101850321534 48771106614567 13694 !?241 18609 8463 14331 19453

772S7O014044 2450814ό 19442 3449 o9601?o70 S39623311080

1579o 1766919353 94661051420733 5801 880915536 1398 1027018705

4303933912774 3696511615388 243313011099 2097 464911467

980410810 18992 681 1243713190 7141 82589o84 3530 1114316025

16491150716359 4o38533416260 1046213945 14037 115151690219208

5301150417421 28511341 10088 154961746421104 5731 2521 13333

3374341520944 96531221216078 110191338221452 6803 1972621100

7387900018446 1683719451 20524 2616443518/43 3732 7141 21140

41961519817373 50636192121 OO 5781 052820818 O088 927420868

128392971195(3 184581890920899 38471235314.717 4396 833419189

252790313630 28121122611554 28121335017336 6532 789714387

1481310449173^7 6067680015450 3555432811051 1824 1524417730

5399 1221017848 11692 1520517475 124101445520434 4762 58747472

7808 1072911105 158744105230 786252019841 1283 1 1733819527

95801391015U84 103331222314508 743450916724 I5o3 1413814357

53176901 10368 2411 335414871 3407804818092 1341 I 156002040 ^Q

18028681 17498 2074574416166 78581099813344 3199 1042211726

85931254613042 166271844419813 4775108721 «350 889787017425

679517514430 36291066213143 5581 740721485 1995 359914195

87510551 10785 1475 15605157o7 2318572219708 157641817319022

290513651 20802 4699550018891 8840127962ilo6 3956 15311 20379

HH 414314967 4912890019663 42481488421559 2069 301420265

3440965913315 22Oo 4451 19920 9362130451 /oi 6 33bό 795o 9681

3811 8441 10858 6867915313395 7034291 11 ?77

3702662210595 1392800821198 2191364618614

5S25893717080 0374951 12585 35371425717073 Table 4

1798299084?09859 10&271074311271 1234413993140761518515461 15784

4553160407306551 1 ^Q 73164461771719471 20034201522026620836 J 11072

321 3008331510608 12212134251421ft 15448 ! ^" ?244175771820518541 21542

4Ot ⁾ T3425051 7220808386191004710710 11546152581598910389 18 ^* 79

1242 I86023542012 33885194602311522 12481 12577147681774720459

25892658281o 3853 46257463837898321 0951 11158184991899620320

206643835487 E785 049210161 108471479416440184271948Q 20088 I .0542

4358511586938954 109641233012791 13C MO 13860140371804219971 20269

35003899417t> 6521 66051231714194153 ^' )91717217 ^Q 2820 ^Q 8521322; .1384

4364761154310731273241 4278472310541 1212314278 I 604516759

455 108440825980 b2S478549931 108331 I7lθ 12386197082136821561

288o 4287 t>673 '546 83128317905510397 1140915351 1041516489 Io769

273812371 17635

4956503877

653 1456214805

99022743983 78261129714807 7281 817418609 2473 492312231

87601404416012 80901630619442 5789696020030 839617320260

8056842919353 434970621093 Io696221 19076 1398 232510270

2139430312774 3b961195614788 24337301109O 2097 1146716709

2468508132 22371319620481 849896841296] 3530 1006316025

71871070916359 91381596016494 04451313721502 154751690219208

1648721 17750 346517701 1^088 50561746421164 1252 1 1333319233

128541433520944 5372863316078 5492792211019 7540 1208319726

44646278400 1587710451 20524 4435561614003 3732 714121140

32737616127OS 50631210912852 8901 1354820818 6448 969420868

18161340316677 62591353818909 25731741720347 4396 833419369

79031315019272 112261257421112 1230281217336 2272 1438720257

44331644917397 87071286021399 432811051 lo035 1410 182415244

5399873015748 58121747519165 124101535520614 4762 587414972

111651656821349 3037475230 78625207181 3231 1733821387

26301486018384 122231243321588 66691784319304 61715631029S

3301 502811577 2411 3354 &S91 502.7804814312 1341 1 1560020409

1278214741 17498 2074574417726 78581099813344 3199 1042214006

742115312546 60241231316987 4775603013392 889787017425

73910596 12015 4469 I0o6213143 43475581 21435 25535998495

111510551 21585 5075688718545 2318782216588 5153 604419022

60858^1 12+62 4420547910191 490688409916 D391 1963431

10227 I 308321274 5743 ^Q 17217420 42481933920404 1274 206913605

96591331515260 7811 1624619926 93o21095b 17125 7956 9681 14946

1891 5038 15641 91531339513707 16891 1816320357

16762186951O&02 1382005221388 219115413640

11805825 18717 6377831 12585 35371083717073

[123] FIG. 9 is a block diagram illustrating a communication system that encodes a DVB- S2 LDPC code, according to an embodiment of the present invention.

[124] Referring to FIG. 9, an LDPC encoder 911 of a transmitter 910 encodes a message u. A modulator 913 modulates the encoded message c. The modulated signal s is transmitted via a Radio Frequency (RF) channel 920. A demodulator 931 of a receiver 930 demodulates a modulated signal r received via the RF channel 920. An LDPC decoder 933 decodes the demodulated signal x from the demodulator 931 and generates an estimate message u.

[125] The LDPC encoder 911 generates a parity-check matrix to meet a block length, required by the communication system, using a predetermined method. In particular, in an embodiment of the present invention, the LDPC encoder 911 can support a parity- check matrix having a variety of block lengths using an LDPC code, without storage information.

[126] FIG. 10 is a block diagram illustrating a transmitter that encodes a DVB-S2 LDPC code, according to an embodiment of the present invention.

[127] Referring to FIG. 10, the transmitter includes an LDPC code parity-check matrix extracting part 1010, a controller 1030, and an LDPC encoder 1050.The parity-check matrix extracting part 1010 extracts a parity-check matrix of an LDPC code to meet the requirement of the communication system. The parity-check matrix of an LDPC code may be extracted, via the process of Equation (4), from information regarding a sequence finally acquired through the method for designing a DVB-S2 LDPC code. It may also be extracted using a memory that implements the parity-check algorithm itself. It may be provided from the transmitter or generated in the transmitter.The controller 1030 determines a parity-check matrix according to a codeword length or information word length to meet the requirement of the communication system.The LDPC encoder 1050 performs an encoding operation according to information regarding a parity-check matrix of an LDPC code that is loaded by the controller 1030 and the parity-check matrix extracting part 1010.

[128] FIG. 11 is a block diagram illustrating a receiver using an LDPC code, according to an embodiment of the present invention.

[129] Referring to FIG. 11, the receiver receives a signal from the transmitter and restores the received signal to a user's original data.

[130] The receiver includes a demodulator 1110, a parity-check matrix determining part 1130, an LDPC code parity-check matrix extracting part 1170, a controller 1150, and an LDPC decoder 1190.

[131] The demodulator 1110 receives and demodulates a signal from the transmitter and outputs the demodulated signal to the parity-check matrix determining part 1130 and the LDPC decoder 1190. The parity-check matrix determining part 1130 determines a parity-check matrix of an LDPC code used in the communication system from the demodulated signal, under the control of the controller 1150.The controller 1150 outputs the result of the parity-check matrix determining part 1130 to the parity-check matrix extracting part 1170 and the LDPC decoder 119O.The parity-check matrix extracting part 1170 extracts a parity-check matrix of an LDPC code required by the communication system under the control of the controller 1150 and then outputs it to the LDPC decoder 1190. The parity-check matrix of an LDPC code may be extracted, via the process of Equation (4), from information regarding a sequence finally acquired through the method for designing a DVB -S2 LDPC code. It may also be extracted using a memory that implements the parity-check algorithm itself. It may be provided from the receiver or generated in the receiver.The LDPC decoder 1190 decodes the demodulated signal from the demodulator 1110 according to information regarding a parity-check matrix of an LDPC code from the parity-check matrix extracting part 1170, under the control of the controller 1150.

[132] FIG. 12 is a flow chart describing a method for performing receiving operations in a receiver using an LDPC code, according to an embodiment of the present invention.

[133] Referring to FIG. 12, a parity-check matrix used in the communication system is determined based on a received signal in step 1210. The determined information is output to the parity-check matrix extracting part 1170 in step 1220. The parity-check matrix extracting part 1170 extracts a parity-check matrix of an LDPC code required by the communication system and then outputs it to the LDPC decoder 1190 in step 1230. The LDPC decoder 1190 performs a decoding operation according to information regarding a parity-check matrix of an LDPC code from the parity-check matrix extracting part 1170 in step 1240. Industrial Applicability

[134] Although exemplary embodiments of the present invention have been described in detail hereinabove, it should be understood that many variations and modifications of the basic inventive concept herein described, which may be apparent to those skilled in the art, will still fall within the spirit and scope of the exemplary embodiments of the present invention as defined in the appended claims.