# Multishot Adversarial Network Decoding
††thanks: The work of G. C. and G. L. M. is supported by NSF DMS-2201075. G.
L. M. is also supported in part by the Commonwealth Cyber Initiative. A. R. is
supported by the Dutch Research Council through grants VI.Vidi.203.045,
OCENW.KLEIN.539, and by the Royal Academy of Arts and Sciences of the
Netherlands.

Giuseppe Cotardo, Gretchen L. Matthews, Julia Shapiro  Dept. of Mathematics
Virginia Tech
Blacksburg, VA, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Alberto Ravagnani  Dept.
of Mathematics and Computer Science
Eindhoven University of Technology
Eindhoven, the Netherlands
<EMAIL_ADDRESS>
###### Abstract

We investigate adversarial network coding and decoding focusing on the
multishot regime. Errors can occur on a proper subset of the network edges and
are modeled via an adversarial channel. The paper contains both bounds and
capacity-achieving schemes for the Diamond Network and the Mirrored Diamond
Network. We also initiate the study of the generalizations of these networks.

###### Index Terms:

network decoding, adversarial network, multishot capacity

##  I Introduction

Network coding is a communication strategy that outperforms routing [4, 7, 9,
10, 15, 16, 12, 11, 14, 13, 17, 6, 8]. In that context, sources attempt to
transmit information packets to one or more terminals through a network of
intermediate nodes. In [1], the authors introduced the problem of computing
the capacity of a network where errors can occur on a proper subset of the
network edges. This scenario was modeled via an adversarial channel and a
generalized Singleton Bound for the one-shot capacity (i.e., the largest
amount of information packets that can be sent to all terminals in a single
use of the network) of networks with restricted adversaries was established.

This study was furthered in [2, 3, 5], where the authors introduced the
concept of network decoding as a necessary strategy to achieve capacity in
networks with a restricted adversary. In [5] five elementary families of
networks were introduced, together with upper bounds on their one-shot
capacity and communication schemes. The Diamond Network and the Mirrored
Diamond Network are examples from these elementary families. The results of
[5] demonstrate that when an adversary is confined to operate on a vulnerable
region of the network, end-to-end communication strategies combined with
linear network coding are sub-optimal.

In this paper, we initiate the study of the multishot capacity of networks
with restricted adversaries. In other words, we wish to compute the largest
amount of information packets that can be sent to all terminals on average
over multiple uses of the network. We focus on the Diamond Network and the
Mirrored Diamond Network as building blocks of a more general theory that will
be presented in an extended version of this work.

Our work gives insight into when using a network multiple times for
communication allows us to send more information than in one use of a network
with a large alphabet. We show that the multishot capacity of the Diamond
Network has a strict increase in comparison to its one-shot capacity in one
adversarial model. On the other hand, for the Mirrored Diamond Network and
generalizations, the maximum capacity is the same over multiple uses of these
networks.

This paper is organized as follows. In Section II we introduce the notation
and background to be used throughout the paper. Section III establishes the
exact multishot capacity of the Diamond Network, the Mirrored Diamond Network
and the families of networks introduced in [3, 5], under the assumption that
the adversary cannot change the edges attacked in each transmission round. In
Section IV, we study the multishot capacities of these networks assuming that
the adversary has freedom to change the edges attacked in each transmission
round. In Section V, we include open questions and ideas for future work.

##  II Network Decoding

This section includes preliminary definitions and results related to
adversarial networks. We establish the notation that will be used throughout
the paper.

In the following, we let $q$ be a prime power and $\mathbb{F}_{q}$ the finite
field with $q$ elements. We recall the definition of network proposed in [1,
Definition 38]. A network is a 4-tuple
$\mathscr{N}=(\mathscr{V},\mathscr{E},S,\bm{T})$ where
$(\mathscr{V},\mathscr{E})$ is a directed, acyclic and finite multigraph,
$S\in\mathscr{V}$ is the source and $\bm{T}\subset\mathscr{V}$ is the set of
terminals. We also assume that there exists a directed path from $S$ to any
$T\in\textbf{T}$, $|\textbf{T}|\geq 1$ and $S\notin\textbf{T}$ and that for
every $V\in\mathscr{V}\setminus(\\{S\\}\cup\textbf{T}),$ there exists a
directed path from $S$ to $V$ and from $V$ to one of the terminals
$T\in\textbf{T}$. The elements of $\mathscr{V}$ are called vertices (or nodes)
and the ones in $\mathscr{E}$ are called edges. The refer to the elements in
$V\in\mathscr{V}\setminus(\\{S\\}\cup\textbf{T})$ as intermediate vertices (or
intermediate nodes). We define indegree (respectively, outdegree) of a vertex
$V\in\mathscr{V}$ to be the the set of edges coming into (respectively, going
out of) $V$. We denote it by $\textup{in}(V)$ (respectively,
$\textup{out}(V)$) and its cardinality by $\deg^{+}(V)$ (respectively,
$\deg^{-}(V)$).

Each edge of the network $\mathscr{N}$ carries one element from an alphabet
$\mathscr{A}$. We assume that $\mathscr{A}$ has cardinality at least $2$. The
vertices in the network $\mathscr{N}$ receive symbols from $\mathscr{A}$ over
the incoming edges, process them according to functions, and then send the
outputs over the outgoing edges. We model errors in the transmission as being
introduced by an adversary $A$ who can corrupt up to $t$ edges from a fixed
subset $\mathscr{U}\subseteq\mathscr{E}$. The adversary can change a symbol
sent across one of the edges of $\mathscr{U}$ and change it to any other
symbol of the alphabet. We call the pair $(\mathscr{N},\textbf{A})$ an
adversarial network.

######  Definition II.1 ([1, Definition 1]).

An adversarial channel is a map $\Omega:=\mathscr{X}\to 2^{\mathscr{Y}}$,
where $\mathscr{X}$ and $\mathscr{Y}$ are the input and output alphabets
respectively and $\mathscr{X},\mathscr{Y}\neq\emptyset$. The notation for this
type of channel is $\Omega:\mathscr{X}\dashrightarrow\mathscr{Y}$.

######  Definition II.2 ([1, Definition 40]).

A network code $\mathscr{F}$ for $\mathscr{N}$ is a family of functions
$\\{\mathscr{F}_{V}:V\in\mathscr{V}\setminus\\{S\cup\textbf{T}\\}\\},$ where
$\mathscr{F}_{V}:\mathscr{A}^{\textup{deg}^{+}(V)}\to\mathscr{A}^{\textup{deg}^{-}(V)}$
for all $V$.

The functions in $\mathscr{F}$ give a description of how $\mathscr{N}$
processes the information in each node coming from the incoming edges. This
can be uniquely interpreted according to a partial ordering. Let $e_{1}$,
$e_{2}$ be edges in a network. We say $e_{1}\in\mathscr{E}$ precedes
$e_{2}\in\mathscr{E}$ ($e_{1}\preceq e_{2}$) if there exists a directed path
in $(V,\mathscr{E})$, with starting edge $e_{1}$ and ending edge $e_{2}$. It
is well know that this partial order can be extended to a total order on
$\mathscr{E}$, denoted by $\leq$. Let
$\mathscr{U},\mathscr{U}^{\prime}\in\mathscr{E}$ be subsets of edges in a
network. As in [3, Definition 3], we say that $\mathscr{U}$ precedes
$\mathscr{U}^{\prime}$ if every path from $S$ to an edge of
$\mathscr{U}^{\prime}$ contains an edge of $\mathscr{U}$.

######  Definition II.3 ([3, Definition 4]).

Let $(\mathscr{N},\bm{A})$ be an adversarial network and let
$\mathscr{U},\mathscr{U}^{\prime}\subseteq\mathscr{E}$ be non empty with
$\mathscr{U}$ preceding $\mathscr{U}^{\prime}$. Let $\mathscr{F}$ be a network
code for $\mathscr{N}$. For $x\in\mathscr{A}^{|\mathscr{U}|}$, we denote the
set of vectors over the alphabet that can be exiting the edges of
$\mathscr{U}^{\prime}$ as

$\Omega[\mathscr{N},\bm{A},\mathscr{F},\mathscr{U}\to\mathscr{U}^{\prime}](x)\subseteq\mathscr{A}^{|\mathscr{U}^{\prime}|}$

We note that the vertices process the information according to the choice of
$\mathscr{F}$, the coordinates of $x$ are values from $\mathscr{A}$ entering
the edges of $\mathscr{U}^{\prime}$ and we consider the total order $\leq$
throughout.

######  Definition II.4 ([3, Definition 6]).

An outer code for $\mathscr{N}$ is a subset
$C\subseteq\mathscr{A}^{\deg^{+}(V)}$ with $|C|\geq 1$. We say that $C$ is
unambiguous (or good) for $(\mathscr{N},\bm{A},\mathscr{F})$ if for all
$x,y\in C$ with $x\neq y$ and for all $T\in\bm{T}$ we have

$\Omega[\mathscr{N},\bm{A},\mathscr{F},\textup{out}(V)\to\textup{in}(V)](x)\cap\\\
\Omega[\mathscr{N},\bm{A},\mathscr{F},\textup{out}(V)\to\textup{in}(V)](y)=\emptyset.$

We note that the intersection being empty guarantees that every element of $C$
can be uniquely recovered by every terminal, despite the actions the adversary
takes. Next we define the notion of one-shot capacity of an adversarial
network.

######  Definition II.5 ([5, Definition 3.18]).

The one-shot capacity of an adversarial network $(\mathscr{N},\bm{A})$ is the
maximum $\alpha\in\mathbb{R}$ such that there exists an unambiguous code $C$
and a network code $\mathscr{F}$ with $\alpha=\log_{|\mathscr{A}|}(|C|).$ We
denote the maximum quantity by $C_{1}(\mathscr{N},\bm{A})$.

The following result, proved in [1], gives an upper bound on the one-shot
capacity of a network $\mathscr{N}$ under the presence of an adversary who is
restricted to corrupting a proper subset of its edges.

######  Theorem II.6 (The Singleton Cut-Set Bound - [1, Theorem 67]).

Let $t\geq 0$ and suppose that $\bm{A}$ can corrupt up to $t$ edges from a
subset $\mathscr{U}\subseteq\mathscr{E}$. Then

$C_{1}(\mathscr{N},\bm{A})\leq\min_{T\in\textbf{T}}\min_{\mathscr{E}^{\prime}}\left(|\mathscr{E}^{\prime}\setminus\mathscr{U}|\right.\\\
\left.+\max\\{0,|\mathscr{E}^{\prime}\cap\mathscr{U}|-2t\\}\right)$

where $\mathscr{E}^{\prime}\subseteq\mathscr{E}$ ranges over all edge-cuts
between $S$ and $T$.

This work focuses on the multishot capacity of an adversarial network
$(\mathscr{N},\bm{A})$. A formal definition, which extends [5, Definition
3.18], is the following.

######  Definition II.7.

Let $i$ be a positive integer. The i-th shot capacity of
$(\mathscr{N},\bm{A})$ is the maximum $\alpha\in\mathbb{R}$ such that there
exists an unambiguous code $C$ for $(\mathscr{N},\bm{A})$ with
$\alpha=\frac{\log_{|\mathscr{A}|}(|C|)}{i}$. We denote this maximum value by
$\textup{C}_{i}(\mathscr{N},\bm{A})$.

Using the network multiple times can also be modeled as the power channel
associated to it. We can formalize it as follows.

######  Definition II.8 ([1, Definition 10]).

Let $i\geq 1$ be an integer. The i-th power of a channel
$\Omega:\mathscr{X}\dashrightarrow\mathscr{Y}$ is represented by the channel

$\Omega^{i}:=\underbrace{\Omega\times\cdots\times\Omega}_{i\text{
times}}:\mathscr{X}^{i}\dashrightarrow\mathscr{Y}^{i}.$

We also recall the definitions the operations of product and concatenation of
channels introduced in [1]. See [1, Definitions 7 and 14] respectively.

Let $\Omega_{1}:\mathscr{X}_{1}\dashrightarrow\mathscr{Y}_{1}$ and
$\Omega_{2}:\mathscr{X}_{2}\dashrightarrow\mathscr{Y}_{2}$ be channels and
assume that $\mathscr{Y}_{1}\subseteq\mathscr{X}_{2}$. The product of
$\Omega_{1}$ and $\Omega_{2}$ is the channel
$\Omega_{1}\times\Omega_{2}:\mathscr{X}_{1}\times\mathscr{X}_{2}\dashrightarrow\mathscr{Y}_{1}\times\mathscr{Y}_{2}$
defined by

$(\Omega_{1}\times\Omega_{2})(x_{1},x_{2}):=\Omega_{1}(x_{1})\times\Omega_{2}(x_{2}),$

for all $(x_{1},x_{2})\in\mathscr{X}_{1}\times\mathscr{X}_{2}$. The
concatenation of $\Omega_{1}$ and $\Omega_{2}$ is the channel
$\Omega_{1}\blacktriangleright\Omega_{2}:\mathscr{X}_{1}\dashrightarrow\mathscr{Y}_{2}$
defined by

$(\Omega_{1}\blacktriangleright\Omega_{2})(x):=\bigcup_{y\in\Omega_{1}(x)}\Omega_{2}(y).$

The following proposition provides a lower bound on the one-shot capacity of
product channels and establishes a connection between the one-shot capacity
and the $i-$th shot capacity of a network.

######  Proposition II.9 ([1, Proposition 12]).

For a channel $\Omega:\mathscr{X}\dashrightarrow\mathscr{Y}$ and any $i\geq
1$, we have

$C_{1}(\Omega^{i})\geq i\cdot C_{1}(\Omega).$

We restrict to networks with a single source $S$ and we follow the notation
introduced in [5, Section V]. A network
$\mathscr{N}=(\mathscr{V},\mathscr{E},S,\bm{T})$ is simple if it has only one
terminal $T$, i.e. $\bm{T}=\\{T\\}$. We say that $\mathscr{N}$ is a simple
two-level network if every path from $S$ to $T$ has length $2$. Let
$\mathscr{N}$ be a simple two-level network with $j\geq 1$ intermediate nodes.
In the sequel we follow [5, Notations 5.3 and Example 5.4], and refer the
reader to that paper for the details. Let $[x_{1},\ldots,x_{j}]$ and
$[y_{1},\ldots,y_{j}]^{\top}$ be the matrix representation of the graph
induced by the source, the intermediate nodes, and the terminal respectively.
We denote $\mathscr{N}$ by $([x_{1},\ldots,x_{j}],[y_{1},\ldots,y_{j}])$.

In the remainder of the paper, we will focus on particular families of
networks introduced in [2], [3] and [5]. We recall their definitions.

Let $\mathscr{D}$ be the network in Figure 1 and consider an adversary
$\bm{A}_{\mathscr{D}}$ able to corrupt at most one of the dashed edges. We
call the pair $(\mathscr{D},\bm{A}_{\mathscr{D}})$ the Diamond Network. It was
shown in [3, Section III] and [2] that this is the smallest example of a
network that does not meet the Singleton Cut-Set Bound proved in [1]. In
particular, the following holds.

######  Theorem II.10 ([3, Theorem 13]).

For any alphabet $\mathscr{A}$, we have
$C_{1}(\mathscr{D},\bm{A}_{\mathscr{D}})=\textup{log}_{|\mathscr{A}|}(|\mathscr{A}|-1).$

$S$$V_{1}$$V_{2}$$T$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$ Figure 1: The Diamond
Network $\mathscr{D}$

In [3, Section 3 and 4], it was proved that the network obtained by adding an
edge to the Diamond Network, as in Figure 2, attains the Singleton Cut-Set
Bound. The pair $(\mathscr{S},\bm{A}_{\mathscr{S}})$ is called Mirrored
Diamond Network, where $\bm{A}_{\mathscr{S}}$ again represents an adversary
able to corrupt at least on dashed edge.

$S$$V_{1}$$V_{2}$$T$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{4}$$e_{5}$ Figure 2:  The
Mirrored Diamond Network $\mathscr{S}$

######  Theorem II.11 ([3, Proposition 14]).

For any alphabet $\mathscr{A}$, we have
$C_{1}(\mathscr{S},\bm{A}_{\mathscr{S}})=1$.

The Diamond Networks were further generalized in [5, Section V.C]. Let $t\geq
2$ be an integer and define the simple two-level networks
$\mathfrak{C}_{t}=([t,t+1],[t,t])$ and $\mathfrak{D}_{t}=([2t,2t],[1,1])$. It
is not hard to check that $\mathfrak{C}_{1}$ and $\mathfrak{D}_{1}$ recovers
the Diamond and the Mirrored Diamond Network respectively.

We let $i\in\mathbb{N}$ represent the number of uses of each network. The
remainder of the paper is organized according to the following adversarial
models.

  1. A.1

The adversary corrupts the same $t$ edges over the multiple uses of the
network.

  2. A.2

The adversary can change the $t$ edges to corrupt over the multiple uses of
the network.

##  III Multishot Regime I

In this section, we study the multishot capacity of the Diamond and Mirrored
Diamond Network introduced in [3] along with the families of networks
introduced in [5], in Scenario A.1.

###  III-A The Diamond Network

We assume that $t=1$ in this section. We start by noticing that reusing the
strategy previously proposed in [3, Proposition 11] one can easily show that
$C_{i}(\mathscr{D},\bm{A}_{\mathscr{D}})\geq\textup{log}_{|\mathscr{A}|}(|\mathscr{A}|-1)$.
We let
$\Omega[\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F},\textup{out}(S)\to\textup{in}(T)]$
be the channel representing the transfer from $S$ to $T$ of the Diamond
Network as in Definition II.3 for the remainder of the paper. The aim of this
section is to explicitly compute the multishot capacity of the Diamond Network
in Scenario A.1. We provide a construction of an unambiguous code of
cardinality $|\mathscr{A}|^{i}-1$ for
$(\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F})$ that models $i$ transmission
rounds and we show that this is the maximum possible in this setting. In
particular, we prove that

$\textup{C}_{i}(\mathscr{D},\bm{A}_{\mathscr{D}})=\frac{\log_{|\mathscr{A}|}(|\mathscr{A}|^{i}-1)}{i}$

We start with the following result.

######  Proposition III.1.

Let $\mathscr{F}$ be a network code for $(\mathscr{D},\bm{A}_{\mathscr{D}})$.
If $C\subseteq(\mathscr{A}^{i})^{3}$ is an unambiguous code for
$(\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F})$ then $|C|\geq|A|^{i}-1$.

###### Proof.

Let $\star$ be a symbol of the alphabet $\mathscr{A}$. We want to show that
the code

$C=\\{(a\mid a\mid
a):a\in\mathscr{A}\setminus(\star,\ldots,\star)\\}\subseteq(\mathscr{A}^{i})^{3}$

is unambiguous for $(\mathscr{D},\bm{A}_{\mathscr{D}})$. At each round, we use
the same network code $\mathscr{F}$ as in the proof of [3, Proposition 11].
Suppose the adversary corrupts $e_{1}$ and recall that in this case the
adversary is forced to change the symbol. One can check that, for any
$a\in\mathscr{A}^{i}$, we have

$\Omega^{i}[\mathscr{D},\bm{A},\mathscr{F},\textup{out}(S)\to\textup{in}(T)]((a\mid
a\mid a))=\\{(b\mid a)\\}$

for some $b\in\mathscr{A}^{i}\setminus\\{(\star,\ldots,\star)\\}$. On the
other hand, if the adversary corrupts $e_{2}$ or $e_{3}$ then, for any
$a\in\mathscr{A}^{i}\setminus\\{(\star,\ldots,\star)\\}$, we get

$\Omega^{i}[\mathscr{D},\bm{A},\mathscr{F},\textup{out}(S)\to\textup{in}(T)]((a\mid
a\mid a))=\\\ \\{(a\mid\star,\ldots,\star)\\}.$

It follows that, for any $c,c^{\prime}\in C$, we have

$\Omega^{i}[\mathscr{D},\bm{A},\mathscr{F},\textup{out}(S)\to\textup{in}(T)](c)\cap\\\
\Omega[\mathscr{N},\bm{A},\mathscr{F},\textup{out}(S)\to\textup{in}(T)](c^{\prime})\neq\emptyset$

if and only if $c=c^{\prime}$ which implies that the code $C$ is unambiguous.
This concludes the proof. ∎

Note that the appropriateness of the construction of $C$ in Proposition III.1
relies on the adversary not being able to change the edge attacked, meaning we
know the exact location of the adversary for the next $i-1$ transmission
rounds. Therefore, the strategy provided in [3, Proposition 11] can be applied
to $i$ transmission rounds by modeling the unambiguous code in
$(\mathscr{A}^{i})^{3}$. The lower bound provided in Proposition III.1 is a
strict improvement on the lower bound provided by Proposition II.9. This shows
that we can send more information over multiple use of the Diamond Network.

The action of the adversary on $(\mathscr{D},\bm{A}_{\mathscr{D}})$ is modeled
by the channel
$\textup{H}_{\mathscr{D}}:\mathscr{A}^{3}\dashrightarrow\mathscr{A}^{3}$
defined as
$\textup{H}_{\mathscr{D}}(x):=\\{y\in\mathscr{A}^{3}:d_{\textup{H}}(x,y)\leq
1\\}$ for all $x\in\mathscr{A}^{3}$, where $d^{\textup{H}}$ represents Hamming
distance. Therefore, a code $C\subseteq\mathscr{A}^{3}$ is unambiguous for
$\textup{H}_{\mathscr{D}}$ if $d^{\textup{H}}(C)=3$. We can extend this to $i$
uses of the network and describe the adversary as a power channel
$\textup{H}_{\mathscr{D}}^{i}$. Let
$x=(x_{1},\ldots,x_{3i})\in(\mathscr{A}^{3})^{i}$ and we can define
$x^{(j)}:=(x_{3j+1},x_{3j+2},x_{3j+3})$ for all $j\in\\{0,\ldots,i-1\\}$.
Then, for any $x\in C$, we have

$\textup{H}_{\mathscr{D}}(x)=\\{y\in(\mathscr{A}^{3})^{i}:d^{\textup{H}}(x^{(j)},y^{(j)})\\\
\textup{ for all }j\in\\{0,\ldots,i-1\\}\\}.$

and hence $C\subseteq(\mathscr{A}^{i})^{3}$ is good code for
$\textup{H}_{\mathscr{D}}^{i}$ if and only if for all $x,y\in C$, with $x\neq
y$ we have $d^{\textup{H}}(x^{(j)},y^{(j)})=3$ for some
$j\in\\{0,\ldots,i-1\\}$.

Let $s\in\\{1,2,3\\}$ and define
$\pi_{s}^{i}:\mathscr{A}^{3i}\longrightarrow\mathscr{A}^{i}$ to be the
projection onto the components in the set $\\{3j+s:j\in\\{0,\ldots,i-1\\}\\}$.
Intuitively, these are the components corresponding to the edge $e_{s}$ in
each round. The following generalizes [3, Claim A]

######  Lemma III.2.

Let $\mathscr{F}$ be a network code for $(\mathscr{D},\bm{A}_{\mathscr{D}})$.
If $C\subseteq\mathscr{A}^{3i}$ be an unambiguous code for
$(\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F})$ then $|\pi_{1}^{i}(C)|=|C|$.

###### Proof.

We already showed that $C$ is unambiguous for the Diamond Network if and only
if for any $x,y\in C$, with $x\neq y$, $d^{\textup{H}}(x^{(j)},y^{(j)})=3$ for
some $j\in\\{0,\ldots,i-1\\}$. Suppose, towards a contradiction, that there
exist $x,y\in C$ with $x\neq y$ and $\pi^{i}(x)=\pi^{i}(y)$. It implies that
$x_{3j+1}=y_{3j+1}$ and therefore $d^{\textup{H}}(x^{(j)},y^{(j)})\leq 2$ for
all $j\in\\{0,\ldots,i-1\\}$. This leads to a contradiction. ∎

The following result generalizes [3, Claim B].

######  Lemma III.3.

Let $\mathscr{F}$ be a network code for $(\mathscr{D},\bm{A}_{\mathscr{D}})$.
If $C\subseteq(\mathscr{A}^{i})^{3}$ be an unambiguous code for
$(\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F})$ then the restriction of
$\mathscr{F}_{V_{1}}$ to $\pi_{1}^{i}(C)$ is injective.

###### Proof.

Suppose, towards a contradiction, that there exist $x,y\in C$ such that $x\neq
y$ and
$\mathscr{F}_{V_{1}}(\pi_{1}^{i}(x))=\mathscr{F}_{V_{2}}(\pi_{1}^{i}(x))$. One
can check that the vector

$\left(\mathscr{F}_{V_{1}}(\pi_{1}^{i}(x))\mid\mathscr{F}_{V_{2}}\left(\pi_{2}^{i}(x)\mid\pi_{3}^{i}(y)\right)\right)\in\mathscr{A}^{2i}$

is in
$\Omega^{i}[\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F},\textup{out}(S)\to\textup{in}(T)](x)\cap\Omega^{i}[\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F},\textup{out}(S)\to\textup{in}(T)](y)$.
This implies that $C$ is not unambiguous for
$(\mathscr{D},\bm{A}_{\mathscr{D}})$ which is a contradiction. ∎

Following the notation in [3], we let

$\displaystyle\overline{\Omega}^{i}:=$
$\displaystyle\Omega^{i}[\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F},\\{e_{1},e_{2},e_{3}\\}\to\\{e_{2},e_{3}\\}],$
$\displaystyle\Omega^{i}:=$
$\displaystyle\Omega^{i}[\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F},\\{e_{1},e_{2},e_{3}\\}\to\\{e_{5}\\}]$

which is well-defined since $\\{e_{1},e_{2},e_{3}\\}$ precedes $\\{e_{5}\\}$.
The following result generalizes [3, Claim C].

######  Lemma III.4.

Let $\mathscr{F}$ be a network code for $(\mathscr{D},\bm{A}_{\mathscr{D}})$.
If $C\subseteq\mathscr{A}^{3i}$ is an unambiguous code for
$(\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F})$ then there exists at most one
element $x\in C$ such that $|\Omega^{i}(x)|=1$.

###### Proof.

Suppose, towards a contradiction, that there exist $x,y\in C$ such that
$|\Omega^{i}(x)|=|\Omega^{i}(y)|=1$ and $x\neq y$. It implies
$|\mathscr{F}_{V_{2}}(\overline{\Omega}^{i}(x))|=|\mathscr{F}_{V_{2}}(\overline{\Omega}^{i}(y))|=1$.
Since
$(\pi_{2}^{i}(x)\mid\pi_{3}^{i}(x)),(\pi_{2}^{i}(x)\mid\pi_{3}^{i}(y))\in\overline{\Omega}^{i}(x)$
and
$(\pi_{2}^{i}(y)\mid\pi_{3}^{i}(y)),(\pi_{2}^{i}(x)\mid\pi_{3}^{i}(y))\in\overline{\Omega}^{i}(y)$,
we have

$\displaystyle\mathscr{F}_{V_{2}}(\pi_{2}^{i}(x)\mid\pi_{3}^{i}(x))$
$\displaystyle=\mathscr{F}_{V_{2}}(\pi_{2}^{i}(x)\mid\pi_{3}^{i}(y))$
$\displaystyle=\mathscr{F}_{V_{2}}(\pi_{2}^{i}(y)\mid\pi_{3}^{i}(y)).$

It follows that

$\Omega^{i}[\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F},\textup{out}(S)\to\textup{in}(T)](x)\cap\\\
\Omega^{i}[\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F},\textup{out}(S)\to\textup{in}(T)](y)\neq\emptyset$

since the adversary can corrupt the edge $e_{1}$. This is a contradiction. ∎

We are now ready to prove a result analogous to [3, Proposition 12].

######  Proposition III.5.

Let $\mathscr{F}$ be a network code for $(\mathscr{D},\bm{A}_{\mathscr{D}})$.
If $C\subseteq\mathscr{A}^{3i}$ is an unambiguous code for
$(\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F})$ then

$|C|^{2}+|C|-1-|\mathscr{A}|^{2i}\leq 0.$

In particular, we have $|C|\leq|\mathscr{A}|^{i}-1$.

###### Proof.

For ease of notation, we define

$\displaystyle\widehat{\Omega}^{i}:=$
$\displaystyle\Omega^{i}[\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F},\\{e_{1},e_{2},e_{3}\\}\to\\{e_{4},e_{5}\\}],$
$\displaystyle\widehat{\Omega}_{1}^{i}:=$
$\displaystyle\\{y\in\widehat{\Omega}^{i}:\mathscr{F}_{V_{1}}(\pi_{1}^{i}(y))=\pi_{1}^{i}(x)\\},$
$\displaystyle\widehat{\Omega}_{2}^{i}:=$
$\displaystyle\\{y\in\widehat{\Omega}^{i}:\mathscr{F}_{V_{2}}((\pi_{2}^{i}(y)\mid\pi_{2}^{3}(y)))$
$\displaystyle=$ $\displaystyle(\pi_{2}^{i}(x)\mid\pi_{2}^{3}(x))\\}.$

for any $x\in C$, and write
$\widehat{\Omega}^{i}(x)=\widehat{\Omega}_{1}^{i}(x)\cup\widehat{\Omega}_{2}^{i}(x)$.
By definition, we have
$|\widehat{\Omega}^{i}(x)|=|\widehat{\Omega}_{1}^{i}(x)|+|\widehat{\Omega}_{2}^{i}(x)|-1$.
Using the three lemmas above we get

$\displaystyle\sum_{x\in C}|\widehat{\Omega}^{i}(x)|$ $\displaystyle\geq
1-2(|C|-1)+\sum_{x\in C}|C|-|C|$ $\displaystyle=2|C|-1+|C|^{2}-|C|$ (III.1)
$\displaystyle=|C|^{2}-|C|-1.$

On the other hand, since the code is unambiguous, we have

$\sum_{x\in C}|\widehat{\Omega}^{i}(x)|\leq|\mathscr{A}|^{2i}.$

Combining this with (III.1) we get the statement. ∎

As a consequence of Propositions III.1 and III.5, we have that in the Scenario
A.1 the maximum size of an unambiguous code for
$(\mathscr{D},\bm{A}_{\mathscr{D}},\mathscr{F})$ is exactly
$|\mathscr{A}|^{i}-1$ and therefore
$\textup{C}_{i}(\mathscr{D},\bm{A}_{\mathscr{D}})=\frac{\log_{|\mathscr{A}|}(|\mathscr{A}|^{i}-1)}{i}$.
Therefore, we have a gain in capacity over multiple uses of
$(\mathscr{D},\bm{A}_{\mathscr{D}})$.

###  III-B The Mirrored Diamond Network

The goal of this section is to explicitly compute the multishot capacity of
the Mirrored Diamond Network in Scenario A.1. Let
$\Omega_{\mathscr{S}}:=\Omega[\mathscr{S},\bm{A}_{\mathscr{S}},\mathscr{F},\textup{out}(S)\to\textup{in}(T)]$
be the channel that represents the transfer from $S$ to $T$ of $\mathscr{S}$.
Assume that $t=1$. Applying the strategy provided in [3, Proposition V.1] one
can check that $C_{i}(\mathscr{S},\bm{A}_{\mathscr{S}})\geq 1$. We will show
that

$C_{i}(\mathscr{S},\bm{A}_{\mathscr{S}})=1$

and hence the Singleton Cut-Set Bound can be achieved in each transmission
round independently. As in the previous section, we model the action of an
adversary acting on $(\mathscr{S},\bm{A}_{\mathscr{S}})$ by the channel
$\textup{H}_{\mathscr{S}}:\mathscr{A}^{4}\dashrightarrow\mathscr{A}^{4}$
defined by
$\textup{H}_{\mathscr{S}}(x):=\\{y\in\mathscr{A}^{\prime}:d^{\textup{H}}(x,y)\leq
1\\}$ for all $x\in\mathscr{A}$. One can check that the largest unambiguous
code for $\textup{H}_{\mathscr{S}}$ has cardinality $|\mathscr{A}|$ and there
is no unambiguous code with larger cardinality. Thus
$C_{1}(\textup{H}_{\mathscr{S}})=1$.

######  Notation III.6.

We let

$\Omega_{i}^{\prime}:=(\Omega_{\mathscr{F}_{1}}[\textup{out}(S)\to\textup{in}(T)]\RHD\textup{H}_{\mathscr{S}})\times\ldots\\\
\times(\Omega_{\mathscr{F}_{i}}[\textup{out}(S)\to\textup{in}(T)]\RHD\textup{H}_{\mathscr{S}})$

represent the channel describing $i$ uses of the network
$(\mathscr{S},\bm{A}_{\mathscr{S}})$, where $\mathscr{F}_{j}$ denotes the
network code used in transmission round $j$, with $j\in\\{1,\ldots,i\\}$.
Notice that
$\Omega_{i}^{\prime}:(\mathscr{A}^{4})^{i}\dashrightarrow(\mathscr{A}^{2})^{i}$.

We now show that there does not exist an unambiguous code
$C\subseteq(\mathscr{A}^{4})^{i}$ for the adversary channel
$\textup{H}_{\mathscr{S}}^{i}$ such that $|C|=|\mathscr{A}|^{i}+1$.

######  Example III.7.

For $x\in(\mathscr{A}^{4})^{i}$, we let
$x^{j}:=(x_{4j+1},x_{4j+2},x_{4j+3},x_{4j+4})$ for all $j\in{0,\ldots,i-1}$.
The code $C\subseteq(\mathscr{A}^{4})^{i}$ is unambiguous for
$\textup{H}_{\mathscr{S}}^{i}$ if and only if one among
$d^{\textup{H}}(x^{1},y^{1}),\ldots,d^{\textup{H}}(x^{i},y^{i})$ has Hamming
distance atleast $3$ for all $x,y$ with $x\neq y$. Let
$c_{1},\ldots,c_{|\mathscr{A}|^{i}+1}$ be elements in $C$. We want to show
that there are no two codewords of $C$ that coincide in the first
$|\mathscr{A}|^{i}$ components. Assume, towards a contradiction, that
$c_{1}^{1}=c_{2}^{1}$. We can also assume that $c_{1}=0$ without loss of
generality, which implies $c_{2}^{1}=0$. It follows that
$c_{3}^{1},\ldots,c_{|\mathscr{A}|^{i}+1}^{1}$ must have Hamming weight at
least $3$. If $c_{3}^{1}$ has Hamming weight less than $3,$ then one among
$\\{c_{1}^{2},c_{2}^{2},c_{3}^{2}\\},\ldots,\\{c_{1}^{i},c_{2}^{i},c_{3}^{i}\\}$
is an unambiguous code for $\textup{H}_{\mathscr{S}}$ of cardinality $3$ with
minimum Hamming distance $3$, which contradicts the fact that
$C_{1}(\textup{H}_{\mathscr{S}})=1.$ On the other hand, since
$c_{3}^{1},\ldots,c_{|\mathscr{A}|^{i}+1}^{1}$ have Hamming weight at least
$3$, we have that the Hamming distance between two elements in
$\\{c_{3}^{1},\ldots,c_{|\mathscr{A}|^{i}+1}^{1}\\}$ is atmost $2$. Therefore
assuming that $C$ is good for $\textup{H}_{\mathscr{S}}^{i}$ implies that one
of
$\\{c_{1}^{2},c_{2}^{2},c_{3}^{2}\\},\ldots,\\{c_{1}^{i},c_{2}^{i},c_{3}^{i}\\}$
must be a code with cardinality $3$ and minimum Hamming distance $3$, which
again contradicts $C_{1}(\textup{H}_{\mathscr{S}})=1$.

We are now ready to prove the main result of this section.

######  Proposition III.8.

The $i$-shot capacity of the Mirrored Diamond Network in Scenario A.1 is

$C_{i}(\mathscr{S},\bm{A}_{\mathscr{S}})=1.$

###### Proof.

We use an approach similar to the one in [1, Example 56]. Let $\mathscr{F}$ be
a network code for $(\mathscr{S},\bm{A}_{\mathscr{S}})$ and assume that
$\bm{A}$ can corrupt at most $1$ edge from $\\{e_{1},e_{2},e_{3},e_{4}\\}$.
Let $x=(x_{1},\ldots,x_{4i})\in\mathscr{A}^{4i}$. We have that

$\Omega_{i}^{\prime}(x)=\textup{H}_{\mathscr{S}}^{i}(\mathscr{F}^{1}(x_{1},x_{2},x_{3},x_{4}),\ldots,\\\
\mathscr{F}^{i}(x_{4i-3},x_{4i-2},x_{4i-1},x_{4i})).$

We want to show that $C_{1}(\Omega_{i}^{\prime})<|\mathscr{A}|^{i}+1$. Assume
that there exists a code $C\subseteq(\mathscr{A}^{4})^{i}$ with
$|C|=|\mathscr{A}|^{i}+1$ which is good for $\Omega_{i}^{\prime}$. Then

$C^{\prime}:=\\{\mathscr{F}^{1}(x_{1},x_{2},x_{3},x_{4}),\ldots,\\\
\mathscr{F}^{i}(x_{4i-3},x_{4i-2},x_{4i-1},x_{4i})):x\in
C\\}\subseteq\mathscr{A}^{2i}$

is an unambiguous code for $\textup{H}_{\mathscr{S}}^{i}$ with
$|C^{\prime}|=|\mathscr{A}|^{i}+1$. We have that there must exist
$a,a^{\prime}\in C$, $a\neq a^{\prime}$ such that
$(a_{1},\ldots,a_{|\mathscr{A}|^{i}})=(a_{1}^{\prime},\ldots,a_{|\mathscr{A}|^{i}}^{\prime})$.
Therefore, $C^{\prime}$ is a good code for $\textup{H}_{\mathscr{S}}^{i}$
which has two different code words that coincide in the first
$|\mathscr{A}|^{i}$ components. However, by Example III.7, this code does not
exist. This implies that
$C_{1}(\Omega_{i}^{\prime})<\textup{log}_{|\mathscr{A}|}(|\mathscr{A}|^{i}+1)$
and we get $C_{i}(\mathscr{S},\bm{A}_{\mathscr{S}})\leq 1$.

It remains to show that $C_{i}(\mathscr{S},\bm{A}_{\mathscr{S}})\geq 1$. This
immediately follows by [3, Proposition 12] using the channel
$\Omega^{i}_{\mathscr{S}}$. In particular, we have that

$C_{i}(\Omega_{\mathscr{S}})=\frac{C_{1}(\Omega^{i}_{\mathscr{S}})}{i}\geq\frac{iC_{1}(\Omega_{\mathscr{S}})}{i}=C_{1}(\Omega_{\mathscr{S}})=1.$

It follows the statement. ∎

We concludes this section with the following remark on the mulishot capacity
of Family $\mathfrak{C}$ and Family $\mathfrak{D}$.

######  Remark III.9.

It is not hard to check that for an adversary able to attack up to $t$ edges,
$C_{i}(\mathfrak{C},\bm{A}_{\mathfrak{C}})=1$ and
$C_{i}(\mathfrak{D},\bm{A}_{\mathfrak{D}})=1.$ This follows by using arguments
similar to the ones in Example III.7 and in the proof of Proposition III.8,
under the assumption that the adversary can corrupt up to $t$ edges, with
$t\geq 2$.

In summary, we showed that in Scenario A.1, there is a gain in capacity for
multiple uses of the Diamond Network. In contrast the Mirrored Diamond
Network, and the networks in families $\mathfrak{C}$ and $\mathfrak{D}$, have
a constant capacity $1$ over multiple uses.

##  IV Multishot Regime II

In this section, we study the multishot capacity of the Diamond and Mirrored
Diamond Network along with the families $\mathfrak{C}$ and $\mathfrak{D}$ in
Scenario A.2.

###  IV-A The Diamond Network

In the main result of this section, we show that the $i$-shot capacity of the
Diamond Network in Scenario A.2 is

$\textup{C}_{i}(\mathscr{D},\bm{A}_{\mathscr{D}})=\textup{log}_{|\mathscr{A}|}{(|\mathscr{A}|-1)}.$

This shows that for multiple uses of the Diamond Network, there is no gain in
capacity, in contrast with Scenario A.1. In the following examples, we provide
a characterization of an unambiguous code for $\textup{H}_{\mathscr{D}}$.

######  Example IV.1.

Let $\textup{H}_{\mathscr{D}}$ be the adversarial channel for $\mathscr{D}$ as
in Section III. The source $S$ can send any symbol of
$\mathscr{A}^{\prime}=\mathscr{A}\setminus\\{\star\\}$, where $\star$ is a
reserved symbol in the alphabet $\mathscr{A}$. One can check that, under the
assumption of Scenario A.2, the largest unambiguous code for
$\textup{H}_{\mathscr{D}}$ has cardinality $|\mathscr{A}|-1$ and there is no
larger unambiguous code. Recall that the source $S$ cannot send $\star$,
implying
$C_{1}(\textup{H}_{\mathscr{D}})=\textup{log}_{|\mathscr{A}|}(|\mathscr{A}|-1).$

The argument similar to the one in Scenario A.1 shows that a code
$C\subseteq(\mathscr{A}^{3})^{i}$ is unambiguous for
$\textup{H}_{\mathscr{D}}^{i}$ if and only if, for all $x,y\in C$ with $x\neq
y$, we have $d^{\textup{H}}(x^{(j)}),y^{(j)})\geq 3$, with
$j\in\\{1,\ldots,i-1\\}$. In the next example, we show that there does not
exist a code $C$ with $|C|=(|\mathscr{A}|-1)^{i}+1$ for $i$ uses of the
Diamond Network.

######  Example IV.2.

We suppose that that there exists an unambiguous code
$C\subseteq(\mathscr{A}^{3})^{i}$ for $\textup{H}_{\mathscr{D}}^{i}$ such that
$|C|<(|\mathscr{A}|-1)^{i}+1$. We use the same notation as in Example III.7,
for any $x=(x_{1},\ldots,x_{3i})\in(\mathscr{A}^{3})^{i}$, we let
$x^{1}:=(x_{1},x_{2},x_{3}),\ldots,x^{i}:=(x_{1}^{i},x_{2}^{i},x_{3}^{i})$ and
$c_{1},\ldots,c_{(|\mathscr{A}|-1)^{i}+1}$ be elements in $C$. We claim that
there are no two codewords of $C$ that coincide in the first
$(|\mathscr{A}|-1)^{i}$ components. Assume, towards a contradiction, that
$c_{1}^{1}=c_{2}^{1}$ for $c_{1}^{1}\neq c_{2}^{1}$ and we let $c_{1}=0$,
without loss of generality. This implies that $c_{2}^{1}=0$ and that
$c_{3}^{1},\ldots,c_{(|\mathscr{A}|-1)^{i}+1}^{1}$ must have Hamming weight at
least $3$. Observe that if $c_{3}^{1}$ has Hamming weight less than $3,$ then
one of
$\\{c_{1}^{2},c_{2}^{2},c_{3}^{2}\\},\ldots,\\{c_{1}^{i},c_{2}^{i},c_{3}^{i}\\}$
is a code in $\mathscr{A}^{3}$ of cardinality $3$ with minimum Hamming
distance $3$, contradicting
$C_{1}(\textup{H}_{\mathscr{D}})=\textup{log}_{|\mathscr{A}|}(|\mathscr{A}|-1).$
On the other hand, since $c_{3}^{1},\ldots,c_{(|\mathscr{A}|-1)^{i}+1}^{1}$
have Hamming weight at least $3$ which implies that the Hamming distance
between any two elements in
$\\{c_{3}^{1},\ldots,c_{(|\mathscr{A}|-1)^{i}+1}^{1}\\}$ is at most $2$. Since
we assumed that $C$ is unambiguous for $\textup{H}_{\mathscr{D}}^{i}$, we have
that one of
$\\{c_{1}^{2},c_{2}^{2},c_{3}^{2}\\},\ldots,\\{c_{1}^{i},c_{2}^{i},c_{3}^{i}\\}$
must be a code with cardinality $3$ and minimum Hamming distance $3$, which
again contradicts the capacity of $\textup{H}_{\mathscr{D}}$.

We introduce the following notation.

######  Notation IV.3.

We let

$\Omega_{i}:=(\Omega_{\mathscr{F}_{1}}[\textup{out}(S)\to\textup{in}(T)]\RHD\textup{H}_{\mathscr{D}})\times\ldots\\\
\times(\Omega_{\mathscr{F}_{i}}[\textup{out}(S)\to\textup{in}(T)]\RHD\textup{H}_{\mathscr{D}})$

be the channel modeling $i$ uses of the network
$(\mathscr{D},\bm{A}_{\mathscr{D}})$, where $\mathscr{F}_{j}$ denotes the
network code used in transmission round $j$, with $j\in\\{1,\ldots,i\\}$. Note
that $\Omega_{i}:(\mathscr{A}^{3})^{i}\dashrightarrow(\mathscr{A}^{2})^{i}$.

We are now ready to prove the main theorem of this section.

######  Theorem IV.4.

The $i$-shot capacity of the Diamond Network in Scenario A.2 is

$\textup{C}_{i}(\mathscr{D},\bm{A}_{\mathscr{D}})=\log_{|\mathscr{A}|}(|\mathscr{A}|-1).$

###### Proof.

We first show that $|C|\leq(|\mathscr{A}|-1)^{i}$. Assume that an adversary
$\bm{A}_{\mathscr{D}}$ can corrupt at most of the edges in the set
$\\{e_{1},e_{2},e_{3}\\}$. We observe that, for an
$x=(x_{1},\ldots,x_{3i})\in\mathscr{A}^{3i}$, we have

$\Omega_{i}(x)=\textup{H}_{\mathscr{D}}^{i}(\mathscr{F}^{1}(x_{1},x_{2},x_{3}),\ldots,\\\
\mathscr{F}^{i}(x_{3i-2},x_{3i-1},x_{3i})).$

Using a similar approach as in Proposition III.8, we assume that there exists
an unambiguous code $C\subseteq\mathscr{A}^{3i}$ for $\Omega_{i}$ with
$|C|=(|\mathscr{A}|-1)^{i}+1$. The code

$C^{\prime}:=\\{\mathscr{F}^{1}(x_{1},x_{2},x_{3}),\ldots,\\\
\mathscr{F}^{i}(x_{3i-2},x_{3i-1},x_{3i}))\\}\subseteq(\mathscr{A}^{3})^{i}$

is unambiguous for $\textup{H}_{\mathscr{D}}^{i}$ of cardinality
$(|\mathscr{A}|-1)^{i}+1$. Since $|C^{\prime}|=(|\mathscr{A}|-1)^{i}+1$, there
must exist $a,a^{\prime}\in C$, $a\neq a^{\prime}$ such that
$(a_{1},\ldots,a_{(|\mathscr{A}|-1)^{i}})=(a_{1}^{\prime},\ldots,a_{(|\mathscr{A}|-1)^{i}}^{\prime})$.
Thus $C^{\prime}\in(\mathscr{A}^{3})^{i}$ is an unambiguous code for
$\textup{H}_{\mathscr{D}}^{i}$ with two different code words that coincide in
the first $(|\mathscr{A}|-1)^{i}$ components. However such a code does not
exist by Example IV.2. It follows
$C_{1}(\Omega_{i})<\textup{log}_{|\mathscr{A}|}((|\mathscr{A}|-1)^{i}+1)$ and
hence $|C|\leq(|\mathscr{A}|-1)^{i}$. It remains to show that
$|C|\geq(|\mathscr{A}|-1)^{i}$. This immediately follows by applying [1,
Proposition 12] and the strategy introduced in [3, Proposition 11] to the
argument above. ∎

It is interesting to note that when the adversary can change the edge attacked
in each transmission round, we recover the same scheme as in [3].

###  IV-B Families $\mathfrak{C}$ and $\mathfrak{D}$

In this section, we show that the multishot capacities of networks in families
$\mathfrak{C}$ and $\mathfrak{D}$ is $1$. Recall that family $\mathfrak{D}$
includes the Mirrored Diamond Network. We start with the following preliminary
result.

######  Proposition IV.5.

The $i$-shot capacity of a network in families $\mathfrak{C}$ and
$\mathfrak{D}$ in Scenario A.2 is $1$.

###### Proof.

The result follows similarly as in PropositionIII.8 and Remark III.9, since we
do not assume anything on the adversary except that it can attack up to $1$
edge. ∎

These results shows that, in Scenario A.2, there is no gain of using these
networks multiple times for communication under this adversarial model.

##  V Open Questions and Future Work

In this paper we have investigated the multishot capacity of networks with
restricted adversaries focusing on the Diamond Network and the Mirrored
Diamond Network as elementary building blocks of a general theory. In future
work, we plan to investigate the multishot capacity of arbitrary networks by
establishing a multishot version of the double cut-set bound of in [5] and by
computing the multishot capacities of all the five families introduced in the
same paper.

## References

  * [1] F. Kschichang and A. Ravagnani, “Adversarial network coding,” IEEE Transactions on Information Theory, vol. 65, pp. 198–219, 2018.
  * [2] A. Beemer and A. Ravagnani, “The curious case of the Diamond Network,” unpublished, arXiv:2107.02144, 2021.
  * [3] A. Beemer, A. Kılıç, and A. Ravagnani, “Network decoding against restricted adversaries,” IFAC-PapersOnLine, vol. 55, pp. 236–241, 2022.
  * [4] N. Cai and R. Yeung, “Network error correction, part I: Basic concepts and upper bounds”, Communications in Information and Systems, vol. 6, pp. 19–36, 2006.
  * [5] A. Beemer, A. Kılıç, and A. Ravagnani, “Network decoding,”, IEEE Transactions On Information Theory, 2023.
  * [6] U. Martínez-Peñas and F. Kschischang, “Reliable and secure multishot network coding using linearized Reed-Solomon codes,” IEEE Transactions on Information Theory vol. 65.8, pp. 4785–4803, 2019.
  * [7] S. Li, R. Yeung, and N. Cai, “Linear network coding,” IEEE Transactions on Information Theory, vol. 49, pp. 371–381, 2003.
  * [8] R. Nóbrega and B. Uchôa-Filho, “Multishot codes for network coding: Bounds and a multilevel construction,” IEEE International Symposium on Information Theory, 2009.
  * [9] R. Ahlswede, N. Cai, S. Li, and R. Yeung, “Network information flow,” IEEE Transactions on Information Theory, vol. 46, no. 4, pp. 1204–-1216, 2000.
  * [10] S. Jaggi, M. Langberg, T. Ho, and M. Effros, “Correction of adversarial errors in networks,” IEEE International Symposium on Information Theory, pp. 1455–-1459, 2005.
  * [11] R. Köetter and F. Kschischang, “Coding for errors and erasures in random network coding,” IEEE Transactions on Information theory vol. 54.8, pp. 3579–3591, 2008.
  * [12] S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, and M. Medard, “Resilient network coding in the presence of Byzantine adversaries,” 26-th IEEE International Conference on Computer Communications, pp. 616–624, 2007.
  * [13] D. Silva, F. R. Kschischang, and R. Köetter, “A rank-metric approach to error control in random network coding,” IEEE Transactions on Information Theory, vol. 54, no. 9, pp. 3951–3967, 2008.
  * [14] L. Nutman and M. Langberg, “Adversarial models and resilient schemes for network coding,” IEEE International Symposium on Information Theory, pp. 171–175, 2008.
  * [15] R. Kötter and M. Médard. “An algebraic approach to network coding,” IEEE/ACM Transactions on Networking, vol. 11, pp. 782–795, 2003.
  * [16] D. Wang, D. Silva, and F. Kschischang, “Constricting the adversary: A broadcast transformation for network coding,” 45th Annual Allerton Conference on Commununications, Control and Computing, 2007.
  * [17] S. Mohajer, M. Jafari, S. N. Diggavi, and C. Fragouli, “On the capacity of multisource non-coherent network coding,” IEEE Information Theory Workshop on Networking and Information Theory, pp. 130–134, 2009.


# Space-Time Phase Coupling in STMM-based Wireless Communications

Marouan Mizmizi1, Dario Tagliaferri1, Marco Di Renzo2 and Umberto Spagnolini1
This work was partially supported by the European Union under the Italian
National Recovery and Resilience Plan (NRRP) of NextGenerationEU, partnership
on “Telecommunications of the Future” (PE00000001 - program “RESTART”). The
work of M. Di Renzo was supported in part by the European Commission through
the H2020 ARIADNE project under grant agreement number 871464 and through the
H2020 RISE-6G project under grant agreement number 101017011, and by the
Agence Nationale de la Recherche (ANR) through the ANR PEPR-5G project.
1Politecnico di Milano, Dipartimento di Elettronica, Informazione e
Bioingegneria, Italy
2Université Paris-Saclay, CNRS, CentraleSupélec, Laboratoire des Signaux et
Systèmes, France
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Space-time modulated metasurfaces (STMMs) are a recently proposed
generalization of reconfigurable intelligent surfaces, which include a proper
time-varying phase at the metasurface elements, enabling higher flexibility
and control of the reflected signals. The spatial component can be designed to
control the direction of reflection, while the temporal one can be adjusted to
change the frequency of the reflected signal or to convey information.
However, the coupling between the spatial and temporal phases at the STMM can
adversely affect its performance. Therefore, this paper analyzes the system
parameters that affect the space-time coupling. Furthermore, two methods for
space-time decoupling are investigated. Numerical results highlight the
effectiveness of the proposed decoupling methods and reveal that the space-
time phase coupling increases with the bandwidth of the temporal phase, the
size of the STMM, and with grazing angles of incidence onto the STMM.

###### Index Terms:

space-time modulated metasurfaces, reconfigurable intelligent surfaces, space-
time coupling.

##  I Introduction

Electromagnetic (EM) metasurfaces, a.k.a. reconfigurable intelligent surfaces
(RISs), are commonly regarded as one of the enablers of 6G services, being the
key component of the smart EM environment [1]. RISs are made of sub-
wavelength-sized elements, referred to as meta-atoms, whose scattering
properties can be engineered to manipulate the impinging EM waves and control
the angles of reflection and refraction [2].

Recent research advances proposed RISs (and metasurfaces in general) as a
candidate technology in many applications, including channel blockage
mitigation [3] [4], coverage extension [5] and, more recently, as an
enhancement for sensing [6]. The RIS technology is based on the generalized
Snell’s law, formulated in 2011 [7], which asserts that setting a spatial
phase gradient across the RIS elements breaks the spatial symmetry (and thus
the conservation of the linear momentum of the reflected and refracted waves).
In other words, an EM wave impinging from an arbitrary angle $\theta_{i}$ can
be reflected toward an angle $\theta_{o}\neq\theta_{i}$. The relation between
$\theta_{i}$ and $\theta_{o}$ is a deterministic function of the spatial phase
gradient. More recently, in 2014, the authors of [8, 9] proposed the universal
Snell’s law, extending the generalized one by considering also a temporal
phase gradient applied at each element of the RIS. The latter operation allows
the RIS to break the Lorentz reciprocity and enables anomalous nonreciprocal
reflections. In this case, an EM wave at carrier frequency $f_{i}$ impinging
on a time-modulated RIS from angle $\theta_{i}$ can be reflected towards an
angle $\theta_{o}\neq\theta_{i}$ and with a frequency $f_{o}\neq f_{i}$. This
opens the possibility to realize new devices, including space-time modulated
metasurfaces (STMMs), that not only control the direction of reflection but
also change the frequency and convey information [10].

The authors of [11] apply a temporally periodic phase gradient at each element
of the RIS, which generates temporal and spatial harmonics, i.e., the
impinging signal is reflected in different directions with different frequency
shifts depending on the set periodicity. A similar approach is proposed by the
authors of [12], where the generated harmonics encode the symbols of a
quadrature amplitude modulation. The idea was validated by using a
demonstrator capable of establishing a 20 Mbps communication link. The authors
of [13] discuss the realization of advanced modulation schemes by engineering
the phase response of the single STMM element. In this direction, the work
[14] analyzes the capacity of a RIS-aided link, where information data are
jointly encoded at the transmitter and at the RIS. The authors prove that the
latter scheme is necessary to achieve the maximum information rate and
provides significant gain over the max-signal-to-noise ratio approach, which
fixes the reflection pattern. A system-level analysis is shown in [15], with a
focus on a beamforming-plus-phase information system toward a single user.
Finally, the authors of [16] propose to apply phase-modulated STMM to enhance
backscatter communications.

All the aforementioned works are focused on the physical realization of STMM
or discuss specific applications. This paper analyzes the coupling between the
spatial and temporal phases that can be applied at the STMM. The space-time
phase coupling has not been considered in the literature so far (see e.g.,
[12]), and manifests itself when the incident signal is not perpendicular to
the STMM and when the phase-modulated reflection coefficient of the STMM has a
relatively large bandwidth compared to the size of the STMM (e.g., for
information-bearing signals). Specifically, we consider a generic full-duplex
system where a master unit (MU) sends a downlink signal of bandwidth $B_{d}$
to a slave unit (SU), equipped with a STMM. The latter is used to back-reflect
and modulate the received MU $\rightarrow$ SU signal with a MU $\leftarrow$ SU
uplink signal of bandwidth $B_{u}$. The uplink signal is encoded in the STMM
reflection coefficient’s phase, reducing the energy consumption of the SU
[17]. In this context, the contributions of the paper are twofold: (i) we
analytically characterize the coupling between the spatial and temporal phases
in STMM-based wireless systems, generalizing our previous work [18] by
considering a hybrid STMM structure, whereby a variable number of wideband
tunable components are employed; (ii) we evaluate the impact of the spatial-
temporal phase coupling on the achievable spectral efficiency of the MU
$\leftarrow$ SU back-reflection link. Specifically, we show the existence of a
cut-off bandwidth limit in the back-reflection MU $\leftarrow$ SU link and
introduce proper decoupling countermeasures.

Organization: The remainder of the present paper is organized as follows.
Section II describes the universal Snell’s law and introduces the system and
channel model. Section III outlines the principles of the considered STMM
temporal modulation, highlighting the space-time phase coupling and proposing
suitable decoupling methods. Section IV reports numerical simulations to
illustrate the performance of the proposed solutions. Section V concludes the
paper.

Notation: Bold upper- and lower-case letters denote matrices and column
vectors. The $(i,j)$-th entry of matrix $\mathbf{A}$ is denoted by
$[\mathbf{A}]_{i,j}$. Matrix transposition, conjugate transposition, and
Frobenius norm are denoted as $\mathbf{A}^{T}$, $\mathbf{A}^{H}$ and
$\|\mathbf{A}\|_{F}$, respectively. $\mathrm{diag}(\mathbf{A})$ denotes the
extraction of the diagonal of $\mathbf{A}$, while $\mathrm{diag}(\mathbf{a})$
is the diagonal matrix whose elements on the main diagonal are those of vector
$\mathbf{a}$. $\mathbf{I}_{n}$ denotes the identity matrix of size $n$.
$\mathbf{a}\sim\mathcal{CN}(\boldsymbol{\mu},\mathbf{C})$ denotes a multi-
variate circularly complex Gaussian random variable with mean
$\boldsymbol{\mu}$ and covariance $\mathbf{C}$. $\mathbb{E}[\cdot]$ is the
expectation operator, * denotes the convolution operator in the time domain,
and $\mathbb{R}$ and $\mathbb{C}$ stand for the set of real and complex
numbers, respectively. $\delta(t)$ is the Dirac delta function in time and
$\delta_{n}$ denotes the Kronecker delta function.

Figure 1: Full-duplex wireless communication system enabled by an STMM.

##  II System Model with STMM

Figure 2: Reference system.

Let us consider the wireless communication system depicted in Fig. 1, where an
MU establishes a full-duplex link with an SU. The MU is equipped with two
antenna arrays of $N$ elements each, while the SU is equipped with a planar
STMM of $M_{u}=M_{u,x}\times M_{u,y}$ elements, with $M_{u,x}$ and $M_{u,y}$
denoting the number of elements on the $x$-axis and $y$-axis, respectively,
and a receiving (Rx) antenna array of $M_{d}$ elements. The SU Rx is meant to
receive and decode the MU $\rightarrow$ SU signal, while the STMM is utilized
to modulate data onto the MU $\leftarrow$ SU link via back-reflection.

###  II-A The Universal Snell’s Law and the STMM

The universal Snell’s law is a generalization of the generalized Snell’s law
when dealing with both spatial and temporal phase gradients across a
metasurface. Let us consider the scheme depicted in Fig. 2, where a plane EM
wave at carrier frequency $f_{i}$ impinges on a planar STMM from direction
$(\phi_{i},\theta_{i})$, whose wavevector is denoted by $\mathbf{k}_{i}$. The
STMM, deployed on the $xy$ plane, is characterized by a space-time varying
reflection coefficient

$\Gamma(\mathbf{x},\boldsymbol{\vartheta},t)=\alpha(\boldsymbol{\vartheta})\;e^{j\beta(\mathbf{x},t)},$
(1)

where $\mathbf{x}=[x,y]^{T}$ is the generic position across the STMM and
$\beta(\mathbf{x},t)$ denote the time- and space-varying phase of the
reflection coefficient, and $\alpha(\boldsymbol{\vartheta})$ denotes the
amplitude of the reflection coefficient, which depends on the incident and
reflected angles
$\boldsymbol{\vartheta}=(\phi_{i},\theta_{i},\phi_{o},\theta_{o})$. The
reflected wave is characterized by the wavevector $\mathbf{k}_{o}$ and the
carrier frequency $f_{o}$, which, based on the universal Snell’s law, depends
on the incident EM wave as follows [9]:

$\displaystyle\mathbf{k}_{o}-\mathbf{k}_{i}$
$\displaystyle=\left[\frac{\beta(\mathbf{x},t)}{\partial{x}},\frac{\beta(\mathbf{x},t)}{\partial{y}},0\right]^{\mathrm{T}},$
(2) $\displaystyle f_{o}-f_{i}$
$\displaystyle=\frac{1}{2\pi}\frac{\beta(\mathbf{x},t)}{\partial{t}}.$ (3)

We note that a non-zero spatial gradient of the phase $\beta(\mathbf{x},t)$
changes the direction of reflection specified by the wavevector
$\mathbf{k}_{o}$, while a non-zero temporal gradient of the phase
$\beta(\mathbf{x},t)$ changes the carrier frequency $f_{o}$ of the reflected
EM wave.

###  II-B Signal Model

The time-continuous signal from the MU can be expressed as

$\mathbf{x}(t)=\mathbf{f}_{d}\;s_{d}(t)e^{j2\pi f_{i}t}$ (4)

where $\mathbf{f}_{d}\in\mathbb{C}^{N\times 1}$ is the spatial precoding
vector and $s_{d}(t)$ is the MU $\rightarrow$ SU time-continuous baseband
information signal with bandwidth $B_{d}$ and centered at the carrier
frequency $f_{i}$. The signal received at the SU can be expressed as

$\begin{split}y_{d}(t)&=\frac{1}{\sqrt{\varrho_{d}}}\,\mathbf{w}_{d}^{H}\mathbf{H}_{d}(t)*\mathbf{x}(t)+\mathbf{w}_{d}^{H}\mathbf{n}(t)\end{split}$
(5)

where $\varrho_{d}$ represents the MU $\rightarrow$ SU power path loss,
$\mathbf{w}_{d}\in\mathbb{C}^{N\times 1}$ is the SU spatial combiner,
$\mathbf{H}_{d}(t)\in\mathbb{C}^{M_{d}\times N}$ is the MU $\rightarrow$ SU
MIMO channel matrix, such that
$\mathrm{E}\left[\|\mathbf{H}_{d}(t)\|_{\mathrm{F}}^{2}\right]=NM_{d}$ while
$\mathbf{n}(t)\sim\mathcal{CN}(0,\sigma^{2}_{n}\mathbf{I}_{M_{d}})$ is the
additive noise, here assumed as temporally uncorrelated.

The back-reflected signal at the MU can be formulated as

$\begin{split}y_{u}(t)=\frac{1}{\sqrt{\varrho_{u}}}\mathbf{w}_{u}^{H}\mathbf{H}_{o}(t)*\boldsymbol{\Gamma}(\boldsymbol{\vartheta},t)\left(\mathbf{H}_{i}(t)*\mathbf{x}(t)\right)+\mathbf{w}_{u}^{H}\mathbf{z}(t)\end{split}$
(6)

where $\varrho_{u}$ is the MU $\rightarrow$ SU $\rightarrow$ MU power path
loss, $\mathbf{w}_{u}\in\mathbb{C}^{N\times 1}$ is the combiner at the MU,
$\mathbf{H}_{i}(t)\in\mathbb{C}^{M_{u}\times N}$ is the forward MIMO channel
between the MU and the STMM, $\mathbf{H}_{o}(t)\in\mathbb{C}^{N\times M_{u}}$
is the backward MIMO channel between the STMM and the MU,
$\mathbf{z}(t)\sim\mathcal{CN}(0,\sigma^{2}_{z}\mathbf{I}_{N})$ is the
additive noise, and
$\boldsymbol{\Gamma}(\boldsymbol{\vartheta},t)\in\mathbb{C}^{M_{u}\times
M_{u}}$ denotes the time-varying STMM reflection coefficient matrix

$\boldsymbol{\Gamma}(\boldsymbol{\vartheta},t)=\alpha(\boldsymbol{\vartheta})\;\mathrm{diag}\left(\left[e^{j\beta_{0}(t)},\cdots,e^{j\beta_{M_{u}-1}(t)}\right]\right),$
(7)

where
$\alpha(\boldsymbol{\vartheta})=2(2q+1)\cos^{2q}\left(\pi/2-\arcsin\left(\cos\theta\sin\phi\right)\right)$,
modeled as in [19], with $q$ being a parameter that depends on the size of the
RIS elements. Notice that, although
$\boldsymbol{\Gamma}(\boldsymbol{\vartheta},t)$ is a time-varying function,
the relation with the incident signal $\mathbf{H}_{i}(t)*\mathbf{x}(t)$ is
multiplicative because $\boldsymbol{\Gamma}(\boldsymbol{\vartheta},t)$ is the
reflection coefficient. It is worth underlining that, for a proper operation
of the wireless communication system, the knowledge of the signal $s_{d}(t)$
is required at the MU side, as the MU must remove $s_{d}(t)$ from $y_{u}(t)$
to obtain $\beta(t)$. For full-duplex systems such as the one in Fig. 1,
involving only two terminals, the latter condition is easily achieved, but in
other implementations, where the receiver of $\beta(t)$ is not the MU,
synchronization techniques shall be applied (not covered here).

###  II-C Channel Model

The $(m,n)$-th entry of any of the channel impulse responses in (5)-(6) can be
written following the millimeter wave cluster-based channel model as follows
[20]:

$\displaystyle[\mathbf{H}(t)]_{m,n}$
$\displaystyle=\sum_{p=1}^{P}\xi_{p}\,\delta\left(t-\tau_{p}-\Delta\tau_{p,n}-\Delta\tau_{p,m}\right)$
(8)

where (i) $P$ is the number of paths, (ii)
$\xi_{p}\sim\mathcal{CN}\left(0,\sigma_{p}^{2}\right)$ is the scattering
amplitude of $p$-th path, such that $\sum_{p=1}^{P}\sigma_{p}^{2}=1$, (iii)
$\tau_{p}$ is the propagation delay of the $p$-th path from the phase center
of the Tx to the phase center of the Rx, (iv) $\Delta\tau_{p,n}$ and
$\Delta\tau_{p,m}$ are the excess propagation delays due to the position of
the $n$-th Tx element and the $m$-th Rx element w.r.t. to their phase centers.

As common for communication systems operating through back-scattering and
radar systems [21], the two-way channel to/from the STMM is characterized by a
single dominant path, i.e., $P=1$ for $\mathbf{H}_{i}(t)$ and
$\mathbf{H}_{o}(t)$. Hence, we have a common propagation delay $\tau=D/c$,
where $D$ is the MU-SU distance, and excess delays at the STMM that depend on
the incidence and reflection angles $\theta=\theta_{o}=\theta_{i}$,
$\phi=\phi_{o}=\phi_{i}$, which are coincident for full-duplex settings. The
inter-element spacing of Tx and Rx arrays (at both MU and SU) is
$\lambda_{i}/2$, while at STMM is $\lambda_{i}/4$.

The propagation path losses in power, $\varrho_{d}$ and $\varrho_{u}$ in
(5)-(6) are modeled as [22]

$\varrho_{d}=\frac{2^{4}\pi
D^{2}}{\lambda_{i}^{2}},\quad\quad\varrho_{u}=\frac{2^{12}\pi
D^{4}}{\lambda_{i}^{4}}.$ (9)

where we assume that (i) the inter-element spacing at the STMM is
$\lambda_{i}/4$, while for the other arrays is $\lambda_{i}/2$ and (ii) the
effective area of the MU/SU arrays (and STMM) is equal to the physical one,
which is $N(\lambda_{i}/2)^{2}$ and $M_{u}(\lambda_{i}/4)^{2}$ [22].

##  III Temporal Modulation

Figure 3: Representation of the proposed time-modulated RIS, with a wideband
tunable element (e.g., fast varactor diode) for a cluster of $M_{u}^{\prime}$
meta-atoms and narrow band tunable elements (e.g., pin-diodes) for each meta-
atom.

This section defines the principles of temporal modulation at the STMM and its
peculiarities. For the implementation of the STMM, we consider the
architecture in Fig. 3, where the $M_{u}$ STMM elements are clustered in
$K^{2}$ equal and non-overlapping subsets, each comprising

$M^{\prime}_{u,x}=\frac{M_{u,x}}{K},\qquad M^{\prime}_{u,y}=\frac{M_{u,y}}{K}$
(10)

elements each along $x$ and $y$. Within the $k$-th cluster, $k=1,...,K^{2}$,
the elements can generate a spatial phase component (different for each
element) and a temporal phase component (common to all elements). Considering
$K^{2}=1$ and $K^{2}=M_{u}$ leads to the architectures described in our
previous work [18], that is here generalized to a hybrid STMM. Reducing
$K^{2}$ means minimizing the cost/complexity of the STMM, while increasing
$K^{2}$ leads to a flexible but expensive architecture (see [23] for further
details). To ease the derivation while maintaining the generality, we consider
the MU to use precoding and combining vectors perfectly aligned with the SU.
Thus, we have that $\mathbf{f}_{d}$ and $\mathbf{w}_{u}$ are given, e.g.,
estimated by conventional approaches [24].

###  III-A Space-Time Phase Coupling

Let us consider the phase signal (7) applied at the $(q,v)$-th element of the
STMM as the superposition of a spatial and a temporal component:

$\beta_{q,v}(t)=\varphi_{q,v}+\gamma(t),$ (11)

for $q=0,...,M_{u,x}-1$, $v=0,...,M_{u,y}-1$, where $\varphi_{q,v}$ is the
space component of the phase used to design a complete back-reflection of the
impinging signal and $\gamma(t)$ is an information-bearing phase signal
applied at each STMM element, and common to all. Here, we assume to apply the
same $\gamma(t)$ across the entire STMM to describe the coupling between the
spatial and temporal phase gradients.

$\begin{split}y_{u}(t)&=\rho\;\alpha(\theta,\phi)\,\sum_{q,v}e^{-j\left(\pi(q\cos\theta\cos\phi+v\cos\theta\sin\phi)-\varphi_{q,v}-\gamma(t-\Delta\tau_{q,v}-\tau)\right)\,h_{u}(t)}s_{d}(t-2\tau)+z(t)=\rho\,h_{u}(t)s_{d}(t-2\tau)+z(t)\overset{(a)}{\approx}\\\
&\overset{(a)}{\approx}\rho\;\alpha(\theta,\phi)\sum_{q,v}e^{-j\left(\pi(q\cos\theta\cos\phi+v\cos\theta\sin\phi)-\varphi_{q,v}\right)}e^{j\gamma(t-\tau)}s_{d}(t-2\tau)+z(t)\end{split}$
(12)

The model of the Rx signal at the MU, reported in (12) can be obtained by
substituting (11) in (6), using the channel model (8) and assuming that there
are no spatially wideband effects at the STMM due to the MU $\rightarrow$ SU
signal, namely $s_{d}(t-2\Delta T)\approx s_{d}(t)$, where $\Delta T$ is the
maximum excess delay across the STMM elements.

In (12), factor $\rho=N^{2}\xi_{i}\xi_{o}/\sqrt{\varrho_{u}}$ accounts for
geometrical energy losses, while

$\Delta\tau_{q,v}=q\underbrace{\frac{\lambda_{i}}{4}\frac{\cos\theta\cos\phi}{c}}_{\Delta\tau_{x}}+v\underbrace{\frac{\lambda_{i}}{4}\frac{\cos\theta\sin\phi}{c}}_{\Delta\tau_{y}}$
(13)

is the excess propagation delay for the $(q,v)$-th STMM element. In this
setting, unwanted beam squinting from spatially wideband effects due to
$s_{d}(t)$ can be avoided (see [25] for details) and the MU $\rightarrow$ SU
signal undergoes a multiplicative channel $h_{u}(t)$ that encodes the MU
$\leftarrow$ SU phase signal $\gamma(t)$. As demonstrated in [18], it is

$\mathbb{E}_{\gamma}\left[\lvert h_{u}(t)\rvert^{2}\right]\leq M_{u}^{2}.$
(14)

except for $\gamma(t)=\mathrm{const}$ (straightforward condition) or
$\Delta\tau_{x}=\Delta\tau_{y}=0$ (perpendicular incidence on the STMM, i.e.,
$\theta=\pi/2$). This effect is referred here as space-time phase coupling and
detrimentally affects the Rx signal $y_{u}(t)$, as shown in Section III-B.

Approximation $(a)$ in (12) is subtends that the MU $\leftarrow$ SU phase-only
signal does not suffer the relative propagation delay across the STMM, thus
$\gamma(t-\Delta T)\approx\gamma(t)$, or equivalently, $\Delta T\ll T_{u}$
where $T_{u}$ is the symbol period of the MU $\leftarrow$ SU phase signal
$\gamma(t)$. Approximation $(a)$ is typically assumed in the existing
literature on STMM, but it is valid in restricted settings (e.g.,
$\theta=\pi/2$ $\phi=0$, as in [12]). Under $(a)$, the bandwidth of the MU
$\leftarrow$ SU Rx signal signal $y_{u}(t)$ in (6) is

$B_{tot}=B_{d}+B_{u}$ (15)

with $B_{u}$ being the bandwidth of $e^{j\gamma(t)}$, which is a generic phase
modulated signal [26]. Notice that the spectrum of $y_{u}(t)$ is centered
around the carrier frequency $f_{i}$. This holds for common information-
bearing signals $\gamma(t)$ whose average time-derivative over time is zero
(thus the net frequency shift is zero). In general, however, the coupling
between spatial and temporal phase patterns for $\theta\neq\pi/2$ cannot be
neglected for arbitrary MU $\leftarrow$ SU bandwidths, and being peculiar to
STMM-based wireless systems, is analyzed herein.

###  III-B Effect of Space-Time Phase Coupling

Figure 4: Normalized reflection loss in presence of space-time phase coupling
considering different angles of incidence and an STMM size of $100\times 100$
elements.

Inequality (14) implies that any phase-encoded modulation signal $\gamma(t)$
leads to a decrease in the reflection gain, except for very low MU
$\leftarrow$ SU signal bandwidth (approximation $(b)$ in (12)) or
$\theta=\pi/2$. The effect of such a space-time coupling phenomenon is due to
an unwanted beam squinting, which can be demonstrated by considering the
first-order Taylor expansion of $\gamma(t)$ around $t=t_{0}$:

$\begin{split}\gamma(t_{0}-\Delta\tau_{q,v})\approx\gamma(t_{0})-\dot{\gamma}(t_{0})\Delta\tau_{q,v}.\end{split}$
(16)

where $\dot{\gamma}(t)$ is the time derivative of $\gamma(t)$. The second term
is a linear phase shift that causes a drift in the angle of maximum reflection
w.r.t. the desired one $(\theta,\phi)$. To quantitatively gain insight into
this phenomenon, let us consider a simple linear phase shift $\gamma(t)=2\pi
f_{s}t$ (e.g., as for one symbol of a frequency shift keying (FSK)
modulation), where $f_{s}=f_{i}-f_{o}=\kappa f_{i}$ is the imposed frequency
shift. The normalized array factor of the STMM is

$AF(\theta,\phi,\kappa)=\frac{1}{M_{u}}\sum_{q=0}^{M_{u,x}-1}\sum_{v=0}^{M_{u,y}-1}e^{j2\pi
f_{i}\kappa(t-\Delta t_{q,v})}.$ (17)

Figure 4 depicts the normalized reflection loss varying the MU $\leftarrow$ SU
signal bandwidth $B_{u}$ and considering different azimuth angles of
incidence, and assuming the elevation as $\phi=0$. As can be observed, when
the bandwidth $B_{u}$ increases for incidence angles $\theta_{i}\neq\pi/2$,
the space-time coupling will cause a loss in the reflection gain and
subsequently in the performances of the system.

The loss observed in Fig. 4 is due to the tilting of the angle of maximum
reflection, which can be evaluated as

$\overline{\theta}=\arccos\left[(1+\kappa)\cos\theta\right]$ (18)

where $\overline{\theta}\neq\theta$ except for $\kappa=0$. Notice that for
$|(1+\kappa)\cos\theta|>1$ in (18) we have evanescent waves. It is clear that
to implement a wideband wireless communication system using STMM, the spatial
phase must be decoupled from the temporal one, as described in subsection
III-C.

###  III-C Space-Time Phase Decoupling

Decoupling the spatial phase from the temporal one can be achieved differently
depending on the specific STMM architecture. In the general case in which
$K^{2}<M_{u}$ (and often $K^{2}\ll M_{u}$), the decoupling is made for the
$k$-th cluster of elements as follows:

$\beta_{q,v}(t)=\varphi_{q,v}+\gamma(t+\Delta\tau_{k})-\dot{\gamma}(t+\Delta\tau_{k})\left(\Delta\tau_{q,v}+\Delta\tau_{k}\right)$
(19)

where $\Delta\tau_{k}$ is the excess propagation delay for the $k$-th cluster
center w.r.t. the STMM phase center. If $K^{2}=M_{u}$, the decoupling
simplifies to $\beta_{q,v}(t)=\varphi_{q,v}+\gamma(t+\Delta\tau_{q,v})$.
Expression (19) is derived from (16) applied to the $k$-th cluster, and allows
compensating for the first time-derivative of the information signal
$\gamma(t)$, i.e., the instantaneous frequency shifts.

##  IV Numerical Results

We show numerical results illustrating the effects of space-time phase
coupling on the MU $\leftarrow$ SU spectral efficiency, and the benefits of
the proposed decoupling. The goal is to provide insights on upper achievable
performance, operating conditions, and possible limitations. In all the
following, the frequency of operation is $f_{0}=30$ GHz, link length is
$D=100$ m, transmitted power by the MU is $20$ dBm, the noise power spectral
density is $N_{0}=-173$ dBm/Hz, and the STMM size is $100\times 100$ elements.
We consider a continuous phase-frequency shift keying (CP-FSK) modulation with
modulation index $h=1$. The $99\%$ of the signal energy is within
$B_{u}=2/T_{u}$ [27], and a fixed total system bandwidth of $B_{tot}=5$ GHz,
split between $B_{d}$ and $B_{u}$. The trends and considerations are the same
for a generic phase/frequency modulation, but the absolute values must be
derived case by case.

We evaluate the total unconstrained spectral efficiency of the MU
$\rightleftarrows$ SU link, that can be expressed as follows:

$\begin{split}\eta=\mu_{u}\log_{2}(1+\mathrm{SNR}_{u})+(1-\mu_{u})\log_{2}(1+\mathrm{SNR}_{d})\end{split}$
(20)

where $\mu_{u}=B_{u}/B_{tot}$, while $\mathrm{SNR}_{u}$ and $\mathrm{SNR}_{d}$
are the MU $\leftarrow$ SU and MU $\rightarrow$ SU signal-to-noise ratio (SNR)
at the decision variable, respectively. The $\mathrm{SNR}_{d}$ is generally
expressed as

$\mathrm{SNR}_{d}\leq\frac{\sigma_{s,d}^{2}NM_{d}}{\varrho_{d}\sigma_{z}^{2}}$
(21)

while $\mathrm{SNR}_{u}$ is upper-bounded by

$\mathrm{SNR}_{u}\leq\frac{\sigma_{s,d}^{2}N^{2}M_{u}^{2}}{\varrho_{u}\sigma^{2}_{z}}|AF(\theta,\phi,\kappa)|^{2}T_{u}B_{tot}$
(22)

where the equality holds when perfect channel state information is available
and optimal precoding/combing is employed, which both provide the maximum MIMO
gain, i.e., $NM_{d}$, and $|AF(\theta,\phi,\kappa)|^{2}\leq 1$ is the
reflection loss due to the space-time phase coupling. The expression (22) is
obtained considering a matched filtering approach at the MU side over the MU
$\leftarrow$ SU symbol duration $T_{u}$, aimed at estimating the phase signal
$\gamma(t)$. The matched filter gain is $T_{u}B_{tot}$. For the system
depicted in Fig. 1, we can assume the MU knows the MU $\rightarrow$ SU signal
$s_{d}(t)$ and has correctly performed the timing recovery to estimate the
macroscopic delay $\tau$. The analytical expression of the true
$\mathrm{SNR}_{u}$ is derived in our work [18].

Figure 5: Total Achievable spectral efficiency varying the uplink bandwidth
$B_{u}$, for an azimuth incidence angle of $\theta_{i}=30$ [deg], and
considering a different number of clusters $K$. Figure 6: Total Achievable
spectral efficiency varying the azimuth incidence angle $\theta_{i}$, for an
uplink bandwidth of $B_{u}=4$ GHz, and considering a different number of
clusters $K$.

Figure 5 depicts the total unconstrained spectral efficiency of the system
varying the uplink bandwidth $B_{u}$. The blue curve shows the performance
achieved when perfectly compensating the coupling, i.e.,
$|AF(\theta,\phi,\kappa)|^{2}=1$, $\forall\theta,\phi$ and $\kappa$. This
result can be achieved if $K^{2}=M_{u}$ and by applying (19). It is
interesting to observe that there is an optimal uplink bandwidth
$B_{u,opt}\approx 1$ GHz, which depends on the tradeoff between the pathloss
$\varrho_{u}$, the processing gain $T_{u}B_{tot}$, and the size of the STMM
$M_{u}$. The red curve depicts the system’s performance when the space-time
coupling is not compensated, which drops dramatically as the uplink bandwidth
$B_{u}$ increases. The black curves show the performance when compensating the
space-time coupling with a limited number of clusters $K^{2}$. The main
takeaway is that when the uplink bandwidth $B_{u}$ increases more clusters
$K^{2}$ are necessary to maintain optimal performances.

The impact of the azimuth angle of incidence $\theta_{i}$ is depicted in Fig.
6 given an uplink bandwidth of $B_{u}=4$ GHz. Without space-time coupling
compensation (red line), as the angle of incidence becomes grazing we observe
a rapid decay in achievable spectral efficiency. The blue line, which refers
to the perfectly compensated coupling, is influenced only by the loss due to
the reduced reflectivity of the RIS elements, i.e., the term
$\alpha(\boldsymbol{\vartheta})$. Again, we observe that as the number of
clusters $K$ increases, the space-time decoupling is more robust, which
highlights the validity of the method proposed.

##  V Conclusion

The paper analyzes the space-time phase coupling arising in STMM-based
wireless communication systems, where a MU equipping a full-duplex transceiver
is transmitting an informative signal toward a SU, that back-reflects its
information by modulating the impinging signal with the STMM. The analytical
findings show that the space-time coupling depends on the direction of
incidence, the bandwidth of the SU’s informative signal, and the size and type
of the STMM. A method for space-time phase decoupling is then proposed and
validated through simulations.

## References

  * [1] M. Di Renzo, A. Zappone, M. Debbah, M.-S. Alouini, C. Yuen, J. De Rosny, and S. Tretyakov, “Smart radio environments empowered by reconfigurable intelligent surfaces: How it works, state of research, and the road ahead,” _IEEE Journal on Selected Areas in Communications_ , vol. 38, no. 11, pp. 2450–2525, 2020.
  * [2] A. M. Elbir, K. V. Mishra, M. R. B. Shankar, and S. Chatzinotas, “The rise of intelligent reflecting surfaces in integrated sensing and communications paradigms,” _IEEE Network_ , pp. 1–8, 2022.
  * [3] L. Jiao, P. Wang, A. Alipour-Fanid, H. Zeng, and K. Zeng, “Enabling efficient blockage-aware handover in ris-assisted mmwave cellular networks,” _IEEE Transactions on Wireless Communications_ , pp. 1–1, 2021.
  * [4] M. Mizmizi, R. A. Ayoubi, D. Tagliaferri, K. Dong, G. G. Gentili, and U. Spagnolini, “Conformal metasurfaces: a novel solution for vehicular communications,” _IEEE Transactions on Wireless Communications_ , pp. 1–1, 2022.
  * [5] Y. U. Ozcan, O. Ozdemir, and G. K. Kurt, “Reconfigurable intelligent surfaces for the connectivity of autonomous vehicles,” _IEEE Transactions on Vehicular Technology_ , vol. 70, no. 3, pp. 2508–2513, 2021.
  * [6] S. Buzzi, E. Grossi, M. Lops, and L. Venturino, “Foundations of mimo radar detection aided by reconfigurable intelligent surfaces,” _IEEE Transactions on Signal Processing_ , vol. 70, pp. 1749–1763, 2022.
  * [7] N. Yu, P. Genevet, M. A. Kats, F. Aieta, J.-P. Tetienne, F. Capasso, and Z. Gaburro, “Light propagation with phase discontinuities: Generalized laws of reflection and refraction,” _Science_ , vol. 334, no. 6054, pp. 333–337, 2011. [Online]. Available: https://www.science.org/doi/abs/10.1126/science.1210713
  * [8] A. Shaltout, A. Kildishev, and V. Shalaev, “Time-varying metasurfaces and lorentz non-reciprocity,” _Optical Materials Express_ , vol. 5, no. 11, pp. 2459–2467, 2015.
  * [9] L. Zhang, X. Q. Chen, S. Liu, Q. Zhang, J. Zhao, J. Y. Dai, G. D. Bai, X. Wan, Q. Cheng, G. Castaldi, V. Galdi, and T. J. Cui, “Space-time-coding digital metasurfaces,” _Nature Communications_ , vol. 9, no. 1, p. 4334, Oct 2018\.
  * [10] S. Taravati and G. V. Eleftheriades, “Microwave space-time-modulated metasurfaces,” _ACS Photonics_ , vol. 9, no. 2, pp. 305–318, 2022.
  * [11] G.-B. Wu, J. Dai, Q. Cheng, T. Cui, and C. Chan, “Sideband-free space–time-coding metasurface antennas,” _Nature Electronics_ , vol. 5, no. 11, p. 808–819, Nov. 2022.
  * [12] W. Tang, J. Y. Dai, M. Z. Chen, K.-K. Wong, X. Li, X. Zhao, S. Jin, Q. Cheng, and T. J. Cui, “Mimo transmission through reconfigurable intelligent surface: System design, analysis, and implementation,” _IEEE Journal on Selected Areas in Communications_ , vol. 38, no. 11, pp. 2683–2699, 2020.
  * [13] J. Y. Dai, W. Tang, L. X. Yang, X. Li, M. Z. Chen, J. C. Ke, Q. Cheng, S. Jin, and T. J. Cui, “Realization of multi-modulation schemes for wireless communication by time-domain digital coding metasurface,” _IEEE Transactions on Antennas and Propagation_ , vol. 68, no. 3, pp. 1618–1627, 2020\.
  * [14] R. Karasik, O. Simeone, M. D. Renzo, and S. Shamai Shitz, “Adaptive coding and channel shaping through reconfigurable intelligent surfaces: An information-theoretic analysis,” _IEEE Transactions on Communications_ , vol. 69, no. 11, pp. 7320–7334, 2021.
  * [15] S. Lin, F. Chen, M. Wen, Y. Feng, and M. Di Renzo, “Reconfigurable intelligent surface-aided quadrature reflection modulation for simultaneous passive beamforming and information transfer,” _IEEE Transactions on Wireless Communications_ , vol. 21, no. 3, pp. 1469–1481, 2022.
  * [16] R. Fara, D.-T. Phan-Huy, P. Ratajczak, A. Ourir, M. Di Renzo, and J. De Rosny, “Reconfigurable intelligent surface-assisted ambient backscatter communications – experimental assessment,” in _2021 IEEE International Conference on Communications Workshops (ICC Workshops)_ , 2021, pp. 1–7.
  * [17] R. Fara, P. Ratajczak, D.-T. Phan-Huy, A. Ourir, M. Di Renzo, and J. de Rosny, “A prototype of reconfigurable intelligent surface with continuous control of the reflection phase,” _IEEE Wireless Communications_ , vol. 29, no. 1, pp. 70–77, 2022.
  * [18] M. Mizmizi, D. Tagliaferri, and U. Spagnolini, “Wireless communications with space-time modulated metasurfaces,” 2023. [Online]. Available: https://arxiv.org/abs/2302.08310
  * [19] S. W. Ellingson, “Path loss in reconfigurable intelligent surface-enabled channels,” in _2021 IEEE 32nd Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)_ , 2021, pp. 829–835.
  * [20] T. S. Rappaport, Y. Xing, O. Kanhere, S. Ju, A. Madanayake, S. Mandal, A. Alkhateeb, and G. C. Trichopoulos, “Wireless communications and applications above 100 ghz: Opportunities and challenges for 6g and beyond,” _IEEE access_ , vol. 7, pp. 78 729–78 757, 2019.
  * [21] M. Manzoni, D. Tagliaferri, M. Rizzi, S. Tebaldini, A. V. Monti-Guarnieri, C. M. Prati, M. Nicoli, I. Russo, S. Duque, C. Mazzucco, and U. Spagnolini, “Motion estimation and compensation in automotive mimo sar,” 2022.
  * [22] F. H. Danufane, M. D. Renzo, J. de Rosny, and S. Tretyakov, “On the path-loss of reconfigurable intelligent surfaces: An approach based on green’s theorem applied to vector fields,” _IEEE Transactions on Communications_ , vol. 69, no. 8, pp. 5573–5592, 2021.
  * [23] A. Rafique, N. U. Hassan, M. Zubair, I. H. Naqvi, M. Q. Mehmood, C. Yuen, M. D. Renzo, and M. Debbah, “Reconfigurable intelligent surfaces: Interplay of unit-cell- and surface-level design and performance under quantifiable benchmarks,” 2023.
  * [24] M. Mizmizi, D. Tagliaferri, D. Badini, C. Mazzucco, and U. Spagnolini, “Channel estimation for 6g v2x hybrid systems using multi-vehicular learning,” _IEEE Access_ , vol. 9, pp. 95 775–95 790, 2021.
  * [25] K. Dovelos, M. Matthaiou, H. Q. Ngo, and B. Bellalta, “Channel estimation and hybrid combining for wideband terahertz massive mimo systems,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 6, pp. 1604–1620, 2021\.
  * [26] J. B. Anderson, T. Aulin, and C.-E. Sundberg, _Digital phase modulation_. Springer Science & Business Media, 2013.
  * [27] C.-H. Kuo and K. M. Chugg, “On the bandwidth efficiency of cpm signals,” in _IEEE MILCOM 2004. Military Communications Conference, 2004._ , vol. 1. IEEE, 2004, pp. 218–224.