CN103236861B - A kind of method of trigonometric ratio under class of galois field LDPC check matrix - Google Patents

Abstract

The invention relates to the technical field of LDPC code encoding, and specifically refers to converting a non-square matrix LPDC code check matrix into a triangular-like structure to the greatest extent so as to enhance the anti-noise ability of the LDPC code. The algorithm of the class lower triangulation process of the LDPC code check matrix based on the Galois field that the present invention proposes comprises the following steps: a, the check matrix is converted into a ladder-like matrix; b, the ladder-like matrix is converted into a class lower triangle The matrix of the structure; the purpose of the present invention is to overcome the above-mentioned deficiency that exists in the prior art, under the premise of guaranteeing not to change the sparsity of the LDPC check matrix, the check matrix is converted into a class as much as possible by basic elementary transformations. Form of lower triangular structure to improve LDPC coding performance.

Description

a galois field LDPC Method of lower triangulation of code parity check matrix

technical field

The present invention relates to the technical field of LDPC code encoding, specifically refers to the LPDC of a non-square matrix The code parity check matrix is transformed into a lower triangular structure to the greatest extent, which enhances the anti-noise ability of LDPC codes.

Background technique

In the field of channel coding, LDPC codes are a class of linear block codes with sparse parity check matrices, which not only approximate Shannon limit has good performance, low decoding complexity and flexible structure, which has become a research hotspot in the field of channel coding in recent years.

In the field of LDPC code coding, the method of processing the check matrix is mainly to use Gaussian elimination to triangulate the check matrix or to triangulate the check matrix by elementary transformation (row-column transformation). Although the Gaussian elimination method is simple and easy, it is at the expense of LDPC at the expense of code performance. The triangularized check matrix under the class only performs elementary transformation on the check matrix, and does not affect the sparsity of the matrix (the proportion of non-0 ∈ GF (q) elements in the matrix to all elements of the matrix), the sparseness of the check matrix in LDPC encoding Sexuality is one of the most critical factors affecting coding complexity and coding performance.

In the LDPC code encoding of the lower triangular check matrix, the degree of triangularization of the check matrix directly determines the encoded LDPC Code anti-noise performance. At present, the more common algorithm for triangulating the check matrix is developed by Thomas The Greedy_A algorithm by J.Richardson and Rudiger L.Urbanke.

The algorithm for triangulating the matrix class proposed in this paper eliminates the disadvantages of the Greedy_A algorithm. The matrix is divided into blocks, and the relative A check matrix with a higher degree of diagonalization for the Greedy_A algorithm.

Contents of the invention

The purpose of the present invention is to overcome the above-mentioned deficiencies existing in the prior art, under the premise of guaranteeing not to change the sparsity of the check matrix of LDPC codes, the check matrix is converted into the class lower triangular structure as far as possible by basic elementary transformation form to improve the performance of LDPC encoding.

In order to realize the above-mentioned purpose of the invention, the present invention provides the following technical solutions:

The core idea of the technical solution of the present invention is to divide the check matrix into blocks, and move 0 ∈ GF (q) in the matrix to the upper right of the matrix as much as possible to convert it into a ladder-like matrix. On the basis of the ladder matrix The class-like triangulation process is carried out above.

This algorithm is realized through the following technical solutions:

A kind of method of triangulation under the class of the LDPC code parity check matrix of a kind of Galois field, the triangulation process under the class of matrix comprises following two processes:

a. Transform the parity check matrix into a ladder-like matrix.

b. Transform the ladder-like matrix into a matrix of lower triangular structure.

Among them, step a is the key step of this algorithm, which embodies the core technical solution of this calculation, and is the process of performing multiple identical operations on different parts of the matrix. These multiple identical operations are defined as pull-down operations.

Perform pull-down operation on a non-square check matrix H (m×n), and two matrices will be obtained. are the new matrix H' and a sub-matrix M of H' after row and column transformation respectively. The main function of the pull-down operation is to transform the check matrix into a preliminary ladder form.

The specific content of the pull-down operation is explained below:

The first step: first calculate all the row weights of the parity check matrix ( ) and all column weights ( ). the matrix line by Rearranged in ascending order, the matrix column by rearranged in descending order.

Step two: according to Find the set of columns of all elements with the smallest column weight: .

The third step: the set of columns For each column in the column, find all non- The row where the element is located, calculate the sum of the row weights of these rows: .

Step 4: Find the column set middle, One of the columns that is the smallest, move that column to the matrix the last column of .

Step 5: Convert the matrix All non- The row of the element is moved to the bottom of the matrix.

In this way, a new matrix H' and its sub-matrix M are obtained. M is the sub-matrix obtained by removing the last column and all rows containing non-0∈GF (q) in the last column of H'.

After the pull-down operation, the check matrix is converted into a new matrix H' containing only one step, and it is ensured that the non-0∈GF(q) elements in H' move to the bottom and left of the matrix as much as possible. It provides favorable conditions for the subsequent diagonalization process.

The specific process of step a is to perform a pull-down operation on the check matrix H to obtain the matrix H', and then perform a pull-down operation on the sub-matrix M of H', and repeat this until the position where the pull-down operation cannot be performed. The original check matrix H will be transformed into a step matrix through elementary transformation.

The specific implementation process of step b is as follows:

Step 1: Find the last column of the step matrix and select the first non- element as a starting point, define that element as ;

Step 2: From Start to traverse to the upper left of the matrix in turn ( ), to determine whether the current element is , if yes, perform operation Y, otherwise perform operation N;

where the operation Y is defined as:

will traverse the first non- The column where the element is located is exchanged with the current column.

The operation N is defined as:

Check whether there are non-elements above the element in the column where the traversal element is located, and if so, put these non-elements Move the row where the element is located to the bottom of the matrix, otherwise do nothing.

Compared with prior art, the beneficial effect of the present invention

1. All operations on the matrix by the algorithm disclosed in the present invention are limited to row exchange and column exchange, and will not affect the sparsity of the LDPC coded check matrix. Use the LDPC code check matrix processed by this algorithm to perform LDPC Coding will greatly improve the anti-noise performance of the information sequence.

2. The principle of this algorithm is easy to understand, and the implementation process is simple and easy. Because he only performs basic row and column exchange operations on the parity check matrix. Whether it is software simulation or hardware implementation, it is easy to implement.

3. Compared with the commonly used Greedy_A algorithm, this algorithm eliminates There are loopholes in the Greedy_A algorithm, and the performance is completely better than the Greedy_A algorithm.

4. This algorithm has certain versatility and is applicable to both binary Galois Field and multi-ary Galois Field.

Description of drawings

Figure 1 is a schematic diagram of the pull-down operation in step a of this algorithm.

Figure 2 is a diagram of the implementation steps of step a of this algorithm.

Figure 3 is the flowchart of this algorithm.

Figure 4 is a flowchart of the pull-down operation.

Figure 5 is a flowchart of step a of this algorithm.

Figure 6 is a flow chart of step b of this algorithm.

Figure 7 is a schematic diagram of the Greedy_A algorithm in the background technology.

Figure 8 is the definition of measuring the degree of diagonalization of check matrix class g.

Figure 9 shows the comparison of g-means between this algorithm and the Greedy_A algorithm in the background technology.

Figure 10 is a comparison of g variance between this algorithm and the Greedy_A algorithm in the background technology.

detailed description

The present invention will be further described in detail below in conjunction with test examples and specific embodiments. However, it should not be understood that the scope of the above subject matter of the present invention is limited to the following embodiments, and all technologies realized based on the content of the present invention belong to the scope of the present invention.

As shown in FIG. 3, a kind of lower triangulation method of the LDPC code check matrix of Galois field, the matrix lower triangulation process includes the following two processes:

a. Transform the parity check matrix into a ladder-like matrix.

b. Transform the ladder-like matrix into a matrix of lower triangular structure.

As shown in Figure 2, step a is the key step of this algorithm, which embodies the core technical solution of this algorithm. It is the process of performing multiple identical operations on different parts of the matrix, and these multiple identical operations are defined as pull-down operations.

Perform pull-down operation on a non-square check matrix H (m×n), and two matrices will be obtained. are the new matrix H' and a sub-matrix M of H' after row and column transformation respectively. The main function of the pull-down operation is to transform the check matrix into a preliminary ladder form.

As shown in Figure 1 and Figure 4, the specific content of the pull-down operation is explained below:

The first step: first calculate all the row weights of the parity check matrix ( ) and all column weights ( ). the matrix line by Rearranged in ascending order, the matrix column by rearranged in descending order.

Step two: according to Find the set of columns of all elements with the smallest column weight: .

The third step: the set of columns For each column in the column, find all non- The row where the element is located, calculate the sum of the row weights of these rows: .

Step 4: Find the column set middle, One of the columns that is the smallest, move that column to the matrix the last column of .

Step 5: Convert the matrix All non- The row of the element is moved to the bottom of the matrix.

In this way, a new matrix H' and its sub-matrix M are obtained. M is the sub-matrix obtained by removing the last column and all rows containing non-0∈GF (q) in the last column of H'.

After the pull-down operation, the check matrix is converted into a new matrix H' containing only one step, and it is ensured that the non-0∈GF(q) elements in H' move to the bottom and left of the matrix as much as possible. It provides favorable conditions for the subsequent diagonalization process.

As shown in Figure 5, the specific process of step a is to perform a pull-down operation on the check matrix H to obtain the matrix H', and then perform a pull-down operation on the sub-matrix M of H', and repeat until the pull-down operation cannot be performed. The original check matrix H will be transformed into a step matrix through elementary transformation.

As shown in Figure 6, the specific implementation process of step b is as follows:

Step 1: Find the last column of the step matrix and select the first non- element as a starting point, which is defined as ;

Step 2: From Start to traverse to the upper left of the matrix in turn ( ), to determine whether the current element is , if yes, perform operation Y, otherwise perform operation N;

where the operation Y is defined as:

will traverse the first non- The column where the element is located is exchanged with the current column.

The operation N is defined as:

Check whether there are non-elements above the element in the column where the traversal element is located, and if so, put these non-elements Move the row where the element is located to the bottom of the matrix, otherwise do nothing.

The present invention compares the performance of this algorithm and the Greedy_A algorithm no matter from the theoretical level analysis or from the actual performance. It can be obtained that this algorithm is better than Conclusions for the Greedy_A algorithm.

First, briefly describe the idea of the Greedy_A algorithm, as shown in Figure 7, which mainly includes three steps:

(1) For a check matrix A, do the following for each column: declare it as a known column independently with the probability of 1 −α (α ∈ (0,1)), otherwise, declare it as a deleted column, delete it. Let Ã=A.

(2) Determine whether it is over. If there is neither a known column nor a row with a weight of 1 in A, output the current matrix and end. Otherwise, perform the diagonal extension step.

(3) Declare known columns. Declare the columns that are connected to the rows in à and 1 as known columns. Return to step 2.

The diagonal extension step is the core part of the Greedy_A algorithm. Suppose now there is a matrix A, and some of its columns have been declared as known columns. We are interested in two situations: either none of these known columns is connected to a row with a weight of 1; or all of these known columns are connected to a row with a weight of 1. Here, the r row and the c column are connected, which means that A _rc =1. Considering the former case (this is often the case at the beginning), exchange columns so that all known columns become the front row of A. These columns are then removed, leaving the remaining matrix as Ã. Considering the latter case, let c ₁ ,..., c _k be known columns, r ₁ ,..., r _k be 1-fold rows, and c _i and c _i are connected. Rearrange these rows and columns so that c ₁ ,..., c _k and r ₁ ,..., r _k become the first k columns and first k rows of A. At this time, the k×k sub-matrix in the upper left corner of A is the identity matrix, and each of the first k rows has only one non-zero element.

Greedy_A Although the algorithm can transform the matrix into an approximate lower triangular form. But there is a big loophole.

That is, in the second step of judgment, if there is no known column and no row with a row weight of 1 is found, the current matrix is directly output and the algorithm ends. But this does not mean that the matrix cannot continue to be diagonalized, and a lot of diagonalization space is wasted. Give a counter-example to prove the vulnerability of the algorithm:

For example matrix

It is obvious that this matrix can be diagonalized. But if you follow the Greedy_A algorithm flow. After the second step, the matrix à is obtained. Since it does not have a row with a row weight of 1, it will not declare the existence of known columns when the known columns are declared in the third step. Then return the second-step decision with neither known columns nor rows with a row weight of 1. It will output directly and will not continue to diagonalize. This wastes 4 lines of resources that can be diagonalized.

However, according to the design idea of this algorithm, it is strictly executed according to the algorithm flow. This special matrix will continue to be diagonalized and get the final triangular-like structure matrix:

The standard to measure the degree of diagonalization of the check matrix of the LDPC code is mainly the T dimension of the lower triangular matrix after the check matrix is divided into blocks. We use g to measure the lower triangular degree of the check matrix, and g is defined as the difference between the number of rows of the check matrix and the dimension of T, see Figure 8. Obviously, the smaller g is, the better the triangulation degree of the check matrix is.

To compare the performance gap between this algorithm and Greedy_A. in MATLAB 7.10.0 (R2010a) platform for simulation verification. The selected code rate is 0.5, and the code length varies from 200 to 2000. Increase in length by 200 yards in turn. Each code length simulates 100 frames, and the parity check matrix of each frame is randomly generated. The quasi-diagonalization process of the parity check matrix is carried out with two algorithms. Perform mean and variance processing on the parity check matrix of each code length after diagonalization. Compare the difference in emission performance. The results are shown in the following table and accompanying drawing 9, accompanying drawing 10.

By table 1 and accompanying drawing 9, accompanying drawing 10 can find out. As the dimension of the matrix increases, the g of the subtriangularized matrix gradually increases. Comparing this algorithm with the Greedy_A algorithm, the g-mean value of this algorithm after triangulating the matrix is obviously smaller than that of the Greedy_A algorithm. In addition, the g variance of this algorithm is also smaller than the Greedy_A algorithm. It shows that the performance of this algorithm is not only better than the Greedy_A algorithm. And the stability is also higher than the Greedy_A algorithm.

Claims (1)

1. the method for triangulation under the class of the LDPC code parity check matrix of a kind of Galois field, it is characterized in that, comprises the following steps: a. Convert the parity check matrix into a stepped matrix; b. Transform the stepped matrix into a matrix of the lower triangular structure; The step a is specifically: performing the same operation process on different parts of the parity check matrix multiple times, and the operation process is a pull-down operation process ; The pull-down operation process described in step a is specifically: The first step: first calculate all the row weights of the parity check matrix ( ) and all column weights ( ); the matrix line by Rearranged in ascending order, the matrix column by rearranged in descending order; Step two: according to Find the set of columns of all elements with the smallest column weight: ; The third step: the set of columns For each column in the column, find all non- The row where the element is located, calculate the sum of the row weights of these rows: ; Step 4: Find the column set middle, One of the columns that is the smallest, move that column to the matrix the last column of Step 5: Convert the matrix All non- The row where the element is located is moved to the bottom of the matrix ; Described step b is specifically: Step 1: Find the last column of the echelon matrix, and select the first non- element as a starting point, define that element as ; Step 2: From Start to traverse to the upper left of the matrix in turn , to determine whether the current element is , if yes, will traverse the first non- The column where the element is located is exchanged with the current column; if not, check whether there is a non- elements, if present, will these non- Move the row where the element is located to the bottom of the matrix, otherwise do nothing.