Finite-Time Capacity: Making
Exceed-Shannon Possible?

The finite-time capacity is, heuristically, defined as the maximum number of bits that can be successfully transmitted within a finite-time window. Since Shannon capacity is defined on pairs of random variables, it is crucial to introduce randomness into the transmission model. Inspired by [9], we model the transmitted signal by a zero-mean stationary Gaussian stochastic process, denoted as $X(t)$, and the received signal by $Y(t):=X(t)+N(t)$. The process $N(t)$, which denotes the noise, is also a stationary Gaussian process independent of $X(t)$. The receiver is only allowed to observe the signal within finite-time window $[0,T]$, where $T>0$ is the observation window span. Our goal is to find the maximum number of bits that can be acquired within this time window.

To analytically express the amount of the acquired information, we first introduce $n$ sampling instants inside the time window, denoted by $(t_{1},t_{2},\cdots,t_{n}):=t_{1}^{n}$, and then let $n\rightarrow\infty$ to approximate the finite-time capacity³³3In this paper, we do not explicitly distinguish between the terms “finite-time mutual information” and “finite-time capacity”, since we consider communication schemes where the source autocorrelation is fixed.. This approximation of capacity becomes more precise as the sampling instants $t_{1}^{n}$ become denser. Then by defining ${\bm{X}}(t_{1}^{n})\equiv(X(t_{1}),X(t_{2}),\cdots,X(t_{n}))$ and ${\bm{Y}}(t_{1}^{n})\equiv(Y(t_{1}),Y(t_{2}),\cdots,Y(t_{n}))$, the capacity on these $n$ samples can be expressed as

and the finite-time capacity is defined as

Then, the transmission rate $C(T)$ can be defined by dividing the amount of information acquired within $[0,T]$ by the time span $T$:

From these definitions, we can define the limit capacity as $C(\infty)=\lim_{T\rightarrow\infty}{C(T)}$ by letting $T\rightarrow\infty$. The quantity $C(\infty)$ characterizes the maximum average number of bits per second one can acquire from a received noisy stochastic process.

Without loss of generality, we fix the sampling instants uniformly onto fractions of $T$: $t_{i}=(i-1)T/n,1\leq i\leq n$. Since the random vectors ${\bm{X}}(t_{1}^{n})$ and ${\bm{Y}}(t_{1}^{n})$ are samples of a Gaussian process, they are both Gaussian random vectors with mean zero and covariance matrices ${\bm{K}}_{X}$ and ${\bm{K}}_{Y}$, where ${\bm{K}}_{X},{\bm{K}}_{Y}\in\mathbb{R}^{n\times n}$ are symmetric positive-definite matrices. The entries of ${\bm{K}}_{X}$ and ${\bm{K}}_{Y}$ are determined by the autocorrelation functions of Gaussian processes $X(t)$ and $Y(t)$, denoted by $R_{X}(t_{1},t_{2})$ and $R_{Y}(t_{1},t_{2})$:

Note that $Y(t)$ is the independent sum of $X(t)$ and $N(t)$, thus the autocorrelation functions satisfy $R_{Y}(t_{1},t_{2})=R_{X}(t_{1},t_{2})+R_{N}(t_{1},t_{2})$, and similarly the covariance matrices satisfy ${\bm{K}}_{Y}={\bm{K}}_{X}+{\bm{K}}_{N}$.

The mutual information $I(t_{1}^{n})$ is defined as $I(t_{1}^{n})=h({\bm{Y}}(t_{1}^{n}))-h({\bm{Y}}(t_{1}^{n})|{\bm{X}}(t_{1}^{n}))=h({\bm{Y}}(t_{1}^{n}))-h({\bm{N}}(t_{1}^{n}))$, where $h(\cdot)$ denotes the differential entropy. For $n$-dimentional Gaussian vector ${\bm{U}}$ with mean 0 and covariance matrix ${\bm{K}}$, the differential entropy is given by

Plugging (5) into the definition of $I(t_{1}^{n})$, we obtain

In (6), by letting $n\rightarrow\infty$, we can find that $I(t_{1}^{n})$ increases monotonously when $n$ doubles, because of the data processing inequality. Though without rigorous proof, we can assume with confidence that $I(t_{1}^{n})$ is an increasing function of $n$. However, it remains unknown whether $I(t_{1}^{n})$ tends to a finite limit. In fact, $I(t_{1}^{n})$ can be arbitrarily large, since the signal outside the noise band is strictly unpolluted by the noise, which results in infinite SNR. Thus, the capacity will diverge to infinity. Therefore, in order to avoid capacity divergence, at least one of the following conditions should be satisfied:

• •

  The noise process $N(t)$ is not band-limited.

• •

  The power spectral density of $X(t)$ is strictly contained inside the band of $N(t)$.

Thus, in the following numerical analysis, we choose $N(t)$ to be band-unlimited. This leads to the choice of reasonable autocorrelation functions of $X(t)$ and $N(t)$ in the following subsection.

In order to study the properties of mutual information $I(t_{1}^{n})$ as a function of $n$, we perform numerical analyses under different values of $n$ and $T$. The autocorrelation function and PSD of the signal process $X(t)$ and noise process $N(t)$ are set to the special case

where $\mathrm{sinc}(x):=\sin(\pi x)/(\pi x)$. Note that the PSD of the transmitted process $S_{X}(f)$ is strictly band-limited, while the PSD of the noise process is not. In fact, the noise PSD is carefully selected to ensure the received noise has finite power on each instant $t_{i}$, allowing the execution of numerical computations. A finitely powered process PSD must be colored, in contrast to additive white Gaussian noise (AWGN) with white PSD and infinite power. That is the reason why we choose $S_{N}(f)$ to be the form of (7).

In order to compare the finite-time capacity with the classical Shannon capacity, we have to calculate the Shannon capacity with colored noise spectrum $S_{N}(f)$, which is a generalized version of the well-known formula $C=W\log\left(1+S/N\right)$. The Shannon capacity $C_{\rm sh}$ of colored noise PSD [5], measured in ${\rm nat/s}$, is expressed as

Then, plugging (7) into (8) yields the numerical result for $C_{\rm sh}$.

In the numerical analysis, we calculate the finite-time transmission rate $C(T)$ and Shannon capacity against the number of samples $n$ within the observation window $[0,T]$. The numerical results are collected in Fig. 1. It is shown that $I(t_{1}^{n})$ is an increasing function of $n$, and for fixed values of $T$, the approximated finite-time capacity $I(t_{1}^{n})$ tends to a finite limit under the correlation assumptions given by (7). The most amazing observation is that, we can obtain more information within finite-time window $[0,T]$ than the prediction $TC_{\rm sh}$ given by the Shannon capacity (8). We call this phenomenon the “Exceed-Shannon” phenomenon.

To analytically verify the existence of the Exceed-Shannon phenomenon, we are going to introduce some mathematical tools in the following Section III, and finally give an analytical proof in Section IV.

Motivated by the discovery of the Exceed-Shannon phenomenon, we go further into the underlying mechanism behind this fact. Since the calculation of (6) depends on the evaluation of determinants that are determined by autocorrelation functions of Gaussian processes, it is possible to obtain $I(t_{1}^{n})$ and $I(T)$ directly from the autocorrelation functions. In fact, if we know the Mercer expansion [7] of the autocorrelation function $R_{X}(t_{1},t_{2})$ on window $[0,T]$, then we can calculate $h({\bm{X}}(t_{1}^{n}))$ more easily [10]. In the following discussion, we assume the Mercer expansion of the source autocorrelation function $R_{X}(t_{1},t_{2})$ to be in the following form

Due to the positive-definite property of the integral kernel $R_{X}(t_{1},t_{2})$, the eigenvalues are strictly positive: $\lambda_{k}>0$, and the eigenfunctions form an orthonormal set:

The Mercer’s theorem [7] ensures the existence and uniqueness of the eigenpairs $(\lambda_{k},\phi_{k}(t))_{k=1}^{\infty}$, and furthermore, the kernel itself can be expanded under the eigenfunctions. The convergence is absolute and uniform:

The Mercer expansion enables us to analytically express an autocorrelation function on a finite-time interval $[0,T]$, since the autocorrelation function can be naturally treated as a positive-definite integral kernel.

Based on Mercer expansion, we can obtain a closed-form formula in the following Theorem 1.

From Theorem 1, we can conclude that the finite-time capacity of AWGN channel is uniquely determined by the Mercer spectra $\lambda_{k}$ of $R_{X}(t_{1},t_{2})$ within $[0,T]$. However, it remains unknown whether the series representation (12) converges. In fact, the convergence is closely related to the signal power. In Fourier transform, the power in the time domain is equal to the power in the frequency domain, which is known as the Parseval’s theorem[11]. Like the Fourier transform, the transform defined by the orthonormal basis $\{\phi_{k}(t)\}_{k=1}^{\infty}$ also satisfy the Parseval’s theorem. This observation leads to a theoretic verification of power conservation in the view of $\lambda_{k}$, which is stated in the following Lemma 1.

The Mercer spectra enables us to explicitly calculate the finite-time capacity, and furthermore, prove the “Exceed-Shannon” phenomenon. This will be demonstrated in the next section.

In order to show the existence of Exceed-Shannon phenomenon, we only need to show that the finite-time capacity is greater than Shannon capacity in a typical case. Let us consider a finite-time communication scheme with a finitely-powered stationary transmitted signal autocorrelation⁴⁴4The signal autocorrelation $R_{X}(\tau)$ is often observed in many scenarios, such as passing a signal with white spectrum through an RC lowpass filter., which is specified as

where $\tau=t_{1}-t_{2}$, in AWGN channel⁵⁵5In this theoretical proof of “Exceed-Shannon” phenomenon, we assume the noise to be AWGN, to simplify the analytical computations. Gaussian processes of white spectrum are “immoral”, thus they can neither be power-limited, nor they can be directly sampled and numerically represented in computers. with noise PSD being $n_{0}/2$. The power of signal $X(t)$ is $P=R_{X}(0)$. According to Lemma 1, the trace of the corresponding Mercer operator $M(\cdot)$ is finite. Then the finite-time capacity given by Theorem 1 is also finite, as is shown in Remark 1. Finding the Mercer expansion is equivalent to finding the eigenpairs $(\lambda_{k},\phi_{k}(t))_{k=1}^{\infty}$. The eigenpairs are determined by the following characteristic integral equation [13]:

Differentiating both sides of (15) twice with respect to $s$ yields the boundary conditions and the differential equation that $\lambda_{k},\phi_{k}$ must satisfy:

Let $\omega_{k}>0$ denote the resonant frequency of the above harmonic oscillator differential equation, then $\lambda_{k}=2\alpha P/(\alpha^{2}+\omega_{k}^{2})$, and $\omega_{k}$ must satisfy the above two boundary constraints. Let $\phi_{k}(t)=A_{k}\cos(\omega_{k}t)+B_{k}\sin(\omega_{k}t)$ be the sinusoidal form of the eigenfunction. Using the boundary conditions we obtain

To ensure the existence of solution to the homogeneous linear equations (17) with unknowns $A_{k},B_{k}$, the determinant must be zero. Exploiting this condition, we find the equation that $\omega_{k}$ must satisfy:

By introducing an auxillary variable $\theta_{k}=\arctan(\omega_{k}/\alpha)\in[0,\pi/2]$, equation (18) can be simplified as $\tan(\omega_{k}T)=-\tan(2\theta_{k})$, i.e., there exists a positive integer $m$ such that $2\arctan(\omega_{k}/\alpha)=m\pi-\omega_{k}T$. The integer $m$ can be chosen to be equal to $k$. From the function images of $2\arctan(\omega/\alpha)$ and $m\pi-\omega T$ (Fig. 2), we can determine $\omega_{k}$, and then $\lambda_{k}$. To sum up, the solution to the characteristic equation (15) are collected into (19) as follows.

where $Z_{k}$ denotes the normalization constants of $\phi_{k}(t)$ on $[0,T]$ to ensure orthonormality.

Equation (19) gives all eigenpairs $(\lambda_{k},\phi_{k})_{k=1}^{\infty}$, from which we can calculate $I(T)$ by applying Theorem 1. As for the Shannon capacity $C_{\rm sh}$, by applying (8) and evaluating the integral with[14], we can obtain

where the evaluation of the improper integral $(a)$ is given in Appendix E.

After all the preparation works above, we can rigorously prove that $C(T)>C_{\rm sh}$ under the typical case of (14), as long as the transmission power $P$ is smaller than a constant $\delta$. The following Theorem 2 proves this result.

To verify the above theoretical analysis, numerical experiments on $I(T)$ are conducted based on evaluations of (19) and (20). As is shown in Fig. 3, it seems that we can always harness more mutual information in a finite-time observation window, compared with the Shannon capacity. Though seems impossible, this fact is somehow unsurprising because the observations ${\bm{Y}}(t_{1}^{N})$ inside the finite-time window $[0,T]$ can always eliminate some extra uncertainty outside the window due to the autocorrelation of $X(t)$. Different from the finite-time capacity, the Shannon capacity describes the circumstance of $T\rightarrow\infty$, where the fringe effect near $t=0$ and $t=T$ becomes negligible compared with the prolonged window period. Thus, the Shannon capacity does not take into consideration the small extra information on the fringe, causing an underestimation of the capacity. Fig. 3 also shows that, the extra capacity $\Delta I:=I(T)-TC_{\rm sh}$ between the finite-time result and Shannon capacity tends to a constant as $T\rightarrow\infty$. As is discussed above, the difference may come from the additional elimination of uncertainty at the fringe of the window. This asymptotically constant difference results in asymptotic linearity of the finite-time mutual information $I(T)$ as a function of $T$.

Apart from the above discussion, there is an extra interesting observation in Fig. 3, which leads to another rigourous proof of the Exceed-Shannon phenomenon. If we investigate the slope of curves $I(T)$ at the origin, i.e., the “instant transmission rate” at the origin, we find that $C(0^{+})>C_{\rm sh}$. This observation is confirmed by the following theorem:

From the conclusion of Theorem 3 and (20), we can reduce the Exceed-Shannon inequality $C(0^{+})>C_{\rm sh}$ at $T=0^{+}$ to the following inequality:

which can be directly verified by simple term-shifting and squaring on both sides. This inequality implies that the average transmission rate in the finite-time regime is strictly larger than the Shannon capacity around the origin $T=0$.

The conclusion of Theorem 3 is verified numerically in Fig. 5 and Fig. 5. The blue solid lines, representing the finite-time capacity $C(T)$, are above the red dashed lines representing the Shannon capacity, which demonstrates the Exceed-Shannon phenomenon. The $C(T)$ curves all start at $P/n_{0}$ when $T=0^{+}$, which coincides with the conclusion of Theorem 3. It can also be observed from the two figures that, for fixed values of $P,n_{0}$, as $\alpha$ increases, the transmitted signal $X(t)$ tends to be less correlated, thus being more informative. The transmission rate is then improved. This insight also comes from the change of PSD $S_{X}(f)$. As $\alpha$ increases, the PSD becomes flatter, i.e., a wider range of bandwidth is occupied, and thus the rate increases accordingly.

Achievability of the finite-time capacity. It is known that for any band-limited stationary Gaussian process $X(t)$ with PSD $S_{X}(f)$, one can generate signals whose PSD is exactly $S_{X}(f)$ by first generating a sequence $X(nT_{s})$ of sufficiently high sampling rate, and then passing the generated sequence through a shaping filter. Since the transmitted signal $X(t)$ and its generating sequence $X(nT_{s})$ determine each other uniquely if $X(t)$ is strictly band-limited, $X(t)$ and $X(nT_{s})$ can be treated to contain the same amount of information. Then we can conclude that, after observing the noisy received process $Y(t),t\in[0,T]$, because of the definition of the finite-time capacity $I(T)$, the amount of uncertainty of the underlying transmitted sequence $X(nT_{s})$ can be reduced by exactly $I(T)$ nats. That is to say, we link the finite-time capacity with a sequence-to-sequence capacity. Thus, the finite-time mutual information $I(T)$ is achievable by standard capacity-achieving techniques such as random coding [1], as long as the sampling instants are dense enough.

Compatibility with the Shannon-Hartley theorem. Though the Exceed-Shannon effect does imply an average data transmission rate within a finite-time window higher than that predicted by Shannon, in fact, it is still impossible to construct a long-time stable data transmission scheme above the Shannon capacity by leveraging this effect. So the Exceed-Shannon phenomenon does not contradict the Shannon-Hartley Theorem. Placing additional observation windows cannot increase the average information rate, because the received process $Y(t)$ observed by the subsequent additional windows has already been implicitly altered by the previous observation. The posterior process $Y(t)|{\bm{Y}}(t_{1}^{N})$ does not carry as much information as the original one, thus causing a rate reduction in the later windows. It is expected that, the average transmission rate would ultimately decrease to the Shannon capacity as the total observation time tends to infinity (i.e., $C(\infty)=C_{\rm sh}$), and the analytical proof is still worth investigation in future works.