CN104426553B - The coding method of low-density parity check (LDPC) matrix - Google Patents

Abstract

The size of the size of check part and circulation submatrix in a kind of coding method of low-density parity check (LDPC) matrix, including the setting low-density parity check (LDPC) matrix；Initialize each check bit corresponding to the check part；The check bit is grouped to obtain multiple check bit groups by the size according to the circulation submatrix；Check bit in each check bit group and its associated information bit in low-density parity check (LDPC) matrix are subjected to accumulation process；Interleaving treatment is made to each check bit after cumulative；Each check bit after interleaving treatment is carried out mould 2 plus computing to obtain final check bit.The technical program reduces encoder complexity.

Description

Coding method of low-density parity check matrix

Technical Field

The invention relates to the field of coding, in particular to a coding method of a low-density parity check matrix.

Background

The LDPC code was proposed by Gallager in his phd paper in 1963 for the first time, meanwhile Gallager also proposed a probability decoding algorithm of the LDPC code, but since the probability iterative decoding calculation is too complex, the LDPC code quickly sinks the sea in the communication field at that time in view of the difficulty in implementation of the technology development at that time. After that, few learners have paid much attention to LDPC codes, except for the bipartite graph that Tanner visualizes in the 80's last century to describe iterative decoding.

In 1993, the Turbo code was proposed, so that 45 years later, a coding scheme approaching the Shannon limit was first seen. Until now, people have paid attention to the excellent performance of iterative decoding, and meanwhile, the iterative theory based on bipartite graph (Tanner graph) has made a great breakthrough: spielman explains the error correction process as a process of gradually reducing errors, proves that a bipartite Graph-based coding and decoding algorithm has linear complexity, on the basis, scholars propose conditions and a method for generating a bipartite Graph with certain error correction capability by using an Expander Graph, and then Kschischang and the like establish the theory of a Factor Graph (Factor Graph) and further deepen the Graph theory basis based on LDPC iterative decoding; based on these studies, Wiber proposed a graph-based LDPC iterative decoding algorithm. All these developments have been made, so that in 1995 Mackay and Neal discovered that LDPC codes have performance approaching the shannon limit as Turbo codes, thereby causing a hot tide of research on LDPC codes.

The LDPC code is more technically and particularly more advantageous in complexity than the Turbo code, and is more suitable for high-speed data transmission and high-performance requirements of a future system, and thus is widely used. Currently, communication systems using LDPC codewords include: the european second generation digital broadcast television transmission standard DVB2 series; the ieee802.11n wireless lan standard; the ieee802.11e wireless wide area network standard; the terrestrial transmission standard for digital television (DTTB) in china, and the near-earth, deep space communication systems of the north american CCSDS, and the like.

From an implementation perspective, several challenges need to be faced. For example, storage is an important reason that LDPC codes are not widely used in practice. Also, one key issue in LDPC code implementation is how to implement a connection network between several processing engines (nodes) of the decoder. In addition, the computational load in the decoding process, especially check node calculation, also presents problems.

Therefore, there is a need for an LDPC communication system that uses simple encoding and decoding processes. There is also a need to efficiently support high data rates using LDPC codes without introducing greater complexity. There is also a need to improve the performance of LDPC encoders and decoders, to minimize the memory requirements for implementing LDPC encoding, and to a simplified communication scheme between processing nodes of an LDPC decoder.

Disclosure of Invention

The invention solves the problem that the existing coding method of the low-density parity check matrix is relatively complicated.

To solve the above problem, an embodiment of the present invention provides a method for encoding a low density parity check matrix, including: setting the size of a check part in the low-density parity check matrix and the size of a cyclic sub-matrix; initializing each check bit corresponding to the check part; grouping the check bits according to the size of the cyclic subarray to obtain a plurality of check bit groups; accumulating the check bits in each check bit group and the information bits related to the check bits in the low-density parity check matrix; interleaving each accumulated check bit; and performing modulo-2 addition operation on each check bit subjected to interleaving processing to obtain a final check bit.

Optionally, the size of the check portion is M × M, and the size of the cyclic sub-array is q × q; the grouping the check bits according to the size of the cyclic sub-array to obtain a plurality of check bit groups comprises: setting the parity bit to { p₀,p₁,p₂,p₃,p₄,p₅,...,p_M-1}; and grouping the check bits by taking q bits as a group in sequence to obtain a plurality of check bit groups.

Optionally, the accumulating the check bits in each check bit group and the information bits associated with the check bits in the low density parity check matrix includes:

for q bits p in each check bit group_mThe following XOR operation is performed:

wherein M is 0,1,2, 3.Is represented in a low density parity check matrix with p_mThe associated information bits are then transmitted to the receiver,

y_mobtained according to the following formula:

where "mod" denotes a modulo operation,denotes a rounding-down operation, and x denotes a position of a column in which "1" in a row in the low density parity check matrix represented by the first check bit in each check bit group is located, but does not include a position of a column of "1" in a parity part in the low density parity check matrix.

Optionally, the interleaving processing on the accumulated check bits includes:

and interleaving the accumulated check bits according to a 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；Q＝M/q；

{p₀,p₁,p₂,p₃,p₄,p₅,...,p_M-1denotes the check bits before interleaving;

{p₀',p₁',p₂',p₃',p₄',p₅',...,p_M-1' } denotes the interleaved check bits.

Optionally, performing modulo-2 addition on each parity bit after interleaving to obtain a final parity bit is implemented by the following formula:

wherein k represents a position of a second "1" of a last column of a parity check part in the low density parity check matrix; the final parity bit is { p }₀',p₁',p₂',p₃',p₄',p₅',...,p_M-1'}。

Optionally, before initializing each parity bit corresponding to the parity part, the method further includes the following steps: setting a position of a second "1" in a last column of the parity part in the low density parity check matrix.

Compared with the prior art, the technical scheme of the invention has the following advantages:

the embodiment of the invention adopts a double diagonal structure (before interleaving) of a low-density parity check matrix check part and is characterized in that: there is a 1 in the upper right corner of the matrix of the check portion (i.e., the last column of the first row) and a 1 in the middle of the last column (the k-th row, the number of rows starting from 0). Based on such a structure, the bits of the parity part can be obtained by using the bit and parity equations of the information part without using a coding matrix, thereby reducing the coding complexity.

Drawings

Fig. 1 is a flowchart illustrating an embodiment of a method for encoding a low density parity check matrix according to the present invention.

Detailed Description

The inventor finds that the existing encoding method of the low-density parity check matrix is relatively complicated.

In view of the above problems, the inventors have studied to provide a method for encoding a low density parity check matrix, thereby reducing the encoding complexity.

In order to make the aforementioned objects, features and advantages of the present invention comprehensible, embodiments accompanied with figures are described in detail below.

Fig. 1 is a flow chart illustrating an embodiment of a method for encoding a low density parity check matrix according to the present invention. Referring to fig. 1, the encoding method includes the steps of:

step S1: setting the size of a check part in the low-density parity check matrix and the size of a cyclic sub-matrix;

step S2: initializing each check bit corresponding to the check part;

step S3: grouping the check bits according to the size of the cyclic subarray to obtain a plurality of check bit groups;

step S4: accumulating the check bits in each check bit group and the information bits related to the check bits in the low-density parity check matrix;

step S5: interleaving each accumulated check bit;

step S6: and performing modulo-2 addition operation on each check bit subjected to interleaving processing to obtain a final check bit.

The following describes an implementation of the above coding method with reference to a specific embodiment.

The size of the parity portion of the low density parity check matrix and the size of the cyclic sub-matrix are set as described in step S1.

The low density parity check matrix includes an information bit portion and a check portion.

Let LDPC code word be c ═ (i)₀,i₁,...,i_j,...,i_K-1,p₀,p₁,...,p_m,...,p_M-1) (ii) a Wherein (i)₀,i₁,...,i_m,...,i_K-1) Which are known {1,0} sequences, for the information bits. (p)₀,p₁,p₂,...,p_M-1) For the check bits, for the bits to be calculated.

In this embodiment, the size M of the parity portion in the low density parity check matrix is q × q, and the size of the cyclic sub-matrix is q × q. Typically, the check portion is located at the right part of the low density parity check matrix, as shown in the structure of codeword c of the above LDPC.

Before executing step S2, the present embodiment further includes: setting a position k of a second "1" in a last column of a parity part in the low density parity check matrix. The check part matrix (P matrix) is constructed as follows, and the rows of the P matrix are counted from 0.

The structure of the P matrix which is a dual diagonal matrix structure before interweaving is different from the prior structure in that: there is a 1 in the top right corner of the P matrix (i.e., the last column in the first row) and a 1 in the middle of the last column (the k-th row, starting with 0).

In step S2, each parity bit corresponding to the parity part is initialized.

I.e. p₀＝0,p₁＝0,p₂＝0,p₃＝0,p₄＝0,p₅＝0,...,p_M-10, wherein each p_iRepresenting one column of the check matrix, e.g. p_mRepresenting the mth column in the check matrix.

As shown in step S3, the check bits are grouped according to the size of the cyclic sub-array to obtain a plurality of check bit groups.

Specifically, first, the check bit is set to { p }₀,p₁,p₂,p₃,p₄,p₅,...,p_M-1}. Then, the check bits are grouped in sequence by q bits to obtain a plurality of check bit groups.

For example, the check bit group is:

{p_jq+0,p_jq+1,...,p_jq+(q-1)j takes the value of (0, 1,2, …, q-1).

As described in step S4, the check bits in each check bit group are accumulated with their associated information bits in the low density parity check matrix.

Specifically, for q bits p in each check bit group_mThe following XOR operation is performed:

wherein M is 0,1,2, 3.

Representing the sum p in the low density parity check matrix_mThe associated information bits are then transmitted to the receiver,

y_mobtained according to the following formula:

where "mod" denotes a modulo operation,representing a rounding-down operation, x representing the first parity bit in each parity bit group (which may be p, for example)₀，p_q+0，p_2q+0，…，p_jq+0…) in the low density parity check matrix (corresponding to rows 0, q,2q,3 q.,. jq.,. row) but not including the column position of "1" in the parity part of the low density parity check matrix.

Taking the code word in table 1 as an example, q is 126, the number of parity bits M is 7560, the number of information bits K is 7560, and the position K of the middle 1 in the last column is 3780.

First row number in table 1:

528、689、768、1333、4402、5010

each number representing the first row (corresponding to the first check bit p) in the low density parity check matrix₀) A position of middle "1" (i.e., a position of a column), but this position does not include a position of a column of "1" of the check portion of the low density parity check matrix.

The number of the row is x, which represents the first bit p in the first check bit block₀The position of the "1" in row 0 of the check matrix is represented (i.e., the position of the column, which also starts counting with 0).

Then there are:

after this is done, there is, according to equation (1):

the next second row of numbers:

441 695 1268 1778 2308 5044

and the rest of the rows are analogized according to the formula (1) and are not listed.

As described in step S5, the accumulated parity bits are interleaved.

Specifically, the method comprises the following steps: and interleaving the accumulated check bits according to a 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 is 0,1,2,3, … …, q-1.

Taking table 1 as an example, the code length is 15120, the code rate is 1/2, and the size of the cyclic sub-array is 126 × 126. In this case, M7560, q 126,

the interleaving process specifically includes:

p₀'＝p₀；p₁'＝p₀₊₁₂₆；p₂'＝p_0+2×126；p₃'＝p_0+3×126；

p₄'＝p_0+4×126,...,p_60-1'＝p_0+(60-1)q；

p₆₀'＝p₁；p₆₀₊₁'＝p₁₊₁₂₆；p₆₀₊₂'＝p_1+2×126；p₆₀₊₃'＝p_1+3×126；

p₆₀₊₄'＝p_1+4×126,...,p_2×60-1'＝p_{1+(60-1)×126}；

p_(126-1)×60'＝p_126-1；p_{(126-1)×60+1}'＝p_(126-1)+126；p_{(126-1)×60+2}'＝p_{(126-1)+2×126}；

p_{(126-1)×60+3}'＝p_{(126-1)+3×126}；

p_{(126-1)×60+4}'＝p_{(126-1)+4×126},...,p_{(126-1)×60+60-1}'＝p_{(126-1)+(60-1)×60}；

in this embodiment, { p₀,p₁,p₂,p₃,p₄,p₅,...,p_M-1Denotes the check bits before interleaving;

{p₀',p₁',p₂',p₃',p₄',p₅',...,p_M-1' } denotes the interleaved check bits.

As shown in step S6, the parity bits after interleaving are modulo-2 added to obtain the final parity bits.

Specifically, this step is realized by the following formula:

where k represents the position of the second "1" in the last column of the parity check part in the low density parity check matrix.

Obtained (p)₀',p₁',...,p_m',...,p_M-1') is the finally coded check bit, and the finally obtained LDPC code c ═ i₀,i₁,...,i_j,...,i_K-1,p₀',p₁',...,p_m',...,p_M-1')。

Table 1 below shows a code table with a code length 15120, a code rate 1/2, and a cyclic sub-array size 126 × 126.

In summary, the dual diagonal structure (before interleaving) of the low density parity check matrix check part adopted in the embodiments of the present invention is characterized in that: there is a 1 in the upper right corner of the matrix of the check portion (i.e., the last column of the first row) and a 1 in the middle of the last column (the k-th row, the number of rows starting from 0). Based on such a structure, the bits of the parity part can be obtained by using the bit and parity equations of the information part without using a coding matrix, thereby reducing the coding complexity.

Although the present invention has been described with reference to the preferred embodiments, it is not intended to limit the present invention, and those skilled in the art can make variations and modifications of the present invention without departing from the spirit and scope of the present invention by using the methods and technical contents disclosed above.

Claims (5)

1. A method for encoding a low density parity check matrix, wherein the last column of the parity check part in the low density parity check matrix has three 1 s, comprising the steps of:

setting the size of a check part in the low-density parity check matrix and the size of a cyclic sub-matrix;

setting a position of a second "1" in a last column of a parity part in the low density parity check matrix;

initializing each check bit corresponding to the check part;

grouping the check bits according to the size of the cyclic subarray to obtain a plurality of check bit groups;

accumulating the check bits in each check bit group and the information bits related to the check bits in the low-density parity check matrix;

interleaving each accumulated check bit;

and performing modulo-2 addition operation on each check bit subjected to interleaving processing to obtain a final check bit.

2. The method of encoding a low density parity check matrix according to claim 1, wherein a codeword of the low density parity check matrix is made c ═ (i)₀,i₁,...,i_j,...,i_K-1,p₀,p₁,...,p_m,...,p_M-1) Wherein (i)₀,i₁,...,i_m,...,i_K-1) For information bits, are known {1,0} sequences, (p)₀,p₁,p₂,...,p_M-1) The check bits are bits to be calculated, the size of the check part is M × M, and the size of the cyclic sub-array is q × q; the grouping the check bits according to the size of the cyclic sub-array to obtain a plurality of check bit groups comprises:

setting the parity bit to { p₀,p₁,p₂,p₃,p₄,p₅,...,p_M-1}；

And grouping the check bits by taking q bits as a group in sequence to obtain a plurality of check bit groups.

3. The method for encoding a low density parity check matrix according to claim 2, wherein accumulating the check bits in each check bit group with the information bits associated therewith in the low density parity check matrix comprises:

for q bits p in each check bit group_mThe following XOR operation is performed:

wherein M is 0,1,2, 3.Is represented in a low density parity check matrix with p_mThe associated information bits are then transmitted to the receiver,

y_mobtained according to the following formula:

where "mod" denotes a modulo operation,denotes a rounding-down operation, and x denotes a position of a column in which "1" is located in a row in the low density parity check matrix associated with the first check bit in each check bit group, but does not include a position of a column of "1" in the parity part in the low density parity check matrix.

4. The method of encoding a low density parity check matrix according to claim 3, wherein the interleaving the accumulated check bits comprises:

and interleaving the accumulated check bits according to a 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 is 0,1,2,3, … …, q-1; q is M/Q;

{p₀,p₁,p₂,p₃,p₄,p₅,...,p_M-1denotes the correction before interleavingChecking bits;

{p₀',p₁',p₂',p₃',p₄',p₅',...,p_M-1' } denotes the interleaved check bits.

5. The method of encoding a low density parity check matrix according to claim 4, wherein performing modulo-2 addition on each interleaved check bit to obtain a final check bit is implemented by the following equation:

$\begin{array}{c}{p_k}^{\′}={p_0}^{\′}\⊕{p_1}^{\′}\⊕{p_2}^{\′}\⊕{p_3}^{\′}\⊕\mathrm{...}\⊕{p_k}^{\′}\\ {p_{k+1}}^{\′}={p_{k+1}}^{\′}\⊕{p_k}^{\′}\\ {p_{k+2}}^{\′}={p_{k+2}}^{\′}\⊕{p_{k+1}}^{\′}\end{array}$

$\begin{array}{c}{p_{k+3}}^{\′}={p_{k+3}}^{\′}\⊕{p_{k+2}}^{\′}\\ .\\ .\\ .\\ {p_{M-1}}^{\′}={p_{M-1}}^{\′}\⊕{p_{M-2}}^{\′}\\ {p_0}^{\′}={p_0}^{\′}\⊕{p_{M-1}}^{\′}\\ .\\ .\\ .\\ {p_{k-1}}^{\′}={p_{k-1}}^{\′}\⊕{p_{k-2}}^{\′}\end{array}$

wherein k represents a position of a second "1" of a last column of a parity check part in the low density parity check matrix; the final parity bit is { p }₀',p₁',p₂',p₃',p₄',p₅',...,p_M-1'}。