CN109951189B - Quasi-cyclic structure multi-element LDPC code construction method based on prime number product - Google Patents

Abstract

The invention discloses a construction method of a quasi-cyclic structure multi-element LDPC code based on prime number product, which comprises the steps of selecting two groups of nonnegative integers and a binary matrix through a given finite field and prime number, then constructing a cyclic permutation matrix, a second matrix and a third matrix according to the selected two groups of nonnegative integers and the binary matrix, and replacing partial data of the third matrix to obtain a check matrix of the multi-element LDPC code; by setting different parameters, the method can be used for constructing various structured multi-element LDPC codes; compared with a structured multi-element LDPC code method based on an algebraic structure, the method has the advantages of high construction flexibility, low implementation complexity, low storage complexity and the like; compared with the multi-element LDPC code constructed randomly, the multi-element LDPC code constructed by the invention is a structured multi-element LDPC code, so that the hardware implementation complexity is lower.

Description

A Construction Method of Quasi-Cyclic Multivariate LDPC Codes Based on Prime Number Product

technical field

The invention relates to the research field of digital communication and digital storage, in particular to a method for constructing a quasi-circular structure multivariate LDPC code based on the product of prime numbers.

Background technique

In recent years, new wireless communication scenarios represented by automation engineering and Internet of Vehicles have emerged, which pose challenges to the delay and reliability of existing communication systems. In order to meet the delay and reliability requirements of new applications, the physical layer must be equipped with highly reliable channel coding technology for short data packets. Currently available channel coding techniques for short-packet communication include tail-biting convolutional codes, polar codes, and multivariate low-density check codes. Compared with tail-biting convolutional codes and convolutional codes, multivariate LDPC codes have a lower error floor. At the same time, the multivariate LDPC codec has a higher degree of parallelism. Therefore, multivariate low-density check codes are more suitable for high-reliability communication oriented to short data packets.

Gallager first proposed multivariate low-density check codes, namely multivariate LDPC codes, in the 1960s. The research boom of multivariate LDPC codes began at the end of last century. There are two main types of construction methods for existing multivariate LDPC codes: random construction methods based on progressive edge growth algorithm and algebraic construction methods based on finite fields and other structures. The random construction method can construct multi-element LDPC codes with any code length and any code rate. Algebraic construction methods can be used to construct structured multivariate LDPC codes, but the codes that can be constructed by algebraic methods are severely limited. Based on algebraic structures such as finite fields, rate-compatible multivariate LDPC codes can be constructed, which is a structured method for constructing multivariate rate-compatible LDPC codes. However, this method is limited by the characteristics of algebraic structures.

Randomly constructed multivariate LDPC codes have poor structure, high hardware implementation complexity, and impracticality. Algebraic construction methods are less flexible. Due to the existence of a large number of variable nodes with low degrees, the error floor of multivariate LDPC codes based on RA structure is relatively high. In addition, RA-based multivariate LDPC codes are generally irregular.

Contents of the invention

The purpose of the present invention is to overcome the shortcomings and deficiencies of the prior art, and provide a structured multivariate LDPC code construction method based on the product of prime numbers. The method has the advantages of high structural flexibility and simple construction process. be at least 6 long. On the one hand, compared with the random construction method based on progressive edge growth and the construction method based on RA, the multivariate LDPC code constructed by the present invention has a regular structure, which is convenient for hardware implementation. On the other hand, compared with the existing structured multivariate LDPC codes, the construction method proposed by the present invention is not based on any algebraic structure, so the flexibility is higher.

The purpose of the present invention is achieved through the following technical solutions:

A method for constructing a quasi-cyclic structure multivariate LDPC code based on the product of prime numbers, comprising the following steps:

Given a finite field F _q , where q=2 ^m , 1≤m; select s prime numbers p ₁ , p ₂ ,…,p _s , where s≥2; select λ and ρ, where 2≤λ≤ ρ≤p ₁ ; given λ non-negative integers r ₀ , r ₁ ,…,r _λ-1 and ρ non-negative integers c ₀ , c ₁ ,…,c _ρ-1 ; given a binary matrix M , whose elements can only take values of "0" or "1";

For generating a row vector e _{i,j,0 of} length p, where, p=p ₁ ×p ₂ ×…×p _s , i=0,1,…,λ-1 and j=0,1,…, ρ-1, counting from 0, the row vector e _i,j, the value of the f(i,j)th component of 0 is M _i,j , and the value of other components is "0", where f(i ,j)=r _i ×c _j , M _i,j represents the elements of the i-th row and j-th column of the matrix M;

The 0th component of the row vector e _i,j,k is the p-1th component of the row vector e _i,j,k-1 , where k=1,2,...,p-1, and the row vector e _i The sth component of _,j,k is the s-1th component of the row vector e _i,j,k-1 , where s=1,2,...,p-1;

Construct a circular permutation matrix of dimension p×p:

Wherein, i=0,1,...,λ-1, j=0,1,...,ρ-1, p is the length of the row vector;

Construct a matrix of dimension p×ρp:

Wherein, ρ represents the number of the first matrix that comprises in the second matrix Λ _i ;

Based on the matrix Λ ₁ , Λ ₂ ,…,Λ _λ-1 , generate a matrix with dimension λp×ρp:

Wherein, λ represents the number of the second matrix contained in the third matrix Λ;

Replace the "1" in the matrix Λ with the non-zero elements in the finite field F _q to obtain the parity check matrix H whose dimension is λp×ρp of the multivariate LDPC code, and the null space of the parity check matrix H defines a finite field F _q multivariate LDPC codes.

Further, the replacement, the replacement process is carried out in the following three ways:

For each "1" of the matrix Λ, a non-zero element of a finite field is randomly generated for replacement;

For all "1" in the matrix Λ _i,j, the non-zero elements of the same randomly generated finite field are used to replace;

For all "1" in the same column of the matrix Λ, the non-zero elements of the same randomly generated finite field are used to replace;

Further, the prime number satisfies 3≤p ₁ ≤p ₂ ≤... _≤ps ;

Further, the prime number, the product of all prime numbers is: p=p ₁ ×p ₂ ×...×p _s ;

Further, the λ is a positive integer and satisfies 2≤λ≤p ₁ ; the ρ is a positive integer and satisfies λ≤ρ≤p;

Further, the non-negative integers r ₀ , r ₁ ,...,r _λ-1 satisfy 0≤r ₀ <r ₁ <...<r _λ-1 <p ₁ ;

Further, the non-negative integers c ₀ , c ₁ ,...,c _ρ-1 satisfy 0≤c ₀ <c ₁ <...<c _ρ-1 <p;

Further, the binary matrix M, M is any binary matrix with a dimension of λ×ρ;

Further, the f(i,j), f(i,j) is f(i,j)=r _i ×c _j .

Compared with the prior art, the present invention has the following advantages and beneficial effects:

A kind of quasi-cyclic structure multivariate LDPC code construction method based on the product of prime numbers proposed by the present invention has the advantages of simple construction process and flexible parameters, and the ring length of the obtained multivariate LDPC code is longer; compared with the construction method based on algebraic structure, The multivariate LDPC code constructed by the present invention has lower hardware implementation complexity.

Description of drawings

Fig. 1 is a method flowchart of a kind of quasi-cyclic structure multivariate LDPC code construction method based on prime number product of the present invention;

FIG. 2 is a graph showing the BER performance of the 8-element multivariate LDPC code based on the product of prime numbers in the embodiment of the present invention on the BPSK-AWGN channel.

Detailed ways

The present invention will be further described in detail below in conjunction with the embodiments and the accompanying drawings, but the embodiments of the present invention are not limited thereto.

Example:

A kind of quasi-cyclic structure multivariate LDPC code construction method based on prime number product, as shown in Figure 1, comprises the following steps:

Set the finite field to F ₈ . Select s=2, p ₁ =5, p ₂ =7, then p=5×7=35. Set λ=4, ρ=35. For i=0,1,2,3, set r _i =i. For i=0,1,...,34, set c _i =i. Set matrix M to be a 4×35 matrix of all 1s.

Step 1: For i=0,1,2,3 and j=0,1,...,34, generate a row vector e _i,j,0 with a length of 35, the i-th × of the row vector e _i,j,0 The value of the j component is 1, and the value of other components is "0"; for k=1,2,...,34, the 0th component of the row vector e _i,j,k is the row vector e _{i,j , the 34th component of k-1} , and the s-th component of row vector e _i,j,k is the s-1th component of row vector e _i,j,k-1 , where s=1,2, ...,63;

Step 2: For i=0,1,2,3 and j=0,1,...,34, construct a cyclic permutation matrix with a dimension of 35×35:

in,

和/>

Construct a matrix with dimensions 35×1225

and />

Step 3: Based on Λ ₁ , Λ ₂ , Λ ₃ , Λ ₄ , construct a matrix with a dimension of 140×1225:

in,

Step 4: For each non-zero element "1" in the matrix Λ, randomly generate a non-zero finite field element in the finite field F ₈ and replace the current "1" with this finite field element. After the above replacement process, the parity check matrix H of the multivariate LDPC code C ₈ [1225,1085] can be obtained.

The following simulation environments are all AWGN channels, and the modulation is BPSK modulation. The selected decoding algorithms include Q-element sum-product algorithm and weighted bit reliability algorithm. The maximum number of iterations for all simulations is 50.

The simulation results are shown in Figure 2; where QSPA represents the Q element sum product algorithm, wBRB algorithm represents the weighted bit reliability algorithm, C _{8, peg} [1225,1085] represents the code length based on the progressive edge growth algorithm (PEG algorithm) is 1225, An 8-element LDPC code with a message length of 1085. It can be seen from Figure 2 that the multivariate LDPC code constructed based on the product of prime numbers has good error correction performance. When the bit error rate is 10 ^-5 , the performance of the multivariate LDPC code constructed based on the product of prime numbers and the equal-length and equal code rate multivariate LDPC code C _8,peg [1225,1085] constructed by the progressive edge growth algorithm (PEG algorithm) is comparable .

The above-mentioned embodiment is a preferred embodiment of the present invention, but the embodiment of the present invention is not limited by the above-mentioned embodiment, and any other changes, modifications, substitutions, combinations, Simplifications should be equivalent replacement methods, and all are included in the protection scope of the present invention.

Claims (7)

1. a kind of quasi-cyclic structure multivariate LDPC code construction method based on prime number product is characterized in that, comprises the following steps: S1. Given a finite field F _q , where q=2 ^m , 1≤m; select s prime numbers p ₁ , p ₂ ,…,p _s , where s≥2; select λ and ρ, where 2≤ λ≤ρ≤p ₁ ; given λ non-negative integers r ₀ , r ₁ ,…,r _λ-1 and ρ non-negative integers c ₀ , c ₁ ,…,c _ρ-1 ; given a binary Matrix M, the value of its elements can only be "0" or "1"; For generating a row vector e _{i,j,0 of} length p, where, p=p ₁ ×p ₂ ×…×p _s , i=0,1,…,λ-1 and j=0,1,…, ρ-1, counting from 0, the row vector e _i,j, the value of the f(i,j)th component of 0 is M _i,j , and the value of other components is "0", where f(i ,j)=r _i ×c _j , M _i,j represent the elements of the i-th row and j-th column of the binary matrix M; The 0th component of the row vector e _i,j,k is the p-1th component of the row vector e _i,j,k-1 , where k=1,2,...,p-1, and the row vector e _i The sth component of _,j,k is the s-1th component of the row vector e _i,j,k-1 , where s=1,2,...,p-1; S2. Construct the first matrix of the quasi-cyclic structure whose dimension is p×p:

Wherein, i=0,1,...,λ-1, j=0,1,...,ρ-1, p is the length of the row vector; S3. Construct the second matrix of the quasi-circular structure whose dimension is p×ρp: Λ _i = [Λ _i,0 Λ _i,1 ...Λ _i,ρ-1 ”; Wherein, ρ represents the number of the first matrix that comprises in the second matrix Λ _i ; S4. Based on the second matrix Λ ₁ , Λ ₂ ,..., Λ _λ-1 , generate a quasi-circular third matrix with a dimension of λp×ρp:

Wherein, λ represents the number of the second matrix contained in the third matrix Λ; S5, "1" in the third matrix Λ is replaced by non-zero elements in the finite field F _q , and the dimension of the multivariate LDPC code is obtained as a parity check matrix H of λp × ρp, and the null space of the parity check matrix H defines a finite Multivariate LDPC codes over the field F _q . 2. a kind of quasi-cyclic structure multivariate LDPC code construction method based on the product of prime numbers according to claim 1, is characterized in that, described replacement, replacement process is carried out according to following three kinds of modes: For each "1" of the third matrix Λ, a non-zero element of a finite field is randomly generated for replacement; For all "1" in the third matrix Λ, the non-zero elements of the same randomly generated finite field are used to replace; All "1"s in the same column of the third matrix Λ are replaced by the same randomly generated non-zero elements of the finite field. 3 . The method for constructing a quasi-cyclic structure multivariate LDPC code based on the product of prime numbers according to claim 1 , wherein the prime numbers satisfy 3≤p ₁ ≤p ₂ ≤... _≤ps . 4. a kind of quasi-cyclic structure multivariate LDPC code construction method based on the product of prime numbers according to claim 1, is characterized in that, described λ is a positive integer, and satisfies 2≤λ≤p ₁ ; Described ρ is a positive integer , satisfying λ≤ρ≤p. 5. A kind of quasi-cyclic structure multivariate LDPC code construction method based on the product of prime numbers according to claim 1, characterized in that, the non-negative integers r ₀ , r ₁ ,..., r _λ-1 satisfy 0≤r ₀ <r ₁ <...<r _λ-1 <p ₁ . 6. A method for constructing a quasi-cyclic structure multivariate LDPC code based on the product of prime numbers according to claim 1, wherein the non-negative integers c ₀ , c ₁ ,..., c _ρ-1 satisfy 0≤c ₀ <c ₁ <...<c _ρ-1 <p. 7. a kind of quasi-cyclic structure multivariate LDPC code construction method based on the product of prime numbers according to claim 1, is characterized in that, described binary matrix M, M is the arbitrary binary matrix that dimension is λ * ρ.

Images