KR100922956B1 - Low Density Parity Check Code Encoding Method - Google Patents

Abstract

The present invention relates to a method of encoding data, and more particularly, to a method of encoding a low-density parity check (LDPC) code.

The method of the present invention is a method for generating a low density parity check code consisting of an information partial matrix and a parity partial matrix, wherein the information partial matrix is changed into an array code structure and an order sequence is assigned to each sub-matrix column. And in the generalized double diagonal matrix which is the parity partial matrix, expanding the offset value between diagonal lines to have an arbitrary value, and lifting the generalized double diagonal matrix. Determining an offset value for cyclic column shift for each sub-matrix of the generalized double diagonal matrix, and an encoding process for determining a parity symbol corresponding to a column of the parity partial matrix Include.

LDPC, double diagonal, irregular LDPC code.

Description

METHOD FOR ENCODING OF LOW DENSITY PARITY CHECK CODE}             

1 shows a parity check matrix for a typical (p, r) array code,

2 shows that the maximum number of 1s in any one column is d _v , A diagram showing the matrix H _d as an example where the number of such sub-matrix columns is n _v and the number of 1s present in the remaining sub-matrix columns is always 3,

3 is a diagram illustrating a factor graph structure of an irregular repeat accumulation code;

4 shows a matrix of low density parity codes having irregular repeating accumulation codes;

5 is a diagram illustrating a double diagonal matrix of parity parts when lifting an offset value f to have an arbitrary value;

FIG. 6 shows p ₀ , p _rf , p _r-2f ,... A diagram illustrating a process of sequentially obtaining values of,

7 is a view showing an example of the information portion H _d of the parity check matrix generated in the same manner as described in section A above when the maximum variable node degree is 15;

8 is a matrix lifted matrix of a basic 4x4 matrix into a 12x12 matrix by replacing each element of an arbitrary 4x4 matrix with a 3x3 identity matrix or a 3x3 0 matrix;

FIG. 9 illustrates a parity matrix H _p constructed by matrix lifting by p x p cyclic substitution sub-matrix. FIG.

10 is a flowchart for generating a matrix of parity parts according to a preferred embodiment of the present invention;

11 illustrates a parity matrix of a generalized double diagonal matrix lifted to have values of r = 15, f = 7, p = 89,

12 is a flowchart of an iterative reliable proliferation decoding process for verifying the efficiency of the present invention;

FIG. 13A shows, as an example, a matrix of information portions Hd when n = 870, p = 29;

FIG. 13B illustrates, as an example, a matrix of parity portions Hp when n = 870 and p = 29;

13C is a simulation result graph comparing the performance of a low density parity check code and a turbo code;

FIG. 14A shows, as an example, a matrix of information portions Hd when n = 1590, p = 53; FIG.

14B is a diagram showing a matrix of parity portions Hp when n = 1590 and p = 53 as an example;

14C is a simulation result graph comparing the performance of a low density parity check code and a turbo code;

FIG. 15A shows, as an example, a matrix of information portions Hd when n = 3090, p = 103;

15B is a diagram showing a matrix of parity portions Hp when n = 3090 and p = 103 as an example;

15C is a graph of a simulation result comparing the performance of a low density parity check code and a turbo code;

FIG. 16A shows, as an example, a matrix of information portions H _d when n = 7710, p = 257;

16B is a diagram illustrating a matrix of parity portions H _p when n = 7710 and p = 257 as an example;

16C is a graph of a simulation result comparing the performance of a low density parity check code and a turbo code;                 

16D is a graph of simulation results according to the change in the number of repetitions of the low density parity check code.

The present invention relates to a method of encoding data, and more particularly, to a method of encoding a low-density parity check (LDPC) code.

In general, a communication system encodes and transmits data to be transmitted at the time of data transmission, thereby improving transmission stability and increasing transmission efficiency by preventing many retransmissions. Among these coding methods, methods such as a convolutional coding method, a turbo coding method, and a quasi-complementary turbo coding (QCTC) are used in a mobile communication system. This is because the use of the above methods can increase the stability and transmission efficiency of data transmission.

However, current wireless communication systems are rapidly developing, and accordingly, systems capable of transmitting very high speed data have emerged. There is a desire to be able to transmit higher speed data in such a wireless communication system. Accordingly, there is a need for an encoding method capable of obtaining higher efficiency than the encoding methods of the above-described methods currently provided.                         

To meet this demand, a new alternative is the low density parity check code. We will then look more closely at the low density parity code. The low density parity check code was first proposed by Gallager in the early 1960's and has since been re-examined by MacKay et al. The low density parity check code re-examined by McKay et al. Is based on a sum-product algorithm. In addition, low-density parity check codes have begun to attract attention as codes that can achieve superior performance close to Shannon's capacity limit by using belief propagation decoding.

Later, Richardson and Chung et al. Described the probability distribution of messages generated and updated during decoding on a factor graph constituting a low density parity code. We proposed a density evolution technique to track changes. By using the density evolution technique and assuming infinite repetition on a cycle free factor graph, a channel parameter (threshold) that allows a probability of error to converge to "0" was invented. . That is, we proposed a degree distribution that can maximize the channel parameters of variable nodes and check nodes on the factor graph. And it was theoretically shown that this case is applicable to LDPC codes of finite length in which there is a cycle.

In addition, the density evolution technique showed that the theoretical channel capacity of an irregular LDPC code can be as close as 0.0045 dB to the Shannon limit. In particular, Flarion leads the design and hardware (H / W) implementation of LDPC codes, and has a frame error rate that is superior to turbo codes for LDPC codes of relatively short length, and is a parallel decoder. We have proposed a multi-edge type vector LDPC code that can be implemented.

Such LDPC codes are considered as a powerful alternative to turbo code in next generation mobile communication systems. This is because of the parallel structure, low complexity, low performance floor and good frame error rate of the decoder implementation of the LDPC code. to be. Therefore, if much research is conducted in the future, LDPC codes with better characteristics are expected to emerge.

However, the problem of implementing the LDPC code is that the encoding process is more complicated than the turbo code, and the structure of the optimized code that can perform better than the turbo code in a short frame size is poor. It is necessary. Many studies have been actively conducted to solve this problem, but there are no proposals for performing the encoding of the optimized LDPC codes.

Accordingly, an object of the present invention is to provide a method for encoding a low density parity check code, in which an encoding process is simple.

Another object of the present invention is to provide an improved method of encoding a low density parity check code at a short frame size.

A method of the present invention for achieving the above objects is a method of generating a low density parity check code consisting of an information sub-matrix and a parity sub-matrix, wherein the information sub-matrix is changed into an array code structure, and the order of each sub-matrix column Allocating a sequence, extending the offset value between diagonal lines in the generalized double diagonal matrix that is the parity partial matrix, and lifting the generalized double diagonal matrix; Determining an offset value for cyclic column shift for each sub-matrix of the generalized double diagonal matrix, and an encoding process for determining a parity symbol corresponding to a column of the parity partial matrix Include.

와 같이 구성할 수 있고, The present invention more preferably the degree sequence (degree sequence)

Can be configured as

The offset value between the diagonal lines is preferably configured to be smaller than the number of columns of the generalized double diagonal matrix.

Also preferably, in the generalized double diagonal matrix that is the parity partial matrix, the sum of the offset values for the cyclic row movement of the oblique sub-matrix and the sum of the offset values for the cyclic row movement of the sub-matrix on the offset diagonal is not zero. Should be.

And, the encoding process,

A first process of determining a parity symbol of a first row in a submatrix having an oblique sub-matrix column index of the parity submatrix, and an offset diagonal line having a sub-matrix column index equal to the sub-matrix column index of the set parity symbol The second process of setting the row index in the sub-matrix of the parity symbol with the determined parity symbol and the column index in the sub-matrix in the sub-matrix, and the sub-matrix row index equal to the sub-matrix row index of the sub-matrix on the offset diagonal line A third process of determining parity symbols having the same row index in the set sub-matrix in an oblique sub-metric, and repeating the operations from the second process to the third process until the generation of the parity matrix is completed Including process Is preferred.

The parity symbol of the first process may be determined as a sum of information symbols of an information partial matrix existing in a row such as a row index in a submatrix in which the parity symbol is to be determined.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. First of all, in adding reference numerals to the components of each drawing, it should be noted that the same reference numerals have the same reference numerals as much as possible even if displayed on different drawings.

In the following description of the present invention, if it is determined that a detailed description of a related known function or configuration may unnecessarily obscure the subject matter of the present invention, the detailed description thereof will be omitted.

The present invention described below proposes a new LDPC code capable of simple encoding and excellent performance. To this end, a new parity check matrix is defined. In other words, we propose a new LDPC code using the new parity check matrix. In addition, it is shown that a new LDPC code according to the present invention can be easily encoded by a linear operation and proposes an encoding method for the same. Finally, it is shown that the LDPC code proposed by the present invention has better decoding performance than the turbo code used in the CDMA2000 1xEV-DV standard by belief propagation decoding.

In the present invention described below, for the convenience of discussion, the performance and implementation of an LDPC code having a code rate of 1/2 will be described. However, it is noted that the coding rate can be lifted within the gist of the present invention.

1.Parity check matrix design

This section defines a new parity check matrix created by applying a parity check matrix structure that defines array codes and irregular repeat accumulate codes. In addition, a method of generating a matrix having a larger size while maintaining the properties of the basic matrix generated in this manner will be described.

A. Array code structure

In general, the parity check matrix for the (p, r) array code is defined as in FIG. 1 is a diagram illustrating a parity check matrix for a general (p, r) array code. Next, a parity check matrix for a general (p, r) array code will be described with reference to FIG. 1.

In FIG. 1, p is prime number. Then, the the square matrix having a size of p p x p identity matrix (identity matrix) of j circular shift (cyclic shift) as long as each line of the I p x p cyclic permutation matrix (cyclic permutation matrix) obtained by a σ ^j Notation is shown. The rows and columns of the set of sigma ^j are referred to as sub-matrix rows and sub-matrix columns, respectively. The columns and rows of the parity check matrix defining the array code have p and r 1 uniformly, respectively. If p is moderately large, the proportion of 1 in the matrix is reduced, resulting in a structure of a low density parity check code. In addition, such an array code does not have a cycle structure of length 4. In other words, if the elements belonging to the four partial matrices σ ^ia , σ ^ib , σ ^ja , σ ^jb (i ≠ j) that form a square-cycle 4-in the parity check matrix have a structure of cycle 4 < Equation 1 is to be established.

That is, in Equation 1, a = b . However, Equation 1 cannot be established because a and b which exist in any different row parts always have different values. Therefore, the array code having the parity check matrix as described above does not have the structure of cycle 4.

In the present invention, a new matrix structure is generated and used by modifying the parity check matrix structure of the array code as described above. Next, look at the process of creating a new matrix structure for use in the present invention. In addition, the purpose of performing such a transformation is to obtain an irregular structure based on an array code structure having no structure of cycle 4 but having various distributions of 1 in each column of the matrix to be generated. to be. In addition, in this process, the distribution of 1 in each row is made to be relatively uniform, that is, only two kinds exist. Then, the method of generating a new matrix structure to be used in the present invention will be examined.

(1) Any j- th sub-matrix column of the parity check matrix constituting the array code is composed of sub matrices as shown in Equation 2 below.

(2) A degree sequence for each sub-matrix column is defined as shown in Equation 3 according to a predefined distribution.

In Equation 3, d _j denotes a column degree corresponding to a j th submatrix column, and s is a total number of submatrix columns. In addition, s is equal to the maximum number d _{v of} 1 present in any column.

(3) According to the degree sequence D defined in the above (2), the arbitrary j- th sub-matrix string is modified as shown in Equation 4 below.

에서 0이 아닌 서브 매트릭스가 존재하기 시작하는 서브 매트릭스 열 번호(sub-matrix row number)이다.That is, in Equation 4, t _j is the j th submatrix column.

Is the sub-matrix row number where non-zero submatrix begins to exist.

(4) The matrix H _d to be generated is a matrix such as the following Equation 5 having each sub-matrix column as a column vector.

If any one sub-matrix column of the matrix is defined according to the above-described process, only one number of degrees equal to the degree assigned to the corresponding sub-matrix column is included in any one column existing in each sub-matrix column. Will always exist. In addition, the matrix consisting of the above sub-matrix columns will minimize the sub-matrix overlap between each matrix. Therefore, the number of 1s present in any one row of the entire matrix will also be minimized. In other words, it is easy to see that the number of 1s in a row will always have two or only one in the whole matrix. In addition, since the matrix H _d generated as described above is a form in which some sub-matrices are removed from the array code structure, it is easy to see that the structure of Cycle 4 does not always exist like the array code.

2 shows that the maximum number of 1s in any one column is d _v , The number of such sub-matrix columns is n _v and the number of 1s present in the remaining sub-matrix columns is a diagram showing the matrix H _d in the case of 3 as an example.

In the present invention, the information partial matrix H _d 220 of the parity check matrix H defined based on the arrangement code structure as shown in FIG. 2 is a parity check matrix of the low density parity code to be defined in the present invention. Will be used as the sub-matrix of H. In the following description, an irregular repeat accumulate code structure is searched for generating a sub-matrix constituting the parity portion of the parity check matrix H.

B. Generalized dual-diagonal matrix

Irregular repeat accumulate (IRA) codes have a simple encoder structure and are known to achieve relatively good performance by a message passing decoder. This irregular repeat accumulation code can be viewed as a form of low density parity check code.

3 is a diagram illustrating a factor graph structure of an irregular repeat accumulation code. Next, the factor graph structure of the iterative accumulation code will be described with reference to FIG. 3. The factor graph of the irregular repeating accumulation code of FIG. 3 is a systemic version, in which parity nodes corresponding to a parity symbol of a codeword are only one parity node. Except for all, they have degree 2. That is, two edges are connected to each of the parity nodes 301, 302, 303,..., 304, 305, 306, and 307. This structure of the parity node has the advantage that the generation of a parity symbol by a given information symbol can be easily performed only by linear operation. In addition, as shown in FIG. 3, the information node of the irregular repeat accumulation code may have various degree distributions. The values of these information nodes are connected to the check node via random permutation 320.

If the irregular repeating accumulation code having the factor graph as shown in FIG. 3 is shown in a matrix form, it may be illustrated as shown in FIG. 4. 4 is a diagram illustrating a matrix of low density parity codes having irregular repeating accumulation codes.

The diagonal of the parity portion of the matrix of the low density parity code of FIG. 4 means '1', and the offset f 401 between the diagonal lines has a value of 1 in a general irregular repeat accumulation code. Accordingly, the sub-matrix corresponding to the parity portion of the parity check matrix defining the irregular repeat accumulation code has a dual-diagonal matrix form. And, the number of 1s present in each column of the information portion of the parity check matrix has an irregular distribution. Their distribution is defined by the random permutation unit of FIG.

In the present invention, only the parity portion of the irregular repeating accumulation code structure is considered. Therefore, we generalize only the parity part and propose a new type of matrix.

In FIG. 4, a general irregular repeat accumulation code has a case where a value f = 1, which is an offset between diagonal lines, is illustrated. In the present invention, when the offset value f is lifted to have an arbitrary value, the double diagonal matrix of the parity portion may be generalized as shown in FIG. 5. The first diagonal line 501 of FIG. 5 forms an oblique line from the position of the top column and the top row of the matrix to the last row of the last column. The first partial oblique line 502a of the second oblique line has a value of '0' at the first position of the position shifted by the offset value, and the rest of the first partial oblique line of the second oblique line has the same offset value ( It has 1 to the last part of 502a, and the second partial diagonal line 502b of the second diagonal line is formed by diagonally having a value of 1 from the first column of the next row.

5 is a diagram illustrating a parity matrix when the offset value of the double oblique matrix is lifted to an arbitrary value according to the present invention. As shown in FIG. 5, even when the offset value is changed, a column in which only one "1" exists in a specific column always exists. In other words, it should be noted that if the number of " 1 " present in all columns is 2, the rank of the double diagonal matrix becomes smaller than the rows of the matrix. Therefore, as shown in FIG. 5, the first row of the second diagonal line does not have “1”, that is, “0”. If the matrix size of the matrix as shown in FIG. 5 is r , i.e., an r x r matrix, a set of any given information symbols is set if the offset value f of the double diagonal matrix and the size r of the matrix do not have a common factor. R parity symbols can be generated with only r addition operations. To prove this, first consider the following theorem.

Theorem 1 : Any Abelian group AG _r = {0, 1, 2,... , R -1} Any one element (element) of, and r and relatively prime to the non-zero random element f will always generate all the elements of the AG _r r times or addition of less of themselves. Ten thousand and one r and the random element f is if you can not generate all the elements in the AG _r by r times or addition of less, to about less any k than r <Equation (6) relatively prime and non-zero in order to prove this, K satisfies the condition>.

However, Equation 6 violates the assumption that f and r are small. That is, the minimum value of k satisfying Equation 6 is It must always be r . Therefore, element f can generate all elements of AG _r by r addition operations.

In addition, the dual diagonal matrix shown in FIG. 5 is a matrix corresponding to a parity portion of an arbitrary parity check matrix. Accordingly, in the matrix of FIG. 5, any i- th column may always obtain information as shown in Equation 7 below from the i- th column of the matrix corresponding to the remaining information portion of the parity check matrix.

In Equation 7, d _i is an i- th information symbol, and a _i is a number of 1s present in the i- th column of the matrix corresponding to the information part of the parity check matrix. And addition means addition operation on GF (2). The GF (2) means Galois Field over 2, which means a finite field defined on modulo 2. The finite field has a finite number of elements, is closed for addition and multiplication (over modulo 2), and has an identity and inverse for addition, respectively, for the identity and nonzero elements for multiplication. It is a set of inverses, and the set of exchange, combination and distribution laws for addition and multiplication. Therefore, GF (2) means a set of {0, 1} that satisfies this property. Therefore, the first parity symbol obtained by the parity check equation corresponding to the first column in the matrix shown in FIG. 5 is represented by Equation 8 below.

In the matrix structure of FIG. 5, the column index and the row index of any 1 present in the diagonal line and the offset diagonal line are represented by Equation 9 below. Has the same relationship as

Using two equations shown in Equation 9, it can be seen that when p _rf is obtained, it is calculated as in Equation 10 using p ₀ .

In addition, since the parity check matrix has a double oblique matrix structure as shown in FIG. 5, using this, Equation 10 may be changed to Equation 11 below.                     

Thus, _if the parity symbol p _r-if can be obtained by Equation (11), and r and f are small by '(theorem 1)', as i increases ( r-if ) ( The value of mod r ) must have all values from 1 to r -1 only once. Accordingly, if r and f are mutually small, all the parity symbols can be obtained through the above process. Therefore, through the above-described method, the parity check matrix having the parity portion as shown in FIG. 5 can always be simply encoded by linear operation. FIG. 6 shows p ₀ , p _rf , p _r-2f ,... Is a diagram illustrating a process of sequentially obtaining the values of.

Referring to FIG. 6, a position value of row r-f of row 0 is connected to row 0 of row 0 as shown by reference numeral 601. The position value of the r-f row of the 0th column is connected to the position value of the r-f row of the r-f column as indicated by reference numeral 602. As described above, 1 is positioned only in an area of the first partial diagonal line 620a of the first diagonal line 610 and the second diagonal line and the second partial diagonal line 620b of the second diagonal line. In addition, since there is only one value of 1 in the first column among the diagonal lines, as described above, if the value of 1 is continuously found and the quadratic function is solved, all values can be found as a result.

The generalized double diagonal matrix structure described so far will be used as a sub-matrix H _p of the parity portion of the parity check matrix H of the low density parity check code defined in the present invention. Now, a method of generating a parity check matrix of a low density parity check code to be defined in the present invention will be described.

C. Parity check matrix construction

Next, a method for generating a new parity check matrix H according to the present invention using a salping array code structure in Section A, a salping generalized double diagonal matrix structure in Section B, and a structure thereof will be described. Do it. The parity check matrix described below defines the matrix H _d , which is defined based on the salping and array code structure in section A, as an information part of the parity check matrix H. In addition, the salping generalized double diagonal matrix H _p in section B is defined as the parity portion of the information partial matrix H. Therefore, the parity check matrix H defining the low density parity check code to be designed in the present invention has a structure as shown in Equation 12 below.

In Equation 12, each sub-matrix column of the information partial matrix H _d of the parity check matrix is defined by degree sequence D according to a predefined degree distribution, and each sub-matrix column sub- matrix column) the forming unit submatrix σ ^ij is moved to open the identity matrix (identity matrix) of p x p of size p much gopin ij of a submatrix column index i and the submatrix row index j (column shift) periodically Cyclic permutation matrix. P is always a prime number. H _p 'lifts' 1 and 0 present in the matrix into a p x p matrix and a 0 matrix, respectively, to match the structure of H _d .

Then, as described above, the processes for generating the low density parity check code according to the present invention will be sequentially examined.

(A) Distribution and parity check submatrix H _d  Structure distribution and H _d  construction)

Richardson et al. Show that when message passing decoding is performed on a factor graph that defines a low density parity code, the variable and check nodes are updated by the sum-product algorithm. It has been shown that changes in messages due to message update and their iterative processing can be tracked through changes in their probabilistic distribution. And, through this density evolution method, a channel parameter that can determine whether or not the average probability of error of a low density parity code defined by a factor graph having a given distribution converges to zero. It is shown that there is a channel parameter threshold. In addition, it has been shown that the probability of bit error can always converge to 0 when assuming infinite iteration in the decoding process for a channel parameter smaller than the channel parameter threshold value. Therefore, this density evolution technique can be used as a design tool for optimizing the degree distribution of low density parity code that can improve a threshold value for a specific channel environment. Therefore, many studies have been conducted to obtain optimized distribution and threshold values for low density parity codes.

In the present invention, an optimized variable node degree distribution that is already defined is approximated to a variable node degree distribution of the parity check matrix H to be defined in the present invention. At this time, degree 2 of the variable nodes, all parity (parity) portion of the H, that is the variable node information (information) portion of the H having a more degree is assigned to each row (column), and the H _p, i.e. H _d Assign to each column of. From the sub-matrix construction of the salping 'array code structure' in clause A and the 'generalized double diagonal matrix' in clause B, the check node degree of parity check matrix H is given by all 1s. You will always have two or one kind of minimized.

Now, to determine the degree sequence for defining the information portion H _d of the parity check matrix to be defined in the present invention. If the maximum variable node degree on the factor graph that defines the low-density parity check code is d _v , the distribution of each edge present on the variable node is represented by the polynomial shown in Equation 13 below. Can be.

In Equation 13, λ _i represents a ratio of edges present in the variable node having degree i . And, for a given λ (x), the ratio c _j of the variable node whose degree is j on the factor graph may be expressed as Equation 14 below.

Considering the implementation in Equation 14 given above, the configuration of the parity check matrix will be described with respect to the case where the maximum variable node degree is 15. Code rate in a binary input additive white Gaussian noise (BI-AWGN) channel environment when the maximum variable node degree on the factor graph that defines the low density parity code is 15 It is known that the optimal degree distribution for rate 1/2 is expressed by Equation 15 by density evolution.

In this case, the maximum channel parameter noise variance in AWGN channel σ ^* is 0.9622 in the white Gaussian noise channel that converges the probability of error of each variable node to 0, which is Eb. Converting to / No, this is 0.3348 dB. That is, the low density parity code defined by the factor graph having the degree distribution as described above is defined by Shannon's capacity limit by belief propagation decoding assuming infinite block size and infinite iteration. The performance is as close as 0.3348 dB. The ratio of the variable nodes having each degree on the felt graph having the same degree distribution as described above is expressed by Equation 16 below.

In the parity check matrix to be defined in the present invention, a variable node having a degree of 2 should always be assigned to the parity portion H _p , and only a variable node other than degree 2 should always be allocated to the information portion H _d . And, all the columns in each sub-matrix column of the information part H _d are arranged to have the same column weight. Therefore, the ratio of the variable nodes having each degree on the factor graph of the parity check matrix H is approximated by Equation 17 below.

The degree distribution polynomial λ (x) is obtained again using the variable node ratio as shown in Equation 17, and the threshold σ ^* in the AWGN of the low density parity code defined by the degree distribution is calculated as follows. Equation 18 &gt;

A value as shown in Equation 18 is a value corresponding to a low density parity code having a coding rate 1/2. When deriving the above values, we used density evolution method by Gaussian approximation as analysis technique, and estimated probability of bit error is less than 10 ^-6 . If it is, it is calculated as error free. This using The degree sequence allocated to each submatrix column of the information portion H _d may be defined as in Equation 19 below.

In the present invention, as described in section A, which describes the array code structure, the information portion H _d of the parity check matrix H may be defined based on the array code structure according to the degree sequence defined as in Equation 18. .

FIG. 7 is a diagram showing an example of the information portion H _d of the parity check matrix generated in the same manner as described in section A, above, when the maximum variable node degree is 15. FIG. In the matrix structure illustrated in FIG. 7, each column and each row refers to a submatrix column and row. In addition, the numbers shown for each column and each row indicate a cyclic shift of sub-matrixes of each sub-matrix column and row. Each of the numbers consists of a pxp submatrix, where p is 89 in the submatrix. Therefore, the matrix of the information portion H _d generated as described above becomes a ( d _v · p ) x ( d _v · p ) matrix.

(B) Matrix Lifting and Parity Matrix Structures H _p  construction)

In general, lifting of a matrix refers to a method of lifting the size of a base matrix by sub-matrix replacement for a matrix having zeros and ones at arbitrary positions. This will be described with reference to FIG. 8. FIG. 8 shows a matrix lifting matrix of a basic 4x4 matrix into a 12x12 matrix by replacing each element of an arbitrary 4x4 matrix with a 3x3 identity matrix or a 3x3 0 matrix. .

As shown in FIG. 8, the matrix lifting consists of a square matrix having only zero elements by a multiple of the size to be lifted for the zero elements. In other words, let's look at the first line only. The elements of each column in the first row are {0, 0, 1, 0}, and the reference numerals 801, 802, 803, and 804 are assigned to them. Three elements 801, 802, and 804 having a value of zero among the elements were lifted by the 3x3 matrix, respectively, and lifted by reference numerals 801a, 802a, and 804a. The element 803 of the first row having an element of 1 was lifted by an identity matrix having a size of 3 × 3. The same applies to the elements of other columns.

As described above, matrix lifting refers to a method of expanding a matrix size by inserting a k x k sub-matrix at positions of elements of a base matrix composed of 0 and 1, in general. In this case, the inserted k x k matrix generally uses a cyclic permutation matrix in which each column of the identity matrix is cyclically shifted.

The parity portion H _p of the parity check matrix H to be defined in the present invention is a generalized dual-diagonal matrix as described in section B. In addition, in consideration of the fact that H _d generated as described in section (a) above consists of p x p sub-matrices, H _p Also A generalized dual-diagonal matrix of r x r is constructed by lifting using a p x p submatrix.

의 첫 번째 행에 존재하는 1은 제거한다. 도 9와 같이 구성된 패리티 부분 H _p 는 (rp )x(rp) 매트릭스가 되며, 각 서브 매트릭스

에서 j _i 는 각 서브 매트릭스마다 할당된 순환 열 이동(cyclic column shift)을 위한 옵셋 값(offset value)이다. 그러면 이제 선형 연산에 의한 부호화가 가능하도록 하는 방법에 대해 살펴보도록 한다.FIG. 9 is a diagram illustrating a parity matrix H _p configured through matrix lifting using a p x p cyclic substitution submatrix. Next, the parity matrix lifting will be described with reference to FIG. 9. The lifted matrix by the cyclic substitution submatrix is used for linear time encoding of low density parity code and linear independency between rows.

The 1 present in the first row of is removed. Parity portion H _p configured as shown in FIG. 9 becomes a ( rp ) x ( rp ) matrix, and each sub-matrix

J _i is an offset value for cyclic column shift allocated to each submatrix. Now, let's look at how to enable encoding by linear operation.

의 모든 열에 해당하는 패리티 심볼들을 구하기 위해서는 rp 만큼의 연산 동안 p개의 열에 해당하는 패리티 심볼에 대한 연산이 반드시, 오직 한 번씩만 이루어져야 한다. 이제 이러한 조건이 만족되기 위한 서브 매트릭스의 옵셋 값(offset value)에 대한 조건을 살펴보도록 한다.When salpin in the above-described B section (the generalized dual-diagonal matrix) bar applied to the parity part H _p lift (lifting) as shown in Figure 9, each of r, and when f is relatively prime to the parity part of the r single operation H _p It can be seen that the sub-matrix column is selected only once. In this single selection process, an operation for obtaining a parity symbol corresponding to any one column in a submatrix column may be performed. Thus, any one p x p submatrix

In order to obtain parity symbols corresponding to all columns of, operations on parity symbols corresponding to p columns must be performed only once for rp operations. Now look at the conditions for the offset value of the submatrix to satisfy these conditions.

와 열 인덱스(column index)

의 관계는 하기 <수학식 20>과 같이 정의된다.In the matrix structure of the parity portion H _p as shown in FIG. 9, a row index in a sub-matrix which is a sub-matrix row index i at a diagonal line.

And column index

Is defined as in Equation 20 below.

와 열 인덱스(column index)

의 관계는 하기 <수학식 21>과 같이 정의된다.Also, the row index in the submatrix that is the sub-matrix row index i of the offset diagonal line

And column index

Is defined as in Equation 21.

의 첫 번째 행으로부터 하기 <수학식 22>와 같이 패리티 심볼

의 값을 얻을 수 있다.Then, the sub-matrix that is the sub-matrix row index 0 from Equations 20 and 21 above.

Parity symbol as shown in Equation 22 from the first row of

You can get the value of.

In Equation 22, v ₀ is a partial check-sum value obtained from the first row of the information portion H _d of the parity check matrix. In addition, when the column index is j ₀ , the row index in the sub-matrix of the offset diagonal lines sharing the same column may be expressed by Equation 23 below.

In addition, the column indexes in the diagonal sub-matrix sharing the same row index may be shown as Equation 24 below.

If r and f in Equation 23 and Equation 24 are small, the parity portion H _p during r times of this process All sub matrices in a must be selected only once. Therefore, the row index in the sub-matrix obtained by repeating the above process r times can be represented as in Equation 25 below.

에 대해 업데이트 되는 열 인덱스의 변화량 x는 항상 하기 <수학식 26>과 같음을 알 수 있다.Lifting to the column indexes of all other sub-matrix in Equation 25, the sub-matrix existing in the diagonal line through an arbitrary r times

It can be seen that the change amount x of the column index updated with respect to Eq.

Theorem 2 : Finite field F _p = {0, 1, 2,... Defined by an arbitrary prime number p . , any non-zero element of p -1} can always produce all elements of F _p only once by _p or less additions to itself. To prove this, if k is smaller than p that satisfies Equation 27 for any non-zero element a of the finite field F _p , it violates the assumption that p is a prime number. Therefore, the minimum value of k that satisfies Equation 27 below is always p .

의 열 인덱스 변화량이 0이 아니면, 이러한 r번의 선형 연산을 모두 p번 반복하면 각 서브 매트릭스들의 p개의 열 인덱스에 대한 패리티 심볼을 생성할 수 있다. 따라서 rp개의 모든 패리티 심볼을 생성할 수 있게 된다. 즉, 하기 <수학식 28>과 같은 조건을 만족하게 된다.Therefore, any non-zero element a of the finite field F _p can generate all elements of F _p by an addition operation of p times or less. Any submatrix updated by theorem 2 to r linear operations

If the change in the column index of is not zero, repeating all r linear operations p times can generate a parity symbol for p column indexes of each submatrix. Therefore, all rp parity symbols can be generated. That is, the following condition is satisfied.

By repeating r operations as shown in Equation 28 p times, parity symbols corresponding to all columns in the submatrix can be generated. In addition, parity symbols corresponding to any one column in each of the remaining ( r -1) sub-matrix lines on the diagonal line may be generated one by one during the above r operations. Accordingly, it can be seen that a parity symbol having rp different column indices can be generated only once by the following rp linear operations.

A process of generating a matrix of the parity portion H _p based on the method described above will be described with reference to FIG. 10. 10 is a flowchart for generating a matrix of parity parts according to a preferred embodiment of the present invention.

을 v₀로 한다. 그리고, 1004단계로 진행하여 패리티 부분 H _p 의 사선상에서 서브 매트릭스 열 인덱스 0인 서브 매트릭스 상에 존재하는 패리티 심볼에 대한 열 인덱스

를 j₀로 초기화 한다.In order to generate a matrix of parity parts, the parity symbol calculation index n is set to 0 in step 1000. Thereafter, the method proceeds to step 1002 to obtain the information symbol sum v ₀ of the first column on the submatrix having the submatrix column index of 0 according to the matrix configuration of the information part H _d , and to obtain the first symbol on the submatrix. Parity symbol for a row

Let v ₀ be. In operation 1004, the column index for the parity symbol existing on the sub-matrix having the sub-matrix column index 0 on the diagonal of the parity portion H _p is obtained.

Is initialized to j ₀ .

를 결정하고, 열 인덱스를 초기화 한 후에 1006단계로 진행한다. 1006단계로 진행하면, 임의의 열 인덱스

에 대하여, 이와 동일한 열을 공유하는 옵셋 사선(offset diagonal line)에 존재하는 서브 매트릭스 내의 행 인덱스

을 하기 <수학식 29>와 같이 구한다.In this way, the sum of information symbols v ₀ is calculated according to the matrix configuration of the information portion H _d for the first row of the row, and thus the parity symbol for the first row.

Next, after initializing the column index, go to step 1006. Proceeding to step 1006, the random column index

For, the row indices in the submatrix that exist on the offset diagonal lines sharing this same column

Obtained as shown in Equation 29.

와 동일한 행 인덱스를 갖는 사선 상에 존재하는 서브 매트릭스 내의 열 인덱스

를 하기 <수학식 30>과 같은 식으로 계산한다.Then, the row diagonal along the offset diagonal

Column index in a submatrix that exists on an oblique line with a row index equal to

Calculate as shown in <Equation 30>.

인 행에 존재하는 정보 심볼의 합(sum)

를 구한다.In operation 1010, the row index in the sub-matrix having the sub-matrix row index i + ( rf ) is obtained.

Sum of the information symbols present in the row

Obtain

에 해당하는 패리티 심볼

을 하기 <수학식 31>과 같은 식을 이용하여 계산한다.And row index

Parity symbol

It is calculated using the equation as shown in Equation 31.

Thereafter, the process proceeds to step 1014, where n is increased by one. In operation 1016, the sub-matrix row index i is updated as shown in Equation 32 below.

In step 1018, n is checked for rp application. The check in step 1018 is to check whether the encoding is completed. When n is rp in step 1018, the routine is stopped because encoding is completed. However, if the check result n of step 1018 is not rp , the process proceeds to step 1006 and repeats the following process to continue the encoding.

Note that all index operations-sub-matrix row index, row index-mean modulo p operation, and subscript operation of index operation Is a modular p operation. The addition of the process of obtaining the parity symbol or the information symbol is a modular two operation. An example of H _p generated while satisfying such a condition may be illustrated in FIG. 11. The values of the numbers shown in FIG. 11 represent offset values of the sub matrices.

(C) the overall construction of low density parity codes; H )

The parity check matrix H for the low density parity code to be defined in the present invention is defined by dividing the matrix into an information part H _d and a parity part H _p and concatenating them for systematic encoding. Generation of the information part H _d and the parity part H _p is made by the method described in (a) section and (b) section, respectively, the generated information part H _d and the parity part H _p are each (d _v · p) x It is a _{(d v · p), (} rp) x (rp) matrix. Where d _v is the maximum variable node degree that exists on an irregular low density parity code, p is the dimension of the submatrix, and r is the dimension of the base matrix before lifting the parity portion H _p . . Therefore, r = d _v for concatenation.

Each matrix information part H _d , parity part H _p It is easy to see that there are no cycles of length 4 inside. In addition, if the diagonal offset f of the parity portion H _p is set to a value close to r / 2, even between the sub-matrix column of the information portion H _d having a column weight less than r / 2 and any column of the parity portion H _p . It is easy to see that there is no cycle of length 4. However, in the case of columns having a maximum variable node degree as a weight in the information portion H _d , there may be a cycle having a length of 4 with the columns of the parity portion H _p . This can be easily removed by properly selecting the sub-matrix offset value of the parity portion H _{p such} that there is no cycle of length 4 in the entire parity check matrix H.

2. Performance of LDPC code

So far, the structure of a parity check matrix for defining a rate 1/2 non-normal low density parity code, which can be easily performed by linear operation, has been described. In the parity check matrix defined in Chapter 1, the matrix is divided into an information part and a parity part to generate a parity symbol of a codeword according to a given information symbol. In addition, the matrix of the information part is constructed in such a way that the weight of each column has a degree close to the optimum irregular degree distribution of the variable node in the matrix structure based on the array code structure, and the matrix of the parity part is a generalized double diagonal line. The generalized dual-diagonal matrix structure was constructed by lifting using a sub-matrix having a random offset. At this time, the variable node with degree 2 is always assigned to the column of the parity part.

Now, let's take a look at the performance of the low-density parity check code formed by the parity check matrix defined above. To this end, a decoding algorithm and an experimental environment for evaluating the performance of the low density parity check code will be described first.

A. Iterative belief propagation decoding

The low density parity check code defined by the MxN parity check matrix may be represented by a factor graph composed of M check nodes and N variable nodes. And degree is d _c Inspection node with degree d _v If the message update process of the variable node in the log-domain is summarized, the message update of the test node may be shown as in Equation 33, and the message update of the variable node is shown in < It may be shown as in Equation 34, and the update of the log likelihood ratio (LLR) may be shown as in Equation 35 below.

은 준 반복 복호 과정에서 j 번째 반복 복호 과정에서 얻게 되는 값으로 검사 노드 m에서 변수 노드 n으로 전달하는 메시지이다. 그리고,

는 j 번째 반복 복호 과정에서 변수 노드 I로부터 검사 노드 m으로 전달되는 메시지이다. 이때, i 는 검사 노드 m에 연결된 변수 노드들을 0부터

까지 재 정렬한 값이다. 따라서 i 가 0인 경우에는 변수 노드 n을 의미한다.Of Equation 33

Is a value obtained from the j-th iterative decoding process in the quasi-iterative decoding process, and is a message transmitted from the check node m to the variable node n. And,

Is a message transferred from the variable node I to the check node m in the j th iterative decoding process. Where i represents the variable nodes connected to check node m from 0

This is a reordered value. Therefore, if i is 0, it means variable node n.

은 j 번째 반복 복호 과정에서 얻게 되는 값으로 변수 노드 n에서 검사 노드 m으로 전달하는 메시지이다. 이때

은 j 번째 반복 과정에서 검사 노드 i로부터 변수 노드 n으로 전달되는 메시지이며, i는 변수 노드 n에 연결된 검사 노드들을 0부터

까지 재 정렬한 값이다. 따라서 i가 0 인 경우에는 검사 노드 m을 의미한다.In Equation 34,

Is a value obtained from the j th iterative decoding process and is a message transmitted from the variable node n to the check node m. At this time

Is the message passed from the check node i to the variable node n during the j th iteration, and i is the number of check nodes connected to the variable node n starting from 0.

This is a reordered value. Therefore, if i is 0, it means the check node m.

은 j번째 반복 복호 과정에서 변수 노드 n에 정의되는 LLR 값이다.In Equation 35

Is the LLR value defined in the variable node n in the j th iterative decoding process.

Next, iterative belief propagation decoding will be described using the processes of Equations 33 to 35. 12 is a flowchart of an iterative reliable proliferation decoding process using Equations 33 to 35.

12 is a process of decoding a message received from the point of view of the receiver. Therefore, the initial message of the variable node n for the received message is defined as channel reliability of the nth symbol of the received codeword, which can be expressed as Equation 36 below.

=

=

은 최초 정의되는 변수 노드 메시지의 초기 값이고,

은 최초 정의되는 변수 노드에 대한 초기 LLR 값이다. 이와 같이 메시지 갱 신 시에 1200단계에서 상기 <수학식 36>과 같이 수신된 부호어의 n번째 심볼의 채널 신뢰도로 정의한다. 또한 반복 횟수 카운터를 리셋한다. 그런 후 1202단계로 진행하여 검사 노드의 메시지를 갱신한다. 이러한 갱신은 상술한 <수학식 33>과 같은 방법으로 갱신을 수행할 수 있다. 그리고, 1204단계로 진행하여 가변 노드와 로그 우도율을 갱신한다. 상기 가변 노드의 메시지 갱신은 상기 <수학식 34>와 같은 방법으로 갱신을 수행하며, 로그 우도율의 갱신은 <수학식 35>와 같은 방법을 통해 갱신한다.In Equation 36,

Is the initial value of the variable node message that is defined first,

Is the initial LLR value for the initially defined variable node. In this manner, when the message is updated, it is defined as the channel reliability of the nth symbol of the received codeword as shown in Equation 36 in step 1200. It also resets the repeat count counter. The process then proceeds to step 1202 to update the message of the check node. Such an update may be performed in the same manner as in Equation 33 described above. In operation 1204, the variable node and the log likelihood are updated. The update of the message of the variable node is performed in the same manner as in Equation 34, and the update of the log likelihood is updated in the manner as in Equation 35.

After all of the check node, the variable node, and the log likelihood are updated through the above procedure, the process proceeds to step 1206 to hard determine the value of the updated log likelihood. In operation 1208, the parity check is performed on the received message based on the hard decision value. If the parity check result has a value of 0, since decoding is successfully performed, decoding is stopped in step 1216. However, if the result of the parity check does not have a value of 0, the process proceeds to step 1210 to check whether the repetition is performed a predetermined number of times. If the repetition is performed a predetermined number of times as a result of the check in step 1210, since the probability of success is small even if the decoding is no longer performed, the process proceeds to step 1214 to perform a decoding failure process. However, if the repetition is not repeated a predetermined number of times as a result of the test of step 1210, the method proceeds to step 1212 and increments the repetition counter by one and proceeds to step 1202.

B. Simulation environment

An experimental environment for evaluating the performance of the low density parity check code formed by the parity check matrix defined in the present invention was performed in the environment as shown in Table 1 below.

Code rate = 1/2, maximum variable node degree = 15-Offset ( f ) in H _p = 7-Frame size = 435 ( p = 29), 795 ( p = 53), 1545 ( p = 103), 3855 ( p = 257)-Binary antipodal signaling over AWGN channel-Iterative belief propagation decoding-Floating point simulation-Maximum number of iterations = 160-Stop by parity check at each iteration-Frame error rate (FER) & information bit error rate (BER evaluation

Also, in the present invention, for convenience of discussion, the code rate of the low density parity code is limited to 1/2. However, the parity check matrix design of the low density parity code to support more various code rates may be discussed by lifting the scheme defined in the present invention according to the code rate. In addition, the maximum variable node degree is set to 15 on the factor graph of the low density parity code based on the parity check matrix defined in the present invention, which is excellent in performance and does not increase the hardware size (H / W size) in the implementation. To do this. The offset f is set to 7 in the parity partial H _p matrix. The reason why such an offset is defined is that the cycle of length 4 is easily eliminated in the parity check matrix as described in Section C of the present invention. The frame size of the low density parity check code tested in the present invention is set similarly to the encoder packet (EP) size specified in the cdma2000 1xEV-DV standard, which is currently used in the cdma2000 1xEV-DV standard. It is compared with the performance of the turbo decoder. In this case, a log-map algorithm (Log-MAP algorithm) was used in the decoding process of the turbo code for performance comparison, and the maximum number of repeated decoding was limited to eight times.

함수의 오버 플로우(overflow)를 방지하기 위해 |x|<10^-8인 x에 대해

의 값을 20으로 제한하였다. 저밀도 패리티 검사 코드의 복호기 상에서는 매 반복(iteration)마다 패리티 검사를 수행하여 stopping criterion으로 삼고 패리티 검사에서 오류가 검출되지 않았으나, 실제로 오류가 발생한 경우에는 비검출 오류(undetected error)가 발생한 프레임(frame)으로 분류하였다. 마지막으로 본 발명에서 설계한 저밀도 패리티 검사 코드의 성능을 평가하는 measure로는 프레임 오류율(frame error rate)과 비트 오류율(bit error rate)을 사용하였다. 이때 프레임/비트 오류(frame/bit error)란 정보 심볼에 오류가 발생한 경우만을 고려하였다. 이제 위에서 제시한 실험 환경에서 실험한 저밀도 패리티 검사 코드의 성능을 보이도록 한다.
On the other hand, the maximum number of iterations of the iterative belief propagation decoder of the low density parity check code is set to 160. This is in consideration of the fact that the convergence rate of the irregular low density parity check code is relatively slow in the density evolution technique. In addition, an experiment on a decoder performed a floating point simulation in which extrinsic & log likelihood ratio information (LLR information) is expressed as a real value. During the update of the check node

For x with | x | <10 ^-8 to avoid overflow of the function

The value of is limited to 20. On the decoder of the low-density parity check code, parity check is performed at every iteration and used as stopping criterion, and no error is detected in the parity check. However, if an error actually occurs, a frame in which an undetected error occurs is generated. Classified as Finally, a frame error rate and a bit error rate were used as a measure for evaluating the performance of the low density parity check code designed in the present invention. In this case, only a case in which an error occurs in an information symbol is referred to as a frame / bit error. Now we show the performance of the low density parity check code tested in the experimental environment presented above.

C. Simulation results

FIG. 13A is a diagram illustrating a matrix of information parts Hd when n = 870 and p = 29 as an example, and FIG. 13B is a diagram illustrating a matrix of parity parts Hp when n = 870 and p = 29 as an example. 13C is a graph of a simulation result comparing the performance of a low density parity check code and a turbo code.

The matrix of the information part and the matrix of the parity part shown in FIGS. 13A and 13B are constructed according to the present invention described above. In practice, the two matrices are combined to perform encoding. Next, the conditions in the case of showing the performance as shown in FIG. 13C will be described. To compare the performance of the two coding methods, the performance of the case where the coded packet (EP) size of the cdma2000 1xEV-DV standard is 408 and the code rate is 1/2 is also shown. As shown in FIG. 13C, when the block size is small, the performance of the turbo code used in the cdma2000 1xEV-DV standard is higher than the performance of the low density parity check code proposed by the present invention. It can be seen that both error rate (BER) is slightly superior. This indicates that the parity check matrix structure that defines the low density parity check code proposed by the present invention is not an optimized structure in terms of decoding performance of a codeword having a small block size. That is, when the coding block size of the low density parity check code is small, it indicates that the optimization of the parity check matrix should be further performed in order to show the excellent performance of the low density parity check code compared to the performance of the known turbo code. can do. However, it can be seen that the decoding performance of a codeword with a large block size is more effective than the turbo code.

Table 2 below shows the average number of repeated decoding for each Eb / No when n = 870. Although a maximum of 160 iterative decodings are performed for a given low density parity check code, the actual decoding result indicates that sufficient performance can be obtained by only 10 iterative decodings considering high SNR within 20 times.

Eb / No (dB) Average number of iterations  1.6  15.085  1.8  11.353  2.0  9.317  2.2  8.01  2.4  7.087

14A is a diagram illustrating a matrix of information portions Hd when n = 1590 and p = 53 as an example, and FIG. 14B is a diagram illustrating a matrix of parity portions Hp when n = 1590 and p = 53 as an example. 14C is a graph of a simulation result comparing the performance of a low density parity check code and a turbo code.

The matrix of the information part and the matrix of the parity part shown in FIGS. 14A and 14B are constructed according to the present invention described above. In practice, the two matrices are combined to perform encoding.

Next, the conditions in the case of showing the performance as shown in FIG. 14C will be described. To compare the performance of the two coding methods, the performance of the case where the coded packet size of the cdma2000 1xEV-DV standard is 792 and the code rate is 1/2 is also shown. Referring to FIG. 14C, as the block size of the low density parity check code increases, the frame error rate shows a performance almost similar to that of the conventional turbo code. However, the bit error rate still shows poor performance compared to turbo code. This is because the rate of bit errors present in the frame where the error of the turbo code is generated is lower than that of the low density parity check code. That is, the turbo code has a lower BER / FER ratio than the low-density parity code at the same Eb / No. If the BER / FER ratio is low, the average number of bit errors in the frame where the error occurs It is less than the low density parity check code. However, since the performance of the frame error rate is better than that of the bit error rate in an actual wireless communication system employing hybrid ARQ, the low density parity check code of the present invention is cdma2000 according to FIG. 14C. It can be seen that the performance is comparable to the turbo code of the 1xEV-DV standard.

Table 3 below shows the average number of repeated decoding for each Eb / No when n = 1590. As the block size increases, it can be seen that the average number of iterative decodings has increased slightly compared to the case of <Table 2>. However, at a sufficiently high SNR, it can be seen that only 20 times of repetitive decoding can achieve sufficient performance.

Eb / No (dB) Average number of iterations  1.1  40.308  1.3  21.504  1.5  14.858  1.7  12.018  1.8  11.020

FIG. 15A is a diagram illustrating a matrix of information portions Hd when n = 3090 and p = 103 as an example, and FIG. 15B is a diagram illustrating a matrix of parity portions Hp when n = 3090 and p = 103 as an example. 15C is a graph of a simulation result comparing the performance of a low density parity check code and a turbo code.

The matrix of the information part and the matrix of the parity part shown in FIGS. 15A and 15B are constructed according to the present invention described above. In practice, the two matrices are combined to perform encoding.

Next, the conditions in the case of showing the performance as shown in FIG. 15C will be described. To compare the performance of the two encodings, the performance of the case where the encoding packet size of the cdma2000 1xEV-DV standard is 1560 and the encoding rate is 1/2 is also shown. As shown in FIG. 15C, as the block size of the low density parity check code increases, the frame error rate is better than that of a turbo code having a similar frame size. Although the bit error rate is still poor performance compared to the turbo code as in Figure 14c, the difference is much reduced, showing that the performance is very close to the turbo code performance.

Table 4 below shows the average number of times of repeated decoding according to each Eb / No when n = 3090. As the size of the block increases, it can be seen that the average number of iterative decodings has increased slightly compared to the case of <Table 2>. However, at a sufficiently high SNR, it can be seen that only 20 times of repetitive decoding can achieve sufficient performance.

Eb / No (dB) Average number of iterations  1.1  38.495  1.2  22.051  1.4  16.190  1.5  14.623

FIG. 16A illustrates a matrix of the information portion H _d when n = 7710 and p = 257 as an example, and FIG. 16B illustrates a matrix of the parity portion H _p when n = 7710 and p = 257 as an example. FIG. 16C is a graph showing a simulation result comparing the performance of the low density parity check code and the turbo code, and FIG. 16D is a graph of the simulation result according to the change in the number of repetitions of the low density parity check code.

The matrix of the information part and the matrix of the parity part shown in FIGS. 16A and 16B are constructed according to the present invention described above. In practice, the two matrices are combined to perform encoding.

Next, the conditions in the case of showing the performance as shown in FIG. 16C will be described. For comparison of performance, the performance of the case where the coded packet size of cdma2000 1xEV-DV standard is 3864 and the code rate is 1/2 is also shown. FIG. 16C shows that when the block size of the low density parity check code is very large, the performance is superior to that of a turbo code having a similar frame size. In particular, the turbo code with a frame length of 3864, which is used in the cdma2000 1xEV-DV standard, has an error floor at both the frame error rate and the bit error rate at a high signal-to-noise ratio (SNR). It can be seen that is occurring. However, in the case of the low density parity check code defined in the present invention, it was confirmed that such an error floor did not occur. This performance is very advantageous in communication systems using H-ARQ. Accordingly, it can be said that the low density parity check code defined in the present invention is very superior in performance compared to the turbo code used in the existing standard. Table 5 below shows the average number of repeated decoding for each Eb / No when n = 7710.

Eb / No (dB) Average number of iterations  0.9  41.036  1.0  31.034  1.1  25.507  1.2  22.170

As shown in Table 5, as the block size of the low-density parity check code increases, it can be seen that the average number of times of repeated decoding increases compared to the case of Table 4 above. That is, a low density parity check code that supports a maximum frame size similar to the cdma2000 1xEV-DV standard requires more than 20 iterative decodings even at high signal-to-noise ratios. In order to achieve the performance, it is necessary to observe the performance of the low density parity check decoder (LDPC decoder) according to the iteration number.

FIG. 16D is a diagram illustrating respective FER / BER performances obtained when the maximum iteration number is limited to 40, 80, 120, and 160 in the low density parity check code having the configuration shown in FIGS. 16A and 16B. to be. Unlike the previous case, when the maximum number of repeated decoding was limited to 40, 80, and 120 times, a slight decrease in performance was observed. However, except that the maximum repetition number of decoding is limited to 40 times, the deterioration of the performance that is generated is considered not so large, and even if the maximum number of repetitive decoding is limited to about 80 times, it will not be a big problem in terms of performance. In particular, when the block size is smaller than this, the performance degradation due to limiting the maximum iteration decoding to 80 times will be further reduced and become very insignificant. Therefore, in the low density parity check code proposed in the present invention, assuming that the maximum code block size is about 7710 times, if the maximum number of iterations is about 80 times, sufficient performance can be obtained during decoding.

3. Conclusions

In the present invention, only a case where code rate is 1/2, a low density parity check code that can efficiently encode and obtain excellent decoding performance is defined. For this purpose, the parity check matrix defining the low density parity check code is partitioned into two parts, and a part corresponding to the information of the codeword in the parity check matrix has an array code having a row weight greater than 2 (column weight). array code) structure. The part corresponding to the parity of the codeword in the parity check matrix is defined in the form of a generalized dual diagonal matrix having row weights of two. The parity check matrix defined in this way generates a non-normal low density parity check code with a maximum variable node degree of d _v = 15, and is applied to the white Gaussian noise channel (AWGN channel) by a density evolution technique by Gaussian approximation. Therefore, we can see that the threshold for error free is 0.9352. This is a performance close to 0.5819 dB compared to Shannon's channel capacity for codes with a code rate of 1/2.

Considering that linear coding is possible first, without considering the possibility of actual linear coding, and designing a parity check matrix in a more random manner, it is 0.5819 dB to Shannon's threshold. It is possible to generate good low density parity check codes that are much closer. However, in such a case, the encoding process becomes complicated and there may be a problem in the actual implementation. Since enabling linear coding acts as a constraint on the parity check matrix defining the low density parity check code, the parity check matrix must have an arbitrary structure. Therefore, the possibility of showing good performance will be less than the arbitrarily defined parity check matrix without considering linear coding. Therefore, when the present invention is applied, relatively excellent performance is considered in consideration of linear coding. That is, despite the constraints of the parity check matrix according to the linear coding, relatively good performance is shown.

In addition, in order to show excellent performance in decoding, in order to define the degree distribution of the parity check matrix, the size of the codeword is increased, and accordingly, increasing the maximum variable node degree has a performance close to the limit of Shannon. Low density parity check codes can be designed. However, in this case, as the maximum variable node degree increases, the complexity of the decoder during decoding increases, which is far from the actual implementation. Therefore, the reason that the decoder complexity is possible is to set a reasonably maximum variable node degree to implement.

The low density parity check code by the parity check matrix defined in the present invention has a form of a generalized double diagonal matrix in which the parity portion of the codeword in the parity check matrix is lifted by cyclic permutation of the p x p identity matrix. Therefore, the coding can be easily performed by a simple linear operation. In addition, when the decoding performance by iterative belief propagation is compared with the performance of the turbo code used in the cdma2000 1xEV-DV standard, it is confirmed through experiments that a better frame error rate can be obtained for a similar frame size. It was. In particular, having an excellent frame error rate compared to the turbo code will be a very good advantage when using the low-density parity check code of the present invention in combination with the hybrid-ARQ technique. Therefore, the low density parity check code defined in the present invention can be easily encoded by a simple linear operation. In addition, in the implementation of the decoder, a check node processor and a variable node processor are implemented in parallel for each row and column of the sub-matrix_ so that the decoder is very fast. Decoding of speeds is possible.

The low density parity check code defined in the present invention can be easily confirmed that there is no cycle having a length of 4 in the factor graph defining the low density parity check code due to the arrangement structure of the sub matrices constituting the parity check matrix.

As described above, in the case of applying the present invention, a performance similar to or better than that of a turbo encoder can be provided, and in particular, there is an advantage of generating a low density parity check code that can reduce a frame error rate. In addition, the low-density parity check code of the present invention has an advantage of reducing complexity even when decoding.

Claims (9)

A method for generating a low density parity check code consisting of an information partial matrix and a parity partial matrix, Changing the information submatrix into an array code structure and assigning a degree sequence to each submatrix column; Expanding the offset value between diagonal lines in the generalized double diagonal matrix, which is the parity partial matrix, to have an arbitrary value; Lifting the generalized double oblique matrix. Determining an offset value for a cyclic column shift for each sub-matrix of the lifted generalized double diagonal matrix; An encoding process of determining a parity symbol corresponding to a column of the parity partial matrix, Low parity check code generation method, characterized in that the number of rows of the sub-matrix is a prime number. The method of claim 1, wherein the degree sequence is configured as shown in Equation 37. 4.

The method of claim 1, wherein the offset value between the oblique lines is A method for generating a low density parity check code characterized by the number of columns in a generalized double diagonal matrix and the mutual dissipation. delete The method of claim 1, The difference between the sum of the offset values for the cyclic row movement of the diagonal sub-matrix and the offset values for the cyclic row movement of the offset diagonal sub-metric in the generalized double diagonal matrix that is the parity partial matrix is not zero. How to generate low density parity check code. delete delete delete delete

Images