text:
\chapter{Time packing}\label{chap:time_pack}

\lettrine{I}{n} satellite links for broadcasting and broadband applications, orthogonal
signaling, that ensures absence of intersymbol interference (ISI),
is often adopted. As an example, in the 2nd-generation satellite digital
video broadcasting (DVB-S2) standard~\cite{DVB-S2-TR}, a conventional
square-root raised-cosine (RRC) pulse shaping filter is specified
at the transmitter. In an additive white Gaussian noise channel and
in the absence of other impairments, the use of a matched filter (MF)
at the receiver and proper sampling ensure that optimal detection
can be performed on a symbol-by-symbol basis. On the other hand, it
is known that, when finite-order constellations are considered {[}e.g.,
phase-shift keying (PSK){]}, the efficiency of the communication system
can be improved by giving up the orthogonality condition, thus accepting
interference. For example, {\it faster-than-Nyquist signaling} (FTN, see
\cite{Ma75c,MaLa88}) is a well known technique consisting
of reducing the spacing between two adjacent pulses in the time-domain
well below the Nyquist rate, thus introducing ISI. If the receiver
is able to cope with the interference, the efficiency of the communication
system will be increased. In the original papers on FTN signaling
\cite{Ma75c,MaLa88}, this optimal time spacing is obtained as the
smallest value giving no reduction of the minimum Euclidean distance
with respect to the Nyquist case. This ensures that, asymptotically,
the ISI-free performance is reached, at least when the optimal detector
is adopted. The i.u.d. capacity or information rate, i.e., the average
mutual information when the channel inputs are independent and uniformly
distributed (i.u.d.) random variables, is then computed, still assuming
the adoption of the optimal detector~\cite{RuAn06,RuAn07}. However,
the complexity of this optimal detector easily becomes unmanageable,
and no hints are provided on how to perform the optimization in the
more practical scenario where a reduced-complexity receiver is employed.

In~\cite{BaFeCo09b}, a different approach for improving the spectral
efficiency, that relies on both {\it time packing} of adjacent symbols and
reducing the spacing of the adjacent channels when applicable (multi-carrier
transmission), has been considered. It is assumed that, at the receiver
side, a symbol-by-symbol detector working on the samples at the MF
output is adopted, and the corresponding information rate is computed,
by also optimizing time and frequency spacings to maximize the \emph{achievable
spectral efficiency} (ASE). Hence, rather than the minimum distance,
the \emph{ASE} \emph{is the performance measure} and, in addition,
a low-complexity detection algorithm, characterized by a given allowable
complexity \emph{irrespectively of the interference set size}, is
considered at the receiver rather than the optimal detector employed
in~\cite{Ma75c,MaLa88,RuAn06,RuAn07}. Although the MF output
represents a set of sufficient statistics for optimal detection, a
suboptimal symbol-by-symbol receiver is considered in~\cite{BaFeCo09b}.
Hence, the ASE can be improved by employing more sophisticated detection
algorithms. In this chapter, we will consider two cases: (i) a proper
filtering of the MF output plus a symbol-by-symbol detector and (ii)
the maximum \emph{a posteriori} (MAP) symbol detector that, in order
to limit the receiver complexity, takes into account only a limited
amount of interference.

This technique represents a good alternative, for low-order constellations,
to the shaping of the transmitted symbol distribution~\cite{CaOz90},
providing spectral efficiencies that cannot be reached when orthogonal
signaling is employed. Improving the ASE without increasing the constellation
order can be considerably convenient since the larger the constellation
size, the higher the decoding complexity and the lower the robustness
to channel impairments such as time-varying phase noise and non-linearities.
In the case of frequency packing, a further improvement could be achieved
by adopting, at the receiver side, a multi-user detector.
The remainder of this chapter is organized as follows. The system model
is described in~\S\ref{sec:System-Model}. In~\S\ref{sec:Spectral-Efficiency-optimization},
we compute and optimize the spectral efficiency considering detectors
with different complexity. Numerical results are reported in~\S\ref{sec:Simulation-Results},
where we also show the performance of some efficient modulation and
coding formats (MODCODs) designed accordingly.

\section{System model\label{sec:System-Model}}

We consider an additive white Gaussian noise (AWGN) channel and a
frequency-division multiplexed system where perfectly synchronized
(downlink assumption) adjacent channels employ the same linear modulation
format, shaping pulse $p(t)$, and symbol interval (or time spacing)
$T$. The shaping pulse is assumed to have unit energy. The received
signal can be expressed as
\begin{equation}
r(t)=\sqrt{E_{s}}\sum_{k,\ell} c_{k}^{(\ell)}p(t-kT)e^{j2\pi \ell Ft}+w(t)\label{eq:rec_signal2}
\end{equation}
where $E_{s}$ is the symbol energy, $c_{k}^{(\ell)}$ the symbol transmitted
over the $u$-th channel during the $\ell$-th symbol interval, $F$
the frequency spacing between adjacent channels, and $w(t)$ a circularly
symmetric zero-mean white Gaussian noise process with power spectral
density $N_{0}$. The transmitted symbols $\{c_k^{(\ell)}\}$ are independent
and uniformly distributed and belong to a given zero-mean $M$-ary
complex constellation $\chi$ properly normalized such that $E\{|c_{k}^{(\ell)}|^{2}\}=1$.
Note that the summations in~\eqref{eq:rec_signal2} extend from $-\infty$
to $+\infty$, namely an infinite number of time epochs and carriers
are employed. For the spectral efficiency computation, we will consider
the central user only using $F$ as a measure of the signal bandwidth.

The base pulse $p(t)$ has often RRC-shaped spectrum (RRC pulse in
the following) with roll-off factor $\alpha$. In addition to it,
we will consider other transmit pulses, e.g., a pulse whose spectrum
is raised-cosine (RC) shaped (RC pulse in the following) and a Gaussian
pulse. In general, we will consider the case of time-frequency packing
and we will optimize the frequency separation $F$ between two adjacent
users and the symbol interval $T$ in order to maximize the ASE. In
the case of bandlimited pulses (i.e., RRC and RC pulses), we will
also consider time packing only. In this case, adjacent users are
not allowed to overlap in frequency (i.e., $F=(1+\alpha)/T$ for RRC
and RC pulses) and we may assume that only the user with $\ell=0$
is transmitted. In satellite communications, this can correspond to
the use of a single carrier occupying the entire transponder bandwidth.
This is of particular interest since the on-board power amplifier
can operate closer to saturation and hence improve the efficiency.

\section{Spectral efficiency optimization\label{sec:Spectral-Efficiency-optimization}}

In this section, we shown how to compute the ASE for a given receiver
and how to optimize the values of $T$ and $F$.

\subsection*{Symbol-by-Symbol detection\label{sec:Symbol-by-Symbol}}

Let us consider the central user (i.e., that for $\ell=0$). We first
consider the case shown in Figure \ref{fig:BlockDiagramReceiver}(a)
of a receiver composed by a filter matched to the shaping pulse $p(t)$,
followed by a proper discrete-time filter, that works on $\gamma\geq1$
samples per symbol interval, and a symbol-by-symbol (SBS) detector.
Although the discrete-time filter could be, in general, fractionally-spaced
(FS, i.e., $\gamma>1$), the detector will operate on one sample per
symbol interval. These samples will be denoted by $\{r_{k}^{(0)}\}$ and
can be expressed as
\begin{equation}
r_{k}^{(0)}=  \sqrt{E_{s}}c_{k}^{(0)}h(0,0,k) +\sqrt{E_{s}}\sum_{(n,\ell)\neq(0,0)}c_{k-n}^{(\ell)}h(n,\ell,k)+z_{k}\label{eq:sample_yk}
\end{equation}
in which $h(n,\ell,k)$ is the residual interference at time $kT$
due to the $\ell$-th user and the $(k-n)$-th transmitted symbol,
and $\{z_{k}\}$ is the additive noise term, in general colored unless
a whitening filter (WF) is employed after the MF. The discrete-time
filter is assumed properly normalized such that the noise variance
is $N_{0}$. The dependence of coefficients $h(n,\ell,k)$ on $k$
is through a complex coefficient of unit amplitude which disappears
for $\ell=0$ (hence $h(n,0,k)$ is independent of $k$) and is due
to the fact that $F$ is not an integer multiple of $1/T$.

\begin{figure}
	\begin{center}
		\includegraphics[width=1.0\columnwidth]{images/tpack/receiver}
		\caption{Some considered receivers: (a) symbol-by-symbol detector and (b) single-user
		detector based on trellis processing.\label{fig:BlockDiagramReceiver}}
	\end{center}
\end{figure}

Eq.~\eqref{eq:sample_yk} shows the two different impairments experienced
by the receiver, namely the background noise and the interference.
Instead of simply neglecting the interference due to adjacent symbols
and users, we pursue here a more general approach, which consists
of modeling the interference as a zero-mean Gaussian process with
power spectral density equal to $N_{I}$, of course independent of
the additive thermal noise---we point out that this approximation
is exploited only by the receiver, while in the actual channel the
interference is clearly generated as in~\eqref{eq:sample_yk}. Note
that the interference is really Gaussian distributed only if the transmitted
symbols $c_{k}^{(\ell)}$ are Gaussian distributed as well. However, especially
when the interference set is small, e.g., when $T$ and $F$ are large,
the actual interference distribution may substantially differ from
a Gaussian distribution.

We define \emph{auxiliary channel} the channel model assumed by the
receiver. With the above mentioned Gaussian approximation, the auxiliary
channel is
\begin{equation}
r_{k}^{(0)}=\sqrt{E_{s}}c_{k}^{(0)}h(0,0,k)+\mathfrak{v}_{k}\label{e:auxiliary}
\end{equation}
where $\{\mathfrak{v}_{k}\}$ are independent and identically distributed zero-mean
circularly symmetric Gaussian random variables, with variance $N_{0}+N_{I}$.
It turns out that
\begin{equation}
N_{I}=E_{s}\sum_{(n,\ell)\neq(0,0)}|h(n,\ell,k)|^{2}\label{eq:N_i}
\end{equation}
which results to be independent of $k$, as can be easily shown. We
are interested in evaluating the ultimate performance limits achievable
by a symbol-by-symbol receiver designed for the auxiliary channel~\eqref{e:auxiliary}
when the actual channel is that in~\eqref{eq:sample_yk}, in terms
of information rate (or spectral efficiency). This issue is an instance
of \emph{mismatched} detection~\cite{MeKaLaSh94} (see also~\cite{ArLoVoKaZe06}).
The achievable information rate (AIR), measured in bit per channel
use, for this mismatched receiver is
\begin{equation}
	I_{\mathrm{R}} = \mathfrak{h}(r_k^{(0)}) - \mathfrak{h}(r_k^{(0)}|c_k^{(0)}) \label{e:AIR}
\end{equation}
where
\begin{eqnarray}
	\mathfrak{h}(r_k^{(0)}) & = & -\mathrm{E}\left\{ \log_2 \left( \sum_{c\in\chi}q(r_{k}^{(0)}|c)\frac{1}{M} \right) \right\} \\
	\mathfrak{h}(r_k^{(0)}|c_k^{(0)}) & = & -\mathrm{E}\left\{ \log_2  q(r_{k}^{(0)}|c_{k}^{(0)}  ) \right\}
\end{eqnarray}
where $q(r_{k}^{(0)}|c_{k}^{(0)})$ is a Gaussian probability
density function (PDF) of mean $c_{k}^{(0)}$ and variance $(N_{0}+N_{I})$
(in accordance with the auxiliary channel model),
while the outer statistical average, with respect to $c_{k}^{(0)}$ and
$r_{k}^{(0)}$, is carried out according to the real channel model~\eqref{eq:sample_yk}~\cite{ArLoVoKaZe06}.
Eq.~\eqref{e:AIR} can be evaluated efficiently by means of a Monte
Carlo average~\cite{ArLoVoKaZe06}. From a system viewpoint, the
spectral efficiency, that is the amount of information transmitted
per second and per Hertz, is a more significant quality figure than
the information rate. Under the assumption of infinite transmission,
the ASE is defined as
\begin{equation}
\eta=\frac{I_\mathrm{R}}{FT}\quad[
\textrm{b/s}/\textrm{Hz} ]\,.\label{e:spectral_efficiency}
\end{equation}

For a given constellation and shaping pulse, it is possible to find
the spacings $T$ and $F$ that provide the largest ASE. In general,
we could expect that the optimal spacings depend on the signal-to-noise
ratio (SNR). In fact, it is possible to show that, as the SNR increases,
not only does the ASE increase, but also the optimal values of the
spacings change. The properties of the function $\eta(T,F,E_{S}/N_{0})$
cannot be easily studied in closed form, but it is clear, by physical
arguments, that it is bounded, continuous in $T$ and $F$, and tends
to zero when $T,F\to0$ or $T,F\to\infty$. Hence, the function $\eta(T,F)$
has a maximum value---according to our findings, in most cases there
are no local maxima other than the global maximum. Formally, for a
given modulation format, shaping pulse, and value of~$E_{S}/N_{0}$,
the optimization problem consists of finding the maximum of $\eta(T,F,E_{S}/N_{0})$
varying $T$ and $F$. This problem can be solved by evaluating $\eta(T,F,E_{S}/N_{0})$
on a grid of values of $T$ and $F$ (coarse search), followed by
an interpolation of the obtained values (fine search).

A measure of the SNR more significant than $E_{s}/N_{0}$ is given
by $E_{b}/N_{0}$, being $E_{b}$ the mean energy per information
bit, for which $E_{s}=I(E_{s})E_{b}$ holds.
The optimization problem becomes
\begin{equation}
\eta_{\textrm{M}}(E_{b}/N_{0})=\max_{T,F>0}\eta(T,F,E_{b}/N_{0})\,.\label{optEb-1}
\end{equation}
In order to solve it for a given value of $E_{b}/N_{0}$, we employed
the following technique. The AIR is first evaluated for some values
of the couple $(T,F)$, and $E_{s}/N_{0}$. The two sets, including
their cardinalities, must be designed so as to ensure an accurate
sampling of the AIR, when the latter is interpreted as a function
of $T$, $F$, and $E_{s}/N_{0}$. For each couple $(T_{i},F_{j})$,
cubic spline interpolation can be used to obtain a continuous function
of $E_{s}/N_{0}$ (fine search), denoted as $I(T_{i},F_{j},E_{s}/N_{0})$.
Then, given a value of $E_{b}/N_{0}$ the following fixed-point problems
are solved in $E_{s}/N_{0}$ for different couples $(T_{i},F_{j})$,

\begin{equation}
\frac{E_{s}}{N_{0}}=I\left(T_{i},F_{j},\frac{E_{s}}{N_{0}}\right)\frac{E_{b}}{N_{0}}
\end{equation}
and the AIRs corresponding to the solutions are denoted by $I(T_{i},F_{j},E_{b}/N_{0})$.
Further improvements could be achieved by adding $N_{I}$ as variable
in eq. \eqref{optEb-1}. However, we have found by numerical results
that choosing $N_{I}$ as in \eqref{eq:N_i} is almost optimal.

The spectral efficiency depends on the employed discrete-time filter.
Since the optimization of this filter with the aim of maximizing the
spectral efficiency is a hard task, we restricted our analysis to
the cases of a WF, that will be also considered in~\S\ref{sec:BCJR-receiver},
and of a minimum mean square error (MMSE) feedforward equalizer, possibly
fractionally spaced (FS) with at most 22 taps.

\subsection*{Single-User Trellis Processing\label{sec:BCJR-receiver}}

Improved, still achievable, lower bounds can be obtained by relaxing
the constraint on the adopted detection algorithm. In other words,
we can consider a more complex receiver able to cope with (a portion
of) the interference introduced by the adoption of the time-frequency
packing. The receiver considered in this section will not cope with
the interference due to the adjacent users---a single-user receiver
is still adopted.

For a general channel with finite intersymbol interference, an optimal
MAP symbol detector can be designed working on the samples at the
WF output as shown in Figure \ref{fig:BlockDiagramReceiver}(b). These
samples, denoted to as Forney observation model (see \S\ref{sec:obs_model}), can
still be expressed as in~\eqref{eq:sample_yk} with a proper expression
of coefficients $h(n,\ell,k)$. We assume to adopt the optimal receiver
for the following auxiliary channel:
\begin{equation}
r_{k}^{(0)}=\sqrt{E_{s}}\sum_{0\le n\le L}f_{n}c_{k-n}^{(0)}+\mathfrak{v}_{k}\label{e:auxiliary_bcjr}
\end{equation}
where $\{f_{n}\}_{n\geq0}$ are such that $f_{n}=h(n,0,k)$ and, as
mentioned, are independent of $k$, whereas the noise samples $\{\mathfrak{v}_{n}\}$,
that take into account the white noise and the residual interference,
are assumed independent and identically distributed zero-mean circularly
symmetric Gaussian random variables with variance $(N_{0}+N_{I})$,
with
\begin{equation}
N_{I}=\sum_{n>L}E_{s}|f_{n}|^{2}+\sum_{n}\sum_{\ell\neq0}E_{s}|h(n,\ell,k)|^{2}\,.\label{eq:N_i_bcjr}
\end{equation}
which is still independent of $k$. The corresponding MAP symbol detector
takes the form of the classical algorithm by Bahl, Cocke, Jelinek
and Raviv (BCJR)~\cite{BaCoJeRa74} working on a trellis whose state
takes into account $L$ interfering symbols only, according to a given
maximal allowable receiver complexity. The number of trellis states
is equal to $S=M^{L}$.

Let us define $\bm{c}=[c_{0}^{(0)},c_{1}^{(0)},...,c_{N-1}^{(0)}]$ and
$\bm{r}=[r_{0}^{(0)},r_{1}^{(0)},...,r_{N-1}^{(0)}]$, $N$ being a proper
integer. The simulation-based method described in~\cite{ArLoVoKaZe06}
allows to evaluate the AIR for the mismatched receiver, i.e.,
\begin{eqnarray}
I_{\mathrm{R}} & = & \lim_{N\rightarrow+\infty}\frac{1}{N}I(\bm{c};\bm{r})\nonumber \\
 & = & \lim_{N\rightarrow+\infty}\frac{1}{N}E\left\{ \log_{2}\frac{q(\bm{r}|\bm{c})}{q(\bm{r})}\right\} \;\left[\frac{\mathrm{bit}}{\mathrm{ch.\, use}}\right]\,.\,\,\,\,\label{eq:AIR_2}
\end{eqnarray}
In \eqref{eq:AIR_2}, $q(\bm{r}|\bm{c})$ and $q(\bm{r})$
are PDF according to the auxiliary channel model, while the outer
statistical average is with respect to the input and output sequences
evaluated according to the actual channel model~\cite{ArLoVoKaZe06}.
Eq. \eqref{eq:AIR_2} can be evaluated recursively through the forward
recursion of the BCJR detection algorithm matched to the auxiliary
channel model~\cite{ArLoVoKaZe06}. Once the AIR has been computed,
the spectral efficiency can be derived and the optimal time and frequency
spacings optimized accordingly, as described in the previous section.
For channels with finite ISI, optimal MAP symbol
detection can be equivalently implemented by working directly on the
MF output~\cite{CoBa05b}, i.e., on the so-called Ungerboeck observation
model (see \S\ref{sec:obs_model}). The equivalence does not hold when reduced-complexity
detection is considered and interference from adjacent channels arises.
Since it is difficult to predict which is the most convenient observation
model, it is of interest to evaluate the ASE when both models are
employed and this can be done as described for the Forney model (see
also \cite{RuFe09} for details).

\subsection*{Multi-User Detection}

Although the assumption of a single-user auxiliary channel gives very
useful results, tighter lower bounds can be obtained by using a more
general auxiliary channel model. In fact, we can consider a receiver
for the central user (that with $\ell=0$) that, in addition to the
interference taken into account by the receivers in~\S\ref{sec:BCJR-receiver},
also takes into account the $J$ adjacent signals on each side as
well (multi-user receiver)\textemdash{}we again point out that this
approximation is exploited only by the receiver, while in the actual
channel the interference is generated as in \eqref{eq:rec_signal2}.
The exact MAP receiver for the multi-user auxiliary channel can be
easily derived and employed to find the ASE in the new scenario. The
benefit of employing the multi-user auxiliary channel model when evaluating
the ASE is two-fold: first, it allows to evaluate the performance
degradation due to the use of single-user receivers, despite the presence
of a strong adjacent channel interference, with respect to a more
involved multi-user receiver, which is more {\it matched}
to the real channel. Second, it gives a practical performance upper
bound when low-complexity approximate multi-user receivers, for example
based on linear equalization or interference cancellation, are employed
(as examples, those in \cite{CoFePi11} and references therein). Obviously,
in this case some (limited) degradation must be expected.

\section{Channel shortening detection for time packing}
In the previous section, we adopted mismatched detectors which
consider just a limited amount of interference. The interference
considered at the detector is a truncation of the actual interference (both in time and frequency).
Clearly, the truncation does not maximize the ASE, which is instead what time packing aims to.
A better approach than truncation, is the adoption of channel shortening (CS) detectors, as described in \S\ref{sec:cont_time_cs}.
Namely, for a given memory $L$ considered at detector, we set the ISI at detector and the front-end filter as
the ones which maximize the achievable spectral efficiency.
Moreover, as shown in \S\ref{sec:cont_time_cs}, the shaping pulse can be also optimized to improve the performance.

\clearpage
\section{Numerical results\label{sec:Simulation-Results}}
In this section, we report the optimized spectral efficiency $\eta_{\textrm{M}}$
as a function of $E_{b}/N_{0}$ for different modulation formats and
shaping pulses. The considered modulation formats are the quaternary
and octal PSK (QPSK and 8PSK).

\begin{figure}
	\begin{center}
		\includegraphics[width=0.8\columnwidth]{images/tpack/QPSKgray_RRC_02}
		\caption{ASE for QPSK with Gray mapping and a RRC pulse having $\alpha=0.2$.\label{fig:ASEs-for--QPSK-RRCgray}}
	\end{center}
\end{figure}

\begin{figure}
	\begin{center}
		\includegraphics[width=0.8\columnwidth]{images/tpack/8PSK_RRC_02}
		\caption{ASE for 8PSK with a RRC pulse having $\alpha=0.2$.\label{fig:ASEs-for-8PSK}}
	\end{center}
\end{figure}

Fig.~\ref{fig:ASEs-for--QPSK-RRCgray} shows the optimized ASE in
case of time packing only for the QPSK modulation with a RRC pulse
with roll-off $\alpha=0.2$. Both symbol-by-symbol detection and trellis
processing (this latter taking into account $L=4$ interfering symbols)
are considered assuming Gray mapping. In this case, at the receiver
side we may use two identical and independent detectors, one working
on the in-phase and the other one on the quadrature component. This
is beneficial in case of adoption of a MAP symbol detector. In fact,
when $L$ interfering symbols are taken into account, we have two
detectors working on a trellis with $2^{L}$ states instead of a single
detector working on a trellis with $4^{L}$ states. Hence, for a given
complexity, a larger number of interferers can be taken into account.
The curve related to the absence of time packing (i.e., in case of
orthogonal signaling) and the Shannon Limit for AWGN~\cite{Sh48},
are also shown for comparison. It can be observed that the time-packing
technique allows to improve the spectral efficiency for each $E_{b}/N_{0}$
value with respect to the case of orthogonal signaling. Moreover it
can noticed that, in case of use of a symbol-by-symbol detector, the
FS-MMSE equalizer seems the best option whereas the Ungerboeck observation
model is more suited in case of trellis processing. Similar considerations
hold for the 8PSK modulation with a RRC pulse of $\alpha=0.2$. The
relevant results are shown in Fig.~\ref{fig:ASEs-for-8PSK}.
Still considering QPSK with Gray mapping and trellis processing with
$S=16$, we evaluated the effect of different shaping pulses. In particular,
RRC and RC pulses with different roll-off factors have been considered
along with prolate spheroidal wave functions~\cite{SlPo61} and the Gaussian pulse. In these
two latter cases, frequency packing is also employed. Fig. \ref{fig:ASE-for-QPSKotherpulses}
shows the performance of some of the considered pulses. In particular,
RRC pulses with $\alpha$ equal to $0.2$ and $1.0$ outperform all
other pulses at low and high $E_{b}/N_{0}$ values, respectively.
In particular, an impressive asymptotic spectral efficiency of 4.3
bit/s/Hz is obtained with QPSK and $\alpha=1$.
\footnote{This is due to the fact that the shaping pulse is smoother and so,
for a given value of $T$, the introduced interference is lower.}

\begin{figure}
	\begin{center}
		\includegraphics[width=0.8\columnwidth]{images/tpack/QPSKgray_cfr}
		\caption{ASE for QPSK with Gray mapping by using different pulses. At the receiver, a MF front end and trellis processing with $S=16$ is considered.\label{fig:ASE-for-QPSKotherpulses}}
	\end{center}
\end{figure}

What information theory promises can be approached by using proper
coding schemes. We considered MODCODs using the low-density parity-check
(LDPC) codes with length 64,800 bits of the DVB-S2 standard~\cite{DVB-S2-TR},
properly combined with QPSK and 8PSK modulations with time packing.
RRC pulses with $\alpha=0.2$ or $\alpha=1$ are considered. The corresponding
packet error rate (PER) have been computed by means of Monte Carlo
simulations and the results are reported in the spectral efficiency
plane in Fig. \ref{fig:Designed-MODCODs} using, as reference, an
MPEG PER of $10^{-4}$. In the same figure, the performance of the
MODCODs based on the same LDPC codes with orthogonal signaling and
employing QPSK, 8PSK, and the amplitude phase-shift keying (APSK)
modulation with 16 and 32 symbols (16- and 32APSK)~\cite{DVB-S2-TR},
are also shown for comparison. We can observe that we can reach, with
QPSK, values of spectral efficiency that, in case of orthogonal signaling,
cannot be reached even with 16APSK.
\begin{figure}
	\begin{center}
		\includegraphics[width=0.8\columnwidth]{images/tpack/shannon_plane}
		\caption{Designed MODCODs for QPSK and 8PSK with RRC pulses.\label{fig:Designed-MODCODs}}
	\end{center}
\end{figure}

The performance can be improved by adopting a CS detector.
Figure \ref{fig:tpack_CS} shows the optimized ASE for RRC and QPSK modulation with Gray mapping and $\alpha=0.2$
by adopting the time packing technique and single-user trellis processing.
Detection is performed by adopting two identical and independent detectors, one working
on the in-phase and the other one on the quadrature component. The figure shows the ASE obtained by single-user trellis processing in either case
of CS or truncation of the ISI. The considered numbers of states are $S=8$ and $S=64$. In the case of ISI truncation,
we optimized also the noise variance at detector, in order to achieve the best performance.
For comparison purpose, we also showed the ASE by quadrature amplitude (QAM) with cardinality 64 and 256
with orthogonal signaling.
It can be noticed that CS outperforms the truncation and exhibits an excellent ASE, which for some SNR values is even higher than the
one achieved by QAM modulations.

\begin{figure}
	\begin{center}
		\includegraphics[width=0.8\columnwidth]{images/tpack/tpacking_CS}
		\caption{ASE for time packing and CS detection when the modulation is QPSK, with Gray mapping and RRC pulse $\alpha=0.2$.\label{fig:tpack_CS}}
	\end{center}
\end{figure}

config: arxiv


TITLE: Calculate determinant of matrix $n \times n$.
QUESTION [0 upvotes]: I have the following matrix
$$A=\begin{bmatrix}
a-x_1 &-x_1   &\cdots &-x_1\\
-x_2 &a-x_2 &\cdots &-x_2\\
\vdots &\vdots &\ddots &\vdots &\\
-x_n &-x_n &\cdots &a-x_n \\
\end{bmatrix}
$$
where $a=1+\sum_{1}^{n}x_i.$ It seems determinant of $A$ has closed form. Can you help?

REPLY [2 votes]: The matrix $B = A - aI$ consists of $n$ identical columns and thus has rank (at most) $1$.  Therefore, $B$ has a $0$ eigenvalue with multiplicity (at least) $n-1$; the sole remaining eigenvalue must be equal to the trace of $B$, which is $\sum_i (-x_i) = 1 - a$.  Therefore, the complete set of eigenvalues of $B$ is $$\underbrace{0,\ldots,0}_{n-1\text{ times}}, 1-a.$$  The eigenvalues of $A = B + aI$ are simply shifted upwards by $a$: $$\underbrace{a,\ldots,a}_{n-1\text{ times}},1,$$ so the determinant of $A$ is the product of these, namely $a^{n-1}$.


TITLE: Beginning the study of coalgebras and the sigma notation.
QUESTION [3 upvotes]: I'm beginning the study of coalgebras and the sigma notation using the book called Hopf Algebras of M.E. Sweedler. I'm doing the exercises and I don't know if this ideas are realy clear for me and if what I do is realy what I need do here.

Let $C$ a $\mathbb{k}$-vectorial space $\Delta$ the comultiplication ($\Delta:C \rightarrow C\otimes C $) and $\varepsilon$ the counity ($\varepsilon: C\rightarrow \mathbb{k}$
Exercise: verify the following identity. For any $c\in C$ $$\Sigma_{(c)}\varepsilon(c_{(2)})\otimes\Delta(c_{(1)})=\Delta(c)$$

Here I'm using the Sigma Notation, $\Delta(c)=\Sigma_{(c)}c_{(1)}\otimes c_{(2)}$.

What I did:
We have that each $\varepsilon(c_{(2)})$ is one scalar, say $k_{(2)}$. Furthermore $\Delta(c_{(2)})=\Sigma_{(c_{(2)})}c_{(2)_{(1)}}\otimes c_{(2)_{(2)}}$.Therefore,
$$
\Sigma_{(c)}\varepsilon(c_{(2)})\otimes\Delta(c_{(1)})=\Sigma_{(c)}\varepsilon(c_{(2)})\otimes\Sigma_{(c_{(2)})}c_{(2)_{(1)}}\otimes c_{(2)_{(2)}}=\Sigma_{(c)}k_{(2)}\otimes\Sigma_{(c_{(2)})}c_{(2)_{(1)}}\otimes c_{(2)_{(2)}}=^*\Sigma_{(c)}k_{(2)}\otimes\Sigma_{(c_{(2)})}c_{(2)_{(1)}}\otimes c_{(2)_{(2)}}=\Sigma_{(c)}\Sigma_{(c_{(2)})}c_{(2)_{(1)}}\otimes c_{(2)_{(2)}}=\Sigma_{(c)}c_{(1)}\otimes c_{(2)}=\Delta(c)
$$
But, after $=^*$  I don't know if each equality makes sense. If makes, why?

REPLY [3 votes]: We have
$$\sum{\epsilon(c_{(1)})\otimes c_{(2)}}=\sum{c_{(1)}\otimes \epsilon(c_{(2)})}=c$$
(This is an axiom.) Since scalar multiplication is commutative, we also have
$$\sum{\epsilon(c_{(2)})\otimes c_{(1)}}=c$$
(Really the identity is $\sum{\epsilon(c_{(2)})c_{(1)}}=c$).
Thus
$$\sum{\epsilon(c_{(2)})\otimes \Delta(c_{(1)})}=\sum{1\otimes \Delta(\epsilon(c_{(2)})c_{(1)})}=1\otimes \Delta(c)$$
(the first equality is true since scalars can be pulled in and out of terms of a tensor product) and the ever-confusing abuse of notation has us calling this $\Delta(c)$.


TITLE: Prove or disprove: $A$ is a subgroup of $G$ if and only if $AA=A$.
QUESTION [2 upvotes]: I have a question about groups.
I need to prove or disprove:

Let $G$ be a group, and $A$ non-empty subset of $G$. $A$ is a subgroup of $G$ if and only if $AA=A$,  where $AA=$ $\{a*a'|a,a' \in A\}$.

If $A$ is a subgroup then of course $AA=A$.
However, I couldn't prove the other direction. I know $A$ is closed under multiplication, but I think something must be wrong with the inverse. However, I couldn't prove it. Any help will be appreciated!

REPLY [1 votes]: Note that, for any group $G$ and for any finite nonempty subset $A\subseteq G$, $A$ is a subgroup of $G$ if and only if $A\cdot A=A$.  A proof can be done using a similar argument to the proof of the proposition below.
If $A$ is an infinite subset of $G$, then it is possible that $A\cdot A=A$, yet $A$ is not a subgroup of $G$ (nonetheless, the condition $A\cdot A=A$ guarantees that $A$ is a subsemigroup of $G$).  A different counterexample is $G:=\mathbb{R}$ where $A:=\mathbb{R}_{>0}$.
Alternatively, for any nonempty subset $A\subseteq G$ whose elements all have finite orders, $A$ is a subgroup of $G$ if and only if $A\cdot A=A$. A proof is, again, similar to the proof of the proposition below.

Proposition.  We say that a group $G$ is neat if, for any nonempty subset $A$ of $G$, $A$ is a subgroup of $G$ if and only if $A\cdot A=A$.  Then, a group $G$ is neat if and only if every cyclic subgroup of $G$ is finite.

If $G$ has an infinite cyclic subgroup $\langle g\rangle$ for some $g\in G$, then take $A:=\{g^k\,|\,k\in\mathbb{Z}_{\geq 0}\}$.  Consequently, $A\cdot A=A$, but $A$ is not a subgroup of $G$.  That is, $G$ is not neat.
Conversely, suppose that every cyclic subgroup of $G$ is finite.  Suppose that $A\subseteq G$ is a nonempty subset such that $A\cdot A=A$.  Pick $a\in A$.  We can see that $a^k\in A\cdot A$ for all positive integer $k$.  Since the subgroup $\langle a\rangle$ of $G$ is cylic, it is finite.  Suppose $n$ is the order of the subgroup $\langle a\rangle$.  If $n=1$, then $a=1_G=a^{-1}$.  For $n>1$, note that $a^n=1_G$ and $a^{n-1}=a^{-1}$.  Thus, $A$ contains the identity element of $G$, and for any $a\in A$, we have $a^{-1}\in A$.  Since $A\cdot A=A$, we conclude that $A$ is a subgroup of $G$.
Examples. Here are some neat groups:

finite groups,
direct limits of finite groups (such as the Prüfer groups and the general linear group $\text{GL}_\infty(\mathbb{F})$ where $\mathbb{F}$ is a finite field), and
weak products (direct sums) of neat groups (such as $\mathbb{Q}/\mathbb{Z}$).


TITLE: showing a set is totally disconnected
QUESTION [6 upvotes]: So, we are considering the subset
$$ S = \{(x, y) \in \mathbb{R^2} | (x \text{ and } y \in \mathbb{Q}) \text{ or }  (x \text{ and } y \notin \mathbb{Q})\} $$
And consider its complement $$ T = \mathbb{R^2} \backslash S $$
The set T is disconnected, actually I am fairly certain it is totally disconnected. I am just having problems showing that rigorously. I was trying to show it using straight lines but I don't think I was getting anywhere. I know that a totally disconnected set's only connected sets are the one point sets. I've been trying to show that given two arbitrary points, that a separation exists between them. It is more difficult since this is in the plane.
Any hints at all would be a great help. Maybe I'm making mountains of molehills.

REPLY [5 votes]: I had written out a full solution, but since this is homework, I've removed it and replaced it with this suggestion.
One way to prove that $T$ is totally disconnected is to show that whenever $p$ and $q$ are distinct points of $T$, then there are open sets $A$ and $B$ of $\mathbb{R}^2$ such that $T\subseteq A\cup B$, $(A\cap B)\cap T=\emptyset$, $p\in A$, and $q\in B$. This will show that there is a disconnection of $T$ in which $p$ and $q$ are in distinct components. In particular, $p$ and $q$ cannot be in the same connected component of $T$. If this holds for all pairs of points $p$ and $q$, then the connected components of $T$ must be single points.
So, pick two distinct points $p$ and $q$ in $T$. Try to find a line that is completely contained in $S$ and which separates $p$ and $q$. One way to achieve a line completely contained in $S$ is to have it go through a rational point with rational slope. Then throw away the line to get your two sets $A$ and $B$.


TITLE: Why $\operatorname{Gal}(\mathbb{Q}_q(\zeta_p)/\mathbb{Q}_q)$ is isomorphic to $\mathbb{Z}/f\mathbb{Z}$
QUESTION [3 upvotes]: I would like to ask a question on this answer. I don't understand why $\operatorname{Gal}(\mathbb{Q}_q(\zeta_p)/\mathbb{Q}_q)$ is isomorphic to $\mathbb{Z}/f\mathbb{Z}$, where $f$ is the degree of the cyclotomic polynomial. How could one calculate this degree?
And a second question: If I know the degree's of the irreducible factors of the cyclotomic polynomial, why is there a connection to the cardinality of a galois gorup?

edit: I found a similar statement here in Corollary 3.10, but without a proof. Maybe the context can help

REPLY [2 votes]: The key ingredients are:

The polynomial $x^p-1$ is separable over the finite field $\mathbb{F}_q$.
The simple Galois theory of finite fields.
Hensel's Lemma.
An extension $\mathbb{F}_{q^m}$ of $\mathbb{F}_q$ contains $p^{th}$ roots of unity, if and only if $p\mid q^m-1$ (the multiplicative group of a finite field is cyclic).

The last point allows you to deduce that the minimal polynomial of $\zeta_p$ over $\mathbb{F}_q$ has degree $f$ = the order of $q$ in $\mathbb{Z}/p\mathbb{Z}^*$. Therefore the cyclotomic polynomial $\Phi_p(x)=(x^p-1)/(x-1)$ has a factor $\overline{m}(x)$ of degree $f$ in
$\mathbb{F}_q[x]$. Hensel's Lemma then tells you that the cyclotomic polynomial
also has a factor $m(x)$ of degree $f$ in $\mathbb{Z}_q[x]$. Now you know that
$$[\mathbb{Q}_q(\zeta_p):\mathbb{Q}_q]=f.$$
So the Galois group is also of order $f$ (the extension is obviously the splitting field of $\Phi_p(x)$).
The roots of $\overline{m}(x)$ are (by the Galois theory of finite fields)
$\zeta_p^{q^i}, 0\le i<f$. Thus the same holds for $m(x)$. Thus there is a
unique automorphism $F$ in the Galois group that has the property $F(\zeta_p)=\zeta_p^q$. From our knowledge of the roots of $m(x)$ we see that the lowest power of $F$ that maps $\zeta_p$ to itself is $F^f$. Hence the Galois group must be cyclic of order $f$.


TITLE: Limit of a sequence $\sqrt{5 + 2a_n}$
QUESTION [3 upvotes]: Let $a_1 = 0$ and $$a_{n+1} = \sqrt{5+2a_n}, n>0$$ Show that $\lim_{n\to\infty}a_n$
exists and find the limit.
Manual computation shows that the limit will be approximately 3.5 but how would i go about proving it?

REPLY [0 votes]: I am actually interested in this problem since I have never made a induction proof earlier. So here is my try.
Since we don't have a closed form of $a_{n}$ we instead prove that $a_{n+1}<1+\sqrt{6}$ since it is obvious that $a_{n}\leq a_{n+1}$.
First step: Since $n>0$ we want to test that the statement holds for $n=1$:
$a_{2}=\sqrt{5}<1+\sqrt{6}$ since we are given that $a_{1}=0$.
Inductive step: Assume now that $n=k$ holds (for arbitrary $k>1,k\in \mathbb{N}$)
If we now can prove that for $n=k+1$ also is true, then we are done with the proof.
$a_{k+2}=\sqrt{5+2a_{k+1}}$ = $\sqrt{5+2\sqrt{5+2a_{k}}}$. From here I not sure how to proceed because I don't know where I am supposed to end.


TITLE: Consider the function $f (z) = z +2z^2 +3z^3 +··· = \sum_{n≥0} nz^n$ defined on the open disk $\{z \vert|z| < 1\}$. Choose the correct option
QUESTION [4 upvotes]: Consider the function $f (z) = z +2z^2 +3z^3 +··· = \sum_{n≥0} nz^n$ defined on the open disk $\{z \vert|z| < 1\}$. Choose the
correct option:
(a) f is not injective but attains every complex value at least once.
(b) f is injective but does not attain every complex value.
(c) f is injective and attains every complex value.
(d) None of the above.
Attempt: $f(z)=z +2z^2 +3z^3 +··· =z(1+2z+3z^2+...)=\frac{z}{(1-z)^2}.$
Now, for injectivity:
$f(z_1)=f(z_2)\implies z_1(1-z_2)^2=z_2(1-z_1)^2\implies (z_1-z_2)(1-z_1z_2)=0$. Since in the open unit disk $z_1z_2\neq1$, so we have $z_1=z_2$ and hence the function is injective.
I looked the function $\frac{z}{(1-z)^2}$ known as the Koebe function and wikipedia says $f(z)$ can never achieve $\frac{-1}{4}$ as $f(z)=\frac{-1}{4} \iff z=-1$ but, $z=-1$ is not in the unit disk, I wish to see a different approach on the surjectivity part. Can someone please help me with the onto (surjective) part?

REPLY [1 votes]: Let's just do it in the straightforward way. We solve $$\frac z{(1-z)^2} = c.$$ This simplifies to $cz^2 - (2c + 1)z + c = 0$. If $c = 0$ then $z = 0$, which is in the open disk. Otherwise, $z^2 - \frac{2c+1}c z + 1 = 0.$ So the two solutions $z_1$ and $z_2$ will always have product $1$, from Vieta's theorem. Therefore, to find a $c$ such that no $z$ in the open unit disk satisfies the equation, you have to let $|z_i| = 1 \quad (i = 1, 2)$. So we substitute $z_1 = e^{i\theta}$ and $z_2 = e^{-i\theta}$, which gets you $$\frac{2c+1}{c} = 2\cos \theta,$$ by Vieta's theorem again. Note that $\theta$ is real while $c$ may be complex.
After solving this, $c = \frac{1}{2\cos\theta - 2} \in \left(-\infty, -\frac14\right]$. And any $c$ in this interval is not obtainable.


TITLE: Relation between cut families and existence of directed cycles
QUESTION [1 upvotes]: I would like to know what you think of the following statement and, in case it is true, how would you prove it. Consider a directed graph $G=(V,A)$ where every vertex has degree higher or equal than three, and which contains an r-arborescence (a directed spanning tree); then

the graph has a directed cycle iff for every maximal obstruction-free family of cuts $\mathcal{S}=\{S_i\}_{i=1}^{|V|}$ such that $S_i\subset S_{i+1}$, $\exists \tilde S\in\mathcal{S}$ with $|\delta^-(\tilde S)|\geq 1$ and $|\delta^+(\tilde S)|\geq 1$.

An obstruction-free family of cuts is here defined as a family such that $\forall S\in\mathcal{S}$, no subset of $\mathcal{S}\setminus S$ forms a partition of $S$. Furthermore, $\delta^+(S)$ is the set of outgoing edges in the boundary of $S$ and $\delta^-(S)$ is the set of incoming edges in the boundary of $S$.

REPLY [0 votes]: If my reasoning are right then it took me more time to understand the statement than to prove it. :-) As I understood, the condition after “iff” is equivalent to that for any ordering $v_1,\dots, v_n$ of vertices of there exists $i$  such that $G$ contains edges $(v_j,v_{j’})$ and $(v_{k’},v_k)$ with $j,k\le i<j’,k’$. Now we can prove the statement for any directed graph $G$.
Assume that the graph $G$ has a directed cycle $C$. Then given an ordering of vertices of $G$  let $v_i$ be the first vertex of $C$ with respect to this order. Then the condition holds even for $j=k=i$.
Conversely, if $G$ is a directed acyclic graph then a topological ordering of its vertices clearly violates the condition.


TITLE: if $(|N|,[G:N])=1$, then $G$ has a unique subgroup of order $|N|$
QUESTION [2 upvotes]: Let $G$ a finite groupe and $N\lhd G$ s.t. $(|N|,[G:N])=1$. Show that $G$ has a unique subgroup of order $|N|$.
To be honnest, I don't really understand the question... would it be that $N$ is the only subgroup of order $|N|$ ? If yes :
Attempts
Let $K\lhd G$ s.t. $|K|=|N|$. Suppose there is $h\in K$ s.t. $h\notin N$. In particular, $hN\neq N$ and $h^{[G:N]}N=H$, how can I continue ?

REPLY [4 votes]: Let $K$ be another subgroup of $G$ such that $ |K| = |N| $ , then since $N$ is a normal subgroup of $G$ , therefore $NK$ will also be a subgroup of $G$.
$|NK| = (|N||K|)/|N \cap K|$
But since $NK$ is a subgroup of G therefore by Lagrange's theorem $|NK|$ divides $|G|$ which from above equation implies $|N| = |K| = |N \cap K|$ (since $(|N| , [G:N]) = 1$ ) Hence $ N = K $  , that is $N$ is unique subgroup of order $|N|$.


TITLE: If an nonnegative measurable function $f$ is Lebesgue integrable on $(0,1)$, then $\sum_{n \geq 0} 2^n m(\{x: f(x) \geq 2^n\})$ is finite
QUESTION [1 upvotes]: Here $m$ is the Lebesgue measure, and $f$ is only defined on $(0,1)$. The converse statement is actually also correct, but I am only struggling with the given direction.
By considering $f_n = f\chi_{2^n \leq f < 2^{n + 1}}$, where $\chi$ is the indicator function, I could conclude by using monotone convergence theorem that $\sum_{n \geq 0} 2^n m(\{x: 2^n \leq f(x) < 2^{n + 1}\})$ is finite, but how do I go from here to the required sum?

REPLY [1 votes]: Having defined $$a_n = 2^{n}m(\{x\in X:2^n\le f(x)<2^{n+1}\}),$$ the desired sum is $$\sum_{n=1}^{\infty}\sum_{k=0}^{\infty}2^{-k}a_{n+k}.$$ Since the terms are non-negative, we can rearrange to get $$\sum_{n=1}^{\infty}\left(\sum_{k=0}^{n-1}2^{-k}\right)a_n = \sum_{n=1}^{\infty}\left(2-\frac{1}{2^{n-1}}\right)a_n\le 2\sum_{n=1}^{\infty}a_n.$$