Coding schemes for several problems in network information theory are constructed starting from point-to-point channel codes that are designed for symmetric channels. Given that the point-to-point codes satisfy certain properties pertaining to the rate, the error probability, and the distribution of decoded sequences, bounds on the performance of the coding schemes are derived and shown to hold irrespective of other properties of the codes. In particular, we consider the problems of lossless and lossy source coding, Slepian–Wolf coding, Wyner–Ziv coding, Berger–Tung coding, multiple description coding, asymmetric channel coding, Gelfand–Pinsker coding, coding for multiple access channels, Marton coding for broadcast channels, and coding for cloud radio access networks (C-RAN’s). We show that the coding schemes can achieve the best known inner bounds for these problems, provided that the constituent point-to-point channel codes are rate-optimal. This would allow one to leverage commercial off-the-shelf codes for point-to-point symmetric channels in the practical implementation of codes over networks. Simulation results demonstrate the gain of the proposed coding schemes compared to existing practical solutions to these problems.

A new portfolio selection strategy that adapts to a continuous side-information sequence is presented, with a universal wealth guarantee against a class of state-constant rebalanced portfolios with respect to a state function that maps each side-information symbol to a finite set of states. In particular, given that a state function belongs to a collection of functions of finite Natarajan dimension, the proposed strategy is shown to achieve, asymptotically to first order in the exponent, the same wealth as the best state-constant rebalanced portfolio with respect to the best state function, chosen in hindsight from observed market. This result can be viewed as an extension of the seminal work of Cover and Ordentlich (1996) that assumes a single-state function.

A fast-converging Monte Carlo Markov chain decoding algorithm for linear codes over binary input memoryless channels is proposed. The new algorithm generates a small number of candidate estimates by simulating multiple Markov chains in parallel on the codebook, and performs a maximum likelihood decoding among the candidates. The key idea is to transform the generator matrix of the linear code into different systematic forms to construct distinct Markov chains for decoding. To demonstrate the practical feasibility of the proposed decoding algorithm, its performance is evaluated for Reed–Muller codes of length 64 and 128, including ℛℳ(2, 6), ℛℳ(3, 6), ℛℳ(2, 7), and ℛℳ(3, 7) over binary symmetric channels. Simulation results show that the proposed algorithm outperforms that of the recursive projection–aggregation algorithm by Ye and Abbe, and achieves a near-optimal performance.

A new multiple-input multiple-output (MIMO) receiver scheme for practical binary codes is proposed that provides consistent gains over conventional linear receivers. We first develop a practical successive integer forcing (IF) scheme based on practical binary codes rather than lattice codes. We then present the successive cancellation integer forcing (SC-IF) scheme, which combines and enhances successive IF and minimum mean squared error successive interference cancellation (MMSE-SIC). In this scheme, the receiver first decides whether individual decoding or IF sum decoding is appropriate for each data stream, and then conducts successive IF sum decoding only for selected streams while decoding the remaining streams using MMSE-SIC. The proposed SC-IF methodology mitigates the performance loss caused by mismatched IF filtering in fading channels, while attenuating the noise amplification caused by MMSE filtering. Extensive link-level simulations demonstrate that the proposed successive IF significantly improves the basic IF, and the SC-IF improves both the successive IF and MMSE-SIC, offering uniform improvements over conventional linear receivers for most channel correlation and variation parameters and modulation orders at comparable computational costs. These results illustrate the viability of SC-IF as a fundamental building block for high-performance MIMO receivers in 5G-Advanced and/or subsequent-generation communication systems.

A class of parameter-free online linear optimization algorithms is proposed that harnesses the structure of an adversarial sequence by adapting to some side information. These algorithms combine the reduction technique of Orabona and Pal (2016) for adapting coin betting algorithms for online linear optimization with universal compression techniques in information theory for incorporating sequential side information to coin betting. Concrete examples are studied in which the side information has a tree structure and consists of quantized values of the previous symbols of the adversarial sequence, including fixed-order and variable-order Markov cases. By modifying the context-tree weighting technique of Willems, Shtarkov, and Tjalkens (1995), the proposed algorithm is further refined to achieve the best performance over all adaptive algorithms with tree-structured side information of a given maximum order in a computationally efficient manner.

A new approach to$L_{2}$-consistent estimation of a general density functional using$k$-nearest neighbor distances is proposed, where the functional under consideration is in the form of the expectation of some function$f$of the densities at each point. The estimator is designed to be asymptotically unbiased, using the convergence of the normalized volume of a$k$-nearest neighbor ball to a Gamma distribution in the large-sample limit, and naturally involves the inverse Laplace transform of a scaled version of the function$f$. Some instantiations of the proposed estimator recover existing$k$-nearest neighbor based estimators of Shannon and Rényi entropies and Kullback–Leibler and Rényi divergences, and discover new consistent estimators for many other functionals such as logarithmic entropies and divergences. The$L_{2}$-consistency of the proposed estimator is established for a broad class of densities for general functionals, and the convergence rate in mean squared error is established as a function of the sample size for smooth, bounded densities.

The problem of online prediction with sequential side information under logarithmic loss is studied, and general upper and lower bounds on the minimax regret incurred by the predictor is established. The upper bounds on the minimax regret are obtained by constructing and analyzing a probability assignment based on mixture probability assignments in universal compression, and the lower bounds are obtained by way of a redundancy–capacity theorem. A tight characterization of the regret is provided in some special settings.

Coding schemes for asymmetric channels and channels with state are developed starting from a pair of linear codes designed for symmetric channels. Guarantees on the block error rate performance of the coding schemes are derived in terms of the parameters of the constituent codes. Assuming the constituent codes satisfy some properties on the rate, the error probability, and the distribution of the Hamming distance to decoded sequences, the performance guarantees hold irrespective of other properties of the codes. This would allow one to leverage commercial off-the-shelf codes for point-to-point symmetric channels to design codes for asymmetric channels and channels with state known noncausally at the encoder.

An interactive communication channel model in which information is exchanged through the action of tossing one or more tokens, potentially of multiple types, is proposed. Two scenarios—point-to-point communication with token feedback and two-way communication—are studied. The capacity of the token passing channel with token feedback and the capacity region for the two-way token passing channel are characterized.

This paper proposes a special variant of Laplacian eigenmaps, whose solution is characterized by the underlying density and the eigenfunctions of the associated Hilbert-Schmidt operator of a similarity kernel function. In contrast to existing kernel-based spectral methods such as kernel principal component analysis and Laplacian eigenmaps, the new embedding algorithm only involves estimating density at each query point without any eigendecomposition of a matrix. A concrete example of dot-product kernels over hypersphere is provided to illustrate the applicability of the proposed framework.

A joint channel estimation and channel coding scheme is presented for channels with memory using polar codes. Unlike the conventional approach of first estimating all channel parameters and then performing channel decoding separately, the proposed scheme incorporates a subset of reliable estimates of channel parameters into the decoding procedure and computes decoding metrics averaged over the statistical behavior of the channel. Specifically, decoding algorithms for finite-state Markov channels of any order, for the Gauss-Markov channel and for flat-fading channels are presented. Further, by adapting list decoding to identify reliably-decoded bits within a codeword, channel estimation and decoding steps are performed iteratively to boost the reliability of channel estimation as well as error correction. In order to improve the performance even further, a new pilot arrangement scheme is developed that utilizes the structure of polar codes and sends pilot symbols embedded within the polar codewords. This construction can be viewed as a new family of shortened polar codes that can be of independent interest. Simulation results demonstrate the benefit of the proposed approach compared to existing solutions.

The essential interactive capacity of a discrete memoryless channel is defined in this paper as the maximal rate at which the transcript of any interactive protocol can be reliably simulated over the channel, using a deterministic coding scheme. In contrast to other interactive capacity definitions in the literature, this definition makes no assumptions on the order of speakers (which can be adaptive) and does not allow any use of private/public randomness; hence, the essential interactive capacity is a function of the channel model only. It is shown that the essential interactive capacity of any binary memoryless symmetric (BMS) channel is at least 0.0302 its Shannon capacity. To that end, we present a simple coding scheme, based on extended-Hamming codes combined with error detection, that achieves the lower bound in the special case of the binary symmetric channel (BSC). We then adapt the scheme to the entire family of BMS channels, and show that it achieves the same lower bound using extremes of the Bhattacharyya parameter.

We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences$U^{n}$and$V^{n}$respectively, drawn from a joint distribution$p_{UV}^ {\otimes n}$, and wish to locally generate sequences$X^{n}$and$Y^{n}$respectively with a joint distribution that is close (in KL divergence) to$p_{XY}^ {\otimes n}$. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between$U$and$V$is nonzero, and we conjecture that only scalar Markov chains$X-U-V-Y$can be simulated otherwise. Motivated by this conjecture, we further examine the case where both$p_{UV}$and$p_{XY}$are doubly symmetric binary sources with parameters$p,q\leq 1/2$respectively. While it is trivial that in this case$p\leq q$is both necessary and sufficient, we use Fourier analytic tools to show that when$p$is close to$q$then any successful simulation is close to being scalar in the total variation sense.

Uplink and downlink cloud radio access networks are modeled as two-hop K-user L-relay networks, whereby small base-stations act as relays for end-to-end communications and are connected to a central processor via orthogonal fronthaul links of finite capacities. Simplified versions of network compress-forward (or noisy network coding) and distributed decode-forward are presented to establish inner bounds on the capacity region for uplink and downlink communications, that match the respective cutset bounds to within a finite gap independent of the channel gains and signal to noise ratios. These approximate capacity regions are then compared with the capacity regions for networks with no capacity limit on the fronthaul. Although it takes infinite fronthaul link capacities to achieve these “fronthaul-unlimited” capacity regions exactly, these capacity regions can be approached approximately with finite-capacity fronthaul. The total fronthaul link capacities required to approach the fronthaul-unlimited sum-rates (for uplink and downlink) are characterized. Based on these results, the capacity scaling law in the large network size limit is established under certain uplink and downlink network models, both theoretically and via simulations.

Monte Carlo Markov chain (MCMC) decoding is a randomized algorithm which has been proven to be near-optimal in terms of decoding error probability. However, the exponentially slow mixing rate of Markov chains seems to preclude MCMC decoding from applications concerning even short blocklength codes. In contrast, belief propagation (BP) is a deterministic algorithm that is empirically fast but sub-optimal in error rate when it is used to decode low-density parity-check (LDPC) codes. In this paper, a code-independent BP-MCMC hybrid decoder is devised for short-blocklength LDPC codes. Theoretical error analysis of the hybrid algorithm is provided. Preliminary experiments show that the preprocessing of BP successfully reduces the time complexity of MCMC decoding and hence significantly improves the applicability of MCMC decoders to short LDPC codes.

Codes are developed for two-user multiple access and broadcast channels starting from Gelfand-Pinsker codes with known block lengths, rates, and error performances. Guarantees are provided on the block error rates of the MAC and BC codes in terms of the parameters of the constituent Gelfand- Pinsker codes. These guarantees hold as long as the constituent codes satisfy the assumed properties on rate, codeword weights, and performances, irrespective of the basic structure and other properties.

In the celebrated coded caching problem studied by Maddah-Ali and Niesen, the peak-traffic network load is to be reduced by first caching some information about contents into individual memories of end users during the off-peak hours and then upon user requests broadcasting some other information about the contents, which, combined with cached information, can let each user recover their requested content. Thus, information-theoretic studies of coded caching involve the optimal tradeoff among communication rates for the two phases of cache placement and content delivery, and the optimal construction of codes for cache placement and content delivery. In order to allow better utilization of network resources, this paper introduces a new caching model in which user requests can arise at any point of time during the cache placement phase, and proposes a successive refinement approach as an answer to this dynamic caching problem. For uniformly random file requests, the optimal tradeoff among average-case delivery rates are characterized when the cache rate is above a well-defined threshold. For arbitrary file requests, a successive caching algorithm is developed to simultaneously reduce worst-case delivery rates at every request time, which are uniformly within a constant multiplicative factor of their respective optima.

The index coding problem studies the fundamental limit on broadcasting multiple messages to their respective receivers with different sets of side information that are represented by a directed graph. The generalized lexicographic product structure in the side information graph is introduced as a natural condition under which the corresponding index coding problem can be decomposed into multiple interacting subproblems, each consisting of vertices with the same adjacency pattern with respect to other subproblems. For side information graphs with this structure, the capacity region is characterized in terms of the subproblem capacity regions combined in the same product structure. The proof is based on dual uses of random coding-one for a new multiletter characterization of the capacity region of a general index coding problem via joint typicality decoding and the other for a construction of a new multiletter code of matching rates from a single-letter code via joint typicality encoding. Several special cases are discussed that recover and strengthen known structural properties of the index coding capacity region.

In index coding, a server broadcasts multiple messages to their respective receivers, each with some side information that can be utilized to reduce the amount of communication from the server. Distributed index coding is an extension of index coding in which the messages are broadcast from multiple servers, each storing different subsets of the messages. In this paper, the optimal tradeoff among the message rates and the server broadcast rates, which is defined formally as the capacity region, is studied for a general distributed index coding problem. Inner and outer bounds on the capacity region are established that have matching sum-rates for all 218 non-isomorphic four-message problems with equal link capacities for all the links from servers to receivers. The proposed inner bound is built on a distributed composite coding scheme that outperforms the existing schemes by incorporating more flexible decoding configurations and enhanced fractional rate allocations into two-stage composite coding, a scheme that was originally introduced for centralized index coding. The proposed outer bound is built on the polymatroidal axioms of entropy, as well as functional dependences such as the fd-separation introduced by the multi-server nature of the problem. This outer bound utilizes general groupings of servers with different levels of granularity, which allows a natural tradeoff between computational complexity and tightness of the bound, and includes and improves upon all existing outer bounds for distributed index coding. Specific features of the proposed inner and outer bounds are demonstrated through concrete examples with four or five messages.

Building on recent development by Padakandla and Pradhan, and by Lim, Feng, Pastore, Nazer, and Gastpar, this paper studies the potential of structured coset coding as a complete replacement for random coding in network information theory. The roles of two techniques used in coset coding to generate nonuniform codewords, namely, shaping and channel transformation, are clarified and illustrated via the simple example of the two-sender multiple access channel. While individually deficient, the optimal combination of shaping via nested coset codes of the same generator matrix (which we refer to as homologous codes) and channel transformation is shown to achieve the same performance as traditional random codes for the general two-sender multiple access channel. The achievability proof of the capacity region is extended to multiple access channels with more than two senders, and with one or more receivers. A quantization argument adapted to the proposed combination of two techniques is presented to establish the achievability proof for their Gaussian counterparts. It is illustrated by an example that combining shaping and channel transformation is useful even when the goal of transmission for a subset of the receivers is to recover a linear combination of messages. These results open up new possibilities of utilizing homologous codes for a broader class of applications.

The problem of computing a linear combination of sources over a multiple access channel is studied. Inner and outer bounds on the optimal tradeoff between the communication rates are established when encoding is restricted to random ensembles of homologous codes, namely, structured nested coset codes from the same generator matrix and individual shaping functions, but when decoding is optimized with respect to the realization of the encoders. For the special case in which the desired linear combination is “matched” to the structure of the multiple access channel in a natural sense, these inner and outer bounds coincide. This result indicates that most, if not all, coding schemes for computation in the literature that rely on random construction of nested coset codes cannot be improved by using more powerful decoders such as the maximum likelihood decoder. The proof techniques are adapted to characterize the rate region for broadcast channels achieved by Marton's (random) coding scheme under maximum likelihood decoding. By generalizing some of the techniques, a single-letter outer bound for the capacity region of the computation problem is presented and compared with the inner bound achieved by homologous codes.

A low-complexity coding scheme is developed to achieve the rate region of maximum likelihood decoding for interference channels. As in the classical rate-splitting multiple access scheme by Grant, Urbanke, and Whiting, the proposed coding scheme uses superposition of multiple codewords with successive cancellation decoding, which can be implemented using standard point-to-point encoders and decoders. Unlike rate-splitting multiple access, which is not rate-optimal for multiple receivers, the proposed coding scheme transmits codewords over multiple blocks in a staggered manner and recovers them successively over sliding decoding windows, achieving the single-stream optimal rate region as well as the more general Han–Kobayashi inner bound for the two-user interference channel. The feasibility of this scheme in practice is verified by implementing it using commercial channel codes over the two-user Gaussian interference channel.

This paper proposes a new scheme that allows the measurement of traffic loads of radio networks by decoding some information about the cell, such as downlink control information (DCI) broadcast on the physical downlink control channel (PDCCH). In the proposed scheme, a client decodes the entire DCI for all user equipments (UEs) with ongoing connections in a cell and extracts some information about the cell, such as the number of active UEs, the number of radio resources occupied, as well as the modulation and coding scheme used by each UE. Based on this information, mobile network carriers can measure exact traffic loads of cells preemptively without affecting ongoing connections. Contrary to an exhaustive searching scheme that attempts to decode DCI with all radio network temporary identifiers (RNTIs), the proposed scheme derives a small set of valid RNTIs by using an inverse function and attempts to decode DCI only with the valid RNTIs instead of the entire set of RNTIs. This reduction enables the client to recover the correct DCI with marginal computational complexity, which allows for real-time decoding of DCI. The simulation results show that the proposed scheme can significantly reduce the complexity required to decode the entire DCI in a cell, compared to the exhaustive searching scheme.

We define the interactive capacity of the binary symmetric channel (BSC) as the maximal rate for which any interactive protocol can be fully and reliably simulated over a pair of BSC's. We show that this quantity is at least 1/40 of the BSC Shannon capacity, uniformly for all channel crossover probabilities. Our result is based on a public-coin rewind-if-error coding scheme in the spirit of Kol & Raz 2013 [1].

We address the problem of simulating a binary interactive protocol over a pair of binary symmetric channels with crossover probability ε. We are interested in the achievable rates of reliable simulation, i.e., in characterizing the smallest possible blowup in communications such that a vanishing error probability in the protocol length can be attained. We analyze the family of Mth-order Markovian protocols in which the transmission at every time depends only on the last M bits of the protocol. For M =1 (first-order Markovian) we prove that all protocols can be simulated at Shannon's capacity. For M > 1 we characterize large classes of protocols that can be simulated at Shannon's capacity.

Uplink and downlink cloud radio access networks are modeled as two-hop K-user L-relay networks, whereby small base-stations act as relays and are connected to a central processor via orthogonal fronthaul links of finite capacities. Based on noisy network coding and distributed decode-forward inner bounds on the capacity regions for uplink and downlink, respectively, the total fronthaul link capacity required to approach the centralized MIMO sum-rate is characterized. The capacity scaling law when the network size increases is examined under certain uplink and downlink network models, both theoretically and via simulations.

We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Unand Vnrespectively, drawn from a joint distribution $p_{UV}^{\otimes n}$, and wish to locally generate sequences Xnand Ynrespectively with a joint distribution that is close (in KL divergence) to $p_{XY}^{\otimes n}$. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains $X-U-V-Y$ can be simulated otherwise. Motivated by this conjecture, we further examine the case where both pUVand pXYare doubly symmetric binary sources with parameters $p, q\leq 1/2$ respectively. While it is trivial that in this case $p\leq q$ is both necessary and sufficient, we show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.

A joint channel estimation and channel coding scheme is presented for finite-state Markov channels using polar codes. Unlike the conventional approach of first estimating all channel parameters and then performing channel decoding separately, the proposed scheme incorporates a subset of reliable estimates of channel parameters into the decoding algorithm and computes decoding metrics averaged over the statistical behavior of the Markov channel. By adapting list decoding (without any inner code), channel estimation and decoding steps can be performed iteratively to boost the reliability of channel estimation as well as error correction. In order to improve the performance even further, a new pilot transmission scheme is developed that utilizes the structure of polar codes and sends pilot symbols along with code symbols. This construction can be viewed as a new family of shortened polar codes that can be of independent interest. Simulation results demonstrate the benefit of the proposed approach compared to existing solutions.

A simple and scalable denoising algorithm is proposed that can be applied to a wide range of source and noise models. At the core of the proposed CUDE algorithm is symbol-by-symbol universal denoising used by the celebrated DUDE algorithm, whereby the optimal estimate of the source from an unknown distribution is computed by inverting the empirical distribution of the noisy observation sequence by a deep neural network, which naturally and implicitly aggregates multi-pie contexts of similar characteristics and estimates the conditional distribution more accurately. The performance of CUDE is evaluated for grayscale images of varying bit depths, which improves upon DUDE and its recent neural network based extension, Neural DUDE.

Simplification methods are introduced for composite coding, which is an existing layered random coding technique for the index coding problem. As the problem size grows, the original number of composite indices grows exponentially and the number of possible decoding configurations (decoding sets) grows super exponentially, leading to considerably high computational complexity. The proposed simplifications address both issues and do not affect the performance (tightness) of the coding scheme. Removing composite indices is achieved by pairwise comparison of any two indices and removing one if its corresponding rate can be transferred without loss to the other in the expressions of the achievable rate region. Decoding configurations are reduced by establishing a baseline or natural decoding configuration, where no smaller decoding configuration can provide a strictly larger rate region. A heuristic method is also proposed for reducing the number of composite indices even further, but possibly with some performance loss. Numerical results demonstrate good performance with substantial reduction in complexity. To achieve the capacity region for all 9608 non-isomorphic index coding problems with n = 5, a single natural decoding configuration per problem and less than 3 out of 25-1=31 composite indices are sufficient, on average. In only 31 problems, 7 to at most 10 composite indices are used.

Recent studies by Padakandla and Pradhan, and by Lim, Feng, Pastore, Nazer, and Gastpar built the framework of nested coset codes for the computation problem, namely, computing a desired linear combination of sources over a multiple access channel. This paper presents an outer bound on the optimal rate region for the computation problem when the encoding strategy is restricted to random ensembles of homologous codes, namely, structured nested coset codes from the same generator matrix and individual shaping functions based on joint typicality encoding. The optimal rate region is characterized when the desired linear combination and the channel structure are matched. Under this condition, a suboptimal joint typicality decoding rule is shown to achieve the optimal rate region. This result implies that the performance of random homologous code ensembles cannot be improved by using the optimal maximum likelihood decoder for the aforementioned class of computation problems.

The Liu-Cuff-Verdu lemma states that in estimating a source X from an observation Y, making a random guess X' from the posterior p(xly) can go wrong at most twice as often as the optimal answer. Several variations of this fundamental, yet rather arcane, result are explored for detection, decoding, and estimation problems.

We extend the composite coding (CC) scheme for the index coding problem from two layers to more layers of random binning. We explicitly introduce the three-layer composite coding (TLCC) scheme and provide the achievable rate region and the error analysis for it. We present a concrete non-trivial example with n = 7 messages where the TLCC strictly outperforms the CC scheme. We also present a number of simplification methods for the TLCC scheme towards better understanding of the scheme, as well as significantly reducing its computational complexity. We further prove that even a simplified version of the TLCC, which can be possibly weaker than the TLCC, still subsumes the CC scheme.

We study the index coding problem in the presence of an eavesdropper, where the aim is to communicate without allowing the eavesdropper to learn any single message aside from the messages it may already know as side information. We establish an outer bound on the underlying secure capacity region of the index coding problem, which includes polymatroidal and security constraints, as well as the set of additional decoding constraints for legitimate receivers. We then propose a secure variant of the composite coding scheme, which yields an inner bound on the secure capacity region of the index coding problem. For the achievability of secure composite coding, a secret key with vanishingly small rate may be needed to ensure that each legitimate receiver who wants the same message as the eavesdropper, knows at least two more messages than the eavesdropper. For all securely feasible index coding problems with four or fewer messages, our numerical results establish the secure index coding capacity region.

Uplink and downlink cloud radio access networks are modeled as two-hop K-user L-relay networks, whereby small base-stations act as relays and are connected to a central processor via orthogonal links of finite capacity. Simplified versions of noisy network coding and distributed decode-forward are used to establish inner bounds on the capacity region for uplink and downlink communications, respectively. Through a careful analysis, the uplink inner bound is shown to achieve the cutset bound on the capacity region universally within O (log L) bits per user. The downlink inner bound achieves the cutset bound with a slightly looser gap of O(log(KL)). These tight per-user gap results are extended to the situations in which the nodes have multiple antennas.

The distributed index coding problem is studied, whereby multiple messages are stored at different servers to be broadcast to receivers with side information. First, the existing composite coding scheme is enhanced for the centralized (single-server) index coding problem, which is then merged with fractional partitioning of servers to yield a new coding scheme for distributed index coding. New outer bounds on the capacity region are also established. For all distributed index coding problems with n ≤ 4 messages and equal server link capacities, the achievable sum-rate of the proposed distributed composite coding scheme match the outer bounds, thus establishing the sum-capacity for these problems.

Building on recent development by Padakandla and Pradhan, and by Lim, Feng, Pastore, Nazer, and Gastpar, this paper studies the potential of structured coding as a complete replacement for random coding in network information theory. The roles of two techniques used in nested coset coding to generate nonuniform codewords, namely, shaping and channel transformation, are clarified and illustrated via the simple example of the two-sender multiple access channel. While individually deficient, the optimal combination of shaping and channel transformation is shown to achieve the same performance as traditional random codes for this channel model, which opens up new possibilities of utilizing nested coset codes with the same generator matrix for a broader class of applications.

Capacity bounds are studied for the multiple-antenna complex Gaussian relay channel with t1transmitting antennas at the sender, r2receiving and t2transmitting antennas at the relay, and r3receiving antennas at the receiver. It is shown that the partial decode-forward coding scheme achieves within (t1,r2) bits from the cutset bound and at least one half of the cutset bound, establishing a good approximate characterization of the capacity. A similar additive gap of (t1+ t2, r3) + r2bits is shown to be achieved by the compress-forward coding scheme. The corresponding results for time-division half-duplex relay channels are also established.

A new coding scheme for general N -node relay networks is presented for unicast, multicast, and broadcast. The proposed distributed decode-forward scheme combines and generalizes Marton coding for single-hop broadcast channels and the Cover-El Gamal partial decode-forward coding scheme for three-node relay channels. The key idea of the scheme is to precode all the codewords of the entire network at the source by multicoding over multiple blocks. This encoding step allows these codewords to carry partial information of the messages implicitly without complicated rate splitting and routing. This partial information is then recovered at the relay nodes and forwarded further. For N-node Gaussian unicast, multicast, and broadcast relay networks, the scheme achieves within 0.5N bits from the cutset bound, and thus from the capacity (region), regardless of the network topology, channel gains, or power constraints. Roughly speaking, distributed decode-forward is dual to noisy network coding, which generalized compress-forward to unicast, multicast, and multiple access relay networks.

For a class of index coding problems with side information graph having the Ramsey number R(i, j) upper bounded by ciajb, it is shown that the clique covering scheme approximates the broadcast rate within a multiplicative factor of O(na+b/a+b+1), where n is the number of messages. Based on this result and known bounds on Ramsey numbers, it is demonstrated that the broadcast rate of planar graphs, line graphs, and fuzzy circular interval graphs can be approximated within a factor of (2n)2/3.

In this paper, we study the capacity region of the general distributed index coding. In contrast to the traditional centralized index coding where a single server contains all n messages requested by the receivers, in the distributed index coding there are 2n- 1 servers, each containing a unique non-empty subset J of the messages and each is connected to all receivers via a noiseless independent broadcast link with an arbitrary capacity CJ≥ 0. First, we generalize the existing outer bound on the capacity region of the centralized problem to the distributed case. Next, building upon the existing centralized composite coding scheme, we propose three distributed composite coding schemes and derive the corresponding inner bounds on the capacity region. We present a number of interesting numerical examples, which highlight the subtleties and challenges of dealing with the distributed index coding, even for very small problem sizes of n = 3 and n = 4.

The multicast capacity of the Gaussian two-hop relay network with one source, N relays, and L destinations is studied. It is shown that a careful modification of the partial decode-forward coding scheme, whereby the relays recover and coherently transmit degraded sets of message parts, achieves the cutset upper bound within (1/2) log N bits regardless of the channel gains and power constraints. This scheme improves upon a previous scheme by Chern and Özgür, which is also based on partial decode-forward yet has an unbounded gap from the cutset bound for L ≥ 2 destinations. When restricted to noncoherent transmission among the relays, the proposed partial decodeforward scheme achieves a slightly larger gap of log N bits from the cutset bound. The computation of this relaxed achievable rate involves evaluating mutual information across L(N + 1) cuts out of the total L2Npossible cuts, providing a very simple linearcomplexity algorithm to approximate the single-source multicast capacity of the Gaussian two-hop relay network.

The sliding-window superposition coding scheme aims to mitigate intercell interference at the physical layer by achieving the simultaneous decoding performance with point-to-point channel codes, low- complexity decoding, and minimal coordination overhead. The associated sliding-window coded modulation (SWCM) scheme can be readily implemented using standard off-the-shelf codes, such as the standard LTE turbo code, and tracks the information-theoretical performance guarantee of sliding-window superposition coding. This paper investigates how the basic SWCM scheme performs for the Ped-B fading interference channel model and proposes several improvements in transceiver design, such as soft decoding, input bit-mapping and layer optimization, and power control. Our enhanced SWCM scheme achieves the rates higher than those of the basic SWCM scheme by 10% to 20%, which already shows a significant gain over existing schemes that ignore modulation or coding information of interfering signals. This result confirms the potential of SWCM as a basic building block for physical-layer interference management in 5G and subsequent generations of cellular networks.

The capacity region of the index coding problem is characterized through the notion of confusion graph and its fractional chromatic number. Based on this multiletter characterization, several structural properties of the capacity region are established, some of which are already noted by Tahmasbi, Shahrasbi, and Gohari, but proved here with simple and more direct graph-theoretic arguments. In particular, the capacity region of a given index coding problem is shown to be simple functionals of the capacity regions of smaller subproblems when the interaction between the subproblems is none, one-way, or complete.

The optimal rate region for interference networks is characterized when encoding is restricted to random code ensembles with superposition coding and time sharing. A simple simultaneous nonunique decoding rule, under which each receiver decodes for the intended message as well as the interfering messages, is shown to achieve this optimal rate region regardless of the relative strengths of signal, interference, and noise. This result implies that the Han-Kobayashi bound, the best known inner bound on the capacity region of the two-user pair interference channel, cannot be improved merely by using the optimal maximum likelihood decoder.

Hybrid analog-digital coding has been used for several communication scenarios, such as joint source-channel coding of Gaussian sources over Gaussian channels and relay communication over Gaussian networks. In this paper, a generalized hybrid coding technique is proposed for communication over discrete memoryless and Gaussian systems, and its utility is demonstrated via three examples-lossy joint source-channel coding over multiple access channels, channel coding over two-way relay channels, and channel coding over diamond networks. The corresponding coding schemes recover and extend several existing results in the literature.

A series of extensions of the index coding schemes based on time sharing by Birk and Kol, by Blasiak, Kleinberg, and Lubetzky, and by Shanmugam, Dimakis, and Langberg are presented. Each extension strictly improves upon the previous extensions as well as the existing schemes. The main idea behind these extensions is local time sharing over subproblems introduced by Shanmugam et al., in which the local side information available at each receiver is exploited to send the subproblm indices with a fewer number of transmissions. The final extension, despite being the best in this class of coding schemes, is shown to be still suboptimal, characterizing the fundamental limit of local time sharing.

The capacity bounds are studied for the multiple-antenna real full-duplex Gaussian relay channel with t1transmitting antennas at the sender, r2receiving and t2transmitting antennas at the relay, and r3receiving antennas at the receiver. It is shown that compress-forward and partial decode-forward achieve within (1/2)(min(t1+ t2, r3) + r2) bits and (1/2) min(t1, r2) bits, respectively, from the cutset bound. Unlike the single-antenna case, partial decode-forward can be arbitrarily better than optimal selection between decode-forward and direct transmission. Similar gap results for half-duplex models are briefly discussed.

A new coding scheme for multicasting a message over a general relay network is presented that extends both network coding for graphical networks by Ahlswede, Cai, Li, and Yeung, and partial decode-forward for relay channels by Cover and El Gamal. For the N-node Gaussian multicast network, the scheme achieves within 0.5N bits from the capacity, improving upon the best known capacity gap results. The key idea is to use multicoding at the source as in Marton coding for broadcast channels. Instead of recovering a specific part of the message as in the original partial decode-forward scheme, a relay in the proposed distributed decode-forward scheme recovers an auxiliary index that implicitly carries some information about the message and forwards it in block Markov coding. This scheme can be adapted to broadcasting multiple messages over a general relay network, extending and refining a recent result by Kannan, Raja, and Viswanath.

Superposition coding with successive cancellation decoding for interference channels is investigated as a low-complexity alternative to the rate-optimal simultaneous decoding. It is shown that regardless of the number of superposition layers and the code distribution of each layer, the standard rate-splitting scheme by Grant, Rimoldi, Urbanke, and Whiting for multiple access channels fails to achieve the simultaneous decoding inner bound on the capacity region for interference channels. A new coding scheme is proposed that uses coding over multiple blocks and sliding-window decoding. With at most two superposition layers, this scheme achieves the simultaneous decoding inner bound for any two-user-pair interference channels without using high-complexity simultaneous multiuser sequence detection. The proposed coding scheme can be also extended to achieve the performance of simultaneous decoding for general interference networks, including the Han-Kobayashi inner bound.

A new coding scheme for broadcasting multiple messages over a general relay network is presented. The proposed distributed decode-forward scheme combines Marton coding for single-hop broadcast channels and partial decode-forward for relay channels by Cover and El Gamal. For the N-node Gaussian broadcast relay network, the scheme achieves within 0.5N bits from the capacity region, extending and refining a recent result by Kannan, Raja, and Viswanath. The main idea of the scheme is to precode all the codewords initially at the source and to decode and forward parts of them on the fly at the relays.

This paper reviews the relationship among several notions of capacity regions of a general discrete memoryless network under different code classes and performance criteria, such as average vs. maximal or block vs. bit error probabilities and deterministic vs. randomized codes. Applications of these meta-theorems include several structural results on capacity regions and a simple proof of the network equivalence theorem.

A new inner bound on the capacity region of the general index coding problem is established. Unlike most existing bounds that are based on graph theoretic or algebraic tools, the bound relies on a random coding scheme and optimal decoding, and has a simple polymatroidal single-letter expression. The utility of the inner bound is demonstrated by examples that include the capacity region for all index coding problems with up to five messages (there are 9846 nonisomorphic ones).

There are two variants of superposition coding schemes. Cover's original superposition coding scheme has code clouds of identical shape, while Bergmans's superposition coding scheme has code clouds of independently generated shapes. These two schemes yield identical achievable rate regions in several scenarios, such as the capacity region for degraded broadcast channels. This paper shows that under optimal decoding, these two superposition coding schemes can result in different rate regions. In particular, it is shown that for the two-receiver broadcast channel, Cover's scheme achieves a larger rate region than Bergmans's scheme in general.

A hypothesis testing problem with communication constraints is studied, in which two nodes interactively communicate with each other in q rounds to perform a simple binary hypothesis testing on whether the observed random sequences at the nodes are generated independently or not. The optimal tradeoff between the communication rates in q rounds interaction and the testing performance measured by the type II error exponent such that the type I error probability asymptotically vanishes. An example is provided that shows that a two-way test outperforms the optimal one-way test and thus that interaction helps for hypothesis testing.

In this paper, we consider the power allocation problem that minimizes the outage probability for Rayleigh slow fading channels with equiprobable QAM inputs. We focus on the uniform power allocation with thresholding (UPAT) policy that assigns nonzero constant power only to a subset of the subchannels. This simple suboptimal policy can significantly alleviate the feedback overhead and the complexity compared to the optimal mercury/water-filling (MWF) solution. Through asymptotic analysis and numerical simulations, we first show that the optimal UPAT, namely, the UPAT with the optimal threshold, performs close to MWF if the constellation size M is large enough that log2M #8811; R, where R is the fixed target transmission rate. This condition log2M #8811; R turns out to define a natural system operating point. As we show through numerical results, if log2M #8776; R, both MWF and the optimal UPAT perform poorly due to having too small M and their performance can be significantly improved by using a larger M. From these results, we conclude that for a given target transmission rate, the optimal UPAT performs close to MWF as long as the constellation size is chosen appropriately not to limit the performance.

The problem of state communication over a discrete memoryless channel with discrete memoryless state is studied when the state information is available strictly causally at the encoder. It is shown that block Markov encoding, in which the encoder communicates a description of the state sequence in the previous block by incorporating side information about the state sequence at the decoder, yields the minimum state estimation error. When the same channel is used to send additional independent information at the expense of a higher channel state estimation error, the optimal tradeoff between the rate of the independent information and the state estimation error is characterized via the capacity-distortion function. It is shown that any optimal tradeoff pair can be achieved via rate-splitting. These coding theorems are then extended optimally to the case of causal channel state information at the encoder using the Shannon strategy.

Four estimators of the directed information rate between a pair of jointly stationary ergodic finite-alphabet processes are proposed, based on universal probability assignments. The first one is a Shannon–McMillan–Breiman-type estimator, similar to those used by Verdú in 2005 and Caiin 2006 for estimation of other information measures. We show the almost sure and$L_{1}$convergence properties of the estimator for any underlying universal probability assignment. The other three estimators map universal probability assignments to different functionals, each exhibiting relative merits such as smoothness, nonnegativity, and boundedness. We establish the consistency of these estimators in almost sure and$L_{1}$senses, and derive near-optimal rates of convergence in the minimax sense under mild conditions. These estimators carry over directly to estimating other information measures of stationary ergodic finite-alphabet processes, such as entropy rate and mutual information rate, with near-optimal performance and provide alternatives to classical approaches in the existing literature. Guided by these theoretical results, the proposed estimators are implemented using the context-tree weighting algorithm as the universal probability assignment. Experiments on synthetic and real data are presented, demonstrating the potential of the proposed schemes in practice and the utility of directed information estimation in detecting and measuring causal influence and delay.

A notion of directed information between two continuous-time processes is proposed. A key component in the definition is taking an infimum over all possible partitions of the time interval, which plays a role no less significant than the supremum over “space” partitions inherent in the definition of mutual information. Properties and operational interpretations in estimation and communication are then established for the proposed notion of directed information. For the continuous-time additive white Gaussian noise channel, it is shown that Duncan's classical relationship between causal estimation error and mutual information continues to hold in the presence of feedback upon replacing mutual information by directed information. A parallel result is established for the Poisson channel. The utility of this relationship is demonstrated in computing the directed information rate between the input and output processes of a continuous-time Poisson channel with feedback, where the channel input process is constrained to be constant between events at the channel output. Finally, the capacity of a wide class of continuous-time channels with feedback is established via directed information, characterizing the fundamental limit on reliable communication.

Optimal coding over the additive white Gaussian noise channel under the peak energy constraint is studied when there is noisy feedback over an orthogonal additive white Gaussian noise channel. As shown by Pinsker, under the peak energy constraint, the best error exponent for communicating an M-ary message, M ≥ 3, with noise-free feedback is strictly larger than the one without feedback. This paper extends Pinsker's result and shows that if the noise power in the feedback link is sufficiently small, the best error exponent for communicating an M-ary message can be strictly larger than the one without feedback. The proof involves two feedback coding schemes. One is motivated by a two-stage noisy feedback coding scheme of Burnashev and Yamamoto for binary symmetric channels, while the other is a linear noisy feedback coding scheme that extends Pinsker's noise-free feedback coding scheme. When the feedback noise power α is sufficiently small, the linear coding scheme outperforms the two-stage (nonlinear) coding scheme, and is asymptotically optimal as α tends to zero. By contrast, when α is relatively larger, the two-stage coding scheme performs better.

We propose four approaches to estimating the directed information rate between a pair of jointly stationary ergodic processes with the help of universal probability assignments. The four approaches yield estimators with different merits such as nonnegativity and boundedness. We establish consistency of these estimators in various senses and derive near-optimal rates of convergence in the minimax sense under mild conditions. The estimators carry over directly to estimating other information measures of stationary ergodic processes, such as entropy rate and mutual information rate, and provide alternatives to classical approaches in the existing literature. Guided by the theoretical results, we use context tree weighting as the vehicle for the implementations of the proposed estimators. Experiments on synthetic and real data are presented, demonstrating the potential of the proposed schemes in practice and the efficacy of directed information estimation as a tool for detecting and measuring causality and delay.

Write-once memory (WOM) is a binary storage medium in which each memory cell is initially in state 0 and can be irreversibly programmed to state 1. This paper studies the problem of writing multiple messages into a WOM. Instead of writing a new message (and obliterating old ones) as in the traditional setup, the user wishes to retain access to some of the previously written messages. The capacity region is studied and code constructions are proposed for three canonical cases.

The capacity region of the -sender Gaussian multiple access channel with feedback is not known in general. This paper studies the class of linear-feedback codes that includes (nonlinear) nonfeedback codes at one extreme and the linear-feedback codes by Schalkwijk and Kailath, Ozarow, and Kramer at the other extreme. The linear-feedback sum-capacity under symmetric power constraints is characterized, the maximum sum-rate achieved by linear-feedback codes when each sender has the equal block power constraint . In particular, it is shown that Kramer's code achieves this linear-feedback sum-capacity. The proof involves the dependence balance condition introduced by Hekstra and Willems and extended by Kramer and Gastpar, and the analysis of the resulting nonconvex optimization problem via a Lagrange dual formulation. Finally, an observation is presented based on the properties of the conditional maximal correlation-an extension of the Hirschfeld-Gebelein-Rényi maximal correlation-which reinforces the conjecture that Kramer's code achieves not only the linear-feedback sum-capacity, but also the sum-capacity itself (the maximum sum-rate achieved by arbitrary feedback codes).

A problem of state information transmission over a state-dependent discrete memoryless channel (DMC) with independent and identically distributed (i.i.d.) states, known causally at the transmitter is investigated. It is shown that block-Markov encoding coupled with channel state estimation conditioned on treating the decoded message and received channel output as side information at the decoder yields the minimum state estimation error. This same channel can also be used to send additional independent information at the expense of a higher channel state estimation error. It is shown that any optimal tradeoff pair can be achieved via a simple rate-splitting technique, whereby the transmitter appropriately allocates its rate between pure information transmission and state estimation.

Motivated by the recently developed hybrid coding scheme for joint source-channel coding, this paper proposes a new coding scheme for noisy relay networks. The proposed coding scheme operates in a similar manner to the noisy network coding scheme, except that each relay node uses the hybrid coding interface to transmit a symbol-by-symbol function of the received sequence and its quantized version. This coding scheme unifies both amplify-forward and noisy network coding and can strictly outperform both. The potential of the hybrid coding interface for relaying is demonstrated through the diamond relay network and two-way relay channel examples.

A new analog-digital hybrid coding architecture for joint source-channel coding is proposed. The encoder generates a channel input by a symbol-by-symbol mapping of the observed (analog) source and its (digital) compression codeword, while the decoder reconstructs the source by a symbol-by-symbol mapping of the (analog) channel output and the decoded (digital) compression codeword from it. When applied to the problem of lossy communication of sources over the two-user discrete memoryless interference channel, this hybrid coding scheme achieves the best known performance and recovers as special cases several previous results on lossless and lossy communication over single hop networks.

Motivated by the emerging interests in non-volatile solid-state computer memories such as flash memories, this paper studies the problem of repeatedly storing information on memory cells with noise and state. The goal is to reliably convey t messages by writing Xjjon an n-cell noisy memory p(yj|xj, yj−1), which stores Yjnat the j-th write. We model this problem as a channel with state and introduce the multiple-write noisy memory model, which includes the write-once memory and flash memory models as special cases. The t-write sum-capacity for the multiple-write noisy memory is established as equation where the maximum is over all pmfs p(x1) Пjt=2 p(uj|yj−1) and functions xj(uj, yj−1), j = 2, …, t. We derive three outer bounds on the capacity region and discuss their extension to other classes of memory models. These results extend Wolf, Wyner, Ziv, and Körner's work on the binary write-once memory and Fu and Vinck's work on the generalized write-once memory to noisy memories.

The notion of directed information was recently introduced for stochastic processes in continuous time. The key idea of the definition is to consider all possible time partitions of a given interval. Unlike the definition of mutual information of discrete-time random variables with continuous alphabets where the supremum over all possible partitions of the alphabets plays an important role, here the infimum over all possible time-partition plays an important role. We show that the fundamental limit on reliable communication for a wide class of continuous-time channels with feedback are characterized using the notion of continuous-time directed information.

In this paper, we consider the problem of exact support recovery of sparse signals via noisy linear measurements. The main focus is finding the sufficient and necessary condition on the number of measurements for support recovery to be reliable. By drawing an analogy between the problem of support recovery and the problem of channel coding over the Gaussian multiple-access channel (MAC), and exploiting mathematical tools developed for the latter problem, we obtain an information-theoretic framework for analyzing the performance limits of support recovery. Specifically, when the number of nonzero entries of the sparse signal is held fixed, the exact asymptotics on the number of measurements sufficient and necessary for support recovery is characterized. In addition, we show that the proposed methodology can deal with a variety of models of sparse signal recovery, hence demonstrating its potential as an effective analytical tool.

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.

A noisy network coding scheme for communicating messages between multiple sources and destinations over a general noisy network is presented. For multi-message multicast networks, the scheme naturally generalizes network coding over noiseless networks by Ahlswede, Cai, Li, and Yeung, and compress-forward coding for the relay channel by Cover and El Gamal to discrete memoryless and Gaussian networks. The scheme also extends the results on coding for wireless relay networks and deterministic networks by Avestimehr, Diggavi, and Tse, and coding for wireless erasure networks by Dana, Gowaikar, Palanki, Hassibi, and Effros. The scheme involves lossy compression by the relay as in the compress-forward coding scheme for the relay channel. However, unlike previous compress-forward schemes in which independent messages are sent over multiple blocks, the same message is sent multiple times using independent codebooks as in the network coding scheme for cyclic networks. Furthermore, the relays do not use Wyner-Ziv binning as in previous compress-forward schemes, and each decoder performs simultaneous decoding of the received signals from all the blocks without uniquely decoding the compression indices. A consequence of this new scheme is that achievability is proved simply and more generally without resorting to time expansion to extend results for acyclic networks to networks with cycles. The noisy network coding scheme is then extended to general multi-message networks by combining it with decoding techniques for the interference channel. For the Gaussian multicast network, noisy network coding improves the previously established gap to the cutset bound. We also demonstrate through two popular Gaussian network examples that noisy network coding can outperform conventional compress-forward, amplify-forward, and hash-forward coding schemes.

We investigate the role of directed information in portfolio theory, data compression, and statistics with causality constraints. In particular, we show that directed information is an upper bound on the increment in growth rates of optimal portfolios in a stock market due to causal side information. This upper bound is tight for gambling in a horse race, which is an extreme case of stock markets. Directed information also characterizes the value of causal side information in instantaneous compression and quantifies the benefit of causal inference in joint compression of two stochastic processes. In hypothesis testing, directed information evaluates the best error exponent for testing whether a random processYcausally influences another processXor not. These results lead to a natural interpretation of directed informationI(Yn→Xn) as the amount of information that a random sequenceYn= (Y1,Y2,...,Yn) causally provides about another random sequenceXn= (X1,X2,...,Xn). A new measure, directed lautum information, is also introduced and interpreted in portfolio theory, data compression, and hypothesis testing.

This paper studies the class of generalized linear feedback codes for additive white Gaussian noise multiple access channel. This class includes (nonlinear) nonfeedback codes at one extreme and linear feedback codes by Schalkwijk and Kailath, Ozarow, and Kramer at the other extreme. The linear sum capacity CL(P), the maximum sum-rate achieved by the generalized linear feedback codes, is characterized under symmetric block power constraints P for all the senders. In particular, it is shown that the Kramer linear code achieves CL(P). Based on the properties of the conditional maximal correlation, an extension of the Hirschfeld-Gebelein-Renyi maximal correlation, it is conjectured that Kramer's linear code achieves not only the linear sum capacity, but also the general sum capacity, i.e., the maximum sum-rate achieved by arbitrary feedback codes.

We study the tradeoffs between the number of measurements, the signal sparsity level, and the measurement noise level for exact support recovery of sparse signals via random noisy measurements. By drawing analogy between exact support recovery and communication over the Gaussian multiple access channel, and exploiting mathematical tools developed for the latter problem, we derive sharp asymptotic sufficient and necessary conditions for exact support recovery. Specifically, when the number of nonzero entries is held fixed, the exact asymptotics on the number of measurements for support recovery is developed. When the number of nonzero entries increases in certain manners, we obtain sufficient conditions tighter than existing results. The proposed information theoretic framework for analyzing the performance of support recovery is further demonstrated to be capable of dealing with a variety of sparse signal recovery models.

Noisy network coding unifies network coding by Ahlswede, Cai, Li, and Yeung for noiseless networks and compress-forward by Cover and El Gamal for noisy relay channels. In particular, it achieves the best known capacity inner bounds for multi-source multicast networks including deterministic networks by Avestimehr, Diggavi, and Tse and erasure networks by Dana, Gowaikar, Palanki, Hassibi, and Effros. This paper extends noisy network coding for multicast networks to networks with general message demand by combining the underlying noisy network coding scheme with decoding techniques for interference channels. At one extreme, noisy network coding is combined with simultaneous decoding, while at the other extreme interference is treated as noise. The potential of noisy network coding as a canonical building block for wireless networks is demonstrated via three examples of Gaussian networks that have drawn recent attentions.

Optimal coding over the additive white Gaussian noise channel under the peak energy constraint is studied when there is noisy feedback over an orthogonal additive white Gaussian noise channel. Previously, Shepp, Wolf, Wyner, and Ziv, and Pinsker showed that under the peak energy constraint the best error exponent for transmission of two messages is achieved by antipodal signaling, regardless of the presence of feedback. This negative result might lead to an impression that under the peak energy constraint, even noise-free feedback does not improve the reliability of communication. Pinsker proved the contrary by showing that the best error exponent for sending M messages does not depend on M, and hence can be strictly larger than the best error exponent without feedback. This paper further extends this and shows that if the noise level in the feedback link is sufficiently small, then the best error exponent for transmission of three messages can be strictly larger than the one without feedback. This result is motivated by a series of recent papers of Burnashev and Yamamoto who considered a similar problem over binary symmetric channels.

In this paper, we develop a universal algorithm to estimate Massey's directed information for stationary ergodic processes. The sequential probability assignment induced by a universal source code plays the critical role in the estimation. In particular, we use context tree weighting to implement the algorithm. Some numerical results are provided to illustrate the performance of the proposed algorithm.

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

This paper studies the question of how well a signal can be reprsented by a sparse linear combination of reference signals from an overcomplete dictionary. When the dictionary size is exponential in the dimension of signal, then the exact characterization of the optimal distortion is given as a function of the dictionary size exponent and the number of reference signals for the linear representation. Roughly speaking, every signal is sparse if the dictionary size is exponentially large, no matter how small the exponent is. Furthermore, an iterative method similar to matching pursuit that successively finds the best reference signal at each stage gives asymptotically optimal representations. This method is essentially equivalent to successive refinement for multiple descriptions and provides a simple alternative proof of the successive refinability of white Gaussian sources.

The notion of directed information is introduced for stochastic processes in continuous time. Properties and operational interpretations are presented for this notion of directed information, which generalizes mutual information between stochastic processes in a similar manner as Massey's original notion of directed information generalizes Shannon's mutual information in the discrete-time setting. As a key application, Duncan's theorem is generalized to estimation problems in which the evolution of the target signal is affected by the past channel noise, and the causal minimum mean squared error estimation is related to directed information from the target signal to the observation corrupted by additive white Gaussian noise. An analogous relationship holds for the Poisson channel.

Motivated by fading channels and erasure channels, the problem of reliable communication over deterministic relay networks is studied, in which relay nodes receive a function of the incoming signals and a random network state. An achievable rate is characterized for the case in which destination nodes have full knowledge of the state information. If the relay nodes receive a linear function of the incoming signals and the state in a finite field, then the achievable rate is shown to be optimal, meeting the cut-set upper bound on the capacity. This result generalizes on a unified framework the work of Avestimehr, Diggavi, and Tse on the deterministic networks with state dependency, the work of Dana, Gowaikar, Palanki, Hassibi, and Effros on linear erasure networks with interference, and the work of Smith and Vishwanath on linear erasure networks with broadcast.

An alternative characterization is given for the coding theorem by Han and Costa, which finds a set of admissible source pairs that can be transmitted reliably over the broadcast channel. The associated coding technique is conceptually simpler and the resulting admissible source region can be shown to include the Gray-Wyner distributed source coding region in a straightforward manner. Incidentally, this new characterization illustrates how the common part between the two random sources does not play any role in broadcasting correlated sources, unlike transmission of correlated sources over the multiple access channel.

The notion of directed information is introduced for stochastic processes in continuous time. Properties and operational interpretations are presented for this notion of directed information, which generalizes mutual information between stochastic processes in a similar manner as Massey's original notion of directed information generalizes Shannon's mutual information in the discrete-time setting. As a key application, Duncan's theorem is generalized to estimation problems in which the evolution of the target signal is affected by the past channel noise, and the causal minimum mean squared error estimation is related to directed information from the target signal to the observation corrupted by additive white Gaussian noise. An analogous relationship holds for the Poisson channel. The notion of directed information as a characterizing of the fundamental limit on reliable communication for a wide class of continuous-time channels with feedback is discussed.

This paper studies the problem of secure communication over a wiretap channel p(y,z|x) with a secure feedback link of rate Rf, where X is the channel input, and Y and Z are channel outputs observed by the legitimate receiver and the eavesdropper, respectively. It is shown that the secrecy capacity, the maximum data rate of reliable communication while the intended message is not revealed to the eavesdropper, is upper bounded as Cs(Rf) les maxmin/p(x) {I(X;Y), I(X;Y |Z) + Rf}. The proof of the bound crucially depends on a recursive argument which is used to obtain the single-letter characterization. This upper bound is shown to be tight for the class of physically degraded wiretap channels. A capacity-achieving coding scheme is presented for this case, in which the receiver securely feeds back fresh randomness with rate Rf, generated independent of the received channel output symbols. The transmitter then uses this shared randomness as a secret key on top of Wyner's coding scheme for wiretap channels without feedback. Hence, when a feedback link is available, the receiver should allocate all resources to convey a new key rather than sending back the channel output.

This paper studies the problem of secure communication over a degraded wiretap channel p(y, z|x) = p(y|x)p(z|y) with secure feedback link of rate Rf, where X is the channel input, and Y and Z are channel outputs observed by the legitimate receiver and the wiretapper respectively. The secrecy capacity is characterized as Cs{Rf) = maxmin{I(X; Y), I(X; Y|Z) + Rf}. p(x)equation. A capacity-achieving coding scheme is presented, in which the receiver securely feeds back fresh randomness with rate Rf, independent of the received channel output. The transmitter then uses the shared randomness as a secret key on top of Wynerpsilas coding scheme for wiretap channel without feedback. Hence, when the receiver has a means of interacting with the transmitter, he should allocate all resources to convey a new key rather than sending back the channel output. For the converse, a recursive argument is used to obtain the single-letter characterization.

We study the problem of gambling in horse races with causal side information and show that Masseypsilas directed information characterizes the increment in the maximum achievable capital growth rate due to the availability of side information. This result gives a natural interpretation of directed information I(Ynrarr Xn) as the amount of information that Yncausally provides about Xn. Extensions to stock market portfolio strategies and data compression with causal side information are also discussed.

The capacity of a class of deterministic relay channels with transmitter input X, receiver output Y, relay output Y1= f(X, Y), and separate noiseless communication link of capacity R0from the relay to the receiver, is shown to be C(R0) = sup min {I(X;Y) + R0, I(X;Y,Y,)}. P(x) Roughly speaking, every bit from the relay is worth one bit to the receiver until saturation at capacity.

We consider the problem of transmitting data at rate over a state-dependent channel with state information available at the sender and at the same time conveying the information about the channel state itself to the receiver. The amount of state information that can be learned at the receiver is captured by the mutual information between the state sequence and the channel output . The optimal tradeoff is characterized between the information transmission rate and the state uncertainty reduction rate , when the state information is either causally or noncausally available at the sender. In particular, when state transmission is the only goal, the maximum uncertainty reduction rate is given by . This result is closely related and in a sense dual to a recent study by Merhav and Shamai, which solves the problem of masking the state information from the receiver rather than conveying it.

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.

The capacity of a class of deterministic relay channels with the transmitter input X, the receiver output Y, the relay output Y1= f(X,Y), and a separate communication link from the relay to the receiver with capacity R0, is shown to be C(R0) =max min{I(X;Y) + R0, I(X;Y,Y1)}. p(x) Thus every bit from the relay is worth exactly one bit to the receiver. Two alternative coding schemes are presented that achieve this capacity. The first scheme, "hash-and-forward", is based on a variation of the usual random binning on the relay outputs, while the second scheme uses the usual "compress-and- forward". In fact, these two schemes can be combined to give a class of optimal coding schemes. As a corollary, this relay capacity result confirms a conjecture by Ahlswede and Han on the capacity of a channel with rate-limited state information at the decoder in the special case when the channel state is recoverable from the channel input and output.

We consider the problem of transmitting data at rateRover a state dependent channelp(y\x,s)with the state information available at the sender and at the same time conveying the information about the channel state itself to the receiver. The amount of state information that can be learned at the receiver is captured by the mutual information I(Sn;Yn) between the state sequence Snand the channel output Yn. The optimal tradeoff is characterized between the information transmission rateRand the state uncertainty reduction rate Delta, when the state information is either causally or noncausally available at the sender. This result is closely related and in a sense dual to a recent study by Merhav and Shamai, which solves the problem of masking the state information from the receiver rather than conveying it.

A coding theorem is proved for a class of stationary channels with 'feedback in which the output Yn= f(Xn-mn, Zn-mn) is the function of the current and past m symbols from the channel input Xnand the stationary ergodic channel noise Zn. In particular, it is shown that the feedback capacity is equal to where I(Xnrarr Yn) = Sigmai=1nI(Xi;Yi|Yi-1) denotes the Massey directed information from the channel input to the output, and the supremum is taken over all causally conditioned distributions p(xnparyn-1) = Pii=1np(xi|xi-1,yi-1)- The main ideas of the proof are the Shannon strategy for coding with side information and a new elementary coding technique for the given channel model without feedback, which is in a sense dual to Gallager's lossy coding of stationary ergodic sources. A similar approach gives a simple alternative proof of coding theorems for finite state channels by Yang-Kavcic-Tatikonda, Chen-Berger, and Permuter-Weissman-Goldsmith.

The feedback capacity of the stationary Gaussian additive noise channel has been open, except for the case where the noise is white. Here we obtain the closed-form feedback capacity of the first-order moving average additive Gaussian noise channel. Specifically, the channel is given by Yi= Xi+ Zi, i = 1,2,..., where the input {Xi} satisfies average power constraint and the noise {Zi} is a first-order moving average Gaussian process defined by Zi= alphaUi-1+ Ui, |alpha| les 1, with white Gaussian innovation {Ui}i=0infin. We show that the feedback capacity of this channel is -log x0, where x0is the unique positive root of the equation rhox2= (1 - x2)(1 - |alpha|x)2, and rho is the ratio of the average input power per transmission to the variance of the noise innovation Ui. The optimal coding scheme parallels the simple linear signalling scheme by Schalkwijk and Kailath for the additive white Gaussian noise channel; the transmitter sends a real-valued information-bearing signal at the beginning of communication, then subsequently processes the feedback noise process through a simple linear stationary first-order autoregressive filter to help the receiver recover the information by maximum likelihood decoding. The resulting probability of error decays doubly exponentially in the duration of the communication. This feedback capacity of the first-order moving average Gaussian channel is very similar in form to the best known achievable rate for the first-order autoregressive Gaussian noise channel studied by Butman, Wolfowitz, and Tiernan, although the optimality of the latter is yet to be established

We extend Shannon's result on the capacity of channels with state information to multiple user channels. More specifically, we characterize the capacity (region) of degraded broadcast channels and physically degraded relay channels where the channel state information is causally available at the transmitters. We also obtain inner and outer bounds on the capacity region for multiple access channels with causal state information at the transmitters

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 formulate a problem of state information transmission over a state-dependent channel with states known at the transmitter. In particular, we solve a problem of minimizing the mean-squared channel state estimation error E/spl par/S/sup n/ - S/spl circ//sup n//spl par/ for a state-dependent additive Gaussian channel Y/sup n/ = X/sup n/ + S/sup n/ + Z/sup n/ with an independent and identically distributed (i.i.d.) Gaussian state sequence S/sup n/ = (S/sub 1/, ..., S/sub n/) known at the transmitter and an unknown i.i.d. additive Gaussian noise Z/sup n/. We show that a simple technique of direct state amplification (i.e., X/sup n/ = /spl alpha/S/sup n/), where the transmitter uses its entire power budget to amplify the channel state, yields the minimum mean-squared state estimation error. This same channel can also be used to send additional independent information at the expense of a higher channel state estimation error. We characterize the optimal tradeoff between the rate R of the independent information that can be reliably transmitted and the mean-squared state estimation error D. We show that any optimal (R, D) tradeoff pair can be achieved via a simple power-sharing technique, whereby the transmitter power is appropriately allocated between pure information transmission and state amplification.

Writing on dirty paper, a variation of the standard additive white Gaussian noise (AWGN) channel with the channel output is considered. The Gaussian noise noncausally known at the transmitter does not affect the capacity of the AWGN channel. This is known as WDP property. The WDP property for three Gaussian multiple user channels with known capacity region is established. The achievable rate regions of corresponding discrete channels is proved. Although those regions may be suboptimal in general, they turn out to be optimal for these Gaussian channels. Alternative proofs can be obtained by successive uses of Costa's WDP coding scheme, from which the WDP property can be established for more general noise and state distributions.