CN104617959B - A LDPC Coding and Decoding Method Based on General Processor - Google Patents

Abstract

The present application discloses an LDPC encoding method, which determines the vectors p ₁ and p ₂ and obtains the encoding result vector; when determining the vectors p ₁ and p ₂ , the multiplication process between any matrix and any vector includes: Each row is used as a thread to multiply the corresponding row of the matrix with any vector, and the multiplication results of all rows form a result vector; the multiplication operation of each row of any matrix with any vector includes: determining the matrix The starting position of the vector corresponding to each element j of row i, the data of the length Z-A _i,j in any vector from the starting position is left-shifted by means of single instruction multiple data flow, and the starting position is shifted to the left After moving the data of length A _{i, j} from the start position to the left-shifted data, the vector shift result corresponding to element j is obtained; then add the vector shift results of each element. By the method described above, it is possible to increase the encoding speed in a general-purpose processor by utilizing multi-threading and SIMD processing.

Description

A LDPC Coding and Decoding Method Based on General Processor

technical field

The present application relates to LDPC encoding and decoding technology, in particular to an LDPC encoding and decoding method based on a general-purpose processor.

Background technique

LDPC code is a linear block code with a large code length. The check matrix is also relatively large, and there are very few non-zero elements in the check matrix, that is, the number of "1" is very small, so it is called low density.

In the process of implementing the IEEE 802.11n wireless LAN transmission protocol, LDPC coding and decoding technology is required. According to the protocol requirements, the generation process of LDPC PPDU (Presentation Protocol Data Unit, presentation layer protocol data unit) is as follows, see Figure 1:

(1) Calculate the shortened bits

(1a) Calculate the number of available bits N _avbits , the formula is:

N _pld = length × 8 + 16,

Among them, if there is STBC (Space-time block code) precoding, the flag bit m _STBC is 2, otherwise it is 1; N _CBPS indicates the number of coded bits per symbol; length indicates the number of bytes of PSDU (presentation Service DataUnit) , which is the number of bytes of information bits; N _pld represents the total number of bits of PSDU and SERVICE FIELD; R represents the coding rate.

(1b) Calculate the number of LDPC codewords N _CW and the code length L _LDPC

When N _{avbits ≤} 648, the number of code words N _CW is 1, and if N _{avbits ≥} N _pld +912×(1-R), the code length L _LDPC is 1296, otherwise the code length L _LDPC is 648; when 648 When <N _avbits ≤1296, the number of code words N _CW is 1, and if N _avbits ≥N _pld +1464×(1-R), the code length L _LDPC is 1944, otherwise the code length L _LDPC is 1296; when 1296 When <N _avbits ≤1944, the number of codewords N _CW is 1, and the code length L _LDPC is 1944; when 1944<N _avbits ≤2592, the number of codewords N _CW is 2, and if N _avbits ≥N _pld When +2916×(1-R), the code length L _LDPC is 1944, otherwise the code length L _LDPC is 1296; when N _avbits >2592, the number of code words N _CW is At this time, the code length L _LDPC is 1944;

(1c) Calculate the number of shortened bits N _shrt , the shortened bits are filled after the information bits before LDPC encoding:

N _shrt ＝max(0,(N _CW ×L _LDPC ×R)-N _pld )

When N _shrt =0, no 0 complement operation is performed. When N _shrt > 0, the shortened bits are evenly distributed on all N _CW codewords, that is, the number of shortened bits allocated to each codeword is If N _shrt mod N _CW ≠ 0, where mod is the remainder, that is, N _shrt takes the remainder of N _CW , then the first codeword has one more shortened bit than the other codewords.

(2) Perform LDPC encoding to obtain check bits.

(3) Discard the shortened bits

(4) Calculate the number of punched bits and discard the punched bits, calculate the number of punched bits N _punc after LDPC encoding according to the following formula:

N _punc ＝max(0,(N _CW ×L _LDPC )-N _avbits- N _shrt )

if Or (N _punc >0.3×N _CW ×L _LDPC ×(1-R)), increase N _avbits and recalculate N _punc according to the following formula:

N' _avbits =N _avbits +N _CBPS ×m _STBC , N _punc =max(0,(N _CW ×L _LDPC )-N' _avbits -N _shrt )

The punctured bits are evenly distributed on all N _CW codewords, that is, the number of punctured bits allocated to each codeword is If N _punc mod N _CW ≠ 0, where mod is the remainder, that is, N _punc takes the remainder of N _CW , then the first codeword has one more punctured bit than other codewords.

(5) Calculate the repeated bits, calculate the number of repeated bits N _rep according to the following formula:

N _rep ＝max(0,N' _avbits -N _CW ×L _LDPC ×(1-R)-N _pld )

The repeated bits are evenly distributed on all N _CW codewords, that is, the number of repeated bits allocated to each codeword is If N _rep mod N _CW ≠ 0, where mod is the remainder, that is, N _rep takes the remainder of N _CW , then the first codeword has one more repetition bit than other codewords. The repetition bits are sequentially selected from the first bit of the information bits until the length requirement is satisfied, and the repetition bits are copied from the codeword after the shortened bits are removed. The selected repetition bits are sequentially connected after the parity bits. When puncturing is required, check bits need not be repeated, and vice versa.

In the process of LDPC PPDU generation, the LDPC encoding method is the most important. The code word vector output after LDPC encoding is denoted as c=(S,p ₁ ,p ₂ ), where S is the information vector, p ₁ and p ₂ are the code words Check vector, but because the check matrix H of the LDPC code is relatively large, the operation in the encoding process will be very cumbersome. Observing the parity check matrix given in the protocol, it can be seen that the row weight of the matrix under different code rates R is 24, and the column weight is 24×(1-R). According to the characteristics of the parity check matrix H, its Do the following block It is divided into six sub-matrices: matrix A, matrix B, matrix D, matrix E, matrix T and matrix F, among which the structure of matrix B, matrix D, matrix E and matrix T is relatively special, B=(1--...0-...) ^T , D=(1), E=(-...-0), The structures of matrix A and matrix F are irregular, see protocol 802.11n. In addition, due to the large scale of the check matrix H, when representing the check matrix, one element represents a sub-matrix in the actual check matrix, specifically, the check matrix H and the block matrix A, B, In the expression methods of D, E, T, and F, "—" indicates that the sub-matrix is a zero matrix, "0" indicates that the sub-matrix is an identity matrix, and "constant C" indicates that the sub-matrix is an identity matrix. The resulting matrix after bit. The dimension of the sub-matrix is Z*Z, and Z can be determined in advance according to the code length. Through the above method, the representation size of the parity check matrix and each block matrix can be greatly reduced.

On the premise that the check matrix H and the information vector S are known, the specific way to determine the codeword vector c is: according to the check equation Hc ^T =0 ^T , the decomposition equation can be obtained can be obtained after optimization After calculating p ₁ and p ₂ , the code word vector c=(S,p ₁ ,p ₂ ) can be calculated.

Refer to Figure 2 for the composition of the encoder referring to the above LDPC encoding process, which contains four functional modules: encoding matrix generator, matrix multiplier, matrix adder and LDPC codeword synthesizer.

There are 6 encoding matrix generators in the encoder, and its input is a matrix, which are six sub-matrices of matrix A, matrix B, matrix D, matrix E, matrix T and matrix F, and its output is a matrix, which is encoded The function of the matrix processed by the matrix generator is to compress and store the input matrix, that is, only store the non-zero elements of the matrix, and transform the input matrix to obtain the output matrix.

There are 6 multipliers in the encoder, which have two input terminals and one output terminal. The two input terminals are the information vector S, the matrix A, the matrix processed by the encoding matrix generator, and the result matrix of other multipliers. Or through two of the result matrices after the adder, the output is a matrix, which is the result vector after the multiplication of the two input terminals, and its function is to perform matrix multiplication on the two input terminals and output the result matrix.

The encoder has two matrix adders. The input is two matrices, both of which are the output matrices of the matrix multiplier in the encoder. The output is a matrix, which is the result of matrix addition of two input matrices. Its function is Performs matrix addition of two input matrices and outputs the resulting matrix.

There is an LDPC codeword synthesizer in the encoder, and its input is three vectors, which are information vector S, codeword check vector p ₁ and codeword check vector p ₂ , and its output is a vector, which is codeword The function of the vector c is to synthesize the three vectors of the information vector S, the codeword check vector p ₁ and the codeword check vector p ₂ into the codeword vector c=(S,p ₁ ,p ₂ ) and the codeword vector c.

The above is the existing LDPC encoding method and the corresponding encoder configuration. At the receiving end, it is also necessary to decode the received LDPC codeword to obtain a reconstructed information vector. The main steps of the existing LDPC decoding technology are as follows:

(1) Divide the M checkpoints into M _b layers, and each layer includes T checkpoints. Next, the decoding process is performed sequentially layer by layer. The information of check nodes and variable nodes is calculated during the processing of the first layer. After the decoding process of the first layer is completed, the second layer is initialized with the information of variable nodes obtained from the first layer, and so on;

(2) Initialization: use LLRs (log-likelihood ratios, ie The information on the variable node The value is initialized, and all check node information Set to 0, the number of iterations of the decoding algorithm is I, and the iterative process is carried out by row, wherein n∈N _m in the minimum sum algorithm represents the column of [H _b ] _{m, n} ≠ '-' in the check matrix prototype H _b ;

(3) Finding the minimum value: the cyclic right shift of the variable node vector q _n (shift times S(m,n)=[H _b ] _m,n ) minus the check node information Store the result in the vector t _n , according to OMS(offset min-sum, ie The value reuse feature of , only need to calculate the minimum value and the second minimum value of the elements in the vector;

(4) Choose the minimum value: for n∈N _m , calculate and update q _n and value.

In order to realize the above-mentioned decoding method, the existing decoder is shown in Fig. 3 and consists of 4 parts, namely an initialization decoder unit, a minimum value and next minimum value selection unit, a data truncation unit and a cyclic shift unit.

The initialization decoder unit in the decoder, its input is an LDPC inspection matrix, its output is an inspection matrix processed by the initialization decoding unit, and its function is to store and convert the inspection matrix according to the input requirements of the decoder And output the processed test matrix.

The minimum value and second minimum value selection unit in the decoder, its input is two matrices, one of which is the inspection matrix after the initial decoder unit processing, and the other is the LDPC code word matrix c, that is, through the wireless channel The output of the transmitted LDPC code word matrix c is a matrix processed by the minimum value and the second minimum value selection unit, and its function is to calculate the minimum value of the difference between the variable node cyclic right shift and the check node and the second smallest value and output the result matrix to provide to the data truncation unit and the cyclic shift unit.

The data truncation unit of the decoder, its input is a matrix output after being processed by the minimum value and the second minimum value selection unit, and its output is a matrix processed by the data truncation unit, and its function is to prevent verification The overflow of node information is processed by data truncation, and the output result matrix is provided to the cyclic shift unit.

The cyclic shift unit of the decoder, its input is two matrices, one of which is the matrix output after being processed by the data truncation unit, and the other is the matrix output after being processed by the minimum value and second minimum value selection unit, and its output It is a matrix processed by the cyclic shift unit, and its function is to calculate the variable node matrix by adding the minimum value matrix and the check node matrix by bitwise modulo, and output the variable node matrix.

As mentioned above, the coding and decoding theory of LDPC codes is relatively mature at present, but because LDPC codes are linear block codes with a large code length and a large check matrix, the algorithm complexity is very high, and the traditional LDPC coding and decoding methods cannot It satisfies the throughput requirement of IEEE 802.11n system very well, and affects the performance of the system to a great extent. Most implementations of LDPC codes in existing high-speed wireless local area network systems are based on FPGA (Field-Programmable Gate Array, Field Programmable Gate Array) chips and DSP (Digital Signal Processor, digital signal processing) chips. Although the previous methods can meet the processing and delay requirements of modern high-speed wireless LAN protocols, FPGA programming and professional DSP are relatively complicated, lacking a rich programming environment and debugging tools, and the applicability is average.

Contents of the invention

This application provides an LDPC encoding and decoding method based on a general-purpose processor, which can efficiently implement LDPC encoding and decoding on a general-purpose processor.

In order to achieve the above object, the application adopts the following technical solutions:

A general-purpose processor-based LDPC encoding method, comprising: obtaining a signal vector S to be encoded through signal acquisition or reception, determining a parity check matrix H and its block matrices A, B, D, E, F, and T, and performing save; according to Determine the vectors p ₁ and p ₂ , and obtain the LDPC encoding result vector c=(S, p ₁ , p ₂ ); wherein, when determining the vectors p ₁ and p ₂ , the correlation between any matrix and any vector Multiplication processing includes:

Taking each row of the arbitrary matrix as a thread, performing the multiplication operation of the corresponding row of the matrix and the arbitrary vector, and combining the multiplication results of all rows to form a result vector;

Wherein, the multiplication operation of each row of any matrix and any vector includes: determining the initial position of the vector corresponding to each element j in the current ith row of the matrix=the initial position of any vector+ A _{i, j} + (j-1) * Z, the data of ZA _{i, j} length from the starting position in any vector is left-shifted by means of single instruction multiple data stream SIMD, and After the data of the length of A _{i, j} before the starting position is moved to the left-shifted data, the vector shift result corresponding to the element j is obtained; and then the vector shift result corresponding to each element is added , as the multiplication result of each row and any vector;

In the SIMD method, the data of ZA _i,j length from the starting position is divided into units of length W segment, yes The segment data is shifted to the left in parallel, and then the remaining (ZA _{i, j} ) modW length data is shifted to the left;

Z is the size of a sub-matrix represented by an element in the parity check matrix.

Preferably, when the arbitrary matrix is T ^-1 , when each row of T ^-1 is multiplied by the corresponding vector, only the element whose value is 0 in T ^-1 is multiplied by the corresponding vector , get the vector shift result corresponding to the element whose value is 0, and set the vector shift result corresponding to the remaining elements as a zero vector; The multiplication result of any vector described above.

Preferably, the first Z data are taken as valid data after the left shift operation is performed on the W segments of data at the same time.

Preferably, adding the vector shift results corresponding to each element includes: dividing the vector shift results corresponding to each element into segment, via SIMD pair The segment data is added in parallel, and then the remaining (ZA _i,j )modW length data is added.

Preferably, the matrices A, B, D, E, F and T ^-1 are stored through a linear lookup table.

A kind of LDPC decoding method based on a general-purpose processor, comprising: receiving the encoded LDPC code word signal c, determining the parity check matrix H; calculating the variable node vector q as the decoding result through multiple iterations, during each iteration, according to The current variable node vector q and check node vector r calculate the temporary variable vector as And update the check node vector r according to the temporary variable vector t, and then update the variable node vector q according to the check node vector r and the temporary variable vector t as In the first iteration, the codeword signal c is used as the variable node vector q, and the check node vector r is set to 0; where,

When calculating the temporary variable vector t, the check node vector r and the variable node vector q each iteration, each row of the check matrix is used as a thread for operation and update, and the vectors t, q and r corresponding to each row are obtained. index number from arrive where i is the row index of the parity check matrix, corresponding to the i-th row of the parity check matrix when calculating the subvectors corresponding to the temporary variable vector t, the check node vector r and the variable node vector q, according to the check Each non-"-" element H _{i, j} in the row of the matrix corresponds to the index number corresponding to the element H _{i, j} in the calculation vectors t, q and r from arrive The subvectors of , and then sequentially connected to obtain the subvectors corresponding to each row, when i=1, let

The way to calculate the temporary variable vector t sub-vector corresponding to H _{i ,j} is: determine the vector starting position Z*(n-1)+H _i,n corresponding to H i,j, and set the vector q corresponding to row i The length from the starting position in the subvector is or 6 data is copied to the beginning of the temporary variable vector t subvector corresponding to H _{i, j} by means of SIMD; when H _{i, n} ≠ 0, H _{i, n} ≠ '-' and (ZH _{i, n} ) modW When ≠0, determine the value of each element in the row corresponding to check matrix element H _i,j in matrix M _{LdpcAssemble1} And the index number in the subvector of the current vector q corresponding to the element H _{i, j} is Each element of is copied to the current position of the temporary variable vector t sub-vector corresponding to H _{i, j} in turn; then determine the second vector starting position M _LdpcOffset2 corresponding to each element H _{i, j} , and set the second vector The length from the starting position is The data of is copied to the current position of the temporary variable vector t subvector corresponding to H _i,j by means of SIMD; take the first Z bits in the temporary variable vector t subvector corresponding to H _i,j and take the absolute value as valid subvectors of the temporary variable vector t corresponding to H _i,j ;

When H _i,n ≠0, H _i,n ≠'-' and (ZH _i,n )modW≠0, When H _i,n =0 or H _i,n ='-' or (ZH _i,n )modW=0, (M _LdpcOffset2 ) _i,j =Z*(n-1); K is the amount of data that can be handled by a general-purpose processor at one time, and k is the basic unit size of SIMD processing; when code length L _LDPC =648, LdpcRemain=11; when code length L _LDPC =1296, LdpcRemain=6; when code length L When _LDPC =1944, LdpcRemain=1; j is the index of each non-"-" element in the i-th row in all non-"-" elements in the row, and n is the j-th non-"-" element in the i-th row Column index in check matrix.

Preferably, the method of calculating the check node vector r subvector corresponding to each row of the check matrix is:

Write the temporary variable vector t subvector corresponding to each row of the check matrix as V _{LdpcRowLength} (v) rows and A matrix T _v of columns, wherein each row of the matrix T _v is a sub-vector corresponding to the element H _{i, j} in the sub-vector of the temporary variable vector t, and when the number of columns is not enough, a complement is performed;

Carrying out the most value assignment to the matrix T _v to obtain the most value variable vector m subvector matrix M _v ;

Calculate the intermediate variable vector s subvector matrix S _{v according to the matrix T v ;}

According to the element with the same index value in the matrix _{Mv and the matrix Sv, determine the element value of the corresponding index value in an intermediate matrix Rv ' ;} wherein, if any element in the matrix _Sv is less than 0, then Take the complement of any element and add it to any element, and use the addition result as the value of the element in the matrix R _v ' that is the same as the index value of any element in the matrix; if any of the matrix S _v If the element is equal to 0, add any element to 0, and use the addition result as the value of the element in the matrix R _v that is the same as the index value of any element in the matrix; if any element in the matrix S _v > 0 , then take the same element as the index value of any element in the matrix M _v and add it to any element, and use the result of the addition as the value of the element same as the index value of any element in the matrix R _v value; the operation of comparing and adding is carried out by means of SIMD;

Subtract the matrix R _v ' from the elements with the same index value in the matrix T _v by means of SIMD, and use the result as the element value of the same index value in the check node vector r subvector matrix R _v ; the matrix R The first Z elements of each row in _v are sequentially read out to form the check node vector r subvector in a row-first manner.

Preferably, said performing the most value distribution includes:

Determine the minimum value and the second minimum value of each column in the matrix T _v and the row index corresponding to the minimum value by means of SIMD; modify the obtained minimum value and the second minimum value, and subtract the preset correction value β, When the corrected minimum and second minimum values are less than 0, set it to 0, otherwise keep it unchanged;

According to the current minimum value of each column in the matrix T _v , the second minimum value and the row index corresponding to the minimum value, construct the column of the same index in the most value variable vector m subvector matrix M _v , wherein, in any column of M _v , set the element corresponding to the same row index as the current minimum value as the determined minimum value, and set the remaining elements as the next smallest value.

Preferably, the method of determining the minimum value and the second minimum value of each column and the corresponding row index through SIMD includes:

Divide each row element of the matrix T _v into sub-blocks, each sub-block includes W basic units; when comparing the elements of any two rows in the matrix T _v , W basic units are compared at one time by means of SIMD.

Preferably, the calculation of the intermediate variable vector s subvector matrix S _v includes:

For each column in the matrix T _v , perform an XOR operation on all the elements in the column, then XOR the result with the elements in the i'th row and then perform an OR operation with 0x7f, and use the OR operation result as the same as in the intermediate vector matrix S _v The i'th row element of the index column; wherein, each row element of the matrix T _v is divided into sub-blocks, each sub-block includes W basic units, and when XOR/OR operations are performed, the XOR/OR operations of W basic units are performed at one time by means of SIMD.

Preferably, calculating the variable node vector q subvector corresponding to H _i,j includes:

Determine the vector starting position Z*(n-1)+H _i,n corresponding to H _{i,j ,} and use the SIMD method to connect the temporary variable vector t subvector corresponding to H _i,j to the check node corresponding to H i,j The vector r sub-vectors are added, and the length from the starting position in the result vector is or 5 data is copied to the beginning of the variable node vector q subvector corresponding to H _{i, j} by means of SIMD; when H _{i, n} ≠ 0, H _{i, n} ≠ '-' and (ZH _{i, n} ) modW When ≠0, determine the value of each element in the row corresponding to check matrix element H _i,j in matrix M _{LdpcAssemble1} And the index number in the subvector of the current vector q corresponding to the element H _{i, j} is Each element of is copied to the current position of the variable node vector q sub-vector corresponding to H _{i, j} in turn;

Determine the second vector starting position M _LdpcOffset2 corresponding to each element H _i,j , and set the length from the starting position of the second vector to 0 or The data of is copied to the current position of the variable node vector q sub-vector corresponding to H _i,j through SIMD;

According to the number of supplementary positions indicated by LdpcRemain, supplementary positions are performed according to the value of the element in the row corresponding to the check matrix element H _{i, j} in M _{LdpcAssemble1} .

Preferably, the vector start position Z*(n-1)+H _i,n corresponding to each element H _i,j is pre-calculated and stored, and the second vector start position M _LdpcOffset2 , matrix M _{LdpcAssemble1} , parity check matrix The vector V _{LdpcRowLength} , M _{LdpcAssemble1} , and LdpcRemain constituted by the number of non-"-" elements in each row.

It can be seen from the above technical solutions that the LDPC encoding and decoding method in the present application can improve the encoding and decoding speed by means of SIMD instructions, multi-threading, and pre-storage.

Description of drawings

Fig. 1 is the schematic diagram of the generation process of LDPC PPDU;

Fig. 2 is the encoder composition schematic diagram of LDPC encoding process;

Fig. 3 is the schematic diagram of existing LDPC decoder;

Fig. 4 is the overall flowchart of the coding method in the present application;

Fig. 5 is the operation schematic diagram of computing code word check vector p ₁ in the LDPC encoding process of the present application;

Fig. 6 is the operation schematic diagram of calculating codeword check vector p ₂ in the LDPC encoding process of the present application;

Fig. 7 is the structural representation of optimization multiplier 1;

Fig. 8 is the structural representation of optimization multiplier 2;

Fig. 9 is a structural schematic diagram of an optimized adder;

Fig. 10 is a schematic diagram of an element in the matrix A and the transpose multiplication process of the vector S;

Fig. 11 is the processing schematic diagram of step 5 in the LDPC coding method of the present application;

Fig. 12 is a schematic diagram of the processing of step 5 in the LDPC decoding method of the present application;

Fig. 13 is a specific flow diagram of the application's LDPC decoding method;

FIG. 14 is a schematic flow chart of the most value allocation process for a sub-block in the LDPC decoding method of the present application;

Fig. 15 is a schematic structural diagram of a maximum value assignment operation in the LDPC decoding method;

16 is a schematic flow chart of calculating an intermediate variable vector for a sub-block in the LDPC decoding method;

Fig. 17 is a schematic structural diagram of an intermediate vector calculation in the LDPC decoding method.

detailed description

In order to make the purpose, technical means and advantages of the present application clearer, the present application will be further described in detail below in conjunction with the accompanying drawings.

This application provides an LDPC encoding method and a decoding method suitable for implementation in a general-purpose processor. The encoding method and decoding method in this application are described in detail below.

According to the LDPC PPDU generation method in the IEEE 802.11n protocol, the encoded codeword vector is recorded as c=(S,p ₁ ,p ₂ ), where S is the information vector, p ₁ and p ₂ are the codeword check vectors, Simplify the check matrix H into six parts It is divided into six sub-matrices of matrix A, matrix B, matrix D, matrix E, matrix F and matrix T. Before decoding, the code length L _LDPC , code rate R and information vector S need to be input from outside. The application optimizes the LDPC encoding method as follows according to the characteristics of the general-purpose processor (GPP) chip architecture:

1. Using the SIMD (Single Instruction Multiple Data, Single Instruction Multiple Data) algorithm to optimize the encoding method, the essential principle is to process multiple data within one clock cycle of the CPU to obtain the effect of parallel processing, while Unlike normal usage - only one data processing operation per clock cycle. It will involve the amount of data that can be processed at one time by the general-purpose processor used. Assuming that the size is K bits, and the basic unit size of SIMD processing is k, the amount of data that can be processed in one operation

2. Use the linear lookup table method to optimize the information storage of the check matrix, and split the check matrix H into six parts Divide into six sub-matrices of matrix A, matrix B, matrix D, matrix E, matrix F and matrix T, and generate six linear look-up tables with these six sub-matrices, reducing computational complexity.

3. Adopt the method of multi-threading, take the number of rows of the check matrix H as the number of threads, that is, process one row of data in the check matrix H as a thread, and execute the processing operations of multiple threads at the same time, thereby improving the performance of the system overall processing performance.

Fig. 4 is a general flowchart of the encoding method in this application, wherein the algorithm principle based on the encoding method is the same as that of the current LDPC encoding method, and the difference lies in the specific implementation of the encoding method in the general-purpose processor. The specific process is as follows:

1. According to the 802.11n protocol, different code lengths L _LDPC and different coding rates R correspond to different parity check matrices H. First, according to the code length L _LDPC and the coding rate R, the corresponding check matrix H is extracted, and the following parameters are initialized:

1.1 Generate matrix A, matrix B, matrix D, matrix E, matrix F and matrix T ^-1 six sub-matrices, where () ^-1 is the inverse of the matrix, and store them in the linear lookup table in turn, using the offset The method marks the specific location of the required data, exchanges the memory for computational complexity, and improves the data processing speed of the LDPC code encoding method.

1.2 The size of the sub-matrix represented by each element in the selected parity check matrix H is generated as Z. When the code length L _LDPC =648, Z=27; when the code length L _LDPC =1296, Z=54; when the code length L _LDPC =1944, Z=81.

2. According to the characteristics of the GPP chip, the encoding method is optimized by using a multi-thread method. The number of rows of the parity check matrix H is the number of threads, and one row of data in the parity check matrix H is one thread to process steps 3 to 4. Execute the processing operations of multiple threads at the same time, that is, perform the processing of multiple steps 3 to 4 at the same time, thereby improving the overall processing performance of the system. The following steps 3 and 4 are specific processes for single-thread processing.

3. Calculate the codeword check vector p ₁ , in which the multiplication and addition operations are optimized using the SIMD operation method. The operation schematic diagram is shown in Figure 5, and the specific process is as follows:

3.1 The matrix A is multiplied by the transpose of the vector S, and the result is a vector whose length is equal to the number of rows of the matrix A.

3.2 The matrix T ^-1 is multiplied by the transposition of the result vector obtained in step 3.1, and the result is a vector whose length is equal to the number of rows of the matrix T ^-1 .

3.3 The matrix E is multiplied by the transpose of the result vector obtained in step 3.2, and the result is a vector whose length is equal to the number of rows of the matrix E.

3.4 The matrix F is multiplied by the transpose of the vector S, and the result is a vector whose length is equal to the number of rows of the matrix F.

3.5 Add the result vector obtained in step 3.3 to the result vector obtained in step 3.4, and the result is the codeword check vector p ₁ .

4. Calculate the codeword check vector p ₂ , in which the multiplication and addition operations are optimized using the SIMD operation method. The schematic diagram of its operation is shown in Figure 6, and the specific process is as follows:

4.1 Matrix B is multiplied by the transpose of vector p ₁ , and the result is a vector whose length is equal to the number of rows of matrix B.

4.2 Add the result vector obtained in step 3.1 to the result vector obtained in step 4.1, and the result is a vector.

4.3 The matrix T ^-1 is multiplied by the transpose of the result vector obtained in step 4.2, and the result is the codeword check vector p ₂ .

5. Assemble the LDPC codeword vector c:

The obtained vectors are stored in the order of S, p ₁ , p ₂ to obtain the LDPC codeword vector c=(S, p ₁ , p ₂ ).

In the encoding method of the present application mentioned above, two kinds of optimized multipliers and one optimized adder are involved, which are called optimized multiplier 1 , optimized multiplier 2 and optimized adder respectively. According to the characteristics of the GPP chip architecture, the optimized multiplier 1, the optimized multiplier 2, and the optimized adder that involve parallel operations can be optimized using the SIMD operation method. Let's introduce them one by one.

The optimal multiplier 1 has two input terminals and one output terminal. The schematic diagram of the optimized multiplier 1 is shown in FIG. Use to optimize multiplier 1. Taking step 3.1 as an example, the input terminal of optimization multiplier 1 is the transposition of matrix A and vector S, and its specific implementation process is as follows:

1. Determine whether the maximum number of rows of matrix A has been reached. If so, the operation has been completed; if not, proceed to step 2.

2. Multiply the submatrix of Z*Z represented by the first element in matrix A by the transpose of vector S. Because this sub-matrix is the result of a Z*Z identity matrix after A _1,1 (A _1,1 represents the elements of the first row and first column of matrix A) cycles left, so the sub-matrix and the vector S Multiplying the transpose of is equivalent to performing A _1,1 cyclic shift operation on the vector S. This operation can be SIMD optimized, see Figure 10, the specific operation process is as follows:

2.1 Calculated Part 2 data length = (ZA _1,1 ) mod W (which is ZA _1,1 modulo W), and required data start value position = information vector s start position + A _1,1 .

2.2 Start the position of the required data starting value The data copy of the length is used as the starting position data of the intermediate data;

2.3 Shift copy the remaining (ZA _1,1 ) modW pieces of data, and copy the "remaining part" and "filling" in Fig. 10 into the output. To accommodate SIMD operations, the input vector length is Z and the output vector size will be But in the output vector, only the first Z elements are valid data, and the result data is stored in the result vector register.

3. Determine whether the maximum number of columns of the matrix A is reached, and if so, return to step 1; if not, proceed to step 4.

4. Multiply the sub-matrix of Z*Z represented by the next element in matrix A with the transpose of vector S. The specific steps are the same as steps 2.1, 2.2, and 2.3, but the transposed multiplication result does not need to be stored in the result vector register, and go to step 5.

5. Add the calculation result of step 4 to the elements in the result vector register. The addition of two binary numbers is equivalent to the XOR operation of two numbers. At this time, SIMD optimization can be performed, that is, W results can be obtained in one operation, as shown in the figure 11, where (a ₁ ,a ₂ ,…,a _W ) represents the calculation result of step 4, (b ₁ ,b ₂ ,…,b _W ) represents the elements in the result vector register, the rectangular box represents the XOR operator, (y ₁ ,y ₂ ,…,y _W ) represent the result after operation, namely Store them in the result vector register and return to step 3.

The optimized multiplier 2 has two input terminals and one output terminal. The schematic diagram of the optimized multiplier 2 is shown in FIG. . The optimized multiplier 2 is a special case of the optimized multiplier 1. One of the inputs of the optimized multiplier 2 is a matrix T ^-1 . Under different parity check matrices H, the matrix Only the elements in the lower triangle of the matrix T ^-1 are valid values. Taking step 3.2 as an example, the input terminal of optimization multiplier 2 is the transposition of the matrix T _- ¹ and the result vector obtained in step 3.1. The specific implementation process is as follows:

1. Determine whether the maximum number of rows of matrix A has been reached. If so, the operation has been completed; if not, proceed to step 2.

2. Yes It can be seen that the triangular elements on the matrix T ^-1 are all 0,

The submatrix of Z*Z represented by the element "0" is multiplied with the transposition of the result vector obtained in step 3.1 in Figure 4, and the result is still the latter, so for the element "0" in each row of the matrix T ^-1 and the figure Multiply the transposition of the result vector obtained in step 3.1 in 4, and add the obtained results according to step 5 in optimized multiplier 1, and return to step 1.

The optimized adder has two input terminals and one output terminal, and both input terminals are vectors. The schematic diagram of the optimized adder is shown in Figure 12. The vector and vector addition operations involved in step 3.5 and step 4.2 of the optimized encoding method are Use an optimized adder. Taking step 3.5 as an example, the input terminal of the optimized adder is the result vector obtained in step 3.3 and the result vector obtained in step 3.4, because the input terminals are all binary numbers, and the addition of two binary numbers is equal to the XOR operation of two binary numbers. SIMD optimization can be performed when , that is, W results can be obtained in one operation, see Figure 11, where (a ₁ ,a ₂ ,…,a _W ) represents the result vector obtained in step 3.3, (b ₁ ,b ₂ ,…,b _W ) represents the result vector obtained in step 3.4, the rectangular box represents the XOR operator, (y ₁ ,y ₂ ,…,y _W ) represents the result after the operation, namely

The above is the specific flow of the LDPC encoding method in this application. This application optimizes the decoding method of the existing decoder, and the specific flowchart of the optimized decoding method is shown in FIG. 13 . Before decoding, the outside world needs to input code length L _LDPC , code rate R, code word vector c after code, maximum number of iterations I and correction offset β. According to the characteristics of the GPP chip architecture, the LDPC decoding method is optimized as follows:

1. Using the SIMD operation method to optimize the encoding method, the essential principle is to process multiple data within one clock cycle of the CPU to obtain the effect of parallel processing, unlike the ordinary use method - each clock Only one data processing operation is performed in a cycle. It will involve the amount of data that can be processed at one time by the general-purpose processor used. Assuming that the size is K bits, and the basic unit size of SIMD processing is k, the amount of data that can be processed in one operation

2. Part of the process in the optimized decoding method adopts a multi-threaded method. The number of rows of the check matrix H is used as the number of threads, that is, one thread is used to process a row of data in the check matrix H, and multiple threads are executed at the same time processing operations, thereby improving the overall processing performance of the system.

The following describes the specific flow of the decoding method in this application, wherein the general framework of the decoding method is the same as the current decoding method, specifically including: receiving the encoded LDPC codeword signal c, determining the parity check matrix H; through multiple iterations Calculate the variable node vector q as the decoding result, and calculate the temporary variable vector according to the current variable node vector q and check node vector r at each iteration as And update the check node vector r according to the temporary variable vector t, and then update the variable node vector q according to the check node vector r and the temporary variable vector t as The difference between the decoding method provided by the present application and the prior art lies in the specific implementation in the general processor. The specific operation steps are as follows:

1. According to the 802.11n protocol, different code lengths L _LDPC and different coding rates R correspond to different parity check matrices H. First, according to the code length L _LDPC and the encoding code rate R, extract the corresponding parity check matrix H, initialize each parameter, and store them in the linear lookup table in turn, and use the offset method to mark the required data The specific location of the memory is exchanged for computational complexity, and the data processing speed of the LDPC code decoding method is improved:

1.1Z, that is, the size of the sub-matrix represented by each element in the selected parity check matrix H, is a variable. When the code length L _LDPC =648, Z=27; when the code length L _LDPC =1296, Z=54; when the code length L _LDPC =1944, Z=81.

1.2 LdpcRowNum, that is, the number of rows of the check matrix H selected, is a variable. bit rate When, LdpcRowNum=12; when the code rate When, LdpcRowNum=8; when the code rate When, LdpcRowNum=6; when the code rate , LdpcRowNum=4.

1.3V _{LdpcRowLength} , that is, the number of non-"—" elements in each row of the selected parity check matrix H, is a vector with a length of 1*LdpcRowNum.

1.4 LdpcBufferNum, that is, the number of registers required to store the data of each sub-matrix of the selected parity check matrix H, is a variable. Its operation formula is

1.5LdpcRemain, which is one of the variables required in step 9, is a variable. When the code length L _LDPC =648, LdpcRemain=11; when the code length L _LDPC =1296, LdpcRemain=6; when the code length L _LDPC =1944, LdpcRemain=1.

1.6 LdpcRoundNum, which is one of the variables required in step 9, is a variable. When the code length L _LDPC =648, LdpcRoundNum=27; when the code length L _LDPC =1296, LdpcRoundNum=22; when the code length L _LDPC =1944, LdpcRoundNum=17.

1.7V _{LdpcRowBuffer} , which is the number of registers required to store non-"—" data in each row of the selected check matrix H, is a vector with a length of 1*LdpcRowNum. Its operation formula is V _{LdpcRowBuffer} (v)=V _{LdpcRowLength} (v)*LdpcBufferNum (wherein V _{LdpcRowBuffer} (v) represents the vth element of the vector LdpcRowBuffer, and v corresponds to the row number of the check matrix H, as follows).

1.8M _LdpcOffset1 , which is one of the cyclic offsets calculated according to the selected parity check matrix H, is used in steps 4 and 9, and is a matrix of LdpcRowNum*max(V _{LdpcRowLength} (v)) (wherein max(V _{LdpcRowLength} ( v)) means to take the maximum value of the elements in the vector V _{LdpcRowLength} , the same reason as follows). Its operation formula is (M _LdpcOffset1 ) _i,j =Z*(n-1)+H _i,n , where n represents the number of columns in the selected check matrix H, and the corresponding relationship between j and n is the selected check matrix The position of the jth non-"—" element in the i-th row of the verification matrix H is the i-th row and the nth column, and the same reasoning follows.

1.9M _LdpcRound1 , which is one of the number of rounds calculated according to the selected parity check matrix H, is used in step 4 and is a matrix of LdpcRowNum*max(V _{LdpcRowLength} (v)). Its operation formula is when H _i,n ≠0 and H _i,n ≠'-', When H _i,n =0 and H _i,n ≠'-', (M _LdpcRound1 ) _i,j =6.

_{1.10M LdpcAssemble1} , which is one of the complementary offset flag bits calculated according to the selected parity check matrix H, is used in step 4 and is a matrix of LdpcRowNum*max(V _{LdpcRowLength} (v)). Its operation formula is when H _i,n =0 and H _i,n ≠'-', (M _{LdpcAssemble1} ) _i,j =0; when H _i,n ≠0, H _i,n ≠'-' and ( ZH _i,n )modW=0, (M _{LdpcAssemble1} ) _i,j =0; when H _i,n ≠0, H _i,n ≠'-' and (ZH _i,n )modW≠0, (M _{LdpcAssemble1} ) _i,j =1.

1.11M _{LdpcAssembleTable1} , that is, calculate the cyclic complement offset according to the selected parity check matrix H, which is used in step 4 and step 9, as ( matrix (where To calculate the sum of all elements in the vector LdpcRowLength),

1.12M _LdpcOffset2 , which is one of the cyclic offsets calculated according to the selected parity check matrix H, is used in step 4 and step 9, and is a matrix of LdpcRowNum*max(V _{LdpcRowLength} (v)). The operation formula is when (M _{LdpcAssemble1} ) _i,j ＝0, (M _LdpcOffset2 ) _i,j ＝Z*(n-1)+[W-Z+H _i,n +(M _LdpcRound1 ) _i,j * W ^] ; when (M _{LdpcAssemble1} ) _i,j =1, (M _LdpcOffset2 ) _i,j =Z*(n-1).

_{1.13M LdpcRound2} , which is one of the number of rounds calculated according to the selected parity check matrix H, is used in step 4 and is a matrix of LdpcRowNum*max(V _{LdpcRowLength} (v)). Its operation formula is

1.14M _LdpcRound3 , which is one of the number of rounds calculated according to the selected parity check matrix H, is used in step 9 and is a matrix of LdpcRowNum*max(V _{LdpcRowLength} (v)). Its operation formula is when H _i,n ≠0 and H _i,n ≠'-', When H _i,n =0 and H _i,n ≠'-', (M _LdpcRound3 ) _i,j =5.

_{1.15M LdpcAssemble2} , which is one of the complementary offset flag bits calculated according to the selected parity check matrix H, is used in step 9, the same as M _{LdpcAssemble1} .

1.16M _LdpcRound4 , which is one of the round times calculated according to the selected parity check matrix H, used in step 9, is a matrix of LdpcRowNum*max(V _{LdpcRowLength} (v)). Its operation formula is when i=0, (M _LdpcRound4 ) _i,j =0; when i≠0,

2. Determine whether the maximum number of iterations I is reached. If the maximum number of iterations I is not reached, proceed to step 3; if the maximum number of iterations I is reached, the decoding ends.

3. According to the characteristics of the GPP chip, the decoding method is optimized by using a multi-threaded method. The number of rows in the parity check matrix H is used as the number of threads, and one row of data in the parity check matrix H is one thread to process steps 4 to 9. Execute the processing operations of multiple threads at the same time, that is, perform the processing of multiple steps 4 to 9 at the same time, thereby improving the overall processing performance of the system. The following steps 4 to 9 are specific processes for single-thread processing.

4. Calculate the temporary variable vector t, whose length is of vectors. Wherein, the temporary variable vector includes a subvector corresponding to each row of the check matrix, and its index number is arrive This subvector in turn includes a subvector corresponding to each non-"-" element H _i,j . (Here, only the non-"-" elements H _{i, j} in the check matrix have corresponding sub-vectors, and the "-" elements in the check matrix are all in the temporary variable vector, check node vector r, and variable node vector q There is no corresponding subvector.) Specifically, the calculation formula of the subvector t' corresponding to H _i,j is That is, the value of the temporary variable vector t sub-vector t' is the sub-vector q' corresponding to the element H _i,j in the variable node vector q, which is cyclically shifted according to the element value of the i-th row and the j-th column of the check matrix H, and the check node Difference of subvector r' corresponding to element H _i,j in vector r. If it is the first iterative operation at this time, the variable node vector q is the codeword vector c after LDPC encoding, and the check node vector r is the initial state, at this time the calculation formula of the temporary variable vector t sub-vector t' is That is, the sub-vector t' of the temporary variable vector t is the result of circular shifting of the element value of the variable node vector q sub-vector q' according to the value of the element in the i-th row and the j-th column of the parity check matrix H. In order to adapt to the SIMD operation, the length of the input variable node vector q subvector q' and the check node vector r subvector r' is Z, and the size of the output temporary variable vector t subvector t' will be But in the output subvector, only the first Z elements are valid data. The operation of the temporary variable vector t is cycled by the number of non-"-" elements in each row of the selected check matrix H, for example, the jth non-"-" element in the ith row of the selected check matrix H will be calculated to obtain a temporary variable vector t's arrive bit elements. The specific calculation steps are as follows:

4.1 According to the M _LdpcOffset1 matrix, find the cyclic offset corresponding to the jth non-"-" element in the i-th row of the selected parity check matrix H, and find the starting value position of the required data in the variable node vector q, so The initial value position of the required data = the initial value position of the variable node vector q sub-vector q' + the corresponding loop offset.

4.2 According to the M _LdpcRound1 matrix, find the number of cycles corresponding to the jth non-"-" element in the i-th row of the selected parity check matrix H, and place (M _LdpcRound1 ) _i,j *W data after the starting value of the required data Copy to the current position of the sub-vector t' of the temporary variable vector t, where the current position refers to the starting position of the uncopied data in the sub-vector.

4.3 According to the M _{LdpcAssemble1} matrix, it is judged whether a supplementary operation is required. If (M _{LdpcAssemble1} ) _i,j =1, the complement operation is performed according to the offset indicated in the M _{LdpcAssembleTable1} matrix; if (M _{LdpcAssemble1} ) _i,j =0, no complement operation is required. The specific complement operation includes: determining the value of each element in the row corresponding to the check matrix element H _{i, j} in the matrix M _{LdpcAssemble1} And the index number in the subvector of the current vector q corresponding to the element H _{i, j} is Each element of is copied to the current position of the temporary variable vector t subvector corresponding to H _{i, j} in turn; where,

4.4 According to the M _LdpcOffset2 matrix, find the cyclic offset corresponding to the jth non-"-" element in the i-th row of the selected parity check matrix H, and find the starting value position of the required data in the variable node vector q, so The initial value position of the required data = the initial value position of the variable node vector q sub-vector q' + the corresponding loop offset.

4.5 According to the M _LdpcRound2 matrix, find out the number of cycles corresponding to the jth non-"-" element in the i-th row of the selected parity check matrix H, and place (M _LdpcRound2 ) _i,j *W data after the starting value of the required data Copy to the current position of the temporary variable vector t sub-vector t'.

4.6 If it is not the first iterative operation at this time, the temporary variable vector t subvector t'=temporary variable vector t subvector t'-check node vector r subvector r' operation is required, and the temporary variable vector t subvector All elements of t' and check node vector r sub-vector r' are divided into a group of W elements, and SIMD optimization can be performed at this time, that is, elements in W temporary variable vector t can be obtained in one operation, see Figure 11, where (a ₁ ,a ₂ ,…,a _W ) represent the elements in a set of temporary variable vector t, (b ₁ ,b ₂ ,…,b _W ) represent the elements in a set of check node vector r, and the rectangular box represents Subtractor, (y ₁ ,y ₂ ,…,y _W ) represents the result after operation, that is, (y ₁ ,y ₂ ,…,y _W )=(a ₁ -b ₁ ,a ₂ -b ₂ ,… ,a _W -b _W ); if this is the first iterative operation, go to step 5.

5. Calculate the absolute value of all elements in the subvector t' of the temporary variable vector t, and record it as the modulo temporary variable vector |t|. The temporary variable vector t sub-vector t' is divided into W elements as a group, and SIMD optimization can be performed at this time, that is, elements in the W temporary variable vector t sub-vector t' can be obtained in one operation, see Figure 12, where ( c ₁ ,c ₂ ,…,c _W ) represent the elements in a set of temporary variable vector t sub-vector t', the rectangular box represents the modulo operator, (y ₁ ,y ₂ ,…,y _W ) represents the modulus Temporary variable vector |t|, ie (y ₁ , y ₂ , ..., y _W )=(|c ₁ |, |c ₂ |, ..., |c _W |). Take it as a subvector t' of the updated temporary variable vector t.

6. The most value distribution operation, and store the result in the matrix M of the most value variable vector m. This process loops with the number of rows of the selected check matrix H, that is, each time the V _{LdpcRowLength} (v)*W*LdpcBufferNum elements in the temporary variable vector t are operated, the length is V _{LdpcRowLength} (v)*W*LdpcBufferNum The result of is stored in the most value variable vector m. Refer to Figure 15 for a schematic diagram of the most value distribution operation. The temporary variable vector t subvector t' corresponding to each row of the check matrix is written as V _{LdpcRowLength} (v) row and The matrix T _v of columns, wherein, each row of the matrix T _v is the sub-vector corresponding to the element H _{i, j} in the temporary variable vector t sub-vector t', and when the number of columns is not enough, the complement is performed; the most value assignment operation is the calculation matrix The minimum value and the second minimum value of each column element in T _v are distributed, and the result is stored in the subvector matrix M _v of the most value variable vector m. There are LdpcBufferNum sub-blocks in each row of the matrix T _v , and there are W basic units in each sub-block; compare the size of the basic units in each row, obtain the minimum value and the second minimum value, and record the number of rows where the minimum value is located Row number, that is, the index value; fill the most value variable vector m according to the index value, if the index value is different from the row number of the most value variable vector m, then fill in the minimum value found in the most value variable vector m, if the index value is the same as the row number of the most value variable vector m, then fill in the second smallest value found in the most value variable vector m. Take finding out the minimum value and second minimum value of a sub-block as an example, its flow chart is shown in Figure 14, and the specific steps are as follows:

6.1 Compare the size of the corresponding basic unit in the first sub-block of the first row and the second row of the matrix T _v , store the row number of the smaller value in the index value, and record the smaller value as the minimum value, and compare The large value is recorded as the second smallest value. At this time, SIMD optimization can be performed, and two calculations are performed. One takes the maximum value to obtain the larger value between the two, and one time removes the minimum value to obtain the smaller value between the two. See Figure 11, where (a ₁ ,a ₂ ,…,a _W ) represents the elements of the first sub-block in the first row, and (b ₁ ,b ₂ ,…,b _W ) represents the first sub-block in the second row The elements of , the rectangular box represents the maximum value operator or the minimum value operator, (y ₁ ,y ₂ ,…,y _W ) represents the result after the operation, that is, (y ₁ ,y ₂ ,…,y _W )= (max(a ₁ ,b ₁ ),max(a ₂ ,b ₂ ),…,max(a _W ,b _W )) or (y ₁ ,y ₂ ,…,y _W )=(min(a ₁ , b ₁ ),min(a ₂ ,b ₂ ),…,min(a _W ,b _W )).

6.2 Determine whether the maximum number of cycles V _{LdpcRowLength} (v) has been reached, if not, proceed to step 6.3; if yes, proceed to step 6.6.

6.3 Perform a maximum value operation on the first sub-block in the next row of the matrix T _v and the previously recorded minimum value, this operation can be SIMD optimized, the same as step 6.1.

6.4 Perform the minimum value operation on the result obtained in step 6.3 and the second smallest value currently recorded. This operation can be SIMD optimized, the same as step 6.1, and record the result as the second smallest value.

6.5 Perform the minimum value operation on the result obtained in step 6.3 and the minimum value currently recorded. This operation can be SIMD optimized, the same as step 6.1, and record the result as the minimum value, and record the row number of the minimum value as the index value , return to step 6.2.

6.6 Subtract the correction value β from the minimum value and the second smallest value of the current record. This operation can be SIMD optimized, see Figure 11, where (a ₁ ,a ₂ ,…,a _W ) represent the minimum or second smallest value recorded previously Small value, (b ₁ ,b ₂ ,…,b _W ) means the correction value β can also be expressed as (β,β,…,β), the rectangular box means the subtractor, (y ₁ ,y ₂ ,…,y _W ) represents the result after the operation, that is, (y ₁ ,y ₂ ,…,y _W )=(a ₁ -β,a ₂ -β,…,a _W -β), and record the result as the minimum value or second small value.

6.7 Correct the minimum value and the second minimum value of the current record. When the minimum value or the second minimum value of the current record is less than zero, set the value to zero, otherwise no operation is performed. This operation can be SIMD optimized. See Figure 11. Where (a ₁ ,a ₂ ,…,a _W ) represents the minimum or second smallest value of the current record, (b ₁ ,b ₂ ,…,b _W ) represents zero value and can also be expressed as (0,0,…, 0), the rectangular frame represents the correction operator, (y ₁ ,y ₂ ,…,y _W ) represents the result after the operation, namely And record the result as the smallest or next smallest value.

6.8 Fill the most value variable vector m according to the index value. If the index value is different from the row number of the subvector matrix M _v of the most value variable vector m, fill in the minimum value of the current record in the same position of the matrix M _v . If the index value is the same as the row number of the most value variable vector m _subvector matrix _Mv , then fill in the second smallest value of the current record in the same position of the most value variable vector m subvector matrix Mv. The elements in the matrix M _v are read out in row-first order to form the subvector of the most valued variable vector m.

7. Calculate the intermediate variable vector s. This process loops with the number of rows of the selected check matrix H, that is, each time the V _{LdpcRowLength} (v)*W*LdpcBufferNum elements in the temporary variable vector t are operated, the length is V _{LdpcRowLength} (v)*W*LdpcBufferNum The result is stored in the intermediate variable vector s. Refer to Figure 17 for a schematic diagram of an intermediate variable vector s operation. The temporary variable vector t is divided into V _{LdpcRowLength} (v) rows, each row has LdpcBufferNum sub-blocks, and each sub-block has W basic units. Take the calculation of the intermediate variable vector s of a sub-block as an example, its flow chart is shown in Figure 16, and the specific operation process is as follows:

7.1 XOR the first sub-block of the first row and the first sub-block of the second row of the temporary variable vector t, this operation can be SIMD optimized, see Figure 11, where (a ₁ ,a ₂ ,…,a _W ) represents the first sub-block in the first row, (b ₁ ,b ₂ ,…,b _W ) represents the first sub-block in the second row, and the rectangular box represents the XOR operator, (y ₁ ,y ₂ ,…,y _W ) represents the result after the operation, namely

7.2 Determine whether the maximum number of cycles V _{LdpcRowLength} (v) has been reached, if not, proceed to step 7.3; if yes, proceed to step 7.4, and execute from the first row.

7.3 XOR the first sub-block of the next row of the temporary variable vector t with the result of step 7.1, this operation can be SIMD optimized, see Figure 11, where (a ₁ ,a ₂ ,…,a _W ) represent the next row The first sub-block, (b ₁ ,b ₂ ,…,b _W ) represents the result of step 7.1, the rectangular box represents the XOR operator, and (y ₁ ,y ₂ ,…,y _W ) represents the result after the operation, namely Return to step 7.2.

7.4 Judging whether the maximum number of cycles V _{LdpcRowLength} (v) has been reached, if not, proceed to step 7.5; if yes, proceed to step 8.

7.5 Perform an XOR operation on the first sub-block of the current row of the temporary variable vector t and the result of step 7.3, and this operation can be SIMD optimized.

7.6 Combine the result of step 7.5 with Perform OR operation, this operation can be SIMD optimized, see Figure 11, where (a ₁ ,a ₂ ,…,a _W ) represents the result of step 7.5, (b ₁ ,b ₂ ,…,b _W ) represents The rectangular box represents the OR operator, (y ₁ ,y ₂ ,…,y _W ) represents the result after the operation, that is, (y ₁ ,y ₂ ,…,y _W )=(a ₁ |b ₁ ,a ₂ |b ₂ ,...,a _W |b _W ), and store the result in the first sub-block of the intermediate variable vector s, and return to step 7.4.

8. Calculate the check node vector r, whose length is of vectors. Wherein, the check node vector includes a subvector corresponding to each row of the check matrix, and its index number is arrive This subvector in turn includes a subvector corresponding to each non-"-" element H _i,j . The process of calculating the check node vector r is circulated with the number of rows of the selected check matrix H, that is, the V _{LdpcRowLength} (v)*W*LdpcBufferNum elements in the temporary variable vector t are operated each time to obtain a length of V _{LdpcRowLength} ( v) The result of *W*LdpcBufferNum is stored in the check node vector r. When calculating the subvector corresponding to each row of the parity check matrix, the subvector corresponding to each non-"-" element H _{i, j} is used as the unit, and the calculated index is arrive elements in the vector of . The following takes the calculation of a check node vector r subvector r' corresponding to a non-"-" element H _i,j as an example, and the specific operation process is as follows:

8.1 Determine whether the maximum number of cycles V _{LdpcRowLength} (v) has been reached, if not, proceed to step 8.2; if yes, proceed to step 9.

8.2 Compare the subvector corresponding to the most value variable vector m and H _i,j with the subvector corresponding to the intermediate variable vector s and H _i,j , if the intermediate variable vector s is less than zero, the result is the most value variable vector The complement of the value of m, if the intermediate variable vector s is equal to zero, the result is zero, if the intermediate variable vector s is greater than zero, the result is the value of the most valued variable vector m. This operation can be SIMD optimized, see Figure 12, where (a ₁ , a ₂ ,…,a _W ) represents the most value variable vector m, (b ₁ ,b ₂ ,…,b _W ) represents the intermediate variable vector s, and the rectangle The box represents the comparison operator, (y ₁ ,y ₂ ,…,y _W ) represents the result after the operation, namely

8.3 Add the result of step 8.2 to the intermediate variable vector s. This operation can be SIMD optimized, see Figure 11, where (a ₁ ,a ₂ ,…,a _W ) represents the result of step 8.2, (b ₁ ,b ₂ ,…,b _W ) represents the intermediate variable vector s, and the rectangular box Indicates the addition operator, (y ₁ ,y ₂ ,…,y _W ) indicates the result after operation, that is, (y ₁ ,y ₂ ,…,y _W )=(a ₁ +b ₁ ,a ₂ +b ₂ , ..., _aW + _bW ).

8.4 Subtract the result of step 8.3 from the temporary variable vector t subvector t'. This operation can be SIMD optimized, see Figure 11, where (a ₁ , a ₂ ,…,a _W ) represents the result of step 8.3, (b ₁ ,b ₂ ,…,b _W ) represents the temporary variable vector t, and the rectangular box Indicates the addition operator, (y ₁ ,y ₂ ,…,y _W ) indicates the result after operation, that is, (y ₁ ,y ₂ ,…,y _W )=(a ₁ -b ₁ ,a ₂ -b ₂ , …,a _W -b _W ), and store the result in the check node vector r, return to step 8.1.

9. Calculate the variable node vector q, whose length is of vectors. Wherein, the variable node vector includes a subvector corresponding to each row of the parity check matrix, and its index number is arrive This sub-vector in turn includes a sub-vector q' corresponding to each non-"-" element H _i,j . The calculation formula of the variable node vector q sub-vector q' is That is, the value of the variable node vector q sub-vector q' is the sum of the value of the temporary variable vector t sub-vector t' and the value of the check node vector r sub-vector r', and loops according to the element value of the ith row and j column of the check matrix H The shifted result. In order to adapt to the SIMD operation, the length of the input temporary variable vector t subvector t' and the check node vector r subvector r' is Z, and the size of the output variable node vector q subvector q' will be But in the output subvector, only the first Z elements are valid data. The operation of the variable node vector q is cyclically based on the number of non-"-" elements in each row of the selected check matrix H, for example, the jth non-"-" element in the i-th row of the selected check matrix H will be calculated to obtain the variable node vector q's arrive bit elements. The specific calculation steps are as follows:

9.1 According to the M _LdpcOffset1 matrix, find the cyclic offset corresponding to the non-"-" element in the i-th row of the selected check matrix H, and find the required starting position in the variable node vector q. The required starting position Position = initial value position of variable node vector q sub-vector q' + corresponding loop offset.

9.2 Add the subvector t' of the temporary variable vector t to the subvector r' of the check node vector r. This operation can be SIMD optimized, see Figure 11, where (a ₁ , a ₂ ,…,a _W ) represents the temporary variable vector t, (b ₁ ,b ₂ ,…,b _W ) represents the check node vector r, and the rectangle The box represents the addition operator, (y ₁ ,y ₂ ,…,y _W ) represents the result after the operation, that is, (y ₁ ,y ₂ ,…,y _W )=(a ₁ +b ₁ ,a ₂ +b ₂ ,...,a _W +b _W ).

9.3 According to the M _LdpcRound3 matrix, find the number of loops corresponding to the jth non-"-" element in the i-th row of the selected check matrix H, and place the starting value of the result data in step 9.2 after (M _LdpcRound1 ) _i,j *W Copy the data to the desired starting location found in step 9.1.

9.4 According to the M _{LdpcAssemble2} matrix, it is judged whether to perform complement operation. If (M _{LdpcAssemble2} ) _i,j =1, the complement operation is performed according to the offset indicated in the M _{LdpcAssembleTable1} matrix; if (M _{LdpcAssemble2} ) _i,j =0, no complement operation is required.

9.5 According to the M _LdpcOffset2 matrix, find the cyclic offset corresponding to the non-"-" element in the i-th row of the selected parity check matrix H, find the required starting position in the variable node vector q, and the required starting position Position = initial value position of variable node vector q + corresponding loop offset.

9.6 According to the M _LdpcRound4 matrix, find the number of cycles corresponding to the jth non-"-" element in the i-th row of the selected parity check matrix H, and place the starting value position of the result data in step 9.2 (M _LdpcRound4 ) _i,j *W Copy the data to the desired starting location found in step 9.5.

9.7 According to the required number of complements indicated by LdpcRemain, and then according to the offset indicated in the M _{LdpcAssembleTable1} matrix, supplement the remaining elements of the variable node vector q, and return to step 2.

The above is the LDPC encoding and decoding method in this application.

The theory of LDPC coding and decoding is relatively mature, but because LDPC code is a linear block code with a large code length n, the check matrix H is also large, and the algorithm complexity is very high. The traditional LDPC coding and decoding methods cannot be very good. Meeting the throughput requirements of the IEEE 802.11n system greatly affects the performance of the system. The implementation of LDPC codes in existing high-speed wireless local area network systems is mostly based on FPGA chips and DSP chips. Although the previous methods can meet the processing and delay requirements of modern high-speed wireless LAN protocols, FPGA programming and professional DSP are relatively complicated, lacking a rich programming environment and debugging tools, and the applicability is average. Based on the GPP chip, developers can use ordinary computers to develop with rich tools in a familiar structure and environment, such as C/C++ environment. The innovation of this patent is to optimize the encoding and decoding method according to the characteristics of the GPP chip under the condition of using the original codec for the LDPC code in the high-speed wireless LAN system on the GPP chip. Since the LDPC code of IEEE802.11n is a non-regular LDPC code, the number of non-negative values in each row of the check matrix prototype is not necessarily the same. Therefore, compared with the previous LDPC code encoding and decoding implementation methods, the flexibility of the GPP chip will be great. Advantage. In addition, considering the rapid development of the CPU (Central Processing Unit, central processing unit), the data processing capability of the GPP chip will also continue to improve.

First, the parallel processing of data is realized by using SIMD instructions. SIMD instruction set, also can be referred to as SSE (Streaming SIMD Extensions, instruction set) instruction set on the Intel CPU adopted in this patent, its essential principle is to process a plurality of data in one clock cycle of CPU to obtain parallel The effect of processing, unlike ordinary usage - only one data processing operation per clock cycle. For the CPU of the Nehalem architecture, its processing bit width is 128 bits, and for the CPU of the Sandy Bridge architecture, its processing bit width is 256 bits, that is, for 8-bit specific points, the former can process 16 data in one instruction cycle Processing, the latter can process 32 data in one instruction cycle, theoretically speaking, the degree of parallelism is 16 times parallelism and 32 times parallelism respectively. However, through the actual program simulation results, it can be known that the ideal parallel multiple is often not achieved during the actual system operation. On the one hand, the program is not completely composed of data operation processes, and also includes a large number of judgment statements, and these judgments Statements cannot be operated in parallel. On the other hand, if a 128-bit wide SIMD instruction is used, for the parity check matrix of the IEEE 802.11n standard, the size of each sub-matrix is not a multiple of 16, so the parallelism of the last group of data processing for each sub-matrix is less than 16 of.

Secondly, by using the lookup table method, that is, initializing multiple known parameters, and marking the specific location of the required data with the offset method, the memory is exchanged for the computational complexity, and the data processing speed of the LDPC encoding and decoding method is improved. In the LDPC code encoder, the block matrix required for encoding under different code rates and code lengths can be calculated in advance and stored in LUTs (Look-Up-Table, look-up table), as long as the program starts to run The table can be read in without repeated calculations.

Finally, a multi-threading method is adopted to execute more than one thread at the same time, thereby improving the overall processing performance of the system. In the LDPC optimized encoding and decoding method, the multi-thread method is used to optimize the operation with one line of data in the check matrix as the unit, and the number of threads is the number of rows of the check matrix.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included in the present invention. within the scope of protection.

Claims (12)

1. a kind of LDPC encoding method based on general processor, comprising: obtain the signal vector S to be encoded by signal acquisition or receiving, determine parity check matrix H and block matrix A, B, D, E, F and T thereof, and save it; according to Determine the vectors p ₁ and p ₂ , and obtain the encoding result vector c=(S, p ₁ , p ₂ ) of LDPC; it is characterized in that any matrix and any vector performed when the vectors p ₁ and p ₂ are determined The multiplication process includes: Taking each row of the arbitrary matrix as a thread, performing the multiplication operation of the corresponding row of the matrix and the arbitrary vector, and combining the multiplication results of all rows to form a result vector; Wherein, the multiplication operation of each row of any matrix and any vector includes: determining the initial position of the vector corresponding to each element j in the current ith row of the matrix=the initial position of any vector+ A _{i, j} + (j-1) * Z, the data of ZA _{i, j} length from the starting position in any vector is left-shifted by means of single instruction multiple data stream SIMD, and After the data of the length of A _{i, j} before the starting position is moved to the left-shifted data, the vector shift result corresponding to the element j is obtained; and then the vector shift result corresponding to each element is added , as the multiplication result of each row and any vector; In the SIMD method, the data of ZA _i,j length from the starting position is divided into units of length W segment, yes Parallel left shift operation is performed on segment data, and then left shift operation is performed on the remaining (ZA _{i, j} ) mod W length data; Z is the size of a sub-matrix represented by an element in the parity check matrix. 2. The method according to claim 1, characterized in that, when the arbitrary matrix is T ^-1 , when each row of the T ^-1 is multiplied with the corresponding vector, only T ^-1 is taken Multiply the element with a value of 0 by the corresponding vector to obtain the vector shift result corresponding to the element with a value of 0, and set the vector shift result corresponding to the remaining elements to a zero vector; then shift the vector corresponding to each element The results are added as the result of multiplying each row by the either vector. 3. The method according to claim 1 or 2, characterized in that, taking the first Z data as valid data after performing a left shift operation on W segments of data simultaneously. 4. The method according to claim 1 or 2, wherein said adding the vector shift results corresponding to each element comprises: dividing the vector shift results corresponding to each element into segment, via SIMD pair The segment data is added in parallel, and then the remaining (ZA _i,j ) mod W length data is added. 5. The method according to claim 1 or 2, wherein said matrices A, B, D, E, F and T ^-1 are stored by a linear lookup table. 6. A kind of LDPC decoding method based on general-purpose processor, comprising: receive encoded LDPC code word signal c, determine parity check matrix H; Calculate variable node vector q as decoding result by multiple iterations, when each iteration , calculate the temporary variable vector according to the current variable node vector q and check node vector r as And update the check node vector r according to the temporary variable vector t, and then update the variable node vector q according to the check node vector r and the temporary variable vector t as During the first iteration, the codeword signal c is used as the variable node vector q, and the check node vector r is set to 0; it is characterized in that, When calculating the temporary variable vector t, the check node vector r and the variable node vector q each iteration, each row of the check matrix is used as a thread for operation and update, and the vectors t, q and r corresponding to each row are obtained. index number from where i is the row index of the parity check matrix, corresponding to the i-th row of the parity check matrix when calculating the subvectors corresponding to the temporary variable vector t, the check node vector r and the variable node vector q, according to the check Each non-"-" element H _{i, j} in the row of the matrix corresponds to the index number corresponding to the element H _{i, j} in the calculation vectors t, q and r from The subvectors of , and then sequentially connected to obtain the subvectors corresponding to each row, when i=1, let V _{LdpcRowLength} (v) is the number of each row of non-"-" elements in the check matrix; The way to calculate the temporary variable vector t sub-vector corresponding to H _{i ,j} is: determine the vector starting position Z*(n-1)+H _i,n corresponding to H i,j, and set the vector q corresponding to row i The length from the starting position in the subvector is or 6 data is copied to the beginning of the temporary variable vector t subvector corresponding to H _{i, j} by means of SIMD; when H _{i, n} ≠ 0, H _{i, n} ≠ '-' and (ZH _{i, n} )mod When W≠0, determine the value of each element in the row corresponding to check matrix element H _i,j in matrix M _{LdpcAssemble1} And the index number in the subvector of the current vector q corresponding to the element H _{i, j} is Each element of is copied to the current position of the temporary variable vector t sub-vector corresponding to H _{i, j} in turn; then determine the second vector starting position M _LdpcOffset2 corresponding to each element H _{i, j} , and set the second vector The length from the starting position is The data of is copied to the current position of the temporary variable vector t subvector corresponding to H _i,j by means of SIMD; take the first Z bits in the temporary variable vector t subvector corresponding to H _i,j and take the absolute value as An effective subvector of the temporary variable vector t corresponding to H _{i, j} ; wherein, M _{LdpcAssemble1} is one of the complementary offset flag bits calculated according to the check matrix, and M _LdpcOffset2 is calculated according to the check matrix One of the cycle offsets of When H _i,n ≠0, H _i,n ≠'-' and (ZH _i,n )mod W≠0, When H _i,n =0 or H _i,n ='-' or (ZH _i,n )mod W=0, (M _LdpcOffset2 ) _i,j =Z*(n-1); K is the amount of data that can be handled by a general-purpose processor at one time, and k is the basic unit size of SIMD processing; when code length L _LDPC =648, LdpcRemain=11; when code length L _LDPC =1296, LdpcRemain=6; when code length L When _LDPC =1944, LdpcRemain=1; j is the index of each non-"-" element in the i-th row in all non-"-" elements in the row, and n is the j-th non-"-" element in the i-th row Column index in check matrix. 7. The method according to claim 6, wherein the mode of calculating the check node vector r subvector corresponding to each row of the check matrix is: Write the temporary variable vector t subvector corresponding to each row of the check matrix as V _{LdpcRowLength} (v) rows and A matrix T _v of columns, wherein each row of the matrix T _v is a sub-vector corresponding to the element H _{i, j} in the sub-vector of the temporary variable vector t, and when the number of columns is not enough, a complement is performed; Carrying out the most value assignment to the matrix T _v to obtain the most value variable vector m subvector matrix M _v ; Calculate the intermediate variable vector s subvector matrix S _{v according to the matrix T v ;} According to the element with the same index value in the matrix _{Mv and the matrix Sv, determine the element value of the corresponding index value in an intermediate matrix Rv ' ;} wherein, if any element in the matrix _Sv is less than 0, then Take the complement of any element and add it to any element, and use the addition result as the value of the element in the matrix R _v ' that is the same as the index value of any element in the matrix; if any of the matrix S _v If the element is equal to 0, add any element to 0, and use the addition result as the value of the element in the matrix R _v that is the same as the index value of any element in the matrix; if any element in the matrix S _v > 0 , then take the same element as the index value of any element in the matrix M _v and add it to any element, and use the result of the addition as the value of the element same as the index value of any element in the matrix R _v Value; the operation of comparing any element in the matrix S _v with 0 and the operation of adding are carried out by means of SIMD; Subtract the matrix R _v ' from the elements with the same index value in the matrix T _v by means of SIMD, and use the result as the element value of the same index value in the check node vector r subvector matrix R _v ; the matrix R The first Z elements of each row in _v are sequentially read out to form the check node vector r subvector in a row-first manner. 8. The method according to claim 7, wherein said carrying out the most value distribution comprises: Determine the minimum value and the second minimum value of each column in the matrix T _v and the row index corresponding to the minimum value by means of SIMD; modify the obtained minimum value and the second minimum value, and subtract the preset correction value β, When the corrected minimum and second minimum values are less than 0, set it to 0, otherwise keep it unchanged; According to the current minimum value of each column in the matrix T _v , the second minimum value and the row index corresponding to the minimum value, construct the column of the same index in the most value variable vector m subvector matrix M _v , wherein, in any column of M _v , set the element corresponding to the same row index as the current minimum value as the determined minimum value, and set the remaining elements as the next smallest value. 9. The method according to claim 8, wherein the method of determining the minimum value and the second minimum value of each column and the corresponding row index by means of SIMD comprises: Divide each row element of the matrix T _v into sub-blocks, each sub-block includes W basic units; when comparing the elements of any two rows in the matrix T _v , W basic units are compared at one time by means of SIMD. 10. method according to claim 7, is characterized in that, described calculation intermediate variable vector s subvector matrix S _v comprises: For each column in the matrix T _v , perform an XOR operation on all the elements in the column, then XOR the result with the elements in the i'th row and then perform an OR operation with 0x7f, and use the OR operation result as the same as in the intermediate vector matrix S _v The i'th row element of the index column; wherein, each row element of the matrix T _v is divided into sub-blocks, each sub-block includes W basic units, when performing XOR/OR operations, the XOR/OR operations of W basic units are performed at one time through SIMD, and the i'th row represents the current row. 11. The method according to claim 6, wherein calculating the variable node vector q sub-vector corresponding to H _i,j comprises: Determine the vector starting position Z*(n-1)+H _i,n corresponding to H _{i,j ,} and use the SIMD method to connect the temporary variable vector t subvector corresponding to H _i,j to the check node corresponding to H i,j The vector r sub-vectors are added, and the length from the starting position in the result vector is or 5 data is copied to the beginning of the variable node vector q subvector corresponding to H _i,j by means of SIMD; when H _i,n ≠0, H _i,n ≠'-' and (ZH _i,n ) mod When W≠0, determine the value of each element in the row corresponding to check matrix element H _i,j in matrix M _{LdpcAssemble1} And the index number in the subvector of the current vector q corresponding to the element H _{i, j} is Each element of is copied to the current position of the variable node vector q sub-vector corresponding to H _{i, j} in turn; Determine the second vector starting position M _LdpcOffset2 corresponding to each element H _i,j , and set the length from the starting position of the second vector to 0 or The data of is copied to the current position of the variable node vector q sub-vector corresponding to H _i,j through SIMD; According to the number of supplementary positions indicated by LdpcRemain, supplementary positions are performed according to the value of the element in the row corresponding to the check matrix element H _{i, j} in M _{LdpcAssemble1} . 12. The method according to any one of claims 6 to 11, characterized in that the vector starting position Z*(n-1)+H _{i , n} and The starting position of the second vector M _LdpcOffset2 , the matrix M _{LdpcAssemble1} , and the vectors V _{LdpcRowLength} , M _{LdpcAssemble1} , and LdpcRemain constituted by the number of non-"-" elements in each row in the parity check matrix.