On the capacity-achieving distribution of the discrete-time noncoherent and partially coherent AWGN channels

We investigate the communication limits over rapid phase-varying channels and consider the capacity of a discrete- time noncoherent additive white Gaussian noise (NCAWGN) channel under the average power constraint. We obtain necessary and sufficient conditions for the capacity-achieving input distribution and show that this distribution is discrete and possesses an infinite number of mass points. Using this characterization of the capacity-achieving distribution we compute a tight lower bound on the capacity of the channel based on examining suboptimal input distributions. In addition, we provide some easily computable lower and upper bounds on the channel capacity. Finally, we extend some of these results to the partially coherent channel, where it is assumed that a phase-locked loop (PLL) is used to track the carrier phase at the receiver, and that an ideal interleaver and de-interleaver are employed-rendering the Tikhonov distributed residual phase errors statistically independent from one symbol interval to another.     

Capacity-achieving probability measure for conditionally Gaussian channels with bounded inputs

A conditionally Gaussian channel is a vector channel in which the channel output, given the channel input, has a Gaussian distribution with (well-behaved) input-dependent mean and covariance. We study the capacity-achieving probability measure for conditionally Gaussian channels subject to bounded-input constraints and average cost constraints. Many practical communication systems, including additive Gaussian noise channels, certain optical channels, fading channels, and interference channels fall within this framework. Subject to bounded-input constraint (and average cost constraints), we show that the channel capacity is achievable and we derive a necessary and sufficient condition for a probability measure to be capacity achieving. Under certain conditions, the capacity-achieving measure is proved to be discrete.     

Error Exponents for Channel Coding With Application to Signal Constellation Design

This paper concerns error exponents and the structure of input distributions maximizing the random coding exponent for a stochastic channel model. The following conclusions are obtained under general assumptions on the channel statistics. 1) The optimal distribution has a finite number of mass points, or in the case of a complex channel, the amplitude has finite support. 2) A new class of algorithms is introduced based on the cutting-plane method to construct an optimal input distribution. The algorithm constructs a sequence of discrete distributions, along with upper and lower bounds on the random coding exponent at each iteration. 3) In some numerical example considered, the resulting code significantly outperforms traditional signal constellation schemes such as quadrature amplitude modulation and phase-shift keying for all rates below the capacity.     

Feedback capacity of finite-state machine channels

We consider a finite-state machine channel with a finite memory length (e.g., finite length intersymbol interference channels with finite input alphabets-also known as partial response channels). For such a finite-state machine channel, we show that feedback-dependent Markov sources achieve the feedback capacity, and that the required memory length of the Markov process matches the memory length of the channel. Further, we show that the whole history of feedback is summarized by the causal posterior channel state distribution, which is computed by the sum-product forward recursion of the Bahl-Cocke-Jelinek-Raviv (BCJR) (Baum-Welch, discrete-time Wonham filtering) algorithm. These results drastically reduce the space over which the optimal feedback-dependent source distribution needs to be sought. Further, the feedback capacity computation may then be formulated as an average-reward-per-stage stochastic control problem, which is solved by dynamic programming. With the knowledge of the capacity-achieving source distribution, the value of the capacity is easily estimated using Markov chain Monte Carlo methods. When the feedback is delayed, we show that the feedback capacity can be computed by similar procedures. We also show that the delayed feedback capacity is a tight upper bound on the feedforward capacity by comparing it to tight existing lower bounds. We demonstrate the applicability of the method by computing the feedback capacity of partial response channels and the feedback capacity of run-length-limited (RLL) sequences over binary symmetric channels (BSCs).     

Zero-Rate Feedback Can Achieve the Empirical Capacity

The utility of limited feedback for coding over an individual sequence of discrete memoryless channels is investigated. This study complements recent results showing how limited or noisy feedback can boost the reliability of communication. A strategy with fixed input distribution P is given that asymptotically achieves rates arbitrarily close to the mutual information induced by P and the state-averaged channel. When the capacity-achieving input distribution is the same over all channel states, this achieves rates at least as large as the capacity of the state-averaged channel, sometimes called the empirical capacity.     

Complexity versus performance of capacity-achieving irregular repeat-accumulate codes on the binary erasure channel

We derive upper and lower bounds on the encoding and decoding complexity of two capacity-achieving ensembles of irregular repeat-accumulate (IRA1 and IRA2) codes on the binary erasure channel (BEC). These bounds are expressed in terms of the gap between the channel capacity and the rate of a typical code from this ensemble for which reliable communications is achievable under message-passing iterative (MPI) decoding. The complexity of the ensemble of IRA1 codes grows like the negative logarithm of the gap to capacity. On the other hand, the complexity of the ensemble of IRA2 codes with any choice of the degree distribution grows at least like the inverse square root of the gap to capacity, and at most like the inverse of the gap to capacity.     

Capacity and coding for the block-independent noncoherent AWGN channel

Communication over the noncoherent additive white Gaussian noise (AWGN) channel is considered, where the transmitted signal undergoes a phase rotation, unknown to the transmitter and the receiver. The effects of phase dynamics are explicitly taken into account by considering a block-independent model for the phase process: the unknown phase is constant for a block of N complex symbols and independent from block to block. In the first part of the paper, the capacity-achieving input distribution is characterized. In particular, it is shown that the maximizing density has circular symmetry, is discrete in amplitude with infinite number of mass points, and always has a mass point at zero. Furthermore, asymptotic expressions and bounds for the capacity are derived. Based on these results, the capacity is evaluated through numerical optimizations for unconstrained and modulation-constrained input distributions. In the second part of this paper, inspired by the capacity results, two classes of coding and modulation schemes are proposed for fast and moderate phase dynamics. In the case of fast phase dynamics (i.e., small N), optimized modulation alphabets are designed having exponential complexity with N at the demodulator. In the case of moderate phase dynamics (i.e., moderate values of N), specially designed modulation alphabets are utilized that have linear complexity with N. These alphabets are used together with optimized irregular low-density parity-check (LDPC) codes. Simulation results show that these codes can achieve close-to-capacity performance with moderate complexity, and outperform the best known codes so far.     

On the capacity of the blockwise incoherent MPSK channel

The capacity of M-ary phase-shift keying (MPSK) over an additive white Gaussian noise (AWGN) channel with carrier phase unknown but constant over L symbols is investigated. It is shown that capacity-achieving channel inputs are uniformly distributed and independent MPSK symbols. Capacity over a range of signal-to-noise ratio (SNR) and L is presented for binary phase-shift keying (BPSK) and quaternary phase-shift keying (QPSK). Upper and lower easy-to-compute bounds on capacity are derived. It is proven that for large L the coherent capacity is approached. An analytic asymptotic expression for low L·SNR is derived exhibiting the expected quadratic dependence on the SNR     

Capacity Regions and Bounds for a Class of Z-Interference Channels

We define a class of Z-interference channels for which we obtain a new upper bound on the capacity region. The bound exploits a technique first introduced by Korner and Marton. A channel in this class has the property that, for the transmitter-receiver pair that suffers from interference, the conditional output entropy at the receiver is invariant with respect to the transmitted codewords. We compare the new capacity region upper bound with the Han/Kobayashi achievable rate region for interference channels. This comparison shows that our bound is tight in some cases, thereby yielding specific points on the capacity region as well as sum capacity for certain Z-interference channels. In particular, this result can be used as an alternate method to obtain sum capacity of Gaussian Z-interference channels. We then apply an additional restriction on our channel class: the transmitter-receiver pair that suffers from interference achieves its maximum output entropy with a single input distribution irrespective of the interference distribution. For these channels, we show that our new capacity region upper bound coincides with the Han/Kobayashi achievable rate region, which is therefore capacity-achieving. In particular, for these channels superposition encoding with partial decoding is shown to be optimal and a single-letter characterization for the capacity region is obtained.     

Capacity Achieving LDPC Codes Through Puncturing

The performance of punctured low-definition parity-check (LDPC) codes under maximum-likelihood (ML) decoding is studied in this correspondence via deriving and analyzing their average weight distributions (AWDs) and the corresponding asymptotic growth rate of the AWDs. In particular, it is proved that capacity-achieving codes of any rate and for any memoryless binary-input output-symmetric (MBIOS) channel under ML decoding can be constructed by puncturing some original LDPC code with small enough rate. Moreover, it is shown that the gap to capacity of all the punctured codes can be the same as the original code with a small enough rate. Conditions under which puncturing results in no rate loss with asymptotically high probability are also given in the process. These results show high potential for puncturing to be used in designing capacity-achieving codes, and in rate-compatible coding under any MBIOS channel.      

Channel capacity and non-uniform signalling for free-space optical intensity channels

This work considers the design of capacityapproaching, non-uniform optical intensity signalling in the presence of average and peak amplitude constraints. Although it is known that the capacity-achieving input distribution is discrete with a finite number of mass points, finding it requires complex non-linear optimization at every SNR. In this work, a simple expression for a capacity-approaching distribution is derived via source entropy maximization. The resulting mutual information using the derived discrete non-uniform input distribution is negligibly far away from the channel capacity. The computation of this distribution is substantially less complex than previous optimization approaches and can be easily computed at different SNRs. A practical algorithm for non-uniform optical intensity signalling is presented using multi-level coding followed by a mapper and multi-stage decoding at the receiver. The proposed signalling is simulated on free-space optical channels and outage capacity is analyzed. A significant gain in both rate and probability of outage is achieved compared to uniform signalling, especially in the case of channels corrupted by fog.     

On the discreteness of capacity-achieving distributions

We consider a scalar additive channel x /spl rarr/ x + N whose input is amplitude constrained. By extending Smith's (1969) argument, we derive a sufficient condition on noise probability density functions (pdf) that guarantee finite support for the associated capacity-achieving distribution(s).     

Capacity-achieving input covariance for single-user multi-antenna channels

We characterize the capacity-achieving input covariance for multi-antenna channels known instantaneously at the receiver and in distribution at the transmitter. Our characterization, valid for arbitrary numbers of antennas, encompasses both the eigenvectors and the eigenvalues. The eigenvectors are found for zero-mean channels with arbitrary fading profiles and a wide range of correlation and keyhole structures. For the eigenvalues, in turn, we present necessary and sufficient conditions as well as an iterative algorithm that exhibits remarkable properties: universal applicability, robustness and rapid convergence. In addition, we identify channel structures for which an isotropic input achieves capacity.     

On the throughput, capacity, and stability regions of random multiple access

This paper studies finite-terminal random multiple access over the standard multipacket reception (MPR) channel. We characterize the relations among the throughput region of random multiple access, the capacity region of multiple access without code synchronization, and the stability region of ALOHA protocol. In the first part of the paper, we show that if the MPR channel is standard, the throughput region of random multiple access is coordinate convex. We then study the information capacity region of multiple access without code synchronization and feedback. Inner and outer bounds to the capacity region are derived. We show that both the inner and the outer bounds converge asymptotically to the throughput region. In the second part of the paper, we study the stability region of finite-terminal ALOHA multiple access. For a class of packet arrival distributions, we demonstrate that the stationary distribution of the queues possesses positive and strong positive correlation properties, which consequently yield an outer bound to the stability region. We also show the major challenge in obtaining the closure of the stability region is due to the lack of sensitivity analysis results with respect to the transmission probabilities. Particularly, if a conjectured "sensitivity monotonicity" property held for the stationary distribution of the queues, then equivalence between the closure of the stability region and the throughput region follows as a direct consequence, irrespective of the packet arrival distributions.     

Capacity of RAKE reception with energy randomization

We consider a RAKE receiver for coherent binary orthogonal signaling over a frequency selective multipath Rayleigh fading channel. The receiver uses maximal-ratio combining such that the weight estimation errors are not independent of the additive noise. We find the capacity-achieving energy randomization scheme with two energy levels for the cases of imperfect and perfect channel estimates. We observe that the capacity-achieving probability gets closer to 1/2 with increase in the number of paths. We also show that the capacity is higher if channel estimates are perfect and that the channel estimation errors have more pronounced effect on the capacity at low signal-to-noise ratios.     

A Generalization of the Blahut–Arimoto Algorithm to Finite-State Channels

The classical Blahut-Arimoto algorithm (BAA) is a well-known algorithm that optimizes a discrete memoryless source (DMS) at the input of a discrete memoryless channel (DMC) in order to maximize the mutual information between channel input and output. This paper considers the problem of optimizing finite-state machine sources (FSMSs) at the input of finite-state machine channels (FSMCs) in order to maximize the mutual information rate between channel input and output. Our main result is an algorithm that efficiently solves this problem numerically; thus, we call the proposed procedure the generalized BAA. It includes as special cases not only the classical BAA but also an algorithm that solves the problem of finding the capacity-achieving input distribution for finite-state channels with no noise. While we present theorems that characterize the local behavior of the generalized BAA, there are still open questions concerning its global behavior; these open questions are addressed by some conjectures at the end of the paper. Apart from these algorithmic issues, our results lead to insights regarding the local conditions that the information-rate-maximizing FSMSs fulfill; these observations naturally generalize the well-known Kuhn-Tucker conditions that are fulfilled by capacity-achieving DMSs at the input of DMCs.     

Capacity-achieving probability measure for a reduced number of signaling points

Putting bounding constraints on the input of a channel leads in many cases to a discrete capacity-achieving distribution with a finite support. Given a finite number of signaling points, we determine reduced subsets and the corresponding optimal probability measures to simplify the receiver design. The objective for the subset selection is to keep the channel quality high by maximizing mutual information and cutoff rate. Two approaches are introduced to obtain a capacity-achieving probability measure for the reduced subset. The first one is based on a preceded signaling point selection while the second one chooses the signaling points and corresponding probabilities simultaneously. Numerical results for both approaches show that using only a small number of signaling points achieves a very high mutual information compared to channels utilizing the full set of signaling points.     

Resolvability theory for the multiple-access channel

We study the randomness needed for approximating the output distribution of a multiple-access channel, where the original input processes are independent of each other. The approximation is achieved by simulating (possibly alternative) input processes at each of the entries, where the sources of randomness available for the simulators are independent of each other, and the simulators do not cooperate. The resolvability region of a multiple-access channel is defined as the set of all random-bit rate pairs at which accurate output approximation is possible, where the simulation accuracy is measured by the variational distance between finite-dimensional output distributions. Inner and outer bounds on the resolvability region are derived, and close relations between the concepts of resolvability region and capacity region are demonstrated     

Capacity-achieving input distributions for some amplitude-limited channels with additive noise (Corresp.)

An additive noise channel wherein the noise is described by a piecewise constant probability density is shown to reduce to a discrete channel by means of an explicit construction. In addition, conditions are found which describe a class of continuous amplitude-limited channels for which the capacity-achieving input distribution is binary.     

Resource Allocation for Wireless Fading Relay Channels: Max-Min Solution

Resource allocation is investigated for fading relay channels under separate power constraints at the source and relay nodes. As a basic information-theoretic model for fading relay channels, the parallel relay channel is first studied, which consists of multiple independent three-terminal relay channels as subchannels. Lower and upper bounds on the capacity are derived, and are shown to match, and thus establish the capacity for the parallel relay channel with degraded subchannels. This capacity theorem is further demonstrated via the Gaussian parallel relay channel with degraded subchannels, for which the synchronized and asynchronized capacities are obtained. The capacity-achieving power allocation at the source and relay nodes among the subchannels is partially characterized for the synchronized case and fully characterized for the asynchronized case. The fading relay channel is then studied, which is based on the three-terminal relay channel with each communication link being corrupted by a multiplicative fading gain coefficient as well as an additive Gaussian noise term. For each link, the fading state information is assumed to be known at both the transmitter and the receiver. The source and relay nodes are allowed to allocate their power adaptively according to the instantaneous channel state information. The source and relay nodes are assumed to be subject to separate power constraints. For both the full-duplex and half-duplex cases, power allocations that maximize the achievable rates are obtained. In the half-duplex case, the power allocation needs to be jointly optimized with the channel resource (time and bandwidth) allocation between the two orthogonal channels over which the relay node transmits and receives. Capacities are established for fading relay channels that satisfy certain conditions.