Training in Millimeter-Wave Communication

3380 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 15, NO. 5, MAY 2016
Hierarchical Codebook Design for Beamforming
Training in Millimeter-Wave Communication
Zhenyu Xiao, Member, IEEE, Tong He, Pengfei Xia, Senior Member, IEEE, and Xiang-Gen Xia, Fellow, IEEE
Abstract—In millimeter-wave communication, large antenna
arrays are required to achieve high power gain by steering toward
each other with narrow beams, which poses the problem to efficiently search the best beam direction in the angle domain at
both Tx and Rx sides. As the exhaustive search is time consuming, hierarchical search has been widely accepted to reduce the
complexity, and its performance is highly dependent on the codebook design. In this paper, we propose two basic criteria for
the hierarchical codebook design, and devise an efficient hierarchical codebook by jointly exploiting sub-array and deactivation
(turning-off) antenna processing techniques, where closed-form
expressions are provided to generate the codebook. Performance
evaluations are conducted under different system and channel
models. Results show superiority of the proposed codebook over
the existing alternatives.
Index Terms—Millimeter wave communication, mmWave,
beamforming, codebook design, hierarchial search.
I. INTRODUCTION
M ILLIMETER-WAVE (mmWave) communication is a promising technology for next-generation wireless
communication owing to its abundant frequency spectrum
resource, which promises a much higher capacity than the existing wireless local area networks (WLANs) and the current cellular mobile communication. In fact, mmWave communication
has received increasing attentions as an important candidate
technology in both the next-generation WLANs [1]–[7] and
mobile cellular communication [8]–[16]. A fundamental challenge to mmWave communication is the extremely high path
loss, thanks to the very high carrier frequency on the order of
30-60 GHz. To bridge this significant link budget gap, joint
Tx/Rx beamforming is usually required to bring large antenna
Manuscript received July 17, 2015; revised November 16, 2015; accepted
January 17, 2016. Date of publication January 22, 2016; date of current version May 6, 2016. This work was supported in part by the National Natural
Science Foundation of China (NSFC) under Grant 61571025, Grant 91338106,
Grant 91538204, and Grant 61231013, in part by the National Basic Research
Program of China under Grant 2011CB707000, and in part by the Foundation
for Innovative Research Groups of the National Natural Science Foundation of
China under Grant 61221061. The associate editor coordinating the review of
this paper and approving it for publication was L. Song.
Z. Xiao and T. He are with the School of Electronic and Information
Engineering, Beijing Key Laboratory for Network-Based Cooperative Air
Traffic Management, Beihang University, Beijing 100191, China, and also with
the Beijing Laboratory for General Aviation Technology, Beihang University,
Beijing 100191, China. (e-mail: xiaozy@buaa.edu.cn).
P. Xia is with the Key Laboratory of Embedded System and Service
Computing, 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 online
at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TWC.2016.2520930
array gains, which typically requires a large Tx/Rx antenna
array size (e.g., an antenna array size of 36 is used in [4].).
Fortunately, thanks to the small wavelength on the mmWave
frequency, large antenna arrays are possible to be packed into a
small area.
In the mmWave domain, the high power consumption of
mixed signal components, as well as expensive radio-frequency
(RF) chains, make it difficult, if not impossible, to realize
digital baseband beamforming as used in the conventional
multiple-input multiple-output (MIMO) systems. Instead, analog beamforming is usually preferred, where all the antennas
share a single RF chain and have constant-amplitude (CA)
constraint on their weights [4], [6], [17], [18]. Meanwhile, a
hybrid analog/digital precoding structure was also proposed
to realize multi-stream/multi-user transmission [9], [12], [13],
where a small number of RF chains are tied to a large antenna
array. No matter whether the analog beamforming or the hybrid
precoding structure is exploited, entry-wise estimation of
channel state information (CSI) is time costly due to large-size
antenna arrays, and a more efficient antenna training algorithm
is needed.
For the hybrid precoding structure, as the mmWave channel
is generally sparse in the angle domain, different compressed
sensing (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-point
multi-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 general
exist two different approaches. In [4], [6], [7], [22], an iterative beamforming training approach is adopted, in which the
beamforming vector on one side (transmitter or receiver) is
alternatively optimized by fixing the beamforming vector on the
other side, and the alternation is repeated iteratively to improve
the beamforming gain one iteration upon another. On the other
hand, in [17], [18], [23], a switched beamforming approach
is adopted, where the beam search space (at the transmitter
and receiver side, respectively) is represented by a codebook
containing multiple codewords, and the best transmit/receive
beams are found by searching through their respective codebooks. Both approaches have their own merit and may be useful
in 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 the
very-low SNR case [24]. Furthermore, single stream beamforming can be readily extended to the more complicated hybrid
1536-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 3381
precoding case [19]. For switched beamforming, an exhaustive
search algorithm may be used, which sequentially tests all the
beam directions in the angle domain and finds the best pair of
transmit/receive beamforming codewords. This is conceptually
straightforward. However, the overall search time is prohibitive,
because the number of candidate beam directions is usually
large 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 with
a 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 beams covering the same intended angle range, and that a coarse beam

Fig. 1. Illustration of the system.

may have the same/similar coverage as that of multiple fine
beams together. A divide-and-conquer search may then be carried out across the hierarchy of codebooks, by finding the best
sector (or coarse beam) first on the low-resolution codebook

level, and then the best fine beam on the high-resolution code	The rest of this paper is as follows. In Section II, the sys
book level, with the best high-resolution beam contained by the tem and channel models are introduced. In Section III, the
best low-resolution beam.	hierarchical codebook design is presented. In Section IV, per
Performances of the switched beamforming schemes, includ ing the search time and success rate, are highly dependent formance evaluation is conducted. The conclusion is drawn lastly in Section V.
on the hierarchical codebook design. In [17], [18], although	Symbol Notations: a, a, A, and A denote a scalar variable,

wider beams were proposed to speed up beam search, design
approaches to broaden the beams were not studied. In [25],
codewords with wider beams were generated by summing
two codewords with narrower beams, but the CA constraint
was no longer satisfied. In [26], a sub-array method was proposed to broaden the beam width by pointing the sub-array
beams in slightly-gapped directions. However, a full hierarchical codebook was not explicitly designed therein, and this
approach may be not feasible to design very wide or even
omni-directional beams. In [19], the hybrid precoding structure was adopted to shape wider beams by exploiting the
sparse reconstruction approach, but high-quality wide beams
can be shaped only when the number of RF chains is large
enough and deep sinks within the angle range appear otherwise.
In [27], a binary-tree structured hierarchical codebook was
designed by using antenna deactivation, where wider beams
were generated by turning off part of the antennas. A complete
codebook was designed with closed-form expressions provided
therein. However, the number of active antennas is too small
for very wide or omni-directional beams, which may limit
its application in mmWave communication, where per-antenna
transmission power is limited.
In this paper, we first propose two basic criteria for arbitrary hierarchical codebook designs, and then devise an efficient
hierarchical codebook by jointly exploiting sub-array and deactivation (turning-off) antenna processing techniques. Closedform expressions are provided to generate the codebook. In the
proposed approach, the beams of the sub-arrays steer towards
widely-gapped directions to broaden beams, which is essentially different from [26], and the deactivation operates on the
sub-arrays instead of individual antennas like that in [27]. To the

best of our knowledge, this is the first to propose these two cri	Letting s denote the transmitted symbol with unit power, the
teria and the joint sub-array and deactivation codebook design. received signal is
Performance evaluations are conducted under both line-of-sight (LOS) and non-LOS (NLOS) channels, as well as with both	y = PtotwHwTs + wn,	(1)

total and per-antenna transmission power models. Results show
superiority of the proposed codebook over the existing alternatives, especially when the per-antenna transmit power is
constrained.
a vector, a matrix, and a set, respectively. (·)∗, (·)T and (·)H
denote conjugate, transpose and conjugate transpose, respectively. E(·) denotes expectation operation. [a]i and [A]i j denote
the 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-th
to j-th entries of [a]. | · | and · denote the absolute value and
two-norm, respectively.
II. SYSTEM AND CHANNEL MODELS
A. System Model
Without 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 and
receiver, 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 structure
is adopted. At the transmitter, each antenna branch has a phase
shifter and power amplifier (AP) to drive the antenna, while
at the receiver, each antenna branch has a low-noise amplifier
(LNA) to amplify the signal and a phase shifter. It is noted that
as the analog beamforming can be seen as one of the branches
of the hybrid precoding structure, the proposed criteria and
codebook design can be naturally used by the hybrid precoding
structure, which will be shown in Section III-D. Additionally,
in our system each antenna branch can be deactivated or turned
off, i.e., there is a switch in each antenna branch at both sides
although not depicted in the figure. Generally, all the PAs, as
well as the LNAs, have the same scaling factor if activated.
Thus, each element of the antenna weight vectors (AWVs) at
the both sides either has a constant amplitude or is zero.
H RH R
3382 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 15, NO. 5, MAY 2016
where Ptot is the total transmission power of all the active
antennas, wT and wR are the transmit and receive AWVs,
respectively, H is the channel matrix, n is the Gaussian noise
vector with power N0, i.e., E(nnH) = N0I. Let W(N) denote
a set of vectors with N entries as shown in (3), at the bottom
of the page, where ν is a normalization factor such that all the
vectors have unit power. We can find that each entry of an arbitrary vector in W(N) has either an amplitude ν (activated) or
is 0 (deactivated). Consequently, we have wT ∈ W(NT), and
wR ∈ W(NR). It is noted that this signaling is based on the total
transmission power, and we can further define the total transmission SNR as γtot = Ptot/N0, and the received SNR with the
total 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-antenna
transmission power model is also with significance to characterize the best transmission ability of the transmitter, which is
shown as
y = PperNTactwH RHwTs + wH Rn, (5)
where P
per is the per-antenna transmission power, NTact is the
number 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 power
model is defined as
ηper = γperNTact|wH RHwT|2. (6)
The power gain under this model is
G
per =
ηper
γper
= NTact|wH RHwT|2, (7)
which includes both the transmission power gain equal to
the 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 scaling
abilities of PA are high enough and limited, respectively.
However, there is no difference for codebook design between
with these two models.
B. Channel Model
Since 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 (3)
That is, mmWave channels have the feature of directionality.
Different MPCs have different physical transmit steering angles
and receive steering angles, i.e., physical angles of departure
(AoDs) and angles of arrival (AoAs). Consequently, mmWave
channels are relevant to the geometry of antenna arrays. With
half-spaced ULAs adopted at the transmitter and receiver, the
channel matrix can be expressed as [19], [26], [27], [29],
[33], [34]

H = NTNR

λa(NR, )a(NT,ψ)H,

(8)

L =1
where λ is the complex coefficient of the -th path, L is the
number 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 AoDs
and AoAs, respectively. Similar to [19], [29], λ can be modeled to be complex Gaussian distributed, while θ and ϕ can
be modeled to be uniformly distributed within [0,2π]. a(·) is a
function of the number of antennas and AoD/AoA, and can be
expressed as
a(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 easy
to find that a(N, ) is a periodical function which satisfies
a(N, ) = a(N, + 2). The channel matrix H also has power
normalization
L =1
E(|λ|2) = 1. (10)
C. The Problem
From a system level, joint Tx/Rx beamforming is required to
maximize 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, and
there 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-wise
estimation of the channel matrix, which has a large scale due
to large antenna arrays, and there exists the CA constraint.
Thus, the SVD approach is basically not feasible for mmWave
communication.
XIAO et al.: HIERARCHICAL CODEBOOK DESIGN FOR BEAMFORMING TRAINING IN MILLIMETER-WAVE COMMUNICATION 3383
Fortunately, according to (8) the mmWave channel has uncer

tainty mainly on AoDs/AoAs at both sides. In such a case, the one-stream beamforming problem in (11) can be simplified to find the AoD/AoA of an arbitrary strong MPC (or better the

A(w, ) = √Na(N, )Hw =

n=1

[w]ne-jπ(n-1) , (12)

strongest MPC)1, and set wT and wR as the Tx/Rx steering
vectors 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 an N antenna-array, and sequentially test all these sampled angles with corresponding steering vectors at both sides. This is the

CV(w) = | |A(w, )| > ρ max ω |A(w,ω)|,

(13)

exhaustive search method. Clearly the codebooks for exhaustive search are composed by only steering vectors. Although
exhaustive search is feasible and can always find the best MPC,
it has a time complexity O(N 2) [27], [35], which is too high for
large arrays. Thus, hierarchical search is widely used to reduce
the search time. In fact, the search time is highly dependent on
the design of the Tx/Rx codebooks, which are subsets of WT
and WR, respectively. Hence, we focus on the codebook design
in this paper.
III. HIERARCHICAL CODEBOOK DESIGN
In this section, we design a hierarchical codebook composed
by codewords (or AWVs) with different beam widths, which
helps 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 the	Nk ∪ n=1 CV(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 instan where Nk is the number of codewords in the k-th layer, K it the maximal index of the layer (there are K + 1 layers in total).
taneous channel response. When beamforming is required in	Criterion 2: The beam coverage of an arbitrary codeword

practice before data transmission, a beam search process needs
to be launched based on the designed codebook to find the
suitable beamforming weights (steering vectors) for a given
channel. For different channels, the codebook is the same, but

the searched optimal steering vectors are different depending on the channel responses.

(15)

Although several hierarchial search schemes have been proposed for beam search in both literatures [25]–[27] and some
standards, 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 there are few complete hierarchical codebooks with closed-form expressions provided for mmWave communication. Therefore, in this section, we first propose two basic criteria to design a hierarchical codebook, and then design one jointly using sub-array and deactivation techniques based on the proposed criteria.	It is clear that Criterion 1 guarantees the full coverage, i.e., there is no miss of any angle during the beam search, while Criterion 2 establishes a tree-fashion relationship between the codewords, which enables hierarchical search. If each parent codeword has M child codewords, all the codewords in the codebook constitute an M-way tree with respect to their beam coverage in the angle domain. In such a case, hierarchical search can be easily realized by using the tree search algorithm in both the receiver and transmitter as following [19], [27]. The Hierarchical Search: Initially, we fix the transmitter to
A. Two Criteria
Before introducing the two criteria, we first introduce two be in an omni-directional mode, and run an M-way tree search
definitions here. Let A(w, ) denote the beam gain of w along angle , which is defined as	for logM(NR) stages to find the best receive codeword. And then we fix the receiver to be in a directional mode with the found 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) needs
to be found; while under NLOS channel, where all the MPCs have similar
strengths, 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 of
AWV w, which can be mathematically expressed as
where ρ is a factor within (0,1) to determine the beam coverage
of w. It is easy to find that the coverage is smaller as ρ becomes
greater. 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 values
of ρ, and codewords with different beam widths in the same
codebook may also have different values of ρ.
Hierarchical search is simply layered search, i.e., the AWVs
within the codebook are layered according to their beam width.
AWVs with a lower layer have larger beam width. Letting
w(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 the
codewords within each layer should cover the whole angle
domain, i.e.,
within a layer should be covered by the union of those of several
codewords in the next layer, i.e.,
CV(w(k,n)) ⊆ ∪
m∈Ik,n
CV(w(k + 1,m)),k = 0,1, . . . , K – 1,
where Ik,n is the index set with indices of the codewords in
the (k + 1)-th layer for the n-th codeword in the k-th layer. For
convenience, we call w(k,n) a parent codeword, and 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 the
M child codewords of a parent codeword found in the last stage.
3384 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 15, NO. 5, MAY 2016
Fig. 2. Beam coverage of a binary-tree structured codebook.
We need to test all the M codewords one by one to find the best
one, and treat it as a new parent codeword for the next-stage
search. Therefore, the search time (number of tests) for Tx/Rx
joint training is
T = M logM NT + M logM NR. (16)
In the next subsection we will design a codebook with
M = 2, for the reason that when M = 2 the codebook tree
is 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 of
M is straightforward.
B. The Deactivation Approach
As a basis of the joint sub-array and deactivation approach,
we first introduce the deactivation (DEACT) approach in this
subsection to design a binary-tree codebook, which has the
beam coverage shown in Fig. 2, where there are log2(N) + 1
layers with indices from k = 0 to k = log2(N), and the number
of codewords in the k-th layer Nk = 2k. Here N denotes the
number of antennas of an arbitrary array. Thus, N = NT at the
transmitter and N = NR at the receiver. Besides, we have
CV(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 define CV(a(N, )) = – , +	,	(18)

N1 N1 which means that the steering vectors have a beam width 2/N
centering at the steering angle [24]. In other words, within the
beam coverage of a(N, ), it has the maximal beam gain along
the 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 N

N n=1
ejπ(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 the
DEACT approach, where N = 128.
Although the value of ρ depends on N, we have ρ ≈ 0.64 given
that N is large, e.g., N ≥ 8. Even when N is small, ρ is still
close to 0.64, e.g., ρ = 0.65 when N = 4.
Notice that the N codewords in the last layer cover
an angle range [-1,1] in total, which means that all
these codewords must have the narrowest beam width 2/N
with different steering angles. In other words, the codewords in the last layer should be the steering vectors
with 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 in
the other layers in turn as an order of descending layer
indices, 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 of
all the codewords can be uniformly written as
CV(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 when
w(k,n) = a 2k,-1 + 2n – 1
2k T ,0T (N-2k)×1 T , (21)
(20) is satisfied. This is just the deactivation approach that was
proposed in [27], where the number of active antennas is 2k in
the k-th layer, and the other antennas are all turned off. Fig. 3
shows an example of beam pattern of the DEACT approach for
the case of N = 128. From this figure we find that the beam
coverage of w(0,1) is just the union of those of w(1,1) and
w(1,2), while the beam coverage of w(1,1) is just the union of
those of w(2,1) and w(2,2).
C. The Joint Sub-Array and Deactivation Approach
It 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 of
an mmWave device. In general, we hope the number of active
XIAO et al.: HIERARCHICAL CODEBOOK DESIGN FOR BEAMFORMING TRAINING IN MILLIMETER-WAVE COMMUNICATION 3385

antennas is as large as possible, such that higher power can be	In addition, w(k,1) has a beam coverage [-1,-1 + 22k ].
transmitted, because in mmWave communication per-antenna According to Theorem 1,
transmission power is usually limited. To achieve this target, we consider jointly using the sub-array and deactivation approach	CV(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, each
codeword has a beam width of 2/2k. For the codewords of
the 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 widths
but different steering angles. Thus, there are two basic tasks in
the codebook design, namely to rotate the beam along required
directions and to broaden the beam by required factors. We first
introduce beam rotation.
1) Beam Rotation: Beam rotation can be realized according
to the following theorem.
Theorem 1: CV(w ◦ √Na(N,ψ)) = CV(w) + ψ, where ◦
represents entry-wise product (a.k.a. Hadamard product), N is
the number of elements of w, ψ is an arbitrary angle. A + ψ
is a new angle set with elements being those of the angle set A
added by ψ.
The proof is referred to Appendix A, and this theorem can
be used not only for the BMW-SS approach, but also for other
codebook 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 is
found. To explain this, we need to emphasize that all the
codewords in the same layer have the same beam widths but
different steering angles according to (20), which means that
the beam coverage of all the codewords can be assumed to have
the same shape but different offsets in the angle domain. Thus,
we can obtain one codeword based on another in the same layer
as long as we know the angle gap between them according to
Theorem 1. In particular, suppose we find the first codeword
in the k-th layer w(k,1). According to (20), we do know that
the angle gap between the n-th codeword in the k-th layer, i.e.,
w(k,n), and w(k,1) is 2n-2
2k , n = 2,3, . . . ,2k. Then we can
obtain 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 layer
w(k,1), all the other codewords in the k-th layer can be found
through 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-2
2k ,-1 + 22nk ].
Since
[w(k,n)]i = [w(k,1) ◦ √Na(N, 2n – 2
2k )]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 – 2
2k
= CV(w(k,1)) + 2n – 2
2k
= -1,-1 + 22k + 2n2-k 2
= -1 + 2n2-k 2,-1 + 22nk . (23)

2) Beam Broadening: The remaining task is to broaden the
beam for each layer. Given an N-element array, generally we
would expect a beam width of 2/N. Nevertheless, this beam
width is in fact achieved by concentrating the transmission
power at a specific angle 0, i.e., by selecting AWV to maximize |A(w, 0)|. Intuitively, if we design the AWV to disperse
the transmission power along different widely-spaced angles,
the beam width can be broadened. More specifically, if a large
antenna array is divided into multiple sub-arrays, and these subarrays point at sufficiently-spaced directions, a wider beam can
be shaped.
To illustrate this, let us separate the N-antenna array into M
sub-arrays with NS antennas in each sub-array, which means
N = M NS. In addition, letting fm = [w](m-1)NS+1:m NS, we
have [fm]n = [w](m-1)NS+n, m = 1,2, . . . , M. fm can be seen
as the sub-AWV of the m-th sub-array. Therefore, the beam gain
of w writes
A(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=1 e-jπ(m-1)NSω[fm]ne-jπ(n-1)ω	(24)
e-jπ(m-1)NSωA(fm,ω),

M NS
n=1
M =
M m=1
which means that the beam gain of w can be seen as the
union 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 scalar
coefficient 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 coverage
CV(w) =
M∪
m=1
CV(fm)=-1,-1+ 2NMS= -1,-1+ 2MN 2 ,
(25)
i.e., the beam width has been broadened by M2 by using the
sub-array technique, where a broadening factor M comes from
the number of sub-arrays, while another factor M results from
the 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 between	2M2 N . If we jointly
different sub-arrays are not taken into account. In the case of using the sub-array and deactivation method, we may obtain
fm = ejθma(NS,-1 + 2mN-S 1), we have A(w,ω) | fm = ejθma NS,-1 + 2m – 1 NS	codewords with beam widths 2NA NS = 2M NA N by setting as
fm = ⎧⎨⎩ e – jm NS-
(29)

= NS
M m=1
e-jπ(m-1)NSωejθm
× a(NS,ω)Ha NS,-1 + 2m – 1
NS . (26)
As the steering vector has the properties that a(NS,-1 +
2m-1
NS )Ha(NS,-1 + 2nN-S1) = 0 when m = n, the beam gain of
fm
along the angle -1 + 2mN-S 1 is affected little by fn. It is clear
that |A(w,-1 + 2mN-S 1)| = √NS for m = 1,2, . . . , M, which
means that the beam gains along angles ω = 1 + 2mN-S 1 are
significant.
Additionally, to reduce the beam fluctuation, it is required
that the intersection points in the angle domain of these coverage regions, i.e., ω = -1 + N2nS , n = 1,2, . . . , M – 1, also
have high beam gain, and this can be realized by adjusting
coefficients ejθm. Concretely, we have (28), shown at the bottom of the page, where in (a) we have used the fact that
a(NS,ω1)Ha(NS,ω2) is small and can be neglected when |ω1 –
ω2| > 2/NS, in (b) we have exploited the condition that NS
is even in this paper. To maximize |A(w,ω)|2, we face the
problem
maximize
θ
| 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 a
A(w,ω) | fm = ejθma NS,-1 + 2m – 1
NS ,ω = -1 + N2nS
= NS
M m=1
e-jπ(m-1)NSωejθma(NS,ω)Ha NS,-1 + 2m – 1
NS
(a)
≈ NSe-jπ(n-1)NSωejθna NS,-1 + 2n
NS Ha NS,-1 + 2nN-S 1
+ NSe-jπnNSωejθn+1a NS,-1 + 2n
NS Ha NS,-1 + 2nN+S 1
=
1
√NS e-jπ(n-1)NSωejθn ×
⎛⎝
NS
i=1
e-jπ(i-1)/NS + ejπ NSωej(θn+1-θn)
NS
i=1
ejπ(i-1)/NS⎞ ⎠
(b)
=
1
√NS e-jπ(n-1)NSωejθn ×
⎛⎝
NS
i=1
e-jπ(i-1)/NS + ejθ
NS
i=1
ejπ(i-1)/NS⎞ ⎠
=
1
√NS e-jπ(n-1)NSωejθn f (NS,θ), (28)
codeword w with a beam width 2M
NS =
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 design
w(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-1
N ), n = 1,2, . . . , N.
When k = log2(N) – , where = 1,2,… ,log2(N), we
obey the following procedures to compute w(k,n):
• Separate w(k,1) into M = 2 (+1)/2 sub-arrays with
fm
= [w(k,1)](m-1)NS+1:mNS, where · is the flooring
integer operation, m = 1,2, . . . , M;
• Set fm as (29), where NA = M/2 if is odd, and NA = M
if 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 find
that the beam coverage of w(0,1) is just the union of those of
w(1,1) and w(1,2), while the beam coverage of w(1,1) is just
the union of those of w(2,1) and w(2,2). Comparing the beam
pattern of DEACT shown in Fig. 3 with that in Fig. 4, it can
be observed that although there are small-scale fluctuations for
BMW-SS, the beams of BMW-SS appear flatter than those of
DEACT within the covered angle.
On the other hand, for BMW-SS all the codewords either
have all the antennas activated, or have half of them activated,
which shows a significant advantage over DEACT in terms
of the maximal total transmission power, especially for the
XIAO et al.: HIERARCHICAL CODEBOOK DESIGN FOR BEAMFORMING TRAINING IN MILLIMETER-WAVE COMMUNICATION 3387
Fig. 4. Beam patterns of w(2, 1), w(2, 2), w(1, 1), w(1, 2) and w(0, 1) for the
BMW-SS approach, where N = 128.
Fig. 5. Comparison of the beam patterns of BMW-SS, DEACT, and the
approach in [19] (termed as Sparse) with the per-antenna transmission power
model, 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 as
Sparse) with the per-antenna transmission power model, where
all the weights of active antennas have a unit amplitude. From
this figure, we find that BMW-SS offers much higher beam
gains than DEACT due to exploiting much greater number of
active antennas. In addition, for the Sparse codebook, when the
number of RF chains is small, there are deep sinks within the
beam coverage of the wide-beam codewords, and the sink is
more severe when the number of RF chains is smaller, which are
in accordance with the results in [19] (Fig. 5 therein). Clearly, if
the AoD or AoA of an MPC is along the sink angle, it cannot be
detected with the codeword, which results in miss detection of
the MPC. By contrast, BMW-SS does not have such deep sinks.
It is noted that the corresponding hierarchical search of the
designed codebook will eventually converge to a codeword of
the last layer, i.e., a steering vector, at both ends. We can find
that the angle resolution of the last layer is 2/N. Thus, the
designed codebook is just coarse codebook, while the corresponding search method is coarse search, like those in [27]. If a
higher angle resolution is required, a fine codebook composed
by steering vectors with a smaller sampling gap than 2/N is
necessary. Details are referred to [27].
D. Generalization
1) For the Hybrid Precoding Structure: In this paper we
adopt an analog beamforming structure, and both the proposed
two criteria and the BMW-SS approach are based on the analog
beamforming structure. However, they are naturally feasible for
the hybrid precoding structure, because the analog beamforming structure can be seen as one of the branches of the hybrid
precoding structure [19].
To realize multi-stream transmission with the hybrid precoding structure, the AoDs and AoAs of multiple MPCs need to
be searched. The search process with BMW-SS based on the
beamforming structure in this paper can be adopted to search
the AoD and AoA of each single MPC. In fact, similar extension from one-stream transmission to multi-stream transmission
has been studied for the Sparse codebook in [19].
2) For Other Types of Antenna Arrays: In this paper we
adopt a ULA model. There are other types of antenna arrays in
practice, e.g., uniform planar array (UPA) and uniform circular
array (UCA). The proposed criteria and the BMW-SS approach
can be easily extended to the UPA model. In particular, for a
typical 2-dimensional grid UPA with m × n elements, its steering vector can be expressed as the Kronecker product of those
of two ULAs with m × 1 and n × 1 elements, respectively [26].
The search process as well as the codebook design could be
extended to the UPA model and will be studied later.
On the other hand, for a UCA model, the two criteria are
also feasible, but that the beam coverage in Criterion 1 should
be extended to a 2-dimensional angle range, including both
the azimuth and elevation angle ranges. However, the proposed
BMW-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 new
codebook according to the proposed criteria with a UCA mode.
3) For Arbitrary Number of Antenna Elements: In this
paper we require that the number of elements of a ULA (N) is
M p for some positive integer p, which is because the BMW-SS
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 approach may not be extended to
with arbitrary number of antenna elements. There are two possible choices 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 BMW-SS
for beamforming with M logM N antennas while deactivating
the other ones, where · is the floor operation. Afterwards,
further beam refinement can be launched with all the antennas
activated.
IV. PERFORMANCE EVALUATION
In this section, we evaluate the performance of the designed
hierarchical codebook by the BMW-SS approach, and compare
it with the alternatives. We consider two different system models on the transmission power, namely total transmission power
and per-antenna transmission power, which correspond to the
3388 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 15, NO. 5, MAY 2016
signal models in (1) and (5), respectively. The total transmission power signal model reflects the performance for the case
that the transmission power on each antenna branch can be high
enough, while the per-antenna transmission power signal model
reflects the limit performance for the case that the transmission power on each antenna branch is limited2. The per-antenna
transmission power model makes more sense in mmWave communication, where the output power of a single power amplifier
is generally limited [2], [4]. The activation/deactivation operations of a codebook are irrelevant to the power models. In
particular, no matter which power model is adopted, the codewords of BMW-SS either have all or half of the antennas
activated, those of DEACT have varying numbers of the antennas activated and the number may be quite small, while those
of Sparse always have all the antennas activated.
Besides, in the simulations, both LOS and NLOS channel
models are considered based on (8). For LOS channel, the
first MPC has a constant coefficient and random AoD and
AoA, while the other NLOS MPCs have complex Gaussiandistributed coefficients and random AoDs and AoAs [26],
[29]. The LOS MPC is generally much stronger than the
NLOS MPCs. For NLOS channel, all the MPCs have complex Gaussian-distributed coefficients with the same variance
and random AoDs and AoAs [19], [26], [29]. Both the LOS
and NLOS channels are sparse in the angle domain, because
the number of MPCs is much smaller than the numbers of the
Tx/Rx antennas [19], [26], [29]. For all the codebooks, the hierarchical search method introduced in Section III-A is used. The
performances of received SNR and success rate are all averaged on the instantaneous results of 104 random realizations of
the LOS/NLOS channel.
A. Total Transmission Power Model
In this subsection, the total transmission power signal model
shown in (1) is used. With this model, the deactivation of antennas will not affect the total transmission power, i.e., the total
transmission power is the same for the involved schemes.
Fig. 6 shows the received power during each search step
with the BMW-SS and DEACT codebooks under both LOS
and NLOS channels, where NT = NR = 64, L = 3, Ptot = 1
W, and N0 = 10-4 W, i.e., the SNR for beam training is sufficiently high, which means the length of the training sequence is
sufficiently long. The upper bound is achieved by the exhaustive search method. For the LOS channel, the LOS component
has 15dB higher power than that of an NLOS MPC. From
this figure we can find that the received-power performance
of these two codebooks is similar to each other. Under both
channels, at the beginning, i.e., in the first two steps, DEACT
behaves slightly better than BMW-SS; while in the following
steps, 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 under
2The limit performance here refers to the performance in the case that all the
active antennas transmit with maximal power.
Fig. 6. Received power during each search step with the BMW-SS and DEACT
codebooks 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, while
Step 7 to Step 12 is for Tx training.
Fig. 7. Success rate of hierarchical search with the BMW-SS, DEACT and
Sparse codebooks under LOS channel, where NT = NR = 64, L = 3. η is the
power difference in dB between the LOS component and an NLOS MPC.
NLOS channel. This is because under LOS channel, the LOS
component is the optimal MPC, and it is acquired by all BMWSS, DEACT and the exhaustive search. However, under NLOS
channel, BMW-SS and DEACT acquire an arbitrary MPC of the
L NLOS MPCs, which may not be the optimal one acquired by
the exhaustive search.
Fig. 7 shows the success rate of hierarchical search with
the 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 component
and an NLOS MPC. From this figure, it is observed that both
the transmission SNR γtot and η affect the success rate. For
all 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 high
enough. Basically when η is bigger, the mutual effect is less,
and the success rate is higher. For the Sparse codebook, the
performance also depends on the number of RF chains. When
the number of RF chains is small, e.g., only 2, the deep sinks
XIAO et al.: HIERARCHICAL CODEBOOK DESIGN FOR BEAMFORMING TRAINING IN MILLIMETER-WAVE COMMUNICATION 3389
Fig. 8. Success rate of hierarchical search with the BMW-SS, DEACT and
Sparse codebooks under NLOS channel, where NT = NR = 64.
within the covered angle (See Fig. 5) will sharply reduce the
success rate, as shown in Fig. 7. Furthermore, we can find that
the success rate with the BMW-SS codebook is higher than that
with the DEACT codebook. This is because the beams of the
BMW-SS codebook are flatter than those of the DEACT codebook; thus they are more robust to the spatial fading. Also, the
success rate with the BMW-SS codebook is higher than that
with the Sparse codebook when the number of RF chains is not
large.
Fig. 8 shows the success rate of hierarchical search with
the BMW-SS, DEACT and Sparse codebooks under NLOS
channel, where NT = NR = 64. From this figure, the same performance variation with respect to the transmission SNR γtot
can be observed as that in Fig. 7, and Sparse with 2 RF chains
also has the poorest performance. In addition, BMW-SS basically outperforms DEACT and Sparse with 4 RF chains, and the
superiority depends on L. When L = 1, i.e., there is only one
MPC, both BMW-SS and DEACT achieve a 100% success rate
when γtot is high enough, because there is no spatial fading. In
contrast, Sparse cannot achieve a 100% success rate even when
L = 1, due to the deep sinks within the covered angle. When
L > 1, all these schemes can hardly achieve a 100% success
rate, due to the mutual effect of multiple MPCs.
It is noteworthy that the superiority of BMW-SS versus
DEACT in Fig. 6 is different from that in Figs. 7 and 8. Fig. 6
just shows the variation of the received power during the search
process with a high SNR, while Figs. 7 and 8 show the search
results over a wide SNR range. Fig. 6 actually corresponds to
the search process for a set of points in Figs. 7 and 8 with SNR
equal of 40dB, and the received-power superiority of BMW-SS
over DEACT in Fig. 6 will become larger if smaller SNR values
are adopted.
B. Per-Antenna Transmission Power Model
In this subsection, the per-antenna transmission power signal
model shown in (5) is used to compare the limit performances
of BMW-SS and DEACT with the same per-antenna transmission power. With this model, the deactivation of antennas will
Fig. 9. Received SNR during each search step with the BMW-SS and DEACT
codebooks 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, while
Step 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 active
antennas is smaller.
Fig. 9 shows the received power during each search step
with the BMW-SS and DEACT codebooks under both LOS and
NLOS 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 component
has 15dB higher power than that of an NLOS MPC. Comparing
this figure with Fig. 6, we find a significant difference that
with the per-antenna transmission power model BMW-SS has
a 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 as
the search goes on, until vanishes at the end of beam search,
i.e., the two methods achieve the same received SNR after the
search process. The superiority of BMW-SS results from the
fact that the number of the active antennas for the codewords
with wide beams is significantly greater than that for DEACT,
and thus BMW-SS has a much higher total transmission power
than DEACT when the per-antenna transmission power is the
same.
Moreover, the increasing speed of received power is the same
from Step 1 to Step 6 for both of the two schemes, but from
Step 7 to Step 12, the increasing speed for BMW-SS varies, and
that for DEACT becomes greater than that from Step 1 to Step
6. This is because with per-antenna transmission power, there
are two power gains during the search process according to (4),
namely the array gain provided by narrowing the Tx/Rx beams
and the total transmission power gain provided by increasing
the number of active transmit antennas. For DEACT, there is
only Rx array gain from Step 1 to Step 6, where Rx training is
performed, while there are both Tx array gain and total transmission power gain from Step 7 to Step 12, where Tx training
is performed; thus, the increasing speed of received power is
greater from Step 7 to Step 12. For BMW-SS, there is also only
Rx array gain from Step 1 to Step 6 for Rx training; thus the
received power consistently increases with the same speed as
3390 IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 15, NO. 5, MAY 2016
Fig. 10. Success rate of hierarchical search with the BMW-SS and DEACT
codebooks under LOS channel, where NT = NR = 64, L = 3. η is the power
difference in dB between the LOS component and an NLOS MPC.
Fig. 11. Success rate of hierarchical search with the BMW-SS and DEACT
codebooks under NLOS channel, where NT = NR = 64.
DEACT. But from Step 7 to Step 12 for Tx training, although
the Tx beam consistently becomes narrower, which means that
Tx array gain is consistently improved, the number of active
antennas alternatively changes between NT and NT/2, which
means that the total transmission power may become larger or
smaller. Hence, when both the Tx array gain and total transmission power increase, the received power improves with a speed
the same as DEACT, while when the Tx array gain increases
but the total transmission power decreases, the received SNR
does not improve and may even decrease.
It is noted that the superiority of BMW-SS over DEACT at
the beginning of the search process is with big significance
for mmWave communication, where per-antenna transmission
power is generally limited. This superiority guarantees that with
the BMW-SS codebook, the success rate of beam search will be
upgraded with the same transmission distance, or the transmission distance will be extended with the same success rate of
beam search.
Figs. 10 and 11 show the success rates of hierarchical search
with the BMW-SS and DEACT codebooks under LOS and
NLOS channels, respectively. The same simulation conditions
are adopted as those in Figs. 7 and 8, respectively, and the
same results can be obtained from Figs. 10 and 11 as those
from Figs. 7 and 8, respectively, except that the superiority of
BMW-SS over DEACT becomes more significant in Figs. 10
and 11, which benefits from not only the fact that the beams
of the BMW-SS codebook are flatter than those of the DEACT
codebook, but also that the number of the active antennas of
the BMW-SS codewords is basically much greater than that of
DEACT, which offers much higher total transmission power.
Also, Figs. 10 and 11 reveal that even with low per-antenna
transmission power, the success rate of BMW-SS can be close
to 100%, which is evidently better than those of DEACT and
Sparse.
V. CONCLUSIONS
In this paper hierarchical codebook design has been studied for mmWave communication. Firstly, two basic criteria
have been proposed for the codebook design. Next, a complete binary-tree structured hierarchical codebook has been
designed by jointly using sub-array and deactivation techniques, i.e., the BMW-SS approach. Performance evaluation
has been conducted with both a total transmission power and a
per-antenna transmission power system models. Results show
that the BMW-SS codebook offers two advantages over the
deactivation codebook, namely flatter beams and much larger
number of active antennas. Both of these two advantages basically provide performance superiorities in terms of received
power during the search process and the success rate of beam
search under both transmission power models, and the performance superiority is especially significant with the per-antenna
transmission power system model. In addition, the BMW-SS
codebook also outperforms the Sparse codebook, since there
are no deep sinks within the beam coverage for BMW-SS.
APPENDIX A
PROOF OF THEOREM 1
Given an arbitrary N-element vector w and two arbitrary
angles ψ and , we want to prove that CV(w ◦ √Na(N,ψ)) =
CV(w) + ψ, where A + ψ is a new angle set with elements
being those of the angle set A added by ψ. Note that w ◦
√Na(N,ψ) is actually a new vector achieved based on w and
the steering vector a(N,ψ). Let us first see the beam gain of
this 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 3391
where (a) and (c) are according to the definition of the beam
gain in (12), while (b) is obtained according to definition of the
entry-wise product.
Thus, we further have
CV(w ◦ √Na(N,ψ))
(a)
=
(b)
= > ρ max
ω

(c)
= A(w, – ψ)
(d)
=
(e)
= + ψ
= 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 the
maxima of |A(w, – ψ)| does not depend on the angle offset
ψ, (d) is obtained by letting = 0 + ψ, and (e) is obtained
according to the definition of an angle set plus a single angle in
Theorem 1.
ACKNOWLEDGMENT
The authors would like to thank the editor and the anonymous reviewers for their many useful and detailed comments
that 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. Ahmed
Alkhateeb for his kind help in explaining how to use the source
code.
REFERENCES
[1] R. C. Daniels, J. N. Murdock, T. S. Rappaport, and R. W. Heath, “60 GHz
wireless: 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 Gbps
WLAN 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 GLOBECOM
Conf., 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,” IEEE
Commun. 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 with
hybrid analog and digital beamforming for millimeter wave 5 G,” IEEE
Commun. 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 prototype
results,” 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 for
millimeter-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 millimeter
wave 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 uniform
linear 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 wave
wireless 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 estimation
and 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 sensing
based multi-user millimeter wave systems: How many measurements are
needed?” in Proc. IEEE Int. Conf. Acoust. Speech Signal Process., May
2015, pp. 2909–2913.
[21] Y. Peng, Y. Li, and P. Wang, “An enhanced channel estimation method for
millimeter 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 with
constant-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 estimation
for 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 beamforming
codebook 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 small
cell 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 for
millimeter-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 models
using 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 for
adaptive 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 sparse
multipath with reconfigurable antenna arrays,” IEEE J. Sel. Topics Signal
Process., 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, “Spatially
sparse 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, and
R. Lauwereins, “Joint transmit and receive analog beamforming in
60 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,” IEEE
Trans. Wireless Commun., vol. 12, no. 2, pp. 504–515, Feb. 2013.
Zhenyu Xiao (M’14) received the B.E. degree
from the Department of Electronics and Information
Engineering, Huazhong University of Science and
Technology, Wuhan, China, in 2006, and the
Ph.D. degree from the Department of Electronic
Engineering, Tsinghua University, Beijing, China,
in 2011. From 2011 to 2013, he served as
a Postdoctororal Fellow with the Department of
Electrical Engineering, Tsinghua University, Beijing,
China. Since 2013, he has been a Lecturer with
Beihang University, Beijing, China. He has authored
over 50 papers. His research interests include communication signal processing and practical system implementation for wideband communication
systems, which cover synchronization, multipath signal processing, diversity,
and multiple antenna technology, millimeter-wave communications, and UAV
networks. He served as a Reviewer for the IEEE TRANSACTIONS ON SIGNAL
PROCESSING, the IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS,
the IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY, and the IEEE
COMMUNICATIONS LETTERS. He served as a TPC Member of IEEE
GLOBECOM’12, the IEEE WCSP’12, and the IEEE ICC’15.
Tong He received the B.E. degree from the
Department of Electronic and Information
Engineering, Beihang University, Beijing, China,
in 2012. He is currently pursuing the Ph.D. degree
at the Department of Electronic and Information
Engineering, Beihang University. His research
interests include millimeter-wave communications.
Pengfei Xia (S’03–M’05–SM’10) received the Ph.D.
degree from the Department of Electrical and
Computer Engineering, University of Minnesota,
Twin Cities, MN, USA, in 2005. Currently, he is a
Full Chair Professor with the College of Electronics
and Information, Tongji University, Shanghai, China.
He has authored over 50 IEEE journal and conference
papers, and have more than 70 U.S. patents and/or
patent applications. His research interests include
the intersection of wireless communications, wireless
networks, signal and data processing, including 4G
LTE/5G cellular systems, IEEE 802.11 WLANs, millimeter wave wirelesss
communications, transceiver beamforming, and unlicensed band communications. He coedited one of the first books on millimeter wave wireless
communications “60GHz Technology for Gbps WLAN and WPAN: From
Theory to Practice.” Currently, he serves as SPCOM technical committee member and SPCOM Industrial/Government Subcommittee Chair for the IEEE
Signal Processing Society. He was the recipient of the IEEE Signal Processing
Society Best Paper Award 2011.
Xiang-Gen Xia (M’97–S’00–F’09) received the
B.S. degree in mathematics from Nanjing Normal
University, Nanjing, China, in 1983, the M.S. degree
in mathematics from Nankai University, Tianjin,
China, in 1986, and the Ph.D. degree in electrical engineering from the University of Southern
California, Los Angeles, CA, USA, in 1992. He
was a Senior/Research Staff Member with Hughes
Research Laboratories, Malibu, CA, USA, from
1995 to 1996. In September 1996, he joined the
Department of Electrical and Computer Engineering,
University of Delaware, Newark, DE, USA, where he is the Charles Black
Evans Professor. His research interests include space-time coding, MIMO
and OFDM systems, digital signal processing, and SAR and ISAR imaging. He is the author of the book Modulated Coding for Intersymbol
Interference Channels (New York, Marcel Dekker, 2000). He is currently
serving and has served as an Associate Editor for numerous international
journals including the IEEE TRANSACTIONS ON SIGNAL PROCESSING,
the IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, the IEEE
TRANSACTIONS ON MOBILE COMPUTING, and the IEEE TRANSACTIONS
ON VEHICULAR TECHNOLOGY. He served as a Technical Program Chair of
the Signal Processing Symposium, Globecom 2007, Washington D.C., USA,
and the General Co-Chair of ICASSP 2005, Philadelphia, PA, USA. He was
the recipient of the National Science Foundation (NSF) Faculty Early Career
Development (CAREER) Program Award in 1997, the Office of Naval Research
(ONR) Young Investigator Award in 1998, and the Outstanding Overseas Young
Investigator Award from the National Nature Science Foundation of China in
2001. He was also the recipient of the Outstanding Junior Faculty Award of the
Engineering School, University of Delaware, in 2001.