CN108880563A - A kind of the improvement coding method and system of LDPC code - Google Patents

Abstract

The invention discloses an improved encoding method and system of LDPC codes. The invention proposes an improved two-way recursive encoding method through the research of serial and parallel encoding methods of LDPC codes used in the IEEE802.16e standard , the analysis shows that the new method has low computational complexity, can improve the parallelism of encoding, and the calculation is simpler in hardware implementation.

Description

An improved encoding method and system for LDPC codes

technical field

The invention relates to encoding technology, in particular to an improved encoding method and system for LDPC codes in the 802.16e standard.

Background technique

Low-density parity-check codes were first proposed by Gallager in 1963. In the late 1990s, scholars re-researched LDPC codes due to the discovery of Turbo codes. Now LDPC codes have been proved theoretically to be a class of error-correcting codes that are very close to the Shannon limit.

LDPC codes are widely used as forward error correction codes in the fields of communication and storage, and are selected by the IEEE 802.16e standard as its channel coding technology. The performance of LDPC codes is close to the Shannon limit when the code length is long enough, but for LDPC codes, a major problem that needs to be faced is that the implementation complexity of the coder increases quadratically with the code length. Therefore, how to make the LDPC code complete the encoding within a time linearly related to the code length has become a very critical issue. Since the LDPC code is also a linear block code, its encoding algorithm is basically similar to that of other linear block codes. It can be mainly divided into three categories: Gaussian elimination method based on generator matrix G, LU encoding algorithm based on parity check matrix H, and simplified Efficient encoding algorithm for approximate lower triangular matrix. These several algorithms have their own advantages and disadvantages, and the encoding algorithm is selected mainly according to the selected LDPC code pattern in the realization.

The LDPC code under the IEEE 802.16e standard has a special structure, and its parity check matrix is a "quasi-bidiagonal" matrix. Its traditional serial coding algorithm has low coding efficiency, so each parity check can be calculated in parallel. bit to improve. Although this parallel computing greatly reduces the encoding delay, it requires a larger amount of storage when implemented in hardware.

Contents of the invention

Purpose of the invention: The present invention aims at the problems existing in the prior art, and provides an improved encoding method and system of LDPC codes in the 802.16e standard, which adopts bidirectional recursive improvement, makes hardware implementation easier, and occupies less memory.

Technical scheme: the improved coding method of LDPC code of the present invention comprises:

(1) Select expansion factor z _f ;

(2) Divide every _{zf bits of the known information bit data vector U into one group, obtain k b groups of} packet data, and divide every zf bits of the parity data vector V to be obtained into one group, Obtain m _b group group data, denoted as Among them, m _b +k _b =n/z _f , n is the code length;

(2) According to the LDPC code base matrix H _b and k _b component data, a _i is calculated according to the following formula:

In the formula, P _{p(i, j)} represents the matrix obtained by cyclically shifting the identity matrix of z _f × z _f to the right by p(i, j) bits, and p(i, j) represents the i-th row in the base matrix H _b the element of column j;

(3) According to a _i , the check digit packet data v ₁ is obtained by calculating according to the following formula:

In the formula, the shape (·) ^(_*) represents the vector obtained by shifting the cycle to the left by * bit, and the shape such as (·) ^(*) represents the vector obtained by shifting the cycle to the right by * bit, and l _x represents the basis The non-zero element in row x in matrix H _b , 2≤x≤m _b -1;

(4) According to the parity bit grouping data v ₁ , the parity bit grouping data v _i is obtained by using the relational expression H _b ×[U,V] ^T = 0 through bidirectional recursive calculation, i=1,...,m _b ;

(5) According to the information bit data vector U and the check bit check bit data vector The encoded LDPC code obtained is C=[U, V].

Further, the step (4) specifically includes:

(4-1) According to the parity group data v ₁ , the parity group data v ₂ and the parity group data are obtained through the relational expression H _b ×[U,V] ^T = 0

In the formula, the form *(·) represents the bit in *, Represents the first bit of the vector after v ₁ is cyclically shifted right by l, l represents the non-zero element in the 1st row or m _b row in the base matrix H _b , and the two non-zero elements are the same;

(4-2) According to v ₂ and Obtain the remaining check bit packet data v _i through bidirectional recursion, i=3,...,m _b -1:

Further, in step (1), the expansion factor z _f is selected according to the 802.16e standard.

The improved coding system of LDPC code in the 802.16e standard of the present invention comprises:

The expansion factor selection module is used to select the expansion factor z _f ;

The data grouping module is used to divide every z _f bits of the known information bit data vector U into a group to obtain k _b groups of packet data, and divide every z _f bits of the parity data vector V to be obtained into A group, get m _b group group data, denoted as Among them, m _b +k _b =n/z _f , n is the code length;

The first calculation module is used to calculate and obtain a _i according to the following formula according to the LDPC code base matrix H _b and k _b group group data:

In the formula, P _{p(i, j)} represents the matrix obtained by cyclically shifting the identity matrix of z _f × z _f to the right by p(i, j) bits, and p(i, j) represents the i-th row in the base matrix H _b the element of column j;

The second calculation module is used to calculate and obtain the check digit packet data v ₁ according to the following formula according to a _i :

In the formula, the shape (·) ^(_*) represents the vector obtained by shifting the cycle to the left by * bit, and the shape such as (·) ^(*) represents the vector obtained by shifting the cycle to the right by * bit, and l _x represents the basis The non-zero element in row x in matrix H _b , 2≤x≤m _b -1;

The third calculation module is used to obtain the check digit group data v i through the relational expression H _b ×[U,V] ^T = 0 bidirectional recursive calculation according to the check digit group data v ₁ , _i =1,...,m _b ;

Coding synthesis module, for according to information bit data vector U and check bit check bit data vector The encoded LDPC code obtained is C=[U, V].

Further, the third calculation module specifically includes:

The first calculation unit is used to obtain the check bit group data v ₂ and the check bit group data by recursion according to the check bit group data v ₁

In the formula, the form *(·) represents the bit in *, Represents the first bit of the vector after v ₁ is cyclically shifted right by l, l represents the non-zero element in the 1st row or m _b row in the base matrix H _b , and the two non-zero elements are the same;

The second calculation unit is used to calculate according to v ₂ and Obtain the remaining check bit packet data v _i through bidirectional recursion, i=3,...,m _b -1:

Further, the expansion factor selection module selects the expansion factor z _f according to the 802.16e standard.

Beneficial effects: compared with the prior art, the present invention has the remarkable advantages that: the method carries out two-way recursive improvement on serial and parallel coding methods through the research on the LDPC code used in the IEEE802.16e standard, and the analysis shows that The new method has low computational complexity, can improve the parallelism of encoding, and the calculation is simpler in hardware implementation.

Detailed ways

This embodiment provides an improved encoding method for LDPC codes in the 802.16e standard, the method comprising:

(1) Select the expansion factor z _f according to the 802.16e standard;

(2) Divide every _{zf bits of the known information bit data vector U into one group, obtain k b groups of} packet data, and divide every zf bits of the parity data vector V to be obtained into one group, Obtain m _b group group data, denoted as Among them, u _i =[u _i (1),u _i (1),...,u _i (z _f )], v _i =[v _i (1),v _i (1),..., v _i (z _f )], form such as * ( ) represents the bit in *, m _b +k _b =n/z _f , n is the code length;

(2) According to the LDPC code base matrix H _b and k _b component data, a _i is calculated according to the following formula:

In the formula, P _{p(i, j)} represents the matrix obtained by cyclically shifting the identity matrix of z _f × z _f to the right by p(i, j) bits, and p(i, j) represents the i-th row in the base matrix H _b the element of column j;

(3) According to a _i , the check digit packet data v ₁ is obtained by calculating according to the following formula:

In the formula, the shape (·) ^(_*) represents the vector obtained by shifting the cycle to the left by * bit, and the shape such as (·) ^(*) represents the vector obtained by shifting the cycle to the right by * bit, and l _x represents the basis The non-zero element in row x in matrix H _b , 2≤x≤m _b -1;

(4) According to the check bit group data v ₁ , the check bit group data v _i is obtained through the relational expression H _b ×[U,V] ^T =0 bidirectional recursive calculation, i=1,...,m _b .

Among them, according to the relational expression H _b ×[U,V] ^T =0, it can be obtained:

a _i +v _i +v _i+1 ＝0(1≤i≤m _b -2,i≠x)

Through the above formula, we can know the calculation method of grouped data v _i , which is:

According to the parity grouping data v ₁ , the parity grouping data v ₂ and the parity grouping data are obtained by recursion

In the formula, the form *(·) represents the bit in *, Represents the first bit of the vector after v ₁ is cyclically shifted right by l, l represents the non-zero element in the 1st row or m _b row in the base matrix H _b , and the two non-zero elements are the same;

According to v ₂ and Obtain the remaining check bit packet data v _i through bidirectional recursion, i=3,...,m _b -1:

(5) According to the information bit data vector U and the check bit check bit data vector The encoded LDPC code obtained is C=[U, V].

This embodiment also provides an improved coding system for LDPC codes in the 802.16e standard, including:

The expansion factor selection module is used to select the expansion factor z _f ;

The data grouping module is used to divide every z _f bits of the known information bit data vector U into a group to obtain k _b groups of packet data, and divide every z _f bits of the parity data vector V to be obtained into A group, get m _b group group data, denoted as Among them, m _b +k _b =n/z _f , n is the code length;

The first calculation module is used to calculate and obtain a _i according to the following formula according to the LDPC code base matrix H _b and k _b group group data:

In the formula, P _{p(i, j)} represents the matrix obtained by cyclically shifting the identity matrix of z _f × z _f to the right by p(i, j) bits, and p(i, j) represents the i-th row in the base matrix H _b the element of column j;

The second calculation module is used to calculate and obtain the check digit packet data v ₁ according to the following formula according to a _i :

In the formula, the shape (·) ^(_*) represents the vector obtained by shifting the cycle to the left by * bit, and the shape such as (·) ^(*) represents the vector obtained by shifting the cycle to the right by * bit, and l _x represents the basis The non-zero element in row x in matrix H _b , 2≤x≤m _b -1;

The third calculation module is used to obtain the check digit group data v i through the relational expression H _b ×[U,V] ^T = 0 bidirectional recursive calculation according to the check digit group data v ₁ , _i =1,...,m _b ;

Coding synthesis module, for according to information bit data vector U and check bit check bit data vector The encoded LDPC code obtained is C=[U, V].

Further, the third calculation module specifically includes:

The first calculation unit is used to obtain the check bit group data v ₂ and the check bit group data by recursion according to the check bit group data v ₁

In the formula, the form *(·) represents the bit in *, Represents the first bit of the vector after v ₁ is cyclically shifted right by l, l represents the non-zero element in the 1st row or m _b row in the base matrix H _b , and the two non-zero elements are the same;

The second calculation unit is used to calculate according to v ₂ and Obtain the remaining check bit packet data v _i through bidirectional recursion, i=3,...,m _b -1:

Further, the expansion factor selection module selects the expansion factor z _f according to the 802.16e standard.

What is disclosed above is only a preferred embodiment of the present invention, which cannot limit the scope of rights of the present invention. Therefore, equivalent changes made according to the claims of the present invention still fall within the scope of the present invention.

Claims (6)

1. a kind of improvement coding method of LDPC code, it is characterised in that this method includes：

(1) spreading factor z is chosen_f；

(2) by the every z of known information bit data vector U_fA bit is divided into one group, obtains k_bGroup packet data, will be to be sought The every z of check bit data vector V_fA bit is divided into one group, obtains m_bGroup packet data, is denoted asWherein, m_b+k_b=n/z_f, n is code length；

(2) according to LDPC code basic matrix H_bAnd k_bA is calculated according to following formula in group packet data_i：

In formula, P_p(i,j)It indicates z_f×z_fThe position unit matrix ring shift right p (i, j) after obtained matrix, p (i, j) indicates group moment Battle array H_bIn the i-th row jth column element；

(3) according to a_iCheck bit packet data v is calculated according to following formula₁：

In formula, shaped like ()^(-*)The vector that will be obtained after ring shift left * is indicated, shaped like ()^(*)Indicating will the circulation right side The vector obtained after moving *, l_xIndicate basic matrix H_bIn be located at xth row nonzero element, 2≤x≤m_b-1；

(4) according to check bit packet data v₁Pass through relational expression H_b×[U,V]^T=0 is calculated check bit point using forward-backward recutrnce Group data v_i, i=1 .., m_b；

(5) according to information bit data vector U and check bit check bit data vectorAfter being encoded LDPC code is C=[U, V].

2. a kind of improvement coding method of LDPC code according to claim 1, it is characterised in that：The step (4) is specific Including：

(4-1) is according to check bit packet data v₁Pass through relational expression H_b×[U,V]^T=0 obtains check bit packet data v₂And verification Position packet data

In formula, the bit in * is indicated shaped like * (),Indicate v₁1st ratio of the vector after ring shift right l Spy, l indicate basic matrix H_bIn be located at 1 row or m_bCapable nonzero element, two nonzero elements are identical；

(4-2) is according to v₂WithRemaining check bit packet data v is obtained by forward-backward recutrnce_i, i=3 .., m_b-1：

3. a kind of improvement coding method of LDPC code according to claim 1, it is characterised in that：Basis in step (1) 802.16e standard chooses spreading factor z_f。

4. the improvement coded system of LDPC code in a kind of 802.16e standard, it is characterised in that including：

Spreading factor chooses module, for choosing spreading factor z_f；

Data grouping module is used for the every z of known information bit data vector U_fA bit is divided into one group, obtains k_bGroup grouping Data, by the every z of check bit data vector V to be sought_fA bit is divided into one group, obtains m_bGroup packet data, is denoted asWherein, m_b+k_b=n/z_f, n is code length；

First computing module, for according to LDPC code basic matrix H_bAnd k_bA is calculated according to following formula in group packet data_i：

In formula, P_p(i,j)It indicates z_f×z_fThe position unit matrix ring shift right p (i, j) after obtained matrix, p (i, j) indicates group moment Battle array H_bIn the i-th row jth column element；

Second computing module, for according to a_iCheck bit packet data v is calculated according to following formula₁：

In formula, shaped like ()^(-*)The vector that will be obtained after ring shift left * is indicated, shaped like ()^(*)Indicating will the circulation right side The vector obtained after moving *, l_xIndicate basic matrix H_bIn be located at xth row nonzero element, 2≤x≤m_b-1；

Third computing module, for according to check bit packet data v₁Pass through relational expression H_b×[U,V]^T=0 forward-backward recutrnce calculates To check bit packet data v_i, i=1 .., m_b；

Synthesis module is encoded, for according to information bit data vector U and check bit check bit data vector LDPC code after being encoded is C=[U, V].

5. the improvement coded system of LDPC code in 802.16e standard according to claim 4, it is characterised in that：Described Three computing modules specifically include：

First computing unit, for according to check bit packet data v₁Check bit packet data v is obtained by recurrence₂And check bit Packet data

In formula, the bit in * is indicated shaped like * (),Indicate v₁1st ratio of the vector after ring shift right l Spy, l indicate basic matrix H_bIn be located at 1 row or m_bCapable nonzero element, two nonzero elements are identical；

Second computing unit, for according to v₂WithRemaining check bit packet data v is obtained by forward-backward recutrnce_i, i=3 .., m_b-1：

6. the improvement coded system of LDPC code in 802.16e standard according to claim 4, it is characterised in that：The expansion It opens up in predictor selection module and spreading factor z is chosen according to 802.16e standard_f。