# On the State Estimation Error of “Beam-Pointing” Channels: The Binary Case

Siyao Li  Communications and Information Theory Group (CommIT)
Technische Universität Berlin
Berlin, Germany
<EMAIL_ADDRESS>Giuseppe Caire  Communications and Information Theory
Group (CommIT)
Technische Universität Berlin
Berlin, Germany
<EMAIL_ADDRESS>
###### Abstract

Sensing capabilities as an integral part of the network have been identified
as a novel feature of sixth-generation (6G) wireless networks. As a key
driver, millimeter-wave (mmWave) communication largely boosts speed,
capacities, and connectivity. In order to maximize the potential of mmWave
communication, precise and fast beam acquisition (BA) is crucial, since it
compensates for a high pathloss and provides a large beamforming gain.
Practically, the angle-of-departure (AoD) remains almost constant over
numerous consecutive time slots, the backscatter signal experiences some
delay, and the hardware is restricted under the peak power constraint. This
work captures these main features by a simple binary beam-pointing (BBP)
channel model with in-block memory (iBM) [1], peak cost constraint, and one
unit-delayed feedback. In particular, we focus on the sensing capabilities of
such a model and characterize the performance of the BA process in terms of
the Hamming distortion of the estimated channel state. We encode the position
of the AoD and derive the minimum distortion of the BBP channel under the peak
cost constraint with no communication constraint. Our previous work [2]
proposed a joint communication and sensing (JCAS) algorithm, which achieves
the capacity of the same channel model. Herein, we show that by employing this
JCAS transmission strategy, optimal data communication and channel estimation
can be accomplished simultaneously. This yields the complete characterization
of the capacity-distortion tradeoff for this model.

##  I Introduction

With the evolution of 4G to 5G, the spectrum allocations have expanded towards
millimeter-wave (mmWave) bands [3]. This trend will continue and communication
spectra in the sub-Terahertz region will likely be available as some of the
frequency bands for 6G deployments. With the introduction of these new
frequencies, the potential for very accurate sensing based on radar-like
technology arises [4, 5, 6].That is, reflections of transmitted signals are
received in the network and processed to yield spatial knowledge of the
physical surroundings. At these frequencies, the communication network must
employ beamforming of the transmitted signals to concentrate and direct the
signal energy to a specific geographical area where the intended receiver is
located [7], which is strongly affected by the initial beam acquisition (BA)
phase [8]. In general, standard BA schemes are based on some “beam-sweeping”
phase, i.e., the base station (BS) sends pilot signals in all the possible
transmission directions at regular intervals, allowing the user equipment (UE)
to identify the best beam index and feed this back via some hand-shaking
protocol. Works have studied the BA problem in various ways (e.g., see [9, 10,
11, 12, 13, 14, 15] and references therein). However, transmission efficiency
is not fully realized in these works, as they isolate the BA phase and the
data communication phase. This separation is known to be sub-optimal from the
information-theoretic perspective [16].

For future sensing, the main advantage of the communication network is that
most of the infrastructure is already in place with transmitter/receiver
(Tx/Rx) nodes. This provides full area coverage as well as a good
interconnection between nodes. Hence, the sensing can be provided almost ‘for
free’. To achieve the full potential of mmWave communication, numerous recent
works exploit “joint communication and sensing’ (JCAS) (see e.g. [17, 18, 19,
20] and references therein), where communication can take place while the
angle-of-departure (AoD) is being estimated via the backscatter signal.

From physical considerations, it is clear that the AoD remains almost constant
over a large number of consecutive time slots, which presents a state-
dependent channel with memory. Additionally, the backscatter signal can be
modeled as causal feedback. In this work, we investigate this scenario with
JCAS from an information-theoretic viewpoint. Considering channels with in-
block memory (iBM) [1], i.e., the state remains constant for blocks of $L$
time slots, and changes in an independent and identically distributed (i.i.d.)
fashion from block to block, the state estimation error is very hard to
evaluate since it requires the optimization over length-$L$ sequences of
conditional input distributions.

#### Contribution

In this paper, we consider a binary beam-pointing (BBP) channel with iBM and
one-unit delayed feedback under the peak cost constraint. In our previous work
[2], we characterized the capacity of this BBP channel. Herein, we are
interested in the ability of the BS to “locate” the target AoD, quantified by
the distortion error achieved by the BS state estimator at the end of each
block. We refer to “distortion” as the (average) error with which the
transmitter is able to determine the channel state (i.e., the AoD of the
receiver) at the end of each block, and characterize the minimum distortion
under the peak cost constraint. It is interesting to see that this minimum
distortion can be obtained by deploying the capacity-achieving transmission
strategy in [2]. We, therefore, obtain a complete capacity-distortion region
of the considered channel model, revealing that for this model the tradeoff is
“trivial” in the sense that optimal communication rate and minimum state
estimation distortion can be achieved at the same time. This corroborates the
general intuition that JCAS yields excellent sensing capabilities without
compromising capacity.

#### Notations

For an integer $n$, we let $[n]=\\{1,\cdots,n\\}$ and
$[n_{1}:n_{2}]=\\{n_{1},\cdots,n_{2}\\}$ for some integers $n_{1}<n_{2}$.
$\underline{X}$ denotes a vector and
$\underline{X}^{n}=[\underline{X}_{1},\cdots,\underline{X}_{n}]$ denotes a
sequence of vectors. Let $[x]^{+}=\max(0,x)$, and $y^{i-1}1$ denote the
realization of the sequence $Y^{i}$ where $Y^{i-1}=y^{i-1}$ and $Y_{i}=1$. Let
$\beta_{k}^{i}$ denote the binary sequence with length $i$ and the first one
element appearing at the $k$-index (i.e.,
$\beta_{2}^{i}=\\{01\underbrace{\star\cdots\star}_{i-2}\\}$ where $\star$ can
be either 0 or 1). $\mathbbm{1}{\\{\cdot\\}}$ denotes an indicator function.
$|\mathcal{A}|$ represents the cardinality of a set $\mathcal{A}$.

##  II System Model

We consider a BBP channel model with iBM [1] and block length $L$. There are
$n$ total transmission time in channel uses where $n=\ell L$ and $\ell$ is the
number of blocks. Note that when $L=1$, the channel becomes the memoryless
channel with independent states. The channel state
${\underline{S}}\in\\{0,1\\}^{M}$ is an $M$-dimensional “one-hot” binary
vector where the single “1” appearing at index $m$ indicates the (unknown)
target receiver AoD, among $M$ possible quantized angles. This index $m$ is a
random variable uniformly distributed over $[M]$ and is referred to as the
transmission direction, i.e., the quantized AoD of the UE with respect to the
BS array. The state remains constant for blocks of $L$ channel uses and the
transmitter (BS) receives binary causal noiseless feedback. This channel state
information is assumed to be perfectly known at the receiver (CSIR) but
unknown at the transmitter. The transmitter decides the transmission direction
estimation $\hat{S}$ (i.e., a one-hot vector) upon the channel input and
feedback at the end of each block. Furthermore,
${\underline{S}}\in\mathcal{S}$ is i) independent of the channel input, ii)
remains constant for an interval of $L$ channel uses, and iii) i.i.d.
according to $P_{\underline{S}}$ across the blocks. The channel input
${\underline{X}}_{i,j}\in\mathcal{X}:=\\{0,1\\}^{M}$ is also an
$M$-dimensional binary vector with a peak Hamming weight cost constraint,
modeling the fact that sending in multiple directions costs transmit power.
The channel output $Y_{i,j}\in\mathcal{Y}:=\\{0,1\\}$ at channel use $j$ of
block $i$

$\displaystyle Y_{i,j}={\underline{S}}_{i}^{T}{\underline{X}}_{i,j}$ (1)

is binary, given by the inner product of the state and input vectors. The
causal feedback is noiseless, i.e., it coincides with the output from the
previous channel use. Notice that $Y_{i,j}=1$ if the single “1” in $S_{i}$
coincides with a “1” in $X_{i,j}$ and zero otherwise. The joint probability
distribution of the considered model is

$\displaystyle
P_{W{\underline{X}}^{n}{\underline{S}}^{\ell}Y^{n}}(w,{\underline{x}}^{n},{\underline{s}}^{\ell},y^{n})=P_{W}(w)$
$\displaystyle\times\prod_{i=1}^{\ell}\left(P_{\underline{S}}({\underline{s}}_{i})\prod_{j=1}^{L}P_{Y|{\underline{X}\underline{S}}}(y_{i,j}|{\underline{x}}_{i,j}{\underline{s}}_{i})P({\underline{x}}_{i,j}|w,{y}_{i}^{j-1})\right)$
(2)

where we denote $y_{i}^{j-1}=[y_{i,1},\cdots,y_{i,j-1}]$.

######  Definition 1.

The estimate of the state sequence $\mathcal{S}^{\ell}$ in the presence of the
input $X^{n}$ and feedback $Y^{n}$ is defined as where
$q:\mathcal{X}^{n}\times\mathcal{Y}^{n}\to\hat{\mathcal{S}}^{\ell},$ is a
state estimation function and $\hat{\mathcal{S}}$ is the reproduction
alphabet. The average per-block distortion is defined as

$\displaystyle\Delta^{(\ell)}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\frac{1}{\ell}\sum_{i=1}^{\ell}\mathbb{E}[d(\underline{S}_{i},\hat{\underline{S}}_{i})],$
(3)

where $\hat{\underline{S}}_{i}$ is the $i$-th component of
$\hat{\underline{S}}^{\ell}$ in (LABEL:eq:hat-S), and
$d:\mathcal{S}\times\hat{\mathcal{S}}\to\mathbb{R}_{+}$ is a state estimation
error measure with
$\max_{({\underline{s}},\hat{\underline{s}})\in\mathcal{S}\times\hat{\mathcal{S}}}d({\underline{s}},\hat{\underline{s}})<\infty.$

######  Lemma 1.

Define the function

$\displaystyle\hat{\underline{s}}^{\star}(\underline{x}_{i}^{L},y_{i}^{L})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\arg\min_{\underline{s}_{i}^{\prime}\in\hat{\mathcal{S}}}\sum_{\underline{s}_{i}\in\mathcal{S}}P_{\underline{S}_{i}|\underline{X}_{i}^{L}Y_{i}^{L}}(\underline{s}_{i}|\underline{x}_{i}^{L},y_{i}^{L})d(\underline{s}_{i},\underline{s}_{i}^{\prime})$

where

$\displaystyle
P_{\underline{S}_{i}|\underline{X}_{i}^{L}Y_{i}^{L}}(\underline{s}_{i}|\underline{x}_{i}^{L},y_{i}^{L})=\frac{P_{\underline{S}_{i}}(\underline{s}_{i})P_{Y_{i}^{L}|\underline{S}_{i},\underline{X}_{i}^{L}}(y_{i}^{L}|\underline{s}_{i},\underline{x}_{i}^{L})}{\sum_{\underline{s}_{i}\in\mathcal{S}}P_{\underline{S}_{i}}(\underline{s}_{i})P_{Y_{i}^{L}|\underline{S}_{i},\underline{X}_{i}^{L}}(y_{i}^{L}|\underline{s}_{i},\underline{x}_{i}^{L})},$

and
$P_{Y_{i}^{L}|\underline{S}_{i},\underline{X}_{i}^{L}}(y_{i}^{L}|\underline{s}_{i},\underline{x}_{i}^{L})=\prod_{j=1}^{L}P_{Y_{i}|\underline{S}_{i},\underline{X}_{i}}(y_{i,j}|\underline{s}_{i},\underline{x}_{i,j})$.
Irrespective of the choice of encoding and decoding functions, distortion
$\Delta^{(\ell)}$ in (3) is minimized by the estimator

$\displaystyle
q^{\star}(\underline{x}^{n},y^{n})=(\hat{\underline{s}}^{\star}(\underline{x}_{1}^{L},y_{1}^{L}),\hat{\underline{s}}^{\star}(\underline{x}_{2}^{L},y_{2}^{L})\cdots,\hat{\underline{s}}^{\star}(\underline{x}_{\ell}^{L},y_{\ell}^{L}))$

where $\hat{\underline{s}}^{\star}(\underline{x}_{i}^{L},y_{i}^{L})$ is the
state estimation of the $i$-th block, $i\in[\ell]$.

###### Proof:

By (LABEL:eq:hat-S), we have

$\displaystyle\mathbb{E}[d(\underline{S}_{i},\hat{\underline{S}}_{i})]$
$\displaystyle=\mathbb{E}_{\underline{X}^{n},Y^{n}}\left[\mathbb{E}[d(\underline{S}_{i},\hat{\underline{S}}_{i})|\underline{X}^{n},Y^{n}]\right]$
$\displaystyle=\sum_{\underline{x}^{n},y^{n}}P_{\underline{X}^{n},Y^{n}}(\underline{x}^{n},y^{n})\sum_{\hat{\underline{s}}_{i}\in\mathcal{S}}P_{\hat{\underline{S}}_{i}|\underline{X}^{n},Y^{n}}(\hat{\underline{s}}|\underline{x}^{n},y^{n})$
$\displaystyle\times\sum_{\underline{s}_{i}\in\mathcal{S}}P_{{\underline{S}}_{i}|\underline{X}_{i}^{L},Y_{i}^{L}}({\underline{s}}_{i}|\underline{x}_{i}^{L},y_{i}^{L})d(\underline{s}_{i},\hat{\underline{s}}_{i})$
(4a)
$\displaystyle\geq\sum_{\underline{x}^{n},y^{n}}P_{\underline{X}^{n},Y^{n}}(\underline{x}^{n},y^{n})$
$\displaystyle\times\min_{\hat{\underline{s}}_{i}\in\mathcal{S}}\sum_{\underline{s}_{i}\in\mathcal{S}}P_{{\underline{S}}_{i}|\underline{X}_{i}^{L},Y_{i}^{L}}({\underline{s}}_{i}|\underline{x}_{i}^{L},y_{i}^{L})d(\underline{s}_{i},\hat{\underline{s}}_{i})$
$\displaystyle=\mathbb{E}[d(\underline{S}_{i},\hat{\underline{s}}^{\star}(\underline{X}_{i}^{L},Y_{i}^{L}))],$
(4b)

where (4a) holds by the Markov chain

$\displaystyle(\underline{X}_{1}^{L},\cdots,\underline{X}_{i-1}^{L},Y_{1}^{L},\cdots,Y_{i-1}^{L},\hat{\underline{S}}_{i})-(\underline{X}_{i}^{L},Y_{i}^{L})-\underline{S}_{i}.$

Summing over all $i=1,\cdots,\ell$, we have

$\displaystyle\Delta^{(\ell)}$
$\displaystyle=\frac{1}{\ell}\sum_{i=1}^{\ell}\mathbb{E}[d(\underline{S}_{i},\hat{\underline{S}}_{i})]\geq\frac{1}{\ell}\sum_{i=1}^{\ell}\mathbb{E}[d(\underline{S}_{i},\hat{\underline{s}}^{\star}(\underline{X}_{i}^{L},Y_{i}^{L}))],$

which leads to the desired conclusion. ∎

Lemma 1 allows us to define the conditional estimation cost

$\displaystyle
c(\underline{x}_{i}^{L})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\mathbb{E}[d(\underline{S}_{i},\hat{\underline{s}}^{\star}(\underline{X}_{i}^{L},Y_{i}^{L}))|\underline{X}_{i}^{L}=\underline{x}_{i}^{L}],$

such that, for any encoding function

$\displaystyle\Delta^{(\ell)}=\frac{1}{\ell}\sum_{i=1}^{\ell}\mathbb{E}[c(\underline{x}_{i}^{L})].$
(5)

######  Definition 2.

Define the minimum distortion $D(B_{\text{peak}})$ under the peak input cost
constraint $B_{\text{peak}}$ as

$\displaystyle\min_{P_{{\underline{X}}^{L}}}\frac{1}{\ell}\sum_{i=1}^{\ell}\sum_{{\underline{x}}^{L}}P_{{\underline{X}}^{L}}({\underline{x}}^{L})c(\underline{x}^{L}),$
(6)

where $P_{{\underline{X}}^{L}}({\underline{x}}^{L})$ satisfies the peak cost
constraint, i.e., $b({\underline{X}}_{i,j})\leq B_{\text{peak}},\forall
i\in[\ell],j\in[L]$ where $b(\cdot):\mathcal{X}\to\mathbb{R}_{+}$ is an input
cost function.

Since the channel state $\underline{S}$ is i.i.d. over each block, without
loss of generality, we consider only the first block and ignore the block
index $i$. The same derivation/strategy can be applied to other blocks
identically. We consider $b(\cdot)$ to be the Hamming weight function (number
of ones). This is physically motivated by the fact that assuming constant
transmission power per direction, the total transmission power is proportional
to the number of directions in which $\underline{X}_{i,j}$ sends a “1”. The
estimation distortion function $d(\underline{s},\hat{\underline{s}})$ is
characterized by Hamming distance, that is,

$\displaystyle
d(\underline{s},\hat{\underline{s}})=\begin{cases}0,&\underline{s}=\hat{\underline{s}}\\\
2,&\underline{s},\hat{\underline{s}}\in\mathcal{S}\text{ and
}\underline{s}\neq\hat{\underline{s}}\end{cases},$ (7)

since $\underline{s}$ and $\hat{\underline{s}}$ are both one-hot vectors.

##  III Main Results

In this section, we first derive the minimum distortion under a peak cost
constraint $B_{\text{peak}}$ with an unconstrained communication of the BBP
channel model, i.e., $D(B_{\text{peak}})$ in (6). Then, we provide a sensing
strategy that achieves the minimum distortion. Notice that this strategy can
simultaneously achieve the capacity of this BBP channel by our previous result
[2].

###  III-A Minimum Distortion

Let ${\mathcal{B}}_{y^{j}}(\underline{x}^{j})$ denote the set of beam indices
containing the transmission direction at channel use $j$ when channel input
$\underline{X}^{j}=\underline{x}^{j}$ and feedback $Y^{j}=y^{j}$ for all
possible transmission strategies. Then, we can simplify the distortion in (5)
as follows. We initialize ${\mathcal{B}}_{y^{0}}(\underline{x}^{0})=[M]$. The
state estimation decision is made based on
${\mathcal{B}}_{y^{L}}(\underline{x}^{L})$. For this BBP channel with iBM and
noiseless feedback, we have

$\displaystyle
P_{\hat{\underline{S}}|\underline{X}^{L}Y^{L}}({\underline{s}}|\underline{x}^{L},y^{L})$
$\displaystyle=P_{{\underline{S}}|\underline{X}^{L}Y^{L}}({\underline{s}}|\underline{x}^{L},y^{L})$
$\displaystyle=\frac{P_{{\underline{S}},\underline{X}^{L}Y^{L}}({\underline{s}},\underline{x}^{L},y^{L})}{P_{\underline{X}^{L}Y^{L}}(\underline{x}^{L},y^{L})}.$

The joint distribution for $L$ channel uses is

$\displaystyle P_{{\underline{X}}^{L},Y^{L}}({\underline{x}}^{L},y^{L}),$
$\displaystyle=\sum_{\underline{s}}P_{{\underline{X}}^{L},Y^{L},{\underline{S}}}({\underline{x}}^{L},y^{L},{\underline{s}})$
$\displaystyle=\sum_{\underline{s}}\prod_{j=1}^{L}P_{\underline{S}}({\underline{s}})\mathbbm{1}_{\\{{\underline{s}}^{T}{\underline{x}}_{j}=y_{j}\\}}P_{{\underline{X}}_{j}|{\underline{X}}^{j-1},Y^{j-1}}({\underline{x}}_{j}|{\underline{x}}^{j-1},y^{j-1})$
$\displaystyle=\frac{|\mathcal{B}_{y^{L}}({\underline{x}}^{L})|}{M}\prod_{j=1}^{L}P_{{\underline{X}}_{j}|{\underline{X}}^{j-1},Y^{j-1}}({\underline{x}}_{j}|{\underline{x}}^{j-1},y^{j-1}),$
(8a)
$\displaystyle=\frac{|\mathcal{B}_{y^{L}}({\underline{x}}^{L})|}{M}P_{{\underline{X}}^{L}||Y^{L-1}}({\underline{x}}^{L}||y^{L-1}),$
(8b)

where (8a) holds since
$\prod_{j=1}^{L}\mathbbm{1}_{\\{{\underline{s}}^{T}{\underline{x}}_{j}=y_{j}\\}}=1$
only for the beam indices belonging to
$\mathcal{B}_{y^{L}}({\underline{x}}^{L})$ and (8b) holds since we define

$\displaystyle
P_{{\underline{X}}^{L}||Y^{L-1}}({\underline{x}}^{L}||y^{L-1})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\prod_{j=1}^{L}P_{\underline{X}_{j}|\underline{X}^{j-1},Y^{j-1}}(\underline{x}_{j}|\underline{x}^{j-1},y^{j-1}).$
(9)

Therefore,

$\displaystyle
P_{\hat{\underline{S}}|\underline{X}^{L}Y^{L}}({\underline{s}}|\underline{x}^{L},y^{L})$
$\displaystyle=P_{{\underline{S}}|\underline{X}^{L}Y^{L}}({\underline{s}}|\underline{x}^{L},y^{L})$
$\displaystyle=\begin{cases}\frac{1}{|{\mathcal{B}}_{y^{L}}(\underline{x}^{L})|},&\forall\underline{s}\in{\mathcal{B}}_{y^{L}}(\underline{x}^{L})\\\
0,&\text{otherwise}\end{cases},$ (10)

where $|{\mathcal{B}}_{y^{L}}(\underline{x}^{L})|\geq 1$, i.e., it is uniform
over the restricted set $B_{y}^{L}(\underline{x}^{L})$ and zero elsewhere. The
distortion can be simplified as

$\displaystyle\mathbb{E}[d(\underline{S},\hat{\underline{S}})]$
$\displaystyle=\mathbb{E}_{\underline{X}^{L},Y^{L}}\left[\mathbb{E}[d(\underline{S},\hat{\underline{S}})|\underline{X}^{L},Y^{L}]\right]$
$\displaystyle=\sum_{\underline{x}^{L},y^{L}}P_{\underline{X}^{L}Y^{L}}(\underline{x}^{L},y^{L})\sum_{\hat{\underline{s}}\in\mathcal{S}}P_{\hat{\underline{S}}|\underline{X}^{L}Y^{L}}(\hat{\underline{s}}|\underline{x}^{L},y^{L})$
$\displaystyle\times\sum_{\underline{s}\in\mathcal{S}}P_{{\underline{S}}|\underline{X}^{L}Y^{L}}({\underline{s}}|\underline{x}^{L},y^{L})d(\underline{s},\hat{\underline{s}})$
$\displaystyle=\sum_{\underline{x}^{L},y^{L}}P_{\underline{X}^{L}Y^{L}}(\underline{x}^{L},y^{L})\frac{2[|{\mathcal{B}}_{y^{L}}(\underline{x}^{L})|-1]^{+}}{|{\mathcal{B}}_{y^{L}}(\underline{x}^{L})|}$
(11a)
$\displaystyle=\sum_{{\underline{x}}^{L}}\sum_{y^{L}}\prod_{j=1}^{L}P_{{\underline{X}}_{j}|{\underline{X}}^{j-1},Y^{j-1}}({\underline{x}}_{j}|{\underline{x}}^{j-1},y^{j-1})\frac{|\mathcal{B}_{y^{L}}({\underline{x}}^{L})|}{M}$
$\displaystyle\qquad\times\frac{2[|\mathcal{B}_{y^{L}}({\underline{x}}^{L})|-1]^{+}}{|\mathcal{B}_{y^{L}}({\underline{x}}^{L})|}$
$\displaystyle=\sum_{{\underline{x}}^{L}}\sum_{y^{L}}P_{{\underline{X}}^{L}||Y^{L-1}}({\underline{x}}^{L}||y^{L-1})\frac{2[|\mathcal{B}_{y^{L}}({\underline{x}}^{L})|-1]^{+}}{M}$
(11b)

where (11a) follows from (7) and (10), and (11b) follows from (9).

Sending back a $Y_{k}=1$ indicates that the transmission direction is detected
within the small set of ones in $\underline{X}_{k}$. Recall that
$\beta_{k}^{L}$ denotes the set containing all possible $L$-length binary
sequences with the first non-zero element appearing at index $k$. Let

$\displaystyle
c_{k}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}M\sum_{y^{L}\in\beta_{k}^{L}}P_{Y^{L}}(y^{L}),$
(12a) which is independent of the transmission strategy. Then, $\displaystyle
P_{Y^{L}}(0^{L})$
$\displaystyle=1-\sum_{k=1}^{L}\sum_{y^{L}\in\beta_{k}^{L}}P_{Y^{L}}(y^{L})=1-\sum_{k=1}^{L}\frac{c_{k}}{M}.$
(12b) Further, by (12a), we have $\displaystyle c_{k}\leq
MP_{Y_{k}}(y_{k}=1)\leq M\frac{B_{\text{peak}}}{M}=B_{\text{peak}},$ (12c)
where (12c) holds by the peak input cost constraint.

Following this notation, we next provide the minimum distortion under the peak
cost constraint.

######  Theorem 1.

The minimum distortion $D(B_{\text{peak}})$ defined in (6) of the BBP model
with iBM under peak cost constraint $B_{\text{peak}}$ is

$\displaystyle
D(B_{\text{peak}})=\sum_{j=1}^{L}\frac{2[c_{j}-2^{L-j}]^{+}}{M}+\frac{2[M-\sum_{j=1}^{L}c_{j}-1]^{+}}{M},$
(13)

where $c_{1}=\min(\frac{M}{2},B_{\text{peak}})$, and

$\displaystyle
c_{j}=\min(\frac{M-\sum_{k=1}^{j-1}c_{k}}{2},B_{\text{peak}}),1<j\leq L.$ (14)

###### Proof:

We first prove that the minimum distortion is presented in (13). By (12a), we
have

$\displaystyle c_{j}$
$\displaystyle=M\sum_{\underline{x}^{L}}\sum_{y^{L}\in\beta_{j}^{L}}P_{\underline{X}^{L},Y^{L}}(\underline{x}^{L},y^{L})$
$\displaystyle=M\sum_{\underline{x}^{L}}\sum_{y^{L}\in\beta_{j}^{L}}\frac{|\mathcal{B}_{y^{L}}(\underline{x}^{L})|}{M}P_{{\underline{X}}^{L}||Y^{L-1}}({\underline{x}}^{L}||y^{L-1})$
(15)

where (15) follows from (8b). Similarly, by (12b), we have

$\displaystyle M-\sum_{j=1}^{L}c_{j}$
$\displaystyle=M\sum_{\underline{x}^{L}}P_{\underline{X}^{L},Y^{L}}(\underline{x}^{L},0^{L})$
$\displaystyle=M\sum_{\underline{x}^{L}}\frac{|\mathcal{B}_{0^{L}}(\underline{x}^{L})|}{M}P_{\underline{X}^{L}||Y^{L-1}}(\underline{x}^{L}||\underline{0}^{L-1}).$

Continuing with (11b), the distortion at the end of each block is at least

$\displaystyle D$
$\displaystyle=\sum_{j=1}^{L}\sum_{y^{L}\in\beta_{j}^{L}}\sum_{{\underline{x}}^{L}}P_{{\underline{X}}^{L}||Y^{L-1}}({\underline{x}}^{L}||y^{L-1})\frac{2[|\mathcal{B}_{y^{L}}({\underline{x}}^{L})|-1]^{+}}{M}$
$\displaystyle+\sum_{{\underline{x}}^{L}}P_{{\underline{X}}^{L}||Y^{L-1}}({\underline{x}}^{L}||0^{L-1})\frac{2[|\mathcal{B}_{0^{L}}({\underline{x}}^{L})|-1]^{+}}{M}$
$\displaystyle\\!\geq\\!\sum_{j=1}^{L}\\!\frac{2[\sum_{y^{L}\in\beta_{j}^{L}}(\sum_{{\underline{x}}^{L}}\\!P_{{\underline{X}}^{L}||Y^{L-1}}({\underline{x}}^{L}||y^{L-1})|\mathcal{B}_{y^{L}}({\underline{x}}^{L})|-1)]^{+}}{M}$
(16a)
$\displaystyle+\frac{2[\sum_{{\underline{x}}^{L}}P_{{\underline{X}}^{L}||Y^{L-1}}({\underline{x}}^{L}||0^{L-1})|\mathcal{B}_{0^{L}}({\underline{x}}^{L})|-1]^{+}}{M}$
$\displaystyle=\sum_{j=1}^{L}\frac{2[c_{j}-2^{L-j}]^{+}}{M}+\frac{2[M-\sum_{j=1}^{L}c_{j}-1]^{+}}{M}$
(16b)

where (16a) holds since $[x-1]^{+}$ is a convex function, and (16b) holds by
(15) and since there are $2^{L-j}$ possible $y^{L}$ belongs to
$\beta_{j}^{L}$. Hence, the minimum distortion can be represented by (13).

Next, we show that the minimum (13) can be obtained by choosing
$c_{j},i\in[L]$ iteratively as given in (14). Ideally, the minimum of (16b) is
achieved when $M-\sum_{j=1}^{L}c_{j}-1\geq 0$ and $c_{j}-2^{L-i}\geq 0,\forall
j\in[L]$. Hence, we have $M-1\geq\sum_{j=1}^{L}2^{L-j},$ which gives
$L\leq\log M$. To have $c_{j}\geq 2^{L-j}$ and $M-\sum_{j=1}^{L}c_{j}-1\geq 0$
hold simultaneously, we can choose $c_{1}=\frac{M}{2}$ and
$c_{j}=\frac{M-\sum_{k=1}^{j-1}c_{k}}{2}$. Meanwhile, by (12c), $c_{j}\leq
B_{\text{peak}}$ for all $j\in[L]$. Therefore, we can choose (14) to achieve
the minimum of (13). Similarly, one can verify that the minimum distortion
$D(B_{\text{peak}})$ is achieved by choosing (14) when $L>\log M$. ∎

######  Remark 1.

The optimal choice of $c_{j}$ to minimize (13) is not unique and depends on
the values of $L,M$ and $B_{\text{peak}}$. For example, when
$L=1,B_{\text{peak}}>1,$ and $M>1$, any $1\leq c_{i}\leq M-1$ achieves the
minimum distortion. Herein, we choose $c_{j}$ as in (14) since it also
achieves the channel capacity as proved in [2].

###  III-B Estimation Strategy

In order to minimize distortion, it is critical to reducing the size of the
set $\mathcal{B}_{y^{L}}(\underline{x}^{L})$. Let $\mathcal{B}_{i}^{e}$ denote
the set of beam indices to be explored at channel use $i$ and
$\mathcal{B}_{i}^{e,c}$ denote the complementary of $\mathcal{B}_{i}^{e}$
(i.e., $\mathcal{B}_{i}^{e}\cup\mathcal{B}_{i}^{e,c}=[M]$). Initially,
${\mathcal{B}}_{y^{0}}=[M]$ and ${\mathcal{B}}_{0}^{e}=\emptyset$. Based on
the strictly causal noiseless feedback,
$|\mathcal{B}_{y^{i}}(\underline{x}^{i})|$ can be updated as

$\displaystyle|\mathcal{B}_{y^{i+1}}(\underline{x}^{i+1})|$
$\displaystyle=y_{i+1}|\mathcal{B}_{y^{i}}(\underline{x}^{i})\cap\mathcal{B}_{i}^{e}|+(1-y_{i+1})|\mathcal{B}_{y^{i}}(\underline{x}^{i})\cap\mathcal{B}_{i}^{e,c}|$
(17) $\displaystyle\geq
y_{i+1}|\mathcal{B}_{i}^{e}|+(1-y_{i+1})(|\mathcal{B}_{y^{i}}(\underline{x}^{i})|-|\mathcal{B}_{i}^{e}|)$
(18)

where (17) indicates that the size of possible transmission directions is
decreasing (i.e.,
$|\mathcal{B}_{y^{i+1}}(\underline{x}^{i+1})|\leq|\mathcal{B}_{y^{i}}(\underline{x}^{i})|$)
and equality in (18) holds when $\mathcal{B}_{i}^{e}\subseteq
B_{y^{i}}(\underline{x}^{i})$, that is, the transmitter selects beam indices
from the set $B_{y^{i}}(\underline{x}^{i})$ recursively.

Following the ideas illustrated above, we next show that the minimum
distortion in Theorem 1 can be obtained by applying the transmission strategy
in [2, Algorithm 1]. Specifically, we initialize a sequence of
$\\{c_{1},\cdots,c_{L}\\}$ iteratively solved by (14). At the beginning of
channel use $i$, we update ${\mathcal{B}}_{y^{i}}$ and choose some number of
beam indices randomly and uniformly from ${\mathcal{B}}_{y^{i}}$ based on the
casual feedback $Y_{i-1}$. Additionally, we use $k,k\in[L]$ to record the
number of channel uses until the transmitter selected the “right” directions
(i.e., $Y_{k}=1$). Before that, the transmitter randomly and uniformly chooses
$c_{i},i\leq k$ beam indices from ${\mathcal{B}}_{y^{i-1}}$. After that, the
transmitter randomly and uniformly chooses $\frac{c_{k}}{2^{i-k}},i>k$ beam
indices from ${\mathcal{B}}_{y^{i-1}}$. These selected beam indices are stored
in set $\mathcal{B}_{i}^{e}$.

Recall that $\beta_{k}^{L}$ denotes the binary sequence with length $L$ and
the first non-zero element appearing at the $k$-index. Based on this
transmission strategy, the probabilities of output sequences $y^{L}$ under the
condition of different channel states are the same, i.e.,
$P_{Y^{L}|\underline{S}}(y^{L}|\underline{s})=P_{Y^{L}|\underline{S}}(y^{L}|\underline{s}^{\prime}),\underline{s}\neq\underline{s}^{\prime}$,
and one can easily check that

$\displaystyle\sum_{\underline{x}^{L}}\sum_{y^{L}\in\beta_{k}^{L}}P_{{\underline{X}}^{L},Y^{L}}({\underline{x}}^{L},y^{L})=\frac{c_{k}}{M},\
|\mathcal{B}_{\beta_{k}^{L}}({\underline{x}}^{L})|=\frac{c_{k}}{2^{L-k}},$
(19a)
$\displaystyle\sum_{\underline{x}^{L}}P_{{\underline{X}}^{L},Y^{L}}({\underline{x}}^{L},0^{L})=1-\frac{\sum_{k=1}^{L}c_{k}}{M},\
|\mathcal{B}_{0^{L}}({\underline{x}}^{L})|=M-\sum_{k=1}^{L}c_{k},$ (19b)

where $|\mathcal{B}_{0^{L}}({\underline{x}}^{L})|\geq 0$ by (14) and
$\mathcal{B}_{\beta_{k}^{L}}({\underline{x}}^{L})$ denotes the set containing
possible transmission directions for any channel input sequence
${\underline{x}}^{L}$ leading to $y^{L}\in\beta_{k}^{L}$. From (11b), the
distortion is at least

$\displaystyle
D(B_{\text{peak}})=\sum_{{\underline{x}}^{L}}\left(\sum_{k=1}^{L}\sum_{y^{L}\in\beta_{k}^{L}}\right.$
$\displaystyle\left.P_{{\underline{X}}^{L}||Y^{L-1}}({\underline{x}}^{L}||y^{L-1})\frac{2[|\mathcal{B}_{\beta_{k}^{L}}({\underline{x}}^{L})|-1]^{+}}{M}\right.$
(20a)
$\displaystyle\left.+P_{{\underline{X}}^{L}||Y^{L-1}}({\underline{x}}^{L}||0^{L-1})\frac{2[|\mathcal{B}_{0^{L}}({\underline{x}}^{L})|-1]^{+}}{M}\right)$
(20b)
$\displaystyle=\sum_{k=1}^{L}2^{L-k}\frac{2[\frac{c_{k}}{2^{L-k}}-1]^{+}}{M}+\frac{2[M-\sum_{k=1}^{L}c_{k}-1]^{+}}{M}$
(20c)
$\displaystyle=\sum_{k=1}^{L}\frac{2[c_{k}-2^{L-k}]^{+}}{M}+\frac{2[M-\sum_{k=1}^{L}c_{k}-1]^{+}}{M}.$
(20d)

We partition the sequence of $y^{L}$ into $y^{L}\in\beta_{k}^{L}$ and
$y^{L}=0^{L}$ in (20a) and (20b). (20c) follows from (19a) and there are
$2^{i-k}$ possible $y^{i}$ sequences in $\beta_{k}^{i}$ sharing the same
probability
$P_{{\underline{X}}^{i},Y^{i}}({\underline{x}}^{i},y^{i}\in\beta_{k}^{i})$ for
$k\leq i$ according to Algorithm 1. Finally, we obtain the lower bound (20d).
Therefore, we showed that Algorithm 1 in [2] achieves the distortion in (13).

##  IV Conclusion

In this work, we studied a binary beam-pointing channel with in-block memory
and feedback that captures the main feature of the beam alignment problem in
mmWave communications and yet is sufficiently simple to be tractable from an
information-theoretic viewpoint. We derived the minimum distortion of this
simplified channel model under the peak cost constraint. We showed that the
capacity-achieving transmission strategy in [2] attains the minimum distortion
simultaneously. In conclusion, we have characterized the full capacity-
distortion region of this binary beam-pointing channel under the peak cost
constraint. This surprising result reveals the fact that channel estimation
and signal communication can be jointly optimal, which enables the efficient
utilization of the available resources in time, frequency, available antennas,
and transmission power.

## References

  * [1] G. Kramer, “Information Networks With In-Block Memory,” _IEEE Transactions on Information Theory_ , vol. 60, no. 4, pp. 2105–2120, April 2014\.
  * [2] S. Li and G. Caire, “On the Capacity of “Beam-Pointing” Channels with Block Memory and Feedback: The Binary Case,” _2022 56th Asilomar Conference on Signals, Systems, and Computers_ , pp. 1262–1268, 2022.
  * [3] R. W. Heath, N. González-Prelcic, S. Rangan, W. Roh, and A. M. Sayeed, “An Overview of Signal Processing Techniques for Millimeter Wave MIMO Systems,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 10, no. 3, pp. 436–453, 2016.
  * [4] K. Aldubaikhy, W. Wu, N. Zhang, N. Cheng, and X. Shen, “mmWave IEEE 802.11ay for 5G Fixed Wireless Access,” _IEEE Wireless Communications_ , vol. 27, no. 2, pp. 88–95, 2020.
  * [5] A. K. R. Chavva, S. K., C. Lim, Y. Lee, J. Kim, and Y. Rashid, “Sensor intelligence based beam tracking for 5g mmwave systems: A practical approach,” in _2019 IEEE Global Communications Conference (GLOBECOM)_ , 2019, pp. 1–6.
  * [6] I. Orikumhi, J. Kang, C. Park, J. Yang, and S. Kim, “Location-Aware Coordinated Beam Alignment in mmWave Communication,” in _2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , 2018, pp. 386–390.
  * [7] W. Roh, J.-Y. Seol, J. Park, B. Lee, J. Lee, Y. Kim, J. Cho, K. Cheun, and F. Aryanfar, “Millimeter-wave beamforming as an enabling technology for 5G cellular communications: theoretical feasibility and prototype results,” _IEEE Communications Magazine_ , vol. 52, no. 2, pp. 106–113, 2014.
  * [8] M. S. Ullah and A. Tewfik, “Beam Detection Analysis for 5G mmWave Initial Acquisition,” in _2018 28th International Telecommunication Networks and Applications Conference (ITNAC)_ , 2018, pp. 1–8.
  * [9] V. Desai, L. Krzymien, P. Sartori, W. Xiao, A. C. K. Soong, and A. Alkhateeb, “Initial beamforming for mmWave communications,” _null_ , 2014.
  * [10] S.-E. Chiu, N. Ronquillo, and T. Javidi, “Active Learning and CSI Acquisition for mmWave Initial Alignment,” _IEEE Journal on Selected Areas in Communications_ , vol. 37, no. 11, pp. 2474–2489, 2019.
  * [11] M. Hashemi, A. Sabharwal, C. E. Koksal, and N. B. Shroff, “Efficient Beam Alignment in Millimeter Wave Systems Using Contextual Bandits,” _null_ , 2018.
  * [12] N. Michelusi and M. Hussain, “Optimal Beam-Sweeping and Communication in Mobile Millimeter-Wave Networks,” _null_ , 2018.
  * [13] X. Song, S. Haghighatshoar, and G. Caire, “A Scalable and Statistically Robust Beam Alignment Technique for Millimeter-Wave Systems,” _IEEE Transactions on Wireless Communications_ , vol. 17, no. 7, pp. 4792–4805, 2018\.
  * [14] F. Pedraza and G. Caire, “Adaptive Two-Sided Beam Alignment in mmWave via Posterior Matching,” in _2020 IEEE Information Theory Workshop (ITW)_ , 2021, pp. 1–5.
  * [15] M. Hussain and N. Michelusi, “Energy-Efficient Interactive Beam Alignment for Millimeter-Wave Networks,” _IEEE Transactions on Wireless Communications_ , 2019.
  * [16] A. Lapidoth and P. Narayan, “Reliable communication under channel uncertainty,” _IEEE Transactions on Information Theory_ , vol. 44, no. 6, pp. 2148–2177, 1998.
  * [17] F. Liu, Y. Cui, C. Masouros, J. Xu, T. X. Han, Y. C. Eldar, and S. Buzzi, “Integrated Sensing and Communications: Towards Dual-functional Wireless Networks for 6G and Beyond,” _IEEE Journal on Selected Areas in Communications_ , pp. 1–1, 2022.
  * [18] M. Kobayashi, G. Caire, and G. Kramer, “Joint State Sensing and Communication: Optimal Tradeoff for a Memoryless Case,” 2018. [Online]. Available: https://arxiv.org/abs/1805.05713
  * [19] M. Kobayashi, H. Hamad, G. Kramer, and G. Caire, “Joint State Sensing and Communication over Memoryless Multiple Access Channels,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , 2019, pp. 270–274.
  * [20] M. Ahmadipour, M. Kobayashi, M. Wigger, and G. Caire, “An information-theoretic approach to joint sensing and communication,” _IEEE Transactions on Information Theory_ , pp. 1–1, 2022.