KR20060108959A - Method and apparatus for generating low density parity check matrix in block units and its recording medium - Google Patents

Abstract

The present invention relates to a method and apparatus for generating a parity check matrix on a block basis that does not require an inverse matrix operation and enables back-substitution in the entire matrix region when generating a parity bit, and a recording medium thereof. According to the method, a low-density parity check matrix is divided in a vertical direction, and a matrix in a block unit is generated such that a double diagonal matrix is disposed on an upper portion of a divided region corresponding to a second parity bit vector, and the generated double diagonal matrix is generated. Dividing the low density parity check matrix in a horizontal direction based on the step S, and generating a block unit matrix included in regions divided in the vertical and horizontal directions of the low density parity check matrix such that column weights of the block units of the low density parity check matrix are the same. Parity check row that can generate parity bits more easily, including It can provide.

Description

Method and apparatus for generating low density parity check matrix by block and recording medium

1 is a diagram illustrating a format of a parity check matrix converted by the Richardson method.

2 is an example of a conventional low density parity check matrix in block units.

3 is a conceptual diagram between a low density parity check matrix H 'and a codeword matrix x in units of blocks during low density parity check coding or decoding.

4 is an operation flowchart of a method for generating a low density parity check matrix on a block basis according to the present invention.

5A to 5D are examples illustrating a process of generating a parity check matrix according to the present invention.

6 is a detailed flowchart of step 404 of FIG.

7 is an exemplary diagram of a parity check matrix for generating a cycle 4 phenomenon in the present invention.

8 is an exemplary diagram of a unit matrix block, a -1th negative shift matrix block, and a + 1st positive shift matrix block used in the present invention.

9 is a functional block diagram of a low density parity check matrix generator according to the present invention.

The present invention relates to a method and apparatus for generating a parity check matrix, and more particularly, to a method and apparatus for generating a low-density parity check matrix on a block basis that facilitates parity bit generation.

As a method for generating additional information for error correction, a low density parity check (hereinafter, referred to as LDPC) coding method is widely used. Low-density parity check coding is a method of generating a parity bit using a low-density parity check matrix H composed of '0' and '1' and significantly less than the number of '0'.

The number of 1s included in each row or column in the parity check matrix is called a row degree and a column degree, respectively. A parity check matrix is called a regular parity check matrix, and a case where it is not an irregular parity check matrix is called a parity check matrix. In the regular parity check matrix, the row order is called row weight (Wr), and the column order is called column weight (Wc).

Parity bit generation using LDPC coding is performed by equation (1).

In Equation 1, H is an m * n parity check matrix, and X is a codeword matrix of n * 1. X consists of a message data vector S of length (n-m) and a parity bit vector P of length m. Therefore, the message data vector length (n-m) + parity bit vector length (m) = n.

The basic concept of such LDPC coding is D.J. MacKay, "Good error-correction codes based on very sparse matrices," IEEE Trans. on Information Theory, vol. 45, no. 2, pp. 399-431, 1999, according to this document, the parity bits can be generated by solving Equation 1 using matrix operations such as Gaussian elimination. However, in the case of LDPC coding, since the code length is long and the size of the parity check matrix H is very large, the encoding process using the Gaussian elimination method is very complicated.

To solve this problem, a method of converting a parity check matrix into another format has been developed. That's T.J. Richardson's efficient encoding. 1 is a diagram illustrating a format of a parity check matrix converted by the Richardson method.

According to Richardson's method, parity check matrix H is converted into parity check matrix H 'by row and column exchange. As shown in FIG. 1, the transformed parity check matrix H 'must have all components of the upper right diagonal portion 100 set to zero. That is, the converted parity check matrix H 'is composed of A, B, C, D, E, and T areas, and the T areas of the upper right diagonal portion 100 are all zero.

According to Richardson's method, since t components of the upper right diagonal portion 100 of the parity check matrix are all zero, t parity bits can be easily obtained by back-substitution, so parity bit generation It is easy. However, to obtain m-t parity bits, an inverse matrix operation is still required. The process of obtaining m-t remaining parity bits is as follows.

Equation 1 is converted into Equation 2 by the method of Richardson.

In Equation 2, S is a message data vector, P ₁ , and P ₂ are a first parity bit vector and a second parity bit vector, respectively. Equation 2 is represented by the matrix equations of Equations 3 and 4.

AS + BP ₁ + TP ₂ = 0, CS + DP ₁ + EP ₂ = 0

(-ET ^-1 A + C) S + (-ET ^-1 B + D) P ₁ = (-ET ^-1 A + C) S + φP ₁ = 0

In Equation 4, the Richardson matrix φ is (−ET ⁻¹ B + D). When the equations 3 and 4 are combined and solved, the first parity bit vector P ₁ and the second parity bit vector P ₂ may be defined as shown in Equations 5 and 6.

P ₁ =-(-ET ^-1 B + D) ^-1 (-ET ^-1 A + C) S = -φ ^-1 (-ET ^-1 A + C) S

P ₂ = -T ^-1 (AS + BP ₁ )

According to the above method, even though t parity information can be easily obtained by the inverse substitution method, parity bit generation is not easy because the remaining mt parity information must calculate an inverse matrix operation, that is, φ ⁻¹ .

The same applies to the case of using the existing low-density parity check matrix in block units. 2 is an example of a low-density parity check matrix in block b that includes a fixed number of 1s in rows and columns. In FIG. 2, one diagonal matrix is formed in the T region using the unit matrix block, and the unit matrix and the shift matrix are randomly arranged in the A, C, B, D, and E regions.

Accordingly, the parity bits corresponding to the blocks included in the T region can be easily obtained by back-substitution, but the blocks of the E region defined by the gap are random in the unit matrix block and the shift matrix block. In order to obtain the parity bits corresponding to the blocks of the E region and the D region, the parity bit generation is not easy because the inverse matrix operation φ ^-1 must still be calculated.

Accordingly, the present invention has been made to solve the above-described problem, and in generating a parity bit, there is no need for an inverse matrix operation and a block-based parity check matrix generation method capable of back-substitution in the entire matrix region; An apparatus and a recording medium thereof are provided.

In order to achieve the above object, the present invention, a) partitioning the region of the low density parity check matrix in the vertical direction based on the length of the first parity bit vector and the second parity bit vector; b) the divided Generating a matrix in block units such that a double diagonal matrix is disposed on an upper portion of a region corresponding to the second parity bit vector; c) dividing an area of the low density parity check matrix in a horizontal direction based on the double diagonal matrix; d) generating a block unit matrix included in the vertically and horizontally divided regions of the low density parity check matrix such that the column weights of the block units of the low density parity check matrix are the same.

In order to achieve the above object, the present invention includes a first region dividing unit for dividing the region of the low density parity check matrix in the vertical direction based on the lengths of the first parity bit vector and the second parity bit vector; A double diagonal matrix block generation unit generating a matrix in units of blocks such that a double diagonal matrix is arranged on an upper portion of a divided region of the low density parity check matrix corresponding to the second parity bit vector; A second region dividing unit dividing the low density parity check matrix region in a horizontal direction based on the double diagonal matrix generated by the double diagonal matrix block generating unit; And a block unit matrix generation unit configured to generate a block unit matrix included in regions divided in a vertical direction and a horizontal direction of the low density parity check matrix such that the column weights of the unit blocks of the low density parity check matrix are the same. .

In order to achieve the above object, the present invention provides a computer-readable recording medium having recorded thereon a program for executing a block parity check matrix generation method in a computer, the method comprising: a) a first parity bit; Dividing an area of the low density parity check matrix in a vertical direction based on a length of a vector and a second parity bit vector; b) generating a matrix in block units such that a double diagonal matrix is disposed on an upper portion of the divided region corresponding to the second parity bit vector; c) dividing an area of the low density parity check matrix in a horizontal direction based on the double diagonal matrix; And d) generating a block unit matrix included in a vertically and horizontally divided region of the low density parity check matrix such that the column weights of the block units of the low density parity check matrix are the same. do.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings.

3 is a conceptual diagram of a low density parity check matrix H ′ 300 and a codeword matrix x 310 in a parity check equation defined by Equation 2 in the low density parity check coding or decoding of a block unit.

Referring to FIG. 3, the parity check matrix H '300 is m * n and the code word matrix x 310 is n * 1. The code word matrix x 310 is composed of a message data vector S having a length of (nm) and a parity bit vector P _{1 having a} length m1 and a parity bit vector P ₂ having a length m2. Thus, the message data vector length (nm) + first parity bit vector length (m1) + second parity bit vector length (m2) = n and m1 + m2 = m. As can be seen in Fig. 3, the areas A, C, B, D, T, and E of the low density parity check matrix H'300 have a message data vector length, a first parity bit vector length, and a second parity bit vector length. Can be determined by.

4 is an operation flowchart of a method for generating a low density parity check matrix on a block basis according to the present invention. Referring to FIG. 4, the region of the low density parity check matrix H 'is vertically divided based on the length m1 of the first parity bit vector P1 and the length m2 of the second parity bit vector P2 illustrated in FIG. 3. Accordingly, the low density parity check matrix H '300 of FIG. 3 is divided into three equal parts in the vertical direction at points 501 and 502, as shown in FIG. Point 501 may be determined by the length m2 of the second parity bit vector P2, and point 502 may be determined by the length m1 of the first parity bit vector P1. However, point 501 may be implemented to be determined by one of the length m2 of the second parity bit vector P2 and the length m1 of the first parity bit vector P1, and the point 502 is the length of the first parity bit vector P1. It can be implemented to be determined by one of m1 and the length (nm) of the message data vector S.

Next, as shown in FIG. 5B, a double diagonal matrix 504 is generated above the region 503 corresponding to the second parity bit vector P2, thereby generating a matrix in block units (402). At this time, all of the component blocks of the upper end 505 of the block-by-block double diagonal matrix 504 generate a zero matrix block. The double diagonal matrix 504 can be generated using a unit matrix block. However, the double diagonal matrix 504 may generate a matrix of block units such that a unit matrix block is arranged in an upper diagonal matrix and a shift matrix block is arranged in a lower diagonal matrix.

Based on the double diagonal matrix 504 generated in step 402, the low density parity check matrix H 'is horizontally divided at point 506 shown in FIG. 5C. Accordingly, the low-density parity check matrix H 'is stored in the A and C regions corresponding to the message data vector S, the B and D regions corresponding to the first parity bit vector P1, and the second parity bit vector P2, as shown in (300) of FIG. It is divided into corresponding T and E regions. Region A may be an upper region corresponding to the message data vector S, and region C may be defined as a lower region corresponding to the message data vector S. FIG. The region B may be defined as an upper region corresponding to the first parity bit vector P1, and the region D may be defined as a lower region corresponding to the first parity bit vector P1. The T region may be defined as an upper region corresponding to the second parity bit vector P2, and the E region may be defined as a lower region corresponding to the second parity bit vector P2.

When divided into six regions as described above, the divided regions A, C, B, D, and E generate a block-by-block matrix such that the cycle 4 condition, the preset column weight condition, and the condition for the Richardson matrix φ are generated ( 404).

FIG. 6 is a detailed flowchart of step 404 of FIG. 4. Referring to FIG. 6, a process of generating a block unit matrix in areas A, C, B, D, and E of the low density parity check matrix H 'is as follows.

First, a block unit matrix is generated in a region E such that the unit matrix block, the shift matrix block, and the zero matrix block are arranged as shown in FIG. 5 (d). As can be seen from the region E shown in FIG. 5 (d), in the region E, a unit matrix block is disposed in the rightmost block unit column, and among the unit matrix block and the shift matrix block in the region except the rightmost block unit column. A block unit matrix is generated such that one and zero matrix blocks are alternately arranged in the vertical direction and the horizontal direction. The shift matrix block used in FIG. 5 (d) is a + 1th positive shift matrix block. As illustrated in FIG. 8, the +1 th positive shift matrix block is a matrix block in which the position of 1 included in the unit matrix 801 is shifted by one space to the right as shown in 803.

A block unit matrix is generated in the region B such that the shift matrix block, the unit matrix block, and the zero matrix block are arranged as shown in FIG. 5 (d). That is, a block unit matrix is generated such that a unit matrix block and a shift matrix block are alternately arranged in a horizontal direction, and a shift matrix block is arranged at a predetermined position of a column in which the shift matrix block is arranged in the top block unit row. do. In FIG. 5 (d), the predetermined position corresponds to the position of the lowermost straight block. The shift matrix in the region B uses a negative first shift matrix block. The -1th negative shift matrix is a matrix block in which the unit matrix is shifted left by one, as shown at 802 shown in FIG.

A block unit matrix is generated in the region D such that the shift matrix block, the unit matrix block, and the zero matrix block are arranged as shown in FIG. 5 (d). That is, in the lowest block unit row, a unit matrix block is arranged, and a matrix of block units is generated such that a shift matrix block is arranged in a block immediately above the block located on the leftmost side in the least significant block unit row in the D region. The shift matrix block used in the D region is the + 1th positive shift matrix block.

Next, the block unit matrix is sequentially generated while checking the type of the matrix block already created in the A and C regions to satisfy the cycle 4 condition in the A and C regions (604). The cycle 4 condition is to arrange the block unit matrix to prevent the cycle 4 phenomenon in which the positions of the unit matrix blocks 701, 702, 703, and 704 form a quadrangle as shown in FIG. 7. This is because normal parity bit check coding and decoding cannot be expected when the cycle 4 phenomenon occurs. If the position of the unit matrix block 701 corresponds to, for example, the position of the (2, 2) block, the position of the unit matrix block 702 corresponds to the position of the (2, 8) block, and the unit The position of the matrix block 703 may correspond to the position of the (4, 2) -th block and the position of the unit matrix block 704 may correspond to the position of the (4, 8) -th block.

The block generation matrix generation order for the E, B, and D regions of FIG. 6 may be changed. In addition, the positions of the zero matrix, the unit matrix, and the shift matrix in the E, B, and D regions are the conditions for preventing the cycle 4 phenomenon in the E, B, T, and D regions, the conditions under which the Richardson matrix φ becomes the unit matrix, and the column weights. (Wc) is previously determined to satisfy the same condition.

Further, a block unit matrix is generated in the A and C regions so that the column weights Wc for the parity check matrix satisfy the same condition. Block unit matrix generation in areas A and C is performed after block unit matrix generation in areas B, D, E, and T. 5D illustrates a case in which the thermal weight is three. The shift matrix block used in the B, D, E, and T regions may use a + P th positive shift matrix block or a -P th negative shift matrix block. The + P-th positive shift matrix block is a matrix block in which the position of 1 in the unit matrix block is shifted P spaces to the right, and the -P-th negative shift matrix block is the P-block shifted 1 position in the unit matrix block to the left. Matrix block.

Accordingly, the parity check matrix as shown in FIG. 5 (d) may be generated. The numeral " 0 " described in the blocks in the areas B, D, E, and T of FIG. 5 (d) represents an unmated unit matrix block, and " -1 " represents a matrix block in which a negative shift is performed. "+1" represents a matrix block in which both shifts have been made. In Figure 5 (d) bM ₁ = m1, bM ₂ = m2, b is the length of one block. Unmarked blocks represent zero matrix blocks.

9 is a functional block diagram of an apparatus for generating a parity check matrix according to an embodiment of the present invention.

The first region dividing unit 901 divides the parity check matrix region set in advance in the vertical direction. That is, the parity check matrix region set in advance is divided in the vertical direction by using the input first parity bit vector length and the second parity bit vector length as shown in FIG. However, as noted in FIG. 4, point 502 is determined using one of the message data vector length and the first parity bit vector length, and one of the first parity bit vector length and the second parity bit vector length is used. In operation 501, the parity check matrix region may be divided in the vertical direction.

The double diagonal matrix block generator 902 is a block unit matrix such that a double diagonal matrix is disposed on an area corresponding to the second parity bit vector in the parity check matrix vertically divided by the first region divider 901. Create That is, as described in step 402 of FIG. 4, a matrix in block units is generated such that a double diagonal matrix is arranged.

The second area divider 903 divides the parity check matrix in the horizontal direction based on the double diagonal matrix block generated by the double diagonal matrix block generator 902. Accordingly, the parity check matrix block is divided into six regions as shown in FIG.

The block unit matrix generator 904 preliminarily satisfies the conditions in which the column weights of the parity check matrix are the same, the condition preventing the cycle 4 phenomenon, and the condition that the Richardson matrix φ becomes the unit matrix for the B, D, E, and T regions. A block unit matrix is generated in the B, D, E, and T regions based on the block unit matrix type information and the position information set in FIG. That is, if the B, D, E, and T regions are 8x8 blocks, as shown in FIG. 5 (d), the block is based on the position of the block previously set to generate the matrix block and the type information of the corresponding matrix block. The unit matrix generator 904 generates a block unit matrix. For example, if the block position in which the double diagonal matrix of the T region is arranged and the type information of the matrix block corresponding thereto are set as the unit matrix block, the block unit matrix generator 904 at the block position where the double diagonal matrix is disposed is the unit. Create a matrix block.

In addition, the block unit matrix generator 904 blocks previously generated in the region A and the C region so that the column weights of the region A and the region C satisfy the same condition and the condition that prevents the cycle 4 phenomenon. Create a block unit matrix by checking the type of the unit matrix. Accordingly, the block unit matrix generator 904 generates a block density low parity check matrix as shown in FIG. 5 (d). As shown in FIG. 5 (d), since the unit matrix block is disposed in the rightmost column of the E region, inverse substitution is possible for the entire region of the parity check matrix.

When using the parity check matrix generated in this way, the first parity bit vector and the second parity bit vector may be defined as in Equations 7 and 8.

P ₁ =-(-ET ^-1 A + C) S

P ₂ = -T ^-1 (AS + BP ₁ )

As can be seen from Equation 7, according to the present invention, it is not necessary to calculate the inverse matrix operation φ ^-1 .

Meanwhile, the parity check matrix generation method according to the present invention can be created by a computer program. Codes and code segments constituting the program can be easily inferred by a computer programmer in the art. In addition, the program is stored in a computer readable media, and read and executed by a computer to implement a parity check matrix generation method. The information storage medium includes a magnetic recording medium, an optical recording medium, and a carrier wave medium.

So far I looked at the center of the preferred embodiment for the present invention. Those skilled in the art will appreciate that the present invention can be implemented in a modified form without departing from the essential features of the present invention. Therefore, the disclosed embodiments should be considered in descriptive sense only and not for purposes of limitation. The scope of the present invention is shown in the claims rather than the foregoing description, and all differences within the scope will be construed as being included in the present invention.

As described above, according to the present invention, since the inverse matrix operation is not required when generating the parity bits and inverse substitution is possible for all regions of the parity check matrix, it is possible to generate the parity bits more easily.

Claims (15)

In the block density generation parity check matrix generation method, a) dividing an area of the low density parity check matrix in a vertical direction based on a length of a first parity bit vector and a second parity bit vector; b) generating a matrix in block units such that a double diagonal matrix is disposed on an upper portion of the divided region corresponding to the second parity bit vector; c) dividing an area of the low density parity check matrix in a horizontal direction based on the double diagonal matrix; d) generating a block unit matrix included in the vertically and horizontally divided regions of the low density parity check matrix such that the column weights of the block units of the low density parity check matrix are the same. The method of claim 1, wherein the step b) uses the unit matrix block to generate a matrix of the block unit so that the double diagonal matrix is arranged. The method of claim 1, wherein b), b1) generating a matrix in units of blocks such that a unit matrix block is disposed in an upper diagonal matrix of the double diagonal matrix; And b2) generating a matrix in units of blocks such that a shift matrix block is disposed in a lower diagonal matrix of the double diagonal matrix. The method according to any one of claims 1 to 3, wherein step d) The location of the unit matrix block, the shift matrix block, and the zero matrix block is determined so that the divided region of the low density parity check matrix other than the area corresponding to the upper portion is prevented from the block 4 cycle 4 phenomenon, and based on the determined position. Generating a matrix in units of blocks. The method of claim 4, wherein the d) step, A unitary matrix block and a shift matrix in the partitioned region such that the Richardson matrix φ for the divided region corresponding to the first parity bit vector and the second parity bit vector in the low density parity check matrix is an identity matrix Determining positions of blocks and zero matrix blocks, and generating a matrix in units of blocks based on the determined positions. The method of claim 4, wherein the d) step, d1) In the lower region corresponding to the upper portion of the divided region, a unit matrix block is disposed in the rightmost block unit column, and in the lower region, among the unit matrix block and the shift matrix block in the region except for the rightmost block unit column. Generating a matrix in units of blocks such that one and zero matrix blocks are alternately arranged in a vertical direction and a horizontal direction; d2) In the upper region corresponding to the first parity bit vector among the divided regions, the most significant block unit row is disposed by alternately arranging a unit matrix block and a shift matrix block in a horizontal direction, and shift matrix blocks are arranged in the most significant block unit row. Generating a matrix in units of blocks such that a shift matrix block is disposed at a predetermined position of an arranged column; d3) In the lower region corresponding to the upper part corresponding to the first parity bit vector among the divided regions, a unit matrix block is arranged in the lowermost block unit row, and is located in a block immediately above the block located on the leftmost side in the least significant block unit row. Generating a matrix in block units such that a shift matrix block is disposed; And d4) generating a block-by-block matrix while checking a type of a matrix block that has already been generated in order to prevent the cycle-four phenomenon of the block-by-block in a region corresponding to a message data vector among the divided regions. 7. The method of claim 6, wherein the shift matrix is one of a + p th positive shift matrix block and a -p th negative shift matrix block. 8. The method of claim 7, wherein said p has a value of one. The method of claim 6, wherein the shift matrix block used in step d2) is a + p th positive shift matrix block, and the shift matrix block used in step d3) is a -p th negative shift matrix block, and d4) And wherein the shift matrix block used in the step is a + p-th positive shift matrix block. In the low density parity check matrix generator in block units, A first region dividing unit dividing an area of the low density parity check matrix in a vertical direction based on a length of a first parity bit vector and a second parity bit vector; A double diagonal matrix block generation unit generating a matrix in units of blocks such that a double diagonal matrix is arranged on an upper portion of a divided region of the low density parity check matrix corresponding to the second parity bit vector; A second region dividing unit dividing the low density parity check matrix region in a horizontal direction based on the double diagonal matrix generated by the double diagonal matrix block generating unit; And And a block unit matrix generator for generating a block unit matrix included in regions divided in a vertical direction and a horizontal direction of the low density parity check matrix such that column weights of the unit blocks of the low density parity check matrix are the same. The method of claim 10, wherein the double diagonal matrix block generator, And generating a matrix in units of blocks so that the double diagonal matrix is arranged using a unit matrix block. The method of claim 10, wherein the double diagonal matrix block generator, The upper diagonal matrix of the double diagonal matrix is arranged in the unit matrix block, the lower diagonal matrix of the double diagonal matrix generates a matrix in block units such that the shift matrix block is arranged. The block unit matrix generation unit of claim 11 or 12, wherein the block unit matrix generation unit is prevented from cycle-by-block 4 phenomenon in a region corresponding to the first parity bit vector and the second parity bit vector in the divided region, and the Richardson matrix and a block unit matrix is generated based on the block unit matrix type information and the position information which are set in advance so that φ becomes the unit matrix. The matrix unit of claim 13, wherein the block unit matrix generation unit selects a type of the matrix block already generated in the divided region in order to prevent the cycle 4 phenomenon in the block unit in the divided region corresponding to the message data vector. Device for generating a block unit matrix while checking. A computer-readable recording medium having recorded thereon a program for executing a method of generating a low-density parity check matrix on a block basis in a computer, The method, a) dividing an area of the low density parity check matrix in a vertical direction based on a length of a first parity bit vector and a second parity bit vector; b) generating a matrix in block units such that a double diagonal matrix is disposed on an upper portion of the divided region corresponding to the second parity bit vector; c) dividing an area of the low density parity check matrix in a horizontal direction based on the double diagonal matrix; And and d) generating a block unit matrix included in the vertically and horizontally divided regions of the low density parity check matrix such that the column weights of the block units of the low density parity check matrix are the same.

Images