JP2009005204A - Matrix generation method, matrix generation device, and encoding / decoding device - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a matrix generation method, a matrix generation device, and an encoding and decoding device for generating a matrix for constituting an LDPC (low density parity check) code of which an encoding circuit and decoding circuit are structured simply. <P>SOLUTION: The method includes a step S101 for setting a parameter of the LDPC code, a step S102 for generating a sparse matrix based on the set parameter, a step S103 for generating a modified sparse matrix by mod2-operating a specific line in the sparse matrix, a step S104 for generating a parity check matrix by using the modified sparse matrix and unit matrix, and a step S105 for generating a modified parity check matrix by mod2-operating a specific line of the parity check matrix. <P>COPYRIGHT: (C)2009,JPO&INPIT

Description

  The present invention relates to a matrix generation method, a matrix generation apparatus, and an encoding / decoding apparatus used for encoding and decoding of an LDPC code.

  In recent years, LDPC (Low Density Parity Check) codes have attracted attention and are actively studied as error correction codes that can achieve error rate characteristics approaching the Shannon limit. The LDPC code is a linear code generated based on a very sparse parity check matrix. A sparse matrix means a matrix with very few non-zero elements in the matrix. FIG. 22 shows an example of a parity check matrix of an LDPC code. As shown in FIG. 22, since the number of 1s constituting the matrix is much smaller than the number of 0s, the LDPC code is called a low density parity check code. The parameters that determine the decoding performance of the LDPC code include a row weight that determines the number of 1s in the row direction and a column weight that determines the number of 1s in the column direction. The row weight indicates the number of bits constituting one parity check code, and the column weight indicates how many times one bit is used as an element bit of the parity check code.

  Since the number of 1s in each row is 4 and the number of 1s in each column is 3 in the parity check matrix of FIG. 22, the LDPC code composed of this parity check matrix is an LDPC code having a row weight of 4 and a column weight of 3. I know that there is. As an LDPC code encoding method, generally, a sparse parity check matrix as shown in FIG. 22 is subjected to sequence conversion using a Gaussian elimination method or the like to generate an LDPC code as shown in FIG. A method of generating a generator matrix and encoding using the generator matrix is often used. However, when this method is used, even if the original parity check matrix is a sparse matrix, the generation matrix generated by performing the sequence conversion becomes a dense matrix, which complicates the structure of the encoding circuit. There is a problem that it ends up.

As a method for solving this problem, a method of constructing a generator matrix and a parity check matrix using a structured matrix has been proposed (for example, see Patent Document 1). If the method described in Patent Document 1 is used, there is an advantage that the structure of the encoding circuit and the decoding circuit is simplified.
JP 2005-340920 A

  However, the conventional method has a problem that the decoding performance is greatly deteriorated because all the column weights of the parity bits are 1 because a part of the parity check matrix is made a unit matrix in advance.

  The present invention solves the conventional problems, and provides a matrix generation method, a matrix generation apparatus, and an encoding / decoding apparatus for generating a matrix capable of forming an LDPC code with a simple structure while alleviating a decrease in decoding performance. The purpose is to do.

  In order to solve the above-described conventional problems, a matrix generation method of the present invention is a matrix generation method for generating a matrix for encoding and decoding an LDPC code, comprising: setting parameters of an LDPC code; A step of generating a sparse matrix based on the set parameters, a step of generating a modified sparse matrix by performing a mod2 operation on a specific row of the sparse matrix, and a parity check using the modified sparse matrix and the unit matrix The method includes a step of generating a matrix and a step of generating a modified parity check matrix by performing a mod2 operation on a specific row of the parity check matrix.

  Furthermore, the matrix generation method of the present invention is a matrix generation method for generating a matrix for encoding and decoding an LDPC code, and includes a step of setting parameters of the LDPC code and a sparseness based on the set parameters. Generating a matrix; generating a modified sparse matrix by performing a mod2 operation on a specific column of the sparse matrix; generating a parity check matrix using a transposed matrix and a unit matrix of the modified sparse matrix; And generating a modified parity check matrix by performing a mod2 operation on a specific row corresponding to the specific column in the parity check matrix.

  Furthermore, the matrix generation device of the present invention is a matrix generation device that generates a matrix for encoding and decoding an LDPC code, and includes a sparse matrix generation unit that generates a sparse matrix, and a specific row of the sparse matrix. A first row addition unit that generates a modified sparse matrix by performing a mod2 operation, a first parity check matrix generation unit that generates a parity check matrix using the modified sparse matrix and a unit matrix, and a parity check matrix It includes a second row addition unit that generates a modified parity check matrix by performing a mod2 operation on a specific row, and a parameter setting unit that sets parameters in the sparse matrix generation unit.

  Furthermore, the matrix generation device of the present invention is a matrix generation device that generates a matrix for encoding and decoding an LDPC code, and a sparse matrix generation unit that generates a sparse matrix, and a specific column of the sparse matrix A column addition unit that generates a modified sparse matrix by performing a mod2 operation, a second parity check matrix generation unit that generates a parity check matrix using a transposed matrix and a unit matrix of the modified sparse matrix, and a parity check matrix A second row addition unit that generates a modified parity check matrix by performing a mod2 operation on a specific row corresponding to the specific column, and a parameter setting unit that sets a parameter in the sparse matrix generation unit. It is a feature.

  Further, the matrix generation device further includes a generation matrix generation unit that generates a generation matrix using a transposed matrix and a unit matrix of the modified sparse matrix.

  Further, the matrix generation device further includes a generation matrix generation unit that generates a generation matrix using the modified sparse matrix and the unit matrix.

  Further, in the matrix generation method, in the step of generating the modified sparse matrix, a plurality of rows are mod2 added to one row, and in the step of generating the modified parity check matrix, the plurality of rows are generated for the one row. This is characterized in that mod 2 is added to the line.

  Further, in the matrix generation method, in the step of generating the modified sparse matrix, a plurality of columns are mod2 added to one column, and in the step of generating the modified parity check matrix, a row corresponding to the one column is generated. In contrast, mod2 is added to a plurality of rows corresponding to the plurality of columns.

  Further, in the matrix generation method, in the step of generating the modified sparse matrix, one row is mod2 added to a plurality of rows, and in the step of generating the modified parity check matrix, the one row is mod2 to the plurality of rows. It is characterized by adding.

  Further, in the matrix generation method, in the step of generating the modified sparse matrix, one column is mod2 added to a plurality of columns, and in the step of generating the modified parity check matrix, the row corresponding to the one column is the plurality of columns. This is characterized in that mod2 is added to a plurality of rows corresponding to the columns.

  Furthermore, in the encoding / decoding device of the present invention, an LDPC encoding circuit that generates an LDPC codeword using a parity check matrix generated in advance by the matrix generation device according to claim 3, and a matrix according to claim 3. And an LDPC decoding circuit that decodes the LDPC codeword using a modified parity check matrix generated in advance by a generation device.

  Furthermore, in the encoding / decoding apparatus of the present invention, an LDPC encoding circuit that generates an LDPC codeword using a generation matrix generated in advance by the matrix generation apparatus according to claim 5, and a matrix generation according to claim 3 And an LDPC decoding circuit that decodes the LDPC codeword using a modified parity check matrix generated in advance by the apparatus.

  Furthermore, in the encoding / decoding device of the present invention, an LDPC encoding circuit that generates an LDPC codeword using a parity check matrix generated in advance by the matrix generation device according to claim 4, and a matrix according to claim 4 And an LDPC decoding circuit that decodes the LDPC codeword using a modified parity check matrix generated in advance by a generation device.

  Furthermore, in the encoding / decoding apparatus of the present invention, an LDPC encoding circuit that generates an LDPC codeword using a generation matrix generated in advance by the matrix generation apparatus according to claim 6, and a matrix generation according to claim 4 And an LDPC decoding circuit that decodes the LDPC codeword using a modified parity check matrix generated in advance by the apparatus.

  According to the matrix generation method, the matrix generation apparatus, and the encoding / decoding apparatus of the present invention, it is possible to provide an LDPC code that has a simple structure while alleviating a decrease in decoding performance.

  Embodiments of a matrix generation method, a matrix generation apparatus, and an encoding / decoding apparatus according to the present invention will be described below in detail with reference to the drawings.

(Embodiment 1)
First, the matrix generation method will be described. FIG. 1 is a flowchart showing a procedure of a matrix generation method according to Embodiment 1 of the present invention.

In FIG. 1, first, parameters of an LDPC code are set in a parameter setting step S101. Then, in a sparse matrix generation step S102, based on the parameters set in the parameter setting step S101, rich in 0, sparse matrix Q ₁ containing only a small amount of 1 is generated. Then, in the first row addition step S103, a predetermined row of the sparse matrix Q ₁ is are added in mod2 to another given row, it is corrected sparse matrix Q ₂ is generated. Then, the first parity check matrix generating step S104, the parity check matrix _{H 1} is generated using a modified sparse matrix _{Q 2} and the unit matrix _{I M.} Then, in the second row addition step S105, the predetermined row in the parity-check matrix H ₁ is added in mod2 to the another predetermined line, fixes the parity check matrix H ₂ are produced.

  Hereinafter, each of these steps will be described in detail. First, in the parameter setting step S101, parameters of the LDPC code to be generated are set. The parameters set here are the code word length N, the information bit length L, and the parity bit length M of the LDPC code. For example, here, N = 35, L = 20, and M = 15 are defined. As a result, a matrix for generating and decoding an LDPC codeword having a codeword length of 35 bits including 20 information bits and 15 parity bits is generated below.

Next, in a sparse matrix generation step S102, based on the parameters set in the parameter setting step S101, rich in 0, sparse matrix Q ₁ containing only a small amount of 1 is generated. In the first embodiment, the case of generating a structured matrix composed of a combination of a square matrix as sparse Q _1. First, a square matrix F of P rows and P columns is defined. For example, when a square matrix F of P rows and P columns is a matrix such as Equation 1, and P = 5, the square matrix F is a matrix such as Equation 2.

Further, the powers F ² , F ³ , F ⁴ , and F ⁵ of the square matrix F are expressed by Equations 3 to 6, respectively.

That is, since F ⁵ is a unit matrix, an arbitrary power F ⁿ of the square matrix F can be expressed by F ^{(n mod 5)} . Next, a structured sparse matrix Q ₁ having M rows and L columns is generated using the square matrix F. Now, in the parameter setting step S101, since L = 20, M = 15 is defined, sparse matrix _{Q 1} is becomes a 15 row 20 column matrix, a square matrix F is defined by a matrix of five rows and five columns and for which, three in a row direction the same matrix and the square matrix F, it is possible to generate a sparse matrix to Q ₁ 15 rows 20 columns by four arranged in the column direction. For example, when the powers of the square matrix F are arranged as shown in Equation 7, the sparse matrix Q ₁ is as shown in FIG.

Then, in the first row addition step S103, a predetermined row of the sparse matrix Q ₁ is are added in mod2 to another given row, it is corrected sparse matrix Q ₂ is generated. However, here, any number of lines may be added and added. For example, it is possible to add only the first line to the fourth line, and in addition to that, add a plurality of lines such as adding the second line to the fifth line and the third line to the sixth line. It doesn't matter. Further, a plurality of rows may be added to one row, or a single row may be added to a plurality of rows. For example, the first and second lines may be added to the third line, or the first line may be added to the second and third lines. Here, as an example, the first row of the sparse matrix Q ₁ is the 11th row, the 2nd row is the 12th row, the 3rd row is the 13th row, the 4th row is the 14th row, the 5th row is the 15th row It shall be added. Then, modified sparse matrix Q ₂ is composed as shown in FIG. Note that the modified sparse matrix Q ₂ is simply a combination of the rows of the structured sparse matrix Q ₁ , so this is also a structured matrix.

Next, the first parity check matrix generating step S104, the parity check matrix H ₁ is generated in accordance with the formula C 8.

However, I _M in Equation 8 is a unit matrix of M rows and M columns. Now, since the M = 15 is defined, _{I M} is the identity matrix of 15 rows and 15 columns. Also, modifications sparse matrix Q ₂ is therefore defined in FIG. 3, a parity check matrix H ₁ is as shown in FIG. In FIG. 4, each row shows an independent parity check condition. Such parity-check matrix H ₁ generated in the shall be used in LDPC coding. Will be described in detail later on how the LDPC encoding using parity check matrix H _1.

Next, in the second row addition step S105, the predetermined row in the parity-check matrix H ₁ is added in mod2 to the another predetermined line, fixes the parity check matrix H ₂ are produced. That is, in the first row addition step S103, 1 row line 11 of a sparse matrix to _{Q 1} 2, line 12 to the second row, the third row of the 13th line, the 14 line 4 row , because it was added to 5 row line 15, where the first row line 11 in the parity-check matrix H ₁ of FIG. 4, line 12 to line 2, the line 13 the third row, The 4th line is added to the 14th line and the 5th line is added to the 15th line. Then, a matrix as shown in FIG. 5 is generated. Since it is generally known that a row formed by adding rows in the parity check matrix with mod 2 also satisfies the parity check condition, the matrix in FIG. 5 is also a parity check matrix. Therefore, to define a matrix of Figure 5 with modified parity check matrix H _2. Such modifications parity check matrix H ₂ generated in the shall be used in the LDPC decoding. Will be described in detail later on how the LDPC decoding using the modified parity check matrix H _2.

By the above method, it is possible to produce a modified parity check matrix of H ₂ for decoding the parity-check matrix H ₁ of the for coding.

Next, a method for performing LDPC coding and LDPC decoding using the parity check matrix H ₁ and the modified parity check matrix H ₂ will be described.

First, LDPC encoding will be described. As an encoding method, first, in the parity check matrix H ₁ of FIG. 4, the part of the modified sparse matrix Q ₂ is made to correspond to the information bit part, and the part of the unit matrix I _{M is} made to correspond to the parity bit part. Then, since each row can be regarded as including one bit of a different parity bit, a parity bit can be easily obtained by adding information bits, which are element bits for each row, with mod 2 be able to.

For example, assuming that the information bit is a data sequence of 20 bits (L = 20) represented in FIG. 6A, the second column and the eighth column are associated with the first row of the parity check matrix H _{1 in} FIG. Since 1 exists in the 14th and 14th columns, the second, eighth, fourteenth and twentieth bits of information bits are added by mod 2 and the result is used as a parity bit. The parity bit in the first row can be obtained. Similarly, in each row, by adding element bits with mod 2, all parity bits are obtained, and by concatenating with information bits as shown in FIG. 6B, a code word length of 35 bits (N = 35) LDPC codeword is obtained. LDPC encoding is performed by such a method, but the parity check matrix H ₁ defined by the above method has a low-density element 1 and a more structured structure as shown in FIG. Therefore, LDPC encoding can be performed easily.

Next, LDPC decoding will be described. As a decoding method, a method of performing Sum-Product decoding on an LDPC codeword using the modified parity check matrix H ₂ can be considered. The Sum-Product decoding method is a decoding method for obtaining a posterior probability distribution corresponding to each transmission symbol from a received value using a BP (Belief Propagation) method, and includes six steps shown in FIG.

Hereinafter, each step will be described. However, here, a bipartite graph called a Tanner graph will be introduced for explanation. The Tanner graph is a graph corresponding to the parity check matrix. For example, the Tanner graph for the parity check matrix shown in FIG. 8A is expressed as shown in FIG. A white node in FIG. 8B is called a variable node 301 and a black node is called a check node 302. Each of the variable nodes 301 corresponds to each column of the parity check matrix, and each of the check nodes 302 corresponds to each row of the parity check matrix. It corresponds to. The presence of an edge at the i-th variable node and the j-th check node is equivalent to 1 being the i-th column and j-th row component of the parity check matrix. Here, a case where decoding is performed using a parity check matrix H = {H _mn } is taken as an example, and a set of variable nodes connected to the check node m is A (m), and a check node connected to the variable node n The set will be described as B (n).

First, in the initialization step S201, the log prior value ratio β _{mn is set} to β _mn : = 0 for all pairs (m, n) that satisfy H _mn = 1. The loop counter l is set to l: = 1.

Next, in the check node calculation step S202, the logarithmic external value ratio α _mn is calculated using Equation 9 for all pairs (m, n) that satisfy H _mn = 1.

Here, sign and f (x) in Equation 9 are functions represented by Equation 10 and Equation 11, respectively.

Symbol log likelihood ratio λi is defined by Equation 12 for the i-th component of the transmitted LDPC code.

Here, p (y | x) is a conditional probability distribution of the communication path.

Next, in the variable node calculation step S203, the log prior value ratio β _mn is calculated using Equation 13 for all pairs (m, n) that satisfy H _mn = 1.

  Next, in temporary estimation step S204, temporary estimated words are calculated using Equation 14 for n = 1, 2, 3,..., N−1, N.

  Next, in the parity check step S205, it is determined whether or not the temporary estimated word obtained in the temporary estimation step S204 satisfies Equation 15, and if Equation 15 is satisfied, the temporary estimated word is output as an estimated word, and the algorithm ends. .

  Next, in the increment step S206, it is determined whether or not the loop counter l satisfies Expression 16. If Expression 16 is satisfied, 1: = l + 1 is set, and the process returns to the check node calculation step S202. If Equation 16 is not satisfied, the temporary estimated word is output as the estimated word, and the algorithm is terminated.

Through the above steps, the LDPC codeword can be decoded. Here, looking at the modified parity check matrix H ₂ in FIG. 5, the information bit part is sparse from the state of the modified sparse matrix Q ₂ by performing row addition on the parity check matrix H _{1 in} FIG. returns to the state of the matrix Q _1, the parity bit portion it is seen that the value of the element bits of the parity bit portion of the lines 1 through 5 is in the state of being copied in the lower left part. That is, the column weights of the parity bit portions from the 21st column to the 25th column have changed from 1 to 2. As described above, the column weight indicates how many times one bit is used as an element bit of the parity check code. Therefore, by performing row addition, it corresponds to the position of the 21st column to the 25th column. This means that the parity bit to be changed is in the same state as when it was double-encoded. Therefore, by performing decoding using this modified parity check matrix H ₂ , the decoding performance can be improved over the conventional method in which decoding is performed using a parity check matrix in which all the column weights of the parity bit part are 1. Can do.

  The advantages of performing LDPC encoding and decoding using a matrix generated by this matrix generation method will be described. If only the column weight of the parity bit portion is improved, the rows of the parity check matrix may be simply added. However, when the parity check matrix is simply added, the added row and the row generated by the addition include, as shown in FIG. 9, a plurality of columns at the same position as element bits in the information bit portion. It becomes. In general, a state in which 1 exists at all four vertices of an arbitrarily selected rectangle as shown in FIG. 9 is called a loop of length 4, and if this pattern exists, decoding performance is significantly deteriorated. It is known to do.

Therefore, when decoding is performed using a parity check matrix in which rows are simply added, decoding performance may be inferior to when decoding is performed using a parity check matrix that has not been added. In order to overcome this problem, in the first embodiment, row addition is performed on the sparse matrix Q1 in the _first row addition step S103. That is, a row addition is performed in advance only for the sparse matrix Q ₁ corresponding to the information bit portion, and a parity check configured by a combination of the row added matrix and a unit matrix I _M corresponding to the parity bit portion by performing row sum in the same row again for matrices H _1, it has created the same state as that performed resulting in the parity bit part only row addition. In this way, it is possible to improve the column weight only the parity bit portion without generating a loop of length 4, by performing decoding using the modified parity check matrix of H ₂ the first embodiment, conventional Decoding performance can be improved as compared with the method. Further, as shown in FIG. 5, the modified parity check matrix H ₂ defined by the above method has a low-density element 1 and a more structured structure, so that the decoding circuit can be easily configured. Is possible.

As described above, in the first embodiment, the modified sparse matrix Q ₂ generated by performing row addition on the sparse matrix Q ₁ composed of the square matrix F and the unit matrix I _M are combined. Thus, a parity check matrix H ₁ that can be easily subjected to LDPC encoding can be generated. Further, by performing mod2 addition of the same row among the row addition operation performed on sparse matrices Q ₁ with respect to the parity-check matrix H _1, the modified parity check matrix H ₂ that can be easily good LDPC decoding of performance Can be generated.

  In the above, the method for generating a matrix has been described. However, a case in which this is replaced with an apparatus or a program is also conceivable. In that case, the matrix generation device has a configuration as shown in FIG. The parameter setting unit 401, sparse matrix generation unit 402, first row addition unit 403, first parity check matrix generation unit 404, and second row addition unit 405 in FIG. The same operations as in the sparse matrix generation step S102, the first row addition step S103, the first parity check matrix generation step S104, and the second row addition step S105 are performed. That is, the parameter setting unit 401 sets LDPC code parameters and sends the information to the sparse matrix generation unit 402.

Next, the sparse matrix generation unit 402 generates a sparse matrix Q ₁ that includes many 0s and includes only a small amount of ₁ , and the first row addition unit 403 generates another predetermined row of the sparse matrix Q ₁ as another predetermined row. is added to the line in mod2, fixes sparse matrix _{Q 2} is generated. The first parity check matrix generation unit 404 generates a parity check matrix H ₁ using the modified sparse matrix Q ₂ and the unit matrix I _M , and the second row addition unit 405 generates the parity check matrix H ₁ . The predetermined row is added to the other predetermined row by mod ₂ to generate a modified parity check matrix H ₂ . Accordingly, the parity check matrix H ₁ and the modified parity check matrix H ₂ can be generated by using the apparatus of FIG.

In addition, the LDPC code can be encoded and decoded by using the encoding / decoding apparatus of FIG. In FIG. 11, LDPC encoding is performed by the LDPC encoding circuit 501, and LDPC decoding is performed by the LDPC decoding circuit 502. The LDPC encoding circuit 501 and the LDPC decoding circuit 502 are configured using a parity check matrix H ₁ and a modified parity check matrix H ₂ generated in advance by the matrix generation apparatus in FIG. As an encoding and decoding method, a circuit structure similar to that described above may be configured.

That is, the coding is configured to add the element bits by mod 2 for each row of the parity check matrix H ₁ and obtain the parity bits for each row. Further, decoding is configured to perform Sum-Product decoding using the modified parity check matrix _{H 2.} By the encoding / decoding device configured as described above, efficient LDPC code encoding and decoding can be performed. Note that the parity check matrix H ₁ and the modified parity check matrix H ₂ generated by the matrix generation apparatus according to the first embodiment are both structured matrices, and thus the LDPC encoding circuit 501 and the LDPC decoding circuit. 502 can be easily configured. Therefore, the encoding / decoding device can be configured by a simple circuit.

Incidentally, as a matrix for coding, it had using the parity check matrix H _1, as a matrix for coding, may be generated generator matrix G. In this case, the above matrix generating method, using a modified sparse matrix Q ₂ transposed matrix Q ₂ ^T and the unit matrix I _L, may be added the step of generating a generator matrix G in accordance with the equation number 17.

Here, the unit matrix _IL is a matrix of L rows and L columns. Therefore, if L = 20 as in the above example, _IL is a 20 × 20 unit matrix. Since the modified sparse matrix Q ₂ is given in FIG. 3, the transposed matrix Q ₂ ^T is a matrix as shown in FIG. 12, and the generator matrix G is a matrix as shown in FIG. When the generator matrix G is used for LDPC encoding, the information bits and the generator matrix G may be multiplied according to the equation (18).

In Equation 18, c represents an LDPC codeword, and s represents an information bit.

In addition, when generating the generator matrix G, it is possible to replace it with a device or a program as in the case where the generator matrix G is not generated. In this case, as shown in FIG. 10 (b), generation of generating a generator matrix G with the matrix generation apparatus of FIG. 10 (a), a modified sparse matrix _{Q 2} transposed matrix _Q ^{2 T} and the unit matrix _{I L} A matrix generation unit 406 may be added.

Even when LDPC encoding is performed using the generator matrix G, encoding and decoding can be performed by using an encoding / decoding device. However, in this case, the LDPC encoding circuit 501 performs LDPC encoding using the generator matrix G. In LDPC decoding circuit 502, LDPC decoding using 11 similarly modified parity check matrix _{H 2} is carried out.

(Embodiment 2)
FIG. 14 is a flowchart showing the procedure of the matrix generation method according to Embodiment 2 of the present invention. The second embodiment is different from the first embodiment in that the generation method of the sparse matrix, the modified sparse matrix, and the parity check matrix is different.

In FIG. 14, first, in the parameter setting step S601, the parameters of the LDPC code are set. Then, in a sparse matrix generation step S602, based on the parameters set in the parameter setting step S601, rich in 0, it is sparse matrix Q ₃ containing only a small amount of 1 is generated. Then, in sequence summing step S603, a given column of the sparse matrix _{Q 3} are added by mod2 to another predetermined sequence, modifying sparse matrix _{Q 4} is generated. Then, in the second parity check matrix generating step S604, the parity check matrix _{H 1} is generated using a modified sparse matrix _{Q 4} transposed matrix _Q ^{4 T} and the unit matrix _{I M.} Then, in the second row addition step S605, the rows where the row corresponding to the given row in the parity-check matrix H ₁ corresponding to the another predetermined sequence are summed in mod2, fixes the parity check matrix H ₂ product Is done.

  Hereinafter, each of these steps will be described in detail. First, in the parameter setting step S601, the parameters of the LDPC code to be generated are set. The parameters set here are the code word length N, the information bit length L, and the parity bit length M of the LDPC code. For example, here, N = 35, L = 20, and M = 15 are defined. As a result, a matrix for generating and decoding an LDPC codeword having a codeword length of 35 bits including 20 information bits and 15 parity bits is generated below.

Next, in a sparse matrix generation step S602, based on the parameters set in the parameter setting step S601, rich in 0, it is sparse matrix Q ₃ containing only a small amount of 1 is generated. In the second embodiment, the case of generating a structured matrix composed of a combination of a square matrix as sparse Q _3. First, a square matrix F of P rows and P columns is defined. For example, when a square matrix F of P rows and P columns is a matrix such as Equation 1, and P = 5, the square matrix F is a matrix such as Equation 2. Further, the powers F ² , F ³ , F ⁴ , and F ⁵ of the square matrix F are expressed by Equations 3 to 6, respectively. That is, since F ⁵ is a unit matrix, an arbitrary power F ⁿ of the square matrix F can be expressed by F ^{(n mod 5)} .

Next, a structured sparse matrix Q ₃ having L rows and M columns is generated using the square matrix F. In the first embodiment, the case where a matrix of M rows and L columns is generated as a partial matrix has been described. However, in the second embodiment, a matrix of L rows and M columns is generated. Now, in the parameter setting step S601, since L = 20, M = 15 is defined, sparse matrix _{Q 3} are but a 20 row 15 column matrix, a square matrix F is defined by a matrix of five rows and five columns and for which, four square matrix F the same matrix in the row direction, it is possible to generate a sparse matrix Q ₃ of 20 rows 15 columns by arranging three in the column direction. For example, when arranging a material obtained by exponentiation of the square matrix F as in equation 19, a sparse matrix Q ₃ are composed as shown in FIG. 15.

Then, column summing step S603, are added in mod2 given column within another predetermined sequence of sparse matrices _{Q 3,} modified sparse matrix _{Q 4} is generated. However, the number of columns to be added and the number of columns to be added may be any number. For example, the first column may be simply added to the fourth column, and in addition to that, a plurality of columns may be added such that the second column is added to the fifth column and the third column is added to the sixth column. It doesn't matter. Further, a plurality of columns may be added to one column, or a single column may be added to a plurality of columns. For example, the first and second columns may be added to the third column, or the first column may be added to the second and third columns. Here, the first column to 11th column of the sparse matrix Q ₃ as an example, 12 column a second column, third column 13 column, the fourth column 14 column, the fifth column in 15 column It shall be added. Then, modified sparse matrix _{Q 4} are made as shown in FIG. 16. Note that the modified sparse matrix Q ₄ is simply a combination of the columns of the structured sparse matrix Q ₃ , so that this is also a structured matrix.

Then, the second parity check matrix generating step S604, the parity check matrix H ₁ is generated in accordance with the equation number 20.

However, I _M in Equation 20 is a unit matrix of M rows and M columns. Now, since the M = 15 is defined, _{I M} is the identity matrix of 15 rows and 15 columns. Since the modified sparse matrix Q ₄ is defined in FIG. 16, the transposed matrix Q ₄ ^T is as shown in FIG. 17, and the parity check matrix H ₁ is as shown in FIG. In FIG. 18, each row indicates an independent parity check condition. Such parity-check matrix H ₁ generated in the shall be used in LDPC coding. Note that LDPC encoding using the parity check matrix H ₁ can be performed by a method similar to the method described in the first embodiment.

Next, in the second row addition step S605, the rows where the row corresponding to the given row in the parity-check matrix H ₁ corresponding to the another predetermined sequence are summed in mod2, fixes the parity check matrix H ₂ Generated. That is, in the column summing step S603, 1 column 11 column sparse matrix _{Q 3} in FIG. 15, column 12 the second column, third column 13 column, 4 column 14 column, 5 columns because it was added eyes 15 column, wherein the first row line 11 in the parity-check matrix H ₁ of FIG. 18, line 12 of the second row, the 13th row third row, fourth row Are added to the 14th line and the 5th line to the 15th line. Then, the matrix of FIG 19 which is a result generated and modified parity check matrix H _2. Such modifications parity check matrix H ₂ generated in the shall be used in the LDPC decoding. Note that LDPC decoding using the parity check matrix H ₂ can be performed by a method similar to the method described in the first embodiment.

By the above method, it is possible to produce a modified parity check matrix of H ₂ for decoding the parity-check matrix H ₁ of the for coding. Note that the parity check matrix H ₁ and the modified parity check matrix H ₂ defined by the above method have a low-density element 1 and a more structured structure. It can be easily configured.

As described above, in the second embodiment, the transposed matrix Q ₄ ^T and the unit matrix of the modified sparse matrix Q ₄ generated by performing column addition on the sparse matrix Q ₃ composed of the square matrix F By combining with I _M , a parity check matrix H ₁ that can be easily subjected to LDPC coding can be generated. Further, by performing mod2 addition in the same row between the column summation performed on sparse matrices Q ₃ against the parity check matrix H _1, the modified parity check matrix H ₂ that can be easily good LDPC decoding of performance Can be generated.

  In the second embodiment, the method for generating a matrix has been described. However, a case in which this is replaced with an apparatus or a program is also conceivable. In that case, the matrix generation device has a configuration as shown in FIG. The parameter setting unit 701, the sparse matrix generation unit 702, the column addition unit 703, the second parity check matrix generation unit 704, and the second row addition unit 705 in FIG. The same operations as in generation step S602, column addition step S603, second parity check matrix generation step S604, and second row addition step S605 are performed.

That is, the parameter setting unit 701 sets LDPC code parameters and sends the information to the sparse matrix generation unit 702. Next, the sparse matrix generation unit 702 generates a sparse matrix Q ₃ that includes many 0s and includes only a small amount of 1, and the column addition unit 703 changes a predetermined row of the sparse matrix Q ₃ to another predetermined row. It is added in mod2, modified sparse matrix _{Q 4} is generated. Then, the second parity check matrix generating unit 704, a parity check matrix _{H 1} is generated by using the transposed matrix of modified sparse _{Q 4 Q} ^{4 T} and the unit matrix _{I M,} in the second row addition section 705, A row corresponding to the predetermined column of the parity check matrix H ₁ is added to a row corresponding to the other predetermined column by mod ₂ to generate a modified parity check matrix H ₂ . Therefore, the parity check matrix H ₁ and the modified parity check matrix H ₂ can be generated by using the apparatus of FIG.

In addition, the LDPC code can be encoded and decoded by using the encoding / decoding apparatus of FIG. In FIG. 10, LDPC encoding is performed by the LDPC encoding circuit 501, and LDPC decoding is performed by the LDPC decoding circuit 502. The LDPC encoding circuit 501 and the LDPC decoding circuit 502 are configured using a parity check matrix H ₁ and a modified parity check matrix H ₂ that are generated in advance by the matrix generation apparatus in FIG.

As a method of encoding and decoding, a method similar to the method described in the first embodiment may be used. Note that the parity check matrix H ₁ and the modified parity check matrix H ₂ generated by the matrix generation apparatus according to the second embodiment are both structured matrices, and thus the LDPC encoding circuit 501 and the LDPC decoding circuit. 502 can be easily configured. Therefore, the encoding / decoding device can be configured by a simple circuit.

Incidentally, as a matrix for coding, it had using the parity check matrix H _1, as a matrix for coding, may be generated generator matrix G. In this case, the above matrix generating method, using a modified sparse matrix Q ₄ and the unit matrix I _L, may be added the step of generating a generator matrix G in accordance with the equation of Expression 21.

Here, the unit matrix _IL is a matrix of L rows and L columns. Therefore, if L = 20 as in the above example, _IL is a 20 × 20 unit matrix. Moreover, since the modified sparse matrix Q ₄ are given in Figure 16, the generator matrix G is a matrix as shown in FIG. 21. When the generator matrix G is used for LDPC encoding, the information bits and the generator matrix G may be multiplied according to the equation (18).

In addition, when generating the generator matrix G, it is possible to replace it with a device or a program as in the case where the generator matrix G is not generated. In this case, as shown in FIG. 20 (b), the matrix generation unit of FIG. 20 (a), adding a generator matrix generating unit 706 for generating a generator matrix G using a modified sparse matrix Q ₄ and the unit matrix I _L Just do it.

Even when LDPC encoding is performed using the generator matrix G, encoding and decoding can be performed by using an encoding / decoding device. However, in this case, the LDPC encoding circuit 501 performs LDPC encoding using the generator matrix G. In LDPC decoding circuit 502, LDPC decoding using the same modified parity check matrix between _{H 2} FIG. 10 is performed.

  According to the matrix generation method, the matrix generation device, and the encoding / decoding device of the present invention, an LDPC code having a simple structure of the encoding circuit and the decoding circuit can be configured. It is.

The flowchart which showed the procedure of the matrix production | generation method in Embodiment 1 of this invention It shows an example of a sparse matrix Q ₁ in the first embodiment of the present invention It shows an example of a modified sparse matrix Q ₂ in the first embodiment of the present invention It shows an example in the parity-check matrix H ₁ of the first embodiment of the present invention It shows an example of a modified parity check matrix H ₂ in the first embodiment of the present invention The figure which shows the example of the LDPC codeword in Embodiment 1 of this invention. The flowchart which showed the decoding procedure of the Sum-Product decoding method in Embodiment 1 of this invention The figure which shows the example of the parity check matrix in Embodiment 1 of this invention, and the corresponding Tanner graph The figure which shows the example of the loop of length 4 in Embodiment 1 of this invention 1 is a block diagram showing a configuration of a matrix generation device according to Embodiment 1 of the present invention. The block diagram which shows the structure of the encoding / decoding apparatus in Embodiment 1 of this invention. It shows an example of a transposed matrix Q ₂ ^T modifications sparse matrix Q ₂ in the first embodiment of the present invention The figure which shows the example of the generator matrix G in Embodiment 1 of this invention The flowchart which showed the procedure of the matrix production | generation method in Embodiment 2 of this invention It shows an example of a sparse matrix Q ₃ in the second embodiment of the present invention It shows an example of a modified sparse matrix Q ₄ in the second embodiment of the present invention It shows an example of a transposed matrix Q ₄ ^T modifications sparse matrix Q ₄ in the second embodiment of the present invention It shows an example in the parity-check matrix H ₁ of the second embodiment of the present invention It shows an example of a modified parity check matrix H ₂ in the second embodiment of the present invention The block diagram which shows the structure of the matrix production | generation apparatus in Embodiment 2 of this invention. The figure which shows the example of the generator matrix G in Embodiment 2 of this invention The figure which shows the example of the general parity check matrix H The figure which shows the example of the general generator matrix G

Explanation of symbols

301 variable node 302 check node 401 parameter setting unit 402 sparse matrix generation unit 403 first row addition unit 404 first parity check matrix generation unit 405 second row addition unit 406 generation matrix generation unit 501 LDPC encoding circuit 502 LDPC Decoding circuit 701 Parameter setting unit 702 Sparse matrix generation unit 703 Column addition unit 704 Second parity check matrix generation unit 705 Second row addition unit 706 Generation matrix generation unit

Claims (14)

A matrix generation method for generating a matrix for encoding and decoding an LDPC code,
Setting LDPC code parameters;
Generating a sparse matrix based on the set parameters;
Performing a mod2 operation on a particular row of the sparse matrix to generate a modified sparse matrix;
Generating a parity check matrix using the modified sparse matrix and unit matrix;
Performing a mod2 operation on a specific row of the parity check matrix to generate a modified parity check matrix;
A matrix generation method including: A matrix generation method for generating a matrix for encoding and decoding an LDPC code,
Setting LDPC code parameters;
Generating a sparse matrix based on the set parameters;
Performing a mod2 operation on a specific column of the sparse matrix to generate a modified sparse matrix;
Generating a parity check matrix using a transposed matrix and a unit matrix of the modified sparse matrix;
Performing a mod2 operation on a specific row corresponding to the specific column in the parity check matrix to generate a modified parity check matrix;
A matrix generation method including: A matrix generation device that generates a matrix for encoding and decoding an LDPC code,
A sparse matrix generator for generating a sparse matrix;
A first row addition unit that generates a modified sparse matrix by performing a mod2 operation on a specific row of the sparse matrix;
A first parity check matrix generation unit that generates a parity check matrix using the modified sparse matrix and the unit matrix;
A second row addition unit for generating a modified parity check matrix by performing a mod2 operation on a specific row of the parity check matrix;
A parameter setting unit for setting parameters in the sparse matrix generation unit;
A matrix generation device including: A matrix generation device that generates a matrix for encoding and decoding an LDPC code,
A sparse matrix generator for generating a sparse matrix;
A column addition unit that generates a modified sparse matrix by performing a mod2 operation on a specific column of the sparse matrix;
A second parity check matrix generation unit that generates a parity check matrix using a transposed matrix and a unit matrix of the modified sparse matrix;
A second row adder for generating a modified parity check matrix by performing mod2 operation on a specific row corresponding to the specific column in the parity check matrix;
A parameter setting unit for setting parameters in the sparse matrix generation unit;
A matrix generation device including: The matrix generation apparatus according to claim 3, further comprising a generation matrix generation unit that generates a generation matrix using a transposed matrix and a unit matrix of the modified sparse matrix. The matrix generation device according to claim 4, further comprising a generation matrix generation unit that generates a generation matrix using the modified sparse matrix and the unit matrix. In the step of generating the modified sparse matrix, mod2 is added to a plurality of rows for one row;
2. The matrix generation method according to claim 1, wherein, in the step of generating the modified parity check matrix, mod2 is added to the plurality of rows with respect to the one row. In the step of generating the modified sparse matrix, mod2 is added to a plurality of columns for one column;
The matrix generation method according to claim 2, wherein in the step of generating the modified parity check matrix, a plurality of rows corresponding to the plurality of columns are added mod 2 to a row corresponding to the one column. In the step of generating the modified sparse matrix, mod2 is added to one row to a plurality of rows;
The matrix generation method according to claim 1, wherein in the step of generating the modified parity check matrix, the one row is added mod 2 to the plurality of rows. In the step of generating the modified sparse matrix, one column is mod2 added to a plurality of columns;
3. The matrix generation method according to claim 2, wherein in the step of generating the modified parity check matrix, mod2 is added to a plurality of rows corresponding to the plurality of columns to a row corresponding to the one column. An LDPC encoding circuit that generates an LDPC codeword using a parity check matrix generated in advance by the matrix generation device according to claim 3,
An LDPC decoding circuit that decodes the LDPC codeword using a modified parity check matrix generated in advance by the matrix generation device according to claim 3;
An encoding / decoding device having: An LDPC encoding circuit that generates an LDPC codeword using a generation matrix generated in advance by the matrix generation device according to claim 5;
An LDPC decoding circuit that decodes the LDPC codeword using a modified parity check matrix generated in advance by the matrix generation device according to claim 3;
An encoding / decoding device having: An LDPC encoding circuit that generates an LDPC codeword using a parity check matrix generated in advance by the matrix generation device according to claim 4,
An LDPC decoding circuit that decodes the LDPC codeword using a modified parity check matrix generated in advance by the matrix generation device according to claim 4,
An encoding / decoding device having: An LDPC encoding circuit that generates an LDPC codeword using a generation matrix generated in advance by the matrix generation device according to claim 6;
An LDPC decoding circuit that decodes the LDPC codeword using a modified parity check matrix generated in advance by the matrix generation device according to claim 4,
An encoding / decoding device having:

Images