Methods for reducing complexity of pre-coding matrix computation and grouping of user equipments in massive MIMO systems

Abstract

This invention presents methods for using spatial FFT to reduce the number of computations for generating the pre-coding matrix in a MIMO system comprising reducing the dimension of channel vectors by neglecting entries whose values are significantly smaller or near zero, and to select UEs into a group assigned to the same time and frequency resources.

Claims

1. A method for Multiple-Input Multiple Output (MIMO) systems comprising computing a MIMO pre-coding matrix, and reducing the dimension of channel vectors by neglecting entries whose values are significantly smaller or near zero in order to reduce the complexity of the MEMO pre-coding matrix computation, wherein said reducing the dimension of channel vectors further comprises using spatial Fast Fourier Transform (FFT) to map signals at a MIMO BS to N.sub.a major angles that capture most of the signal power wherein N.sub.a is less than the number of antennas M; and in the subsequent signal processing, only signals that fall in the bins of these major angles are included.

2. The method of claim 1 wherein the spatial FFT process is implemented in the digital-domain comprising processing the received signals at BS antennas using a bandpass filter and an Analog-to-Digital Converter to obtain digital samples; transforming the digital samples using a spatial FFT block; and using the output of the spatial FFT block as virtual BS antennas.

3. The method of claim 2 further comprising performing baseband signal processing on the signals associated with the virtual BS antennas.

4. The method of claim 1 further comprising implementing the spatial FFT process in the Radio Frequency (RF) domain.

5. The method of claim 4 wherein a Butler matrix is used to perform FFT in the RF domain.

6. The method of claim 1 further comprising implementing the spatial FFT process using a digital radix FFT block combined with a Butler matrix.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows the system model of a massive MIMO system.

(2) FIG. 2 shows the received signals at massive MIMO antennas before the spatial FFT block for an example.

(3) FIG. 3 shows the received signals at massive MIMO antennas after the spatial FFT block for an example.

(4) FIG. 4 shows the block diagram of a receiver of a massive MIMO BS with the spatial FFT block.

(5) FIG. 5 shows the block diagram of a receiver of a massive MIMO BS with the Butler matrix blocks and the radix spatial FFT block.

(6) FIG. 6 shows the process of pre-coding computation with the spatial FFT block.

(7) FIG. 7 shows the process of computing the correlation coefficient between two UEs.

(8) FIG. 8 shows the process of transmission of multi-user data streams at a massive MIMO BS with the spatial FFT block.

(9) FIG. 9 shows the process of UE grouping.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

(10) Reference may now be made to the drawings wherein like numerals refer to like parts throughout. Exemplary embodiments of the invention may now be described. The exemplary embodiments are provided to illustrate aspects of the invention and should not be construed as limiting the scope of the invention. When the exemplary embodiments are described with reference to block diagrams or flowcharts, each block may represent a method step or an apparatus element for performing the method step. Depending upon the implementation, the corresponding apparatus element may be configured in hardware, software, firmware or combinations thereof.

(11) The system model of the massive MIMO system is shown in FIG. 1, where a BS 1 with a large number of antennas serves many UEs 2 at the same time-frequency resource. For the sake of simplicity, single-antenna UEs are assumed below. However, this invention can be easily generalized to the case of multiple-antenna UEs.

(12) The reason that the massive MIMO system is able to achieve high throughput is to enable signals from the BS antennas adding up constructively at the desired UEs, which requires accurate estimation of the channels between UEs and the BS antennas. Let h.sub.k,m denote the channel between the kth UE and the mth BS antenna. The BS estimates the channels between each antenna and each UE. Assume that the channel matrix between the BS and UEs is denoted by a KM matrix H with the entry on the kth row and the mth column being h.sub.k,m, where k=1, . . . , K, and m=1, . . . , M.

(13) The ZF pre-coding algorithm is an efficient linear pre-coding algorithm to achieve the performance close to the theoretical capacity of a massive MIMO system. Let s=[s.sub.1, . . . , s.sub.K].sup.T be the information signal vector from the BS and y=[y.sub.1, . . . , y.sub.M].sup.T be the received signal at the UEs, where s.sub.k is the data symbol intended for the kth UE and y.sub.k is the received signal at the kth UE. Let the MK pre-coding matrix be G, then the input output relation is
y=HGs.(1)

(14) For the ZF pre-coding algorithm, G is evaluated as
G=H.sup.H(HH.sup.H).sup.1(2)

(15) It can be shown that with the ZF pre-coding, the product of HG is a diagonal matrix, indicating that no interference is among the served UEs.

(16) The G matrix needs to be calculated within the channel coherence time. Note that given the estimation of H, the computation of G includes three steps, which are listed below.

(17) Step 1: The computation of W=HH.sup.H;

(18) Step 2: The computation of W.sup.1;

(19) Step 3: The computation of H.sup.HW.sup.1.

(20) Since is H a KM matrix, the complexity levels of Step 1 and Step 3 above are both O(MK.sup.2). The complexity level of Step 2 above is O(K.sup.3). Note that in massive MIMO systems, the value of M is always much larger than K, e.g., M=512, and K=32. Therefore, the complexity levels of Step 1 and Step 3 are the bottleneck of pre-coding computation.

(21) The rest of this invention focuses on methods for reducing the computations of Step 1 and Step 3. One embodiment of this invention is to use spatial FFT to reduce the dimension of the row vectors of H. The entry of W on the ith row and the jth row is evaluated as W.sub.i,j=h.sub.ih.sub.j.sup.H=.sub.m=1.sup.Mh.sub.i,mh.sub.j,m*, where h.sub.k,m is the channel between the kth UE and the mth BS antenna. With spatial FFT, the dimension of the kth row of H, h.sub.k, can be reduced because many entries of h.sub.k are near zero. Then, when computing W, these entries with near zero values can be neglected, so the number of multiplications can be reduced to speed up the process of Step 1.

(22) Principle of Spatial Fast Fourier Transform

(23) The received signals arrive at a massive MIMO BS with limited angles, and the number of major angles N.sub.a, i.e., angles that capture the most of signal power, is less than the number of antennas M. Therefore, if the directions of the arrived signals are known, the correlation coefficients among UEs can be obtained by only considering the signals in the dimension of major angles N.sub.a instead of the dimension of BS antennas M. The spatial FFT can be used to map the signals to different angles. Compared to other options to map M-dimensional signals into other spaces, spatial FFT has advantages listed below. 1. Easy implementation: the symmetric property of FFT enables M log(M) complexity of implementation, and there are designs that can be implemented in the Radio Frequency (RF) domain for the spatial FFT process. 2. Spatial FFT naturally matches the nature of signal propagation: since the signals are reflected by limited reflectors and arrive at a BS at different angles, spatial FFT fits the nature of signal propagation by mappings the signals into the spatial domain.

(24) Assume that the channel for the kth UE is h.sub.k, then the spatial FFT of h.sub.k is denoted as {tilde over (h)}.sub.k=FFT(h.sub.k)=h.sub.kP.sub.FFT, where P.sub.FFT is the FFT matrix with the entry on the ith row and the jth column being w.sup.ij with

(25) $w=\frac{1}{\sqrt{M}}{e}^{\frac{2\sqrt{-1}}{M}}.$
FIG. 2 shows the received signals generated according to the Long-Term Evolution (LTE) standard at the 512 antennas of a massive MIMO BS for an example. After spatial FFT, the received signals are shown in FIG. 3 for the same example. As shown in FIG. 3, only a limited number of angles has strong signal power. Therefore, in the subsequent signal processing, only the signals in these angle bins need to be considered. One strategy is to choose the N.sub.a angles, so that these angle bins contain p percent of the total power.
Implementation of Spatial FFT

(26) Another embodiment is the architecture to implement the spatial FFT algorithm. This embodiment includes two methods for implementing the spatial FFT algorithm, i.e., FFT in the digital domain and FFT in both the analog and digital domains.

(27) One method is the structure of digital-domain spatial FFT shown in FIG. 4. Specifically, the received signals at BS antennas 3 are first passed through the bandpass filter 4 and the Analog-to-Digital Converter (ADC) 5 to become digital samples, which are then passed through the spatial FFT block 6. For easy understanding, the output of the spatial FFT block is called Virtual BS antennas 7. Then, the channel vector between the kth UE to the Virtual BS antennas is {tilde over (h)}.sub.k=h.sub.kP.sub.FFT, where h.sub.k is the channel row vector between the kth UE and real BS antennas. After it, {tilde over (h)}.sub.k is passed to the signal processing block 8 to conduct the signal processing. Note that this spatial FFT block can be used in both the uplink and the downlink, though FIG. 4 only shows an example of the uplink. Another embodiment of this invention is to perform the baseband signal processing functions with spatial FFT such as detection, time or frequency offset estimation, decoding, etc. Since the outputs of the spatial FFT block is considered as virtual BS antennas, these signal processing functions are performed on each virtual BS antenna as illustrated in FIG. 4. In other words, since the spatial FFT block is included in the channels between BS and UE antennas, all the baseband signal processing functions are performed after the virtual BS antennas.

(28) Another method is the spatial FFT block consisting of both analog and digital parts as shown in FIG. 5. If the number of BS antennas is too large, the complexity of the digital-domain spatial FFT block might be too high. To reduce the complexity, the Butler matrix 9 can be used to perform FFT in the RF domain [3]. The Butler matrix uses wires to implement the analog FFT function, so that the signals passing through the Butler matrix automatically conduct FFT. Note that the size of Butler matrix also could not be too large due to the nature of its implementation. Normally, the size of Butler Matrix could be up to 8 [3]. Hence, this method proposes to use the digital radix FFT block 10 combined with the Butler matrix to perform spatial FFT as shown in FIG. 5.

(29) The design of combining the Butler matrix and the digital radix FFT block is based on the following principle. For the signal sequence x[n] with the length N, it can be divided into two sequences with the length of N/2, i.e., s.sub.1[n]=x[2n] and s.sub.2[n]=x[2n+1]. Let S.sub.1[k] and S.sub.2[k] denote the FFTs of s.sub.1[n] and s.sub.2[n] respectively. Then, the FFT of x[n] can be computed as

(30) $\begin{array}{cc}X\left[k\right]=S_1\left[k\right]+G_2\left[k\right],X\left[k+N/2\right]=S_1\left[k\right]-G_2\left[k\right],\mathrm{where}k=0,1,\mathrm{.Math.},N/2-1,\mathrm{and}{G}_2\left[k\right]=W_N^k{S}_2\left[k\right]\mathrm{with}{W}_N^k=\cos \frac{2}{N}k-j\sin \frac{2}{N}k.& \left(3\right)\end{array}$

(31) Therefore, to compute FFT with the length N, the number of complex-valued multiplications is reduced from N.sup.2 to (N/W)log.sub.2(N/W), where W is the size of a implemented Butler Matrix. For example, if N=512 and W=8, the complex-valued multiplication complexity is reduced from 262144 to 384, only 0.15% of the complexity with the Butler matrix and the digital radix FFT block.

(32) ZF Pre-Coding Based on Spatial FFT

(33) Another embodiment of this invention is the procedure to reduce the complexity of pre-coding matrix computation based on the spatial FFT block, which is shown in FIG. 6. After the spatial FFT block 6, the set of indices of virtual BS antennas containing p percent energy is found, and the values on the rest virtual BS antennas are set to be 0 11. The channel matrix between the UEs and the virtual BS antennas is {tilde over (H)}=HP.sub.FFT, where H is the channel matrix between the UEs and the real BS antennas, and P.sub.FFT is the FFT matrix. Then, the pre-coding matrix of ZF for the virtual BS antennas is calculated as {tilde over (G)}={tilde over (H)}.sup.H({tilde over (H)}{tilde over (H)}.sup.H).sup.1 12. Note that the row vectors of {tilde over (H)} are sparse after spatial FFT, so the computation of W={tilde over (H)}{tilde over (H)}.sup.H is simplified. The procedure of computing the entry on the ith row and the jth column of W, W.sub.i,j, is shown in FIG. 7. Specifically, the ith row {tilde over (h)}.sub.i of {tilde over (H)} and the jth column {tilde over (h)}.sub.j.sup.H of {tilde over (H)}.sup.H are first selected 13. Next, the product W.sub.i,j(m) is calculated as W.sub.i,j(m)={tilde over (h)}.sub.i,m{tilde over (h)}.sub.j,m*, if {tilde over (h)}.sub.i,m and {tilde over (h)}.sub.j.sup.H are both non-zero, otherwise W.sub.i,j(m)=0 14, where {tilde over (h)}.sub.i,m and {tilde over (h)}.sub.j,m* are the mth elements of {tilde over (h)}.sub.i and {tilde over (h)}.sub.j.sup.H respectively with m=0, 1, . . . , M. After that, W.sub.i,j is computed as W.sub.i,j=.sub.m=1.sup.MW.sub.i,j(m)/M 15, where W.sub.i,j is optionally normalized.

(34) After the computation of the pre-coding matrix {tilde over (G)}, the process to transmitted signals to K UEs on the same time-frequency resource is illustrated in FIG. 8. Specifically, the K1 information data vector s is first generated 16. Then, s is multiplied by the pre-coding matrix {tilde over (G)} to compute the M1 precoded data vector x to be sent through virtual BS antennas 17. Next, x is passed through the spatial FFT block, the Digital-to-Analog Converter (DAC) 18, the bandpass filter, and sent out by the real BS antennas.

(35) UE Grouping Based on Spatial FFT

(36) Another embodiment of this invention is to perform UE grouping based on the correlation coefficient between any two UEs computed with the spatial FFT block.

(37) Since the number of active UEs in wireless systems is generally much larger than the supported UEs on one time-frequency resource, the BS needs to select and group K UEs for one time-frequency resource for multi-user transmission. Several criteria can be followed to group UEs. One criterion is to schedule UEs with small correlation coefficients among them in the same group. In this way, the system throughput is generally higher because the correlation coefficients among these UEs are low, and the NS theory for computing the inverse of {tilde over (H)}{tilde over (H)}.sup.H is easier to converge.

(38) The correlation coefficient between the ith and the jth UEs is essentially evaluated by W.sub.i,j. The problem of UE grouping is to select K UEs from the pool of UEs waiting to be served. The procedure of UE grouping is shown in FIG. 9. For every new UE, the process checks the correlation coefficients between it and the existing UEs in the group. If the correlation coefficients between it and all the existing UEs are all below a threshold , it is added into the group. Otherwise, the next UE in the pool is selected until all the K UEs are selected. Specifically, after the process starts 19, k=1 20. Next, whether k=K is checked 21. If kK, one new UE UE.sub.k is selected from the waiting pool 22. Then, whether the correlation coefficients between UE.sub.k and all existing UEs in the group are all lower than is checked 23. If yes, UE.sub.k is added into the group, k=k+1 24, and the process jumps back to 21 and continues. Otherwise, the process directly jumps back to 21 and continues. At 21, if k=K, the process ends 25.

(39) Although the foregoing descriptions of the preferred embodiments of the present inventions have shown, described, or illustrated the fundamental novel features or principles of the inventions, it is understood that various omissions, substitutions, and changes in the form of the detail of the methods, elements or apparatuses as illustrated, as well as the uses thereof, may be made by those skilled in the art without departing from the spirit of the present inventions. Hence, the scope of the present inventions should not be limited to the foregoing descriptions. Rather, the principles of the inventions may be applied to a wide range of methods, systems, and apparatuses, to achieve the advantages described herein and to achieve other advantages or to satisfy other objectives as well.

REFERENCE

(40) [1]. F. Rusek, D. Persson, B. K. Lau, E. G. Larsson, T. L. Marzetta, O. Edfors, and F. Tufvesson, Scaling up MIMO: Opportunities and Challenges with Very Large Arrays, IEEE Signal Process. Mag., vol. 30, no. 1, pp. 40-46, January 2013. [2]. H. Prabhu, J. Rodrigues, O. Edfors, and F. Rusek, Approximative Matrix Inverse Computations for Very-Large MIMO and Applications to Linear Pre-coding Systems, in Proc. IEEE WCNC 2013, Shanghai, China, April 2013, pp. 2710-2715. [3]. E. Bialkowski, F.-C. E. Tsai, Y.-C. Su, and K.-H. Cheng, Design of Fully Integrated 44 and 88 Butler Matrices in Microstrip/Slot technology for Ultra Wideband Smart Antennas in Proc. 2008 IEEE Antennas and Propagation Society International Symposium, San Diego, Calif., USA, July 2008.