CN102882532B - LDPC (low density parity check) encoder in CMMB (China mobile multimedia broadcasting) based on rotate right accumulation and encoding method - Google Patents

Abstract

The invention relates to a scheme for encoding two different code rate QC (quasi-cyclic)-LDPC (low density parity check) codes in a CMMB (China mobile multimedia broadcasting) system. The scheme is characterized in that an encoder of QC-LDPC codes of the system is based on the rotate right accumulation mechanism and mainly comprises a controller, a vector storage, a rotate right meter, a rotate right accumulator and a parallel rotate left accumulator. The encoding method is simple in process, highly uniform in step, easy to implement, simplified in backward recursion operation and free of complex operations such as reading out-operating-writing back. The QC-LDPC encoder is compatible with multiple-code-rate and capable of obviously increasing encoding speed and effectively reducing logic resource demand, and has the advantages of easiness to implementation, high encoding speed, low resource consumption, low power consumption, low cost and the like.

Description

Ring shift right add up base CMMB in LDPC encoder and coding method

Technical field

The present invention relates to filed of mobile multimedia broadcasting, particularly the efficient implementation method of QC-LDPC code coder in a kind of CMMB system.

Background technology

Because the various distortion that exists in transmission channel and noise can produce interference to transmission signal, receiving terminal inevitably data signal produces the situation of error code.In order to reduce the bit error rate, need to adopt channel coding technology.

Low-density checksum (Low-Density Parity-Check, LDPC) code becomes the study hotspot of field of channel coding with the excellent properties that it approaches Shannon limit.Quasi-cyclic LDPC code (Quasic-LDPC, QC-LDPC) code is a kind of special LDPC code, and its coding can adopt shift register to add accumulator (Shift-Register-Adder-Accumulator, SRAA) and be realized.

SRAA method utilizes generator matrix G_qCencode.The generator matrix G of QC-LDPC code_qCby a × t b × b rank circular matrix G_{i, j}the array that (1≤i≤a, 1≤j≤t) is formed, t=a+c.The a part of generator matrix corresponding with information vector is unit matrix, and the remainder generator matrix corresponding with verification vector is high-density matrix.Serial SRAA method completes first encoding needs ab+t clock cycle, needs (t+c) b register, cb two inputs to input XOR gate with door and cb individual two.In addition, acb bit ROM is also needed to store the first trip of circular matrix.

CMMB standard have employed the LDPC code of 1/2 code check η different from 3/4 two kind, and exchanged by ranks, check matrix H can be transformed the circulation form H that is as the criterion_qC, H_qCcorresponding accurate circulation generator matrix G_qC.For these two kinds of QC-LDPC codes, all there is t=36 and b=256.Fig. 1 gives parameter a under different code check η and c.

In CMMB standard, the existing solution of QC-LDPC coding adopts serial SRAA method, and the scramble time needed for 2 kinds of code checks is 4644 and 6948 clock cycle respectively.Logical resource needs 13824 registers, 4608 two inputs input XOR gate with door and 4608 two, and this is determined by the parameter of code check η=1/2 correspondence.In addition, two kinds of code checks need 145 altogether, and 152 bit ROM store the first trip of circular matrix.When adopting hardware implementing, so large storage demand can increase equipment cost, and the scramble time is longer.

Summary of the invention

Mass storage and the slow shortcoming of coding rate is needed for what exist in the existing implementation that CMMB system multi code Rate of Chinese character QC-LDPC encodes, the invention provides a kind of high efficiency encoding method cumulative based on ring shift right, while significantly improving coding rate, effectively reduce the demand of memory and logical resource.

As shown in Figure 5, in the CMMB standard added up based on ring shift right, the encoder of multi code Rate of Chinese character QC-LDPC code forms primarily of 5 parts: controller, vector memory, ring shift right table, ring shift right accumulator and cardiopulmonary bypass in beating heart move to left accumulator (parallel C LSA).Whole cataloged procedure divides 5 steps to complete: the 1st step, clearing part verifies vectorial p_x, input information vector s; 2nd step, ring shift right accumulator uses whole ring shift right table calculating section to verify vectorial p line by line_ywith vectorial q; 3rd step, uses parallel C LSA calculating section to verify vectorial p_x; 4th step, ring shift right accumulator uses the capable calculating section of front c-u of ring shift right table to verify vectorial p line by line_y; 5th step, output codons v.Above-mentioned cataloged procedure is simple, and step uniformity is strong, is easy to realize, simplifies backward recursion computing, without the need to reading-computing-write back this complex operations.

The compatible multi code Rate of Chinese character of QC-LDPC encoder provided by the invention, can effectively reduce memory and logical resource demand, thus reach the object reducing hardware cost and power consumption while significantly improving coding rate.

Be further understood by ensuing detailed description and accompanying drawings about the advantages and spirit of the present invention.

Accompanying drawing explanation

Fig. 1 is the parameter a given under different code check η, c, u and ρ;

Fig. 2 is near lower triangular check matrix H after ranks exchange_qCstructural representation;

QC-LDPC code H when Fig. 3 is code check η=1/2_qCin each piece of row permutation matrix place block row number and ring shift right figure place;

QC-LDPC code H when Fig. 4 is code check η=3/4_qCin each piece of row permutation matrix place block row number and ring shift right figure place;

Fig. 5 is the QC-LDPC code coder overall structure of compatible 2 kinds of code checks in CMMB standard;

H when Fig. 6 gives code check η=1/2_zerothe block row number at the quantity of permutation matrix, place and ring shift right figure place in each piece of row;

H when Fig. 7 gives code check η=3/4_zerothe block row number at the quantity of permutation matrix, place and ring shift right figure place in each piece of row;

Fig. 8 gives H under different code check_zeroin all pieces of row the total α of permutation matrix and front c-u block capable in the total β of permutation matrix;

Fig. 9 is the structural representation of ring shift right accumulator;

Figure 10 is the structural representation of parallel C LSA;

Figure 11 is the hardware resource consumption of each part of encoder and whole circuit;

Figure 12 is each coding step and the processing time needed for whole cataloged procedure;

Figure 13 compares traditional serial SRAA method and coding rate of the present invention and resource consumption.

Detailed description of the invention

Below in conjunction with the drawings and specific embodiments, the invention will be further described, but not as a limitation of the invention.

QC-LDPC code is the special LDPC code of a class, its generator matrix G_qCand check matrix H_qCbe all the array be made up of circular matrix, there is stages cycle feature, therefore be called as quasi-cyclic LDPC code.From the angle of row, each provisional capital of circular matrix is the result of lastrow (first trip is footline) ring shift right one; From the angle of row, each row of circular matrix are all the results that previous column (first is terminal column) circulation moves down.The set that the row vector of circular matrix is formed is identical with the set that column vector is formed, and therefore, circular matrix can be characterized by its first trip or first completely.The row of circular matrix is heavy identical with column weight, is denoted as w.If w=0, so this circular matrix is full null matrix.If w=1, so this circular matrix is replaceable, is called permutation matrix, and it is by obtaining the some positions of unit matrix I ring shift right.The check matrix H of QC-LDPC code_qCby c × t b × b rank circular matrix H_{i, j}the following array that (1≤i≤c, 1≤j≤t) is formed:

Check matrix H_qCcontinuous b capable and b row be called as the capable and block row of block respectively.

CMMB standard have employed the LDPC code of 1/2 code check η different from 3/4 two kind, is exchanged by ranks, and check matrix H can be transformed to the accurate circulation form H of near lower triangular_qC.Check matrix H_qCcorresponding code word v=(s, p), H_qCfront a block row corresponding be information vector s, that rear c block row are corresponding is the vectorial p of verification.Be one section with b bit, information vector s is divided into a section, i.e. s=(s₁, s₂..., s_a); Verify vectorial p and be divided into c section, be i.e. p=(p₁, p₂..., p_c).CMMB standard have employed the QC-LDPC code of 2 kinds of different code checks, and Fig. 1 gives parameter a under different code check η and c.For these 2 kinds of QC-LDPC codes, check matrix H_qCin all circular matrixes are full null matrix (w=0) or are permutation matrix (w=1), and t=36 and b=256.

For CMMB standard, check matrix H_qCthere is near lower triangular shape, as shown in Figure 2.In fig. 2, the unit of all submatrixs is all b bit instead of 1 bit.T is lower triangular matrix, and u reflects H_qCwith the degree of closeness of lower triangular matrix, H_qCevery block capable in have ρ permutation matrix, Fig. 1 gives parameter u under 2 kinds of code checks and ρ.H when Fig. 3 and 4 sets forth η=1/2 and 3/4_qCin each piece of row permutation matrix place block row number and ring shift right figure place.

Check matrix H shown in Fig. 2_qCcorresponding code word v=(s, p)=(s, p_x, p_y) in, matrix A and C corresponding informance vector s, matrix B and the vectorial p of the corresponding part verification of D_x=(p₁, p₂..., p_u), matrix T and E be corresponding remaining verification vector p then_y=(p_u+1, p_u+2..., p_c).Above-mentioned matrix and vector meet following relation:

p_x^T=Φ(ET^-1As^T+Cs^T)(2)

p_y^T=T^-1(As^T+Bp_x^T)(3)

Wherein, Φ=(ET^-1b+D)^-1, subscript^twith^-1represent transposition and inverse respectively.As everyone knows, circular matrix inverse, product and remain circular matrix.Therefore, Φ is also the array be made up of circular matrix.But although matrix E, T, B and D are sparse matrixes, Φ is no longer sparse but highdensity.

According to formula (2) and (3), the general coding flow process of QC-LDPC code can be obtained, comprise the following steps:

(1) input information vector s, clearing part verifies vectorial p_x.

(2) calculating section verifies vectorial p_y^t=T^-1(As^t+ Bp_x^t) and vectorial q^t=CS^t+ Ep_y^t.

(3) calculating section verifies vectorial p_x^t=Φ q^t.

(4) calculating section verifies vectorial p_y^t=T^-1(As^t+ Bp_x^t).

(5) parallel output code word v=(s, p_x, p_y).

According to above-mentioned coding flow process, Fig. 5 gives the encoder being applicable to 2 kinds of code check QC-LDPC codes in CMMB standard, it is based on the cumulative mechanism of ring shift right, to move to left accumulator (parallel C LSA) five functional modules compositions primarily of controller, vector memory, ring shift right table, ring shift right accumulator and cardiopulmonary bypass in beating heart.Vector memory stores vectorial q and code word v=(v₁, v₂..., v_t), its bit wide is b bit, and the code section v of v can be used in the space of vector memory₁, v₂..., v_tidentify.Ring shift right table stores the ring shift right figure place of circular matrix and the block row number at place.Ring shift right accumulator utilizes ring shift right table compute vector q and part to verify vectorial p_y.Parallel C LSA is used for calculating section and verifies vectorial p_x.

When making ring shift right table, need check matrix H_qCfurther process obtains H_zero.Specific as follows: the unit matrix on lower triangular matrix T diagonal to be reset, matrix D is reset.On this basis, H is added up_zerothe quantity Number [i] (Number [i]≤11) of i-th (1≤i≤c) permutation matrix during block is capable, and ring shift right figure place Offset [i] [j] (1≤j≤Number [i] of each permutation matrix, 0≤Offset [i] [j] <b) and block row Column [i] [j] (1≤j≤Number [i], 1≤Column [i] [the j]≤t) at place.H when Fig. 6 and 7 sets forth η=1/2 and 3/4_zerothe block row number at the quantity of permutation matrix, place and ring shift right figure place in each piece of row, Fig. 8 gives H under different code check_zeroin all pieces of row the total α of permutation matrix and front c-u block capable in the total β of permutation matrix.Each unit of ring shift right table stores ring shift right figure place Offset [i] [j] of permutation matrix and block row Column [i] [j] at place, they represent with 8 bits and 6 bits respectively, and therefore the bit wide of each unit of ring shift right table is 14 bits.

Fig. 9 is the structural representation of ring shift right accumulator, and it uses ring shift right table compute vector q and part to verify vectorial p primarily of ring shift right device and accumulator composition_y.When calculating by the capable data of ring shift right table the i-th (1≤i≤c) block, accumulator initialization is 0.When jth (1≤j≤Number [i]) the individual clock cycle arrives, ring shift right device is to the code section v of input_{column [i] [j]}ring shift right Offset [i] [j] position, acquired results and accumulator add up.It is secondary that aforesaid operations repeats Number [i], and the content of accumulator is stored into v_iin corresponding vector memory space.Vector memory space v_a+u+1~ v_tthe data of middle storage constitute part and verify vectorial p_y, and v_a+1~ v_a+uthe data of middle storage constitute vectorial q.

Figure 10 is the structural representation of parallel C LSA, and it is primarily of register R₁~ R₁₀, b position two input with door M_{i, j}(1≤i, j≤5) and b position two input XOR gate A_{i, j}(1≤i, j≤5) form, and verify vectorial p for calculating section_x.Time initial, register R₁~ R_uthat store is vectorial q.When each clock arrives, register R₁~ R₅respective serial moves to left 1 time, and b position two inputs and door M_{i, j}carry out scalar and vectorial multiplying, M_{i, 1}~ M_{i, 5}product and register R_i+5serial loop moves to left the results added of 1 time, and deposits back register R_i+5.Repeat said process, complete computing through b clock cycle.Now, register R₆~ R₁₀what store is that part verifies vectorial p_x.Next, p_xtransfer to vector memory space v_a+1~ v_a+u.

The invention provides a kind of high efficiency encoding method of variable bit rate QC-LDPC code, in conjunction with the encoder (as shown in Figure 5) of multi code Rate of Chinese character QC-LDPC code in CMMB standard, its coding step is described below:

1st step, clearing part verifies vectorial p_xcorresponding vector memory space v_a+1~ v_a+u, input information vector s, by message segment s₁~ s_abe stored in vector memory space v respectively₁~ v_a;

2nd step, ring shift right accumulator uses whole ring shift right table calculating section to verify vectorial p line by line_ywith vectorial q, and they are stored in respectively vector memory space v_a+u+1~ v_tand v_a+1~ v_a+u;

3rd step, uses parallel C LSA calculating section to verify vectorial p_x, and result is stored in vector memory space v_a+1~ v_a+u;

4th step, ring shift right accumulator uses the capable calculating section of front c-u of ring shift right table to verify vectorial p line by line_y, and result is stored in vector memory space v_a+u+1~ v_t, note, the p that the 2nd step obtains_yresults of intermediate calculations, and the p that this step obtains_yit is final calculation result;

5th step, output codons v=(s, p_x, p_y).

Above-mentioned cataloged procedure is simple, is easy to realize.2nd step and the 4th step uniformity by force, significantly reduce programing work amount.Backward recursion computing is simplified, and without the need to reading-computing-write back this complex operations, shortens the scramble time.

Figure 11 summarizes the hardware resource consumption of each part of encoder and whole circuit.Wherein, ring shift right device adopts 7 stage pipeline structure.

Figure 12 summarizes each coding step and the processing time needed for whole cataloged procedure.

Figure 13 compares traditional serial SRAA method and coding rate of the present invention and resource consumption.No matter can know from figure and see, be coding rate, or logical resource, especially memory, and performance of the present invention is all better than serial SRAA method.Memory required for the present invention is only 8% of serial SRAA method, employs less register, and consumption is 33% of serial SRAA method.For η=1/2 and 3/4, coding rate of the present invention is 9.9 and 14.3 times of serial SRAA method respectively.

As fully visible, compared with traditional serial SRAA method, the present invention have be easy to realize, coding rate is fast, resource consumption is few, power consumption is little, low cost and other advantages.

Above-described embodiment, just the present invention's more preferably detailed description of the invention, the usual change that those skilled in the art carries out within the scope of technical solution of the present invention and replacement all should be included in protection scope of the present invention.

Claims (4)

1. one kind is suitable for the encoder of 2 kinds of different code check QC-LDPC codes in CMMB standard, CMMB is the English abbreviation of China Mobile multimedia broadcasting professional standard, English full name is China Mobile Multimedia Broadcasting, the near lower triangular check matrix H of QC-LDPC code_qCbe the array be made up of c × t b × b rank circular matrix, u reflects H_qCwith the degree of closeness of lower triangular matrix, wherein, c, t, b and u are all positive integer, t=a+c, and 2 kinds of different code check η are 1/2,3/4 respectively, for these 2 kinds different code check QC-LDPC codes, all have t=36 and b=256, the parameter a that 2 kinds of different code checks are corresponding is 18,27 respectively, and the parameter c that 2 kinds of different code checks are corresponding is 18,9 respectively, the parameter u that 2 kinds of different code checks are corresponding is 5,3 respectively, check matrix H_qCcorresponding code word v=(s, p)=(s, p_x, p_y), H_qCfront a block row corresponding be information vector s, that rear c block row are corresponding is the vectorial p of verification, and be one section with b bit, information vector s is divided into a section, i.e. s=(s₁, s₂..., s_a), verify vectorial p and be divided into c section, be i.e. p=(p₁, p₂..., p_c), v is divided into t section, i.e. v=(v₁, v₂..., v_t), p_x=(p₁, p₂..., p_u), p_y=(p_u+1, p_u+2..., p_c), it is characterized in that, described encoder comprises following parts:

Controller, the operation of the input of control information vector, the output of code word and other parts;

Vector memory, for storing vectorial q and code word v, the code section v of its space v₁, v₂..., v_tidentify;

Ring shift right table, for storage matrix H_zeroin the block row number at the ring shift right figure place of all circular matrixes and place, wherein, H_zeroby H_qCthe diagonal of middle lower triangular matrix T and the clearing of whole matrix D obtain;

Ring shift right accumulator, verifies vectorial p for compute vector q and part_y;

Cardiopulmonary bypass in beating heart moves to left accumulator, verifies vectorial p for calculating section_x.

2. encoder as claimed in claim 1, it is characterized in that, described ring shift right accumulator is made up of ring shift right device and accumulator, when calculating by ring shift right table the i-th piece row data, accumulator initialization is 0, and when a jth clock cycle arrives, ring shift right device is to the code section v of input_{column [i] [j]}ring shift right Offset [i] [j] position, acquired results and accumulator add up, and it is secondary that aforesaid operations repeats Number [i], and after computing, the content of accumulator is stored in vector memory space, vector memory space v_a+u+1~ v_tthe data of middle storage constitute part and verify vectorial p_y, v_a+1~ v_a+uthe data of middle storage constitute vectorial q, and wherein, 1≤i≤c, 1≤j≤Number [i], Number [i] are H_zerothe quantity of permutation matrix in i-th piece of row, Offset [i] [j] and Column [i] [j] is the ring shift right figure place of permutation matrix and the block row number at place respectively, Number [i]≤11,0≤Offset [i] [j] <b, 1≤Column [i] [j]≤t.

3. encoder as claimed in claim 1, it is characterized in that, described cardiopulmonary bypass in beating heart moves to left accumulator by register R₁~ R₁₀, b position two input with door M_i,jxOR gate A is inputted with b position two_i,jcomposition, wherein, 1≤i, j≤5, verify vectorial p for calculating section_x:

Time initial, register R₁~ R_uthat store is vectorial q;

When each clock arrives, register R₁~ R₅respective serial moves to left 1 time, and b position two inputs and door M_i,jcarry out scalar and vectorial multiplying, M_{i, 1}~ M_{i, 5}product and register R_i+5serial loop moves to left the results added of 1 time, and deposits back register R_i+5;

Repeat the operation in the preceding paragraph, complete computing through b clock cycle, register R₆~ R₁₀what store is that part verifies vectorial p_x, it is transferred to vector memory space v_a+1~ v_a+u.

4. one kind is suitable for the coding method of 2 kinds of different code check QC-LDPC codes in CMMB standard, CMMB is the English abbreviation of China Mobile multimedia broadcasting professional standard, English full name is China Mobile Multimedia Broadcasting, the near lower triangular check matrix H of QC-LDPC code_qCbe the array be made up of c × t b × b rank circular matrix, u reflects H_qCwith the degree of closeness of lower triangular matrix, wherein, c, t, b and u are all positive integer, t=a+c, and 2 kinds of different code check η are 1/2,3/4 respectively, for these 2 kinds different code check QC-LDPC codes, all have t=36 and b=256, the parameter a that 2 kinds of different code checks are corresponding is 18,27 respectively, and the parameter c that 2 kinds of different code checks are corresponding is 18,9 respectively, the parameter u that 2 kinds of different code checks are corresponding is 5,3 respectively, check matrix H_qCcorresponding code word v=(s, p)=(s, p_x, p_y), H_qCfront a block row corresponding be information vector s, that rear c block row are corresponding is the vectorial p of verification, and be one section with b bit, information vector s is divided into a section, i.e. s=(s₁, s₂..., s_a), verify vectorial p and be divided into c section, be i.e. p=(p₁, p₂..., p_c), v is divided into t section, i.e. v=(v₁, v₂..., v_t), p_x=(p₁, p₂..., p_u), p_y=(p_u+1, p_u+2..., p_c), it is characterized in that, described coding method comprises the following steps:

1st step, clearing part verifies vectorial p_xcorresponding vector memory space v_a+1~ v_a+u, input information vector s, by message segment s₁~ s_abe stored in vector memory space v respectively₁~ v_a;

2nd step, ring shift right accumulator uses whole ring shift right table calculating section to verify vectorial p line by line_ywith vectorial q, and they are stored in respectively vector memory space v_a+u+1~ v_tand v_a+1~ v_a+u;

3rd step, uses the cardiopulmonary bypass in beating heart accumulator computes part that moves to left to verify vectorial p_x, and result is stored in vector memory space v_a+1~ v_a+u;

4th step, ring shift right accumulator uses the capable calculating section of front c-u of ring shift right table to verify vectorial p line by line_y, and result is stored in vector memory space v_a+u+1~ v_t, note, the p that the 2nd step obtains_yresults of intermediate calculations, and the p that this step obtains_yit is final calculation result;

5th step, output codons v=(s, p_x, p_y).