3380 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 15, NO. 5, MAY 2016Hierarchical Codebook Design for BeamformingTraining in Millimeter-Wave CommunicationZhenyu Xiao, Member, IEEE, Tong He, Pengfei Xia, Senior Member, IEEE, and Xiang-Gen Xia, Fellow, IEEEAbstract—In millimeter-wave communication, large antennaarrays are required to achieve high power gain by steering towardeach other with narrow beams, which poses the problem to efficiently search the best beam direction in the angle domain atboth Tx and Rx sides. As the exhaustive search is time consuming, hierarchical search has been widely accepted to reduce thecomplexity, and its performance is highly dependent on the codebook design. In this paper, we propose two basic criteria forthe hierarchical codebook design, and devise an efficient hierarchical codebook by jointly exploiting sub-array and deactivation(turning-off) antenna processing techniques, where closed-formexpressions are provided to generate the codebook. Performanceevaluations are conducted under different system and channelmodels. Results show superiority of the proposed codebook overthe existing alternatives.Index Terms—Millimeter wave communication, mmWave,beamforming, codebook design, hierarchial search.I. INTRODUCTIONM ILLIMETER-WAVE (mmWave) communication is a promising technology for next-generation wirelesscommunication owing to its abundant frequency spectrumresource, which promises a much higher capacity than the existing wireless local area networks (WLANs) and the current cellular mobile communication. In fact, mmWave communicationhas received increasing attentions as an important candidatetechnology in both the next-generation WLANs [1]–[7] andmobile cellular communication [8]–[16]. A fundamental challenge to mmWave communication is the extremely high pathloss, thanks to the very high carrier frequency on the order of30-60 GHz. To bridge this significant link budget gap, jointTx/Rx beamforming is usually required to bring large antennaManuscript received July 17, 2015; revised November 16, 2015; acceptedJanuary 17, 2016. Date of publication January 22, 2016; date of current version May 6, 2016. This work was supported in part by the National NaturalScience Foundation of China (NSFC) under Grant 61571025, Grant 91338106,Grant 91538204, and Grant 61231013, in part by the National Basic ResearchProgram of China under Grant 2011CB707000, and in part by the Foundationfor Innovative Research Groups of the National Natural Science Foundation ofChina under Grant 61221061. The associate editor coordinating the review ofthis paper and approving it for publication was L. Song.Z. Xiao and T. He are with the School of Electronic and InformationEngineering, Beijing Key Laboratory for Network-Based Cooperative AirTraffic Management, Beihang University, Beijing 100191, China, and also withthe Beijing Laboratory for General Aviation Technology, Beihang University,Beijing 100191, China. (e-mail: [email protected]).P. Xia is with the Key Laboratory of Embedded System and ServiceComputing, Tongji University, Shanghai 201804, China.X.-G. Xia is with the Department of Electrical and Computer Engineering,University of Delaware, Newark, DE 19716 USA.Color versions of one or more of the figures in this paper are available onlineat http://ieeexplore.ieee.org.Digital Object Identifier 10.1109/TWC.2016.2520930array gains, which typically requires a large Tx/Rx antennaarray size (e.g., an antenna array size of 36 is used in [4].).Fortunately, thanks to the small wavelength on the mmWavefrequency, large antenna arrays are possible to be packed into asmall area.In the mmWave domain, the high power consumption ofmixed signal components, as well as expensive radio-frequency(RF) chains, make it difficult, if not impossible, to realizedigital baseband beamforming as used in the conventionalmultiple-input multiple-output (MIMO) systems. Instead, analog beamforming is usually preferred, where all the antennasshare a single RF chain and have constant-amplitude (CA)constraint on their weights [4], [6], [17], [18]. Meanwhile, ahybrid analog/digital precoding structure was also proposedto realize multi-stream/multi-user transmission [9], [12], [13],where a small number of RF chains are tied to a large antennaarray. No matter whether the analog beamforming or the hybridprecoding structure is exploited, entry-wise estimation ofchannel state information (CSI) is time costly due to large-sizeantenna arrays, and a more efficient antenna training algorithmis needed.For the hybrid precoding structure, as the mmWave channelis generally sparse in the angle domain, different compressedsensing (CS) based channel estimation methods were proposed to estimate the steering angles of multipath components(MPCs) [9], [16], [19]–[21], where [19] is for point-to-pointmulti-stream transmission, [20] is for multi-user transmission,while [21], based on a presentation of antenna array with virtual elements, further enhances the channel estimation over[19]. For the analog beamforming structure, there in generalexist two different approaches. In [4], [6], [7], [22], an iterative beamforming training approach is adopted, in which thebeamforming vector on one side (transmitter or receiver) isalternatively optimized by fixing the beamforming vector on theother side, and the alternation is repeated iteratively to improvethe beamforming gain one iteration upon another. On the otherhand, in [17], [18], [23], a switched beamforming approachis adopted, where the beam search space (at the transmitterand receiver side, respectively) is represented by a codebookcontaining multiple codewords, and the best transmit/receivebeams are found by searching through their respective codebooks. Both approaches have their own merit and may be usefulin different applications.In this paper, we focus on switched beamforming for onestream transmissions. This is motivated by the fact that singlestream beamforming is actually capacity achieving in thevery-low SNR case [24]. Furthermore, single stream beamforming can be readily extended to the more complicated hybrid1536-1276 © 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.XIAO et al.: HIERARCHICAL CODEBOOK DESIGN FOR BEAMFORMING TRAINING IN MILLIMETER-WAVE COMMUNICATION 3381precoding case [19]. For switched beamforming, an exhaustivesearch algorithm may be used, which sequentially tests all thebeam directions in the angle domain and finds the best pair oftransmit/receive beamforming codewords. This is conceptuallystraightforward. However, the overall search time is prohibitive,because the number of candidate beam directions is usuallylarge for mmWave communication. To improve the search efficiency, a hierarchy of codebooks may be defined [3], [17], [18],[25]–[27]. For example, a coarse codebook may be defined witha small number of coarse/low-resolution beams (or sectors)covering the intended angle range, while a fine codebook may be defined with a large number of fine/high-resolution beamscovering the same intended angle range, and that a coarse beamFig. 1. Illustration of the system. may have the same/similar coverage as that of multiple finebeams together. A divide-and-conquer search may then be carried out across the hierarchy of codebooks, by finding the bestsector (or coarse beam) first on the low-resolution codebook level, and then the best fine beam on the high-resolution codeThe rest of this paper is as follows. In Section II, the sysbook level, with the best high-resolution beam contained by thetem and channel models are introduced. In Section III, thebest low-resolution beam.hierarchical codebook design is presented. In Section IV, perPerformances of the switched beamforming schemes, including the search time and success rate, are highly dependentformance evaluation is conducted. The conclusion is drawnlastly in Section V.on the hierarchical codebook design. In [17], [18], althoughSymbol Notations: a, a, A, and A denote a scalar variable, wider beams were proposed to speed up beam search, designapproaches to broaden the beams were not studied. In [25],codewords with wider beams were generated by summingtwo codewords with narrower beams, but the CA constraintwas no longer satisfied. In [26], a sub-array method was proposed to broaden the beam width by pointing the sub-arraybeams in slightly-gapped directions. However, a full hierarchical codebook was not explicitly designed therein, and thisapproach may be not feasible to design very wide or evenomni-directional beams. In [19], the hybrid precoding structure was adopted to shape wider beams by exploiting thesparse reconstruction approach, but high-quality wide beamscan be shaped only when the number of RF chains is largeenough and deep sinks within the angle range appear otherwise.In [27], a binary-tree structured hierarchical codebook wasdesigned by using antenna deactivation, where wider beamswere generated by turning off part of the antennas. A completecodebook was designed with closed-form expressions providedtherein. However, the number of active antennas is too smallfor very wide or omni-directional beams, which may limitits application in mmWave communication, where per-antennatransmission power is limited.In this paper, we first propose two basic criteria for arbitrary hierarchical codebook designs, and then devise an efficienthierarchical codebook by jointly exploiting sub-array and deactivation (turning-off) antenna processing techniques. Closedform expressions are provided to generate the codebook. In theproposed approach, the beams of the sub-arrays steer towardswidely-gapped directions to broaden beams, which is essentially different from [26], and the deactivation operates on thesub-arrays instead of individual antennas like that in [27]. To the best of our knowledge, this is the first to propose these two criLetting s denote the transmitted symbol with unit power, theteria and the joint sub-array and deactivation codebook design.received signal isPerformance evaluations are conducted under both line-of-sight(LOS) and non-LOS (NLOS) channels, as well as with bothy = PtotwHwTs + wn,(1) total and per-antenna transmission power models. Results showsuperiority of the proposed codebook over the existing alternatives, especially when the per-antenna transmit power isconstrained.a vector, a matrix, and a set, respectively. (·)∗, (·)T and (·)Hdenote conjugate, transpose and conjugate transpose, respectively. E(·) denotes expectation operation. [a]i and [A]i j denotethe i-th entry of a and the i-row and j-column entry of A,respectively. [a]i: j denotes a vector with entries being the i-thto j-th entries of [a]. | · | and · denote the absolute value andtwo-norm, respectively.II. SYSTEM AND CHANNEL MODELSA. System ModelWithout loss of generality, we consider an mmWave communication system with half-wave spaced uniform linear arrays(ULAs) of NT and NR elements equipped at the transmitter andreceiver, respectively [5], [17], [28], [29], as shown in Fig. 1,where a single RF chain is tied to the ULA at both the transmitter and receiver, and thus the analog beamforming structureis adopted. At the transmitter, each antenna branch has a phaseshifter and power amplifier (AP) to drive the antenna, whileat the receiver, each antenna branch has a low-noise amplifier(LNA) to amplify the signal and a phase shifter. It is noted thatas the analog beamforming can be seen as one of the branchesof the hybrid precoding structure, the proposed criteria andcodebook design can be naturally used by the hybrid precodingstructure, which will be shown in Section III-D. Additionally,in our system each antenna branch can be deactivated or turnedoff, i.e., there is a switch in each antenna branch at both sidesalthough not depicted in the figure. Generally, all the PAs, aswell as the LNAs, have the same scaling factor if activated.Thus, each element of the antenna weight vectors (AWVs) atthe both sides either has a constant amplitude or is zero.H RH R3382 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 15, NO. 5, MAY 2016where Ptot is the total transmission power of all the activeantennas, wT and wR are the transmit and receive AWVs,respectively, H is the channel matrix, n is the Gaussian noisevector with power N0, i.e., E(nnH) = N0I. Let W(N) denotea set of vectors with N entries as shown in (3), at the bottomof the page, where ν is a normalization factor such that all thevectors have unit power. We can find that each entry of an arbitrary vector in W(N) has either an amplitude ν (activated) oris 0 (deactivated). Consequently, we have wT ∈ W(NT), andwR ∈ W(NR). It is noted that this signaling is based on the totaltransmission power, and we can further define the total transmission SNR as γtot = Ptot/N0, and the received SNR with thetotal transmission power model as ηtot = γtot|wHwT|2.The power gain under this model is(2) H RGtot =ηtotγtot= |wH RHwT|2, (4)which is also the array gain.On the other hand, in mmWave communication the scaling abilities of PAs are generally limited. Thus, a per-antennatransmission power model is also with significance to characterize the best transmission ability of the transmitter, which isshown asy = PperNTactwH RHwTs + wH Rn, (5)where Pper is the per-antenna transmission power, NTact is thenumber of active antennas of wT, which varies as different wT.Also, we have wT ∈ W(NT), and wR ∈ W(NR). In addition,the per-antenna transmission SNR is defined as γper = Pper/N0,and the received SNR with the per-antenna transmission powermodel is defined asηper = γperNTact|wH RHwT|2. (6)The power gain under this model isGper =ηperγper= NTact|wH RHwT|2, (7)which includes both the transmission power gain equal tothe number of active antennas NTact and the array gain|wH RHwT|2.It is worth mentioning that the total and per-antenna transmission power models are suitable for the cases that the scalingabilities of PA are high enough and limited, respectively.However, there is no difference for codebook design betweenwith these two models.B. Channel ModelSince mmWave channels are expected to have limited scattering [19], [29]–[32], MPCs are mainly generated by reflection.W(N) = {ν[β1ejθ1,β2ejθ2, . . . , βNejθN ]T | βi ∈ {0,1},θi ∈ [0,2π),i = 1,2, . . . , N} (3)That is, mmWave channels have the feature of directionality.Different MPCs have different physical transmit steering anglesand receive steering angles, i.e., physical angles of departure(AoDs) and angles of arrival (AoAs). Consequently, mmWavechannels are relevant to the geometry of antenna arrays. Withhalf-spaced ULAs adopted at the transmitter and receiver, thechannel matrix can be expressed as [19], [26], [27], [29],[33], [34] H = NTNRλa(NR, )a(NT,ψ)H,(8) L =1where λ is the complex coefficient of the -th path, L is thenumber of MPCs, a(·) is the steering vector function, and ψare cos(AoD) and cos(AoA) of the -th path, respectively. Letθ and ϕ denote the physical AoD and AoA of the -th path,respectively; then we have = cos(θ) and ψ = cos(ϕ).Therefore, and ψ are within the range [-11]. For convenience, in the rest of this paper, and ψ are called AoDsand AoAs, respectively. Similar to [19], [29], λ can be modeled to be complex Gaussian distributed, while θ and ϕ canbe modeled to be uniformly distributed within [0,2π]. a(·) is afunction of the number of antennas and AoD/AoA, and can beexpressed asa(N, ) =1 √N[ejπ0 ,ejπ1 , . . . ,ejπ(N-1) ]T, (9)where N is the number of antennas (N is NT at the transmitter and MR at the receiver), is AoD or AoA. It is easyto find that a(N, ) is a periodical function which satisfiesa(N, ) = a(N, + 2). The channel matrix H also has powernormalizationL =1E(|λ|2) = 1. (10)C. The ProblemFrom a system level, joint Tx/Rx beamforming is required tomaximize the received SNR, i.e.,Maximize ηtot = γtot|wH RHwT|2 or ηper = γperNTact|wHwT|2,Subject to wR ∈ WR,wT ∈ WT.(11) H RClearly, if H is known at the transmitter and receiver, andthere is no CA constraint, the optimal wT and wR can be easily solved by singular value decomposition (SVD). However,in mmWave communication it is too time costly for entry-wiseestimation of the channel matrix, which has a large scale dueto large antenna arrays, and there exists the CA constraint.Thus, the SVD approach is basically not feasible for mmWavecommunication.XIAO et al.: HIERARCHICAL CODEBOOK DESIGN FOR BEAMFORMING TRAINING IN MILLIMETER-WAVE COMMUNICATION 3383Fortunately, according to (8) the mmWave channel has uncer tainty mainly on AoDs/AoAs at both sides. In such a case, theone-stream beamforming problem in (11) can be simplified tofind the AoD/AoA of an arbitrary strong MPC (or better theA(w, ) = √Na(N, )Hw =n=1[w]ne-jπ(n-1) , (12) strongest MPC)1, and set wT and wR as the Tx/Rx steeringvectors pointing to these AoD/AoA.To this end, a straightforward way is to evenly sample the angle domain [-1,1] with a small interval, e.g., 1/N for anN antenna-array, and sequentially test all these sampled angleswith corresponding steering vectors at both sides. This is theCV(w) = | |A(w, )| > ρ max ω |A(w,ω)|,(13) exhaustive search method. Clearly the codebooks for exhaustive search are composed by only steering vectors. Althoughexhaustive search is feasible and can always find the best MPC,it has a time complexity O(N 2) [27], [35], which is too high forlarge arrays. Thus, hierarchical search is widely used to reducethe search time. In fact, the search time is highly dependent onthe design of the Tx/Rx codebooks, which are subsets of WTand WR, respectively. Hence, we focus on the codebook designin this paper.III. HIERARCHICAL CODEBOOK DESIGNIn this section, we design a hierarchical codebook composedby codewords (or AWVs) with different beam widths, whichhelps the search efficiency in finding the steering vectors of a strong or the strongest MPC at both sides. It is noted that,based on the specific structure of the mmWave channel model,the codebook design is to establish a relationship between theNk∪n=1CV(w(k,n)) = [-1,1],k = 0,1, . . . , K,(14)codewords in the angle domain to speed up the beam search.Thus, the codebook design is in fact irrelevant to the instanwhere Nk is the number of codewords in the k-th layer, K it themaximal index of the layer (there are K + 1 layers in total).taneous channel response. When beamforming is required inCriterion 2: The beam coverage of an arbitrary codeword practice before data transmission, a beam search process needsto be launched based on the designed codebook to find thesuitable beamforming weights (steering vectors) for a givenchannel. For different channels, the codebook is the same, but the searched optimal steering vectors are different dependingon the channel responses.(15) Although several hierarchial search schemes have been proposed for beam search in both literatures [25]–[27] and somestandards, like IEEE 802.15.3c and IEEE 802.11ad [3], [17],[18], to the best of our acknowledge, there are no criteria pro posed to judge whether a codebook is suitable or not, and thereare few complete hierarchical codebooks with closed-formexpressions provided for mmWave communication. Therefore,in this section, we first propose two basic criteria to designa hierarchical codebook, and then design one jointly usingsub-array and deactivation techniques based on the proposedcriteria.It is clear that Criterion 1 guarantees the full coverage, i.e.,there is no miss of any angle during the beam search, whileCriterion 2 establishes a tree-fashion relationship between thecodewords, which enables hierarchical search. If each parentcodeword has M child codewords, all the codewords in thecodebook constitute an M-way tree with respect to their beamcoverage in the angle domain. In such a case, hierarchicalsearch can be easily realized by using the tree search algorithmin both the receiver and transmitter as following [19], [27].The Hierarchical Search: Initially, we fix the transmitter toA. Two CriteriaBefore introducing the two criteria, we first introduce twobe in an omni-directional mode, and run an M-way tree searchdefinitions here. Let A(w, ) denote the beam gain of w alongangle , which is defined asfor logM(NR) stages to find the best receive codeword. Andthen we fix the receiver to be in a directional mode with thefound best receive codeword, and then run an M-way tree 1Basically, under LOS channel, where there is a LOS component significantly stronger than the other MPCs, the best MPC (the LOS component) needsto be found; while under NLOS channel, where all the MPCs have similarstrengths, an arbitrary strong MPC can be feasible.Nwhere N is the number of elements of w.Let CV(w) denote the beam coverage in the angle domain ofAWV w, which can be mathematically expressed aswhere ρ is a factor within (0,1) to determine the beam coverageof w. It is easy to find that the coverage is smaller as ρ becomesgreater. When ρ = 1/√2, the beam coverage is the 3dB coverage, and the beam width is the well-known 3dB beam width.Different codebook design methods may have different valuesof ρ, and codewords with different beam widths in the samecodebook may also have different values of ρ.Hierarchical search is simply layered search, i.e., the AWVswithin the codebook are layered according to their beam width.AWVs with a lower layer have larger beam width. Lettingw(k,n) denote the n-th codeword (or AWV) in the k-th layer,the two criteria are presented as follows.Criterion 1: The union of the beam coverage of all thecodewords within each layer should cover the whole angledomain, i.e.,within a layer should be covered by the union of those of severalcodewords in the next layer, i.e.,CV(w(k,n)) ⊆ ∪m∈Ik,nCV(w(k + 1,m)),k = 0,1, . . . , K – 1,where Ik,n is the index set with indices of the codewords inthe (k + 1)-th layer for the n-th codeword in the k-th layer. Forconvenience, we call w(k,n) a parent codeword, and {w(k +1,m)|m ∈ Ik,n} the child codewords of w(k,n).search for logM(NT) stages to find the best transmit codeword.In each stage, we have M candidate codewords, which are theM child codewords of a parent codeword found in the last stage.3384 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 15, NO. 5, MAY 2016Fig. 2. Beam coverage of a binary-tree structured codebook.We need to test all the M codewords one by one to find the bestone, and treat it as a new parent codeword for the next-stagesearch. Therefore, the search time (number of tests) for Tx/Rxjoint training isT = M logM NT + M logM NR. (16)In the next subsection we will design a codebook withM = 2, for the reason that when M = 2 the codebook treeis a typical binary tree, and the number of antennas is powers of two, which is generally used in antenna array design.Nevertheless, extending the proposed method to other values ofM is straightforward.B. The Deactivation ApproachAs a basis of the joint sub-array and deactivation approach,we first introduce the deactivation (DEACT) approach in thissubsection to design a binary-tree codebook, which has thebeam coverage shown in Fig. 2, where there are log2(N) + 1layers with indices from k = 0 to k = log2(N), and the numberof codewords in the k-th layer Nk = 2k. Here N denotes thenumber of antennas of an arbitrary array. Thus, N = NT at thetransmitter and N = NR at the receiver. Besides, we haveCV(w(k,n)) = CV(w(k + 1,2n – 1)) ∪ CV(w(k + 1,2n)), k = 0,1, . . . , (log2(N) – 1),n = 1,2,3,… ,2k.(17)In our method, we defineCV(a(N, )) = – , +,(18) N1 N1 which means that the steering vectors have a beam width 2/Ncentering at the steering angle [24]. In other words, within thebeam coverage of a(N, ), it has the maximal beam gain alongthe angle , while the minimal beam gain along the angles ±1/N. Thus, we can compute the value of ρ for our codebook asρ = or(N, ) a(N, – 1/N)Ha(N, )a(N, )Ha(N, )a(N, + 1/N)Haa(N, )Ha(N, )=1 NN n=1ejπ(n-1)/N. (19)Fig. 3. Beam patterns of w(2, 1), w(2, 2), w(1, 1), w(1, 2) and w(0, 1) for theDEACT approach, where N = 128.Although the value of ρ depends on N, we have ρ ≈ 0.64 giventhat N is large, e.g., N ≥ 8. Even when N is small, ρ is stillclose to 0.64, e.g., ρ = 0.65 when N = 4.Notice that the N codewords in the last layer coveran angle range [-1,1] in total, which means that allthese codewords must have the narrowest beam width 2/Nwith different steering angles. In other words, the codewords in the last layer should be the steering vectorswith angles evenly sampled within [-1,1]. Consequently,we have CV(w(log2(N),n)) = [-1 + 2nN-2,-1 + 2Nn ], n =1,2, . . . , N. With the beam coverage of the last-layer codewords, we can further obtain that of the codewords inthe other layers in turn as an order of descending layerindices, i.e., obtain CV(w(log2(N) – 1,n)),CV(w(log2(N) –2,n)), . . . ,CV(w(0,n)) in turn. Finally, the beam coverage ofall the codewords can be uniformly written asCV(w(k,n)) = -1 + 2n2-k 2,-1 + 22nk ,k = 0,1,2,… ,log2 N,n = 1,2,3,… ,2k. (20)Comparing (20) with (18), it is clear that whenw(k,n) = a 2k,-1 + 2n – 12k T ,0T (N-2k)×1 T , (21)(20) is satisfied. This is just the deactivation approach that wasproposed in [27], where the number of active antennas is 2k inthe k-th layer, and the other antennas are all turned off. Fig. 3shows an example of beam pattern of the DEACT approach forthe case of N = 128. From this figure we find that the beamcoverage of w(0,1) is just the union of those of w(1,1) andw(1,2), while the beam coverage of w(1,1) is just the union ofthose of w(2,1) and w(2,2).C. The Joint Sub-Array and Deactivation ApproachIt is noted that for the deactivation approach, when k is small,the number of active antennas is small, or even 1 when k =0. This greatly limits the maximal total transmission power ofan mmWave device. In general, we hope the number of activeXIAO et al.: HIERARCHICAL CODEBOOK DESIGN FOR BEAMFORMING TRAINING IN MILLIMETER-WAVE COMMUNICATION 3385 antennas is as large as possible, such that higher power can beIn addition, w(k,1) has a beam coverage [-1,-1 + 22k ].transmitted, because in mmWave communication per-antennaAccording to Theorem 1,transmission power is usually limited. To achieve this target, weconsider jointly using the sub-array and deactivation approachCV(w(k,n)) here. As the key of this approach is BeaM Widening via SingleRF Subarray, we term it BMW-SS.We also want to design a codebook with the beam coverage shown in Fig. 2. According to (18), in the k-th layer, eachcodeword has a beam width of 2/2k. For the codewords ofthe last layer, we can also adopt the steering vectors according to (21). Compared with the codewords in the last layer,those in the lower layers have wider beams, and according to(20), codewords in the same layer have the same beam widthsbut different steering angles. Thus, there are two basic tasks inthe codebook design, namely to rotate the beam along requireddirections and to broaden the beam by required factors. We firstintroduce beam rotation.1) Beam Rotation: Beam rotation can be realized accordingto the following theorem.Theorem 1: CV(w ◦ √Na(N,ψ)) = CV(w) + ψ, where ◦represents entry-wise product (a.k.a. Hadamard product), N isthe number of elements of w, ψ is an arbitrary angle. A + ψis a new angle set with elements being those of the angle set Aadded by ψ.The proof is referred to Appendix A, and this theorem canbe used not only for the BMW-SS approach, but also for othercodebook design methods.Theorem 1 implies that given an arbitrary codeword w,we can rotate its beam coverage CV(w) by ψ with w ◦√Na(N,ψ). This theorem helps to design all the other codewords in the same layer once one codeword in this layer isfound. To explain this, we need to emphasize that all thecodewords in the same layer have the same beam widths butdifferent steering angles according to (20), which means thatthe beam coverage of all the codewords can be assumed to havethe same shape but different offsets in the angle domain. Thus,we can obtain one codeword based on another in the same layeras long as we know the angle gap between them according toTheorem 1. In particular, suppose we find the first codewordin the k-th layer w(k,1). According to (20), we do know thatthe angle gap between the n-th codeword in the k-th layer, i.e.,w(k,n), and w(k,1) is 2n-22k , n = 2,3, . . . ,2k. Then we canobtain the all the other codewords in this layer based on w(k,1)according to Theorem 1 (see Corollary 1 below).Corollary 1: Given the first codeword in the k-th layerw(k,1), all the other codewords in the k-th layer can be foundthrough rotating w(k,1) by 2n2-k 2, n = 2,3, . . . ,2k, respectively, i.e., w(k,n) = w(k,1) ◦ √Na(N, 2n2-k 2).Proof: To prove this corollary, we need to prove that,according to (20), when w(k,n) = w(k,1) ◦ √Na(N, 2n2-k 2),w(k,n) ∈ W(N) and CV(w(k,n)) = [-1 + 2n-22k ,-1 + 22nk ].Since[w(k,n)]i = [w(k,1) ◦ √Na(N, 2n – 22k )]i= [w(k,1)]i ejπ(n-1) 2n2-k 2 , (22)we have |[w(k,n)]i| = |[w(k,1)]i|. As w(k,1) ∈ W(N),w(k,n) ∈ W(N).= CV w(k,1) ◦ √Na N, 2n – 22k = CV(w(k,1)) + 2n – 22k= -1,-1 + 22k + 2n2-k 2= -1 + 2n2-k 2,-1 + 22nk . (23) 2) Beam Broadening: The remaining task is to broaden thebeam for each layer. Given an N-element array, generally wewould expect a beam width of 2/N. Nevertheless, this beamwidth is in fact achieved by concentrating the transmissionpower at a specific angle 0, i.e., by selecting AWV to maximize |A(w, 0)|. Intuitively, if we design the AWV to dispersethe transmission power along different widely-spaced angles,the beam width can be broadened. More specifically, if a largeantenna array is divided into multiple sub-arrays, and these subarrays point at sufficiently-spaced directions, a wider beam canbe shaped.To illustrate this, let us separate the N-antenna array into Msub-arrays with NS antennas in each sub-array, which meansN = M NS. In addition, letting fm = [w](m-1)NS+1:m NS, wehave [fm]n = [w](m-1)NS+n, m = 1,2, . . . , M. fm can be seenas the sub-AWV of the m-th sub-array. Therefore, the beam gainof w writesA(w,ω) =N n=1[w]ne-jπ(n-1)ω =m=1[w](m-1)NS+ne-jπ((m-1)NS+n-1)ωNS=m=1 n=1e-jπ(m-1)NSω[fm]ne-jπ(n-1)ω(24)e-jπ(m-1)NSωA(fm,ω), M NS n=1M =M m=1which means that the beam gain of w can be seen as theunion of those of fm. According to (18), by assigning fm =ejθma(NS,-1 + 2mN-S 1), where ejθm can be seen as a scalarcoefficient with unit norm for the m-th sub-array, the m-th subarray has beam coverage CV(fm) = [-1 + 2mN-S 2,-1 + 2NmS ],m = 1,2,… , M. Hence, w has the beam coverageCV(w) =M∪m=1CV(fm)=-1,-1+ 2NMS= -1,-1+ 2MN 2 ,(25)i.e., the beam width has been broadened by M2 by using thesub-array technique, where a broadening factor M comes fromthe number of sub-arrays, while another factor M results fromthe reduction factor of the sub-array size.3386 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 15, NO. 5, MAY 2016 However, in the above process, the mutual effects between2M2N . If we jointlydifferent sub-arrays are not taken into account. In the case ofusing the sub-array and deactivation method, we may obtainfm= ejθma(NS,-1 + 2mN-S 1), we haveA(w,ω) | fm = ejθma NS,-1 + 2m – 1NS codewords with beam widths 2NANS =2M NAN by setting asfm=⎧⎨⎩e– jm NS-(29) = NSM m=1e-jπ(m-1)NSωejθm× a(NS,ω)Ha NS,-1 + 2m – 1NS . (26)As the steering vector has the properties that a(NS,-1 +2m-1NS )Ha(NS,-1 + 2nN-S1) = 0 when m = n, the beam gain offmalong the angle -1 + 2mN-S 1 is affected little by fn. It is clearthat |A(w,-1 + 2mN-S 1)| = √NS for m = 1,2, . . . , M, whichmeans that the beam gains along angles ω = 1 + 2mN-S 1 aresignificant.Additionally, to reduce the beam fluctuation, it is requiredthat the intersection points in the angle domain of these coverage regions, i.e., ω = -1 + N2nS , n = 1,2, . . . , M – 1, alsohave high beam gain, and this can be realized by adjustingcoefficients ejθm. Concretely, we have (28), shown at the bottom of the page, where in (a) we have used the fact thata(NS,ω1)Ha(NS,ω2) is small and can be neglected when |ω1 –ω2| > 2/NS, in (b) we have exploited the condition that NSis even in this paper. To maximize |A(w,ω)|2, we face theproblemmaximizeθ| f (NS,θ)|2, (27)which has a solution that θ = (2k – NNS-S 1)π, where k ∈ Z.Thus, we may choose θm = – jm NNS-S 1π, which satisfies θ =π, to reduce the fluctuation of the beam.In summary, by using the sub-array method and setting fm =e– jm NNS- S 1πa(NS,-1 + 2mN-S 1), m = 1,2, . . . , M, we obtain aA(w,ω) | fm = ejθma NS,-1 + 2m – 1NS ,ω = -1 + N2nS = NSM m=1e-jπ(m-1)NSωejθma(NS,ω)Ha NS,-1 + 2m – 1NS (a)≈ NSe-jπ(n-1)NSωejθna NS,-1 + 2nNS Ha NS,-1 + 2nN-S 1+ NSe-jπnNSωejθn+1a NS,-1 + 2nNS Ha NS,-1 + 2nN+S 1=1√NS e-jπ(n-1)NSωejθn ×⎛⎝NS i=1e-jπ(i-1)/NS + ejπ NSωej(θn+1-θn)NS i=1ejπ(i-1)/NS⎞ ⎠(b)=1√NS e-jπ(n-1)NSωejθn ×⎛⎝NS i=1e-jπ(i-1)/NS + ejθNS i=1ejπ(i-1)/NS⎞ ⎠=1√NS e-jπ(n-1)NSωejθn f (NS,θ), (28)codeword w with a beam width 2MNS =NS 1πa(NS,-1 + 2mN-S 1),m = 1,2, . . . , NA,0NS×1,m = NA + 1, NA + 2, . . . , M.where NA is the number of active sub-arrays.3) Codebook Generation: Recall that we need to designw(k,n) with beam widths 2/2k in the k-th layer.When k = log2(N), we have w(log2(N),n) = a(N,-1 +2n-1N ), n = 1,2, . . . , N.When k = log2(N) – , where = 1,2,… ,log2(N), weobey the following procedures to compute w(k,n):• Separate w(k,1) into M = 2 (+1)/2 sub-arrays withfm= [w(k,1)](m-1)NS+1:mNS, where · is the flooringinteger operation, m = 1,2, . . . , M;• Set fm as (29), where NA = M/2 if is odd, and NA = Mif is even;• According to Corollary 1, we have w(k,n) = w(k,1) ◦√Na(N, 2(nN-1)), where n = 2,3,… ,2k;• Normalize w(k,n).Fig. 4 shows an example of the beam pattern of the BMWSS approach in the case of N = 128. From this figure we findthat the beam coverage of w(0,1) is just the union of those ofw(1,1) and w(1,2), while the beam coverage of w(1,1) is justthe union of those of w(2,1) and w(2,2). Comparing the beampattern of DEACT shown in Fig. 3 with that in Fig. 4, it canbe observed that although there are small-scale fluctuations forBMW-SS, the beams of BMW-SS appear flatter than those ofDEACT within the covered angle.On the other hand, for BMW-SS all the codewords eitherhave all the antennas activated, or have half of them activated,which shows a significant advantage over DEACT in termsof the maximal total transmission power, especially for theXIAO et al.: HIERARCHICAL CODEBOOK DESIGN FOR BEAMFORMING TRAINING IN MILLIMETER-WAVE COMMUNICATION 3387Fig. 4. Beam patterns of w(2, 1), w(2, 2), w(1, 1), w(1, 2) and w(0, 1) for theBMW-SS approach, where N = 128.Fig. 5. Comparison of the beam patterns of BMW-SS, DEACT, and theapproach in [19] (termed as Sparse) with the per-antenna transmission powermodel, where N = 32. Ld = 1 for the Sparse approach.low-layer codewords. Fig. 5 shows the comparison of beam patterns of BMW-SS, DEACT, and the approach in [19] (termed asSparse) with the per-antenna transmission power model, whereall the weights of active antennas have a unit amplitude. Fromthis figure, we find that BMW-SS offers much higher beamgains than DEACT due to exploiting much greater number ofactive antennas. In addition, for the Sparse codebook, when thenumber of RF chains is small, there are deep sinks within thebeam coverage of the wide-beam codewords, and the sink ismore severe when the number of RF chains is smaller, which arein accordance with the results in [19] (Fig. 5 therein). Clearly, ifthe AoD or AoA of an MPC is along the sink angle, it cannot bedetected with the codeword, which results in miss detection ofthe MPC. By contrast, BMW-SS does not have such deep sinks.It is noted that the corresponding hierarchical search of thedesigned codebook will eventually converge to a codeword ofthe last layer, i.e., a steering vector, at both ends. We can findthat the angle resolution of the last layer is 2/N. Thus, thedesigned codebook is just coarse codebook, while the corresponding search method is coarse search, like those in [27]. If ahigher angle resolution is required, a fine codebook composedby steering vectors with a smaller sampling gap than 2/N isnecessary. Details are referred to [27].D. Generalization1) For the Hybrid Precoding Structure: In this paper weadopt an analog beamforming structure, and both the proposedtwo criteria and the BMW-SS approach are based on the analogbeamforming structure. However, they are naturally feasible forthe hybrid precoding structure, because the analog beamforming structure can be seen as one of the branches of the hybridprecoding structure [19].To realize multi-stream transmission with the hybrid precoding structure, the AoDs and AoAs of multiple MPCs need tobe searched. The search process with BMW-SS based on thebeamforming structure in this paper can be adopted to searchthe AoD and AoA of each single MPC. In fact, similar extension from one-stream transmission to multi-stream transmissionhas been studied for the Sparse codebook in [19].2) For Other Types of Antenna Arrays: In this paper weadopt a ULA model. There are other types of antenna arrays inpractice, e.g., uniform planar array (UPA) and uniform circulararray (UCA). The proposed criteria and the BMW-SS approachcan be easily extended to the UPA model. In particular, for atypical 2-dimensional grid UPA with m × n elements, its steering vector can be expressed as the Kronecker product of thoseof two ULAs with m × 1 and n × 1 elements, respectively [26].The search process as well as the codebook design could beextended to the UPA model and will be studied later.On the other hand, for a UCA model, the two criteria arealso feasible, but that the beam coverage in Criterion 1 shouldbe extended to a 2-dimensional angle range, including boththe azimuth and elevation angle ranges. However, the proposedBMW-SS approach can hardly be extended to the UCA model,because the relation between the elements of a steering vector changes. It would be indeed interesting to design a newcodebook according to the proposed criteria with a UCA mode.3) For Arbitrary Number of Antenna Elements: In thispaper we require that the number of elements of a ULA (N) isM p for some positive integer p, which is because the BMW-SSapproach needs to divide the array or a sub-array into M smallersub-arrays. For a ULA with an arbitrary number of elements,the sub-array technology is infeasible if N is not M to an integerpower. Hence, the proposed approach may not be extended towith arbitrary number of antenna elements. There are two possible choices in practice. One is to select a ULA with N beingM to an integer power when designing the system, which isreasonable because the beamforming method should be considered in system planning. The other one is to exploit BMW-SSfor beamforming with M logM N antennas while deactivatingthe other ones, where · is the floor operation. Afterwards,further beam refinement can be launched with all the antennasactivated.IV. PERFORMANCE EVALUATIONIn this section, we evaluate the performance of the designedhierarchical codebook by the BMW-SS approach, and compareit with the alternatives. We consider two different system models on the transmission power, namely total transmission powerand per-antenna transmission power, which correspond to the3388 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 15, NO. 5, MAY 2016signal models in (1) and (5), respectively. The total transmission power signal model reflects the performance for the casethat the transmission power on each antenna branch can be highenough, while the per-antenna transmission power signal modelreflects the limit performance for the case that the transmission power on each antenna branch is limited2. The per-antennatransmission power model makes more sense in mmWave communication, where the output power of a single power amplifieris generally limited [2], [4]. The activation/deactivation operations of a codebook are irrelevant to the power models. Inparticular, no matter which power model is adopted, the codewords of BMW-SS either have all or half of the antennasactivated, those of DEACT have varying numbers of the antennas activated and the number may be quite small, while thoseof Sparse always have all the antennas activated.Besides, in the simulations, both LOS and NLOS channelmodels are considered based on (8). For LOS channel, thefirst MPC has a constant coefficient and random AoD andAoA, while the other NLOS MPCs have complex Gaussiandistributed coefficients and random AoDs and AoAs [26],[29]. The LOS MPC is generally much stronger than theNLOS MPCs. For NLOS channel, all the MPCs have complex Gaussian-distributed coefficients with the same varianceand random AoDs and AoAs [19], [26], [29]. Both the LOSand NLOS channels are sparse in the angle domain, becausethe number of MPCs is much smaller than the numbers of theTx/Rx antennas [19], [26], [29]. For all the codebooks, the hierarchical search method introduced in Section III-A is used. Theperformances of received SNR and success rate are all averaged on the instantaneous results of 104 random realizations ofthe LOS/NLOS channel.A. Total Transmission Power ModelIn this subsection, the total transmission power signal modelshown in (1) is used. With this model, the deactivation of antennas will not affect the total transmission power, i.e., the totaltransmission power is the same for the involved schemes.Fig. 6 shows the received power during each search stepwith the BMW-SS and DEACT codebooks under both LOSand NLOS channels, where NT = NR = 64, L = 3, Ptot = 1W, and N0 = 10-4 W, i.e., the SNR for beam training is sufficiently high, which means the length of the training sequence issufficiently long. The upper bound is achieved by the exhaustive search method. For the LOS channel, the LOS componenthas 15dB higher power than that of an NLOS MPC. Fromthis figure we can find that the received-power performanceof these two codebooks is similar to each other. Under bothchannels, at the beginning, i.e., in the first two steps, DEACTbehaves slightly better than BMW-SS; while in the followingsteps, BMW-SS slightly outperforms DEACT, until both methods achieve the same performance after the search process,because they have the same last-layer codewords. Meanwhile,both approaches reach the upper bound under LOS channel,while achieve a performance close to the upper bound under2The limit performance here refers to the performance in the case that all theactive antennas transmit with maximal power.Fig. 6. Received power during each search step with the BMW-SS and DEACTcodebooks under both LOS and NLOS channels, where NT = NR = 64, L =3, Ptot = 1 W, and N0 = 10-4 W. Step 1 to Step 6 is for Rx training, whileStep 7 to Step 12 is for Tx training.Fig. 7. Success rate of hierarchical search with the BMW-SS, DEACT andSparse codebooks under LOS channel, where NT = NR = 64, L = 3. η is thepower difference in dB between the LOS component and an NLOS MPC.NLOS channel. This is because under LOS channel, the LOScomponent is the optimal MPC, and it is acquired by all BMWSS, DEACT and the exhaustive search. However, under NLOSchannel, BMW-SS and DEACT acquire an arbitrary MPC of theL NLOS MPCs, which may not be the optimal one acquired bythe exhaustive search.Fig. 7 shows the success rate of hierarchical search withthe BMW-SS, DEACT and Sparse (proposed in [19]) codebooks under LOS channel, where NT = NR = 64, L = 3. ηis the power difference in dB between the LOS componentand an NLOS MPC. From this figure, it is observed that boththe transmission SNR γtot and η affect the success rate. Forall the codebooks, the success rate improves as γtot increases.However, due to the mutual effect of MPCs (i.e., spatial fading), the success rate improves little when γtot is already highenough. Basically when η is bigger, the mutual effect is less,and the success rate is higher. For the Sparse codebook, theperformance also depends on the number of RF chains. Whenthe number of RF chains is small, e.g., only 2, the deep sinksXIAO et al.: HIERARCHICAL CODEBOOK DESIGN FOR BEAMFORMING TRAINING IN MILLIMETER-WAVE COMMUNICATION 3389Fig. 8. Success rate of hierarchical search with the BMW-SS, DEACT andSparse codebooks under NLOS channel, where NT = NR = 64.within the covered angle (See Fig. 5) will sharply reduce thesuccess rate, as shown in Fig. 7. Furthermore, we can find thatthe success rate with the BMW-SS codebook is higher than thatwith the DEACT codebook. This is because the beams of theBMW-SS codebook are flatter than those of the DEACT codebook; thus they are more robust to the spatial fading. Also, thesuccess rate with the BMW-SS codebook is higher than thatwith the Sparse codebook when the number of RF chains is notlarge.Fig. 8 shows the success rate of hierarchical search withthe BMW-SS, DEACT and Sparse codebooks under NLOSchannel, where NT = NR = 64. From this figure, the same performance variation with respect to the transmission SNR γtotcan be observed as that in Fig. 7, and Sparse with 2 RF chainsalso has the poorest performance. In addition, BMW-SS basically outperforms DEACT and Sparse with 4 RF chains, and thesuperiority depends on L. When L = 1, i.e., there is only oneMPC, both BMW-SS and DEACT achieve a 100% success ratewhen γtot is high enough, because there is no spatial fading. Incontrast, Sparse cannot achieve a 100% success rate even whenL = 1, due to the deep sinks within the covered angle. WhenL > 1, all these schemes can hardly achieve a 100% successrate, due to the mutual effect of multiple MPCs.It is noteworthy that the superiority of BMW-SS versusDEACT in Fig. 6 is different from that in Figs. 7 and 8. Fig. 6just shows the variation of the received power during the searchprocess with a high SNR, while Figs. 7 and 8 show the searchresults over a wide SNR range. Fig. 6 actually corresponds tothe search process for a set of points in Figs. 7 and 8 with SNRequal of 40dB, and the received-power superiority of BMW-SSover DEACT in Fig. 6 will become larger if smaller SNR valuesare adopted.B. Per-Antenna Transmission Power ModelIn this subsection, the per-antenna transmission power signalmodel shown in (5) is used to compare the limit performancesof BMW-SS and DEACT with the same per-antenna transmission power. With this model, the deactivation of antennas willFig. 9. Received SNR during each search step with the BMW-SS and DEACTcodebooks under both LOS and NLOS channels, where NT = NR = 64, L =3, Pper = 1 W, and N0 = 10-4 W. Step 1 to Step 6 is for Rx training, whileStep 7 to Step 12 is for Tx training.significantly affect the total transmission power. In particular,the total transmission power is lower if the number of activeantennas is smaller.Fig. 9 shows the received power during each search stepwith the BMW-SS and DEACT codebooks under both LOS andNLOS channels, where NT = NR = 64, L = 3, Pper = 1 W,and N0 = 10-4 W. The upper bound is achieved by the exhaustive search method. For the LOS channel, the LOS componenthas 15dB higher power than that of an NLOS MPC. Comparingthis figure with Fig. 6, we find a significant difference thatwith the per-antenna transmission power model BMW-SS hasa distinct superiority over DEACT during the search process,especially at the beginning of the search process. The superiority is about 15 dB at the beginning, and it becomes less asthe search goes on, until vanishes at the end of beam search,i.e., the two methods achieve the same received SNR after thesearch process. The superiority of BMW-SS results from thefact that the number of the active antennas for the codewordswith wide beams is significantly greater than that for DEACT,and thus BMW-SS has a much higher total transmission powerthan DEACT when the per-antenna transmission power is thesame.Moreover, the increasing speed of received power is the samefrom Step 1 to Step 6 for both of the two schemes, but fromStep 7 to Step 12, the increasing speed for BMW-SS varies, andthat for DEACT becomes greater than that from Step 1 to Step6. This is because with per-antenna transmission power, thereare two power gains during the search process according to (4),namely the array gain provided by narrowing the Tx/Rx beamsand the total transmission power gain provided by increasingthe number of active transmit antennas. For DEACT, there isonly Rx array gain from Step 1 to Step 6, where Rx training isperformed, while there are both Tx array gain and total transmission power gain from Step 7 to Step 12, where Tx trainingis performed; thus, the increasing speed of received power isgreater from Step 7 to Step 12. For BMW-SS, there is also onlyRx array gain from Step 1 to Step 6 for Rx training; thus thereceived power consistently increases with the same speed as3390 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 15, NO. 5, MAY 2016Fig. 10. Success rate of hierarchical search with the BMW-SS and DEACTcodebooks under LOS channel, where NT = NR = 64, L = 3. η is the powerdifference in dB between the LOS component and an NLOS MPC.Fig. 11. Success rate of hierarchical search with the BMW-SS and DEACTcodebooks under NLOS channel, where NT = NR = 64.DEACT. But from Step 7 to Step 12 for Tx training, althoughthe Tx beam consistently becomes narrower, which means thatTx array gain is consistently improved, the number of activeantennas alternatively changes between NT and NT/2, whichmeans that the total transmission power may become larger orsmaller. Hence, when both the Tx array gain and total transmission power increase, the received power improves with a speedthe same as DEACT, while when the Tx array gain increasesbut the total transmission power decreases, the received SNRdoes not improve and may even decrease.It is noted that the superiority of BMW-SS over DEACT atthe beginning of the search process is with big significancefor mmWave communication, where per-antenna transmissionpower is generally limited. This superiority guarantees that withthe BMW-SS codebook, the success rate of beam search will beupgraded with the same transmission distance, or the transmission distance will be extended with the same success rate ofbeam search.Figs. 10 and 11 show the success rates of hierarchical searchwith the BMW-SS and DEACT codebooks under LOS andNLOS channels, respectively. The same simulation conditionsare adopted as those in Figs. 7 and 8, respectively, and thesame results can be obtained from Figs. 10 and 11 as thosefrom Figs. 7 and 8, respectively, except that the superiority ofBMW-SS over DEACT becomes more significant in Figs. 10and 11, which benefits from not only the fact that the beamsof the BMW-SS codebook are flatter than those of the DEACTcodebook, but also that the number of the active antennas ofthe BMW-SS codewords is basically much greater than that ofDEACT, which offers much higher total transmission power.Also, Figs. 10 and 11 reveal that even with low per-antennatransmission power, the success rate of BMW-SS can be closeto 100%, which is evidently better than those of DEACT andSparse.V. CONCLUSIONSIn this paper hierarchical codebook design has been studied for mmWave communication. Firstly, two basic criteriahave been proposed for the codebook design. Next, a complete binary-tree structured hierarchical codebook has beendesigned by jointly using sub-array and deactivation techniques, i.e., the BMW-SS approach. Performance evaluationhas been conducted with both a total transmission power and aper-antenna transmission power system models. Results showthat the BMW-SS codebook offers two advantages over thedeactivation codebook, namely flatter beams and much largernumber of active antennas. Both of these two advantages basically provide performance superiorities in terms of receivedpower during the search process and the success rate of beamsearch under both transmission power models, and the performance superiority is especially significant with the per-antennatransmission power system model. In addition, the BMW-SScodebook also outperforms the Sparse codebook, since thereare no deep sinks within the beam coverage for BMW-SS.APPENDIX APROOF OF THEOREM 1Given an arbitrary N-element vector w and two arbitraryangles ψ and , we want to prove that CV(w ◦ √Na(N,ψ)) =CV(w) + ψ, where A + ψ is a new angle set with elementsbeing those of the angle set A added by ψ. Note that w ◦√Na(N,ψ) is actually a new vector achieved based on w andthe steering vector a(N,ψ). Let us first see the beam gain ofthis new vector.A(w ◦ √Na(N,ψ), )(a)= √Na(N, )H(w ◦ √Na(N,ψ))(b)=Nn=1[w]nejπ(n-1)ψe-jπ(n-1)=Nn=1[w]ne-jπ(n-1)( -ψ)(c)= A(w, – ψ), (30)XIAO et al.: HIERARCHICAL CODEBOOK DESIGN FOR BEAMFORMING TRAINING IN MILLIMETER-WAVE COMMUNICATION 3391where (a) and (c) are according to the definition of the beamgain in (12), while (b) is obtained according to definition of theentry-wise product.Thus, we further haveCV(w ◦ √Na(N,ψ))(a)= { | |A(w ◦ √Na(N,ψ), )| >ρ maxω|A(w ◦ √Na(N,ψ), ω)|}(b)= { | |A(w, – ψ)| > ρ maxω|A(w,ω – ψ)|}(c)= { | |A(w, – ψ)| > ρ maxω|A(w,ω)|}(d)= { 0 + ψ| |A(w, 0)| > ρ maxω|A(w,ω)|}(e)= { 0| |A(w, 0)| > ρ maxω|A(w,ω)|} + ψ= CV(w) + ψ, (31)where (a) is according to the definition of beam coverage in(13), (b) is according to (30), (c) is based on the fact that themaxima of |A(w, – ψ)| does not depend on the angle offsetψ, (d) is obtained by letting = 0 + ψ, and (e) is obtainedaccording to the definition of an angle set plus a single angle inTheorem 1.ACKNOWLEDGMENTThe authors would like to thank the editor and the anonymous reviewers for their many useful and detailed commentsthat have helped to improve the presentation of this manuscript.The authors would also like to thank the authors of [19] for sharing their source code online, and particularly thank Dr. AhmedAlkhateeb for his kind help in explaining how to use the sourcecode.REFERENCES[1] R. C. Daniels, J. N. Murdock, T. S. Rappaport, and R. W. Heath, “60 GHzwireless: Up close and personal,” IEEE Microw. Mag., vol. 11, no. 7,pp. 44–50, Dec. 2010.[2] K.-C. Huang and Z. Wang, Millimeter Wave Communication Systems.Hoboken, NJ, USA: Wiley/IEEE Press, 2011.[3] E. Perahia, C. Cordeiro, M. Park, and L. L. Yang, “IEEE 802.11 ad:Defining the next generation multi-Gbps Wi-Fi,” in Proc. IEEE Consum.Commun. Netw. Conf. (CCNC), Las Vegas, NV, USA, Jan. 2010, pp. 1–5.[4] S. K. Yong, P. Xia, and A. Valdes-Garcia, 60 GHz Technology for GbpsWLAN and WPAN: From Theory to Practice. Hoboken, NJ, USA: Wiley.[5] Z. Xiao, “Suboptimal spatial diversity scheme for 60 GHz millimeterwave WLAN,” IEEE Commun. Lett., vol. 17, no. 9, pp. 1790–1793, Sep.2013.[6] P. Xia, H. Niu, J. Oh, and C. Ngo, “Practical antenna training for millimeter wave MIMO communication,” in Proc. IEEE Veh. Technol. Conf.(VTC’08), Calgary, AB, Canada, Oct. 2008, pp. 1–5.[7] P. Xia, S. K. Yong, J. Oh, and C. Ngo, “Multi-stage iterative antenna training for millimeter wave communications,” in Proc. IEEE GLOBECOMConf., New Orleans, LA, USA, Dec. 2008, pp. 1–6.[8] F. Khan and J. Pi, “Millimeter-wave mobile broadband: Unleashing 3–300 GHz spectrum,” in Proc. IEEE Wireless Commun. Netw. Conf.,Cancun, Mexico, Mar. 2011, pp. 1–6.[9] A. Alkhateeb, J. Mo, N. González-Prelcic, and R. Heath, “MIMO precoding and combining solutions for millimeter-wave systems,” IEEECommun. Mag., vol. 52, no. 12, pp. 122–131, Dec. 2014.[10] J. Choi, “On coding and beamforming for large antenna arrays in mmwave systems,” IEEE Wireless Commun. Lett., vol. 3, no. 2, pp. 193–196,Apr. 2014.[11] S. Han, C.-L. I, Z. Xu, and C. Rowell, “Large-scale antenna systems withhybrid analog and digital beamforming for millimeter wave 5 G,” IEEECommun. Mag., vol. 53, no. 1, pp. 186–194, Jan. 2015.[12] W. Roh et al., “Millimeter-wave beamforming as an enabling technology for 5G cellular communications: Theoretical feasibility and prototyperesults,” IEEE Commun. Mag., vol. 52, no. 2, pp. 106–113, Feb. 2014.[13] S. Sun, T. S. Rappaport, R. Heath, A. Nix, and S. Rangan, “MIMO formillimeter-wave wireless communications: Beamforming, spatial multiplexing, or both?” IEEE Commun. Mag., vol. 52, no. 12, pp. 110–121,Dec. 2014.[14] Y. Niu, Y. Li, D. Jin, L. Su, and A. V. Vasilakos, “A survey of millimeterwave communications (mmwave) for 5G: Opportunities and challenges,”Wireless Netw., vol. 21, no. 8, pp. 1–20, Apr. 2015.[15] P. Wang, Y. Li, X. Yuan, L. Song, and B. Vucetic, “Tens of gigabits wireless communications over E-band LoS MIMO channels with uniformlinear antenna arrays,” IEEE Trans. Wireless Commun., vol. 13, no. 7,pp. 3791–3805, Jul. 2014.[16] P. Wang, Y. Li, L. Song, and B. Vucetic, “Multi-gigabit millimeter wavewireless communications for 5G: From fixed access to cellular networks,”IEEE Commun. Mag., vol. 53, no. 1, pp. 168–178, Jan. 2015.[17] J. Wang et al., “Beam codebook based beamforming protocol for multiGbps millimeter-wave WPAN systems,” IEEE J. Sel. Areas Commun.,vol. 27, no. 8, pp. 1390–1399, Oct. 2009.[18] J. Wang et al., “Beamforming codebook design and performance evaluation for 60 GHz wideband WPANs,” in Proc. IEEE Veh. Technol. Conf.(VTC-Fall), Alaska, AK, USA, Sep. 2009, pp. 1–6.[19] A. Alkhateeb, O. El Ayach, G. Leus, and R. Heath, “Channel estimationand hybrid precoding for millimeter wave cellular systems,” IEEE J. Sel.Topics Signal Process., vol. 8, no. 5, pp. 831–846, Oct. 2014.[20] A. Alkhateeb, G. Leus, and R. W. Heath Jr., “Compressed sensingbased multi-user millimeter wave systems: How many measurements areneeded?” in Proc. IEEE Int. Conf. Acoust. Speech Signal Process., May2015, pp. 2909–2913.[21] Y. Peng, Y. Li, and P. Wang, “An enhanced channel estimation method formillimeter wave systems with massive antenna arrays,” IEEE Commun.Lett., vol. 19, no. 9, pp. 1592–1595, Sep. 2015.[22] Z. Xiao, L. Bai, and J. Choi, “Iterative joint beamforming training withconstant-amplitude phased arrays in millimeter-wave communications,”IEEE Commun. Lett., vol. 18, no. 5, pp. 829–832, May 2014.[23] M. Kokshoorn, P. Wang, Y. Li, and B. Vucetic, “Fast channel estimationfor millimetre wave wireless systems using overlapped beam patterns,”in Proc. IEEE Int. Conf. Commun. (ICC), London, U.K., Jun. 2015,pp. 1304–1309.[24] D. Tse and P. Viswanath, Fundamentals of Wireless Communication.London, U.K.: Cambridge Univ. Press.[25] L. Chen, Y. Yang, X. Chen, and W. Wang, “Multi-stage beamformingcodebook for 60 GHz WPAN,” in Proc. 6th Int. ICST Conf. Commun.Netw. China (CHINACOM), Harbin, China, Aug. 2011, pp. 361–365.[26] S. Hur, T. Kim, D. J. Love, J. V. Krogmeier, T. A. Thomas, and A. Ghosh,“Millimeter wave beamforming for wireless backhaul and access in smallcell networks,” IEEE Trans. Commun., vol. 61, no. 10, pp. 4391–4403,Oct. 2013.[27] T. He and Z. Xiao, “Suboptimal beam search algorithm and codebook design for millimeter-wave communications,” Mobile Netw. Appl.,vol. 20, no. 1, pp. 86–97, Jan. 2015.[28] Z. Xiao, X.-G. Xia, D. Jin, and N. Ge, “Multipath grouping formillimeter-wave communications,” in Proc. IEEE Global Commun. Conf.(GLOBECOM), Atlanta, GA, USA, Dec. 2013, pp. 3378–3383.[29] Z. Xiao, X.-G. Xia, D. Jin, and N. Ge, “Iterative eigenvalue decomposition and multipath-grouping Tx/Rx joint beamformings for millimeterwave communications,” IEEE Trans. Wireless Commun., vol. 14, no. 3,pp. 1595–1607, Mar. 2015.[30] T. Rappaport, F. Gutierrez, E. Ben-Dor, J. Murdock, Y. Qiao, and J. Tamir,“Broadband millimeter wave propagation measurements and modelsusing adaptive beam antennas for outdoor urban cellular communications,” IEEE Trans. Antennas Propag., vol. 61, no. 4, pp. 1850–1859,Apr. 2013.[31] T. S. Rappaport, Y. Qiao, J. I. Tamir, J. N. Murdock, and E. Ben-Dor,“Cellular broadband millimeter wave propagation and angle of arrival foradaptive beam steering systems,” in Proc. IEEE Radio Wireless Symp.(RWS), Santa Clara, CA, USA, Jan. 2012, pp. 151–154.[32] A. M. Sayeed and V. Raghavan, “Maximizing MIMO capacity in sparsemultipath with reconfigurable antenna arrays,” IEEE J. Sel. Topics SignalProcess., vol. 1, no. 1, pp. 156–166, Jun. 2007.3392 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 15, NO. 5, MAY 2016[33] O. El Ayach, S. Rajagopal, S. Abu-Surra, Z. Pi, and R. Heath, “Spatiallysparse precoding in millimeter wave MIMO systems,” IEEE Trans.Wireless Commun., vol. 13, no. 3, pp. 1499–1513, Mar. 2014.[34] J. Nsenga, W. Van Thillo, F. Horlin, V. Ramon, A. Bourdoux, andR. Lauwereins, “Joint transmit and receive analog beamforming in60 GHz MIMO multipath channels,” in Proc. IEEE Int. Conf. Commun.(ICC), Dresden, Germany, Jun. 2009, pp. 1–5.[35] B. Li, Z. Zhou, W. Zou, X. Sun, and G. Du, “On the efficient beamforming training for 60 GHz wireless personal area networks,” IEEETrans. Wireless Commun., vol. 12, no. 2, pp. 504–515, Feb. 2013.Zhenyu Xiao (M’14) received the B.E. degreefrom the Department of Electronics and InformationEngineering, Huazhong University of Science andTechnology, Wuhan, China, in 2006, and thePh.D. degree from the Department of ElectronicEngineering, Tsinghua University, Beijing, China,in 2011. From 2011 to 2013, he served asa Postdoctororal Fellow with the Department ofElectrical Engineering, Tsinghua University, Beijing,China. Since 2013, he has been a Lecturer withBeihang University, Beijing, China. He has authoredover 50 papers. His research interests include communication signal processing and practical system implementation for wideband communicationsystems, which cover synchronization, multipath signal processing, diversity,and multiple antenna technology, millimeter-wave communications, and UAVnetworks. He served as a Reviewer for the IEEE TRANSACTIONS ON SIGNALPROCESSING, the IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS,the IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, and the IEEECOMMUNICATIONS LETTERS. He served as a TPC Member of IEEEGLOBECOM’12, the IEEE WCSP’12, and the IEEE ICC’15.Tong He received the B.E. degree from theDepartment of Electronic and InformationEngineering, Beihang University, Beijing, China,in 2012. He is currently pursuing the Ph.D. degreeat the Department of Electronic and InformationEngineering, Beihang University. His researchinterests include millimeter-wave communications.Pengfei Xia (S’03–M’05–SM’10) received the Ph.D.degree from the Department of Electrical andComputer Engineering, University of Minnesota,Twin Cities, MN, USA, in 2005. Currently, he is aFull Chair Professor with the College of Electronicsand Information, Tongji University, Shanghai, China.He has authored over 50 IEEE journal and conferencepapers, and have more than 70 U.S. patents and/orpatent applications. His research interests includethe intersection of wireless communications, wirelessnetworks, signal and data processing, including 4GLTE/5G cellular systems, IEEE 802.11 WLANs, millimeter wave wirelessscommunications, transceiver beamforming, and unlicensed band communications. He coedited one of the first books on millimeter wave wirelesscommunications “60GHz Technology for Gbps WLAN and WPAN: FromTheory to Practice.” Currently, he serves as SPCOM technical committee member and SPCOM Industrial/Government Subcommittee Chair for the IEEESignal Processing Society. He was the recipient of the IEEE Signal ProcessingSociety Best Paper Award 2011.Xiang-Gen Xia (M’97–S’00–F’09) received theB.S. degree in mathematics from Nanjing NormalUniversity, Nanjing, China, in 1983, the M.S. degreein mathematics from Nankai University, Tianjin,China, in 1986, and the Ph.D. degree in electrical engineering from the University of SouthernCalifornia, Los Angeles, CA, USA, in 1992. Hewas a Senior/Research Staff Member with HughesResearch Laboratories, Malibu, CA, USA, from1995 to 1996. In September 1996, he joined theDepartment of Electrical and Computer Engineering,University of Delaware, Newark, DE, USA, where he is the Charles BlackEvans Professor. His research interests include space-time coding, MIMOand OFDM systems, digital signal processing, and SAR and ISAR imaging. He is the author of the book Modulated Coding for IntersymbolInterference Channels (New York, Marcel Dekker, 2000). He is currentlyserving and has served as an Associate Editor for numerous internationaljournals including the IEEE TRANSACTIONS ON SIGNAL PROCESSING,the IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, the IEEETRANSACTIONS ON MOBILE COMPUTING, and the IEEE TRANSACTIONSON VEHICULAR TECHNOLOGY. He served as a Technical Program Chair ofthe Signal Processing Symposium, Globecom 2007, Washington D.C., USA,and the General Co-Chair of ICASSP 2005, Philadelphia, PA, USA. He wasthe recipient of the National Science Foundation (NSF) Faculty Early CareerDevelopment (CAREER) Program Award in 1997, the Office of Naval Research(ONR) Young Investigator Award in 1998, and the Outstanding Overseas YoungInvestigator Award from the National Nature Science Foundation of China in2001. He was also the recipient of the Outstanding Junior Faculty Award of theEngineering School, University of Delaware, in 2001.

- Assignment status: Already Solved By Our Experts
*(USA, AUS, UK & CA PhD. Writers)***CLICK HERE TO GET A PROFESSIONAL WRITER TO WORK ON THIS PAPER AND OTHER SIMILAR PAPERS, GET A NON PLAGIARIZED PAPER FROM OUR EXPERTS**

**NO PLAGIARISM**– CUSTOM PAPER