# Energy-Efficient Design of Broad Beams
for Massive MIMO Systems

Sven O. Petersson, and Maksym A. Girnyk S. O. Petersson is with Ericsson
Research, Gothenburg, Sweden. M. A. Girnyk is with Ericsson Research,
Stockholm, Sweden.

###### Abstract

Massive MIMO is a promising air interface technique for 5G wireless
communications. Such antennas offers capabilities to utilize channel
correlations to create beams suitable for user specific transmissions. Most of
the prior research is devoted to user-specific transmission in such systems,
where a narrow beam is formed towards a user to improve its reception.
Meanwhile, public-channel transmission to multiple users at once by means of
broad beams has been understudied. In this paper, we introduce the concept of
_array-size invariant_ (ASI) beamforming, enabling generation of broad beams
from very large antenna arrays where all elements are transmitting at maximum
power. The ASI technique offers the possibility to achieve a perfectly flat
array factor by exploiting the additional degree of freedom coming from
polarization diversity. The technique is applicable to uniform linear and
rectangular arrays and is characterized by low-complexity beam synthesis. The
usefulness of the ASI beamforming is illustrated by means of a numerical
example showing the design of a cell-specific broad beam for public-channel
transmission in a realistic network deployment.

###### Index Terms:

Array-size invariant beamforming, dual-polarization beamforming, beam design,
broad beam.

##  I Introduction

One of the main goals of mobile communication systems have, for many years,
been to increase user data rates and system throughput. One of the means for
making this happen has been the increase of the number of antennas in order to
more efficiently utilize the spatial domain. Various transmission schemes for
dedicated channels for exchange of user-specific data have been investigated
and standardized in 5G New Radio (NR), see [1] for an overview.

Meanwhile, another important aspect of multi-antenna technology that has
received less attention is transmission in the absence of channel state
information (CSI), often referred to as _broad-beam_ transmission. Such
transmission is suitable for public channels, such as, e.g., Physical Downlink
Control Channel (PDCCH) and Physical Broadcast Channel (PBCH), for
broadcasting cell-specific reference and synchronization signals. Typical
requirements on such transmission are a broad radiation pattern and equal
power per antenna. Unfortunately, designing beams with such characteristics is
not straightforward. It is well known that feeding all elements in an antenna
array with the same amplitude and phase results in a narrow beam, potentially
much narrower than the angular region in which the served users are located.
For instance, 4G Long-Tem Evolution (LTE) specifies _discrete Fourier
transform_ (DFT) based codebooks [2] for user-specific beamforming.

One way to make a beam broader is to apply amplitude tapering. In the most
extreme case, this reduces to transmission from a single active element.
However, since practical transmitters employ a single power amplifier (PA) per
antenna, this results in a significant reduction in output power due to poor
utilization of power resources. Several amplitude-tapering techniques have
been proposed in literature. For instance, a beamforming method proposed in
[3] combines a basis pattern with low gain variations over angle and a phase
sequence to ensure equal average power in each direction. A numerical method
proposed in [4] minimizes the gap with the ideal beam pattern, derived via the
Parseval identity, using an iterative multi-convex optimization algorithm. An
eigenvalue-based optimization approach for codebook beam broadening is
proposed in [5]. Another broad beamforming method, based on minimization of
the transmit power, is proposed in [6]. Furthermore, in [7], a broad beam is
designed by means of Riemannian optimization. Semi-definite programming is
applied to broad beam design in [8].

Nevertheless, it is proven in [9] that the _only_ solution able to achieve
constant transmitted power for all angles, at a given time instant, is the
trivial solution where only one out of all antennas is active. By allowing for
a small variation in transmitted power over the angles, the authors of [9]
were able to find beamforming vectors where all antennas radiate.
Nevertheless, similarly to the aforementioned algorithms, the obtained
solution exhibits mediocre utilization of PAs due to large variations in the
amplitude of the elements in the beamforming vector.

A power-efficient alternative to the above methods is to apply phase tapering.
That is, optimize the phases of the excitation weights, while keeping their
amplitudes fixed. This, however, typically results in a power pattern with
significant ripple. For instance, a method based on Zadoff-Chu sequences,
proposed in [10], designs beamforming weights that ensure that the signal
powers are equal at a set of discrete angles, as many as there are antennas in
the array. In [11], a method for beam broadening was proposed by drawing
numerous random weight phases and picking the broadest pattern, satisfying
certain conditions. Another broadening approach was proposed in [12], where a
broadening function is applied to a reference beamforming vector, typically
based on a DFT vector. By optimizing parameters of the broadening function, it
is possible to increase the angular span of the beam, while reducing the
ripple to some acceptable level. Nevertheless, all of the above approaches
result in ripple in the shape of the beam.

We note that most of the state-of-the-art references assume that the antenna
array is operating with a _single polarization_. However, since the beginning
of 4G the majority of antennas, practically used for mobile communications,
are _dual-polarized_. That is, an antenna array typically operates with a pair
of orthogonal polarizations. Furthermore, most antenna systems are _not_
designed with truly omnidirectional coverage in mind. Instead, they are built
to cover an angular sector corresponding to a cell.111For example, in a
conventional three-sector deployment, a cell has the angular width of only
$120^{\circ}$.

Considering the above observations, this paper rests on a slightly different
problem formulation, where the total transmitted power, i.e., the sum of
powers from two orthogonal polarizations, defines the radiation pattern. This
novel approach to beamforming, referred to as _dual-polarization_ beamforming,
was recently introduced in [13]. Such a formulation allows us to develop a
beamforming technique that, as it turns out, makes it possible to find
beamformers that result in total power patterns that are constant for all
angles at any instant in time.

The proposed technique is referred to as _array-size invariant_ (ASI)
beamforming, and it is based on successive _expansion_ of an antenna array,
while preserving its radiation pattern. The technique ensures excellent power
utilization due to constant transmission power across all antennas. Moreover,
the technique is applicable to one- and two-dimensional arrays and is
characterized with low complexity (logarithmic in the array size). Finally, it
is practically useful since most of the real-world antenna arrays are indeed
dual-polarized and could readily adopt the proposed technique.

The paper’s contributions can be summarized as follows:

  * •

We introduce the concept of ASI beamforming which allows one to increase the
size of an antenna array, while preserving the total radiation pattern of the
original array, as well as ensuring that all the available power at all the
elements of the array is utilized.

  * •

We propose computationally-efficient algorithms for synthesizing perfectly
broad beams (without any ripple) for both one- and two-dimensional uniform
arrays of arbitrarily large size.

  * •

We showcase the usefulness of the proposed ASI beamforming technique by
providing a practically-relevant example of designing a broad beam for public-
channel transmission in a realistic network deployment.

The remainder of the paper is organized as follows. Section II presents system
model, as well as considered antenna arrays. Section III discusses the
fundamental requirements for the broad beam beamforming concept, as well as
presents the main results of the paper: methods for generating broad beams for
one- and two-dimensional arrays. Section IV illustrates the obtained findings
with numerical examples. Finally, Section V presents the conclusions of the
study.

The following notations are used throughout the paper. Upper-case and lower-
case boldface letters respectively denote matrices and column vectors.
Hereafter, $\mathbf{[}\cdot]^{T}$ denotes transpose, $\mathbf{[}\cdot]^{*}$
denotes conjugate, $[\cdot]^{H}$ denotes Hermitian transpose, $\mathbf{I}_{N}$
denotes the $N\times N$ identity matrix, and $\mathbf{J}_{N}$ denotes the
$N\times N$ exchange matrix, i.e., a matrix with ones on the anti-diagonal.
The Kronecker product of two matrices $\mathbf{A}$ and $\mathbf{B}$ is denoted
$\mathbf{A}\otimes\mathbf{B}$. Vectorization of matrix $\mathbf{A}$ is denoted
as $\mathrm{vec}(\mathbf{A})$.

##  II System Model

The antenna arrays considered in this paper are of two types, uniform linear
arrays (ULAs) and uniform rectangular arrays (URAs). It is assumed that all
elements in the arrays are identical dual-polarized antenna elements. It is
further assumed that the embedded elements are ideal, meaning that the power
patterns for the two polarizations are identical and that the element
polarizations are perfectly orthogonal. Fig. 1 shows an illustration of a URA
$M\times N$-elements, for which element positions, polarizations and element
orientation are indicated. The URA collapses into an $N$-element ULA when we
consider the one-dimensional case.

Figure 1: Dual polarized array. $M\times N$-element URA.

###  II-A Uniform Linear Array

The steering vector for an $N$-element ULA along the y-axis, in direction
$\hat{\mathbf{r}}$, is represented by [14]

$\mathbf{a}(\hat{\mathbf{r}})=[1,e^{j\psi_{\textnormal{y}}},e^{j2\psi_{\textnormal{y}}}\cdots,e^{j(N-1)\psi_{\textnormal{y}}}]^{T},$
(1)

where $\hat{\mathbf{r}}$ is a direction vector of unit length, defined as

$\hat{\mathbf{r}}=[\sin\theta\cos\phi,\;\sin\theta\sin\phi,\;\cos\theta]^{T},$
(2)

and

$\psi_{\textnormal{y}}=-2\pi d_{\textnormal{y}}\sin\theta\sin\phi,$ (3)

with $\phi$ being the azimuth angle, $\theta$ being the zenith angle and
$d_{\textnormal{y}}$ being the element spacing in wavelengths along the array
axis.222Note that we here have defined the ULA as a horizontal array to
address the issue of forming broad beams in azimuth. This may be useful in the
cases where one needs to cover an entire sector with broadcast information.
Nevertheless, the need for broad beams also exists in the elevation domain,
e.g., to cover a high-rise building.

Modern communication systems are equipped with dual-polarized antennas with
almost orthogonal polarizations. Hence, one can design a desired beam as a
total power radiation pattern, i.e., the sum of the partial, per polarization,
power patterns by means of the _dual-polarization beamforming_ (DPBF)
technique [13]. Remarkably, it turns out that with DPBF it is often possible
to find unimodular beamforming weights resulting in a desired broad beam shape
for the total power pattern, therewith, due to constant-modulus beamformers,
making efficient use of all the available output power.

Looking at the total power rather than the power for a given polarization—the
conventional approach in the beamforming literature—means that the actual
polarization state is actually ignored. At first, this might seem counter-
intuitive, however, it can be justified by the polarization at the user
equipment (UE) anyway being unknown. The latter is due to the impact of the
radio channel, the unknown orientation of the UE and the unknown polarization
of the UE antenna(s). To counteract performance losses due to all these
effects, diversity reception has become a conventional operation at the
receive end. Furthermore, if desired, there is always a possibility to create
a second beam with identical total power pattern and orthogonal polarization
in all directions.

The total complex electric field radiated by the array, when excited by
beamforming weight vectors $\mathbf{w_{\textnormal{{A}}}}$, for polarization
A, and $\mathbf{w_{\textnormal{{B}}}}$, for polarization B, is given by

$\mathbf{e}(\hat{\mathbf{r}})=\begin{bmatrix}\textnormal{e}_{\textnormal{A}}(\hat{\mathbf{r}})\\\
\textnormal{e}_{\textnormal{B}}(\hat{\mathbf{r}})\end{bmatrix}=\begin{bmatrix}\mathbf{w}_{\textnormal{A}}^{T}\mathbf{a}(\hat{\mathbf{r}})\\\
\mathbf{w}_{\textnormal{B}}^{T}\mathbf{a}(\hat{\mathbf{r}})\end{bmatrix}E_{\textnormal{el}}(\hat{\mathbf{r}}),$
(4)

where $E_{\textnormal{el}}(\hat{\mathbf{r}})$ is the electric field radiated
by a single antenna element, identical for both polarizations.

The total power radiation pattern is found by superposition of the power for
the orthogonal polarizations as

$\displaystyle{G}(\hat{\mathbf{r}})$
$\displaystyle={\mathbf{e}}(\hat{\mathbf{r}})^{H}\;{\mathbf{e}}(\hat{\mathbf{r}})$
(5)
$\displaystyle=A(\hat{\mathbf{r}}){G_{\textnormal{el}}(\hat{\mathbf{r}})},$
(6)

where
$G_{\textnormal{el}}(\hat{\mathbf{r}})=|{E_{\textnormal{el}}(\hat{\mathbf{r}})}|^{2}$
is the element power pattern and $A(\hat{\mathbf{r}})$ is the array factor. As
DPBF involves a sum over two orthogonal polarizations, the conventional
definition of array factor does not apply. Instead, it is defined as

$A(\hat{\mathbf{r}})=\mathbf{a(\hat{\mathbf{r}})}^{H}(\mathbf{w_{\textnormal{{A}}}}^{*}\mathbf{w_{\textnormal{{A}}}}^{T}+\mathbf{w_{\textnormal{{B}}}}^{*}\mathbf{w_{\textnormal{{B}}}}^{T})\mathbf{a(\hat{\mathbf{r}})}.$
(7)

###  II-B Uniform Rectangular Array

Similarly to the case of ULA, the $(m,n)$th entry in the steering matrix
$\mathbf{A}(\hat{\mathbf{r}})$ for a URA reads

${a}_{m,n}(\hat{\mathbf{r}})=e^{j(n\psi_{\textnormal{y}}+m\psi_{\textnormal{z}})},$
(8)

where

$\displaystyle\psi_{\textnormal{y}}$ $\displaystyle=-2\pi
d_{\textnormal{y}}\sin\theta\sin\phi,$ (9)
$\displaystyle\psi_{\textnormal{z}}$ $\displaystyle=-\pi
d_{\textnormal{z}}\cos\theta.$ (10)

The total complex far-field pattern is found, in a similar way as for the ULA,
when excited by beamforming weight matrices $\mathbf{W_{\textnormal{{A}}}}$,
for polarization A, and $\mathbf{W_{\textnormal{{B}}}}$, for polarization B,
as

$\mathbf{e}(\hat{\mathbf{r}})=\begin{bmatrix}\mathrm{vec}^{T}(\mathbf{W}_{\textnormal{A}})\,\mathrm{vec}(\mathbf{A}(\hat{\mathbf{r}}))\\\
\mathrm{vec}^{T}(\mathbf{W}_{\textnormal{B}})\,\mathrm{vec}(\mathbf{A}(\hat{\mathbf{r}}))\end{bmatrix}E_{\textnormal{el}}(\hat{\mathbf{r}}).$
(11)

The total power radiation pattern is, as for the ULA, found by superposition
of the power for the orthogonal polarizations, as in (6). The array factor
definition for an URA is similar to the one for a ULA, and is given by

$\displaystyle A(\hat{\mathbf{r}})=$
$\displaystyle\mathrm{vec}(\mathbf{A}(\hat{\mathbf{r}}))^{H}(\mathrm{vec}^{*}(\mathbf{W}_{\textnormal{A}})\mathrm{vec}^{T}(\mathbf{W}_{\textnormal{A}})$
$\displaystyle+\mathrm{vec}^{*}(\mathbf{W}_{\textnormal{B}})\mathrm{vec}^{T}(\mathbf{W}_{\textnormal{B}}))\mathrm{vec}(\mathbf{A}(\hat{\mathbf{r}})).$
(12)

##  III Broad beam Generation

In this paper, a broad beam is referred to as a radiation pattern with limited
variation in total radiated power in all directions within an angular sector
of interest. A beamforming method that produces such a beam shape shall allow
for the following:

  * •

Creating a desired power pattern (for example, but not limited to, the power
pattern of a single element);

  * •

Using the distributed power resource in an efficient way (ideally by having
constant modulus beamforming weights).

As an extreme case of the above requirements, a broad beam could be defined as
the total power radiation pattern in (6), being identical to the power
radiation pattern for a single element. Equivalently, the array factor must be
flat, i.e.,

$A(\hat{\mathbf{r}})=c\hat{\mathbf{r}},$ (13)

for any direction $\hat{\mathbf{r}}$, where $c$ is a constant.

###  III-A Existing approaches

As mentioned in Sec. I, the subject of finding beamformers that fulfill (13)
has received scholarly attention over the years. Common to all the prior
research is an assumption that beamforming is performed using an array where
all elements are identical, with respect to both radiation pattern and
polarization, i.e., _single-polarization beamforming_ (SPBF). Amplitude and
phase tapering are widely used approaches for designing a beam with spatially
flat array factor for such arrays.

With amplitude tapering one can optimize amplitudes and phases of the
excitation weights to produce a broad beam shape. Unfortunately, in [9], it
was proven that the only true solution for the problem of designing such a
broad beam by means of SPBF is the trivial one where only one element in the
excitation vector is active. This solution is, however, not acceptable in the
case of active antennas due to the very poor utilization of the available
power resources in the antenna array, especially in massive MIMO deployments.
Another common method for designing a broad beam with improved power
utilization is phase tapering. In this case, the corresponding algorithm
optimizes only phases of the excitation weights, while keeping the amplitudes
constant. In this way, it ensures the all the available power is utilized.
There is, however, a limit of the extent to which phase tapering can optimize
the beam shape. Typically, it leads to a certain unavoidable amount of ripple
in the power pattern.

As spotted in [15], there is a trade-off between power utilization and beam
ripple achievable using amplitude and phase tapering. Yet another possible
approach is to address this trade-off by means of multi-objective optimization
[16]. Such a solution provides a compromise between the two requirements: on
constant beam shape and efficient power utilization.

###  III-B Array-Size Invariant Beamforming

Although providing practically acceptable means for wide-sector coverage, the
above existing solutions do not enable the generation of broad beams with a
flat array factor. In this section, we introduce the concept of _array-size
invariant_ (ASI) beamforming that provide a means for generating broad beams
of controllable width. The concept is based on the previously reported
technique of creating beams with identical power patterns and orthogonal
polarizations by means of DPBF [13]. The main idea is to utilize the
additional degree of freedom that comes from using orthogonal polarizations
when designing the antenna excitation weights resulting in a desired beam
shape. The excitation weights can often be designed with no amplitude taper
leading to full power utilization.

The central technique of the ASI approach is the successive doubling of the
size of the array while preserving its power radiation pattern, which we refer
to as the _expansion technique_. Consider, for instance, a ULA with $N$ dual-
polarized antennas which has been designed so that its power radiation pattern
has a desired shape (e.g., as broad as the pattern of a single element); we
refer to such an array as a _protoarray_. The task of the expansion technique
is to expand the protoarray into an _expanded array_ of a larger size, while
preserving the radiation pattern of the former. This is done by designing a
second array that would be appended to the protoarray without distorting the
resulting power pattern; this second array is referred to as the _companion
array_. By appending the companion array to the protoarray, we get an expanded
array of size $2N$ with the same power radiation pattern as the former.

####  III-B1 ULA expansion

Consider a protoarray of size $N$, excited with beamforming weights
$\mathbf{w}_{1,\textnormal{A}}$ and $\mathbf{w}_{1,\textnormal{B}}$ for the
respective polarizations. In order to expand it, while preserving the
radiation pattern, the conditions of the following proposition should hold.

######  Proposition 1.

Let $(\mathbf{w}_{1,\textnormal{A}},\mathbf{w}_{1,\textnormal{B}})$ be a pair
of per-polarization excitation vectors applied to a protoarray yielding a
desired beam shape. Let, furthermore,
$(\mathbf{w}_{2,\textnormal{A}},\mathbf{w}_{2,\textnormal{B}})$ be a pair of
per-polarization excitation vectors applied to a companion array appended to
the protoarray. The radiation pattern of the expanded array with per-
polarization weights given by

$\displaystyle\mathbf{w}_{\textnormal{A}}$
$\displaystyle=[\mathbf{w}_{1,\textnormal{A}}^{T},\mathbf{w}_{2,\textnormal{A}}^{T}]^{T},$
(14) $\displaystyle\mathbf{w}_{\textnormal{B}}$
$\displaystyle=[\mathbf{w}_{1,\textnormal{B}}^{T},\mathbf{w}_{2,\textnormal{B}}^{T}]^{T},$
(15)

preserves the pattern of the protoarray if

$\displaystyle\mathbf{w}_{2,\textnormal{A}}$
$\displaystyle=-\mathbf{J}_{N}\mathbf{w}_{1,\textnormal{B}}^{*},$ (16)
$\displaystyle\mathbf{w}_{2,\textnormal{B}}$
$\displaystyle=\mathbf{J}_{N}\mathbf{w}_{1,\textnormal{A}}^{*},$ (17)

###### Proof:

First, we note that the radiation pattern of the protoarray is given by

$G_{1}(\hat{\mathbf{r}})=\left[|\mathbf{w}_{1,\textnormal{A}}^{T}\mathbf{a}_{1}(\hat{\mathbf{r}})|^{2}+|\mathbf{w}_{1,\textnormal{B}}^{T}\mathbf{a}_{1}(\hat{\mathbf{r}})|^{2}\right]G_{\textnormal{el}}(\hat{\mathbf{r}})$
(18)

When appending the companion array to the protoarray, we obtain an expanded
array of size $2N$ with excitation weights given by (14) and (15), as well as
the steering vector given by

$\displaystyle\mathbf{a}(\hat{\mathbf{r}})$
$\displaystyle=[{a}_{1}(\hat{\mathbf{r}}),\cdots,{a}_{2N}(\hat{\mathbf{r}})]^{T}.$
(19)

The radiated electric-field vector of the expanded array is given by the
superposition of the fields of the two parts

$\displaystyle\mathbf{e}(\hat{\mathbf{r}})$
$\displaystyle=\mathbf{e}_{1}(\hat{\mathbf{r}})+\mathbf{e}_{2}(\hat{\mathbf{r}})$
(20)
$\displaystyle=\left[\begin{matrix}\mathbf{w}_{1,\textnormal{A}}^{T}\mathbf{a}_{1}(\hat{\mathbf{r}})+\mathbf{w}_{2,\textnormal{A}}^{T}\mathbf{a}_{2}(\hat{\mathbf{r}})\\\
\mathbf{w}_{1,\textnormal{B}}^{T}\mathbf{a}_{1}(\hat{\mathbf{r}})+\mathbf{w}_{2,\textnormal{B}}^{T}\mathbf{a}_{2}(\hat{\mathbf{r}})\end{matrix}\right]E_{\textnormal{el}}(\hat{\mathbf{r}}).$
(21)

The total radiation power pattern of the expanded array is thus given by

$\displaystyle G(\hat{\mathbf{r}})$
$\displaystyle=\mathbf{e}^{H}(\hat{\mathbf{r}})\mathbf{e}(\hat{\mathbf{r}})$
(22)
$\displaystyle=\|\mathbf{e}_{1}(\hat{\mathbf{r}})\|^{2}+\|\mathbf{e}_{2}(\hat{\mathbf{r}})\|^{2}+2\;\textrm{Re}\left\\{\mathbf{e}_{1}^{H}(\hat{\mathbf{r}})\mathbf{e}_{2}(\hat{\mathbf{r}})\right\\}.$
(23)

If the electric field vectors radiated from the two subarrays are orthogonal,
the last term disappears.

$\displaystyle\mathbf{e}_{1}^{H}(\hat{\mathbf{r}})\mathbf{e}_{2}(\hat{\mathbf{r}})=$
$\displaystyle\left[\mathbf{a}_{1}^{H}(\hat{\mathbf{r}})\mathbf{w}_{1,\textnormal{A}}^{*}\mathbf{w}_{2,\textnormal{A}}^{T}\mathbf{a}_{2}(\hat{\mathbf{r}})\right.$
$\displaystyle+\left.\mathbf{a}_{1}^{H}(\hat{\mathbf{r}})\mathbf{w}_{1,\textnormal{B}}^{*}\mathbf{w}_{2,\textnormal{B}}^{T}\mathbf{a}_{2}(\hat{\mathbf{r}})\right]G_{\textnormal{el}}(\hat{\mathbf{r}}).$
(24)

We notice that the steering vectors of the companion array and the protoarray
are related by

$\mathbf{a}_{2}(\hat{\mathbf{r}})=e^{jN\psi_{\textnormal{y}}}\;\mathbf{a}_{1}(\hat{\mathbf{r}}),$
(25)

where $\psi_{\textnormal{y}}=-2\pi\;d_{\textnormal{y}}\sin\theta\sin\phi$.
Next, we plug in the weights given in (16) and (17) and, utilizing the fact
that

$\mathbf{J}_{N}\mathbf{a}_{2}(\hat{\mathbf{r}})=e^{j(N-1)\psi_{\textnormal{y}}}\;\mathbf{a}_{2}^{*}(\hat{\mathbf{r}}),$
(26)

as well as transposing the second term, we get

$\displaystyle\mathbf{e}_{1}^{H}(\hat{\mathbf{r}})$
$\displaystyle\mathbf{e}_{2}(\hat{\mathbf{r}})=\left[-\mathbf{a}_{1}^{H}(\hat{\mathbf{r}})\mathbf{w}_{1,\textnormal{A}}^{*}\mathbf{w}_{1,\textnormal{B}}^{H}\mathbf{a}_{1}^{*}(\hat{\mathbf{r}})e^{j(2N-1)\psi_{\textnormal{y}}}\right.$
$\displaystyle+\left.\left(\mathbf{a}_{1}^{H}(\hat{\mathbf{r}})\mathbf{w}_{1,\textnormal{A}}^{*}\mathbf{w}_{1,\textnormal{B}}^{H}\mathbf{a}_{1}^{*}(\hat{\mathbf{r}})e^{j(2N-1)\psi_{\textnormal{y}}}\right)^{T}\right]G_{\textnormal{el}}(\hat{\mathbf{r}}).$
(27)

since both summands are scalars, the transposition operation does not affect
them, and hence the two terms inside the braces cancel each other out,
yielding
$\mathbf{e}_{1}^{H}(\hat{\mathbf{r}})\mathbf{e}_{2}(\hat{\mathbf{r}})=0$.
Thus, the choice of excitation weights for the companion array in (16) and
(17) leads to electric fields being orthogonal for every observation angle.
The total power radiation pattern is therefore given by

$\displaystyle G(\hat{\mathbf{r}})$
$\displaystyle=2\left[|\mathbf{w}_{1,\textnormal{A}}^{T}\mathbf{a}_{1}(\hat{\mathbf{r}})|^{2}+|\mathbf{w}_{1,\textnormal{B}}^{T}\mathbf{a}_{1}(\hat{\mathbf{r}})|^{2}\right]G_{\textnormal{el}}(\hat{\mathbf{r}})$
(28) $\displaystyle=2\;G_{1}(\hat{\mathbf{r}}),$ (29)

being a scaled version of the pattern of the protoarray (18).

∎

Figure 2: Array expansion for ULA by appending a synthesized companion array
to the protoarray.

The procedure described above is illustrated in Fig. 2. It can be conducted
successively $k$ times to obtain a $k$-fold array expansion summarized in
Algorithm 1. Note that the algorithm has very low computational complexity,
$\mathcal{O}(\log N)$.

Remarkably, if the expansion starts from a single antenna element, the entire
array will have an array pattern that is a scaled version of the pattern of an
individual element. At the same time, all the PAs of the expanded array are
fully utilized, and, in principle, there exists no upper limit for the size of
such an expanded array.

Algorithm 1 ULA Expansion.

0: Size $K=2^{k}N$ of the desired large array, $N$-antenna protoarray with a
pre-designed pattern given by weights $\mathbf{w}_{1,A}$ and
$\mathbf{w}_{1,B}$.

1: for $i\leftarrow 1$ to $k$ do

2: Compute the excitation weight vectors $\mathbf{w}_{2,A}$ and
$\mathbf{w}_{2,B}$ of the companion array using (16) and (17).

3: Stack the weight vectors of the companion array and the protoarray as in
(14) and (15) and obtain the excitation weight vectors $\mathbf{w}_{A}$ and
$\mathbf{w}_{B}$ of an expanded array.

4:
$(\mathbf{w}_{1,A},\mathbf{w}_{1,B})\leftarrow(\mathbf{w}_{A},\mathbf{w}_{B})$,
i.e., replace the protoarray with the expanded array.

5: end for

(a) Horizontal expansion.

(b) Vertical expansion.

Figure 3: Array expansion for URA by appending the companion array to the
protoarray in different ways.

####  III-B2 URA expansion

Consider a rectangular protoarray of size $N\times M$, excited with
beamforming weights $\mathbf{W}_{1,\textnormal{A}}$ and
$\mathbf{W}_{1,\textnormal{B}}$ for the respective polarizations. In order to
expand it with preserving the total power radiation pattern, the conditions of
the following should hold.

######  Proposition 2.

Let $(\mathbf{W}_{1,\textnormal{A}},\mathbf{W}_{1,\textnormal{B}})$ be a pair
of per-polarization excitation matrices applied to a protoarray yielding a
desired beam shape. Let, furthermore,
$(\mathbf{W}_{2,\textnormal{A}},\mathbf{W}_{2,\textnormal{B}})$ be a pair of
per-polarization excitation vectors applied to a companion array appended to
the protoarray. The radiation pattern of the expanded array with per-
polarization weights given by one of the ways below

$\displaystyle\mathbf{W}_{\textnormal{A}}$
$\displaystyle=[\mathbf{W}_{1,\textnormal{A}}^{T},\mathbf{W}_{2,\textnormal{A}}^{T}]^{T},$
$\displaystyle\mathbf{W}_{\textnormal{B}}$
$\displaystyle=[\mathbf{W}_{1,\textnormal{B}}^{T},\mathbf{W}_{2,\textnormal{B}}^{T}]^{T},$
(30) $\displaystyle\mathbf{W}_{\textnormal{A}}$
$\displaystyle=[\mathbf{W}_{1,\textnormal{A}},\mathbf{W}_{2,\textnormal{A}}],$
$\displaystyle\mathbf{W}_{\textnormal{B}}$
$\displaystyle=[\mathbf{W}_{1,\textnormal{B}},\mathbf{W}_{2,\textnormal{B}}],$
(31)

preserves the pattern of the protoarray if the companion array is excited with

$\displaystyle\mathbf{W}_{2,\textnormal{A}}$
$\displaystyle=-\mathbf{J}_{M}\mathbf{W}_{1,\textnormal{B}}^{*}\mathbf{J}_{N},$
(32) $\displaystyle\mathbf{W}_{2,\textnormal{B}}$
$\displaystyle=\mathbf{J}_{M}\mathbf{W}_{1,\textnormal{A}}^{*}\mathbf{J}_{N},$
(33)

where $\mathbf{J}_{M}$ is the exchange matrix of size $M\times M$,
$\mathbf{J}_{N}$ is the exchange matrix of size $N\times N$.

###### Proof:

Here we follow the same steps as in the case of ULA. The radiated electric-
field vector of the expanded array is given by the superposition of the fields
of the two parts

$\displaystyle\mathbf{e}(\hat{\mathbf{r}})=\mathbf{e}_{1}(\hat{\mathbf{r}})+\mathbf{e}_{2}(\hat{\mathbf{r}}),$
(34)

and the total power radiation pattern of the expanded array is thus given by

$\displaystyle
G(\hat{\mathbf{r}})=\|\mathbf{e}_{1}(\hat{\mathbf{r}})\|^{2}+\|\mathbf{e}_{2}(\hat{\mathbf{r}})\|^{2}+2\;\textrm{Re}\left\\{\mathbf{e}_{1}^{H}(\hat{\mathbf{r}})\mathbf{e}_{2}(\hat{\mathbf{r}})\right\\}.$
(35)

The last term disappears when

$\displaystyle\mathrm{vec}^{H}(\mathbf{A}_{1}(\hat{\mathbf{r}}))\mathrm{vec}^{*}(\mathbf{W}_{1,\textnormal{A}})\mathrm{vec}^{T}(\mathbf{W}_{2,\textnormal{A}})\mathrm{vec}(\mathbf{A}_{2}(\hat{\mathbf{r}}))$
$\displaystyle+\mathrm{vec}^{H}(\mathbf{A}_{1}(\hat{\mathbf{r}}))\mathrm{vec}^{*}(\mathbf{W}_{1,\textnormal{B}})\mathrm{vec}^{T}(\mathbf{W}_{2,\textnormal{B}})\mathrm{vec}(\mathbf{A}_{2}(\hat{\mathbf{r}}))=0.$
(36)

We notice that the steering matrices of the companion array and the protoarray
are related as

$\mathbf{A}_{2}(\hat{\mathbf{r}})=\kappa\mathbf{A}_{1}(\hat{\mathbf{r}}),$
(37)

where $\kappa=\exp(jN\psi_{\textnormal{z}})$ when the companion array is
attached as in (30), and $\kappa=\exp{jM\psi_{\textnormal{y}}}$ when it is
attached as in (31). We plug in the excitation weights given in (32) and (33)
and, utilizing the fact that

$\mathbf{J}_{M}\mathbf{A}_{2}(\hat{\mathbf{r}})\mathbf{J}_{N}=\xi\mathbf{A}_{2}^{*}(\hat{\mathbf{r}}),$
(38)

where $\xi=\exp(j\;[(N-1)\psi_{\textnormal{y}}+(M-1)\psi_{\textnormal{z}}])$.
Furthermore, transposing the second term, we see that

$\displaystyle-$
$\displaystyle\mathrm{vec}^{H}(\mathbf{A}_{1}(\hat{\mathbf{r}}))\mathrm{vec}^{*}(\mathbf{W}_{1,\textnormal{A}})\mathrm{vec}^{H}(\mathbf{W}_{1,\textnormal{B}})\mathrm{vec}^{*}(\mathbf{A}_{1}(\hat{\mathbf{r}}))\kappa\xi$
$\displaystyle+$
$\displaystyle(\mathrm{vec}^{H}\\!(\mathbf{A}_{1}(\hat{\mathbf{r}}))\mathrm{vec}^{*}(\mathbf{W}_{1,\textnormal{A}})\mathrm{vec}^{H}\\!(\mathbf{W}_{1,\textnormal{B}})\mathrm{vec}^{*}(\mathbf{A}_{1}(\hat{\mathbf{r}}))\kappa\xi)^{T}\\!\\!\\!=\\!0$
(39)

since both summands are scalars. Therefore,
$\mathbf{e}_{1}^{H}(\hat{\mathbf{r}})\mathbf{e}_{2}(\hat{\mathbf{r}})=0$, and
the choice of wights for the companion array in (32) and (33) leads to
electric fields generated by the two arrays being orthogonal for every
observation angle. The total radiation power pattern is therefore given by

$\displaystyle G(\hat{\mathbf{r}})=$
$\displaystyle\;2\left[|\mathrm{vec}^{T}(\mathbf{W}_{1,\textnormal{A}})\mathrm{vec}(\mathbf{A}(\hat{\mathbf{r}})|^{2}\right.$
$\displaystyle+\left.|\mathrm{vec}^{T}(\mathbf{W}_{1,\textnormal{B}})\mathrm{vec}(\mathbf{A}(\hat{\mathbf{r}})|^{2}\right]G_{\textnormal{el}}(\hat{\mathbf{r}})$
(40) $\displaystyle=$ $\displaystyle\;2\;G_{1}(\hat{\mathbf{r}}),$ (41)

being a scaled version of the pattern of the protoarray. ∎

The procedure is illustrated in Fig. 3 on the top of next page. Similarly to
the one-dimensional case, the expansion can also be repeated successively
$k+l$ times to produce an expanded URA that preserves the radiation pattern of
its protoarray, as summarized in Algorithm 2.333Note that the order of
expansion—horizontal, then vertical, or vice versa—does not influence the
final radiation pattern, as far as total power pattern is concerned. Again,
the complexity is logarithmic in array sizes, i.e., $\mathcal{O}(\log N+\log
M)$.

Algorithm 2 URA Expansion.

0: Size $L\times K$ of the desired large array, where $L=2^{l}M$ and
$K=2^{k}N$. $M\times N$-antenna protoarray with a pre-designed pattern via
per-polarization weight matrices $\mathbf{W}_{1,A}$ and $\mathbf{W}_{1,B}$. //
Horizontal expansion

1: for $j\leftarrow 1$ to $k$ do

2: Compute the excitation weight matrices $\mathbf{W}_{2,A}$ and
$\mathbf{W}_{2,B}$ of the companion array using (32) or (33).

3: Stack the weight matrices of the companion array and the protoarray as in
(30), and obtain the excitation weight matrices $\mathbf{W}_{A}$ and
$\mathbf{W}_{B}$ of an expanded array.

4:
$(\mathbf{W}_{1,A},\mathbf{W}_{1,B})\leftarrow(\mathbf{W}_{A},\mathbf{W}_{B})$,
i.e., replace the protoarray with the expanded array.

5: end for// Vertical expansion

6: for $i\leftarrow 1$ to $l$ do

7: Compute the excitation weight matrices $\mathbf{W}_{2,A}$ and
$\mathbf{W}_{2,B}$ of the companion array using (32) or (33).

8: Stack the weight matrices of the companion array and the protoarray as in
(30), and obtain the excitation weight matrices $\mathbf{W}_{A}$ and
$\mathbf{W}_{B}$ of an expanded array.

9:
$(\mathbf{W}_{1,A},\mathbf{W}_{1,B})\leftarrow(\mathbf{W}_{A},\mathbf{W}_{B})$,
i.e., replace the protoarray with the expanded array.

10: end for

##  IV Numerical Examples

In the previous section, we have shown that by means of the ASI technique it
is possible to, for many array sizes, design a beamformer that not only
results in a desired total power pattern, but also ensures very efficient
utilization of PAs. The companion array, designed according to Algorithms 1
and 2, will have the same power utilization as the protoarray. Therefore, the
power utilization for the weights, after expansion, will be the same as that
for the protoarray. And, given that each antenna element is fed by identical
PAs no matter the size of the array, it follows that

the total output power will increase by a factor of two for each iteration of
the algorithm as the array size increases.

(a) $k=3$.

(b) $k=7$.

Figure 4: Array factor for single element after $k$-fold one-dimensional
expansion.

Below, we will present several numerical examples illustrating the usefulness
of the proposed beamforming method.

###  IV-A Spatially flat array factor

One example which has received a lot of interest in literature in recent years
is the design of a constant-modulus beamforming vector whose radiation pattern
looks like if it was formed by a single antenna element [9, 8]. We recall that
a beam pattern of a ULA can be written as a product of the array factor and
the element pattern. Hence, for the case where the target is a beam pattern
similar to that of a single element, we need to find a spatially flat array
factor. Interestingly, this array factor can be found for any ULA, regardless
of the element separation. Here we demonstrate how beamforming weights can be
designed with a simple example.

For that matter, we set the target to be the power pattern formed by a single
element. That is, the protoarray is chosen to be a single dual-polarized
element with excitation weights given by, e.g.,

$\mathbf{w}_{1,\textnormal{A}}=\mathbf{w}_{1,\textnormal{B}}=1.$ (42)

####  IV-A1 Uniform linear array

Consider a ULA with $N=8$ dual-polarized antennas. Following the procedure
outlined in Algorithm 1, we start with a single dual-polarized element, and
expand it $k=3$ times. Thus, we arrive at a pair of excitation vectors of
length $2^{k}=8$, each for its corresponding polarization:

$\displaystyle\mathbf{w}_{\textnormal{A}}$
$\displaystyle=[\;1,-1,-1,-1,-1,\hphantom{-}1,-1,-1]^{T},$ (43)
$\displaystyle\mathbf{w}_{\textnormal{B}}$
$\displaystyle=[\;1,\hphantom{-}1,-1,\hphantom{-}1,-1,-1,-1,\hphantom{-}1]^{T},$
(44)

As can be seen, these excitation vectors are constant modulus so power
amplifiers in an active antenna array can be efficiently utilized with no loss
due to amplitude taper.

The array factor corresponding to the excitation weights above is shown in
Fig. 4(a). As can be seen from the figure, the patterns in individual
polarizations fluctuate with spatial angle. However, in any direction, the
power of the two orthogonal polarizations adds up to the same value. Thus, the
array factor for the total power is flat.

A similar example but for a much larger ULA, now with $N=128$ elements is
shown in Fig. 4(b). The beamforming weights were found by means of Algorithm 1
with $k=7$-fold expansion of a single element. The beamforming vectors are
omitted here due to their length. Just as in the previous case, the
beamforming vectors are characterized with constant modulus. Therefore, the
power loss of more than 8 dB due to amplitude taper reported in [9] for
$N=128$, can be avoided with the technique presented herein.

(a) Per-polarization array factors and total array factor.

(b) Array factor in polar coordinates.

Figure 5: Array factor of a single element after two-dimensional expansion by
a factor of 8 along each dimension.

####  IV-A2 Uniform rectangular array

Consider a URA with $M\times N=8\times 8$ antennas. To design the excitation
vectors for this case we follow the procedure outlined in Algorithm 2. We
start by expanding the single-element protoarray along one dimension. Which
dimension to start with does not really matter, but here we have selected to
start the expansion along elevation (index $j$) until we have a one-
dimensional array of size $8\times 1$. The excitation vectors after this step,
which are identical to the excitation vectors in (43) and (44), now form a new
protoarray, which we further expand along the other dimension, i.e., azimuth
(index $i$), to form a two-dimensional array. The resulting excitation weight
matrices (one per polarization) are shown in (45) and (46). As can be seen,
similarly to the previous case, the excitation matrices are constant-modulus.
The array factors per polarization as well as for total power are shown in
Fig. 5(a). The total power array factor (only the front half sphere) is also
shown in Fig. 5(b) in polar coordinates. As can be seen from Fig. 5, the array
factor for total power is spatially flat and thus the resulting beam pattern
will be a scaled version of the element pattern.

$\displaystyle\mathbf{W}_{\textnormal{A}}=\begin{bmatrix}\hphantom{-}1&-1&-1&-1&-1&\hphantom{-}1&-1&-1\\\
-1&\hphantom{-}1&\hphantom{-}1&\hphantom{-}1&\hphantom{-}1&-1&\hphantom{-}1&\hphantom{-}1\\\
-1&\hphantom{-}1&\hphantom{-}1&\hphantom{-}1&\hphantom{-}1&-1&\hphantom{-}1&\hphantom{-}1\\\
-1&\hphantom{-}1&\hphantom{-}1&\hphantom{-}1&\hphantom{-}1&-1&\hphantom{-}1&\hphantom{-}1\\\
-1&-1&\hphantom{-}1&-1&\hphantom{-}1&\hphantom{-}1&\hphantom{-}1&-1\\\
\hphantom{-}1&\hphantom{-}1&-1&\hphantom{-}1&-1&-1&-1&\hphantom{-}1\\\
-1&-1&\hphantom{-}1&-1&\hphantom{-}1&\hphantom{-}1&\hphantom{-}1&-1\\\
-1&-1&\hphantom{-}1&-1&\hphantom{-}1&\hphantom{-}1&\hphantom{-}1&-1\end{bmatrix}$
(45)
$\displaystyle\mathbf{W}_{\textnormal{B}}=\begin{bmatrix}\hphantom{-}1&-1&-1&-1&-1&\hphantom{-}1&-1&-1\\\
\hphantom{-}1&-1&-1&-1&-1&\hphantom{-}1&-1&-1\\\
-1&\hphantom{-}1&\hphantom{-}1&\hphantom{-}1&\hphantom{-}1&-1&\hphantom{-}1&\hphantom{-}1\\\
\hphantom{-}1&-1&-1&-1&-1&\hphantom{-}1&-1&-1\\\
-1&-1&\hphantom{-}1&-1&\hphantom{-}1&\hphantom{-}1&\hphantom{-}1&-1\\\
-1&-1&\hphantom{-}1&-1&\hphantom{-}1&\hphantom{-}1&\hphantom{-}1&-1\\\
-1&-1&\hphantom{-}1&-1&\hphantom{-}1&\hphantom{-}1&\hphantom{-}1&-1\\\
\hphantom{-}1&\hphantom{-}1&-1&\hphantom{-}1&-1&-1&-1&\hphantom{-}1\end{bmatrix}$
(46)

###  IV-B Design of a cell-specific beam

The above result shows that, even though the conclusions of [9] hold for SPBF,
it is indeed possible achieve omnidirectional transmission by using DPBF
(provided that the subelement also has omnidirectional radiation pattern).
However, this is rarely required in practice. Instead, one typically needs to
design a cell-specific beam with certain characteristics for a specified
antenna array. We present an example of such beam design with detailed
discussion below.

TABLE I: Array parameters considered for the example. Attribute |  Value
---|---
Array size ($M\times N$) |  $8\times 8$ elements
Subarray size |  $2\times 1$ elements
Polarizations |  Two orthogonal
Element pattern (both polarizations) |  Gaussian
Element HPBW, elevation |  90∘
Element HPBW, azimuth |  90∘
Column separation $d_{\textnormal{y}}$ |  $0.5\lambda$
Row separation (for URA) $d_{\textnormal{z}}$ |  $0.6\lambda$
Target beam pattern shape |  Gaussian
Target HPBW, elevation |  15∘
Target HPBW, azimuth |  65∘
Electrical array tilt |  6∘
Electrical sub-array tilt |  6∘
Inter-site distance |  500 m
Cell hole radius |  25 m
Building height |  20 m
BS height |  25 m
BS power |  46 dBm
Number of UE drops per cell |  $\sim 7400$
Number of UE antennas |  2, orthogonal polariz.
UE antenna gain |  0 dBi
Height outdoor UE |  1.5 m
Height indoor UE |  Uniform within building
Indoor UEs |  80 %
Lognormal fading |  6 dB
Angular spread (elevation and azimuth) |  Uniform$(2^{\circ},5^{\circ})$
Frequency |  3.5 GHz
Pathloss model |  From TR 38.901 [17]
Scenario |  3GPP UMa [17]

Consider a typical cellular deployment with three sectors. To cover each
sector, an angular range of $120^{\circ}$ should be covered with a single
beam. To avoid interference to the neighboring sectors, the beam should have a
matching angular width at the level of $-10$ dB with respect to the beam peak.
Provided that such a beam has a smooth Gaussian shape, the HPBW of such a beam
should be roughly $65^{\circ}$. The pattern of a single cross-pole element
typically has HPBW of $90^{\circ}$ or even wider. Therefore, it appears too
broad for cell coverage. Meanwhile, the DFT beam produced by a ULA with $N=8$
antennas has HPBW of $\sim 10^{\circ}$, which is too narrow. Therefore, we
need to optimize the beam pattern to find an intermediate configuration with
the desired HPBW of $65^{\circ}$.

To optimize beamforming weights resulting in a desired beam shape we utilize
the robust multi-objective Godlike optimizer [18]. Optimizations here are run
with two objectives:

  * •

Variance for the difference, in dB, between a target power pattern and the
synthesized total power pattern within a certain angular range;

  * •

Power utilization, or equivalently taper loss, defined as

$\displaystyle
L_{\textnormal{taper}}(\mathbf{W}_{\textnormal{A}},\mathbf{W}_{\textnormal{B}})=$
$\displaystyle\frac{2MN\max(|[\mathrm{vec}^{T}(\mathbf{W}_{\textnormal{A}}),\mathrm{vec}^{T}(\mathbf{W}_{\textnormal{B}})]^{T}|^{2})}{\|[\mathrm{vec}^{T}(\mathbf{W}_{\textnormal{A}}),\mathrm{vec}^{T}(\mathbf{W}_{\textnormal{B}})]^{T}\|^{2}}.$
(47)

To find the beamforming matrices for a URA with $M\times N$ dual-polarized
elements one could run the optimization for the entire 2D-array. However, that
is a difficult and time consuming task due to the large number of parameters.
To simplify the former, we note that the total radiation pattern is a
combination of the elevation pattern and the azimuth pattern. Therefore, we
can optimize beamforming vectors for elevation and azimuth separately, thereby
significantly reducing the computational complexity.

The array configuration and deployment of interest are summarized in Table I.
Note that in contrast to the azimuth dimension, where UEs are spread widely
over the entire $120^{\circ}$-wide sector, in the elevation dimension, UEs are
located within a rather narrow angular sector. Hence, a narrow radiation
pattern is required in elevation, pointing at the center of the UE
distribution, as seen from the BS. In practice, this is often achieved by
means of _virtualization_ , i.e., partitioning the entire array into subarrays
and treating those as array elements, as well as applying a tilt angle. This
means that our $M\times N$ array is reduced to an array of size $M/2\times N$
whose elements will be subarrays of size $2\times 1$ with pattern down-tilted
by $6^{\circ}$. Again, according to the pattern multiplication property, the
total radiation pattern of the array is given by the product of the array
factor and the pattern of the subarray.

(a) Elevation cut.

(b) Azimuth cut.

Figure 6: Elevation and azimuth cuts for optimized beam patterns.

####  IV-B1 SPBF radiation patterns

For the case of SPBF, the beam pattern for the sector-wide public-channel
transmission is optimized separately for elevation and azimuth patterns. The
patterns are then combined into a three-dimensional pattern as follows. Assume
that $\mathbf{w}_{\mathrm{y}}\in\mathbb{C}^{N}$ and
$\mathbf{w}_{\mathrm{z}}\in\mathbb{C}^{M}$ are optimized beamforming vectors
in azimuth and elevation dimensions, respectively. The optimized SPBF
beamforming matrix of the entire two-dimensional array is then given by

$\mathbf{W}=\mathbf{w}_{\mathrm{z}}\otimes\mathbf{w}_{\mathrm{y}}^{T}\in\mathbb{C}^{M\times
N}.$ (48)

In elevation, the following SPBF beamforming vector (electrical tilt not
included) is used to feed the 4 subarrays,

$\mathbf{w}_{\mathrm{z},1}=\begin{bmatrix}\;0.297-0.146j\\\ 0.271+0.256j\\\
0.267+0.260j\\\ 0.301-0.146j\end{bmatrix}.\\\ $ (49)

The corresponding vector feeding the elements is found via

$\mathbf{w}_{\mathrm{z}}=\mathbf{w}_{\mathrm{z},1}\otimes[1,1]^{T}\in\mathbb{C}^{M}.\\\
$ (50)

In azimuth, the following SPBF beamforming vector is used to feed the 8
columns

$\mathbf{w}_{\mathrm{y}}=\begin{bmatrix}\;\hphantom{-}0.189+0.189j\\\
\hphantom{-}0.093-0.165j\\\ -0.244+0.112j\\\ -0.129+0.232j\\\ -0.129+0.232j\\\
-0.244+0.112j\\\ \hphantom{-}0.093-0.165j\\\
\hphantom{-}0.189+0.189j\end{bmatrix}.\\\ $ (51)

As both $\mathbf{w}_{z}$ and $\mathbf{w}_{z}$ are SPBF vectors the excitation
matrix for the two-dimensional array $\mathbf{W}$, (48), will also be SPBF.
Thus, only half of the elements, and hence PAs, in the array will be in use.
For that reason we feed also the orthogonal polarization B using the same
excitation matrix as for the first polarization A. Finally, we apply a scaling
factor, $\alpha$, to the total excitation matrix, which takes base station
(BS) output power from Table I and taper loss (47) into account,

$\alpha=(P_{\textnormal{BS}}/L_{\textnormal{taper}})^{2}/{\|[\mathrm{vec}^{T}(\mathbf{W}_{\textnormal{A}}),\mathrm{vec}^{T}(\mathbf{W}_{\textnormal{B}})]^{T}\|},$
(52)

This scaling factor ensures the correct output power without overloading any
power amplifier. In addition, we also need to apply the tilt according to
Table I.

####  IV-B2 DPBF radiation patterns

The process for deriving excitation matrices for DPBF is similar to the one
for SPBF patterns, but there are some important differences. One is that we
now have two matrices, one per element polarization, for both elevation and
azimuth beamforming. Another one is that, when creating the matrices for the
entire two-dimensional array, one must avoid introducing amplitude variations.

Here, the elevation pattern is optimized using the Godlike optimizer [18] with
the constraints that the excitation weights shall be constant modulus (i.e.,
phase-only taper) and that the elevation power pattern shall be symmetrical
with respect to its peak.

The following DPBF beamforming vector is used to feed the 4 subarrays for
polarization A,

$\mathbf{w}_{\mathrm{z,1,A}}=\begin{bmatrix}\;\hphantom{-}0.271+0.227j\\\
\hphantom{-}0.181+0.304j\\\ -0.091+0.342j\\\ -0.199+0.292j\end{bmatrix}.\\\ $
(53)

The corresponding vector in element space is found via

$\mathbf{w}_{\mathrm{z,A}}=\mathbf{w}_{\mathrm{z,1,A}}\otimes[1,1]^{T}\in\mathbb{C}^{M}.\\\
$ (54)

For polarization B, the beamforming vector is defined as

$\mathbf{w}_{\mathrm{z,B}}=\mathbf{w}_{\mathrm{z,A}}^{*}$ (55)

to meet the symmetry requirement for the total power pattern.

In azimuth, a constant-modulus beamforming vector for a protoarray consisting
of two dual polarized elements is found via a bisection search, similar to
what is done in [19]. Requiring that the total power pattern shall be
symmetrical, the resulting vectors are

$\displaystyle\mathbf{w}_{\mathrm{y,A}}$
$\displaystyle=\begin{bmatrix}\;0.458-0.200j\\\ 0.458+0.200j\end{bmatrix},$
(56) $\displaystyle\mathbf{w}_{\mathrm{y,B}}$
$\displaystyle=\mathbf{w}_{\mathrm{y,A}}^{*}.$ (57)

Next, these beamforming vectors are expanded according to Algorithm 1 to
length 4, i.e., $k=1$, and zero padded to the full length of 8. Avoiding
extending the weight to the full length, zero padding instead, is important to
avoid introducing amplitude variations when the excitation matrix for the
entire two-dimensional array is created (see [13] for more details).

The matrices, one per element polarization, for the entire two-dimensional
array are found as

$\displaystyle\mathbf{W}_{\mathrm{A}}$
$\displaystyle=\mathbf{w}_{\mathrm{z,A}}\otimes\mathbf{w}_{\mathrm{y,A}}^{T}-\mathbf{w}_{\mathrm{z,B}}\otimes\mathbf{J}\mathbf{w}_{\mathrm{y,B}}^{H}\in\mathbb{C}^{M\times
N},$ (58) $\displaystyle\mathbf{W}_{\mathrm{B}}$
$\displaystyle=\mathbf{w}_{\mathrm{z,A}}\otimes\mathbf{w}_{\mathrm{y,B}}^{T}+\mathbf{w}_{\mathrm{z,B}}\otimes\mathbf{J}\mathbf{w}_{\mathrm{y,A}}^{H}\in\mathbb{C}^{M\times
N},$ (59)

The weights are furthermore properly normalized with a scaling factor, (52),
to have the correct output power without overloading any PA. In addition, a
tilt is applied according to Table I.

The radiation patterns for the optimized weights are shown in Fig. 6,
alongside the target patterns. Note that the elevation cuts in Fig. 6(a) are
shown after applying the electrical tilt according to Table I. Also note that
the patterns are plotted in terms of equivalent isotropically radiated power
(EIRP). For these plots the beamforming weights are normalized, such that the
output power is 1 W minus taper loss.

Figure 7: Network deployment and UE locations for DPBF.

####  IV-B3 Received signal power

To illustrate the performance gain obtained from the proposed technique, we
simulate a system with a total of 27 cells in an Urban Macro (UMa) environment
[17]. All BSs are equipped with the same antenna array and hence have the same
beam pattern. Users are dropped with uniform distribution in the horizontal
plane, although avoiding the cell hole of 25 m around the BS. 80% of the users
are located indoors and for these the height is given by a uniform
distribution within [0, building height]. Users are served by the cell with
the lowest pathloss. An example of network layout is shown in Fig. 7. The
figure shows the positions of 9 three-sector sites. The blue arrows in the
figure indicate the boresight directions of the antenna arrays, while the
orange dots indicate the UE locations for users connected to a particular
cell.

Received signal power, that is the desired signal total power received by the
UE, is used as a performance metric whose cumulative distributions for the
different beamforming methods are shown in Fig. 8. The figure shows that the
proposed DPBF-based ASI beamformer outperforms the SPBF solution and
approaches the upper bound, the ideal Gaussian beam. The former shows a gain
of 1-1.5 dB in received signal power. This is partly explained by the taper
loss of 1.1 dB for the SPBF solution, as was observed in (47). Furthermore,
the gain comes also partly due to the shape of the resulting power pattern.
All in all, the figure demonstrates the superiority of the proposed DPBF- and
ASI-based beam design.

Figure 8: Performance comparison between SPBF and DPBF.

##  V Conclusion

In this paper, we have proposed the technique of array-size invariant (ASI)
beamforming that allows us to expand an antenna array, while preserving its
total radiation pattern. The ASI technique is based on successive doubling of
a dual-polarized array, exploiting the additional degree of freedom coming
from the two available polarizations. It is based on phase-only beamforming,
and hence guarantees full power utilization due to constant-modulus weights.
The technique is applicable to uniform linear and rectangular arrays and is
characterized with low complexity for beam synthesis. We have propose two
computationally-efficient algorithms for designing broad beams for uniform
arrays of arbitrarily large size. Our simulations the benefits of the proposed
ASI beamforming technique vs. single-polarization beamforming for designing a
cell-specific broad beam for public-channel transmission in a realistic
network deployment.

## Acknowledgment

The authors would like to thank their colleagues at Ericsson Research for
stimulating discussions throughout the course of this work.

## References

  * [1] H. Asplund, D. Astely, P. von Butovitsch, T. Chapman, M. Frenne, F. Ghasemzadeh, M. Hagström, B. Hogan, G. Jöngren, J. Karlsson _et al._ , _Advanced Antenna Systems for 5G Network Deployments: Bridging the Gap Between Theory and Practice_. Academic Press, 2020.
  * [2] D. J. Love and R. W. Heath, “Equal gain transmission in multiple-input multiple-output wireless systems,” _IEEE Trans. Commun._ , vol. 51, no. 7, pp. 1102–1110, 2003.
  * [3] X. Yang, W. Jiang, and B. Vucetic, “A random beamforming technique for omnidirectional coverage in multiple-antenna systems,” _IEEE Trans. Veh. Technol._ , vol. 62, no. 3, pp. 1420–1425, 2012.
  * [4] C. Zhang, Y. Huang, Y. Jing, and L. Yang, “Energy efficient beamforming for massive MIMO public channel,” _IEEE Trans. Veh. Technol._ , vol. 66, no. 11, pp. 10 595–10 600, 2017.
  * [5] V. Raghavan, J. Cezanne, S. Subramanian, A. Sampath, and O. Koymen, “Beamforming tradeoffs for initial UE discovery in millimeter-wave MIMO systems,” _IEEE J. Sel. Top. Signal Process._ , vol. 10, no. 3, pp. 543–559, 2016.
  * [6] K. Xiong, B. Wang, C. Jiang, and K. R. Liu, “A broad beamforming approach for high-mobility communications,” _IEEE Trans. Veh. Technol._ , vol. 66, no. 11, pp. 10 546–10 550, 2017.
  * [7] W. Fan, C. Zhang, and Y. Huang, “Flat beam design for massive MIMO systems via Riemannian optimization,” _IEEE Wireless Commun. Lett._ , vol. 8, no. 1, pp. 301–304, 2018.
  * [8] D. Su, Y. Jiang, and X. Wang, “Semidefinite programming based omnidirectional beamforming for massive mimo,” in _Proc. IEEE WCSP_ , 2017, pp. 1–6.
  * [9] D. Qiao, H. Qian, and G. Y. Li, “Broadbeam for massive MIMO systems,” _IEEE Trans. Signal Process._ , vol. 64, no. 9, pp. 2365–2374, 2016.
  * [10] X. Meng, X. Gao, and X.-G. Xia, “Omnidirectional precoding based transmission in massive MIMO systems,” _IEEE Trans. Commun._ , vol. 64, no. 1, pp. 174–186, 2015.
  * [11] K. H. Sayidmarie and Q. H. Sultan, “Synthesis of wide beam array patterns using random phase weights,” in _Proc. IEEE ICECCPCE_ , 2013, pp. 52–57.
  * [12] Intel Corp., “Codebook with beam broadening,” 3GPP R1-1611929, 2016.
  * [13] S. O. Petersson, “Power-efficient beam pattern synthesis via dual polarization beamforming,” in _Proc. EuCap 2020_ , 2019.
  * [14] C. A. Balanis, _Antenna theory: Analysis and design_. John Wiley & Sons, 2016.
  * [15] Ericsson AB, “On forming wide beams,” 3GPP R1-1700772, 2017.
  * [16] K. Deb, “Multi-objective optimization,” in _Search methodologies_. Springer, 2014, pp. 403–449.
  * [17] 3GPP TR 38.901, “Study on channel model for frequencies from 0.5 to 100 GHz (Release 15),” 3GPP, Tech. Rep., 2018.
  * [18] R. P. Oldenhuis, “Trajectory optimization for a mission to the solar bow shock and minor planets,” M.Sc. thesis, TU Dleft, 2010.
  * [19] M. A. Girnyk and S. O. Petersson, “A simple cell-specific beamforming technique for multi-antenna wireless communications,” in _Proc. IEEE WCNC_ , 2020, pp. 1–4.


# Palindromic Polynomials Over Finite Fields

Geoffrey L. Price  and  Katherine Thompson

###### Abstract.

For any finite field $\mathbb{F}$ and any positive integer $n$ we count the
number of monic polynomials of degree $n$ over $\mathbb{F}$ with nonzero
constant coefficient and a self-reciprocal factor of any specified degree. An
application is given for systems of linear equations over $\mathbb{F}$ of
index $2$.

2010 MSC Classification 11T06, 15A06 Keywords: finite fields, self-reciprocal
polynomials, partially reciprocal polynomials, linear systems

The first author was supported in part by the United States Naval Research
Laboratory, Washington, D.C.

##  1\. Introduction and Statement of Results

Fix a prime $p$. Let $\mathbb{F}_{q}$ be the field of $q=p^{k}$ elements where
$k\in\mathbb{N}$. Let $f$ be a monic polynomial over $\mathbb{F}$ of degree
$n\geq 1$ and with non-zero constant coefficient. The reciprocal of $f$ is the
degree $n$ polynomial $f^{*}$ given by $f^{*}(x)=x^{n}f(1/x)$. We say that a
polynomial $f$ with non-zero constant coefficient is a reciprocal polynomial
(or a self-reciprocal polynomial, or a palindrome polynomial) if $f=f^{*}$.

Given a nonnegative integer $n$ let $z(n)$ denote the number of monic
polynomials of degree $n$ over $\mathbb{F}_{q}$ with nonzero constant
coefficient that have no reciprocal factors other than the constant function
$1$. Our main result is:

######  Theorem 1.

Fix $q=p^{k}$ for $p$ prime and $k\in\mathbb{N}$. Then

  * (i)

$z(0)=1$;

  * (ii)

$z(1)=q-2$;

  * (iii)

for $n\geq 2$, $z(n)=k(q)q^{n-1}+c(q,n)$ where $k(q)=\frac{(q-1)^{2}}{q+1}$
and $c(q,n)=(-1)^{n+1}2(\frac{q-1}{q+1})$.

Remark: In Theorem $4.4$ of [6] (see also [7]) the first author proved Theorem
1 for the case $q=2$. This result was used in the classification (up to
conjugacy) of the binary shifts on the hyperfinite $II_{1}$ factor.

##  2\. Proof

######  Lemma 2.

For $n\in\mathbb{N}$ let $t(n)$ be the number of monic polynomials of degree
$n$ over $\mathbb{F}_{q}$ with non-zero constant coefficient. Then
$t(n)=(q-1)q^{n-1}$.

###### Proof.

There are $q-1$ choices for the constant term and $q$ choices for each of the
degree $d$ terms, for $1\leq d\leq n-1$. ∎

We will use the notation $pr(n)$ to denote the number of partially reciprocal
polynomials of degree $n$, i.e. the monic polynomials of degree $n$ with
nonzero constant term which have a reciprocal factor of degree at least $2$.

######  Lemma 3.

For $n\geq 2$, $t(n)-pr(n)=z(n)+z(n-1)$.

###### Proof.

Clearly $t(n)-pr(n)$ is the number of monic polynomials with nonzero constant
coefficient which have a reciprocal factor of degree at most $1$. Note that
such a polynomial $f$ either has no palindrome factors or has $x+1$ as its
only palindrome factor. If $x+1$ is the only palindrome factor of $f$, then
$g(x)=\frac{1}{x+1}f(x)$ is a polynomial of degree $n-1$ with no palindrome
factors. Conversely, if $g$ is a monic polynomial over $\mathbb{F}_{q}$ of
degree $n-1$ with no palindrome factors, then $f(x)=(x+1)g(x)$ is a polynomial
with $x+1$ as its only palindrome factor, so there is a one-to-one
correspondence between polynomials of degree $n-1$ with no palindrome factors
and polynomials of degree $n$ with just a single linear palindrome factor. The
result follows. ∎

######  Lemma 4.

For each $n\in\mathbb{N}$ let s(n) be the number of monic reciprocal
polynomials. For any $j\in\mathbb{N}\cup\\{0\\}$, $s(2j)=q^{j}=s(2j+1)$.

###### Proof.

Direct, and left to the reader. ∎

We now proceed with the proof of Theorem 1.

###### Proof.

  * (i)

The only monic constant is $f(x)=1$, so $z(0)=1$ trivially.

  * (ii)

Let $f(x)=x+a$ with $a\in\mathbb{F}_{q}$. We exclude $a=0,1$, leaving $q-2$
polynomials. So $z(1)=q-2$.

  * (iii)

We proceed by induction on $n\geq 2$.

For $n=2$, we have $pr(2)=z(0)s(2)=1\cdot q=q$, so by Lemma 3,
$t(2)-pr(2)=(q-1)q-q=q^{2}-2q$. So then, since $z(1)=q-2$ and
$z(1)+z(2)=t(2)-pr(2)$, we have

$\displaystyle z(2)$ $\displaystyle=$ $\displaystyle q^{2}-2q-(q-2)$
$\displaystyle=$ $\displaystyle(q-1)(q-2)$ $\displaystyle=$
$\displaystyle\frac{(q-1)(q^{2}-q-2)}{q+1}$ $\displaystyle=$
$\displaystyle\frac{(q-1)[q(q-1)-2]}{q+1}$ $\displaystyle=$
$\displaystyle\dfrac{(q-1)^{2}}{q+1}\cdot
q^{2-1}+(-1)^{2+1}2\left(\dfrac{q-1}{q+1}\right)$ $\displaystyle=$
$\displaystyle k(q)q^{2-1}+c(q,2),$

which completes the base case.

For the inductive step, we first suppose $n$ is odd, and write $n=2m+1$ for
$m\in\mathbb{N}$, By assumption $z(2m)=k(q)q^{2m-1}+c(q,2m)$. Then

$pr(n)=pr(2m+1)=s(2m+1)z(0)+s(2m)z(1)+\cdots+s(2)z(2m-1)=I+II,$

where

$\displaystyle I$ $\displaystyle=$
$\displaystyle\sum_{\ell=0}^{m-1}z(2\ell)s(2(m-\ell)+1)$ $\displaystyle=$
$\displaystyle z(0)s(2m+1)+\sum_{\ell=1}^{m-1}z(2\ell)s(2(m-\ell)+1)$
$\displaystyle=$ $\displaystyle 1\cdot
q^{m}+\sum_{\ell=1}^{m-1}\left(k(q)q^{2\ell-1}-2\left(\frac{q-1}{q+1}\right)\right)q^{m-\ell}$
$\displaystyle=$ $\displaystyle
q^{m}+\sum_{\ell=1}^{m-1}\left(k(q)q^{m+\ell-1}-2\left(\dfrac{q-1}{q+1}\right)p^{m-\ell}\right)$
$\displaystyle=$ $\displaystyle
q^{m}+k(q)(q^{m}+\cdots+q^{2m-2})-2\left(\dfrac{q-1}{q+1}\right)(q^{m-1}+\cdots+q)$
$\displaystyle=$ $\displaystyle
q^{m}+k(q)q^{m}\left(\frac{q^{m-1}-1}{q-1}\right)-2\left(\dfrac{q-1}{q+1}\right)q(\frac{q^{m-1}-1}{q-1})$
$\displaystyle=$ $\displaystyle
q^{m}+k(q)\left(\frac{q^{2m-1}-q^{m}}{q-1}\right)-2\left(\dfrac{q-1}{q+1}\right)\left(\frac{q^{m}-q}{q-1}\right),$

and

$\displaystyle II$ $\displaystyle=$ $\displaystyle
s(2m)z(1)+s(2m-2)z(3)+\cdots+s(2)z(2m-1)$ $\displaystyle=$ $\displaystyle
s(2m)z(1)+\sum_{\ell=0}^{m-2}z(2\ell+3)s(2(m-\ell-1))$ $\displaystyle=$
$\displaystyle(q-2)q^{m}+\sum_{\ell=0}^{m-2}\left(k(q)q^{2\ell+2}+2\left(\dfrac{q-1}{q+1}\right)\right)q^{m-\ell-1}$
$\displaystyle=$
$\displaystyle(q-2)q^{m}+k(q)(q^{m+1}+\cdots+q^{2m-1})+2\left(\dfrac{q-1}{q+1}\right)(q^{m-1}+\cdots+q)$
$\displaystyle=$
$\displaystyle(q-2)q^{m}+k(q)q^{m+1}\left(\frac{q^{m-1}-1}{q-1}\right)+2\left(\dfrac{q-1}{q+1}\right)q\left(\frac{q^{m-1}-1}{q-1}\right)$
$\displaystyle=$
$\displaystyle(q-2)q^{m}+k(q)\left(\frac{q^{2m}-q^{m+1}}{q-1}\right)+2\left(\dfrac{q-1}{q+1}\right)\left(\frac{q^{m}-q}{q-1}\right).$

Then

$\displaystyle pr(2m+1)$ $\displaystyle=$ $\displaystyle I+II$
$\displaystyle=$ $\displaystyle
q^{m}+k(q)\left(\frac{q^{2m-1}-q^{m}}{q-1}\right)-2\left(\dfrac{q-1}{q+1}\right)\left(\frac{q^{m}-q}{q-1}\right)+$
$\displaystyle(q-2)q^{m}+k(q)\left(\frac{q^{2m}-q^{m+1}}{q-1}\right)+2\left(\dfrac{q-1}{q+1}\right)\left(\frac{q^{m}-q}{q-1}\right)$
$\displaystyle=$ $\displaystyle
q^{m}+k(q)\left(\frac{q^{2m-1}-q^{m}}{q-1}\right)+(q-2)q^{m}+k(q)\left(\frac{q^{2m}-q^{m+1}}{q-1}\right)$
$\displaystyle=$ $\displaystyle
q^{m}+\left(\frac{q-1}{q+1}\right)(q^{2m-1}-q^{m})+(q-2)q^{m}+\left(\frac{q-1}{q+1}\right)(q^{2m}-q^{m+1})$
$\displaystyle=$
$\displaystyle(q-1)q^{m}+\left(\dfrac{q-1}{q+1}\right)(q^{2m-1}-q^{m}+q^{2m}-q^{m+1})$
$\displaystyle=$
$\displaystyle\dfrac{q-1}{q+1}(q^{m+1}+q^{m})+\dfrac{q-1}{q+1}(q^{2m-1}-q^{m}+q^{2m}-q^{m+1})$
$\displaystyle=$ $\displaystyle(q-1)q^{2m-1}.$

But now by Lemma 3

$\displaystyle z(2m+1)$ $\displaystyle=$ $\displaystyle
t(2m+1)-pr(2m+1)-z(2m)$ $\displaystyle=$
$\displaystyle(q-1)q^{2m}-(q-1)q^{2m-1}-\left(\dfrac{(q-1)^{2}}{q+1}\cdot
q^{2m-1}-2\cdot\dfrac{q-1}{q+1}\right)$ $\displaystyle=$
$\displaystyle(q-1)q^{2m-1}\left(q-1-\frac{q-1}{q+1}\right)+2\left(\frac{q-1}{q+1}\right)$
$\displaystyle=$
$\displaystyle(q-1)^{2}q^{2m-1}\left(1-\frac{1}{q+1}\right)+2\left(\frac{q-1}{q+1}\right)$
$\displaystyle=$ $\displaystyle k(q)q^{2m}+c(q,2m+1).$

We now suppose that $n$ is even, and write $n=2m$ where $m\in\mathbb{N}$.
Assume $z(\ell)=k(q)q^{\ell-1}+c(q,n)$ for $\ell=2,\dots,2m-1$. We have

$pr(2m)=\sum_{k=0}^{2m-2}z(k)s(2m-k)=I+II,$

where

$\displaystyle I$ $\displaystyle=$
$\displaystyle\sum_{\ell=0}^{m-1}z(2\ell)s(2(m-\ell))$ $\displaystyle=$
$\displaystyle z(0)s(2m)+\sum_{\ell=1}^{m-1}z(2\ell)s(2(m-\ell))$
$\displaystyle=$ $\displaystyle 1\cdot
q^{m}+\sum_{\ell=1}^{m-1}\left(k(q)\cdot
q^{2\ell-1}-2\left(\dfrac{q-1}{q+1}\right)\right)q^{m-\ell}$ $\displaystyle=$
$\displaystyle
q^{m}+\sum_{\ell=1}^{m-1}\left(k(q)q^{m+\ell-1}-2\left(\dfrac{q-1}{q+1}\right)q^{m-\ell}\right)$
$\displaystyle=$ $\displaystyle
q^{m}+k(q)q^{m}(1+\cdots+q^{m-2})-2\left(\dfrac{q-1}{q+1}\right)q(1+\cdots+q^{m-2})$
$\displaystyle=$ $\displaystyle
q^{m}+k(q)q^{m}\left(\frac{q^{m-1}-1}{q-1}\right)-2\left(\dfrac{q-1}{q+1}\right)q\left(\frac{q^{m-1}-1}{q-1}\right)$
$\displaystyle=$ $\displaystyle
q^{m}+k(q)\left(\frac{q^{2m-1}-q^{m}}{q-1}\right)-2\left(\dfrac{q-1}{q+1}\right)\left(\frac{q^{m}-q}{q-1}\right),$

and

$\displaystyle II$ $\displaystyle=$
$\displaystyle\sum_{\ell=1}^{m-1}z(2(\ell-1)+1)s(2(m-\ell)+1)$
$\displaystyle=$ $\displaystyle
z(1)s(2(m-1)+1)+\sum_{\ell=2}^{m-1}z(2(\ell-1)+1)s(2(m-\ell)+1)$
$\displaystyle=$
$\displaystyle(q-2)q^{m-1}+\sum_{\ell=2}^{m-1}\left(k(q)q^{2\ell-2}+2\left(\dfrac{q-1}{q+1}\right)\right)q^{m-\ell}$
$\displaystyle=$
$\displaystyle(q-2)q^{m-1}+k(q)(q^{m}+\cdots+q^{2m-3})+2\left(\dfrac{q-1}{q+1}\right)(q^{m-2}+\cdots+q)$
$\displaystyle=$
$\displaystyle(q-2)q^{m-1}+k(q)q^{m}(1+\cdots+q^{m-3})+2\left(\dfrac{q-1}{q+1}\right)q(1+\cdots+q^{m-3})$
$\displaystyle=$
$\displaystyle(q-2)q^{m-1}+k(q)q^{m}(\frac{q^{m-2}-1}{q-1})+2\left(\dfrac{q-1}{q+1}\right)q\left(\frac{q^{m-2}-1}{q-1}\right)$
$\displaystyle=$
$\displaystyle(q-2)q^{m-1}+k(q)(\frac{q^{2m-2}-q^{m}}{q-1})+2\left(\dfrac{q-1}{q+1}\right)\left(\frac{q^{m-1}-q}{q-1}\right).$

Then

$\displaystyle pr(2m)$ $\displaystyle=$ $\displaystyle I+II$ $\displaystyle=$
$\displaystyle
q^{m}+k(q)\left(\frac{q^{2m-1}-q^{m}}{q-1}\right)-2\left(\dfrac{q-1}{q+1}\right)\left(\frac{q^{m}-q}{q-1}\right)+(q-2)q^{m-1}+k(q)\left(\frac{q^{2m-2}-q^{m}}{q-1}\right)+2\left(\dfrac{q-1}{q+1}\right)\left(\frac{q^{m-1}-q}{q-1}\right)$
$\displaystyle=$ $\displaystyle
q^{m}+(q-2)q^{m-1}+k(q)\left(\dfrac{q^{2m-1}+q^{2m-2}-2q^{m}}{q-1}\right)-2\left(\dfrac{q-1}{q+1}\right)\left(\dfrac{q^{m}-q^{m-1}}{q-1}\right)$
$\displaystyle=$ $\displaystyle
2(q^{m}-q^{m-1})+\left(\dfrac{q-1}{q+1}\right)(q^{2m-1}+q^{2m-2}-2q^{m})-\dfrac{2(q^{m}-q^{m-1})}{q+1}$
$\displaystyle=$
$\displaystyle\dfrac{2(q^{m}-q^{m-1})(q+1)}{q+1}-\dfrac{2(q^{m}-q^{m-1})}{q+1}+\dfrac{q^{2m}-2q^{m+1}-q^{2m-2}+2q^{m}}{q+1}$
$\displaystyle=$
$\displaystyle\dfrac{2q^{m+1}-2q^{m}+q^{2m}-2q^{m+1}-q^{2m-2}+2q^{m}}{q+1}$
$\displaystyle=$ $\displaystyle q^{2m-2}(q-1).$

But again by Lemma 3 we have

$\displaystyle z(2m)$ $\displaystyle=$ $\displaystyle t(2m)-pr(2m)-z(2m-1)$
$\displaystyle=$
$\displaystyle(q-1)q^{2m-1}-(q-1)q^{2m-2}-\left(k(2m-1)q^{2m-2}+2\left(\dfrac{q-1}{q+1}\right)\right)$
$\displaystyle=$
$\displaystyle(q-1)^{2}q^{2m-2}-\left(\dfrac{(q-1)^{2}}{q+1}\right)q^{2m-2}-2\left(\dfrac{q-1}{q+1}\right)$
$\displaystyle=$
$\displaystyle\left(\dfrac{(q-1)^{2}}{q+1}\right)q^{2m-2}-2\left(\dfrac{q-1}{q+1}\right)$
$\displaystyle=$ $\displaystyle k(q)q^{2m-1}+c(q,2m).$

∎

######  Corollary 5.

Let $j$ and $n$ be positive integers with $1\leq j\leq n$. Let $p(n,j)$ be the
number of monic polynomials $f$ over $\mathbb{F}_{q}$ with nonzero constant
coefficient such that $f$ has a self-reciprocal factor of degree $j$ and no
higher. Then $p(n,j)=z(n-j)s(j)$.

##  3\. Application to Systems of Linear Equations

As mentioned above, our counting result was established in [6] for
$\mathbb{F}_{2}$. Here $z(0)=1,z(1)=z(2)=0$ and for $n\geq 3$,
$z(n)=\frac{1}{3}(2^{n-1})+\frac{2}{3}$ (for $n$ odd) and
$\frac{1}{3}(2^{n-1})-\frac{2}{3}$ (for $n$ even). We present an application
of these results to a family of linear systems of equations over
$\mathbb{F}_{2}$. This application is related to the classification problem in
[6] mentioned in Section 1 above.

######  Definition 6.

Let $(a)=(\dots,a_{-2},a_{-1},a_{0},a_{1},a_{2},\dots)$ be a sequence in
$\mathbb{F}_{2}$ with $a_{0}=0$ and with $a_{j}=a_{-j}$. We shall say that
$(a)$ has index $2$ if one of the following holds:

  1. (1)

$a_{-1}=a_{1}=1$, and $a_{j}=0$ otherwise.

  2. (2)

$a_{0}=0$ and $a_{j}=1$ otherwise.

  3. (3)

For some $m\geq 2$ there is a vector $\vec{k}=[k_{0},k_{1},\dots,k_{m}]$, with
$k_{0}=k_{m}=1$ satisfying the following infinite linear system of equations:

$\displaystyle 1=$ $\displaystyle
k_{0}a_{1}+k_{1}a_{0}+k_{2}a_{1}+\cdots+k_{m}a_{m-1}$ $\displaystyle 0=$
$\displaystyle k_{0}a_{2}+k_{1}a_{1}+k_{2}a_{0}+\cdots+k_{m}a_{m-2}$
$\displaystyle 0=$ $\displaystyle
k_{0}a_{3}+k_{1}a_{2}+k_{2}a_{1}+\cdots+k_{m}a_{m-3}$ $\displaystyle 0=$
$\displaystyle k_{0}a_{4}+k_{1}a_{3}+k_{2}a_{2}+\cdots+k_{m}a_{m-4}$
$\displaystyle\vdots$

Note that $(1)$ may be rewritten (with $\vec{k}=[k_{0}]=[1]$ and
$(a)=(0100\cdots)$ as

$\displaystyle 1=$ $\displaystyle k_{0}a_{1}$ $\displaystyle 0=$
$\displaystyle k_{0}a_{2}$ $\displaystyle 0=$ $\displaystyle k_{0}a_{3}$
$\displaystyle 0=$ $\displaystyle k_{0}a_{4}$ $\displaystyle\vdots$

and $(2)$ may be rewritten (with $\vec{c}=[k_{0},k_{1}]=[1,1]$ and
$(a)=(0111\cdots)$ as

$\displaystyle 1=$ $\displaystyle k_{0}a_{1}+k_{1}a_{0}$ $\displaystyle 0=$
$\displaystyle k_{0}a_{2}+k_{1}a_{1}$ $\displaystyle 0=$ $\displaystyle
k_{0}a_{3}+k_{1}a_{2}$ $\displaystyle 0=$ $\displaystyle
k_{0}a_{4}+k_{1}a_{3}$ $\displaystyle\vdots$

One can show that the sequence
$a_{m-1},a_{m-2},\dots,a_{1},a_{0},a_{1},a_{2},\dots$ in (3) is not periodic,
whereas
$a_{m-2},a_{m-3},\dots,a_{1},a_{0},a_{1},a_{2},\dots$ is periodic, see
[5][Theorem 6.11]. From the proof of Theorem 3.3 of [6] it follows that a
vector $\vec{k}=[k_{0},k_{1},\dots,k_{m}]$ with $m\geq 2$ satisfies a system
of the form $(3)$ for at most one sequence $(a)$. From the proof of Lemma 3.1
of [6], a necessary condition for a vector $\vec{k}$ to satisfy $(3)$ is that
the polynomial $k_{0}+k_{1}x+\cdots+k_{m}x^{m}$ either has no palindrome
factors or the single palindrome factor $1+x$ over $\mathbb{F}_{2}$. There are
exactly $z(m)+z(m-1)$ such polynomials, with $z(m)$ polynomials of degree $m$
and constant coefficient $1$ having no palindrome factors, and $z(m-1)$ such
polynomials of degree $m$ having $1+x$ as its only palindrome factor.
Therefore there are
$z(m)+z(m-1)=\frac{1}{3}(2^{m-1})+\frac{1}{3}(2^{m-2})=2^{m-2}$ such
polynomials. By the proof of Theorem 3.4 of [6] there are at least $2^{m-2}$
vectors $\vec{k}=[k_{0},k_{1},\dots,k_{m}]$ satisfying (3). Therefore we have
the following result (cf. [6][Theorem 5.1]).

######  Theorem 7.

For $m\geq 3$ there are exactly $2^{m-2}$ linear systems of index $2$
satisfying $(3)$ over $\mathbb{F}_{2}$.

######  Remark.

Note that every degree $2$ polynomial with constant coefficient $1$ is a
palindrome so that there are no systems (3) with $m=2$.

######  Remark.

There is a notion of a linear system of equations over $\mathbb{F}_{2}$ of
index $j$ with $j>2$, but the analysis is considerably more complicated, as
there is no longer a one-to-one correspondence between vectors $\vec{k}$ and
sequences $(a)$ (see [7] for related results).

## References

  * [1] Ahmadi, O., Generalization of a theorem of Carlitz, Finite Fields and Their Applications, September 2011, 17(5), 473-480.
  * [2] Ahmadi, O., Vega, G., On the parity of the number of irreducible factors of self-reciprocal polynomials over finite fields, Finite Fields and Their Applications, January 2008, 14(1):124-131
  * [3] Carlitz, L., Some theorems on irreducible reciprocal polynomials over a finite field, Journal für die Reine und Angewandte Mathematik, 227:212-220, 1967
  * [4] Chebolu, S., Minac, J., Counting irreducible polynomials over finite fields using the inclusion-exclusion principle, Math. Mag., Vol. 84, No. 5, Dec. 2011, 369-371.
  * [5] Lidl, R., Niederreiter, H., Finite Fields, Volume 20, Part 1, Cambridge University Press, 1997.
  * [6] Price, G.L., On the classification of binary shifts of minimal commutant index, Proc. Natl. Acad. Sci., Vol. 96, August 1999, 8839-8844.
  * [7] Price, G.L., On the classification of binary shifts of finite commutant index, Proc. Natl. Acad. Sci., Vol. 96, December 1999, 14700-14705.
  * [8] SageMath, the Sage Mathematics Software System (Version 6.10), The Sage Developers, 2015, http://www.sagemath.org.

G.L. Price, Department of Mathematics, United States Naval Academy, Annapolis,
MD., 21402

E-mail address, G.L. Price<EMAIL_ADDRESS>
K. Thompson, Department of Mathematics, United States Naval Academy,
Annapolis, MD., 21402

E-mail address, K. Thompson<EMAIL_ADDRESS>