# Structural Controllability of Drift-free Bilinear Systems on the Special
Euclidean Group

A. Sanand Amita Dilip<EMAIL_ADDRESS>Chirayu D. Athalye
<EMAIL_ADDRESS>Department of Electrical Engineering, IIT Kharagpur
Department of Electrical Engineering, BITS Goa

###### Abstract

We obtain graph theoretic necessary and sufficient conditions for the
structural controllability of drift free bilinear systems on the special
Euclidean group leveraging results from the existing literature. The graph
theoretic conditions allow us to check the structural controllability in
polynomial time. We use these conditions to find the sparsest structures for
structural controllability. These conditions can also be used to check the
structural accessibility of bilinear systems with drift. Equivalent conditions
using the permutation group are also obtained. We consider the problem of link
failures within a given structure and obtain equivalent conditions for
structural controllability which are polynomial time checkable. We show that
the problem of finding sparsest structures under $k$ link failures is NP-hard
for $k>0$. We also discuss the case of structural controllability under
probabilistic link failures.

###### keywords:

Structural controlBilinear systemsLie groups and Lie algebras Graph theory
Combinatorial methodsSparsityComputational complexity.

††thanks: Corresponding author A. Sanand Amita Dilip.

, ,

##  1 Introduction

While modeling, numerical entries of the system models are not known exactly.
It may happen that with a small numerical perturbation of models, some system
properties are lost. In networked systems, the weights of the links in the
network are not known exactly. To avoid numerical issues (or if the precise
numerical values are not available), one studies structural properties of the
underlying system. Structural controllability is one such property which is
generic i.e., true for almost all numerical realizations [Boothby1, Glover,
Lin]. The structure of zero and nonzero entries in the model might be due to
inherent structure of the underlying systems such as RC circuits or
interconnections of subsystems present in the original system [Ramos]. The
interconnection pattern is determined by the interacting subsystems e.g., in
multi-agent systems and other complex systems [Liu]. The presence or absense
of this interconnecting link is more important than its numerical value.
Structural controllability for linear time invariant systems was first
introduced in [Lin] where a graph theoretic characterisation was obtained (and
later extended by [Shields] for multi-input systems). Graph theoretic methods
provide an elegant way of analyzing such structural properties where the graph
construction depends only on the zero/nonzero pattern in the system matrices.
We refer the reader to the survey papers [Dion, Ramos] and the references
therein for a detailed discussion on the structural controllability and the
allied problems in general. Article [Liu] discusses linear and nonlinear
control topics, complex networks as well as structural controllability and
observability and various applications. Controllability of nonlinear systems
was first characterized in seminal works of [JurdSuss1, JurdSuss, Brockett,
Brockett1]. Bilinear systems on Lie groups were studied in [Brockett,
Brockett1]. Some early works on the control of bilinear systems include
[Boothby, Boothby1]. For further details, we refer the reader to [Elliot].
Bilinear system models are useful in biology [Williamson], quantum control
[Boussaid], and so on. Whereas, control systems over the special Euclidean
group appear in the synchronization and coordination problems [Sarlette], the
distributed control of rigid bodies [Ibuki] and so on. In this article, we
study the structural controllability of bilinear systems on $\mathbb{SE}(n)$
using graph theory.

Graph theoretic methods are quite common in the study of linear systems,
complex systems, multi-agent systems and so on and are used regularly in
studying structural properties of these systems as well [Dion, Ramos, Liu,
van, monshi, Trefois]. Recently, they are being used in studying both
structural and non structural properties of bilinear systems as well [Tsope,
cz, Wang, Zhang, Gharesifard, Ghosh1]. Graph theoretic characterization of
(non structural) controllability on Lie groups was done in [cz, Wang, Zhang].
In [cz, Zhang], combinatorial characterization of controllability of systems
on the Lie group $\mathbb{SO}(n)$ was obtained but the structural
controllability was not studied. Combinatorial controllability
characterization over $\mathbb{SE}(n)$ was done in [Zhang1]. In [Wang], graph
theoretic characterization of controllability and accessibility of systems
over Lie groups $\mathbb{SO}(n),\mathbb{GL}(n),\mathbb{SL}(n)$ was obtained.
The main advantage of the graph theoretic conditions is the reduced
computational cost of checking the Lie algebraic rank conditions.

Tsopelakos et, al. [Tsope] consider drift-free bilinear systems on
$\mathbb{R}^{n}$ of the form

$\dot{\mathbf{x}}=\bigg{(}\sum_{i=1}^{m}u_{i}B_{i}\bigg{)}\mathbf{x},$

where $B_{i}$s are $n\times n$ structured matrices which belong to the Lie
algebra $\mathcal{GL}(n),\mathcal{SL}(n),\mathcal{SO}(n)$ of Lie groups
$\mathbb{GL}(n),\mathbb{SL}(n),\mathbb{SO}(n)$ respectively. The necessary and
sufficient conditions for structural controllability were obtained using graph
theoretic methods. Two separate cases were considered where in the first case,
all matrices $B_{i}$ belong to the same structured class; and in the second
case, they belong to different structured classes. The results were also
extended for structural accessibility. Tsopelakos et, al. [Tsope] also
consider the minimum controllability problem on these systems and gave a
probability one algorithm for the same.

Motivated by the results of [Tsope], we study the structural controllability
problem for drift-free bilinear systems on $\mathbb{SE}(n)$ using graphs and
obtain an analogous graph theoretic characterization (Theorem 2). Such a graph
based characterization is not studied in the literature for $\mathbb{SE}(n)$
to the best of our knowledge. This allows us to characterize the sparsest
pattern required for structural controllability. The existing algorithms on
graph theory literature ([West, klein]) can be used to check the structural
controllability of these driftless bilinear systems efficiently. Furthermore,
we give another combinatorial characterization of controllability using
permutation groups.

Combinatorial problems involving structural controllability for LTI systems
have been studied in [Olshevsky, Pequito, Moothedath]. Link failures are
common in communication networks [yang] and consequently in networked control
as well [Newman, Latora, Jafari, Rahimian, Ramos1]. Structural controllability
of multi-agent systems under communication link failures is considered in
[Jafari, Rahimian] whereas structural controllability of power systems under
transmission line failures is studied in [Ramos1]. We consider the case of
link failures in structured bilinear system over $\mathbb{SE}(n)$ and give
equivalent conditions for structural controllability. Furthermore, we also
consider the problem of finding the sparset pattern subject to maintaining
structural controllability in the presence of $k$ link failures. The sparsity
becomes important in large scale systems and also when there are costs
associated with the nonzero entries of the pattern matrix
$\mathcal{B}_{\Lambda}$. We consider both deterministic and probabilistic case
of link failures.

The paper is organized as follows. In the next section, we introduce
preliminaries and the problem formulation. In Section 3, we give graph
theoretic characterization of structural controllability on $\mathbb{SE}(n)$.
In Section 4, we consider some sparsity optimization problems and the problem
of structural controllability under link failures followed by discussion in
Section 5. Proofs of Theorem 2 and Theorem 9 are deferred in the Appendix.
Notation: $\mathbb{R},\mathbb{R}^{n},\mathbb{R}^{n\times n}$ denote the set of
real numbers, $n-$dimensional real vector space and the vector space of
$n\times n$ real matrices respectively. Matrices/vectors/scalars are denoted
by capital/bold-face/small letters. Lie groups are denoted by $\mathbb{LG}$
and the corresponding Lie algebra by $\mathcal{LG}$.
$\mathbb{GL}(n),\mathbb{SL}(n),\mathbb{SO}(n),\\\ \mathbb{SE}(n)$ denote
general linear, special linear, special orthogonal and special Euclidean
groups respectively, and
$\mathcal{GL}(n),\mathcal{SL}(n),\mathcal{SO}(n),\mathcal{SE}(n)$ their
respective Lie algebras. $\mathcal{G}(V,E)$ denotes a graph with $V$ as the
vertex set and $E$ as the edge set. The complete graph of $n$ vertices is
denoted by $\mathcal{K}_{n}$. The set of structured matrices with nonzero
pattern $\Lambda$ is denoted as $\mathcal{B}_{\Lambda}$. The entries of
structured matrices taking arbitrary real values are denoted by $\star$. The
$l_{0}-$norm is denoted by $\|.\|_{0}$.

##  2 Preliminaries and Problem formulation

###  2.1 Problem Formulation

We consider drift free bilinear control systems ([Elliot]) of the form

$\dot{X}=\bigg{(}\sum_{i=1}^{m}u_{i}B_{i}\bigg{)}X,\;X(0)=I$ (1)

where $X\in\mathbb{LG}(n)$ and $B_{i}\in\mathcal{LG}(n)$. For structured
systems, $B_{i}\in\mathcal{B}_{\Lambda}\subset\mathcal{LG}(n)$ where
$\mathcal{B}_{\Lambda}$ is the set of structured matrices with entries
specified by $\Lambda\subset\\{1,2,\ldots,n\\}\times\\{1,2,\ldots,n\\}$ being
arbitrary real numbers with the remaining entries fixed to zero. In other
words, $\Lambda$ determines the zero pattern of $\mathcal{B}_{\Lambda}$. Note
that the state variables are given by $X_{ij}$. The structure $\Lambda$
corresponds to the interaction/non interaction pattern among these state
variables for example in networked systems dynamics. (Instead of the exact
numerical values, only the interconnection pattern is known.)

The Lie algebra $\mathcal{LG}$ of a matrix Lie group $\mathbb{LG}$ is a vector
space closed under the Lie bracket operation defined as
$[A_{1},A_{2}]:=A_{1}A_{2}-A_{2}A_{1}$, $A_{1},A_{2}\in\mathcal{LG}$. If
$A_{1},\ldots,A_{k}\in\mathcal{LG}$, then the vector space generated repeated
by Lie bracket operation is called the Lie subalgebra generated by
$A_{1},\ldots,A_{k}$. For details on Lie groups and Lie algebras, we refer the
reader to [Hall]. The necessary and sufficient condition for controllability
of driftless systems on Lie groups via Lie algebra is given by Theorem $7.1$
of [JurdSuss].

###### Theorem 1

([JurdSuss]) For a drift free control system (1) on a Lie group
$\mathbb{LG}(n)$, the system is controllable $\Leftrightarrow$ the associated
Lie subalgebra generated by $\\{B_{1},\ldots,B_{m}\\}$ is the Lie algebra
$\mathcal{LG}(n)$.

This condition is known in the literature as the Lie algebraic rank condition
(LARC).

######  Definition 1 (Structural controllability)

[Tsope] The pattern $\mathcal{B}_{\Lambda}$ is said to be structurally
controllable if there exists $m\geq 1,m\in\mathbb{Z}$ such that (1) is
controllable for at least one numerical realization of $B_{i}$, $(1\leq i\leq
m)$. If such an $m$ exists such that (1) is controllable, then we call
$\mathcal{B}_{\Lambda}$ $m-$structurally controllable.

Thus, for $\mathcal{B}_{\Lambda}$ to be $m-$structurally controllable, the
LARC condition given by Theorem 1 must be satisfied for at least one numerical
realization of $B_{i},(1\leq i\leq m)$. Note that if the system (1) is
$m-$structurally controllable, then it is controllable for almost all
numerical realizations of $B_{i},(1\leq i\leq m)$.

###### Problem 1

Find graph theoretic necessary and sufficient conditions for $m-$ structural
controllability of (1) evolving on $\mathbb{SE}(n)$ for a given pattern
$\Lambda$.

We now consider a design problem as follows. Each nonzero entry of
$B_{\Lambda}$ corresponds to an interconnection between state variables.
Suppose there is a cost associated with each nonzero entry in the pattern
matrix $\mathcal{B}_{\Lambda}$. Consider the following uniform cost matrix

$\displaystyle C(i,j):=\begin{cases}1&\text{ if }1\leq i\leq n,1\leq j\leq
n+1,i\neq j\\\ 0&\text{ if }i=j,1\leq i,j\leq n+1\\\ 0&\text{ if }i=n+1,1\leq
j\leq n.\\\ \end{cases}$ (2)

Note that the cost matrix $C$ is consistent with the structure of
$\mathcal{SE}(n)$. Consider the problem of designing a pattern $\Lambda$
minimizing the cost associated with $\mathcal{B}_{\Lambda}$. Due to the
uniform cost in (2), this is equivalent to minimizing the
$\|\mathcal{B}_{\Lambda}\|_{0}$ (i.e., the number of nonzero entries of
$\mathcal{B}_{\Lambda}$) which measures the sparsity. Sparsity becomes
important in the design of large scale systems and the goal is to attain
structural controllability with as little interconnections as possible.

###### Problem 2

—l—[3] Λ∥B_Λ∥_0 $m-$structural controllability of  (1).

We now consider the case of link failures in structured matrices i.e., some
nonzero entries of $\mathcal{B}_{\Lambda}$ become zero due to failure of
interconnecting links. Suppose there are exactly $k$ arbitrary link failures.
Thus, any $k$ entries in the structure $\mathcal{B}_{\Lambda}$ defined by
$\Lambda$ become zero.

###### Problem 3

Given $\mathcal{B}_{\Lambda}$, solve problem $1$ in the presence of $k$ link
failures.

###### Problem 4

Solve Problem 2 in the presence of $k$ link failures.

###  2.2 Preliminaries

The special Euclidean group consists of distance preserving transformations on
$\mathbb{R}^{n}$. In specific, if $\mathbf{x}\in\mathbb{R}^{n}$, then a
special Euclidean transformation $T$ on $\mathbb{R}^{n}$ can be defined as
$\mathbf{x}\mapsto T(\mathbf{x})=O\mathbf{x}+\mathbf{v}$ where
$O\in\mathbb{SO}(n)$ and $\mathbf{v}\in\mathbb{R}^{n}$ (i.e., a rotation
followed by a translation). This can be expressed as a linear transformation
by embedding $\mathbf{x}\in\mathbb{R}^{n}$ into $\mathbb{R}^{n+1}$ as follows

$\mathbf{x}\mapsto\left[\begin{array}[]{cc}O&\mathbf{v}\\\
\mathbf{0}^{\mathsf{T}}&1\end{array}\right]\left[\begin{array}[]{c}\mathbf{x}\\\
1\end{array}\right]=\left[\begin{array}[]{c}O\mathbf{x}+\mathbf{v}\\\
1\end{array}\right].$

This gives a representation of $\mathbb{SE}(n)$ on
$\mathbb{R}^{(n+1)\times{(n+1)}}$ as a matrix group. The fact that it is a
group can be easily checked. Let $\Omega_{ij}$ denote the skew-symmetric
matrix with $1$ in the $(i,j)-$th entry, $-1$ in the $(j,i)-$th entry and zero
everywhere else. Let
$\hat{\Omega}_{ij}=\left[\begin{array}[]{cc}\Omega_{ij}&\mathbf{0}\\\
\mathbf{0}^{\mathsf{T}}&0\end{array}\right]$. Let $E_{ij}$ denote the matrix
with $1$ in the $(i,j)-$th entry and zero everywhere else. The Lie algebra
$\mathcal{SE}(n)$ is a vector subspace of $\mathbb{R}^{(n+1)\times(n+1)}$ with
basis $\mathcal{BS}:=\\{\hat{\Omega}_{ij},\;1\leq i<j\leq
n\\}\cup\\{E_{k,{n+1}},1\leq k\leq n\\}$ with dimension $\frac{n(n+1)}{2}$.

In [Tsope], graph theoretic necessary and sufficient conditions for structural
controllability of driftless bilinear systems on $\mathbb{R}^{n}$ were
obtained when the matrices $B_{i}\in\mathcal{B}_{\Lambda}$, $(1\leq i\leq m)$
for the cases $\mathcal{B}_{\Lambda}\subset\mathcal{GL}(n)$ and
$\mathcal{B}_{\Lambda}\subset\mathcal{SL}(n)$. Another case of certain central
extension $\widetilde{\mathbb{SO}}(n)$ of $\mathbb{SO}(n)$ with Lie algebra
$\widetilde{\mathcal{SO}}(n)$ was also considered. Directed graphs were used
to represent the structure of nonzero entries of $B_{i}$. We mention a how
directed and undirected graphs are used for representation of structured
matrices of different Lie algebras in Remark 1.

An undirected graph $\mathcal{G}(V,E)$ consists of a vertex set $V$ and an
edge set $E$. An edge connecting vertices $i,j\in V$ is denoted as $(i,j)\in
E$. The degree of a vertex is the number of edges incident on that vertex. A
graph is said to be complete if every vertex is connected to every other
vertex by an edge. A directed graph is the one where the order of vertices in
a pair $(i,j)$ determines the direction of the edge. A path between two
vertices $i_{1},i_{k}$ is the sequence of vertices
$\\{i_{1},i_{2},\ldots,i_{k}\\}$ such that $(i_{j},i_{j+1})\in E$ for
$j=1,\ldots,k-1$. An undirected graph is said to be connected if there exists
a path between any two vertices, otherwise it is said to be disconnected. A
disconnecting set of edges is an edge set $F\subseteq E$ such that
$\mathcal{G}\setminus F$ is disconnected. A graph $\mathcal{G}$ is said to be
$k-$edge connected if every disconnecting set has at least $k$ edges [West]. A
directed graph is said to be strongly connected if there exists a directed
path between any two vertices. We define the transitive closure of undirected
graphs using the definition of transitive closure of digraphs from [Tsope].

######  Definition 2 (transitive closure)

Let $\mathcal{G}:=\mathcal{G}(V,E)$ be an undirected graph with the vertex set
$V$ and the edge set $E$ with $|V|=n$. Let $E_{s}$ be the set of solid edges
and $E_{b}$ be the set of broken edges. The $i-$th transitive closure of
$\mathcal{G}$ is defined inductively as follows. Let
$\mathcal{G}^{1}:=\mathcal{G}$ with $E^{1}:=E_{s}^{1}\cup E_{b}^{1}$.

for $2\leq l\leq n$ do

if $(i,j),(j,k)\in E^{l-1}_{s}$ then $(i,k)\in E^{l}_{s}$.

else if $(i,j),(j,k)\in E^{l-1}$ and one of the two edges belongs to
$E^{l-1}_{b}$ then $(i,k)\in E^{l}_{b}$.

else if $(i,j),(j,k)\in E^{l-1}_{b}$ then $(i,k)\notin E^{l}$.

end if

end for

The $n-$th transitive closure of $\mathcal{G}(V,E)$ is the transitive closure.

Let $\mathcal{D}^{0}\subset\mathbb{R}^{(n+1)\times(n+1)}$. Then as defined
recursively in [Tsope], we define the distributions

$\mathcal{D}^{i}:=\mathcal{D}^{i-1}\oplus\text{
span}\\{[A_{1},A_{2}]\in\mathcal{D}^{i-1}\\}.$ (3)

where $\oplus$ represents the direct sum. Let $\bar{\mathcal{D}}$ be the Lie
subalgebra generated by $\mathcal{D}^{0}$. Set $\mathcal{D}^{0}:=$
$\mathcal{B}_{\Lambda}$, then the controllability condition of Theorem 1
implies that $\mathcal{B}_{\Lambda}$ is $m-$structurally controllable on
$\mathbb{SE}(n)$ $\Leftrightarrow$ $\bar{\mathcal{D}}=\mathcal{SE}(n)$.

###### Lemma 1

([Tsope]) Let $r_{i}:=$ dim$(\mathcal{D}^{i})$, $1\leq i\leq k$. Then,
$\\{r_{i}\\}_{i=1}^{k}$ is a nondecreasing sequence. If $r_{i}=r_{j}$ for some
$i\in\\{1,\ldots,k\\}$, then $\mathcal{D}^{i}=\mathcal{D}^{j}$ for all $j>i$.

Let $S_{n+1}$ denote the permutation group on the set $\\{1,\ldots,n+1\\}$.
For example, if $\sigma\in S_{3}$ such that $\sigma(1)=2,\sigma(2)=3$ and
$\sigma(3)=1$, then $\sigma=\begin{pmatrix}1&2&3\\\ 2&3&1\end{pmatrix}$ is a
$3-$cycle. Note that $\sigma=(12)(23)=(132)$ and it turns out that every
permutation can be written as a product of transpositions (i.e.,
$2-$permutations) [Lang]. Let $\mathcal{P}(\mathcal{B}_{\Lambda})$ be the
power set consisting of all possible numerical realizations of the set
$\mathcal{B}_{\Lambda}$. We define a following relation ([cz])

$\iota(\mathcal{P}(\mathcal{B}_{\Lambda}))\rightarrow
S_{n+1},\iota(B_{i_{1}j_{1}},\ldots,B_{i_{m}j_{m}})=(i_{0}j_{0})\ldots(i_{m}j_{m})$
(4)

where $B_{i_{k},j_{k}}\in\mathcal{BS}$ satisfying the structure of
$\mathcal{B}_{\Lambda}$.

##  3 Structural controllability and accessibility

###  3.1 Graph Theoretic Structural Controllability of $\mathbb{SE}(n)$

###### Definition 3

Given $\mathcal{B}_{\Lambda}\subseteq\mathcal{SE}(n)$, we denote by
$\mathcal{G}(\mathcal{B}_{\Lambda})$ the undirected graph with the vertex set
$V:=\\{1,\ldots,n,n+1\\}$ and edge set

$\displaystyle E:=\begin{cases}(i,j)&\text{ if }B_{k}(i,j)\neq 0,1\leq i<j\leq
n\\\ &\text{ for at least one }B_{k}\in\mathcal{B}_{\Lambda},1\leq k\leq m\\\
(i,n+1)&\text{ if }B_{k}(i,n+1)\neq 0,1\leq i\leq n\\\ &\text{ for at least
one }B_{k}\in\mathcal{B}_{\Lambda},1\leq k\leq m.\end{cases}$ (5)

The edges $(i,j)$ $1\leq i<j\leq n$ are denoted by solid edges whereas the
edges $(i,n+1)$ $1\leq i\leq n$ are denoted by broken edges.

###### Example 1

Consider $\mathbb{SE}(3)$ with structured matrices
$B_{1}=\hat{\Omega}_{12}(\star),B_{2}=\hat{\Omega}_{23}(\star),B_{3}=E_{1,4}(\star)$
where
$\Lambda=\\{(1,2),(2,3),(1,4)\\}$ and $\star$ denotes an arbitrary entry in
$\mathbb{R}$. The graphs $\mathcal{G}^{1},\mathcal{G}^{2},\mathcal{G}^{3}$ are
as shown in the Figure 1 where $\mathcal{G}^{3}$ is the complete graph.

(a) $\mathcal{G}^{1}=\mathcal{G}$

(b) $\mathcal{G}^{2}$

(c) $\mathcal{G}^{3}$

Figure 1: $i-$th transitive closures of $\mathcal{G}$ for $i=1,2,3$.

Notice that given a derived distribution $\mathcal{D}^{i}$ of structured
matrices, we can associate an undirected graph to this distribution denoted as
$\mathcal{G}(\mathcal{D}^{i})$ using Definition 3. Conversely, given
$\mathcal{G}^{i}$, we can associate the corresponding distribution denoted as
$\mathcal{B}(\mathcal{G}^{i})$ using $(n+1)\times(n+1)$ structured matrices as
follows

$\displaystyle\mathcal{B}(\mathcal{G}^{i})(j,k):=\begin{cases}\star&\text{ if
}(j,k)\in\mathcal{G}^{i},1\leq j<k\leq n\\\ 0&\text{ if
}(j,k)\notin\mathcal{G}^{i},1\leq j<k\leq n\\\ \star&\text{ if
}k=n+1,(j,k)\in\mathcal{G}^{i},1\leq j\leq n\\\ 0&\text{ if
}k=n+1,(j,k)\notin\mathcal{G}^{i},1\leq j\leq n\end{cases}$ (6)

with $\mathcal{B}(\mathcal{G}^{i})(k,j)=-\mathcal{B}(\mathcal{G}^{i})(j,k)$
for $1\leq j<k\leq n$ and $\mathcal{B}(\mathcal{G}^{i})(n+1,:)=0$ for $i\geq
1$.

Notice that $\mathcal{G}(\mathcal{B}_{\Lambda})$ also naturally induces a map
$\mathcal{G}^{l}\rightarrow S_{n}$ for $1\leq l\leq n+1$ given by
$(j,k)\mapsto(jk)$ where $(j,k)\in E^{l}$ since, the edge $(j,k)$ can be
identified with $\hat{\Omega}_{jk}$ or $E_{j,n+1}$. Note that if
$(i,n+1)(n+1,j)\in E^{l}$, then $(i,n+1)(n+1,j)=(i\;n+1\;j)$ but
$(i,j)\notin{\mathcal{G}}^{l+1}$ as the edges incident on the node $n+1$ do
not satisfy transitivity. This is crucial in proving the following main
result.

###### Theorem 2

Let $\mathcal{B}_{\Lambda}\in\mathcal{SE}(n)$ in (1) and
$\mathcal{G}(\mathcal{B}_{\Lambda})$ be the associated graph. Then, the
following are equivalent.

  1. 1.

$\mathcal{B}_{\Lambda}$ is $m-$structurally controllable on $\mathbb{SE}(n)$.

  2. 2.

The Lie subalgebra generated by at least one numerical realization of $B_{i}$
$1\leq i\leq m$ is equal to the Lie algebra $\mathcal{SE}(n)$.

  3. 3.

The transitive closure of $\mathcal{G}(\mathcal{B}_{\Lambda})$ is the complete
graph on $n+1$ vertices.

  4. 4.

The graph $\mathcal{G}(\mathcal{B}_{\Lambda}(1:n,1:n))$ is connected on
$V_{1}:=\\{1,\ldots,n\\}$ and $\mathcal{G}(\mathcal{B}_{\Lambda})$ is also
connected on $V:=\\{1,\ldots,n+1\\}$.

  5. 5.

$\iota(\mathcal{B}_{\Lambda})$ contains an $(n+1)-$cycle $c=(c_{1})(c_{2})$
where $c_{1}$ is an $n-$cycle on $\\{1,\ldots,n\\}$ and $c_{2}=(i_{k}\;n+1)$
with $1\leq i_{k}\leq n$.

###### Example 2

Consider Example 1 of a control system on $\mathbb{SE}(3)$. It turns out that
$\mathcal{G}^{3}$ gives the transitive closure which is the complete graph on
$4$ vertices. Furthermore, both $\mathcal{G}^{1}$ and
$\mathcal{G}^{1}(\mathcal{B}_{\Lambda}(1:n,1:n))$ are connected. Note that
$\iota(\mathcal{B}_{\Lambda})$ contains an element
$c=c_{1}.c_{2}=(213)(14)=(2413)$ where $c_{1}=(213)$ associated with the path
$1-2-3$ connecting vertices $\\{1,2,3\\}$ and $c_{2}=(14)$ associated with the
edge $(1,4)$. Therefore, by Theorem 2, the system is controllable. One can
also verify that the Lie subalgebra formed by $B_{1},B_{2},B_{3}$ is equal to
$\mathcal{SE}(3)$.

###### Example 3

Consider a control system on $\mathbb{SE}(3)$ as shown in the Figure 2 where
$\Lambda=\\{(1,4),(3,4),(1,2)\\}$.

Figure 2: $\mathcal{G}^{1}=\mathcal{G}$

Note that $\mathcal{G}^{1}$ is connected but
$\mathcal{G}^{1}(\mathcal{B}_{\Lambda}(1:n,1:n))$ is not connected. Observe
that edges $(1,4)$ and $(4,3)$ do not satisfy the edge transitivity property.
The system is not controllable as the LARC not being satisfied. In this case,
$\iota(\mathcal{B}_{\Lambda})$ contains an element $c=c_{1}.c_{2}=(413)(12)$
where $c_{1}=(413)$ associated with the path $1-4-3$ connecting vertices
$\\{1,4,3\\}$ and $c_{2}=(12)$ associated with the edge $(1,2)$. Clearly, this
example does not satisfy conditions $(2)-(5)$ of Theorem 2.

Similar equivalent conditions for structural controllability of
$\mathbb{GL}(n),\mathbb{SL}(n)$ and $\widetilde{\mathbb{SO}}(n)$ hold using
results of [Tsope] where digraphs are used to map structured matrices. The
condition $4$ in Theorem 2 becomes: the digraph
$\mathcal{G}(\mathcal{B}_{\Lambda})$ is strongly connected. Notice that
$\mathbb{SO}(n)\subset\mathbb{SE}(n)$. Therefore, ignoring translations and
using undirected graphs with $n$ nodes, we obtain graph theoretic conditions
of [cz].

###### Remark 1

Notice that when the elements of Lie algebra have zero diagonal entries e.g.,
$\mathbb{SO}(n),\mathbb{SE}(n)$, it makes sense to use undirected graphs. The
reason being that nonzero diagonal entries correspond to self loops at nodes
which are avoided in undirected graphs. On the other hand, if the elements of
Lie algebra have nonzero diagonal entries, then we can use directed graphs and
allow self loops as done in [Tsope] for
$\mathbb{GL}(n),\mathbb{SL}(n),\widetilde{\mathbb{SO}}(n)$ and also in [Wang].
The analogue of condition $(5)$ of Theorem 2 i.e., presence of an $n-$cycle in
$S_{n}$ gives an equivalent controllability condition for the controllability
of the Lie groups $\mathbb{GL}(n),\mathbb{SL}(n),\widetilde{\mathbb{SO}}(n)$
without the decomposition constraint (which is $c=(c_{1})(c_{2})$).

###### Remark 2

Note that equivalent conditions of Theorem 2 hold for structural
controllability of drift free switched bilinear systems too. Due to absense of
the drift term, we can identify drift-free switched bilinear systems with
drift-free bilinear systems by assigning zero inputs to vector fields which
are inactive.

###### Remark 3

From Theorem 2, to check the controllability of driftless bilinear systems on
$\mathbb{SE}(n)$, it is enough to check the connectedness of the associated
graphs $\mathcal{G}(\mathcal{B}_{\Lambda})$ and
$\mathcal{G}(\mathcal{B}_{\Lambda}(1:n,1:n))$. The connectedness of a graph is
equivalent to an existence of a spanning tree [West]. Checking the
connectedness of an undirected graph can be done using depth first search or
breadth first search algorithms which require $O(|V|+|E|)$ time where $V,E$
are vertices and edges of $\mathcal{G}^{1}$ ([klein]). Using results analogous
to [cz] (Theorem $3.22$), we can find the controllable submanifolds of (1) by
finding the connected components of $\mathcal{G}(\mathcal{B}_{\Lambda})$ and
$\mathcal{G}(\mathcal{B}_{\Lambda}(1:n,1:n))$ for uncontrollable systems.

Note that Theorem 2 also allows us to answer Problem 2. From condition $(4)$,
we need a tree structure on vertices $V_{1}:=\\{1,\ldots,n\\}$ and an edge
$(j,n+1)$ connecting one of the vertices $j\in V_{1}$ to the vertex $n+1$ for
$m-$structural controllability. Clearly, the minimum sparsity pattern is not
unique and can be found in $O(V)$ time. In Example 1, the structure $\Lambda$
associated with $\mathcal{G}^{1}$ gives a sparsest structure for
$m-$structural controllability. The minimum number of inputs $m$ required for
controllability of the sparsest pattern is $n$ which is the number of edges in
a spanning tree of a graph over $n+1$ vertices.

####  3.1.1 Minimum Controllability

Note that $m$ was not fixed in (1). In [Tsope], minimum controllability
problem was considered for drift free bilinear systems and probability one
algorithm was given for $k-$controllability i.e., whether the system is
controllable with $k$ inputs. The algorithm involves picking $k$ matrices
$A_{1},\ldots,A_{k}\in\mathcal{B}_{\Lambda}$ at random and computing
$\Delta^{i}=\Delta^{i-1}\cup\\{[A_{1},A_{2}]\;|\;A_{1},A_{2}\in\Delta^{i-1}\\}$
recursively up to $\Delta^{r-k}$ where $r$ is the dimension of the underlying
Lie algebra. Then stack all $X_{i}\in\Delta^{r-k}$ as columns of a matrix $M$
i.e., $M(:,i)=$ vec$(X_{i})$ and check if rank$(M)=r$ or not to verify
controllability. The same algorithm can be used to solve $k-$controllability
problem for $\mathbb{SE}(n)$.

####  3.1.2 Multiple Patterns and Structural Controllability

We have studied only single pattern structured systems so far. In [Tsope],
structural controllability with multiple patterns was also studied and results
analogous to single pattern were obtained for the Lie algebras
$\mathcal{GL}(n),\mathcal{SL}(n)$ and $\widetilde{\mathcal{SO}}(n)$. Similar
results can be obtained for structural controllability of $\mathbb{SE}(n)$
using the approach followed in this article.

In [Sarlette], coordination problem of drift-free multi-agent systems on Lie
Groups $\mathbb{SO}(n),\mathbb{SE}(n)$ is considered and control laws are
given provided that the agents are controllable. Each agent is provided with
the same number of inputs. Using Theorem 4 and the minimum input algorithm in
Section 3.1.1, one can verify controllability with $m$ inputs for each agent
with all agents having the same or different pattern. Taking different
numerical realizations and applying control laws of [Sarlette], one can design
coordination of agents over $\mathbb{SE}(n)$.

###  3.2 Structural Accessibility for Bilinear Systems with Drift

Consider bilinear systems on $\mathbb{SE}(n)$ with drift i.e.,

$\dot{X}=B_{0}X+\bigg{(}\sum_{i=1}^{m}u_{i}B_{i}\bigg{)}X,X(0)=X_{0}$ (7)

$B_{i}\in\mathbb{R}^{(n+1)\times(n+1)}$. Controllability and accessibility of
bilinear systems with drift has been studied from graph theoretic viewpoint in
[Wang] recently on Lie groups $\mathbb{GL}(n),\mathbb{SL}(n),\mathbb{SO}(n)$.
Tsopelakos et. al [Tsope] studied structural accessibility using graphs
whereas Wang et. al. [Wang] did not consider structural properties. We mention
how some of the results mentioned in here for drift free systems can be
applied to systems with drift. Given $T\geq 0$, the set of attainable points
from $X_{0}$ at time $T$ using any arbitrary inputs $u_{i},\;1\leq i\leq m$ is
denoted by $\mathcal{R}_{T}(X_{0})$. These are the set of points in the state
space which can be reached from $X_{0}$ by applying inputs $u_{i},\;1\leq
i\leq m$ from $t=0$ to $t=T$.

###### Definition 4

[Helmke] The system (7) is said to be accessible if $\mathcal{R}_{T}(X_{0})$
has an interior point.

###### Definition 5

[Tsope] The pattern $\mathcal{B}_{\Lambda}$ is said to be structurally
accessible if there exists $m\geq 1,m\in\mathbb{Z}$ such that (1) is
accessible for at least one numerical realization of $B_{i}$, $(1\leq i\leq
m)$. If such an $m$ exists such that (1) is accessible, then we call
$\mathcal{B}_{\Lambda}$ $m-$structurally accessible.

###### Theorem 3

([JurdSuss1, JurdSuss, Helmke]) (a) The system (7) is accessible on the Lie
group $\mathbb{LG}$ $\Leftrightarrow$ the Lie algebra formed by
$\\{B_{0},B_{1},\ldots,B_{m}\\}$ is equal to $\mathcal{LG}$.

(b) If $B_{0}=0$ or the Lie group $\mathbb{LG}$ is compact, then (7) is
controllable $\Leftrightarrow$ it is accessible on $\mathbb{LG}$.

Note that from Theorem 3, it is clear that accessibility and controllability
are equivalent for systems with drift on $\mathbb{SO}(n)$ since it is a
compact Lie group. This is consistent with [cz] where combinatorially
equivalent controllability conditions were obtained for bilinear systems on
$\mathbb{SO}(n)$ with drift. Similar results were obtained in [Wang] too
(Proposition $1$, Theorem $2$) for $\mathbb{SO}(n)$. However, since
$\mathbb{SE}(n)$ is not compact, controllability and accessibility are not
equivalent for systems with drift. The proof of the following theorem follows
from Theorem 3 and the condition $2\Leftrightarrow 3$ of Theorem 2.

###### Theorem 4

The control system (7) with $B_{i}\in\mathcal{B}_{\Lambda}$ for $i=0,\ldots,m$
is structurally accessible $\Leftrightarrow$ the transitive closure
$\mathcal{G}(\mathcal{B}_{\Lambda})$ is a complete graph on $n+1$ vertices.

##  4 Sparsity and link failures

In this section, we discuss Problems 2-4. The following theorem addresses
Problem 2.

###### Theorem 5

Let $\mathcal{T}_{n+1}$ be the set of spanning trees on $n+1$ vertices
$\\{1,2,\ldots,n+1\\}$ such that if $\mathcal{G}_{T}\in\mathcal{T}_{n+1}$,
then $\mathcal{G}_{T}$ restricted to vertices $\\{1,2,\ldots,n\\}$ is a
spanning tree. Then, there is a one to one correspondence between the elements
of $\mathcal{T}_{n+1}$ and solutions of Problem 2.

Let $\mathcal{G}_{T}\in\mathcal{T}_{n+1}$. Then from Theorem 2, there is a
unique pattern $\Lambda$ given by nonzero entries of
$\mathcal{B}(\mathcal{G}_{T})$ which is $m-$structurally controllable.

Conversely, suppose $\Lambda$ is a sparsest pattern for which (1) is
$m-$structurally controllable. Let $\hat{\mathcal{G}}(\mathcal{B}_{\Lambda})$
be the associated graph. From Theorem 2, condition $(4)$ must be satisfied. If
$\hat{\mathcal{G}}(\mathcal{B}_{\Lambda})$ is not a tree, we can drop some
edges and still maintain $m-$structural controllability. But that contradicts
$\Lambda$ being sparsest. Therefore,
$\hat{\mathcal{G}}(\mathcal{B}_{\Lambda})$ must be a tree and must belong to
$\mathcal{T}_{n+1}$.

Consider the case of non-uniform costs in the cost matrix $C$. Note that the
entries $\mathcal{B}_{\Lambda}(i,j)$ and $\mathcal{B}_{\Lambda}(j,i)$ are not
independent for $1\leq i,j\leq n$ due to the structure of $\mathcal{SE}(n)$.
Hence, we assign the same cost for all such pairs. Once the cost matrix is
defined, we can form a weighted undirected graph
$\mathcal{G}(\mathcal{B}_{\Lambda})$. The non-uniform cost matrix $C$ is
defined according to (2) as

$\displaystyle C_{u}(i,j):=\begin{cases}c_{ij}&\text{ if }1\leq i<j\leq n+1\\\
0&\text{ if }i=j,1\leq i,j\leq n+1\end{cases}$ (8)

and

$\displaystyle C_{l}(j,i):=\begin{cases}C_{u}(i,j)&\text{ if }1\leq i<j\leq
n\\\ 0&\text{ if }j=n+1,1\leq i\leq n\end{cases}$ (9)

where $C_{u}$ and $C_{l}$ are the upper triangular and the strictly lower
triangular parts of $C$ respectively.

We consider the following problem —l—[3] (i,j)∈Λ∑C(i,j) $m-$structural
controllability of  (1). From the cost matrix $C$ in (8)-(9), we can form a
weighted complete graph $\mathcal{K}_{n+1}$ on $(n+1)$ vertices with the
following edge weights

$\displaystyle w(i,j)$ $\displaystyle=$ $\displaystyle 2c_{ij}\mbox{ if }1\leq
i,j\leq n$ (10) $\displaystyle w(i,j)$ $\displaystyle=$ $\displaystyle
c_{ij}\mbox{ if }1\leq i\leq n,j=n+1.$ (11)

Notice that the factor $2$ in (10) is present because an edge
$(i,j)\in\mathcal{G}(\mathcal{B}_{\Lambda})$ $(1\leq i,j\leq n)$ corresponds
to elements $\mathcal{B}_{\Lambda}(i,j),\mathcal{B}_{\Lambda}(j,i)$ in the
pattern matrix.

From Theorem 5, it follows that the search space for (5)-(5) can be restricted
to $\mathcal{T}_{n+1}$ reducing the problem to the minimum spanning tree
problem. We give the following greedy algorithm (Algorithm $1$) to solve
(5)-(5). Let $\mathcal{K}_{n}$ be the complete graph on vertices
$\\{1,\ldots,n\\}$.

Algorithm 1 An algorithm to solve (5)-(5)

1:$\mathcal{T}_{1}\leftarrow$ the minimum spanning tree on $\mathcal{K}_{n}$.

2:if $e=(i,n+1)$, $(1\leq i\leq n)$ is an edge with minimum weight incident on
the vertex $n+1$ then,

3: $\mathcal{T}=\mathcal{T}_{1}\cup e$.

4:end if

5:return $\mathcal{T}$.

The minimum spanning tree in Step $1$ of the algorithm above can be obtained
using any of the existing minimum spanning tree algorithms in the literature
[West]. If Prim’s algorithm with time complexity $O(|E|\log|V|)$ or
$O(|E|+|V|\log|V|)$ [West] is used in Step $1$, and deg$(n+1)$ is the degree
of the $(n+1)-$th vertex, then Algorithm $1$ has time complexity
$O(|E|\log|V|+$deg$(n+1))$ or $O(|E|+|V|\log|V|+$deg$(n+1))$.

###### Remark 4

Algorithm $1$ can be used to find the minimum cost sparsest pattern within a
given structure $\mathcal{B}_{\Lambda}$ for $m-$structural controllability.
Given positive integers $k,b$ suppose we want to find if there are $k$
distinct sparsest structures with total cost less than or equal to $b$ in the
pattern matrix $\mathcal{B}_{\Lambda}$. This is equivalent to the $k-$th best
spanning tree problem known to be NP-complete [Garey].

We now give a structural controllability characterization robust to a fixed
number of link failures in the following theorem.

###### Theorem 6

Suppose any $k$ entries of the structured matrices in the class
$\mathcal{B}_{\Lambda}$ become zero due to link failures. Then the following
are equivalent.

  1. 1.

$\mathcal{B}_{\Lambda}$ is $m-$structurally controllable on $\mathbb{SE}(n)$
under $k$ link failures.

  2. 2.

The graph $\mathcal{G}^{1}(\mathcal{B}_{\Lambda}(1:n,1:n))$ is at least
$(k+1)-$edge connected and the degree of the vertex
$(n+1)\in\mathcal{G}^{1}(\mathcal{B}_{\Lambda})$ is at least $(k+1)$.

$(2)\Rightarrow(1)$: Condition $(2)$ implies that under $k$ link failures,
condition $(4)$ of Theorem 2 is still satisfied which implies $(1)$.
$(1)\Rightarrow(2)$: If $(2)$ is not satisfied, then $(1)$ cannot hold.

###### Remark 5

The edge connectivity of a graph can be found by finding the minimum cut of a
graph (i.e., minimum number of edges whose removal disconnects the graph). The
minimum cut can be found using Stoer-Wagner algorithm [Stoer] or Karger’s
randomized algorithm [Karger] in polynomial time. (The minumum cut of a
network is equal to the maximum flow in the network by the Max-flow Min-cut
theorem [West]). Thus, checking $m-$structural controllability under $k$ link
failures can be done in polynomial time. From the minimum cut of
$\mathcal{G}^{1}({\mathcal{B}_{\Lambda}}(1:n,1:n))$ and deg$(n+1)$, we can
find the maximum allowable link failures such that (1) is $m-$structurally
controllable.

###### Example 4

Consider (1) on $\mathbb{SE}(3)$ with
$\Lambda_{1}:=\\{(1,2),(2,3),(3,1),(1,4)\\}$ and
$\Lambda_{2}:=\\{(1,2),(2,3),(1,3),\\\ (4,2),(1,4)\\}$. Their respectively
graphs $\mathcal{G}^{1}(\mathcal{B}_{\Lambda_{1}})$ and
$\mathcal{G}^{1}(\mathcal{B}_{\Lambda_{2}})$ are as shown in the figure.

(a) $\mathcal{G}^{1}(\mathcal{B}_{\Lambda_{1}})$

(b) $\mathcal{G}^{1}(\mathcal{B}_{\Lambda_{2}})$

Figure 3: $\mathcal{G}^{1}(\mathcal{B}_{\Lambda_{1}})$ is not $2-$connected
but $\mathcal{G}^{1}(\mathcal{B}_{\Lambda_{2}})$ is $2-$connected.

Notice that $\mathcal{G}^{1}(\mathcal{B}_{\Lambda_{1}}(1:3,1:3))$ is $2-$edge
connected but the degree of vertex $4$ is one whereas
$\mathcal{G}^{1}(\mathcal{B}_{\Lambda_{2}}(1:3,1:3))$ is $2-$edge connected
and the degree of vertex $4$ is two. Therefore, (1) is not $m-$structurally
controllable under $1$ link failure for $\mathcal{B}_{\Lambda_{1}}$ but it is
$m-$structurally controllable for $\mathcal{B}_{\Lambda_{2}}$ under $1$ link
failure.

###### Theorem 7

Problem 4 is NP-hard for $k\geq 1$.

Note that from Theorem 6, $\mathcal{G}^{1}(\mathcal{B}_{\Lambda})$ must be
$(k+1)-$edge connected. Therefore, the problem becomes minimum $(k+1)-$edge
connected spanning subgraph problem which is NP-hard [Garey].

Problem 4 is equivalent to the NP-hard minimum $k-$edge connected spanning
subgraph problem (minimum $k-$ECSS) [Garey]. It was shown in [FERNANDES] that
minimum $2-$ECSS is a MAX-SNP hard problem which means that there exists a
constant $\epsilon>0$ such that the existence of a polynomial time
approximation algorithm with performance ratio at most $1+\epsilon$ would
imply $P=NP$. Approximation algorithms within a factor of $1+1/2k+O(1/k^{2})$
can be found in [Gabow].

We finally consider the case of probabilistic link failures.

###### Theorem 8

Let $p$ be a rational probability of link failure, $0\leq p\leq 1$ for any
edge $e\in\mathcal{G}(\mathcal{B}_{\Lambda})$ and suppose edge failures are
independent. Let $q\leq 1$ be a positive rational number. The problem of
deciding if (1) is $m-$structurally controllable with probability $q$ or
higher is NP-hard.

By Theorem 2, the $m-$structural controllability reduces to
$\mathcal{G}(\mathcal{B}_{\Lambda})$ being connected without any failed edge
with probability $q$ or higher. This is the NP-hard network reliability
problem [Garey].

Network reliability problems are known to be $\\#P-$complete ([Colbourn])
i.e., NP-hard problems which may require exponential time even if $P=NP$. In
[Guo], a polynomial time approximation algorithm is given.

The results obtained in this section are applicable to systems of the form (1)
evolving over $\mathbb{SO}(n)$ as well since, $\mathbb{SO}(n)$ forms a
subgroup of $\mathbb{SE}(n)$.

##  5 Discussion

In the following two subsections we mention a connection of the results
obtained in this article with the some results in the literature and possible
future directions. Results obtained in Section 4 can also be obtained for
bilinear systems considered in [Tsope] and will be considered in a separate
article.

###  5.1 The Permutation group and non structural controllability

Controllability test for bilinear control systems $\mathbb{SO}(n)$ using the
permutation group of the set $\\{1,\ldots,n\\}$ was obtained in [cz] (Theorem
$3.4$) and in [Zhang] (Theorem $3$). Using the result of [cz], we give another
combinatorial test for the non structural controllability of (1) on
$\mathbb{SE}(n)$. Similar results are obtained in [Zhang1] using a slightly
different approach.

###### Theorem 9

Consider (1) where $B_{k}\in\mathcal{BS},\;1\leq k\leq m$. Suppose
$B_{k}(1:n,n+1)\neq 0$ for at least one $B_{k}$. Then, (1) is controllable
$\Leftrightarrow$ the Lie subalgebra generated by $B_{k}(1:n,1:n)\;1\leq k\leq
m$ is equal to $\mathcal{SO}(n)$.

###### Remark 6

From the previous theorem, given the condition that $B_{k}(1:n,n+1)\neq 0$ for
at least one $B_{k},\;1\leq k\leq m$, checking the LARC condition for
$\mathcal{SE}(n)$ reduces to checking the LARC condition on $\mathcal{SO}(n)$.
In other words, we can restrict $B_{k}$s to principle $n\times n$ submatrices
$B_{k}(1:n,1:n)$ (which are skew symmetric) and consider the Lie subalgebra
generated by them. This allows us to use the permutation group test of [cz] on
$\mathcal{SO}(n)$ to check the LARC condition on $\mathcal{SE}(n)$

We now give the controllability test of [cz] on $\mathcal{SO}(n)$ using
permutation cycles. Let $\mathcal{BS}_{\mathcal{SO}}:=\\{\Omega_{ij}\\}_{1\leq
i<j\leq n}$ be the basis of skew symmetric matrices. It turns out that all
permutations can be written as product of translations ($2-$cycles).

###### Theorem 10

([cz], Theorem $3.4$) Define the relation
$\iota:\mathcal{P}(\mathcal{BS})\rightarrow S_{n}$ as follows

$\iota(\\{\Omega_{i_{1}j_{1}},\ldots,\Omega_{i_{m}j_{m}}\\})=(i_{1}j_{1})\ldots(i_{m}j_{m}).$
(12)

The control system

$\dot{X}=\sum_{k=1}^{m}u_{k}\Omega_{i_{k}j_{k}}X,X(0)=I$ (13)

defined on $\mathbb{SO}(n)$ where
$\Gamma:=\\{\Omega_{i_{k}j_{k}}\\}\subseteq\mathcal{BS}_{\mathcal{SO}}$ for
$k=1,\ldots,m$ is controllable $\Leftrightarrow$ there exists a subset
$\Sigma\subseteq\Gamma$ such that $\iota(\Sigma)$ is an $n-$cycle, where
$\iota$ is the relation defined in (12).

Now as mentioned in Remark 6, given $B_{1},\ldots,B_{m}\in\mathcal{SE}(n)$, we
can consider
$B_{1}(1:n,1:n),\ldots,B_{m}(1:n,1:n)\in\mathcal{BS}_{\mathcal{SO}}$. Now
provided that the condition given in Theorem 9 is satisfied, controllability
on $\mathbb{SE}(n)$ reduces to checking the condition of Theorem 10.

###  5.2 Strong structural controllability

Strong structural controllability for LTI systems is studied in [van] where
three types of entries were considered: zero, nonzero and arbitrary (the
arbitrary entries can take zero or nonzero values). For strong structural
controllability, the system must be controllable for all numerical
realizations of the given structured matrices. In [van], the necessary and
sufficient conditions are obtained using graph colorability which can also be
associated with zero forcing sets ([monshi, Trefois]). One of the possible
questions is obtaining necessary and sufficient conditions for strong
structural controllability of bilinear systems on Lie groups. Suppose all
entries marked as $\star$ in $\mathcal{B}_{\Lambda}$ take nonzero real values
only. (The set $\mathcal{B}_{\Lambda}$ is no longer a vector space.)

######  Definition 6 (Strong structural controllability)

The pattern $\mathcal{B}_{\Lambda}$ is said to be strong structurally
controllable if there exists $m\geq 1,m\in\mathbb{Z}$ such that (1) is
controllable for all numerical realization of $B_{i}$, $(1\leq i\leq m)$. If
such an $m$ exists such that (1) is controllable, then we call the pattern
$\mathcal{B}_{\Lambda}$ strong $m-$structurally controllable.

Let $\mathcal{D}^{0}$ be the vector space generated by $\mathcal{B}_{\Lambda}$
and define $\mathcal{D}^{i}$ recursively as done before. Now we can associate
graphs $\mathcal{G}^{i}$ to distributions $\mathcal{D}^{i-1}$. Suppose,
conditions of Theorem 2 hold. Now choose a numerical realization such that
$B_{i}=B$ for $1\leq i\leq m$ where $B\in\mathcal{B}_{\Lambda}$. Clearly, the
LARC condition fails and the realization is uncontrollable. Therefore, one
needs different equivalent conditions for strong $m-$structural
controllability. Suppose we allow some entries in $\mathcal{B}_{\Lambda}$ to
be marked as $?$ which can take arbitrary real values as in [van] apart from
identically zero entries (possible link failures) and entries marked as
$\star$ which are strictly nonzero. In future, we also want to find necessary
and sufficient conditions for strong structural controllability in this
setting.

## Proofs of Theorem 2 and Theorem 9

Proof of Theorem 2: We need the following lemmas for the proof. In the lemma
below, first statement follows from Lemma $2.3$ of [cz] whereas; the second
and the third statements follow from construction.

###### Lemma 2

Consider $\mathcal{SE}(n):=$ span$\\{\\{\hat{\Omega}_{ij},\;1\leq i<j\leq
n\\},\cup\\{E_{k,{n+1}},1\leq k\leq n\\}\\}$. The following equations hold

  1. 1.

$[\hat{\Omega}_{ij},\hat{\Omega}_{kl}]=\delta_{jk}\hat{\Omega}_{il}+\delta_{il}\hat{\Omega}_{jk}+\delta_{jl}\hat{\Omega}_{ki}+\delta_{ik}\hat{\Omega}_{lj}$
where $\delta$ is the Kronecker delta function.

  2. 2.

$[E_{i,n+1},E_{j,n+1}]=0$.

  3. 3.

$[\hat{\Omega}_{ij},E_{k,n+1}]=\delta_{jk}E_{i,n+1}-\delta_{ik}E_{j,n+1}$.

The proof of the following Lemma also follows from construction.

###### Lemma 3

For $i\geq 1$, the equalities
$\mathcal{B}(\mathcal{G}(\mathcal{D}^{i-1}))=\mathcal{D}^{i-1}$ and
$\mathcal{G}(\mathcal{B}(\mathcal{G}^{i}))=\mathcal{G}^{i}$ hold.

###### Lemma 4

Let $\mathcal{B}_{\Lambda}\subset\mathcal{SE}(n)$ be a zero-pattern. Let
$\mathcal{D}^{0}=\mathcal{B}_{\Lambda}$ and
$\mathcal{G}^{1}=\mathcal{G}(\mathcal{B}_{\Lambda})$. Then, for $1\leq i\leq
n+1$,

$\mathcal{G}(\mathcal{D}^{i-1})=\mathcal{G}^{i}\text{ and
}\mathcal{B}(\mathcal{G}^{i})=\mathcal{D}^{i-1}.$

We give an inductive proof as follows. For $i=1$,
$\mathcal{G}(\mathcal{D}^{0})=\mathcal{G}^{1}$ and
$\mathcal{B}(\mathcal{G}^{1})=\mathcal{D}^{0}$.

Now suppose the inductive hypothesis is true for $i=i_{1}$ i.e.,
$\mathcal{G}(\mathcal{D}^{i_{1}-1})=\mathcal{G}^{i_{1}}$ and
$\mathcal{B}(\mathcal{G}^{i_{1}})=\mathcal{D}^{i_{1}-1}$. Consider the two
cases $\mathcal{G}^{i_{1}}=\mathcal{G}^{i_{1}+1}$ and
$\mathcal{G}^{i_{1}}\neq\mathcal{G}^{i_{1}+1}$.
(Case I) $\mathcal{G}^{i_{1}}=\mathcal{G}^{i_{1}+1}$: From the induction
hypothesis,

$\mathcal{B}(\mathcal{G}^{i_{1}+1})=\mathcal{B}(\mathcal{G}^{i_{1}})=\mathcal{D}^{i_{1}-1}.$
(14)

We need to show that $\mathcal{D}^{i_{1}-1}=\mathcal{D}^{i_{1}}$.

Suppose $A_{1},A_{2}\in\mathcal{D}^{i_{1}-1}$ such that
$[A_{1},A_{2}]\notin\mathcal{D}^{i_{1}-1}$. From the definition of
$\mathcal{B}(\mathcal{G}^{i_{1}})$ and the inductive hypothesis,

$\mathcal{D}^{i_{1}-1}=\text{span}\\{\\{\hat{\Omega}_{ij}\\}_{(i,j)\in\mathcal{G}^{i_{1}}}\cup\\{E_{k,n+1}\\}_{(k,n+1)\in\mathcal{G}^{i_{1}}}\\}$

where $(1\leq i<j\leq n)$ and $(1\leq k\leq n)$. Therefore,
$A_{1}=\sum_{p,q,r}(a_{pq}\hat{\Omega}_{pq}+a^{\prime}_{r}E_{r,n+1})$ and
$A_{2}=\sum_{p^{\prime},q^{\prime},r^{\prime}}(b_{p^{\prime}q^{\prime}}\hat{\Omega}_{p^{\prime}q^{\prime}}+b^{\prime}_{r^{\prime}}E_{r^{\prime},n+1})$.
Now $[A_{1},A_{2}]=$

$\displaystyle\sum_{p,q,r,p^{\prime},q^{\prime},r^{\prime}}a_{pq}b_{p^{\prime}q^{\prime}}[\hat{\Omega}_{pq},\hat{\Omega}_{p^{\prime}q^{\prime}}]+a^{\prime}_{r}b_{pq}[E_{r,n+1},\hat{\Omega}_{p^{\prime}q^{\prime}}]+$
$\displaystyle
a_{pq}b^{\prime}_{r^{\prime}}[\hat{\Omega}_{pq},E_{r^{\prime},n+1}]$ (15)

and since $[A_{1},A_{2}]\notin\mathcal{D}^{i_{1}-1}$, one of the Lie brackets
in (15) is nonzero. Now from the first statement of Lemma 2,
$[\hat{\Omega}_{pq},\hat{\Omega}_{p^{\prime}q^{\prime}}]\neq 0\Leftrightarrow$
$p=p^{\prime},p=q^{\prime},q=p^{\prime}$ or $q=q^{\prime}$. Therefore, if
$[\hat{\Omega}_{pq},\hat{\Omega}_{p^{\prime}q^{\prime}}]\neq 0$, edges $(p,q)$
and $(q,q^{\prime})$ belong to $\mathcal{G}^{i_{1}}$ and
$(p,q^{\prime})\in\mathcal{G}^{i_{1}+1}$ since $(p,q)$ and $(q,q^{\prime})$
are both solid edges. Therefore,
$\hat{\Omega}_{pq^{\prime}}\in\mathcal{D}^{i_{1}}$ but
$\hat{\Omega}_{pq^{\prime}}\notin\mathcal{D}^{i_{1}-1}$ which contradicts
(14). From the third statement of Lemma 2,
$[\hat{\Omega}_{pq},E_{r^{\prime},n+1}]\neq 0\Leftrightarrow$ $p=r^{\prime}$
or $q=r^{\prime}$. Again via similar arguments, if
$[\hat{\Omega}_{pq},E_{r^{\prime},n+1}]\neq 0$, edges $(p,q)$ and $(q,n+1)$
belong to $\mathcal{G}^{i_{1}}$ and $(p,n+1)\in\mathcal{G}^{i_{1}+1}$.
Therefore, $E_{p,n+1}\in\mathcal{D}^{i_{1}}$ but
$E_{p,n+1}\notin\mathcal{D}^{i_{1}-1}$ which contradicts (14). Therefore,
$\mathcal{D}^{i_{1}-1}=\mathcal{D}^{i_{1}}$ and the lemma follows by
induction.
(Case II) $\mathcal{G}^{i_{1}}\neq\mathcal{G}^{i_{1}+1}$: Let
$(p,r)\in\mathcal{G}^{i_{1}+1}$ and $(p,r)\notin\mathcal{G}^{i_{1}}$.
Claim: $\mathcal{G}(\mathcal{D}^{i_{1}})=\mathcal{G}^{i_{1}+1}$.
Since $\mathcal{G}^{i_{1}+1}$ is the $1-$step transitive closure of
$\mathcal{G}^{i_{1}}$, $\exists q\in V$ such that
$(p,q),(q,r)\in\mathcal{G}^{i_{1}}=\mathcal{G}(\mathcal{D}^{i_{1}-1})$.
case (a): Suppose $p,q,r<n+1$. Then, from the definition of
$\mathcal{G}(\mathcal{D}^{i_{1}-1})$, matrices
$\hat{\Omega}_{pq},\hat{\Omega}_{qr}\in\mathcal{D}^{i_{1}-1}$. From Lemma 2,
$[\hat{\Omega}_{pq},\hat{\Omega}_{qr}]=\hat{\Omega}_{pr}\Rightarrow\hat{\Omega}_{pr}\in\mathcal{D}^{i_{1}}$.
This implies that $(p,r)\in\mathcal{G}(\mathcal{D}^{i_{1}})$ showing that
$\mathcal{G}(\mathcal{D}^{i_{1}})=\mathcal{G}^{i_{1}+1}$.
case (b): Suppose $p,q<n+1,r=n+1$. Then, from the definition of
$\mathcal{G}(\mathcal{D}^{i_{1}-1})$, matrices
$\hat{\Omega}_{pq},E_{q,n+1}\in\mathcal{D}^{i_{1}-1}$. From Lemma 2,
$[\hat{\Omega}_{pq},E_{q,n+1}]=E_{p,n+1}\Rightarrow
E_{p,n+1}\in\mathcal{D}^{i_{1}}$. This implies that
$(p,n+1)\in\mathcal{G}(\mathcal{D}^{i_{1}})$ again showing that
$\mathcal{G}(\mathcal{D}^{i_{1}})=\mathcal{G}^{i_{1}+1}$.
case (c): Suppose $q=n+1$. In this case, both $(p,q)$ and $(q,r)$ belong to
$E^{i_{1}}_{b}$. Therefore, $(p,r)\notin\mathcal{G}^{i_{1}+1}$ by construction
(Definition 2) and case $(c)$ cannot happen thus proving the claim and the
inductive step for $\mathcal{G}(\mathcal{D}^{i-1})=\mathcal{G}^{i}$.

Note that using
$\mathcal{G}^{i_{1}+1}=\mathcal{G}(\mathcal{D}^{i_{1}}),\mathcal{B}(\mathcal{G}^{i_{1}+1})=\mathcal{B}(\mathcal{G}(\mathcal{D}^{i_{1}}))=\mathcal{D}^{i_{1}}$
(from Lemma 3), we prove the second part of the lemma
$\mathcal{B}(\mathcal{G}^{i})=\mathcal{D}^{i-1}$ for the case $i=i_{1}+1$
concluding the proof by induction. (Theorem 2) Note that $1\Leftrightarrow 2$
follows from Theorem 1 and the definition of structural controllability.
$3\Leftrightarrow 4$ follows from basics of graph theory [West], the
construction of transitive closure (Definition 2) and Definition 3. We show
that $2\Leftrightarrow 3$. From the relation
$\mathcal{B}(\mathcal{G}^{i})=\mathcal{D}^{i-1}$ of Lemma 4, if the transitive
closure of $\mathcal{G}^{1}$ is the complete graph, then
$\\{\hat{\Omega}_{ij},\;1\leq i<j\leq n\\},\cup\\{E_{k,{n+1}},1\leq k\leq
n\\}\subset\bar{D}$ hence, $\bar{D}=\mathcal{SE}(n)$. The converse also
follows from Lemma 4 and Lemma 3.

Finally, we need to prove $4\Leftrightarrow 5$. From $(4)$, there exists a
path connecting vertices $\\{1,\ldots,n\\}$ which gives a cycle
$c_{1}=(i_{1}\ldots i_{n})$ from the induced map from
$\mathcal{G}^{1}\rightarrow S_{n}$. It follows from $(4)$ that there exists an
edge $(i_{k},n+1)\in\mathcal{G}(\mathcal{B}_{\Lambda})$ ($1\leq i_{k}\leq n$)
which corresponds to $c_{2}=(i_{k}\;n+1)$ proving $(5)$. Conversely, if $(5)$
holds then, corresponding to the cycle $c_{1}$ there exists a path in
$\mathcal{G}^{1}$ connecting vertices $\\{1,\ldots,n\\}$ and there is an edge
$(i_{k},n+1)$ ($1\leq i_{k}\leq n$) in $\mathcal{G}^{1}$ corresponding to
$c_{2}$ which proves $(4)$. Proof of Theorem 9: The proof of the following
lemma follows from construction.

###### Lemma 5

Let $\mathbf{e}_{k}$ be the standard basis vector and
$\\{\Omega_{kj}\\}_{j=1}^{n}$ be skew symmetric matrices such that
$\Omega_{kj}(k,j)=1$, $\Omega_{kj}(j,k)=-1$ and $\Omega_{kj}(l,m)=0$ for
$l\neq k,j$ and $m\neq k,j$. Then
$\mathbf{e}_{k},\Omega_{k1}\mathbf{e}_{k},\ldots,\Omega_{kn}\mathbf{e}_{k}$
span $\mathbb{R}^{n}$.

(Theorem 9) Notice that we can write $B_{k}$ in the block form
$\left[\begin{array}[]{cc}\Omega_{ij}&\mathbf{0}\\\
\mathbf{0}^{\mathsf{T}}&0\end{array}\right]$ or
$\left[\begin{array}[]{cc}0_{n\times n}&\mathbf{e}_{k}\\\
\mathbf{0}^{\mathsf{T}}&0\end{array}\right]$ where $\Omega_{ij}$ is skew
symmetric and $\mathbf{e}_{l}\in\mathbb{R}^{n}$ is the $l-$th standard basis
vector. If the Lie bracket $[B_{k},B_{l}]\neq 0$, then
$[B_{k},B_{l}]=\left[\begin{array}[]{cc}[\Omega_{ij},\Omega_{pq}]&\mathbf{0}\\\
\mathbf{0}^{\mathsf{T}}&0\end{array}\right]$ or
$\left[\begin{array}[]{cc}0_{n\times n}&\Omega_{ij}\mathbf{e}_{l}\\\
\mathbf{0}^{\mathsf{T}}&0\end{array}\right]$. Therefore, from the previous
lemma and the block matrix structure of $\mathcal{SE}(n)$, the statement of
the theorem follows.


# Reliable Detection for Spatial Modulation Systems

Ibrahim Al-Nahhal∗, Octavia A. Dobre∗ and Salama Ikki‡
∗Faculty of Engineering and Applied Science, Memorial University, St. John’s,
Canada
‡Department of Electrical Engineering, Lakehead University, Thunder Bay,
Canada

###### Abstract

Spatial modulation (SM) is a promising multiple-input multiple-output system
used to increase spectral efficiency. The maximum likelihood (ML) decoder
jointly detects the transmitted SM symbol, which is of high complexity. In
this paper, a novel reliable sphere decoder (RSD) algorithm based on tree-
search is proposed for the SM system. The basic idea of the proposed RSD
algorithm is to reduce the size of the tree-search, and then, a smart
searching method inside the reduced tree-search is performed to find the
solution. The proposed RSD algorithm provides a significant reduction in
decoding complexity compared to the ML decoder and existent decoders as well.
Moreover, the RSD algorithm provides a flexible trade-off between the bit
error rate (BER) performance and decoding complexity, so as to be reliable for
a wide range of practical hardware implementations. The BER performance and
decoding complexity analysis for the RSD algorithm are studied, and Monte
Carlo simulations are then provided to demonstrate the findings.

###### Index Terms:

Multiple-input multiple-output (MIMO), spatial modulation (SM), low complexity
decoders, complexity analysis, error analysis.

##  I Introduction

Spatial modulation (SM) is a promising technique [References] that has been
recently applied to many of the emerging technologies [References],
[References]. It overcomes the inter-channel interference (ICI) problem that
exists in multiple-input multiple-output (MIMO) systems. The SM system
completely eliminates the ICI by delivering a phase-shift-keying (PSK) or
quadrature amplitude modulation (QAM) symbol from only one transmit antenna at
a time. A part of the input bit-stream determines an active transmit antenna,
while the rest determines the PSK/QAM symbol to be delivered from the
activated antenna [References], [References]. At the receiver, the maximum-
likelihood (ML) decoder is applied to obtain the optimum bit error rate (BER)
at the expense of the decoding complexity [References].

Several low-complexity decoding algorithms have been recently proposed in
[References]-[References] to reduce the high decoding complexity of the ML
decoder. In [References] and [References], the sphere decoder (SD) concept is
utilized to reduce the decoding complexity without sacrificing the optimum BER
performance. A low-complexity decoding algorithm has been proposed in
[References] and extended in [References] by exploiting a smart searching
algorithm in the tree-search to obtain the optimum BER performance. The
authors in [References] and [References] proposed low-complexity decoders by
sacrificing the optimality of the BER performance. The existing SD algorithms
suffer from a lack of reliability when it comes to fitting the practical
hardware implementation requirements. In other words, the existing algorithms
do not provide a suitable trade-off between the BER performance and decoding
complexity.

This paper proposes a novel and reliable SD (RSD) algorithm that provides an
advantageous arrangement between the BER performance and decoding complexity.
Besides, the proposed RSD algorithm can achieve the optimum BER performance
with a significant reduction in the decoding complexity compared to the ML
decoder and the existing algorithms as well. The analytical BER analysis and
expected decoding complexity of the proposed algorithm are provided and
confirmed through Monte Carlo simulations.

##  II System Model

Consider an $N_{r}\times N_{t}$ SM-MIMO system, where $N_{r}$ and $N_{t}$
represent the number of transmit and receive antennas, respectively. SM
delivers $\text{log}_{2}(N_{t}M)$ bit per channel use, where $M$ is the
modulation order of the QAM constellation. The input bit-stream is split into
two groups: the first $\text{log}_{2}(N_{t})$ bits select the active antenna,
while the second $\text{log}_{2}(M)$ bits determine the QAM symbol to be
transmitted, $s_{t}\in\\{s_{1},\cdots,s_{M}\\}$. The SM transmitted message,
$\boldsymbol{x}_{t}$, is equal to $\boldsymbol{h}_{t}s_{t}$, where
$\boldsymbol{h}_{t}$ is a vector of the Rayleigh fading channel coefficients
with entries distributed as $\mathcal{C}\mathcal{N}(0,1)$ and drawn from the
channel matrix, $\boldsymbol{H}\in\mathbb{C}^{N_{r}\times N_{t}}$. The
received signal is

$\boldsymbol{y}=\boldsymbol{x}_{t}+\boldsymbol{g},$ (1)

where $\boldsymbol{g}\sim\mathcal{C}\mathcal{N}(0,\sigma_{g}^{2})$ is the
vector of additive white Gaussian noise (AWGN) samples.

At the receiver side, the ML decoder estimates the transmitted SM message,
$\hat{\boldsymbol{x}}_{\text{ML}}$, as [References]

$\hat{\boldsymbol{x}}_{\text{ML}}=\underset{\boldsymbol{x}_{j}|j=1,\cdots,MN_{t}}{\text{arg\,min}}\left\|\boldsymbol{y}-\boldsymbol{x}_{j}\right\|^{2}=\underset{\boldsymbol{x}_{j}|j=1,\cdots,MN_{t}}{\text{arg\,min}}\sum_{i=1}^{N_{r}}\left|y_{i}-x_{i,j}\right|^{2}.$
(2)

The tree-search structure [References], [References] can be used to represent
(2). The tree-search is a two-dimensional structure with a size of
$N_{r}\times MN_{t}$; the tree-search width represents the $MN_{t}$
possibilities of the SM message called branches, while its depth represents
the $N_{r}$ levels of each possibility of the SM message. Fig. 1 shows a tree-
search example of the ML decoder for $M=2$, $N_{t}=4$, and $N_{r}=6$. The
accumulated distance metric vector of the $i$-th level,
$\boldsymbol{v}(i)\in\mathbb{R}^{1\times MN_{t}}$, is

$\boldsymbol{v}(i)=\left[\begin{array}[]{ccc}\sum_{n=1}^{i}\left|y_{n}-x_{n,1}\right|^{2}&\cdots&\sum_{n=1}^{i}\left|y_{n}-x_{n,MN_{t}}\right|^{2}\end{array}\right].$
(3)

Typically, the last level of the tree-search is called the decision level. The
ML decoder estimates $\hat{\boldsymbol{x}}_{\text{ML}}$ that corresponds to
the minimum node in $\boldsymbol{v}(N_{r})$. Note that the SM tree-search is
quite different than the MIMO tree-search [References]-[References].

In this paper, the decoding complexity is defined as the total number of nodes
that should be visited in the tree-search to estimate the transmitted SM
message. Since the ML decoder visits all nodes in the tree-search, its
decoding complexity is $\Psi^{\text{ML}}=MN_{t}N_{r}$.

The complexity of the ML decoder consequently becomes extensive, especially
for higher SM-MIMO dimensions and/or QAM sizes. Several works in the
literature have been proposed to reduce the ML complexity, which are based on
tree-search and SD concepts. However, further complexity reduction can still
be achieved, as well as progress towards its reliability to fit a wide range
of hardware implementation.

Fig. 1: Tree-search of SM-MIMO for $M=2$, $N_{t}=4$, and $N_{r}=6$.

##  III The Proposed RSD Algorithm

The proposed RSD algorithm firstly reduces the size of the tree-search, and
then performs a smart searching method to reach the solution. Let us define
$\psi_{\text{col}}$ as the number of branches/SM message possibilities that
most likely contains the optimum solution. The RSD algorithm performs its
searching for the solution inside these $\psi_{\text{col}}$ branches and stops
at the $\psi_{\text{row}}$-th level, where $1\leq\psi_{\text{row}}\leq N_{r}$
is the maximum number of levels that can be visited by the RSD algorithm
(i.e., the decision level at $\psi_{\text{row}}$). It is worth noting that the
flexibility trade-off between the BER performance and complexity provided by
the RSD algorithm comes from changing the value of $\psi_{\text{row}}$ within
the range of $1$ and $N_{r}$.

The steps of searching for the solution of the RSD algorithm inside the
reduced tree-search are as follows:

Step 1: Expand all nodes of the first level, i.e., $\boldsymbol{v}(1)$ in (3).

Step 2: Appropriately choose the smallest $\psi_{\text{col}}$ nodes that come
from Step 1. It should be noted that the RSD algorithm searches for the
solution inside the branches that correspond to the smallest
$\psi_{\text{col}}$ nodes. Consequently, the RSD algorithm reduces the
decoding complexity by at least $(MN_{t}-\psi_{\text{col}})\psi_{\text{row}}$
nodes. The vector of distance metric nodes in (3) yields

$\boldsymbol{v}(i)=\left[\begin{array}[]{ccccc}v(i,1)&\cdots&v(i,j)&\cdots&v(i,\psi_{\text{col}})\end{array}\right],$
(4)

where $v(i,j)$ is the $j$-th node of level $i$, and given by

$v(i,j)=\sum_{n=1}^{i}\left|y_{n}-x_{n,j}\right|^{2}.$ (5)

  * •

Input $\boldsymbol{H}$, $M$, and $N_{t}$;

  * •

Compute $\boldsymbol{v}(1)$ in (3);

  * •

Choose $\psi_{\text{col}}$ empirically, based on $M$ and $N_{t}$ to most
likely include the optimum BER performance;

  * •

Store the branches indices that corresponding to the smallest
$\psi_{\text{col}}$ node of $\boldsymbol{v}(1)$ into
$\varXi_{\psi_{\text{col}}}$;

  * •

Choose $\psi_{\text{row}}$ based on the system requirements from the BER and
complexity points of views;

  * •

Define $\text{Len}(j)$ as the length of the $j$-th branch and initiate it with
one for $\forall j$;

1: While$\,\,\,n<\psi_{\text{row}}\psi_{\text{col}}$, do

2: Find $j_{\text{min}}$ that solves
$\underset{\begin{array}[]{c}j\in\varXi_{\psi_{\text{col}}}\\\
i_{\text{min}}\in\\{1,\cdots,\psi_{\text{row}}\\}\end{array}}{\text{arg\,min}}\left\\{\boldsymbol{v}(i_{\text{min}})\right\\}$;

3: Update $i_{\text{min}}$ as the level that corresponding to
$j_{\text{min}}$;

4:  if $\text{Len}(j_{\text{min}})==\psi_{\text{row}}$

5: break and end the algorithm;

6:  else

7: Expand $v(i_{\text{min}},j_{\text{min}})\leftarrow
v(i_{\text{min}}+1,j_{\text{min}})$;

8: Update $\boldsymbol{v}(i_{\text{min}})$ based on
$v(i_{\text{min}},j_{\text{min}})$;

9:  end if

10:  Set $n\leftarrow n+1$;

11: end While

  * •

Output
$\hat{\boldsymbol{x}}_{\text{RSD}}=\underset{\begin{array}[]{c}j\in\varXi_{\psi_{\text{col}}}\end{array}}{\text{arg\,min}}\left\\{\boldsymbol{v}(\psi_{\text{row}})\right\\}$.

Algorithm 1 The proposed RSD algorithm pseudo-code.

Step 3: Perform a single expansion to the minimum node in (4).

Step 4: Check if the expanded node from Step 3 still has a minimum value among
the rest of $\psi_{\text{col}}$ nodes or not. If yes, perform another single
expansion to that node. If no, find the new minimum node and expand it once.

Step 5: Repeat Step 3 and Step 4 until the RSD algorithm obtains the minimum
node at a branch with a length of $\psi_{\text{row}}$.

Step 6: Find the index corresponding to the node that comes from Step 5, and
declare it as the solution of the RSD algorithm. The estimated SM message
using the RSD algorithm, $\hat{\boldsymbol{x}}_{\text{RSD}}$, can be given as

$\hat{\boldsymbol{x}}_{\text{RSD}}=\underset{\begin{array}[]{c}\boldsymbol{x}_{j}|j\in\varXi_{\psi_{\text{col}}}\end{array}}{\text{arg\,min}}\sum_{i=1}^{\psi_{\text{row}}}\left|y_{i}-x_{i,j}\right|^{2}$

$=\underset{\begin{array}[]{c}j\in\varXi_{\psi_{\text{col}}}\end{array}}{\text{arg\,min}}\left\\{\boldsymbol{v}(\psi_{\text{row}})\right\\},$
(6)

where $\varXi_{\psi_{\text{col}}}$ denotes the set of branch indices that
corresponds to the smallest $\psi_{\text{col}}$ metric node values of
$\boldsymbol{v}(1)$ (i.e., the first level at $i=1$ in (3)). The RSD algorithm
is summarized in Algorithm 1.

##  IV Theoretical Analysis

The RSD algorithm provides the optimum BER performance with a significant
reduction in the decoding complexity. In addition, by changing the value of
$\psi_{\text{row}}$, a flexible trade-off between the BER performance and
decoding complexity can be obtained to fit a wide range of hardware
implementation. In this section, the BER performance and expected complexity
are considered random variables, and their approximate expressions are derived
using the probability theory.

###  IV-A BER Upper Bound Analysis

The general expression for the upper bound of the ML BER for SM is
[References], [References]

$\text{BER}^{\text{ML}}\leq\sum_{j=1}^{MN_{t}}\sum_{\hat{j}=1}^{MN_{t}}\frac{\delta(\boldsymbol{x}_{j},\hat{\boldsymbol{x}}_{\hat{j}})\mathcal{\mathbb{E}}\left\\{\mathbb{P}\text{r}^{\text{ML}}\left(\boldsymbol{x}_{j}\rightarrow\hat{\boldsymbol{x}}_{\hat{j}}\right)\right\\}}{MN_{t}\text{log}_{2}(MN_{t})},$
(7)

where
$\mathbb{P}\text{r}^{\text{ML}}(\boldsymbol{x}_{j}\rightarrow\hat{\boldsymbol{x}}_{\hat{j}})$
is the pairwise error probability (PEP) of the ML algorithm,
$\mathbb{P}\text{r}(\centerdot)$ denotes the probability of an event,
$\mathcal{\mathbb{E}}\left\\{\cdot\right\\}$ represents the expectation
operation, and $\delta(\boldsymbol{x}_{j},\hat{\boldsymbol{x}}_{\hat{j}})$
denotes the Hamming distance which measures the number of bits in error
between $\boldsymbol{x}_{j}$ and $\hat{\boldsymbol{x}}_{\hat{j}}$.

Since the RSD algorithm performs the search inside a portion of the tree-
search with a size of $\psi_{\text{row}}\times\psi_{\text{col}}$, the optimal
solution may not be included in that portion of the tree-search. Thus, the PEP
in (7) for the RSD algorithm can be written as

$\mathbb{P}\text{r}^{\text{RSD}}\left(\boldsymbol{x}_{j}\rightarrow\hat{\boldsymbol{x}}_{\hat{j}}\right)=\mathbb{P}\text{r}\left(\hat{\boldsymbol{x}}_{\text{opt}}\neq\boldsymbol{x}_{t}|\hat{\boldsymbol{x}}_{\text{opt}}\in\varXi_{\psi_{\text{col}}}\right)+\mathbb{P}\text{r}\left(\hat{\boldsymbol{x}}_{\text{opt}}\notin\varXi_{\psi_{\text{col}}}\right),$
(8)

where $\hat{\boldsymbol{x}}_{\text{opt}}$ is the optimal solution. The
conditional probability in (8) contains two independent events. The expected
value of (8) can consequently be written as

$\mathcal{\mathbb{E}}\left\\{\mathbb{P}\text{r}^{\text{RSD}}\left(\boldsymbol{x}_{j}\rightarrow\hat{\boldsymbol{x}}_{\hat{j}}\right)\right\\}=\underset{\text{Term
1}}{\underbrace{\mathcal{\mathbb{E}}\left\\{\mathbb{P}\text{r}\left(\hat{\boldsymbol{x}}_{\text{opt}}\neq\boldsymbol{x}_{t}\right)\right\\}}}+\underset{\text{Term
2}}{\underbrace{\mathcal{\mathbb{E}}\left\\{\mathbb{P}\text{r}\left(\hat{\boldsymbol{x}}_{\text{opt}}\notin\varXi_{\psi_{\text{col}}}\right)\right\\}}}.$
(9)

Term 1 in (9) can be written as in [References], [References]

$\mathcal{\mathbb{E}}\left\\{\mathbb{P}\text{r}\left(\hat{\boldsymbol{x}}_{\text{opt}}\neq\boldsymbol{x}_{t}\right)\right\\}=\mu_{j,\hat{j}}^{\psi_{\text{row}}}\sum_{k=0}^{\psi_{\text{row}}-1}\left(\begin{array}[]{c}\psi_{\text{row}}-1+k\\\
k\end{array}\right)(1-\mu_{j,\hat{j}})^{k},$ (10)

with

$\mu_{j,\hat{j}}=0.5\left(1-\sqrt{\frac{\sigma_{j,\hat{j}}^{2}}{1+\sigma_{j,\hat{j}}^{2}}}\right),\,\,\,\,\,\sigma_{j,\hat{j}}^{2}=\frac{\rho(|s(j)|^{2}+|s(\hat{j})|^{2})}{4},$
(11)

where $\rho$ is the average signal to noise ratio (SNR), and $s(j)$ is the QAM
symbol of the $j$-th SM transmitted message. Hence, for the RSD algorithm, (7)
can be written as

$\text{BER}^{\text{RSD}}\leq\sum_{j=1}^{\psi_{\text{col}}}\sum_{\hat{j}=1}^{\psi_{\text{col}}}\frac{\delta(\boldsymbol{x}_{j},\hat{\boldsymbol{x}}_{\hat{j}})}{MN_{t}\text{log}_{2}(MN_{t})}\times\hskip
85.35826pt$

$\left[\left[\mu_{j,\hat{j}}^{\psi_{\text{row}}}\sum_{k=0}^{\psi_{\text{row}}-1}\left(\begin{array}[]{c}\psi_{\text{row}}-1+k\\\
k\end{array}\right)(1-\mu_{j,\hat{j}})^{k}\right]+\mathcal{\mathbb{E}}\left\\{\mathbb{P}\text{r}\left(\hat{\boldsymbol{x}}_{\text{opt}}\notin\varXi_{\psi_{\text{col}}}\right)\right\\}\right].$
(12)

Based on (12), the RSD algorithm provides a near optimum BER performance when
Term 2 in (9) tends to be zero (i.e.,
$\mathbb{P}\text{r}(\hat{\boldsymbol{x}}_{\text{opt}}\notin\varXi_{\psi_{\text{col}}})\approx
0$); this can be achieved by properly choosing $\psi_{\text{col}}$. In this
paper, $\psi_{\text{col}}$ is empirically chosen such that
$\mathbb{P}\text{r}(\hat{\boldsymbol{x}}_{\text{opt}}\notin\varXi_{\psi_{\text{col}}})\approx
0$.

###  IV-B Expected Complexity Analysis

In this paper, the complexity of the RSD algorithm is measured by the number
of visited nodes in the tree-search needed to estimate the solution. In
general, the complexity of the SD algorithms is a random variable. The general
approximation for the expected SD complexity is [References]

$\Psi^{\text{SD}}\approx
MN_{t}+\sum_{j=1}^{MN_{t}}\sum_{i=1}^{N_{r}}\mathbb{P}\text{r}\left(v(i,j)\leq\zeta\left|\boldsymbol{x}_{t},\mathbf{H},\sigma_{g}^{2},\zeta\right.\right),$
(13)

where $\Psi^{\text{SD}}$ is the expected complexity of an SD algorithm and
$\zeta$ is the pruned radius (i.e., threshold) of that algorithm. It should be
noted that (13) represents the general expression and its solution depends on
the algorithm itself.

To find the conditional probability in (13) for the RSD algorithm, the
distributions of $v(i,j)$ and $\zeta$ should be defined. From (5), $v(i,j)$
has a non-central chi-square distribution with $2i$ degrees of freedom. Thus,
the closed-form of the conditional probability in (13) is [References, (Ch.
2)]

$\mathbb{P}\text{r}\left(v(i,j)\leq\zeta\left|\boldsymbol{x}_{t},\mathbf{H},\sigma_{g}^{2},\zeta\right.\right)=1-Q_{i}\left(\frac{\sqrt{2\gamma_{i,j}^{2}}}{\sigma_{g}}\,,\,\frac{\sqrt{2\zeta}}{\sigma_{g}}\right),$
(14)

where $\gamma_{i,j}^{2}=\sum_{n=1}^{i}|x_{n,t}-x_{n,j}|^{2}$, $x_{n,j}$ is the
$n$-th element of the $j$-th SM transmitted message, and
$Q_{i}(\centerdot,\centerdot)$ is the Marcum Q-function.

To remove the dependency of (14) on $\zeta$, the expectation operation should
be applied for (14) over the distribution of $\zeta$. For simplicity, let us
assume that the RSD algorithm most likely reaches the optimum solution. Thus,
the pruned radius can be given from
$\zeta=\sum_{i=1}^{\psi_{\text{row}}}|g_{i}|^{2}$, where $g_{i}$ denotes the
$i$-th element of the AWGN vector in (1). It is worth noting that this
simplified assumption of $\zeta$ is especially for high SNR. The distribution
of $\zeta$ is a central chi-square with $2\psi_{\text{row}}$ degrees of
freedom and its probability density function, $f_{\zeta}(\zeta)$, is
[References, (Ch. 2)]

$f_{\zeta}(\zeta)=\frac{\left(\zeta\right)^{\psi_{\text{row}}-1}}{\sigma_{g}^{2\psi_{\text{row}}}\left(\psi_{\text{row}}-1\right)!}\,\text{exp}\left(\frac{-\zeta}{\sigma_{g}^{2}}\right).$
(15)

Hence, (14) yields

$\mathbb{P}\text{r}\left(v(i,j)\leq\zeta\left|\boldsymbol{x}_{t},\mathbf{H},\sigma_{g}^{2}\right.\right)=1-\int_{0}^{\infty}Q_{i}\left(\frac{\sqrt{2\gamma_{i,j}^{2}}}{\sigma_{g}}\,,\,\frac{\sqrt{2\zeta}}{\sigma_{g}}\right)\text{d}\zeta.$
(16)

The closed-form expression of (16) can be given as [References]

$\mathbb{P}\text{r}\left(v(i,j)\leq\zeta\left|\boldsymbol{x}_{t},\mathbf{H},\sigma_{g}^{2}\right.\right)=2^{i}\,\text{exp}\left(\frac{-\gamma_{i,j}^{2}}{\sigma_{g}^{2}}\right)\hskip
56.9055pt$

$\hskip
71.13188pt\times\sum_{n=0}^{\psi_{\text{row}}-1}\frac{\left(i\right)_{n}}{2^{n}\,n!}\,_{1}F_{1}\left(n+i;i;\frac{\gamma_{i,j}^{2}}{2\sigma_{g}^{2}}\right),$
(17)

where $\left(i\right)_{n}$ represents the Pochhammer symbol and ${}_{1}F_{1}$
is the Kummer hypergeometric function. Since the RSD algorithm searches for
the solution inside a reduced tree-search with a size of
$\psi_{\text{row}}\times\psi_{\text{col}}$, the approximation of the expected
complexity in (13) becomes

$\Psi^{\text{RSD}}\approx\psi_{\text{col}}+\sum_{j=1}^{\psi_{\text{col}}}\sum_{i=1}^{\psi_{\text{row}}}2^{i}\,\text{exp}\left(\frac{-\gamma_{i,j}^{2}}{\sigma_{g}^{2}}\right)\hskip
65.44142pt$

$\hskip
71.13188pt\times\sum_{n=0}^{\psi_{\text{row}}-1}\frac{\left(i\right)_{n}}{2^{n}\,n!}\,_{1}F_{1}\left(n+i;i;\frac{\gamma_{i,j}^{2}}{2\sigma_{g}^{2}}\right),$
(18)

where $\Psi^{\text{RSD}}$ is the expected complexity of the RSD algorithm.

Alternatively, (16) can be numerically calculated using the Gauss–Laguerre
quadrature [References]. Thus, (13) becomes

$\Psi^{\text{RSD}}\approx\psi_{\text{col}}\left(\psi_{\text{row}}+1\right)-\frac{1}{\left(\psi_{\text{row}}-1\right)!}\hskip
65.44142pt$

$\times\sum_{j=1}^{\psi_{\text{col}}}\sum_{i=1}^{\psi_{\text{row}}}\sum_{k=1}^{\beta}w_{k}\left(z_{k}\right)^{(\psi_{\text{row}}-1)}Q_{k}\left(\frac{\sqrt{2\gamma_{i,j}^{2}}}{\sigma_{g}}\,,\,\sqrt{2z_{k}}\right),$
(19)

where $w_{k}$ and $z_{k}$ are given values based on the order $\beta$, which
is given from [References, (Table 25.9)]. Note that (19) provides a close
value to that in (18) with considerably lower execution time.

##  V Simulation Results

In this section, the BER and ing complexity of the proposed RSD algorithm are
assessed and compared with optimum algorithms in literature, such as
[References], [References], and [References]. Two SM-MIMO systems are
considered; 16-QAM for $8\times 8$ and $16\times 16$ SM-MIMO, respectively. As
mentioned before, $\psi_{\text{col}}$ is empirically chosen to provide the
optimum BER performance (i.e.,
$\mathbb{P}\text{r}(\hat{\boldsymbol{x}}_{\text{opt}}\notin\varXi_{\psi_{\text{col}}})\approx
0$ in (12)) at $\psi_{\text{row}}=N_{r}$, where $\psi_{\text{col}}=70$ and
$180$ for the first and second SM-MIMO systems, respectively. The proposed RSD
algorithm is denoted by RSD-($\psi_{\text{row}}$,$\psi_{\text{col}}$) to show
the values of $\psi_{\text{row}}$ and $\psi_{\text{col}}$. Monte Carlo
simulations are used to obtain the results by running at least $10^{6}$
Rayleigh flat fading channel realizations. The channel state information at
the receiver is considered to be perfectly known.

###  V-A Assessment of Expected Complexity for the RSD Algorithm

The expression in (19) is evaluated for the two considered SM-MIMO systems
using $\beta=7$. The expected complexity coming from (19) provides almost
identical results to (18), however, with added speed. The corresponding
$w_{k}$ and $z_{k}$ at $\beta=7$ are given in [References, (Table 25.9)].

Figures 2 and 3 depict the average number of visited nodes of the RSD
algorithm for $16$-QAM with $8\times 8$ SM-MIMO and $16$-QAM with $16\times
16$ SM-MIMO, respectively. By decreasing $\psi_{\text{row}}$, the size of the
tree-search decreases and the complexity decreases correspondingly, as shown
in the figures. It is also notable that the RSD algorithm requires less
complexity to find the solution as the SNR increases. As seen from these
figures, the theoretical analysis in (19) (or in (18)) provides a tight
expression for simulation results, for different values of
$\psi_{\text{row}}$. Note that (19) perfectly matches the simulation results
in the higher SNR, which verifies the feasibility of the pruned radius
simplification assumption mentioned in Section IV-B.

###  V-B Comparisons with Literature Algorithms

In this subsection, the BER and complexity are compared with those of the
literature algorithms (e.g., [References], [References], and [References]).
The complexity comparison is assessed by calculating the complexity reduction
ratio which is defined as

$\Psi_{\text{Reduction}}^{\Omega}=\frac{MN_{t}N_{r}-\Psi^{\Omega}}{MN_{t}N_{r}}=1-\frac{\Psi^{\Omega}}{MN_{t}N_{r}},$
(20)

where $\Psi_{\text{Reduction}}^{\Omega}$ is the complexity reduction ratio for
the $\Omega\in$ {RSD, SD-[References], SD-[References], SD-[References]}
algorithm.

Figures 4 and 5 show the BER performance of the RSD algorithm compared to the
optimum algorithms, for $16$-QAM with $8\times 8$ SM-MIMO and $16$-QAM with
$16\times 16$ SM-MIMO, respectively. As shown from these figures, the
RSD-(8,70) and RSD-(16,180) provide the same BER as the ML BER performance for
$16$-QAM with $8\times 8$ SM-MIMO and $16$-QAM with $16\times 16$ SM-MIMO,
respectively. It should be noted that the SD-[References] and SD-[References]
algorithms provide the same BER performance as the ML and SD-[References]
algorithms, and their results are omitted for the visibility of figures. Based
on the reliable design of the RSD algorithm, sub-optimal BER performances can
be obtained by varying the value of $\psi_{\text{row}}$. The BER analysis in
(12) is confirmed via simulation results.

Figures 6 and 7 depict the complexity reduction ratio of all algorithms for
$16$-QAM with $8\times 8$ SM-MIMO and $16$-QAM with $16\times 16$ SM-MIMO,
respectively. As seen from these figures, the RSD algorithm provides the best
reduction in complexity compared to all existing algorithms. It also offers
reliable decoding complexities that vary from $72\%$ to $92\%$ for $16$-QAM
with $8\times 8$ SM-MIMO and from $68\%$ to $95\%$ for $16$-QAM with $16\times
16$ SM-MIMO. This reliability in the decoding can fit a wide range of
practical application requirements.

Fig. 2: Average number of visited nodes of the proposed RSD algorithm for
$16$-QAM and $8\times 8$ SM-MIMO system. Fig. 3: Average number of visited
nodes of the proposed RSD algorithm for $16$-QAM and $16\times 16$ SM-MIMO
system. Fig. 4: BER comparison for the $16$-QAM and $8\times 8$ SM-MIMO.

##  VI Conclusion

This paper proposes a novel reliable algorithm to decode SM transmitted
messages. The BER performance and complexity of the proposed algorithm are
theoretically derived. The proposed algorithm provides a significant reduction
in the decoding complexity (e.g., up to $95\%$) compared to ML, without
sacrificing the BER performance. A flexible trade-off between the BER
performance and complexity is presented to demonstrate the reliability of the
proposed algorithm.

Fig. 5: BER comparison for the $16$-QAM and $16\times 16$ SM-MIMO. Fig. 6:
Complexity reduction comparison for the $16$-QAM and $8\times 8$ SM-MIMO
system. Fig. 7: Complexity reduction comparison for the $16$-QAM and $16\times
16$ SM-MIMO system.

## References

  * [1] E. Basar, “Index modulation techniques for 5G wireless networks,” IEEE Commun. Mag., vol. 54, no. 7, pp. 168–175, Jul. 2016.
  * [2] Z. Pan et al., “Uplink spatial modulation SCMA system,” IEEE Commun. Lett., vol. 23, no. 1, pp. 184-187, Jan. 2019.
  * [3] I. Al-Nahhal, O. A. Dobre, E. Basar, and S. Ikki, “Low-cost uplink sparse code multiple access for spatial modulation,” IEEE Trans. Veh. Technol., vol. 68, no. 9, pp. 9313-9317, Jul. 2019.
  * [4] R. Mesleh et al., “Spatial modulation,” IEEE Trans. Veh. Technol., vol. 57, no. 4, pp. 2228–2241, July 2008.
  * [5] M. Di Renzo, H. Haas, and P. M. Grant, “Spatial modulation for multiple-antenna wireless systems: A survey,” IEEE Commun. Mag., vol. 49, no. 12, pp. 182–191, Dec. 2011.
  * [6] E. Basar, U. Aygolu, E. Panayırcı, and H. V. Poor, “Performance of spatial modulation in the presence of channel estimation errors,” IEEE Commun. Lett., vol. 16, no. 2, pp. 176–179, Feb. 2012.
  * [7] A. Younis et al., “Generalised sphere decoding for spatial modulation,” IEEE Trans. Commun., vol. 61, no. 7, pp. 2805–2815, July 2013.
  * [8] I. Al-Nahhal, O. A. Dobre, and S. Ikki, “Quadrature spatial modulation decoding complexity: Study and reduction,” IEEE Wireless Commun. Lett., vol. 6, pp. 378-381, Jun. 2017.
  * [9] I. Al-Nahhal et al., “Low complexity decoders for spatial and quadrature spatial modulations,” in Proc. IEEE VTC Spring, Jun. 2018, pp. 1–5.
  * [10] I. Al-Nahhal, E. Basar, O. A. Dobre, and S. Ikki, “Optimum low-complexity decoder for spatial modulation,” IEEE J. Sel. Areas Commun., vol. 37, no. 9, pp. 2001-2013, Jul. 2019.
  * [11] Q. Tang, Y. Xiao, P. Yang, Q. Yu, and S. Li, “A new low-complexity near-ml detection algorithm for spatial modulation,” IEEE Wireless Commun. Lett., vol. 2, no. 1, pp. 90–93, Feb. 2013.
  * [12] L. Xiao, P. Yang, S. Fan, S. Li, L. Song, and Y. Xiao, “Low-complexity signal detection for large-scale quadrature spatial modulation systems,” IEEE Commun. Lett., vol. 20, pp. 2173-2176, Nov. 2016.
  * [13] I. Al-Nahhal et al., “Modified zero forcing decoder for ill-conditioned channels” in Proc. IFIP Wireless Days (WD), Nov 2013, pp. 1–3.
  * [14] I. Al-Nahhal et al., “Flexible fractional K-best sphere decoding for uncoded MIMO channels,” IEICE Communications Express, vol., 4, pp. 20-25, Jan. 2015.
  * [15] I. Al-Nahhal et al., “Reduced complexity k-best sphere decoding algorithms for ill-conditioned MIMO channels,” in Proc. IEEE Annu. Consum. Commun. Netw. Conf., pp. 183-187, Jan. 2016.
  * [16] R. Mesleh, S. S. Ikki, and H. M. Aggoune, “Quadrature spatial modulation,” IEEE Trans. Veh. Technol., vol. 64, pp. 2738–2742, Jun. 2015\.
  * [17] J. Proakis, Digital Communications Systems Engineering, 4th ed. McGraw-Hill, New Yourk, 2000.
  * [18] P. C. Sofotasios et al., “Solutions to integrals involving the Marcum Q-function and applications,” IEEE Signal Process. Lett., vol. 22, no. 10, pp. 1752–1756, Oct. 2015.
  * [19] M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th ed. Dover Publications, New York, 1972.