{'fraction_non_alphanumeric': 0.03958655390864175, 'fraction_numerical': 0.009669303749507441, 'mean_word_length': 4.650282582634013, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A New Codebook Design for Analog Beamforming in Millimeter-wave Communication

In this study, we analyze the codebook design used for analog beamforming. Analog beamforming and combining suffer from a subspace sampling limitation, that is, the receiver cannot directly observe the channel coefficients; instead, the receiver observes a noisy version of their weighted combination. To resolve this, the transmitter and the receiver usually collaborate to determine the best beamformer combiner pair during the beam-sweeping process. This is done by evaluating a limited number of codewords chosen from a pre-defined codebook. In this study, we propose a new framework inspired by the generalized Lloyd algorithm to design analog beamforming codebooks that optimize various performance metrics including the average beamforming gain, the outage, and the average data rate. The flexibility of our framework enables us to design beamforming codebooks for any array shapes including uniform linear and planar arrays. The other practical complexity in analog beamforming is the low resolution of the phase shifters. Therefore, we have extended our algorithm to create quantized codebooks that outperform the existing codebooks in literature. We have also provided extensive simulations to verify the superiority of our proposed codebook as compared with the existing codebooks.

are expensive. This hinders the realization of digital baseband beamforming as in conventional multiple-input multiple-output (MIMO) systems [1]- [5] particularly in Massive MIMO settings [6]- [9]. Therefore, analog beamforming is usually preferred when all the antennas share a single RF chain and have constant-amplitude constraints on their weights [10].
With one RF chain, the channel coefficients cannot be directly observed. Instead, a noisy version of their linear combination weighted by a vector called the beamforming vector (codeword) is accessible. In the beam-sweeping process, the beamforming vectors are chosen from a pre-defined pool (codebook) of antenna weight vectors that are maintained at the transmitter and the receiver [11]. After the beam-sweeping process, we can attempt to estimate the channel coefficients and use the estimated channel to perform beamforming. Another method is to choose the beamformer/combiner pair that optimizes a certain cost function and use that pair for subsequent transmissions. We call this method as selection-based beamforming, and this will be the focus of our study.
The constant modulus constraint imposed by the phase shifters is a major obstacle to optimizing the beamforming designs [12]. One common solution is to consider the discrete Fourier transform (DFT) codebook, which includes N beams, N being the number of antennas in the array. However, the DFT beams have a narrow beam width and limited sweeping resources; therefore, they provide limited coverage and performance. Hence, the challenge is to design a codebook of beamforming vectors with wide beam widths [13]. In addition, to improve the search efficiency, we may define a hierarchical of codebooks [14]- [16]. For example, a coarse codebook may be defined by using a small number of low-resolution beams that cover the intended angle range, whereas a fine codebook may be defined with a large number of highresolution beams that cover the same intended angle range. In [17], the authors proposed an approach called BeaM Widening via SingleRF Subarray (BMW-SS), where they jointly used the subarray and the deactivation approach to create wide beams. To create wide beams, however, half of the array antennas might need to be deactivated; this limits the application of BMW-SS for mmWave communication. In addition, the proposed approach may not be extended to arrays with an arbitrary number of antenna elements. In [11], a three-level hierarchical codebook was proposed, but it provided a limited beamforming gain. In [14], codewords with wide beams were generated by summing two codewords with narrow beams, but the constant module constraint was not satisfied. In [15], [18], the hybrid precoding structure was used to shape wide beams by exploiting the sparse reconstruction approach, but the wide beams could be shaped accurately only when the number of RF chains was large enough; otherwise, deep sinks appeared within the spatial domain.
Another method for creating wider beams falls under the beam-pattern synthesis (BPS) problem [19], [20], where the goal is to design the beamforming vector (codeword) such that it generates some pre-defined beam patterns. For example, in [21], the preferred beamforming vectors were selected to approximate a beamforming gain mask by using a low complexity local search algorithm. In [22], the analog codewords were designed to minimize the MSE between the pre-defined beam patterns and the beam pattern generated by the beamforming vector. In [23], the authors proposed a codebook design by formulating the BPS as an optimization problem by using both the ripple and the transition band of beam patterns.
However, imposing pre-defined shapes on the beam patterns limits both the performance of the codebook and its adaptability to different array shapes, such as Uniform Linear Array (ULA), Uniform Planar Array (UPA) and Uniform Circular Array (UCA). In addition, considering a hierarchical design is mainly beneficial when the channel is modeled as a one-ray channel (Line-of-sight); otherwise, the hierarchical design might not capture all the available power [17]. Also, there is error propagation in the search process, which can reduce the beamforming performance. The design of the analog-only beamforming vectors with certain shapes or beam widths relies mostly on the beam steering of ULAs. It is difficult to apply this design to non-ULAs because of the lack of intuition about their beam patterns [24], [25]. Indeed, most antennas already deployed in cellular systems are UPAs, which necessitates the need for a more flexible framework considering different antenna configurations. Besides, the existence of quantized phase shifters complicates the design of non-overlapping beam patterns, which might require an exhaustive search over a large space given the large number of antennas [15]. However, the search complexity involved in determining the optimal beamformers by using the exhaustive search algorithm increases exponentially with the number of antennas and the resolution of the phase shifters; this limits and complicates their implementation [16], [21]. Quantized beamforming with perfect knowledge of channel state information (CSI) is also considered in [26], [27]. However, because of the large size of the antenna arrays and the limited number of sweeping resources, the acquisition of CSI matrices could be challenging and would require a more efficient design for the quantized analog beamforming vectors for UPAs without any CSI information [28], [29].
In addition, computational complexity and timing play a central role in the algorithm design [30]- [34].
In this paper, we propose a new framework to design analog beamforming codebooks that enable us to design analog beam vectors without any restrictions on the beam patterns, the number of antennas, or the antenna array shape. We model the codebook design for analog beamforming as a vector quantization problem [35] to seek the codebook that optimizes the performance metric over all possible codebooks. A widely used design approach defines the data source through the use of a finite training set, and uses an iterative procedure called the generalized Lloyd algorithm to generate a codebook [36]. Similarly, our iterative method uses training channel vectors generated based on the system characteristics to output a locally optimal codebook. After the initialization step, the iteration begins by assigning each training channel vector to its "best fit" codeword based on some closeness (distortion) measure and an exhaustive search. Next, given a set of training vectors assigned to a particular codeword, the corresponding codeword is modified to optimize the performance metric relative to its currently assigned training vectors.
The algorithm is essentially the same as the k-means algorithm used in pattern recognition [37] where the codebook design can be interpreted as an unsupervised learning problem to optimally cluster all the training channel vectors and find an optimal codeword for each cluster in order to optimize a desired metric. Unlike [38], where an algorithm was proposed to minimize a specific distortion function for ULAs, our generalized Lloyd-based (LB) framework can be applied to various performance metrics including the average beamforming gain, outage, and the average data rate. In addition, we applied the proposed algorithm to the UPAs that were widely used in the 3GPP standards (see 3GPP TR 38.901) with an arbitrary number of antennas. Due to the flexibility of our proposed method even with a low-resolution phase shifter, this method can outperform existing analog beamforming methods with unlimited resolutions.
In summary, the contributions of this research are as follows: • We propose a general LB algorithm to design analog beamforming codebooks using different number of codewords.
• We consider different antenna array shapes including ULA, which is the most common array shape in the literature, and UPA, which is more practical and insufficiently investigated in literature.
• We propose various codebooks intended for optimizing different metrics including the average beamforming gain, the average data rate, and the outage.
• We also consider quantized phase shifters and show that our proposed codebooks outperform the existing codebooks having ideal phase shifters.
• We compare the performance of our proposed LB codebook with the DFT (beam-steering), BMW-SS [17], and BPS [20] codebooks using extensive simulations.
The rest of paper is organized as follows. In Section II, we present the general settings, including the spatial response description in the 3GPP antenna model, the system model assumptions, and the evaluation metrics. In Section III, we present some codebooks in literature and explain their drawbacks. In Section IV, we introduce our proposed framework including some preliminaries on the Lloyd's algorithm and our generalized algorithm for designing codebooks. We also consider the quantized phase shifters. Then, we provide extensive performance simulations in Section V.
Finally, we present our concluding remarks in Section VI.

II. GENERAL SETTINGS
We consider a mmWave communication system with antenna arrays of N T and N R elements equipped at the transmitter and receiver, respectively. Please note that we assumed single antenna array and single RF chain throughout the report, however, the codebook designs can be extended to multiple antenna arrays and multiple RF chains [39].

A. Spatial Response
We first describe 3GPP antenna model [e.g. see TR 38.901]. Antennas are defined in 3D coordinate system as in Fig. 1. The incoming ray is represented by a pair of two angles (θ, φ), where θ denotes angle to the zenith and φ is the angle between the projection of incoming ray to x-y plane and the x axis. Antennas are located in y-z plane with N v elements in vertical direction and N h elements in horizontal direction. The spacing between two elements are d v and d h in vertical and horizontal directions, respectively. For 1D array, N h will reduce to 1 and array response in φ is identical. We define antenna index (n v , n h ) as the n v th antenna in vertical column and the n h th antenna in horizontal row. Assuming a planar wave model, the location of antenna elements introduce phase offsets. The offset at Antenna (n v , n h ) can be written as [40]: Assume that Antenna (n v , n h ) applies phase shift of w nv,n h , then the array response of antenna system is defined as A(w, θ, φ) = nv,n h w * nv,n h v nv,n h (θ, φ) . The spatial response or the beam pattern of the antenna system is then defined as B(w, θ, φ) = A(w, θ, φ)P E (θ, φ), where P E (θ, φ) denotes the directionality of antenna elements and for an isotropic element P E (θ, φ) = 1. In this work, we consider isotropic elements, however, our proposed framework can also be applied to directional antenna elements. For simple and unified representation, we define N v × N h matrices of W and V (θ, φ) containing w nv,n h and v nv,n h (θ, φ) as their (n v , n h )th element, respectively.
Then, the spatial response (beam pattern) of the corresponding codeword can be written as and v(θ, φ) = vec(V (θ, φ)). Note that the mentioned representation can constitute any antenna array shape with N antenna elements given the corresponding phase offsets vector.

B. System Model
The received signal at the receiver can be written as: where s denote the transmitted symbol with unit power, w T and w R are the N T × 1 transmit and N R × 1 receive beamforming vectors, respectively, H is the N R × N T channel matrix and n is the Gaussian noise vector with power N 0 , i.e., E(nn H ) = N 0 I N R . Beamforming vectors N is a normalization factor such that all the vectors have unit power [17].
The channel matrix can be modeled by the combination of a line-of-sight (LOS) path and a few non-line-of-sight (NLOS) paths as [41]: where κ is the Ricean K-factor, α i ∼ CN (0, 1) is the complex channel gain, I is the number of NLOS paths. Each ray is represented by a pair of two angles (θ, φ) where θ denotes angle to the zenith and φ is the angle between the projection of incoming ray to x-y plane and the x axis as shown in Fig. 1.
vector representing the phase offsets introduced at receive/transmit antenna elements. The average power transmitted from each transmit antenna equals P tot /N T and the total radiated power from the transmitter is thus equal to P tot . After combining the signals from all receive antenna elements, the effective received signal-to-noise ratio (SNR) is defined as δ R = P tot |w H R Hw T | 2 /N 0 . The total beamforming gain due to beamforming at the transmitter and the receiver can be denoted as

C. Selection-based Beamforming
In the selection-based beamforming, a set of codewords is chosen from W (N ) to create the beamforming codebook. After evaluating all the codewords within the pre-designed codebook, the best one which maximizes the desired metric is chosen and used in successive transmissions.
Assuming K sweeping resources, then, the beamforming codebook is denoted as an N × K matrix, W, containing beamforming codewords on its columns. Then, the commonly used beamsweeping process refereed as ping-pong sampling [13] can be explained as follows. During Tx beam-sweeping, the receive beamforming vector can be set to omni-directional beam and then the obtained sample by evaluating the kth codeword in the Tx codebook can be written as: where K is the number of Tx beam-sweeps. The receiver feedbacks the best Tx beamforming vector, i.e., w opt After Rx measurement and feedback, the Tx beam is selected and will be kept the same in the Rx beam-sweeping process.
At the receiver side, all the codewords in the Rx codebook are applied. Similarly, the receiver chooses the best receive beamforming vector, i.e., w R opt by observing K samples of where K is the number of Rx beam-sweeps. Then, the pair of (w opt T , w opt R ) is used for successive transmissions. Consequently, the effective beamforming gain associated with Tx and Rx codebooks can be denoted as Because the beamforming processes are the same at the transmitter and the receiver, we focus on designing the codebook at the receiver side and the same codebook can be used at the transmitter (the index of T/R is discarded).
D. Metrics for Designing Codebooks 1) Average beamforming gain: Different metrics can be considered to compare the codebooks.
One of the common metrics is the average of beamforming gain over different channel Neglecting the beam mis-detection, the effective beamforming gain reduces to Then, the codebook design can be formulated as designing the matrix W which includes K codewords from the feasible set W (N ) maximizing: 2) Outage: Considering the randomness in the channel vectors, the effective beamforming gain, i.e., G B (W), is a random variable whose distribution depends on distribution of h and also the beamforming codebook. Although the average metric, i.e., G B (W), is an important metric in analyzing system performance, in some applications, the individual performance in each realization is of greater importance. This motivates us to define the outage metric as: where γ is a performance threshold specified by the system requirements. The coverage can be defined as the complimentary event of outage as J cov (γ) = 1 − J out (γ). Normalizing the threshold by the maximum possible gain, i.e.,γ = γ/N , J cov (γ) and J out (γ) can be called thê γ-coverage and theγ-outage, respectively. For example, for a 2 × 2 UPA, J cov (2) and J cov (1) are called 1/2-coverage and 1/4-coverage or conventionally 3dB-coverage and 6dB-coverage, respectfully.
To have a unified framework, we rewrite the outage metric as follows J cov (γ) = . We further simplify the outage metric by replacing the sign() function which is not differentiable with sigmoid function defined as: sigmoid(x) = 1 1+e −αx where α is a metric to adjust the steepness of the curve. Thus, the coverage metric can be approximated by 3) Average Data Rate: Average data rate is another important criterion which can be defined as: Other metrics, e.g. bit error rate (BER) performance, can also be considered, thus we propose a unifying approach that can be applied to various performance metrics. Before delving into details of our proposed framework, some of the codebooks in the literature are analyzed in the next Section.

III. PROBLEM STATEMENT
Here, we present and discuss some of the existing beamforming codebooks and their drawbacks. Most of the work in the corresponding literature considers the 1D antenna array (ULA), for which the steering vector reduces to a vector, the only input of which is the angle Assuming a uniform distribution for θ over the spatial domain Ψ, the spatial response can be considered a random variable for any given codeword. For example, for the omni-directional codeword, the spatial response is equal to 1, i.e., B(w) = 1, with a probability of 1. The other common codeword is termed the beamsteering codeword and is defined as The beam-steering codeword can achieve the largest array gain toward its directionality, i.e., N ; however, owing to its narrow beam, it has poor performance for other values of θ. To further analyze the behavior of a codebook, we extend the definition of spatial response to B(W) = max k W[k] H v 2 , which is termed the effective spatial response of the codebook. Assuming θ to be uniformly distributed in [0, 180], the cumulative density function (CDF) of the effective spatial response for the omni-directional codeword and beam-steering codebook with different numbers of codewords is shown in Fig. 2.
The beam width of the Beam-Steering codewords are inversely proportional to the number of antennas, meaning that, when we increase the number of antennas the beams get narrower with smaller beam width. Therefore, with limited number of codewords, the beam-steering codebook fails to provide reliable performance as shown in Fig. 2. It can be observed that 1,2, or even 3 beam-steering codewords provide a worse performance than omni-directional codeword with the The main problem in analog beamforming is that the number of beam-sweeping resources is usually much lower than that of antenna elements. Therefore, the DFT codebook is not a good candidate owing to narrow beam width of its codewords. One solution offered in literature is deactivation, whereby the antenna elements are deactivated to provide wider beams [42].
However, to create wide beams, the number of active antennas becomes small, which limits the maximal total transmission/reception power of a mmWave device. Another solution is using the sub-array technique. In particular, if a large antenna array is divided into multiple sub-arrays and these sub-arrays point at sufficiently-spaced directions, a wider beam can be shaped. The combination of these two methods is termed BMW-SS in [17] and There are other works in the literature which constraint the spatial response to some pre-defined shapes and then attempt to synthesize it with various algorithms [21], [23]. For example, in Fig.   4, the algorithm in [20] is used to generate a codebook with three levels for ULA with 32 antenna elements. Imposing pre-defined shapes on beam patterns, e.g., rectangular-like beam patterns, limits the performance and requires large number of antennas to be realizable [22]. Unlike ULA antenna arrays, in particular UPA. Authors in [17] propose using Kronecker product to extend the 1D codebooks to 2D arrays. Similarly, beam pattern synthesis methods are proposed to synthesize the cubic-like beam patterns [25]. Another solution for 2D antenna arrays is using beam-steering codewords, where w = 1 √ N v(θ, φ). However, unlike ULA, the shape of covered space is much more complicated and changes with different steering angles. When steering angle is around the center, the covered space is more like a circle. When beams are steered towards the edge direction, the covered space has irregular shape. Thus, choosing the peak directions of beam-steering vectors is particularly challenging in 2D. Choosing the peak directions are out of scope of this work, however, two examples of steering angles for 3 codewords and 4 codewords are listed in Table I. The beam patterns of the beam-steering codebooks, given in Table I, are shown in Figs. 5 and 6. However, the extension of the beam-steering codebooks to a larger number of antennas and larger codebook sizes is not straightforward.  The drawbacks of the mentioned codebooks, and more importantly, the lack of a general codebook design for 2D arrays, motivate us to propose a general framework encompassing different array shapes with different numbers of elements and various performance metrics.

A. Preliminaries
One of the closely related topics to our problem, i.e., codebook design for analog beamforming, is the quantization problem, particularly, the vector quantization. A vector quantizer of dimension N and size K is a mapping from a vector in N-dimensional Euclidean Distance R N into a finite set C containing K output or reproduction points. We can write it mathematically as , · · · , C[K]} and C[k] ∈ R N . The set C is called the codebook, and C[k], 1 ≤ k ≤ K, are called the code vectors or codewords. To measure the vector quantizer performance, a distortion measure d(s, Q(s)) has to be defined in association with any input vector s and its reproduction vector Q(s), and consequently the performance of a vector quantizer can be quantified by average distortion as J = E s {d(s, Q(s))} [43]. To permit tractable analysis and easy evaluation, the distortion measure is often chosen to be the squared error, i.e., |s−Q(c)| 2 .
The algorithm often used for generating the codebook is referred to as generalized Lloyd algorithm, since it is a vector generalization of the well-known clustering algorithm due to Lloyd [44]. Application of Lloyd's algorithm can be found in the machine learning contexts as well, such as Adversarial networks [45], GANs [46] and completion/pruning methods [47]- [49].
Generalized Lloyd algorithm is an iterative algorithm based on a set of training vectors which can be described as follows: • Initialization: The initialization step involves choosing the starting codebook of vectors, • Partitioning: Given a codebook C i obtained from the ith iteration, find the optimal partitioning of the space R N using the least-distortion condition, i.e.
• Codeword-Updating: For a given partitioning {Ω i }, find the so-called centroids of each cell, i.e.
The solution to the above optimization problems can be obtained as . For a finite training set, the expected value is replaced by the sample mean of the corresponding cell.
• iterate until the convergence criteria is satisfied.
Note that many different initialization methods have been proposed, including random coding, pruning, pairwise nearest-neighbor design, product code, and splitting. A thorough survey of these methods can be found in [36]. In addition, to improve the performance of the vector quantization codebook, methods other than the standard generalized Lloyd algorithm have been examined, e.g., using stochastic relaxation, such as the simulated annealing [51]. Next, our codebook design algorithm for analog beamforming is introduced.

B. Proposed Algorithm
After brief description of the Generalized Lloyd algorithm, the time is ripe to explain our proposed method. We design an algorithm for maximizing a general performance metric defined as follows: The algorithm can be described as follows: • Generating Training Points: Generate L training vectors of h l , l = 1, · · · , L.
where f (.) can be any desired metric function. Unfortunately, there is no closed-form solution for a general function, thus we use the Gradient decent method to update the codewords in each iteration. Note that this method can work with any differentiable function.
The derivative of J[k] with respect to the vector θ, can be denoted as: ∂f ∂x ∂x ∂w ∂w ∂θ (13) where x is the input variable of function f (.). After some calculations, ∂J[k] ∂θ can be calculated as: where Θ is a diagonal matrix whose nth diagonal element is equal to je jθ(n) . Then, the phase shifts of the kth codeword can be updated as θ k ∂θ k @θ k (i) where is the step size and should be tuned carefully along with the number of iterations.
• Iterate until convergence criteria is satisfied.

Remarks:
The training points can be empirical points obtained by measurements or drawn from some distributions based on the characteristics of the system. If no prior information is available, uniform spatial coverage, i.e., single-ray with uniform angle of arrival (AOA), can be considered.
The proposed algorithm is a decent algorithm, i.e., at each iteration in the algorithm a positive improvement in performance is achieved over the previous iteration, which converges to a local optimal. Powerful initialization techniques and optimization methods that introduce elements of randomness into the algorithm can be applied to improve the resulting performance [51]; however, in this work, to disclose the main concepts, we simply use random initialization and standard gradient decent method as described above. Further improvements in the proposed algorithm can be considered for future work. The algorithm iterates until some convergence criteria, e.g., the difference between two consecutive objective metrics, is satisfied. The flowchart of the algorithm is shown in Fig. 7.
The proposed algorithm scheme has several attractive properties. First, it can be applied to arbitrary codebook sizes. Second, it is indifferent to the training channel vectors and it can be applied to different array shapes including ULA, UPA and UCA. Finally, it can be employed to optimize various performance metrics, e.g., average beamforming gain (f (x) = x), average data rate (f (x) = log(1 + x)) and outage (f (x) = sigmoid(x − γ)).

C. Outage/Coverage Analysis
Here, the effect of the optimization metric in the effective spatial response is shown. In Figs. 8a and 8b, the effective spatial response of two codebooks with 8 codewords are shown which are designed to optimize J avg and J cov (8), respectively, for a 4 × 4 UPA antenna array. The 3dB-outage of the two codebooks optimizing J avg and J out (8) are 19% and 15%, respectively.
In Figs. 9a and 9b, the 6dB-coverage of the codebooks optimizing J avg and J out (4) are shown., respectively. The 6dB-outage of the two codebooks are 7% and 0.1%, verifying the effectiveness of the proposed algorithm for minimizing the outage. More simulation results are shown later, in Section V.

D. Quantized Phase Shifters
So far, we have assumed ideal phase shifters with no constraint on the precision of introduced phase shifts. However, in practice, phase shifters might be limited to few quantized values.
Assume that the value of each phase shifter is specified by B bits. Then, the codebook vectors 2) Quantized Codebook for Optimizing the Outage Metric: In Fig. 10b, the effect of quantization in the outage probability is shown. As you can see, to reach the ideal outage performance, 3 bits and 5 bits per antenna are required when the array size is 4 × 4 and 2 × 2, respectively. However, 1-bit phase shifter does not provide good outage performance, particularly, when the size of array is large. The average is taken over 10 5 different realizations (in each realization, θ i R is chosen uniformly from [0, 180]), and the channel gains and noise samples are drawn from CN (0, 1). The beamsteering codebook is created by considering an equi-spaced direction. Assuming K sweeping times, the BMW-SS and BPS codebooks follow a hierarchical design with K/2 levels, with two codewords evaluated at each level. For a fair comparison, (4,6) and (6,8) sweeping times are considered for ULAs with 8 and 16 antennas, respectively. The LB codebooks are designed to optimize J avg , where the training channel vectors are single-rays whose AOA is uniformly distributed in [0, 180]. In Fig. 11, 4 sweeping times are considered; thus, the BMW-SS and BPS codebooks each consist of 2 levels. The LB codebook provides the best average beamforming gain, approximately 4 dB, 2dB, and 1dB more than the BMW-SS, beam-steering, and BPS codebooks, respectively. With a dominant LOS path, the hierarchical designs, particularly the BPS codebook, get closer to the LB codebook in terms of performance. In the low SNR regime, the hierarchical designs suffer from error propagation in the search step for choosing the best codeword, and the performance is even worse than that of the beam-steering codebook. In In the high SNR regime and LOS scenario, the hierarchical codebook performance is very close to that of the LB codebook, particularly the BMW-SS codebook, whose last level coincides with the DFT codebook. However, in the NLOS scenario, the LB codebook provides better performance. In Fig. 13, a ULA with 16 antenna elements and 6 sweeping times is considered. In Fig. 15, 2 × 2 UPA with 4 sweeping times is considered. The LB codebook is providing around 1 dB (100%) gain compared with other codebooks, in both LOS and NLOS scenarios.
In Fig. 16, 4 × 4 UPA with 4 sweeping times is considered. As it can be seen, noticeable

C. Effective Spatial Response
As explained before, the effective spatial response of a codebook, i.e., B(W, θ) =  codewords is equal to 3, 4.3 and 6.3, respectively. In addition, the maximum value of γ such that J out (γ) = 0, is equal to 1.2, 1.7 and 3.2 for 2, 4 and 8 number of codewords, respectively. Our framework can be utilized to design the system parameters, e.g., number of required sweeping resources, such that specific performance metrics are satisfied. In addition, the beam patterns of (a) γ = 1 of codewords are considered. In Fig. 22a, the codebook presented in Table I and LB codebooks optimizing J out (γ = 1.5, 2, 2.5, 3) are considered. In Fig. 22b, the codebook presented in Table   I  The data rate can also be considered as a random variable denoted by R(W) = log 2 (1 + Ptot N 0 G B (W)) which depends on the distribution of the channel vectors and also the codebook design. We plot the CDF of R(W) assuming Ptot N 0 = 5dB and considering different codebooks including Beam-steering, BMW-SS, BPS and LB. The LB codebooks are designed by optimizing J rate . In Fig. 25, the CDF of R(W) is shown for ULA with 8 antennas and 4 sweeping times, scenarios, respectively, higher than that of other codebooks. It also provides better outage for every data rate threshold. For example, LB codebook provides P r(R(W) < 1) = 9% in LOS scenario, while BPS, BMW-SS and beam-steering codebooks provide 25%, 28% and 42% data rate outage. Similar analysis is shown in Fig. 26, for 2 × 2 UPA with 4 codewords. Higher average data rate and lower data rate outage are provided by using the LB codebook.

E. Quantized Phase Shifters
In this section, performance of the quantized codebooks designed with LB algorithm are analyzed. The average data rate, i.e., R(W), is considered and it is shown that the LB codebook  In this work, we studied the codebook design for analog beamforming and proposed a new framework to design beamforming codebooks. The proposed method is inspired by generalized Lloyd algorithm and is able to optimize various performance metrics including, but not limited to, average beamforming gain, outage, and average data rate. In addition, unlike most of the work in the literature, which are limited to ULAs, the proposed algorithm can be applied to