The capacity of a state-dependent discrete memoryless channel is derived for the setting where a message-cognizant rate-limited helper observes the state sequence noncausally and provides its description to both encoder and decoder. Said capacity is not increased if the channel outputs are fed back to the encoder via a noiseless feedback link. The analogous capacity is derived for the Gaussian channel, where the state corresponds to the additive noise. In this setting the feedback link—while not increasing capacity—eliminates the need for the helper’s cognition of the transmitted message. Moreover, in this setting, the results on capacity also hold for the cutoff rate and the listsize capacity.

A formula is derived for the capacity of the Gaus-sian channel with a message-cognizant rate-limited helper that provides a noncausal description of the noise to the encoder and the decoder. This capacity is strictly larger than when the helper is message oblivious. It is shown that, in this setup, a feedback link from the receiver to the encoder does not increase capacity. However, in the presence of such a link, said capacity can be achieved even if the helper is oblivious to the transmitted message.

The capacity of a memoryless state-dependent chan-nel is derived for a setting in which the encoder is provided with rate-limited assistance from a cribbing helper that observes the state sequence causally and the past channel inputs strictly-causally. Said cribbing may increase capacity but not to the level achievable by a message-cognizant helper.

A memoryless state sequence governing the behavior of a memoryless state-dependent channel is to be described causally to an encoder wishing to communicate over said channel. Given the maximal-allowed description rate, we seek the description that maximizes the Shannon capacity. It is shown that the maximum need not be achieved by a memoryless (symbol-by-symbol) description. Such descriptions are, however, optimal when the receiver is cognizant of the state sequence or when the description is allowed to depend on the message. For other cases, a block-Markov scheme with backward decoding is proposed.

The zero-error helper capacity of the modulo-additive noise channel is studied both in the presence and in the absence of feedback. In its presence, a complete solution of said capacity is provided. In its absence, a solution is provided when the alphabet size is prime. For all other cases, upper and lower bounds are derived, and a necessary and sufficient condition for positivity is provided. Thanks to the help, the zero-error capacity may increase by more than the help’s rate, and it can be positive yet smaller than one bit.

The gain in the Identification Capacity afforded by a rate-limited description of the noise sequence corrupting a modulo-additive noise channel is studied. Both the classical Ahlswede-Dueck version and the Ahlswede-Cai-Ning-Zhang version, which does not allow for missed identifications, are studied. Irrespective of whether the help is provided to the transmitter, to the receiver, or to both—the two capacities coincide and both equal the helper-assisted Shannon capacity.

The zero-error helper capacity of the modulo-additive noise channel is studied both in the presence and in the absence of feedback. In its presence, a complete solution of said capacity is provided. In its absence, a solution is provided when the alphabet size is prime. For all other cases, a necessary and sufficient condition for positivity is provided. Thanks to the help, the zero-error capacity may increase by more than the help’s rate, and it can be positive yet smaller than one bit.

A source sequence is to be guessed with some fidelity based on a rate-limited description of an observed sequence with which it is correlated. The tension between the description rate and the exponential growth rate of the power mean of the required number of guesses is quantified. This can be viewed as the guessing version of the classical indirect-rate-distortion problem of Dobrushin-Tsybakov’62 and Witsenhausen’80. Judicious choices of the correlated sequence, the description rate, and the fidelity criterion recover a number of recent and classical results on guessing. In the context of security, the paper provides conservative estimates on a password’s remaining security after a number of bits from a correlated database have been leaked.

A single-letter expression is provided for the exponential growth rate of the least expected number of guesses required to recover all the sequences produced by correlated memoryless sources when each guess is of a single source sequence, with the source at the guesser's discretion.

The erasures-only capacity, the listsize capacity, and the cutoff rate are computed for the modulo-additive noise channel with a helper. In one scenario the helper provides a rate-limited description of the noise sequence to the decoder and in the other to the encoder. In both scenarios the gains in these capacities thanks to the helper can exceed the helper's rate.

We study the guessing variants of two distributed source coding problems: the Gray-Wyner network and the Slepian-Wolf network. Building on the former, we propose a new definition of the Rényi common information as the least attainable common rate in the Gray-Wyner guessing problem under the no-excess-rate constraint. We then provide a variational characterization of this quantity. In the Slepian-Wolf setting, we follow up the work of Bracher-Lapidoth-Pfister with the case where the expected number of guesses need not converge to one but must be dominated by some given exponential.

Flash helping has recently been shown to be an effective technique for describing additive noise to a decoder. It is shown here to be effective also in assisting the encoder: it achieves the helper capacity on the single-user Gaussian channel, on the multiple-access Gaussian channel, on the Exponential channel, and on the discrete modulo-additive noise channel. Most of the results hold irrespective of whether the helper observes the noise causally or noncausally.

A number of additive noise networks are studied in the presence of a helper that observes the noise and assists the decoder by providing it with a rate-limited description of said noise. It is shown that “flash helping”-where noise descriptions are provided infrequently but with great precision-is often optimal and typically increases capacity by the maximal allowed description rate. It requires no binning. The discrete setting of the modulo-additive noise channel is also discussed.

A coding technique that is based on flash helping is proposed for communicating over additive noise channels where a helper observes the noise and can describe it to the encoder over a noise-free rate-limited bit pipe. The technique is applicable irrespective of whether the helper observes the noise causally or noncausally. On the single-user channel of general noise, the rate it achieves is the sum of the channel's capacity without a helper and the rate of the bit pipe. For Gaussian noise and under an average-power constraint, it is optimal. Analogous results are derived for the additive noise multiple-access channel and the single-user Exponential channel. The approach is applicable also in some (noncausal) discrete settings, as demonstrated on the discrete modulo-additive noise channel.

For gambling on horses, a one-parameter family of utility functions is proposed, which contains Kelly's logarithmic criterion and the expected-return criterion as special cases. The strategies that maximize the utility function are derived, and the connection to the Rényi divergence is shown. Optimal strategies are also derived when the gambler has some side information; this setting leads to a novel conditional Rényi divergence.

Correlated memoryless sources produce a principal and an ancillary sequence. The exponential growth of the least expected total number of guesses required to guess the principal sequence is determined when, prior to guessing it, the guesser is allowed to produce guesses (not necessarily terminating with a correct one) of the ancillary.

The additive noise channel is studied in the presence of a helper who observes the noise and can describe it to the receiver over a rate-limited noise-free bit-pipe. It is shown that the capacity of this network is typically the sum of the capacity of the channel in the absence of the helper and the capacity of the bit-pipe from the helper to the receiver. This holds for finite-variance stationary and ergodic noises under fairly general power-like constraints on the transmitted signal. A helper that is only cognizant of the noise is thus as helpful as an omniscient helper that is cognizant of both the noise and the transmitted message. The achievability proof is based on “flash helping” and requires no binning. Extensions to additive-noise multi-access channels are also discussed.

A Gaussian source and two data streams are to be transmitted over a Gaussian broadcast channel: the first stream, the “common stream,” is to be decoded by both receivers, and the second, the “private stream,” only by the strong receiver. Both receivers wish to estimate the source sequence, though with possibly different mean squared-errors. The quadruples of achievable rates and estimation errors are characterized, and it is shown that-once the data rates have been fixed-there is no tension between the estimation errors. Only the “equal bandwidth” case is treated, where the rate at which the source emits symbols is also the rate at which the channel is used.

The secrecy of a distributed-storage system for passwords is studied. The encoder, Alice, observes a length-$n$password and describes it using two hints, which she stores in different locations. The legitimate receiver, Bob, observes both hints and the eavesdropper, Eve, only one. In one scenario—the “guessing version”—we require that the expected number of guesses it takes Bob to guess the password approach one as$n$tends to infinity, and in the second—the “listsize version”—that the expected size of the shortest list that Bob must form to guarantee that it contain the password approach one. Assuming that Alice cannot control which hint Eve observes, the largest normalized (by$n$) exponent that can be guaranteed for the expected number of guesses it takes Eve to guess the password is characterized for each scenario. Key to the proof are new results on Massey–Arikan guessing, Bunte–Lapidoth task-encoding, and the close relation between them. A generalization that allows for Alice to produce$\delta $(not necessarily two) hints, for Bob to observe$\nu $(not necessarily two) of the hints, and for Eve to observe$\eta $(not necessarily one) of the hints is also discussed. This models scenarios where hints are stored on fail-prone disks.

Two independent data streams are to be transmitted over a noisy discrete memoryless channel with noiseless (ideal) feedback. Errors are tolerated only in the second stream, provided that they occur with vanishing probability. The rate of the error-free stream cannot, of course, exceed the channel's zero-error feedback capacity, and nor can the sum of the streams' rates exceed the channel's Shannon capacity. Using a suitable coding scheme, these necessary conditions are shown to characterize all the achievable rate pairs. Planning for the worst channel behavior-as is needed to achieve zero-error communication-and planning for the typical channel behavior-as is needed to communicate near the Shannon limit-are thus not incompatible. It is further shown that feedback may be beneficial for the multiplexing problem even on channels on which it does not increase the zero-error capacity.

We establish the deterministic-code capacity region of a network with one transmitter and two receivers: an ordinary receiver and a robust receiver. The channel to the ordinary receiver is a given (known) discrete memoryless channel, whereas the channel to the robust receiver is an arbitrarily varying channel. Both receivers are required to decode the common message (the better-protected message), whereas only the ordinary receiver is required to decode the private message (the less-protected message). As in the single-user case, under the appropriate compactness and convexity conditions, the capacity region is either empty or else the intersection of the capacity regions of the broadcast channels that the various states induce.

Three variations on the Massey-Arikan guessing problem are considered. Their solutions provide new evidence of the duality between good guessing functions and efficient quantization schemes. They also show how type-covering can be used to provide side-information in the guessing setup.

To study the fundamental limits on the joint transmission of data of different levels of sensitivity, we establish the deterministic-code capacity region of a network with one transmitter and two receivers: an “ordinary receiver” and a “robust receiver.” The channel to the ordinary receiver is a given (known) discrete memoryless channel, whereas the channel to the robust receiver is an arbitrarily varying channel. Both receivers are required to decode the “common message” (the more sensitive data), whereas only the ordinary receiver is required to decode the “private message” (the less sensitive data).

The achievable error-exponent pairs for the type I and type II errors are characterized in a hypothesis testing setup where the observation consists of independent and identically distributed samples from either a known joint probability distribution or an unknown product distribution. The empirical mutual information test, the Hoeffding test, and the generalized likelihood-ratio test are all shown to be asymptotically optimal. An expression based on a Rényi measure of dependence is shown to be the Fenchel biconjugate of the error-exponent function obtained by fixing one error exponent and optimizing the other. An example is provided where the error-exponent function is not convex and thus not equal to its Fenchel biconjugate.

The zero-error feedback capacity of the Gel'fand-Pinsker channel is established. It can be positive even if the channel's zero-error capacity is zero in the absence of feedback. Moreover, the error-free transmission of a single bit may require more than one channel use. These phenomena do not occur when the state is revealed to the transmitter causally, a case that is solved here using Shannon strategies. Cost constraints on the channel inputs or channel states are also discussed, as is the scenario where-in addition to the message-also the state sequence must be recovered.

The rate-and-state capacity of a state-dependent channel with a state-cognizant encoder is the highest possible rate of communication over the channel when the decoder - in addition to reliably decoding the data - must also reconstruct the state sequence with some required fidelity. Feedback from the channel output to the encoder is shown to increase this capacity even for channels that are memoryless with memoryless states. This capacity is calculated here for such channels with feedback when the state reconstruction fidelity is measured using a single-letter distortion function and the state sequence is revealed to the encoder in one of two different ways: strictly-causally or causally. For the noncausal case, we provide bounds on the capacity and identify a condition under which the bounds coincide. Feedback does not increase the rate-and-state capacity when the decoder must reconstruct the state sequence perfectly or, in some settings, when the channel is Gaussian and fidelity is measured in terms of mean squared-error.

The rate region of the task-encoding problem for two correlated sources is characterized using a novel parametric family of dependence measures. The converse uses a new expression for the ρ-th moment of the list size, which is derived using the relative α-entropy.

Two independent data streams - the “zero-error stream” and the “rare-error stream” - are to be transmitted over a noisy discrete memoryless channel with feedback. Errors are tolerated only in the rare-error stream, provided that their probability tends to zero. Clearly the rate of the error-free stream cannot exceed the channel's zero-error feedback capacity, and the sum of the streams' rates cannot exceed the channel's Shannon capacity. Using a suitable coding scheme, these necessary conditions are shown to characterize all the achievable rate pairs. Planning for the worst - as is needed to achieve zero-error communication - and planning for the true channel - as is needed to communicate near the Shannon limit - are thus not incompatible.

A necessary condition is established for the lossy transmission of correlated sources over a memoryless multiple-access channel (MAC). It is used to derive lower bounds on the symmetric distortions that are achievable over Gaussian and binary adder MACs. When specialized to symmetric Gaussian MACs and Gaussian sources, the new lower bound recovers Lapidoth and Tinguely's max-correlation lower bound (2010) when the channel bandwidth is equal to the source bandwidth, and it improves on it when the channel bandwidth is higher. An analogous condition is also derived for the MAC with correlated sources and feedback.

The identification (ID) capacity region of the two-receiver broadcast channel (BC) is shown to be the set of rate-pairs for which, for some distribution on the channel input, each receiver's ID rate does not exceed the mutual information between the channel input and the channel output that it observes. Moreover, the capacity region's interior is achieved by codes with deterministic encoders. The results are obtained under the average-error criterion, which requires that each receiver reliably identify its message whenever the message intended for the other receiver is drawn at random. They hold also for channels whose transmission capacity region is to-date unknown. Key to the proof is a new ID code construction for the single-user channel. An extension to the three-receiver BC is also discussed: an inner bound on the ID capacity region is obtained, and that is shown to be in some cases tight.

The zero-error feedback capacity of the Gelfand-Pinsker channel is established. It can be positive even if the channel's zero-error capacity is zero in the absence of feedback. Moreover, the error-free transmission of a single bit may require more than one channel use.

The Rate-and-State capacity of a state-dependent channel with a state-cognizant encoder is the highest possible rate of communication over the channel when the decoder-in addition to reliably decoding the data-must also reconstruct the state sequence with some required fidelity. Feedback from the channel output to the encoder is shown to increase this capacity even for channels that are memoryless with memoryless states. This capacity is calculated here for such channels with feedback when the state reconstruction fidelity is measured using a single-letter distortion function and the state sequence is revealed to the encoder in one of two different ways: strictly-causally or causally.

A necessary condition for the transmissibility of correlated sources over a multi-access channel (MAC) is presented. The condition is related to Wyner's common information and to the Slepian-Wolf capacity region of the MAC with private and common messages. An analogous condition for the transmissibility of remote sources over a MAC is also derived. Here the transmitters only observe noisy versions of the sources.

The supremum of the Rényi entropy rate over the class of discrete-time stationary stochastic processes, whose marginals are supported by some given set and satisfy some given cost constraint, is computed. Unlike the Shannon entropy, the Rényi entropy of a random vector can exceed the sum of the Rényi entropies of its components, and the supremum is, therefore, typically not achieved by memoryless processes. It is nonetheless related to Shannon's entropy: when the Rényi parameter exceeds one, the supremum is equal to the corresponding supremum of Shannon's entropy, and when it is smaller than one, the supremum equals the logarithm of the volume of the support set. A Burg-like supremum of the Rényi entropy rate over the class of stochastic processes, whose autocovariance function begins with some given values, is also solved. It is not achieved by Gauss-Markov processes, but it is nonetheless related to Burg's supremum: the two are equal when the Rényi parameter exceeds one, and the former is infinite otherwise.

We study the secrecy of a distributed-storage system for passwords. The encoder, Alice, observes a length-n password and describes it using δ s-bit hints, which she stores in different locations. The legitimate receiver, Bob, observes ν of those hints. In one scenario we require that the expected number of guesses it takes Bob to guess the password approach 1 as n tends to infinity, and in the other that the expected size of the shortest list that Bob must form to guarantee that it contain the password approach 1. The eavesdropper, Eve, sees η < ν hints. Assuming that Alice cannot control which hints Bob and Eve observe, we characterize for each scenario the largest normalized (by n) exponent that we can guarantee for the expected number of guesses it takes Eve to guess the password.

An algorithm of polynomial complexity is proposed that produces an optimal task encoder for tasks that are generated according to some given law and that need to be described using a given number of labels. It thus minimizes the expectation (or ρ-th moment) of the number of tasks that share the label of a randomly-generated task.

A source generates a point pattern consisting of a finite number of points in an interval. Based on a binary description of the point pattern, a reconstructor must produce a covering set that is guaranteed to contain the pattern. We study the optimal tradeoff (as the length of the interval tends to infinity) between the description length and the least average Lebesgue measure of the covering set. The tradeoff is established for point patterns that are generated by homogeneous and inhomogeneous Poisson processes. The homogeneous Poisson process is shown to be the most difficult to describe among all point patterns. We also study a Wyner-Ziv version of this problem, where some of the points in the pattern are revealed to the reconstructor but not to the encoder. We show that this scenario is as good as when they are revealed to both encoder and reconstructor. A connection between this problem and the queueing distortion is established via feedforward. Finally, we establish the aforementioned tradeoff when the covering set is allowed to miss some of the points in the pattern at a certain cost.

We show that the identification (ID) capacity of the two-receivers broadcast channel is the set of rate pairs satisfying that, for some distribution on the input, each receiver's ID rate does not exceed the mutual information between the input and the output that it observes. The capacity's interior is achieved by codes with deterministic encoders. Our results hold under the average error criterion, which requires that each receiver reliably identify its message if the other receiver's message is uniformly distributed. Key in the proof is a new ID code for the single-user channel.

A task is randomly drawn from a finite set of tasks and is described using a fixed number of bits. All the tasks that share its description must be performed. Upper and lower bounds on the minimum ρ-th moment of the number of performed tasks are derived. The key is an analog of the Kraft Inequality for partitions of finite sets. When a sequence of tasks is produced by a source of a given Rényi entropy rate of order 1=(1 + ρ) and n tasks are jointly described using nR bits, it is shown that for R larger than the Rényi entropy rate, the ρ-th moment of the ratio of performed tasks to n can be driven to one as n tends to infinity, and that for R less than the Rényi entropy rate it tends to infinity. This generalizes a recent result for IID sources by the same authors. A mismatched version of the direct part is also considered, where the code is designed according to the wrong law. The penalty incurred by the mismatch can be expressed in terms of a divergence measure that was shown by Sundaresan to play a similar role in the Massey-Arikan guessing problem.

Optimal error probabilities for transmission over the average-power-limited Gaussian channel with intermittent feedback are studied. For the two-message case, the asymptotic decay of the probability of error in the blocklength is double-exponential and is fully characterized. For positive rates a critical rate is identified below which a double-exponential decay is possible and above which it is not.

Ahlswede, Cai, and Zhang proved that, in the noise-free limit, the zero-undetected-error capacity is lower-bounded by the Sperner capacity of the channel graph, and they conjectured equality. Here we derive an upper bound that proves the conjecture.

We study the secrecy of a distributed storage system for passwords. The encoder, Alice, observes a length-n password and describes it using two hints, which she then stores in different locations. The legitimate receiver, Bob, observes both hints. In one scenario we require that the number of guesses it takes Bob to guess the password approach 1 as n tends to infinity and in the other that the size of the list that Bob must form to guarantee that it contain the password approach 1. The eavesdropper, Eve, sees only one of the hints; Alice cannot control which. For each scenario we characterize the largest normalized (by n) exponent that we can guarantee for the number of guesses it takes Eve to guess the password.

A random variable Z taking value in a finite, nonatomic measure space (X;M; μ) and whose distribution is absolutely continuous with respect to μ is to be described using N labels. We seek the labeling that minimizes the ρ-th moment of the μ-volume of the set of points in X that have the same label as Z. The large-N asymptotics of this minimum are expressed in terms of the Rényi entropy of order 1=(1 + ρ).

The benefits afforded by feedback and/or causal state information (SI) on the state-dependent discrete memoryless multiple-access channel (SD-MAC) with cribbing encoder/s are studied. Capacity regions are derived for communication scenarios whose capacities without cribbing are still unknown. It is shown that when the encoders can crib, the SD-MAC behaves less like a MAC and more like a single-user channel: 1) feedback does not help; 2) strictly causal SI does not help; and 3) causal SI to both encoders is best utilized using Shannon strategies. However, in asymmetric settings, the single-user-like behavior may or may not occur. For example, the SD-MAC with only one cribbing encoder is single-user-like when the state is revealed to the cribbing encoder, but not if it is revealed to the noncribbing encoder.

A task is randomly drawn from a finite set of tasks and is described using a fixed number of bits. All the tasks that share its description must be performed. Upper and lower bounds on the minimum pth moment of the number of performed tasks are derived. The case where a sequence of tasks is produced by a source and n tasks are jointly described using nR bits is considered. If R is larger than the Rényi entropy rate of the source of order 1/(1 + ρ) (provided it exists), then the ρth moment of the ratio of performed tasks to n can be driven to one as n tends to infinity. If R is smaller than the Rényi entropy rate, this moment tends to infinity. The results are generalized to account for the presence of side-information. In this more general setting, the key quantity is a conditional version of Rényi entropy that was introduced by Arimoto. For IID sources, two additional extensions are solved, one of a rate-distortion flavor and the other where different tasks may have different nonnegative costs. Finally, a divergence that was identified by Sundaresan as a mismatch penalty in the Massey-Arikan guessing problem is shown to play a similar role here.

The listsize capacity of a discrete memoryless channel is the largest transmission rate for which the expectation-or, more generally, the ρ-th moment-of the number of messages that could have produced the output of the channel approaches one as the blocklength tends to infinity. We show that for channels with feedback, this rate is upper bounded by the maximum of Gallager's E0function divided by ρ, and that equality holds when the zero-error capacity of the channel is positive. To establish this inequality, we prove that feedback does not increase the cutoff rate. Relationships to other notions of channel capacity are explored.

Ahlswede, Cai, and Zhang proved that, in the noise-free limit, the zero-undetected-error capacity is lower bounded by the Sperner capacity of the channel graph, and they conjectured equality. Here, we derive an upper bound that proves the conjecture.

A coding scheme is proposed for the memoryless Gaussian broadcast channel with correlated noises and feedback. For all noise correlations other than ±1, the gap between the sum-rate that the scheme achieves and the full-cooperation bound vanishes as the signal-to-noise ratio tends to infinity. When the correlation coefficient is -1, the gains afforded by feedback are unbounded and the prelog is doubled. When the correlation coefficient is +1, we demonstrate a dichotomy that if the noise variances are equal, then feedback is useless, and otherwise, feedback affords unbounded rate gains and doubles the prelog. The unbounded feedback gains, however, require perfect (noiseless) feedback. When the feedback links are noisy, the feedback gains are bounded, unless the feedback noise decays to zero sufficiently fast with the signal-to-noise ratio. Extensions to more receivers are also discussed as is the memoryless Gaussian interference channel with feedback.

We study an interference network where equally numbered transmitters and receivers lie on two parallel lines, with each transmitter opposite its intended receiver. We consider two short-range interference models: the asymmetric network, where the signal sent by each transmitter is interfered only by the signal sent by its left neighbor (if present), and a symmetric network, where it is interfered by both its left and its right neighbors. Each transmitter is cognizant of its own message, the messages of the tℓtransmitters to its left, and the messages of the trtransmitters to its right. Each receiver decodes its message based on the signals received at its own antenna, at the rrreceive antennas to its left, and at the rrreceive antennas to its right. For such networks, we provide upper and lower bounds on the multiplexing gain, i.e., on the high signal-to-noise ratio asymptotic logarithmic growth of the sum-rate capacity. In some cases, our bounds coincide, e.g., for the asymmetric network. Our results exhibit an equivalence between the transmitter sideinformation parameters tℓ, tr and the receiver side-information parameters rℓ, rrin the sense that increasing/decreasing tℓor trby a positive integer δ has the same effect on the multiplexing gain as increasing/decreasing rℓor rrby δ. Moreover-even in asymmetric networks-there is an equivalence between the left side-information parameters (tℓ, rℓ) and the right sideinformation parameters (tr, rr).

The source-coding problem with side information at the decoder is studied subject to a constraint that the encoder-to whom the side information is unavailable-be able to compute the decoder's reconstruction sequence to within some distortion. For discrete memoryless sources and finite single-letter distortion measures, an expression is given for the minimal description rate as a function of the joint law of the source and side information and of the allowed distortions at the encoder and at the decoder. The minimal description rate is also computed for a memoryless Gaussian source with squared-error distortion measures. A solution is also provided to a more general problem where there are more than two distortion constraints and each distortion measure may be a function of three arguments: the source symbol, the encoder's reconstruction symbol, and the decoder's reconstruction symbol.

We study the zero-undetected-error capacity of the discrete memoryless channel whose directed channel graph is the cyclic triangle. We show that this capacity is upper-bounded by log 2 and approaches log 2 as the crossover probabilities tend to zero.

We study two multiple-access scenarios with encoders that are informed only intermittently. The first is the Gaussian multiple-access channel with an intermittent feedback link. Here we assume that, depending on the current binary state which evolves in a memoryless fashion, the previous channel output is either revealed to the two encoders or not. For this scenario we obtain an outer bound on the capacity region that approaches the capacity region without feedback when the probability that the channel output will be fed back approaches zero. We also propose an inner bound that converges to the capacity region with ideal feedback and the capacity region with no feedback in the associated extreme cases. In the second scenario the encoders always observe ideal feedback, and in addition they can crib intermittently. For this scenario we establish the capacity region for the special class of semi-deterministic multiple-access channels. The capacity is achieved using the Superposition Block Markov Coding technique of Cover and Leung. For both scenarios the outer bounds are tighter than those obtained by revealing the underlying state sequence non-causally to the encoders.

A sequence produced by a memoryless source is to be described using a fixed number of bits that is proportional to its length. Based on the description, a list that is guaranteed to contain the sequence must be produced. The trade-off between the description length and the moments of the listsize is studied when the sequence's length tends to infinity. It is characterized by the source's Rényi entropy. Extensions to scenarios with side information are also studied, where the key is conditional Rényi entropy. The lossy case where at least one of the elements of the list must be within a specified distortion from the source sequence is also solved.

We study the cutoff rate and the average-listsize capacity of discrete memoryless channels (DMCs) with feedback. We show that feedback can increase the average-listsize capacity but not the cutoff rate. For DMCs with positive zero-error capacity, we show that the average-listsize capacity with feedback is equal to the cutoff rate. For all other DMCs, we derive a lower bound on the average-listsize capacity with feedback. The bound is asymptotically tight for low-noise channels. We also show that a multi-letter version of Forney's lower bound on the average-listsize capacity of DMCs without feedback is asymptotically tight.

We study the capacity of the discrete-time Gaussian channel when its output is quantized with a 1-bit quantizer. We focus on the low signal-to-noise ratio (SNR) regime, where communication at very low spectral efficiencies takes place. In this regime, a symmetric threshold quantizer is known to reduce channel capacity by a factor of 2/π, i.e., to cause an asymptotic power loss of approximately 2 dB. Here, it is shown that this power loss can be avoided by using asymmetric threshold quantizers and asymmetric signaling constellations. To avoid this power loss, flash-signaling input distributions are essential. Consequently, 1-bit output quantization of the Gaussian channel reduces spectral efficiency. Threshold quantizers are not only asymptotically optimal: at every fixed SNR, a threshold quantizer maximizes capacity among all 1-bit output quantizers. The picture changes on the Rayleigh-fading channel. In the noncoherent case, a 1-bit output quantizer causes an unavoidable low-SNR asymptotic power loss. In the coherent case, however, this power loss is avoidable provided that we allow the quantizer to depend on the fading level.

We show that if a memoryless multiple-access channel (MAC) is governed by an independent and identically distributed state sequence, then-unlike the single-user case-the capacity region is typically increased if the state is revealed to the encoders in a strictly causal way. For this scenario, we derive inner and outer bounds on the capacity region. For the Gaussian MAC whose state sequence comprises the channel noise, we compute the capacity region and propose a variation on the Schalkwijk-Kailath scheme that achieves capacity with a double-exponential decay of the maximal probability of error. We also study the causal case for which we derive an achievable region, which is typically strictly larger than the region achievable with naïve Shannon strategies.

We consider a memoryless multiple-access channel (MAC) that is governed by two independent memoryless state sequences, each of which is revealed to a different encoder in a strictly causal or causal way. The special case where one of the state sequences is deterministic (null) corresponds to an MAC governed by a single state that is revealed to only one of the encoders. We show that, even in the strictly causal case, the state information at the encoders can increase the capacity region. It cannot, however, increase the sum-rate capacity. We provide general inner and outer bounds on the capacity region, and we also study a Gaussian example where they coincide. We show that in the causal case, naïve Shannon strategies may be suboptimal.

We derive the capacity region of the state-dependent semideterministic broadcast channel with noncausal state information at the transmitter. One of the two outputs of this channel is a deterministic function of the channel input and the channel state, and the state is assumed to be known noncausally to the transmitter but not to the receivers. We show that appending the state to the deterministic output does not increase capacity. We also derive an outer bound on the capacity of general (not necessarily semideterministic) state-dependent broadcast channels.

We derive the capacity region of the state-dependent semideterministic broadcast channel with noncausal state-information at the transmitter. In this broadcast channel one of the outputs is a deterministic function of the channel input and the channel state, and the state is assumed to be known noncausally to the transmitter but not to the receivers.

We show that the capacity region of the state-dependent multiple-access channel (SD-MAC) with strictly-causally cribbing encoders is not enlarged if strictly-causal state-information (SI) and feedback are furnished to the encoders. We also derive the capacity region of the SD-MAC with causal SI at the cribbing encoders and show that Shannon strategies are optimal. Such strategies are generally suboptimal if the encoders access distinct SI. However, Shannon strategies are optimal and we have a characterization of the capacity region for the case where both encoders crib, causal SI is revealed to one encoder, and feedback is available to the other encoder.

We derive the capacity region of the two-user dirty-paper Gaussian multiaccess channel (MAC) with conferencing encoders. In this MAC, prior to each transmission block, the transmitters can hold a conference in which they can communicate with each other over error-free bit pipes of given capacities. The received signal suffers not only from additive Gaussian noise but also from additive interference, which is known noncausally to the transmitters but not to the receiver. The additive interference is modeled as Gaussian or uniform over a sphere. We show that the interference can be perfectly mitigated, i.e., that the capacity region without interference can also be achieved in its presence. This holds irrespective of whether the transmitters learn the interference before or after the conference. It follows as a corollary that also for the MAC with degraded message sets, the interference can be perfectly mitigated if it is known noncausally to the transmitters. To derive our results, we generalize Costa's single-user writing-on-dirty-paper achievability result to channels with dependent interference and not-necessarily Gaussian noise.

We propose an algorithm for computing the capacity of discrete rewritable storage devices subject to a constraint on the maximal number of rewrite operations. The linchpin is that-although the number of writing strategies is exponential in the maximal number of allowed rewrites-linear functionals of the probabilities they induce on the output space can be efficiently maximized using Dynamic Programming.

We study the behavior of channel capacity when a one-bit quantizer is employed at the output of the discrete-time average-power-limited Gaussian channel. We focus on the low signal-to-noise ratio regime, where communication at very low spectral efficiencies takes place, as in Spread-Spectrum and Ultra-Wideband communications. It is well known that, in this regime, a symmetric one-bit quantizer reduces capacity by 2/π, which translates to a power loss of approximately two decibels. Here we show that if an asymmetric one-bit quantizer is employed, and if asymmetric signal constellations are used, then these two decibels can be recovered in full.

A source generates a “point pattern” consisting of a finite number of points in an interval. Based on a binary description of the point pattern, a reconstructor must produce a “covering set” that is guaranteed to contain the pattern. We study the optimal trade-off (as the length of the interval tends to infinity) between the description length and the least average Lebesgue measure of the covering set. The trade-off is established for point patterns that are generated by a Poisson process. Such point patterns are shown to be the most difficult to describe. We also study a Wyner-Ziv version of this problem, where some of the points in the pattern are known to the reconstructor but not to the encoder. We show that this scenario is as good as when they are known to both encoder and reconstructor.

We consider a variation on the Wyner-Ziv source coding problem with side-information at the decoder where the encoder is required to be able to compute the decoder's reconstruction sequence with some fidelity. This requirement limits the extent to which the reconstruction sequence can depend on the side-information, which is not available to the encoder. For finite-alphabet memoryless sources and single-letter distortion measures we compute the minimal description rate as a function of the joint law of the source and side-information and of the allowed distortions at the encoder and decoder. We also treat memoryless Gaussian sources with mean squared-error distortion measures.

We study a multiple-terminal joint source-channel coding problem, where two remote correlated Gaussian sources are transmitted over a Gaussian multiple-access channel with two transmitters. Each transmitter observes one of the sources contaminated in Gaussian noise. The receiver wishes to reconstruct both sources. We derive necessary conditions and sufficient conditions for the receiver to be able to reconstruct the sources with given expected squared-error distortions. These conditions establish the optimality of uncoded transmission below some signal-to-noise ratio (SNR) threshold, and they also establish the high-SNR asymptotics. To achieve the latter, a coding scheme is proposed that superimposes analog uncoded transmission and digital combined source-channel Gaussian vector quantization.

We study the best exponential decay in the blocklength of the probability of error that can be achieved in the transmission of a single bit over the Gaussian channel with an active noisy Gaussian feedback link. We impose an expected block power constraint on the forward link and study both almost-sure and expected block power constraints on the feedback link. In both cases the best achievable error exponents are finite and grow approximately proportionally to the larger between the signal-to-noise ratios on the forward and feedback links. The error exponents under almost-sure block power constraints are typically strictly smaller than under expected constraints. Some of the results extend to communication at arbitrary rates below capacity and to general discrete memoryless channels.

The asymptotic capacity at low input powers of an average-power limited or an average- and peak-power limited discrete-time Poisson channel is considered. For a Poisson channel whose dark current is zero or decays to zero linearly with its average input powerε, capacity scales likeεlog 1/εfor smallε. For a Poisson channel whose dark current is a nonzero constant, capacity scales, to within a constant, likeεlog log 1/ε for smallε.

We study the state-dependent multiple access channel (MAC) with causal side information at the encoders. The channel state consists of two independent components, S1and S2, available at Encoder 1 and Encoder 2, respectively. The problem where the state is available at only one of the encoders is a special case. We consider two scenarios. In the first, the states are available at the encoders in a strictly causal manner. We derive an achievable region, which is tight for a Gaussian MAC where the state sequence comprises the channel noise and is available at one of the encoders only. In the second scenario the state sequence is available to the encoders in a causal manner, as in Shannon's model. A simple extension of the previous result to Shannon strategies yields an achievability result. Our region contains as a special case the naïve rate region obtained when each of the users applies Shannon strategies. In some cases the inclusion is strict.

We study the transmission of a memoryless bivariate Gaussian source over an average-power-constrained one-to-two Gaussian broadcast channel. The transmitter observes the source and describes it to the two receivers by means of an average-power-constrained signal. Each receiver observes the transmitted signal corrupted by a different additive white Gaussian noise and wishes to estimate the source component intended for it: Receiver 1 wishes to estimate the first source component and Receiver 2 wishes to estimate the second. Our interest is in the pairs of expected squared-error distortions that are simultaneously achievable at the two receivers. We prove that an uncoded transmission scheme that sends a linear combination of the source components achieves the optimal power-versus-distortion trade-off whenever the signal-to-noise ratio is below a certain threshold. The threshold is a function of the source correlation and the distortion at the receiver with the weaker noise.

The capacity of peak-power limited, single-antenna, noncoherent, flat-fading channels with memory is considered. The emphasis is on the capacity pre-log, i.e., on the limiting ratio of channel capacity to the logarithm of the signal-to-noise ratio (SNR), as the SNR tends to infinity. It is shown that, among all stationary and ergodic fading processes of a given spectral distribution function and whose law has no mass point at zero, the Gaussian process gives rise to the smallest pre-log. The assumption that the law of the fading process has no mass point at zero is essential in the sense that there exist stationary and ergodic fading processes whose law has a mass point at zero and that give rise to a smaller pre-log than the Gaussian process of equal spectral distribution function. An extension of these results to multiple-input single-output (MISO) fading channels with memory is also presented.

A noncoherent multipath fading channel is considered, where neither the transmitter nor the receiver is cognizant of the realization of the path gains, but both are cognizant of their statistics. It is shown that if the delay spread is large in the sense that the variances of the path gains decay exponentially or slower, then capacity is bounded in the signal-to-noise ratio (SNR). For such channels, capacity does not tend to infinity as the SNR tends to infinity. In contrast, if the variances of the path gains decay faster than exponentially, then capacity is unbounded in the SNR. It is further demonstrated that if the number of paths is finite, then at high SNR capacity grows double-logarithmically with the SNR, and the capacity pre-loglog-defined as the limiting ratio of capacity to loglog(SNR) as the SNR tends to infinity-is 1 irrespective of the number of paths. The results demonstrate that at high SNR multipath fading channels with an infinite number of paths cannot be approximated by multipath fading channels with only a finite number of paths. The number of paths that are needed to approximate a multipath fading channel typically depends on the SNR and may grow to infinity as the SNR tends to infinity.

We study the power-versus-distortion tradeoff for the transmission of a memoryless bivariate Gaussian source over a two-to-one Gaussian multiple-access channel with perfect causal feedback. In this problem, each of two separate transmitters observes a different component of a memoryless bivariate Gaussian source as well as the feedback from the channel output of the previous time-instants. Based on the observed source sequence and the feedback, each transmitter then describes its source component to the common receiver via an average-power constrained Gaussian multiple-access channel. From the resulting channel output, the receiver wishes to reconstruct each source component with the least possible expected squared-error distortion. We study the set of distortion pairs that can be achieved by the receiver on the two source components. We present sufficient conditions and necessary conditions for the achievability of a distortion pair. These conditions are expressed in terms of the source correlation and of the signal-to-noise ratio (SNR) of the channel. In several cases the necessary conditions and sufficient conditions are shown to agree. In particular, we show that if the channel SNR is below a certain threshold, then an uncoded transmission scheme that ignores the feedback is optimal. Thus, below this SNR-threshold, feedback is useless. We also derive the optimal high-SNR asymptotics.

We study the power-versus-distortion tradeoff for the distributed transmission of a memoryless bivariate Gaussian source over a two-to-one average-power limited Gaussian multiple-access channel. In this problem, each of two separate transmitters observes a different component of a memoryless bivariate Gaussian source. The two transmitters then describe their source component to a common receiver via an average-power constrained Gaussian multiple-access channel. From the output of the multiple-access channel, the receiver wishes to reconstruct each source component with the least possible expected squared-error distortion. Our interest is in characterizing the distortion pairs that are simultaneously achievable on the two source components. We focus on the ¿equal bandwidth¿ case, where the source rate in source-symbols per second is equal to the channel rate in channel-uses per second. We present sufficient conditions and necessary conditions for the achievability of a distortion pair. These conditions are expressed as a function of the channel signal-to-noise ratio (SNR) and of the source correlation. In several cases, the necessary conditions and sufficient conditions are shown to agree. In particular, we show that if the channel SNR is below a certain threshold, then an uncoded transmission scheme is optimal. Moreover, we introduce a ¿source-channel vector-quantizer¿ scheme which is asymptotically optimal as the SNR tends to infinity.

New achievable rate regions are derived for the two-user additive white Gaussian multiple-access channel with noisy feedback. The regions exhibit the following two properties. Irrespective of the (finite) Gaussian feedback-noise variances, the regions include rate points that lie outside the no-feedback capacity region, and when the feedback-noise variances tend to zero the regions converge to the perfect-feedback capacity region.

We study the uplink of a linear cellular model featuring short range inter-cell interference. Specifically, we consider a K-transmitter/K-receiver interference network where the signal transmitted by a given transmitter is interfered by the signal sent by the transmitter to its left. We assume that each transmitter has side-information consisting of the messages of the Jlusers to its left and the Jrusers to its right, and that each receiver can decode its message using the signals received at its own antenna, at the ilantennas to its left, and at the irantennas to its right. For this setting, we characterize the multiplexing gain, i.e., the asymptotic logarithmic growth of the sum-rate capacity at high SNR, and point out interesting duality aspects. We also present results on the multiplexing gain of a symmetric version of this network where the signal sent by a given transmitter is interfered by the signals sent by the transmitter to its left and the transmitter to its right.

This paper considers an additive noise channel where the time-A; noise variance is a weighted sum of the squared magnitudes of the previous channel inputs plus a constant. This channel model accounts for the dependence of the intrinsic thermal noise on the data due to the heat dissipation associated with the transmission of data in electronic circuits: the data determine the transmitted signal, which in turn heats up the circuit and thus influences the power of the thermal noise. The capacity of this channel (both with and without feedback) is studied at low transmit powers and at high transmit powers. At low transmit powers, the slope of the capacity-versus-power curve at zero is computed and it is shown that the heating-up effect is beneficial. At high transmit powers, conditions are determined under which the capacity is bounded, i.e., under which the capacity does not grow to infinity as the allowed average power tends to infinity.

The large-inputs asymptotic capacity of a peak-power and average-power limited discrete-time Poisson channel is derived using a new firm (nonasymptotic) lower bound and an asymptotic upper bound. The upper bound is based on the dual expression for channel capacity and the notion of capacity-achieving input distributions that escape to infinity. The lower bound is based on a lower bound on the entropy of a conditionally Poisson random variable in terms of the differential entropy of its conditional mean.

Upper and lower bounds are derived on the capacity of the free-space optical intensity channel. This channel has a nonnegative input (representing the transmitted optical intensity), which is corrupted by additive white Gaussian noise. To preserve the battery and for safety reasons, the input is constrained in both its average and its peak power. For a fixed ratio of the allowed average power to the allowed peak power, the difference between the upper and the lower bound tends to zero as the average power tends to infinity and their ratio tends to one as the average power tends to zero. When only an average power constraint is imposed on the input, the difference between the bounds tends to zero as the allowed average power tends to infinity, and their ratio tends to a constant as the allowed average power tends to zero.

Discrete-time Rayleigh-fading single-input single-output (SISO) and multiple-input multiple-output (MIMO) channels are considered, with no channel state information at the transmitter or the receiver. The fading is assumed to be stationary and correlated in time, but independent from antenna to antenna. Peak-power and average-power constraints are imposed on the transmit antennas. For MIMO channels, these constraints are either imposed on the sum over antennas, or on each individual antenna. For SISO channels and MIMO channels with sum power constraints, the asymptotic capacity as the peak signal-to-noise ratio (SNR) goes to zero is identified; for MIMO channels with individual power constraints, this asymptotic capacity is obtained for a class of channels called transmit separable channels. The results for MIMO channels with individual power constraints are carried over to SISO channels with delay spread (i.e., frequency-selective fading).

We consider a one-to-two Gaussian broadcasting problem where the transmitter observes a memoryless bi-variate Gaussian source and each receiver wishes to estimate one of the source components. The transmitter describes the source pair by means of an average-power-constrained signal and each receiver observes this signal corrupted by a different additive white Gaussian noise. From its respective observation, Receiver 1 wishes to estimate the first source component and Receiver 2 wishes to estimate the second. We seek to characterize the pairs of expected squared-error distortions that are simultaneously achievable at the two receivers. Our result is that below a certain SNR-threshold an ldquouncoded schemerdquo that sends a linear combination of the source components is optimal. We present a lower bound on this threshold in terms of the source correlation and the distortion at the receiver with weaker channel noise.

We derive the capacity region of the Gaussian version of Willemspsilas two-user MAC with conferencing encoders. This setting differs from the classical MAC in that, prior to each transmission block, the two transmitters can communicate with each other over noise-free bit-pipes of given capacities. The derivation requires a new technique for proving the optimality of Gaussian input distributions in certain mutual information maximizations under a Markov constraint. We also consider a Costa-type extension of the Gaussian MAC with conferencing encoders. In this extension, the channel can be described as a two-user MAC with Gaussian noise and Gaussian interference where the interference is known non-causally to the encoders but not to the decoder. We show that as in Costa's setting the interference sequence can be perfectly canceled, i.e., that the capacity region without interference can be achieved.

This paper studies the capacity of discrete-time multipath fading channels. It is assumed that the number of paths is finite, i.e., that the channel output is influenced by the present and by the L previous channel inputs. A noncoherent channel model is considered where neither transmitter nor receiver are cognizant of the fading's realization, but both are aware of its statistic. The focus is on capacity at high signal-to-noise ratios (SNR). In particular, the capacity pre-loglog-defined as the limiting ratio of the capacity to loglog(SNR) as SNR tends to infinity-is studied. It is shown that, irrespective of the number of paths L, the capacity pre-loglog is 1.

New upper and lower bounds are presented on the capacity of the free-space optical intensity channel. This channel is characterized by inputs that are nonnegative (representing the transmitted optical intensity) and by outputs that are corrupted by additive white Gaussian noise (because in free space the disturbances arise from many independent sources). Due to battery and safety reasons the inputs are simultaneously constrained in both their average and peak power. For a fixed ratio of the average power to the peak power the difference between the upper and the lower bounds tends to zero as the average power tends to infinity, and the ratio of the upper and lower bounds tends to one as the average power tends to zero. The case where only an average-power constraint is imposed on the input is treated separately. In this case, the difference of the upper and lower bound tends to 0 as the average power tends to infinity, and their ratio tends to a constant as the power tends to zero.

The capacity of discrete-time, non-coherent, multi-path fading channels is considered. It is shown that if the delay spread is large in the sense that the variances of the path gains do not decay faster than geometrically, then capacity is bounded in the signal-to-noise ratio.

Upper and lower bounds are derived on the reliability function of the additive white Gaussian noise channel with output fed back to the transmitter over an independent additive white Gaussian noise channel. Special attention is paid to the regime of very low feedback noise variance and it is shown that the reliability function is asymptotically inversely proportional to the feedback noise variance. This result shows that the noise in the feedback link, however small, renders the communication with noisy feedback fundamentally different from the perfect feedback case. For example, it is demonstrated that with noisy feedback, linear coding schemes fail to achieve any positive rate. In contrast, an asymptotically optimal coding scheme is devised, based on a three-phase detection/retransmission protocol, which achieves an error exponent inversely proportional to the feedback noise variance for any rate less than capacity.

Motivated by on-chip communication, a channel model is proposed where the variance of the additive noise depends on the weighted sum of the past channel input powers. For this channel, an expression for the capacity per unit cost is derived, and it is shown that the expression holds also in the presence of feedback.

For an interference network where receiver k receives the sum of the signal transmitted by Transmitter k and a scaled version of the signal transmitted by Transmitter k - 1 corrupted by Gaussian noise we compute the pre-log of the sum-rate capacity for the case where each transmitter has side- information consisting of the messages to be sent by its J predecessors.

We consider the problem of transmitting a bivariate Gaussian source over a two-user additive Gaussian multiple-access channel with feedback. Each of the transmitters observes one of the source components and tries to describe it to the common receiver. We are interested in the minimal mean squared error at which the receiver can reconstruct each of the source components. In the "symmetric case" we show that, below a certain signal-to-noise ratio threshold which is determined by the source correlation, feedback is useless and the minimal distortion is achieved by uncoded transmission. For the general case we give necessary conditions for the achievability of a distortion pair.

Discrete-time Rayleigh fading multiple-input multiple-output (MIMO) channels are considered, with no channel state information at the transmitter and receiver. The fading is assumed to be correlated in time and independent from antenna to antenna. Peak and average transmit power constraints are imposed, either on the sum over antennas, or on each individual antenna. In both cases, an upper bound and an asymptotic lower bound, as the signal-to-noise ratio approaches zero, on the channel capacity are presented. The limit of normalized capacity is identified under the sum power constraints, and, for a subclass of channels, for individual power constraints. These results carry over to a SISO channel with delay spread (i.e. frequency selective fading).

A generalization of the problem of writing on dirty paper is considered in which one transmitter sends a common message to multiple receivers. Each receiver experiences on its link an additive interference (in addition to the additive noise), which is known noncausally to the transmitter but not to any of the receivers. Applications range from wireless multiple-antenna multicasting to robust dirty paper coding. We develop results for memoryless channels in Gaussian and binary special cases. In most cases, we observe that the availability of side information at the transmitter increases capacity relative to systems without such side information, and that the lack of side information at the receivers decreases capacity relative to systems with such side information. For the noiseless binary case, we establish the capacity when there are two receivers. When there are many receivers, we show that the transmitter side information provides a vanishingly small benefit. When the interference is large and independent across the users, we show that time sharing is optimal. For the Gaussian case, we present a coding scheme and establish its optimality in the high signal-to-interference-plus-noise limit when there are two receivers. When the interference power is large and independent across all the receivers, we show that time-sharing is again optimal. Connections to the problem of robust dirty paper coding are also discussed

We propose to send a Gaussian source over an average-power limited additive white Gaussian noise channel by transmitting a linear combination of the source sequence and the result of its quantization using a high dimensional Gaussian vector quantizer. We show that, irrespective of the rate of the vector quantizer (assumed to be fixed and smaller than the channel's capacity), this transmission scheme is asymptotically optimal (as the quantizer's dimension tends to infinity) under the mean squared-error fidelity criterion. This generalizes the classical result of Goblick about the optimality of scaled uncoded transmission, which corresponds to choosing the rate of the vector quantizer as zero, and the classical source-channel separation approach, which corresponds to choosing the rate of the vector quantizer arbitrarily close to the capacity of the channel

The capacity of pear-power limited, single-antenna, non-coherent, flat-fading channels with memory is considered. The emphasis is on the capacity pre-log, i.e., on the limiting ratio of channel capacity to the logarithm of the signal-to-noise ratio (SNR), as the SNR tends to infinity. It is shown that, among all stationary and ergodic fading processes of given spectral distribution function whose law has no mass point at zero, the Gaussian process gives rise to the smallest pre-log

We consider a problem where a memoryless bi-variate Gaussian source is to be transmitted over an additive white Gaussian multiple-access channel with two transmitting terminals and one receiving terminal. The first transmitter only sees the first source component and the second transmitter only sees the second source component. We are interested in the pair of mean squared-error distortions at which the receiving terminal can reproduce each of the source components. It is demonstrated that in the symmetric case, below a certain signal-to-noise ratio (SNR) threshold, which is determined by the source correlation, uncoded communication is optimal. For SNRs above this threshold we present outer and inner bounds on the achievable distortions

We derive the fading number of stationary and ergodic (not necessarily Gaussian) single-input multiple-output (SIMO) fading channels with memory. This is the second term, after the double-logarithmic term, of the high signal-to-noise ratio (SNR) expansion of channel capacity. The transmitter and receiver are assumed to be cognizant of the probability law governing the fading but not of its realization. It is demonstrated that the fading number is achieved by independent and identically distributed (i.i.d.) circularly symmetric inputs of squared magnitude whose logarithm is uniformly distributed over an SNR-dependent interval. The upper limit of the interval is the logarithm of the allowed transmit power, and the lower limit tends to infinity sublogarithmically in the SNR. The converse relies inter alia on a new observation regarding input distributions that escape to infinity. Lower and upper bounds on the fading number for Gaussian fading are also presented. These are related to the mean squared-errors of the one-step predictor and the one-gap interpolator of the fading process respectively. The bounds are computed explicitly for stationary mth-order autoregressive AR(m) Gaussian fading processes.

We propose a technique to derive upper bounds on Gallager's cost-constrained random coding exponent function. Applying this technique to the noncoherent peak-power or average-power limited discrete time memoryless Ricean fading channel, we obtain the high signal-to-noise ratio (SNR) expansion of this channel's cutoff rate. At high SNR, the gap between channel capacity and the cutoff rate approaches a finite limit. This limit is approximately 0.26 nats per channel-use for zero specular component (Rayleigh) fading and approaches 0.39 nats per channel-use for very large values of the specular component. We also compute the asymptotic cutoff rate of a Rayleigh-fading channel when the receiver has access to some partial side information concerning the fading. It is demonstrated that the cutoff rate does not utilize the side information as efficiently as capacity, and that the high SNR gap between the two increases to infinity as the imperfect side information becomes more and more precise.

We introduce a preorder on the line-of-sight (LOS) matrices in coherent multiple-input multiple-output (MIMO) Rician fading channels. We demonstrate that under this preorder, the information rate and the rate-R outage probability corresponding to zero-mean multivariate circularly symmetric Gaussian inputs of arbitrary but fixed covariance matrices are monotonic in the LOS matrix. This result extends previous results obtained by Kim & Lapidoth, ISIT, 2003, and Hosli & Lapidoth, ITG Conference on SCC, 2004, i.e., our result implies the monotonicity of the information rates corresponding to isotropic Gaussian inputs and of channel capacity in the singular values of the LOS matrix. It is particularly useful in scenarios such as MIMO Rician multiple-access channels, where the achievable rates depend on the LOS matrices of the different users and cannot be determined based on their corresponding singular values alone. We also prove a converse to the main result. That is, given two different LOS matrices, we show that if for all zero-mean multivariate circularly symmetric Gaussian inputs the induced mutual information over one channel is at least as large as over the other channel, then the two LOS matrices can be ordered

New non-asymptotic upper bounds on the capacity of non-coherent multiple-input multiple-output (MIMO) Gaussian fading channels with memory are proposed. These upper bounds are used to derive upper bounds on the fading number of regular Gaussian fading channels and on the pre-log of nonregular ones. The resulting bounds are tight in the multiple-input single-output (MISO) spatially independent Gaussian case when the entries in the fading vector are either zero-mean or possess the same spectral distribution function. A new approach is proposed for the derivation of lower bounds on the fading number of MIMO channels. This approach is applied to derive a lower bound on the fading number of spatially IID zero-mean Gaussian fading channels. The new upper and lower bounds on the fading number demonstrate that when the number of receive antennas does not exceed the number of transmit antennas, the fading number of zero-mean spatially IID slowly varying Gaussian MIMO channels is proportional to the number of degrees of freedom, i.e., to the minimum of the number of transmit and receive antennas. We conjecture that the same is true also when the number of receive antennas exceeds the number of transmit antennas. The single-input multiple-output case that was recently solved by Lapidoth & Moser supports this conjecture

An achievable region for the two-user discrete memoryless multiple-access channel (DMMAC) with noiseless feedback is proposed. The proposed region includes the Cover-Leung region, with the inclusion being, for some channels, strict. This inner bound is demonstrated for the ideal two-user Poisson multiple-access channel with noiseless feedback, in which case it is shown to improve on the Cover-Leung rate-sum.

The dependence of the Gaussian input information rate on the line-of-sight (LOS) matrix in multiple-input multiple-output (MIMO) coherent Rician fading channels is explored. It is proved that the outage probability and the mutual information induced by a multivariate circularly symmetric Gaussian input with any covariance matrix are monotonic in the LOS matrix D, or more precisely, monotonic in D/sup /spl dagger//D in the sense of the Loewner partial order. Conversely, it is also demonstrated that this ordering on the LOS matrices is a necessary condition for the uniform monotonicity over all input covariance matrices. This result is subsequently applied to prove the monotonicity of the isotropic Gaussian input information rate and channel capacity in the singular values of the LOS matrix. Extensions to multiple-access channels (MAC) are also provided.

We consider a peak-power-limited single-antenna flat complex-Gaussian fading channel where the receiver and transmitter, while fully cognizant of the distribution of the fading process, have no knowledge of its realization. Upper and lower bounds on channel capacity are derived, with special emphasis on tightness in the high signal-to-noise ratio (SNR) regime. Necessary and sufficient conditions (in terms of the autocorrelation of the fading process) are derived for capacity to grow double-logarithmically in the SNR. For cases in which capacity increases logarithmically in the SNR, we provide an expression for the "pre-log", i.e., for the asymptotic ratio between channel capacity and the logarithm of the SNR. This ratio is given by the Lebesgue measure of the set of harmonics where the spectral density of the fading process is zero. We finally demonstrate that the asymptotic dependence of channel capacity on the SNR need not be limited to logarithmic or double-logarithmic behaviors. We exhibit power spectra for which capacity grows as a fractional power of the logarithm of the SNR

We obtain the first term in the high signal-to-noise ratio (SNR) asymptotic expansion of the sum-rate capacity of noncoherent fading networks, i.e., networks where the transmitters and receivers-while fully cognizant of the fading law-have no access to the fading realization. This term is an integer multiple of log log SNR with the coefficient having a simple combinatorial characterization. It can be interpreted as the effective number of parallel channels that can be supported by the network, i.e., as the maximal number of point-to-point single-user scalar channels that can be supported by the network in a manner that will allow, with proper power allocation, negligible cross interference. The results hold irrespective of whether the transmitters can cooperate or must operate in an multiple-access regime; irrespective of whether feedback from the receivers to the transmitters is available or not; and irrespective of whether the receivers can cooperate or not

For a MIMO Ricean fading channel with perfect side information at the receiver we derive an analytic upper bound on the difference between capacity and the mutual information that is induced by an isotropic Gaussian input. We show that if the number of receiver antennas is at least equal to the number of transmitter antennas, then, as the signal-to-noise ratio tends to infinity, such an input is asymptotically optimal. But otherwise such an isotropic input might be suboptimal. We also propose an iterative algorithm to calculate the optimal power allocation.

We propose to use an expression of Csiszar & Korner's to upper bound Gallager's E/sub 0/(/spl rho/,Q,r) function. We demonstrate this approach by computing the high SNR asymptotic expansion of the computational cut-off rate of the peak-or average-power limited discrete-time memoryless Ricean fading channel with no-or with only partial-side information at the receiver.

A technique is proposed for the derivation of upper bounds on channel capacity. It is based on a dual expression for channel capacity where the maximization (of mutual information) over distributions on the channel input alphabet is replaced with a minimization (of average relative entropy) over distributions on the channel output alphabet. We also propose a technique for the analysis of the asymptotic capacity of cost-constrained channels. The technique is based on the observation that under fairly mild conditions capacity achieving input distributions "escape to infinity." The above techniques are applied to multiple-antenna flat-fading channels with memory where the realization of the fading process is unknown at the transmitter and unknown (or only partially known) at the receiver. It is demonstrated that, for high signal-to-noise ratio (SNR), the capacity of such channels typically grows only double-logarithmically in the SNR. To better understand this phenomenon and the rates at which it occurs, we introduce the fading number as the second-order term in the high-SNR asymptotic expansion of capacity, and derive estimates on its value for various systems. It is suggested that at rates that are significantly higher than the fading number, communication becomes extremely power inefficient, thus posing a practical limit on practically achievable rates. Upper and lower bounds on the fading number are also presented. For single-input-single-output (SISO) systems the bounds coincide, thus yielding a complete characterization of the fading number for general stationary and ergodic fading processes. We also demonstrate that for memoryless multiple-input single-output (MISO) channels, the fading number is achievable using beam-forming, and we derive an expression for the optimal beam direction. This direction depends on the fading law and is, in general, not the direction that maximizes the SNR on the induced SISO channel. Using a new closed-form expression for the expectation of the logarithm of a noncentral chi-square distributed random variable we provide some closed-form expressions for the fading number of some systems with Gaussian fading, including SISO systems with circularly symmetric stationary and ergodic Gaussian fading. The fading number of the latter is determined by the fading mean, fading variance, and the mean squared error in predicting the present fading from its past; it is not directly related to the Doppler spread. For the Rayleigh, Ricean, and multiple-antenna Rayleigh-fading channels we also present firm (nonasymptotic) upper and lower bounds on channel capacity. These bounds are asymptotically tight in the sense that their difference from capacity approaches zero at high SNR, and their ratio to capacity approaches one at low SNR.

Several models of wide-band broadcast communication scenarios are studied with an emphasis on conditions under which, as the bandwidth tends to infinity, time sharing is asymptotically optimal. The models include the Gaussian channel, the Poisson channel, the "very noisy" channel, and the average-power limited fading channel. Only stochastically degraded scenarios are studied.

Lapidoth and Moser (2001) have recently proposed a general technique for obtaining upper bounds on channel capacity via a dual expression in which the maximization over probability distributions on the channel input alphabet is replaced with a minimization over probability distributions on the channel output alphabet. They have also introduced the notion of "capacity achieving input distributions that escape to infinity" in order to study channel capacity at high signal-to-noise (SNR) ratios. In this partly tutorial paper we demonstrate the use of these ideas by applying them to the study of communication over discrete-time channels impaired by additive white Gaussian noise and phase noise.

Watermarking models a copyright protection mechanism where an original source sequence or "covertext" is modified before distribution to the public in order to embed some extra information. The embedding should be transparent (i.e., the modified data sequence or "stegotext" should be similar to the covertext) and robust (i.e., the extra information should be recoverable even if the stegotext is modified further, possibly by a malicious "attacker"). We compute the coding capacity of the watermarking game for a Gaussian covertext and squared-error distortions. Both the public version of the game (covertext known to neither attacker nor decoder) and the private version of the game (covertext unknown to attacker but known to decoder) are treated. While the capacity of the former cannot, of course, exceed the capacity of the latter, we show that the two are, in fact, identical. These capacities depend critically on whether the distortion constraints are required to be met in expectation or with probability one. In the former case, the coding capacity is zero, whereas in the latter it coincides with the value of related zero-sum dynamic mutual information games of complete and perfect information. We also compute the capacity when the attacker is restricted to additive attacks. This capacity turns out to be strictly larger than the watermarking capacity, thus demonstrating that additive attacks are suboptimal. In fact, under the additive attack restriction, capacity turns out to coincide with the capacity of Costa's (1983) model for "writing on dirty paper," thus demonstrating that in Costa's model, the independent and identically distributed (i.i.d.) Gaussian "noise" is the most malevolent power-limited "noise". Additionally, Costa's observation that in the presence of i.i.d. Gaussian "noise," an i.i.d. Gaussian "dirt" process that is noncausally known to the transmitter (but not receiver) does not reduce capacity, is extended to general ergodic "dirt" and to stationary (but not necessarily white) Gaussian "noise".

The analysis of flat-fading channels is often performed under the assumption that the additive noise is white and Gaussian, and that the receiver has precise knowledge of the realization of the fading process. These assumptions imply the optimality of Gaussian codebooks and of scaled nearest-neighbor decoding. Here we study the robustness of this communication scheme with respect to errors in the estimation of the fading process. We quantify the degradation in performance that results from such estimation errors, and demonstrate the lack of robustness of this scheme. For some situations we suggest the rule of thumb that, in order to avoid degradation, the estimation error should be negligible compared to the reciprocal of the signal-to-noise ratio (SNR).

It has recently been shown that at high signal-to-noise ratios (SNR) the capacity of multi-antenna systems over flat fading channels (without receiver or transmitter side-information) typically grows only double-logarithmically in the SNR. Here we further refine the analysis and study the "fading number" /spl chi/, which we define as the limit of the difference between channel capacity and log(1+log(1+SNR)). It is suggested that at high SNR, i.e., at rates that significantly exceed the fading number, a capacity increase of one bit per channel use requires the squaring of the SNR, or equivalently, the doubling of the SNR as expressed in decibels. In this loose sense, the fading number can be viewed as the channel limiting rate for power-efficient communication. Note, however, that the fading number may be negative. While the use of multiple antennas does not typically change the double-logarithmic asymptotic dependence of channel capacity on the SNR, multiple antennas do typically increase the fading number, albeit at times (e.g., in the Rayleigh fading case) only in an additive way that grows only logarithmically with the number of antennas.

The mismatch capacity of a channel is the highest rate at which reliable communication is possible over the channel with a given (possibly suboptimal) decoding rule. This quantity has been studied extensively for single-letter decoding rules over discrete memoryless channels (DMCs). Here we extend the study to memoryless channels with general alphabets and to channels with memory with possibly non-single-letter decoding rules. We also study the wide-band limit, and, in particular, the mismatch capacity per unit cost, and the achievable rates on an additive-noise spread-spectrum system with single-letter decoding and binary signaling.

An algorithm is proposed for universal decoding of convolutional/trellis codes employed over unknown channels. On discrete memoryless channels and at rates below the channel's computational cutoff rate (for a uniform input distribution), the algorithm achieves an asymptotic complexity-performance tradeoff similar to the tradeoff achieved by the Viterbi (1979) algorithm, but with the benefit that the algorithm's implementation does not require knowledge of the channel law. The algorithm is also applicable to channels with memory, and in particular to intersymbol interference (ISI) channels, to channels with nonlinear ISI, and even to general finite-state channels.

A universal decoder for a parametric family of channels is a decoder whose structure depends on the family but not on the individual channel over which transmission takes place, and it yet attains the same random-coding error exponent as the maximum-likelihood receiver tuned to the channel in use. The existence and structure of such decoders is demonstrated under relatively mild conditions of continuity of the channel law with respect to the parameter indexing the family. It is further shown that under somewhat stronger conditions on the family of channels, the convergence of the performance of the universal decoder to that of the optimal decoder is uniform over the set of channels. Examples of families for which universal decoding is demonstrated include the family of finite-state channels and the family of Gaussian intersymbol interference channels.

In many communication situations, the transmitter and the receiver must be designed without a complete knowledge of the probability law governing the channel over which transmission takes place. Various models for such channels and their corresponding capacities are surveyed. Special emphasis is placed on the encoders and decoders which enable reliable communication over these channels.

The Poisson multiple-access channel (MAC) models many-to-one optical communication through an optical fiber or in free space. For this model we compute the capacity region for the two-user case as a function of the allowed peak power. Focusing on the maximum throughput we generalize our results to the case where the users are subjected to an additional average-power constraint and to the many-users case. We show that contrary to the Gaussian MAC, in the Poisson MAC the maximum throughput is bounded in the number of users. We quantify the loss that is incurred when time-division multiple access (TDMA) is employed and show that while in the two-user case and in the absence of dark current the penalty is rather mild, the penalty can be quite severe in the many-users case in the presence of large dark current. We introduce a generalized TDMA technique that mitigates this loss to a large extent.

A transmitter and receiver need to be designed to guarantee reliable communication on any channel belonging to a given family of finite-state channels defined over common finite input, output, and state alphabets. Both the transmitter and receiver are assumed to be ignorant of the channel over which transmission is carried out and also ignorant of its initial state. For this scenario we derive an expression for the highest achievable rate. As a special case we derive the compound channel capacity of a class of Gilbert-Elliott channels.

A universal decoder for a family of channels is a decoder that can be designed without prior knowledge of the particular channel in the family over which transmission takes place, and it yet attains the same random-coding error exponent as the optimal decoder tuned to the channel in use. We study Ziv's (1985) decoding algorithm, which is based on Lempel-Ziv (1978) incremental string parsing, and demonstrate that while it was originally proposed as a universal decoder for the family of finite-state channels with deterministic (but unknown) transitions, it is in fact universal for the broader class of all finite-state channels. We also demonstrate that the generalized likelihood decoder may not be universal even for finite families for which a universal decoder always exists.

An upper bound is derived on the probability that at least one of a sequence of B consecutive bits at the output of a Viterbi (1979) decoder is in error. Such a bound is useful for the analysis of concatenated coding schemes employing an outer block code over GF(2/sup B/) (typically a Reed-Solomon (RS) code), an inner convolutional code, and a symbol (GF(2/sup B/)) interleaver separating the two codes. The bound demonstrates that in such coding schemes a symbol interleaver is preferable to a bit interleaver. It also suggests a new criterion for good inner convolutional codes.

Using a codebook C, a source sequence is described by the codeword that is closest to it according to the distortion measure d/sub 0/(x,x/spl circ//sub 0/). Based on this description, the source sequence is reconstructed to minimize the reconstruction distortion as measured by d/sub 1/(x,x/spl circ//sub 1/), where, in general, d/sub 1/(x,x/spl circ//sub 1/)/spl ne/d/sub 0/(x,x/spl circ//sub 0/). We study the minimum resulting d/sub 1/(x,x/spl circ//sub 1/)-distortion between the reconstructed sequence and the source sequence as we optimize over the codebook subject to a rate constraint. Using a random coding argument we derive an upper bound on the resulting distortion. Applying this bound to blocks of source symbols we construct a sequence of bounds which are shown to converge to the least distortion achievable in this setup. This solves the rate distortion dual of an open problem related to the capacity of channels with a given decoding rule-the mismatch capacity. Addressing a different kind of mismatch, we also study the mean-squared error description of non-Gaussian sources with random Gaussian codebooks. It is shown that the use of a Gaussian codebook to compress any ergodic source results in an average distortion which depends on the source via its second moment only. The source with a given second moment that is most difficult to describe is the memoryless zero-mean Gaussian source, and it is best described using a Gaussian codebook. Once a Gaussian codebook is used, we show that all sources of a given second moment become equally hard to describe.

An achievable region is derived for the multiple-access channel under decoding mismatch conditions. It is shown that achievable rates higher than the random coding capacity of the single-user mismatched channel can sometimes be demonstrated by treating the single-user channel as a multiple-access channel. Refining these ideas we derive a lower bound on the capacity of the mismatched single-user channel, which is tighter than previously published bounds. Using this bound, we are able to answer in the negative the question raised by Csiszar and Narayan (see ibid., vol.41, no.1, p.35, 1995) as to whether equality between the mismatch capacity and the matched capacity implies that the random coding lower bound to the mismatch capacity is tight.

We study the performance of a transmission scheme employing random Gaussian codebooks and nearest neighbor decoding over a power limited additive non-Gaussian noise channel. We show that the achievable rates depend on the noise distribution only via its power and thus coincide with the capacity region of a white Gaussian noise channel with signal and noise power equal to those of the original channel. The results are presented for single-user channels as well as multiple-access channels, and are extended to fading channels with side information at the receiver.

Consider the transmission of a finitely interleaved rate 1/n convolutionally encoded message over a channel with memory having two internal states /spl Xi//sub 0/ and /spl Xi//sub 1/ where when in state /spl Xi//sub 0/, the channel resembles a noiseless binary symmetric channel (BSC), whereas when in state /spl Xi//sub 1/, the channel is totally blocked and is well approximated by a binary-input single-output channel. Assume that the channel's internal state is drawn at random once every h channel uses, and then remains constant for the following h channel uses. Further assume that the message is short in comparison to h, and that due to delay constraints, the message must be decoded within Nh channel uses, where N need not be large in comparison to the code's constraint length. Such a model is appropriate for describing a convolutionally coded slow frequency hopping system with non-ideal interleaving, in which every frequency is either totally erased or else noiseless. The probability of a message error, the normalized expected number of bits in error, and the bit error rate (BER) are analytically computed for the periodic N/spl times/h bit and word interleavers, where a bit refers to a binary code symbol, and a word refers to a n-tuple of consecutive bits. An analytic expression for the BER is also given for pseudo-random word and bit interleavers and for the corresponding limiting cases of infinite interleaving, i.e., N/spl rarr//spl infin/. As an example for the use of our methods, we analyze the performance of the GSM system with various interleaving depths and methods. We introduce the notion of "matched" code and interleaver pairs, and argue that this is a desirable property. Several exhaustive searches are carried out for matched codes and interleavers.>

Reliable transmission over a discrete-time memoryless channel with a decoding metric that is not necessarily matched to the channel (mismatched decoding) is considered. It is assumed that the encoder knows both the true channel and the decoding metric. The lower bound on the highest achievable rate found by Csiszar and Korner (1981) and by Hui (1983) for DMC's, hereafter denoted C/sub LM/, is shown to bear some interesting information-theoretic meanings. The bound C/sub LM/ turns out to be the highest achievable rate in the random coding sense, namely, the random coding capacity for mismatched decoding. It is also demonstrated that the /spl epsiv/-capacity associated with mismatched decoding cannot exceed C/sub LM/. New bounds and some properties of C/sub LM/ are established and used to find relations to the generalized mutual information and to the generalized cutoff rate. The expression for C/sub LM/ is extended to a certain class of memoryless channels with continuous input and output alphabets, and is used to calculate C/sub LM/ explicitly for several examples of theoretical and practical interest. Finally, it is demonstrated that in contrast to the classical matched decoding case, here, under the mismatched decoding regime, the highest achievable rate depends on whether the performance criterion is the bit error rate or the message error probability and whether the coding strategy is deterministic or randomized.>

A coding scheme for the channel under peak power and average power constraints on the input is presented, and its asymptotic error exponent is shown to coincide, at all rates below capacity, with the sphere packing error exponent, which, for the case at hand, is known to be unachievable without feedback for rates below the critical rate. An upper bound on the error exponent achievable with feedback is also derived and shown, under a capacity reducing average power constraint, to coincide with the error exponent achieved by the proposed coding scheme; in such a case the coding scheme is asymptotically optimal. Thus, the ideal Poisson channel, limited by a capacity-reducing average power constraint, provides a nontrivial example of a channel for which the reliability function is known exactly both with and without feedback. It is shown that a slight modification of the coding scheme to one of random transmission time can achieve zero-error probability for any rate lower than the ordinary average-error channel capacity.>

An upper bound is derived on the capacity of a Poisson channel that has a stationary input process of a given spectrum and is subjected to peak and average power constraints. The bound is shown to be asymptotically tight with the relaxation of the spectral constraints. Its maximization over a given set of admissible spectra is closely related to an analogous problem in the AWGN regime. The results are used for bounding the capacity of a Poisson channel under a second-moment-bandwidth constraint, as well as the capacity under a strict bandwidth constraint. Asymptotically tight lower bounds on the channel capacity for the above two cases are also presented. The approach for lower bounding the capacity for the latter case yields, as a by-product, improved bounds on the bit-error probability in uncoded amplitude shift keying (and on-off modulation as a special case) operating over a Poisson channel impaired by intersymbol interference.>