CHANNEL ESTIMATION FOR MILLIMETER-WAVE COMMUNICATION/DATA LINK AND THE CORRESPONDING CODEBOOK DESIGN

Abstract

The channel estimation method for millimeter-wave communication includes virtual multipath acquisition and sparse reconstruction. In the virtual multipath acquisition stage, instead of searching the real multipath components (MPCs), the virtual representation of the real MPCs is derived, and the hierarchical search is utilized to acquire the virtual MPCs based on a normal limited-resolution codebook. In the sparse reconstruction stage, the real MPCs are reconstructed from the virtual MPCs acquired in the virtual multipath acquisition stage. An enhanced sub-array scheme is used to design a hierarchical codebook under a strict constant-modulus constraint. The designed codebook can be used for both analog and hybrid beamforming/combining devices. The training overhead of channel estimation and the complexity of the search are significantly reduced, and the size of the dictionary matrix is greatly reduced by exploiting the results of the virtual multipath acquisition.

Claims

1. The method of channel estimation for millimeter-wave communication, comprising the steps of: providing a millimeter-wave transmitter (Tx) with N.sub.t antennas; providing a millimeter-wave receiver (Rx) with N.sub.r antennas; performing virtual multipath acquisition (VMA) using a hierarchical search of multiple layers to acquire virtual multipath components (MPCs) and a corresponding virtual channel H.sub.fd, wherein the hierarchical search for each layer comprises: causing the transmitter to transmit signals based on Tx codewords selected from a transmitter codebook, causing the receiver to receive signals from the transmitter based on Rx codewords selected from a receiver codebook, obtain measured values of the received signals, process the measured values of the received signals by a processor of the receiver, and to determine Tx codewords and. Rx codewords for the next layer of the hierarchical search, and returning to the transmitter the indexes of the Tx codewords for the next layer, wherein the Tx codewords are used as transmitter antenna weight vectors (Tx AWVs) for shifting the phase of the signals transmitted by the transmitter, and the Rx codewords are used as receiver antenna weight vectors (Rx AWVs) for shifting the phase of the signals received by the receiver; and performing sparse reconstruction (SR) to reconstruct real MPCs and therefore original channel H from the virtual channel H .sub.fd acquired in the VMA step.

2. The method of channel estimation of claim 1, wherein: the transmitter codebook and the receiver codebook for the hierarchical search are each a hierarchical codebook of (log.sub.2 N+1) layers having 2.sup.k codewords w(k,j), j=1,2, . . . , 2.sup.k, in the k-th layer, where N=N.sub.r for the receiver codebook and N=N.sub.t for the transmitter codebook, k=0,1,2, . . . , log.sub.2 N; each codeword in the k-th layer of the hierarchical codebook has S.sub.k sub-arrays, each sub-array covering N.sub.S=N/S .sub.k antennas, where S.sub.k=2.sup.(log.sup.2 .sup.Nk)/2 and . denotes ceil integer operation; and the hierarchical codebook is constructed according to the following steps: (a) for k0,1,2, . . . , log.sub.2 N, setting the first codeword in the k-th layer w(k,1 ) according to ${\left[w\left(k,1\right)\right]}_{\left(m-1\right).Math.N_s+1:{\mathrm{mN}}_s}=\sqrt{\frac{N_s}{N}}.Math.e^{j.Math..Math.{}_m}.Math.a\left(N_s,{}_m\right),m=1,2,\mathrm{.Math.}.Math.,S_k,.Math.\mathrm{where}$ ${}_m=-.Math..Math.m\left(N_s-1\right).Math./2-.Math..Math.N_s.Math.m\left(m-1\right).Math./2.$ $=2^{1-k}/S_k,.Math.a\left(N_s,{}_{m.Math.}\right)={\frac{1}{\sqrt{N_s}}\left[e^{j.Math..Math..Math..Math.0.Math..Math.{}_m},e^{j.Math..Math..Math..Math.1.Math..Math.{}_m},\mathrm{.Math.}.Math.,e^{j.Math..Math..Math..Math.\left(N_s-1\right).Math..Math.{}_m}\right]}^T,\mathrm{and}$ ${}_m=-1+\frac{2.Math.m-1}{2}.Math.;$ (b) for k=1,2, . . . , log.sub.2 N, setting other codewords in the k-th layer according to $w\left(k,n\right)=w\left(k,1\right).Math..Math.\sqrt{N}.Math.a\left(N,\frac{2.Math.n-2}{2^k}\right),n=2,3,\mathrm{.Math.}.Math.,2^k,$ where is the entry-wise product.

3. The method of channel estimation of claim 2, wherein the hierarchical search comprises the following steps: setting S.sub.t=log.sub.2 N.sub.t, S.sub.r=log.sub.2 N.sub.r, S=log.sub.2 N, where N=N.sub.r if N.sub.rN.sub.t, otherwise N=N.sub.r; setting initial layer index S.sub.0 and initializing H.sub.fd=0; executing the following steps for each l=1,2, . . . , L, where L is a predetermined number of real MPCs: (1) performing a search over all 2.sup.S.sup.02.sup.S.sup.0 Tx/Rx codeword pairs in the S.sub.0-th layer to find a best Tx/Rx codeword pair w.sub.t(S.sub.0,m.sub.t) and w.sub.r(S.sub.0,n.sub.r), for which the value of
y.sub.mw.sub.r(S.sub.0,n.sub.r).sup.HH.sub.fdw.sub.t(S.sub.0,m.sub.t) is the largest, where w.sub.r and w.sub.t respectively denote the receiver codeword and the transmitter codeword, y.sub.m is the measured value of the received signal corresponding to the Tx/Rx codeword pair w.sub.t(S.sub.0,m.sub.t) and w.sub.r(S.sub.0,n.sub.r); (2A) performing a search for a best Tx/Rx codeword pair for each layer from the (S.sub.0+1)-th layer to the S-th layer, wherein the best Tx/Rx codeword pair in the s-th layer is acquired by first finding (a,b) in the following problem: $y\left(m,n\right)=y_m\left(m,n\right)-{w_r\left(s,2.Math.\left(n_r-1\right)+n\right)}^H.Math.H_{\mathrm{fd}}.Math.w_t\left(s,2.Math.\left(m_t-1\right)+m\right),.Math..Math.\left(a,b\right)=\underset{\left(m,n\right)}{\arg .Math..Math.\max }.Math..Math.y\left(m,n\right).Math.,$ where m.sub.t and n.sub.r are respectively the indexes of the best Tx/Rx codeword pair acquired from the immediate preceding layer, m and n are in range of {1,2}, y.sub.m(m,n) is the measured value of the corresponding received signal, and then updating the best Tx/Rx codeword indexes m.sub.t and n.sub.r according to:
m.sub.t=2(m.sub.t1)+a,
n.sub.r=2(n.sub.r1)+b (2B ) if S.sub.r>S.sub.t, performing a search for best Tx/Rx codeword pair for each layer from the (S+1)-th layer to the S.sub.r-th layer, wherein the best Tx/Rx codeword pair in the s-th layer is acquired by first finding b in the following problem: $y^{}\left(n\right)=y_m^{}\left(m\right)-{w_r\left(s,2.Math.\left(n_r-1\right)+n\right)}^H.Math.H_{\mathrm{fd}}.Math.w_t\left(S_t,m_t\right),.Math.a=\underset{n}{\arg .Math..Math.\max }.Math..Math.y^{}\left(m\right).Math.,$ where m.sub.t and n.sub.r are respectively the indexes of the best Tx/Rx codeword pair acquired from the immediate preceding layer, n is in range of {1,2}, y.sub.m(n) is the measured value of the corresponding received signal, and then updating the best Tx/Rx codeword index n.sub.r according to:
n.sub.r=2(n.sub.r1)+b; or if S.sub.t>S.sub.r, performing a search for a best Tx/Rx codeword pair for each layer from the (S+1)-th layer to the S.sub.t-th layer, wherein the best Tx/Rx codeword pair in the s-th layer is acquired by first finding a in the following problem: $y^{}\left(m\right)=y_m^{}\left(m\right)-{w_r\left(S_r,n_r\right)}^H.Math.H_{\mathrm{fd}}.Math.w_t\left(s,2.Math.\left(m_t-1\right)+m\right),.Math.a=\underset{m}{\arg .Math..Math.\max }.Math..Math.y^{}\left(m\right).Math.,$ where m.sub.t and n.sub.r are respectively the indexes of the best Tx/Rx codeword pair acquired from the immediate preceding layer, m is in range of {1,2, y.sub.m(m) is the measured value of the corresponding received signal, and then updating the best Tx/Rx codeword index m.sub.t according to:
m.sub.t=2(m.sub.t1)+a, whereby the best Tx/Rx codeword pair w.sub.t(S.sub.r, m.sub.t) and w .sub.r(S.sub.r, n.sub.r) for the l-th MPC is acquired; (3) Measuring received signals that correspond to codeword pairs w.sub.r(S.sub.r,n.sub.r+n) and w.sub.t(S.sub.t,m.sub.t+m), where m and n are in range of {1,0,1}, to obtain nine virtual MPCs for the l-th real MPC, and updating the virtual channel H.sub.fd according to
H.sub.fd=H.sub.fd+y.sub.m(m,n)w.sub.r(S.sub.r,n.sub.r+n)w.sub.t(S.sub.t,m.sub.t+m).sup.H for all permutations of m and n where y.sub.m(m,n) is the measured value of the corresponding received signal,

4. The method of channel estimation of claim 3, wherein the SR step comprises: (a) calculating reduced Rx candidate antenna weight vectors .sub.r and reduced Tx candidate antenna weight vectors .sub.t according to ${\stackrel{\_}{A}}_r=\left[{\left[a_r\left({\hat{}}_1-\frac{2}{N_r}+\frac{2.Math.k}{{\mathrm{KN}}_r}\right)\right]}_{k=0,1,.Math.\mathrm{.Math.}.Math.,2.Math.K},{\left[a_r\left({\hat{}}_2-\frac{2}{N_r}+\frac{2.Math.k}{{\mathrm{KN}}_r}\right)\right]}_{k=0,1,.Math.\mathrm{.Math.}.Math.,2.Math.K},{\mathrm{.Math.}.Math.\left[a_r\left({\hat{}}_L-\frac{2}{N_r}+\frac{2.Math.k}{{\mathrm{KN}}_r}\right)\right]}_{k=0,1,.Math.\mathrm{.Math.}.Math.,2.Math.K}\right],\mathrm{and}$ ${\stackrel{\_}{A}}_t=\left[{\left[a_t\left({\hat{}}_1-\frac{2}{N_t}+\frac{2.Math.k}{{\mathrm{KN}}_t}\right)\right]}_{k=0,1,.Math.\mathrm{.Math.}.Math.,2.Math.K},{\left[a_t\left({\hat{}}_2-\frac{2}{N_t}+\frac{2.Math.k}{{\mathrm{KN}}_t}\right)\right]}_{k=0,1,.Math.\mathrm{.Math.}.Math.,2.Math.K},{\mathrm{.Math.}.Math.\left[a_t\left({\hat{}}_L-\frac{2}{N_t}+\frac{2.Math.k}{{\mathrm{KN}}_t}\right)\right]}_{k=0,1,.Math.\mathrm{.Math.}.Math.,2.Math.K}\right],.Math..Math.\mathrm{where}$ $.Math.{\hat{}}_{}=-1+\frac{2.Math..Math.n_{r.Math..Math.}-1}{N_r},{\hat{}}_{}=-1+\frac{2.Math..Math.m_{t.Math..Math.}-1}{N_t},=1,2,\mathrm{.Math.}.Math.,L,$ m.sub.tl and n.sub.rl respectively denote the indexes of the best Tx/Rx codeword pair acquired for the l-th MPC, $a_r\left(\right)={\frac{1}{\sqrt{N_r}}\left[e^{j.Math..Math..Math..Math.0.Math..Math.},e^{j.Math..Math..Math..Math.1.Math..Math.},\mathrm{.Math.}.Math.,e^{j.Math..Math..Math..Math.\left(N_t-1\right).Math.}\right]}^T,.Math.a_t\left(\right)={\frac{1}{\sqrt{N_t}}\left[e^{j.Math..Math..Math..Math.0.Math.},e^{j.Math..Math..Math..Math.1.Math.},\mathrm{.Math.}.Math.,e^{j.Math..Math..Math..Math.\left(N_t-1\right).Math.}\right]}^T,$ K is an over-sampling factor; (b) solving $\underset{{}_{},{}_L,{}_{}}{\mathrm{minimize}}.Math.{.Math.\mathrm{vec}\left(H_{\mathrm{fd}}\right)-\left(\stackrel{\_}{A_t^{*}}.Math.\stackrel{\_}{A_r}\right).Math.\mathrm{vec}\left(\right).Math.}_2$ $\mathrm{subject}.Math..Math.\mathrm{to}.Math..Math.{.Math.\mathrm{vec}\left(\right).Math.}_0=L,$ where .Math. is the Kronecker product, the superscript * denotes conjugate, to obtain values of channel coefficients .sub.t, angles of arrival .sub.t and angles of departure .sub.l; and (c) calculating channel matrix H by
H=.sub.r.sub.t.sup.H, where is a sparse matrix with every column and every row thereof having at most one nonzero element and with the nonzero elements corresponding to the channel coefficients .sub.l, and the superscript H denotes conjugate transpose.

5. The method of channel estimation of claim 4, wherein an orthogonal matching pursuit (OMP) algorithm is used to solve the problem in step (b).

6. The method of channel estimation of claim 1, wherein during the VMA step four virtual MPCs are acquired for each real MPC.

7. The method of channel estimation of claim 4, wherein the problem in step (b) is solved subject to vec()||.sub.0=L instead of vec()||.sub.0=L, assuming there are adjacent MPCs with very close angles of arrival (AoAs) and angles of departure (AoDs) within each cluster.

8. The method of channel estimation of claim 1, wherein the transmitter codebook and the receiver codebook are each a uniform planar array (UPA) codebook based on two uniform linear array (ULA) codebooks.

9. The method of channel estimation of claim 8, wherein the UPA codebook has N.sub.x and N.sub.y antennas along x and y axes, respectively, both N.sub.x and N.sub.y being integer powers of 2, and the n.sub.x and n.sub.y-th (along x and y axes, respectively) codeword in the k-th layer of the UPA codebook, denoted as w.sub.P(k,n.sub.x,n.sub.y) is expressed as
w.sub.P(k,n.sub.x,n.sub.y)=w.sub.x(k,n.sub.x).Math.w.sub.y(k,n.sub.y), where .Math. is the Kronecker product, w.sub.x(k,n.sub.x) is the n.sub.x-th codeword in the k-th layer of a ULA codebook with N.sub.x antennas, while w.sub.y(k,n.sub.y) is the n.sub.y-th codeword in the k-th layer of a ULA codebook with N.sub.y antennas.

10. The method of channel estimation of claim 1, wherein the transmitter includes a digital baseband and an RF phased array, the RF phased array including an RF chain and N.sub.t transmitting antenna branches each having a phase shifter connected to the RF chain, a power amplifier connected to the phase shifter, and one of said N.sub.t antennas connected to the power amplifier; and the receiver includes an RF phased array and a digital baseband, the RF phased array including an RF chain, an adder having an output end connected to the RF chain, and N.sub.r receiving antenna branches each having one of said N.sub.r antennas, a low noise amplifier connected to the antenna, a phase shifter connected between the low noise amplifier and an input end of the adder,

11. The method of channel estimation of claim 10, wherein the digital baseband of the receiver comprises a baseband signal detector, a beam controller, and said processor of the receiver, wherein the processor controls the baseband signal detector to detect the received signal and controls the beam controller to generate an Rx codeword for the RF phased array of the receiver.

12. The method of channel estimation of claim 10, wherein the digital baseband of the transmitter comprises a controller, a baseband signal generator, and a beam controller, wherein the controller controls the baseband signal generator to generate a baseband signal and controls the beam controller to generate a Tx codeword for the RF phased array of the transmitter.

13. The method of channel estimation of claim 1, wherein the processor of the receiver is a computer configured with software and memory for processing the measured values of received signals.

14. The method of channel estimation of claim 13, wherein the SR step is performed by the computer configured with software and memory for performing the SR step.

15. The codebook for the hierarchical search in the method of channel estimation of claim 1, wherein: the codebook is a hierarchical codebook of (log.sub.2 N+1) layers having 2.sup.k codewords w(k, j), j=1,2, . . . , 2.sup.k, in the k-th layer, where N=N.sub.r for the receiver codebook and N=N.sub.t for the transmitter codebook, k=0,1,2, . . . , log.sub.2 N; each codeword in the k-th layer of the hierarchical codebook has S.sub.k sub-arrays, each sub-array covering N.sub.S=N/S.sub.k antennas, where S.sub.k=2.sup.(log.sup.2 .sup.Nk)/2 and . denotes coil integer operation; and the hierarchical codebook is constructed according to the following steps: (a) for k=0,1,2, . . . , log.sub.2 N, setting the first codeword in the k-th layer w(k,1) according to ${\left[w\left(k,1\right)\right]}_{\left(m-1\right).Math.N_s+1:{\mathrm{mN}}_s}=\sqrt{\frac{N_s}{N}}.Math.e^{j.Math..Math.{}_m}.Math.a\left(N_s,{}_m\right),m=1,2,\mathrm{.Math.}.Math.,S_k,.Math.\mathrm{where}$ ${}_m=-.Math..Math.m\left(N_s-1\right).Math./2-.Math..Math.N_s.Math.m\left(m-1\right).Math./2.$ $=2^{1-k}/S_k,.Math.a\left(N_s,{}_{m.Math.}\right)={\frac{1}{\sqrt{N_s}}\left[e^{j.Math..Math..Math..Math.0.Math..Math.{}_m},e^{j.Math..Math..Math..Math.1.Math..Math.{}_m},\mathrm{.Math.}.Math.,e^{j.Math..Math..Math..Math.\left(N_s-1\right).Math..Math.{}_m}\right]}^T,\mathrm{and}$ ${}_m=-1+\frac{2.Math.m-1}{2}.Math.;$ (b) for k=1,2, . . . , log.sub.2 N, setting other codewords in the k-th layer according to $w\left(k,n\right)=w\left(k,1\right).Math..Math.\sqrt{N}.Math.a\left(N,\frac{2.Math.n-2}{2^k}\right),n=2,3,\mathrm{.Math.}.Math.,2^k,$ where is the entry-wise product.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0019] FIG. 1 illustrates the Fejr kernel functions for an MPC with AoA=0 and AoD= 1/16 (in the cosine angle domain), where N.sub.t=N.sub.r=8;

[0020] FIG. 2 illustrates the 4 virtual MPCs for a real MPC with AoA=0 and AoD = 1/16 (in the cosine angle domain), where N.sub.t=N.sub.r=8;

[0021] FIG. 3 shows the beam coverage of a hierarchical codebook with 16 antennas;

[0022] FIG. 4 illustrates a simplified block diagram of the signal measurement system for the VMA stage of the VMA-SR method according to the present application;

[0023] FIG. 5 illustrates the RF phased array of the transmitter of the signal measurement system;

[0024] FIG. 6 illustrates the RF phased array of the receiver of the signal measurement system;

[0025] FIG. 7 shows the flowchart of a measurement process;

[0026] FIG. 8 shows the beam patterns of the proposed enhanced sub-array scheme with a uniform linear array (ULA) codebook, where N=64 ;

[0027] FIG. 9 shows the beam patterns of the codewords in the first layer of a uniform planar array (UPA) codebook, where the size of the UPA is 88;

[0028] FIG. 10 shows the effect of the over-sampling factor K on the detection performance of the proposed VMA-SR approach;

[0029] FIG. 11 shows the effect of the over-sampling factor K on the mean squared error (MSE) performance of the proposed VMA-SR approach;

DETAILED DESCRIPTION OF THE INVENTION

[0030] The invention will now be further described referring to the attached wings and illustrative examples.

[0031] Before the virtual multipath acquisition and sparse reconstruction (VMA-SR) approach of the present application is described, the system model and existing channel estimation methods are first introduced.

[0032] A. System Models

[0033] Letting s denote a training signal with unit average power, when an analog beamforming/combining structure is adopted at the transmitter (Tx) and receiver (Rx), the received signal y is expressed as

y={square root over (P)}w.sub.r.sup.HHw.sub.ts+z, (1)

where P is the average transmission power, w.sub.r and w.sub.t are Rx and Tx antenna weight vectors (AWVs), respectively, H is the channel matrix, and z is the Gaussian white noise. Let N.sub.r and N.sub.t denote the numbers of antennas at the Rx and Tx, respectively. Then w.sub.r and w.sub.t are N.sub.r1 and N.sub.t1 vectors, respectively, with constant modulus (CM) and unit 2-norm, i.e., |w.sub.r|=1/{square root over (N.sub.r)} and |w.sub.t|=1/{square root over (N.sub.t)}. In the case that a hybrid beamforming/combining structure is adopted at the Rx and Tx, w.sub.r and w.sub.t will be the product of a digital beamforming/combining vector and an analog preceding/combining matrix with constant modulus.

[0034] It is known that mmWave channels have limited scattering, and multipath components (MPCs) are mainly generated by reflections. Different MPCs have different angles of departure (AoDs) and angles of arrival (AoAs). Without loss of generality, this invention adopts the directional channel model here, which is relevant to the geometry of antenna arrays. When using uniform linear array (ULA) with a half-wavelength antenna space, an mmWave channel can be expressed as

[00005]$\begin{array}{cc}H=\underset{=1}{\overset{L}{.Math.}}.Math..Math.{}_{}.Math.a_r\left({}_{}\right).Math.a_t^H\left({}_{}\right),& \left(2\right)\end{array}$

where .sub.l is the complex channel coefficient of the l-th path and

[00006]$\left(\underset{=1}{\overset{L}{.Math.}}.Math..Math.{.Math.{}_{}.Math.}^2\right)=N_r.Math.N_t,$

is the number of MPCs, a.sub.r(.) and a.sub.t (.) are the Rx and Tx steering vector functions, respectively, defined as

[00007]$\begin{array}{cc}{a}_r\left(\right)={\frac{1}{\sqrt{N_r}}\left[e^{j.Math..Math.0},e^{j.Math..Math.1},\mathrm{.Math.}.Math.,e^{j.Math..Math.\left(N_r-1\right).Math.}\right]}^T,.Math.a_t\left(\right)={\frac{1}{\sqrt{N_t}}\left[e^{j.Math..Math.0},e^{j.Math..Math.1},\mathrm{.Math.}.Math.,e^{j.Math..Math.\left(N_t-1\right).Math.}\right]}^T,& \left(3\right)\end{array}$

where and are cos (AoD) and cos (AoA), respectively. Specifically, .sub.l and .sub.l are cos (AoD) and cos (AoA) of the l-th path, respectively. Let .sub.l and .sub.l denote the real AoD and AoA of the l-th path, respectively; then we have .sub.l=cos (.sub.l) and .sub.l=cos (.sub.l). Therefore, .sub.l and are.sub.l within the range of [1,1 ]. For convenience, in the rest of this invention, .sub.l and .sub.l are called AoAs and AoDs, respectively. The superscript T denotes transpose.

[0035] B. Channel Estimation

[0036] To estimate the channel, we need to make some measurements based on the beamforming/combining structure shown in (1): In each measurement, Tx would transmit a training signal with a Tx AWV, while Rx would receive the signal with an Rx AWV. If the conventional least-square (LS) method is adopted to estimate the channel, at least N.sub.rN.sub.t measurements are needed, which is unaffordable in mmWave communication where N.sub.r and N.sub.t are large in general. To reduce the pilot overhead, there are two main candidate approaches: the compressed sensing (CS) based method and the hierarchical search method. This invention briefly introduces them for comparison with the proposed approach.

[0037] The CS Approach: Based on the signal model in (1), multiple measurements may be made with different Tx AWVs [w.sub.t1, w.sub.t2, . . . , w.sub.t.sub.t]W.sub.t and Rx AWVs [w.sub.r1, w.sub.r2, . . . , w.sub.r.sub.r]W.sub.r, where .sub.r is the number of the different Tx AWVs and .sub.r is the number of the different Rx AWVs and assuming, without loss of generality, s=1, then

Y={square root over (P)}W.sub.r.sup.HHW.sub.t+Z, (4)

where Z is the noise matrix. By sampling the AoA/AoD domains with sufficiently high resolution , we can obtain

[00008]$A_r=[a_r\left(-1+\frac{}{2}\right),a_r\left(-1+\frac{3.Math.}{2}\right),\mathrm{.Math.}.Math.].Math..Math.\mathrm{and}$$A_t=[a_t\left(-1+\frac{}{2}\right),a_t\left(-1+\frac{3.Math.}{2}\right),\mathrm{.Math.}.Math.].$

Then H can be approximately expressed as H=A.sub.rA.sub.t.sup.H, where is a sparse matrix with every column and every row thereof having at most one nonzero element and with the nonzero elements corresponding to the channel coefficients .sub.l. Substituting H in (1) with this expression and vectorizing Y, we have

[00009]$\begin{array}{cc}\begin{array}{c}\mathrm{vec}\left(Y\right)=.Math.\mathrm{vec}\left(\sqrt{P}.Math.W_r^H.Math.A_r.Math..Math..Math.A_t^H.Math.W_t+Z\right)\\ =.Math.\sqrt{P}.Math.\left({\left(A_t^H.Math.W_t\right)}^T.Math.\left(W_r^H.Math.A_r\right)\right).Math.\mathrm{vec}\left(\right)+\mathrm{vec}\left(Z\right)\\ \stackrel{}{=}.Math..Math.\sqrt{P}.Math.\mathrm{Qvec}\left(\right)+\mathrm{vec}\left(Z\right),\end{array}& \left(5\right)\end{array}$

where .Math. is the Kronecker product. Since || vec()|.sub.0=L<<N.sub.rN.sub.t, sparse recovery tools can be adopted to estimate H, where the dictionary matrix Q can be obtained by randomly setting the Tx and Rx training AWVs in each measurement as [w.sub.r].sub.k {e.sup.j/{square root over (N.sub.r)}} and [w.sub.t].sub.m {e.sup.j/{square root over (N.sub.t)}} with uniformly distributed phase . Note that as the number of candidate vectors, i.e., the number of columns of Q, is large, the computational complexity of the CS approach is high. In addition, the total number of measurements is T.sub.CS=.sub.r.sub.t. And when T.sub.CS is not large enough, the performance of the CS approach is not satisfactory. The adaptive compressed sensing (ACS) scheme proposed by Alkhateeb et al. can reduce the training overhead to some extent, but multiple RF chains are required to guarantee satisfactory performance.

[0038] The Hierarchical Search Approach: The hierarchical search method is based on the structure of H. As there are L MPCs to be found, it is natural to search them one by one, and a hierarchical codebook can be used to reduce the search time. Different from the single-path search, for multi-path search, the contribution of the formerly found MPCs should be subtracted from the received signal during the search of each MPC. For instance, suppose that we have estimated the coefficients, AoAs and AoDs of the first L.sub.f MPCs, denoted by {circumflex over ()}.sub.i, {circumflex over ()}.sub.i, {circumflex over ()}.sub.i for i=1,2, . . . , L.sub.f, then in the search of the (L.sub.f+1)-th MPC, in each measurement we can compute the decision variable as

[00010]$\begin{array}{cc}\begin{array}{c}\stackrel{\_}{y}=.Math.\underset{\underset{\mathrm{Measured}}{}}{\sqrt{P}.Math.w_r^H.Math.{\mathrm{Hw}}_t+z}-\underset{\underset{\mathrm{FormerContribution}}{}}{\sqrt{P}.Math.w_r^H.Math.\left(\underset{i=1}{\overset{L_f}{.Math.}}.Math..Math.{\hat{}}_i.Math.a_r\left({\hat{}}_i\right).Math.a_t^H\left({\hat{}}_i\right)\right).Math.w_t}\\ =.Math.\sqrt{P}.Math.w_r^H\left(\underset{i=L_f+1}{\overset{L}{.Math.}}.Math..Math.{}_i.Math.a_r\left({}_i\right).Math.a_t^H\left({}_i\right)\right).Math.w_t+z+\\ .Math.\sqrt{P}.Math.w_r^H\left(\underset{i=1}{\overset{L_f}{.Math.}}.Math..Math.\left({}_i.Math.a_r\left({}_i\right).Math.a_t^H\left({}_i\right)-{\hat{}}_i.Math.a_r\left({\hat{}}_i\right).Math.a_t^H\left({\hat{}}_i\right)\right)\right).Math.w_t\\ \stackrel{}{=}.Math..Math.\sqrt{P}.Math.w_r^H\left(\underset{i=L_f+1}{\overset{L}{.Math.}}.Math..Math.{}_i.Math.a_r\left({}_i\right).Math.a_t^H\left({}_i\right)\right).Math.w_t+z+I_{\mathrm{res}},\end{array}& \left(6\right)\end{array}$

where I.sub.res is the residual interference. If the AoAs and AoDs are accurately estimated, the coefficients will also be accurately estimated, and I.sub.res will be small. Dropping the noise component, we have

[00011]$\begin{array}{cc}\stackrel{\_}{y}\sqrt{P}.Math.w_r^H\left(\underset{i=L_f=1}{\overset{L}{.Math.}}.Math..Math.{}_i.Math.a_r\left({}_i\right).Math.a_t^H\left({}_i\right)\right).Math.w_t,& \left(7\right)\end{array}$

which means the (L.sub.f+1)-th MPC can be normally found by using the hierarchical search method. However, if the AoAs and AoDs are not accurately estimated, there would be significant coefficient errors, and I.sub.res will be large. In such a case, the search of the (L.sub.f+1)-th MPC will be dramatically affected by the residual interference. That is to say, accurate estimation of the AoAs and AoDs are critical for the hierarchical search method. In practice, the best angle resolution of a codebook for an ULA with N.sub.A antennas is 2/N.sub.A in general, because a steering vector has an angle resolution of 2/N.sub.A. Although it is possible to design a codebook with a much higher resolution so as to accurately estimate the AoAs and AoDs, it will accordingly increase the search time and the storage size of the codebook. More importantly, a higher angle resolution will further intensify the challenge of phase shifter design at the mmWave band, which is undesired in mmWave communication, where hardware design is already harsh. Hence, the codebook with the resolution of 2/N.sub.A is a normal limited-resolution codebook, and the codebook with the resolution higher than 2/N.sub.A is a high resolution codebook.

[0039] In summary, the CS approach can estimate multiple MPCs, but it requires a large number of measurements; otherwise the performance is not satisfactory. The hierarchical search method can also estimate multiple MPCs, provided that the angle resolution of the exploited codebook is sufficiently high. However, this is undesirable from the perspective of hardware design for mmWave devices.

[0040] To solve the problems in the above approaches, this invention provides a VMA-SR method to quickly and accurately acquire multiple MPCs while exploiting a normal limited-resolution codebook.

[0041] The VMA-SR method according to the present invention has two stages, namely virtual multipath acquisition (VMA) for the first stage and sparse reconstruction (SR) for the second stage.

[0042] A. The First Stage: Virtual Multipath Acquisition

[0043] I) Virtual Representation of the Real MPCs: First, we sample the AoA and AoD domains with angle resolutions 2/N.sub.r and 2/N.sub.t, respectively, and obtain two sets of steeling vectors:

[00012]$U=\left[a_r\left(-1+\frac{1}{N_r}\right),a_r\left(-1+\frac{3}{N_r}\right),\mathrm{.Math.}.Math.,a_r\left(-1+\frac{2.Math..Math.N_r-1}{N_r}\right)\right],.Math.V=\left[a_t\left(-1+\frac{1}{N_t}\right),a_t\left(-1+\frac{3}{N_t}\right),\mathrm{.Math.}.Math.,a_t\left(-1+\frac{2.Math..Math.N_t-1}{N_t}\right)\right].$

It is easy to verify that U.sup.HU=I.sub.N, and V.sup.HV=I.sub.N.sub.t, which means that

[00013]${\left\{a_r\left(-1+\frac{2.Math..Math.k-1}{N_r}\right)\right\}}_{k=1,2,\mathrm{.Math.}.Math.,N_r}.Math..Math.\mathrm{and}.Math..Math.{\left\{a_t\left(-1+\frac{2.Math..Math.k-1}{N_t}\right)\right\}}_{k=1,2,\mathrm{.Math.}.Math.,N_t}$

constitute an orthogonal base of .sup.N.sup.r and .sup.N.sup.t, respectively. Hence, for arbitrary .sub.l and .sub.l we have

[00014]$\begin{array}{cc}\{\begin{array}{c}{a}_r\left({}_{}\right)=\underset{k=1}{\overset{N_r}{.Math.}}.Math..Math.{}_{k,}.Math.a_r\left(-1+\frac{2.Math..Math.k-1}{N_r}\right),\\ a_t\left({}_{}\right)=\underset{k=1}{\overset{N_t}{.Math.}}.Math..Math.{}_{k,}.Math.a_t\left(-1+\frac{2.Math..Math.k-1}{N_t}\right),\end{array}.Math..Math.\mathrm{where}& \left(8\right)\\ \{\begin{array}{c}{}_{k,}=a_r^H\left(-1+\frac{2.Math..Math.k-1}{N_r}\right).Math.a_r\left({}_{}\right),\\ {}_{k,}=a_t^H\left(-1+\frac{2.Math..Math.k-1}{N_t}\right).Math.a_t\left({}_{}\right),\end{array}& \left(9\right)\end{array}$

[0044] where .sub.k,l denotes the projection of a.sub.r(.sub.l) in the direction of the unit vector

[00015]$a_r\left(-1+\frac{2.Math..Math.k-1}{N_r}\right),$

and .sub.k,l denotes the projection of a.sub.t(.sub.l) in the direction of the unit vector

[00016]$a_t\left(-1+\frac{2.Math..Math.k-1}{N_t}\right).$

[0045] Let f.sub.r(x)=|a.sub.t.sup.H()a.sub.r(+x)|, i.e., a Fejr kernel function, which goes to zero quickly by increasing |x|. It is known that f.sub.r(0)=1, and when |x|>1/N.sub.r, the kernel is far smaller than 1 given that N.sub.r is large. According to this property, there are only 2 elements in {.sub.k,l}.sub.k1,2, . . . , N.sub.r that may have a significant absolute value, which are .sub.I.sub.r.sub.+(.sub.l.sub.),l and .sub.I.sub.t.sub.(.sub.l.sub.),l with

[00017]$\begin{array}{cc}\{\begin{array}{c}{I}_r^{+}\left({}_{}\right)=\left[\left(N_r\left({}_{}+1\right)+1\right)/2\right],\\ I_r^{-}\left({}_{}\right)=\left[\left(N_r\left({}_{}+1\right)+1\right)/2\right],\end{array}& \left(10\right)\end{array}$

where . and . denote ceil and floor integer operations, respectively. Analogously, there are only 2 elements in {.sub.k,l}.sub.k=1,2, . . . , N.sub.t that may have a significant absolute value, which are .sub.I.sub.t.sub.+(.sub.l.sub.),l and .sub.I.sub.t.sub.(.sub.l.sub.),l with

[00018]$\begin{array}{cc}\{\begin{array}{c}{I}_t^{+}\left({}_{}\right)=\left[\left(N_t\left({}_{}+1\right)+1\right)/2\right],\\ I_t^{-}\left({}_{}\right)=\left[\left(N_t\left({}_{}+1\right)+1\right)/2\right],\end{array}& \left(11\right)\end{array}$

[0046] Consequently, we have

[00019]$\begin{array}{cc}{a}_r\left({}_{}\right){}_{+}.Math.a_r\left({}_{+}\right)+{}_{-}.Math.a_r\left({}_{-}\right),& \left(12\right)\\ a_t\left({}_{}\right){}_{+}.Math.a_t\left({}_{+}\right)+{}_{-}.Math.a_t\left({}_{-}\right),& \left(13\right)\\ \mathrm{where}& \\ \{\begin{array}{cc}{}_{+}={}_{I_r^{+}\left({}_{}\right),},& {}_{-}={}_{I_t^{-}\left({}_{}\right),},\\ {}_{+}={}_{I_t^{+}\left({}_{}\right),},& {}_{-}={}_{I_t^{-}\left({}_{}\right),},\end{array}& \left(14\right)\\ \{\begin{array}{cc}{}_{+}=-1+\frac{2.Math.I_r^{+}\left({}_{}\right)-1}{N_r},& {}_{-}=-1+\frac{2.Math.I_r^{-}\left({}_{}\right)-1}{N_r},\\ {}_{+}=-1-+\frac{2.Math.I_t^{+}\left({}_{}\right)-1}{N_t},& {}_{-}=-1+\frac{2.Math.I_t^{-}\left({}_{}\right)-1}{N_t}.\end{array}& \left(15\right)\end{array}$

[0047] Finally, we can approximately express H as

[00020]$\begin{array}{cc}H\underset{=1}{\overset{L}{.Math.}}.Math.{}_{}\left[{}_{+}.Math.a_r\left({}_{+}\right)+{}_{-}.Math.a_r\left({}_{-}\right)\right]{\left[{}_{+}.Math.a_t\left({}_{+}\right)+{}_{-}.Math.a_t\left({}_{-}\right)\right]}^H=\underset{=1}{\overset{L}{.Math.}}.Math.{}_{}\left[{}_{+}.Math.{}_{+}^{*}.Math.a_r\left({}_{+}\right).Math.a_t^H\left({}_{+}\right)+{}_{-}.Math.{}_{+}^{*}.Math.a_r\left({}_{-}\right).Math.a_t^H\left({}_{+}\right)+{}_{+}.Math.{}_{-}^{*}.Math.a_r\left({}_{+}\right).Math.a_t^H\left({}_{-}\right)+{}_{-}.Math.{}_{-}^{*}.Math.a_r\left({}_{-}\right).Math.a_t^H\left({}_{-}\right)\right],& \left(16\right)\end{array}$

where we can find that the original L real MPCs are represented by 4L virtual MPCs, and most importantly, the Rx and Tx steering vectors of the 4 virtual MPCs, corresponding to one single real MPC, are two adjacent basis vectors within U and V, respectively. The superscript * denotes conjugate.

[0048] FIG. 1 illustrates these properties of an MPC with an AoA of 0 (in the cosine angle domain) and an AoD of 1/16, where N.sub.t=N.sub.r=16, I.sub.r.sup.(.sub.l)=1/N.sub.r, I.sub.r.sup.(.sub.l)=1/N.sub.r, I.sub.t.sup.+(.sub.l)=1/N.sub.t and I.sub.t.sup.(.sub.l)=1/N.sub.t. The absolute values of .sub.1, .sub.1+, .sub.1 and .sub.1+ are also shown in FIG. 1. FIG. 2 shows the 4 virtual MPCs corresponding to the real MPC with an AoA of 0 and an AoD of 1/16, where N.sub.t=N.sub.r=8.

[0049] Note that different from the real MPCs which have arbitrary AoAs and AoDs, the AoAs and AoDs of the virtual MPCs can be accurately estimated with a normal limited-resolution codebook containing the AWVs in U and V, which means that, instead of directly estimating the L real MPCs, we may estimate the 4L virtual MPCs based on a limited-resolution codebook. Afterwards, we can reconstruct the original L real MPCs based on the 4L virtual MPCs.

[0050] II) Hierarchical Search of the Virtual MPCs: Since the AoAs and AoDs (in the cosine angle domain) of the virtual MPCs are within

[00021]${\left\{-1+\frac{2.Math.k-1}{N_r}\right\}}_{k=1,2,.Math.\mathrm{.Math.}.Math.,N_r}.Math..Math.\mathrm{and}.Math..Math.{\left\{-1+\frac{2.Math.k-1}{N_t}\right\}}_{k=1,2,.Math.\mathrm{.Math.}.Math..Math.N_t},$

respectively, the virtual MPCs can be accurately estimated by hierarchical search with a limited-resolution codebook. For instance, FIG. 3 shows a typical limited-resolution codebook with N=16 antennas. The codebook has (log, N+1) layers. In the k-th layer, k=0,1,2, . . . , log.sub.2 N, there are 2.sup.k codewords of the same beam width with different steering angles and collectively covering the entire search space in the cosine angle domain. Note that a codeword is actually an AWV used for beamforming. Let w(k,n) denote the n-th codeword in the k-th layer, n=1, . . . , 2.sup.k. Then the beam coverage of w(k,n) is approximately the union of the beam coverage of the 2 codewords in the (k+1)-th layer, i.e., {w(k+1,2(n1)+m)}.sub.m1,2. There are different methods to design such a codebook, and all the hierarchical codebooks designed by different methods can be used to search the virtual MPCs, provided that the last-layer codewords are steering vectors towards

[00022]${\left\{-1+\frac{2.Math.k-1}{N}\right\}}_{k=1,2,.Math.\mathrm{.Math.}.Math.,N}.$

[0051] Based on the hierarchical codebook, we next introduce the proposed hierarchical search algorithm to acquire the virtual MPCs, which is shown in Algorithm 1, where w.sub.t(.) and w.sub.r(.) represent the Tx and Rx codewords, respectively.

TABLE-US-00001 Algorithm 1: Hierarchical Search of the Virtual MPCs. 1) Initialization: S = log.sub.2 N.sub.r. /*Assume N.sub.r = N.sub.t , and calculate the total number of layers S */ S.sub.0 = 2. /*The initial layer index.*/ H.sub.fd = 0. /*The already found MPCs.*/ 2) Iteration: for l = 1:L do /*There are L iterations in the search process.*/ /*Step 1: Search for the initial Tx/Rx codewords.*/ for m = 1:2.sup.S.sub.0 do for n = 1:2.sup.S.sub.0 do y(m,n) = {square root over (P)}w.sub.r(S.sub.0,n).sup.HHw.sub.t(S.sub.0,m) + z w.sub.r(S.sub.0,n).sup.HH.sub.fdw.sub.t(S.sub.0,m) (m.sub.t,n.sub.r) = arg.sub.(m,n) max | y(m,n)| /*Step 2: Hierarchical search. The best Tx/Rx codeword pair w.sub.t(S.sub.0,m.sub.t) and w.sub.r(S.sub.0, n.sub.r) acquired in Step 1 are treated as the parent codewords for Step 2. */ for s = (S.sub.0 + 1): S do for m = 1,2 do for n = 1,2 do y(m,n) = {square root over (P)}w.sub.r(s,2(n.sub.r 1) + n).sup.HHw.sub.t(s,2(m.sub.t 1) + m) + z w.sub.r(s,2(n.sub.r 1) + n).sup.HH.sub.fdw.sub.t(s,2(m.sub.t 1) + m) (a,b) = arg.sub.(m,n) max | y(m,n)| m.sub.t = 2(m.sub.t 1) + a;n.sub.r = 2(n.sub.r 1) + b /*Step 3: Collection of the virtual MPCs: Acquire the significant virtual MPC at the last layer (S -th layer).*/ for m = 1,0,1 do for n = 1,0,1 do y = {square root over (P)}w.sub.r(S,n.sub.r + n).sup.HHw.sub.t(S,m.sub.t + m) + z H.sub.fd = H.sub.fd + yw.sub.r(S,n.sub.r + n)w.sub.t(S,m.sub.t + m).sup.H 3) Results: Return the virtual channel H.sub.fd

[0052] There are L iterations in the search process, and the virtual MPCs corresponding to a single MPC are acquired in each iteration. The hierarchical search algorithm for the VMA-SR method is briefly illustrated as follows.

[0053] (1) Initialization: Calculate the total number of layers S, set the initial layer index S.sub.0 and initialize the already found MPCs as a zero vector, i.e., H.sub.fd=0. (2) Search process: Execute the following three steps L times.

[0054] Step 1: Search for the initial Tx/Rx codewords. As in mmWave communication the transmission power is generally limited, the beamforming training may not start from the 0-th layer, where the codeword is omni-directional and the gain is low. Instead, the beamforming training may need to start from a higher layer, e.g., the S.sub.0-th layer, to provide sufficient start-up beamforming gain. In this process, there are 2.sup.S.sup.0 candidate codewords at both Tx and Rx. Thus, an exhaustive search over all base station (BS) and mobile station (MS) codeword pairs is adopted to search the best Tx/Rx codeword pair, which are treated as the parent codewords for the following search. m.sub.t and n.sub.r denote the best Tx/Rx codeword indexes in the S.sub.0-th layer, respectively. Note that when computing y(m,n), the sum of the first two terms is substituted by the measured value of the corresponding received value.

[0055] Step 2: Hierarchical search. In this process, a layered search is performed to refine the beam angle step by step, until the most significant virtual UPC is acquired at the last layer (the S-th layer).

[0056] The best Tx/Rx codeword pair w.sub.t(S.sub.0,m.sub.t) and w.sub.r(S.sub.0,n.sub.r) acquired in step 1 are treated as the parent codewords for step 2. Then a layered search is performed from the (S.sub.0+1)-th layer to the S-th layer to acquire the most significant virtual MPC.

[0057] In the search for each layer, the best Tx/Rx codeword pair in current layer are found according to the following problem:

[00023]$\begin{array}{cc}y\left(m,n\right)=\begin{array}{cc}\sqrt{P}.Math.{w_r\left(s,2.Math.\left(n_r-1\right)+n\right)}^H.Math.{\mathrm{Hw}}_t\left(s,2.Math.\left(m_t-1\right)+m\right)+z-{w_r\left(s,2.Math.\left(n_r-1\right)+n\right)}^H.Math.H_{\mathrm{fd}}.Math.w_t\left(s,2.Math.\left(m_t-1\right)+m\right),.Math.\left(a,b\right)=\underset{\left(m,n\right)}{\arg .Math..Math.\max .Math.}.Math..Math.y\left(m,n\right).Math.,& \end{array}& \left(17\right)\end{array}$

where m and n are in range of {1,2], and s is the index of the current layer. And the best codewords in the current layer are treated as the parent codewords in the next layer, i.e., after (a,b) is acquired, update the best Tx/Rx codeword indexes in the current layer. Note that when computing y(m,n), the sum of the first two terms, {square root over (P)}w.sub.r(s,2)(n.sub.r1)+n).sup.HHw.sub.t(s,2(m.sub.t1)+m)+z, is substituted by the measured value of the corresponding received signal.

[0058] Step 3: Collection of the virtual MPCs. After the hierarchical search, the most significant virtual MPC is acquired. Since the other 3 virtual MPCs are adjacent to the already found MPC, we measure a 1 AoA/AoD neighborhood to make sure that the desired virtual MPCs are all collected. Note that y={square root over (P)}w.sub.r(S,n.sub.r+n).sup.HHw.sub.t(S,m.sub.t+m)+z is substituted by the measured value of the corresponding received signal. With this operation, 9 instead of 4 virtual MPCs are actually acquired. Flowever, the other 5 virtual MPCs have much smaller strength compared with the 4 desired virtual MPCs, and thus affect little on the results.

[0059] As shown in the above steps, in each measurement, Tx would transmit a training signal with a Tx AWV, while Rx would receive the signal with an Rx AWV. Then the received signal y would be measured at the Rx. In step 3, after the most significant virtual MPC is acquired, we measure a neighborhood to collect the desired virtual MPCs. Each time a virtual MPC is acquired, the virtual channel H.sub.fd is updated. Computing the sum of the collected virtual MPC, the virtual channel is obtained as H.sub.fd=H.sub.fd+yw.sub.r(S,n.sub.r+n)w.sub.t(S,m.sub.t30 m).sup.H, where m and n are in range of {1,0,1}.

[0060] Note that in each iteration, H.sub.fd obtained in the current iteration will be the initial H.sub.fd in the next iteration.

[0061] In Alrothm 1, it is assumed that N.sub.t=N.sub.r. When N.sub.t is different from N.sub.r, Algorithm 1 may be easily modified as follows. Let S.sub.t denote the total number of layers of the Tx codebook and S.sub.r denote the total number of layers of the Rx codebook. If S.sub.t<S.sub.r, in Step 2 of Algorithm 1, when the best Tx codeword w.sub.t(S.sub.t,m.sub.t) at the S.sub.t-th layer is acquired, the layered search of the Rx codebook continues to be performed from the (S.sub.t+1)-th layer to the S.sub.r-th layer to acquire the best Rx codeword w.sub.r(S.sub.t,m.sub.r). If S.sub.t>S.sub.r, in Step 2 of Algorithm 1, when the best Rx codeword w.sub.r(S.sub.r,m.sub.r) at the S.sub.r-th layer is acquired, the layered search of the Tx codebook continues to be performed from the S.sub.r+1-th layer to the S.sub.t-th layer to acquire the best Tx codeword w.sub.t(S.sub.t,m.sub.t).

[0062] III) Signal measurement hardware system: In the hierarchical search of MPCs, when searching the best Tx/Rx codeword pair w.sub.t and w.sub.r in each layer, for each candidate codeword pair, the received signal y correspondimg to the codeword pair needs to be measured. To facilitate understanding of the process of measuring the received signal y, a signal measurement hardware system is described below.

[0063] FIG. 4 illustrates a simplified block diagram of the signal measurement system. This system includes a transmitter 100 and a receiver 110.

[0064] The transmitter 100 includes a digital baseband 101 and an RF phased array 105. The digital baseband 101 includes a controller 102, a baseband signal generator 103, and a beam controller 104, wherein the controller 102 controls the baseband signal generator 103 to generate a baseband signal s and controls the beam controller 104 to generate the Tx codeword w.sub.t, which is used as the Tx AWV. As shown in FIG. 5, the RF phased array 105 includes an RF chain 501, phase shifters 502, power amplifiers 503, and transmitting antennas 504, wherein the RF chain 501 generates an RF based on the baseband signal s, the phase shifters 502 adjust the phase of the RE based on the Tx AWV, the power amplifiers 503 increase the output power of the RF, and the signal S is transmitted at the transmitting antennas 504.

[0065] The receiver 110 includes a digital baseband 111 and an RF phased array 115. The digital baseband 111 includes a processor 112, a baseband signal detector 113 and a beam controller 114, wherein the processor 112 controls the beam controller 114 to generate the Rx codeword w.sub.r, which is used as the Rx AWV, and controls the baseband signal detector 113 to detect the received signal y, and processes the received signal y. As shown in FIG. 6, the RF phased array 115 includes receiving antennas 601, low noise amplifiers 602, phase shifters 603, an adder 604 and an RF chain 605, wherein the receiving antennas 601 receive the signal S, the low noise amplifiers 602 enhance the input power of the signal, the phase shifters 603 adjust the phase of the signal based on the Rx AWV, the signals from the phase shifters 603 are added by the adder 604 and fed to the RF chain 605 to generate the RE, and the RF is fed to the baseband signal detector 113.

[0066] IV) Implementation of Hierarchical Search in Algorithm 1

[0067] Hierarchical search algorithm is achieved through multiple measurements. In the search of each layer, for each candidate codeword pair of the current layer, the received signal y corresponding to the codeword pair needs to be measured, i.e., one candidate codeword pair (w.sub.t,w.sub.r) corresponds to one measurement. In each measurement, the transmitter 100 uses w.sub.t as the Tx AWV set on the Tx RF phased array 105, and sends a baseband signal s with power P. The receiver 110 uses w.sub.r as the Rx AWV set on the Rx RF phased array 115, measures the received signal y, sends it to the processor 112 for calculation, and feeds back the result to the transmitter 100. As shown in FIG. 7, specific steps are as follows:

[0068] At S710, determine the Tx codeword w.sub.t from the Tx codebook and Rx codeword w.sub.r from the Rx codebook;

[0069] At S720, the Tx controller 102 controls the beam controller 104 to generate the Tx codeword (i.e., w.sub.t), and set the weights of the RF phased array 105 (i.e., Tx AWV) with the generated codeword;

[0070] At S730, the Rx processor 112 controls the beam controller 114 to generate the Rx codeword (i.e., w.sub.r), and set the weights of the RF phased array 115 (i.e., Rx AWV) with the generated codeword;

[0071] At S740, the Tx controller 102 controls the baseband signal generator 103 to generate the baseband signal s, and the RF phased array 105 generates the transmitted signal S;

[0072] At S750, the RF phased array 115 receives the received signal S. After converting it into an RF signal, the RF phased array 115 transmits the RF signal to the baseband signal detector 113. The baseband signal detector 113 detects and measures the received signal y.

[0073] At S760, the baseband signal detector 113 passes the received signal y to the processor 112 for calculation. The processor 112 determines the Tx codeword w.sub.t and the Rx codeword w.sub.r for setting the Tx AWV and the Rx AWV for the next measurement.

[0074] B. The Second Stage: Sparse Reconstruction

[0075] As we have estimated the virtual channel H.sub.fd, we have the following relation:

[00024]$\begin{array}{cc}H=\underset{=1}{\overset{L}{.Math.}}.Math.{}_{}.Math.a_r\left({}_{}\right).Math.a_t^H\left({}_{}\right)H_{\mathrm{fd}}.& \left(18\right)\end{array}$

[0076] To reconstruct the original channel H, we need to estimate .sub.l, .sub.l and .sub.l. Hence, we formulate the following problem:

[00025]$\begin{array}{cc}\underset{{}_{},{}_{},{}_{}}{\mathrm{minimize}.Math.}.Math.{.Math.H_{\mathrm{fd}}-\underset{=1}{\overset{L}{.Math.}}.Math.{}_{}.Math.a_r\left({}_{}\right).Math.a_t^H\left({}_{}\right).Math.}_F,& \left(19\right)\end{array}$

[0077] Then, analogous to the pure CS approach, we sample the AoA and AoD domain with a high resolution, i.e., an angle interval 2/(KN.sub.r) at the Rx and 2/(KN.sub.t) at the Tx, where K is the over-sampling factor, and we obtain

[00026]$A_r=\left[a_r\left(-1+\frac{1}{{\mathrm{KN}}_r}\right),a_r\left(-1+\frac{3}{{\mathrm{KN}}_r}\right),\mathrm{.Math.}.Math.,a_r\left(-1+\frac{2.Math.{\mathrm{KN}}_r-1}{{\mathrm{KN}}_r}\right)\right].Math..Math.\mathrm{and}.Math..Math.A_t=\left[a_t\left(-1+\frac{1}{{\mathrm{KN}}_t}\right),a_t\left(-1+\frac{3}{{\mathrm{KN}}_t}\right),\mathrm{.Math.}.Math..Math.a_t\left(-1+\frac{2.Math.{\mathrm{KN}}_t-1}{{\mathrm{KN}}_t}\right)\right].$

This manipulation is applicable, but at the cost of a high computational complexity. In fact, by exploiting the search results in Algorithm 1, we can significantly reduce the number of the Rx and Tx candidate AWVs. Concretely, since the estimated AoA of the l-th MPC is

[00027]${\hat{}}_{}=-1+\frac{2.Math.n_{r.Math..Math.}-1}{N_r},$

where n.sub.rl is the index of the best Rx codeword for the l-th MPC obtained at the end of Step 2 of Algorithm 1, the uncertainty range of the l-th AoA should be

[00028]$\left[{\hat{}}_{}-\frac{2}{N_r},{\hat{}}_{}+\frac{2}{N_r}\right],$

which means that the candidate AoAs are the angle set obtained by sampling the angle range

[00029]$\left[{\hat{}}_{}-\frac{2}{N_r},{\hat{}}_{}+\frac{2}{N_r}\right]$

with an interval 2/(KN.sub.r). Consequently, the reduced Rx and Tx candidate AWVs are

[00030]$\begin{array}{cc}{\stackrel{\_}{A}}_r=\left[{\left[a_r\left({\hat{}}_1-\frac{2}{N_r}+\frac{2.Math.k}{{\mathrm{KN}}_r}\right)\right]}_{k=0,1,.Math.\mathrm{.Math.}.Math..Math.2.Math.K},{\left[a_r\left({\hat{}}_2-\frac{2}{N_r}+\frac{2.Math.k}{{\mathrm{KN}}_r}\right)\right]}_{k=0,1,.Math.\mathrm{.Math.}.Math..Math.2.Math.K},{\left[a_r\left({\hat{}}_L-\frac{2}{N_r}+\frac{2.Math.k}{{\mathrm{KN}}_r}\right)\right]}_{k=0,1,.Math.\mathrm{.Math.}.Math..Math.2.Math.K}\right],& \left(20\right)\\ \mathrm{and}& \\ {\stackrel{\_}{A}}_t=\left[{\left[a_t\left({\hat{}}_1-\frac{2}{N_t}+\frac{2.Math.k}{{\mathrm{KN}}_t}\right)\right]}_{k=0,1,.Math.\mathrm{.Math.}.Math..Math.2.Math.K},{\left[a_t\left({\hat{}}_2-\frac{2}{N_t}+\frac{2.Math.k}{{\mathrm{KN}}_t}\right)\right]}_{k=0,1,.Math.\mathrm{.Math.}.Math..Math.2.Math.K},{\left[a_t\left({\hat{}}_L-\frac{2}{N_t}+\frac{2.Math.k}{{\mathrm{KN}}_t}\right)\right]}_{k=0,1,.Math.\mathrm{.Math.}.Math.,2.Math.K}\right],& \left(21\right)\end{array}$

respectively, where

[00031]${\hat{}}_{}=-1+\frac{2.Math.m_{t.Math..Math.}-1}{N_t},$

where m.sub.tl is the index of the best Tx codeword for the l-th MPC obtained at the end of Step 2 of Algorithm I. Then H can be approximately expressed as H=.sub.r.sub.t.sup.H, where is a sparse matrix with every column and every row thereof having at most one nonzero element and with the nonzero elements corresponding to the channel coefficients .sub.l, i.e., || vec()||.sub.0=L. In a sequel,

[00032]$\begin{array}{cc}{.Math.H_{\mathrm{fd}}-\underset{=1}{\overset{L}{.Math.}}.Math.{}_{}.Math.a_r\left({}_{}\right).Math.{a_t\left({}_{}\right)}^H.Math.}_F=.Math.H_{\mathrm{fd}}-{\stackrel{\_}{A}}_r.Math..Math.{\stackrel{\_}{A}}_t^H.Math.{.Math.}_F.Math.=.Math.\mathrm{vec}\left(H_{\mathrm{fd}}-{\stackrel{\_}{A}}_r.Math..Math.{\stackrel{\_}{A}}_t^H\right).Math..Math.{.Math.}_2.Math.=.Math.\mathrm{vec}\left(H_{\mathrm{fd}}\right)-\mathrm{vec}\left({\stackrel{\_}{A}}_r.Math..Math.{\stackrel{\_}{A}}_t^H\right).Math..Math.{.Math.}_2.Math..Math.=.Math.\mathrm{vec}\left(H_{\mathrm{fd}}\right)-\left({\stackrel{\_}{A}}_t^{*}.Math.{\stackrel{\_}{A}}_r\right).Math..Math.\mathrm{vec}(.Math.).Math..Math.{.Math.}_2.Math..Math.=.Math.\mathrm{vec}\left(H_{\mathrm{fd}}\right)-\stackrel{\_}{Q}.Math.\mathrm{vec}(.Math.).Math.{.Math.}_2,& \left(22\right)\end{array}$

where |.|.sub.F represents Frobenius norm.

[0078] Hence, the problem (19) becomes

[00033]$\begin{array}{cc}\begin{array}{c}\underset{{}_{},{}_{}.Math.{}_{}}{\mathrm{minimize}.Math.}.Math..Math.\mathrm{vec}\left(H_{\mathrm{fd}}\right)-\stackrel{\_}{Q}.Math.\mathrm{vec}(.Math.).Math.{.Math.}_2\\ \mathrm{subject}.Math..Math.\mathrm{to}.Math..Math..Math..Math.\mathrm{vec}(.Math.).Math.{.Math.}_0.Math.=L,\end{array}& \left(23\right)\end{array}$

which is a standard sparse reconstruction problem. By using the results of the VMA stage, the size of the dictionary matrix Q of the sparse reconstruction problem can be greatly reduced, and thus the problem can be efficiently solved by the classic orthogonal matching pursuit (OMP) method.

[0079] In practice, the number of MPCs (i.e., L) is not known a priori. Besides, in some cases, it is not necessary to estimate all of the MPCs. In such cases, the number of MPCs in the VMA-SR method of the present application, in both of the two stages, is set to L=L.sub.d, the desired number of MPCs. For instance, if we want to realize a 2-stream transmission, we only need to estimate L.sub.d=2 MPCs, no matter how many MPCs the channel really has.

[0080] Given a sufficiently large over-sampling factor K, it is possible to use the VMA-SR method to resolve MPCs with very close AoAs and AoDs, where the AoA and AoD gaps can be smaller than 2/N.sub.r, and 2/N.sub.t, respectively. In the VMA stage, we actually search an MPC cluster in each iteration, which can be either a single MPC or the summation of multiple adjacent MPCs with very close AoAs and AoDs. In the SR stage, we have implicitly assumed that there is only one MPC within each searched cluster in (23). If necessary, we can assume that there are adjacent MPCs with very close AoAs and AoDs within each cluster, and they can also be separately estimated by solving (23), with || vec()||.sub.0=L instead of || vec()||.sub.0=L. The value of usually runs from 2 to 4.

[0081] Since the sparse reconstruction stage does not need measurement, the total number of measurements of the VMA-SR method is

T.sub.VMA-SR=L(4.sup.S.sup.0+2(log.sub.2(N.sub.r)+log.sub.2(N.sub.t)2S.sub.0)+9) (24)

[0082] Note that this is the training overhead for an analog beamforming/combining structure. In the case of a hybrid structure, where parallel transmission of multiple-stream training sequences is available, the time cost will be further reduced. Simulation results show that the VMA-SR method according to the present application achieves a superior tradeoff between estimation performance and training penalty.

[0083] To make the method according to the present application applicable for both analog and hybrid beamforming/combining devices with strict constant-modulus constraint, we particularly design a codebook for the hierarchical search by using an enhanced sub-array scheme. And we need to design w(k,n) with beam widths 2/2.sup.k in the k-th layer, for k=0,1,2, . . . , log.sub.2 N. We obey the following procedures to compute w(k,n):

[0084] Step 1: Separate w(k,1) into S.sub.k=2.sup.(log.sup.2 .sup.Nk)/2 sub-arrays; thus each sub-array has N.sub.S=N/S.sub.k antennas.

[0085] Step 2: Set the AWVs of the S.sub.k sub-arrays.

[0086] For w(k,1), the steering angle space between adjacent sub-arrays is =2.sup.1k/S.sub.k, and the steering angles of the sub-arrays are

[00034]${}_m=-1+\frac{2.Math.m-1}{2}.Math.,m=1,2,\mathrm{.Math.}.Math.,S_k.$

The steering vector function a(N.sub.S,.sub.m) is defined as

[00035]$a\left(N_s,{}_m\right)={\frac{1}{\sqrt{N_s}}\left[e^{j.Math..Math..Math..Math.0.Math..Math.{}_m},e^{j.Math..Math..Math..Math.1.Math..Math.{}_m},\mathrm{.Math.}.Math.,e^{j.Math..Math..Math..Math.\left(N_s-1\right).Math..Math.{}_m}\right]}^T.$

Then, for m=1,2, . . . S.sub.k, set

[00036]${\left[w\left(k,1\right)\right]}_{\left(m-1\right).Math.N_s+1:{\mathrm{mN}}_s}=\sqrt{\frac{N_S}{N}}.Math.e^{j.Math..Math.{}_m}.Math.a\left(N_s,{}_m\right),$

where the co-phase .sub.m=m(N.sub.S1)/2N.sub.Sm(m1)/2,

[0087] Step 3: After the first codeword in the k-th layer w(k,1) obtained, all the other codewords in the k-th layer are found through rotating w(k,1) by

[00037]$\frac{2.Math.n-2}{2^k},n=2,3,\mathrm{.Math.}.Math.,2^k,$

respectively, i.e.,

[00038]$w\left(k,n\right)=w\left(k,1\right).Math..Math.\sqrt{N}.Math.a\left(N,\frac{2.Math.n-2}{2^k}\right),$

where is the entry-wise product.

[0088] It is clear that there is no deactivation operation for all the codewords. Thus, the codebook according to the present application does not need to turn off some antenna branches and thus increases the maximal total transmission power. FIG. 8 shows the Beam patterns of the enhanced sub-array scheme described above, where we can find that for the 1st and the 3rd layer codewords, the enhanced sub-array scheme can achieve a significantly higher beam gain, due to no deactivation operation. Meanwhile, we can find that for the enhanced sub-array scheme, the beam width of w(1,1) is indeed rowdily 2 tunes of that of w(2,1), and 4 times of that of w(3,1), which are in accordance with that in FIG. 3.

[0089] In this invention, we require that the number of elements of a uniform linear array (ULA), i.e., N, be M.sup.P for some positive integers M and p, which is because the proposed codebook design approach needs to divide the array or a sub-array into M smaller sub-arrays. For a ULA with an arbitrary number of elements, the sub-array technology is infeasible if N is not M to an integer power. Hence, the proposed codebook design approach may not be extended to ULAs with an arbitrary number of antenna elements without further modification or accommodation. There are two possible solutions in practice. One is to select a ULA with N being M to an integer power when designing the system, which is reasonable because the beamforming method should be considered in system planning. The other one is to exploit the proposed codebook design approach for beaming with M.sup. log.sup.M .sup.N antennas while deactivating the other ones, where . is the floor integer operation. Afterwards, further beam refinement can be launched with all the antennas activated.

[0090] In the context of this invention, we have adopted a ULA model. In practice, it is more convenient to use a uniform planar array (UPA) in an minWave device, especially when the size of the device is small, because a UPA is more compact than a ULA and can save much area with the same number of antennas. Thus, we generalize the hierarchical codebook, which is designed by applying the enhanced sub-array scheme to UPA. In fact, by exploiting the Kronecker product, a UPA codeword can be obtained based on two ULA codewords. We introduce it in detail as follows.

[0091] Suppose the size of a UPA is N.sub.xN.sub.y, where N.sub.x and N.sub.y are the number of antennas along x and y axes, respectively, and they both are integer powers of 2. Let w.sub.P(k,n.sub.x,n.sub.y) denote the n.sub.x and n.sub.y-th (along x and y axes, respectively) codeword in the k-th layer. Then we have

w.sub.P(k,n.sub.x,n.sub.y)=w.sub.x(k,n.sub.x).Math.w.sub.y(k,n.sub.y), (25)

where .Math. is the Kronecker product, w.sub.x(k,n.sub.x) is the n.sub.x-th codeword in the k-th layer of a ULA codebook with N.sub.x antennas, while w.sub.y(k,n.sub.y) is the n.sub.y-th codeword in the k-th layer of a ULA codebook with N.sub.y antennas. w.sub.x(k,n.sub.x) and w.sub.y(k,n.sub.y) are ULA codewords and can be computed according to the enhanced sub-array scheme.

[0092] Without loss of generality, we design a fully hierarchical UPA codebook by exploiting the approach shown in (25). We assume the size of the UPA is NN, and thus there is also (log.sub.2 N+1) layers in the codebook. In the k-th layer, k=0,1,2, . . . , log.sub.2 N, there are 4.sup.k codewords in total, which are {w.sub.P(k,n.sub.x,n.sub.y)|n.sub.x=1,2,3, . . . , 2.sup.k; n.sub.y=1,2,3, . . . , 2.sup.k}.

[0093] FIG. 9 shows the beam patterns of the codewords in the first layer of a UPA codebook, where the size of the UPA is 88 . It can be observed that there are 4.sup.1 codewords, and the beam coverage of a UPA codeword is a 2-dimensional angle domain, including the x and y-axes angel domains. The union of the beam coverage of the 4 codewords is roughly the whole 2-dimensional angle domain. The sub-beams within the beam coverage of each UPA codeword are due to the sub-array technique.

[0094] FIGS. 10 and 11 show the effect of the over-sampling factor K on the detection and mean squared error (MSE) performances of the VMA-SR approach. As we can see, the detection performance is improved little by increasing K when K2, while the MSE performance is consistently improved when increasing K. However, increasing K will result in larger dictionary matrix Q as shown in (23), which increases the computational complexity in the SR stage. In practice, a tradeoff between the MSE performance and the computational complexity is necessary to adopt appropriate K.