CN101335528B

CN101335528B - Construction method and encoding method for multiple LDPC code

Info

Publication number: CN101335528B
Application number: CN2008100300621A
Authority: CN
Inventors: 马啸; 王秀妮; 白宝明
Original assignee: Sun Yat Sen University
Current assignee: Sun Yat Sen University
Priority date: 2008-08-07
Filing date: 2008-08-07
Publication date: 2011-05-11
Anticipated expiration: 2028-08-07
Also published as: CN101335528A

Abstract

The present invention belongs to the technical field of communication, and particularly relates to a construction method of a multivariate LDPC code, comprising the following steps: the parity check matrix H of the multivariate LDPC code is a block matrix consisting of (m×n) sub-matrices H _{i, j} , each A sub-matrix H _{i, j} is obtained by multiplying the scale factor β _{i, j} ∈ GF(q) by a (l×l) identity matrix, and then shifting s _{i, j} times to the left according to the column cycle, where GF(q) is a finite field with q elements; the check matrix H of the multivariate LDPC code can be divided into two parts H=(H ₁ , H ₂ ), where H ₂ is a block bidiagonal matrix with a size of (m×m) , H ₁ is composed of the remaining sub-matrices in H; H ₁ corresponds to information symbols, and H ₂ corresponds to check symbols. In addition, the present invention also provides a fast encoding method suitable for the invented multi-element LDPC code.

Description

A Construction Method and Encoding Method of Multivariate LDPC Code

技术领域technical field

本发明属于通讯技术领域，特别涉及一种多元LDPC码的构造方法及编码方法。The invention belongs to the technical field of communication, and in particular relates to a construction method and an encoding method of a multivariate LDPC code.

技术背景technical background

低密度一致校验码(LDPC码)是一种逼近Shannon限的线性分组码，可由校验矩阵来描述。早在1962年，Gallager就提出了LDPC码，并证明了该码可以比其它纠错码更加接近Shannon极限。然而，由于其复杂度较高，在当时并没有引起人们的注意。随着Turbo码的提出，1995年，Mackay和Neal又重新发现了LDPC码。从此LDPC码引起人们的广泛关注。Low-density parity-check code (LDPC code) is a linear block code approaching the Shannon limit, which can be described by a check matrix. As early as 1962, Gallager proposed the LDPC code and proved that the code can be closer to the Shannon limit than other error-correcting codes. However, due to its high complexity, it did not attract people's attention at the time. With the introduction of Turbo codes, Mackay and Neal rediscovered LDPC codes in 1995. Since then, LDPC codes have attracted widespread attention.

根据校验矩阵的产生过程，LDPC码可分为随机型和结构型两大类。当码长较长时，随机产生一个稀疏矩阵作为LDPC码的校验矩阵，该码的性能就可以非常接近Shannon限。然而，随机型LDPC码的编码复杂度较高，仅适用于理论研究方面。近几年，人们在代数和有限几何的基础上提出了很多性能优良的结构型LDPC码。According to the generation process of check matrix, LDPC codes can be divided into two categories: random type and structured type. When the code length is long, a sparse matrix is randomly generated as the parity check matrix of the LDPC code, and the performance of the code can be very close to the Shannon limit. However, the encoding complexity of random LDPC codes is relatively high, which is only suitable for theoretical research. In recent years, people have proposed many structural LDPC codes with excellent performance on the basis of algebra and finite geometry.

目前，大部分的研究工作以及发明专利是针对二元LDPC码的。一些具有高效、快速编码算法的结构型二元LDPC码被广泛地应用到各种通信标准中，如3GPP2、802.16e、802.11n等等。与二元LDPC码相比，多元LDPC码的研究工作相对较少。1998年Davey与MacKay通过实验仿真，证实了在相同条件下，多元LDPC码的误比特率(BER)性能优于二元LDPC码，指出在相同BER的情况下，采用多元LDPC码可获得大约1dB的编码增益。特别地，多元LDPC码可以与高阶调制相结合，从而节省带宽受限通信系统的发射功率。但是，现有的多元LDPC码存在很多问题，包括较高的存储空间以及较复杂的编码过程等方面。At present, most research work and invention patents are aimed at binary LDPC codes. Some structured binary LDPC codes with efficient and fast coding algorithms are widely used in various communication standards, such as 3GPP2, 802.16e, 802.11n and so on. Compared with binary LDPC codes, research work on multivariate LDPC codes is relatively less. In 1998, Davey and MacKay confirmed through experimental simulation that under the same conditions, the bit error rate (BER) performance of multivariate LDPC codes is better than that of binary LDPC codes, pointing out that under the same BER conditions, using multivariate LDPC codes can obtain about 1dB coding gain. In particular, multivariate LDPC codes can be combined with high-order modulation to save transmit power in bandwidth-constrained communication systems. However, there are many problems in the existing multivariate LDPC codes, including relatively high storage space and relatively complicated encoding process.

发明内容Contents of the invention

针对现有技术的缺点，本发明的目的是提供一种多元LDPC码的构造方法及编码方法。所提出的构造方法解决了多元LDPC码的存储空间问题；而且，所设计出的编码方法能够使多元LDPC码更好的在实际中得到应用。Aiming at the shortcomings of the prior art, the object of the present invention is to provide a construction method and an encoding method of a multivariate LDPC code. The proposed construction method solves the storage space problem of multivariate LDPC codes; moreover, the coding method designed can make multivariate LDPC codes be better applied in practice.

为实现上述目的，本发明的技术方案为：一种多元LDPC码的构造方法，其包括以下步骤：To achieve the above object, the technical solution of the present invention is: a kind of construction method of multivariate LDPC code, it comprises the following steps:

a.多元LDPC码的校验矩阵H是有限域GF(q)上的分块矩阵，由(m×n)个子矩阵构成；位于校验矩阵H的第i行与第j列交叉位置的子矩阵H_i，j是由尺度因子β_i，j∈GF(q)乘以一个(l×l)的单位矩阵后，再按列循环左移s_i，j次得到，其中0≤i≤m-1，0≤j≤n-1，0≤s_i，j≤l-1；a. The parity check matrix H of the multivariate LDPC code is a block matrix on the finite field GF(q), which is composed of (m×n) sub-matrices; The matrix H _{i, j} is obtained by multiplying the scale factor β _{i, j} ∈ GF(q) by a (l×l) identity matrix, and then shifting s _{i, j} times to the left according to the column cycle, where 0≤i≤m -1, 0≤j≤n-1, 0≤s _{i, j} ≤l-1;

b.将多元LDPC码的校验矩阵经过列顺序调整分为左右两部分：H＝(H₁H₂)，其中H₂由(m×m)个子矩阵构成，对应m个长度为l的校验子序列，而H₁由校验矩阵H中剩下的子矩阵构成，对应(n-m)个长度为l的信息子序列；b. Divide the check matrix of the multivariate LDPC code into two parts: H=(H ₁ H ₂ ), wherein H ₂ is composed of (m×m) sub-matrices, corresponding to m check matrixes of length l check sub-sequence, and H ₁ consists of the remaining sub-matrixes in the check-check matrix H, corresponding to (nm) information sub-sequences with a length of l;

c.将多元LDPC码的校验矩阵H中对应校验子序列的矩阵H₂经过行顺序调整为一个大小为(m×m)的分块双对角矩阵，c. Adjust the matrix _H2 corresponding to the syndrome sequence in the parity check matrix H of the multivariate LDPC code into a block bidiagonal matrix with a size of (m×m),

${H h}_{22} = = [\begin{matrix} {H h}_{00,, k k} & 00 & 00 & 00 & . . & . . & . . & 00 & 00 & 00 \\ {H h}_{11,, k k} & {H h}_{11,, k k + + 11} & 00 & 00 & . . & . . & . . & 00 & 00 & 00 \\ 00 & {H h}_{22,, k k + + 11} & {H h}_{22,, k k + + 22} & 00 & . . & . . & . . & 00 & 00 & 00 \\ . . & . . & . . & . . & . . & . . & . . \\ . . & . . & . . & . . & . . & . . & . . & . . & . . & . . \\ . . & . . & . . & . . & . . & . . & . . \\ 00 & 00 & 00 & 00 & . . & . . & . . & {H h}_{m m - - 22,, n no - - 33} & {H h}_{m m - - 22,, n no - - 22} & 00 \\ 00 & 00 & 00 & 00 & . . & . . & . . & 00 & {H h}_{m m - - 11,, n no - - 22} & {H h}_{m m - - 11,, n no - - 11} \end{matrix}] - - - - - - ((1.1 1.1)),,$

其中k＝n-m。where k=n-m.

在步骤a中，分块子矩阵H_i，j是一个尺度循环矩阵，In step a, the block submatrix H _i,j is a scaled circulant matrix,

${H h}_{i i,, j j} = = {β β}_{i i,, j j} {P P}^{{s the s}_{i i,, j j}} - - - - - - ((1.2 1.2)),,$

其中P是由(l×l)的单位阵循环左移1次得到的矩阵。Among them, P is a matrix obtained by cyclically shifting the unit matrix of (l×l) to the left once.

矩阵H₂中，主对角线上的子矩阵的尺度因子为1，次对角线上的子矩阵的尺度因子为α，其中α是GF(q)的本原元，此时H₂详细描述为：In the matrix H ₂ , the scale factor of the sub-matrix on the main diagonal is 1, and the scale factor of the sub-matrix on the sub-diagonal is α, where α is the primitive element of GF(q). At this time, the details of H ₂ described as:

${H h}_{22} = = [\begin{matrix} {P P}^{{s the s}_{00,, k k}} & 00 & 00 & 00 & . . & . . & . . & 00 & 00 & 00 \\ {αP αP}^{{s the s}_{11,, k k}} & {P P}^{{s the s}_{11,, k k + + 11}} & 00 & 00 & . . & . . & . . & 00 & 00 & 00 \\ 00 & {αP αP}^{{s the s}_{22,, k k + + 11}} & {P P}^{{s the s}_{22,, k k + + 22}} & 00 & . . & . . & . . & 00 & 00 & 00 \\ . . & . . & . . & . . & . . & . . & . . \\ . . & . . & . . & . . & . . & . . & . . & . . & . . & . . \\ . . & . . & . . & . . & . . & . . & . . \\ 00 & 00 & 00 & 00 & . . & . . & . . & {αP αP}^{{s the s}_{m m - - 22,, n no - - 33}} & {P P}^{{s the s}_{m m - - 22,, n no - - 22}} & 00 \\ 00 & 00 & 00 & 00 & . . & . . & . . & 00 & {αP αP}^{{s the s}_{m m - - 11,, n no - - 22}} & {P P}^{{s the s}_{m m - - 11,, n no - - 11}} \end{matrix}] - - - - - - ((1.3 1.3)) . .$

从GF(q)中选取k个非零元素β₀，β₁，…，β_k-1作为矩阵H₁中第0行的k个子矩阵的尺度因子，相应的第i行的k个子矩阵的尺度因子分别为β₀ ⁱ⁺¹，β₁ ⁱ⁺¹，…，β_k-1 ⁱ⁺¹，此时H₁是一个类范德蒙矩阵，详细描述为：Select k non-zero elements β ₀ , β ₁ ,..., β _k-1 from GF(q) as the scale factors of the k sub-matrices in the 0th row of the matrix H ₁ , and the corresponding k sub-matrices in the i-th row The scale factors are β ₀ ⁱ⁺¹ , β ₁ ⁱ⁺¹ ,..., β _k-1 ⁱ⁺¹ , and H ₁ is a Vandermonde-like matrix at this time, which is described in detail as:

${H h}_{11} = = [\begin{matrix} {β β}_{00} {P P}^{{s the s}_{0,0 0,0}} & {β β}_{11} {P P}^{{s the s}_{0,1 0,1}} & . . & . . & . . & {β β}_{k k - - 11} {P P}^{{s the s}_{00,, k k - - 11}} \\ {β β}_{00}^{22} {P P}^{{s the s}_{1,0 1,0}} & {β β}_{11}^{22} {P P}^{{s the s}_{1,1 1,1}} & . . & . . & . . & {β β}_{k k - - 11}^{22} {P P}^{{s the s}_{11,, k k - - 11}} \\ . . & . . & . . \\ . . & . . & . . & . . & . . & . . \\ . . & . . & . . \\ {β β}_{00}^{m m} {P P}^{{s the s}_{m m - - 1,0 1,0}} & {β β}_{11}^{m m} {P P}^{{s the s}_{m m - - 1,1 1,1}} & . . & . . & . . & {β β}_{k k - - 11}^{m m} {P P}^{{s the s}_{m m - - 11,, k k - - 11}} \end{matrix}] - - - - - - ((1.4 1.4)) . .$

另外，本发明提供了一种多元LDPC码的编码方法，多元LDPC码的编码方法直接通过上述的多元LDPC码的校验矩阵来实现；将码字序列看作长为l的多个子序列的集合，c＝(u ⁽⁰⁾，u ⁽¹⁾，…，u ^(k-1)，v ⁽⁰⁾，v ⁽¹⁾，…，v ^(m-1))，其中u ^(j)(0≤j≤k-1)是长为l的信息子序列，v ⁽ⁱ⁾(0≤i≤m-1)是长为l的校验子序列，编码方法包括以下步骤：In addition, the present invention provides a kind of coding method of multivariate LDPC code, the coding method of multivariate LDPC code realizes directly through the parity check matrix of above-mentioned multivariate LDPC code; The code word sequence is regarded as the set of a plurality of subsequences of length 1 , c = ( u ⁽⁰⁾ , u ⁽¹⁾ , …, u ^(k-1) , v ⁽⁰⁾ , v ⁽¹⁾ , …, v ^(m-1) ), where u ^(j) (0 ≤j≤k-1) is an information subsequence of length l, v ⁽ⁱ⁾ (0≤i≤m-1) is a syndrome subsequence of length l, and the encoding method includes the following steps:

(1)初始化，将长度为kl的信息序列u划分为k个子序列，u＝(u ⁽⁰⁾，u ⁽¹⁾，…，u ^(k-1))；令v ^(-1)＝0；(1) Initialize, divide the information sequence u with length kl into k subsequences, u =( u ⁽⁰⁾ , u ⁽¹⁾ ,..., u ^(k-1) ); let v ^(-1) = 0 ;

(2)对于0≤i≤m-1，按照附图1的流程计算第i个校验子序列v ⁽ⁱ⁾：对于0≤j≤k-1，第j个信息子序列u ^(j)首先被循环右移s_i，j次，然后再乘以尺度因子β_j ⁱ⁺¹，得到一个长度为l的矢量β_j ⁱ⁺¹ u ^(j)h_i，j ^T，其中h_i，j是由(l×l)的单位矩阵循环左移s_i， _j次得到， $h_{i, j} = P^{s_{i, j}}$ ；将第i-1个校验子序列v ^(i-1)循环右移s_i，k+i-1次，然后再乘以尺度因子α，得到一个长度为l的矢量αv^(i-1)h_i，k+i-1 ^T；将之前两步操作得到的所有矢量相加，得到一个长度为l的和矢量；将此和矢量乘以-1，然后再循环左移s_i，k+i次，得到矢量 ${\underset{&OverBar;}{v}}^{(i)} = - (Σ_{j = 0}^{k - 1} β_{j}^{i + 1} {\underset{&OverBar;}{u}}^{(j)} h_{i, j}^{T} + α {\underset{&OverBar;}{v}}^{(i - 1)} h_{i, k + i - 1}^{T}) {(h_{i, k + i}^{T})}^{- 1} .$ (2) For 0≤i≤m-1, calculate the ith syndrome subsequence v ⁽ⁱ⁾ according to the flow of Figure 1: for 0≤j≤k-1, the jth information subsequence u ^(j) First, it is cyclically shifted right s _{i, j} times, and then multiplied by the scale factor β _j ⁱ⁺¹ to obtain a vector β _j ⁱ⁺¹ u ^(j) h _{i, j} ^T with length l, where h _{i, j} is obtained by cyclically shifting left _si, _j times of the identity matrix of (l×l), $h_{i, j} = P^{{the s}_{i, j}}$ ; Move the i-1th syndrome sequence v ^(i-1) cyclically to the right si _{, k+i-1} times, and then multiply it by the scale factor α to obtain a vector αv ^{(i-1 )} h _{i, k+i-1} ^T ; add all the vectors obtained in the previous two steps to get a sum vector with length l; multiply this sum vector by -1, and then move left _{si, k +i} times, get the vector ${\underset{&OverBar;}{v}}^{(i)} = - (Σ_{j = 0}^{k - 1} β_{j}^{i + 1} {\underset{&OverBar;}{u}}^{(j)} h_{i, j}^{T} + α {\underset{&OverBar;}{v}}^{(i - 1)} h_{i, k + i - 1}^{T}) {(h_{i, k + i}^{T})}^{- 1} .$

与现有技术相比，本发明构造出一种多元LDPC码，此码是一种系统码。由于校验矩阵是由尺度分块循环子矩阵构成，因此降低了多元LDPC码的存储空间。在新的构造方法的基础上设计出一种高效快速的编码方法，使多元LDPC码能够很好得在实际中得到应用。Compared with the prior art, the present invention constructs a multivariate LDPC code, which is a systematic code. Since the parity check matrix is composed of scale-block cyclic sub-matrixes, the storage space of the multivariate LDPC code is reduced. On the basis of the new construction method, an efficient and fast encoding method is designed, so that the multivariate LDPC code can be well applied in practice.

附图说明Description of drawings

图1为本发明计算第i个校验子序列的流程图；Fig. 1 is the flow chart of calculating the i-th syndrome sequence in the present invention;

图2为本发明多元LDPC码的BER性能曲线。Fig. 2 is the BER performance curve of the multi-element LDPC code of the present invention.

具体实施方式Detailed ways

实施例1Example 1

设GF(q)是一个具有q个元素的有限域，α是一个本原元。一个码长为N，维数为K的多元LDPC码C可以由一个多元校验矩阵H来描述。该校验矩阵的维数是(M×N)。一个矢量c＝(c₁，c₂，…，c_N-1)是C中的一个码字当且仅当cH^T＝0，其中H^T表示矩阵H的转置，0表示一个长为M的全零向量。Let GF(q) be a finite field with q elements, and α be a primitive element. A multivariate LDPC code C with code length N and dimension K can be described by a multivariate check matrix H. The dimension of the parity check matrix is (M×N). A vector c = (c ₁ , c ₂ ,..., c _N-1 ) is a codeword in C if and only if c H ^T = 0 , where H ^T represents the transpose of matrix H, and 0 represents a length of The all-zero vector of M.

多元LDPC码的构造主要分为两大步：分块矩阵的构造以及非零元素的替换，其包括以下步骤：The construction of the multivariate LDPC code is mainly divided into two steps: the construction of the block matrix and the replacement of non-zero elements, which include the following steps:

其中k＝n-m。where k=n-m.

给定校验矩阵H＝(H₁H₂)及长度为kl的信息序列u＝(u₀，u₁，…，u_kl-1)，其中u_i∈GF(q)，与u对应的码字序列可写为c＝(uv)，v是长为ml的校验序列。码字序列与校验矩阵之间满足关系Given check matrix H=(H ₁ H ₂ ) and information sequence u =(u ₀ ,u ₁ ,…,u _kl-1 ) of length kl, where u _i ∈GF(q), corresponding to u The codeword sequence can be written as c = ( uv ), and v is a check sequence whose length is ml. The relationship between the codeword sequence and check matrix satisfies

(uv)H^T＝0 (1.7)( uv ) H ^T ＝ 0 (1.7)

因此校验序列可被计算为Therefore the check sequence can be calculated as

$\underset{&OverBar; &OverBar;}{v v} = = - - \underset{&OverBar; &OverBar;}{u u} {H h}_{11}^{T T} {(({H h}_{22}^{T T}))}^{- - 11} - - - - - - ((1.8 1.8))$

编码方法的目的就是计算校验序列v。为了方便计算，将码字序列看作是长为l的多个子序列的集合，即c＝(u ⁽⁰⁾，u ⁽¹⁾，…，u ^(k-1)，v ⁽⁰⁾，v ⁽¹⁾，…，v ^(m-1))，其中u ^(j)(0≤j≤k-1)是长为l的信息子序列，v ⁽ⁱ⁾(0≤i≤m-1)是长为l的校验子序列。具体编码算法如下：The purpose of the encoding method is to calculate the check sequence v . For the convenience of calculation, the codeword sequence is regarded as a set of multiple subsequences of length l, namely c = ( u ⁽⁰⁾ , u ⁽¹⁾ ,..., u ^(k-1) , v ⁽⁰⁾ , v ⁽¹⁾ ,..., v ^(m-1) ), where u ^(j) (0≤j≤k-1) is an information subsequence of length l, v ⁽ⁱ⁾ (0≤i≤m-1) is a syndrome sequence of length l. The specific encoding algorithm is as follows:

1.初始化。1. Initialization.

(2)对于0≤i≤m-1，按照附图1的流程计算第i个校验子序列v ⁽ⁱ⁾：对于0≤j≤k-1，第j个信息子序列u ^(j)首先被循环右移s_i，j次，然后再乘以尺度因子β_j ⁱ⁺¹，得到一个长度为l的矢量β_j ^i+1u(j)h_i，j ^T，其中h_i，j是由(l×l)的单位矩阵循环左移s_i，j次得到， $h_{i, j} = P^{s_{i, j}}$ ；将第i-1个校验子序列v ^(i-1)循环右移s_i，k+i-1次，然后再乘以尺度因子α，得到一个长度为l的矢量αv^(i-1)h_i，k+i-1 ^T；将之前两步操作得到的所有矢量相加，得到一个长度为l的和矢量；将此和矢量乘以-1，然后再循环左移s_i，k+i次，得到矢量 ${\underset{&OverBar;}{v}}^{(i)} = - (Σ_{j = 0}^{k - 1} β_{j}^{i + 1} {\underset{&OverBar;}{u}}^{(j)} h_{i, j}^{T} + α {\underset{&OverBar;}{v}}^{(i - 1)} h_{i, k + i - 1}^{T}) {(h_{i, k + i}^{T})}^{- 1} .$ (2) For 0≤i≤m-1, calculate the ith syndrome subsequence v ⁽ⁱ⁾ according to the flow of Figure 1: for 0≤j≤k-1, the jth information subsequence u ^(j) First, it is cyclically shifted right s _{i, j} times, and then multiplied by the scale factor β _j ⁱ⁺¹ to obtain a vector β _j ^{i+1 u (j)} h _{i, j} ^T with length l, where h _{i, j} is obtained by cyclically shifting left _si,j times of the (l×l) identity matrix, $h_{i, j} = P^{{the s}_{i, j}}$ ; Move the i-1th syndrome sequence v ^(i-1) cyclically to the right si _{, k+i-1} times, and then multiply it by the scale factor α to obtain a vector αv ^{(i-1 )} h _{i, k+i-1} ^T ; add all the vectors obtained in the previous two steps to get a sum vector with length l; multiply this sum vector by -1, and then move left _{si, k +i} times, get the vector ${\underset{&OverBar;}{v}}^{(i)} = - (Σ_{j = 0}^{k - 1} β_{j}^{i + 1} {\underset{&OverBar;}{u}}^{(j)} h_{i, j}^{T} + α {\underset{&OverBar;}{v}}^{(i - 1)} h_{i, k + i - 1}^{T}) {(h_{i, k + i}^{T})}^{- 1} .$

复杂性分析，如果给定参数l，a与b，所发明的多元LDPC码可以唯一的由k个域元素β₀，β₁，…，β_k-1来确定，从而解决了多元LDPC码的存储空间问题。Complexity analysis, if the parameters l, a and b are given, the invented multivariate LDPC code can be uniquely determined by k field elements β ₀ , β ₁ ,..., β _k-1 , thus solving the problem of multivariate LDPC code Storage space issue.

从所发明的编码算法中可以看出，计算一个长度为l的校验子序列，仅仅需要(k+1)l次乘法运算以及kl次加法运算。平均意义上说，计算一个校验符号，仅需要k+1次乘法运算及k次加法运算。因此其编码复杂度随着码长的增加而线性增加。It can be seen from the invented encoding algorithm that to calculate a syndrome sequence of length l, only (k+1)l times of multiplication and kl times of addition are needed. On average, to calculate one check symbol, only k+1 multiplication operations and k addition operations are required. Therefore, its encoding complexity increases linearly with the increase of the code length.

应用举例Application examples

一、GF(16)上多元LDPC码1. Multivariate LDPC codes on GF(16)

1.参数设置：1. Parameter setting:

l＝277，a＝48，b＝7；可以验证a的阶m＝3，b的阶n＝12。l=277, a=48, b=7; it can be verified that the order of a is m=3, and the order of b is n=12.

2.非零序列选取：2. Non-zero sequence selection:

(β₀，β₁，…β₈)＝(α²，α⁶，α⁹，α³，α⁷，α¹¹，α⁴，α¹，α¹²)。(β ₀ , β ₁ , . . . β ₈ )=(α ² , α ⁶ , α ⁹ , α ³ , α ⁷ , α ¹¹ , α ⁴ , α ¹ , α ¹² ).

3.对应码参数3. Corresponding code parameters

码长：3324；维数：2493；码率：3/4。Code length: 3324; dimension: 2493; code rate: 3/4.

4.实验仿真4. Experimental simulation

采用16-QAM调制方式及AWGN信道模型。BER曲线及相对应的Shannon限如图2所示。Adopt 16-QAM modulation mode and AWGN channel model. The BER curve and the corresponding Shannon limit are shown in Figure 2.

二、GF(32)上多元LDPC码2. Multivariate LDPC codes on GF(32)

1.参数设置：1. Parameter setting:

l＝211，a＝196，b＝137；可以验证a的阶m＝3，b的阶n＝15。l=211, a=196, b=137; it can be verified that the order of a is m=3, and the order of b is n=15.

2.非零序列选取：2. Non-zero sequence selection:

(β₀，β₁，…β₁₁)＝(α¹，α⁶，α²⁶，α²，α⁷，α¹²，α¹⁷，α²²，α²⁷，α³，α⁸，α¹³)。(β ₀ , β ₁ , . . . β ₁₁ )=(α ¹ , α ⁶ , α ²⁶ , α ² , α ⁷ , α ^{12 , α 17} , α ²² , α ²⁷ ^, α ³ , α ⁸ , α ¹³ ).

3.对应码参数3. Corresponding code parameters

码长：3165；维数：2532；码率：4/5。Code length: 3165; dimension: 2532; code rate: 4/5.

4.实验仿真4. Experimental simulation

采用32-QAM调制方式及AWGN信道模型。BER曲线及相对应的Shannon限如图2所示。Adopt 32-QAM modulation mode and AWGN channel model. The BER curve and the corresponding Shannon limit are shown in Figure 2.

三、GF(64)上多元LDPC码3. Multivariate LDPC codes on GF(64)

1.参数设置：1. Parameter setting:

l＝181，a＝48，b＝119；可以验证a的阶m＝3，b的阶n＝18。l=181, a=48, b=119; it can be verified that the order of a is m=3, and the order of b is n=18.

2.非零序列选取：2. Non-zero sequence selection:

(β₀，β₁，…β₁₄)＝(α¹⁹，α²⁵，α³¹，α³⁷，α⁴³，α⁴⁹，α⁵⁵，α²，α⁸，α¹⁴，α²⁰，α²⁶，α¹，α³⁸，α⁴⁴)。(β ₀ , β ₁ ,...β ₁₄ )=(α ¹⁹ , α ²⁵ , α ³¹ , α ³⁷ , α ⁴³ , α 49 , ^{α 55} ^, α ² , α 8 , α ¹⁴ , ^{α 20} ^, α ²⁶ , α ¹ , α ³⁸ , α ⁴⁴ ).

3.对应码参数3. Corresponding code parameters

码长：3258；维数：2715；码率：5/6。Code length: 3258; dimension: 2715; code rate: 5/6.

4.实验仿真4. Experimental simulation

采用64-QAM调制方式及AWGN信道模型。BER曲线及相对应的Shannon限如图2所示。Adopt 64-QAM modulation mode and AWGN channel model. The BER curve and the corresponding Shannon limit are shown in Figure 2.

实施例2Example 2

本实施例以二元基矩阵的构造以及非零元素的替换来说明多元LDPC码的构造方法。In this embodiment, the method of constructing a multivariate LDPC code is described by constructing a binary basis matrix and replacing non-zero elements.

1)二元基矩阵的构造1) Construction of binary basis matrix

对任意正整数l，将所有小于l且与其互素的那些正整数构成集合Z_l ^*，这些正整数在模l乘法运算下构成一个乘法群。Tanner在2001年发表的文章“LDPCBlock and Convolutional Codes Based on Circulant Matrices”中指出：若Z_l ^*中存在两个元素a，b，且有a的阶为m，b的阶为n，则可以构造如下二元矩阵H^(b) For any positive integer l, form a set Z _l ^* of all positive integers smaller than l and relatively prime to it, and these positive integers form a multiplicative group under the modulo l multiplication operation. Tanner pointed out in the article "LDPCBlock and Convolutional Codes Based on Circulant Matrices" published in 2001: If there are two elements a and b in Z _l ^* , and the order of a is m, and the order of b is n, then it can be constructed The following binary matrix H ^(b)

${H h}^{((b b))} = = [\begin{matrix} {h h}_{0,0 0,0} & {h h}_{0,1 0,1} & . . & . . & . . & {h h}_{00,, n no - - 11} \\ {h h}_{1,0 1,0} & {h h}_{1,1 1,1} & . . & . . & . . & {h h}_{11,, n no - - 11} \\ . . & . . & . . \\ . . & . . & . . & . . & . . & . . \\ . . & . . & . . \\ {h h}_{m m - - 1,0 1,0} & {h h}_{m m - - 11,, 11} & . . & . . & . . & {h h}_{m m - - 11,, n no - - 11} \end{matrix}] - - - - - - ((1.1 1.1)),,$

其中h_i，j是一个(l×l)的子矩阵，它是由单位阵循环右移s_i，j＝aⁱb^j次得到。。Where h _i,j is a (l×l) sub-matrix, which is obtained by cyclically shifting the identity matrix s _i,j =a ⁱ b ^j times. .

所得到的二元矩阵H^(b)是一个(ml×nl)的稀疏矩阵，其中非零元素的个数为mnl。此二元矩阵可以写为左右两部分 $H^{(b)} = (\begin{matrix} H_{1}^{(b)} & H_{2}^{(b)} \end{matrix}),$ 其中H₂ ^(b)是由H^(b)中(m×m)个子矩阵构成，H₁ ^(b)是由H^(b)中剩下的子矩阵构成。删除矩阵H₂ ^(b)中的一些元素，使其为分块双对角矩阵，如(1.2)所示。The resulting binary matrix H ^(b) is a (ml×nl) sparse matrix, where the number of non-zero elements is mnl. This binary matrix can be written as left and right parts $h^{(b)} = (\begin{matrix} h_{1}^{(b)} & h_{2}^{(b)} \end{matrix}),$ Wherein H ₂ ^(b) is composed of (m×m) sub-matrices in H ^(b) , and H ₁ ^(b) is composed of the remaining sub-matrices in H ^(b) . Delete some elements in the matrix H ₂ ^(b) to make it a block bidiagonal matrix, as shown in (1.2).

${\overset{~ ~}{H h}}_{22}^{((b b))} = = [\begin{matrix} {h h}_{00,, k k} & 00 & 00 & 00 & . . & . . & . . & 00 & 00 & 00 \\ {h h}_{11,, k k} & {h h}_{11,, k k + + 11} & 00 & 00 & . . & . . & . . & 00 & 00 & 00 \\ 00 & {h h}_{22,, k k + + 11} & {h h}_{22,, k k + + 22} & 00 & . . & . . & . . & 00 & 00 & 00 \\ . . & . . & . . & . . & . . & . . & . . \\ . . & . . & . . & . . & . . & . . & . . & . . & . . & . . \\ . . & . . & . . & . . & . . & . . & . . \\ 00 & 00 & 00 & 00 & . . & . . & . . & {h h}_{m m - - 22,, n no - - 33} & {h h}_{m m - - 22,, n no - - 22} & 00 \\ 00 & 00 & 00 & 00 & . . & . . & . . & 00 & {h h}_{m m - - 11,, n no - - 22} & {h h}_{m m - - 11,, n no - - 11} \end{matrix}] - - - - - - ((11 . . 22))$

其中k＝n-m。where k=n-m.

矩阵 ${\tilde{H}}^{(b)} = (\begin{matrix} H_{1}^{(b)} & {\tilde{H}}_{2}^{(b)} \end{matrix})$ 是构造多元LDPC码的基矩阵。matrix ${\tilde{h}}^{(b)} = (\begin{matrix} h_{1}^{(b)} & {\tilde{h}}_{2}^{(b)} \end{matrix})$ is the basis matrix for constructing multivariate LDPC codes.

2)非零元素的替换2) Replacement of non-zero elements

为了构造多元LDPC码，我们要把二元基矩阵 ${\tilde{H}}^{(b)} = (\begin{matrix} H_{1}^{(b)} & {\tilde{H}}_{2}^{(b)} \end{matrix})$ 中的“1”用有限域GF(q)中的元素替代。为了节约存储空间，我们的替换原则是：每一个分块子矩阵h_i，j中的非零元素被同一个域元素β_i，j ∈GF(q)替代，即将二元基矩阵中的分块子矩阵h_i，j变为尺度分块子矩阵β_i，jh_i，j，其中β_i，j称为尺度因子。In order to construct a multivariate LDPC code, we need the binary basis matrix ${\tilde{h}}^{(b)} = (\begin{matrix} h_{1}^{(b)} & {\tilde{h}}_{2}^{(b)} \end{matrix})$ The "1" in is replaced by elements in the finite field GF(q). In order to save storage space, our replacement principle is: the non-zero elements in each block sub-matrix h _{i, j} are replaced by the same field element β _{i, j} ∈ GF(q), that is, the partitions in the binary basis matrix The block sub-matrix h _i,j becomes a scaled block sub-matrix β _i,j hi _,j , where β _i,j is called the scale factor.

子矩阵中非零元素的替换规则是：主对角线上的分块子矩阵的尺度因子为1；次对角线上的分块子矩阵的尺度因子为α(α是GF(q)的本原元)，即submatrix The replacement rule for non-zero elements in is: the scale factor of the block sub-matrix on the main diagonal is 1; the scale factor of the block sub-matrix on the sub-diagonal is α (α is the primitive of GF(q) Yuan), that is

${H h}_{22} = = [\begin{matrix} {h h}_{00,, k k} & 00 & 00 & 00 & . . & . . & . . & 00 & 00 & 00 \\ {αh α h}_{11,, k k} & {h h}_{11,, k k + + 11} & 00 & 00 & . . & . . & . . & 00 & 00 & 00 \\ 00 & {αh αh}_{22,, k k + + 11} & {h h}_{22,, k k + + 22} & 00 & . . & . . & . . & 00 & 00 & 00 \\ . . & . . & . . & . . & . . & . . & . . \\ . . & . . & . . & . . & . . & . . & . . & . . & . . & . . \\ . . & . . & . . & . . & . . & . . & . . \\ 00 & 00 & 00 & 00 & . . & . . & . . & {αh αh}_{m m - - 22,, n no - - 33} & {h h}_{m m - - 22,, n no - - 22} & 00 \\ 00 & 00 & 00 & 00 & . . & . . & . . & 00 & {αh αh}_{m m - - 11,, n no - - 22} & {h h}_{m m - - 11,, n no - - 11} \end{matrix}] - - - - - - ((11 . . 44))$

子矩阵H₁ ^(b)中非零元素的替换规则是：根据一定的优化准则(比如最大熵准则)，从GF(q)中选取k个非零元素β₀，β₁，…，β_k-1作为H₁ ^(b)中第0行的k个分块子矩阵的尺度因子；对于H₁ ^(b)中第i行的k个分块子矩阵，其尺度因子分别为β₀ ⁱ⁺¹，β₁ ⁱ⁺¹，…，β_k-1 ⁱ⁺¹，即The replacement rule of the non-zero elements in the sub-matrix H ₁ ^(b) is: according to a certain optimization criterion (such as the maximum entropy criterion), select k non-zero elements β ₀ , β ₁ , ..., β _k from GF(q) _-1 is used as the scale factor of the k block sub-matrices in row 0 in H ₁ ^(b) ; for the k block sub-matrices in row i in H ₁ ^(b) , the scale factors are β ₀ ^{i+ 1} , β ₁ ⁱ⁺¹ ,…, β _k-1 ⁱ⁺¹ , namely

${H h}_{11} = = [\begin{matrix} {β β}_{00} {h h}_{0,0 0,0} & {β β}_{11} {h h}_{0,1 0,1} & . . & . . & . . & {β β}_{k k - - 11} {h h}_{00,, k k - - 11} \\ {β β}_{00}^{22} {h h}_{1,0 1,0} & {β β}_{11}^{22} {h h}_{1,1 1,1} & . . & . . & . . & {β β}_{k k - - 11}^{22} {h h}_{11,, k k - - 11} \\ . . & . . & . . \\ . . & . . & . . & . . & . . & . . \\ . . & . . & . . \\ {β β}_{00}^{m m} {h h}_{m m - - 1,0 1,0} & {β β}_{11}^{m m} {h h}_{m m - - 1,1 1,1} & . . & . . & . . & {β β}_{k k - - 11}^{m m} {h h}_{m m - - 11,, k k - - 11} \end{matrix}] - - - - - - ((1.5 1.5))$

经过上述操作，与多元LDPC码对应的校验矩阵H可以表示为After the above operations, the parity check matrix H corresponding to the multivariate LDPC code can be expressed as

H＝(H₁H₂) (1.6)H=(H ₁ H ₂ ) (1.6)

由校验矩阵H描述的多元LDPC码是一种系统码，其码长N＝nl，维数K＝kl，码率r＝k/n。The multivariate LDPC code described by the parity check matrix H is a systematic code, whose code length is N=nl, dimension K=kl, code rate r=k/n.

Claims

1. the building method of a multielement LDPC code is characterized in that may further comprise the steps:

A. the check matrix H of multielement LDPC code is the matrix in block form on the finite field gf (q) with q element, is made of m * n submatrix; Be positioned at the capable submatrix H with j row crossover location of the i of check matrix H _{I, j}Be by scale factor β _{I, j}After ∈ GF (q) multiply by the unit matrix of a l * l, press row ring shift left s again _{I, j}Inferior obtaining, 0≤i≤m-1 wherein, 0≤j≤n-1,0≤s _{I, j}≤ l-1;

B. the check matrix of multielement LDPC code is adjusted in proper order through row and be divided into left and right sides two parts: H=(H ₁H ₂), H wherein ₂Be made of m * m submatrix, a corresponding m length is the syndrome sequence of l, and H ₁Be made of submatrix remaining in the check matrix H, a corresponding n-m length is the information subsequence of l;

C. the matrix H of corresponding syndrome sequence in the check matrix H with multielement LDPC code ₂Through the space order piecemeal biconjugate angular moment battle array that to be adjusted into a size be m * m,

H_{2} = [\begin{matrix} H_{0, k} & 0 & 0 & 0 & . . . & 0 & 0 & 0 \\ H_{1, k} & H_{1, k + 1} & 0 & 0 & . . . & 0 & 0 & 0 \\ 0 & H_{2, k + 1} & H_{2, k + 2} & 0 & . . . & 0 & 0 & 0 \\ . & . & . & . & . & . & . \\ . & . & . & . & . . . & . & . & . \\ . & . & . & . & . & . & . \\ 0 & 0 & 0 & 0 & . . . & H_{m - 2, n - 3} & H_{m - 2, n - 2} & 0 \\ 0 & 0 & 0 & 0 & . . . & 0 & H_{m - 1, n - 2} & H_{m - 1, n - 1} \end{matrix}] - - - (1.1),

K=n-m wherein.

2. the building method of multielement LDPC code according to claim 1 is characterized in that: in step a, and piecemeal submatrix H _{I, j}Be a yardstick circular matrix,

H_{i, j} = β_{i, j} P^{s_{i, j}} - - - (1.2),

Wherein P is the matrix that the unit matrix ring shift left by l * l obtains for 1 time.

3. the building method of multielement LDPC code according to claim 2 is characterized in that: matrix H ₂In, the scale factor of the submatrix on the leading diagonal is 1, and the scale factor of the submatrix on the minor diagonal is α, and wherein α is the primitive element of GF (q), at this moment H ₂Be specifically described as:

H_{2} = [\begin{matrix} P^{s_{0, k}} & 0 & 0 & 0 & . . . & 0 & 0 & 0 \\ α P^{s_{1, k}} & P^{s_{1, k + 1}} & 0 & 0 & . . . & 0 & 0 & 0 \\ 0 & α P^{s_{2, k + 1}} & P^{s_{2, k + 2}} & 0 & . . . & 0 & 0 & 0 \\ . & . & . & . & . & . & . \\ . & . & . & . & . . . & . & . & . \\ . & . & . & . & . & . & . \\ 0 & 0 & 0 & 0 & . . . & α P^{s_{m - 2, n - 3}} & P^{s_{m - 2, n - 2}} & 0 \\ 0 & 0 & 0 & 0 & . . . & 0 & α P^{s_{m - 1, n - 2}} & P^{s_{m - 1, n - 1}} \end{matrix}] - - - (1.3) .

4. the building method of multielement LDPC code according to claim 2 is characterized in that: choose k nonzero element β from GF (q) ₀, β ₁..., β _K-1As matrix H ₁In the scale factor of k submatrix of the 0th row, the scale factor of k the submatrix that corresponding i is capable is respectively β ₀ ^I+1, β ₁ ^I+1..., β _K-1 ^I+1, this moment H ₁Be a class Fan Demeng matrix, be specifically described as:

H_{1} = [\begin{matrix} β_{0} P^{s_{0,0}} & β_{1} P^{s_{0,1}} & . . . & β_{k - 1} P^{s_{0, k - 1}} \\ β_{0}^{2} P^{s_{1,0}} & β_{1}^{2} P^{s_{1,1}} & . . . & β_{k - 1}^{2} P^{s_{1, k - 1}} \\ . & . & . \\ . & . & . . . & . \\ . & . & . \\ β_{0}^{m} P^{s_{m - 1,0}} & β_{1}^{m} P^{s_{m - 1,1}} & . . . & β_{k - 1}^{m} P^{s_{m - 1, k - 1}} \end{matrix}] - - - (1.4) .

5. the coding method of a multielement LDPC code is characterized in that: the coding method of multielement LDPC code directly realizes by the check matrix of the described multielement LDPC code of claim 1; Regard codeword sequence the set of length as for a plurality of subsequences of l, c=( u ⁽⁰⁾, u ⁽¹⁾..., u ^(k-1), v ⁽⁰⁾, v ⁽¹⁾..., v ^(m-1)), wherein u ^(j)Be the long information subsequence of l that is, 0≤j≤k-1 wherein, v ⁽ⁱ⁾Be the long syndrome sequence of l that is, 0≤i≤m-1 wherein, coding method may further comprise the steps:

(1) initialization is the information sequence of kl with length uBe divided into k subsequence, u=( u ⁽⁰⁾, u ⁽¹⁾..., u ^(k-1)); Order v ⁽¹⁾= 0

(2), calculate i syndrome sequence for 0≤i≤m-1 v ⁽ⁱ⁾: for 0≤j≤k-1, j information subsequence u ^(j)At first be recycled the s that moves to right _{I, j}Inferior, and then multiply by scale factor β _j ^I+1, the vector beta that to obtain a length be l _j ^I+1 u ^(j)h _{I, j} ^T, h wherein _{I, j}Be unit matrix ring shift left s by l * l _{I, j}Inferior obtaining, With i-1 syndrome sequence v ^(i-1)Ring shift right s _{I, k+i-1}The vector inferior, and then multiply by scale factor α, that to obtain a length be l v ^(i-1)h _{I, k+i-1} ^TWith all vector additions that the operation of its first two steps obtains, obtain a length and be l's and vector; This and vector be multiply by-1, and then ring shift left s _{I, k+i}Inferior, obtain vector

{\underset{&OverBar;}{v}}^{(i)} = - (Σ_{j = 0}^{k - 1} β_{j}^{i + 1} {\underset{&OverBar;}{u}}^{(j)} h_{i, j}^{T} + α {\underset{&OverBar;}{v}}^{(i - 1)} h_{i, k + i - 1}^{T}) {(h_{i, k + i}^{T})}^{- 1} .