CN1753315A - Coding method of low density oven odd check code - Google Patents

Abstract

This invention discloses an encoding method for a low density odd-even check code including: 1, determining code rate R and a code length N and computing the check bit length M, 2, constructing the H to the power p matrix of MxM, 3, determining the structure parameter line weight t of the H to the power d, rank weight q and a sub-matrix dimension u, 4, utilizing the arithmetic sequence to comprise the vector v to constitute matrix D finally, 5, the D matrix and a group of its orthogonal D matrix group constitute matrix H to the power d, 6, evaluating the code sequence c and construct the H matrix, H=H to the power p:H to the power d.

Description

A kind of coding method of low density parity check code

Technical field

The invention belongs to information theory channel coding technology field, be specifically related to the coding method of a kind of low-density checksum (LDPC) sign indicating number, the present invention can with 3G mobile communication standard compatibility, be mainly used in broadband radio multi-media communication.

Background technology

In more than 50 year since Shannon is set up information theory, channel coding theorem is used widely in a plurality of fields such as deep space communication and satellite communication, transfer of data, storage, mobile communication, file transfers and digital audio video transmissions.And produced five class standards thus, promptly be used for deep space and satellite communication the Aerospace Data Systems coding standard, be used for the high speed data modulations demodulation the trellis coded standard, be used for disk compression storage system RS coding standard, mobile cellular communication coding standard, be used for the CRC coding standard of HDLC agreement.At present, the next generation network of studying (NGN) is organically blending of all new generation network technology such as soft switchcall server net, IPv6 data the Internet, 3G (Third Generation) Moblie net, various broadband access network, intelligent optical fiber transmission network, require network have higher data transmission rate, bigger power system capacity, more high spectrum utilization, be more suitable for various channel conditions and Geng Gao QoS, in the hope of realizing that collection speech, image, video and data are the transmission of the multimedia integration business of one.In the face of the challenge of next generation network, existing error-correcting code technique is difficult to satisfy its transmission requirement, so a collection of new and effective error-correcting code technique arises at the historic moment.One of error correcting code that wherein performance is best, computation complexity is minimum is low-density checksum (LDPC) sign indicating number.

1993, C.Berrou etc. made the research of channel coding theorem stride forward a revolutionary step to the achievement in research that the world has announced Turbo code.Be subjected to the prompting of Turbo code iterative technique, people have expected low density parity check code (LDPC sign indicating number) and the iterative decoding algorithm thereof that R.gallager proposed in 1962 once more ^[2]The nineties later stage, Spielman et al. ^[3]Rediscover with MacKay et al. and developed the LDPC sign indicating number.The LDPC sign indicating number has become the research focus in error correcting code field at present, and becomes the rival of Turbo code, and the iteration signal treatment technology also is penetrated in each link of communication link.In the North America, Europe, Japan and other countries and area, existing a plurality of research groups are in the research work of being engaged in the LDPC sign indicating number.The application study of Turbo code moves to maturity, and has become the part of the third generation (3G) mobile communication standard recently.The coral coral of LDPC sign indicating number almost will misses this standard late.But have the expert to think, because the delay of 3G system deployment makes LDPC sign indicating number coding/decoding system probably participate in 3G standard.Recently, the basic solution of a LDPC sign indicating number is adopted by the DVB satellite communications standards.We can say that LDPC sign indicating number and Turbo code are to test the channel error correction encoding class of approaching shannon limit with application verification up to now, they will become the key areas of current and the following several years reliable communications Journal of Sex Research.

Studies show that the LDPC sign indicating number can be applied in the error control protection of a plurality of communications fields such as high speed optical fiber communication, broadband radio multi-media communication, IPv6 internet communication, space communication, Computer Storage and transmission system in future.Since the LDPC sign indicating number was appeared again, communication enineer and coding theory man had carried out number of research projects, and these work comprise: 1) the limiting performance analysis of LDPC sign indicating number, as density Evolution Theory, capacity limit, minimum range limit etc.; 2) efficient iterative decoding algorithm research as BP algorithm, MP algorithm, sum-product algorithm, minimum-sum algorithm and bit flipping algorithm, comprises their performance evaluation and improvement, effective realization design and convergence analysis; 3) design of structural analysis and building method is as based on the structure of the regular and irregular sign indicating number of sparse bigraph, factor graph or Tanner figure, the finite group and the design of structure, random structure sign indicating number and the Algebraic Structure sign indicating number of multi-element code etc.; 4) encryption algorithm design mainly is the research of linear expense encryption algorithm; 5) the LDPC sign indicating number is in the application in a plurality of digital processings field, as the LDPC sign indicating number magnetic recording channel, high speed optical fiber communication, deep space and satellite communication, Digital Subscriber Line, with the combining of the CDMA of mobile communication and OFDM technology, with combining of modulation technique etc.The research input of this, different aspects multi-faceted to the LDPC sign indicating number, great dynamics shows: the LDPC sign indicating number has application potential.

The LDPC sign indicating number is defined as the kernel of sparse parity check matrix H, can be summarized as follows by the structure of the H matrix of Gallager structure: 1) every row contain 1 number be one fixing than decimal d _v, d _v〉=3; 2) every row contain 1 number also be fix than decimal d _c, d _c〉=d _v3) be all 1 line number (being called overlapping number) between any two row and be no more than 1, promptly not containing four jiaos in the H matrix is 1 little square formation, does not also promptly have the circulation of 4 lines; 4) d _vAnd d _cAll much smaller than line number the M (=Nd of code word size N and matrix _v/ d _c), and when N → ∞, d _c/ N=d _v/ M → 0 shows that the H matrix is sparse.This is the H matrix of Gallager design before more than 30 year, even applied for patent at that time, has also lost efficacy now.Storage of large-scale sparse parity check matrix H at present and quick generation method, the algebraically construction problem of LDPC sign indicating number just, and the design problem of linear expense LDPC code coder is to hinder the bottleneck problem that the LDPC sign indicating number moves towards application always.Algebraically building method about the H matrix has the following representative research results: 1) MacKay of finder again of LDPC sign indicating number has proposed the method with the regular at random LDPC sign indicating number of computer search, produce the H matrix that does not contain the circulation of 4 lines at random, when code check is 1/2, code length is greater than 10 ⁴The time, performance reaches from about shannon limit 1.5dB, and he does not propose the algebraically building method of regular LDPC sign indicating number, and random code has only theoretical research to be worth, and does not have actual application value; 2) Yu Kou, Heng Tang etc. has proposed the LDPC sign indicating number based on finite geometry, Bane Vasic and Bassem Ammar propose to utilize the branch of Combinational Mathematics---balanced not exclusively packet design (BIBD), construct the LDPC sign indicating number, the weak point of this two algebra of classes structure LDPC sign indicating number is the change underaction of coding parameter, as can not first given code length and the value of code check, construct the H matrix then, but earlier according to algorithmic rule structure H matrix, determine code parameters according to the H matrix then, the code parameters of Que Dinging is difficult to and the existing standard compatibility like this, this two classes sign indicating number during the length block length, has good performance at high code check; 3) Gallager has only provided (N in its thesis for the doctorate, 3,4) construction algorithm of the sparse parity check matrix H of ad hoc structure LDPC sign indicating number, piecemeal submatrix in its H matrix is to be made of unit matrix and one group cyclic shift matrices, be called quasi-cyclic LDPC code (QC-LDPC sign indicating number) at present, he does not provide the building method of the sparse parity check matrix H of arbitrary structures, the method for designing of encoder is not proposed yet, R.M.Tanner and Marc.P.C.Fossorier further investigate the QC-LDPC sign indicating number on the research basis of Gallager, their basic thought is: by certain regularly arranged, be made up of one group of cyclic shift matrices of unit matrix and unit matrix thereof by this component masses matrix by a component masses matrix for the H matrix.The difference of the two is, the queueing discipline difference of matrix in block form in the H matrix.In the design of this external Tanner, the dimension u that requires matrix in block form is the even-multiple of prime number or prime number, and this restriction causes the value of code length and code check dumb, the negligible amounts of sign indicating number.In the design of Fossorier, the restrictive condition broad of u can be got prime number and other integer, but can not get this class integer of power of 2.As if it is dumb to cause the code check parameter of QC-LDPC sign indicating number to be selected to the restriction of u, is 0.5 sign indicating number as not designing code check, and the performance of QC-LDPC sign indicating number is 3-5dB, be not fine.

Summary of the invention

The object of the present invention is to provide a kind of coding method of low density parity check code, the low density parity check code that this coding method obtained has the characteristics of the low and code parameters flexible design of computation complexity, and this coding method also provides the building method of a sparse parity matrix.

The coding method of a kind of low density parity check code provided by the invention the steps include:

(1) determine code check R and code length N, and calculation check bit length M;

(2) H of structure M * M ^pMatrix

First of first row is " 1 " element, and all the other positions are " 0 " elements; First and second position of second row is " 1 " element, and all the other positions are " 0 " elements; From the third line, next line is to be obtained by 1 of lastrow ring shift right;

(3) according to code check R, determine H ^dThe capable weight t of matrix and column weight amount q, calculated sub-matrix dimension u again, t/ (q+t)=R wherein, ut=K, K are information bit length;

(4) utilize arithmetic progression structure D matrix, the D defined matrix is: to the u * u rank square formation of matrix element value on GF (2) finite field, its every row, every row all have only " a 1 " element, and all the other elements all are " 0 ";

(5) utilize D matrix construction H ^dMatrix;

(6) ask codeword sequence c, and structure H matrix, H=[H ^p H ^d];

Ask the process of codeword sequence c to be:

1. to appointing the information sequence c that gives ^d={ d _j, j=1,2 ... K}, utilize $H^p=[h_{\mathrm{ij}}^p:i=\mathrm{1,2},...,M,j=\mathrm{1,2},...,M]$ With

$H^d=[h_{\mathrm{ij}}^d:i=\mathrm{1,2},...,M,j=\mathrm{1,2},...,K]$ Matrix, according to following formula:

${\mathrm{Hc}}^T=\left[H^p{H}^d\right]\left[\begin{array}{c}{c}^p\\ c^d\end{array}\right]=H^p{c}^p+H^d{c}^d=0$

2. make c ^p={ p _i, i=1,2 ... M}, $p_1=\underset{j}{\mathrm{\Σ}}{h_{1j}^{d}d}_j$ Recursion can get $p_i=p_{i-1}+\underset{j}{\mathrm{\Σ}}{h}_{\mathrm{ij}}^d{d}_j$

3. ask codeword sequence c=[c ^p c ^d]={ cl, l=1,2 ... N}.

The concrete steps of above-mentioned steps (4) can for:

(4.1) utilize arithmetic progression to constitute the V vector, the general term formula of arithmetic progression is a _u=a ₁+ (u-1) b, wherein tolerance b is the integer greater than 2, u is the dimension of vector V, as first term a ₁Value be respectively 1,2 ..., during b, the general term formula of bringing arithmetic progression respectively into calculates, correspondence obtains b sequence, and this b sequence concatenation is constituted the 0th u n dimensional vector n V without cyclic shift together ₀, to u n dimensional vector n V ₀Ring shift left or move to right u-1 time, obtaining number is one group of V vector V of u ₀, V ₁, V ₂... v _U-1

(4.2) utilize V vectorial structure D ' matrix, the corresponding relation of the two is: the sequence number of " 1 " element column in the sequence number representing matrix of each element position in the vector, the sequence number that " 1 " element is expert in the value representation matrix of element in the vector, method is by one group of V vector V in view of the above ₀, V ₁, V ₂... V _U-1Correspondence obtains one group of quadrature D ' matrix D ₀', D ₁', D ₂' ..., D _U-1';

(4.3) from quadrature D ' matrix D ₀', D ₁', D ₂' ..., D _U-1' in an optional matrix as piecemeal submatrix D ₀, it is carried out cyclic shift obtains u piecemeal submatrix D ₀, D ₁, D ₂..., D _U-1

The concrete steps of above-mentioned steps (5) can for:

H ^dFirst row, first row of matrix are placed D ₀The piecemeal submatrix, D can not appear in all the other each row of each row again ₀The piecemeal submatrix;

To D ₀Piecemeal submatrix ring shift left or move to right gs time, s=1 wherein, 2 ..., t-1, g increase progressively by row successively since 2 and get (q-1) individual prime number, and correspondence obtains D _g, D _2g..., D _{(t-1) g}, place it in H successively ^dThe 2nd, 3 of matrix ..., q is capable or the 2nd, 3 ..., the t row; Obtain H ^dMatrix.

The concrete steps of step (4) can also for:

(4.1) utilize arithmetic progression to constitute the V vector, the general term formula of arithmetic progression is a _u=a ₁+ (u-1) b, wherein tolerance b is the integer greater than 2, u is the dimension of vector V, as first term a ₁Value be respectively 1,2 ..., during b, the general term formula of bringing arithmetic progression respectively into calculates, correspondence obtains b sequence, and this b sequence concatenation is constituted u n dimensional vector n V together ₀

(4.2) by v ₀Vector obtains D ₀' matrix is to D ₀' matrix carries out circulative shift operation, obtains one group of quadrature D ' matrix D ₀', D ₁', D ₂' ..., D _U-1';

(4.3) from quadrature D ' matrix D ₀', D ₁', D ₂' ..., D _U-1' in an optional matrix as piecemeal submatrix D ₀, it is carried out cyclic shift obtains u piecemeal submatrix D ₀, D ₁, D ₂..., D _U-1

The concrete steps of step (5) can also for:

H ^dFirst row, first row of matrix are placed D ₀The piecemeal submatrix, D can not appear in all the other each row of each row again ₀The piecemeal submatrix;

To D ₀Piecemeal submatrix ring shift left or move to right gs time, s=1 wherein, 2 ..., t-1, g increase progressively by row successively since 2 and get (q-1) individual prime number, and correspondence obtains D _g, D _2g..., D _{(t-1) g}, place it in H successively ^dThe 2nd, 3 of matrix ..., q is capable or the 2nd, 3 ..., the t row obtain H ^dMatrix.

The present invention proposes to construct with arithmetic progression the method for sparse parity check matrix H, if be the matrix H of check digit correspondence with the H matrix decomposition ^pMatrix H with the information bit correspondence ^d, i.e. H=[H ^p H ^d], H ^dMatrix can constitute with arithmetic progression.The present invention proposes to utilize arithmetic progression to produce D vector and D matrix, the D matrix is the cyclic shift orthogonal matrix, with one group of quadrature D matrix as the piecemeal submatrix, by certain regularly arranged formation H matrix, thereby produce the LDPC sign indicating number, low code check during this sign indicating number is suitable for, as 1/2 of CDMA2000,1/3,1/4 and 1/6 code check, be suitable for long, in, short block length, all code lengths of 192 to 20736 as CDMA2000, preferable performance is arranged, the complex structure degree of H matrix and the design complexities of encoder are all linear with block length N, the most outstanding advantages different with existing Algebraic Structure sign indicating number are that the value of code parameters is very flexible, can be according to given code check and code length design H matrix.Particularly, the present invention has following two characteristics:

(1) computation complexity is low: by following design procedure as can be seen, and design H ^p, H ^dNeed to do addition and multiplication hardly with the algorithm of H, only need do cyclic shift,, can be considered zero so computation complexity is quite low; In the algorithm for design of encoder, amount of calculation mainly is that the recursion of following (4) formula is calculated, and finds the solution a p _i, need be multiplication K time, (K+1) sub-addition if do not consider to do addition and multiplication with " 0 ", then needs to be multiplication t time, (t+1) sub-addition; Need ask M p altogether _iSo, need be multiplication Mt time, M (t+1) sub-addition.Total amount of calculation is that M (2t+1) is inferior, represents to be M (2t+1)=N (1-R) (2t+1) with N, because 0＜R＜1, so amount of calculation less than the 2t of code length N doubly, promptly the amount of calculation and code length N are linear.

(2) code parameters flexible design: (the LDPC sign indicating number of tolerance b:2≤b≤u/2) can calculate H according to known code check R and code length N based on arithmetic progression ^dWith the structural parameters of H matrix, thus structure H ^dWith the H matrix, to make this sign indicating number class can with the existing standard compatibility, have application potential widely, this existing Algebraic Structure LDPC sign indicating number class does not also reach.

Description of drawings

Fig. 1 is the flow chart of the inventive method.

Embodiment

The invention provides a kind of can with the quasi-regular LDPC code encoding method of existing standard compatibility.The LDPC sign indicating number is defined as the kernel of sparse parity check matrix H, and Hc is promptly arranged ^T=0, wherein c is a codeword sequence.By definition as can be known, design LDPC sign indicating number, key is the structure of design H matrix, the superiority and inferiority of H matrix structure can produce the influence of three aspects: the one, during iterative decoding, use the H matrix, and its structure can influence the performance of iterative decoding, for example " 1 " element is many more, and it is inhomogeneous more to distribute, and performance is good more; The 2nd, the complexity of iterative decoding algorithm is relevant with the structure of H matrix, and just the number of " 1 " element is few more, and decoding complex degree is low more; The 3rd, the structure of H matrix should be designed to help the realization of encoder, preferably separately, just the H matrix design is become system form with the matrix of information bit and check digit correspondence.

Basic principle of the present invention is as follows: in order to construct the H matrix, matrix H can be decomposed into the check digit matrix H ^pWith information bit matrix H ^d, H ^pConstitute H by biconjugate angle lower triangular matrix ^dMatrix is made of through suitably arranging one group of quadrature D matrix, the structure of D matrix is that every row, every row all have only one 1 square formation, the pairing V vector of D matrix is made of arithmetic progression, makes submatrix with the D matrix, to the various forms of sparse parity check matrix H of being arranged to form of D matrix.To appointing the information sequence c that gives ^d, according to ${\mathrm{Hc}}^T=\left[H^p{H}^d\right]\left[\begin{array}{c}{c}^p\\ c^d\end{array}\right]=H^p{c}^p+H^d{c}^d=0$ Formula is found the solution check digit sequence c ^p, find the solution codeword sequence c=[c thus ^pc ^d].

Flow process of the present invention is described in further detail it as shown in Figure 1 below.

(1) code parameters R and N's determines

The supervisory channel state information is according to adaptive option code parameters R of channel situation and N.According to the CDMA2000 standard, the span of code check R is 1/2,1/3,1/4 and 1/6, and the span of code length N is 192,288,3072,4608,6144,9216,12288,20736.The span that need to prove code check R and code length N is not limited to the CDMA2000 standard, in principle, as long as structural parameters N, M, column weight amount, row weight and the matrix in block form dimension u of structure H matrix keep positive integer, R can get any arithmetic number so, and N can get any positive integer.Specific practice is, according to input message sequence c ^dInformation extraction sequence length K adjusts code check R according to the channel condition information self adaptation, calculates code length N then, i.e. R=K/N, calculation check bit length M, M=N-K.

(2) structure H ^pMatrix

Known parameters M just can construct M * M's $H^p=[h_{\mathrm{ij}}^p:i=\mathrm{1,2},...,M,j=\mathrm{1,2},...,M]$ Matrix, it is made of biconjugate angle lower triangular matrix, and form is as follows:

Concrete construction algorithm is: first of first row is " 1 " element, and all the other positions are " 0 " elements; First and second position of second row is " 1 " element, and all the other positions are " 0 " elements; From the third line, next line is to be obtained by 1 of lastrow ring shift right.

(3) H ^dThe capable weight t of the structural parameters of matrix, column weight amount q and u determine

Known code check R can determine H ^dThe capable weight t of matrix and column weight amount q promptly have R=t/ (t+q), and the value of q can be any positive integer more than or equal to 3, and t can get any positive integer.Q=3 for example, t=1, then R=1/4; Q=3, t=3, then R=1/2.That is to say known R, given t can determine q; Perhaps given q can be in the hope of t.Should be noted that under the condition that satisfies R=t/ (t+q), guarantee that the q (or t) that tries to achieve is a positive integer.Given information bit length K, and determined after the capable weight t, can determine submatrix dimension u, i.e. K=ut.

(4) structure of D matrix

The present invention utilizes arithmetic progression to design sparse parity check matrix H, the H matrix is carried out the piecemeal design, the piecemeal submatrix adopts the D matrix, the D matrix is definition like this: to the u * u rank square formation (u is any positive integer) of matrix element value on GF (2) finite field, its every row, every row all have only " a 1 " element, all the other elements all are " 0 ", and then this matrix is called the D matrix.

The D matrix can be expressed as the form of vector, be called the V vector, every row, every row have only one 1 submatrix that application is all arranged in many documents, different is that the pairing V vector of D matrix is formed by arithmetic progression here, the corresponding relation of V vector and D matrix is: the sequence number of " 1 " element column in the sequence number representing matrix of each element position in the vector, the sequence number that " 1 " element is expert in the value representation matrix of element in the vector; To u n dimensional vector n V ₀Ring shift left (or moving to right) u-1 time obtains one group of (u altogether) V vector V ₀, V ₁, V ₂... V _U-1, corresponding one group of quadrature D matrix D ₀, D ₁, D ₂..., D _U-1Note D ₀(or V ₀) the 0th the D matrix (or the 0th V vector) that constitute by arithmetic progression of subscript 0 expression without displacement, to D0 matrix cyclic shift once D ₁Matrix is to D ₀After matrix cyclic shift u-1 time, obtain D successively ₁, D ₂, D ₃..., D _u

At first utilize arithmetic progression to constitute the V vector, the general term formula of arithmetic progression is a _u=a ₁+ (u-1) b, for example vector length is u=12, tolerance is b=2, when first term is a ₁=1 o'clock, obtain arithmetic progression 1,3,5,7,9,11, work as a ₁=2 o'clock, obtain another arithmetic progression 2,4,6,8,10,12, two ordered series of numbers are combined, and be expressed as vector form, be V ₀Vector (1,3,5,7,9,11,2,4,6,8,10,12), the merging mode of ordered series of numbers also can be before second number is listed in, first ordered series of numbers after, i.e. (2,4,6,8,10,12,1,3,5,7,9,11); And for example, get tolerance b=3, work as a ₁=1 o'clock, obtain arithmetic progression 1,4,7,10, work as a ₁=2 o'clock, obtain arithmetic progression 2,5,8,11, work as a ₁=3 o'clock, obtain arithmetic progression 3,6,9,12, three ordered series of numbers are combined, get another v ₀Vector (1,4,7,10,2,5,8,11,3,6,9,12), three ordered series of numbers can have six kinds of arrangement modes, therefore can obtain six different v ₀Vector.When b=1, v ₀Vector is (1,2,3,4,5,6,7,8,9,10,11,12), corresponding D ₀Matrix is a unit matrix, and the standard circulation QC-LDPC sign indicating number that the LDPC sign indicating number that is generated by this unit matrix and one group circular matrix has been studied by many people just is not so the situation of b=1 is in protection scope of the present invention.Above-mentioned 4 V ₀The pairing D of vector ₀Matrix is unfolded as follows:

$\left[\begin{array}{cccccccccccc}1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1\end{array}\right]$ $\left[\begin{array}{cccccccccccc}0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0\end{array}\right]$

$\left[\begin{array}{cccccccccccc}1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1\end{array}\right]$ $\left[\begin{array}{cccccccccccc}1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1\end{array}\right]$

By above-mentioned 4 V ₀Vector launches resulting 4 D ₀Matrix all is square formations that every row, every row have only " a 1 " element, to these 4 D ₀Square formation is carried out ring shift left 15 times, can obtain 4 groups of 16 orthogonal D square formations, carries out permutation and combination by any one group of D square formation by certain rule, all can constitute H matrix or H ^dMatrix, when this explanation constituted the LDPC sign indicating number by arithmetic progression, the number of codes in its yard set was quite abundant.It is emphasized that H matrix or H that the 4th unit matrix and one group cyclic shift orthogonal matrix are constituted ^dMatrix is not within protection scope of the present invention.

(5) H ^dThe formation of matrix

, one group of quadrature D square formation of tolerance b 〉=2 is carried out permutation and combination can construct various forms of sparse matrixes as the piecemeal submatrix with one group of quadrature D square formation $H^d=[h_{\mathrm{ij}}^d:i=\mathrm{1,2},...,M,j=\mathrm{1,2},...,K];$ If the 0th the D square formation without cyclic shift that is made of arithmetic progression is D ₀, one can effectively carry out utilize D ₀Piecemeal submatrix structure H ^dThe method of matrix is described as follows:

H ^dFirst row, first row of matrix are placed D ₀The piecemeal submatrix, D can not appear in all the other each row of each row again ₀The piecemeal submatrix;

To D ₀Piecemeal submatrix ring shift left (or moving to right) 2s (s=1,2 ..., t-1) inferior, correspondence obtains D ₂, D ₄, D ₆, D ₈, D ₁₀..., place it in H ^dSecond row (from secondary series) of matrix;

To D ₀Piecemeal submatrix ring shift left (or moving to right) 3s (s=1,2 ..., t-1) inferior, correspondence obtains D ₃, D ₆, D ₉, D ₁₂, D ₁₅..., place it in H ^dThe third line of matrix (from secondary series);

To D ₀Piecemeal submatrix ring shift left (or moving to right) 5s (s=1,2 ..., t-1) inferior, correspondence obtains D ₅, D ₁₀, D ₁₅, D ₂₀, D ₂₅..., place it in H ^dThe fourth line of matrix (from secondary series);

To D ₀Piecemeal submatrix ring shift left (or moving to right) 7s (s=1,2 ..., t-1) inferior, correspondence obtains D ₇, D ₁₄, D ₂₁, D ₂₈, D ₃₅..., place it in H ^dThe fifth line of matrix (from secondary series);

......

Continue operation and go down up to the capable piecemeal submatrix of q, needing the line number of placement piecemeal shift matrix is that q-1 is capable, and each row is to D ₀Piecemeal submatrix cyclic shift number of times be prime number g (g=2,3,5,7,11,13,17 ...) and the multiple gs of prime number g (s=1,2 ..., t-1), the value of prime number increases progressively by row.By above-mentioned algorithm construction $H^d=[h_{\mathrm{ij}}^d:i=\mathrm{1,2},...,M,j=\mathrm{1,2},...,K]$ Matrix is as follows:

H by (2) formula formation ^dMatrix is the matrix array of a q * t, H ^dMatrix is capable by q, t row D square formation constitutes H ^dThe dimension of matrix is qu * tu=M * K.

(6) find the solution codeword sequence C

The method of design structure encoder is found the solution codeword sequence c.To appointing the information sequence c that gives ^d={ d _j, j=1,2 ... K}, surface construction in the utilization $H^p=[h_{\mathrm{ij}}^p:i=\mathrm{1,2},...,M,j=\mathrm{1,2},...,M]$ With $H^d=[h_{\mathrm{ij}}^d:i=\mathrm{1,2},...,M,j=\mathrm{1,2},...,K]$ Matrix, according to following (3) formula:

${\mathrm{Hc}}^T=\left[H^p{H}^d\right]\left[\begin{array}{c}{c}^p\\ c^d\end{array}\right]=H^p{c}^p+H^d{c}^d=0---\left(3\right)$

Find the solution check digit sequence c ^p, because H ^pStructure be biconjugate angle lower triangular matrix, so utilize (3) formula to find the solution check digit sequence c ^pThe time, do not need H ^pMatrix inversion, but the method by back substitution and recursion is found the solution c as following (4) formula ^p={ p _i, i=1,2 ... M}:

$p_1=\underset{j}{\mathrm{\Σ}}{h_{1j}^{d}d}_j$ Recursion can get $p_i=p_{i-1}+\underset{j}{\mathrm{\Σ}}{h}_{\mathrm{ij}}^d{d}_j---\left(4\right)$ Find the solution codeword sequence c=[c thus ^p c ^d]={ c _l, l=1,2 ... N}.Need to prove that two summation expression formulas of (4) formula have the addition of K item outwardly, in fact because H ^dEvery row of matrix has only t " 1 ", so each summation, two expression formulas of (4) formula have only the addition of t item.

(7) formation of H matrix

From above-mentioned step (1) as can be seen, from input message sequence c to step (6) ^dIn the whole encoder design process of output code word c, do not use the H matrix, but in the coding/decoding system of a terminal, need use the H matrix and decode, thus still need here to construct the H matrix, so that finish whole process.H with (1) formula ^pThe H of matrix and (2) formula ^dMatrix is also put together, gets following H matrix:

Be based on the quasi-regular LDPC sign indicating number of arithmetic progression by the defined LDPC sign indicating number of the kernel of (5) formula H matrix, its code check is R=t/ (t+q), and code length is N=u (t+q).

Example:

This example is with the code parameters R=1/2 of mobile communication standard CDMA2000, and N=192 is an example, provides the LDPC code coder specific implementation method based on arithmetic progression, and for 1/2 code check, the check bit sum information bit equates, i.e. M=K=192/2=96, H ^dThe value of matrix column weight and row weight also equates, can get 3,4,5 and 6, gets q=t=4 here, so try to achieve the dimension u=96/4=24 of D matrix, the input of encoder is information sequence c ^d={ d _j, j=1,2 ... 96}, the output of encoder is a yard sequence c={c _l, l=1,2 ... 192}.

Code parameters R and N can carry out self adaptation according to channel state feedback information and input message sequence and choose, and according to the code parameters R and N value computation structure parameter q, t and the u that determine, the implementation algorithm of each matrix square frame is as follows in the encoder:

1.D the design of matrix:

According to arithmetic progression formula a _u=a ₁+ (u-1) b, according to top calculating ordered series of numbers length u=24 here, tolerance b (2≤b≤u/2) can get any positive integer, for example, b=4, first term a so ₁Therefore can get 1,2,3 and 4,4 hop counts row are arranged, have 1 * 2 * 3 * 4=4! First term a is adopted in=24 kinds of arrangements here ₁The sequence arrangement of value is worked as a ₁=1 o'clock, get ordered series of numbers (1,5,9,13,17,21), work as a ₁=2 o'clock, get ordered series of numbers (2,6,10,14,18,22), work as a ₁=3 o'clock, get ordered series of numbers (3,7,11,15,19,23), work as a ₁=4 o'clock, get ordered series of numbers (4,8,12,16,20,24), above-mentioned 4 hop count row are merged in proper order, obtain the V vector V of 24 bit elements ₀=(1,5,9,13,17,21,2,6,10,14,18,22,3,7,11,15,19,23,4,8,12,16,20,24) are with V ₀Vector ring shift left (or moving to right) 23 times obtains one group of (u=24) V vector, and corresponding one group (u=24) orthogonal D matrix if the value of u is enough big, so just has abundant quadrature D matrix as submatrix, is used for constructing the H matrix.

2.H ^dThe design of matrix:

According to (2) formula H ^dThe algorithm for design of matrix for the example of u=24, can design a q=t=4, the H of K=96 ^dMatrix is as follows:

$H^d=\left[\begin{array}{cccc}{D}_0& D_0& D_0& D_0\\ D_0& D_2& D_4& D_6\\ D_0& D_3& D_6& D_9\\ D_0& D_5& D_{10}& D_{15}\end{array}\right]---\left(6\right)$

As can be seen from the above equation, though 24 quadrature D matrixes are arranged, (6) formula has only been used 10, wherein D ₀The largest loop carry digit of matrix is 15, so can not occur the circulation of 4 lines in (6) formula.In fact, u can get any positive integer, and q can get 2,3,4,5,6,7,8 ... any positive integer, the t of corresponding u=24 can get 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, any positive integer of 16....

3, H ^pThe design of matrix:

H ^pMatrix is a biconjugate angle lower triangular matrix, to u=24, M=96 is arranged, the biconjugate angle lower triangular matrix that the usefulness computer construction is 96 * 96, and specific practice is: first of first row is " 1 " element, all the other positions are " 0 " elements; First and second position of second row is " 1 " element, and all the other positions are " 0 " elements; From the third line, next line is to be obtained by 1 of lastrow ring shift right.H ^pMatrix rewrites as follows as (1) formula:

4.H the design of matrix:

With top (7) formula H ^pMatrix and (6) formula H ^dMatrix cascade obtains following H matrix together:

(8) kernel of the H matrix of formula has provided the quasi-regular LDPC sign indicating number based on arithmetic progression, and design parameter is: code check R=t/ (q+t)=4/ (4+4)=1/2, code length N=u (q+t)=24 * (4+4)=192.To this as can be seen, can follow such design rule, at first provide the value R and the N of code check and code length, calculate structural parameters t, q and the u of H matrix then, construct the H matrix at last, so this design can with the CDMA2000 operating such.

5.LDPC Exploit of Designing Encoder:

Owing to the H matrix construction is become the H=[H of system form ^p H ^d], correspondingly the sign indicating number sequence also is decomposed into check bit sum information bit c=[c ^pc ^d], appoint to information sequence c ^d={ d _j, j=1,2 ... 96}, by (3) formula ${\mathrm{Hc}}^T=\left[H^p{H}^d\right]\left[\begin{array}{c}{c}^p\\ c^d\end{array}\right]=H^p{c}^p+H^d{c}^d=0,$ Can find the solution verification sequence c ^pBecause H ^pBe designed to biconjugate angle lower triangular matrix, therefore when finding the solution (3) formula, do not needed H ^pMatrix inversion, but ask first row earlier, obtain p ₁, adopt the mode of back substitution and recursion to find the solution following each row then, obtain p ₂, p ₃... delegation to the last, finally try to achieve c ^p={ p _i, i=1,2 ... 96}, according to (4) formula, calculation expression is as follows: $p_1=\underset{j=1}{\overset{96}{\mathrm{\Σ}}}{h_{1j}^{d}d}_j$ Recursion can get $p_i=p_{i-1}+\underset{j=1}{\overset{96}{\mathrm{\Σ}}}{h}_{\mathrm{ij}}^d{d}_j---\left(9\right)$ Obtain c ^pAfter, can try to achieve codeword sequence c=[c ^pc ^d]={ c _l, l=1,2 ... 192}.Need to prove that two of (9) formula summation expression formulas have 96 additions on the surface, in fact owing to t=4, H ^dEach row of matrix has only 4 " 1 ", so two summation expression formulas of (9) formula have only 4 additions (mould 2 adds), just whenever asks a p _i, 4 that participate in summation (mould 2 with) is different, and their value is the same, all is 1.

Claims (3)

1. the coding method of a low density parity check code the steps include:

(1) determine code check R and code length N, and calculation check bit length M;

(2) H of structure M * M ^pMatrix

First of first row is " 1 " element, and all the other positions are " 0 " elements; First and second position of second row is " 1 " element, and all the other positions are " 0 " elements; From the third line, next line is to be obtained by 1 of lastrow ring shift right;

(3) according to code check R, determine H ^dThe capable weight t of matrix and column weight amount q, calculated sub-matrix dimension u again, t/ (q+t)=R wherein, ut=K, K are information bit length;

(4) utilize arithmetic progression structure D matrix, the D defined matrix is: to the u * u rank square formation of matrix element value on GF (2) finite field, its every row, every row all have only " a 1 " element, and all the other elements all are " 0 ";

(5) utilize D matrix construction H ^dMatrix;

(6) ask codeword sequence c, and structure H matrix, H=[H ^p H ^d];

Ask the process of codeword sequence c to be:

1. to appointing the information sequence c that gives ^d={ d _j, j=1,2 ... K} utilizes $H^p=[h_{\mathrm{ij}}^p:i=\mathrm{1,2},...,M,j=\mathrm{1,2},...,M]$ With $H^d=[h_{\mathrm{ij}}^p:i=\mathrm{1,2},...,M,j=\mathrm{1,2},...,K]$ Matrix, according to following formula:

${H_c}^T=\left[H^p{H}^d\right]\left[\begin{array}{c}{c}^p\\ c^d\end{array}\right]=H^p{c}^p+H^d{c}^d=0$

2. make c ^p={ p _i, i=1,2 ... M}, $p_1=\underset{j}{\mathrm{\Σ}}{h}_{1j}^d{d}_j$ Recursion can get $p_i=p_{i-1}+\underset{j}{\mathrm{\Σ}}{h}_{\mathrm{ij}}^d{d}_j$

3. ask codeword sequence c=[c ^p c ^d]={ c _l, l=1,2 ... N}.

$c=\left[\begin{array}{ccc}& \·& \\ c^p& \·& c^p\\ & \·& \end{array}\right]=\{c_l,l=\mathrm{1,2},...N\}.$

2, method according to claim 1 is characterized in that:

The concrete steps of step (4) are:

(4.1) utilize arithmetic progression to constitute the v vector, the general term formula of arithmetic progression is a _u=a ₁+ (u-1) b, wherein tolerance b is the integer greater than 2, u is the dimension of vector v, as first term a ₁Value be respectively 1,2 ..., during b, the general term formula of bringing arithmetic progression respectively into calculates, and correspondence obtains b sequence, and this b sequence concatenation is constituted the 0th u n dimensional vector n v without cyclic shift together ₀, to u n dimensional vector n v ₀Ring shift left or move to right u-1 time, obtaining number is one group of v vector v of u ₀, v ₁, v ₂... v _U-1

(4.2) utilize v vectorial structure D ' matrix, the corresponding relation of the two is: the sequence number of " 1 " element column in the sequence number representing matrix of each element position in the vector, the sequence number that " 1 " element is expert in the value representation matrix of element in the vector, method is by one group of v vector v in view of the above ₀, v ₁, v ₂... v _U-1Correspondence obtains one group of quadrature D ' matrix D ₀', D ₁', D ₂' ..., D _U-1';

(4.3) from quadrature D ' matrix D ₀', D ₁', D ₂' ..., D _U-1' in an optional matrix as piecemeal submatrix D ₀, it is carried out cyclic shift obtains u piecemeal submatrix D ₀, D ₁, D ₂..., D _U-1

The concrete steps of step (5) are:

H ^dFirst row, first row of matrix are placed D ₀The piecemeal submatrix, D can not appear in all the other each row of each row again ₀The piecemeal submatrix;

To D ₀Piecemeal submatrix ring shift left or move to right gs time, s=1 wherein, 2 ..., t-1, g gets (q-1) individual prime number by going to increase progressively successively since 2, and correspondence obtains D _g, D _2g..., D _{(t-1) g}, place it in H successively ^dThe 2nd, 3 of matrix ..., q is capable or the 2nd, 3 ..., the t row; Obtain H ^dMatrix.

3, method according to claim 1 is characterized in that:

The concrete steps of step (4) are:

(4.1) utilize arithmetic progression to constitute the v vector, the general term formula of arithmetic progression is a _u=a ₁+ (u-1) b, wherein tolerance b is the integer greater than 2, u is the dimension of vector v, as first term a ₁Value be respectively 1,2 ..., during b, the general term formula of bringing arithmetic progression respectively into calculates, and correspondence obtains b sequence, and this b sequence concatenation is constituted u n dimensional vector n v together ₀

(4.2) by v ₀Vector obtains D ₀' matrix is to D ₀' matrix carries out circulative shift operation, obtains one group of quadrature D ' matrix D ₀', D ₁', D ₂' ..., D _U-1';

(4.3) from quadrature D ' matrix D ₀', D ₁', D ₂', D _U-1' in an optional matrix as piecemeal submatrix D ₀, it is carried out cyclic shift obtains u piecemeal submatrix D ₀, D ₁, D ₂..., D _U-1

The concrete steps of step (5) are:

H ^dFirst row, first row of matrix are placed D ₀The piecemeal submatrix, D can not appear in all the other each row of each row again ₀The piecemeal submatrix;

To D ₀Piecemeal submatrix ring shift left or move to right gs time, s=1 wherein, 2 ... t-1, g gets (q-1) individual prime number by going to increase progressively successively since 2, and correspondence obtains D _g, D _2g..., D _{(t-2) g}, place it in H successively ^dThe 2nd, 3 of matrix ..., q is capable or the 2nd, 3 ..., the t row obtain H ^dMatrix.