This paper derives the optimal test channel distribution and the complete characterization of the classical Gorbunov and Pinsker (1973), Gorbunov and Pinsker (1974) nonanticipatory epsilon entropy of multivariate Gaussian Markov sources with square-error fidelity, which remained an open problem since 1974. The paper also formulates a state dependent nonanticipatory epsilon entropy, in which past reproductions are available to the decoder and not to the encoder, the test channel is specified with respect to an auxiliary (state) random process, and the reproduction process is a causal function of past reproduction and the auxiliary random process. This variation is analogous to the Wyner and Ziv (1976) and Wyner (1978) rate distortion function (RDF), of memoryless sources. It is shown that the operational rate of zero-delay codes, with past reproductions available to the decoder but not to the encoder is bounded below by the state dependent nonanticipatory epsilon entropy rate. For the case of multivariate Gaussian Markov sources with square-error fidelity, the optimal test channel distribution and the complete characterization of the state dependent of nonanticipatory epsilon entropy are derived, and also shown that that the two nonanticipatory epsilon entropies coincide. The derivations are new; they are based on structural properties of the stochastic realizations of the reproduction process that induce the optimal test channel distributions. They are derived using, achievable lower bounds on information theoretic measures, properties of mean-square estimation theory, Hadamard’s inequality, and canonical correlation coefficients of a tuple of multivariate jointly Gaussian random processes. Applications of the nonanticipatory epsilon entropy and its state dependent variation are discussed to the areas of control of unstable Gaussian systems over limited memory channels, design of causal estimators for Gaussian Markov sources with a fidelity criterion, computation of the rate loss of causal and zero-delay codes of Gaussian Markov sources with respect to non-causal codes.

The multiple-input multiple-output (MIMO) generalization of Cover’s and Pombra’s Gaussian feedback capacity [1] is considered. A sequential characterization of the finite block or transmission feedback information (FTFI) capacity is derived, with the optimal channel input process expressed as functional of a sufficient statistic and a Gaussian orthogonal innovations process. From the new representations follows that the MIMO version of the Cover and Pombra characterization of the FTFI capacity is expressed as a functional of two generalized matrix difference Riccati equations (DRE) of filtering theory of Gaussian systems. Analogous expressions for nonfeedback capacity are also derived, which involve a Lyapunov equation. The derivations follow directly from [2]; application examples to autoregressive moving average noise are found in [3], and to autoregressive noise in [4], [5]. Asymptotic formulas of feedback, nonfeedback capacity, and achievable lower bound incurred by asymptotically stationary channel inputs follow from the analysis of [2, Section III].

Presented are closed-form feedback capacity formulas, and lower bounds on nonfeedback achievable rates, for additive Gaussian noise (AGN) channels, driven by unstable, i.e., nonstationary, and stable, autoregressive moving average noise, ARMA $(a,c),a\in(-\infty,\infty),c\in(-\infty,\infty)$ (with one pole at c and one zero at a), which are independent of the distributions of the initial random variables, i.e., the initial state of the noise. The feedback capacity exhibits multiple regimes of capacity; (i) for the regime that includes the stable noise, ARMA $(a,c),a\in(-{1},{1}), c\in$(−1, 1) and for all transmit powers $\kappa\in(0,\infty)$, feedback does not increase capacity, (ii) for the regime that includes the unstable noise, ARMA $(a,c), |c| \gt 1,a\in$(−1, 1), and for transmit power above a threshold $\kappa \gt \kappa_{{\min}}$, feedback increases capacity, and the higher the $|c|$ the higher the capacity. The unstable regime is verified by the semi-definite program of [1]. Although, our answer} feedback does not increase capacity for stable noise, ARMA $(a,c)$, $a\in$(−1, 1), $c\in$(−1, 1) contradicts the feedback capacity, $C_{FB}$, in [2, Theorem 6.1,] $C_{FB}]$, [1] and the maximal information rate, $I_{{\max}}$ in [3, Theorem 7,] $I_{{\max}}$, this is attributed to the fact that rates in [1] –[3], depend on the initial state of the noise, and these rates are not achievable, for asymptotically stationary noise. This paper uses results from [4].

The complete characterization of the Gorbunov and Pinsker [1], [2] nonanticipatory epsilon entropy of multivariate Gauss-Markov sources with square-error fidelity is derived, which remained an open problem since 1974. Specifically, it is shown that the optimal matrices of the stochastic realization of the optimal test channel or reproduction distribution, admit spectral representations with respect to the same unitary matrices, and that the optimal reproduction process is generated, subject to pre-processing and post-processing by memoryless parallel additive Gaussian noise channels. The derivations and analyses are new and bring out several properties of such optimization problems over the space of conditional distributions and their realizations.

In this paper we characterize the feedback capacity of Additive Gaussian Noise (AGN) channels driven by stable and unstable autoregressive noise, for time-invariant feedback codes (channel input distributions). For stable (resp. unstable) channel noise we identify necessary and sufficient conditions for the optimal input process to induce asymptotic stationarity and ergodicity of the channel output (resp. innovations) process. We call this the ergodic feedback capacity. From our characterization follows the surprising result: for a time-invariant unit memory Gaussian autoregressive noise AR(c), c ∈ (-∞, ∞), (i) feedback does not increase capacity for the region with c ∈ (-1, 1) and certain unstable c, and total transmit power κ ∈ [0,%), and (ii) feedback increases capacity for the compliment of the region of values of (c, κ), not covered in (i).

In this paper we employ the information structures of optimal channel inputs of feedback capacity of additive Gaussian noise (AGN) channels, driven by stable and unstable autoregressive noise, to derive achievable rates for nofeedback capacity, and the corresponding channel input processes. The expressions of rates are derived using time-domain methods, they hold for stable and unstable noise, for all values of transmit power. The method avoids power spectral techniques and their limitations. The lower bounds are evaluated against the classical nonfeedback capacity obtained via water-filling frequency-domain techniques.

Motivated by the demand of reliable and finite blocklength communications, we employ tools from information theory, stochastic processes and queueing theory, in order to provide a comprehensive framework regarding the analysis of a Time Division Multiple Access (TDMA) network with bursty traffic, in the finite blocklength regime. Specifically, we reexamine the stability conditions of a non-cooperative TDMA multiple access channel, evaluate the optimal throughput, and identify the optimal data packet size, k, for fixed codeword of blocklength, n. The evaluation is performed both numerically and via the proposed approximations, which result in closed form expressions and provide insight on how the optimal data size, k*, relates to the information metrics of channel capacity and channel dispersion in the finite blocklength regime. Then, we examine the stability conditions and the performance of the Multiple Access Relay Channel with TDMA scheduling, subject to finite blocklength constraints, by applying a cognitive cooperation protocol that assumes relaying is enabled when sources are idle. Finally, we propose the novel Batch-And-Forward (BAF) strategy, a mechanism that allows terminals to send batches of data packets instead on individual data packets, and evaluate the stability conditions and the optimal throughput. Numerical evaluation of the proposed strategy indicates that the performance of the cooperative network in the finite blocklength regime, in terms of throughput, can be significantly enhanced. Moreover, it reduces the requirement in control signals (metadata) [3], since, it avoids the unnecessary repetition of metadata (e.g. address of the source terminal and the destination). The BAF strategy is quite versatile, thus, it can be embedded in existing cooperative protocols, without imposing additional complexity on the overall scheme.

Recent advances in information theory have provided a novel framework regarding finite blocklength analysis, which can be employed to address the current and future demands of communication networks. In this paper, we investigate the performance of the Time-Division Multiple-Access (TDMA) scheme with bursty traffic, subject to finite blocklength constraints. In contrast to previously reported work, where the analysis of such communication networks was performed under the infinite blocklength assumption, we develop a comprehensive framework that takes finite blocklength constraints into account. In particular, we employ the recent results in finite blocklength analysis, to prove necessary stability conditions for the overall system at the finite blocklength regime, and to identify the optimal trade-off between data length and channel blocklength. The later one is evaluated both numerically and via the proposed linear and quadratic approximations that result to closed form expressions.

This work provides a comprehensive framework regarding the analysis of the Multiple Access Relay Channel (MARC) with Time Division Multiple Access (TDMA) scheduling, subject to finite blocklength constraints. In particular, we examine the stability conditions and evaluate the maximum throughput, by applying a cognitive cooperation protocol that assumes relaying is enabled when sources are idle. Moreover, we propose the novel Batch-And-Forward (BAF) strategy, that can significantly enhance the performance of cooperative networks in the finite blocklength regime, as well as reduce the requirement in metadata. The BAF strategy is quite versatile, thus, it can be embedded in existing cooperative protocols, without imposing additional complexity on the overall scheme.

Shannon's coding capacity of memoryless additive Gaussian noise (AGN) channels with noiseless feedback, is known to be achieved by the Elias [1] coding scheme of communicating the mean square-error (MSE) of a Gaussian RV X ~ N(0, σ'), from past channel outputs, and decoding it using a MSE decoder. Further, it is known that among all encoders, and decoders that minimize the MSE, then the Elias encoder and decoder are globally optimal. In this paper we derive analogous results, for communicating unstable Gaussian Markov processes over unstable multiple-input multiple-output (MIMO) Gaussian recursive models (GRM) with memory, often called infinite impulse response (IIR) models, subject to an average cost of quadratic form. However, unlike memoryless AGNs, certain conditions are required, for such generalizations. Further, to show global optimality, we need to invoke Gorbunov and Pinsker [2] nonanticipatory € entropy, instead of the classical rate distortion function of the source. Another important observation is that we need a two-parameter coding scheme, instead of the one-parameter coding scheme of memoryless AGN channels.

A method is developed to realize optimal channel input conditional distributions, which maximize the finite transmission feedback information (FTFI) capacity, often called $n$ -block length feedback capacity, by information lossless randomized strategies. The method is applied to compute closed form expressions for the FTFI capacity and feedback capacity, of nonstationary, nonergodic, unstable, multiple input multiple output Gaussian channels with memory on past channel outputs, subject to average transmission cost constraints of quadratic form in the channel inputs and outputs. It is shown that randomized strategies decompose into two orthogonal parts-an deterministic part, which controls the channel output process, and an innovation part, which transmits new information over the channel. Then a separation principle is shown between the computation of the optimal deterministic part and the random part of the optimal randomized strategies. Finally, the ergodic theory of linear-quadratic-Gaussian stochastic optimal control theory, is applied to identify sufficient conditions, expressed in terms of solutions to matrix difference and algebraic Riccati equations, so that the optimal control part of randomized strategies induces asymptotic stationarity and ergodicity, and feedback capacity is characterized by the per unit time limit of the FTFI capacity. The method reveals an interaction of the control and the information transmission parts of the optimal randomized strategies, and that whether feedback increases capacity, is directly related to the channel parameters and the transmission cost function, through the solutions of the matrix Riccati equations. For unstable channels, it is shown that feedback capacity exists and it is strictly positive, provided the power exceeds a critical threshold.

Stochastic optimal control theory and a variational equality of directed information are applied, to develop a methodology to identify the information structures of optimal channel input conditional distributions, which maximize directed information, for classes of channel conditional distributions and transmission cost functions that depend on previous channel output symbols. The subsets of the maximizing distributions are characterized by conditional independence. One of the main theorems of this paper states that, for any channel conditional distribution with finite memory on past channel outputs, subject to an average cost constraint, then the information structure of the optimal channel input conditional distribution, which maximizes directed information, is determined by the maximum of the memory of the channel distribution and the functional dependence of the transmission cost function on past channel outputs. This theorem provides, for the first time, a direct analogy, in terms of the conditional independence properties of maximizing distributions, between the characterization of feedback capacity of channels with memory, and Shannon's two-letter characterization of capacity of memoryless channels. Another main result of the paper is the identification of sufficient conditions for the validity of direct and converse coding theorems, for unstable Gaussian channel models with memory, that is based on the ergodic theory of Markov decision.

Feedback capacity is extended beyond classical communication channels, to stochastic dynamical systems, which may correspond to unstable control systems or unstable communication channels, subject to average cost constraints of total power κ ∈ [0, ∞). It is shown that optimal conditional distributions or randomized strategies, have a dual role, to simultaneously control the output process and to encode information. The dual role is due to the interaction of control and information transmission; it states that encoders in communication channels operate as encoders-controllers, while controllers in control systems operate as controllers-encoders. The concepts are illustrated through the analysis of Gaussian control systems with randomized strategies, which are equivalent to Additive Gaussian Noise channels, Stable or Unstable, with arbitrary memory on past outputs, with an average constraint of quadratic form. It is shown that such unstable dynamical systems have Control-Coding Capacity which is operational, precisely as in Shannon's operational definition. However, the control-coding capacity is zero, unless the power κ allocated to the system, exceeds a threshold Kmin, where Kminis the minimum cost of ensuring asymptotic stability and ergodicity. The excess power κ - Kminis turned into an achievable rate of information transmission over the dynamical system.

For a class of channels with unit memory on previous channels outputs, we identify necessary and sufficient conditions, to test whether the capacity achieving channel input distributions with feedback are time-invariant, and whether feedback capacity is characterized by a two-letter expression, similar to that of memoryless channels. The method is based on showing that a certain dynamic programming equation, which in general, is a nested optimization problem over the sequence of channel input distributions, reduces to a non-nested optimization problem. We then apply these conditions to derive a two-letter expression for the feedback capacity of the Binary State Symmetric Channel, which is evaluated explicitly. Further, we derive computationally efficient upper bounds on the probability of maximum likelihood decoding error in the finite-blocklength regime.

We derive sequential necessary and sufficient conditions for any channel input conditional distribution P0,n=Δ{PXt|Xt-1,Yt-1: t = 0, ..., n} to maximize the finite-time horizon directed information defined by CXn→YnFB =ΔsupP0,nI(Xn→ Yn), where I(Xn→ Yn) = Σt=0nI(Xt; Yt|Yt-1), for channel distributions {PYt|Yt-1,Xt: t = 0, ..., n} and {PYt|Yt-Mt-1,Xt: t = 0, ..., n}, where Yt =Δ{Y-1, Y0, ..., Yt} and Xt =Δ{X0, ..., Xt} are the channel input and output random processes, and M is a finite non-negative integer. We apply the necessary and sufficient conditions to application examples of time-varying channels with memory to derive recursive closed form expressions of the optimal distributions, which maximize the finite-time horizon directed information. Furthermore, we derive the feedback capacity from the asymptotic properties of the optimal distributions by investigating the limit CX∞→Y∞FB =Δlimn→∞(1/(n + 1))CXn→YnFBwithout any á priori assumptions, such as stationarity, ergodicity, or irreducibility of the channel distribution. The framework based on sequential necessary and sufficient conditions can be easily applied to a variety of channels with memory, beyond the ones considered in this paper.

The information structures of the optimal channel input distributions P[0,n]=Δ{PAi|Ai-1, Bi-1: i = 0,1,..., n}, which correspond to the extremum problem of feedback capacity CAn→BnFB=Δsup P[0,n]Σi=0nI(Ai;Bi|Bi-1) are identified, for any class of channel distributions {PBi|Bi-1,Ai: i = 0,1,...,n} and {PBi|Bi-Mi-1,Ai: i = 0,1,...,n}, where Bn=Δ{Bj: j = 0,1,...,n} are the channel output RVs, An=Δ{Aj: j = 0,1,...,n} are the channel inputs RVs, and M is a finite nonnegative integer. The methodology utilizes stochastic optimal control theory, to identify the control process, the controlled process, and a variational equality of directed information, to derive upper bounds on I(An→ Bn)=ΔΣi=0nI(Ai;Bi|Bi-1), which are achievable over specific subsets of P[0,n], which satisfy conditional independence. The main theorem states, that for any channel with memory M, the optimal channel input conditional distribution occur in the subset P[0,n]=Δ{PAi|Bi-Mi-1: i = 1,...,n} ⊂ P[0,n], and the corresponding extremum problem simplifies to the following characterization CAn→BnFB,M=Δsup P[0,n]Σi=0nI(Ai;Bi|Bi-Mi-1).

We derive Sequential Necessary and Sufficient Conditions (SNSC) for any channel input distribution P0,n=̑{P((Xt)|Xt-1,Yt-1):t=0,1,...,n} to maximize directed information for channel distributions of the form {P(Yt|Yt-Mt-1,xt): t=0,1,...,n} where Xn=̑{X0...,Xn} , and Yn=̑{Y0,...,Yn} are the channel input and output random variables, and M is nonnegative and finite. The results are obtained using the information structures of the optimal channel input distributions and the corresponding Finite Transmission Feedback Information (FTFI) capacity, convexity properties of directed information, and dynamic programming recursions. The conditions are applied to a finite alphabet channel with M = 1 to derive recursive closed form expressions for the optimal (nonstationary) distributions, which achieve the FTFI capacity. Further, ergodic feedback capacity is obtained in closed form, using the asymptotic properties of the optimal distributions. A numerical example is presented to illustrate the convergence properties of the per unit time limiting version of the FTFI capacity.

In this paper we analyze nonanticipative (delayless) transmission of source symbols with memory over channels with memory (with and without feedback). We employ duality of {source, channel} pairs with respect to {distortion function, transmission cost} pairs to show achievability of nonanticipative transmission in terms of excess distortion probability. We apply the method to the Binary Markov source with Hamming distortion function and the Binary Unit Memory channel with transmission cost, with the joint-design operating optimally and in real-time, with and without feedback encoding and decoding.

We consider a unit memory channel, called Binary State Symmetric Channel (BSSC), in which the channel state is the modulo2 addition of the current channel input and the previous channel output. We derive closed form expressions for the capacity and corresponding channel input distribution for the BSSC with and without feedback and transmission cost. We also show that the capacity of the BSSC, with or without feedback, is achieved by a first order symmetric Markov process.

The objective of this paper is to further investigate various applications of information Nonanticipative Rate Distortion Function (NRDF) by discussing two working examples, the Binary Symmetric Markov Source with parameter p (BSMS(p)) with Hamming distance distortion, and the multidimensional partially observed Gaussian-Markov source. For the BSMS(p), we give the solution to the NRDF, and we use it to compute the Rate Loss (RL) of causal codes with respect to noncausal codes. For the multidimensional Gaussian-Markov source, we give the solution to the NRDF, we show its operational meaning via joint source-channel matching over a vector of parallel Gaussian channels, and we compute the RL of causal and zero-delay codes with respect to noncausal codes.