We study a binary distributed hypothesis testing problem where two agents observe correlated binary vectors and communicate compressed information at the same rate to a central decision maker. In particular, we study linear compression schemes and show that simple truncation is the best linear scheme in two cases: (1) testing opposite signs of the same magnitude of correlation, and (2) testing for or against independence. We conjecture, supported by numerical evidence, that truncation is the best linear code for testing any correlations of opposite signs. Further, for testing against independence, we also compute classical random coding exponents and show that truncation, and consequently any linear code, is strictly suboptimal.

We study the input-entropy-constrained Gaussian channel capacity problem in the asymptotic high signal-to-noise ratio (SNR) regime. We show that the capacity-achieving distribution as SNR goes to infinity is given by a discrete Gaussian distribution supported on a scaled integer lattice. Further, we show that the gap between the input entropy and the capacity decreases to zero exponentially in SNR, and characterize this exponent.

In the problem of minimal perfect hashing, we are given a size $k$ subset $\mathcal{A}$ of a universe of keys $[n] = \{1,2, \cdots, n\}$, for which we wish to construct a hash function $h: [n] \to [k]$ such that $h(\cdot)$ maps $\mathcal{A}$ to $[k]$ with no collisions, i.e., the restriction of $h(\cdot)$ to $\mathcal{A}$ is injective. In this paper, we extend the study of minimal perfect hashing to the approximate setting. For an $α\in [0, 1]$, we say that a randomized hashing scheme is $α$-perfect if for any input $\mathcal{A}$ of size $k$, it outputs a hash function which exhibits at most $(1-α)k$ collisions on $\mathcal{A}$ in expectation. One important performance consideration for any hashing scheme is the space required to store the hash functions. For minimal perfect hashing, it is well known that approximately $k\log(e)$ bits, or $\log(e)$ bits per key, is required to store the hash function. In this paper, we propose schemes for constructing minimal $α$-perfect hash functions and analyze their space requirements. We begin by presenting a simple base-line scheme which randomizes between perfect hashing and zero-bit random hashing. We then present a more sophisticated hashing scheme based on sampling which significantly improves upon the space requirement of the aforementioned strategy for all values of $α$.

We study the capacity of the power-constrained additive Gaussian channel with an entropy constraint at the input. In particular, we characterize this capacity in the low signal-to-noise ratio regime at small entropy. This follows as a corollary of the following general result on a moment matching problem: We show that for any continuous random variable with finite moments, the largest number of initial moments that can be matched by a discrete random variable of sufficiently small but positive entropy is three.

We consider a distributed binary hypothesis testing setup where multiple nodes send quantized information to a central processor, which is oblivious to the nodes’ statistics. We study the regime where the missed detection (type-II error) probability decays exponentially and the false alarm (type-I error) probability vanishes. For memoryless quantization, we characterize a tradeoff curve that yields a lower bound for the feasible region of type-II error exponents and the average number of bits sent under the null hypothesis. Moreover, we show that the tradeoff curve is approached at high rates with lattice quantization.

We study a social learning scheme where at every time instant, each agent chooses to receive information from one of its neighbors at random. We show that under this sparser communication scheme, the agents learn the truth eventually and the asymptotic convergence rate remains the same as the standard algorithms, which use more communication resources. We also derive large deviation estimates of the log-belief ratios for a special case where each agent replaces its belief with that of the chosen neighbor.

We consider a problem of labeling a memoryless temporal point process. The labelings have to be done causally. We study the tradeoff between the rate and age of the labeled process and characterize the optimal tradeoff curve. We show that the optimal curve can be achieved with rather simple labeling procedures which repeatedly do the following: Wait for T time units and label the next arrival.

In this work, we introduce a setup where a monitoring entity attempts to distinguish a cheating player among a group of regular players where all players behave in order to maximize their reward. We assume that the cheating player has an "information advantage" compared to the regular players. However, greedily exploiting this advantage will lead to the cheating player being easily distinguishable from its peers. Hence there is a tension between exploitation of the said advantage and the probability of being caught. We characterize this trade-off showing that the cheating player can obtain a higher reward as the number of regular players grows. We also show that, under a certain regime, a monitoring strategy based on the empirical divergence function attains the same normalized reward as the minimax reward.

Previous works on age of information and erasure channels have dealt with specific models and computed the average age or average peak age for certain settings. In this paper, given a source that produces a letter every$T_{s}$seconds and an erasure channel that can be used every$T_{c}$seconds, we ask what is the coding strategy that minimizes the time-average “age of information” that an observer of the channel output incurs. We first analyze the case where the source alphabet and the channel-input alphabet have the same size. We show that a trivial coding strategy is optimal and a closed form expression for the age can be derived. We then analyze the case where the alphabets have different sizes. We use a random coding argument to bound the average age and show that the average age achieved using random codes converges to the optimal average age of linear block codes as the source alphabet becomes large.

We propose a simple model to study the tradeoff between timeliness and distortion, where different pieces of data have a different cost of not being sent. We pose the question of finding the optimal tradeoff as a policy design problem amenable to dynamic programming methods. We study the structural properties of optimal transmission policies, give an algorithmic procedure to find the optimal tradeoff, and numerically evaluate some instances.

We consider finite-level, symmetric quantization procedures for construction and decoding of polar codes. Whether polarization occurs in the presence of quantization is not known in general. In [1], it is shown that a simple three-level quantization procedure polarizes and a calculation method is proposed to obtain a lower bound for achievable rates. We find an improved calculation method for achievable rates and also the exact asymptotic behavior of the block error probability for the simple case. We then prove that certain D-level quantization schemes polarize and give a lower bound on achievable rates. Furthermore, we show that a broad class of quantization procedures result in a weaker form of the polarization phenomenon.

Given a source that produces a letter every Tsseconds and an erasure channel that can be used every Tcseconds, we ask what is the coding strategy that minimizes the time-average "age of information" that an observer of the channel output incurs. We will see that one has to distinguish the cases when the source and channel-input alphabets have equal or different size. In the first case, we show that a trivial coding strategy is optimal and a closed form expression for the age may be derived. In the second, we use random coding argument to bound the average age and show that the average age achieved using random codes converges to the optimal average age as the source alphabet becomes large.

Consider a stream of status updates generated by a source, where each update is of one of two types: priority or ordinary; these updates are to be transmitted through a network to a monitor. We analyze a transmission policy that treats updates depending on their content: ordinary updates are served in a first-come first-served fashion, whereas the priority updates receive preferential treatment. An arriving priority update discards and replaces any currently-in-service priority update, and preempts (with eventual resume) any ordinary update. We model the arrival processes of the two kinds of updates as independent Poisson processes and the service times as two (possibly different rate) exponentials. We find the arrival and service rates under which the system is stable and give closed-form expressions for average peak age and a lower bound on the average age of the ordinary stream. We give numerical results on the average age of both streams and observe the effect of each stream on the age of the other.

Usually, wireless radios are half-duplex, i.e. they can not transmit and receive at the same time over the same frequency band. However, building on self-interference cancellation techniques, full-duplex radios have emerged as a viable paradigm over the recent years. In this paper, we ask the following question: how much can full-duplex increase the capacity of wireless networks? Intuitively, one may expect that full-duplex radios can at most double the capacity of wireless networks, since they enable nodes to transmit and receive at the same time. In this paper, we show that the capacity gain can indeed be larger than a factor of 2; in particular, we construct a specific instance of a wireless relay network where the capacity with full-duplex radios is triple the capacity of the network when the relays are half-duplex. We also propose a universal schedule for half-duplex networks composed of independent, memoryless, point-to-point channels which achieves at least a fraction of 1/4 of the corresponding full-duplex capacity. This means that for wireless networks composed of point-to-point channels full-duplex capability at the relays cannot more than quadruple the capacity of network.

One problem with multiple access channel (MAC) polar codes that are based on MAC polarization is that they may not achieve the entire capacity region. The reason behind this problem is that MAC polarization sometimes induces a loss in the capacity region. This paper provides a single letter necessary and sufficient condition, which characterizes all the MACs that do not lose any part of their capacity region by polarization.

We analyze the exact exponential decay rate of the expected amount of information leaked to the wiretapper in Wyner's wiretap channel setting using wiretap channel codes constructed from both i.i.d. and constant-composition random codes. Our analysis for those sampled from i.i.d. random coding ensemble shows that the previously known achievable secrecy exponent using this ensemble is indeed the exact exponent for an average code in the ensemble. Furthermore, our analysis on wiretap channel codes constructed from the ensemble of constant-composition random codes leads to an exponent which, in addition to being the exact exponent for an average code, is larger than the achievable secrecy exponent that has been established so far in the literature for this ensemble (which in turn was known to be smaller than that achievable by wiretap channel codes sampled from i.i.d. random coding ensemble). We show examples where the exact secrecy exponent for the wiretap channel codes constructed from random constant-composition codes is larger than that of those constructed from i.i.d. random codes and examples where the exact secrecy exponent for the wiretap channel codes constructed from i.i.d. random codes is larger than that of those constructed from constant-composition random codes. We, hence, conclude that, unlike the error correction problem, there is no general ordering between the two random coding ensembles in terms of their secrecy exponent.

We analyze the exact exponential decay rate of the expected amount of information leaked to the wiretapper in Wyner's wiretap channel setting using wiretap channel codes constructed from both i.i.d. and constant-composition random codes. Our analysis for those sampled from i.i.d. random coding ensemble shows that the previously-known achievable secrecy exponent using this ensemble is indeed the exact exponent for an average code in the ensemble. Furthermore, our analysis on wiretap channel codes constructed from the ensemble of constant-composition random codes leads to an exponent which, in addition to being the exact exponent for an average code, is larger than the achievable secrecy exponent that has been established so far in the literature for this ensemble (which in turn was known to be smaller than that achievable by wiretap channel codes sampled from i.i.d. random coding ensemble). We also show examples where the exact secrecy exponent for the wiretap channel codes constructed from random constant-composition codes is larger than that of those constructed from i.i.d. random codes.

We give a simple proof of Arıkan's polarization phenomenon that uses only elementary methods. Using the same method, we show that Arıkan's construction also polarizes non-stationary memoryless channels in the same way it polarizes the stationary memoryless channels.

Polar codes are constructed for arbitrary channels by imposing an arbitrary quasi-group structure on the input alphabet. Just as with usual polar codes, the block error probability under successive cancellation decoding is o(2-N1/2ε), where N is the block length. Encoding and decoding for these codes can be implemented with a complexity of O(N\log N). It is shown that the same technique can be used to construct polar codes for arbitrary multiple access channels by using an appropriate Abelian group structure. Although the symmetric sum capacity is achieved by this coding scheme, some points in the symmetric capacity region may not be achieved. In the case where the channel is a combination of linear channels, we provide a necessary and sufficient condition characterizing the channels whose symmetric capacity region is preserved by the polarization process. We also provide a sufficient condition for having a maximal loss in the dominant face.

A problem of the polar code construction for multiple access channels (MACs) is that they do not always achieve the whole capacity region. This paper provides a single letter necessary and sufficient condition which characterizes all the MACs that do not lose any part of their capacity region by polarization.

We introduce a property that we call Successive Description property for Slepian Wolf coding. We show that Monotone-Chain Polar Codes can be used to construct low-complexity codes that satisfy this property. We discuss applications of this property to network coding problems.

We give a simple proof of Arikan's polarization phenomenon that uses only elementary methods. Using the same method, we show that Arikan's construction also polarizes non-stationary memoryless channels in the same way it polarizes stationary memoryless channels. This is a new result.

We show that the mismatched capacity of binary discrete memoryless channels can be improved by channel combining and splitting via Arikan's polar transform. We also show that the improvement is possible even if the transformed channels are decoded with a mismatched polar decoder.

We prove that channel combining and splitting via Arikan's polarization transformation improves Gallager's reliability function E0for binary input channels. In this sense, polarization creates E0. This observation gives yet another justification as to why the polar transform yields capacity achieving and low complexity codes: the improvement in E0translates to an improvement in complexity-error-probability trade-off. In analyzing polar codes, one examines auxiliary random processes that follow the evolution of information measures as an underlying communication channel undergoes a sequence of transformations. The conclusion of this paper shows that the E0process associated to such an analysis is a submartingale.

The entropy power inequality (EPI) yields lower bounds on the differential entropy of the sum of two independent real-valued random variables in terms of the individual entropies. Versions of the EPI for discrete random variables have been obtained for special families of distributions with the differential entropy replaced by the discrete entropy, but no universal inequality is known (beyond trivial ones). More recently, the sumset theory for the entropy function yields a sharp inequality H(X + X') - H(X) ≥ 1/2 - o(1) when X, X' are independent identically distributed (i.i.d.) with high entropy. This paper provides the inequality H(X + X') - H(X)≥ g(H(X)), where X, X' are arbitrary i.i.d. integer-valued random variables and where g is a universal strictly positive function on R+satisfying g(0) = 0. Extensions to nonidentically distributed random variables and to conditional entropies are also obtained.

We prove that channel combining and splitting via Arikan's polarization transformation improves Gallager's reliability function E0for binary input channels. In this sense polarization `creates' E0. This observation gives yet another justification as to why the polar transform yields capacity achieving and low complexity codes: the improvement in E0translates to an improvement in complexity-error-probability trade-off. In analyzing polar codes, one examines auxiliary random processes that follow the evolution of information measures as an underlying communication channel undergoes a sequence of transformations. The conclusion of this paper shows that the E0process associated to such an analysis is a submartingale.

The entropy power inequality (EPI) provides lower bounds on the differential entropy of the sum of two independent real-valued random variables in terms of the individual entropies. Versions of the EPI for discrete random variables have been obtained for special families of distributions with the differential entropy replaced by the discrete entropy, but no universal inequality is known (beyond trivial ones). More recently, the sumset theory for the entropy function yields a sharp inequality H(X + X') - H(X) ≥ 1/2 - o(l) when X,X' are i.i.d. with high entropy. This paper provides the inequality H(X + X') - H(X) ≥ g(H(X)), where X, X' are arbitrary i.i.d. integer-valued random variables and where g is a universal strictly positive function on R+satisfying g(0) = 0. Extensions to non identically distributed random variables and to conditional entropies are also obtained.

A polarization phenomenon in a special sense is shown for an arbitrary discrete memoryless channel (DMC) by imposing a quasigroup structure on the input alphabet. The same technique is used to derive a polarization theorem for an arbitrary multiple access channel (MAC) by using an appropriate Abelian group structure. These results can be used to construct capacity-achieving polar codes for arbitrary DMCs with a block error probability of o(2-N1/2-ε), and an encoding/decoding complexity of O(N log N), where N is the block length.

We consider the 2nchannels synthesized by the n-fold application of Arıkan's polar transform to a binary erasure channel (BEC). The synthetic channels are BECs themselves, and we show that, asymptotically for almost all these channels, the pairwise correlations between their erasure events are extremely small: the correlation coefficients vanish faster than any exponential in n. Such a fast decay of correlations allows us to conclude that the union bound on the block error probability of polar codes is very tight.

It is conjectured that the covariance matrices minimizing the outage probability under a power constraint for multiple-input multiple-output channels with Gaussian fading are diagonal with either zeros or constant values on the diagonal. In the multiple-input single-output (MISO) setting, this is equivalent to conjecture that the Gaussian quadratic forms having largest tail probability correspond to such diagonal matrices. This paper provides a proof of the conjecture in this MISO setting.

Arikan's polar coding method is extended to two-user multiple-access channels. It is shown that if the two users of the channel use Arikan's construction, the resulting channels will polarize to one of five possible extremals, on each of which uncoded transmission is optimal. The sum rate achieved by this coding technique is the one that corresponds to uniform input distributions. The encoding and decoding complexities and the error performance of these codes are as in the single-user case: O(nlogn) for encoding and decoding, and o(2-n1/2-ε) for the block error probability, where n is the blocklength.

This paper investigates the construction of deterministic measurement matrices preserving the entropy of a random vector with a given probability distribution. In particular, it is shown that for a random vector with i.i.d. discrete components, this is achieved by selecting a subset of rows of a Hadamard matrix such that (i) the selection is deterministic (ii) the fraction of selected rows is vanishing. In contrast, it is shown that for a random vector with i.i.d. continuous components, no entropy preserving measurement matrix allows dimensionality reduction. These results are in agreement with the results of Wu-Verdu on almost lossless analog compression and provide a low-complexity measurement matrix. The proof technique is based on a polar code martingale argument and on a new entropy power inequality for integer-valued random variables.

It is conjectured in [6] that the covariance matrices minimizing the outage probability under a power constraint for MIMO channels with Gaussian fading are diagonal with either zeros or constant values on the diagonal. In the MISO setting, this is equivalent to conjecture that the Gaussian quadratic forms having largest tail probability correspond to such diagonal matrices. This paper provides a proof of the conjecture in this MISO setting.

In this paper, polar codes for the m-user multiple access channel (MAC) with binary inputs are constructed. It is shown that Arikan's polarization technique applied individually to each user transforms independent uses of an m-user binary input MAC into successive uses of extremal MACs. This transformation has a number of desirable properties: 1) the “uniform sum-rate” of the original MAC is preserved, 2) the extremal MACs have uniform rate regions that are not only polymatroids but matroids, and thus, 3) their uniform sum-rate can be reached by each user transmitting either uncoded or fixed bits; in this sense, they are easy to communicate over. A polar code can then be constructed with an encoding and decoding complexity of O(n log n) (where n is the block length), a block error probability of o(exp (- n1/2 - ε)), and capable of achieving the uniform sum-rate of any binary input MAC with arbitrary many users. Applications of this polar code construction to channels with a finite field input alphabet and to the additive white Gaussian noise channel are also discussed.

The issue of how to efficiently represent the data collected by a network of microphones recording spatio-temporal acoustic wave fields is addressed. Each sensor node in the network samples the sound field, quantizes the samples and transmits the encoded samples to some central unit, which computes an estimate of the original sound field based on the information received from all the microphones. Our analysis is based on the spectral properties of the sound field, which are induced by the physics of wave propagation and have a significant impact on the efficiency of the chosen sampling lattice and coding scheme. As field acquisition by a sensor network typically implies spatio-temporal sampling of the field, a multidimensional sampling theorem for homogeneous random fields with compactly supported spectral measures is proved. To assess the loss of information implied by source coding, rate distortion functions for various coding schemes and sampling lattices are determined. In particular, centralized coding, independent coding and some multiterminal schemes are compared. Under the assumption of spectral whiteness of the sound field, it is shown that sampling with a quincunx lattice followed by independent coding is optimal as it achieves the lower bound given by centralized coding.

We consider the problem of efficiently constructing polar codes over binary memoryless symmetric (BMS) channels. The complexity of designing polar codes via an exact evaluation of the polarized channels to find which ones are “good” appears to be exponential in the block length. In [3], Tal and Vardy show that if instead the evaluation if performed approximately, the construction has only linear complexity. In this paper, we follow this approach and present a framework where the algorithms of [3] and new related algorithms can be analyzed for complexity and accuracy. We provide numerical and analytical results on the efficiency of such algorithms, in particular we show that one can find all the “good” channels (except a vanishing fraction) with almost linear complexity in block-length (except a polylogarithmic factor).

Polar coding is a recent channel coding technique invented by Arikan to achieve the 'symmetric capacity' of binary-input memoryless channels. Subsequently it was observed by Korada and Urbanke that such codes are also good for lossy channel coding, achieving the `symmetric rate distortion' bound, when the representation alphabet is binary. In this note we extend this result to the case when the representation alphabet is q-ary, for q a prime number.

Using scaling laws, we obtain estimates of the block error probability of polar codes under successive cancellation decoding. For the binary erasure channel we present an upper and a lower bound for the scaling parameter. Numerically these two bounds match. We also present a scaling law for general binary discrete memoryless channels.

In this paper we consider information-theoretically secure communication between two special nodes (“source” and “destination”) in a memoryless network with authenticated relays, where the secrecy is with respect to a class of eavesdroppers. We develop achievable secrecy rates when authenticated relays also help increase secrecy rate by inserting noise into the network.

We introduce the interference-multiple-access channel, which is a discrete memoryless channel with two transmitters and two receivers, similar to the interference channel. One receiver is required to decode the information encoded at one transmitter, the other receiver is required to decode the messages from both transmitters. We provide an inner bound on the capacity region of this channel, as well as an outer bound for a special class of such channels. For this class, we also quantify the gap between inner and outer bound and show that the bounds match for a semi-deterministic channel, providing a complete characterization. For the Gaussian case, we show that the gap is at most 1 bit, yielding an approximate characterization.

Given that wireless communication occurs in a shared and inherently broadcast medium, the transmissions are vulnerable to undesired eavesdropping. This occurs even when a point-to-point communication is sought, and hence a fundamental question is whether we can utilize the wireless channel properties to establish secrecy. In this paper we consider secret communication between two special nodes ("source" and "destination") in a wireless network with authenticated relays: the message communicated to the destination is to be kept information-theoretically (unconditionally) secret from any eavesdropper within a class. Since the transmissions are broadcast and interfere with each other, complex signal interactions occur. We develop cooperative schemes which utilize these interactions in wireless communication over networks with arbitrary topology, and give provable unconditional secrecy guarantees.

A bound is given on the rate of channel polarization. As a corollary, an earlier bound on the probability of error for polar coding is improved. Specifically, it is shown that, for any binary-input discrete memoryless channel W with symmetric capacity I(W) and any rate R ≪ I(W), the polar-coding block-error probability under successive cancellation decoding satisfies Pe(N, R) ≤ 2−Nβfor any β ≪ 1/2 when the block-length N is large enough.

In this paper we find properties that are shared between two seemingly unrelated lossy source coding setups with side-information. The first setup is when the source and side-information are jointly Gaussian and the distortion measure is quadratic. The second setup is when the side-information is an erased version of the source. We begin with the observation that in both these cases the Wyner-Ziv and conditional rate-distortion functions are equal. We further find that there is a continuum of optimal strategies for the conditional rate distortion problem in both these setups. Next, we consider the case when there are two decoders with access to different side-information sources. For the case when the encoder has access to the side-information we establish bounds on the rate-distortion function and a sufficient condition for tightness. Under this condition, we find a characterization of the rate-distortion function for physically degraded side-information. This characterization holds for both the Gaussian and erasure setups.

In a remarkable paper published in 1976, Burnashev determined the reliability function of variable-length block codes over discrete memoryless channels (DMCs) with feedback. Subsequently, an alternativeachievabilityproof was obtained by Yamamoto and Itoh via a particularly simple and instructive scheme. Their idea is to alternate between a communication and a confirmation phase until the receiver detects the codeword used by the sender to acknowledge that the message is correct. We provide aconversethat parallels the Yamamoto-Itoh achievability construction. Besides being simpler than the original, the proposed converse suggests that a communication and a confirmation phase are implicit in any scheme for which the probability of error decreases with the largest possible exponent. The proposed converse also makes it intuitively clear why the terms that appear in Burnashev's exponent are necessary.

We prove a new outer bound to the capacity region of a certain class of interference channels, and quantify the gap between it and the Han-Kobayashi inner bound. The new bound allows the recovery of the El Gamal-Costa characterization of the capacity region of certain deterministic interference channels, and also the recent characterization by Etkin, Tse and Wang of the capacity region of scalar Gaussian interference channels to within '1 bit'. Moreover, the new bound allows a straightforward generalization of the '1 bit' result to vector Gaussian interference channels.

Fountain codes are currently employed for reliable and efficient transmission of information via erasure channels with unknown erasure rates. This correspondence introduces the notion of fountain capacity for arbitrary channels. In contrast to the conventional definition of rate, in the fountain setup the definition of rate penalizes the reception of symbols by the receiver rather than their transmission. Fountain capacity measures the maximum rate compatible with reliable reception regardless of the erasure pattern. We show that fountain capacity and Shannon capacity are equal for stationary memoryless channels. In contrast, Shannon capacity may exceed fountain capacity if the channel has memory or is not stationary.

We consider the rate-distortion problem for recording a Gaussian acoustic field with an array of sensors equipped with microphones. Our analysis is based on the field's spatio-temporal correlation structure, which is induced by the physics of sound propagation. Under certain assumptions about the spectrum of the wave kernel, we determine the rate-distortion functions for various distributed source coding schemes and sampling lattices. Our results also include an answer to the multiterminal rate-distortion problem for the setup considered in the paper

The kurtosis of a signal is a quantitative measure of how `peaky' it is. In this paper we consider two scenarios of communication over fading channels with kurtosis constraints: in the first, we analyze a non-coherent Rayleigh fading channel where the input signal is required to satisfy a kurtosis constraint in addition to a power constraint. In the second, we find the `worst' fading process that satisfies a kurtosis constraint and has a given second moment, while the fading coefficients are assumed to be known at the receiver. In both cases the transmitter is assumed ignorant of the instantaneous fading realization. The technique that enables our analysis is based on bounding mutual information between random variables which satisfy kurtosis and second moment constraints; the bound is tight in the low second moment regime and can be extended to multi-antenna communications.

Traditionally, the bursty nature of data sources is not taken in consideration by information theory. Random arrival times typically are assumed to be smoothed out by appropriate source coding, rendering any meaningful analysis of the end-to-end delay impossible. On the other hand, network theory directly treats these issues, but over-simplifies the channel model. Particularly, the issues of noise and interference are ignored and no sophisticated coding is allowed. In this paper, we introduce a framework in which some aspects of both sides are incorporated. This results in the formulation of new scheduling problems. In simple settings, we are able to characterize and analyze delay optimal policies

We consider a lossy source coding problem where the description of a source is going to be used by two decoders, each having access to information correlated with the source. This side-information is also present at the encoder. We gave inner and outer bounds to the set of achievable rate and distortion triples. For the special case Gaussian sources wish degraded side-information and squared error distortions, the two bounds coincide and we obtain the true rate-distortion region. As a further specialization, we obtain the rate-distortion region of the Gaussian version of a problem previously solved by Kaspi for discrete memoryless sources. Using this resist we quantify bow much revealing the side-information to the encoder helps in such a Gaussian setup

Fountain codes have been successfully employed for reliable and efficient transmission of information via erasure channels with unknown erasure rates. This paper introduces the notion of fountain capacity for arbitrary channels, and shows that it is equal to the conventional Shannon capacity for stationary memoryless channels. In contrast, when the channel is not stationary or has memory, Shannon capacity and fountain capacity need not be equal

Feedback coupled with variable-length codes can substantially increase the reliability of a discrete memoryless channel (DMC). Burnashev, in a remarkable paper published in 1976, derived an asymptotically achievable lower bound to the average blocklength needed for a system that communicates at a specified rate and achieves a given error probability. We offer an alternative proof of the lower bound. Our proof is simpler than the original, and clarifies the roles of the quantites that appear in the bound by relating one to uncertainty reduction and the other to binary hypothesis testing. In addition, our derivation of the lower bound closely parallels a derivation of an upper bound by Yamamoto and Itoh.

Suppose Q is a family of discrete memoryless channels. An unknown member of Q will be available, with perfect, causal output feedback for communication. We study a scenario where communication is carried by first testing the channel by means of a training sequence, then coding according to the channel estimate. We provide an upper bound on the maximum achievable error exponent of any such coding scheme. If we consider the Binary Symmetric and the Z families of channels this bound is much lower than Burnashev's exponent. For example, in the case of Binary Symmetric Channels this bound has a slope that vanishes at capacity. This is to be compared with our previous result that demonstrates the existence of coding schemes that achieve Burnashev's exponent (that has a nonzero slope at capacity) even though the channel is revealed neither to the transmitter nor to the receiver. Hence, the present result suggests that, in terms of error exponent, a good universal feedback scheme entangles channel estimation with information delivery, rather than separating them.

Burnashev in 1976 gave an exact expression for the reliability function of a discrete memoryless channel (DMC) with noiseless feedback. A coding scheme that achieves this exponent needs, in general, to know the statistics of the channel. Suppose now that the coding scheme is designed knowing only that the channel belongs to a family Q of DMCs. Is there a coding scheme with noiseless feedback that achieves Burnashev's exponent uniformly over Q at a nontrivial rate? We answer the question in the affirmative for two families of channels (binary symmetric, and Z). For these families we show that, for any given fraction, there is a feedback coding strategy such that for any member of the family: i) guarantees this fraction of its capacity as rate, and ii) guarantees the corresponding Burnashev's exponent. Therefore, for these families, in terms of delay and error probability, the knowledge of the channel becomes asymptotically irrelevant in feedback code design: there are blind schemes that perform as well as the best coding scheme designed with the foreknowledge of the channel under use. However, a converse result shows that, in general, even for families that consist of only two channels, such blind schemes do not exist.

We consider communication over a time invariant discrete memoryless channel with noiseless and instantaneous feedback. We assume that the communicating parties are not aware of the underlying channel, however they know that it belongs to some specific family of discrete memoryless channels. Recent results (A. Tchamkerten and I.E. Telatar) show that for certain families (e.g., binary symmetric channels and Z channels) there exists coding schemes that universally achieve any rate below capacity while attaining Burnashev's error exponent. We show that this is not the case in general by deriving an upper bound to the universally achievable error exponent

Suppose Q is a family of discrete memoryless channels. An unknown member of Q is available with perfect (causal) feedback for communication. A recent result (A. Tchamkerten and I.E. Telatar) shows the existence, for certain families of channels (e.g. binary symmetric channels and Z channels), of coding schemes that achieve Burnashev's exponent universally over these families. In other words, in certain cases, there is no loss in the error exponent by ignoring the channel: transmitter and receiver can design optimal blind coding schemes that perform as well as the best feedback coding schemes tuned for the channel under use. Here we study the situation where communication is carried by first testing the channel by means of a training sequence, then coding the information according to the channel estimate. We provide an upper bound on the maximum achievable error exponent of any such scheme. If we consider binary symmetric channels and Z channels this bound is much lower than Burnashev's exponent. This suggests that in terms of error exponent, a good universal feedback scheme entangles channel estimation with information delivery, rather than separating them.

We derive an information-theoretic upper bound on the rate per communication pair in a large ad hoc wireless network. We show that under minimal conditions on the attenuation due to the environment and for networks with a constant density of users, this rate tends to zero as the number of users gets large.

We consider communication over a time-invariant discrete memoryless channel (DMC) with noiseless and instantaneous feedback. We assume that the transmitter and the receiver are not aware of the underlying channel, however, they know that it belongs to some specific family of DMCs. Recent results show that for certain families (e.g., binary-symmetric channels and Z channels) there exist coding schemes that universally achieve any rate below capacity while attaining Burnashev's error exponent. We show that this is not the case in general by deriving an upper bound to the universally achievable error exponent.

We derive an information theoretic upper bound on the maximum achievable rate per communication pair in a large extended ad-hoc wireless network. We show that under a reasonably weak assumption on the attenuation due to environment, this rate tends to zero as the number of users gets large

Communication over unknown discrete memoryless channels with instantaneous and perfect feedback is considered. For a given set of channels we define a notion of optimal coding schemes in terms of achievable rate and error exponent, and prove the existence of such coding schemes for two families of channels

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.

In this paper, we are concerned with the finite-length analysis of low-density parity-check (LDPC) codes when used over the binary erasure channel (BEC). The main result is an expression for the exact average bit and block erasure probability for a given regular ensemble of LDPC codes when decoded iteratively. We also give expressions for upper bounds on the average bit and block erasure probability for regular LDPC ensembles and the standard random ensemble under maximum-likelihood (ML) decoding. Finally, we present what we consider to be the most important open problems in this area.

We present a general method for computing the asymptotic input-output weight distribution of convolutional encoders. In some instances, one can derive explicit analytic expressions. In general, though, to determine the growth rate of the input-output weight distribution for a particular normalized input weight /spl kappa/ and output weight /spl omega/, a system of polynomial equations has to be solved. This method is then used to determine the asymptotic weight distribution of various concatenated code ensembles and to derive lower bounds on the thresholds of these ensembles under maximum-likelihood (ML) decoding.

We consider multiple antenna systems in which a large number of antennas occupy a given physical volume. In this regime the assumptions of the standard models of multiple antennas systems become questionable. We show that for such spatially dense multiple antenna systems one should expect the behavior of the capacity to be qualitatively different than what the standard multiple antenna models predict.

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.

We investigate the capacity and mutual information of a broadband fading channel consisting of a finite number of time-varying paths. We show that the capacity of the channel in the wideband limit is the same as that of a wideband Gaussian channel with the same average received power. However, the input signals needed to achieve the capacity must be "peaky" in time or frequency. In particular, we show that if white-like signals are used instead (as is common in spread-spectrum systems), the mutual information is inversely proportional to the number of resolvable paths L/spl tilde/ with energy spread out, and in fact approaches 0 as the number of paths gets large. This is true even when the paths are assumed to be tracked perfectly at the receiver. A critical parameter L/spl tilde//sub crit/ is defined in terms of system parameters to delineate the threshold on L over which such overspreading phenomenon occurs.

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.

We define zero-error list capacities for discrete memoryless channels. We find lower bounds to, and a characterization of these capacities. As is usual for such zero-error problems in information theory, the characterization is not generally a single-letter one. Nonetheless, we exhibit a class of channels for which a single letter characterization exists. We also show how the computational cutoff rate relates to the capacities we have defined.

We develop and analyze a multiaccess communication model over the additive Gaussian noise channel. The framework is information-theoretic; nonetheless it also incorporates some queueing-theoretic aspects of the problem.>