text:
\begin{document}

\title{On the MIMO Capacity with Residual \\Transceiver Hardware Impairments}
\author{\IEEEauthorblockN{Xinlin~Zhang\IEEEauthorrefmark{1}, Michail~Matthaiou\IEEEauthorrefmark{2}\IEEEauthorrefmark{1}, Emil~Bj\"ornson\IEEEauthorrefmark{3}\IEEEauthorrefmark{4}, Mikael Coldrey\IEEEauthorrefmark{5}, and M\'erouane~Debbah\IEEEauthorrefmark{3}}
\IEEEauthorblockA{\IEEEauthorrefmark{1}Department of Signals and Systems, Chalmers University of Technology, Gothenburg, Sweden}
\IEEEauthorblockA{\IEEEauthorrefmark{2}School of Electronics, Electrical Engineering and Computer Science, Queen's University Belfast, Belfast, U.K.}
\IEEEauthorblockA{\IEEEauthorrefmark{3}Alcatel-Lucent Chair on Flexible Radio, SUPELEC, Gif-sur-Yvette, France}
\IEEEauthorblockA{\IEEEauthorrefmark{4}Department of Signal Processing, ACCESS, KTH Royal Institute of Technology, Stockholm, Sweden}
\IEEEauthorblockA{\IEEEauthorrefmark{5}Ericsson Research, Ericsson AB, Gothenburg, Sweden}
E-mail: xinlin@chalmers.se, m.matthaiou@qub.ac.uk, emil.bjornson@supelec.fr, \\mikael.coldrey@ericsson.com,  merouane.debbah@supelec.fr}
\maketitle

\begin{abstract}
Radio-frequency (RF) impairments in the transceiver hardware of communication systems (e.g., phase noise (PN), high power amplifier (HPA) nonlinearities, or in-phase/quadrature-phase (I/Q) imbalance) can severely degrade the performance of traditional multiple-input multiple-output (MIMO) systems. Although calibration algorithms can partially compensate these impairments, the remaining distortion still has substantial impact. Despite this, most prior works have not analyzed this type of distortion. In this paper, we investigate the impact of residual transceiver hardware impairments on the MIMO system performance. In particular, we consider a transceiver impairment model, which has been experimentally validated, and derive analytical ergodic capacity expressions for both exact and high signal-to-noise ratios (SNRs). We demonstrate that the capacity saturates in the high-SNR regime, thereby creating a finite capacity ceiling. We also present a linear approximation for the ergodic capacity in the low-SNR regime, and show that impairments have only a second-order impact on the capacity. Furthermore, we analyze the effect of transceiver impairments on large-scale MIMO systems; interestingly, we prove that if one increases the number of antennas at one side only, the capacity behaves similar to the finite-dimensional case. On the contrary, if the number of antennas on both sides increases with a fixed ratio, the capacity ceiling vanishes; thus, impairments cause only a bounded offset in the capacity compared to the ideal transceiver hardware case.

\end{abstract}
\thispagestyle{empty}

\vspace{0.2cm}
\section{Introduction}
MIMO wireless communication systems have attracted considerable attention over the past decades due to their ability to enhance the channel capacity and transmission reliability.  Telatar and Foschini have respectively shown in \cite{telatar1999capacity} and \cite{foschini1998a} that there is a linear growth in channel capacity by increasing the number of transmit and receive antennas, without requiring additional transmit power or bandwidth. Although numerous publications have appeared in this field, the vast majority assumes ideal RF hardware. However, this assumption is quite unrealistic in practice. More specifically, RF impairments, such as I/Q imbalance \cite{qi2010IQ, zou2008IQ}, HPA nonlinearities \cite{qi2012HPA_nonlinearity, au2007HPA} and oscillator PN \cite{durisi2013PN_Wiener, katz2004PN} are known to have a deleterious impact on the performance of practical MIMO systems. Even though one can resort to calibration schemes at the transmitter, or compensation algorithms at the receiver  to partially mitigate these impairments \cite{schenk2008rf}, there still remains certain amount of distortion unaccounted for. The reasons for such residual transceiver impairments are, for example, inaccurate models which are used to characterize the impairments' behavior, imperfect parameters estimation errors due to thermal noise, and unsophisticated compensation algorithms with limited capabilities.

In this context, very few publications have studied the impact of residual transceiver impairments. For example, \cite{studer2010residual} provided experimental results to model the statistical behavior of residual hardware impairments. Moreover, they also investigated the impact of  transmitter impairments on several existing MIMO detection algorithms (e.g., zero-forcing  detection, maximum-likelihood detection, and max-log a posteriori probability detection). In \cite{Emil2013imp}, the authors analyzed the MIMO channel capacity under the aforementioned residual impairment model, but they only considered hardware impairments at the transmitter side and mainly derived high-SNR capacity ceilings. Very recently, \cite{Michalis2013relay} reported how hardware impairments affect dual-hop relaying systems. However, to the best of our knowledge, a detailed study of the MIMO system capacity in the presence of residual transceiver hardware impairments is missing from the literature.

Motivated by the above discussion, we hereafter analytically assess the impact of residual RF impairments in \textit{the transmitter and receiver hardware} of MIMO systems. More specifically, we derive a new analytical expression for the MIMO ergodic capacity in independent and identically distributed (i.i.d.) Rayleigh fading channels for arbitrary SNR values. Additionally, we also present asymptotic capacity expressions in the high-SNR regime. In the low-SNR regime, we derive expressions for the minimum normalized energy per information bit required to convey any positive rate reliably and the wideband slope \cite{lozano2003lowSNR}, which are the two key low-SNR parameters. Throughout our analysis, we find that the impact of residual impairments is marginal on low SNR systems, while it can substantially affect the performance of high SNR systems. In the last part, we analyze the ergodic capacity of large-dimensional MIMO systems with transceiver impairments and deduce asymptotic closed-form expressions for three typical cases. This provides valuable insights on how transceiver impairments affect large-scale (or ``massive'') MIMO systems \cite{Rusek2013a}.

\textit{Notation:} Upper and lower case boldface letters denote matrices and vectors, respectively. The trace of a matrix is expressed by $\mathrm{tr}\left(\cdot\right)$. The $n \times n$ identity matrix is represented by $\mathbf I_n$. The expectation operation is $\mathbb {E} [\cdot]$, while the matrix determinant is denoted by det$(\cdot)$. The superscripts $(\cdot)^ H$ and $(\cdot)^{-1}$ stand for Hermitian transpose and matrix inverse, respectively. The Euclidean vector norm is denoted by $\left\|\cdot\right\|$. The symbol $\mathcal{CN}\left(\mathbf m, \boldsymbol\Sigma\right)$ denotes a circularly-symmetric complex Gaussian distribution with mean $\mathbf m$ and covariance $\boldsymbol\Sigma$.

\section{Signal and System Models}
\label{sec:signalandsystems}

The canonical flat-fading point-to-point MIMO channel with $N_{t}$ transmit antennas and $N_{r}$ receive antennas is modeled as
\begin{equation}
{\mathbf{y}}={\mathbf{H}}\mathbf{s}+\boldsymbol\nu
\label{eq:canonical}
\end{equation}
where ${\mathbf{s}}\in\mathbb{C}^{N_{t}\times 1}$ represents the transmitted signal, with zero mean and covariance matrix $\mathbb{E}_{\mathbf{s}} \left[\mathbf s\mathbf s^H\right] = \mathbf Q$. The received signal is denoted by ${\mathbf{y}}\in\mathbb{C}^{N_{r}\times 1}$, while ${\boldsymbol\nu}  \sim\mathcal{CN}\left(\mathbf{0}, \mathbf{I}_{N_r} \right)$ is the (normalized) additive complex Gaussian receiver noise.
The channel matrix is denoted by $\mathbf{H}\in \mathbb{C}^{N_r\times N_t}$ and is assumed to have i.i.d. complex Gaussian entries with zero mean and unit variance. The receiver is assumed to know $\mathbf{H}$ perfectly, while only its statistical characteristics are available at the transmitter.

Unfortunately, the canonical model cannot describe physical hardware impairments of RF transceivers in an accurate way.
To be more specific, on the transmitter side, the impairments will cause a mismatch between the intended signal and what is actually transmitted; on the receiver side, the impairments will distort the received signal during the reception processing. These impairments come from different sources, for example, I/Q imbalance, HPA non-linearities and PN \cite{schenk2008rf}. Compensation schemes can be applied at both the transmitter and receiver to mitigate part of these impairments; however, as shown in \cite{schenk2008rf,studer2010residual}, the residual impairments will still induce additional additive distortion noises. As proposed and validated in \cite{schenk2008rf,studer2010residual}, the impact of residual transceiver impairments is well-modeled by a more general channel model:

\begin{equation}
{\mathbf{y}} = {\mathbf{H}}\left( {\mathbf{s} + \boldsymbol\eta_{t} } \right) + \boldsymbol\eta_{r} + \boldsymbol\nu
\label{eq:impairmodel}
\end{equation}
where the additive terms $\boldsymbol\eta_t$ and $\boldsymbol\eta_r$ are $\textit{distortion noises}$ from the residual impairments in the transmitter and receiver, respectively. The system block diagram is shown in Fig.~\ref{fig:Block_Diagram}. Furthermore, the measurement results in \cite{studer2010residual} show that the residual transmit distortion noise is well-modeled as Gaussian distributed, with the important property that its average power is proportional to the average signal power.
On this basis, the transmitter and the receiver distortion noises are modeled as
\begin{align} \label{eq:etat-distribution}
\boldsymbol{\eta}_t &\sim \mathcal{CN}\left(\mathbf{0}, \delta_t^2  \diag(q_1,\ldots,q_{N_t}) \right) \\
\boldsymbol{\eta}_r &\sim \mathcal{CN}\left(\mathbf{0}, \delta_r^2  \mathrm{tr}( \mathbf{Q}) \mathbf{I}_{N_r} \right) \label{eq:etar-distribution}
\end{align}
where $q_1,\ldots,q_{N_t}$ are the diagonal elements of the signal covariance matrix $\mathbf{Q}$. This means that the transmitter distortion power at the $n$th transmit antenna is proportional to the signal power $q_n$ applied on the same antenna, while the receiver distortion power at the $m$th receive antenna is proportional to the average signal power $\mathrm{tr}( \mathbf{Q})$ received over the $m$th row of the channel matrix $\mathbf{H}$.\footnote{In practice, the receiver will amplify and filter the received signal ${\mathbf{y}}$ in several steps during reception. The receiver distortion noise $\boldsymbol{\eta}_r$ is the aggregation of these steps which occur at different amplification levels. Without loss of generality, \eqref{eq:etar-distribution} represents the aggregate receiver distortion using the amplification at the time when the signal first reaches the receive antenna.} This model assumes sufficient decoupling between the transmit and the receive RF chains, such that the corresponding impairments are statistically independent across the antennas \cite{studer2010residual}.

\begin{figure}
\begin{centering}
\includegraphics [keepaspectratio,width=\columnwidth]{block-model}
\caption{Block diagram of the MIMO channel with distortion noises from residual impairments in the transmitter and receiver hardware.}\label{fig:Block_Diagram}
\end{centering}
\end{figure}

The proportionality parameters $\delta_t$ and $\delta_r$ characterize the level of residual impairments in the transmitter and receiver, respectively. Note that $\delta_t$ and $\delta_r$ are inherently connected to the error-vector magnitude (EVM) metric \cite{holma2011LTE}, which is commonly used to quantify the mismatch between the intended signal and the actual signal in RF transceivers. In our notation, the total EVM in the transmitter hardware is given by
\begin{equation}
\mathrm{EVM} \triangleq \sqrt{\frac{\mathbb{E}_{\boldsymbol\eta_t}[ \left\| \boldsymbol\eta_t \right\|^2 ]}{\mathbb{E}_{\mathbf s}[ \left\| \mathbf s\right\|^2 ]}} = \delta_t.
\end{equation}
In practical applications, such as long term evolution (LTE), the EVM requirements are in the range $\delta_t \in [0.08, 0.175]$ \cite[Sec.~14.3.4]{holma2011LTE}. Note that (\ref{eq:impairmodel}) reduces to the canonical model (\ref{eq:canonical}) for $\delta_t = \delta_r = 0$, which indicates ideal hardware on both sides.

\section{Ergodic Channel Capacity Analysis}

Based on the residual impairment model in Section \ref{sec:signalandsystems}, we now derive an expression for the ergodic capacity for any number of antennas and arbitrary SNR.

\begin{definition}
The SNR is denoted by $\rho$. We will also use the SNR to represent the effective signal power $\rho = \mathrm{tr}( \mathbf{Q}  )$, since the channel gain and receiver noise power are normalized in this paper.
\end{definition}

\begin{remark}
An increase in SNR can be achieved by increasing the transmit power or improving the channel conditions (i.e., by decreasing the propagation loss). If the transmit power is increased such that we move far outside the dynamic range of the power amplifier, then the EVM will increase and thus $\delta_t$ should also be increased \cite{studer2011residual2} and advanced dynamic power adaptation is required \cite{Emil2012imp}. For the sake of clarity and brevity in interpretation, we will keep the analysis clean by assuming that any change in SNR is achieved by a change in the propagation loss, while the transmit power is fixed.
\end{remark}

We define $q \triangleq \mathrm {min}({N_t,N_r})$ and $p \triangleq \mathrm {max}({N_t,N_r})$ and have the following lemma.

\begin{lemma} \label{lemma_capacity_expression}
The ergodic channel capacity of \eqref{eq:impairmodel} with i.i.d.~Rayleigh fading and under the constraint $\mathrm{tr}( \mathbf{Q}  ) \leq \rho$ is
\begin{equation} \label{eq:ergodiccapacity}
C = {{\mathbb E}_{\mathbf H}} \left[ \log_2 \det \left( \mathbf{I}_{N_r} + \frac{\rho}{N_t} \mathbf{H} \mathbf{H}^H \boldsymbol{\Phi}^{-1} \right) \right]
\end{equation}
where $\boldsymbol{\Phi} \triangleq \left( \frac{\rho}{N_t} \delta_t^2 \mathbf{H} \mathbf{H}^H + (\delta_r^2 \rho+ 1) \mathbf{I}_{N_r} \right)$. The capacity is achieved by $\mathbf{s} \sim \mathcal{CN}(\mathbf{0}, \frac{\rho}{N_t} \mathbf{I}_{N_t})$, giving the distortion noise distributions
\begin{align}
\boldsymbol{\eta}_t &\sim \mathcal{CN}\left(\mathbf{0}, \delta_t^2  \frac{\rho}{N_t} \mathbf{I}_{N_t} \right) \\
\boldsymbol{\eta}_r &\sim \mathcal{CN}\left(\mathbf{0}, \delta_r^2  \rho \mathbf{I}_{N_r} \right).
\end{align}
\end{lemma}
\begin{IEEEproof}
For any channel realization $\mathbf{H}$ and signal covariance matrix $\mathbf{Q}$, \eqref{eq:impairmodel} can be seen as an instance of the canonical model \eqref{eq:canonical} with noise covariance
\begin{equation}
\boldsymbol{\Phi} = \left( \delta_t^2 \mathbf{H} \diag(q_1,\ldots,q_{N_t}) \mathbf{H}^H \!+\! (\delta_r^2  \mathrm{tr}( \mathbf{Q})+ 1) \mathbf{I}_{N_r} \right).
\end{equation}
Thus, the sufficiency of using a Gaussian distribution on $\mathbf{s}$ follows from \cite{telatar1999capacity} and the ergodic capacity becomes
\begin{equation}
C = \max_{\mathbf{Q}: \, \mathrm{tr}( \mathbf{Q}  ) \leq \rho} {{\mathbb E}_{\mathbf H}} \bigg[{ \log_2 \det \left( \mathbf{I}_{N_r} + \mathbf{H} \mathbf{Q} \mathbf{H}^H \boldsymbol{\Phi}^{-1} \right) }\bigg].
\end{equation}
Finally, the optimality of the signal covariance matrix $\mathbf{Q} = \frac{\rho}{N_t} \mathbf{I}_{N_t}$ is a simple consequence of \cite[Corollary 1]{Emil2013imp}.
\end{IEEEproof}

This lemma shows that the ergodic capacity with transceiver hardware impairments has a similar structure as for the canonical model in \eqref{eq:canonical}. In the remainder of this paper we will, however, show that it behaves fundamentally different in many cases and regimes of practical relevance.

\subsection{Exact SNR Analysis}

We now derive a closed-form expression for the ergodic capacity in Lemma \ref{lemma_capacity_expression}. To this end, we first define the instantaneous MIMO channel correlation matrix as
\begin{equation} \label{eq:W-definition}
\mathbf W \triangleq \begin{cases}
\mathbf H\mathbf H^H, & \textrm{if $N_r\leq N_t$},\\
\mathbf H^H\mathbf H, & \textrm{if $N_r > N_t$},
\end{cases}
\end{equation}
since it will be often used in our manipulations. We begin our discussion with the following proposition.

\begin{proposition} \label{prop:ergodic-capacity}
For i.i.d. Rayleigh fading channels, the ergodic capacity in \eqref{eq:ergodiccapacity}, under the proposed residual impairment model, is

\begin{equation}
\begin{split}
C_{N_r\times N_t} &= \frac{q}{{\ln (2)}}{K}\sum\limits_{n = 1}^q {\sum\limits_{m = 1}^q {{{\left( { - 1} \right)}^{n + m}} \det \left( \boldsymbol\Omega  \right)} }  \Gamma \left( {t + 1} \right) \\
&\times\sum\limits_{k = 1}^{t + 1}{\left( {e^{\frac{1}{f}}}{ E}_{t+2-k}\left( \frac{1}{f}\right)  - {e^{\frac{1}{g}}} E_{t+2-k}\left( \frac{1}{g}\right) \right)}\label{eq:analcapacity}
\end{split}
\end{equation}
where we define $t \triangleq n+m+p-q-2$, $f \triangleq \frac{\rho\left(\delta_t^2 +1 \right)}{N_t\left(\rho\delta_r^2+1\right)}$ and $g \triangleq \frac{\rho\delta_t^2}{N_t(\rho\delta_r^2 + 1)}$, while ${K} = \left[ \prod_{i=1}^{q}(p-i)!\prod_{j=1}^{q}(q-j)!  \right]^{-1}$ is a normalization constant. Moreover, $\Gamma(z)$  denotes the Gamma function \cite[Eq.~(8.310.1)]{gradshteyn2007a} and $E_n(z) = \int_1^\infty t^{-n}e^{-zt}dt$  is the exponential integral function \cite[Eq.~(8.211.1)]{gradshteyn2007a}. Finally, $\boldsymbol\Omega$ is a $(q-1)\times(q-1)$ matrix whose $(i,j)$-th element is given by
\begin{equation}
\boldsymbol\Omega_{i,j}=\left(\alpha_{i,j}^{(n)(m)} + p - q\right)! \, q^{-\frac{1}{q-1}}\notag
\end{equation}
where
\begin{equation}
\alpha_{i,j}^{(n)(m)} \triangleq \begin{cases}
i+j-2, & \textrm{if $i<n$ and $j<m$}\\
i+j, & \textrm{if $i\ge n$ and $j \ge m$}\\
i+j-1, & \textrm{otherwise.}
\end{cases}
\end{equation}

\begin{IEEEproof}
Using the notation in \eqref{eq:W-definition}, the ergodic capacity in \eqref{eq:ergodiccapacity} can be expressed as
\begin{align}
\mathit{C}_{N_r\times N_t} = {{\mathbb E}_{\mathbf H}} \left[ {\log _2}\det \left( {\mathbf{I}_q + \frac{\rho}{N_t}\mathbf{W}{\boldsymbol\Phi^{-1}}} \right)\right]
\label{eq:detcapacity}
\end{align}
where $\boldsymbol{\Phi} = \left( \frac{\rho}{N_t} \delta_t^2 \mathbf{W} + (\delta_r^2 \rho+ 1) \mathbf{I}_{q} \right)$. Note that $\mathbf W$ is a $q\times q$ random, non-negative definite matrix following the complex Wishart distribution. Thus, it has real non-negative eigenvalues and the probability density function (PDF) of its unordered eigenvalue, $\lambda$, is found in \cite[Eq.~(38)]{zanella2009marginal} to be

\begin{equation}
p_\lambda(\lambda) = K\sum\limits_{n = 1}^{q}\sum\limits_{m = 1}^{q} \frac{(-1)^{m+n} \lambda^{n+m+p-q-2}}{ e^{\lambda}} \det \left({\boldsymbol\Omega}\right).
\end{equation}

By exploiting the eigenvalue properties, we can now alternatively express the capacity in (\ref{eq:detcapacity}) as
\begin{align}
&C_{N_r\times N_t} = {{\mathbb E}_{\mathbf H}}\left[ {\sum\limits_{i = 1}^q {{{\log }_2}\left( {1 + \frac{{\frac{{\rho}}{{N_t}}{\lambda _i}}}{{\frac{{\rho\delta_t^2}}{{{N_t}}}{\lambda _i} + \rho\delta_r^2 + 1}}} \right)} } \right] \label{C_alter}  \\&=q\int\limits_0^\infty  {{{\log }_2}\left( {1 + \frac{{\frac{\rho}{N_t}\lambda }}{{\frac{\rho\delta_t^2}{N_t}\lambda  + \rho
\delta_r^2+1}}} \right){p_\lambda }} \left( \lambda  \right)d\lambda \label{eq:CapIntegral}\\
&= q\left( \int\limits_0^\infty  {{{\log }_2}\left( {\left( {\frac{{\rho}}{N_t} + \frac{{\rho\delta_t^2}}{{{N_t}}}} \right)\lambda  + \rho\delta_r^2 + 1} \right) {p_\lambda }} \left( \lambda  \right)d\lambda \right)\notag\\ & \quad - q\left(\int\limits_0^\infty  {{{\log }_2}\left({\frac{{\rho\delta_t^2}}{{{N_t}}} \lambda  + \rho\delta_r^2 + 1} \right)} {p_\lambda }\left( \lambda  \right)d\lambda \right)\label{eq:int}
\end{align}
where $\lambda_i$ represents the $i$-th ordered eigenvalue of $\mathbf W$.

The integrals in (\ref{eq:int}) can be evaluated using the following integral identity \cite[Eq.~(40)]{kang2006rician}
\begin{align}
\int\limits_0^\infty\ln\left(1+ay\right)y^{n-1}e^{-cy}dy = \Gamma(n)e^{\frac{c}{a}}\sum\limits_{k = 1}^{n}\frac{\Gamma\left(-n+k, \frac{c}{a}\right)}{c^ka^{n-k}}

\end{align}
and the fact that $E_n(z) = z^{n-1}\Gamma(1-n,z)$, where $\Gamma(s,x)=\int_x^\infty t^{s-1}e^{-t}dt$ is the upper incomplete gamma function \cite[Eq.~(8.350.2)]{gradshteyn2007a}. The expression in \eqref{eq:analcapacity} then follows after some simple algebraic manipulations.
\end{IEEEproof}
\end{proposition}

Figure \ref{fig:Sim_Analytical} illustrates the ergodic capacity for different hardware conditions and antenna configurations. In all cases, the results demonstrate an excellent agreement between analytical results and Monte-Carlo simulations. Furthermore, for both $2\times2$ and $4\times4$ configurations, it is clear that hardware impairments will cause severe degradation on the ergodic capacity, compared with the ideal case studied by Telatar and Foschini \cite{telatar1999capacity,foschini1998a}. Observe that the capacity gap between the ideal system and the impaired system gets larger with the SNR. It is also noteworthy that for high SNR values, the ergodic capacity saturates and thus exhibits a finite capacity ceiling that cannot be crossed regardless of the SNR value. The reason for this effect is that the distortion noise power on both sides grows linearly and unboundedly with the transmit power. This confirms that hardware impairments fundamentally limit the performance of high-capacity systems, as quantified by the following corollary.
\begin{corollary} \label{cor:asymptotic-capacity}
Asymptotically as $\rho \rightarrow \infty$, the ergodic capacity in (\ref{eq:ergodiccapacity}) approaches the finite limit
\begin{equation}
\begin{split}
{C_\mathrm{limit} }\!& = \frac{q}{{\ln (2)}}{K}\sum\limits_{n = 1}^q {\sum\limits_{m = 1}^q {{{\left( { - 1} \right)}^{n + m}} \det \left( \boldsymbol\Omega  \right)} }  \Gamma \left( {t + 1} \right) \\
&\times\sum\limits_{k = 1}^{t + 1}{\left( {e^{\frac{1}{\hat{f}}}}{ E}_{t+2-k}\left( \frac{1}{\hat{f}}\right) - {e^{\frac{1}{\hat{g}}}} E_{t+2-k}\left( \frac{1}{\hat{g}}\right) \right)} \label{eq:CapLimit}
\end{split}
\end{equation}
where $\hat{f} \triangleq \frac{1+\delta_t^2}{N_t\delta_r^2}$ and $\hat{g} \triangleq \frac{\delta_t^2}{N_t\delta_r^2}$.
\vspace{0.1cm}
\begin{IEEEproof}
The asymptotic capacity is defined as
\begin{align}
{C_\mathrm{limit} }\!&= \!\mathop {\lim }\limits_{\rho \to \infty } \!{\mathbb E}_\mathbf{H}\!\left[ {\sum\limits_{i = 1}^q {{{\log }_2}\left( {1 + \frac{{\frac{{\rho}}{{N_t}}{\lambda _i}}}{{\frac{{\rho\delta_t^2}}{{{N_t}}}{\lambda_i} + \rho\delta_r^2 + 1}}} \right)} } \right]\label{eq:CapLimit1}\\
  &= q\int_0^\infty{{\log }_2}\left( {1 + \frac{\lambda}{{\delta_t^2\lambda+N_t\delta_r^2}}} \right)p(\lambda)d(\lambda). \label{eq:CapLimit2}
\end{align}
From (\ref{eq:CapLimit1}) to (\ref{eq:CapLimit2}) we have changed the order of expectation and limit, since according to Jensen's inequality,

the term inside the expectation is upper bounded by an integrable function, hence the dominated convergence theorem \cite{bartle1995integration} holds. The final expression \eqref{eq:CapLimit} is obtained as in Proposition \ref{prop:ergodic-capacity}.
\end{IEEEproof}
\end{corollary}

As expected, \eqref{eq:CapLimit} is a deterministic constant independent of the SNR. Observe that Corollary \ref{cor:asymptotic-capacity} extends the asymptotic results in \cite{studer2010residual,Emil2013imp} that only considered aggregate hardware impairments at the receiver.

\begin{figure}[ht]
\begin{centering}
\includegraphics [keepaspectratio,width=\columnwidth]{Sim_Ana.pdf}
\caption{Simulated and analytical ergodic MIMO capacity in i.i.d. Rayleigh fading channels with residual hardware impairments ($\delta_t = \delta_r = 0.15$) and without hardware impairments ($\delta_t = \delta_r = 0$).}\label{fig:Sim_Analytical}
\end{centering}
\end{figure}

\vspace{0.05cm}
\subsection{Low-SNR Analysis}
In the low-SNR regime, the capacity is well-approximated as \cite{lozano2003lowSNR}

\begin{align}
C \left(\frac{E_b}{N_0}\right) \approx S_0\log_2\left(\frac{\frac{E_b}{N_0}}{\frac{E_b}{N_0}_{\mathrm{min}}}\right)
\end{align}
where $\frac{E_b}{N_0}_\mathrm{min}$ and $S_0$ represent the \emph{minimum normalized energy per information bit required to convey any positive rate reliably} and the \emph{wideband slope}, respectively.

As shown in \cite{lozano2003lowSNR}, $S_0$ and $\frac{E_b}{N_0}_{\mathrm{min}}$ can be calculated from the first and second derivatives of $C(\rho)$ at $\rho = 0$ through
\begin{align}
\frac{E_b}{N_0}_{\mathrm{min}} \triangleq \mathop{\lim}\limits_{\rho \to 0} \frac{\rho}{C(\rho)} = \frac{1}{\dot{C}(0)}\label{eq:EbNo_def}
\end{align}
and
\begin{align}
S_0 \triangleq -\frac{2 \ln (2) \left[\dot{C}(0)\right]^2}{\ddot{C}(0)}\label{eq:So_def}.
\end{align}

\begin{proposition}
For i.i.d. Rayleigh fading channels, the minimum energy per information bit and the wideband slope, under the proposed residual impairment model, are respectively given by
\begin{align}
\frac{E_b}{N_0}_{\mathrm{min}} &= \frac{\ln (2) }{N_r} \label{eq:EbNo_result}

\\S_0 &= \frac{2N_tN_r}{(2\delta_t^2+1)(N_t+N_r)+2\delta_r^2N_t}\label{eq:So_result}.
\end{align}

\end{proposition}

\begin{IEEEproof}
Substituting (\ref{eq:CapIntegral}) into (\ref{eq:EbNo_def}) and taking the first derivative with respect to $\rho$, we get
\begin{align}
\dot{C}(0)&=q\int_0^\infty\!{\left[{{\log }_2}\left( \left.{1\!+\!\frac{{\frac{\rho}{N_t}\lambda }}{{\frac{\rho\delta_t^2}{N_t}\lambda\!+\!\rho\delta_r^2\!+\!1}}} \right)'\right|_{\rho=0}\right]{p_\lambda }} \left( \lambda  \right)d\lambda\notag\\
&=\frac{q}{N_t \ln(2)}\int_0^\infty\lambda p(\lambda) d\lambda\label{eq:C1st_1}\\
&=\frac{\mathbb E\left[ \mathrm{tr}\left(\mathbf W\right) \right]}{N_t \ln (2)} = \frac{N_r}{\ln (2)}\label{eq:C1st_2}
\end{align}
where from (\ref{eq:C1st_1}) to (\ref{eq:C1st_2}) we have used the fact that \cite[Lemma~
4]{lozano2003lowSNR}
\begin{equation}
q\int_0^\infty \lambda p(\lambda)d\lambda = q\mathbb E[\lambda] = \mathbb E\left[\mathrm{tr}\left(\mathbf W\right)\right] = N_rN_t.
\end{equation}
Similarly, we can find the second derivative as follows
\begin{align}
\ddot{C}(0) &=q\int_0^\infty\!{\left[{{\log }_2}\left( \left.{\!1\!+\!\frac{{\frac{\rho}{N_t}\lambda }}{{\frac{\rho\delta_t^2}{N_t}\lambda\! +\! \rho\delta_r^2\!+\!1}}} \right)''\right|_{\rho=0}\right]{p_\lambda }} \left( \lambda  \right)d\lambda\notag\\
&=-\frac{q(2\delta_t^2+1)}{\ln (2) N_t^2}\!\int_0^\infty\!\lambda^2p(\lambda)d\lambda \!-\! \frac{2q\delta_r^2}{\ln(2) N_t}\!\int_0^\infty\!\lambda p(\lambda)d\lambda \label{eq:C2nd_1}\!\\
&=-\frac{q(2\delta_t^2+1)}{\ln(2) N_t^2}\mathbb E\big[\mathrm{tr}\left(\mathbf W^2\right)\big] - \frac{2q\delta_r^2}{\ln(2) N_t}\mathbb E\big[\mathrm{tr}\left(\mathbf W\right)\big]\label{eq:C2nd_2}\\
&=-\frac{N_r}{\ln (2) }\left( \frac{(2\delta_t^2+1)(N_t+N_r)}{N_t} + 2\delta_r^2 \right)\label{eq:C2nd_3}
\end{align}
where from (\ref{eq:C2nd_1}) to (\ref{eq:C2nd_3}) we use the fact that \cite[Lemma~4]{lozano2003lowSNR}
\begin{equation}
q\int_0^\infty \lambda^2 p(\lambda)d\lambda\!= \!q\mathbb E[\lambda^2]\!= \!\mathbb E\left[\mathrm{tr}\left(\mathbf W^2\right)\right]\!=\! N_rN_t\left(N_r+N_t\right).
\end{equation}
Combining (\ref{eq:C1st_2}), (\ref{eq:C2nd_3}) with the definitions in (\ref{eq:EbNo_def}) and (\ref{eq:So_def}) we can obtain the results in (\ref{eq:EbNo_result}), (\ref{eq:So_result}).
\end{IEEEproof}

Figure~\ref{fig:LowSNR} depicts the ergodic capacity of a $4\times4$ MIMO system under different hardware conditions. Note that $\frac{E_b}{N_0}_\mathrm{min}$ is the intersection of the curves with the horizontal axis. We see in both cases that the analytical results (linear approximation) and the numerical results have very good agreement across a wide SNR range. Interestingly, for both ideal and impaired systems, $\frac{E_b}{N_0}_\mathrm{min}$ remains the same. The impact of transceiver impairments is seen only via the wideband slope $S_0$; observe that the slope of capacity curve decreases when impairments are considered. This implies that hardware impairments have only a second-order impact on the capacity in the low-SNR regime. From the expression in \eqref{eq:So_result}, we notice that the transmitter impairments have a more influential impact on $S_0$ than the receiver impairments, since $\delta_t^2$ is multiplied with a larger number. This reveals that transmitter impairments are more influential in the low-SNR regime.

\begin{figure}[t]
\begin{centering}
\includegraphics [keepaspectratio,width=\columnwidth]{LowSNR.pdf} \vskip-2mm
\caption{Simulated and analytical low-SNR ergodic capacity of a $4\times4$ MIMO system in i.i.d. Rayleigh fading channels with impairments ($\delta_t = \delta_r = 0.15$) and without impairments ($\delta_t = \delta_r = 0$).}\label{fig:LowSNR} \vskip-3mm
\end{centering}
\end{figure}
\vspace{-0.2cm}

\subsection{Large-Scale MIMO Analysis}

In this section, we analyze the asymptotic behavior of the ergodic capacity when the number of antennas is large. Specifically, our discussion includes three cases:
\begin{enumerate}[i)]
  \item large $N_t$ and fixed $N_r$;\label{case1}
  \item large $N_r$ and fixed $N_t$;
  \item large $N_t$ and $N_r$, with a fixed finite ratio $\beta = \frac{N_r}{N_t}>0$.
\end{enumerate}

For case i), recall that the $N_r \times N_r$ matrix $\frac{1}{N_t}\mathbf H\mathbf H^H$ converges almost surely to $\mathbf I_{N_r}$ almost surely as $N_t \rightarrow \infty$ \cite{bertrand2004hardening}, thus \eqref{eq:ergodiccapacity} becomes
\begin{equation}
C_{\infty, N_r} = N_r\log_2\left( 1 + \frac{\rho}{\rho\delta_t^2 + \rho\delta_r^2 + 1}  \right).\label{eq:Ntinf}
\end{equation}
This shows that having a large number of transmit antennas makes the capacity converge to a finite deterministic value, which is characterized by the level of transceiver impairments and the number of receive antennas. From (\ref{eq:Ntinf}), we notice that for fixed SNR values, the capacity increases linearly with the number of receive antennas; however, for fixed antenna setups, if we only increase SNR, the capacity behaves similar to the finite-dimensional MIMO case in Corollary \ref{cor:asymptotic-capacity}; that is, it saturates in the high-SNR regime. Figure \ref{fig:Nrfix} shows the behavior of the ergodic capacity as we increase the number of transmit antennas. When $N_t$ is small, the gap between the two systems is small; as $N_t$ increases the gap gets larger, and finally when $N_t$ is sufficiently large the gap converges to a constant which is determined by the SNR and the level of impairments. We can interpret this gap as a SNR penalty due to the transceiver hardware impairments. From Fig.~\ref{fig:Nrfix}, we can see that, for both the impaired system and the ideal system, the ergodic capacity converges to the finite ceiling given by \eqref{eq:Ntinf} as $N_t$ grows large.
\begin{figure}[t]
\begin{centering}
\includegraphics [keepaspectratio,width=\columnwidth]{Nrfix.pdf} \vskip-2mm
\caption{Ergodic MIMO capacity when the numbers of receive antennas is fixed and the number of transmit antennas increases ($N_r = 4, \rho = 10\mathrm{dB}$).}\label{fig:Nrfix}
\end{centering}
\end{figure}
\vspace{-0.3cm}

For case ii), analogously to the previous case, we use the property that $\frac{1}{N_t}\mathbf H^H\mathbf H = \frac{N_r}{N_t}\times\frac{1}{N_r} \mathbf H^H\mathbf H$ and the $N_t\times N_t$ matrix $\frac{1}{N_r}\mathbf H^H\mathbf H$ converges to $\mathbf I_{N_t}$ as $N_r \rightarrow \infty$ \cite{bertrand2004hardening}. Consequently, \eqref{eq:ergodiccapacity} becomes
\begin{align}
C_{N_t, \infty} &= \mathop {\lim }\limits_{N_r \to \infty } N_t\log_2\left( 1 +  \frac{\rho\frac{N_r}{N_t}}{\rho\delta_t^2\frac{N_r}{N_t}+\rho\delta_r^2+1} \right) \notag\\
&= N_t\log_2\left( 1+\frac{1}{\delta_t^2} \right).\label{eq:Nrinf}
\end{align}
Observe that this capacity ceiling is characterized only by the number of transmit antennas and the level of transmitter impairments, while the receiver impairments have no impact on the system performance, similar to \cite[Theorem 1]{Emil2013imp}, where receiver impairments were ignored all along.
The behavior in case ii) is quite different from case \ref{case1}), where both the transmitter and the receiver impairments affect the system performance. This result indicates a very important implication for system design: if a large-scale MIMO system adopts the antenna configuration with $N_r \gg N_t$, it is of pivotal importance to build high-quality transmitter hardware. Figure \ref{fig:Ntfix} compares the ergodic capacity of the impaired system and the ideal system as $N_r$ increases. We find that, for the impaired system, the ergodic capacity converges to the finite deterministic ceiling which is given in \eqref{eq:Nrinf}. However, for the ideal system, the capacity increases logarithmically with $N_r$ (this coincides with the result in \cite[Eq.~(6)]{bertrand2004hardening}). We conclude from this observation that, with the existence of residual transmitter hardware impairments, we cannot benefit from the array gain by increasing the number of receive antennas as in the ideal hardware case.

\begin{figure}[t]
\begin{centering}
\includegraphics [keepaspectratio,width=\columnwidth]{Ntfix.pdf}
\caption{Ergodic MIMO capacity when the number of transmit antennas is fixed and the number of receive antennas increases ($N_t = 4, \rho = 10\mathrm{dB}$).}\label{fig:Ntfix}
\end{centering}
\end{figure}

For case iii), we first note that the ergodic capacity in \eqref{eq:ergodiccapacity} can be expressed as the difference
\begin{equation}
\begin{split}
C &= {{\mathbb E}_{\mathbf H}} \left[ \log_2 \det \left( (\delta_r^2 \rho+ 1) \mathbf{I}_{N_r} + \frac{\rho(1+\delta_t^2)}{N_t} \mathbf{H} \mathbf{H}^H  \right) \right] \\ &- {{\mathbb E}_{\mathbf H}} \left[\log_2 \det \left( (\delta_r^2 \rho+ 1) \mathbf{I}_{N_r} + \frac{\rho \delta_t^2}{N_t} \mathbf{H} \mathbf{H}^H  \right) \right]
\end{split}
\end{equation}
where each term represents a classical ergodic capacity expression. The asymptotic behavior as $N_t$ and $N_r$ grow large
with a finite ratio $\beta = \frac{N_r}{N_t}>0$ can therefore be obtained by analyzing each term separately. More precisely, we apply
an asymptotically tight approximation from \cite[Chapter 13.2.2]{Couillet2011a}, which shows that
\vspace{0.15cm}
\begin{equation} \label{eq:deterministic_equivalent}
\begin{split}
C &- N_r \Bigg[ \!
\log_2 \! \!  \left( \!\frac{1+\rho \delta_r^2 + \frac{\rho(1+\delta_t^2)}{1+\beta \rho_1}
}{1+\rho \delta_r^2 + \frac{\rho\delta_t^2}{1+\beta \rho_2}} \! \right) \!\! +\! \beta^{-1} \log_2 \! \left( \frac{1 + \beta \rho_1}
{1 + \beta \rho_2} \right) \\ & + \log_2(e) \left( \frac{\rho_1 (1+\rho \delta_r^2) }{\rho(1+\delta_t^2)} - \frac{\rho_2 (1+\rho \delta_r^2) }{\rho\delta_t^2} \right)
 \Bigg] = \mathcal{O} \left(\frac{1}{N_t} \right)
 \end{split}
\end{equation}
\vspace{0.15cm}
where $C$ is the true ergodic capacity, $L \triangleq 1 - \beta^{-1}$, and
\begin{align}
\rho_1 & \triangleq \frac{1}{2} \Bigg( \frac{\rho(1+\delta_t^2) L}{1+\rho \delta_r^2} - \beta^{-1} \notag\\ & + \sqrt{ \Big( \frac{\rho(1+\delta_t^2) L}{1+\rho \delta_r^2} - \beta^{-1} \Big)^2 + \frac{4  \rho (1+\delta_t^2)}{ \beta (1+\rho \delta_r^2)}  } \Bigg)  \\
\rho_2 & \triangleq \frac{1}{2} \Bigg( \frac{\rho\delta_t^2 L}{1+\rho\delta_r^2} - \beta^{-1} \notag\\ & + \sqrt{ \Big(\frac{\rho\delta_t^2 L}{1+\rho \delta_r^2} - \beta^{-1} \Big)^2 + \frac{4 \rho \delta_t^2}{\beta (1+\rho \delta_r^2)}  } \Bigg).
\end{align}
Since the difference between the true and approximate ergodic capacity in \eqref{eq:deterministic_equivalent} behaves as $\mathcal{O}\left(\frac{1}{N_t}\right)$, the approximation error vanishes asymptotically. Observe that the expression inside the square brackets in \eqref{eq:deterministic_equivalent} is strictly positive and only depends on the fixed ratio $\beta=\frac{N_r}{N_t}$ and not on the individual values on $N_t$ and $N_r$. When the number of antennas is scaled with the fixed ratio $\beta$, then the approximated ergodic capacity in \eqref{eq:deterministic_equivalent} grows linearly with $N_r$ and without bound. This is the same scaling behavior as with ideal hardware, which means that transceiver impairments will only inflict a small/bounded offset in the ergodic capacity in this case. It is important to note that since the SNR is fixed, the effective SNR per element in $\mathbf{s}$ will reduce as $\frac{\rho}{N_t}$, but this reduction is counteracted by the large array gain achieved at the receiver when $N_r$ also grows large. Another important explanation for this phenomenon is that by deploying a large number of antennas on both sides, we can create several spatially parallel subchannels. The total transmit power is then allocated to these subchannels such that each subchannel only has a small portion of the total transmit power, which makes the effective SNR on each stream very low. As we observed in the low-SNR analysis, transceiver impairments do not have significant impact on the capacity for low SNR values. Consequently, the ``capacity ceiling'' disappears. Figure \ref{fig:Large_Nr_Nt} illustrates the ergodic capacity of this scenario for three different values of $\beta$. Apart from the previous observations, this figure also demonstrates that for different $\beta$, the relative capacity gaps, $\frac{C_\mathrm{imp} - C_\mathrm{ideal}}{C_\mathrm{ideal}}$, between the impaired systems and the ideal systems, are nearly the same. This indicates that residual transceiver impairments has a  relative smaller impact on large-dimensional MIMO systems.

\begin{figure}[ht]
\begin{centering}
\includegraphics [keepaspectratio,width=\columnwidth]{Large_Nr_Nt.pdf}
\caption{Ergodic MIMO capacity when the number of transmit and receive antennas both increase with a fixed ratio ($\beta=\frac{N_r}{N_t}, \rho = 10\mathrm{dB}$). }\label{fig:Large_Nr_Nt}
\end{centering}
\end{figure}

\vspace{-0.2cm}
\section{Conclusions}
Residual RF hardware impairments can have a dramatic impact on the capacity of MIMO communication systems, especially on those operating at high SNRs (i.e., high-rate systems). In this paper, we analytically derived an ergodic capacity expression for a MIMO system with residual transceiver impairments, which applies for any finite number of antennas and the entire SNR range. This expression can be very easily evaluated, since it only contains elementary functions. Additionally, we presented analytical capacity expressions in the high-SNR and low-SNR regimes. Finally, we presented results on the ergodic capacity for large-scale MIMO systems with residual transceiver impairments. While the ergodic capacity generally has a finite ceiling due to the transceiver impairments, we found that by increasing both the number of transmit and receive antennas, the ceiling vanishes and the capacity can increase unboundedly at any SNR. As such, large-scale MIMO is one viable solution for mitigating the detrimental impact of residual impairments---at least, if the increasing overhead signaling can be handled properly.

\section*{ACKNOWLEDGMENTS}
We wish to thank Dr.~G.~Durisi for fruitful discussions. The work of X.~Zhang, M.~Matthaiou and M. Coldrey has been supported in part by the Swedish Governmental Agency for Innovation Systems (VINNOVA) within the VINN Excellence Center Chase, and by the Swedish Foundation for Strategic Research. The work of E.~Bj{\"o}rnson was supported by International Postdoc Grant 2012-228 from the Swedish Research Council. This research has been supported by the ERC Starting Grant 305123 MORE (Advanced Mathematical Tools for Complex Network Engineering).

\bibliographystyle{IEEEtran}
\bibliography{IEEEabrv,Reference}

\end{document}


TITLE: whether a integer set can be divided into equal sum subsets
QUESTION [0 upvotes]: Is there a way to check whether a set containing 1 to n integers can be partitioned in 2 equal sum subsets in minimum time complexity.

REPLY [3 votes]: Yes, it is possible if and only if $n\equiv 0,3\pmod 4$.
Because $1+2+\cdots+n=\frac{n(n+1)}{2}$, for this to be further divisible by $2$ we must have either $n$ or $n+1$ divisible by $4$, which means $n\equiv 0,3\pmod 4$.
Conversely, assume $n\equiv 0,3\pmod 4$. It is obvious that four consecutive numbers can be split into pairs giving the same sum. ($\{k,k+1,k+2,k+3\}$ can be split into $\{k+1,k+2\}$ and $\{k,k+3\}$, both giving sum $2k+3$.) Now, start taking groups of $4$ numbers off the end of the sequence $1,2,\ldots,n$ (last $4$ numbers, then the $4$ numbers before that, then the $4$ numbers before that etc.). Split those as shown above. What you end up at the end is:

$n\equiv 0\pmod 4$: nothing. We've thus split the whole set into two sets with equal sums.
$n\equiv 3\pmod 4$: remaining are $\{1,2,3\}$, which can be split into $\{1,2\}$ and $\{3\}$.

Examples for those two cases:

$n=8$: $8+5+4+1=7+6+3+2$
$n=11$: $11+8+7+4+3=10+9+6+5+2+1$


text:
\subsection{Pressurized hollow sphere}
\begin{figure}[htb!]
\begin{center}
\begin{picture}(160,180)
\put(0,0){\includegraphics[width=0.55\textwidth]{figures/biMat_3D/mesh.png}}
\put(36.67,82.19){\circle*{2}}
\put(36.67,77){\text{A}}
\put(132.92,71.6){\circle*{2}}
\put(123.14,71.6){\text{B}}
\end{picture}
\caption{Bimaterial geometry with the front  quarter removed for visualization.}
\label{fig:geo_3d}
\end{center}
\end{figure}
The final example extends the previous setup to the three-dimensional case. We consider a   pressurized hollow sphere with two $45^\circ$ holes as shown in Figure~\ref{fig:geo_3d}. Again, there is a thin inclusion of a stiff material with an elliptic cross-section. More precisely, the equatorial plane resembles the two-dimensional geometry from Section \ref{sec:numerics:annulus}.   We choose the same material parameters as before, but consider a non-linear Neo-Hooke material:
\[
 \sef(\rcg) = c\, (\mathrm{tr}\rcg -3) + \frac{c}{\beta}\big((\det\rcg)^{-\beta}-1\big),
\]
with $c={E}/(1+4\nu)$ and $\beta={\nu}/(1-2\nu)$.

The final deformation for quadratic NURBS on $68\,624$ elements for the whole domain, with $104\,016$ control points is shown in Figure~\ref{fig:3d_result_stress}, which includes the circumferential Cauchy stress. As expected, the thin stiff inclusion carries most of the pressure.
The biorthogonal basis guarantees an accurate and smooth transmission of the forces, and no oscillations across the interface can be seen at all.

\begin{figure}[htb!]
\begin{minipage}{.48\textwidth}
\scalebox{0.53}{
\input{figures/biMat_3D/displacement_plot.tex}
}
\caption{Radial displacement  in relation to the internal pressure. }
\label{fig:3d_load_displacement}
\end{minipage}\hfill
\begin{minipage}{.48\textwidth}
\scalebox{0.53}{
\input{figures/biMat_3D/displacement_abs_error.tex}
}
\caption{Estimated error of the displacements by comparison of $\bar{h}=1$ to $\bar{h}=0.25$.}
\label{fig:3d_absolut_difference}
\end{minipage}
\end{figure}

We observe the radial displacements at two points $A$ and $B$ as shown in Figure~\ref{fig:geo_3d} during the increase of the internal pressure, see Figure~\ref{fig:3d_load_displacement}.
The discretization error is estimated qualitatively by comparing to the values obtained on a coarser mesh, see Figure~\ref{fig:3d_absolut_difference}. We see a good agreement, since the computed displacements differ by a value of less then $0.02$. For pressure values lower than $150$, the difference is even less then 2e-4.

 \begin{figure}
 \centering
 \includegraphics[width=\textwidth]{figures/biMat_3D/stress_circ_final.png}
\caption{Deformed geometry with the circumferential Cauchy stress indicated.}
\label{fig:3d_result_stress}
\end{figure}

config: arxiv


TITLE: What is the difference between radial velocity, angular velocity and instantaneous velocity?
QUESTION [0 upvotes]: A particle is moving in a plane with constant radial velocity 12 m/s and constant angular velocity 2 rad/s. When a particle is at a distance r=8 m from origin what is the magnitude of instantaneous velocity?

I am familiar with angular velocity(ω). But what is meant by radial velocity? Is it the velocity of a body along the radius vector or that along the tangent drawn to the path traversed by the object which is usually perpendicular to radius vector? How can these three terms be related?

REPLY [2 votes]: The line element in polar coordinates is $\vec{ds}=dr\hat{r}+rd\theta\hat{\theta}$.
Divide by dt, you get $\frac{\vec{ds}}{dt}=\frac{dr}{dt}\hat{r}+r\frac{d\theta}{dt}\hat{\theta}$
We are given that $\frac{dr}{dt}=12m/s$ and $\frac{d\theta}{dt}=2$rad/s. We multiply by 8 m to get $r\frac{d\theta}{dt}=16$m/s.
The instantaneous velocity is the vector sum of the two. The magnitude of the instantaneous velocity is the square root of the  sum of the square of the components, 20 m/s.


text:
\begin{document}
\title{An algebraic approach to information theory}
\author{\IEEEauthorblockN{Manas K. Patra and Samuel L. Braunstein\\}
\IEEEauthorblockA{Department of Computer Science, University of York, York YO10 5DD, UK}
}
\date{}
\maketitle
\begin{abstract}
This work proposes an algebraic model for classical information theory. We first give an algebraic model of probability theory. Information theoretic constructs are based on this model. In addition to theoretical insights provided by our model one obtains new computational and analytical tools. Several important theorems of classical probability and information theory are presented in the algebraic framework.
\end{abstract}

\section{Introduction}
The present paper reports a brief synopsis of our work on an algebraic model of {\em classical} information theory based on operator algebras. Let us recall a simple model of a communication system proposed by Shanon \cite{Shannon48}. This model has essentially four components: source, channel, encoder/decoder and receiver. Some amount of noise affects every stage of the operation and the behavior of components are generally modeled as stochastic processes. In this work our primary focus will be on discrete processes. A discrete source can be viewed as a generator of a countable set of random variables. In a communication process the source generates sequence of random variables. Then it is sent through the channel (with encoding/decoding) and the output at the receiver is another sequence of random variables. Thus, the concrete objects or  {\em observables}, to use the language of quantum theory, are modeled as random variables. The underlying probability space is primarily used to define probability distributions or {\em states} associated with the relevant random variables. In the algebraic approach we directly model the observables. Since random variables can be added and multiplied \footnote{We assume that they are real or complex valued.}they constitute an {\em algebra}. This is our starting point. In fact, the algebra of random variables have a richer structure called a $\cstar$ algebra. Starting with a $\cstar$ algebra of observables we can define most important concepts in probability theory in general and information theory in particular. A natural question is: why should we adopt this algebraic approach? We discuss the reasons below.

First, it seems more appropriate to deal with the ``concrete'' quantities, {\em viz}.\ observables and their intrinsic structure. The choice of underlying probability space is somewhat arbitrary as a comparison of standard textbooks on information theory \cite{CoverT,Ciszar} reveals. Moreover, from the algebra of observables we can recover particular probability spaces from representations of the algebra. Second, some constraints, may have to be imposed on the set of random variables. In security protocols  different participants have access to different sets of observables and may assign different probability structures. In this case, the algebraic approach seems more natural: we have to study different subalgebras. Third, the algebraic approach gives us new theoretical insights and computational tools. This will be justified in the following sections. Finally, and this was our original motivation, the algebraic approach provides the basic framework for a unified approach to classical {\em and} quantum information. All quantum protocols have some classical components, e.g.\ classical communication, ``coin-tosses'' etc. But the language of the two processes, classical and quantum, seem quite different. In the former we are dealing with random variables defined on one or more probability spaces where as in the latter we are processing quantum states which also give complete information about the measurement statistics of {\em quantum} observables. The algebraic framework is eminently suitable for bringing together these somewhat disparate viewpoints. Classical observables are simply elements that commute with every element in the algebra.

The connection between operator algebras and information theory---classical {\em and} quantum---have appeared in the scientific literature since the beginnings of information theory and operator algebras---both classical and quantum (see e.g.\ \cite{Umegaki4, Segal60,araki75,Keyl,Beny,Kretschmann}). Most previous work focus on some aspects of information theory like the noncommutative generalizations of the concepts of entropy. There does not appear to be a unified and coherent approach based on intrinsically algebraic notions. The construction of such a model is one of the goals of the paper. As probabilistic concepts play such an important role in the development of information theory we first present an algebraic approach to probability. I. E. Segal \cite{Segal54} first proposed such an algebraic approach model of  probability theory. Later Voiculescu \cite{Voic} developed noncommutative or ``free probability'' theory. We believe several aspects of our approach are novel and yield deeper insights to information processes. In this summary, we have omitted most proofs or give only brief outlines. The full proofs can be found in our \href{http://arxiv.org/abs/0910.1536}{arXiv submission} \cite{Patra09}. A brief outline of the paper follows.

In Section \ref{sec:algebra} we give the basic definitions of the $\cstar$ algebras.  This is followed by an account of probabilistic concepts from an algebraic perspective. In particular, we investigate the fundamental notion of independence and demonstrate how it relates to the algebraic structure. One important aspect in which our approach seems novel is the treatment of  probability distribution functions.  In Section \ref{sec:info} we give a precise algebraic model of information/communication system. The fundamental concept of entropy is introduced. We also define and study the crucial notion of a channel as a (completely) positive map. In particular, the {\em channel coding theorem} is presented as an approximation result. Stated informally: {\em Every channel other than the useless ones can be approximated by a lossless channel under appropriate coding}. We conclude the paper with some comments and discussions.

\section{$C^*$ Algebras and Probability} \label{sec:algebra}
A Banach algebra $A$ is a complete normed algebra \cite{Rudin,KR1}. That is, $A$ is an algebra over real ($\real$) or complex numbers ($\comp$), for every $x\in A$ the norm $\norm{x}\geq 0$ is defined satisfying the usual properties and every Cauchy sequence converges in the norm.
A $\cstar$ algebra $B$ is a Banach algebra\cite{KR1} with
an anti-linear involution $^*$ ($x^{**}=x$ and $(x+cy)^*=x^*+\conj{c}y^*$, $x,y\in B$ and $c\in\comp$) such that
\(\norm{xx^*}=\norm{x}^2\text{ and } (xy)^*=y^*x^*\forall x,y \in B\).
This implies that $\norm{x}=\norm{x^*}$. We often assume that the unit $I\in B$.
The fundamental Gelfand-Naimark-Segal ({\bf GNS}) theorem states that
every $\cstar$ algebra can be isometrically embedded in some $\cali{L}(H)$, the set of bounded operators on a Hilbert space of $H$. The spectrum of an element $x\in B$ is defined by $\Sp(x)=\{c\in \comp: x-cI \text{ invertible }\}$. The spectrum is a nonempty closed and bounded set and hence compact.
An element $x$ is self-adjoint if $x=x^*$, normal if $x^*x=xx^*$ and positive (strictly positive) if $x$ is self-adjoint and $\Sp(x)\subset [0,\infty)((0,\infty))$. A self-adjoint
element has a real spectrum and conversely. Since $x=x_1+ix_2$ with $x_1=(x+x^*)/2$ and $x_1=(x+x^*)/2i$ any element of a $\cstar$ algebra can be decomposed into self-adjoint ``real'' and ``imaginary'' parts.
The positive elements define a partial order on $A$:
$x\leq y$ iff $y-x\geq 0$ (positive). A positive element $a$ has a unique square-root $\sqrt{a}$ such that $\sqrt{a}\geq 0\text{ and } (\sqrt{a})^2=a$. If $x$ is self-adjoint, $x^2\geq 0$ and $|x|=\sqrt{x^2}$.  A self-adjoint element $x$ has a decomposition $x=x_+-x_-$ into positive and negative parts where \(x_+=(|x|+x)/2\ \text{ and } x_-=(|x|-x)/2)\) are positive. An element $p\in B$ is a projection
if $p$ is self-adjoint and $p^2=p$. Given two $\cstar$-algebras $A$ and $B$ a homomorphism $F$ is a linear map preserving the product and $^*$ structures.

A homomorphism is positive if it maps positive elements to positive elements. A (linear) functional on $A$ is a linear map $A\rightarrow \comp$. A positive functional $\omega$ such that $\omega(\unit)=1$ is called a {\em state}. The set of states $G$ is convex. The extreme points
are called {\em pure states} and $G$ is the convex closure of pure states (Krein-Millman theorem). A set $B\subset A$ is called a subalgebra if it is a
$\cstar$ algebra with the inherited product. A subalgebra is called unital if it contains the identity of $A$.
Our primary interest will be on {\em abelian} or commutative algebras.
The basic representation theorem (Gelfand-Naimark) \cite{KR1} states that: {\em An abelian $\cstar$ algebra with unity is isomorphic to the algebra $C(X)$ continuous complex-valued functions on a compact Hausdorff space $X$}.

Now let $X=\{a_1, \dotsc, a_n\}$  be a finite set with discreet topology. Then $A=C(X)$ is the set of all functions $X\rightarrow \comp$. The algebra $C(X)$ can be considered as the algebra of (complex) random variables on the finite probability space $X$. Let $x_i(a_j)=\delta_{ij},\; i,j=1,\dotsc, n$. Here $\delta_{ij}=1 \text{ if }i=j \text{ and } 0$ otherwise. The functions $x_i\in A$ form a basis for $A$. Their multiplication table is particularly simple: $x_ix_j=\delta_{ij}x_i$. They also satisfy $\sum_i x_i=\unit$. These are projections in $A$. They are orthogonal in the sense that $x_ix_j=0\text{ for }i\neq j$. We call any basis consisting of elements of norm 1 with distinct elements orthogonal {\em atomic}. A set of linearly independent elements $\{y_i\}$ satisfying $\sum_i y_i=\unit$ is said to be complete. The next theorem gives us the general structure of any finite-dimensional algebra.
\begin{thm}\label{thm:structFinite}
Let $A$ be a finite-dimensional abelian $\cstar$ algebra. Then there is a unique (up to permutations) complete atomic basis $\cali{B}=\{x_1, \dotsc, x_n\}$. That is, the basis elements satisfy
\beq \label{eq:structFinite}
x_i^*=x_i,\; x_ix_j=\delta_{ij}x_i,\;  \norm{x_i}=1 \text{ and }\sum_i x_i =\unit,\;
\eeq
Let $x=\sum_i a_ix_i\in A$. Then $\Sp(x)=\{a_i\}$ and hence $\norm{x}=\max_i\{|a_i|\}$.
\end{thm}
We next describe an important construction for $\cstar$ algebras. Given two $\cstar$ algebras $A$ and $B$, the tensor product $A\tensor B$ is defined as follows. As a set it consists of all finite linear combinations of symbols of the form $\{x\tensor y:x\in A,y\in B\}$ subject to the conditions that the map $(x,y)\rightarrow x\tensor y$ is bilinear in each variable. Hence, if $\{x_i\} \text{ and } \{y_j\}$ are bases for $A$ and $B$  respectively then $\{x_i\tensor y_j\}$ is a basis for $A\tensor B$. The linear space $A\tensor B$ becomes an algebra by defining
$(x\tensor y)(u\tensor z)=xu\tensor yz$ and extending by bilinearity.
The $*$ is defined by $(x\tensor y)^*=x^*\tensor y^*$ and extending {\em anti-linearly}. We will define the norm in a more general setting. Our basic model will be an {\em infinite} tensor product of finite dimensional $\cstar$ algebras which we present next.

\newcommand{\inftens}[1]{\bigotimes^{\infty}{#1}}
Let $A_k,\;k=1,2,\dotsc,$ be finite dimensional abelian $\cstar$ algebras with atomic basis $B_k=\{x_{k1},\dotsc,x_{kn_k}\}$. Let $B^{\infty}$ be the set consisting of all infinite strings of the form \(z_{i_1}\tensor z_{i_2}\tensor \cdots\) where all but a finite number ($>0$) of $z_{i_k}$s are equal to $\unit$ and if some $z_{i_k}\neq \unit$ then $z_{i_k}\in B_k$.
\commentout{
Explicitly, $B^{\infty}$ consists of strings of the form $z_{i_1}\tensor z_{i_2}\tensor \cdots \tensor z_{i_k}\tensor\unit\tensor\unit\tensor\cdots,\;k=1,2,\dotsc $ and $z_i\in B$.} Let $\tilde{\mathfrak{A}}=\tensor_{i=1}^{\infty}{A}_i $ be the vector space with basis $B^{\infty}$ such that $z_{i_1}\tensor z_{i_2}\tensor \cdots \tensor z_{i_k}\tensor\cdots $ is linear in each factor separately.

\commentout{
\[
\begin{split}
&z_{1_1}\tensor\cdots \tensor (az_{i_k}+bz'_{i_k})\tensor z_{i_{k+1}}\tensor \cdots= \\
&a(z_{1_1}\tensor \cdots \tensor z_{i_k}\tensor z_{i_{k+1}}\tensor \cdots)+
b(z_{1_1}\tensor \cdots \tensor z'_{i_k}\tensor z_{i_{k+1}}\tensor \cdots).\\
\end{split}
\]

Clearly every $\alpha \in \tilde{\mathfrak{A}} $ is a finite linear combination of elements in $B^{\infty}$. }
We define a product in $\tilde{\mathfrak{A}}$ as follows. First, for elements of $B^{\infty}$:
\((z_{i_1}\tensor z_{i_2}\tensor\cdots )(z'_{i_1}\tensor z'_{i_2}\tensor\cdots )=(z_{i_1}z'_{i_1}\tensor z_{i_2}z'_{i_2}\tensor\cdots )\)
We extend the product to whole of $\tilde{\mathfrak{A}}$ by linearity. Next define a norm  by:
\(\norm{\sum_{i_1,i_2,\dotsc}a_{i_1i_2\cdots}z_{i_1}\tensor z_{i_2}\tensor \cdots }=\sup\{|a_{i_1i_2\cdots}|\}\).  $B^{\infty}$ is an atomic basis. It follows that $\tilde{\mathfrak{A}}$ is an abelian normed algebra. We define $*$-operation by
\(\left(\sum_{i_1,i_2,\dotsc}a_{i_1i_2\cdots}z_{i_1}\tensor z_{i_2}\tensor \cdots \right)^*=\sum_{i_1,i_2,\dotsc}\conj{a_{i_1i_2\cdots}}z_{i_1}\tensor z_{i_2}\tensor \cdots \)
It follows that for $x\in \tilde{\mathfrak{A}}$, $\norm{xx^*}=\norm{x}^2$. Finally, we complete the norm \cite{KR1} and call the resulting $\cstar$ algebra $\mathfrak{A}$. With these definitions  $\mathfrak{A}$ is a $\cstar$ algebra. We call a $\cstar$ algebra $B$ of {\bf finite type} if it is either finite dimensional or infinite tensor product of finite-dimensional algebras. An important special case is when all the factor algebras $A_i=A$. We then write the infinite tensor product $\cstar$ algebra as $\inftens{A}$. Intuitively, the elements of an atomic basis $B^{\infty}$ of $\inftens{A}$ correspond to strings from an alphabet (represented by the basis $B$). Of particular interest is the 2-dimensional algebra $D$ corresponding to a binary alphabet.
\commentout{
It can be shown that there are injective algebra maps---\(\cali{J}: \inftens{G}\rightarrow \inftens{A} \text{ and } \cali{J}': \inftens{A} \rightarrow \inftens{G}\). This is relevant for coding theory. }

The next step is to describe the state space. Given a $\cstar$ subalgebra $V\subset A$ the set of states of $V$ will be denoted by $\mathscr{S}(V)$. Let $\mathfrak{A}=\tensor^{\infty}_{i=1} A_i$ denote the infinite tensor product of finite-dimensional algebras $A_i$. An infinite product state of $\mathfrak{A}$ is a functional of the form
\( \Omega=\omega_1\tensor \omega_2\tensor\cdots \text{ such that }\omega_i\in \mathscr{S}(A_i)\)
This is indeed a state of $\mathfrak{A}$ for if $\alpha_k = z_1\tensor z_2 \tensor \cdots \tensor z_k\tensor\unit\tensor\unit\cdots\in \mathfrak{A}$ then
\(\Omega(\alpha)=\omega_1(z_1)\omega_2(z_2)\cdots \omega_k(z_k), \)
a {\em finite} product.
\commentout{
Since an arbitrary element of $\mathfrak{A}$ is the limit of sequence of finite sums of elements of the form $\alpha_k,\; k=1,2,\dotsc $ $\Omega$ is bounded by the principle of uniform boundedness. Clearly, it is positive.}
A general state on $\mathfrak{A}$ is a convex combination of product states like $\Omega$.
Finally, we discuss another useful construction in a $\cstar$ algebra $A$. If $f(z)$ is an analytic function whose Taylor series $\sum_{n=0}^{\infty}a_n (z-c)^n$  converges in a region $|z-c|<R$. Then the series $\sum _{n=0}^{\infty}(x-c\unit)^n$ converges and it makes sense to talk of analytic functions on a $\cstar$ algebra. If we have an atomic basis $\{x_1,x_2,\dotsc \}$ in an abelian $\cstar$ algebra then the functions are particularly simple in this basis. Thus if $x=\sum_i a_ix_i$ then $f(x)=\sum_i f(a_i)x_i$ provided that $f(a_i)$ are defined in an appropriate domain.

We gave a brief description of $\cstar$ algebras. We now
 introduce an algebraic model of probability which is used later to model communication processes.
In this model we treat random variables as elements of a $\cstar$ algebra. The probabilities are introduced via states.
\commentout{
We emphasize again that random variables often  represent quantities that are actually measured or observed- the voltage across a resistor, the currents in an antenna, the position of a Brownian particle and so on. The probability distribution corresponds to the {\em state} of the devices that produce these outputs. We will take the alternative view and start with these observables as our basic objects.}

\newcommand{\scrp}[1]{{\mathscr #1}}
\newcommand{\intd}{\mathrm{d}}
A classical observable algebra is a complex abelian $\cstar$ algebra $A$. We can restrict our attention to real algebras whenever necessary. The Riesz representation theorem \cite{Rudin} makes it possible identify $\omega$ with some {\em probability measure}.

A {\em probability algebra} is a pair $(A, S)$ where $A$ is an observable algebra and $S\subset \scrp{S}(A)$ is a set of states. A probability algebra is defined to be {\em fixed} if $S$ contains only one state.

\noindent

Let $\omega$ be a state on an abelian $\cstar$ algebra $A$. Call two elements $x,y\in A$ {\em uncorrelated in the state} $\omega$ if $\omega(xy)=\omega(x)\omega(y)$. This definition depends on the state: two uncorrelated elements can be correlated in some other state $\omega'$. A state $\omega$ is called multiplicative if $\omega(xy)=\omega(x)\omega(y)$ for all $x,y\in A$.  The set of states, $\mathscr{S}$, is convex. The extreme points of $\mathscr{S}$ are called {\em pure} states. In the case of abelian $\cstar$ algebras a state is pure if and only of it is multiplicative \cite{KR1}. Thus, in a pure state any two observables are uncorrelated. This is not generally true in the non-abelian quantum case. Now  we can introduce the important notion of {\em independence}. Given $S\subset A$ let $A(S)$ denote the subalgebra generated by $S$ (the smallest subalgebra of $A$ containing $S$). Two subsets $S_1,S_2\subset A$ are defined to be {\em independent} if all the pairs $\{(x_1,x_2): x_1\in A(S_1), x_2\in A(S_2)\}$ are uncorrelated. As independence and correlation depend on the state we sometimes write $\omega$-independent/uncorrelated. Independence is a much stronger condition than being uncorrelated.

\commentout{
However, in 2 dimensions $x\text{ and }x'$ are uncorrelated if and only if one of them is 0 or $c\unit$. Let us note that as in the quantum case two dimensions is an exceptional case.}
 The next theorem states the structural implications of independence.
\begin{thm} \label{thm:structIndep}
Two sets of observables $S_1,S_2$ in a finite dimensional abelian $\cstar$ algebra $A$ are independent in a state $\omega$ if and only if for the subalgebras $A(S_1)$ and $A(S_2)$ generated by $S_1$ and $S_2$ respectively there exist states $\omega_1 \in \scrp{S}(A(S_1)),\; \omega_2\in \scrp{S}(A(S_2))$ such that $(A(S_1)\tensor A(S_2),\{\omega_1\tensor\omega_2\})$ is a cover of $(A(S_1S_2),\omega')$ where $A(S_1S_2)$ is the subalgebra generated by $\{S_1,S_2\}$ and $\omega'$ is the restriction of $\omega$ to $A(S_1S_2)$.
\end{thm}

\commentout{
The next step is to extend the notion of independence to more than two subsets. Let $S_1,\dotsc,S_k\subset A$ and $\omega$ a state of $A$. Then the subsets are defined to be $\omega$-independent if for all $x_i\in A(S_i),\; i=1,\dotsc, k$ we have
\[ \omega(x_1\cdots x_k)=\omega(x_1)\cdots \omega(x_k)\]
Here $A(S_i)$ is the subalgebra generated by $S_i$. We can then show that for states $\omega_i\in \scrp(A(S_i))$, the restriction of $\omega$ to $A(S_i)$ the pair
\((A(S_1)\tensor\cdots \tensor A(S_k), \omega_1\tensor\cdots\tensor \omega_k)\) is a cover of $A(S_1\dotsc S_k),\omega'$, where $\omega'$ is the restriction of $\omega$ to $A(S_1\dotsc S_k)$, the algebra generated by $S_1,\dotsc, S_k$.}
We thus see the relation between independence and (tensor) product states in the classical theory. Next we show how one can formulate another important concept, {\em distribution function} ({\bf d.f}) in the algebraic framework. We restrict our analysis to $\cstar$ algebras of finite type. The general case is more delicate and is defined using approximate identities in subalgebras in \cite{Patra09}. The idea is that we approximate indicator functions of sets by a sequence of elements in the algebra. In the case of finite type algebras the sequence converges to a projection operator $J_S$.
\commentout{
\noindent
{\bf Definition.} Let $S=\{x_1,x_2,\dotsc, x_n\}$ be a finite self-adjoint subset of $A$ where $(A,\omega)$ is a fixed probability algebra of finite type. For ${\tt t}=(t_1,t_2,\dotsc, t_n )\in \real$ let $S_{\tt t}\subset A$ denote the set of elements  $\{(t_i\unit - x_i):i=1,\dots, n\}$. Let $J_S$ be the identity in the (annihilator) subalgebra  $(S_{\tt t})_a\equiv \{ x\in A : xs=0\forall s\in S_{\tt t}\}$. Then the $\omega$-distribution of $S$ is defined to be the real function \( f_S({\tt t})= \omega(J_S) \). Using the d.f we can define the cumulative distribution function $F_S({\tt t})= \sum _{q_i} f_S({\tt t}: q_i\leq t_i)$. The sum is well defined since $f_S$ has only finitely many nonzero values.

\noindent
We explain the rationale of this definition.} Thus, if we consider a representation where the elements of $A$ are functions on some finite set $F$ then $J_S$ is precisely the indicator function of the set $S'=\{c:x_i(c)-t_i=0:c\in F\text{ and }i=1,\dotsc, n\}$. The set $S'$ corresponds to the subalgebra $(S_{\tt t})_a$ and $J_S$, a projection in $A$, acts as identity in $(S_{\tt t})_a$.
\commentout{
The following shows  the existence of $J_S$ by an explicit construction. Suppose $S$ contains a single element $x$. Writing $x=\sum_ia_ix_i$ in some atomic basis we have $x-t=\sum a_jP_j$ where $a_j\neq 0$ are distinct and $P_j$ are projections. Now use Lagrange interpolation to obtain polynomials $g_j$ such that $g_j(a_k)=\delta_{jk}$ and $g_j(0)=0$. Then $Q=\sum_j P_j$ is the required projection. If there are more elements in $S$ then let $Q_j$ be the projection for $x_j-t_j$ and $Q$ the product of $Q_j$'s. Then $J_s=\unit-Q$. Note that we have an explicit formula for distribution function that we can use it to prove properties of d.f. }

From the notion of distribution functions we can define now probabilities $Pr(a\leq x\leq b)$ in the algebraic context. We can now formulate problems in any discrete stochastic process in finite dimensions. The algebraic method actually provides practical tools besides theoretical insights as the example of ``waiting time'' shows \cite{Patra09}.

Now we consider the algebraic formulation of a basic limit theorem of probability theory: the {\bf weak law of large numbers}. From information theory perspective it is perhaps the most useful limit theorem. Let $X_1,X_2,\cdots, X_n$ be independent, identically distributed (i.i.d) bounded random variables on a probability space $\Omega$ with probability measure $P$. Let $\mu$ be the mean of $X_1$. Recall the
{\em Weak law of large numbers}. Given $\epsilon>0$
\[\lim_{n\rightarrow \infty}P(|S_n=\frac{X_1+\cdots +X_N}{n}-\mu |>\epsilon)=0\]
We have an algebraic version of this important result.
\begin{thm} [Law of large numbers (weak)] \label{thm:weak-law}

If $x_1,\dotsc,x_n,\dotsc$ are
$\omega$-\\independent self-adjoint elements in an observable algebra and $\omega(x_i^k)=\omega(x_j^k)$ for all positive integers $i,j\text{ and }k$ (identically distributed) then
\[\lim_{n\rightarrow \infty} \omega(|\frac{x_1+\dotsb+x_n}{n}-\mu|^k)=0 \text{ where } \mu=\omega(x_1) \text{ and } k>0\]
\end{thm}
\commentout{
\begin{proof}
We may assume $\mu=0$ (by reasoning with $x_i-\omega(x_i)$ instead of $x_i$). First we prove the statement for $k=2$. Then $\omega(|\frac{x_1+\dotsb+x_n}{n}|)^2=\sum_i\omega(x_i^2)/n^2=\omega(x_1^2)/n$. The first equality follows from independence ($\omega(x_ix_j)=\omega(x_i)\omega(x_j)=0\text{ for }i\neq j$) the second from the fact that they are identically distributed. The case $k=2$ is now trivial. Now let $k=2m$. Then $|x_1+\dotsb +x_n|^k=(x_1+\dotsb +x_n)^k$. Put $s_n=(x_1+\dotsb +x_n)/n$. Expanding $s_n^k$ in a multinomial series we note that  independence and the fact that $\omega(x_i)=0$ implies that all terms in which at least one of the $x_i$ has power 1 do not contribute to $\omega(s_n^k)$. The total number of the remaining terms is $O(n^{m})$. Since the denominator is $n^{2m}$ we see that $\omega(s_n^k)\rightarrow 0$. Since for any $x\in A$, $|x|=(x^2)^{1/2}$ can be approximated by polynomials in $x^2$ we conclude that $\omega(|s_n|)\rightarrow 0$. Finally, using the Cauchy-Schwartz type inequality $\omega(|s_n|^{2r+1})\leq \omega(s_n^2)\omega(s_n^{2r})$ we see that the theorem is true for all $k$.
\end{proof}
}
Using the algebraic version of Chebysev inequality the above result implies the following.
Let $x_1,\dotsc, x_n \text{ and } \mu$ be as in the Theorem and set $s_n=(x_1+\dotsb+x_n)/n$. Then for any $\epsilon >0$ there exist $n_0$ such that for all $n>n_0$
\(
P(|s_n-\mu|>\epsilon) <\epsilon
\)

\commentout{
\begin{proof}
Using Chebysev inequality we have \( P(|s_n-\mu|>\epsilon)= P(|s_n-\omega(s_n)|>\epsilon) \leq \frac{\omega(|s_n-\mu|^2)}{\epsilon^2}\). As $\omega(|s_n-\mu|^2)\rightarrow 0$ (Theorem \ref{thm:weak-law}) there is $n_0$ such that $\omega(|s_n-\mu|^2)<\epsilon^3$ for $n>n_0$.
\end{proof}
}
\section{Communication and Information}\label{sec:info}
We now come to our original theme: an algebraic framework for communication and information processes. Since our primary goal is the modeling of information processes we refer to the simple model of communication in the Introduction and model different aspects of it. In this work we will only deal with sources with a finite alphabet.

\noindent
{\bf Definition.} {\em A source  is a pair $\scrp{S}=(B,\Omega)$ where $B$ is an atomic basis of a finite-dimensional abelian $\cstar$ algebra $A$ and $\Omega$ is a state in $\inftens{A}$}.

\noindent
This definition abstracts the essential properties of a source. The basis $B$ is called the {\em alphabet}. A typical output of the source is of the form $x_1\tensor x_2\tensor \dotsb\tensor x_k\tensor \unit \tensor \dotsb \in B^{\infty}$, the infinite product basis of $\inftens{A}$. We identify \(\hat{x}_k= \unit\tensor\dotsb\tensor\unit\tensor x_k\tensor\unit\tensor\dotsb\) with the $k$th signal. If these are independent
then Theorem \ref{thm:structIndep} tells us that $\Omega$ must be product state. Further, if the state of the source does not change then $\Omega=\omega\tensor\omega\tensor\dotsb$ where $\omega$ is a state in $A$.
For a such state $\omega$ define:
\(\cali{O}_{\omega}=\sum_{i=1}^n \omega(x_i)x_i, \; \{x_1, \dotsc, x_n\},\; x_i\in B\)
We say that $\cali{O}_{\omega}$ is the ``instantaneous'' output of the source in state $\omega$.
\commentout{
Intuitively, $\cali{O}_{\omega}$ is a kind of mean ``point'' in the space of outputs (compare it with the notion of center of mass in mechanics). More importantly, it facilitates calculation of important quantities and has close analogy with the quantum case. The quantum analogue may be pictured as follows. The source outputs ``particles'' in definite ``states'' $x_i$ with probability $p_i=\omega(x_i)$. Note that here state corresponds to a projection operator. A measurement for $x_i$ means applying the dual operator $\omega_i\;(\omega_i(x_j)=\delta_{ij})$ giving $\omega_i(\cali{O}_\omega)= p_i$.

Let $\mathscr{Z}=(X,\omega)$ be a static discrete source. Suppose every $x\in X$ belongs to a finite-dimensional subalgebra generated by a (finite) set of $\omega$-independent elements. Then using the Theorem \ref{thm:structIndep} we may assume that $A=\inftens B$ where $B$ is finite-dimensional abelian $\cstar$ algebra and $\omega$ is an (infinite) product state. In this case, each element of $X$ is a tensor product of elements of an atomic basis of $B$. In the rest of the paper we assume that $X$ is the product basis of atomic elements. For example, if $B$ is the two dimensional algebra with atomic basis $\{y_0,y_1\}$ then $X$ is the set of elements of the form
$z_1\tensor z_2\tensor\dotsb \tensor z_k\tensor\unit\tensor\unit\tensor\dotsb$ where $z_i\in\{y_0,y_1\}$.

Let $B$ be a finite-dimensional $\cstar$ algebra and $A=\inftens B$ . We consider $\tensor^n B$ as a subalgebra of $A$ via the standard embedding (all ``factors'' beyond the $n$th place equal $\unit$). Let $X_n$ be its atomic basis in some fixed ordering and let $X=\bigcup_n X_n$. We can consider $B$ as the source alphabet and $X_n$ as strings of length $n$.} Let $A'$ be another finite-dimensional $\cstar$ algebra with atomic basis $B'$
 A source coding is a linear map $f:B\rightarrow  T= \sum_{k= 1}^m \tensor^k A' $. Such that for $x\in B$, $f(x)=x'_{i_1}\tensor x'_{i_2}\tensor \dotsb\tensor x'_{i_r},\; r\leq k$ with $x'_{i_j}\in B'$. Thus each ``letter'' in the alphabet $B$ is coded by ``words'' of maximum length $k$ from $B'$.

\commentout{
Let us consider an example to clarify these points.
Let $\{x_0,x_1,x_2,x_3\}$ be an atomic basis for $B$. Let $B'=G$ with atomic basis $\{y_0,y_1\}$. Define $f_1$ by $f_1(x_0)=y_0,f_1(x_1)= y_1, f_1(x_2)=y_0\tensor y_1 \text{ and } f_1(x_3)=y_1\tensor y_0$. Denote by $\hat{f}_1$ its extension to tensor products. Since $\hat{f}_1(x_0\tensor x_1)=y_0\tensor y_1=\hat{f}_1(x_2)$, $\hat{f}_1$ is not injective. Hence it cannot be inverted on its range. Consider next the map $f_2(x_0)=y_0,f_2(x_1)=y_0\tensor y_1,f_2(x_2)=y_0\tensor y_1\tensor y_1\text{ and }f_2(x_3)=y_1\tensor y_1\tensor y_1$. This map is invertible but one has to look at the complete product before finding the inverse. It is not {\em prefix-free}.}

A code $f:B\rightarrow T$ is defined to be prefix-free if for distinct members  $x_1,x_2$ in an atomic basis of $B$, $f'(x_1)f'(x_2)=0$ where $f'$ is the map $f': B\rightarrow \inftens B'$ induced by $f$. That is, distinct elements of the atomic basis of $B$ are mapped to {\em orthogonal} elements. Thus the
``code-word'' $ z_1\tensor z_1\tensor\dotsb \tensor z_k \tensor \unit\tensor \unit\tensor\dotsb$ is not orthogonal to another $ z'_1\tensor z'_1\tensor\dotsb \tensor z'_m \tensor \unit\tensor \unit\tensor\dotsb$ with $k\leq m$ if and only if $z_1=z'_1,\dotsc, z_k=z'_k$.
\commentout{
We observe that one has to be careful about correspondence between the two approaches. For example, one might be tempted to identify the identity $\unit$ with the empty string but the $\unit$ is the sum of the members of an atomic basis! The binary operation ``+'' has a relatively lesser role in the classical formalism but it is crucial in the quantum framework (via superposition principle).}
The useful Kraft inequality can be proved using algebraic techniques.

Corresponding to a finite sequence $k_1\leq k_2\leq \dotsb \leq k_m$ of positive integers let $\alpha_1,\dotsc, \alpha_m$ be a set of prefix-free elements in $\sum_{i\geq 1} \tensor^i A'$ such that $\alpha_i\in \tensor^{k_i} A'$. Further, suppose that each $\alpha_i$ is a tensor product of elements from $B'$. Then
\beq \label{eq:Kraft}
 \sum_{i=1}^m n^{k_m-k_i} \leq n^{k_m}
\eeq

This inequality is proved by looking at bounds on dimensions of a sequence of orthogonal subspaces.
\commentout{
The Kraft inequality is valid for decipherable sequences \cite{McMillan}. However, the proof is essentially combinatorial. The Kraft inequality also provides a sufficiency condition for prefix-free code \cite{Ciszar,CoverT}. Thus the existence of a decipherable code of word-lengths $(k_1,k_2,\dotsc,k_m)$ implies the existence of a prefix-free code of same word-lengths.}
In the following, we restrict ourselves to prefix-free codes.

\commentout{
\begin{lem}
Let $f$ be a continuous real function on $(0,\infty )$ such that $xf(x)$ is convex and $\lim_{x\rightarrow 0} xf(x)=0$. Let $A$ be a finite-dimensional $\cstar$ algebra with atomic basis $\{x_1,\dotsc, x_n\}$ and $\omega$ a state on $A$. Then for any set of numbers $\{a_i\; :i=1,\dotsc, n;\; a_i>0\text{ and } \sum_i a_i\leq 1\}$ we have
\(\omega(\sum_i f(\frac{\omega(x_i)}{a_i})x_i) \geq f(1)\)
\end{lem}

\begin{proof}
Let $\omega(x_i)=p_i$. We have to show that $\sum p_if(p_i/a_i) \geq f(1)$. First assume that all $p_i>0$ and $\sum_i a_i=1$. Then
\[ \sum_i p_i f(p_i/a_i) =\sum_i a_i\frac{p_i }{a_i}f(\frac{p_i }{a_i}) \geq f(\sum p_i)=f(1)\]
by convexity of $xf(x)$. The general case can be proved by starting with $a_i$ corresponding to $p_i>0$ and adding extra $a_j$'s to satisfy $\sum_i a_i=1$ if necessary. The corresponding $p_j$ is set to $0$. Now define a new function $g(x)=xf(x), \; x>0$ and $g(0)=0$. The conclusion of the lemma follows by arguing as above with $g$.
\end{proof}
}
Using convexity function $f(x)=-\log {x}$ and the Kraft inequality \ref{eq:Kraft} we deduce the following.
\begin{propn}[Noiseless coding]
Let $\mathscr{S}$ be a source with output $\cali{O}_{\omega}\in A$, a finite-dimensional $\cstar$ algebra with atomic basis $\{x_1,\dotsc, x_n\}$ (the alphabet). Let $g$ be prefix-free code such that $g(x_i)$ is a tensor product of $k_i$ members of the code basis. Then
\(\omega(\sum_i k_ix_i+\log{\cali{O}_{\omega}})\geq 0\)
\end{propn}

Next we give a simple application of the law of large numbers. First define a positive functional $\tr$ on a finite dimensional abelian $\cstar$ algebra $A$ with an atomic basis $\{x_1,\dotsc, x_d\}$ by
\(\tr =\omega_1+\dotsb+\omega_d\) where $\omega_i$ are the dual functionals. It is clear that $\tr$ is independent of the choice of atomic basis.
\begin{thm}[Asymptotic Equipartition Property (AEP)]\label{thm:AEP}
Let $\scrp{S}$ be a source with output $\cali{O}_{\omega}=\sum_{i=1}^d \omega(x_i)x_i$ where $\omega$ is a state on the finite dimensional algebra with atomic basis $\{x_i\}$. Then given $\epsilon >0$ there is a positive integer $n_0$ such that for all $n>n_0$
\[ P(2^{n(H(\omega)-\epsilon)}\leq \tensor^n \cali{O}_{\omega}\leq 2^{n(H(\omega)+\epsilon)}) > 1- \epsilon \]
where $H=\omega(\log_2(\cali{O}_{\omega}))$ is the {\em entropy} of the source and the probability distribution is calculated with respect to the state $\Omega_n=\omega\tensor\dotsm\tensor\omega$ ($n$ factors) of $\tensor^n A$. If $Q$ denotes the identity in the subalgebra generated by $(\epsilon I-|\log_2(\tensor^n\cali{O}_\omega)+nH|)_+$ then
\[(1-\epsilon)2^{n(H(\omega)-\epsilon)}\leq \tr(Q) \leq 2^{n(H(\omega)+\epsilon)} \]
\end{thm}
\commentout{
The function $\log{x}\equiv \log_2{x}\;(=\ln{x}/\ln{2})$ is defined for strictly positive elements of a $\cstar$ algebra. We extend the definition to all non-zero $x\geq 0$. Let $\{y_i\}$ be a  atomic basis in an abelian $\cstar$ algebra. Let $y=\sum_i a_iy_i$ with $a_i\geq 0$. Then define $\log_2{y}=\sum_i b_i y_i$ where $b_i=\log{a_i}$ if $a_i>0$ and 0 otherwise. This definition implies that some standard properties of $\log$ are no longer true (e.g.\ $2^{\log{x}}\neq x$). But in the present context it gives the correct result when we take expectation values as in the formulas in the theorem.

A somewhat longer but mathematically better justified route is to ``renormalize'' the state. Thus if $\omega(x_i)=0$ for $k$ indices we define $\omega'(x_i)=\delta$ where $\delta$ is arbitrarily small but positive and $\omega'(x_j)=\omega(x_j)-k\delta$ where $\omega'(x_j)>k\delta$. If we can prove the theorem now for $\omega'$ and since the relations are valid in the limit $\delta\rightarrow 0$ then we are done. We will not take this path but implicitly assume that the probabilities are positive.} Note that the element $Q$ is a projection on the subalgebra generated by $(\epsilon I-|\log_2(\tensor^n\cali{O}_\omega)-nH|)_+$. It corresponds to the set of strings whose probabilities are between $2^{-nH-\epsilon}$ and $2^{-nH+\epsilon}$. The integer $\tr(Q)$ is simply the cardinality of this set.
\commentout{
\begin{proof}[Proof of the theorem]
First note that $\log{ab}=\log a+\log b$ for elements $a,b\geq 0$ in $A$. We can write $\tensor^n\cali{O}_{\omega}=X_1X_2\dotsb X_n$ where $X_i=\unit\tensor\unit\tensor\dotsm\tensor\cali{O}_{\omega}\tensor\unit\tensor\dotsm\tensor\unit$ with $\log{\cali{O}_{\omega}}$ in the $i$th place. The fact that $\Omega_n$ is a product state on $\tensor^n A$ (corresponding to a source whose successive outputs are independent) implies that $X_i$ are independent and identically distributed. We can now apply the corollary to Theorem \ref{thm:weak-law} yielding
\(P(|\log{(\tensor^n\cali{O}_{\omega})} -\Omega_n(\log{X_1})|>\epsilon)=P(|\log{(\tensor^n\cali{O}_{\omega})} -\omega(\log{(\cali{O}_{\omega})})|>\epsilon)\).
\end{proof}
}

We now come to the most important part of the communication model: the {\em channel}.
The original paper of Shannon characterized channels by a transition probability function. We will consider only (discrete) memoryless channel (DMS). A  DMS channel has an input alphabet $X$ and output alphabet $Y$ and
\commentout{
a sequence of random functions $\phi_n: X^n\rightarrow Y^n$. The latter are characterized by probability distributions $p_n(y^{(n)}|x^{(n)})$, the interpretation being: $\phi_n(x^{(n)})=y^{(n)}$ with conditional probability  $p_n(y^{(n)}|x^{(n)})$. Note that the distribution depends on the entire history. We say that such a channel has (infinite) memory. A channel has finite memory if there is an integer $k\geq 0$ such that if $x^{(n)}=x_nx_{n-1}\cdots x_{n-k+1}\dotsc x_1$ then $p_n(y^{(n)}|x^{(n)})= p_n(y^{(n)}|x'^{(n)})$ for any string $x_n'$ of length $n$ such that $x_n'=x_n, \dotsc, x_{n-k+1}'=x_{n-k+1}$. That is, the probability distribution depends on the most recent $k$ symbols seen by the channel. A channel is {\em memoryless} if $k=1$. Since we will be dealing mostly with discrete memoryless channels (DMS) this property will be tacitly assumed unless stated otherwise. In the memoryless case it is easy to show the simple form of transition probabilities
\beq
\begin{split}
&p_n(y^{(n)}|x^{(n)})=p_n(y_1\dotsc y_n|x_1\dotsc x_n)\\
& =p(y_1|x_1)p(y_2|x_2)\dotsb p(y_n|x_n)\\
\end{split}
\eeq
This motivates us to define the}
a {\em channel transformation matrix} $C(y_j|x_i)$ with $y_j\in Y$ and $x_i\in X$. Since the matrix $C(y_j|x_i)$  represents the probability that the channel outputs $y_j$ on input $x_i$ we  have $\sum_j C(y_j|x_i)=1$ for all $i$: $C(ij)=C(y_j|x_i)$ is {\em row stochastic}. This is the standard formulation.  \cite{Ciszar,CoverT}. We now turn to the algebraic formulation.

\noindent
{\bf Definition.} A DMS channel $\cali{C}=\{X,Y,C\}$ where $X$ and $Y$ are abelian $\cstar$ algebras of dimension $m$ and $n$ respectively and $C: Y \rightarrow X$ is a unital positive map. The algebras $X$ and $Y$ will be called the input and output algebras of the channel respectively. Given a state $\omega$ on $X$ we say that $(X,\omega)$ is the input source for the channel.

\noindent
Sometimes we write the entries of $C$ in the more suggestive form $C_{ij}=C(y_j|x_i)$ where $\{y_j\}$ and $\{x_i\}$ are atomic bases for $Y$ and $X$ respectively. Thus $C(y_j)=\sum_i C_{ij}x_i= \sum_i C(y_j|x_i)x_i$. Note that in our notation $C$ is an $m\times n$ matrix. Its transpose $C^T_{ji}=C(y_j|x_i)$ is the channel matrix in the standard formulation. We have to deal with the transpose because the channel is a map {\em from} the output alphabet to the input alphabet. This may be counterintuitive but observe that any map $Y\rightarrow X$ defines a unique dual map $\cali{S}(X)\rightarrow \cali{S}(Y)$, on the respective state spaces. Informally, a channel transforms a probability distribution on the input alphabet to a distribution on the output.
\commentout{
Let us note that in case of abelian algebras every positive map is guaranteed to be {\em completely positive} \cite{Tak1}. This is no longer true in the non-abelian case. Hence for the quantum case completely positivity has to be explicitly imposed on (quantum) channels.}
We characterize a channel by input/output algebras (of observables) and a positive map. Like the source output we now define a useful quantity called {\em channel output}. Corresponding to the atomic basis $\{y_i\}$ of $Y$ let $\tensor^k y_{i(k)}$ be an atomic basis in $\tensor^n Y$. Here $i(k)=(i_1i_2\dotsc i_k)$ is a multi-index. Similarly we have an atomic basis $\{\tensor^k x_{j(k)}\}$ for $\tensor^k X$. The level-$k$ channel output is defined to be

\(O^k_C = \sum_{i(k)} y_{i(k)}\tensor C^{(k)}(y_{i(k)})  \).

Here $C^{(k)}$ represents the channel transition probability matrix on the $k$-fold tensor product corresponding to strings of length $k$. In the DMS case it is simply the $k$-fold tensor product of the matrix $C$. The channel output defined here encodes most important features of the communication process. First, given the input source function  \(\cali{I}_{\omega^k}=\sum_i\omega^k(x_{i(k)})x_{i(k)}\) the output source function is defined by

\(\cali{O}_{\tilde{\omega}^k} = I\tensor \tr_{\tensor^kX}((\unit \tensor \cali{I}_{\omega^k})O^k_c)
=\sum_i \sum_j C(y_{i(k)}|x_{j(k)})\omega^k(x_{j(k)})y_{i(k)}\).

Here, the state $\tilde{\omega}^k$ on the output space $\tensor^k Y$ can be obtained via the dual $\tilde{\omega}^k(y)=\tilde{C}^k(\omega^k)(y)=\omega^k(C^k(y))$. The formula above is an alternative representation which is very similar to the quantum case. The {\em joint output} of the channel can be considered as the combined output of the two terminals of the channel. Thus the joint output
\beq \label{eq:chOutputJoint}
\begin{split}
&\cali{J}_{\tilde{\Omega}^k} = (\unit \tensor \cali{I}_{\omega^k})O^k_C=\sum_{ij} \Omega^k(y_{i(k)}\tensor x_{j(k)})y_{i(k)}\tensor x_{j(k)},  \\
& \Omega^k(y_{i(k)}\tensor x_{j(k)})\equiv C(y_{i(k)}|x_{j(k)})\omega(x_{j(k)})
\end{split}
\eeq
Let us analyze the algebraic definition of channel given above. For simplicity of notation, we restrict ourselves to level 1. The explicit representation of channel output is
\(\sum_i y_i\tensor \sum_j C(y_i|x_j)x_j \)
We interpreted this as follows: if on the channel's out-terminal $y_i$ is observed then the input could be $x_j$ with probability \(C(y_i|x_j)\omega(x_j)/\sum_jC(y_i|x_j)\omega(x_j)\). Now suppose that for a fixed $i$  $C(y_i|x_j)=0$ for all $j$ except one say, $j_i$. Then on observing $y_i$ at the output we are certain that the the input is $x_{j_i}$. If this is true for all values of $y$ then we have an instance of a lossless channel. Given $1\leq j\leq n$ let $d_j$ be the set of integers $i$ for which $C(y_i|x_j)> 0$. If the channel is lossless then $\{d_j\}$ form a partition of the set $\{1,\dotsc, m\}$. The corresponding channel output is
\( O_C= \sum_j \Bigl(\sum_{i\in d_j} C(y_i|x_j)y_i\Bigr)\tensor x_j\).
At the other extreme is the {\em useless} channel in which there is no correlation between the input and the output.
To define it formally, consider a channel $\cali{C}=\{X,Y,C\}$ as above. The map $C$ induces a map $C': Y\tensor X\rightarrow X$ defined by $C'(y\tensor x)=xC(y)$. Given a state $\omega$ on $X$ the
dual of the map $C'$ defines a state $\Omega_C$ on $Y\tensor X$: \(\Omega_C(y\tensor x)=\omega(C'(y\tensor x))=C(y|x)\omega(x)\). We call $\Omega_C$ the joint (input-output) state of the channel. A channel is
useless if $Y$ and $X$ (identified as $Y\tensor \unit$ and $\unit \tensor X$ resp.) are $\Omega_C$-independent. It is easily shown that: {\em a channel $\cali{C}=\{X,Y,C\}$ with input source $(X,\omega)$ is useless iff the matrix $C_{ij}=C(y_j|x_i)$ is of rank 1}.

The algebraic version of the channel coding theorem assures that it is possible to approximate, in the long run, an arbitrary channel (excepting the useless case) by a lossless one.

\begin{thm}[Channel coding]\label{thm:ch_coding}
Let $\cali{C}$ be a channel with input algebra $X$ and output algebra $Y$. Let \(\{x_i\}_{i=1}^n\text{ and } \{y_j\}_{j=1}^m\) be atomic bases for $X$ and $Y$ resp. Given a state $\omega$ on $X$, if the channel is not useless then  for each $k$ there are subalgebras \(Y_k\subset \tensor^k Y, X_k\subset \tensor^k X\), a map $C_k: Y_k\rightarrow X_k$ induced by $C$ and  a lossless channel $L_k: Y_k\rightarrow X_k$ such that
\[\lim_{k\rightarrow \infty} \Omega(|O_{C_k}-O_{L_k}|) = 0 \text{ on } T_k=Y_k\tensor X_k\]
Here $\Omega=\tensor^{\infty}\Omega_C$ and on $\tensor^k Y\tensor \tensor^k Y$ it acts as $\Omega^k=\tensor^k\Omega_C$ where $\Omega_C$ is the state induced by the channel and a given input state $\omega$. Moreover, if $r_k=\text{dim}(X_k)$ then $R=\frac{\log{r_k}}{k}$, called transmission rate, is independent of $k$.
\end{thm}
Let us clarify the meaning of the above statements. The theorem simply states that on the chosen set of codewords the channel output of $C_k$ induced by the given channel can be made arbitrarily close to that of a lossless channel $L_k$. Since a lossless channel has a definite decision scheme for decoding the choice of $L_k$ is effectively a decision scheme for decoding the original channel's output when the input is restricted to our ``code-book''. This implies probability of error tends to 0 it is possible to choose a set of ``codewords'' which can be transmitted with high reliability. The proof of the theorem \cite{Patra09} uses algebraic arguments only.  The theorem guarantees ``convergence in the mean'' in the appropriate subspace which implies convergence in probability. For a lossless channel the input entropy $H(X)$ is equal to the mutual information. We may think of this as conservation of entropy or information which justifies the term ``lossless''. Since it is always the case that $H(X)-H(X|Y)=I(X,Y)$ the quantity $H(X|Y)$ can be considered the loss due to the channel. The algebraic version of the theorem serves two primary purposes. It gives us the abelian perspective from which we will seek possible extensions to the non-commutative case. Secondly, the channel map $L$ can be used for a decoding scheme. Thus we may think of a coding-decoding scheme for a given channel as a sequence of pairs $(X_k, L_k)$ as above.

The coding theorems can be extended to more complicated scenarios like ergodic sources and channels with finite memory. We will not pursue these issues further here. But we are confident that these generalizations can be appropriately formulated and proved in the algebraic framework.

In the preceding sections we have laid the basic algebraic framework for classical information theory. Although, we often confined our discussion to finite-dimensional algebras corresponding to finite sample spaces it is possible to extend it to infinite-dimensional algebras of continuous sample spaces.
\commentout{
In this regard, a natural question is: can the algebraic formulation replace  Kolmogorov axiomatics based on measure theory? Naively, the answer is no because the assumption of a norm-compete algebra imposes the restriction that the random variables that they represent must be {\em bounded}. Moreover, the GNS construction implies that the algebraic framework is essentially equivalent to (almost) bounded random variables on a locally compact space. In order to deal with the unbounded case we have to go beyond the normed algebra structures. A possible course of action is indicated in the examples given in section \ref{sec:examples}: via the use of a ``cut-off''. A more general approach would be to consider sequences which converge in a topology weaker than the norm topology to elements of a larger algebra. These and other related issues on foundations are deep and merit a separate investigation.}
These topics will be  investigated in the future in the non-commutative setting.  We will delve deeper into these analogies and aim to throw light on some basic issues like quantum Huffman coding \cite{Braunstein}, channel capacities and general no-go theorems among others, once we formulate the appropriate models.