CN110504995A - Soft output MIMO detection method based on lattice reduction and K-Best - Google Patents

Abstract

A kind of soft output MIMO detection method based on lattice reduction and K-Best carries out Cholesky decomposition to the channel matrix of mimo system and lattice reduction is handled, while converting received vector.Breadth First tree, which is carried out, in lattice domain searches for the expansion mode, it is specified that child node.The candidate list that tree search obtains is converted back into constellation point domain by lattice domain, and size is measured into each path by path and is ranked up, calculates each bit soft information to complete signal detection.The present invention has further reduced the gap of detection algorithm Yu optimal MIMO detection performance with lower delay, computation complexity and storage demand.

Description

Lattice reduction and K-Best based soft output MIMO detection method

Technical Field

The invention belongs to the technical field of Multiple Input Multiple Output (MIMO) transmission, and particularly relates to a MIMO detection method based on lattice reduction and K-Best tree search.

Background

The development of mobile communication facilitates life, wherein Multiple Input Multiple Output (MIMO) technology employs Multiple transmit/receive antennas, so as to increase system throughput and reliability without additional spectrum resources. MIMO in communication systems is becoming larger and larger in order to achieve higher data transmission rates and better device accessibility. The technical standard of the wireless local area network is developed from first generation 802.11 in 1997 to 802.11ac proposed in 2012, the data transmission rate is developed from 2Mbps to 6993Mbps, and the antenna scale is also developed from 1 transmission and 1 reception to 8 transmission and 8 reception. Wireless communication technologies have evolved from 3G to 5G, again beginning to support up to 8 transmit antennas. The principle is that the multipath scattering effect of the receiving end and the transmitting end channels is utilized, and the method can be divided into two types: one type, known as spatial diversity, focuses on suppressing signal fading and improving the reliability of communications. In most wireless communication systems, the received signal strength varies with time, i.e., signal fading, which causes the bit error rate to increase, and seriously affects the communication performance. MIMO uses multiple antennas to transmit and receive multiple copies of the same information, and if the distance between each antenna is greater than half a wavelength, the information copies can be considered to reach the receiving end through multiple independent paths, and their fading is independent. The greater the number of paths, the lower the probability that these copies of information will fade simultaneously, and by combining the received copies, the effect of fading can be reduced. Another class is called spatial multiplexing, which is also the direction of application of the current mainstream. Spatial multiplexing is similar to frequency division multiplexing and time division multiplexing, but the two mechanisms are to allocate a plurality of signals to different frequencies or time slices, and the spatial multiplexing simultaneously uses a plurality of antennas to send a plurality of different sub-data streams at a transmitting end, and allocates the signals to different paths, and the different paths can simultaneously use the same frequency spectrum resource, thereby improving the frequency spectrum utilization efficiency and increasing the data transmission rate.

In an MIMO system, a transmitting end carries out channel coding on an original bit stream, reduces the correlation between transmitting bits through interleaving, carries out modulation according to constellation mapping to obtain a corresponding complex symbol, and finally carries out M-ary channel coding on the complex symbol_tThe root antenna is launched. At the receiving end, M_rReceiving and transmitting by root antennaAfter vector launching, a channel matrix is obtained according to information estimation such as pilot frequency, an original launching vector is restored by a detection module according to the estimated channel matrix and a receiving vector, and then a receiving bit stream is obtained after demodulation, deinterleaving and decoding. The detection algorithm directly affects the performance of the MIMO system, and is one of the key technologies for applying MIMO. However, as the antenna scale increases, the complexity index of the MIMO detection algorithm increases, and it is of great significance to provide a high-performance and low-complexity detection algorithm and its implementation. The detection algorithm can be classified into an optimal detection algorithm, a linear detection algorithm and a nonlinear detection algorithm. The optimal detection algorithm comprises a maximum likelihood and maximum posterior probability detection algorithm. Such algorithms need to traverse all possible transmit vectors in the entire space and compute the path metrics corresponding to each transmit vector. For hard decision, the detection algorithm selects the minimum metric as the detection result; for soft decision, soft information is calculated according to all paths and output, and the soft information reflects the possibility that each bit is 0 or 1. The algorithm that examines all possible transmit vectors has the best performance, but it is very complex and difficult to apply practically. The linear detection algorithm eliminates the interference between signals by applying a linear filter to the received vector, and can be subdivided into a zero forcing method, a minimum mean square error method and the like according to different filter matrix selections. Although the linear detection has low complexity, the performance is poor, and the performance requirement of the next generation communication system is difficult to meet. The nonlinear algorithm is typically represented by a tree search algorithm, which can be subdivided into a breadth-first K-Best search and a fixed complexity decoding algorithm, and a depth-first single tree search algorithm. The depth-first search throughput rate is not fixed and is not suitable for hardware implementation. The breadth-first search has fixed computational complexity and delay, and can achieve near-optimal performance, but the breadth-first search also faces a larger challenge in complexity and needs to be optimized in aspects of algorithm design, hardware implementation and the like.

Liu Liang et al of Longde university, in "Low-complexity likelihood information generation for spatial-multiplexing MIMO signal detection soft information calculation mode" published by IEEE Transactions on temporal Technology 2012, 61(2):607-617 ", proposes an unbalanced sub-node expansion strategy and a Low-complexity soft information calculation mode based on a fixed complexity decoding algorithm, reduces algorithm complexity, and is suitable for 4 × 4-scale 64-QAM modulated MIMO systems.

A lattice reduction is introduced to carry out preprocessing on the basis of traditional K-Best detection by a Huangyuan luxury team of Chinese university in Taiwan, IEEE trans. VLSI Syst, 2014,22(12): 2675-one 2688, wherein the A3.1 Gb/s 8 × 8 software Reduced K-Best Detector With lattice reduction and QR reduction is a 3.1Gb/s 8 × 8 scale Sorting optimized K-Best Detector based on lattice reduction and QR Decomposition, and the orthogonality of a channel matrix is improved by using the lattice reduction, so that the number of paths required to be reserved by the K-Best is Reduced. But the selection of each layer of survivor nodes still needs to be sequenced, and more comparators are consumed; sorting QR decomposition is adopted, so that delay is large, and a certain influence is brought to throughput; due to the adoption of the K-Best algorithm of hard decision, certain gap exists between the performance and the optimal detection.

Disclosure of Invention

In order to overcome the defects of the prior art, the invention aims to provide a near-optimal low-complexity MIMO detection method based on lattice reduction and K-Best tree search, which reduces the complexity of a detection algorithm and reduces the storage of data while ensuring the detection performance.

The technical solution of the invention is as follows:

a soft output MIMO detection method based on lattice reduction and K-Best is characterized by comprising the following steps:

step 1) carrying out lattice reduction transformation on a channel matrix H in a multi-input multi-output MIMO system y ═ Hx + nAnd Cholesky decompositionWherein, T is a complex integer unimodular matrix R is an upper triangular matrix, Q is a unitary matrix, n is a obedient mean value of 0, and variance isIs σ²With a noise energy of N₀＝σ²X is a transmission vector, y is a reception vector, and the number of transmission antennas of the MIMO system is M_tLayer, receiving antenna number M_rA layer;

step 2) carrying out translation, scaling and projection transformation on the received vector y, wherein the formula is as follows:

wherein j represents an imaginary unit, i.e., j²＝1；

Step 3) carrying out breadth-first tree search in the lattice domain to obtain a candidate path;

step 4) converting the candidate path obtained in the step 3) from the lattice domain to the constellation point domain:

1 st path is according to S₁＝2TZ₁+1j +1 conversion, 2 nd to K th path according to S_k＝S₁+2TZ_kConversion, S_iFor the ith path constellation point domain, Z₁Is a complex vector corresponding to the 1 st path in the lattice domain, when K is more than or equal to 2 and less than or equal to K, Z is_kThe difference between the k-th path complex vector and the 1 st path;

step 5) sorting the candidate paths of the constellation point domain obtained in the step 4 according to the measurement size;

and 6) calculating soft information of each bit according to the metric difference between each sequenced path and the optimal path.

Step 3) performing breadth-first tree search in the lattice domain to obtain candidate paths: taking the first path as a reference path, storing the complete metric value, storing the difference value between the rest paths and the first path, and recording the value representing the node path in the form of the difference value as res_k；

Step 3.1 calculate res for each path_kThe formula is as follows:

wherein z is_iIs an estimate of the transmitted symbol of the i-th layer, z_i＝res_k/R_i，i，R_i,jFor the ith row and jth column element of the R matrix,the jth node value for the kth path;

step 3.2 calculate for each path a bounding z_iEnumerate a number N_i，kThe child nodes and calculates the branch metric e of each path_iAnd partial path metric P_iThe formula is as follows:

P_i(xⁱ)＝P_i+1(xⁱ⁺¹)+e_i(xⁱ)。

3.3, selecting K survivor nodes as father nodes of the next layer;

step 3.4 makes i-1 and repeats steps 3.1-3.3 until i-1.

In the step 3), the surviving nodes in each layer are selected without sorting, and partial paths with the lowest paths are directly selected as child nodes; and then the rest child nodes are subjected to grouping comparison, and the child node with the minimum measurement is selected from each group.

Said step 3.3) for the M-th_rLayer, K4, for mth_rLayer 1, receiving 4 father nodes, expanding 12 son nodes, selecting 10 reservations with minimum measurement, Mth_rLayer 2 to the first, receive 10 parent nodes, expand 15 child nodes and select 10 reservations.

The step 6) of calculating the soft information of each bit specifically includes:

step 6.1) calculates all possible absolute values of soft information, for i ═ 1, 2, … K

In the formula, λ_iThe path metric corresponding to the ith path in the candidate list is MAX _ LLR which is a given constant value of 1 and is the upper limit of the soft information value;

step 6.2) calculating soft information of the b bit of the ith transmitting symbol, wherein the formula is as follows:

wherein m is the first (i, b) bit of the 2-K paths andthe opposite path.

Compared with the prior art, the invention has the following technical effects:

the soft output MIMO detection method based on the lattice reduction and the K-Best can further approach the optimal detection performance; the survival nodes of each layer are determined by pre-selection and grouping comparison instead of sequencing the path metrics, so that the delay and the computational complexity are reduced; the path node value is represented in a difference value form, the bit width required by the difference value is low, and the storage required by hardware implementation is reduced; the intermediate result of the soft information is calculated through 1-time sequencing and a small amount of subtraction, the soft information is calculated by selecting the corresponding intermediate result and symbol according to the bit value, and compared with the traditional mode that each bit of soft information needs 1-time minimum value solving and 1-time subtraction, the method saves the calculation resources.

Drawings

FIG. 1 is a flowchart of the steps of the soft output MIMO detection based on lattice reduction and K-Best of the present invention

FIG. 2 is a diagram illustrating the selection strategy for node expansion of each layer in the tree search process according to the present invention

FIG. 3 is a sub-node enumeration strategy in the tree search process of the present invention

Fig. 4 is a graph comparing bit error rate performance of a soft output MIMO detection method based on lattice reduction and K-Best according to the present invention with other low complexity detection methods.

Detailed Description

The method of the present invention is described in further detail below with reference to the accompanying drawings, which show detailed embodiments and modes of operation.

Fig. 1 is a flowchart illustrating steps of a soft output MIMO detection method based on lattice reduction and K-Best according to the present invention. As shown in fig. 1, the method for supporting the maximum antenna configuration of 8 × 8 scale specifically includes the following steps:

firstly, carrying out QR decomposition and lattice reduction processing on a channel matrix H of a multi-input multi-output MIMO system;

considering the number of transmitting antennas as M_tLayer, receiving antenna number M_rA MIMO system of layers. Assuming the number of transmitting antennas M_tAnd the number of receiving antennas M_rAll 8, the MIMO system model can be expressed as: y is Hx + n

Complex vector x ═ x₁ x₂ ... x₈]^TEach component is a complex symbol obtained by modulating according to constellation mapping; complex vector y ═ y₁ y₂ ... y₈]^TIs a receive vector for the MIMO detector; h is a channel matrix with dimensions of 8 × 8; n ═ n₁ n₂ ... n₈]^TFor a Gaussian-distributed noise vector, each component is independently subjected to a mean of 0 and a variance of σ²Gaussian distribution of (1), noise energy of N₀＝σ²。

Carrying out lattice reduction and Cholesky decomposition on the channel matrix H to obtainWherein T is an unimodular matrix which records the change of rows and columns and has complex integers of elements.

The channel matrix H and the received vector y are preprocessed to improve detection performance. Lattice reduction transformation is carried out on the channel matrix to obtain a transformed matrixWherein, the elements of T are complex integers, which are used for storing the transformation process, and Cholesky decomposition is adopted to obtain Q, R matrix，Likewise for the transformation of the received vector y

Second, transform the received vector y, order

Wherein Q isUnitary matrix of the domain, R beingAn upper triangular matrix of domains.

And thirdly, preferentially performing tree search in the lattice domain according to the breadth, searching from the 8 th layer to the 1 st layer, expanding child nodes with different numbers for all father nodes of different layers, and reserving expanded nodes with different numbers: the 1 st layer is expanded and reserved with 4 nodes, the other layers are reserved with K equal to 10 nodes, and the number of the first layer (leaf nodes) is 10.

And then, the detection data enters an MIMO detection module, and breadth-first K-Best tree search is carried out on the transformed lattice domain, wherein the search comprises the expansion of child nodes and the selection mode of survival nodes.

The child node expansion mode is carried out according to the following modes:

layer 8 unfolds 4 child nodes and all remain. The 4 father nodes on the 7 th layer enumerate 4, 3 and 2 child nodes in sequence, and directly reserve a first child node, a second child node, a first child node, a second child node and a first child node from the first to the third child nodes respectively, wherein the first child node, the second child node and the first child node respectively correspond to the father nodes 1-8 on the next layer; the rest child nodes are marked as R1, R2, R3 and R4 according to the sequence of the parent nodes, the smaller child node is selected from R1 and R4 to be reserved as the parent node 9 of the next layer, and the smaller child node is selected from R2 and R3 to be reserved as the parent node 10 of the next layer; a total of 10 child nodes are reserved at layer 7. In layers 6 to 1, the first 5 father nodes of each layer enumerate 2 child nodes, and the last 5 father nodes enumerate 1 child node; directly reserving first child nodes of the first 5 father nodes, and respectively corresponding to father nodes 1 to 5 of the next layer; the remaining nodes are marked as R1, R2., (R10) according to the parent node sequence, and smaller child nodes are selected from (R1, R10), (R2, R9., (R5, R6) to be reserved, and correspond to 6 th-10 th parent nodes of the next layer.

Further, the node value of the first path corresponds to a complete transmission vector; the node values of the remaining paths are represented as difference values from the first path, which correspond to the sum of the path 1 node values for 1 complete transmit vector.

The computation and update of the partial path metric is performed by:

the invention takes the first path as a reference, stores the complete value, and calculates the difference res between the kth path and the first path_k

Wherein,the j node value of the kth path, R is an upper triangular matrix output after preprocessing,low bit width, less possible values, calculation for given R_i，jCalculation of R_i，jz^k _jAll possible results of (a) are stored in a look-up table, which is shared by K paths, according to its node value z^k _jSelecting corresponding R_i，jZ^k _jThe result is used to calculate res_k. Immediately after calculating z_i＝res_k/R_i，iAs z_iAround z_iThe four lattice points of (1) are 4 child nodes and are according to z_iDetermining the sequence of the child nodes, and calculating branch metrics corresponding to the child nodes:

and updating partial path metrics of paths corresponding to each child node: p_i(xⁱ)＝P_i+1(xⁱ⁺¹)+e_i(xⁱ)。

And sequencing the path metrics in the obtained candidate list and calculating to update the bit soft information. Firstly, the k-th path is converted from a lattice domain to a constellation point domain by the following formula:

Z_ithe ith path vector obtained for the lattice field. Path 1 has the smallest metric λ^MLCorresponds to x^ML. Path metrics of 2 nd to K th_kAnd (4) increasing. When calculating soft information, calculating an intermediate result:

here, MAX _ LLR is the upper limit value of LLR, λ, set^MLAnd the path metric corresponding to the first path. The soft information value for the b-th bit of the ith transmit symbol is:

where m is the first (i, b) bit of the 2-K paths andthe opposite path; if the (i, b) th bits of the 2-K paths are all ANDLikewise, m is taken to be 1.

Specifically, the third step is as follows:

hypothesis algorithm inputIs introduced intoT, R, i layer k parent node enumerates N_i，kChild node, 1. ltoreq. N_i，kLess than or equal to 4. For each survivor path; i is initialized to 8 and detection starts from layer 8.

(1) For each path calculation

Calculating z_i＝res_k/R_i，iObtaining the estimated value of the transmitting symbol of the layer;

(2) calculate for each path around z_iEnumerate a number N_i，kThe child nodes and calculates the branch metric e of each path_iAnd partial path metric P_i：

P_i(xⁱ)＝P_i+1(xⁱ⁺¹)+e_i(xⁱ)。

(3) Selecting K survivor nodes from all the expanded child nodes as parent nodes of the next layer. For the 8 th layer, K is 4 and the other layers K is 10;

(4) repeating steps (1) - (3) with i ═ i-1.

(5) Execute (4) up to layer 1, i ═ 1.

The invention performs child node expansion in the lattice domain, as shown in FIG. 3, around z_iThe four lattice points of (2) are 4 child nodes. Wherein for z_iRounding to obtain the 1 st child node z₁(ii) a If z is_iAnd z₁The distance in the horizontal direction is greater than that in the vertical direction, then the 2 nd child node is z₁Adjacent grid point in horizontal direction, sub-node 3 is z₁A directional neighborhood grid; otherwise, the 3 rd child node is z₁Adjacent lattice point in horizontal direction, 2 nd child node is z₁A directional neighborhood grid; the 4 th child node has 3 candidates p1, p2 and p3, the probabilities of the candidates are 2/3, 1/6 and 1/6 in sequence, and the candidates are directly selectedGet z₁The lattice point p1 with the highest probability on the diagonal is the 4 th child node. Child nodes 1 to 4 and estimate z_iThe distance is increased progressively, and the metric of the corresponding path is also increased from small to large. Let the estimate z obtained for a layer_i1.7-i0.9, the 4 child nodes are [2-i1, 1-i1, 2-i0 and 1-i0 in sequence]. The selection of each layer of survivor nodes in tree search adopts a mode of pre-selection and grouping comparison, the selection strategy is shown in figure 2, the first and second child nodes with smaller measurement are pre-selected and directly reserved as the survivor nodes, and then every two of the rest nodes are divided into 1 group and the nodes with smaller measurement are selected and reserved.

Fourthly, converting K to 10 paths in the candidate list from the lattice domain to the constellation point domain, and converting the formula of the K paths into

And fifthly, sorting 10 paths from K in the paths in the candidate list according to the partial path metrics from big to small. After sorting, the 1 st path has the smallest metric λ^MLCorresponds to x^MLIf hard decision, x is adopted^MLThe result is the detection result; path metrics of 2 nd to K th_kAnd (4) increasing the number of times, and if soft decision is adopted, the method can be used for soft information calculation.

And sixthly, calculating soft information of each bit according to each path and the metric thereof sequenced in the fifth step. First all possible soft information absolute values are calculated, for i1, 2

Wherein λ_iMeasuring the path corresponding to the ith path in the candidate list; MAX _ LLR is 1 given a constant value, an upper limit for the soft information value. For soft information of the b bit of the ith transmission symbol, calculating

Where m is the first (i, b) bit of the 2-K paths andthe opposite path; if the (i, b) th bits of the 2-K paths are all ANDLikewise, m is taken to be 1.

FIG. 4 is a simulation result comparing the bit error rate performance of the signal detection method of the present invention with that of other detection methods. The simulation of the invention is based on a Matlab platform, the MIMO system antenna is configured to be 8 multiplied by 8 scale, the transmitting end adopts 64-QAM modulation, the code rate is 5/6, the polynomial is [ 131171 ] convolutional coding, BCJR decoding is used at the receiving end, and the channel model is AWGN channel.

As can be seen from fig. 4, the signal detection method of the present invention has BER of 10^-5The advantage on performance is obvious, and the performance is improved by 1.2dB compared with the existing detection algorithm based on lattice reduction; compared with an MMSE linear detection algorithm, the method is about 4.3dB earlier; it also differs by only 0.7dB compared to the optimal detection algorithm. The FSD algorithm performs better than the proposed algorithm after unfolding 8 × 8 × 4 × 2 paths into 512 paths, but it is too complex to implement. In general, the proposed algorithm has better performance on the premise of acceptable hardware complexity.

The invention uses the K-Best tree search method of soft output to reach the optimal detection performance; by simplifying the enumeration and selection strategies of the child nodes, the sequencing of each layer of the path metric by fixed complexity decoding, K-Best and other tree search methods is avoided; by using difference values to represent path node values, less bit width is required due to the lower range of difference values, thereby reducing storage requirements; by improving the soft information calculation mode, the soft information of a plurality of bits shares the intermediate calculation result, and the calculation redundancy is reduced. Therefore, the lattice reduction and K-Best based soft output MIMO detection method provided by the invention achieves near-optimal detection performance with lower delay and complexity.

Claims (5)

1. A soft output MIMO detection method based on lattice reduction and K-Best is characterized by comprising the following steps:

step 1) carrying out lattice reduction transformation on a channel matrix H in a multi-input multi-output MIMO system y ═ Hx + nAnd Cholesky decompositionWherein, T is a complex integer unimodular matrix R is an upper triangular matrix, Q is a unitary matrix, n is a obedient mean value of 0, and variance is sigma²With a noise energy of N_o＝σ²X is a transmission vector, y is a reception vector, and the number of transmission antennas of the MIMO system is M_tLayer, receiving antenna number M_rA layer;

step 2) carrying out translation, scaling and projection transformation on the received vector y, wherein the formula is as follows:

wherein j represents an imaginary unit, i.e., j²＝1；

Step 3) carrying out breadth-first tree search in the lattice domain to obtain a candidate path;

step 4) converting the candidate path obtained in the step 3) from the lattice domain to the constellation point domain:

1 st path is according to S₁＝2TZ₁+1j +1 conversion, 2 nd to K th path according to S_k＝S₁+2TZ_kConversion, S_iFor the ith path constellation point domain, Z₁Is a complex vector corresponding to the 1 st path in the lattice domain, when K is more than or equal to 2 and less than or equal to K, Z is_kThe difference between the k-th path complex vector and the 1 st path;

step 5) sorting the candidate paths of the constellation point domain obtained in the step 4 according to the measurement size;

and 6) calculating soft information of each bit according to the metric difference between each sequenced path and the optimal path.

2. The lattice reduction and K-Best based soft output MIMO detection method according to claim 1, wherein said step 3) performs breadth first tree search in lattice domain to obtain candidate paths: taking the first path as a reference path, storing the complete metric value, storing the difference value between the rest paths and the first path, and recording the value representing the node path in the form of the difference value as res_k；

Step 3.1 calculate res for each path_kThe formula is as follows:

wherein z is_iIs an estimate of the transmitted symbol of the i-th layer, z_i＝res_k/R_i，i，R_i,jFor the ith row and jth column element of the R matrix,the jth node value for the kth path;

step 3.2 calculate for each path a bounding z_iEnumerate a number N_i，kThe child nodes and calculates the branch metric e of each path_iAnd partial path metric P_iThe formula is as follows:

P_i(xⁱ)＝P_i+1(xⁱ⁺¹)+e_i(xⁱ)。

3.3, selecting K survivor nodes as father nodes of the next layer;

step 3.4 makes i-1 and repeats steps 3.1-3.3 until i-1.

3. The lattice reduction and K-Best based soft output MIMO detection method according to claim 1, wherein in step 3), the surviving nodes in each layer are selected without sorting, and the node with the lowest partial path is directly selected as the child node; and then the rest child nodes are subjected to grouping comparison, and the child node with the minimum measurement is selected from each group.

4. The lattice reduction and K-Best based soft output MIMO detection method of claim 2, wherein: said step 3.3) for the M-th_rLayer, K4, for mth_rLayer 1, receiving 4 father nodes, expanding 12 son nodes, selecting 10 reservations with minimum measurement, Mth_rLayer 2 to the first, receive 10 parent nodes, expand 15 child nodes and select 10 reservations.

5. The lattice reduction and K-Best based soft output MIMO detection method of claim 1, wherein: the step 6) of calculating the soft information of each bit specifically includes:

step 6.1) calculates all possible absolute values of soft information, for i ═ 1, 2, … K

In the formula, λ_iThe path metric corresponding to the ith path in the candidate list is MAX _ LLR which is a given constant value of 1 and is the upper limit of the soft information value;

step 6.2) calculating soft information of the b bit of the ith transmitting symbol, wherein the formula is as follows:

wherein m is the first (i, b) bit of the 2-K paths andthe opposite path.