Apparatus and method for coding/decoding block low density parity check code in a mobile communication system

The present invention relates to a mobile communication system, and more particularly to an apparatus and method for encoding / decoding a block low density parity check code.

Since the development of the cellular mobile telecommunications system in the United States in the late 1970s, AMPS (Advanced Mobile Phone Service) is called the analog 1st Generation mobile communication system in South Korea. ) Started to provide voice communication services. Since the mid-1990s, South Korea has commercialized a code division multiple access (hereinafter referred to as "CDMA") system as a two-generation mobile communication system to provide voice and low-speed data services.

IMT (International Mobile Telecommunication) -2000, a 3G mobile communication system that started with the goals of improved wireless multimedia services, global roaming, and high-speed data services since the end of the 1990s, is now partially commercialized. The service is provided. In particular, 3G mobile communication systems have been developed to transmit faster data as the amount of data serviced by mobile communication systems increases rapidly. That is, the 3G mobile communication system has been developed in the form of a packet service communication system. The packet service communication system is designed to be suitable for large-capacity data transmission as a system for transmitting burst packet data to a plurality of mobile stations. As a result, packet service communication systems are evolving for high speed packet services.

On the other hand, it is currently developing from a 3G mobile communication system to a 4th generation mobile communication system. The 4th generation mobile communication system is not limited to simple wireless communication services like the previous generation mobile communication systems, but is standardized with the goal of efficient interlocking and integrated services between wired communication networks and wireless communication networks. Therefore, there is a demand for technological development capable of transmitting a large amount of data close to the capacity of a wired communication network in a wireless communication network.

In this way, there is a demand for a high-speed, large-capacity communication system that can process and transmit not only voice service data but also various information such as video and wireless data, and as a result, system transmission efficiency is achieved by using an appropriate channel coding method. Will work as an essential element for improving system performance. However, due to the characteristics of the mobile communication system, when transmitting data, an error is inevitably generated due to noise, interference, fading, etc. depending on the channel condition. Therefore, the occurrence of an error results in the loss of information data.

In order to reduce the information data loss due to the occurrence of such an error, the reliability of the mobile communication system can be improved by using various error control techniques depending on the characteristics of the channel. Among the error control technologies, the technology that uses an error-correcting code is the most universal. Here, a turbo code, which is a typical code of an error correction code, and a low density parity check (hereinafter referred to as LDPC) code will be described.

<u style="single">Turbo code </u> The turbo code is an error correction code that is used in both the synchronous method and the asynchronous method, which have recently attracted attention in the third generation mobile communication system. Compared to the convolutional code that has been used mainly for forward error correction, this turbo code is known to have excellent performance gain during high-speed data transmission. Further, the turbo code has an advantage that an error due to noise generated in a transmission channel is effectively corrected to improve the reliability of data transmission.

<u style="single">LDPC code </u> The LDPC code can be decoded in a factor graph using an iterative decoding algorithm based on the sum-product algorithm. Since the LDPC code decoder uses an iterative decoding algorithm based on the sum product algorithm, it not only has lower complexity than the turbo code decoder, but can also be realized by a parallel processing decoder. It's easy. When the LDPC code is expressed by the factor graph, the cycle exists on the factor graph of the LDPC code. Iterative decoding on the factor graph of the LDPC code in which this cycle exists is a well-known fact that it is sub-optimal. It is also an experimentally proven fact that LDPC codes have excellent performance through iterative decoding. However, when there are many short-length cycles in the factor graph of the LDPC code, the performance deterioration of the LDPC code occurs. Therefore, research for designing LDPC codes so that short-length cycles do not exist on the factor graph of LDPC codes is being continuously carried out.

The LDPC code coding process has generally been developed in the form of using a parity check matrix having a low weight density due to the characteristics of a generating matrix having a high weight density. Here, the weight indicates the number of elements having a non-zero value among the elements constituting the generator matrix and the parity check matrix. In particular, if the form of the partial matrix corresponding to parity in the parity check matrix has a regular form, more efficient coding is possible.

On the other hand, since the LDPC code contains various codes having non-zero values, we will develop an efficient coding algorithm and an efficient decoding algorithm for the LDPC code having various forms in the practical use problem of the LDPC code. Is very important. Further, since the parity check matrix of the LDPC code determines the performance of the LDPC code, it is very important to design the parity check matrix having excellent performance. That is, if an efficient parity check matrix having excellent performance and an efficient coding algorithm and decoding algorithm are not considered at the same time, a high-performance LDPC code can be generated.

In addition, the LDPC code is defined by a parity check matrix in which most of the elements have a value of 0 and a very small number of elements other than the elements having a value of 0 have a value of 1. For example, the (N, j, k) LDPC code is a linear block code with a block length of N, with an element having j 1 values for each column and each row. Each element has k elements with a value of 1 and all but the elements with a value of 1 are defined by a sparse-structured parity check matrix composed of all elements with a value of 0. To.

As described above, an LDPC code in which the weight value of each column in the parity check matrix is constant at j and the weight value of each row in the parity check matrix is constant at k is referred to as a uniform LDPC code. On the other hand, an LDPC code in which the weight value of each column and the weight value of each row in the parity check matrix are not constant is called a "non-uniform LDPC code". In general, it is known that the performance of a non-uniform LDPC code is further superior to the performance of a uniform LDPC code. However, in the case of a non-uniform LDPC code, the weight value of each column in the parity check matrix and the weight value of each row are not constant, that is, because they are non-uniform, the number of weights of each column in the parity check matrix and each row. If the number of weights is not adjusted appropriately, excellent performance cannot be guaranteed.

Here, with reference to FIG. 1, a parity check matrix of (N, j, k) LDPC code and (8,2,4) LDPC code as an example will be described.

FIG. 1 is a diagram showing a parity check matrix of a general (8,2,4) LDPC code. Referring to FIG. 1, the (8,2,4) LDPC code parity check matrix H is composed of 8 columns and 4 rows, and the number of weights in each column is uniform as 2, and each row. The number of weights is uniform as 4. In this way, the number of weights in each column and the number of weights in each row in the parity check matrix are uniform. Therefore, the (8,2,4) LDPC code shown in FIG. 1 is a uniform LDPC code.

FIG. 1 describes the (8,2,4) LDPC code parity check matrix. Next, the factor graph of the (8,2,4) LDPC code shown in FIG. 1 will be described with reference to FIG.

FIG. 2 is a diagram showing a factor graph of the (8,2,4) LDPC code of FIG. Referring to FIG. 2, the factor graph of (8,2,4) LDPC code shows 8 variable nodes, that is, x.₁211 and x₂213 and x₃215, x₄217 and x₅219 and x₆221 and x₇223 and x₈It consists of 225 and four inspection nodes 227,229,231,233. (8,2,4) Variable node x when there is a weight, that is, an element with a value of 1, at the intersection of the i-th row and the j-th column of the parity check matrix of the LDPC code._jA branch is formed between and the i-th check node.

As described above, since the parity check matrix of the LDPC code has a very small number of weights, even a block code having a relatively long length can be decoded through iterative decoding, and the block length of the block code is continued. When increased, it shows the performance of a form close to Shannon's channel capacitance limit, such as a turbo code. The iterative decoding process of the LDPC code using the flow transmission method has a performance that is almost close to the iterative decoding process of the turbo code. On the other hand, the conditions for generating a high-performance LDPC code are as follows.

<u style="single">(1) The cycle on the factor graph of the LDPC code should be considered.</u> The cycle indicates the loop formed by the edges connecting the variable node and the inspection node in the factor graph of the LDPC code, and the length of the cycle is defined by the number of edges forming the loop. A long cycle length means that there are a large number of edges connecting the variable nodes and inspection nodes that make up the loop in the factor graph of the LDPC code. On the contrary, the short cycle length means that the number of edges connecting the variable nodes and the inspection nodes that make up the loop in the factor graph of the LDPC code is small.

The longer the cycle on the factor graph of the LDPC code is generated, the more the performance of the LDPC code increases. The reason is as follows. When generating long cycles on the factor graph of LDPC code, performance degradation such as error floor that occurs when there are many short cycles on the factor graph of LDPC code does not occur. Is.

<u style="single">(2) Efficient coding of LDPC codes should be considered.</u> Due to the characteristics of the LDPC code, the LDPC code has a higher coding complexity than the convolutional code and the turbo code, and real-time coding is not easy. Repeat Accumulate (RA) codes and the like have been proposed to reduce the coding complexity of LDPC codes. Iterative cumulative codes also have limitations in reducing the coding complexity of LDPC codes. Therefore, efficient coding of LDPC codes must be considered.

<u style="single">(3) The order distribution on the factor graph of LDPC code should be considered.</u> In general, non-uniform LDPC codes perform better than uniform LDPC codes. The reason is that the factor graph of the non-uniform LDPC code has various orders. Here, the degree indicates the number of edges connected to each node, that is, the variable node and the inspection node on the factor graph of the LDPC code. Further, the "order distribution" on the factor graph of the LDPC code indicates how many nodes having a specific order exist in the whole node. It has already been proved that the performance of LDPC codes having a specific order distribution is excellent.

FIG. 3 is a diagram schematically showing a parity check matrix of a general block LDPC code. Prior to the explanation of FIG. 3, the block LDPC code is a new LDPC code that considers not only efficient coding but also efficient storage of a parity check matrix and performance improvement. This block LDPC code is a concept LDPC code that generalizes and extends the structure of a uniform LDPC code. Referring to FIG. 3, the parity check matrix of the block LDPC code has a form in which the entire parity check matrix is divided into a plurality of subblocks, and each of the subblocks is associated with a permutation matrix). As shown in Figure 3, P is N_sxN_sIndicates a permutation matrix with size, and the superscript a of this permutation matrix P_ijIs 0 a_ij N_s-1 or a_ijHas = . In FIG. 3, P indicates the number of rows of the partial block, and q indicates the number of columns of the partial block. I means that the corresponding permutation matrix is located in the i-th row of the parity check matrix subblock, and j means that the corresponding permutation matrix is in the j-th column of the parity check matrix subblock. Means to be located. That is,

<maths num="1"><img id="000002" he="12" wi="15" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Is a permutation matrix located in a subblock that intersects the i-th row and the j-th column.

Here, the above permutation matrix will be described with reference to FIG. As shown in Figure 4, the circulation matrix P is N_sxN_sN forming the cyclic matrix P as a square matrix with size_sEach row has a weight of 1, and N constitutes the circulant matrix P._sIndicates a matrix in which the weights of each row are also 1.

On the other hand, in Figure 3, the superscript a of the permutation matrix_ijWhen = 0, that is, the permutation matrix P⁰Is the identity matrix

<maths num="2"><img id="000003" he="12" wi="85" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

And the superscript a of the permutation matrix P_ijIf = , that is, the permutation matrix P^∞Indicates a zero matrix.

In Fig. 3, the total parity check matrix of the block LDPC code has N total columns._sxq (p q) and the total number of rows is N_sSince it is xp, when the total parity check matrix of the block LDPC code has the maximum rank, the coding rate is as shown in &lt;Equation 1&gt; below regardless of the size of the partial block. is there.

<maths num="3"><img id="000004" he="19" wi="132" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

A for all i, j_ijWhen , it means that the permutation matrix corresponding to each of the subblocks is not a zero matrix, and the weight of each row of the permutation matrix corresponding to each of the subblocks is p, and the weight of each column is q. It becomes a uniform LDPC code. Here, the permutation matrix corresponding to the submatrix is referred to as a "submatrix".

Moreover, since there are p-1 dependent rows in the total parity check matrix, the code rate has a value higher than the code rate calculated by &lt;Equation 1&gt;. This block LDPC code is the remaining N when the weight position of the first row of each submatrix that constitutes the total parity check matrix is determined._s-The weight position of one row is determined. Therefore, the size of memory required to store the information of the total parity check matrix is 1 / N compared to the case of selecting weights irregularly._sIs reduced to.

FIG. 5 is a diagram showing a parity check matrix of a general uniform block LDPC code.

As shown in FIG. 5, the parity check matrix is a uniform block LDPC code, that is, a (s, r) array (array) code parity check matrix. The (s, r) array code is a typical uniform block LDPC code, and this (s, r) array code is N in FIG._sCorresponds to the block LDPC code where = s, q = s, and p = r. Here, s is an odd prime number, and r always satisfies the condition r s.

(s, r) The parity check matrix of the array code is s.²It has columns and rxs rows, and ranks rx (s-1). Here, the reason why the rank of the parity check matrix of the (s, r) array code is r (s-1) is that the r submatrixes of the parity check matrix of the (s, r) array code in the row direction are , This is because adding all the p rows in this submatrix produces rows with all elements having a value of 1. That is, since r rows in which all elements have a value of 1 are generated, it can be seen that there are r rows that are dependent on r. Therefore, the code rate R of the (s, r) array code_arrayIs shown as &lt;Equation 2&gt; below.

<maths num="4"><img id="000005" he="19" wi="146" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

As explained above, the (s, r) array code can be seen from its algebraic properties that no cycle of length 4 exists on the factor graph and can also reduce memory capacity. it can.

However, since the (s, r) array code is a uniform LDPC block code, performance deterioration occurs as compared with the non-uniform LDPC code. Further, in the case of the block LDPC code, since the randomness of the block LDPC code itself is low, excellent performance cannot be guaranteed. In other words, the (s, r) array code takes into account efficient coding, but the complexity is still high in coding, and there is no cycle of length 4, but there is a cycle of length 6. To do. Since the order distribution is not taken into consideration, performance deterioration occurs.

FIG. 6 is a diagram showing a parity check matrix of a general non-uniform block LDPC code. Prior to the description of FIG. 6, the non-uniform block LDPC code is a block LDPC code in which the array code is modified in consideration of efficient coding, as described in FIG. In FIG. 6, in the parity check matrix of the non-uniform block LDPC code, k and r are integers satisfying the condition of k and r s (where s is a prime number), I indicates an identity matrix of sxs size, and 0 is sxs. Shows a zero size matrix. As shown in FIG. 6, the parity check matrix of the non-uniform block LDPC code is N in FIG._sIt corresponds to the parity check matrix of the block LDPC code of p = r with = s and q = k.

On the other hand, in order to efficiently encode the LDPC code, as shown in Fig. 6, the submatrix corresponding to the parity in the total parity check matrix is composed of the complete lower triangular matrix so that it can be encoded within the linear time. did. Since the structure of the total parity check matrix, that is, the submatrix corresponding to the information word and the submatrix structure corresponding to the parity will be described below, detailed description thereof will be omitted here. When the submatrix corresponding to parity is composed of a complete lower triangular matrix in this way, the parity check matrix always has the maximum rank due to the structural characteristics of the parity check matrix. Therefore, the block length of the modified array code, that is, the non-uniform LDPC code is ks, and the coding rate R is shown as shown in &lt;Equation 3&gt; below.

<maths num="5"><img id="000006" he="19" wi="132" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

However, as shown in FIG. 6, a non-uniform LDPC code having a parity check matrix in which the submatrix corresponding to parity has a complete lower triangular matrix form is more efficient in terms of coding than an array code, but LDPC. We did not consider the order distribution on the factor graph to consider when generating the code, nor did we consider the elimination for short cycles. Therefore, it has a lower error correction capability than a non-uniform LDPC code having random characteristics. Therefore, there is an increasing need for non-uniform LDPC codes that maximize error correction capability.

<p num="0043"> Therefore, an object of the present invention is to provide an apparatus and a method for encoding / decoding an LDPC code that maximizes an error correction capability in a mobile communication system.</p><p num="0044"> Another object of the present invention is to provide an apparatus and a method for encoding / decoding an LDPC code having a maximum minimum cycle length in a mobile communication system.</p><p num="0045"> Another object of the present invention is to provide an apparatus and a method for encoding / decoding an LDPC code whose coding complexity is minimized in a mobile communication system.</p>

<p num="0046"> In a method for achieving the above object, the present invention presents the block low density parity check (Low Density Parity). Check: LDPC) The code parity check matrix is composed of an information part corresponding to an information word, a first parity part corresponding to parity, and a second parity part, and the parity check matrix for improving error correction performance. The step of determining the size of the parity check matrix based on the coding rate applied when the information word is encoded by the block LDPC code and the code word length, and the determination. A step of dividing a parity check matrix of a determined size into a predetermined number of blocks, a block corresponding to the information portion, a block corresponding to the first parity portion, and the second parity. In the stage of classifying into blocks corresponding to the parts, and in the blocks classified into the first parity part, a forward matrix is arranged in a predetermined block in the blocks classified into the first parity part, and in the blocks classified into the second parity part. The minimum cycle length of the factor graph of the block LDPC code is maximized in the stage of arranging the ordinal matrix in the complete lower triangular form in the predetermined block and the block classified in the information part, and the weight value is not. It is characterized by having a step of arranging the ordinal matrix so as to be uniform.</p><p num="0047"> Further, the present invention is a method for decoding a block low density parity check (LDPC) code, which is composed of an information portion corresponding to an information word, a first parity portion corresponding to parity, and a second parity portion. A step of generating the parity check matrix and determining a deinterleaving method and an interleaving method corresponding to the parity check matrix, a step of detecting a probability value of a received signal, and a step of previously decoding from the probability value of the received signal. A step of subtracting the generated signal to generate a first signal, a step of inputting the first signal and deinterleaving by the deinterleaving method, and a step of inputting the deinterleaved signal. A step of detecting the probability value, a step of subtracting the deinterleaved signal with the probability value of the deinterleaved signal to generate a second signal, and a step of generating the second signal, and the interlacing of the second signal. It is characterized by including a step of interleaving by a leaving method and repeatedly decoding the interleaved signal.</p><p num="0048"> The present invention is a block low density parity check (LDPC) code coding method, in which an information word, an information portion corresponding to the information word, and a first parity portion corresponding to parity are generated in advance. And the step of multiplying the first submatrix of the parity check matrix composed of the second parity part to generate the first signal, and multiplying the information word with the second submatrix of the parity check matrix. Then, the step of generating the second signal, the first signal, and the matrix product of the third submatrix of the parity check matrix and the inverse matrix of the fourth submatrix are multiplied to obtain the third signal. The generation step, the step of adding the second signal and the third signal to generate the fourth signal, and the step of multiplying the fourth signal by the fifth submatrix of the parity check matrix to generate the fourth signal. A step of generating the signal 5, a step of adding the second signal and the fifth signal to generate a sixth signal, and a third submatrix of the sixth signal and the parity check matrix. And the step of multiplying the matrix product of the inverse matrix of the fourth submatrix to generate the seventh signal, the information term, the fourth signal with the first parity, and the seventh signal with the first parity. It is characterized by having a parity of 2 and having a stage of multiplexing and outputting so as to correspond to the block LDPC code format.</p><p num="0049"> In the present invention, the parity check matrix is arranged in the form of a row and column matrix of a plurality of information subblocks and a plurality of parity subblocks, and the parity check matrix is an information portion composed of a matrix of the information subblocks and the above. It is divided into a parity part composed of a matrix of parity subblocks, each of the information subblocks is composed of a matrix showing a plurality of information bits, and each of the parity subblocks is composed of a matrix showing a plurality of parity bits. In the parity check matrix, the information subblock and the parity subblock existing in a plurality of rows are divided into a first information matrix, a first parity matrix, and a second parity matrix, respectively, and the plurality of rows are excluded. The information subblock and the parity subblock existing in the remaining rows are divided into a second information matrix, a third parity matrix, and a fourth parity matrix, respectively, and the first and second information matrices and the first and second The third parity matrix and the second and fourth parity matrices are arranged in the same column, respectively, and are a method of generating the parity check matrix for improving error correction performance. And the step of setting the sum of the product of the inverse matrix of the second parity matrix, the first parity matrix, and the third parity matrix to be a unit matrix, and the first parity matrix and the third parity matrix. The translocation vector of the first parity vector corresponding to the parity matrix is the sum of the product of the fourth parity matrix, the inverse matrix of the second parity matrix, the first information matrix, and the second information matrix. A step of determining the value obtained by multiplying the first information matrix and the information vector corresponding to the second information matrix, and a second parity corresponding to the second parity matrix and the fourth parity matrix. The transmutation vector of the vector is a value obtained by multiplying the inverse matrix of the second parity matrix by the transmutation vector of the first information matrix and the information vector, and the translocation vector of the first parity matrix and the first parity vector. It is characterized by having a step of determining the value obtained by multiplying the value obtained by multiplying the value obtained by multiplying the value of.</p><p num="0050"> Further, in the present invention, the parity check matrix of the block low density parity check (LDPC) code is arranged in the form of a row and column matrix of a plurality of subblocks, and each of the plurality of subblocks has N._sxN_sA method in which a sequence matrix generated by shifting a matrix having a size by a predetermined exponent corresponding to each of the plurality of subblocks is arranged, and the parity check matrix for improving error correction performance is generated. In the step of determining the block cycle of the block LDPC code to an arbitrary first value, and after determining the block cycle, the exponent is in the ordinal matrix arranged in each of the subblocks. The sum of the exponents of the ordinal matrix, which is an odd number, minus the sum of the exponents of the ordinal matrix, whose exponent is even, among the ordinal matrices arranged in each of the subblocks, is multiplied by an arbitrary second value. Having a step of determining the second value to be a value and controlling each of the subblocks to have a cycle corresponding to the product of the first value and the second value. It is characterized by.</p><p num="0051"> In the device for achieving the above object, the present invention is a block low density parity check (LDPC) code decoding device, wherein an information portion corresponding to an information word and a third device corresponding to parity are controlled by a predetermined control. A variable node decoder that connects variable nodes by the weights of the columns that make up the parity check matrix, which consists of a parity part of 1 and a second parity part, detects the probability value of the received signal, and outputs it. The first adder that subtracts the signal previously generated during decoding from the signal output from the variable node decoder and outputs it, and the parity check matrix that inputs the signal output from the first adder and outputs it. The deinterleaver that deinterleaves and outputs by the deinterleaving method set corresponding to the above, and the inspection node corresponding to each weight of the row constituting the parity check matrix are connected by a predetermined control signal. , An inspection node decoder that detects and outputs the probability value of the output signal from the deinterleaver, and a second adder that subtracts the signal output from the deinterleaver from the output signal of the inspection node decoder. , The interleaver that interleaves the signal output from the second adder by the interleaving method set by the parity check matrix and outputs it to the variable node decoder and the first adder, and the parity check. It is characterized by including a controller that generates a matrix and controls the deinterleaving method and the interleaving method corresponding to the parity check matrix.</p><p num="0052"> Further, the present invention is a block low density parity inspection (LDPC) code encoding device, in which an information portion corresponding to an information word and a first one corresponding to parity, which are generated in advance by inputting an information word. A first matrix multiplication device that multiplies the first submatrix of the parity check matrix composed of the parity part and the second parity part of the above, and the second part of the parity check matrix by inputting the information word. Multiply the matrix product of the second matrix multiplication device that multiplies the matrix, the signal output from the first matrix multiplication device, and the inverse matrix of the third submatrix and the fourth submatrix of the parity check matrix. A third matrix multiplication device, a first adder that adds a signal output from the second matrix multiplication device and a signal output from the third matrix multiplication device, and the first adder. A fourth matrix multiplier that multiplies the signal output from and the fifth submatrix of the parity check matrix, a signal output from the second matrix multiplier, and an output from the fourth matrix multiplier. The second adder that adds the obtained signals, the signal output from the second adder, and the matrix product of the third submatrix of the parity check matrix and the inverse matrix of the fourth submatrix are multiplied. The block LDPC code is used with the output signal of the fifth matrix multiplication device, the information word, and the first adder as the first parity, and the output signal of the fifth matrix multiplication device as the second parity. It is characterized by including a switch that multiplies and outputs according to the format.</p>

<p num="0053"> The present invention has the effect of maximizing error correction capability and improving system performance by proposing a block LDPC code that maximizes the minimum cycle length in a mobile communication system. The present invention also has the effect of minimizing the coding complexity of the block LDPC code by generating an efficient parity check matrix.</p>

Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings. In the following description, when it is determined that the description of a known function or configuration related to the present invention makes the gist of the present invention unclear, the detailed description thereof will be omitted.

The present invention presents a method for encoding and decoding a non-uniform low density parity check (hereinafter referred to as LDPC) code having excellent performance. That is, the present invention is a heterogeneous LDPC code having a distribution that maximizes the length of the minimum cycle on the factor graph, minimizes the coding complexity, and optimizes the order distribution on the factor graph. The coding and decoding plan of is presented.

The cycle on the factor graph of the LDPC code indicates a loop composed of edges connecting the variable node and the inspection node in the factor graph, and the length of the cycle is defined by the number of edges constituting the loop. Ru. A long cycle length indicates that the factor graph has a large number of edges connecting the variable nodes and inspection nodes that make up the loop. The longer the cycle length on the factor graph is generated, the better the performance of the LDPC code. On the other hand, the more short cycles there are on the factor graph, the lower the error correction capability of the LDPC code because of the performance degradation of the error floor. That is, when there are many short-length cycles on the factor graph, one's own information starting from any node belonging to the short-length cycle comes back after a small number of iterations. As the number of iterations increases, the information will continue to come back to you. Therefore, the information is not updated well, and the error correction capability of the LDPC code is eventually reduced.

FIG. 7 is a diagram schematically showing the cycle structure of the block LDPC code in which the parity check matrix is composed of four submatrixes.

Prior to explaining FIG. 7, the block LDPC code is a new LDPC code that considers not only efficient coding but also efficient storage of a parity check matrix and improvement in performance. This block LDPC code is a concept LDPC code that generalizes and extends the structure of a uniform LDPC code. As shown in FIG. 7, the parity check matrix of the block LDPC code is composed of four blocks, the diagonal line means the position where the element having the value of 1 exists, and all the parts other than the dead line part are present. It means the position where the element having a value of 0 exists. Further, P indicates the same permutation matrix as the permutation matrix described in FIG. 4 of the prior art. Here, the permutation matrix P is N, as explained in FIG._sxN_sA square matrix of size, N that constitutes this permutation matrix P_sEach row has a weight of 1, N_sShows a matrix in which the weight of each row is also 1. Here, the weight indicates the number of elements having a non-zero value among the elements constituting the parity check matrix.

To analyze the cycle structure of the block LDPC code shown in FIG. 7, the submatrix P^aThe element with the value of 1 located in the i-th row is defined as a reference, and the element with the value of 1 located in the i-th row is called "0-point". Here, "submatrix" indicates a matrix corresponding to a submatrix. Then the 0-point is the submatrix P^aIt is located in the (i + a) th column of.

Submatrix P located in the same row as the 0-point^{b b}An element having a value of 1 in is called a "1-point". For the same reason as this 0-point, the 1-point is the submatrix P^{b b}Located in the (i + b) th column of.

Then the submatrix P located in the same column as the 1-point^cAn element having a value of 1 in is called a "2-point". Submatrix P^cModulo N to the right of each of the columns in the identity matrix I_sSince it is a matrix obtained by moving by c with respect to, the 2-point is this submatrix P.^cIt will be located on the (i + bc) th line of.

Also, the submatrix P located in the same row as the 2-point^dAn element having a value of 1 in is called a "3-point". 3-Point is the submatrix P^dIt will be located in the (i + b-c + d) th column in.

Finally, the submatrix P located in the same column as the 3-point^aAn element having a value of 1 in is called a "4-point". This 4-point is the submatrix P^aIt will be located on the (i + b-c + da) th line of.

In the cycle structure of the LDPC code shown in FIG. 7, if there is a cycle having a length of 4, the 0-point and the 4-point are at the same position. That is, the following relationship &lt;Equation 4&gt; is established between 0-point and 4-point.

<maths num="6"><img id="000007" he="19" wi="153" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Then, if the above &lt;Equation 4&gt; is further arranged, it is as follows &lt;Equation 5&gt;.

<maths num="7"><img id="000008" he="14" wi="153" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

As a result, a cycle of length 4 is generated when a relationship such as &lt;Equation 5&gt; is established. In general, when the 0-point and 4m-point are the same first, the ii + m (b-c + da) relationship is established, and the relationship as shown in &lt;Equation 6&gt; below is established. To.

<maths num="8"><img id="000009" he="14" wi="153" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

To explain further, when m is a positive integer having the minimum value among the positive integers satisfying &lt;Equation 6&gt; for a given a, b, c, and d, a block as shown in FIG. 7 is used. In the cycle structure of the LDPC code, the cycle having a length of 4 m is the cycle having the minimum length.

As a result, as mentioned above, gcd (N) when (a-b + cd) 0_s, a-b + cd) = 1 then m = N_sbecome. Where gcd (N_s, a-b + cd) is an integer N_sAnd a-b + cd for the calculation of the greatest common divisor. Therefore, the length is 4N_sIs the cycle having the minimum length.

As explained in FIG. 7, in the analysis of the block LDPC code cycle, when the number of blocks constituting the parity check matrix of the block LDPC code exceeds 4, that is, the number of submatrix constituting the parity check matrix is 4. It is also applicable when it exceeds. Here, with reference to FIG. 8, the cycle structure of the LDPC code when the number of submatrix constituting the parity check matrix exceeds 4.

FIG. 8 is a diagram schematically showing the cycle structure of the block LDPC code in which the parity check matrix is composed of six submatrixes.

The parity check matrix of the block LDPC code shown in FIG. 8 is composed of 6 blocks, and as explained in FIG. 7, the diagonal line indicates the position where the element having the value of 1 exists, and other than this shaded portion. The part of indicates the position where the element having a value of 0 exists. Further, P also shows the same permutation matrix as the permutation matrix described in FIG. 4, which is a conventional technique. Analyzing the cycle structure of the block LDPC code in FIG. 8 by the method as described in FIG. 7, the cycle having a length of 6 m is the cycle having the minimum length.

In general, i i + m (b-c + d-e + fa) (mod N) if the 0-point and 6m-point are the same first._s) Is established, and the following &lt;Equation 7&gt; is satisfied.

<maths num="9"><img id="000010" he="14" wi="153" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Among the positive integers satisfying &lt;Equation 7&gt; for these given a, b, c, d, e, and f, letting the positive integer having the minimum value be "m", the block shown in FIG. In the cycle structure of the LDPC code, the cycle having a length of 6 m is the cycle having the minimum length.

As mentioned above, gcd (N) when (a-b + c-d + ef) 0_s, a-b + c-d + ef) = 1 then m = N_sbecome. Therefore, the length is 6N_sIs the cycle having the minimum length.

As described above, the following rules can be estimated for the block LDPC code.

&lt;Rule 1&gt; If there is a cycle with a block LDPC code and a length of 2 liters, the condition of &lt;Equation 8&gt; below should be satisfied.

<maths num="10"><img id="000011" he="13" wi="159" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

&lt;Equation 8&gt; d, a_i(i = 1,2, ..., 21) shows the exponential of the permutation matrix through which cycles of length 2l pass sequentially. That is, a cycle having a length of 2 l with respect to the subblocks constituting the parity check matrix of the block LDPC code is

<maths num="11"><img id="000012" he="15" wi="51" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Indicates that the passage is in the order of. Where all a_iOf course, they do not have to be different from each other, and it is possible that there are partial blocks that pass through in duplicate.

&lt;Rule 2&gt; m is defined as the smallest positive integer that satisfies &lt;Equation 9&gt; below.

<maths num="12"><img id="000013" he="13" wi="159" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

In &lt;Equation 9&gt;, a_iIs the exponential of a permutation matrix properly selected so that block-by-block cycles are formed in the overall parity check matrix. And a_iAs in the description of &lt;Rule 1&gt;, they do not all have to be different from each other, and it is of course possible that there are subblocks that pass through in duplicate. That is, the submatrix

<maths num="13"><img id="000014" he="15" wi="13" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Has a cycle structure with a minimum length of 2 lm.

Using &lt;Rule 1&gt; and &lt;Rule 2&gt; makes it easy to analyze the characteristics of the cycle structure of the block LDPC code. As an example, using &lt;Rule 1&gt; and &lt;Rule 2&gt; not only shows exactly how well the cycles with a minimum length of 6 in the array code are distributed, but also the block LDPC code block described below. The characteristic analysis of the unit cycle (hereinafter referred to as "block cycle") structure is also facilitated. Here, the block cycle is an important element for adjusting the cycle length in the configuration of the parity check matrix, and the block cycle will be described using FIG. 9 and &lt;Rule 1&gt; and &lt;Rule 2&gt;.

FIG. 9 is a diagram schematically showing a block cycle structure of a block LDPC code. With reference to FIG. 9, it is assumed that each of the blocks constituting the block LDPC code has a weight 1, and when this block constitutes a cycle, it is defined as constituting a block cycle. FIG. 9 shows a block cycle composed of 4 blocks from the left side, a block cycle composed of 6 blocks, and a block cycle composed of 8 blocks. Then, as explained in &lt;Rule 1&gt; and &lt;Rule 2&gt;, even if a short block cycle is constructed, the submatrix corresponding to each of the blocks constituting the block cycle is appropriately selected. , The actual parity check matrix can be controlled so that short cycles are not generated. However, when multiple block cycles overlap in a block LDPC code, the minimum length of the actual cycle within the block cycle is reduced. As a result, there is a problem that a short cycle is generated in the actual parity check matrix.

Here, the problem that a plurality of block cycles are duplicated in the block LDPC code will be described with reference to FIG. 10 and &lt;Rule 1&gt; and &lt;Rule 2&gt;. It also describes why duplicate block cycles should be avoided when generating a parity check matrix for block LDPC codes.

FIG. 10 is a diagram schematically showing a block cycle structure of a block LDPC code in which six submatrixes of a parity check matrix are overlapped. Following the arrows shown in FIG. 10, the following sequential block order can be considered.

<maths num="14"><img id="000015" he="14" wi="159" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

The exponential of the submatrix by sequential block order is N_sRegardless of the value of, the condition of &lt;Equation 10&gt; below is always satisfied.

<maths num="15"><img id="000016" he="15" wi="159" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

When &lt;Equation 10&gt; is applied to &lt;Equation 9&gt; explained in &lt;Rule 2&gt;, m = 1. Therefore, in the case of a block LDPC code in which a block cycle in which six submatrixes are duplicated as shown in FIG. 10 exists, the length of any submatrix constituting the total parity check matrix is always selected. Will include a cycle structure where is 12. That is, in the case of a block LDPC code in which a block cycle in which six submatrixes are overlapped as shown in FIG. 10 exists, the minimum cycle length of the parity check matrix is limited to a maximum of 12.

FIG. 11 is a diagram schematically showing a block cycle structure of a block LDPC code in which seven partial blocks of a parity check matrix are overlapped. Following the arrows shown in FIG. 11, the following sequential block order can be considered.

<maths num="16"><img id="000017" he="16" wi="153" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

The exponential of the submatrix by sequential block order is N_sRegardless of the value of, the condition of &lt;Equation 11&gt; below is always satisfied.

<maths num="17"><img id="000018" he="14" wi="159" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Applying &lt;Equation 11&gt; to &lt;Equation 9&gt; described in &lt;Rule 2&gt;, m = 1. Therefore, in the case of a block LDPC code in which seven submatrixes of the parity check matrix as shown in FIG. 11 have overlapping block cycles, no matter which submatrix constituting the total parity check matrix is selected, Includes a cycle structure whose length is always 14. That is, as shown in FIG. 11, in the case of a block LDPC code in which seven submatrixes of the parity check matrix have overlapping block cycles, the minimum cycle length of the parity check matrix is limited to a maximum of 14.

As described above, when there are many block cycles overlapping between the blocks that make up the parity check matrix with the block LDPC code, the minimum cycle length is set regardless of how the submatrix of the parity check matrix is selected. It can be seen that there is a limit to maximizing the value and its performance deteriorates. Therefore, when generating a parity check matrix with a block LDPC code, it is necessary to generate as few block cycles as possible so that duplicate block cycles do not occur.

Next, a method of generating a parity check matrix of a block LDPC code in consideration of efficient coding other than the block cycle will be described.

In the present invention, the Richardson-Urbanke method is used as the coding method of the block LDPC code. Since this Richardson-Urbanke method is used in the coding method, the complexity of coding can be minimized so that the parity check matrix has a form similar to that of the complete lower triangular matrix.

FIG. 12 is a diagram showing a parity check matrix having a complete lower triangular matrix form.

As shown in FIG. 12, the parity check matrix has a complete lower triangular matrix form, and is composed of an information part and a parity part. Here, the information part indicates the part of the parity check matrix that is mapped to the actual information word in the process of encoding the block LDPC code, and the parity part is mapped to the actual parity in the process of encoding the block LDPC code. The part of the parity check matrix is shown. As shown in FIG. 12, the parity part has a zero matrix and a submatrix based on the identity matrix I, and the submatrix has a complete lower triangular form.

FIG. 13 is a diagram showing a parity check matrix having a form similar to the complete lower triangular matrix form. As shown in FIG. 13, the parity check matrix is different from the complete lower triangular matrix form as compared with the parity check matrix of the complete lower triangular matrix form shown in FIG. 12. In FIG. 13, the superscript a of the permutation matrix P of the information part_ijIs 0 a_ij N_s-1 or a_ij= . Superscript a of this permutation matrix P_ijWhen = 0, that is, the permutation matrix P⁰Is the identity matrix

<maths num="18"><img id="000019" he="16" wi="18" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

And the superscript a of the permutation matrix P_ijIf = , that is, the permutation matrix P^∞Indicates a zero matrix. In FIG. 13, m indicates the number of rows of subblocks mapped to the information portion, and q indicates the number of columns of subblocks mapped to the parity portion. I means that the corresponding permutation matrix is located in the i-th row of the parity check matrix subblock, and j means that the corresponding permutation matrix is in the j-th column of the parity check matrix subblock. Means to be located. That is,

<maths num="19"><img id="000020" he="16" wi="18" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Is a permutation matrix located in a subblock that intersects the i-th row and the j-th column. Also, the superscript a of the permutation matrix of the above parity part_i, X, y indicate the exponent (superscript) of the permutation matrix P, but for convenience of explanation, this a_i, X, y are only set to be different from each other for the purpose of distinguishing from the information part. That is, in FIG.

<maths num="20"><img id="000021" he="16" wi="22" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Is also a permutation matrix and is located diagonally to the parity part. Superscript a₁~ a_mIndicates that the submatrix is sequentially indexed. In Figure 13, p^xAnd p^yIs also a permutation matrix, and for convenience of explanation, it is set so as to be different from each other in order to distinguish it from the information part.

Assuming that the block length of the block LDPC code having the parity check matrix as shown in FIG. 13 is N, the coding complexity of the block LDPC code increases linearly with respect to the block length N.

The biggest problem with the LDPC code having the parity check matrix in FIG. 13 is that the length of the partial block is N._sWhen is N, the degree is always 1 on the factor graph of the block LDPC code._sThe number of inspection nodes is generated. Here, the inspection node having a degree of 1 cannot affect the performance improvement by iterative decoding. Therefore, the standard LDPC code based on the Richardson-Urbanke method does not include check nodes of degree 1. Therefore, in order to design the parity check matrix so that efficient coding is possible without including the check node having the order 1, the parity check matrix of FIG. 13 is assumed as the basic parity check matrix. As shown in FIG. 13, the selection of the submatrix in the parity check matrix composed of the submatrix is a very important factor in improving the performance of the block LDPC code, and therefore it is also very important to find an appropriate selection criterion of the submatrix. It is an important factor.

Therefore, in the generation of the block LDPC code, the parity check matrix is constructed in consideration of the following design criteria.

&lt;Design criteria for parity check matrix of block LDPC code&gt;

(1) The parity portion is configured to have a fixed form. The fact that the parity portion has a fixed form means that the unit matrix is located as shown in FIG. 16 to be described later.

(2) Preferentially select from the submatrix with the lowest order. In the present invention, the "order" of a submatrix is called the order between 3 and 5. In addition, the submatrixes are arranged so that the block cycles are generated as few as possible when sequentially selecting from the submatrixes of lower order, and the cycle having the minimum length between the submatrixes of lower order is constructed as long as possible. ..

(3) After constructing all the submatrixes of low order, construct the submatrixes of high order in sequence. When arranging high-order submatrixes, make the minimum length cycle as long as possible overall.

The design method of the parity check matrix of the block LDPC code will be described based on the parity check matrix design standard of the block LDPC code described above.

Here, in order to facilitate the design method of the parity check matrix of the block LDPC code and the coding method of the block LDPC code, the parity check matrix as shown in FIG. 13 is composed of six sub-matrix as shown in FIG. It is assumed that it is in the form of.

FIG. 14 is a diagram in which the parity check matrix of FIG. 13 is divided into six subblocks. Referring to FIG. 14, as shown in FIG. 13, the parity check matrix of the block LDPC code is divided into the information part s and the first parity part p.₁And the second parity part p₂Divide into partial blocks of. Here, the information part indicates a part of the parity check matrix that is mapped to the actual information word in the process of encoding the block LDPC code as in the information part described with reference to FIGS. For convenience, the information part s is only displayed with different reference codes. Also, the first parity part p₁And the second parity part p₂Shows the part of the parity check matrix that is mapped to the actual parity in the process of encoding the block LDPC code as in the parity part described in FIGS. 12 and 13, and the parity part is divided into two parts. ..

The submatrixes A and C correspond to the partial blocks of the information part s, that is, the submatrixes A and C, and the submatrixes B and D correspond to the first parity part p.₁Corresponds to the submatrix B and D of, and the submatrix T and E are the second parity part p.₂Corresponds to the partial blocks T and E of. Here, FIG. 14 shows that the parity check matrix is divided into seven subblocks, but '0' is not a separate subblock, and the submatrix T corresponding to the subblock T is a complete lower triangle. Since it has a morphology, the area where the zero matrix is arranged around the diagonal is indicated by '0'. Information part s and first parity part p₁And the second parity part p₂The process of simplifying the coding method using the submatrix of is described in FIG. 17 below.

The submatrix of FIG. 14 will be described below with reference to FIG.

FIG. 15 is a diagram showing a transposed matrix of the submatrix B of FIG. 14, a submatrix E, a submatrix T, and an inverse matrix of the submatrix T. See Figure 15

<maths num="21"><img id="000022" he="19" wi="51" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Is shown. Also, the permutation matrix shown in FIG. 15, for example,

<maths num="22"><img id="000023" he="12" wi="13" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Can be an identity matrix. As mentioned above, the exponential of the permutation matrix, i.e. a₁Permutation matrix if is 0

<maths num="23"><img id="000024" he="12" wi="13" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Is the identity matrix. Also, the exponential of the permutation matrix, that is, a₁If is increased by a preset value, then the permutation matrix is cyclically shifted by the increased set value, that is, the permutation matrix.

<maths num="24"><img id="000025" he="13" wi="13" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Becomes the identity matrix.

FIG. 17 is a flowchart showing a process of generating a parity check matrix of the block LDPC code according to the embodiment of the present invention. Prior to the explanation of FIG. 17, in order to generate the block LDPC code, the codeword size and the code rate of the block LDPC code to be generated are determined, and the parity is determined by the determined codeword size and the code rate. The size of the check matrix should be determined. Assuming that the codeword size of the block LDPC code is N and the code rate is R, the size of the parity check matrix is N (1-R) xN. Further, as shown in FIG. 17, the parity check matrix generation process of the block LDPC code is first generated according to the system state of the communication system, and by using the generated parity check matrix, the parity check matrix is substantially generated. It is good to carry out the generation process of. Only once.

Referring to FIG. 17, in step 1711 the controller divides the size N (1-R) xN parity check matrix into p blocks on the horizontal axis and q blocks on the vertical axis. After splitting into pxq blocks, proceed to step 1713. Here, the size of each block is N_sxN_sTherefore, the parity check matrix is N_sxq rows and N_sIt consists of xp columns. In step 1713, the controller divides the parity check matrix into pxq blocks into the information part s and the parity part, that is, the first parity part p.₁And the second parity part p₂And proceed to step 1715 and step 1721.

In step 1715, the controller determines a non-zero block or non-zero matrix, a block that is '0', or a block that is a zero matrix with a degree distribution that guarantees the high performance of the block LDPC code for the information part s. Proceed to step 1717. Here, since the order distribution that guarantees the high performance of the block LDPC code is as described above, a detailed description thereof will be omitted. In step 1717, the controller puts the minimum cycle length of the block cycle in the non-zero matrix portion of the blocks having a low order among the blocks determined by the order distribution that guarantees the high performance of the block LDPC code as described above. Column matrix so that

<maths num="25"><img id="000026" he="13" wi="13" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

And proceed to step 1719. Where the permutation matrix

<maths num="26"><img id="000027" he="13" wi="13" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

When determining the information part s as well as the first and second parity parts P₁, P₂The block cycle of is also taken into consideration when deciding.

In step 1719, the controller randomly permutates the non-zero matrix portion of the blocks with high order in the blocks determined by the order distribution that guarantees the excellent performance of the block LDPC code.

<maths num="27"><img id="000028" he="13" wi="13" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

To decide and finish. Here, a permutation matrix applied to the non-zero matrix part of a block having a high degree.

<maths num="28"><img id="000029" he="13" wi="13" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Permutation matrix so that the minimum cycle size of the block cycle is maximized when determining

<maths num="29"><img id="000030" he="13" wi="13" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Should be decided. Also, not only the information part s but also the first parity part p₁And the second parity part p₂The block cycle of is also taken into consideration when deciding. As mentioned above, the permutation matrix in the information part s of the parity check matrix

<maths num="30"><img id="000031" he="13" wi="13" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

The form in which is arranged is shown in FIG.

In step 1721, the controller has the first and second parity parts p.₁, P₂Is divided into four submatrixes B, T, D, and E, and then the process proceeds to step 1723. In step 1723, the controller has two submatrixes in the submatrix B that make up the submatrix B.^yWhen

<maths num="31"><img id="000032" he="13" wi="13" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Enter and proceed to step 1725. Here, a permutation matrix P that is not 0 in two subblocks in the subblocks that make up the submatrix B^yWhen

<maths num="32"><img id="000033" he="13" wi="13" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

The structure for inputting is already explained with reference to FIG.

In step 1725, the controller inputs the identity matrix I to the diagonal submatrix T of the submatrix T, and any submatrix T below the diagonal component (i, i + 1) th submatrix. Permutation matrix

<maths num="33"><img id="000034" he="13" wi="40" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Enter and proceed to step 1727. Here, the identity matrix I is input to the diagonal submatrix of the submatrix T, and any permutation matrix is entered to the (i, i + 1) th submatrix below the diagonal component of the submatrix T.

<maths num="34"><img id="000035" he="13" wi="40" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

The method of inputting is described with reference to FIG.

At step 1727, the controller permutates the submatrix D to the permutation matrix P.^xAfter entering, proceed to step 1729. At step 1729, the control is only in the last subblock in the submatrix E.

<maths num="35"><img id="000036" he="13" wi="16" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Enter to exit. Here, there are two subblocks in the last subblock that make up the submatrix E.

<maths num="36"><img id="000037" he="13" wi="16" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

The structure for inputting is already explained with reference to FIG.

If the submatrix B, the submatrix D, and the submatrix E are appropriately configured in the parity check matrix of the block LDPC code, the coding process of the block LDPC code can be easily controlled. Here, in order to facilitate the coding process of the block LDPC code, the process of constructing the submatrix B, the submatrix D, and the submatrix E of the parity check matrix will be described.

As described above, when the parity check matrix of FIG. 13 is divided into the submatrix as described in FIG. 14, it can be shown as shown in FIG.

Codeword vector<u style="single">c</u>Is the information part s and the first parity part p as shown in FIG.₁And the second parity part p₂Codeword vector when splitting into<u style="single">c</u>Is an information word vector<u style="single">s</u> And the first parity vector<u style="single">P</u>_{<u style="single">1</u>}And the second parity vector<u style="single">P</u>_{<u style="single">2</u>}It can be divided into. In this case, the parity check matrix and the codeword vector<u style="single">c</u>The product of is shown as &lt;Equation 12&gt; and &lt;Equation 13&gt; below.

<maths num="37"><img id="000038" he="13" wi="147" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths><maths num="38"><img id="000039" he="13" wi="146" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

In &lt;Equation 12&gt;, T indicates the transpose operation, and in &lt;Equation 13&gt; the first parity vector.<u style="single">P</u>_{<u style="single">1</u>}The part related to, that is,

<maths num="39"><img id="000040" he="13" wi="14" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Is obtained using &lt;Equation 14&gt; below.

<maths num="40"><img id="000041" he="13" wi="158" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

In &lt;Equation 14&gt;, the coding complexity of the block LDPC code is generated in proportion to the square of the size of the matrix φ. Therefore, in the present invention, the first parity vector<u style="single">P</u>_{<u style="single">1</u>}The matrix φ used to find is set to be the identity matrix I. By setting the matrix φ to be the identity matrix I in this way, the coding complexity of the block LDPC code is minimized. Here, the process of setting the matrix φ to be the identity matrix I will be described with reference to FIG.

First, the permutation matrix

<maths num="41"><img id="000042" he="13" wi="22" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Can be fixed to the identity matrix I. Submatrix T shown in FIG.^-1In a partial block of

<maths num="42"><img id="000043" he="13" wi="22" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Part is a matrix

<maths num="43"><img id="000044" he="13" wi="17" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

From the matrix

<maths num="44"><img id="000045" he="13" wi="17" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Is the product of

<maths num="45"><img id="000046" he="19" wi="34" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Is shown. The matrix φ can be obtained by using the following &lt;Equation 15&gt; to &lt;Equation 17&gt;.

First, in FIG. 15, since the submatrix E is a zero matrix except for one submatrix, T is the inverse matrix of the submatrix E and the submatrix T.^-1Multiplication is the inverse of the submatrix T^-1It is shown as &lt;Equation 15&gt; in the form of multiplication of the last row of and the last block of the submatrix E.

<maths num="46"><img id="000047" he="14" wi="159" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Inverse matrix T of submatrix E and submatrix T^-1When the product of is multiplied by the submatrix B, it is shown as &lt;Equation 16&gt;.

<maths num="47"><img id="000048" he="14" wi="159" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

(Where k is P^yIt is an arbitrary natural number determined by the position of. ) As shown in &lt;Equation 16&gt;, T is the inverse matrix of the submatrix E and the submatrix T.^-1When multiplying the product of submatrix B by the submatrix B, since the submatrix B contains all zero matrices except for two submatrixes, by performing the multiplication on only the two blocks of the submatrix B. , Easy to calculate.

if,

<maths num="48"><img id="000049" he="15" wi="80" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

When set to, φ ET^-1B + D = I. Therefore, the matrix φ is the identity matrix I. Then, &lt;Equation 17&gt; simply shows the condition that the matrix φ becomes the identity matrix I.

<maths num="49"><img id="000050" he="15" wi="159" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

As shown in &lt;Equation 15&gt; to &lt;Equation 17&gt;, if the matrix φ is set to be the identity matrix I, the complexity of the block LDPC code coding process can be minimized.

Next, the process of encoding the block LDPC code using the parity check matrix according to the present invention will be described with reference to FIG.

FIG. 18 is a flowchart showing a coding process of the block LDPC code according to the embodiment of the present invention. Referring to FIG. 18, the controller in step 1811 is an information word vector for encoding with a block LDPC code.<u style="single">s</u>Is received, and the process proceeds to step 1813 and step 1815. Here, the information word vector received for coding with the block LDPC code.<u style="single">s</u>The length of is assumed to be k. In step 1813, the controller has this information word vector<u style="single">s</u>And parity check matrix (A<u style="single">s</u>After performing matrix multiplication on the submatrix A of) ()<u style="single">s</u>), Proceed to step 1817. Here, since the number of elements having a value of 1 existing in the submatrix A is much smaller than the number of elements having a value of 0, the information word vector.<u style="single">s</u>And the matrix multiplication of the submatrix A of the parity check matrix is possible with a relatively small number of sum-product operations. Also, the position of an element with a value of 1 in the submatrix A can be indicated by the non-zero block position and the exponential of the forward matrix of that block, so that only a very simple operation compared to a given parity check matrix. But matrix multiplication is feasible. In step 1815, the controller sees the parity check matrix submatrix C and the information word vector.<u style="single">s</u>Perform matrix multiplication of (C<u style="single">s</u>), Proceed to step 1819.

On the other hand, in step 1817, the control is an information word vector.<u style="single">s</u>And parity check matrix (ET^-1A<u style="single">s</u>) Submatrix A matrix multiplication result and matrix ET^-1Perform matrix multiplication and proceed to step 1819. As mentioned above, the matrix ET^-1Since the number of elements having a value of 1 is very small, matrix multiplication can be easily performed just by knowing the exponential of the permutation matrix of the block. In step 1819, the controller is ET^-1A<u style="single">s</u>And C<u style="single">s</u>Add up to the first parity vector<u style="single">p</u>_{<u style="single">1</u>}After calculating (<u style="single">p</u>_{<u style="single">1</u>}= ET^-1A<u style="single">s</u>+ C<u style="single">s</u> ), Proceed to step 1821. Here, the addition operation is 0 when the same bits are added in the exclusive OR operation, and 1 when different bits are added. As a result, the process up to step 1819 is the first parity vector as explained in &lt;Equation 14&gt;.<u style="single">p</u>_{<u style="single">1</u>}Is for calculating.

In step 1821, the controller sees the parity check matrix submatrix B and the first parity vector.<u style="single">p</u>_{<u style="single">1</u>} Multiply (B<u style="single">p</u>_{<u style="single">1</u>}), A to that value<u style="single">s</u>After adding (A<u style="single">s</u>+ B<u style="single">p</u>_{<u style="single">1</u>}), Proceed to step 1823. Here, as explained in &lt;Equation 12&gt;, the information word vector<u style="single">s</u>And the first parity vector<u style="single">p</u>_{<u style="single">1</u>}Knowing that, the second parity vector<u style="single">p</u>_{<u style="single">2</u>}To find the inverse matrix T of the submatrix T of the parity check matrix^-1Must be multiplied. Therefore, in step 1823, the controller has a second parity vector.<u style="single">p</u>_{<u style="single">2</u>}To find the inverse matrix T of the submatrix T on the vector calculated in step 1821^-1After multiplying by (<u style="single">p</u>_{<u style="single">2</u>}= T^-1(A<u style="single">s</u>+ B<u style="single">p</u>_{<u style="single">1</u>})), Proceed to step 1825. As mentioned above, the information word vector of the block LDPC code for coding<u style="single">s</u>Knowing only, the first parity vector<u style="single">p</u>_{<u style="single">1</u>}And the second parity vector<u style="single">p</u>_{<u style="single">2</u>}Can be obtained, and as a result, all codeword vectors are obtained. Then, in step 1825, the controller takes the information word vector.<u style="single">s</u>And the first parity vector<u style="single">p</u>_{<u style="single">1</u>}And the second parity vector<u style="single">p</u>_{<u style="single">2</u>}Codeword vector generated by<u style="single">c</u>Is generated and transmitted, and the above procedure is completed.

FIG. 19 is a block configuration diagram showing an internal structure of a block LDPC code coding device for performing the functions according to the embodiment of the present invention.

Referring to FIG. 19, the block LDPC code encoders are the matrix A multiplier 1911, the matrix C multiplier 1913, and the matrix ET.^-1Multiplier 1915, first adder 1917, matrix B multiplier 1919, second adder 1921, matrix ET^-1Includes multiplier 1923 and switches 1925, 1927, 1929.

First, the input signal, that is, the information word vector of length k to be encoded by the block LDPC code.<u style="single">s</u>Is input, and the information word vector of the input length k<u style="single">s</u>Is input to the switch 1925, the matrix A multiplier 1911, and the matrix C multiplier 1913. This matrix A multiplier 1911 is an information word vector<u style="single">s</u>After multiplying by the submatrix A of the total parity check matrix, the matrix ET^-1Output to multiplier 1915 and adder 1921. Also, the matrix C multiplier 1913 is an information word vector.<u style="single">s</u>Is multiplied by the submatrix C of the total parity check matrix, and then output to the first adder 1917. Matrix ET^-1The multiplier 1915 is a submatrix ET of the total parity check matrix to the signal output from the matrix A multiplier 1911.^-1Is multiplied and then output to the first adder 1917.

The first adder 1917 is the matrix ET^-1The signal output from the multiplier 1915 and the signal output from the matrix C multiplier 1913 are input and added, and then output to the matrix B multiplier 1919 and the switch 1927. Here, the first adder 1917 performs an exclusive OR (XOR) operation bit by bit. For example, a vector x = (x) of length 3₁, x₂, x₃) And a vector of length 3 y = (y₁, y₂, y₃) Is input to adder 1917, which is a vector of length 3 x = (x)₁, x₂, x₃) And a vector of length 3 y = (y₁, y₂, y₃) Is exclusively ORed to a vector of length 3

<maths num="50"><img id="000051" he="17" wi="121" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Indicates an exclusive OR operation that becomes 0 when the same bit is operated and becomes 1 when different bits are operated. That is, the signal output from the first adder 1917 is the first parity vector.<u style="single">p</u>_{<u style="single">1</u>}become.

Further, the matrix B multiplier 1919 is a signal output from the first adder 1917, that is, a first parity vector.<u style="single">p</u>_{<u style="single">1</u>}Is input, the submatrix B of the total parity check matrix is multiplied, and then the output is output to the adder 1921. The adder 1921 adds the signal output from the matrix B multiplier 1919 and the signal output from the matrix A multiplier 1911, and then the matrix T.^-1Output to multiplier 1923. Here, the adder 1921 performs an exclusive OR operation on the signal output from the matrix B multiplier 1919 and the signal output from the matrix A multiplier 1911 as described in the adder 1917, and then the matrix T.^-1Output to multiplier 1923.

Matrix T^-1The multiplier 1923 is the signal and matrix T output from the adder 1921.^-1After multiplying by, output to switch 1929. Where the matrix T^-1The output of the multiplier 1923 ends up being the second parity vector<u style="single">p</u>_{<u style="single">2</u>}become. On the other hand, the switches 1925, 1927, and 1929 are switched on and transmit the corresponding signal only at the time of their own transmission. That is, the information word vector<u style="single">s</u>Is transmitted, the switch 1925 is switched on and the first parity vector<u style="single">p</u>_{<u style="single">1</u>}Switch 1927 is switched on when is transmitted, and the second parity vector<u style="single">p</u>_{<u style="single">2</u>}Switch 1929 is switched on when is transmitted.

As mentioned above, by properly selecting the submatrix of the total parity check matrix, the matrix multiplication ET^-1Is relatively easy, thereby ET^-1A<u style="single">s</u>^TIs easy to calculate. The matrix φ becomes the identity matrix I.<u style="single">p</u>_{<u style="single">1</u>}^TΦ for calculating^-1The calculation process of is omitted.

In the above, the method of generating the block LDPC code in consideration of efficient coding has been described. The above block LDPC code is not only highly memory efficient for storing information related to the parity check matrix due to the structural characteristics of the block LDPC code, but also by appropriately selecting the submatrix in the parity check matrix. Efficient coding becomes possible. However, by generating the parity check matrix on a block-by-block basis, the randomness is reduced, which results in a deterioration in the performance of the block LDPC code. That is, as described above, since the non-uniform block LDPC code has better performance than the uniform block LDPC code, it is very important to select a submatrix in the total parity check matrix when designing the block LDPC code. It will act as an element.

Here, a specific method for generating a block LDPC code, which is capable of efficient coding in consideration of the cycle characteristics of the block LDPC code and has excellent performance, will be described with reference to FIG.

FIG. 16 is a diagram showing a parity check matrix of the block LDPC code according to the embodiment of the present invention. Referring to FIG. 16, the parity check matrix of the block LDPC code is as described above, considering the simplicity of the structure.

<maths num="51"><img id="000052" he="17" wi="113" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Set to. In this case, the matrix φ becomes the identity matrix I, which enables efficient coding. Here, the block length N of the submatrix of the parity check matrix_s= 31, and therefore P^-1= P³⁰Is. Since the number of blocks for the entire column of the parity check matrix is 32, the parity check matrix of the block LDPC code having the total block length of 32x31 = 992 and the coding rate of 1/2 is generated.

As a result, as shown in FIG. 16, the block LDPC code has 15 blocks having a weight value of 2 and 12 blocks having a weight value of 3 based on the column of the parity check matrix, and 11 blocks having a weight value of 11. It becomes a non-uniform block LDPC code composed of 5 blocks. Therefore, as shown in FIG. 16, the order distribution of the block LDPC code is shown as &lt;Equation 18&gt; below.

<maths num="52"><img id="000053" he="15" wi="159" file="JP5219552B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

In &lt;Equation 18&gt;, f_iShows the ratio of variable nodes of degree i to total variable nodes in the factor graph of block LDPC code, f_ρiShows the ratio of inspection nodes of degree i to the overall inspection node in the factor graph of the block LDPC code. As an example, the block length is N_sIn the block LDPC code where = 32, the column of the parity check matrix corresponding to 15 variable nodes in the total 32 variable nodes on the factor graph of the block LDPC code has a weight value of 32, and 12 The column of the parity check matrix corresponding to the variable node has the weight value 3, and the column of the parity check matrix corresponding to the five variable nodes has the weight value 11. Not only for these variable nodes, but also for the parity check matrix corresponding to the check node, the weight value can be considered in the same form as that performed for the variable node. On the other hand, as shown in &lt;Equation 18&gt;, the order distribution has a form almost close to the order distribution of the LDPC code having a threshold value. Further, in the case of the block LDPC code shown in FIG. 16, the minimum size of the cycle existing between the nodes having the order 2 or 3 is 12, and in the case of the whole node, the minimum size is 6.

Next, with reference to FIG. 20, a step of decoding the block LDPC code using the parity check matrix according to the embodiment of the present invention will be described.

FIG. 20 is a diagram showing an internal structure of a block LDPC code decoding device according to an embodiment of the present invention. Referring to FIG. 20, the decoding device of the block LDPC code includes the variable node part 2000, the adder 2015, the deinterleaver 2017, the interleaver 2019, the controller 2021, the memory 2023, and the adder 2025. , The inspection node unit 2050 and the hardness determination device 2029 are included. The variable node section 2000 is composed of the variable node decoder 2011 and the switch 2013, and the check node section 2050 is composed of the check node decoder 2027.

The received signal received through the wireless channel is input to the variable node decoder 2011 of the variable node unit 2000. The variable node decoder 2011 calculates the probability value of this received received signal, updates the calculated probability value, and then outputs it to the switch 2013 and the adder 2015. Here, the variable node decoder 2011 connects the variable nodes corresponding to the parity check matrix preset in the block LDPC code decoder, and inputs as many as the number of '1' connected to the variable nodes. And the update operation having the output value is executed. The number of '1' connected to each of the variable nodes is the same as the weight value of each of the columns that make up the parity check matrix. Therefore, the internal operation of the variable node decoder 2011 is performed differently depending on the weight of each column constituting the parity check matrix.

The first adder 2015 inputs the signal output from the variable node decoder 2011 and the output signal of the interleaver 2019 in the previous iterative decoding process, and from the signal from the variable node decoder 2011 in the previous iterative decoding process of the interleaver 2019. After subtracting the output signal, it is output to the deinterleaver 2017. Here, of course, when the decoding process is the first decoding process, the output signal of the interleaver 2019 is regarded as '0'.

The deinterleaver 2017 inputs the signal output from the first adder 2015 and deinterleaves it corresponding to the preset setting method, and then sets it to the second adder 2025 and the inspection node decoder 2027. Output. Here, the internal structure of the deinterriver 2017 has a structure corresponding to the parity check matrix, and the reason is that the interleaver 2019 corresponding to the deinterleaver 2017 depends on the position of the element having the value of '1' in the parity check matrix. This is because the output value with respect to the input value is different from each other.

The second adder 2025 receives the output signal of the check node decoder 2027 and the output signal of the deinterleaver 2017 in the previous iterative decoding process, and deinterleaver from the output signal of the check node decoder 2027 in the previous iterative decoding process. After subtracting the output signal of 2017, it is output to the interleaver 2019. The inspection node decoder 2027 connects inspection nodes corresponding to the parity check matrix preset in the block LDPC code decoder, and inputs and outputs as many as the number of '1' connected to the inspection node. The update operation with is performed. The number of '1' connected to each of the check nodes is the same as the weight value of each of the rows that make up the parity check matrix. Therefore, the internal operations of the check node decoder 2027 differ from each other depending on the weight value of each row constituting the parity check matrix.

The interleaver 2019 interleaves the signal output from the adder 2025 by the setting method preset by the control of the controller 2021, and then outputs the signal to the adder 2015 and the variable node decoder 2011. Here, the controller 2021 reads out the information related to the interleaving method stored in the memory 2023 and controls the interleaving method of the interleaver 2019. Moreover, when this decoding process is the first decoding process, it goes without saying that the output signal of the deinterleaver 2017 is regarded as '0'.

By iterating through the above process, error-free and reliable decoding is performed, and after performing iterative decoding corresponding to the preset number of iterations, Switch 2013 is a variable node. Switch off between decoder 2011 and adder 2015. After that, the switch 2013 switches on between the variable node decoder 2011 and the hard judge 2029, and outputs the signal output from the variable node decoder 2011 to the hard judge 2029. The hard judgment device 2029 inputs the signal output from the variable node decoder 2011, makes a hard judgment, outputs the hard judgment result, and sets the output value of the hard judgment device 2029 to the finally decoded value. Become.

<figref num="1">It is a figure which shows the parity check matrix of a general (8,2,4) LDPC code.</figref><figref num="2">It is a figure which shows the factor graph of the (8,2,4) LDPC code of FIG.</figref><figref num="3">It is a figure which shows schematic the parity check matrix of a general block LDPC code.</figref><figref num="4">It is a figure which shows the circular matrix P of FIG.</figref><figref num="5">It is a figure which shows the parity check matrix of a general uniform block LDPC code.</figref><figref num="6">It is a figure which shows the parity check matrix of the general non-uniform block LDPC code.</figref><figref num="7">It is a figure which shows schematic the cycle structure of the block LDPC code which a parity check matrix is composed of 4 submatrix.</figref><figref num="8">It is a figure which shows schematic the cycle structure of the block LDPC code which made up 6 submatrix of a parity check matrix.</figref><figref num="9">It is a figure which shows roughly the block cycle structure of a block LDPC code.</figref><figref num="10">It is a figure which shows schematic the block cycle structure of the block LDPC code in which 6 submatrix of a parity check matrix is overlapped.</figref><figref num="11">It is a figure which shows schematic the block cycle structure of the block LDPC code in which 7 submatrix of a parity check matrix is overlapped.</figref><figref num="12">It is a figure which shows the parity check matrix which has a perfect lower triangular matrix form.</figref><figref num="13">It is a figure which shows the parity check matrix which has the form similar to the complete lower triangular matrix form.</figref><figref num="14">It is the figure which divided the parity check matrix of FIG. 13 into 6 subblocks.</figref><figref num="15">It is a figure which shows the transpose matrix of the submatrix B of FIG. 14, the submatrix E, the submatrix T, and the inverse matrix of the submatrix T.</figref><figref num="16">It is a figure which shows the parity check matrix of the block LDPC code by embodiment of this invention.</figref><figref num="17">It is a flowchart which shows the generation process of the parity check matrix of the block LDPC code by embodiment of this invention .</figref><figref num="18">It is a flowchart which shows the coding process of the block LDPC code by embodiment of this invention.</figref><figref num="19">It is a block block diagram which shows the internal structure of the block LDPC code coding apparatus by embodiment of this invention.</figref><figref num="20">It is a figure which shows the internal structure of the decoding apparatus of the block LDPC code by embodiment of this invention.</figref>

Code description

1911 Matrix A multiplier 1913 Matrix C multiplier 1915 matrix ET^-1Multiplier 1917 1st adder 1919 Matrix B multiplier 1921 Second adder 1923 Matrix ET^-1Multiplier 1925,1927,1929 switch