KR20070085244A - Test matrix generation method and communication method - Google Patents

Abstract

A parameter for a pseudo random number substitution matrix is calculated using a predetermined information length, a coding rate, and a maximum order of columns, and a pseudo random number substitution matrix using a pseudo random number sequence and a Latin square matrix by the parameters for the calculated pseudo random number substitution matrix. Using a predetermined information length, coding rate, and column maximum order, calculating a parameter of a combination of possible order distributions for optimization of order distributions of configurable check matrix generation using a pseudo random number substitution matrix; Optimize the order distribution of the test matrix generation by using the combination of the calculated order distributions as the constraints, By the order distribution of the optimized check matrix generation, the generated pseudo random number substitution matrix is placed to generate a check matrix for the low density parity check code.

Description

CHECK MATRIX PRODUCING APPARATUS AND COMMUNICATION APPARATUS}

TECHNICAL FIELD The present invention relates to a parity check matrix generator when a low density parity check (LDPC) code is adopted as the error correction code, and a communication device equipped with the parity check matrix generation device. The present invention relates to a test matrix generator capable of searching for a parity check matrix for an LDPC code that is stable and characteristic, and a communication device equipped with the check matrix generator.

The conventional parity check matrix generation method for LDPC codes will be described below. In the conventional LDPC encoding / decoding system, the communication apparatus on the transmitting side is provided with an encoder and a modulator, while the apparatus on the receiving side is configured with a demodulator and a decoder. Here, the flow of coding and decoding when the LDPC code is used will be described before explaining the conventional parity check generation method for the LDPC code.

First, the encoder on the transmitting side generates the parity check matrix H by a conventional method described later. Then, the generation matrix G is obtained based on the following conditions.

G: K × N matrix (K is information length, N is sign length)

GH ^T = O (T is transpose)

The encoder then receives a message (m ₁ m ₂ ... M _k ) of information length K, and generates code word C using the generation matrix G.

C = (m ₁ m ₂ … m _K ) G

= (c ₁ c ₂ … c _N ), where H (c ₁ c ₂ … c _N ) ^T = 0)

The encoder then receives a message (m ₁ m ₂ ... M _K ) of information length K, and generates code word C using the generation matrix G.

The modulator performs digital modulation such as Binary Phase Shift Keying (BPSK), Quadrature Phase Shift Keying (QPSK), Quadrature Amplitude Modulation (QAM), and transmits the generated code word C.

On the other hand, on the receiving side, the demodulator performs digital demodulation such as BPSK, QPSK, multi-valued QAM, etc. on the modulated signal received through the communication path, and the decoder performs a "sum-multiply algorithm" on the demodulation result obtained by LDPC encoding. (sum-product algorithm) "is repeated, and the estimation result (corresponding to the original m ₁ m ₂ ... m _k ) is output.

Next, a conventional check matrix generation method for LDPC codes will be described in detail.

1 is a diagram showing a parity check matrix for a conventional LDPC code proposed by Non-Patent Document 1, for example. The matrix shown in FIG. 1 is a two-valued matrix of "1" and "0", and all portions of "1" are filled with black. All other blank parts are "0". The matrix has a number of "1" s in one row (expressed as the order of the row) of 4, a number of "1" s in a single column (expressed as the order of the column) is 3, and the order of all columns and rows is uniform. For this reason, this is generally called "Regular-LDPC code." In addition, in the code | symbol by Nonpatent literature 1, as shown in FIG. 1, the matrix is divided into three blocks, and the random substitution is performed with respect to the 2nd block and the 3rd block.

However, since there is no predetermined loop in this random substitution, in order to find out the code with more favorable characteristic, the time-consuming search by the calculator was required.

Thus, for example, Non Patent Literature 2 has proposed a method of using a Euclidean geometry code as an LDPC code that can generate a matrix definitely without a calculator search and exhibits relatively stable good characteristics. In this method, the "Regular-LDPC code" composed of regular ensemble is described.

According to Non-Patent Document 2, there is a method using a Euclid geometry code EG (2,2 ^6), a type of finite geometry codes to generate a check matrix of the LDPC code has been proposed, in the error rate of 10 ^-4 points, Shannon limit ( The characteristic approaching 1.45 dB is obtained from Shannon limit.

Fig. 2 is a diagram showing the configuration of Euclidean geometry code EG (2, 2 ² ), for example, and has a structure of " Regular-LDPC code "

Therefore, in the case of the Euclidean geometry code EG (m, 2 ^s ), its characteristics are defined as follows. Where EG (m, 2 ^s ) is the m-dimensional Euclidean geometry code above GF (2 ^s ).

Code Length: N = 2 ^2s -1

Redundant bit length: NK = 3 ^s -1

Length of information: K = 2 ^2s -3 ^s

Minimum distance: d _{min =} 2 ^s +1

Density: r = 2 ^s / (2 ^2s -1)

As can be seen from Fig. 2, the Euclidean geometry code has a structure in which the arrangement of " 1 " of each row is cyclically shifted for each row, and the code can be easily and deterministically constructed.

In the parity check matrix generating method according to Non-Patent Document 2, the order of rows and columns is further changed based on the Euclidean geometry code to expand rows and columns as necessary. For example, when dividing the order of the rows of EG (2, 2 ² ) by 1/2, non-patent document 2 separates every other order of four in one column, and separates each.

3 is a diagram showing an example in which the order of the columns of the Euclidean geometry code is regularly separated from 4 to 2;

On the other hand, Non Patent Literature 3 has reported that the characteristic of "Irregular-LDPC code" is better than the characteristic of "Regular-LDPC code". And it interpreted theoretically by the nonpatent literature 4 and the nonpatent literature 5. In addition, said "Irregular-LDPC code" shows the LDPC code which the order of a column and a row is respectively or which is not uniform.

In particular, in Non-Patent Document 5, assuming that the log-likelihood ratio (LLR) of the input and output in the iterative decoder can be approximated to the Gaussian distribution, the "sum-multiply algorithm" of the LDPC code is analyzed and the order of good rows and columns is analyzed. You are saving the ensemble.

[Non-Patent Document 1] R.G. Gallager. "Low-Density Parity Check Codes." IRE Trans. On IT pp 21-28 January 1962.

[Non-Patent Document 2] Y. Kou, S. Lin, and M. P. C. Fossorier, "Low Density Parity Check Codes Based on Finite Geometries: A Rediscovery and New Results," IEEE Trans. Inform. Theory, vol. 47, No. 2, pp. 2711-2736, Feb. 2001.

[Non-Patent Document 3] M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D.A. Spielman, "Improved Low-Density Parity-Check Codes Using Irregular Graphs and Belief Propagation," Proceedings of 1998 IEEE International Symposium on Information Theory, pp. 171, Cambridge, Mass., August 16-21, 1998.

[Non-Patent Document 4] T. J. Richardson and R. Urbanke, "The capacity of low-density parity-check codes under message-passing decoding," IEEE Trans. Inform. Theory, vol. 47, No. 2, pp. 599-618, Feb. 2001.

[Non-Patent Document 5] S. -Y. Chung, T. J. Richardson, and R. Urbanke, "Analysis of Sum-Product Decoding of Low-Density Parity-Check Codes Using a Gaussian Approximation," IEEE Trans. Inform. Theory, vol. 47, No. 2, pp. 657-670, Feb. 2001.

Since the conventional method of generating a check matrix for an LDPC code is performed as described above, it is about 6 when the minimum value (called an inner diameter) of the cycle of the check matrix is large (6 in FIGS. 2 and 3). The larger the cycle of, the larger the hamming distance of the codeword, and the general analysis results show that the characteristics of the sum-product decoding method are good, resulting in insufficient performance of error correction capability. .

SUMMARY OF THE INVENTION The present invention has been made to solve the above-described problems. The present invention provides a check matrix for Irregular-LDPC codes that is deterministic, stable in characteristics, good in error correction, and corresponding to various ensembles, code lengths, and coding rates. An object of the present invention is to obtain a parity check matrix generator for LDPC codes that can be easily generated in a short time, and a communication device equipped with the parity check matrix generator.

Here, "deterministic" means that both the transmission and reception have a common algorithm and lead to the same result with a limited specification. In the present invention, generating a check matrix for an LDPC code with limited specifications such as a coding rate and a code length, etc. It means possible.

An apparatus for generating a parity check matrix according to the present invention includes an information length, encoding rate, and column maximum order input unit for inputting a predetermined information length, a coding rate, and a maximum degree of a column, and an input maximum length of the predetermined information length, coding rate, and column. A pseudo random number substitution matrix parameter calculating unit for calculating a parameter for a pseudo random number substitution matrix described below using a pseudo random number sequence and a Latin square matrix using a pseudo random number sequence and a Latin square matrix by the calculated parameters for the pseudo random number substitution matrix. Optimization of order distribution of test matrix generation configurable using the pseudo random number substitution matrix by using a pseudo random number substitution matrix generation unit for generating a substitution matrix and the inputted predetermined information length, coding rate, and maximum order of columns A parameter for order distribution optimization that calculates a parameter of a combination of possible order distributions for The order distribution optimizer for optimizing the order distribution of the test matrix generation by the density power generation method, with a combination of the calculation unit and the calculated order distribution of the available order distribution, and the optimized order distribution of the test matrix generation And a parity check matrix generator for arranging the generated pseudo random number substitution matrix to generate a parity check matrix for the low density parity check code.

Effect of the Invention According to the present invention, it is possible to easily generate a check matrix for Irregular-LDPC codes corresponding to various ensembles, code lengths, and code rates in a short time, which is deterministic, stable in characteristics, and has good error correction capability. Can be obtained.

1 is a diagram showing a parity check matrix for a conventional LDPC code;

2 is a diagram showing the configuration of Euclidean geometric symbols EG (2, 2 ² ),

3 is a diagram showing an example in which the order of the columns of the Euclidean geometry code is regularly separated from 4 to 2,

4 is a block diagram showing the configuration of an LDPC encoding / decoding system;

5 is a block diagram showing the structure of a parity check matrix generating apparatus according to Embodiment 1 of the present invention;

6 is a flowchart showing the flow of processing by the parity check matrix generating apparatus according to Embodiment 1 of the present invention;

7 is a block diagram showing the structure of a parity check matrix generating apparatus according to Embodiment 2 of the present invention;

8 is a flowchart showing the flow of processing in the parity check matrix generating apparatus according to Embodiment 2 of the present invention;

9 shows bit error rate characteristics and frame error rate characteristics for a signal power to noise power ratio per information bit;

10 is a block diagram showing the structure of a parity check matrix generating apparatus according to Embodiment 3 of the present invention;

11 is a flowchart showing the flow of processing by the parity check matrix generating apparatus according to Embodiment 3 of the present invention;

12 is a block diagram showing the structure of a parity check matrix generating apparatus according to Embodiment 4 of the present invention;

13 is a flowchart showing the flow of processing by the parity check matrix generating apparatus according to Embodiment 4 of the present invention;

14 is a diagram illustrating an example of an ensemble of a multi-edge type;

15 is a diagram illustrating an example of an irregular LDPC code;

16 is a diagram illustrating an example of a parity check matrix constructed according to the order distribution of FIG. 15;

17 is a diagram showing an example of order distribution of an irregular LDPC code used for evaluation;

18 is a diagram illustrating frame error rate characteristics of an irregular LDPC code;

19 is a block diagram showing the structure of a parity check matrix generating apparatus according to a fifth embodiment of the present invention;

20 is a block diagram showing the construction of a communication device according to a sixth embodiment of the present invention.

EMBODIMENT OF THE INVENTION Hereinafter, in order to demonstrate this invention in detail, the best form for implementing this invention is demonstrated according to attached drawing. In addition, this invention is not limited by this Example.

(Example 1)

First, before describing the method of generating the parity check matrix for the LDPC code of the first embodiment, the positioning of the encoder and the decoder using the generated parity check matrix for the LDPC code, and the conventional check for the "Irregular-LDPC code" The matrix generation method will be described.

4 is a block diagram showing the configuration of an LDPC encoding / decoding system. In FIG. 4, the communication apparatus on the transmission side includes an encoder 101 and a modulator 102, and the communication apparatus on the reception side includes a demodulator 104 and a decoder 105. In FIG. Here, the flow of encoding and decoding in the case of using the generated parity check matrix for the LDPC code will be described.

In the communication apparatus on the transmission side, as described later, the parity check matrix H generated by the parity check matrix generation device for the LDPC code is used. The encoder 101 then obtains a generation matrix G based on the following conditions.

G: K × N matrix (K is information length, N is code length)

GH ^T = 0 (T is transpose)

After that, in the encoder 101, the message of information length K (u _1). u ₂ ... u _K ) is generated and a sign word C is generated using the generation matrix G.

C = (u ₁ u ₂ … u _K ) G

= (c ₁ c ₂ … c _N ), where H (c ₁ c ₂ … c _N ) ^T = 0)

The modulator 102 then transmits the generated code word C by digital modulation such as BPSK, QPSK, and multivalued QAM.

However, in the case of the encoder 101, the generation matrix G must be generated from the test matrix H by the Gaussian elimination method or the like, and the test matrix H has a low density, whereas the generation matrix G is relatively high density, Since the ratio of 1 " is large, there is a problem that a large amount of memory for storing the generation matrix G is also required.

In order to solve this problem, the method which sets it as the structure containing the matrix of a lower triangular structure (or an upper triangular structure) in the test matrix H is proposed by the following literature.

M.Rashidpour and S.H.Jamali, "Low-Density Parity-Check Codes with Simple Irregular Semi-Random Parity Check Matrix for Finite-Length Applications," pp 439-443, in proc. IEEE PIMRC 2003.

Now let T be the matrix of lower triangles of M × M, MMZ _{> 0} as shown below. Where Z _{> 0} is the set of whole positive integers.

The binary M × N, N∈Z _{> 0} , and matrix H = [h _{i, j} ] composed of elements h _{i, j} in row _i, column _j are shown below.

Here, H is assumed to be a matrix of M × N. A _{M × A} is an arbitrary binary M × K, K = NM matrix.

If the organization code word vector C is C = (u ₁ , u ₂ , ..., u _K , p ₁ , p ₂ , ..., p _M ), this code word vector C satisfies H.C ^T = 0, When the information message u = (u ₁ , u ₂ ,..., U _K ) is applied, the encoder 101 generates a parity element by the following equation.

According to this procedure, since encoding can be easily realized without using the generation matrix G, the present invention is subject to the construction of the parity check matrix H including the matrix of the lower triangular structure.

On the other hand, the communication apparatus on the receiving side receives information on the required specifications from the communication apparatus on the transmitting side in advance and generates a test matrix, and the demodulator 104 receives a modulation signal received through the communication path 103. , BPSK, QPSK, multi-valued QAM, and the like, and the decoder 105 performs iterative decoding by the "sum-product algorithm" on the LDPC-coded demodulation result using the generated test matrix. Outputs an estimation result (corresponding to the original u ₁ u ₂ ... U _K ).

Next, the conventional parity check matrix generation method for "Irregular-LDPC code" theoretically interpreted by the said nonpatent literature 5 is demonstrated in detail. Here, the sum-product decoding method is performed by iteratively calculating the probability density function of the logarithmic likelihood ratios (LLRs) of the inputs and outputs of the decoder 105 in accordance with the decoding process of the sum-product decoding method. The ensemble of the order of good rows and columns is obtained by using a method called density power generation method which analyzes the decoding characteristics of and a Gaussian approximation method which is an approximation method.

In addition, the calculation is simplified because the logarithmic likelihood ratio (LLR) of the input and output of the density generation method and the decoder 105, which is a check matrix generation method for the LDPC code described in Non-Patent Document 5, can approximate a Gaussian distribution. In the Gaussian Approximation, as a premise, each column is defined as a variable node, and each row is defined as a check node, using a representation of a test matrix as a Tanner graph. In addition, when there is "1" at the intersection of an arbitrary column and an arbitrary row, it is assumed that the variable node and the check node are connected by an "edge".

First, the LLR message propagation from the check node to the variable node is analyzed. On the condition that 0 <s <∞ and 0≤t <∞, the following function (1) is defined. However, s = m _u0 is an average value of u0, u0 is an ensemble average of the logarithmic likelihood ratios (LLRs) of signals received via a transmission path including Gaussian noise having a variance value σ _n ² , and t is a predetermined repetition. The ensemble average of the LLR outputs of the check nodes at the time of.

Λ _i and p _i represent the ratios of the edges belonging to the variable node of the order i and the check node, respectively. In addition, d ₁ is the order of the maximum variable node, d _r is the order of the maximum check node. In addition, [lambda] (x) and [rho] (x) are order distributions of the variable node and the check node, respectively (the number of &quot; 1 &quot; in each one row and each column of the barrier and check nodes is expressed as an order). The generation function of is shown, and can be represented as following formula (2) and (3).

In addition, ((x)) of said Formula (1) is defined like following formula (4).

Here, R represents the whole real number set, u represents the ensemble average of the LLR output of the variable node.

In addition, said (1) Formula can be represented equivalently to following (5) Formula.

In addition, t ₁ is an ensemble average of the LLR output values of the check nodes at the first iteration time point.

Here, the condition for obtaining the threshold of the SNR that can be zero error is that t ₁ (s) → ∞ (expressed as R ⁺ ) when 1 → ∞, in order to satisfy this condition, It is necessary to satisfy the following condition (6).

t <f (s, t), all t∈R⁺ … (6)

Next, the LLR message propagation from the variable node to the check node is analyzed. On the condition that 0 <s <∞ and 0 <r≤1, equation (7) of the following function is defined. In addition, the initial value r ₀ of r is (phi) (s).

In addition, said Formula (7) can be equivalently represented by following formula (8).

Here, the condition for obtaining the threshold of the SNR that can cause the error to be 0 is r ₁ (s) → 0. To satisfy this condition, the following condition (9) is satisfied. There is a need.

r> h (s, r), all r∈ (0, φ (s))... (9)

Moreover, in the said nonpatent literature 5, the optimum order of a variable node and a check node is searched using the said formula (Gaussian approximation method of a density generation method).

[ST101]

Assuming that the generation function λ (x) of the order allocation of the variable node and the Gaussian noise σ _n are applied, and that the coding rate is maximized using the generation function ρ (x) of the order allocation of the check node as a variable, Search. The constraint condition in this search is to normalize ρ (1) = 1 and satisfy the above expression (6).

[ST102]

Assuming that the generation function ρ (x) of the order distribution of the check node and the Gaussian noise σ _n are applied (for example, a value obtained from the result of ST101), the generation function λ (x) of the order distribution of the variable node is converted into a variable. The point where the coding rate is maximized is searched. The constraint condition in this search is to normalize λ (1) = 1 and satisfy the above expression (9).

[ST103]

In order to obtain the maximum coding rate, the above steps ST101 and ST102 are executed repeatedly, and better than the generation function? (X) of the order distribution of the variable node and the generation function? (X) of the order distribution of the check node. Search for ensembles with linear programming.

[ST104]

The signal power is normalized to 1 from the Gaussian noise sigma _n, and the threshold of the SNR at which the error can be zero is obtained from the following expression (10).

However, in the said nonpatent literature 5, the test matrix obtained by the maximum value of a coding rate becomes fluid, and there exists a problem that the coding rate fixed as a specification at the time of design fluctuates. Further, in the non-patent document 5, the derivation of the generation function? (X) of the order allocation of the variable node and the derivation of the generation function ρ (x) of the order allocation of the check node are repeatedly performed for a predetermined number of times. Another problem is that a certain amount of time is required for search processing, and another problem is that it cannot easily cope with various ensembles, code lengths, and coding rates.

In the first embodiment, therefore, a method for easily searching for the parity check matrix for the "Irregular-LDPC code" corresponding to the deterministic, stable, and various ensembles, code lengths, and code rates in a short time will be described. do.

Fig. 5 is a block diagram showing the structure of a parity check matrix generation device for LDPC codes according to the first embodiment of the present invention. The test matrix generator includes an information length, coding rate, and column maximum order input unit 11, a parameter calculator 12 for pseudo random number substitution matrix, a pseudo random number substitution matrix generator 13, and a parameter calculator for order distribution optimization. (14), the order distribution optimization unit 15 and the parity check matrix generating unit 16 are provided. This check matrix generating device is mounted in the communication device on the transmitting side and the receiving side in FIG. 4, and may output the generated check matrix to the encoder 101 and the decoder 105, and the communication device on the transmitting side and the receiving side. It may be provided outside, and the generated check matrix may be stored in a memory (not shown) in the communication device on the transmitting side and the receiving side and output to the encoder 101 and the decoder 105.

6 is a flowchart showing the flow of processing by the parity check matrix generating apparatus according to the first embodiment of the present invention. In step ST11, the information length, coding rate, and column maximum order input unit 11 inputs a predetermined information length, coding rate, and maximum order of columns. In step ST12, the pseudo random number substitution matrix parameter calculating unit 12 calculates parameters for the pseudo random number substitution matrix by using the predetermined information length, coding rate, and maximum order of the columns input in step ST11.

In step ST13, the pseudo random number substitution matrix generation unit 13 generates a pseudo random number substitution matrix using a pseudo random number sequence and a Latin square matrix by the parameters for the pseudo random number substitution matrix calculated in step ST12. In step ST14, the parameter distribution optimization parameter calculation unit 14 generates a test matrix configurable using a pseudo random number substitution matrix by using the predetermined information length, coding rate, and maximum order of columns input in step ST11. Calculate the parameters of the combination of possible order distributions for the optimization of the order distribution.

In step ST15, the order distribution optimization unit 15 optimizes the order distribution of the test matrix generation by the density power generation method by using the combination of the possible order distributions calculated in the above step ST14 as constraint conditions. In step ST16, the parity check matrix generation unit 16 generates the parity check matrix for the LDPC code by arranging the pseudo random number substitution matrix generated in step ST13 by the order distribution of the parity check matrix generation optimized in step ST15. .

Next, the detailed processing of steps ST11 to ST16 in the flowchart of FIG. 6 will be described.

In step ST11, the information length, encoding rate, and column maximum order input unit 11 is a predetermined information length, coding rate, and maximum order of columns, and the information length K = 144 preset in the system and coding rate = 0.5 , Enter the maximum order d = 4 for the column.

In step ST12, the parameter calculation unit 12 for the pseudorandom number substitution matrix uses p ² x p ² by using the information length K = 576, coding rate = 0.5, and maximum order d = 4 of the column input in step ST11. The parameter p for the pseudo random number substitution matrix SP of (p + 1 is prime) is calculated as follows.

Number of row directions of pseudo random number substitution matrix SP = d = 4

Number of columns N (= code length N) of the test matrix H = K / rate

= 144 / 0.5 = 288

The number of rows in the check matrix H M = N × (1-rate)

= 288 × 0.5 = 144

Size of the pseudorandom substitution matrix SP p ² = M / d = 144/4 = 36

Thus p = 6

In step ST13, the pseudo random number substitution matrix generation part 13 shows in the procedure of steps ST13-1 to ST13-6 shown below by the parameter p for the pseudo random number substitution matrix SP computed in said step ST12. As shown, a pseudo random number substitution matrix SP of p ² × p ² (p + 1 is prime) is generated using a pseudo random number sequence and a Latin square matrix.

In the encoding / decoding using the LDPC code, generally, the smaller the number of cycles with smaller check matrices such as "cycle 4" and "cycle 6" on the two-part graph in the Tanner graph, the better characteristics can be obtained. Therefore, as the LDPC code, a structure that suppresses the generation of small cycles such as "cycle 4" or "cycle 6" is preferable, and the pseudo random number substitution matrix generation unit 13 is a pseudo that suppresses the generation of small cycles by the check matrix. Generate a random substitution matrix SP.

[Step ST13-1]

Pseudo random number series C (i) defined by the following equation is generated.

C (1) = 1, C (i + 1) = G ₀ × C (i) mod P, i = 1, 2,... , P-2

Where P is a prime number where P = p + 1, and C ₀ is the source of GF (P). In addition, successive powers of G _{0 that} are elements of GF (P) (eg, G ₀ ¹ , G ₀ ² ,..., G ₀ ^P-1 = 1) represent all elements that are not zero of GF (P). In this case, G ₀ is called the primitive source. This series C (i) is a pseudorandom series with nonuniform differences between elements and no overlapping elements.

As an example it is shown below for the case of _{P = 7, G 0 = 3} .

[ST13-2]

The substitution pattern LB _j (i) shown in the following formula for the pseudo random number series C (i) is generated.

By this operation, when LB _j (i) is expressed by a matrix of i rows and j columns, each element in each row and each element in each column can form a different Latin square.

An example is shown below.

[ST13-3]

A Latin square matrix L _j (q, l) having a pseudorandom number series and its substitution pattern as an element is generated by the following equation.

By this _{operation, L j (q, l)} L 1 (q, l) _{using, L 2 (q, l)} , ... We can generate p different Latin square matrices of, L _p (q, l).

An example is shown below.

As you can see from this example, if you list each element of L _j (q = 1, l) for q = 1 as follows, each element in each row and each element in each column is a different Latin square matrix. It can be seen that.

Similarly q = 2,... With respect to, p, it is a Latin square even if we look at the matrix of the j row l column which arranges each element of L _j (q, l).

[ST13-4]

A basic substitution matrix pattern BP _j (q, l) is generated using the Latin square matrix L _j (q, l) and the parameter p by the following equation.

By this operation, a basic substitution matrix pattern for generating a pseudo-random substitution matrix of column order 1 and row order 1 of p ² × p ² can be generated.

BP _j (q, l) is a q-row i-column matrix for any _j of L _j (q, l), which is added to each element within that row by p for each increment of each row. .

An example is shown below.

From the discussion in the previous step (3), the matrix of j rows and l columns that lists each element of BP _j (q, l) for any q is also Latin square. Moreover, by this operation, the distance between elements of the same column of the matrix of q rows l columns generated from BP _j (q, l) for arbitrary j is widened.

[ST13-5]

A plurality of basic substitution series SP _{j , s} (i) obtained by shifting the starting point of the basic substitution matrix pattern BP _j (q, l) by s by the following equation is generated.

By this operation, a basic substitution sequence for generating a pseudo substitution matrix of column order 1 and row order 1 of p ² × p ² can be generated.

The distance between adjacent elements of this series is widening. By enlarging the distance between adjacent elements, it is possible to suppress the occurrence of short cycles, that is, cycles 4 and 6, occurring between the lower triangular matrix of T described in the first embodiment.

An example is shown below.

[ST13-6]

From a plurality of basic substitution series SP _{j , s} (i), a plurality of binary p ² xp ² pseudo random random substitution matrices SP _{j , s} = (h _{m , n} ) defined by the following equation are generated.

By this operation, a plurality of pseudo random number substitution matrices of column order 1 and row order 1 of p ² × p ² can be generated. The SP _j, equal to the value of s in _s, is a matrix that is the value of j consists of a combination of a plurality of different SP _{j, s,} a case that two or more that match the number of columns with a "1" on each row Since there is no cycle 4, the minimum number of cycles is six. In addition, even when the value of _s in a plurality of SP _{j , s} is different, there is a combination which does not become cycle 4, and this combination can be obtained by searching or the like.

An example is shown below.

In step ST14, the order distribution optimization parameter calculating unit 14 uses a pseudo random number substitution matrix, using a predetermined information length K, a coding rate, and a maximum order d of columns input in the step ST11. Calculate the parameters of a combination of possible order distributions for optimization of order distributions of matrix generation. Here, the combination of order distribution which can be taken is computed based on the constraint of the largest order d of a column, and the test matrix containing a lower triangular matrix.

From the maximum order d of the target column, the information length K, and the code rate, the constraints of the parity check matrix H as shown in the following equation are obtained.

Here, sp means any sp _{j , s} . In addition, the continuation of 배치 arrange | positioned on a diagonal line means that 1 is arrange | positioned like step T through T from the top row to the bottom row of H.

Constraints determined here are the size of the pseudo random number substitution matrix SP, its maximum number of arrangements, and its location.

As an example, the case of information length K = 144, coding rate = 0.5, and the maximum order d = 4 of a column is shown below.

Number of row directions of pseudo random number substitution matrix SP = d = 4

Number of columns N (= code length N) of the test matrix H = K / rate

= 144 / 0.5 = 288

The number of rows in the check matrix H M = N × (1-rate)

= 288 × 0.5 = 144

Size of the pseudorandom substitution matrix p ² = M / d = 144/4 = 36

Thus p = 6

Maximum number of pseudorandom substitution matrices SP of information length part

= N × rate / p ² = 288 × 0.5 / 36 = 4

From these results, 3 + 2 + 1 pseudo random number substitution matrix SP can be arrange | positioned with respect to the test matrix H from the left end at 4 * 4 pseudo random number substitution matrix SP and the left / low triangle of the right side of the test matrix H.

Under the constraints of the test matrix including the maximum order and the lower triangular matrix, a combination of possible order distributions is calculated. The order distribution indicates, for example, the ratio of the total number of columns of the column order 4 to the number of columns of the test matrix, and the pseudo random number substitution matrix (column weight 1, row weight 1) in the column direction so as to be the column order 4 according to the ratio. Four combinations should be written. Similarly, the row order is executed. For example, in the above example, the ratio of column weight 4 to the number of columns of the entire test matrix H using the pseudo random number substitution matrix is 0 to 4/8, and the ratio of column weight 3 to 0 to 5/8. It becomes The combination of these column orders and row orders and the ratios that can be taken is output as a parameter for optimization of the order distribution executed in the next step ST15.

In step ST15, the order distribution optimization unit 15 sets the order distribution of the test matrix generation by the density power generation method as shown below, with the combination of the possible order distributions calculated in step ST14 as the constraint condition. To optimize. Here, the optimum order distribution is calculated among the combinations of the order distributions obtained in step ST14. Here, the degree distribution indicates, for example, what percentage of the entire test matrix is the column number of column order 4, and the pseudo random number substitution matrix (column weight 1, row weight 1) is columned so as to be column order 4 according to the ratio. Four combinations in the direction are written. Accordingly, the parity check matrix can be generated in the next step ST16.

In step ST15, the arbitrary random number substitution matrix SP in the parity check matrix H obtained in the step ST14, and the maximum random number and the location constraints are restricted at the position of the pseudo random number substitution matrix SP in the parity check matrix H. Arrangement of the pseudo random number substitution matrix SP, or its location allows the selection of the combination to be made under the condition of arranging an O matrix of p ² × p ² .

Next, using an optimization in the Gaussian approximation of the density generation method, an ensemble (order allocation) of "Irregular-LDPC code" based on the required coding rate is obtained.

The generation function λ (x) of the column order distribution and the generation function ρ (x) of the order distribution of the rows are treated simultaneously as variables, and the optimal generation function λ (x) and the linear programming method are applied so that the Gaussian noise σ _n is maximized. Search for the generation function ρ (x) (see equation (11) below). The constraint condition in this search satisfies the following expression (12).

At this time, the possible values of the variables of the generation function λ (x) of the order distribution of the columns and the generation function ρ (x) of the order allocation of the rows are only values calculated by the constraints of the test matrix H.

r> h (s, r), all r∈ (0, φ (s))

Further, s is a mean value of the logarithmic likelihood ratios (LLR) of signals received through a Gaussian communication path, and a two-value signal of {-1, 1} is output as a transmission signal, and s = 2 / σ _n ² . It can calculate by

As described above, since the generation function λ (x) and the generation function ρ (x) satisfying the predetermined conditions are obtained by one linear programming method, the derivation and generation function of the generation function λ (x) is obtained as in Non-Patent Document 5. It is possible to generate an ensemble that is decisive and stable in a shorter time and easier than the method of repeatedly calculating the optimum value of both by calculating ρ (x).

In step ST16, the parity check matrix generator 16 arranges the pseudo random number substitution matrix SP generated in step ST13 as shown below by LDPC by the order distribution of the parity check matrix generation optimized in step ST15. Create a check matrix for the sign. That is, here, the arrangement of the pseudo random number substitution matrix SP in the parity check matrix H is determined based on the order distribution obtained in step ST15.

In determining the arrangement and parameters of the SP _{, the} combination without occurrence of short cycles such as cycles 4 and 6 is determined by searching for by adjusting j and s of SP _{j , s} . SP _{j , s} is a different pseudo-random substitution matrix by changing j and s, and cycle 4 or 6 generation due to the combination is inherently difficult to occur. It can be mentioned as.

As described above, according to the first embodiment, a check matrix for Irregular-LDPC codes corresponding to deterministic, stable characteristics, good error correction capability, and various ensembles, code lengths, and code rates can be easily obtained in a short time. The effect that it can produce is obtained.

(Example 2)

Next, the first embodiment will be expanded and a method of generating a parity check matrix of a rate comapatible (RCPC) -LDPC code compatible with a plurality of coding rates (the information length does not change and only the code rate changes) will be described.

Fig. 7 is a block diagram showing the structure of a parity check matrix generation device for LDPC codes according to the second embodiment of the present invention. The parity check matrix generating apparatus includes an information length, coding rate, and column maximum order input unit 21, a parameter calculation unit 22 for pseudorandom number substitution matrix, a pseudo random number substitution matrix generator 23, and a parameter distribution optimizer for order distribution optimization. (24), the order distribution optimization unit 25 and the parity check matrix generating unit 26 are provided. This check matrix generating device is mounted in the communication device on the transmitting side and the receiving side in FIG. 4, and may output the generated check matrix to the encoder 101 and the decoder 105, and the communication device on the transmitting side and the receiving side. It may be provided outside, and the generated check matrix may be stored in a memory (not shown) in the communication device on the transmitting side and the receiving side and output to the encoder 101 and the decoder 105.

8 is a flowchart showing the flow of processing by the parity check matrix generating apparatus according to the second embodiment of the present invention. In step ST21, the information length, coding rate, and column maximum order input unit 21 inputs a maximum order of columns of a predetermined information length, a plurality of coding rates, and a maximum coding rate excluding uncoding. In step ST22, the pseudo random number substitution matrix parameter calculating unit 22 substitutes pseudorandom number numbers using the maximum order of columns of a predetermined information length, a plurality of coding rates, and a maximum coding rate excluding unsigned, input in step ST21. Compute the parameters for the matrix.

In step ST23, the pseudo random number substitution matrix generation unit 23 generates a pseudo random number substitution matrix using a pseudo random number sequence and a Latin square matrix by the parameters for the pseudo random number substitution matrix calculated in step ST22. In step ST24, the order distribution optimization parameter calculating unit 24 uses pseudo-random number substitution by using the maximum order of the columns of the maximum information rate excluding a predetermined information length, a plurality of code rates, and no coding input in the step ST21. The matrix is used to calculate the parameters of a combination of possible order distributions for optimization of the order distribution of the configurable test matrix generation.

In step ST25, the order distribution optimization unit 25 sets the order distribution of the test matrix generation for the plurality of coding rates by the density generation method, with the combination of the possible order distributions calculated in step ST24 as constraint conditions. Optimize. In step ST26, the parity check matrix generator 26 arranges the pseudo random number substitution matrix generated in step ST23 for the LDPC code by order distribution of the parity check matrix generation for the plurality of coding rates optimized in step ST25. Create a check matrix of.

Next, detailed processing of steps ST21 to ST26 in the flowchart of FIG. 8 will be described.

In step ST21, the information length, coding rate, and column maximum order input unit 21 inputs a predetermined information length K, a plurality of code rates R (l), and a maximum order d of columns of maximum coding rate excluding uncoding. Here, in a plurality of coding rates R (l), l = 1, 2,... , 0 <R (1) <R (2) <.. Let it be <1. This step ST21 differs from the step ST11 of the first embodiment in that a plurality of code rates R (l) and a maximum order d of columns of the maximum code rate excluding unsigned are input.

Among the input code rates R (l), the number of rows of the parity check matrix H _{R (max-1)} for the largest code rate R (max-1) is b, and the number of columns = code length is N. Here, R (max) = 1 means unsigned, and shall not be used in this description.

In step ST22, the parameter calculation unit 22 for the pseudorandom number substitution matrix is the maximum order of the predetermined information length K, the plurality of code rates R (l), and the maximum code rate column except for the unsigned inputted in step ST21. Using d, the parameters for the pseudo random number substitution matrix are calculated as shown below.

Number of columns N (= code length N) of test matrix H = K / R (l)

The number of rows in the check matrix H M = N-K

Next, the size p ² of the pseudo random number substitution matrix is obtained from the maximum order d (value previously set by the system) of the columns of the coding rate R (max-1) as follows.

p ² = M / d

For example, if K = 864, R (max-1) = R (3) = 2/3, d = 3,

N = K / R (3) = 864 / (2/3) = 1296

M = N-K = 1296-864 = 432

p ² = M / d = 432/3 = 144

Therefore, p = 12.

In step ST23, the pseudo random number substitution matrix generator 23 performs the same processing as that in step ST13 that the pseudo random number substitution matrix generator 13 of the first embodiment executes. That is, the pseudo random number substitution matrix generation part 23 performs the process of step ST13-1-step ST13-6.

In step ST24, the parameter distribution optimization parameter calculation unit 24 determines a predetermined information length K, a plurality of code rates R (l) input in the step ST21, and a maximum order d of columns of the maximum code rate excluding unsigned. Using this, as shown below, a parameter of the combination of possible order distributions for the optimization of the order distribution of the configurable check matrix generation using the pseudo random number substitution matrix is calculated.

For example, in step ST21, information length K = 864, a plurality of coding rates R (1) = 1/3, R (2) = 1/2, R (3) = 2/3, maximum coding excluding uncoding It is assumed that the maximum order d = 3 of the row of the rate R (3) is entered. Here, among the plurality of code rates R (1), the number of rows and columns of the parity check matrix corresponding to the highest code rate R (3) = 2/3 is set to M ₃ and N ₃ . Further, in step ST22, and the _{M 3 = M, N 3 =} N, there are p = 12 is obtained. Assuming that the number of rows and columns of the check matrix is M ₂ and N ₂ from the code rate R (2) = _1/2 , and the information length K is not changed,

Hydrothermal N ₂ = K / R (2) = 864 / (1/2) = 1728,

Number of rows M ₂ = N ₂ × (1-R (2)) = 1728 × (1/2) = 864

It becomes Similarly, assuming that the number of rows and columns of the parity check matrix is M ₁ and N ₁ from the code rate R (1) = 1/3, and the information length K does not change,

Hydrothermal number N ₁ = K / R (1) = 864 / (1/3) = 2592,

Number of rows M ₁ = N ₁ × (1-R (1)) = 2592 × (2/3)

= 1728

It becomes With respect to the number of rows M ₁ = 1728, 12 pseudo random number substitution matrices SP of p ² × p ² = 144 × 144 can be arranged in the row direction, and from K = 864, a pseudo random number substitution matrix is provided in the information length part of the column direction. 12 SPs can be arranged. From these results, 12 x 6 p ² x p ² = 144 x 144 pseudo random number substitution matrix SP from the left end with respect to the test matrix H for executing the coding rate of R (1), and the left side of the right side of the test matrix H. 11 + 10 + in the lower triangular part; +1 pseudo-random substitution matrix SP can be arranged. This parity check matrix can also constitute R (2) and R (3) in the manner described in the next step ST25.

In step ST25, the degree distribution optimization unit 25 checks a plurality of coding rates by the density generation method as shown below, using the combination of the order distributions calculated in step ST24 as constraint conditions. Optimize the order distribution of matrix generation.

Let F ₂ = {0, 1} as a binary finite body. Let the code word C⊂F ₂ ^N be set, and let H = (h _ij ) be the parity check matrix of M × N corresponding to C. The code word C consists of a sequence x of length N bits satisfying M binary parity check bits defined by the parity check equation of the parity check matrix Hx = 0. Assuming that matrix H is full rank, the number of information bits is K = NM and the coding rate is R = K / N.

In addition, let H _{R (j ) be} the parity check matrix of the LDPC code C _{R (l)} having a variable coding rate. Where R (l) is the coding rate, where R (l), l = 1, 2,... , max 0 <R (1) <R (2) <… <R (max) = 1 (R (max) = 1 means no sign). In addition, let H _{R (max-1) be} an N × N parity check matrix for C _{R (max-1)} . H _{R (max-2)} is represented by the following equation consisting of H _{R (max-1)} , an M matrix of M × l and an additional parity check matrix A _{R (max-2)} of t × (N + t). A parity check matrix of (M + t) × (N + t) is defined.

( H _{R (max-1)} and H _{R (max-2)} are both full rank)

If this is expressed as a picture, it becomes as follows.

If you generalize this,

( H _{R (l)} is full rank)

Where t _i is the number of _columns of H _{R (i)} and H _{R (i + 1)} And the number of rows.

By a Gaussian approximation of the density Development Act for the design of H _{R (i)} all _{H R (i), l =} 1,2, ... , optimize the order distribution of max-1 simultaneously. The optimization problem is shown below.

를 최소화하도록 하는 H _R(i)의 차수 배분을 구한다. Here,

Find the order distribution of H _{R (i)} to minimize.

Here, the difference between the SNR of the repetition threshold of H _{R (i)} estimated by the GAP _{R (l)} Gaussian approximation and the Shannon limit is expressed in dB, and is expressed by the following equation.

,

,

및 E는 각각 부호화율 R(l)의 때의 SNR의 섀논 한계, 가우스 통신로의 노이즈의 분산값, 및 가우스 통신로를 통해 수신한 신호의 대수 우도비(LLR)의 평균값 및 신호의 에너지이다. here

,

,

And E are the Shannon limit of the SNR at the code rate R (l), the variance of the noise of the Gaussian channel, and the mean value of the logarithmic likelihood ratio (LLR) of the signal received via the Gaussian channel and the energy of the signal, respectively. .

For each of these coding rates, under the condition of equation (18), using the GAP _{R (l)} and (14) equations,

Obtain

R (l) = 1-M ₁ / N ₁ = 1/3, R (2) = 1-M ₂ / N ₂ = 1/2, R (3) = 1-M ₃ / N used in step ST24 above _{For 3} = 2/3, the correspondence with the variables used in the explanation is as follows.

M ₃ = M, N ₃ = N, M ₂ = M ₃ + t, N ₂ = N ₃ + t,

M ₁ = M ₂ + t, N ₁ = N ₂ + t

In step ST26, the parity check matrix generator 26 arranges the pseudo random number substitution matrix generated in step ST23 according to the order distribution of the parity check matrix generation for the plurality of coding rates optimized in step ST25, and shows the following. A check matrix for the LDPC code as described above is generated.

For example, R (1) = 1-M ₁ / N ₁ = 1/3, R (2) = 1-M ₂ / N ₂ = 1/2, R (3) = 1-M ₃ / N ₃ = 2 For / 3, the following check matrix is generated according to the order distribution obtained in step ST25.

Next, the characteristics of the LDPC code described above are compared.

FIG. 9 shows the bit error rate (BER) characteristic and the frame error rate (FER) of signal power to noise power ratio (Eb / No) per bit information of the LDPC code using the test matrix generated by the test matrix generator according to the second embodiment. ) Is a diagram showing characteristics. Here, the information length is 1536 bits, the communication path AWGN, and the maximum number of repetitions is 200 times. The decoding method is a "sum-product algorithm". This characteristic uses the parity check matrix of the RC-LDPC code generated according to the procedure of the second embodiment using the parameters M ₁ to M ₃ and N ₁ to N _{3 shown below} . In this test matrix, R (1) = 1-M ₁ / N ₁ = 1/3, R (2) = 1-M ₂ / N ₂ = 1/2, R (3) = 1-M ₃ / N ₃ = 2/3.

On the other hand, the SNRs of the Shannon limits at R (1) = 1/3, R (2) = 1/2, and R (3) = 2/3 are -0.4954 (dB), 0.1870 (dB) and 1.0595 ( dB), and each difference is approximately 1.8 (dB), 1.7 (dB), 1.45 (dB) at BER = 10 ^-4 points, and RC- approaching the Shannon limit despite being not very long with an information length of 1536 bits. LDPC code can be realized.

As described above, according to the second embodiment, the same effects as those of the first embodiment can be obtained. In addition, in the first embodiment, a check matrix must be generated for each coding rate. Finally, only one kind of check matrix is prepared, and the effect that the check matrix can be easily generated can be obtained.

(Example 3)

Fig. 10 is a block diagram showing the structure of a parity check matrix generating apparatus for LDPC codes according to the third embodiment of the present invention. The test matrix generator includes an information length, coding rate, and column maximum order input unit 31, a parameter calculator 32 for pseudo-random number substitution matrix, a pseudo random number substitution matrix generator 33, and a parameter calculator for order distribution optimization. 34, an order distribution optimizer 35, and a parity check matrix generator 36 are provided. This check matrix generating device may be mounted in the communication device on the transmitting side and the receiving side in FIG. 4, and may output the generated check matrix to the encoder 101 and the decoder 105, and the communication device on the transmitting side and the receiving side. It may be provided outside, and the generated check matrix may be stored in a memory (not shown) in the communication device on the transmitting side and the receiving side and output to the encoder 101 and the decoder 105.

Fig. 11 is a flowchart showing the flow of processing by the parity check matrix generating apparatus according to the third embodiment of the present invention. In step ST31, the information length, coding rate, and column maximum order input unit 31 inputs a predetermined information length, coding rate, and maximum order of columns. In step ST32, the pseudo random number substitution matrix parameter calculating unit 32 uses the predetermined information length, coding rate, and maximum order of columns input in step ST31 to generate the first and second pseudorandom substitution matrices described later. Calculate the parameter.

In step ST33, the pseudo random number substitution matrix generation unit 33 uses a pseudo random number sequence and a Latin square matrix as a parameter for the first and second pseudo random number substitution matrices calculated in step ST32, to form a first pseudo random number. A substitution matrix is generated, and further, the first pseudo random number substitution matrix is further compressed in a row direction to generate a second pseudo random number substitution matrix. In step ST34, the parameter distribution optimization parameter calculation unit 34 is configured by using the first and second pseudorandom number substitution matrices using the predetermined information length, coding rate, and maximum order of columns input in step ST31. Calculate the parameters of the combination of possible order distributions for optimization of the order distribution of possible test matrix generations.

In step ST35, the order distribution optimization unit 35 optimizes the order distribution of the test matrix generation by the density power generation method by using the combination of the possible order distributions calculated in the above step ST34 as constraint conditions. In step ST36, the parity check matrix generation unit 36 arranges the first and second pseudo random number substitution matrices generated in step ST33 according to the order distribution of the parity check matrix generation optimized in step ST35 for LDPC code. Create a check matrix.

Next, detailed processing of steps ST31 to ST36 in the flowchart of FIG. 11 will be described.

In step ST31, the information length, encoding rate, and column maximum order input unit 31 is a predetermined information length, a coding rate, and a maximum order of columns, and the information length K = 120 and coding rate rate = 0.5 previously set in the system. , Enter the maximum order of columns d = 16.

In step ST32, the parameter calculation unit 32 for the pseudorandom number substitution matrix uses the predetermined information length K = 120, the coding rate rate = 0.5, and the maximum order d = 16 of the column input in step ST31, as follows. As shown, the number of rows M of the test matrix H, the number of columns (= code rate) N, and the common parameters for the first and second pseudo-random number substitution matrices (p of the pseudo random number substitution matrix of p · b × p · b and calculate b).

To below the first pseudo-random number BPS _I _{hop, hop} _II BPS, BPS _III _hop, because the maximum number of the row direction of the BPS _hop _IV is 4 (as explained in step ST33-7), the column degree d-4 = 12, which remains By the second pseudorandom number substitution matrix cI _cw , cII _cw , cIII _cw , cIV _cw described in step ST34, cw = 3 is realized. For cw = 3, the number of pseudorandom substitution matrices cI _cw , cII _cw , cIII _cw , cIV _cw = remaining number of orders 12 / cw = 4, four combinations of cI _cw , cII _cw , cIII _cw , cIV _cw Use in the column direction.

Sign length = column of check matrix II N = k / rate = 120 / (1/3) = 360,

The number of rows in the check matrix H M = N * (1-rate) = 360 * (2/3) = 240,

Pseudo-random number substituted size p · b = M / (pseudo-random number permutation matrix of the matrix BPS _hop _I, BPS _hop _II, BPS _hop _III, using the number of BPS _hop _IV + pseudo-random number permutation matrix cI _cw, cII _cw, cIII _cw, cIV _The number of _cw used) = _240/8 = 30. For example, p = 0 and b = 5.

In step ST33, the pseudo random number substitution matrix generation unit 33 performs the first and second pseudo random number substitution matrices calculated in step ST32 as shown in steps ST33-1 to ST33-8 below. A first pseudo random number substitution matrix is generated using a pseudo random number sequence and a Latin square matrix by parameters, and the first pseudo random number substitution matrix is further compressed in a row direction to generate a second pseudo random number substitution matrix.

That is, substituted first pseudo-random number from the p and b obtained in step ST32 matrix BPS _hop _I, BPS _hop _II, BPS _hop _III, BPS _hop _IV and second pseudo-random number permutation matrix cI _cw, cII _cw, cIII _cw, cIV _cw Create

[Step ST33-1]

Produces a pseudorandom sequence C _init (i) defined by the following equation: The _init at this index represents the value of C _init (1), the initial value.

Here, P is a prime number where P> p, and G ₀ is a source of GF (P). In addition, successive powers of G ₀ , which are elements of GF (P) (eg, G ₀ ¹ , G ₀ ² , ..., G ₀ ^{P -1} = 1) are used for all elements that are not zero of GF (P). If present, C ₀ is called the source. This series C _init (i) is a pseudorandom series with non-uniform differences between elements and no overlapping elements.

For example, for P = 7, G ₀ = 3, init = 3,

Next, extract the number greater than p from the elements of C _init (i).

For example, for p = 5

[ST33-2]

A Latin square matrix L _i (q, l) having a pseudorandom number sequence and its substitution pattern as an element is generated by the following equation.

By this operation, a Latin square matrix can be generated using L (q, l).

An example in the case of p = 6 is shown below.

For example, in the case of p = 5, it becomes as follows.

[ST33-3]

A basic substitution matrix pattern BP (q, l) is generated by the following equation.

An example in the case of p = 6 is shown below.

[ST33-4]

The matrix BP _hop (q, i) substituted at regular intervals in row units of the basic substitution matrix pattern BP (q, l) is generated by the following equation. In addition, the hop is set to the interval at which line-by-line substitution is performed.

i) if b and hop are mutually

ii) if b and hop are not mutually

An example in the case of b = 5 and hop = 2 is shown below.

[Step ST33-5]

A basic substitution series BPS _hop (i) is generated from the basic substitution matrix pattern BP _hop (q, i) by the following equation.

By this operation, it is possible to generate a column position vector with respect to the row at the position "1" of the basic substitution matrix for generating a matrix of column order 1 and row order 1 of p · b × p · b.

An example is shown below.

[Step ST33-6]

From the basic substitution series BPS _hop (i), the binary p * b * p * b matrix BPS _hop = (h _{m , n} ) defined by the following formula is generated.

By this operation, a basic substitution matrix for generating a matrix of column order 1 and row order 1 of p · b × p · b can be generated. By the operation so far, a pseudo random number substitution matrix having a large distance between adjacent elements and a nonuniform distance between elements can be generated.

By enlarging the distance between adjacent elements, it is possible to suppress a short cycle occurring between the lower triangular matrix of T described in the first embodiment. Moreover, by making the distance between elements non-uniform, generation | occurrence | production of a short cycle can be suppressed also in the said basic substitution matrix of p * b * p * b. Also, in order to avoid the occurrence of cycle 4, the basic substitution matrix of generated p · b × p · b is confirmed, and if cycle 4 exists, p, b, G ₀ , init, hop are changed to cycle Play by searching for a combination where 4 does not exist. However, in the procedure of this embodiment, cycle 4 is rarely present, and regeneration is rarely required.

An example is shown below.

[Step ST33-7]

From a base substitution matrix BPS _hop generates four kinds of base substitution matrix _hop _I BPS, BPS _II _{hop, hop} _III BPS, BPS _hop _IV of.

i)

All other elements of BPS _hop _I are zero.

ii)

iii)

iv)

Ii), jii), and iv) are rows and columns replaced based on BPS _hop _I, and are all matrices of column order 1 and row order 1 of p · b × p · b. By the combination of these matrices, a matrix of column order 1 × row order 1 to column order 4 × row order 4 can be generated.

By replacing these rows and columns, four different pseudo-random substitution matrices can be generated.

[Step ST33-8]

Next, create a basic substitution matrix larger than column order 1.

Using the basic substitution matrix BPS _hop _I obtained in step ST33-7, a column order cw and a (p · b) × (p · b / cw) pseudo random number substitution matrix cI _cw of row order 1 are generated by the following procedure. . At this time, the column is compressed to 1 / cw, that is, compressed in the row direction.

Here, I is the unit matrix of (p · b / cw) × (p · b / cw).

By the same procedure, the basic substitution matrices cII _cw , cIII _cw and cIV _cw of column order cw and row order 1 are generated using the basic substitution matrices BPS _hop _II, BPS _hop _III and BPS _hop _IV. However, when two or more combinations of cI _cw , cII _cw , cIII _cw , and cIV _cw are listed in the column direction, it is assumed that cycle 4 occurs, so that they are listed in one column only in the row direction.

In step ST34, the order distribution optimization parameter calculating unit 34 uses the predetermined information length, coding rate, and maximum order of columns input in step ST31, as follows, to form the first and second pseudo-random number substitution matrices as follows. Calculate the parameters of the combination of possible order distributions for the optimization of the order distributions of the configurable check matrix generation using

The BPS _hop _I, using the triangular matrix of the BPS _II _{hop, hop} _III BPS, BPS _hop _IV _cw and cI, cII _cw, cIII _cw, cIV _cw combinations and right upper triangular zero obtains a feasible combination.

For example, to the pseudo-random number permutation matrix of 4 × 4 of the pseudo-random number permutation matrix BPS _hop _I, BPS _hop _II, BPS _hop _III, (the case of cw = 3) BPS _hop _IV and 4 × 1 gae from the left end with respect to the check matrix H 7 + 6 + to the left / low triangles on the right side of cI _cw , cII _cw , cIII _cw , cIV _cw and H. The one pseudo-random number permutation matrix _hop _I BPS, BPS _II _{hop, hop} _III BPS, BPS _hop _IV possible arrangement.

In step ST35, the order distribution optimization unit 35 generates test matrix by the density power generation method in the same manner as in step ST15 of the first embodiment, with the combination of the possible order distributions calculated in step ST34 as the constraint condition. Optimize the order distribution of.

In step ST36, the parity check matrix generation unit 36 arranges the first and second pseudo random number substitution matrices generated in step ST33 according to the order distribution of the parity check matrix generation optimized in step ST35 for LDPC code. Create a check matrix.

That is, by using the optimum combination of the degree distribution of the obtained in step ST35, the first pseudo-random number permutation matrix BPS _hop _I, BPS _hop _II, BPS _hop _III, BPS _hop _IV and second pseudo-random number permutation matrix cI _cw, cII _cw, The test matrix H is generated using cIII _cw and cIV _cw . As to the arrangement of each pseudo random number substitution matrix, the number of cycles is checked by searching or the like to obtain a good arrangement.

As described above, according to the third embodiment, the same effects as those of the first embodiment can be obtained.

(Example 4)

Fig. 12 is a block diagram showing the structure of a parity check matrix generating apparatus for LDPC codes according to Embodiment 4 of the present invention. The apparatus for generating a parity check matrix includes an information length, coding rate, and column maximum order input section 41, a parameter calculation section 42 for pseudo random number substitution matrix, a pseudo random number substitution matrix generation section 43, and a parameter calculation section for order distribution optimization (44), the order distribution optimizer 45 and the parity check matrix generator 46 are provided. This check matrix generating device is mounted in the communication device on the transmitting side and the receiving side in FIG. 4, and may output the generated check matrix to the encoder 101 and the decoder 105, and the communication device on the transmitting side and the receiving side. It may be provided outside, and the generated check matrix may be stored in a memory (not shown) in the communication device on the transmitting side and the receiving side and output to the encoder 101 and the decoder 105.

Fig. 13 is a flowchart showing the flow of processing in the parity check matrix generating apparatus according to the fourth embodiment of the present invention.

Example 3, BPS _hop _I, BPS _hop _II, BPS _hop _III, BPS _hop using _IV, e.g., column degree 4 × in the exemplary produce a matrix of row-order 4, but Example 4, ELHP _(cw below _{', rw')} is used to generate a matrix of direct column order cw '× row order rw'.

In step ST41, the information length, coding rate, and column maximum order input unit 31 inputs a predetermined information length, coding rate, and maximum order of columns. In step ST42, the parameter calculation unit 42 for the pseudo random number substitution matrix uses the parameters of the third pseudo random number substitution matrix described later by using the predetermined information length, coding rate, and maximum order of the columns input in step ST41; The parameters for the second pseudo random number substitution matrix as in Example 2 are calculated.

In step ST43, the pseudo random number substitution matrix generation unit 43 uses a pseudo random number sequence and a Latin square by the parameters for the third pseudo random number substitution matrix and the parameter for the second pseudo random number substitution matrix calculated in step ST42. A first pseudo random number substitution matrix is generated using the matrix, and the third pseudo random number substitution matrix is further generated by further substituting and extending the rows and columns of the generated first pseudo random number substitution matrix, and further generating the first pseudo random number substitution matrix. The substitution matrix is also compressed in the row direction to produce a second pseudo-random substitution matrix. In step ST44, the parameter distribution optimization parameter calculation unit 44 can take the optimization of the order distribution of the generation of the test matrix by using the predetermined information length, coding rate and the maximum order of the columns input in the step ST41. Calculate the parameters of the combination of order distributions.

In step ST45, the order distribution optimization unit 45 sets the order distribution of the inspection matrix generation by the density power generation method or the multi-edge type density power generation method, with the combination of the possible order distributions calculated in step ST44 as a constraint condition. To optimize. In step ST46, the parity check matrix generation unit 46 arranges the third and second pseudo random number substitution matrices generated in step ST43 according to the order distribution of the parity check matrix generation optimized in step ST45 for LDPC code. Create a check matrix.

Next, detailed processing of steps ST41 to ST46 in the flowchart of FIG. 13 will be described.

In step ST41, the information length, coding rate, and column maximum order input unit 41 is a predetermined information length, coding rate, and maximum order of columns, and the information length K = 120 and coding rate rate = 0.5 are set in advance in the system. , Enter the maximum order of columns d = 16.

In step ST42, the pseudo random number substitution matrix parameter calculating unit 42 uses the predetermined information length K = 120, the coding rate rate = 0.5 and the maximum order d = 16 of the column input in step ST41, as follows. As shown, the number of rows M of the test matrix H, the number of columns (= coding rate) N, the parameters for the third pseudo random number substitution matrix and the parameters for the second pseudo random number substitution matrix are calculated.

That is, here, using the data input in step ST41, the number of rows M of the parity check matrix H is the number of columns (= code length) N, the column weight cw 'of p' · b '× p' · b ', and the row weight rw' P 'and b' of the third pseudo-random substitution matrix ELHP _{( cw ' , rw')} are calculated, and the second pseudo-random substitution matrix cI _cw , cII of (p · b) × (p · b / cw) is calculated. _cw , cIII _cw , cIV _cw , p, b, cw.

For example, the parameters for the third pseudo random number substitution matrix and the parameters for the second pseudo random number substitution matrix are calculated as follows.

After the calculations, such as calculations carried out in step ST32 Example 3, pseudo-random numbers is described in the substitution matrix _hop _I BPS, BPS _II _{hop, hop} _III BPS, BPS _hop _IV step of ST43-1~ST43-9 to the part of The pseudo random number substitution matrix ELHP _{( cw ' , rw')} is substituted.

The maximum number of pseudo-random number permutation matrix in the row direction _hop _I BPS, BPS _II _{hop, hop} _III BPS, BPS _hop _IV 4 is because (prepared as described in step ST33-7 of Example 3), the remaining column degree d-4 = 12 a is realized by cw = 3 in the pseudo-random number permutation matrix _cw cI, cII _cw, cIII _cw, cIV _cw that is described in the following step ST44. For cw = 3, the number of pseudorandom substitution matrices cI _cw , cII _cw , cIII _cw , cIV _cw = remaining number of orders 12 / cw = 4, four combinations of cI _cw , cII _cw , cIII _cw , cIV _cw Use in the column direction.

Sign length = column of check matrix H N = k / rate = 120 / (1/3) = 360,

The number of rows in the check matrix H M = N × (1-rate) = 360 × (2/3) = 240,

Pseudo-random number substituted size p · b = M / (pseudo-random number permutation matrix of the matrix BPS _hop _I, BPS _hop _II, BPS _hop _III, using the number of BPS _hop _IV + pseudo-random number permutation matrix cI _cw, cII _cw, cIII _cw, cIV number of uses of _cw ) = _240/8 = 30. Therefore, for example, the parameters for generating the first and second pseudorandom substitution matrices are p = 6 and b = 5.

Until now, it is the value of p and b calculated | required in Example 3, and the following test matrix H is assumed.

A substituted pseudo-random number of the check matrix H, the matrix BPS _I _{hop, hop} _II BPS, BPS _hop _III, for example consisting of BPS _hop _IV, column order in the row order of 4 × 4

The 4 · p · b × 4 · p · b sub-matrix of P is the pseudorandom substitution matrix p '· b' × p '· b with column order cw' = 4 and row order rw '= 4 It _{is set} as the structure substituted by ELHP _{(cw '= 4, rw' = 4)} of '= 4 * p * b * 4 * p *.

Therefore, for example, p'6'b '= 4'p'b'4'30'120' from p = 6 and b = 5. Therefore, for example, the parameters for generating the third pseudo random number substitution matrix are p '= 12 and b' = 10.

In step ST43, the pseudo random number substitution matrix generation unit 43 uses a pseudo random number sequence and a Latin square by the parameters for the third pseudo random number substitution matrix and the parameter for the second pseudo random number substitution matrix calculated in step ST42. The first pseudo random number substitution matrix (generated by parameters common to the parameters for the second pseudo random number substitution matrix) is generated using the matrix, and the rows and columns of the generated first pseudo random number substitution matrix are further substituted and expanded to generate the first pseudo random number substitution matrix. Create a pseudo-random substitution matrix.

In other words, here, from p 'and b' obtained in step ST42, the third pseudo-random substitution matrix ELHP _{( cw ' , rw')} is created by the following steps ST43-1 to ST43-9.

In this step ST43, the method for generating the second pseudo random number substitution matrix by further compressing the first pseudo random number substitution matrix in the row direction is the same as the processing from steps ST33-1 to ST33-8 of the third embodiment. Do.

[ST43-1]

Produces the base column number C _init (i), defined by The init of this index represents the value of C _init (1), that is, the initial value.

Where P is a prime number where P> p 'and G ₀ is the source of GF (P). In addition, all elements of successive powers of G ₀ which are elements of GF (P) (for example, G ₀ ¹ , G ₀ ² , ..., G ₀ ^{P -1} = 1) are all elements that are not zero of GF (P). In the case of, G ₀ is called a primitive source. This series C _init (i) is a pseudorandom series with non-uniform differences between elements and no overlapping elements. Next, extract a number greater than p 'from the elements of C _init (i).

For example, for P = 7, G ₀ = 3, init = 3, p '= 6,

[ST43-2]

The matrix which has a pseudorandom number series and its substitution pattern as an element is produced by the following formula.

 An example in the case of p '= 6 is shown below.

[ST43-3]

The basic substitution matrix pattern LHP _{( cw ' , rw')} (j, i) of column order cw 'and row order rw' is generated by the following equation.

An example in the case of p '= 6 is shown below.

[ST43-4]

In step ST43-3, a basic substitution matrix pattern of p'xp 'was generated. Next, the procedure for multiplying this by the row and column will be explained.

을 생성한다. 이

은 C_init(i)에 대하여 p'를 b'로 바꿔 생성한 기본 란수 계열이다. Base Ransu series in the same procedure as in step ST43-1

Create this

Is the default column number generated by replacing p 'with b' for C _init (i).

For example, if P = 7, C ₀ = 3, init = 3, b '= 6,

[Step ST43-5]

The following formula produces a Latin square matrix L _j (q, l) having a pseudorandom number series and its substitution pattern as an element.

By this operation, Latin square can be generated using L ^h (q, l).

An example in the case of p '= 6 is shown below.

[Step ST43-6]

The matrix L ^{b '} P _{( cw' , rw '} ) for extending the basic substitution matrix pattern LHP _{(cw', rw ')} (j, i) of column order cw' and row order rw 'by b _{' )} produces (j, i)

An example in the case of p '= 6 is shown below.

[Step ST43-7]

By the following formula, the basic substitution matrix pattern eLHP _{(cw ', rw')} (i, j) which extends in a column direction is produced.

An example in the case where p '= 6, b' = 6, cw '= 3 and rw' = 3 is shown below.

[ST43-8]

By the following formula, a basic substitution matrix pattern ELHP _{(cw ', rw')} (i, j) extending in the row direction is generated.

An example in the case where p '= 6, b' = 6, cw '= 3 and rw' = 3 is shown below.

[ST43-9]

From the basic substitution pattern ELHP _{( cw ' , rw')} (i, j), the binary p '· b' × p '· b' matrix ELHP _{( cw ' , rw')} defined by the following equation = (h _{m , n} )

By this operation, a basic substitution matrix for generating a matrix of column order cw 'and row order rw' of p'b'xp'b 'can be generated. By the above operations, a pseudo substitution matrix of column order cw 'and row order rw' can be generated. Since the column order cw 'and the row order rw' of the pseudo random number substitution matrix are all four or less and cycle 4 often does not exist, the column order cw 'and the row order rw' have a maximum value of four.

In step ST44, the order distribution optimization parameter calculator 44 uses the predetermined information length, coding rate, and maximum order of columns input in step ST41, as shown below, to order distribution of the test matrix generation. Calculate the parameters of the combination of possible order distributions for the optimization of.

By using these ELHP _{(cw ', rw')} of the triangular matrix (i, j) and _cw cI, cII _cw, cIII _cw, cIV _cw in combination with right / upper triangular zero obtains a feasible combination.

For example, one pseudo-random substitution matrix ELHP _{( cw ' , rw')} and 4x1 ₍ if cw = 3) pseudorandom substitution matrixes cI _cw , cII _cw , cIII _cw , cIV _cw becomes deployable.

The combination of order distributions that can be taken is a constraint of the optimization of the order distribution.

In step ST45, the order distribution optimization unit 45 sets the density generation method or the multi-edge type density power generation method as shown below, with the combination of possible order distributions calculated in step ST44 as constraint conditions. By optimizing the order distribution of the parity check matrix generation.

That is, here, the best order distribution is obtained by optimization of the same order distribution as in step ST15 of the first embodiment, under the constraint of the combination of order distributions that can be taken for the optimization of the order distribution of the generation of the test matrix calculated in step ST44. May be obtained, or the density generation method of the multi-edge type described below may be used.

In the density generation method described in the first embodiment, an irregular LDPC code ensemble (indicating an order distribution) is expressed as a ratio of a row order and a ratio of a column order. In combination "(order type). In addition, in the structure of the multi-edge type ensemble, an ensemble that defines which bits to puncture can be considered, and consideration can be made for each communication channel type ("Multi-Edge Type LDPC Codes DRAFT", T. Richard Hardson). , On R. Urbanke, web)

14 is a diagram illustrating an example of an ensemble of a multi-edge type. The communication path (b = (1 0)) of the communication path type (BEC (Binary Erasure Channel in the case of the example of FIG. 14)) or a communication path to which noise is applied according to a Gaussian distribution of variance value σ _n ² , so-called additiveness A communication path (b = (0 1)) of white Gaussian noise (AWGN) is b, and a ratio of the code length N of the variable node of order type d to ν _{b, d} and the code length N of the check node Assuming that the ratio is μ _d , FIG. 14 is expressed as in the table shown in FIG. 15.

15 is a diagram illustrating an example of order distribution of an irregular LDPC code.

An example of the concrete test matrix is shown below. For example, the sum of v _{b, d} of Variable (variable node: each column of the matrix becomes a barrier node) in the table of FIG. 15 is 1. The ratio of the first phase of the variable in the table of FIG. 15 is ν _{b, d} = 0.5 and d = (2 0 0 0), but this is the 15th to 24th column of the test matrix shown in FIG. 16 constructed according to the degree distribution of FIG. Indicates. Ν _{b, d} = 0.2, b = (1 0), d = (0 3 3 0) are displayed in the third variable in the table of FIG. 15, and the 11th to 14th columns of the test matrix of FIG. have. This part means a communication path with a loss probability of 1, and in reality, the sign bit of this part is punctured and not transmitted. On the receiving side, the calculation of this part is calculated such that the probability of 0 and 1 is 1/2. The LLR (log likelihood ratio) of the received value is zero.

Constraint in the table of FIG. 15 represents the ratio of check nodes (each row of the matrix is a check node respectively). The ratio of the first phase of the Constraint in the table of FIG. 15 is μ _d = 0.4 and d = (4 1 0 0), but this represents the fifth to twelfth rows of the parity check matrix of FIG. 16.

In addition, among the edges of type i, the ratio of edges connected to nodes of order type d is

Obtained by (Corresponding to λ and ρ of Standard Irregular LDPC)

1 represents ALL1.

Next, the density generation method of the multi-edge type is demonstrated. In the multi-edge-type density generation method, the probability density function is divided for each type of edge without the message from the variable node to the check node together ("Multi-edge Type LDPC Codes DRAFT", T. Richard Hardson). , R. Urbanke, on web).

Row processing (messages from check nodes)

Now let I set all the sets of edge types. Now, for i∈I, the order of edge type i is d _i , the probability density function transmitted to the check node via edge type i is P _vi , and the probability density function transmitted from the check node via edge type i is P _ui . .

A probability density function for each edge type is calculated by calculating the probability density function for each order type, multiplying the ratio of the edges to the edge type i, and adding.

… (Al)

∀j∈I＼i

로 하면, 이하를 만족시키는 것이 합-곱 복호에서의 반복 복호에서 점근적으로 오류가 한없이 0에 가까워지는 필요 조건이다. In addition, the number of repetitions in the iterative decoding is set to l, and the ensemble average of the check nodes at the iterative l th time with respect to the edge type i is calculated.

In this case, satisfying the following is a necessary condition that the error gradually approaches zero in repetitive decoding in sum-product decoding.

For all edge types i

Thermal processing (messages from barrier nodes)

The order for the channel types b1, b2 is d _b1 , d _b2,. The initial values are P _u0b1 , P _u0b2 ,... Shall be.

Calculate the probability density function for each edge type by calculating the probability density function for each order type, multiplying the ratio of the edge to edge type i, and adding.

로 하면, 이하를 만족시키는 것이 합-곱 복호에서의 반복 복호에서 점근적으로 오류가 한없이 0에 가까워지는 필요 조건이다. In addition, the number of repetitions in the iterative decoding is set to l, and the ensemble average of the iterable lth variable nodes for the edge type i is calculated.

In this case, satisfying the following is a necessary condition that the error gradually approaches zero in repetitive decoding in sum-product decoding.

For all edge types i

Furthermore, satisfying the following is a necessary and sufficient condition that the error gradually approaches zero in the iterative decoding in sum-product decoding.

Satisfying either formula (A2) or formula (A4). (A5)

Next, using an optimization in the multi-edge type density generation method, an ensemble (order allocation) of "Irregular-LDPC code" based on the obtained coding rate is obtained.

Treat the ratio of the code length N of the variable node of the communication path type b and the order type d as ν _{b, d} and the ratio of the code length N of the check node as μ _d at the same time as the variable, respectively. In order to maximize the b1: = b = (01) Gaussian noise σ _n (following equation) of the channel type AWGN, the optimal ν _{b, d} and μ _d are searched by linear programming. At this time, in this embodiment, the communication path type is set only to b1: = b = (0 1) of AWGN and b2: = b = (1 0) of BEC.

Constraints in this search satisfy the conditional expression (A5).

At this time, the possible values of the variables of the communication path type b, the order type d, ν _{b, d} , μ _d are values derived from the constraints of the test matrix H by the generation method described in the first to fourth embodiments. Only do it.

In step ST46, the parity check matrix generation section 46 generates the third and second pseudo-random number substitution matrices generated in step ST43 by the order distribution of the parity check matrix generation optimized in step ST45, as shown below. Is arranged to generate a parity check matrix for the LDPC code.

Here, the third pseudo-random substitution matrix ELHP _{( cw ' , rw')} and the second pseudo-random substitution matrix cI _cw , cII _cw , cIII _cw , and cIV _cw are used using the combination of the optimal order distribution obtained in step ST43. To generate the parity check matrix H. As to the arrangement of each pseudo random number substitution matrix, the number of cycles is checked by searching or the like to obtain a good arrangement.

The performance evaluation result of the LDPC code by the construction method of Example 3 and Example 4 is shown.

It is a figure which shows the example of order distribution of the irregular LDPC code used for evaluation.

18 is a diagram illustrating frame error rate characteristics of an irregular LDPC code.

Fig. 18 uses parameters of p = 16, b = 9, P = 17, G ₀ = 3, init = 9 and hop = 2 using Example 3 using this order distribution shown in Fig. 17. P = 48, b = 30, P = 71, G ₀ = as a parameter of ELHP _{(cw, rw)} by using the information length 576 bits, the LDPC code (ldpc576 in the figure) of code rate 0.5, and the fourth embodiment. 7, init = 13, cw = 4, rw = 4, cI _cw , cII _cw , cIII _cw , cIV _cw as parameters of p = 30, b = 12, P = 31, G ₀ = 3, init = 9, hop P = 132, b = 24, P = 137 as a parameter of the LDPC code (ldpc1440 in the drawing) of the information length 1440 bits and code rate 0.5 constructed using = 1 and ELHP _{( cw , rw)} using Example 4 As parameters for G ₀ = 3, init = 13, cw = 4, rw = 4, cI _cw , cII _cw , cIII _cw , cIV _cw , p = 33, b = 34, P = 53, G ₀ = 3, init LDPC code (ldpc3168 in the drawing) having an information length of 3168 bits and a code rate of 0.5 configured using hop = 2 and p = 204, b = 24 as a parameter of ELHP _{( cw , rw)} using Example 4 , P = 211, G ₀ = 3, init = 13, cw = 4, rw = 4, cI _cw , cII _cw , cIII _cw , cIV _cw as parameters of p = 51, b = 24, P = 53, G ₀ = 3, init = 9, The FER (frame error rate) simulation result of the LDPC code (ldpc4896 in the figure) of information length 4896 bits and code rate 0.5 which were formed using hop = 2 is shown.

In Fig. 18, the same code lengths and coding rates of turbo codes used in third-generation communication (3GPP) are compared for comparison (turbo576, turbo1440, turbo3168, turbo4896). As can be seen from FIG. 18, the turbo code has been superior in the short code length of 10000 bits or less. However, according to the present invention, almost equivalent performance is achieved at the information length of 576 bits. Has the superior performance, and it can be confirmed that it is a code construction method showing very high performance.

In the conventional LDPC code, a good performance is achieved at a code length of 10000 bits or more, but on the contrary, a turbo code is said to be superior at a code length of 10000 bits or less. However, in Fig. 18, the information length is 4896 bits (code length 9792 bits because the coding rate is 0.5), which shows better performance than turbo codes. Further, as the code length becomes longer, the performance tends to be better than that of the turbo code. In the conventional LDPC code, the performance is equivalent to that of a turbo code at a code length of about 10000 bits, but in the present invention, the code length is about 1000 bits (in Fig. 18, an information length of 576 bits and a code rate of 0.5 is 1152 bits). Shows the same performance as the turbo code.

As described above, according to the fourth embodiment, the same effects as those of the first embodiment can be obtained, and by using the multi-edge type density generation method, an LDPC code with a good error correction capability can be generated. You can get more effect.

(Example 5)

Fig. 19 is a block diagram showing the structure of a parity check matrix generation device for LDPC codes according to the fifth embodiment of the present invention. The parity check matrix generating apparatus of the fifth embodiment includes a pseudo random number substitution matrix generator 13, a parity check matrix generation unit 16, a parameter random storage unit 17 for the pseudo random number substitution matrix, and an order distribution storage unit 18. Doing. This check matrix generating device is mounted in the communication device on the transmitting side and the receiving side in FIG. 4, and may output the generated check matrix to the encoder 101 and the decoder 105, and the communication device on the transmitting side and the receiving side. It may be provided outside, and the generated check matrix may be stored in a memory (not shown) in the communication device on the transmitting side and the receiving side and output to the encoder 101 and the decoder 105.

In Fig. 19, the pseudo random number substitution matrix storage unit 17 stores parameters for a pseudo random number substitution matrix calculated using a predetermined information length, coding rate, and maximum order of columns. The parameter for this pseudo random number substitution matrix is generated externally in the same manner as in Example 1. The pseudo random number substitution matrix generator 13 uses a pseudo random number substitution matrix and a pseudo random number substitution matrix by using a pseudo random number sequence and a Latin square matrix by the parameters for the pseudo random number substitution matrix stored in the pseudo random number substitution matrix parameter storage unit 17. Create

In addition, the order distribution storage unit 18 can take an order for optimizing the order distribution of the test matrix generation configurable using a pseudo random number substitution matrix calculated using a predetermined information length, coding rate, and maximum order of columns. With the combination of distributions as constraint conditions, the order distribution of the generation of the test matrix optimized by the density generation method is stored. The order distribution of the parity check matrix generation is optimized in the same manner as in Example 1 from the outside. The parity check matrix generation unit 16 generates the parity check matrix for the low density parity check code by arranging the generated pseudo random number substitution matrix by the order distribution of the optimized parity check matrix generation stored in the order distribution storage unit 18. do.

In the fifth embodiment, the pseudo random number substitution matrix generation unit 13 and the parity check matrix generation unit 16 of the first embodiment are constituted by the parameter storage unit 17 and the order distribution storage unit 18 for the pseudo random number substitution matrix. However, the pseudo random number substitution matrix generator 23 and the parity check matrix generator 26, the parameter storage unit 27 for the pseudo random number substitution matrix, and the order distribution storage unit 28 (not shown) of Embodiment 2 are used. The pseudo random number substitution matrix generation unit 33 and the parity check matrix generation unit 36, the parameter storage unit 37 for the pseudo random number substitution matrix 37, and the order distribution storage unit 38 (not shown) of the third embodiment may be employed. The pseudo random number substitution matrix generation unit 43 and the parity check matrix generation unit 46, the parameter random storage unit 47 and the order distribution storage unit 48 (shown in FIG. May be configured).

As described above, according to the fifth embodiment, the same effects as in the first embodiment can be obtained.

(Example 6)

20 is a block diagram showing the construction of a communication device according to a sixth embodiment of the present invention. The communication device 201 on the transmitting side includes the parity check matrix generating device 100 of any one of the first to fifth embodiments, the encoder 101 and the modulator 102. The communication device 202 on the receiving side includes the parity check matrix generating device 100 of any one of the first to fifth embodiments, the demodulator 104 and the decoder 105.

In the communication device 201 on the transmission side, the parity check matrix generating apparatus 100 generates the parity check matrix H by any of the first to fifth embodiments, and the encoder 101 generates the generated parity check matrix. A generation matrix G is obtained using H, and a message (u ₁ u ₂ ... u _K ) is received, and a sign word C is generated using the obtained generation matrix G. The modulator 102 performs digital modulation such as BPSK, QPSK, multi-valued QAM, and transmits the generated code word C.

In the communication device 202 on the receiving side, the parity check matrix generating device 100 generates the parity check matrix H by the method of any one of the first to fifth embodiments, and the demodulator 104 communicates with the communication path 103. Digital demodulation such as BPSK, QPSK, multi-valued QAM, etc., and the decoder 105 performs a "sum-multiply algorithm" using the generated parity check matrix with respect to the LDPC-coded demodulation result. Iterative decoding is performed, and the estimation result (corresponding to the original u ₁ u ₂ ... U _K ) is output.

As described above, according to the sixth embodiment, by using the parity check matrix generating apparatus 100 of any one of the first to fifth embodiments, it is deterministic, stable in characteristics, good in error correction capability, and various ensemble. The effect of using a check matrix for Irregular-LDPC codes corresponding to the code length and the code rate can be obtained.

As described above, the parity check matrix generating apparatus and the parity check matrix generating method according to the present invention are, for example, for LDPC codes corresponding to deterministic and stable characteristics, good error correction capability, and corresponding to various ensembles, code lengths, and coding rates. It is suitable to easily generate the test matrix of.

Claims (10)

An information length, encoding rate, and column maximum order input unit for inputting a predetermined information length, coding rate, and maximum order of columns; A parameter calculating unit for a pseudo random number substitution matrix for calculating a parameter for a pseudo random number substitution matrix described later using the inputted information length, coding rate, and maximum order of columns; A pseudo random number substitution matrix generator for generating the pseudo random number substitution matrix using a pseudo random number series and a Latin square matrix by the calculated parameters for the pseudo random number substitution matrix; Calculating parameters of a combination of possible order distributions for optimization of order distributions of configurable check matrix generation using the pseudo random number substitution matrix, using the inputted information length, coding rate and maximum order of columns. A parameter calculator for order distribution optimization; An order distribution optimization unit for optimizing the order distribution of the generation of the test matrix by the density generation method, using the calculated combination of the order distributions that can be taken; A parity check matrix generator for generating the parity check matrix for the low-density parity check code by arranging the pseudo random number substitution matrix generated by the optimized distribution of the parity check generation An apparatus for generating a parity check matrix. The method of claim 1, The information length, encoding rate, column maximum order input unit inputs a maximum order of a predetermined information length, a plurality of coding rates, and a column of the maximum coding rate excluding uncoding, The parameter calculation unit for the pseudo random number substitution matrix calculates a parameter for the pseudo random number substitution matrix by using the inputted maximum length of the predetermined information length, a plurality of coding rates, and a maximum coding rate except for uncoding, The order distribution optimization parameter calculating unit generates a check matrix that is configurable using the pseudo random number substitution matrix by using the maximum order of input columns of the predetermined information length, a plurality of coding rates, and a maximum coding rate excluding uncoding. To calculate the parameters of a combination of possible order distributions for optimization of the order distribution An apparatus for generating a check matrix, characterized in that. The method of claim 1, The parameter calculation unit for the pseudo random number substitution matrix calculates parameters for the first and second pseudo random number substitution matrices described later using the inputted information length, coding rate, and maximum order of columns. The pseudo random number substitution matrix generator generates the first pseudo random number substitution matrix using a pseudo random number sequence and a Latin square matrix by the calculated parameters for the first and second pseudo random number substitution matrices. Further compressing one pseudo-random substitution matrix in a row direction to produce the second pseudo-random substitution matrix, The order distribution optimization parameter calculating unit optimizes the order distribution of the generation of the test matrix configurable using the first and second pseudorandom number substitution matrices using the inputted information length, coding rate, and maximum order of columns. Calculate a parameter of the combination of possible order distributions for The parity check matrix generation unit generates the parity check matrix for the low density parity check code by arranging the generated first and second pseudo random number substitution matrices by the optimized order distribution of the parity check matrix generation. An apparatus for generating a check matrix, characterized in that. The method of claim 1, The parameter calculation unit for the pseudo random number substitution matrix may include a parameter for a third pseudo random number substitution matrix to be described later and a second pseudo random number substitution matrix to be described later using the inputted information length, coding rate, and maximum order of columns. Calculate the parameters, The pseudo random number substitution matrix generator is configured to generate a first pseudo random number using a pseudo random number sequence and a Latin square matrix based on the calculated parameters for the third pseudo random number substitution matrix and the parameters for the second pseudo random number substitution matrix. A substitution matrix is further extended by substituting rows and columns to generate the third pseudo-random substitution matrix, and further compressing the first pseudo-random substitution matrix in a row direction to generate the second pseudo random substitution matrix, The order distribution optimization parameter calculating unit optimizes an order distribution of a check matrix generation that is configurable using the third and second pseudo-random substitution matrices using the inputted predetermined information length, coding rate, and maximum order of columns. Calculate a parameter of the combination of possible order distributions for The order distribution optimization unit optimizes the order distribution of the generation of the test matrix by the density power generation method or the multi-edge type density power generation method, using the calculated combinations of the possible order distributions as constraint conditions. The parity check matrix generation unit generates the parity check matrix for the low-density parity check code by arranging the third and second pseudo-random substitution matrices generated by the optimized distribution of the parity check generation. An apparatus for generating a check matrix, characterized in that. The method of claim 1, And a cycle of the parity check matrix generated by arranging the pseudo random number substitution matrix by the parity check matrix generator is 6 or more. Generate a pseudo random number substitution matrix for inputting a parameter for a pseudo random number substitution matrix calculated using a predetermined information length, coding rate, and column maximum order, and generating the pseudo random number substitution matrix using a pseudo random number series and a Latin square matrix. Wealth, A constraint condition is a combination of acceptable order distributions for optimizing the order distribution of a test matrix generation configurable using the pseudo random number substitution matrix calculated using the predetermined information length, coding rate, and maximum order of columns. A parity check matrix generator for inputting the order distribution of the parity check generation optimized by the density generation method and arranging the generated pseudo random number substitution matrix to generate a parity check matrix for a low density parity check code An apparatus for generating a parity check matrix. A test matrix generating device according to claim 1, An encoder for generating a sign word by obtaining a generation matrix by using the check matrix generated by the check matrix generator Communication device having a. A test matrix generating device according to claim 1, A decoder that performs iterative decoding by a sum-product algorithm using the test matrix generated by the test matrix generator to calculate an estimation result. Communication device having a. A test matrix generating device according to claim 6, An encoder for generating a sign word by obtaining a generation matrix by using the check matrix generated by the check matrix generator Communication device having a. A test matrix generating device according to claim 6, A decoder that performs iterative decoding by a sum-product algorithm using the check matrix generated by the check matrix generator to calculate an estimation result. Communication device having a.

Images