# Iterated function systems over arbitrary shift spaces

Dawoud Ahmadi<EMAIL_ADDRESS><EMAIL_ADDRESS>Mahdi
Aghaee<EMAIL_ADDRESS>
###### Abstract

The orbit of a point $x\in X$ in a classical iterated function system (IFS)
can be defined as $\\{f_{u}(x)=f_{u_{n}}\circ\cdots\circ f_{u_{1}}(x):$
$u=u_{1}\cdots u_{n}$ is a word of a full shift $\Sigma$ on finite symbols and
$f_{u_{i}}$ is a continuous self map on $X$ $\\}$. One also can associate to
$\sigma=\sigma_{1}\sigma_{2}\cdots\in\Sigma$ a non-autonomous system
$(X,\,f_{\sigma})$ where the trajectory of $x\in X$ is defined as
$x,\,f_{\sigma_{1}}(x),\,f_{\sigma_{1}\sigma_{2}}(x),\ldots$. Here instead of
the full shift, we consider an arbitrary shift space $\Sigma$. Then we
investigate basic properties related to this IFS and the associated non-
autonomous systems. In particular, we look for sufficient conditions that
guarantees that in a transitive IFS one may have a transitive
$(X,\,f_{\sigma})$ for some $\sigma\in\Sigma$ and how abundance are such
$\sigma$’s.

Keywords: iterated function systems (IFS), non-autonomous system, topological
transitivity, point transitivity.
2010 Mathematics Subject Classification: 37B55, 37B05, 37B10.

##  1 Introduction

In a classical dynamical system, here called _conventional dynamical system_ ,
we have a phase space and a unique map where the trajectories of points are
obtained by iterating this map. However, in various problems, including
applied ones, one may have some finite sequence of maps in place of a single
map acting on the same phase space. As an example let $X$ be the space of
mixture of some materials which are supposed to be mixed by application of two
robotic arms $r_{0}$ and $r_{1}$ and only one of them at each unit of time.
Due to some technical considerations, two $r_{1}$ cannot be applied in a row,
though this consideration is not on place for $r_{0}$. Thus the application of
these arms, and hence the dynamics of the system, is bound to the golden
subshift, i.e., the subshift whose forbidden set is $\\{11\\}$. In fact, there
are many natural processes whose evolution evolve with discrete time which are
involved with two or more interactions. For instance, in Physics by two or
more maps have appeared in [2, 20], Economy in [22] and Biology in [7]. In
Mathematics, this has been studied either by non-autonomous systems in many
literature such as [15] or as iterated function system (IFS) for constructing
and studying some fractals in [8, 13] or for investigating dynamical
properties in some studies such as [3, 4, 11, 12].

In a “classical” IFS, a compact metric space $X$ and a set of some $k$ finite
continuous functions $\\{f_{0},\,\cdots,\,f_{k-1}\\}$ on $X$ are assumed and
the trajectory of a point $x\in X$ is considered to be the action on $x$ of
the sequence of freely combination of those maps, or action on $x$ of
combination of those maps over the words of a full shift: just write
$f_{u}=f_{u_{1}}\circ\cdots\circ f_{u_{m}}$ where $u=u_{1}\cdots u_{m}$ is a
word of the full shift over $k$ symbols. Hence no limitation is applied as in
our aforesaid example on the robotic arms where there words were forbidden to
have $11$ as a subword. The limitation applied on the shift space would
transfer to some limitations on the system. For instance, a system may be
topological transitive in classical IFS but not in our case, i.e., when the
full shift is replaced with a more general subshift.

Thus one may look at $X$ as a phase space and the subshift $\Sigma$ as a
parameter space showing how the maps must be combined.

The present paper is organized as follows. In Section 2, we formalize the
definitions and notations. Section 3 is mainly devoted to the definitions of
transitivity in IFS and relation between them. In particular, we show that
when the shift space is sofic, topological transitivity in the constituent IFS
implies the point transitivity along a transitive orbit in the shift space; a
fact which is not necessarily satisfied for nonsofics. In Section 4, we like
to see how large the set $S=\\{\sigma\in\Sigma:\;\exists\,x\in
X,\,\overline{\mathcal{O}_{\sigma}(x)}=X\\}$ can be. Section 5 mixing and
exactness of an IFS versus to those properties along orbits through some
examples has been considered.

##  2 Preliminaries

###  2.1 Iterated function systems

Throughout the paper, $X$ will be a compact metric space. The _classical_
iterated function system (IFS) consists of finitely many continuous self maps
$\mathcal{F}=\left\\{f_{0},\,\ldots,\,f_{k-1}\right\\}$ on $X$. The _forward
orbit_ of a point $x\in X$, denoted by $\mathcal{O}^{+}(x)$, is the set of all
values of finite possible combinations of $f_{i}$’s at $x$. We need the
following equivalent statement: Let $\Sigma_{|\mathcal{F}|}$ be the full shift
on $k$ symbols and let $\mathcal{L}(\Sigma_{|\mathcal{F}|})$ called the
_language of $\Sigma_{|\mathcal{F}|}$_ be the set of words or blocks. Define
$f_{u}(x):X\rightarrow X$ by

$f_{u_{n}}\circ\cdots\circ f_{u_{1}}(x),\quad u=u_{1}\cdots
u_{n}\in\mathcal{L}(\Sigma_{|\mathcal{F}|}).$ (1)

Then
$\mathcal{O}^{+}(x)=\\{f_{u}(x):\;u\in\mathcal{L}(\Sigma_{|\mathcal{F}|})\\}$.
Such iterated function systems, here called _classical IFS_ , have been the
subject of study for quite a long time.

Here we define an IFS to be

$\mathfrak{I}=(X,\,\mathcal{F}=\left\\{f_{0},\,\ldots,\,f_{k-1}\right\\},\,\Sigma).$
(2)

where each $f_{i}$ is continuous and $\Sigma$ is an arbitrary subshift on $k$
symbols, not necessarily the full shift $\Sigma_{|\mathcal{F}|}$ as in the
classical IFS. Later a brief review of symbolic dynamics will be given in
subsection 2.2. By this setting, $\Sigma_{|\mathcal{F}|}$ above will be
replaced with $\Sigma$ and thus
$\mathcal{O}^{+}(x)=\\{f_{u}(x):\;u\in\mathcal{L}(\Sigma)\\}$ is the forward
orbit of $x$. In particular, $f_{u}(f_{v}(x))=f_{vu}(x)$ whenever $vu$ is
admissible or equivalently $vu\in\mathcal{L}(\Sigma)$. Let $u=u_{1}\cdots
u_{n}\in\mathcal{L}(\Sigma)$ and set $u^{-1}:=u_{n}\cdots u_{1}$. Then for
$A\subseteq X$,

$\displaystyle(f_{u})^{-1}(A)$ $\displaystyle=$
$\displaystyle(f_{u_{n}}\circ\cdots\circ f_{u_{1}})^{-1}(A)$ $\displaystyle=$
$\displaystyle f^{-1}_{u_{1}}\circ\cdots\circ f^{-1}_{u_{n}}(A)$
$\displaystyle=$ $\displaystyle f^{-1}_{u^{-1}}(A),$

where for the last equality, we used (1). Also

$\displaystyle f^{-1}_{u^{-1}}(f^{-1}_{v^{-1}}(A))$ $\displaystyle=$
$\displaystyle f^{-1}_{v^{-1}u^{-1}}(A)=f^{-1}_{(uv)^{-1}}(A)$
$\displaystyle=$ $\displaystyle\left(f_{uv}\right)^{-1}(A).$

Thus the backward orbit and the (full) orbit of a point $x\in X$ are
$\mathcal{O}_{-}(x)=\\{f^{-1}_{u^{-1}}(x):\;u\in\mathcal{L}(\Sigma)\\}$ and
$\mathcal{O}(x)=\mathcal{O}^{+}_{-}(x)=\mathcal{O}^{+}(x)\cup\mathcal{O}_{-}(x)$
respectively.

When all $f_{i}$’s are homeomorphisms, the backward, forward and full
trajectory of $x$ is defined.

We say $\mathcal{F}=\\{f_{0},\,\ldots,\,f_{k-1}\\}$ is _surjective_ ,
_injective_ , _homeomorphism_ if all $f_{i}$’s in $\mathcal{F}$ are so.

When $k=1$ and $\Sigma=\\{0^{\infty}\\}$, we simply have the classical
dynamical system, here called _conventional dynamical system_ denoted either
by the pair $(X,\,f)$ or $\mathfrak{I}=(X,\,\\{f_{0}\\},\,\\{0^{\infty}\\})$.

###  2.2 Symbolic dynamics

A brief recall of the symbolic dynamics is given here. Notations and main
ideas are borrowed from [17] and the proofs of the claims can be found there.
Let $\mathcal{A}$ be a non-empty finite set and let
$\Sigma_{|\mathcal{A}|}=\mathcal{A}^{\mathbb{Z}}$ (resp.
$\mathcal{A}^{\mathbb{N}}$) be the collection of all bi-infinite (resp. right-
infinite) sequences of symbols from $\mathcal{A}$. The shift map on
$\Sigma_{|\mathcal{A}|}$ is the map $\tau$ where
$\tau(\sigma)=\sigma^{\prime}$ is defined by
$\sigma^{\prime}_{i}=\sigma_{i+1}$. The pair $(\Sigma_{|\mathcal{A}|},\,\tau)$
is the _full shift_ and any closed invariant subset $\Sigma$ of
$\Sigma_{|\mathcal{A}|}$ is called a _subshift_ or a _shift space_. A _word_
or _block_ over $\mathcal{A}$ is a finite sequence of symbols from
$\mathcal{A}$. Denote by $\mathcal{L}_{n}(\Sigma)$ the set of all admissible
$n$-words and call
$\mathcal{L}(\Sigma):=\bigcup_{n=0}^{\infty}\mathcal{L}_{n}(\Sigma)$ the
_language_ of $\Sigma$. For $u\in\mathcal{L}_{k}(\Sigma)$, let the cylinder
${}_{\ell}[u]_{\ell+k-1}$ $=_{\ell}[u_{\ell}\cdots u_{\ell+k-1}]_{\ell+k-1}$
be the set
$\\{\sigma=\cdots\sigma_{-1}\sigma_{0}\sigma_{1}\cdots\in\Sigma:\sigma_{\ell}\cdots\sigma_{\ell+k-1}=u\\}$.
If $\ell=0$, we drop the subscripts and we just write $[u]$.

A shift space $\Sigma$ is _irreducible_ if for every ordered pair of words
$u,\,v\in\mathcal{L}(\Sigma)$ there is a word $w\in\mathcal{L}(\Sigma)$ so
that $uwv\in\mathcal{L}(\Sigma)$. A point $\sigma\in\Sigma$ is _transitive_ if
every word in $\Sigma$ appears in $\sigma$ infinitely many often. A subshift
$\Sigma$ is irreducible iff $\Sigma$ has a transitive point.

Shift spaces described by a finite set of forbidden blocks are called _shifts
of finite type_ (SFT) and their factors are called _sofic_. A word
$w\in\mathcal{L}(\Sigma)$ is called _synchronizing_ if
$uwv\in\mathcal{L}(\Sigma)$ whenever $uw,wv\in\mathcal{L}(\Sigma)$. A
_synchronized system_ is an irreducible shift which has a synchronizing word.
Any sofic is synchronized.

A subshift $\Sigma$ is _specified_ , or has the _specification property_ , if
there is $N\in\mathbb{N}$ such that if $u,v\in\mathcal{L}(\Sigma)$, then there
is $w$ of length $N$ so that $uwv\in\mathcal{L}(\Sigma)$. A specified system
is mixing and synchronized and any mixing sofic is specified. A _coded system_
is the closure of the set of sequences obtained by freely concatenating the
words in a list of words. In particular, any synchronized system is coded.

All synchronized systems have an (edge) labeled graph presentation called
_cover_. These are directed graphs whose edges are with assigned labels from
$\mathcal{A}$ and infinite walk on the graph and recording the labels will
represent a point in the subshift. The set of all such points is dense in the
subshift.

####  2.2.1 Factors and extensions in an IFS

There is a natural way to define factors in a non-autonomous and in classical
iterated function systems [15] and [18] Let $(X,\,f_{1,\,\infty})$ and
$(Y,\,g_{1,\,\infty})$ be two non-autonomous systems. Then,
$(Y,\,g_{1,\,\infty})$ is a factor of $(X,\,f_{1,\,\infty})$, if there is a
surjective continuous function $\varphi:X\rightarrow Y$ such that
$\varphi\circ f_{i}(x)=g_{i}\circ\varphi(x)$ for each $x\in X$ and each
$i\in\mathbb{N}$. Also let
$\mathfrak{I}=(X,\,\mathcal{F},\,\Sigma_{|\mathcal{A}|})$ and
$\mathfrak{I}^{\prime}=(Y,\,\mathcal{G},\,\Sigma_{|\mathcal{A}^{\prime}|})$ be
two classical IFS where $\Sigma_{|\mathcal{A}|}$ and
$\Sigma_{|\mathcal{A}^{\prime}|}$ are full shifts over the finite alphabets
$\mathcal{A}$ and $\mathcal{A}^{\prime}$. Then, $\mathfrak{I}^{\prime}$ is a
factor of $\mathfrak{I}$ if $|\mathcal{A}|\geq|\mathcal{A}^{\prime}|$ and
there are surjective continuous maps
$\Psi:\Sigma_{|\mathcal{A}|}\rightarrow\Sigma_{|\mathcal{A}^{\prime}|}$ and
$\varphi:X\rightarrow Y$ such that $\varphi\circ
f_{\sigma_{i}}(x)=g_{\Psi(\sigma_{i})}\circ\varphi(x)$ for each $x\in X$ and
each $\sigma\in\Sigma_{|\mathcal{A}|}$. In the latter, by the way it has been
defined, a necessity for $\mathfrak{I}^{\prime}$ being a factor of
$\mathfrak{I}$ is that $\Sigma_{|\mathcal{A}^{\prime}|}$ being a factor of
$\Sigma_{|\mathcal{A}|}$.

Now we set up to define factors in general IFS. First let $\Sigma$ and
$\Sigma^{\prime}$ be subshifts on the alphabets $\mathcal{A}$ and
$\mathcal{A}^{\prime}$ respectively and suppose that $\Sigma^{\prime}$ is a
factor of $\Sigma$ via an $(m+n+1)$-block map
$\Psi:\mathcal{B}_{m+n+1}(\Sigma)\to\mathcal{A}$. Let
$\psi=\Psi_{\infty}=\Psi^{[-m,\,n]}_{\infty}:\Sigma\to\Sigma^{\prime}$ be the
induced sliding block map with

$\psi(\sigma)=\psi(\cdots\sigma_{-1}\sigma_{0}\sigma_{1}\cdots)=\cdots\sigma^{\prime}_{-1}\sigma^{\prime}_{0}\sigma^{\prime}_{1}\cdots$

whenever
$\Psi(\sigma_{i-m}\sigma_{i-m+1}\cdots\sigma_{i+n})=\sigma^{\prime}_{i}$. For
one sided shifts, let $m=0$. If necessary, by passing to higher block shifts
[17, §1.4], and replacing $\Sigma$ and $\Sigma^{\prime}$ with suitable
conjugate subshifts, one may consider that $\Psi$ to be a 1-block map.

######  Definition 2.1.

Let $\varphi$ be a continuous map from $X$ onto $Y$. Then
$\mathfrak{I}^{\prime}=(Y,\mathcal{G}=\\{g_{0},\,\ldots,\,g_{\ell^{\prime}}\\},\,\Sigma^{\prime})$
is a _factor_ of
$\mathfrak{I}=(X,\mathcal{F}=\\{f_{0},\,\ldots,\,f_{\ell}\\},\,\Sigma)$ if
$\Sigma^{\prime}$ is a factor of $\Sigma$ as above and for all $y\in Y$ and
$x\in\varphi^{-1}(y)$

$\varphi\circ
f_{\sigma_{i-m}\cdots\sigma_{i+n}}(x)=g_{\sigma_{i}^{\prime}}(y).$

Hence, $\mathfrak{I}^{\prime}$ is a factor of $\mathfrak{I}$, if for each
$\sigma\in\Sigma$, the non-autonomous system $(Y,\,g_{\psi(\sigma)})$ is a
factor of $(X,\,f_{\sigma})$ via $\varphi:X\rightarrow Y$. In this situation,
$\mathfrak{I}$ is called an _extension_ of $\mathfrak{I}^{\prime}$. If
$\mathfrak{I}$ is also a factor of $\mathfrak{I}^{\prime}$, then
$\mathfrak{I}$ and $\mathfrak{I}^{\prime}$ are _conjugate_.

If necessary, by passing to an $N$-higher block shifts for some
$N\in\mathbb{N}$ and replacing $\Sigma$ with that new shift and $\mathcal{F}$
with $\\{f_{u}:\;u\in\mathcal{L}_{N}(\Sigma)\\}$, we may consider that $\Psi$
defining the block factor map between $\Sigma$ and $\Sigma^{\prime}$,
$N$-higher block shift, to be a 1-block map.

It is trivial to check that all dynamical properties defined in Definitions
3.1 and 3.4 are invariant under the factor map.

##  3 Transitivity

Two sorts of transitivity are very common in the study of topological
dynamical systems: topological transitivity and point transitivity. These two
concepts are the same for surjective conventional dynamical systems on the
compact metric spaces such as subshifts but not for IFS’s and non-autonomous
dynamical systems. Hence we say a transitive point in $\Sigma$ but will
emphasize for point transitivity or topological transitivity in other places.

######  Definition 3.1.

Consider $\mathfrak{I}$ as in (2) and let $U$ and $V$ be arbitrary open sets
in $X$. Then $\mathfrak{I}$ is

  1. 1.

_“forward” point transitive_ , if there is $x\in X$ such that
$\\{f_{u}(x):\;u\in\mathcal{L}(\Sigma)\\}$ is dense in $X$. We drop “forward”
when it is clear from the context. _Backward point transitivity_ is likewise
defined.

  2. 2.

_topological transitive_ , if there is $u\in\mathcal{L}_{n}(\Sigma)$ such that
$f_{u}(U)\cap V\neq\emptyset$.

  3. 3.

_mixing_ , if there is $M=M(U,\,V)\in\mathbb{N}$ such that for $n\geq M$,
there is $u\in\mathcal{L}_{n}(\Sigma)$ such that $f_{u}(U)\cap
V\neq\emptyset$.

  4. 4.

_exact_ , if there is $u(U)\in\mathcal{L}({\Sigma})$ such that for any
$uu^{\prime}\in\mathcal{L}(\Sigma)$, $f_{uu^{\prime}}(U)=X$.

We have the following implications in any IFS:

$\text{exactness }\Rightarrow\text{ mixing }\Rightarrow\text{ topological
transitivity }\Rightarrow\text{point transitivity}.$ (3)

The first two implications follow from the definition and the last from the
next proposition. Also, since conventional dynamical systems are IFS, they
provides examples that the first two implications are not reversible.

######  Proposition 3.2.

Let $\mathfrak{I}=(X,\,\mathcal{F},\,\Sigma)\;$be a surjective IFS. If for
arbitrary non-empty open sets $U,\,V$ there is $u\in\mathcal{L}(\Sigma)$ such
that $(f_{u})^{-1}(U)\cap V\neq\emptyset$, then $\mathfrak{I}$ is point
transitive.

###### Proof.

Let $\mathcal{B}=\\{U_{n}:n\in\mathbb{N}\\}$ be a countable base for $X$. Fix
$n\in\mathbb{N}$ and set

$G_{n}:=\cup_{u\in\mathcal{L}(\Sigma)}(f_{u})^{-1}(U_{n}).$ (4)

By the assumption for an arbitrary open set $V$, $G_{n}\cap V\neq\emptyset$
and so the open set $G_{n}$ is dense and as a result,
$\cap_{n\in\mathbb{N}}G_{n}$ is residual. Hence for
$x\in\cap_{n\in\mathbb{N}}G_{n}$ and any $n\in\mathbb{N}$, there is
$u\in\mathcal{L}(\Sigma)$ such that $x\in(f_{u})^{-1}(U_{n})$. This means
$f_{u}(x)\in U_{n}$ and so $x$ is a transitive point. ∎

Unlike a surjective conventional dynamical system, the last implication in (3)
is not reversible. This fact was noticed in some literature [16, 19]; however,
we did not find any example to justify, so we bring our own.

######  Example 3.3.

Let $\mathfrak{I}=(X,\,\\{f_{0},\,f_{1},\,f_{2}\\},\,\Sigma_{|\mathcal{F}|})$
where $X=\\{1/n:\;n\in\mathbb{N}\\}\cup\\{0\\}\subset\mathbb{R}$ is equipped
with subspace topology.

Our maps are defined as follows. (See Figure 1.) For all $i$, $f_{i}(0)=0$ and
$f_{i}(1)=1$.

$\displaystyle f_{0}(\frac{1}{n+1})$ $\displaystyle=$
$\displaystyle\frac{1}{n},\quad n\geq 1,$ $\displaystyle
f_{1}(\frac{1}{2n+1})$ $\displaystyle=$ $\displaystyle\frac{1}{2n},\quad n\geq
1,$ $\displaystyle f_{1}(\frac{1}{2n})$ $\displaystyle=$
$\displaystyle\frac{1}{2n+1},\quad n\geq 1\quad\text{and}\quad
f_{1}(\frac{1}{2})=\frac{1}{3}.$

Also, $f_{2}(\frac{1}{4})=\frac{1}{2}$, $f_{2}(\frac{1}{2})=\frac{1}{3}$ and

$\displaystyle f_{2}(\frac{1}{2n+1})$ $\displaystyle=$
$\displaystyle\frac{1}{2n+2},\quad n\geq 1,$ $\displaystyle
f_{2}(\frac{1}{2n+2})$ $\displaystyle=$ $\displaystyle\frac{1}{2n+1},\quad
n\geq 2.$

All maps are continuous, open and surjective. Both $f_{1}$ and $f_{2}$ are
homeomorphism, but $f_{0}$ is not injective: $f_{0}(\frac{1}{2})=f_{0}(1)=1$.

Observe that any point $x=\frac{1}{n}$, $n\geq 2$ is transitive. However, the
system is not topological transitive. Because, for any $u$,
$f_{u}(\\{1\\})\cap\\{\frac{1}{2}\\}=\emptyset$. It is easy to observe that
$\mathfrak{I}$ is neither topological nor point transitive along any orbit.

$\cdots$$f_{0}$$f_{1}$$f_{2}$$f_{0}$$f_{1}$$f_{2}$$f_{1}$$f_{2}$$f_{1}$$f_{1}$$f_{1}$$f_{2}$$f_{1}$$f_{2}$$f_{2}$$f_{0}$$f_{0}$$f_{0}$$f_{0}$$f_{0}$$f_{0}$$f_{1}$$f_{2}$$0$$1$$\frac{1}{2}$
Figure 1: Nodes represent the points in $X$. The farthest node on the right is
1, the second $\frac{1}{2}$ and so on.

It is worth mentioning that if $\mathcal{F}$ was homeomorphism in Definition
3.1, then topological and point transitivity were equivalent [6].

###  3.1 Dynamics along an orbit as a non-autonomous dynamical system

Let $X$ be a topological space and $f_{n}:X\to X$ a continuous map for
$n\in\mathbb{N}$. Then the sequence $\\{f_{n}\\}_{1}^{\infty}$ denoted by
$f_{1,\,\infty}$ defines a non-autonomous discrete dynamical system
$(X,\,f_{1,\,\infty})$ [15]. In an IFS, dynamics along a $\sigma$ also defines
a non-autonomous system which we show it by $(X,\,f_{\sigma})$ or
$f_{\sigma}:=\\{f_{\sigma_{i}}\\}_{i=1}^{\infty}$ (resp.
$f_{\sigma}:=\\{f_{\sigma_{i}}\\}_{i=-\infty}^{+\infty}$) when $\Sigma$ is one
sided (resp. two sided). If $\Sigma$ is over a finite alphabet, then clearly
$f_{\sigma}$ is defined only by finitely many different $f_{i}$’s.

Let $\sigma=\sigma_{1}\sigma_{2}\cdots\in\Sigma$. Then the sequence
$x,\,f_{\sigma_{1}}(x),\,f_{\sigma_{1}\sigma_{2}}(x),\ldots$ is the
_trajectory of $x$ along_ $\sigma$ and $\mathcal{O}^{+}_{\sigma}(x)$ the set
of points in this trajectory is the _(forward) orbit of $x$ along $\sigma$_.
The backward orbit and backward trajectory may be defined similarly for the
case where $\Sigma$ is a two sided subshift. Hence one may say that
$\mathfrak{I}=(X,\,\mathcal{F},\,\Sigma)\;$has property $P$ along
$\sigma\in\Sigma$ if the respective non-autonomous system $(X,\,f_{\sigma})$
has property $P$. By this the following definition may sound abundance, though
we bring it for the sake of completeness.

######  Definition 3.4.

Let $\mathfrak{I}=(X,\,\mathcal{F},\,\Sigma)\;$be an IFS and $U$, $V$
arbitrary non-empty open sets in $X$. Then $\mathfrak{I}$ is called

  1. 1.

_forward point transitive along an orbit_ $\sigma\in\Sigma$, if there is a
point $x\in X$, called the transitive point, such that
$\overline{\mathcal{O}_{\sigma}^{+}(x)}=X$.

  2. 2.

_topological transitive along an orbit_ $\sigma\in\Sigma$, if there is
$n\in\mathbb{N}$ such that $f_{\sigma_{1}\cdots\sigma_{n}}(U)\cap
V\neq\emptyset$.

  3. 3.

_mixing_ (resp. _exact_) _along an orbit_ $\sigma\in\Sigma$, if there is
$N\in\mathbb{N}$ such that for $n\geq N$,
$f_{\sigma_{1}\cdots\sigma_{n}}(U)\cap V\neq\emptyset$ (resp.
$f_{\sigma_{1}\cdots\sigma_{n}}(U)=X$).

Similar implications as in (3) hold here as well. So we have the following
result.

######  Proposition 3.5.

[21, Proposition 4.6] If an IFS has topological transitivity along $\sigma$,
then it is point transitive along $\sigma$.

###### Proof.

The proof is similar to the proof of Proposition 3.2 by replacing (4) with

$G_{n}=\cup_{\ell\in\mathbb{N}}(f_{\sigma_{1}\sigma_{2}\cdots\sigma_{\ell}})^{-1}(U_{n})$
and applying the same reasoning. ∎

The converse of the above proposition is not necessarily true as the next
example shows. This example also shows that point transitivity along an orbit
does not imply that the transitive points are residual along that orbit.

######  Example 3.6.

Let $X=[0,\,1]$ and
$\mathfrak{I}=(X,\,\\{f_{0},\,f_{1}\\},\,\Sigma_{|\mathcal{F}|})$ where

$f_{0}(x)=\begin{cases}2x,&0\leq x\leq\dfrac{1}{2},\\\ 1&\dfrac{1}{2}\leq
x\leq 1,\end{cases}\quad\text{and}\quad f_{1}(x)=\begin{cases}0,&0\leq
x\leq\dfrac{1}{2},\\\ 2x-1,&\dfrac{1}{2}\leq x\leq 1.\end{cases}$

Also let $f:[0,\,1]\to[0,\,1]$ be defined as $f(x)=2x\mod 1$, i.e.

$f(x)=\begin{cases}f_{0}(x),&0\leq x\leq\dfrac{1}{2},\\\
f_{1}(x),&\dfrac{1}{2}\leq x\leq 1.\end{cases}$

Let $z\in(0,\,1/2)$ be a transitive point of $f$ and set
$\sigma:=\sigma_{1}\sigma_{2}\cdots\in\Sigma_{|\mathcal{F}|}$ where
$\sigma_{1}=0$ and for $i>1$, $\sigma_{i}=0$ (resp. $\sigma_{i}=1$) whenever
$f_{\sigma_{1}\cdots\sigma_{i-1}}(z)\in(0,\,1/2)$ (resp.
$f_{\sigma_{1}\cdots\sigma_{i-1}}(z)\in(1/2,\,1)$). By this settings, $z$ is a
transitive point and so the non-autonomous system $([0,\,1],\,f_{\sigma})$ is
point transitive, but not topological transitive. Because for $U=(1/2,\,1)$,
$V=(0,\,1/2)$ and for any $n\in\mathbb{N}$,
$f_{\sigma_{1}\cdots\sigma_{n}}(U)\cap V=\emptyset$.

###  3.2 Transitivity in IFS vs transitivity in the subshift

In general there is not a meaningful relation between the dynamical properties
of $(\Sigma,\,\tau)$ and that of $\mathfrak{I}$. For instance consider (2) and
let $X=[0,\,1]$, $\mathcal{F}=\\{f_{0}(x)=2x\mod 1,\,f_{1}(x)\equiv 0\\}$ and
$\Sigma=\Sigma_{|\mathcal{F}|}=\\{0,\,1\\}^{\mathbb{N}}$. Then, for any open
set $U\subset X$, there is some $m$ such that for $u=0^{m}$, $f_{u}(U)=X$.
Thus interesting dynamics happens along just one point $\sigma\in\Sigma$,
i.e., $\sigma=0^{\infty}$. Surely there will be some relations when $f_{i}$’s
are surjective and some conditions exist on $\Sigma$. This is what we are
interested to deal with.

So far we know that transitivity along an orbit defined in Definition 3.4
implies the transitivity of the system defined in Definition 3.1. However, the
converse is not necessarily true as we will see in Example 3.13. Having this
in mind, we like to address the following questions in this section.

  1. 1.

Does transitivities given in 3.1 imply some sort of transitivity given in
Definition 3.4?

  2. 2.

If the answer to the above question is affirmative, in which situation there
is a transitive $t\in\Sigma$ such that for some $x\in X$,
$\overline{{O}^{+}_{t}(x)}=X$?

The following example shows, as one expects, that transitivity depends on the
subshift.

######  Example 3.7.

Let $\mathfrak{I}=(X,\,\mathcal{F},\,\Sigma)$ where $\Sigma$ is an SFT
generated by $\mathcal{W}=\\{01,\,10\\}$ and $f_{0}$ is the shift map on the
two sided full shift $X=\\{0,\,1\\}^{\mathbb{Z}}$ and $f_{1}=f_{0}^{-1}$.
Clearly this system is not point transitive. Moreover, if
$W=_{-1}\\!\\![000]_{1}$ and $V=_{-1}\\!\\![111]_{1}$ are two open central
cylinders in $X$ and if $w$ is any word in $\Sigma$, then $f^{-1}_{w}W\cap
V=\emptyset$ and so $\mathfrak{I}$ is not topological transitive either.
However, if $\Sigma$ were generated by $\mathcal{W}\cup\\{0\\}$, then the
constituent IFS was both topological and point transitive, showing that
transitivity depends on our subshift.

Later the sets $X$ and $\mathcal{F}=\\{f_{0},\,f_{1}\\}$ introduced in the
following example will be used in several occasions, for instance in examples
3.13, 4.5 and 4.6.

######  Example 3.8.

Let $\\{x_{n}\\}_{n\in\mathbb{Z}}$ be an increasing sequence ($x_{n+1}>x_{n}$)
in $[0,\,1]$ such that $\lim_{n\rightarrow+\infty}x_{n}=1$ and
$\lim_{n\rightarrow-\infty}x_{n}=0$. Let $X$ be the set of points of this
sequence together with $0$ and $1$ and equip $X$ with the subset topology of
$[0,\,1]$.

  1. 1.

Let $\mathfrak{I}_{1}=(X,\,\\{f_{0}\\},\,\\{0^{\mathbb{Z}}\\})$ be the
conventional dynamical system where

$f_{0}(x)=\begin{cases}x&\text{if}\quad x\in\\{0,\,1\\},\\\
x_{n+1}&\text{if}\quad x=x_{n}.\end{cases}$ (5)

This system is point transitive but not forward point transitive. In fact, any
point in $X\setminus\\{0,\,1\\}$ is a transitive point and $0$ and $1$ are
fixed points.

  2. 2.

Let $\mathfrak{I}_{2}=(X,\,\\{f_{0},\,f_{1}\\},\,\Sigma)$ and let $f_{0}$ be
as in (5) but $f_{1}$ be defined as

$f_{1}(x)=\begin{cases}x&\text{if}\quad x\in\\{0,\,1\\},\\\
x_{n-1}&\text{if}\quad x=x_{n}.\end{cases}$ (6)

Also let $\Sigma\subseteq\\{0,\,1\\}^{\mathbb{N}_{0}}$ be generated by
$\mathcal{W}=\\{w_{0},\,w_{1},\,w_{3},\ldots\\}$ so that there are two words
in $\mathcal{W}$, say $w_{0}$ and $w_{1}$ such that $|w_{0}|=|w_{1}|$ and
$\frac{0_{w_{0}}}{|w_{0}|}=\frac{1_{w_{1}}}{|w_{1}|}>\frac{1}{2}$ where
$i_{w_{j}}$ is the number of i’s appearing in $w_{j}$. Then,
$\mathfrak{I}_{2}$ is transitive. To see this, let

$\sigma^{0}=w_{0}w_{1}w_{1}w_{0}w_{0}w_{0}w_{1}w_{1}w_{1}w_{1}\cdots
w_{0}^{n}w_{1}^{n+1}w_{0}^{n+2}w_{1}^{n+3}\cdots$ (7)

and let $x\in X\setminus\\{0,\,1\\}$. Then,
$\overline{\mathcal{O}_{\sigma^{0}}^{+}(x)}=X$. One example is when
$\Sigma=\Sigma_{|\mathcal{F}|}$ and $\mathcal{W}=\\{w_{0}=0,\,w_{1}=1\\}$
where then $\frac{0_{w_{0}}}{|w_{0}|}=\frac{1_{w_{1}}}{|w_{1}|}=1$.

Now we set up to show that when $\Sigma$ is an irreducible sofic, functions
are semi-open, i.e., interior of image of any open set is non-empty, and when
the respective IFS is topological transitive, then for some transitive
$t\in\Sigma$, one has point transitivity along $t$. This will give an answer
to questions 1 and 2 on the beginning of this section for special cases where
$\Sigma$ is an irreducible sofic. First we recall a classical result.

######  Theorem 3.9.

(Boyle [5]) Let $\Sigma$ and $\Sigma^{\prime}$ be irreducible shifts of finite
type with $h(\Sigma)>h(\Sigma^{\prime})$. Then, there is a factor code from
$\Sigma$ onto $\Sigma^{\prime}$ if and only if $P(\Sigma)\searrow
P(\Sigma^{\prime})$.

######  Proposition 3.10.

Let $\mathfrak{I}=(X,\,\mathcal{F},\,\Sigma)$ be a surjective and topological
transitive IFS and maps in $\mathcal{F}$ semi-open. Also let $\Sigma$ be an
irreducible sofic. Then there is a forward transitive $t\in\Sigma$ such that
the non-autonomous system $(X,\,f_{t})$ is point transitive.

###### Proof.

Let $\mathcal{A}=\\{0,\,\ldots,\,k-1\\}$ be the set of characters of $\Sigma$.
If $\Sigma$ does not have a fixed point, replace $\mathcal{A}$ with
$\mathcal{A}^{\prime}=\mathcal{A}\cup\\{k\\}$ and replace $\mathcal{F}$ with
$\\{f_{0},\ldots,\,f_{k-1}\\}\cup\\{f_{k}\\}$ where $f_{k}$ is the identity
map and set $\Sigma^{\prime}$ to be the corresponding subshift whose set of
forbidden set is the same as $\Sigma$. Observe that $k^{\mathbb{N}_{0}}$ is a
fixed point of $\Sigma^{\prime}$ and if $t^{\prime}\in\Sigma^{\prime}$ is a
transitive point, then $t$ obtained from $t^{\prime}$ by forgetting the
entries whose value is $k$ is transitive in $\Sigma$. Thus without loss of
generality, we may assume that $\Sigma$ has a fixed point.

So let $\mathfrak{I}$ be topological transitive and set
$\mathfrak{I}^{\prime}:=(X,\,\mathcal{F},\,\Sigma_{|\mathcal{F}|})$ and let
$\mathcal{B}:=\\{W_{m}:m\in\mathbb{N}\\}$ be a base for the topology on $X$.
First we construct a transitive point $t\in\Sigma_{|\mathcal{F}|}$ such that
$\overline{{O}^{+}_{t}(x)}=X$.

Let $U_{m}$ be an open set such that $\overline{U_{m}}\subseteq W_{m}$. Pick
$v_{1}\in\mathcal{L}(\Sigma_{|\mathcal{F}|})$ such that $f_{v_{1}}(U_{1})\cap
U_{2}\neq\emptyset$ and consider $f_{v_{1}v^{\prime}_{1}}$ where
$v^{\prime}_{1}$ is the concatenation of all characters or words of length 1.
Then by the fact that $f_{i}$’s are semi-open and our system is topological
transitive, there is $v_{2}$ such that
$f_{v_{1}v^{\prime}_{1}v_{2}}(U_{1})\cap U_{3}\neq\emptyset$. By the same
reasoning and induction argument, there is $v_{k}$ such that for
$u_{k}:=v_{1}v^{\prime}_{1}v_{2}\cdots v_{i}v^{\prime}_{i}v_{i+1}\cdots
v_{k-1}v^{\prime}_{k-1}v_{k}$,

$f_{u_{k}}(U_{1})\cap U_{k+1}\neq\emptyset.$ (8)

Here $v^{\prime}_{i}$ is the concatenation of all words of length $i$. Let
$C_{k}=\overline{U_{1}}\cap(f_{u_{k}})^{-1}(\overline{U_{k+1}})$ be the
compact set in $W_{1}$ and notice that $C_{k+1}\subseteq C_{k}$; in
particular, $\cap_{k}C_{k}$ is a nonempty compact set in $W_{1}$. Thus if
$x\in\cap_{k}C_{k}$, then $f_{u_{k}}(x)\in W_{k}$. This means that our system
is point transitive along the transitive
$t=v_{1}v^{\prime}_{1}v_{2}\cdots\in\Sigma_{|\mathcal{F}|}$. So the problem is
set when $\Sigma$ is a full shift.

Now let $\Sigma$ be SFT and recall that we are assuming that it has a fixed
point. This means $P(\Sigma_{|\mathcal{F}|})\searrow P(\Sigma)$ and so by 3.9
there is a factor code $\phi$ from $\Sigma_{|\mathcal{F}|}$ onto $\Sigma$ and
in particular there exists a transitive point $\phi(t)\in\Sigma$ with
$\overline{{O}^{+}_{\phi(t)}(x)}=X$. It remains to prove the case when
$\Sigma$ is sofic. But any sofic is a factor of an SFT and transitivity is
preserved by factor codes and take this factor code to be a 1-block factor
code. By an argument as above we may extend this SFT to have a fixed point and
the new character, if any, will map to a new added character in character set
of $\Sigma$ by the block factor map whose associated map in $\mathfrak{I}$ is
identity. As a result, a transitive $t\in\Sigma$ and $x\in X$ exists as
required. ∎

In the above proposition, the same conclusion holds if we are sure that for
any $k$, there is $u_{k}$ such that as in (8), the intersection has non-empty
interior. In fact we conjecture that this is the case, i.e. if IFS is
topological transitive, $\mathcal{F}$ surjective, then for any nonempty open
sets $U$ and $V$ there is a $u\in\Sigma_{|\mathcal{F}|}$ such that
$f_{u}(U)\cap V$ has nonempty interior. In that case we do not require semi-
openness in the hypothesis.

Next we bring examples showing that none of the other conditions on the
hypothesis of the above proposition can be ignored.

######  Example 3.11.

The alphabet defining our subshift in the above proposition was finite; the
conclusion is not valid for an infinite case. Authors in [10, Example 2.1]
show that in that situation, even when the subshift is a full shift, the
topological transitivity dose not imply topological transitivity along any
orbit.

######  Example 3.12.

Topological transitivity of the IFS in Proposition 3.10 cannot be replaced
with point transitivity. For instance, the system given in Example 3.3 had all
the conditions on the hypothesis of the proposition (subshift was the full
shift, and so sofic and all maps were open) except topological transitivity.
There we had point transitivity of the IFS but yet we did not have point
transitivity along any orbit.

Now we show that the sofic property cannot be omitted in the hypothesis of the
above proposition. Moreover, this example shows that in general topological
transitivity of an IFS does not necessarily imply the point transitivity along
any $\sigma\in\Sigma$.

######  Example 3.13.

Let $f_{0}$, $f_{1}$ be homeomorphisms defined in Example 3.8 and let
$\mathfrak{I}=(X,\,\\{f_{0},\,f_{1}\\},\,\Sigma)$ where
$\Sigma\subseteq\\{0,\,1\\}^{\mathbb{N}}$ is the non-sofic shift generated by
$\mathcal{W}=\\{0^{n}1^{n}:\;n\in\mathbb{N}\\}$. Then any $\sigma\in\Sigma$
consists of concatenation of words in $\mathcal{W}$ and their shifts together
with points in the closure of them. Thus since $f_{0^{n}1^{n}}\equiv\text{id}$
for $n\in\mathbb{N}$, any $\sigma\in\Sigma$ is either concatenation of words
in $\mathcal{W}$ or terminating at $0^{\infty}$ or $1^{\infty}$. Therefore,
$\overline{\mathcal{O}^{+}_{\sigma}(x)}\neq X$ for any $\sigma\in\Sigma$ and
$x\in X$.

On the other hand, any point $x_{0}\in X\setminus\\{0,\,1\\}$ has dense orbit.
Because, since $0^{\mathbb{N}_{0}}$ and $1^{\mathbb{N}_{0}}$ are points of
$\Sigma$, $x_{0}$ can travel left and right as far as required by $f_{0}$ and
$f_{1}$ respectively. As a result $\mathfrak{I}$ is topological transitive and
yet not point transitive along any $\sigma\in\Sigma$.

##  4 The abundance of point transitive non-autonomous systems in an IFS

When a dynamical property such as transitivity, mixing, exactness occur along
a $\sigma\in\Sigma$, then the IFS will posses that property as well; though
the converse is not necessarily true. In fact, it may not even hold along just
a single orbit. In this section we investigate transitivity in this respect.

Let

$S=S(\mathfrak{I}):=\\{\sigma\in\Sigma:\;\exists\,x\in X\text{ s.t.
}\overline{\mathcal{O}_{\sigma}^{+}(x)}=X\\}.$ (9)

In general, except in few cases, a definite structure cannot be given for $S$,
though its largeness can be understood in some cases. Let us demonstrate how
different $S$ can be.

######  Example 4.1.

  1. 1.

$S$ may be all of $\Sigma$. For an example, let $f_{0}(x)=2x\mod 1$ and
$f_{1}(x)=3x\mod 1$ and consider
$\mathfrak{I}=([0,\,1],\,\\{f_{0},\,f_{1}\\},\,\Sigma_{|\mathcal{F}|})$.

  2. 2.

$S$ may be an empty set. This is the case when we have an IFS which is not
point transitive. Though even for a topological transitive IFS, $S$ still may
be empty (see Example 3.13).

  3. 3.

$S$ may be residual and yet not all of $\Sigma$. The IFS in Example 3.6 has
such property.

  4. 4.

$S$ may be dense and uncountable, yet not a residual subset. See Example 4.6.

Now we give sufficient conditions for $S$ being dense in $\Sigma$. First a
weaker version of specification property for subshifts:

######  Definition 4.2.

A subshift $\Sigma$ is called a _subshift of variable gap length_ or SVGL, if
there exists $M\in\mathbb{N}$ such that for $u$ and $v$ in
$\mathcal{L}(\Sigma)$, there is $w$ with $|w|\leq M$ and
$uwv\in\mathcal{L}(\Sigma)$.

When $\Sigma$ is mixing and SVGL, then $\Sigma$ has _specification property_
and in this situation, there exists $M\in\mathbb{N}$ such that for $u$ and $v$
in $\mathcal{L}(\Sigma)$ there is $w$ with $|w|=M$ and
$uwv\in\mathcal{L}(\Sigma)$. Clearly an SVGL is irreducible. Moreover, all
sofics are SVGL; however, there are SVGL’s which are not sofic. The SVGL is
called almost specification property in [14].

######  Proposition 4.3.

Let $\mathfrak{I}=(X,\,\mathcal{F},\,\Sigma)$ be point transitive along some
$\sigma\in\Sigma$, $\mathcal{F}$ surjective and $\Sigma$ an SVGL. Then, $S$
defined in (9) is dense in $\Sigma$. If $S\neq\Sigma$, then $\Sigma\setminus
S$ is also dense in $\Sigma$.

###### Proof.

We prove the first part; the other part has similar proof.

Choose any $\sigma=\sigma_{1}\sigma_{2}\cdots\in\Sigma$ such that
$\overline{\mathcal{O}_{\sigma}^{+}(x)}=X$. Let $[u]$ be a cylinder in
$\Sigma$ and use the SVGL property of $\Sigma$ to pick
$w_{n}\in\mathcal{L}(\Sigma)$ such that
$uw_{n}\sigma_{1}\sigma_{2}\cdots\sigma_{n}\in\mathcal{L}(\Sigma)$ with
$|w_{n}|\leq M$ where $M$ is provided by the definition of SVGL. Since
$\\{w_{n}\in\mathcal{L}(\Sigma):\;|w_{n}|\leq M\\}$ is finite, there is a $w$
and an infinite subsequence $n_{i}$ such that for all $i$, $w_{n_{i}}=w$. Let
$\sigma^{\prime}=uw\sigma_{1}\sigma_{2}\cdots$ be the unique point in
$\cap_{i\in\mathbb{N}}[uw\sigma_{1}\sigma_{2}\cdots\sigma_{n_{i}}]$ and
observe that for $x^{\prime}\in f^{-1}_{uw}(x)$,
$\overline{\mathcal{O}_{\sigma^{\prime}}^{+}(x^{\prime})}=X$. This implies
$\sigma^{\prime}\in[u]\cap S$ and since $[u]$ was arbitrary, we are done. ∎

######  Remark 4.4.

Assume the hypothesis of Proposition 4.3 and let for some $\sigma\in\Sigma$,
$\omega_{\sigma}(x)$ be the _$\omega$ limit set of $x$ along $\sigma$_, that
is the limit set of
$\mathcal{O}^{+}_{\sigma}(x)=\\{f_{\sigma_{1}\sigma_{2}\cdots\sigma_{n}}(x):\;n\in\mathbb{N}\\}$.
The proof of Proposition 4.3 shows that

$\\{\sigma^{\prime}\in\Sigma:\;\exists\,x^{\prime}\in X\text{ s.t.
}\omega_{\sigma^{\prime}}(x^{\prime})=\omega_{\sigma}(x)\\}$

is dense in $\Sigma$.

Now we show that the SVGL property is a necessity in the hypothesis of
Proposition 4.3.

######  Example 4.5.

Let $X$, $w_{0}=010$, $w_{1}=101$, $f_{0}$ and $f_{1}$ be as in Example 3.8
and set $u_{0}=000$. Let
$\sigma^{0}=\sigma_{1}^{0}\sigma_{2}^{0}\cdots\sigma_{\ell}^{0}\cdots=w_{0}w_{1}\cdots$
be defined as in (7) and let $\mathfrak{I}=(X,\,\\{f_{0},\,f_{1}\\},\,\Sigma)$
where $\Sigma$ is generated by

$\mathcal{W}=\\{u_{0}w_{0}^{\ell}\sigma_{1}^{0}\sigma_{2}^{0}\cdots\sigma_{\ell}^{0}w_{0}^{\ell}u_{0}:\;\ell\in\mathbb{N}\setminus\\}.$

See a presentation for $\Sigma$ in Figure 2.

$u_{0}$$u_{0}$$b$$w_{0}$$w_{0}$$w_{0}$$w_{0}$$\sigma^{0}_{{1}}$$\sigma^{0}_{{1}}$$\sigma^{0}_{{2}}$$\cdots$$w_{0}$$w_{0}$$w_{0}$$w_{0}$$w_{0}$$w_{0}$$\vdots$$\vdots$$\vdots$$\vdots$$\sigma^{0}_{{1}}$$\sigma^{0}_{{n}}$
Figure 2:  Any word in $\mathcal{W}$ starts and terminates at $b$.

If $v=v_{1}\cdots v_{|v|}\in\mathcal{W}$, then 0 and 1 are fixed by $f_{v}$
and for any other $x_{i}\in X\setminus\\{0,\,1\\}$, $f_{v_{1}\cdots
v_{\ell}}(x_{i})=x_{j}$ where $1\leq\ell\leq|v|$ and $j>i$.

Observe that $\sigma^{0}\in\Sigma$ does not have $u_{0}$ as a subword and also
by the same reasoning for $\mathfrak{I}_{2}$ in Example 3.8 ,
$\overline{{O}^{+}_{\sigma^{0}}(x)}=X$ for $x\in X\setminus\\{0,\,1\\}$. On
the other hand if $u_{0}$ appears in a $\sigma\in\Sigma$ infinitely (resp.
finitely) many times, then by our construction where any $u_{0}$ appears only
on the beginning or ending of members of $\mathcal{W}$, this $\sigma$ must
start with a terminal subword of a $w\in\mathcal{W}$, may be empty, and
afterwards has some infinite concatenation of the members of $\mathcal{W}$
(resp. eventually will terminate at $w_{0}^{\infty}$). This in turn implies
that $\overline{{O}^{+}_{\sigma}(x)}\neq X$ for any $x\in X$. In fact then 0
and 1 are fixed by the orbit along $\sigma$ and any other $x$ marches to 1
along that orbit with some relatively minor fluctuations. Hence, if $\sigma$
is transitive then for any $x,\;\overline{{O}^{+}_{\sigma}(x)}\neq X$. In
particular, if $\sigma\in[u_{0}]$, then $\sigma\not\in S$ and consequently $S$
is not dense in $\Sigma$.

Since $u_{0}u_{0}$ is a synchronizing word, the above example is synchronized.
For irreducible shifts we have the following implications.

$\text{ full shift }\Rightarrow\text{ SFT }\Rightarrow\text{ sofic
}\Rightarrow\text{ SVGL }\Rightarrow\text{ synchronized }\Rightarrow\text{
coded}.$

Thus the transitive non-autonomous systems in an IFS whose subshift is
synchronized or beyond may be scarce.

Observe that by Proposition 3.10, the conclusion of Proposition 4.3 is
immediate when $\Sigma$ is sofic; that is because the orbit of a transitive
$\sigma$, attained by the above proposition, is again in $S$ and is dense in
$\Sigma$. However, still we cannot guarantee that $S$ is residual as the next
example shows, even for a case where $\Sigma$ is a mixing SFT.

######  Example 4.6.

Let $X$ and $\mathcal{F}=\\{f_{0},\,f_{1}\\}$ be as in Example 3.8 and
consider $\mathfrak{I}_{\Sigma}=(X,\,\mathcal{F},\,\Sigma)$.

  1. 1.

First let $\Sigma=\Sigma_{|\mathcal{F}|}$ and let $w_{i}$ be a word consisting
of the concatenation of all words of length $i\in\mathbb{N}$ in
$\mathcal{L}(\Sigma_{|\mathcal{F}|})$ and notice that
$\frac{0_{w_{i}}}{|w_{i}|}=\frac{1}{2}$. As a result, if
$u={1^{|w_{i}|}{w_{i}}}$, then $f_{u}(x)$ moves $x\not\in\\{0,\,1\\}$ at least
$\frac{|w_{i}|}{2}$ to left. Therefore, for the transitive

$t=1^{|w_{1}|}w_{1}1^{|w_{2}|}w_{2}1^{|w_{3}|}w_{3}\cdots\in\Sigma_{|\mathcal{F}|},$

$1\notin\overline{\mathcal{O}^{+}_{t}(x)}$ and so
$\overline{\mathcal{O}^{+}_{t}(x)}\neq X$. In particular, this shows that the
conclusion of Proposition 3.10 is not necessarily valid for all transitive
points in an irreducible sofic shift. Clearly
$S(\mathfrak{I}_{\Sigma_{|\mathcal{F}|}})$, although dense, it is not closed
and hence it is not a subshift.

  2. 2.

To complete our collection of the possible various cases of $S(\mathfrak{I})$,
we construct an example where $S(\mathfrak{I})$ is a dense uncountable but not
residual subset of the subshift. To do this let $\Sigma_{\mathcal{W}}$ be the
SFT generated by $\mathcal{W}=\\{w_{0}=100,\,w_{1}=011,\,w_{2}=000\\}$ and
call the associated IFS $\mathfrak{I}_{\mathcal{W}}$.

We have $\frac{0_{w_{0}}}{|w_{0}|}=\frac{1_{w_{1}}}{|w_{1}|}=\frac{2}{3}$.
Hence if $\sigma^{0}$ is chosen as in (7), then
$\overline{\mathcal{O}^{+}_{\sigma^{0}}(x)}=X$ for $x\in
X\setminus\\{0,\,1\\}$. However, $\mathcal{O}^{+}_{0^{\infty}}(x)$ is not
dense for any $x\in X$ and hence $S(\mathfrak{I}_{\mathcal{W}})$ is not closed
and again not a subshift. Also, observe that the subshift
$\Sigma_{\mathcal{W}^{\prime}}$ generated by
$\mathcal{W}^{\prime}=\cup_{k\in\mathbb{N}}\\{w_{0}^{k}w_{1}^{k},\,w_{1}^{k}w_{0}^{k}\\}$
is a subsystem of $\Sigma_{\mathcal{W}}$ and any transitive point of that lies
in $S(\mathfrak{I}_{\mathcal{W}})$. The latter follows from the fact that
$f_{u}(x)=x$ for $u=w_{0}^{k}w_{1}^{k}$ or $u=w_{1}^{k}w_{0}^{k}$ and the fact
that $w_{0}^{k}w_{1}^{k}w_{1}^{k}w_{0}^{k}$ is a subword for a transitive
point in $\Sigma_{\mathcal{W}^{\prime}}$ for any $k\in\mathbb{N}$. Thus any
$x\in X\setminus\\{0,\,1\\}$ moves left and right as far as possible. This
implies that $S(\mathfrak{I}_{\mathcal{W}^{\prime}})\subset
S(\mathfrak{I}_{\mathcal{W}})$ has uncountable points.

Now we show that in this example $S(\mathfrak{I}_{\mathcal{W}})$ is not a
residual subset of $\Sigma_{\mathcal{W}}$. It is an easy consequence of the
Birkhoff’s ergodic theorem that the frequency of $w_{i}\in\mathcal{W}$ is
$\frac{1}{3}$ for almost all $\sigma\in\Sigma_{\mathcal{W}}$ (we are
considering the Markov measure on $\Sigma_{\mathcal{W}}$: A unique ergodic
Borel measure $\mu$ which is positive on open sets and has the maximum metric
entropy among all other measures). This means that occurrence of $0$ is as
twice as that of $1$ for almost all $\sigma$. Thus for $x\in X$ and almost all
$\sigma$, $\overline{{O}^{+}_{\sigma}(x)}\neq X$. This in turn implies that
$\mu(S(\mathfrak{I}_{\mathcal{W}}))=0$. Now if $S(\mathfrak{I}_{\mathcal{W}})$
was residual in $\Sigma_{\mathcal{W}}$, then $S(\mathfrak{I}_{\mathcal{W}})$
would be measurable and since it is shift invariant it must have full measure
which is impossible for this example.

If one chooses $w_{2}$ in $\mathcal{W}$ to be $0000$, then
gcd$\\{|w_{i}|\,|\;w_{i}\in\mathcal{W},\,0\leq i\leq 2\\}=1$ which implies
that $\Sigma_{\mathcal{W}}$ is a mixing SFT ([1, 9]). So either mixing or non-
mixing, there are examples that $S$, in spite of being invariant and having a
transitive point under the shift map, is not residual.

##  5 Mixing and exactness in an IFS

Clearly mixing along an orbit given in Definition 3.4 implies mixing defined
in Definition 3.1 and the converse is not true as the next example shows. This
example also shows that if the IFS is mixing, unlike Proposition 3.10, one
cannot have mixing along an orbit.

######  Example 5.1.

Let
$\mathfrak{I}=\left(X=\\{0,\,1\\}^{\mathbb{N}},\,\mathcal{F}=\\{f_{0},\,f_{1}\\},\,\Sigma_{|\mathcal{F}|}\right)$
and for $\xi=\xi_{1}\xi_{2}\cdots\in X$ define

$\displaystyle f_{0}(\xi)$ $\displaystyle=0\xi=0\xi_{1}\xi_{2}\cdots,$
$\displaystyle f_{1}(\xi)$ $\displaystyle=1\xi=1\xi_{1}\xi_{2}\cdots.$

For $w=w_{1}\cdots w_{n-1}w_{n}$, set $w^{-1}:=w_{n}w_{n-1}\cdots w_{1}$ and
observe that $f_{w}(\xi)=w^{-1}\xi$. Now let $[u]$ and $[v]$ be any cylinder
and set $M:=|v|$. Then for $m\geq M$ and $w\in\mathcal{L}_{m}(\Sigma)$,
$f_{w}([u])\cap[v]\neq\emptyset$ iff $w$ is a word terminating at $v^{-1}$ and
hence $\mathfrak{I}$ is mixing. On the other hand assume
$\sigma\in\Sigma,\,v=100$ and $u$ any word. Now for $m\geq 2$, if
$f_{\sigma_{1}\ldots\sigma_{m}}([u])\cap[v]\neq\emptyset$, then
$w=\sigma_{1}\cdots\sigma_{m}$ terminates at $v^{-1}$ but neither $w0$ nor
$w1$ terminates at $v^{-1}$. This implies that both $f_{w0}([u])\cap[v]$ and
$f_{w1}([u])\cap[v]$ are empty sets. Thus $\mathfrak{I}$ is not mixing along
any orbit $\sigma$.

Next example shows that simple dynamics in the individual maps in an IFS may
raise to a rich dynamics in the IFS. Intuitively, if we have two maps in an
IFS that one flows all the point in a definite direction and the other on the
opposite direction, then the arbitrary combination of these maps can create a
complicate dynamics. Example 5.1 had this property but the IFS was not as rich
as the following.

######  Example 5.2.

Here we give an example such that none of the maps of the IFS, considering as
a conventional dynamical system, is transitive but the IFS itself is exact and
thus mixing and topological transitive.

Let
$\mathfrak{I}=(X=\\{0,\,1\\}^{\mathbb{N}},\,\\{f_{0},\,f_{1}\\},\,\Sigma_{|\mathcal{F}|}=\\{0,\,1\\}^{\mathbb{N}})$
be an IFS where for
$\zeta=\zeta_{1}\zeta_{2}\cdots\in\\{0,\,1\\}^{\mathbb{N}}$,

$f_{i}(\zeta)=\begin{cases}i\zeta_{1}\zeta_{2}\cdots&\text{if}\quad\zeta_{1}=i,\\\
\zeta_{2}\zeta_{3}\cdots&\text{if}\quad\zeta_{1}\neq i.\end{cases}$ (10)

we have the following observations

  1. 1.

$f_{i}$ is a finite to 1 surjective open map with $0^{\infty}$ and
$1^{\infty}$ its only fixed points.

  2. 2.

$f_{0}$ (resp. $f_{1}$) attracts all points in $X\setminus\\{1^{\infty}\\}$
(resp. $X\setminus\\{0^{\infty}\\}$) and leaves the point $1^{\infty}$ (resp.
$0^{\infty}$) fixed. Thus $f_{i}$ is not transitive and has a very simple
dynamics.

  3. 3.

Any $\zeta=\zeta_{1}\zeta_{2}\cdots\in X$ is periodic of any given even period
$p=2q\in\mathbb{N}$ along a $\sigma\in\Sigma$. To see this set

$\sigma=(\zeta_{1}^{q}{\zeta_{1}^{*}}^{q})^{\infty}=\left(\overbrace{\zeta_{1}\zeta_{1}\cdots\zeta_{1}}^{q\text{
times}}\overbrace{\zeta_{1}^{*}\zeta_{1}^{*}\cdots\zeta_{1}^{*}}^{q\text{
times}}\right)^{\infty}$

where for $a\in\mathcal{A}=\\{0,\,1\\}$,

$a^{*}=\begin{cases}1,\quad a=0\\\ 0,\quad a=1.\end{cases}$ (11)

Also, any transitive $\zeta=\zeta_{1}\zeta_{2}\cdots\in X$ is transitive along
the transitive point $\zeta^{*}=\zeta_{1}^{*}\zeta_{2}^{*}\cdots\in\Sigma$. A
point such as $\zeta=(\zeta_{1}\zeta_{2}\cdots\zeta_{p})^{\infty}\in X$ is
periodic of period $p$ along the periodic point
$\zeta^{*}=(\zeta_{1}^{*}\zeta_{1}^{*}\cdots\zeta_{p}^{*})^{\infty}\in\Sigma$.

  4. 4.

$\mathfrak{I}$ is exact along a transitive point.

###### Proof.

Fix an open set $U\subseteq X$ and pick
$w\in\mathcal{L}_{k}(\Sigma_{|\mathcal{F}|})$ such that ${[w]}\subseteq U$.
Set $w^{*}:=w_{0}^{*}\cdots w_{k}^{*}$, $w^{*}_{i}$ defined as in (11), and
note that $X=f_{w^{*}v}([w])$ where $w^{*}v$ is any word whose initial segment
is $w^{*}$.

The set $\mathcal{L}_{m}(\Sigma_{|\mathcal{F}|})$ has $2^{m}$ words. Set
$\mathcal{P}_{m}(\mathcal{L}_{m}(\Sigma_{|\mathcal{F}|}))=\\{v_{1}^{m},\,\ldots,\,v_{2^{m}!}^{m}\\}\subseteq\mathcal{L}_{m2^{m}}(\Sigma_{|\mathcal{F}|})$
to be the set of $2^{m}!$ words constructed from the permutation of words in
$\mathcal{L}_{m}(\Sigma_{|\mathcal{F}|})$ and for $n>m$, let

$t=v_{1}^{1}v_{2}^{1}\cdots v_{1}^{m}\cdots v_{2^{m}!}^{m}\cdots
v_{1}^{n}\cdots
v_{2^{n}!}^{n}\cdots=u_{1}u_{2}\cdots\in\Sigma_{|\mathcal{F}|},$

be the transitive point where $u_{1}=v_{1}^{1}$, $u_{2}=v_{2}^{1}$ and so on.
So each $u_{i}$ is one of the $v_{j}^{m}$’s coming after each other in the
obvious order. Observe that $u_{i}$ has the same number of 0’s and 1’s and any
word $v\in\mathcal{L}(\Sigma_{|\mathcal{F}|})$ appears as the initial segment
of infinitely many $u_{i}$’s. We will show that $\mathfrak{I}$ is exact along
$t$.

Another observation is that for any word $b$ such as $u_{i}$ whose 0’s and 1’s
are equal, and any cylinder $[a]$, $|f_{b}([a])|\leq|[a]|$.

Set

$[a_{i}]:=f_{u_{1}\cdots u_{i}}([w])$

and note that $\\{|a_{i}|\\}_{i\in\mathbb{N}}$ is a non-increasing sequence.
Moreover, if $|a_{i+1}|<|a_{i}|$ for some $|w|$ instances of $i$’s along $t$,
then call the last instance $\ell$ and notice that then $f_{u_{1}\cdots
u_{\ell}}([w])=X$ and so in this case this IFS is exact along $t$. Otherwise,
without loss of generality assume that for all $i\in\mathbb{N}$,
$|a_{i}|=|w|$. We will show that this latter case does not happen and so we
are done.

First let $b=b_{1}\cdots b_{|b|}$ be any word and let $|f_{b}([a])|=|[a]|$
where $a=a_{1}\cdots a_{|a|}$. Let $m(a,\,b)=\min\\{|f_{b_{1}\cdots
b_{i}}([a])|:\;1\leq i\leq|b|\\}$ and set

$\alpha=\alpha(a,\,b):=\max\\{i:\;|f_{b_{1}\cdots
b_{i}}([a])|=m(a,\,b),\,1\leq i\leq|b|\\}.$

In other words, $\alpha(a,\,b)$ is the last instance where $f_{b_{1}\cdots
b_{i}}([a])$ has the shortest length. Let $f_{b_{1}\cdots
b_{\alpha}}([a])=[a^{\prime}]=[a^{\prime}_{1}\cdots
a^{\prime}_{|a^{\prime}|}]$ for some $a^{\prime}$, $|a^{\prime}|<|a|$. In fact
$a^{\prime}$ is the terminal segment of $a$. Since $|f_{b_{1}\cdots
b_{\alpha+i}}([a])|>|a^{\prime}|$ for $1\leq i\leq|b|-\alpha$, by the
definition of $f_{j}$’s, $b_{\alpha+1}=a^{\prime}_{1}$ and in particular
$f_{b}([a])=[a^{\prime\beta(a,\,b)}_{1}a^{\prime}]$ where

$\beta(a,\,b)=|a|-|a^{\prime}|.$

Now assume $|a_{i}|=|w|$ and set $\alpha_{i}=\alpha(a_{i},\,u_{i+1})$ and
$\beta_{i}=\beta(a_{i},\,u_{i+1})$. If $\beta_{i+1}\leq\beta_{i}$, then
$[a_{i}]=[a_{i+1}]$. So if there is $M\in\mathbb{N}$ such that for $i\geq M$,
$\beta_{i+1}\leq\beta_{i}$; or equivalently, for $i\geq M$, $[a_{i}]=[a_{M}]$,
then along $t$ we arrive at a $u_{\ell}$ whose initial segment is $a_{M}^{*}$
and then $f_{u_{1}\cdots u_{\ell}}([w])=X$. This violates our assumption that
$|a_{i}|=|w|$.

So the only other possibility is that $|a_{i}|=|w|$ and for any
$M\in\mathbb{N}$, there is an $i>M$ where
$0\leq\beta_{i}<\beta_{i+1}\leq|a_{i}|$ which is clearly not possible. ∎

Next we give an example whose any map in the IFS is exact as a conventional
dynamical system, though the IFS itself is not exact; somehow presenting
opposite properties comparing to the previous example.

######  Example 5.3.

Let
$\mathfrak{I}=(X=[0,\,1],\,\\{f_{0},\,f_{1}\\},\,\Sigma=\\{(01)^{\infty},\,(10)^{\infty}\\})$.
To define $f_{i}$, choose two different points $x_{0},\,x_{1}\in(0,\,1)$ and
small open interval $I_{i}$ around $x_{i}$ such that $x_{j}\not\in I_{i}$ if
$j\neq i$. We aim to have

$I_{0}\xrightarrow{f_{0}}I_{1}\xrightarrow{f_{1}}I_{0}$

and $f_{0}$ (resp. $f_{1}$) being contracting on points of $I_{0}$ (resp.
$I_{1}$) with an infimum rate $c_{0}\in(\frac{1}{2},\,1)$ and elsewhere
expansive with infimum rate $e_{0}>2$. An example of $f_{0}$ and $f_{1}$ can
be those presented in Figure 3.

$1$$\dfrac{1}{4}$$\dfrac{3}{4}$$1$$x_{0}$$x_{1}$$x_{0}$$x_{1}$$1$$\dfrac{1}{4}$$\dfrac{3}{4}$$1$$x_{0}$$x_{1}$$x_{0}$$x_{1}$$f_{0}$$f_{1}$$(\frac{1}{2},1)$$(\frac{1}{2},1)$
Figure 3: $([0,\,1],\,f_{i})$ is exact, but
$\mathfrak{I}=([0,\,1],\,\\{f_{0},\,f_{1}\\},\,\\{(01)^{\infty},\,(10)^{\infty}\\})$
is not even point transitive.

This construction guarantees that $f_{i}$ being exact; however, a sufficiently
small neighborhood around $x_{0}$ shrinks to a point along
$\sigma=(01)^{\infty}$. Thus $\mathfrak{I}$ cannot be exact.

## References

  * [1] Ahmadi Dastjerdi, Dawoud, and Maliheh Dabbaghian Amiri. Mixing coded systems. Georgian Mathematical Journal 26.4 (2019): 637-642.
  * [2] Allison, Andrew, and Derek Abbott. Control systems with stochastic feedback. Chaos: An Interdisciplinary Journal of Nonlinear Science 11.3 (2001): 715-724.
  * [3] Barnsley, Michael F., and Andrew Vince. The Conley attractors of an iterated function system. Bulletin of the Australian Mathematical Society 88.2 (2013): 267-279.
  * [4] Barrientos, Pablo G., et al. On the chaos game of iterated function systems. Topological methods in nonlinear analysis 49.1 (2017): 105-132.
  * [5] Boyle, M. (1983). Lower entropy factors of sofic systems. Ergodic theory and dynamical systems, 3(4), 541-557.
  * [6] Cairns, Grant, Alla Kolganova, and Anthony Nielsen. Topological transitivity and mixing notions for group actions. The Rocky Mountain Journal of Mathematics (2007): 371-397.
  * [7] De la Sen, M. The generalized Beverton–Holt equation and the control of populations. Applied Mathematical Modelling 32.11 (2008): 2312-2328.
  * [8] Diaconis, Persi, and David Freedman. Iterated random functions. SIAM review 41.1 (1999): 45-76.
  * [9] Epperlein, Jeremias, Dominik Kwietniak, and Piotr Oprocha. Mixing properties in coded systems. New trends in one-dimensional dynamics. Springer, Cham, 2019. 183-200.
  * [10] Ghane, Fatemeh H., and Javad Nazarian Sarkooh. On topological entropy and topological pressure of non-autonomous iterated function systems. Journal of the Korean Mathematical Society 56.6 (2019): 1561-1597.
  * [11] Glavan, Vasile, and Valeriu Gutu. Shadowing in parameterized IFS. Fixed Point Theory 7.2 (2006): 263-274.
  * [12] Hui, Huihui, and Dongkui Ma. Some dynamical properties for free semigroup actions. Stochastics and Dynamics 18.04 (2018): 1850032.
  * [13] Hutchinson, John E. Fractals and self similarity. Indiana University Mathematics Journal 30.5 (1981): 713-747.
  * [14] Jung, Uijin. On the existence of open and bi-continuing codes. Transactions of the American Mathematical Society 363.3 (2011): 1399-1417.
  * [15] Kolyada, Sergiĭ, and Lubomir Snoha. Topological entropy of nonautonomous dynamical systems. Random and computational dynamics 4.2 (1996): 205.
  * [16] Kontorovich, Eduard, and Michael Megrelishvili. A note on sensitivity of semigroup actions. Semigroup Forum. Vol. 76. No. 1. Springer-Verlag, 2008.
  * [17] Lind, Douglas, and Brian Marcus. An introduction to symbolic dynamics and coding. Cambridge university press, 2021.
  * [18] Liu, Kairan, Yixiao Qiao, and Leiye Xu. Topological entropy of nonautonomous dynamical systems. Journal of Differential Equations 268.9 (2020): 5353-5365.
  * [19] Parham, Hadi, F. H. Ghane, and Azam Ehsani. Iterated function systems: transitivity and minimality. Boletim da Sociedade Paranaense de Matematica 38.3 (2020): 97-109.
  * [20] Parrondo, Juan MR, Gregory P. Harmer, and Derek Abbott. New paradoxical games based on Brownian ratchets. Physical Review Letters 85.24 (2000): 5226.
  * [21] Sanchez, Ivan, Manuel Sanchis, and Hugo Villanueva. Chaos in hyperspaces of nonautonomous discrete systems. Chaos, Solitons and Fractals 94 (2017): 68-74.
  * [22] Zhang, Wei-Bin. Discrete dynamical systems, bifurcations and chaos in economics. elsevier, 2006.


# Deep Learning-Based Quantization of L-Values for Gray-Coded Modulation

Marius Arvinte, Sriram Vishwanath and Ahmed H. Tewfik  Department of
Electrical and Computer Engineering
University of Texas at Austin
Austin, Texas 78712
Email<EMAIL_ADDRESS>
###### Abstract

In this work, a deep learning-based quantization scheme for log-likelihood
ratio (L-value) storage is introduced. We analyze the dependency between the
average magnitude of different L-values from the same quadrature amplitude
modulation (QAM) symbol and show they follow a consistent ordering. Based on
this we design a deep autoencoder that jointly compresses and separately
reconstructs each L-value, allowing the use of a weighted loss function that
aims to more accurately reconstructs low magnitude inputs. Our method is shown
to be competitive with state-of-the-art maximum mutual information
quantization schemes, reducing the required memory footprint by a ratio of up
to two and a loss of performance smaller than $0.1$ dB with less than two
effective bits per L-value or smaller than $0.04$ dB with $2.25$ effective
bits. We experimentally show that our proposed method is a universal
compression scheme in the sense that after training on an LDPC-coded Rayleigh
fading scenario we can reuse the same network without further training on
other channel models and codes while preserving the same performance benefits.

##  I Introduction

Deep learning has recently gained a foothold in wireless communications and
signal processing with experimental results showing that it can be used for
various tasks ranging from channel code design [1] to black-box communication
schemes [2]. At the same time, quantization of information in communication
systems is critical for applications such as feedback channels, relay schemes
or hydrid automatic repeat request storage. Motivated by finding a
quantization scheme that is as greedy as possible with minimal impact to the
end-to-end performance, we introduce a deep learning-based L-value vector
quantization scheme that leverages a statistical ordering among them to weigh
its loss function during training.

Log-likelihood ratio quantization is a well studied topic, where it has been
identified that the optimal formulation aims to maximize mutual information
[3]. Prior work in [4] presents a data-driven approach for quantizing L-values
even in cases when the channel has an arbitrary or intractable distribution.
The work in [5] introduces a maximum mutual information vector quantization
method for L-values by using the Lloyd algorithm with a KL divergence metric.
In both cases, a sharp drop in performance is exhibited when the effective
storage size approaches or goes below two bits per L-value.

More recently, deep networks have been used for quantization and codebook
learning, where the main challenge is back-propagating gradients through the
quantization function. Solutions to this include soft-to-hard approximations
of the nearest neighbor function that are parameterized by an increasing
attraction coefficient over time, or replacing the null gradient with other
approximations. The work in [6] uses such a schedule during the training phase
to learn a compression scheme for high resolution images that outperforms
state-of-the-art schemes by almost an order of magnitude. With the same goal,
the work in [7] introduces the architecture of vector quantized variational
autoencoder (VQ-VAE) to learn a discrete, compressed representation of image
and speech signals by approximating the null gradient with a linear function.

Even though these solutions are shown to be successful for images, in the case
of communications the signal statistics are fundamentally different and any
application requires careful analysis and design of the network architecture
and loss function. Previous work in [8] uses an autoencoder structure to
compress the channel state information (CSI) matrix by exploiting its time and
spatial domain correlation. In this work, we propose to exploit the use of
binary reflected Gray coding (BRGC), almost universally adopted in practical
systems and known to be optimal [9] and show that it induces an ordering on
the average magnitude of the L-values that holds for any channel coefficient
distribution. We leverage this to design a deep autoencoder network that uses
a branched decoder architecture to individually reconstruct each L-value,
allowing us to weigh the loss function towards smaller magnitude L-values.

Our work is closest to [10], where a deep autoencoder is used to jointly
compress and reconstructs the set of L-values corresponding to a channel use
by leveraging the fact that three sufficient statistics will recover them.
However, their work exhibits a performance gap even when the compressed signal
(latent representation) is not quantized. By leveraging the statistics of
L-values, we manage to virtually close this performance gap, reducing it from
$0.2$ dB to as low as $0.02$ dB and consequently improving the quantized
results as well. We compare our work with state-of-the-art maximum mutual
information schemes and show that we exhibit a compression gain of up to two,
allowing us to use an effective storage size of less than two bits per L-value
for high order modulation schemes. Furthermore, we experimentally show that
the same network weights can be used for a wide range of scenarios with
different channel models and codes, without requiring any further training or
adjustments.

##  II System Model

Consider the digital baseband model of a binary reflected Gray coded (BRGC)
$M$-QAM modulation scheme, where the transmitted symbol $x$ is found by
mapping the bits $b_{1},\dots,b_{K}$ to a complex constellation symbol
belonging to the set of all constellation points $C$, where $K=\log_{2}M$. We
adopt a flat fading complex channel model in which the complex received symbol
$y$ has the expression

$y=hx+n,$ (1)

where $n$ is drawn i.i.d. from a complex Gaussian distribution with zero mean
and variance equal to $\frac{\sigma_{n}^{2}}{2}$ and $h$ represents the
complex channel coefficient. We assume that $h$ comes from a complex
distribution such that $\mathbb{E}[|h|^{2}]=1$, but make no further
assumptions on the shape of the distribution for the rest of our derivations.
Given instantaneous channel state information at the receiver, the exact log-
likelihood ratio (L-value) for bit $b_{k}$ is given by

$L_{k}=\log{\frac{P(y|b_{k}=1)}{P(y|b_{k}=0)}}=\log{\left\\{\frac{\sum\limits_{\hat{x}\in
C,b_{k}=1}\exp{-\frac{|y-h\hat{x}|^{2}}{\sigma_{n}^{2}}}}{\sum\limits_{\hat{x}\in
C,b_{k}=0}\exp{-\frac{|y-h\hat{x}|^{2}}{\sigma_{n}^{2}}}}\right\\}}.$ (2)

Prior work shows that by factoring out the $h$ term, letting
$\tilde{y}=\frac{y}{h}$ be the equalized received symbol and rewriting the
expressions, the exact L-values can be reconstructed given the three
sufficient statistics [10]

$G=\left(\frac{\lvert
h\rvert}{\sigma_{n}}\right)^{2},\tilde{y}_{r}=\text{Re}\\{\tilde{y}\\},\tilde{y}_{i}=\text{Im}\\{\tilde{y}\\},$
(3)

or any bijective function of them. We aim to learn such a highly nonlinear
representation of these statistics with our deep network.

We further consider the conditional distributions of the L-values under the
max-log approximation for different bit positions $k=1,\dots,K$. The work in
[11] shows that in a nonfading (i.e., affected only by noise) scenario the
probability density function (PDF) of the L-values for each bit level can be
written as a sum of truncated Gaussian PDFs. According to [11], the
approximate PDF of the $k$-th L-value conditioned on the transmitted bit
$b_{k}$ has the expression

$p_{k}(\lambda|b_{k})=\sum\limits_{l=0}^{\frac{M}{2}-1}w_{k,l}\Phi(\lambda;(-1)^{b_{k}+1}\mu_{l},\sigma_{l}^{2}),$
(4)

where $\Phi(\lambda;\mu,\sigma^{2})$ represents the Gaussian PDF and $w_{k,l}$
is the uniform probability that $L_{k}$ is a Gaussian with mean and variance
given by $\mu_{l}$ and $\sigma_{l}^{2}$ respectively, in concordance with the
Zero-Crossing Model approximation in [11]. As the authors of [11] show, this
leads to a key observation about the L-values corresponding to different bit
positions, namely that after splitting the bits in two groups (due to the
real/imaginary symmetry induced by BRGC) the bits occupying the first
positions are more robust to channel conditions than later ones. Formally,
this can be expressed by the inequality

$\mathbb{E}\left[|L_{1}|\right]>\mathbb{E}\left[|L_{2}|\right]>\dots>\mathbb{E}\left[|L_{\frac{K}{2}}|\right],$
(5)

where the expectation is taken across all noise realizations and a similar
ordering holding true for the second half of L-values associated with the
imaginary part. Finally, let $\Lambda_{k}$ be the soft bit associated to the
L-value $L_{k}$, given by [3]

$\Lambda_{k}=\tanh{\frac{L_{k}}{2}}.$ (6)

Since $\tanh$ is a monotonic function it follows that the ordering in (5)
holds for $\Lambda_{k}$ as well. We let $\mathbf{L}$ and $\mathbf{\Lambda}$
denote the $K$-dimensional real, ordered — according to (5) — vectors of
L-values and soft bits corresponding to a single channel use with
$\Lambda_{k}$ and $L_{k}$ their $k$-th elements, respectively. Our goal is to
compress $\mathbf{\Lambda}$ to a three-dimensional latent representation,
quantize it to a finite, small number of bits and reconstruct the original
input.

The basic machine learning structure we use for compressing the L-values is a
deep neural network. From a high-level perspective, a deep neural network can
be viewed as a parameterized function $f(\mathbf{x};\theta_{f})$, where
$\mathbf{x}$ is the real-valued input vector and $\theta_{f}$ denotes the
weight vector, containing the serialized weights of all layers. For the rest
of this work, we only refer to feedforward, fully-connected neural networks,
in which a layer that takes as input the vector $\mathbf{x}$ and outputs
$\mathbf{y}$ implements the operation

$\mathbf{y}=\phi(\mathbf{W}\mathbf{x}+\mathbf{b}),$ (7)

where $(\mathbf{W},\mathbf{b})$ represent the weights and biases associated
with a layer and $\phi$ is the element-wise activation function and all
dimensions are consistent with matrix-vector multiplication. Typical
activation functions include the rectified linear unit (ReLU) given by
$\phi(x)=\max{\\{x,0\\}}$ and the hyperbolic tangent $\phi(x)=\tanh x$.
Finally, an autoencoder is a deep neural network that is trained to
reconstruct its own input $\mathbf{x}$. This is commonly achieved by
performing gradient updates on the weights $\theta_{f}$ in order to minimize
the empirical risk function

$\mathcal{L}(\theta_{f})=\frac{1}{N}\sum\limits_{i=1}^{N}L(f(\mathbf{x}_{i};\theta_{f}),\mathbf{x}_{i}),$
(8)

where $\mathbf{x}_{i}$ represents the $i$-th training sample and $L$ can be
chosen to any distance or quasi-distance function. Importantly, we note that
gradient-based approaches are incompatible with the quantization of hidden
activations in deep networks, since the gradient becomes null almost
everywhere after quantization, preventing preceding weights from being
updated. In this work

##  III The Proposed Scheme

While the original derivation is performed for a nonfading scenario,
additional conditioning on the channel realization and averaging ensures the
ordering of L-values holds even for an arbitrary fading distribution. We
formulate and prove the following proposition.

###### Proposition 1

The ordering in (5) holds for any arbitrary distribution of $h$.

###### Proof:

First we note that by (3) knowledge of $|h|^{2}$ is sufficient to characterize
the distribution of L-values, since the phase can always be corrected assuming
full CSI is available. By letting $g=|h|^{2}$ and expanding the PDF of the
$k$-th L-value we obtain

$p_{k}(\lambda|b_{k})=\int_{0}^{\infty}p_{k}(\lambda|b_{k},g)f_{g}(g)\ dg,$
(9)

where $f_{g}$ is the PDF of $g$. Considering $p_{k}(\lambda|b_{k},g)$, it
follows that (4) holds for any fixed $g$, thus the ordering (5) holds
pointwise, thus it holds globally. ∎

The previous result is proven for the max-log approximation of the L-values,
but empirically holds for the complete expression as well. In the case of a
fading channel Figure 1 illustrates this property by plotting four of the
eight distributions of the soft bits for a 256-QAM scenario, where it can be
clearly observed that the latter bits have much lower average reliability than
the earlier ones. This asymmetry of the different bit locations has wide
implications in forward error correction coding scenarios, especially in the
mid-high signal-to-noise ratio regime, where accurate reconstruction of low
L-values is shown to be critical for correct decoding [12].

Figure 1: Empirical PDFs for the first four soft bits of a $K=8$ ($256$-QAM)
transmission over a Rayleigh fading channel at $18$ dB, exhibiting the
ordering in (5). The next four soft bits have a similar order due to the
binary reflected Gray coding.

This key observation motivates the architecture of our compression and
reconstruction network. Since we target vector quantization of the set of all
L-values corresponding for a channel use, accurate reconstruction of the
latter bit locations is crucial for high order modulation, otherwise a simple
averaged error (e.g., the very common mean squared error) will not capture
high relative errors on low values. Furthermore, this reconstruction property
is also desirable in the soft bit domain, since the hyperbolic tangent
function is approximately linear around the origin.

To achieve our goal, we propose an autoencoder with a branched decoder that
employs one separate deep network to reconstruct each input channel. The
architecture of our solution is shown in Figure 2. The network takes as input
the vector of soft bits $\mathbf{\Lambda}$ and feeds them to the encoder,
where the compressed latent representation $\mathbf{z}$ is output. Letting
$f(\cdot;\theta_{f})$ be the encoder part of the network and
$g_{k}(\cdot;\theta_{g_{k}})$ each of the bit decoders, the $k$-th
reconstructed soft bit can be expressed as

$\tilde{\Lambda}_{k}=g_{i}\left(\mathbf{z};\theta_{g_{k}}\right)=g_{i}\left(f\left(\mathbf{\Lambda};\theta_{f}\right);\theta_{g_{k}}\right).$
(10)

Since prior work successfully uses a latent representation $\mathbf{z}$ of
dimension three equal to the number of sufficient statistics in (3), we adopt
the same model here and set $\mathbf{z}\in\mathbb{R}^{3}$.

To account for accurate reconstruction of low magnitude soft bits, we adopt
two measures:

  1. 1.

We use a sample-wise weighted mean squared error function as in [10]. The loss
function between the $k$-th soft bits and its reconstruction has the
expression

$L(\tilde{\Lambda}_{k},\Lambda_{k})=\frac{|\tilde{\Lambda}_{k}-\Lambda_{k}|^{2}}{|\Lambda_{k}|+\epsilon},$
(11)

where $\epsilon=10^{-6}$ is used for numerical stability. This formulation
ensures that more importance is given to soft bits with low values in the same
bit location.

  2. 2.

We use a set of real weights $w_{k}\geq 0$ to weigh the contributions of each
soft bit to the total loss function leading to the expression

$\mathcal{L(\tilde{\mathbf{\Lambda}},\mathbf{\Lambda})}=\sum\limits_{k=1}^{K}w_{k}\sum\limits_{i=1}^{N}L(\tilde{\Lambda}_{k}^{(i)},\Lambda_{k}^{(i)}),$
(12)

where the weights are normalized to satisfy $\sum_{k}w_{k}=1$, thus at least
one weight must be positive.

Figure 2: Block diagram of our proposed deep network architecture with one
decoder for each soft bit. Each solid rectangular box represents a
feedforward, fully-connected layer. The dashed block represents the latent
representation quantizer and is not active during training.

Note that the weights $w_{k}$ are not applied per sample, but rather per soft
bit and ensure that more importance is placed on reconstructing certain bit
positions. By using Proposition 1 and the ordering in (5), we order the
weights $w_{k}$ in decreasing order of reliability by

$\begin{split}w_{1}\leq w_{2}\leq\dots\leq w_{\frac{K}{2}},\\\
w_{\frac{K}{2}+1}\leq w_{\frac{K}{2}+2}\leq\dots\leq w_{K}.\end{split}$ (13)

Once the weights are set, the architecture is jointly trained for a number of
epochs. Since we are using a single encoder, all gradient updates are averaged
(with the weights $w_{k}$ factored in) and $\theta_{f}$ is updated, while
$\theta_{g_{k}}$ are individually updated for each of the constituent
decoders. We note that a different training regime is also possible, where
only the weights of specific decoders are updated if the performance after
joint training is not good enough on specific soft bits. In fact, the scheme
is completely modular in terms of the decoders, meaning that we can replace
any of them with other reconstruction methods once the encoder is fixed.

Once training is complete, we have a universal, compressed representation of
the soft bits in the form of $\mathbf{z}$ and the next step is quantizing and
storing the latent representation. Letting
$\hat{\mathbf{z}}_{i},i=1,\dots,2^{N_{b}}$ be the $N_{b}$-bit codebook in the
latent space the quantization function is given by

$Q(\mathbf{z})=\operatorname*{argmin}_{\hat{\mathbf{z}}}\left\lVert\mathbf{z}-\hat{\mathbf{z}}\right\rVert_{2}.$
(14)

The use of a minimum distortion quantization in the latent space is justified
by prior work showing that overparametrized deep networks are naturally robust
to quantization of their activations [13]. Finally, reconstruction is
performed by applying the decoders for each soft bit on the quantized latent
representation $\hat{\mathbf{z}}$.

##  IV Performance Results

###  IV-A Architectural and Training Details

We use a number of three hidden layers for the encoder and each of the
decoders, with a uniform intermediate output size of $4\times K$, except for
the latent representation which has a dimension of three as discussed in
Section III. Storing weights in 32-bit floating precision leads to a total
memory footprint (considering the quantization codebook negligible) lower than
$83$ KB for $K=8$ ($256$-QAM), and scaling on the order of $K^{2}$, thus
rapidly decreasing for lower order modulations.

All hidden activations are ReLU, expect for the latent representation and the
outputs, which come from $\tanh$. During training, we also add a small amount
of additive white Gaussian noise with zero mean and $\sigma_{t}=10^{-3}$ to
the latent representation before it is decoded to encourage generalization and
robustness to numerical quantization. Since the latent representation $z$
comes from a $tanh$ activation, this bounds each of its elements to $[-1,1]$
and avoids learning trivial solutions such as boosting the power of
$\mathbf{z}$ to overcome the added noise.

Figure 3: Histograms of the three components of $\mathbf{z}$ after training
and the resulted one-dimensional k-Means quantization codebooks with $4$ bits
($16$ levels) per latent component in dashed red lines. The Cartesian product
of these quantizers is used to derive the $Q$ function. This latent
representation is only trained once and reused for different channel models
and codes.

We use the Adam algorithm for minimizing the empirical risk function in (12)
with a batch size of $65\,536$ samples, learning rate of $0.001$ and
recommended parameters [14] and split the training in two phases. The entire
procedure is summarized in Algorithm 1. In the first phase the encoder and all
decoders are jointly trained starting with equal weights $w_{k}=\frac{1}{K}$.
After a number of epochs $N_{e_{1}}$ the average reconstruction error $e_{k}$
is computed for all soft bits in the training data and we update the weights
$w_{k}$ as

$w_{k}=\frac{e_{k}}{\sum\limits_{i=1}^{K}e_{i}}.$ (15)

This process is repeated for a number of rounds $N_{r}$, placing a higher
importance on soft bits that have larger average reconstruction errors. We
empirically observe that this procedure always respects the order induced by
(13) and also converges to a steady state where the weights no longer need an
update. Alternatively, if a closed form expression of the distribution of
$p_{k}(\lambda|b_{k})$ is available and can be numerically evaluated one can
use a fixed set of weights inversely proportional to $\mathbb{E}[|L_{k}|]$.

Data: $\mathbf{\Lambda}_{i}\in\mathbb{R}^{K},i=1,\dots,N.$

Randomly initialize weights $\theta_{f},\theta_{g_{k}}$.

Initialize weights $w_{k}=\frac{1}{K},\forall k=1,\dots,K.$

_Stage 1_. Encoder and decoders jointly optimized.

for  _$i=1$ to $N_{r}$_ do

Train with fixed $w_{k}$ for a number of $N_{e_{1}}$ epochs.

for  _$j=1$ to $N_{e_{1}}$_ do

Mini-batch Adam update of weighted loss function.

for  _$b=1$ to $N_{b}$_ do

$\theta_{f},\theta_{g_{k}}\leftarrow\text{Adam}(\mathbf{\Lambda}_{i},w_{k},\theta_{f},\theta_{g_{k}})$

end for

end for

Compute average reconstruction error for each L-value.

$e_{k}=\frac{1}{N}\sum\limits_{i=1}^{N}L(\tilde{\Lambda}_{i},\Lambda_{i})$

Update weights using (15).

end for

_Stage 2_. Individual decoder training.

for  _$k=1$ to $K$_ do

for  _$i=1$ to $N_{e_{2,k}}$_ do

Mini-batch Adam update of loss function.

$\theta_{g_{k}}\leftarrow\text{Adam}(\mathbf{z}_{i},\theta_{g_{k}})$

end for

end for

Algorithm 1 Training procedure

In the second phase we freeze the weights of the encoder and continue
individual training for each decoder for a number of $N_{e_{2,k}}$ epochs.
Here we leverage the branched architecture to improve the performance of
individual decoders without affecting the learned representation. We explore
options where $N_{e_{2,k}}$ is equal or proportional to the stationary
$w_{k}$, but both cases lead to roughly the same performance. Since each
decoder only updates its own weights, this process is fully parallelizable
among them.

Once training is completed, we apply a mini-batch version of the k-Means
algorithm [15] to independently obtain a non-uniform scalar quantizer for each
of the three components of the latent representation. Note that this has the
advantage of drastically minimizing the storage requirements of the codebook
versus vector quantization of the latent space and is also empirically
observed to offer similar or better performance. The training data consists of
L-values computed using (2) and generated from the coded bits of a number of
$10\,000$ LDPC codewords with a length of $648$ and rate $1/2$ transmitted
over a Rayleigh fading channel with $h\sim\mathcal{CN}(0,1)$. The complete
source code, pretrained networks and all performance results are available
online111https://github.com/mariusarvinte/deep-llr-quantization.

###  IV-B Impact of Quantization on Block Error Rate

Figure 4: BLER performance of the proposed quantization scheme in a Rayleigh
fading scenario with LDPC coding and $K=8$ ($256$-QAM) modulation.

Throughout this section, we show the results obtained for $K=8$ ($256$-QAM),
but the architecture can be readily used for any modulation scheme. Since the
number of quantized values is a constant w.r.t. $K$, the scheme offers more
efficient compression for high-order modulation schemes. The first experiment
involves investigating the performance of our scheme in the same conditions in
which the training data is generated. We generate $10\,000$ LDPC codewords for
each signal-to-noise ratio in the set $\\{16,17,18,19\\}$ dB, corresponding to
a high-mid noise power regime, concatenate the data points and shuffle them.
Once training is completed, we design the k-Means quantizers using the latent
representation of the same dataset. The empirical marginal distributions of
the three components of $\mathbf{z}$ are shown in Figure 3 together with their
quantization codebooks. For validation, we generate a set of unseen $100\,000$
LDPC codewords across a slightly wider signal-to-ratio range, encode them,
quantize the latent representation with the trained codebooks and reconstruct
them, followed by LDPC decoding using belief propagation with $50$ iterations.

We compare the performance of our method with the maximum mutual information
quantization in [4], where we train a reference quantization for each separate
bit position to account for large order modulation schemes, as well as use an
initial codebook constrained in the $[-3,3]$ to further boost performance.
Additionally, we include the full precision (unquantized latent
representation) results from [10] to show that we successfully cover the
performance gap coming from the autoencoder reconstruction. Figure 4 shows the
obtained block error rate (BLER) curves for all the schemes, as well as the
unquantized performance. Comparing at BLER $=0.01$ we notice that we achieve
the same performance with $15$ bits instead of $24$, leading to a compression
ratio of $1.6$ times and a loss of performance smaller than $0.2$ dB when
compared to full precision storage, while using an equivalent of
$\frac{15}{K}=1.875$ bits per L-value. As a contrast, using the scheme in [4]
with $2$ bits per L-value leads to a performance loss of almost $1$ dB.

###  IV-C Generalization Performance

We now investigate the performance of the proposed quantization scheme when
applied to different configurations than the one we train on. Figure 5 shows
the validation performance of the network trained in Section IV-B when the
channel is a frequency domain representation of a multitap fading ETU channel,
corresponding to an OFDM scenario. Each LDPC codeword experiences a different
realization of the ETU channel and we use a random, but fixed interleaver for
extra robustness. We point out that the BLER performance is fully preserved
when quantizing to 15 or 18 bits, even though the network and codebooks are
not further trained or adjusted in any way for this particular scenario.

Figure 5: BLER performance of the proposed quantization scheme in a ETU fading
scenario with LDPC coding and $K=8$ ($256$-QAM) modulation. The same network
and codebooks used in Figure 4 are reused without additional training or
adjustments.

Additionally, we investigate the performance of the same network when applied
to a Polar-coded Rayleigh fading scenario. We simulate a polar code of length
$256$ and rate $1/2$ used for the NR control channels. Figure 6 plots the BLER
performance on $100\,000$ codewords obtained with the same network, where we
can notice that greedy quantization causes the same small losses. This leads
us to the claim that the learned quantization scheme is universal, in the
sense that it exhibits the same performance regardless of the type of channel
or channel code used and does not require any further training whatsoever.

###  IV-D Discussion

The performance of our scheme can be further extended if we take into account
that we are not forced to keep the resolution of all latent space components
equal. Indeed, judging by Figure 3 it may appear that the second component
$z_{2}$ is more sensitive to scalar quantization since its distribution has a
higher entropy. Thus, given a budget of $16$ bits, we expect that allocating
them to $(z_{1},z_{2},z_{3})$ as $(5,6,5)$ instead of, say, $(5,5,6)$ produces
better quality results. Due to space constraints and to not make the figures
too crowded we omit this result, but this is indeed the case. This reasoning
can be further extended to groups of latent components if vector quantization
is applied in the latent space, but we leave this for future research.

Figure 6: BLER performance of the proposed quantization scheme in a Rayleigh
fading scenario with Polar coding and $K=8$ ($256$-QAM) modulation. The same
network and codebooks used in Figure 4 are reused without additional training
or adjustments.

##  V Conclusions

In this work we have introduced a universal log-likelihood ratio (L-value)
compression and quantization method that uses a deep autoencoder with a
branched decoder, quantizes and reconstructs the latent representation of all
L-values corresponding to a channel use. The branched decoder architecture
allows us to more accurately reconstruct low-magnitude L-values, which are
critical for successful decoding under greedy quantization.

Our results show that we can afford quantization with less than two effective
bits per L-value for 256-QAM modulation, regardless of the type of channel
model or code used with a loss smaller than $0.1$ dB in terms of BLER. In the
high performance regime, we achieve losses smaller than $0.05$ dB with an
effective $2.25$ bits per L-value. The algorithm can be used for any
modulation scheme (with better gains achieved for higher order schemes) and is
competitive with state-of-the-art maximum mutual information quantization
algorithms, achieving a compression factor of up to $1.8$ times for the same
accuracy.

## References

  * [1] H. Kim, Y. Jiang, S. Kannan, S. Oh, and P. Viswanath, “Deepcode: Feedback codes via deep learning,” in _Advances in Neural Information Processing Systems_ , 2018, pp. 9436–9446.
  * [2] T. O’Shea and J. Hoydis, “An introduction to deep learning for the physical layer,” _IEEE Transactions on Cognitive Communications and Networking_ , vol. 3, no. 4, pp. 563–575, 2017.
  * [3] W. Rave, “Quantization of log-likelihood ratios to maximize mutual information,” _IEEE Signal Processing Letters_ , vol. 16, no. 4, pp. 283–286, 2009.
  * [4] A. Winkelbauer and G. Matz, “On quantization of log-likelihood ratios for maximum mutual information,” in _2015 IEEE 16th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_. IEEE, 2015, pp. 316–320.
  * [5] M. Danieli, S. Forchhammer, J. D. Andersen, L. P. Christensen, and S. S. Christensen, “Maximum mutual information vector quantization of log-likelihood ratios for memory efficient harq implementations,” in _2010 Data Compression Conference_. IEEE, 2010, pp. 30–39.
  * [6] E. Agustsson, F. Mentzer, M. Tschannen, L. Cavigelli, R. Timofte, L. Benini, and L. V. Gool, “Soft-to-hard vector quantization for end-to-end learning compressible representations,” in _Advances in Neural Information Processing Systems_ , 2017, pp. 1141–1151.
  * [7] A. van den Oord, O. Vinyals _et al._ , “Neural discrete representation learning,” in _Advances in Neural Information Processing Systems_ , 2017, pp. 6306–6315.
  * [8] C. Lu, W. Xu, H. Shen, J. Zhu, and K. Wang, “Mimo channel information feedback using deep recurrent network,” _IEEE Communications Letters_ , vol. 23, no. 1, pp. 188–191, 2018.
  * [9] E. Agrell, J. Lassing, E. G. Strom, and T. Ottosson, “Gray coding for multilevel constellations in gaussian noise,” _IEEE Transactions on Information Theory_ , vol. 53, no. 1, pp. 224–235, 2006.
  * [10] M. Arvinte, A. H. Tewfik, and S. Vishwanath, “Deep log-likelihood ratio quantization,” _Accepted for Publication at EUSIPCO ’19_ , 2019. [Online]. Available: http://arxiv.org/abs/1903.04656
  * [11] A. Alvarado, L. Szczecinski, R. Feick, and L. Ahumada, “Distribution of l-values in gray-mapped m 2-qam: Closed-form approximations and applications,” _IEEE Transactions on Communications_ , vol. 57, no. 7, pp. 2071–2079, 2009.
  * [12] X. Zhang and P. H. Siegel, “Quantized iterative message passing decoders with low error floor for ldpc codes,” _IEEE Transactions on Communications_ , vol. 62, no. 1, pp. 1–14, 2013.
  * [13] Y. Guo, “A survey on methods and theories of quantized neural networks,” _arXiv preprint arXiv:1808.04752_ , 2018.
  * [14] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [15] D. Sculley, “Web-scale k-means clustering,” in _Proceedings of the 19th international conference on World wide web_. ACM, 2010, pp. 1177–1178.