CN105024703B - Based on the long LDPC of quasi-cyclic middle short code and codec and coding method - Google Patents

Abstract

Present invention discloses one kind to be based on the long LDPC of quasi-cyclic middle short code and codec and coding method, and the structure of code word is H=[H '₁Π P '], H₁' it is information bit matrix, P ' is check bit matrix, and Π P ' is to do capable transformation to the check bit matrix, wherein information bit matrix H₁' it include multiple circulation submatrix p_i,j, each circulation submatrix can only be unit circle excursion matrix or full null matrix.Using technical solution of the present invention, pass through a large amount of analogue simulations, the information bit matrix structure for being more suitable for a kind of LDPC code word of HSS decoding algorithm than the prior art is had found, and using encoder, the decoder of this LDPC code, improves the performance of LDPC code word.

Description

Short and Medium Code Length LDPC Based on Quasi-Cycle and Its Codec and Encoding Method

technical field

The present invention relates to an LDPC codeword, an encoder, a decoder, and a corresponding encoding method using the codeword, and more specifically, relates to a quasi-circular-based short-medium code length LDPC, a codec, and an encoding method.

Background technique

Low density parity check code word (Low density Parity Check, LDPC) can be divided into two types according to its structure, one is random code word, the most classic one is MacKay code, he also has a special webpage to give him Various codewords (MacKay1999) (Richardson2001) (Luby2001) (Richardson and Urbanke2001); another type is a codeword designed based on an algebraic combinatorial structure (Combinatorial). Random codewords can approach the Shannon limit very well, but due to the randomness of the '1' distribution, the design of the encoder and the decoder are not feasible in parallel or regularity, so it is not suitable for systems that require a certain throughput , so it has not been widely used.

The emergence of codewords based on algebraic combination structures has solved this problem very well. Among them, there is a class of codewords based on Finite Geometry that have good performance (Y.Kou and S.Lin2001) , but the disadvantage of this type of codeword is that due to the relatively high density of its H matrix (large row weight and column weight), when using a class of algorithms based on belief propagation, the complexity is very high. Another class of quasi-cyclic codewords (Quasi-cyclic LDPC, QC-LDPC) is a very important class of codewords constructed based on algebraic combinations. The main construction of the QC-LDPC codeword is based on the quasi-cyclic identity sub-matrix. (J.L.Fan2000)(R.M.Tanner2001)(R.M.Tanner2001)(T.Okamura2003)(R.M.Tanner2004) This kind of quasi-circular identity sub-matrix structure is very suitable for hardware that implements parallel operations, such as translation with high parallelism and high throughput. Encoder. Although the traditional QC-LDPC codeword is suitable for the implementation of a decoder with a high degree of parallelism and improves the throughput rate, the generation matrix of the QC structure obtained through the reverse method may not be sparse, or even if it is sparse, it uses the generation matrix to generate It is not obvious to obtain the parity bit by encoding, and it must be obtained by seeking a linear equation system, so the encoder of the traditional QC-LDPC codeword is relatively complicated. In order to solve this problem, scholars Zhang and Ryan first proposed the Structured Irregular Repeat Accumulator code (S-IRA) LDPC codeword (Zhang and Ryan2006). , which can be coded in a very simple and efficient way. This kind of codeword structure has the following characteristics, the matrix part corresponding to the information bits is composed of quasi-circular sub-matrixes, and the matrix part corresponding to the check bits is composed of double diagonal matrices.

At present, the S-IRA code word has been widely used in major communication standards, mainly including the second generation of European digital broadcasting and television transmission standard DVB series (ETSI, 2006, DVBT22009, DVB-C22009, DVB-NGH2012); IEEE802.11n Wireless Local Area Network Standard (IEEE802.11n2009); IEEE802.11e Wireless Wide Area Network Standard (IEEE802.16e2006); China Digital Television Terrestrial Transmission Standard (DTTB) (GB20600-2006); Mobile Multimedia Broadcasting (CMMB2006); Communication system (CCSDS2007); and some standards for disk storage devices, etc. Judging from the development trend of the entire international digital communication field, there will be more standards that are using LDPC codewords or will use them in the future.

From the standards that have been submitted so far, especially the DVBT2 and DVBS2 standards that are very commercially successful, and the DVB-NGH standard (finalized at the end of 2012) that has only recently set standards and has broad commercial prospects, the S- The check matrix corresponding to the IRA codeword mainly uses the following structure:

H=[ΠH ₁ P]

Where H ₁ is the matrix part corresponding to the information bits, Π is a certain form of row transformation for H ₁ , and P is the matrix part corresponding to the parity bits.

and:

is composed of L x J Circular subarrays of size or 0 matrices.

For example, the first structure of P _i,j looks like this:

At this time, P _{i, j} is composed of two unit offset matrices. Further, P _{i, j} may also be composed of N unit circulant matrices, where N>2 is an integer.

The second structure of P _i,j is as follows:

At this time, P _{i, j} is composed of an all-zero matrix.

Since P _i,j may consist of more than one unit cyclic matrix, it is not suitable for hardware implementation of HSS (Horizontalshuffle scheduling) decoding algorithm. There are many references to this point in the literature on the implementation methods of DVBT2 and S2, and related solutions to sacrifice complexity are proposed.

And P is the matrix part corresponding to the parity bit, which is the following bidiagonal matrix:

Contents of the invention

The purpose of the present invention is to provide a kind of medium-short code length LDPC based on quasi-cyclic and codec and coding method, to solve the problems caused by the structure of check matrix of common S-IRA LDPC code in the prior art. It is suitable for HSS (Horizontal shuffle scheduling) decoding algorithm and affects the performance of the entire LDPC codeword.

This patent proposes a structure in which P _{i, j} consists of only 0 or 1 unit circulant matrix. Under the condition of maintaining performance, it is suitable for HSS decoding. At the same time, a codeword with specific parameters and its code table are proposed, and the corresponding encoding method encoder, decoding method and decoder are proposed.

According to above-mentioned purpose, implement a kind of S-IRA LDPC code word that is used for codec of the present invention, the structure of its code word is: H=[H ' ₁ ΠP '], H ₁ ' is information bit matrix, P ' is the check bit matrix, and ΠP' is the row transformation of the check bit matrix. Wherein, the information bit matrix H ₁ ′ includes multiple cyclic sub-matrices p _i,j , and each cyclic sub-matrix can only be a unit cyclic offset matrix or an all-zero matrix.

According to above-mentioned purpose, implement a kind of LDPC coder of the present invention, it adopts a kind of LDPC codeword of S-IRA structure, the structure of S-IRA LDPC codeword is: H=[H' ₁ ΠP'], H ₁ ' is the information bit matrix, P' is the parity bit matrix, and ΠP' is the row transformation of the parity bit matrix. Wherein, the information bit matrix H ₁ ′ includes multiple cyclic sub-matrices p _i,j , and each cyclic sub-matrix can only be a unit cyclic offset matrix or an all-zero matrix.

According to above-mentioned purpose, implement a kind of LDPC decoder of the present invention, it adopts the LDPC code word of a kind of S-IRA structure, the structure of S-IRA LDPC code word is: H=[H ' ₁ ΠP '], H ₁ ' is the information bit matrix, P' is the parity bit matrix, and ΠP' is the row transformation of the parity bit matrix. Wherein, the information bit matrix H ₁ ′ includes multiple cyclic sub-matrices p _i,j , and each cyclic sub-matrix can only be a unit cyclic offset matrix or an all-zero matrix.

According to the above-mentioned main features, the information bit matrix of the encoder, the decoder and the S-IRA LDPC code word of the present invention is a matrix of m rows × n-m columns:

The size of each cyclic sub-matrix p _i,j is

According to the above-mentioned main features, the check bit matrix P' of the encoder, the decoder and the S-IRA LDPC code word of the present invention is a matrix of m rows * m columns: Its main diagonal and secondary diagonal are all 1, and the rest of the positions are 0.

According to above-mentioned purpose, implement the encoding method of S-IRA LDPC code word of the present invention and comprise the following steps:

Obtain information bits {i ₀ , i ₁ , i ₂ , i ₃ , i ₄ , i ₅ ,...,i _nm-1 };

Initialize parity bits p ₀ =0, p ₁ =0, p ₂ =0, p ₃ =0, p ₄ =0,...,p _m-1 =0;

Make a modulo 2 sum of each parity bit p _i and the information bits connected to it, i=0,1,2...m-1, and rearrange them to obtain the rearranged parity bit sequence

The rearranged parity bit sequence Do the accumulation as follows:

p' ₀ =p' ₀

According to above-mentioned purpose, implement LDPC encoding method and encoder of the present invention, wherein the encoding operation module built-in encoder has adopted the encoding method of described LDPC, and it comprises:

Calculate check bits Among them, j=0,1,2,3,...,m-1; Represents the information bits associated with p _j in the low density parity check matrix; y _j is the information bits The serial number of is obtained according to the following formula:

Wherein, q=24, m=192 (for code length n=1920) or m=576 (for code length n=5760), x represents the address of the information bits participating in the accumulation of parity bits, and the code table of x is as follows Two code tables with different code lengths:

Code table 1: code rate 9/10m=192, code length n=1920

Code table 2: code rate 9/10m=576, code length n=5760

Adopted the technical scheme of the present invention, through a large number of emulations, found out the information bit matrix structure of a kind of S-IRALDPC code word that is more suitable for HSS (Horizontal shuffle scheduling) decoding algorithm than prior art, and use this The encoder and decoder of the S-IRA LDPC code, thus producing an unexpected improvement in the performance of the S-IRA LDPC code word.

Detailed ways

The technical solutions of the present invention will be further described below in conjunction with the accompanying drawings and embodiments.

The difference between the HSS (Horizontal Shuffle Scheduling) algorithm and the Flooding algorithm is that the Flooding algorithm must wait until all the row operations are completed, and then update the obtained data at one time, and then use it in the next iteration. In a certain iteration of the HSS algorithm, the result obtained after each row operation can be updated immediately and used in the next row operation still in this iteration, which can greatly improve the convergence speed of the decoding algorithm. On the other hand, the HSS algorithm only needs to save n pieces (n is the code length) of soft information data, and m×2 (m is the number of rows of check matrix) rows of soft value information. Compared with the Flooding algorithm, Save a lot of chip area.

However, when the existing HSS algorithm selects a cyclic sub-block, the cyclic sub-block is usually not a unit sub-block, but two or more unit sub-blocks, which will inevitably lead to memory access conflicts in the process of parallel operation. This is because if the loop sub-block is composed of more than two unit sub-blocks, when the loop sub-block is operating in parallel rows, there will be two rows of row operation inputs that require reading the same block of memory at the same time, and after the operation is completed Then write to the same block of memory at the same time. This not only fails to achieve the original intention of the HSS algorithm, but also causes memory conflicts.

Therefore, based on the shortcomings of the LDPC codeword structure in the existing standards, specifically, the cyclic sub-matrix in the information bit matrix may be composed of multiple cyclic identity matrices, which is not suitable for the realization of the HSS decoding algorithm. The present invention proposes The structure of a new S-IRA LDPC codeword, the structure of its parity check matrix is as follows:

H=[H′ ₁ ΠP′]

Wherein, H ₁ ' is the information bit matrix, P' is the check bit matrix, and ΠP' is a certain form of row transformation for the check bit matrix P'.

The information bit matrix H ₁ ′ is a matrix of m rows×nm columns, and its specific structure is as follows:

In the present invention, the information bit matrix H ₁ ′ includes multiple cyclic sub-matrices p _i,j , and the size of each cyclic sub-matrix p _i ,j in H ₁ ′ is Each cyclic sub-matrix can only be a unit cyclic offset matrix or an all-zero matrix, that is, H ₁ ′ here consists of L×J The size of the unit cyclic offset matrix or 0 matrix. The unit cyclic offset matrix here refers to a unit matrix of the same size that is cyclically shifted to the right.

According to the limitation of the above-mentioned p _{i, j} structure, it can be obtained that the cyclic sub-matrix p _{i, j} of the present invention can only be the following two specific structural forms:

At this time, p _{i, j} is formed by the unit cyclic offset matrix.

2) At this time, p _{i, j} is formed by an all-zero matrix.

On the other hand, in order to cooperate with the structure of the information bit matrix H ₁ ', the check bit matrix P' of the present invention is a matrix of m rows×m columns, and its specific structure is as follows:

It can be seen from the above structure that the check bit matrix P' is a special double diagonal matrix, its main diagonal is all '1', and the secondary diagonal is also '1', and the rest of each row and column Some positions are '0'.

The present invention also discloses a kind of LDPC coder in addition, what it adopts is exactly above-mentioned S-IRALDPC code word, specifically, the concrete structure of its parity check matrix is:

H=[H' ₁ ΠP'], where H ₁ ' is the information bit matrix, P' is the check bit matrix, and ΠP' is the row transformation of the check bit matrix. In particular, the information bit matrix H ₁ ′ includes multiple cyclic sub-matrices p _i,j , and each cyclic sub-matrix can only be a unit cyclic offset matrix or an all-zero matrix.

The present invention also discloses a kind of LDPC decoder in addition, what it adopts is exactly above-mentioned S-IRALDPC code word, specifically, the specific structure of its parity check matrix is:

H=[H' ₁ ΠP'], where H ₁ ' is the information bit matrix, P' is the check bit matrix, and ΠP' is the row transformation of the check bit matrix. In particular, the information bit matrix H ₁ ′ includes multiple cyclic sub-matrices p _i,j , and each cyclic sub-matrix can only be a unit cyclic offset matrix or an all-zero matrix.

Since both the encoder and the decoder of the present invention use the LDPC codewords disclosed above, other detailed characteristics of the LDPC codewords have been disclosed in the above specification, and will not be repeated here.

In addition, the present invention also discloses the encoding method of above-mentioned LDPC code word, and its main steps are as follows:

Step S1: Get the information bits, set the known information bits as {i ₀ , i ₁ , i ₂ , i ₃ , i ₄ , i ₅ ,...,i _nm-1 }, the so-called encoding is to use the parity check matrix H finds the parity bit:

Step S2: Initialize parity bits p ₀ =0, p ₁ =0, p ₂ =0, p ₃ =0, p ₄ =0,...,p _m-1 =0;

Step S3: Perform a modulo 2 sum of each parity bit p _i and the information bits connected to it, where i=0, 1, 2...m-1. Afterwards, rearrange the above-mentioned modulo 2 and the following parity bits p _i :

p _iQ '=p _i ; p _iQ+1 '=p _i+q ; p _iQ+2 '=p _i+2q ; p _iQ+3 '=p _i+3q ;

p _iQ+4 '=p _i+4q ,...,p _iQ+Q-1 '=p _i+(Q-1)q ;

where i=0,1,2,3,...,q-1 and in

Thus, the rearranged parity bit sequence is obtained

Step S4: the rearranged parity bit sequence Do the accumulation as follows:

p' ₀ =p' ₀

Finally, the parity bit sequence is obtained:

It can be seen from the technical solution disclosed in the description of the present invention that the S-IRALDPC code word of the present invention is characterized in that the cyclic sub-matrix in its information bit matrix can only be composed of a unit cyclic offset matrix except for the structure of the 0 matrix, The selection of this cyclic sub-matrix adapts to the technical characteristics of the HSS algorithm parallel computing is based on the cyclic sub-block, so when the cyclic sub-block is operated in parallel rows, there is no need to read the same block of memory at the same time for the row operation input of two rows , and there is no writing the same piece of content at the same time after the operation is completed, which can avoid memory conflicts.

According to the S-IRA LDPC code formed by the information bit matrix and check bit matrix of the present invention, the encoder and decoder applying the LDPC code of the present invention can have better code word performance in the HSS algorithm.

In addition, the present invention also discloses an encoding method and an encoder corresponding to the above-mentioned S-IRA LDPC codeword, and can correspond to the above-mentioned structure. The encoder has a built-in encoding operation module, and the encoding operation module adopts the following LDPC encoding method:

In the encoding operation module,

Calculate check bits Among them, j=0,1,2,3,...,m-1; Represents the information bits associated with p _j in the low density parity check matrix; y _j is the information bits The serial number of is obtained according to the following formula:

Wherein, q=24, m=192 (for code length n=1920) or m=576 (for code length n=5760), x represents the address of the information bits participating in the accumulation of parity bits, and the code table of x is as follows Two code tables with different code lengths:

Code table 1: code rate 9/10m=192, code length n=1920

Code table 2: code rate 9/10m=576, code length n=5760

Specifically, let the codeword of LDPC be:

c＝(i ₀ ,i ₁ ,...,i _j ,...,i _K-1 ,p ₀ ,p ₁ ,...,p _m-1 ); among them, (i ₀ ,i ₁ , ...,i _nm-1 ) are information bits, which are known {1,0} sequences. (p ₀ , p ₁ , p ₂ ,..., p _m-1 ) are parity bits, which are bits to be calculated.

First, initialize each parity bit corresponding to the parity part,

That is, p ₀ =0, p ₁ =0, p ₂ =0, p ₃ =0, p ₄ =0, p ₅ =0,...,p _m-1 =0, where each p _i represents a verification A row in the matrix, for example, p _m represents the mth row in the parity check matrix.

The parity bits are grouped into groups of q bits to obtain multiple parity bit groups.

Specifically, first, set the parity bit as:

{p ₀ ,p ₁ ,p ₂ ,p ₃ ,p ₄ ,p ₅ ,...,pm _-1 }. Then, the parity bits are sequentially grouped into groups of q bits to obtain multiple parity bit groups.

For example, the check bit group is:

{p _jq+0 ,p _jq+1 ,...,p _jq+(q-1) }, where j is (0, 1, 2,..., Q-1), where

Secondly, the check bits in each check bit group and their associated information bits in the low-density parity check matrix are accumulated.

Specifically, perform the following XOR operation on the q bits p _m in each parity bit group:

Among them, j=0,1,2,3,...,m-1; Represents the information bits associated with p _j in the low density parity check matrix; y _j is the information bits The serial number of is obtained according to the following formula:

Wherein, q=24, m=192 (for code length n=1920) or m=576 (for code length n=5760), and x represents the address of the information bits participating in the accumulation of parity bits

x represents the first check bit (for example, p ₀ , p _q+0 , p _2q+0 , ..., p _jq+0 , ...) in each check bit group represents the low The row of the density parity check matrix (corresponding to the 0th, q, 2q, 3q, ..., jq, ... row) in the position of the column where "1" is located, but does not include the low density parity check matrix The column position of the "1" in the checksum section.

Taking the code word of code table 1 as an example, q=24, the number of check bits m=192, and the number of information bits n−m=1728.

The first line of numbers in code table 1:

6

Each number represents the position of "1" in the first row (corresponding to the first parity bit p ₀ ) in the low-density parity check matrix (that is, the position of the column), but this position does not include the low-density parity check matrix The column position of "1" in the parity part of the parity matrix.

In addition, the number of this line is x, which represents the position of "1" in the 0th row in the parity check matrix represented by the first bit p ₀ in the first parity bit block (that is, the position of the column, and the column is the same start counting with 0).

Then there are:

Then, according to the formula:

For other rows, the above formulas are followed in turn, and they are not listed here.

Afterwards, interleave processing is performed on the accumulated parity bits.

Specifically, it includes: interleaving the accumulated parity bits according to the permutation format, wherein the permutation format is realized by the following formula:

p _iQ '=p _i ; p _iQ+1 '=p _i+q ; p _iQ+2 '=p _i+2q ; p _iQ+3 '=p _i+3q ;

p _iQ+4 '=p _i+4q ,...,p _iQ+Q-1 '=p _i+(Q-1)q ;

Wherein, i=0, 1, 2, 3, ..., q-1.

E.g,

p ₀ '=p ₀ ; p ₁ '=p _0+q ; p ₂ '=p _0+2q ; p ₃ '=p _0+3q ;

p ₄ '=p _0+4q ,...,p _Q-1 '=p _0+(Q-1)q ;

p _Q '=p ₁ ; p _Q+1 '=p _1+q ; p _Q+2 '=p _1+2q ; p _Q+3 '=p _1+3q ;

p _Q+4 '=p _1+4q ,...,p _2Q-1 '=p _1+(Q-1)q ;

p _(q-1)Q '=p _q-1 ; p _(q-1)Q+1 '=p _(q-1)+q ; p _(q-1)Q+2 '=p _{(q-1 )+2q} ;

p _(q-1)Q+3 '=p _(q-1)+3q ;

p _(q-1)Q+4 '=p _(q-1)+4q ,...,p _(q-1)Q+Q-1 '=p _(q-1)+(Q-1)q ;

in,

In this embodiment, {p ₀ , p ₁ , p ₂ , p ₃ , p ₄ , p ₅ ,...,p _m-1 } represent parity bits before interleaving;

{p ₀ ', p ₁ ', p ₂ ', p ₃ ', p ₄ ', p ₅ ',..., p _m-1 '} represent parity bits after interleaving.

Finally, a modulo 2 addition operation is performed on each parity bit after the interleaving process to obtain the final parity bit.

Specifically, this step is implemented through the following formula:

p′ ₀ = p′ ₀

The obtained (p ₀ ', p ₁ ',...p _m-1 ') is the final coded parity bit, and the final LDPC code c=(i ₀ ,i ₁ ,...,i _j ,...,i _nm-1 ,p ₀ ',p ₁ ',...,p _m-1 ').

For solving the problem of memory conflict when the LDPC code is used for the HSS algorithm by sacrificing complexity in the prior art, the S-IRA LDPC code of the present invention, the coder that uses S-IRA LDPC code, the information bit matrix in the decoder Selecting the design can produce unexpected technical effects. From the code word structure itself, the complexity of the HSS algorithm is effectively reduced, and the technical problems in the above-mentioned prior art are solved.

Those skilled in the art should recognize that the above description is only one or several implementations among many embodiments of the present invention, rather than limiting the present invention. Any equivalent changes, modifications and equivalent replacements to the above-mentioned embodiments will fall within the protection scope of the claims of the present invention as long as they conform to the spirit and scope of the present invention.

Claims (2)

1. a coding method of LDPC code, is characterized in that, comprises the following steps: Calculate check bits Among them, j=0,1,2,3,...,m-1; Represents the information bits associated with p _j in the low density parity check matrix; y _j is the information bits The serial number of is obtained according to the following formula: Wherein, the number of bits q=24 in the bit group, the number of check bits m=192, for the code length n=1920 or m=576, for the code length n=5760, x represents the number of information bits participating in the accumulation of parity bits address, the code table of x is the following two code tables with different code lengths: Code table 1: code rate 9/10m=192, code length n=1920 Code table 2: code rate 9/10m=576, code length n=5760 2. A kind of LDPC encoder, is characterized in that, described encoder comprises: Encoding operation module for calculating parity bits Among them, j=0,1,2,3,...,m-1; Represents the information bits associated with p _j in the low density parity check matrix; y _j is the information bits The serial number of is obtained according to the following formula: Wherein, the number of bits q=24 in the bit group, the number of check bits m=192, for the code length n=1920 or m=576, for the code length n=5760, x represents the number of information bits participating in the accumulation of parity bits address, the code table of x is the following two code tables with different code lengths: Code table 1: code rate 9/10m=192, code length n=1920 Code table 2: code rate 9/10m=576, code length n=5760