KR20060013197A - Encoding method using LDPC code and computer readable recording medium for encoding - Google Patents

Abstract

The present invention relates to an encoding method using an LDPC code and a computer readable recording medium for encoding. In the encoding method using a low density parity check (LDPC) code according to the present invention, in the encoding method using an LDPC code, parity check matrix H (H is (nk) × n dimension) of the source input data. ), And when the parity check matrix H is composed of a plurality of submatrices having (nk) / m × (nk) / m dimensions, any of the submatrices constituting the parity check matrix H The row weight and the column weight are 1, and the case where all two combineable rows selected from any of the three rows of the parity check matrix ƒ has 1 at the same point is less than or equal to a preset threshold value C _max .

LDPC code, encoding, decoding, parity check, matrix

Description

Encoding method by using LDPC code and computer-readable medium for the same}

1 is a configuration of a communication system for explaining an embodiment of the present invention.

Fig. 2 shows an example of H ⁽ⁱ⁾ _d when m = 4.

Fig. 3 shows an example in which all two combinable rows selected from any of the three rows of the parity check matrix Η have 1 at the same point.

4 is a bipartite graph, which is another representation of the parity check matrix ƒ.

5 is a diagram illustrating a case where two rows of the parity check matrix Η have 1 at two points at the same time.

6 is a procedure flowchart for explaining a process of generating a parity check matrix H.

The present invention relates to an encoding method. More specifically, the present invention relates to an encoding method capable of improving the performance of a method of encoding using a low density parity check (LDPC) code, and a computer-readable recording medium for encoding.

In general, encoding means that the receiver can restore the original data in spite of an error caused by distortion or loss of the signal generated in the process of transmitting the data transmitted from the transmitter through the communication channel. In order to do so, it means a process of data processing at the transmitting side. Decoding is a process of restoring the encoded and transmitted signal to the original data at the receiving side.

Recently, a coding method using an LDPC code has emerged. The LDPC code was proposed by Gallagher in 1962 as a linear block code of low density, where most of the elements of the parity check matrix Η are zero. Since the LDPC code is so complex that it could not be implemented by the hardware technology at the time of the proposal, it was forgotten and rediscovered in 1995, and the performance of the LDPC code has been actively studied. (Reference: [1] Robert G. Gallager, "Low-Density Parity-Check Codes", The MIT Press, September 15, 1963. [2] DJC Mackay, Good error-correcting codes based on very sparse matrices, IEEE Trans Inform.Theory, IT-45, pp. 399-431 (1999)).                         

Since the parity check matrix of the LDPC code is very small, it can be decoded through iterative decoding even in a very large block size. When the block size becomes very large, the performance is close to Shannon's channel capacity limit like a turbo code.

The LDPC code can be described by the (n-k) × n parity check matrix Η. The generator matrix 하는 corresponding to the parity check matrix ƒ can be obtained from Equation 1 below.

Η · Ｇ = 0

In the encoding and decoding method using the LDPC code, the transmitting side encodes the input data by the following equation (2) by using the generation matrix 에 in the relation between the parity check matrix ƒ and equation (1).

c = u and u (where c is a codeword and u is a data frame)

As described above, in the coding method using the LDPC code, the parity check matrix ƒ is the most important factor. Since the parity check matrix ƒ has a size of about 1000 × 2000, many operations are required in the encoding and decoding process, implementation is very complicated, and requires a lot of storage space.

In general, adding more weight to the parity check matrix H may add more variables to the parity check equations, and thus may perform better in the encoding and decoding method using the LDPC code. However, if more weight is added to the parity check matrix H, 4-cycles or 6-cycles are often formed in the parity check matrix as a whole, thereby degrading the performance of the encoding and decoding method using the LDPC code. There is also a risk.

As a result, a reasonable criterion for this is that the addition of more weight to the parity check matrix H has a significant effect on the performance of the encoding and decoding method by the LDPC code depending on how much to allow 4-cycles or 6-cycles. need.

The present invention has been made to solve the problems of the prior art as described above, an object of the present invention is to encode the encoding and decoding method using the LDPC code in the method of encoding using the LDPC code To provide a way.

Another object of the present invention is to provide a computer readable recording medium having recorded thereon a data structure necessary for providing the encoding method.

It is still another object of the present invention to provide a computer readable recording medium having recorded thereon a program for generating the parity check matrix used in an encoding and decoding method using an LDPC code.

Summary of the Invention

As an aspect of the present invention, the encoding method using a low density parity check (LDPC) code according to the present invention, in the encoding method using an LDPC code, source input data H = [H _d | H _p ] (H _d (Nk) × k, H _p is a relationship of (nk) × (nk) dimension.) And a parity check matrix H having a structure of (nk) × k, where H _d is (nk R / (1-r) (where r = k / n) matrices H ⁽ⁱ⁾ _d (where i = 1, 2, ..., r / (1-r) ), And any H ⁽ⁱ⁾ _d consists of m × m submatrices having dimensions (nk) / m × (nk) / m, where any submatrices constituting H _d are The row weight and column weight of are 1, and all of the two selectable rows selected from any of the three rows of the parity check matrix Η have 1 at the same point. C _max ) or less. It is preferable that any two rows of the parity check matrix ƒ not have 1 at more than one point at the same time.

As another aspect of the present invention, the encoding method using a low density parity check (LDPC) code according to the present invention, in the encoding method using an LDPC code, parity check matrix H (H (nk) × n dimension, and when the parity check matrix H is composed of a plurality of submatrices having (nk) / m × (nk) / m dimensions, the parity check matrix H The row weight and column weight of any sub-matrix constituting are 1, and if all two combinable rows selected from any of the three rows of the parity check matrix Η have 1 at the same point, the preset threshold value (C _max) It is characterized by the following.

As another aspect, a recording medium which is part of data structure of the H _d of the parity check matrix H according to the invention can be read by a recording computer of the present invention, the parity check matrix H = [H _d | H _p] (H _d is a relationship of (nk) × k, H _p is a dimension of (nk) × (nk).), and H _d has a dimension of (nk) × (nk). r) (where r = k / n) matrices H ⁽ⁱ⁾ _d (where i = 1, 2, ..., r / (1-r)), and any H ⁽ⁱ⁾ _d Is the row weight and column weight of any sub-matrix constituting H _d , when is composed of m × m submatrices with dimensions (nk) / m × (nk) / m ) is 1, the same as the Η _d, characterized in that the parity check matrix, if having a 1 in any and all combinations both the same point row possible selected from the three rows of the Η a preset threshold value (C _max) less than or equal to Characterized in that the data structure is recorded The.

As another aspect of the present invention, in a computer-readable recording medium having a data structure of the parity check matrix H according to the present invention, the parity check matrix H has a dimension of (nk) / m × (nk) / m. In the case of a plurality of sub-matrices having a plurality of sub-matrices, the row weight and column weight of any sub-matrix constituting the parity check matrix H is 1, and all of the two possible combinations selected from any three rows of the parity check matrix Η The same data structure as the parity check matrix Η is recorded, wherein the case in which the rows have 1 at the same point is equal to or less than the preset threshold value C _max .

As another aspect of the present invention, a computer-readable recording medium having recorded thereon a program for generating a parity check matrix H used in the encoding and decoding method using the LDPC code according to the present invention is the jth of the parity check matrix H. A first procedure of temporarily adding weight to the i th row of the column; When the parity check matrix H is composed of a plurality of submatrices having dimensions (nk) / m × (nk) / m, weights of two or more of the rows and columns of the submatrix to which the i th row of the j th column belongs A second procedure for checking whether a row or column exists; A third procedure of determining whether four cycles exist for the entire parity check matrix H when there are no rows or columns having a weight of two or more among the rows and columns of the sub-matrix to which the i th row of the j th column belongs; A fourth procedure of determining whether a six-cycle is less than or equal to a predetermined threshold value C _max for the entire parity check matrix H if there are no four cycles for the parity check matrix H; A fifth procedure of finally adding weight to the i-th row if a six-cycle is less than or equal to a predetermined threshold value C _max for the entire parity check matrix H; And a program for performing the sixth procedure for generating the parity check matrix H by performing the first to fifth procedures on all columns and all rows of the parity check matrix H.

As another aspect of the present invention, in the parity check matrix H having a configuration of [H _d | H _p ] and used for the encoding and decoding method using a Low Density Parity Check (LDPC) code according to the present invention, the H _d A computer-readable recording medium having recorded thereon a program for generating a computer includes: a first procedure of temporarily adding a weight to an i th row of a j th column of the H _d ; When the parity check matrix H _d is composed of a plurality of submatrices having (nk) / m × (nk) / m dimensions, the weight is 2 out of the rows and columns of the submatrix to which the i th row of the j th column belongs. A second procedure for checking whether there are any abnormal rows or columns; A third procedure of determining whether four cycles exist for the entire parity check matrix H when there are no rows or columns having a weight of two or more among the rows and columns of the sub-matrix to which the i th row of the j th column belongs; A fourth procedure of determining whether a six-cycle is less than or equal to a predetermined threshold value C _max for the entire parity check matrix H if there are no four cycles for the parity check matrix H; A fifth procedure of finally adding weight to the i-th row if a six-cycle is less than or equal to a predetermined threshold value C _max for the entire parity check matrix H; And it characterized by storing a program for performing for every column and every row of the H _d of the first process to a fifth process for performing a fifth process of generating the H _d.

Example

Hereinafter, preferred embodiments of a coding method using a Low Density Parity Check (LDPC) code according to the present invention will be described with reference to the accompanying drawings. 1 is a view for explaining a preferred embodiment of the present invention, an example of the technical features of the present invention applied to a wireless communication system. Embodiments described below are merely examples for explaining the features of the present invention, and it is apparent to those skilled in the art that the technical features of the present invention may be applied to all fields requiring encoding.

In FIG. 1, the transmitter 10 and the receiver 30 perform communication via a radio channel 20. In the transmitter 10, the k-bit source data u output from the data source 11 becomes an n-bit codeword c by LDPC encoding in the LDPC encoding module 13. The codeword c is wirelessly modulated by the modulation module 15 and transmitted through the antenna 17 and received by the antenna 31 of the receiver 30 through the radio channel 20. The receiver 30 undergoes an inverse process of the process that occurred in the transmitter 10, which is demodulated by the demodulation module 33 and decoded by the LDPC decoding module 35 to finally obtain source data u. Can be.

It will be readily understood by those skilled in the art that the above-described data transmission / reception processes are described within the minimum range necessary to describe the features of the present invention, and there are many other processes necessary for data transmission.

In the above Equation 1, the parity check matrix Η is represented by Η = [H _d | H _p ] (H _d is (nk) × k and H _p is (nk) × (nk).) Can be expressed. K denotes the length (bit unit) of the source data input to the LDPC encoding module 13, and n denotes the length (bit unit) of the coded codeword c.

It can be seen from the relationship between Equation 1 and Η = [H _d | H _p ] that Ｇ = [I | (H _p ^-1 H _d ) ^t ] ^t . Accordingly, the LDPC encoding module 13 encodes the input data u by multiplying the input data u by Ｇ = [I | (H _p- ¹ H _d ) ^t ] ^t by Equation (2). As a result, Equation 2 may be expressed as Equation 3 below.

c = [I | (H _p ^-1 H _d ) ^t ] ^t

A feature of the present invention lies in the data structure of H _d constituting the parity check matrix H or the parity check matrix H having the structure of [H _d | H _p ], and the method of generating H or H _d .

That is, the H _d is r / (1-r) (where r = k / n) matrices H ⁽ⁱ⁾ _d having a dimension of (nk) × (nk), where i = 1, 2, ... , r / (1-r)), and any H ⁽ⁱ⁾ _d is composed of m × m submatrices having dimensions of (nk) / m × (nk) / m. _The row weight and column weight of any sub-matrix constituting _d is 1, and all two combinable rows selected from any of the three rows of the parity check matrix Η have 1 at the same point. It is characterized in that the case having a preset threshold value (C _max ) or less. It is preferable that any two rows of the parity check matrix ƒ not have 1 at more than one point at the same time.

The H _d may consist of one or more H ⁽ⁱ⁾ _d (where i = 1, 2, ..., r / (1-r)) depending on the code rate (r = k / n). The code rate r is a ratio of the length k of the source data to the length n of the encoded data, and r = 1/2, 2/3, 3/4, 4/5, and the like are generally used. The H ⁽ⁱ⁾ _d is a matrix having a dimension of (nk) × (nk), where H _d = [H ⁽¹⁾ _d | H ⁽²⁾ _d | ··· H ^{(r / (1-r))} _d ].

When each H ⁽ⁱ⁾ _d is divided into m × m submatrices having (nk) / m × (nk) / m dimensions, the row weight of any m × m submatrices constituting H _d weight and column weight are characterized by one. M is a positive integer and is the resolution factor of H _d .

FIG. 2 shows an example of H ⁽ⁱ⁾ _d when m = 4, and is composed of 16 submatrices (1, 1), (1, 2), ..., (4, 4) It can be seen. A row weight and a column weight of 1 for each sub-matrix means that there is only one 1 for any row and column of each sub-matrix and all others are zero. It is preferable to select and use the said m which shows the best performance among 4-12.

As H _p, it is preferable to use a dual diagonal matrix of (nk) × (nk) dimension. The double diagonal matrix refers to a matrix in which the main diagonal and the diagonal immediately below the main diagonal are 1 and all the others are zero.

In the above, the row and column weights constituting the H _d have been described as 1. However, when the parity check matrix H is composed of a plurality of sub matrices having (nk) / m × (nk) / m dimensions. It is also possible to set the row weight and column weight of any sub-matrix constituting the H to be one. That is, the parity check matrix H Some configurations of H _d in only the H _d to configure both the restriction of the row and column weights of the sub-matrix 1 may have, the parity check matrix with respect to the entirety of the parity check matrix H to H of It is also possible to limit the row and column weight of the sub-matrices that make up the whole.

In addition, the case where all two combinable rows selected from any of the three rows of the parity check matrix ƒ have 1 at the same point is less than or equal to a preset threshold value C _max . It is preferable that any two rows of the parity check matrix ƒ not have 1 at more than one point at the same time. The threshold value C _max is preferably determined in a range where performance degradation of encoding and decoding using the parity check matrix H does not occur even if 6-cycles exist in the parity check matrix H. More specifically, it is desirable to determine within a reasonable range by comparatively weighing the performance improvement effect due to the reduction of 6-cycles present in the parity check matrix H and the amount of calculation necessary to reduce 6-cycles. Simulation resulted in satisfactory performance in the range of about 10 to 500 of the threshold value (C _max ), and better performance in the range of 10 to 100. However, the threshold is not limited to the above range.

Fig. 3 shows an example in which all two combinable rows selected from any of the three rows of the parity check matrix ƒ have 1 at the same point. In other words, all two combinable rows selected from the three rows i, j, and k, that is, the i-th row and the j-th row, the j-th row and the k-th row, and the k-th row and the i-th row are at the same point. As shown in FIG. 3, when the six points drawn in the circle are connected to each other, a cycle is formed, which is called a six-cycle. 4 is a bipartite graph, which is another method of expressing the parity check matrix ƒ, and means a parity check matrix of 6 rows and 9 columns. In Fig. 4, the part indicated by the thick line is the part forming the 6-cycle. The case in which all two combinable rows selected from any one of the three parity check matrices have 1 at the same point is less than or equal to a preset threshold value C _max means that 6-cycles are performed for the entire parity check matrix Η. Means that the portion forming is smaller than or equal to the threshold value C _max .

5 is a diagram illustrating a case where two rows of the parity check matrix ƒ have 1 at two points at the same time. That is, in FIG. 5, both the points of the circle of the i-th row and the points of the circle of the j-th row are both 1, and the case of FIG. 5 should not be present in the parity check matrix Η. The method is good performance. As shown in Fig. 5, the case where two rows of the parity check matrix ƒ has 1 at two points at the same time is called a 4-cycle. The fact that any two rows of the parity check matrix ƒ does not have 1 at two or more points at the same time means that no 4-cycle is formed for the entire parity check matrix ƒ.

In the encoding method using the LDPC code, it is achieved by repetitive exchange of probabilistic information determined by the channel situation between rows constituting the parity check matrix Η. Each par row in the parity check matrix Η where the two conditions are not satisfied. Probabilistic information of is passed on to other rows and does not perform well because it does not go through enough iterations.

6 is a flowchart illustrating a process of generating a parity check matrix H having the characteristics described above. The method described below is just an example, and the parity check matrix H having the above-described characteristics may be obtained by various methods.

In Fig. 6, i is the index of any row of the parity check matrix H, j is the index of any column, and Cw means the current weight number of any column j. . First, weights are added to the first column (j = 1) without weights (Cw = 0) [S20]. In this case, adding weight means that the element corresponding to any row of any column is 1.

A weight is tentatively added to any i-th candidate row of the first column [S21]. Provisionally adding a weight means that the weight addition for that row is not final but can be changed by a later procedure. Next, when the parity check matrix H is composed of a plurality of submatrices having (nk) / m × (nk) / m dimensions, the weight among the rows and columns of the submatrix to which the i th row of the j th column belongs. Checks whether there are two or more rows or columns [S22]. If there is a row or column having a weight of 2 or more among the rows and columns of the sub-matrix to which the i-th row of the j-th column belongs, the weight is added to another row without adding a weight to the i-th row [S21]. The procedure is repeated, and if there is no row or column of weight 2 or more among the rows and columns of the sub-matrix to which the i-th row of the j-th column belongs, it is determined whether a 4-cycle exists for the entire parity check matrix H [ S23].

It is determined whether a 4-cycle exists for the entire parity check matrix H [S23]. If a 4-cycle exists, a weight is added to another row without adding a weight to the i-th row [S22]. The process proceeds again, and if there is no 4-cycle, it is determined whether 6-cycles exist for the entire parity check matrix H [S24].

As a result of determining whether 6-cycles exist for the entire parity check matrix H, a weight is finally added to the i-th row if no 6-cycles exist. If there are 6-cycles, it is determined whether the number of 6-cycles of the entire parity check matrix H is equal to or less than a predetermined threshold value C _max [S25], and if it is less than or equals, weights are finally added to the i-th row. If not, the weight is added to the other row without adding the weight to the i-th row [S22], and then the procedure is repeated again.

When the weight is finally added to the i-th row [S26], the current weight number Cw of the j-th column is increased by 1 [S27], and the current weight number of the j-th column is allowable for the j-th column (Cjmax). It is determined whether or not equal to [S28]. If the current weight of the j-th column is equal to the maximum allowable number of weights (Cjmax) in the j-th column, the weight addition to the j-th column is terminated, and it is determined whether j is equal to the codeword length [S29]. If the current weight of the j-th column is not equal to the maximum allowable number of weights (Cjmax) of the j-th column, the flow returns to step S22 to provisionally add weights to other rows of the j-th column and continue the subsequent procedure.

If j is equal to the codeword length, since the weight addition is completed for the entire parity check matrix H, the parity check matrix H can be finally generated according to the weight addition result up to that point [S31]. If j is not equal to the codeword length, it means that there is a column that has not been added yet. Therefore, 1 is added to j [S30] and the weight is added to the next column in the same manner as described above from step S22.

As described above, the entire parity check matrix H may be generated by the same procedure as described above, but in the parity check matrix H having the structure of [H _d | H _p ], H _{d is added} to the procedure as described above. generated, and it is also possible to use a standardized form of the H _p. As H _p, it is preferable to use a dual diagonal matrix of (nk) × (nk) dimension.

In FIG. 1, the following equation (4) is used for the receiver 30 to receive and decode the data encoded in the manner described above.

Η · c = 0

That is, if the coded data c is multiplied by the parity check matrix Η and becomes 0, it means that there is no transmission error. If not, it means that there is a transmission error. Can be.

Technical concept is H or the data structures, and program for generating the H or H _d having the characteristics as H _d recorded, CD-ROM, a floppy disk, computer memory, or a mobile communication terminal having the features of the present invention having It should be understood that the recording medium may also be read by a CPU (Control Process Unit), such as a memory of the same.

It is apparent to those skilled in the art that the present invention can be embodied in other specific forms without departing from the spirit and essential features of the present invention. Accordingly, the above detailed description should not be construed as limiting in all aspects and should be considered as illustrative. The scope of the invention should be determined by reasonable interpretation of the appended claims, and all changes within the equivalent scope of the invention are included in the scope of the invention.

According to the encoding method using the LDPC code and the computer-readable recording medium for encoding according to the present invention, the performance of the encoding and decoding method using the LDPC code can be improved.

Claims (18)

In the encoding method using a low density parity check (LDPC) code, Parity check matrix (parity) having the structure of H = [H _d | H _p ] (H _d is (nk) × k, H _p is (nk) × (nk) dimension).) check matrix) is encoded using H, Where H _d is an r / (1-r) (where r = k / n) matrix H ⁽ⁱ⁾ _d having a dimension of (nk) × (nk), where i = 1, 2, ..., r / (1-r)) is composed of, any of the H ⁽ⁱ⁾ _d is (nk) / m × (nk ) / a m when configured as a dimension of m × m sub-matrix with, the H _d The row weight and column weight of any sub-matrix that make up is 1, And a case in which all two combinable rows selected from any one of the three parity check matrices have 1 at the same point is less than or equal to a preset threshold value C _max . The method of claim 1, And any two rows of the parity check matrix ƒ do not have 1 at two or more points at the same time. The method of claim 1, The threshold value (C _max ) is selected from within the range of 10 to 100 coding method using an LDPC code. The method according to any one of claims 1 to 3, The H _p is an encoding method using an LDPC code, characterized in that the dual diagonal matrix. In the coding method using the LDPC code, The source input data is encoded using a parity check matrix H (H is (n-k) × n dimension), The row weight of any sub-matrix constituting the parity check matrix H, when the parity check matrix H is composed of a plurality of submatrices having (nk) / m × (nk) / m dimensions, and The column weight is 1, And a case in which all two combinable rows selected from any one of the three parity check matrices have 1 at the same point is less than or equal to a preset threshold value C _max . The method of claim 5, And any two rows of the parity check matrix ƒ do not have 1 at two or more points at the same time. The method of claim 5, The threshold value (C _max ) is selected from within the range of 10 to 100 coding method using an LDPC code. In the parity check matrix H used to encode source input data, The parity check matrix H = [H _d | H _p ] (H _d is a relationship of (nk) × k, H _p is (nk) × (nk) dimension).), Wherein H _d is r / (1-r) (where r = k / n) matrices H ⁽ⁱ⁾ _d (where i = 1, 2, ..., r / (1) with dimensions (nk) × (nk) -r)), where any H ⁽ⁱ⁾ _d consists of m × m submatrices with dimensions (nk) / m × (nk) / m, The row weight and column weight of any sub-matrix constituting the H _d is 1, The same data structure as Η _d is recorded, wherein the case where all two combinable rows selected from any of the three rows of the parity check matrix Η have 1 at the same point is less than or equal to a preset threshold value C _max . Computer-readable recording media. The method of claim 8, The parity check matrix of any Η any two lines (rows) is also a recording medium which can be read in the same data structure as the Η _d, characterized in that that do not have a 1 at the same time to more than one point of the recording computer. The method of claim 8, And the threshold (C _max ) is selected within the range of 10 to 100. A computer readable recording medium having a data structure identical to that of Η _d . In the parity check matrix H (the parity check matrix H is (n-k) × n dimension.) Used for encoding the source input data, When the parity check matrix H is composed of a plurality of submatrices having (n-k) / m × (n-k) / m dimensions, The row weight and column weight of any sub-matrix constituting the parity check matrix H is 1, The parity check matrix, a prescribed threshold value (C _max) same data structure as a parity check matrix Η to that in FEATURE or less is set if having one to any two such points of rows available all of the selected combinations of the three rows of the Η the Recorded computer-readable recording media. The method of claim 11, And any two rows of the parity check matrix ƒ have no one at the same time at two or more points. The method of claim 12, And said threshold value (C _max ) is selected within the range of 10 to 100. A computer-readable recording medium having the same data structure as the parity check matrix Η recorded thereon. A computer-readable recording medium recording a program for generating a parity check matrix H (the parity check matrix H is (nk) × n dimension.) Used in a coding and decoding method using a low density parity check (LDPC) code. To A first procedure of temporarily adding a weight to an i th row of a j th column of the parity check matrix H; When the parity check matrix H is composed of a plurality of submatrices having (nk) / m × (nk) / m dimensions, the weight of two or more of the rows and columns of the submatrix to which the i th row of the j th column belongs A second procedure for checking whether a row or column exists; A third procedure of determining whether four cycles exist for the entire parity check matrix H when there are no rows or columns having a weight of two or more among the rows and columns of the sub-matrix to which the i th row of the j th column belongs; A fourth procedure of determining whether a six-cycle is less than or equal to a predetermined threshold value C _max for the entire parity check matrix H if there are no four cycles for the parity check matrix H; A fifth procedure of finally adding weight to the i-th row if a six-cycle is less than or equal to a predetermined threshold value C _max for the entire parity check matrix H; And And a program for performing a sixth procedure for generating the parity check matrix H by performing the first to fifth procedures on all columns and all rows of the parity check matrix H. The method of claim 14, The threshold value (C _max ) is selected within the range of 10 to 100. A computer-readable recording medium having recorded thereon a program. It is used for encoding and decoding method using Low Density Parity Check (LDPC) code, and parity check matrix H having the configuration of [H _d | H _p ] (where parity check matrix H is (nk) × n dimension). A computer-readable recording medium having recorded thereon a program for generating H _d , A first procedure of temporarily adding a weight to an i th row of a j th column of H _d ; When the parity check matrix H _d is composed of a plurality of submatrices having (nk) / m × (nk) / m dimensions, the weight is 2 out of the rows and columns of the submatrix to which the i th row of the j th column belongs. A second procedure for checking whether there are any abnormal rows or columns; A third procedure of determining whether four cycles exist for the entire parity check matrix H when there are no rows or columns having a weight of two or more among the rows and columns of the sub-matrix to which the i th row of the j th column belongs; A fourth procedure of determining whether a six-cycle is less than or equal to a predetermined threshold value C _max for the entire parity check matrix H if there are no four cycles for the parity check matrix H; A fifth procedure of finally adding weight to the i-th row if a six-cycle is less than or equal to a predetermined threshold value C _max for the entire parity check matrix H; And The first process to the recording medium in the fifth process can be read by a computer storing a program for performing for every column and every row of the H _d performs the sixth procedure of generating the H _d. The method of claim 16, The threshold value (C _max ) is selected within the range of 10 to 100. A computer-readable recording medium having recorded thereon a program. The method of claim 16, The _p H is a computer-readable recording medium storing a program for generating a _d H, characterized in that a dual diagonal matrix (dual diagonal matrix).

Images