Feedback Capacity of Stationary Gaussian Channels

The feedback capacity of additive stationary Gaussian noise channels is characterized as the solution to a variational problem in the noise power spectral density. When specialized to the first-order autoregressive moving-average noise spectrum, this variational characterization yields a closed-form expression for the feedback capacity. In particular, this result shows that the celebrated Schalkwijk-Kailath coding achieves the feedback capacity for the first-order autoregressive moving-average Gaussian channel, positively answering a long-standing open problem studied by Butman, Tiernan-Schalkwijk, Wolfowitz, Ozarow, Ordentlich, Yang-Kavc?ic?-Tatikonda, and others. More generally, it is shown that a k-dimensional generalization of the Schalkwijk-Kailath coding achieves the feedback capacity for any autoregressive moving-average noise spectrum of order k. Simply put, the optimal transmitter iteratively refines the receiver's knowledge of the intended message. This development reveals intriguing connections between estimation, control, and feedback communication.     

On the Feedback Capacity of Power-Constrained Gaussian Noise Channels With Memory

For a stationary additive Gaussian-noise channel with a rational noise power spectrum of a finite-order L, we derive two new results for the feedback capacity under an average channel input power constraint. First, we show that a very simple feedback-dependent Gauss-Markov source achieves the feedback capacity, and that Kalman-Bucy filtering is optimal for processing the feedback. Based on these results, we develop a new method for optimizing the channel inputs for achieving the Cover-Pombra block-length- n feedback capacity by using a dynamic programming approach that decomposes the computation into n sequentially identical optimization problems where each stage involves optimizing O(L ²) variables. Second, we derive the explicit maximal information rate for stationary feedback-dependent sources. In general, evaluating the maximal information rate for stationary sources requires solving only a few equations by simple nonlinear programming. For first-order autoregressive and/or moving average (ARMA) noise channels, this optimization admits a closed-form maximal information rate formula. The maximal information rate for stationary sources is a lower bound on the feedback capacity, and it equals the feedback capacity if the long-standing conjecture, that stationary sources achieve the feedback capacity, holds     

Decorrelation of Wavelet Coefficients for Long-Range Dependent Processes

We consider a discrete-time stationary long-range dependent process (X_k)_kisinZ such that its spectral density equals phi(|lambda|)^-2d, where phi is a smooth function such that phi(0)=phi'(0)=0 and phi(lambda)gesclambda for lambdaisin[0,pi]. Then for any wavelet psi with N vanishing moments, the lag k within-level covariance of wavelet coefficients decays as O(k^2d-2N-1) when krarrinfin. The result applies to fractionally integrated autoregressive moving average (ARMA) processes as well as to fractional Gaussian noise     

Feedback coding schemes for an additive noise channel with a noisy feedback link

A coding scheme for an additive Gaussian channel is developed using a noisy feedback link andD-dimensional elementary signals with no bandwidth constraint. This allows error-free transmission at a rateR < R_{c}whereR_{c}is slightly less than the channel capacityC. When there is no noise in the feedback channel, the coding scheme reduces to aD-dimensional generalization of the coding scheme of Schalkwijk and Kailath. In addition, the expression for the probability of error is determined whenT, the time of transmission rate, is finite. The scheme is also compared with the best codes that use only the forward channel.     

Bounds on the information rate of intertransition-time-restrictedbinary signaling over an AWGN channel

Upper and lower bounds on the capacity of a continuous-time additive white Gaussian noise (AWGN) channel with bilevel (±√P) input signals subjected to a minimum inter-transition time (T_min) constraint are derived. The channel model and input constraints reflect basic features of certain magnetic recording systems. The upper bounds are based on Duncan's relation between the average mutual information in an AWGN regime and the mean-square error (MSE) of an optimal causal estimator. Evaluation or upper-bounding the MSE of suboptimal causal estimators yields the desired upper bounds. The lower bound is found by invoking the extended “Mrs. Gerber's” lemma and asymptotic properties of the entropy of max-entropic bipolar (d, k) codes. Asymptotic results indicate that at low SNR=PT_min/N₀, with N₀ designating the noise one-sided power spectral density, the capacity tends to P/N ₀ nats per second (nats/s), i.e., it equals the capacity in the simplest average power limited case. At high SNR, the capacity in the simplest average power limited case. At high SNR, the capacity behaves asymptotically as T_min^-1ln(SNR/ln(SNR)) (nats/s), demonstrating the degradation relatively to T_avg ^-1 lnSNR, which is the asymptotic known behavior of the capacity with a bilevel average intertransition-time (T_avg) restricted channel input. Additional lower bounds are obtained by considering specific signaling formats such as pulsewidth modulation. The effect of mild channel filtering on the lower bounds on capacity is also addressed, and novel techniques to lower-bound the capacity in this case are introduced     

Adaptive recovery of a chirped signal using the RLS algorithm

This paper studies the performance of the recursive least squares (RLS) algorithm in the presence of a general chirped signal and additive white noise. The chirped signal, which is a moving average (MA) signal deterministically shifted in frequency at rate ψ, can be used to model a frequency shift in a received signal. General expressions for the optimum Wiener-Hopf coefficients, one-step recovery and estimation errors, noise and lag misadjustments, and the optimum adaptation constant (β_opt) are found in terms of the parameters of the stationary MA signal. The output misadjustment is shown to be composed of a noise (ξ₀Mβ/2) and lag term (κ/(β²ψ²)), and the optimum adaptation constant is proportional to the chirp rate as ψ^2/3 . The special case of a chirped first-order autoregressive (AR1) process with correlation (α) is used to illustrate the effect the bandwidth (1/α) of the chirped signal on the adaptation parameters. It is shown that unlike for the chirped tone, where the β_opt increases with the filter length (M), the adaptation constant reaches a maximum for M near the inverse of the signal correlation (1/α). Furthermore, there is an optimum filter length for tracking the chirped signal and this length is less than (1/α)     

Erasure, list, and detection zero-error capacities for low noiseand a relation to identification

For the discrete memoryless channel (χ, y, W) we give characterizations of the zero-error erasure capacity C_er and the zero-error average list size capacity C_al in terms of limits of suitable information (respectively, divergence) quantities (Theorem 1). However, they do not “single-letterize.” Next we assume that χ⊂y and W(x|x)>0 for all x∈χ, and we associate with W the low-noise channel W_ϵ, where for y ⁺(x)={y:W(y|x)>0} W_ϵ(y|x)={1, if y=x and |y⁺(x)|=1 1-ϵ, if y=x and |y⁺(x)|>1 e/|y ⁺(x)|-1, if y≠x. Our Theorem-2 says that as ε tends to zero the capacities C_er(W_ε) and C_al (W_ε) relate to the zero-error detection capacity C _de(W). Our third result is a seemingly basic contribution to the theory of identification via channels. We introduce the (second-order) identification capacity C_oid for identification codes with zero misrejection probability and misacceptance probability tending to zero. Our Theorem 3 says that C_oid equals the zero-error erasure capacity for transmission C_er     

A parametric modeling of ionic channel current fluctuations usingthird-order statistics and its application to estimation of the kineticparameters of single ionic channels

The case where third-order cumulants of stationary ionic-channel current fluctuations (SICFs) are nonzero, and where SICFs are corrupted by an unobservable additive colored Gaussian noise that is independent of SICFs is considered. First, a virtual synthesizer that yields an output whose third-order cumulants are equivalent to those of SICFs on a specific slice is constructed. The synthesizer output is expressed by the sum of N_s-1 first-order differential equation systems, where N_s denotes the number of states of single ionic channels. Next, discretizing the synthesizer output, a discrete autoregressive [AR(N_s-1)] process driven by the sum of N_s-1 moving average (MA(N_s -2)) processes is derived. Then the AR coefficients are explicitly related to the kinetic parameters of single ionic channels, implying that the kinetic parameters can be estimated by identifying the autoregressive moving-average coefficients using the third-order cumulants. In order to assess the validity of the proposed modeling and the accuracy of parameter estimates, Monte Carlo simulation is carried out in which the closed-open and closed-open-blocked schemes are treated as specific examples     

Constellations matched to the Rayleigh fading channel

We introduce a new technique for designing signal sets matched to the Rayleigh fading channel, In particular, we look for n-dimensional (n⩾2) lattices whose structure provides nth-order diversity. Our approach is based on a geometric formulation of the design problem which in turn can be solved by using a number-geometric approach. Specifically, a suitable upper bound on the pairwise error probability makes the design problem tantamount to the determination of what is called a critical lattice of the body S={x=(x₁, ···, x_n)∈Rⁿ, |Π_i=1ⁿx_i|⩽1}. The lattices among which we search for an optimal solution are the standard embeddings in R ⁿ of the number ring of some totally real number field of degree n over Q. Simulation results confirm that this approach yields lattices with considerable coding gains     

On the Schalkwijk-Kailath coding scheme with a peak energy constraint

In a recent series of papers, [2]-[4] Schalkwijk and Kailath have proposed a block coding scheme for transmission over the additive white Gaussian noise channel with one-sided spectral densityN_{0}using a noiseless delayless feedback link. The signals have bandwidthW (W leq infty)and average powerbar{P}. They show how to communicate at ratesR < C = W log (1 + bar{P}/N_{0}W), the channel capacity, with error probabilityP_{e} = exp {-e^{2(C-R)T+o(T)}}(whereTis the coding delay), a "double exponential" decay. In their scheme the signal energy (in aT-second transmission) is a random variable with only its expectation constrained to bebar{P}T. In this paper we consider the effect of imposing a peak energy constraint on the transmitter such that whenever the Schalkwijk-Kailath scheme requires energy exceeding abar{P}T(wherea > 1is a fixed parameter) transmission stops and an error is declared. We show that the error probability is degraded to a "single exponential" formP_{e} = e^{-E(a)T+o(T)}and find the exponentE(a). In the caseW = infty , E(a) = (a - 1)^{2}/4a C. For finiteW, E(a)is given by a more complicated expression.     

Non white Gaussian multiple access channels with feedback

Although feedback does not increase the capacity of an additive white noise Gaussian channel, it enables prediction of the noise for non-white additive Gaussian noise channels and results in an improvement of capacity, but at most by a factor of 2 (Pinsker, Ebert, Pombra, and Cover). Although the capacity of white noise channels cannot be increased by feedback, multiple access white noise channels have a capacity increase due to the cooperation induced by feedback. Thomas has shown that the total capacity (sum of the rates of all the senders) of an m-user Gaussian white noise multiple access channel with feedback is less than twice the total capacity without feedback. The present authors show that this factor of 2 bound holds even when cooperation and prediction are combined, by proving that feedback increases the total capacity of an m-user multiple access channel with non-white additive Gaussian noise by at most a factor of 2     

The Cost of Uncorrelation and Noncooperation in MIMO Channels

We investigate the capacity loss for using uncorrelated Gaussian input over a multiple-input multiple-output (MIMO) linear additive-noise channel. We upper-bound the capacity loss by a universal constant C* which is independent of the channel matrix and the noise distribution. For a single-user MIMO channel with n_t inputs and n_r outputs C* = min [ 1/2, n_r/n_t log₂ (1+n_t/n_r) ] bit per input dimension (or 2C* bit per transmit antenna per second per hertz), under both total and per-input power constraints. If we restrict attention to (colored) Gaussian noise, then the capacity loss is upper-bounded by a smaller constant C_G = n_r/2n_r log₂ (n_t/n_r) for n_r ges n_t/e, and C_G = 0.265 otherwise, and this bound is tight for certain cases of channel matrix and noise covariance. We also derive similar bounds for the sum-capacity loss in multiuser MIMO channels. This includes in particular uncorrelated Gaussian transmission in a MIMO multiple-access channel (MAC), and "flat" Gaussian dirty-paper coding (DPC) in a MIMO broadcast channel. In the context of wireless communication, our results imply that the benefit of beamforming and spatial water-filling over simple isotropic transmission is limited. Moreover, the excess capacity of a point-to-point MIMO channel over the same MIMO channel in a multiuser configuration is bounded by a universal constant.     

Multivariate regression estimation of continuous-time processesfrom sampled data: local polynomial fitting approach

Let (Y,X)={Y(t),X(t),-∞j) be a renewal point processes on (0,∞), with a finite mean rate, independent of (Y,X). We consider the estimation of regression function r(x₀, x₁,...,x_m-1; τ₁,...,τ_m) of ψ(Y(τ_m)) given (X(0)=x₀, X(τ₁)=x₁,...,X(τ_m-1)=_x-1 ) for arbitrary lags 0<τ₁<...< τ_m on the basis of the discrete-time observations {Y(t_j),X(t_j),t_j)_j=1ⁿ . We estimate the regression function and all its partial derivatives up to a total order p⩾1 using high-order local polynomial fitting. We establish the weak consistency of such estimates along with rates of convergence. We also establish the joint asymptotic normality of the estimates for the regression function and all its partial derivatives up to a total order p⩾1 and provide explicit expressions for the bias and covariance matrix (of the asymptotically normal distribution)     

The capacity of the physically degraded Gaussian broadcast channel with feedback (Corresp.)

Bounds on the output entropy of the additive white Gaussian noise (AWGN) channel with feedback are used to prove that the capacity of the degraded additive white Gaussian noise (DAWGN) broadcast channel is not increased by feedback.     

Low-Density Lattice Codes

Low-density lattice codes (LDLC) are novel lattice codes that can be decoded efficiently and approach the capacity of the additive white Gaussian noise (AWGN) channel. In LDLC a codeword x is generated directly at the n-dimensional Euclidean space as a linear transformation of a corresponding integer message vector b, i.e., x = Gb^-1, where H = G^-1 is restricted to be sparse. The fact that H is sparse is utilized to develop a linear-time iterative decoding scheme which attains, as demonstrated by simulations, good error performance within ~0.5 dB from capacity at block length of n =100,000 symbols. The paper also discusses convergence results and implementation considerations.     

Universal schemes for learning the best nonlinear predictor giventhe infinite past and side information

Let {X_t} be a real-valued time series. The best nonlinear predictor of X₀ given the infinite past X_-∞^-1 in the least squares sense, is equal to the conditional mean E{X₀|X_-∞^-1}. Previously, it has been shown that certain predictors based on growing segments of past observations converge to the best predictor given the infinite past whenever {X_t} is a stationary process with values in a bounded interval. The present paper deals with universal prediction schemes for stationary processes with finite mean. We also discuss universal schemes for learning the conditional mean E{X₀|X _-∞^-1Y_-∞^-1Y₀ } from past observations of a stationary pair process {(X_t , Y_t)}, and schemes for learning the repression function m(y)=E{X|Y=y} from independent samples of (X, Y)     

Threshold detection in correlated non-Gaussian noise fields

Classical threshold detection theory for arbitrary noise and signals, based on independent noise samples, i.e., using only the first-order probability density of the noise, is generalized to include the critical additional statistical information contained in the (first-order) covariances of the noise. This is accomplished by replacing the actual, generalized noise by a “quasi-equivalent” (QE-)model employing both the first-order PDF and covariance. The result is a “near-optimum” approach, which is the best available to date incorporating these fundamental statistical data. Space-time noise and signal fields are specifically considered throughout. Even with additive white Gaussian noise (AWGN) worthwhile processing gains per sample (Γ^(c)) are attainable, often O(10-20 dB), over the usual independent sampling procedures, with corresponding reductions in the minimum detectable signal. The earlier moving average (MA) noise model, while not realistic, is included because it reduces in the Gaussian noise cases to the threshold optimum results of previous analyses, while the QE-model remains suboptimum here because of the necessary constraints imposed in combining the PDF and covariance information into the detector structure. Full space-time formulation is provided in general, with the important special cases of adaptive and preformed beams in reception. The needed (first-order) PDF here is given by the canonical Class A and Class B noise models. The general analysis, including the canonical threshold algorithms, correlation gain factors Γ^(c), detection parameters for the QE-model, along with some representative numerical results for both coherent and incoherent detection, based on four representative Toeplitz covariance models is presented     

Feedback Capacity of the Compound Channel

In this work, we find the capacity of a compound finite-state channel (FSC) with time-invariant deterministic feedback. We consider the use of fixed length block codes over the compound channel. Our achievability result includes a proof of the existence of a universal decoder for the family of FSCs with feedback. As a consequence of our capacity result, we show that feedback does not increase the capacity of the compound Gilbert-Elliot channel. Additionally, we show that for a stationary and uniformly ergodic Markovian channel, if the compound channel capacity is zero without feedback then it is zero with feedback. Finally, we use our result on the FSC to show that the feedback capacity of the memoryless compound channel is given by inf_thetas max_QX I(X; Y |thetas).     

Gaussian feedback capacity

The capacity of time-varying additive Gaussian noise channels with feedback is characterized. Toward this end, an asymptotic equipartition theorem for nonstationary Gaussian processes is proved. Then, with the aid of certain matrix inequalities, it is proved that the feedback capacity C_FB in bits per transmission and the nonfeedback capacity C satisfy C⩽C_FB ⩽2C and C⩽C_FB⩽ C+1/2     

An Algorithm for Universal Lossless Compression With Side Information

This paper proposes a new algorithm based on the Context-Tree Weighting (CTW) method for universal compression of a finite-alphabet sequence x₁ ⁿ with side information y₁ ⁿ available to both the encoder and decoder. We prove that with probability one the compression ratio converges to the conditional entropy rate for jointly stationary ergodic sources. Experimental results with Markov chains and English texts show the effectiveness of the algorithm