Search

We investigate a privacy-signaling game problem in which a sender with privacy concerns observes a pair of correlated random vectors which are modeled as jointly Gaussian. The sender aims to hide one of these random vectors and convey the other one whereas the objective of the receiver is to accurately estimate both of the random vectors. We analyze these conflicting objectives in a game theoretic framework with quadratic costs where depending on the commitment conditions (of the sender), we consider Nash or Stackelberg (Bayesian persuasion) equilibria. We show that a payoff dominant Nash equilibrium among all admissible policies is attained by a set of explicitly characterized linear policies. We also show that a payoff dominant Nash equilibrium coincides with a Stackelberg equilibrium. We formulate the information bottleneck problem within our Stackelberg framework under the mean squared error distortion criterion where the information bottleneck setup has a further restriction that only one of the random variables is observed at the sender. We show that this MMSE Gaussian Information Bottleneck Problem admits a linear solution which is explicitly characterized in the paper. We provide explicit conditions on when the optimal solutions, or equilibrium solutions in the Nash setup, are informative or noninformative. [ABSTRACT FROM AUTHOR]

This paper presents explicit solutions for two related non-convex information extremization problems due to Gray and Wyner in the Gaussian case. The first problem is the Gray-Wyner network subject to a sum-rate constraint on the two private links. Here, our argument establishes the optimality of Gaussian codebooks and hence, a closed-form formula for the optimal rate region. The second problem is Wyner’s common information and a generalization thereof, where conditional independence is generalized to a limit on the conditional mutual information. We present full explicit solutions for the scalar as well as the vector case. [ABSTRACT FROM AUTHOR]

This paper employs auxiliary receivers as a mathematical tool to identify Gallager-type auxiliary random variables and write outer bounds for some basic multiuser settings. This approach is then applied to the relay, interference, and broadcast channel settings, yielding new outer bounds that improve on existing outer bounds and strictly outperform classical outer bounds. For instance, we strictly improve on: the cutset outer bound for the scalar Gaussian relay channel, the outer bounds for the Gaussian Z-interference channel, and the outer bounds for the two receiver broadcast channel. [ABSTRACT FROM AUTHOR]

In this paper, capacity bounds for the two-user interference channels with cooperative receivers via conferencing links of finite capacities are investigated. Capacity results known for these communication scenarios are limited to a very few special cases of the one-sided channels. One of the challenges in obtaining capacity limits of such cooperative networks is how to establish efficient capacity outer bounds for them. In this paper, by applying new techniques, novel capacity outer bounds are established for the interference channels with conferencing receivers. Using the outer bounds, several new capacity results are proved for interesting channels with unidirectional cooperation in strong and mixed interference regimes. A conferencing link (between receivers) may be utilized to provide a receiver with “information about its desired signal” or “information about its interfering signal”. It is demonstrated that both strategies can be helpful to achieve capacity. Finally, for the case of Gaussian interference channel with conferencing receivers, it is argued that our outer bound is strictly tighter than the previous one derived by Wang and Tse. [ABSTRACT FROM AUTHOR]

A coding scheme for transmission of a bit maps a given bit to a sequence of channel inputs (called the codeword associated with the transmitted bit). In this paper, we study the problem of designing the best code for a discrete Poisson channel with memory (under peak-power and total-power constraints). The outputs of a discrete Poisson channel with memory are Poisson distributed random variables with a mean comprising of a fixed additive noise and a linear combination of past input symbols. Assuming a maximum-likelihood (ML) decoder, we search for a codebook that has the smallest possible error probability. This problem is challenging because error probability of a code does not have a closed-form analytical expression. For the case of having only a total-power constraint, the optimal code structure is obtained, provided that the blocklength is greater than the memory length of the channel. For the case of having only a peak-power constraint, the optimal code is derived for arbitrary memory and blocklength in the high-power regime. For the case of having both the peak-power and total-power constraints, the optimal code is derived for memoryless Poisson channels when both the total-power and the peak-power bounds are large. [ABSTRACT FROM AUTHOR]

In this paper, a new model for arbitrarily varying classical-quantum channels is proposed. In this model, a jammer has side information. The communication scenario in which a jammer can select only classical inputs as a jamming sequence is considered in the first part of the paper. This situation corresponds to the standard model of arbitrarily varying classical-quantum channels. Two scenarios are considered. In the first scenario, the jammer knows the channel input, while in the second scenario the jammer knows both the channel input and the message. The transmitter and receiver share a secret random key with a vanishing key rate. The capacity for both average and maximum error criteria for both scenarios is determined in this paper. A strong converse is also proved. It is shown that all these corresponding capacities are equal, which means that additionally revealing the message to the jammer does not change the capacity. The communication scenario with a fully quantum jammer is considered in the second part of the paper. A single letter characterization for the capacity with secret random key as assistance for both average and maximum error criteria is derived in the paper. [ABSTRACT FROM AUTHOR]

Algebraic network information theory is an emerging facet of network information theory, studying the achievable rates of random code ensembles that have algebraic structure, such as random linear codes. A distinguishing feature is that linear combinations of codewords can sometimes be decoded more efficiently than codewords themselves. The present work further develops this framework by studying the simultaneous decoding of multiple messages. Specifically, consider a receiver in a multi-user network that wishes to decode several messages. Simultaneous joint typicality decoding is one of the most powerful techniques for determining the fundamental limits at which reliable decoding is possible. This technique has historically been used in conjunction with random i.i.d. codebooks to establish achievable rate regions for networks. Recently, it has been shown that, in certain scenarios, nested linear codebooks in conjunction with “single-user” or sequential decoding can yield better achievable rates. For instance, the compute–forward problem examines the scenario of recovering $L \le K$ linear combinations of transmitted codewords over a $K$ -user multiple-access channel (MAC), and it is well established that linear codebooks can yield higher rates. This paper develops bounds for simultaneous joint typicality decoding used in conjunction with nested linear codebooks, and applies them to obtain a larger achievable region for compute–forward over a $K$ -user discrete memoryless MAC. The key technical challenge is that competing codeword tuples that are linearly dependent on the true codeword tuple introduce statistical dependencies, which requires careful partitioning of the associated error events. [ABSTRACT FROM AUTHOR]

Classical multiuser information theory studies the fundamental limits of models with a fixed (often small) number of users as the coding blocklength goes to infinity. This paper proposes a new paradigm, referred to as many-user information theory, where the number of users is allowed to grow with the blocklength. This paradigm is motivated by emerging systems with a massive number of users in an area, such as the Internet of Things. The focus of this paper is the many-access channel model, which consists of a single receiver and many transmitters, whose number increases unboundedly with the blocklength. Moreover, an unknown subset of transmitters may transmit in a given block and need to be identified as well as decoded by the receiver. A new notion of capacity is introduced and characterized for the Gaussian many-access channel with random user activities. The capacity can be achieved by first detecting the set of active users and then decoding their messages. The minimum cost of identifying the active users is also quantified. [ABSTRACT FROM AUTHOR]

An open problem in polarization theory is to determine the binary operations that always lead to polarization (in the general multilevel sense) when they are used in Arıkan style constructions. This paper, which is presented in two parts, solves this problem by providing a necessary and sufficient condition for a binary operation to be polarizing. This (first) part of this paper introduces the mathematical framework that we will use in the second part to characterize the polarizing operations. We define uniformity preserving, irreducible, ergodic, and strongly ergodic operations, and we study their properties. The concepts of a stable partition and the residue of a stable partition are introduced. We show that an ergodic operation is strongly ergodic if and only if all its stable partitions are their own residues. We also study the products of binary operations and the structure of their stable partitions. We show that the product of a sequence of binary operations is strongly ergodic if and only if all the operations in the sequence are strongly ergodic. In the second part of this paper, we provide a foundation of polarization theory based on the ergodic theory of binary operations that we develop in this part. [ABSTRACT FROM PUBLISHER]

New capacity upper bounds are presented for the discrete-time Poisson channel with no dark current and an average-power constraint. These bounds are a consequence of techniques developed for the seemingly unrelated problem of upper bounding the capacity of binary deletion and repetition channels. Previously, the best known capacity upper bound in the regime where the average-power constraint does not approach zero was due to Martinez (JOSA B, 2007), which is re-derived as a special case of the framework developed in this paper. Furthermore, this framework is carefully instantiated in order to obtain a closed-form bound that improves the result of Martinez everywhere. Finally, capacity-achieving distributions for the discrete-time Poisson channel are studied under an average-power constraint and/or a peak-power constraint and arbitrary dark current. In particular, it is shown that the support of the capacity-achieving distribution under an average-power constraint must only be countably infinite. This settles a conjecture of Shamai (IEE Proceedings I, 1990) in the affirmative. Previously, it was only known that the support must be an unbounded set. [ABSTRACT FROM AUTHOR]

In this paper, we consider a binary erasure channel (BEC) with an unknown erasure probability of ${\delta }$ at a transmitter. In addition, we consider that ${\delta }$ has a constant value in each transmission block and the transmitter knows the probability distribution of ${\delta }$. For this problem with the infinite block length, based on the distribution of the random variable ${\delta }$ , a multi-layer encoding strategy at the transmitter and a successive decoding strategy at the receiver are proposed. In our proposed scheme, based on the value of ${\delta }$ , the receiver can decode a part of transmitted data from different transmission layers. In order to have a comparison with other erasure correction codes, we generalize the result of the infinite block length to the finite block-length transmission. We show that considering the average transmission rate, our scheme has a better performance than the other erasure correction codes such as the Raptor and the MDS codes. We also analyze both the decoding complexity and bit error rate versus the erasure probability of the channel. Besides, by using a numerical comparison, we try to show that our proposed strategy outperforms other transmission strategies. [ABSTRACT FROM AUTHOR]

The capacity under strong asynchronism was recently shown to be essentially unaffected by the imposed decoding delay—the elapsed time between when information is available at the transmitter and when it is decoded—and the output sampling rate. This paper shows that, in contrast with capacity, the second-order term in the maximum rate expansion is sensitive to both parameters. When the receiver must locate the sent codeword exactly and therefore achieve minimum delay equal to the blocklength $n$ , the second-order term in the maximum rate expansion is of order $\Theta (1/\rho)$ for any sampling rate $\rho =O(1/\sqrt {n})$ (and $\rho =\omega (1/n)$ for otherwise reliable communication is impossible). Instead, if $\rho =\omega (1/\sqrt {n})$ , then the second-order term is the same as under full sampling and is given by a standard $\Theta (\sqrt {n})$ term. However, if the delay constraint is only slightly relaxed to $n(1+o(1))$ , then the above order transition (for $\rho =O(1/\sqrt {n})$ and $\rho =\omega (1/\sqrt {n})$) vanishes and the second-order term remains the same as under full sampling for any $\rho =\omega (1/n)$. [ABSTRACT FROM AUTHOR]

Marton’s inner bound is the best known achievable rate region for a general two-receiver discrete memoryless broadcast channel. In this paper, we establish improved bounds on the cardinalities of the auxiliary random variables appearing in this inner bound to the true rate region. We combine a perturbation technique, along with a representation using concave envelopes of information-theoretic functions that involve the use of auxiliary random variables, to achieve this improvement. The new cardinality bounds lead to a proof that a randomized-time-division strategy achieves every rate triple in Marton’s region for binary input broadcast channels. This extends the result by Hajek and Pursley which showed that the Cover-van der Muelen region was exhausted by the randomized-time-division strategy. [ABSTRACT FROM AUTHOR]

This paper obtains the first degrees of freedom (DoFs) bound that is provably sensitive tonetworkcoherence time, i.e., coherence time in an interference network, where all channels experience the same coherence patterns. This is accomplished by a novel adaptation of the aligned image sets bound and settles various open problems noted previously by Naderi and Avestimehr and by Gouet al.For example, a necessary and sufficient condition is obtained for the optimality of 1/2 DoF per user in a partially connected interference network, where the channel state information at the receivers (CSIRs) is perfect, the channel state information at the transmitters (CSITs) is instantaneous but limited to finite precision, and the network coherence time is $T_{c}=1$. The surprising insight that emerges is that even with perfect CSIR and instantaneous finite precision CSIT, the network coherence time matters, i.e., it has a DoF impact. [ABSTRACT FROM AUTHOR]

The ordering of communication channels was first introduced by Shannon. In this paper, we aim to find characterizations of two orderings: input-degradedness and the Shannon ordering. A channel $W$ is said to be input-degraded from another channel $W'$ if $W$ can be simulated from $W'$ by randomization at the input. We provide a necessary and sufficient condition for a channel to be input-degraded from another one. We show that any decoder that is good for $W$ is also good for $W'$. We provide two characterizations for input-degradedness, one of which is similar to the Blackwell-Sherman-Stein theorem. We show that $W'$ contains $W$ (in the Shannon ordering sense) if and only if $W$ is the skew-composition of $W'$ with a convex-product $n$ channel. This fact is used to derive a characterization of the Shannon ordering that is similar to the Blackwell-Sherman-Stein theorem. [ABSTRACT FROM AUTHOR]

In multiuser information theory, it is often assumed that every node in the network possesses all codebooks used in the network. This assumption may be impractical in distributed ad hoc, cognitive, or heterogeneous networks. This paper considers the two-user interference channel with one oblivious receiver (IC-OR), i.e., one receiver lacks knowledge of the interfering cookbook, whereas the other receiver knows both codebooks. This paper asks whether, and if so how much, the channel capacity of the IC-OR is reduced compared with that of the classical IC where both receivers know all codebooks. A novel outer bound is derived and shown to be achievable to within a gap for the class of injective semideterministic IC-ORs; the gap is shown to be zero for injective fully deterministic IC-ORs. An exact capacity result is shown for the general memoryless IC-OR when the nonoblivious receiver experiences very strong interference. For the linear deterministic IC-OR that models the Gaussian noise channel at high SNR, nonindependent identically distributed. Bernoulli(1/2) input bits are shown to achieve points not achievable by i.i.d. Bernoulli(1/2) input bits used in the same achievability scheme. For the real-valued Gaussian IC-OR, the gap is shown to be at most 1/2 bit per channel use, even though the set of optimal input distributions for the derived outer bound could not be determined. Toward understanding the Gaussian IC-OR, an achievability strategy is evaluated in which the input alphabets at the nonoblivious transmitter are a mixture of discrete and Gaussian random variables, where the cardinality of the discrete part is appropriately chosen as a function of the channel parameters. Surprisingly, as the oblivious receiver intuitively should not be able to jointly decode the intended and interfering messages (whose codebook is unavailable), it is shown that with this choice of input, the capacity region of the symmetric Gaussian IC-OR is to within 1/2\log \left (12\pi \mathrm e \right )\approx 3.34 bits (per channel use per user) of an outer bound for the classical Gaussian IC with full codebook knowledge at both receivers. [ABSTRACT FROM PUBLISHER]

This paper presents polar coding schemes for the two-user discrete memoryless broadcast channel (DM-BC) which achieve Marton’s region with both common and private messages. This is the best achievable rate region known to date, and it is tight for all classes of two-user DM-BCs whose capacity regions are known. To accomplish this task, we first construct polar codes for both the superposition as well as binning strategy. By combining these two schemes, we obtain Marton’s region with private messages only. Finally, we show how to handle the case of common information. The proposed coding schemes possess the usual advantages of polar codes, i.e., they have low encoding and decoding complexity and a superpolynomial decay rate of the error probability. We follow the lead of Goela, Abbe, and Gastpar, who recently introduced polar codes emulating the superposition and binning schemes. To align the polar indices, for both schemes, their solution involves some degradedness constraints that are assumed to hold between the auxiliary random variables and channel outputs. To remove these constraints, we consider the transmission of $k$ blocks and employ a chaining construction that guarantees the proper alignment of the polarized indices. The techniques described in this paper are quite general, and they can be adopted to many other multiterminal scenarios whenever there polar indices need to be aligned. [ABSTRACT FROM AUTHOR]

In this paper, we consider different aspects of the problem of compressing for function computation across a network, which we call network functional compression. In network functional compression, computation of a function (or, some functions) of sources located at certain nodes in a network is desired at receiver(s). The rate region of this problem has been considered in the literature under certain restrictive assumptions, particularly in terms of the network topology, the functions, and the characteristics of the sources. In this paper, we present results that significantly relax these assumptions. For a one-stage tree network, we characterize a rate region by introducing a necessary and sufficient condition for any achievable coloring-based coding scheme called coloring connectivity condition. We also propose a modularized coding scheme based on graph colorings to perform arbitrarily closely to rate lower bounds. For a general tree network, we provide a rate lower bound based on graph entropies and show that, this bound is tight in the case of having independent sources. In particular, we show that, in a general tree network case with independent sources, to achieve the rate lower bound, intermediate nodes should perform computations. However, for a family of functions and random variables, which we call chain-rule proper sets, it is sufficient to have no computations at intermediate nodes to perform arbitrarily closely to the rate lower bound. In addition, we consider practical issues of coloring-based coding schemes and propose an efficient algorithm to compute a minimum entropy coloring of a characteristic graph under some conditions on source distributions and/or the desired function. Finally, extensions of these results for cases of having feedback and lossy function computations are discussed. [ABSTRACT FROM AUTHOR]

We consider a broadcast channel with three receivers and three-degraded message sets, i.e., the transmitter has a common message intended for all three receivers, a message intended for receivers 2 and 3, and a private message intended only for receiver 3. The messages are transmitted over a family of parallel degraded broadcast channels. In the most general case, the broadcast channel consists of the product of six parallel degraded broadcast channels, each with a different order of degradedness. We first consider an achievable rate region of Nair and El Gamal, by appropriately choosing independent input random variables and auxiliary random variables for each subchannel. We then show that the achievable rate region attains the capacity region for two different classes of such broadcast channels, one consisting of the product of five parallel degraded broadcast channels and another consisting of the product of three parallel degraded broadcast channels. To accomplish this, we make use of an information-theoretic inequality that may be proven using the Csiszár-sum identity. Next, we extend the result to the Gaussian case. We consider the aligned Gaussian MIMO broadcast channel consisting of the product of six parallel degraded Gaussian broadcast channels, where the Gaussian noise vectors for each of the users in each of the subchannels follow a degradedness order, i.e., the noise covariance matrices may be ordered in a positive semi-definite sense. We show that the Nair–El Gamal achievable rate region considered in this paper is maximized by Gaussian inputs. To prove that Gaussian inputs are optimal, we prove an extremal entropy inequality employing a new method recently introduced by Geng and Nair to prove the capacity region of the two-user Gaussian MIMO broadcast channel with common and private messages. [ABSTRACT FROM AUTHOR]

We study the channel capacity of a general discrete energy harvesting channel with a finite battery. Contrary to traditional communication systems, the transmitter of such a channel is powered by a device that harvests energy from a random exogenous energy source and has a finite-sized battery. As a consequence, at each transmission opportunity, the system can only transmit a symbol whose energy is no more than the energy currently available. This new type of power supply introduces an unprecedented input constraint for the channel, which is simultaneously random, instantaneous, and influenced by the full history of the inputs and the energy harvesting process. Furthermore, naturally, in such a channel, the energy information is observed causally at the transmitter. Both of these characteristics pose great challenges for the analysis of the channel capacity. In this paper, we use techniques developed for channels with side information and finite-state channels, to obtain lower and upper bounds on the capacity of energy harvesting channels. In particular, in a general case with Markov energy harvesting processes, we use stationarity and ergodicity theory to compute and optimize the achievable rates for the channels, and derive a series of computable capacity upper and lower bounds. [ABSTRACT FROM AUTHOR]

It was previously shown by Hashimoto that Forney’s optimal erasure decoder can be significantly simplified, in the sense that a simplified decoder achieves the same random coding bounds, for the ensemble of independent and identically distributed codewords. In this paper, the analysis of simplified decoders is refined and generalized in several aspects. First, tighter random coding bounds for simplified decoders are derived, which equal the exact exponential behavior of the fixed composition ensemble average. Second, the exponential bounds are valid both in the erasure mode and in the list mode. Third, the analysis pertains to a rather general class of simplified decoders, including the case of mismatch in the threshold function of the decoder. Fourth, expurgated exponents, which are larger than the random coding exponents at low rates, are shown to be achievable using a significantly simpler decoder than Forney’s optimal decoder. It is shown numerically that, from the aspect of exact random coding exponents, a decoder in the spirit of Hashimoto’s is as good as Forney’s in the erasure mode, as well as in the list mode. [ABSTRACT FROM PUBLISHER]

An open problem in polarization theory is to determine the binary operations that always lead to polarization (in the general multilevel sense) when they are used in Arıkan style constructions. This paper, which is presented in two parts, solves this problem by providing a necessary and sufficient condition for a binary operation to be polarizing. This (second) part provides a foundation of polarization theory based on the ergodic theory of binary operations which we developed in the first part. We show that a binary operation is polarizing if and only if it is uniformity preserving and its right-inverse is strongly ergodic. The rate of polarization of single user channels is studied. It is shown that the exponent of any polarizing operation cannot exceed \frac 12 , which is the exponent of quasi-group operations. We also study the polarization of multiple access channels (MAC). In particular, we show that a sequence of binary operations is MAC-polarizing if and only if each binary operation in the sequence is polarizing. It is shown that the exponent of any MAC-polarizing sequence cannot exceed \frac 12 , which is the exponent of sequences of quasi-group operations. [ABSTRACT FROM AUTHOR]

Treating interference as noise (TIN) as the most appropriate approach in dealing with interference and the conditions on its optimality has attracted the interest of researchers recently. However, our knowledge on necessary and sufficient conditions of TIN is restricted to a few setups with limited number of users. In this paper, we study the optimality of TIN in terms of the generalized degrees of freedom (GDoF) for a fundamental network, namely, the $M\times 2$ X-channel. To this end, the achievable GDoF of TIN with power allocations at the transmitters is studied. It turns out that the transmit power allocation maximizing the achievable GDOF is given by on–off signaling as long as the receivers use TIN. This leads to two variants of TIN, namely, P2P-TIN and 2-IC-TIN. While in the first variant the $M\times 2$ X-channel is reduced to a point-to-point (P2P) channel, in the second variant, the setup is reduced to a two-user interference channel in which the receivers use TIN. The optimality of these two variants is studied separately. To this end, novel genie-aided upper bounds on the capacity of the X-channel are established. The conditions on the optimality of P2P-TIN can be summarized as follows. P2P-TIN is GDoF-optimal if there exists a dominant multiple access channel or a dominant broadcast channel embedded in the X channel. Furthermore, the necessary and sufficient conditions on the GDoF-optimality of 2-IC-TIN are presented. Interestingly, it turns out that operating the $M\times 2$ X-channel in the 2-IC-TIN mode might be still GDOF optimal, although the conditions given by Geng et al. are violated. However, 2-IC-TIN is sub-optimal if there exists a single interferer which causes sufficiently strong interference at both receivers. The comparison of the results with the state of the art shows that the GDOF optimality of TIN is expanded significantldy. [ABSTRACT FROM PUBLISHER]

The best known inner bound for the two-user discrete memoryless interference channel is the Han–Kobayashi rate region. The coding schemes that achieve this region are based on rate-splitting and superposition coding. In this paper, we develop a multicoding scheme to achieve the same rate region. A key advantage of the multicoding nature of the proposed coding scheme is that it can be naturally extended to more general settings, such as when encoders have state information or can overhear each other. In particular, we extend our coding scheme to characterize the capacity region of the state-dependent deterministic Z-interference channel when noncausal state information is available at the interfering transmitter. We specialize our results to the case of the linear deterministic model with ON/OFF interference, which models a wireless system where a cognitive transmitter is noncausally aware of the times it interferes with a primary transmission. For this special case, we provide an explicit expression for the capacity region and discuss some interesting properties of the optimal strategy. We also extend our multicoding scheme to find the capacity region of the deterministic Z-interference channel when the signal of the interfering transmitter can be overheard at the other transmitter (also known as unidirectional partial cribbing). [ABSTRACT FROM PUBLISHER]

In this paper, we investigate problems of communication over physically degraded, state-dependent broadcast channels (BCs) with cooperating decoders. Two different setups are considered, and their capacity regions are characterized. First, we study a setting in which one decoder can use a finite capacity link to send the other decoder information regarding the messages or the channel states. In this scenario, we analyze two cases: one, where noncausal state information, is available to the encoder and the strong decoder, and the other, where state information, is available only to the encoder in a causal manner. Second, we examine a setting in which the cooperation between the decoders is limited to taking place before the outputs of the channel are given. In this case, one decoder, which is informed of the state sequence noncausally, can cooperate only to send the other decoder rate-limited information about the state sequence. The proofs of the capacity regions introduce a new idea of coding for channels with cooperation between different users, where we exploit the link between the decoders for multiple binnings. Finally, we discuss the optimality of using rate-splitting techniques when coding for cooperative BCs. In particular, we show that rate splitting is not necessarily optimal when coding for cooperative BCs by solving an example in which our method of coding outperforms rate splitting. [ABSTRACT FROM AUTHOR]

We propose two coding schemes for the two-receiver discrete memoryless broadcast channel (BC) with rate-limited feedback from one or both receivers. They improve over the no feedback capacity region for a large class of channels, including the class of strictly essentially less-noisy BCs that we introduce in this paper. Examples of strictly essentially less-noisy BCs are the binary symmetric BC or the binary erasure BC with unequal crossover or erasure probabilities at the two receivers. When the feedback rates are sufficiently large, our schemes recover all previously known capacity results for discrete memoryless BCs with feedback. In both our schemes, we let the receivers feedback quantization messages about their receive signals. In the first scheme, the transmitter simply relays the quantization information obtained from Receiver 1 to Receiver 2, and vice versa. This provides each receiver with a second observation of the input signal and can thus improve its decoding performance unless the BC is physically degraded. Moreover, each receiver uses its knowledge of the quantization message describing its own outputs so as to attain the same performance as if this message had not been transmitted at all. In our second scheme, the transmitter first reconstructs and processes the quantized output signals, and then sends the outcome as a common update information to both receivers. A special case of our second scheme also applies to memoryless BCs without feedback but with strictly causal state-information at the transmitter and causal state-information at the receivers. It recovers all previous achievable regions also for this setup with state-information. [ABSTRACT FROM AUTHOR]

This paper shows that the capacity region of the continuous-time Poisson broadcast channel is achieved via superposition coding for most channel parameter values. Interestingly, the channel in some subset of these parameter values does not belong to any of the existing classes of broadcast channels for which superposition coding is optimal (e.g., degraded, less noisy, and more capable). In particular, we introduce the notion of effectively less noisy broadcast channel and show that it implies less noisy but is not in general implied by more capable. For the rest of the channel parameter values, we show that there is a gap between Marton’s inner bound and the UV outer bound. [ABSTRACT FROM AUTHOR]

We consider the transmission of a memoryless bivariate Gaussian source over a two-user additive Gaussian multiple-access channel with unidirectional conferencing encoders. Here, prior to each transmission block, Encoder 1, which observes the first source component, is allowed to communicate with Encoder 2, which observes the second source component, via a unidirectional noise-free bit-pipe of given capacity. The main results of this paper are sufficient conditions and a necessary condition for the achievability of a distortion pair expressed as a function of the channel \sf SNR and of the source correlation. The main sufficient condition is obtained by an extension of the vector-quantizer scheme suggested by Lapidoth–Tinguely, for the case without conferencing, to the case with unidirectional conference. In the high- \sf SNR regime, and when the capacity of the conference channel is unlimited, these necessary and sufficient conditions are shown to agree. We evaluate the precise high- \sf SNR asymptotics for a subset of distortion pairs when the capacity of the conference channel is unlimited in which case we show that a separation-based scheme attains these optimal distortion pairs. However, with symmetric average-power constraints and fixed conferencing capacity, at high- \sf SNR , the latter separation-based scheme is shown to be suboptimal. [ABSTRACT FROM AUTHOR]

Wyner’s common information was originally defined for a pair of dependent discrete random variables. Its significance is largely reflected in, and also confined to, several existing interpretations in various source coding problems. This paper attempts to expand its practical significance by providing a new operational interpretation. In the context of the Gray–Wyner network, it is established that Wyner’s common information has a new lossy source coding interpretation. Specifically, it is established that, under suitable conditions, Wyner’s common information equals to the smallest common message rate when the total rate is arbitrarily close to the rate distortion function with joint decoding for the Gray–Wyner network. A surprising observation is that such equality holds independent of the values of distortion constraints as long as the distortions are within some distortion region. The new lossy source coding interpretation provides the first meaningful justification for defining Wyner’s common information for continuous random variables and the result can also be extended to that of multiple variables. Examples are given for characterizing the rate distortion region for the Gray–Wyner lossy source coding problem and for identifying conditions under which Wyner’s common information equals that of the smallest common rate. As a by-product, the explicit expression for the common information between a pair of Gaussian random variables is obtained. [ABSTRACT FROM AUTHOR]

This paper investigates the maximal channel coding rate achievable at a given blocklength $ n$ and error probability \epsilon $ , when the codewords are subjected to a long-term (i.e., averaged-over-all-codeword) power constraint. The second-order term in the large-n expansion of the maximal channel coding rate is characterized both for additive white Gaussian noise (AWGN) channels and for quasi-static fading channels with perfect channel state information available at both the transmitter and the receiver. It is shown that in both the cases, the second-order term is proportional to ({n ^{-1}\ln n })^{1/2} . For the quasi-static fading case, this second-order term is achieved by truncated channel inversion, namely, by concatenating a dispersion-optimal code for an AWGN channel subject to a short-term power constraint, with a power controller that inverts the channel whenever the fading gain is above a certain threshold. Easy-to-evaluate approximations of the maximal channel coding rate are developed for both the AWGN and the quasi-static fading case. [ABSTRACT FROM AUTHOR]

This paper studies a decentralized wireless network of asynchronous transmitter–receiver pairs with burst transmissions. Each receiver learns about the number of active users, channel coefficients, and mutual delays based on locally available measurements. The estimates for the mutual delays are not perfect, however, they are reliable enough to guarantee successful decoding. Two signalling schemes are addressed, namely, randomized masking (RM) and reduced cycle transmission (RCT). Under RM, the $n$ symbols of a codeword are generated according to a Bernoulli–Gaussian distribution with activity factor $0<\theta \leq 1$ . This is in contrast to RCT where each codeword consists of $\lfloor \theta n\rfloor $ Gaussian symbols followed by $n-\lfloor \theta n\rfloor $ zeros. Assuming the transmitters are unaware of the number of users, channel coefficients, and mutual delays, the probability of outage under RM is considerably lower compared with RCT if the signal-to-noise ratio (SNR) is sufficiently large. A generalized RCT scheme is also examined where the $n-\lfloor \theta n\rfloor $ zero symbols are not necessarily located at the end of a codeword. In the asymptote of large SNR, the outage probability becomes vanishingly small under RM, however, it is bounded away from zero for generalized RCT regardless of the value of SNR. [ABSTRACT FROM PUBLISHER]

This paper shows that the Maddah-Ali–Tse (MAT) scheme, which achieves the symmetric capacity of two example broadcast channels with strictly causal state information at the transmitter, is a simple special case of the Shayevitz–Wigger (SW) scheme for the broadcast channel with generalized feedback, which involves block Markov coding, Gray–Wyner compression, superposition coding, and Marton coding. Focusing on the class of symmetric broadcast channels with state, we derive an expression for the maximum achievable symmetric rate using the SW scheme. We show that the MAT results for the two-receiver case can be recovered by evaluating this expression for the special case in which superposition coding and Marton coding are not used. We then introduce a new broadcast channel example that shares many features of the MAT examples. We show that another special case of our maximum symmetric rate expression in which superposition coding is also used attains a higher symmetric rate than the MAT scheme. The symmetric capacity of this new example is not known, however. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the fluctuation of mutual information statistics of a multiple input multiple output channel communication systems without assuming that the entries of the channel matrix have zero pseudovariance. To this end, we also establish a central limit theorem of the linear spectral statistics for sample covariance matrices under general moment conditions by removing the restrictions imposed on the second moment and fourth moment on the matrix entries in Bai and Silverstein (2004). [ABSTRACT FROM AUTHOR]

In coding schemes for the wire-tap channel or for broadcast channels with confidential messages, it is well-known that the sender needs to use stochastic encoding to avoid information about the transmitted confidential message from being leaked to an eavesdropper. In this paper, we investigate the tradeoff between the rate of random numbers needed to realize the stochastic encoding and the rates of common, private, and confidential messages. For the direct theorem, we use the superposition coding scheme for the wire-tap channel, recently proposed by Chia and El Gamal, and its strong security is proved. The matching converse theorem is also established. Our result clarifies that a combination of ordinary stochastic encoding and channel prefixing by channel simulation is suboptimal. [ABSTRACT FROM AUTHOR]

We consider a cooperative two-user multiaccess channel in which the transmission is controlled by a random state. Both encoders transmit a common message and, one of the encoders also transmits an individual message. We study the capacity region of this communication model for different degrees of availability of the states at the encoders, causally or strictly causally. In the case in which the states are revealed causally to both encoders but not to the decoder we find an explicit characterization of the capacity region in the discrete memoryless case. In the case in which the states are revealed only strictly causally to both encoders, we establish inner and outer bounds on the capacity region. The outer bound is nontrivial, and has a relatively simple form. It has the advantage of incorporating only one auxiliary random variable. In particular, it suggests that there is none, or at best only little, to gain from having the encoder that transmits both messages also sending an individual description of the state to the receiver, in addition to the compressed version that is sent cooperatively with the other encoder. We then introduce a class of cooperative multiaccess channels with states known strictly causally at both encoders for which the inner and outer bounds agree, and so we characterize the capacity region for this class. In this class of channels, the state can be obtained as a deterministic function of the channel inputs and output. We also study the model in which the states are revealed, strictly causally, in an asymmetric manner, to only one encoder. Throughout this paper, we discuss a number of examples, and compute the capacity region of some of these examples. The results shed more light on the utility of delayed channel state information for increasing the capacity region of state-dependent cooperative multiaccess channels, and tie with recent progress in this framework. [ABSTRACT FROM AUTHOR]

We show how to efficiently simulate the sending of a single message \(M\) to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver. This is a generalization and strengthening of the Slepian–Wolf theorem, which shows how to carry out such a simulation with low amortized communication in the case that \(M\) is a deterministic function of \(X\) . A caveat is that our simulation is interactive. As a consequence, we prove that the internal information cost (namely the information revealed to the parties) involved in computing any relation or function using a two party interactive protocol is exactly equal to the amortized communication complexity of computing independent copies of the same relation or function. We also show that the only way to prove a strong direct sum theorem for randomized communication complexity is by solving a particular variant of the pointer jumping problem that we define. This paper implies that a strong direct sum theorem for communication complexity holds if and only if efficient compression of communication protocols is possible. In particular, together with our result, a recent result of Ganor, Kol, and Raz implies that the strongest version of direct sum for randomized communication complexity is false. [ABSTRACT FROM AUTHOR]

In this paper, we revisit the structure of infeasibility results in network information theory, based on a notion of information state. We also discuss ideas for generalizing a known outer bound for lossless transmission of independent sources over a network to one of lossy transmission of dependent sources over the same network. To concretely demonstrate this, we apply our ideas and prove new results for lossy transmission of dependent sources by generalizing: 1) the cut-set bound; 2) the best known outer bound on the capacity region of a general broadcast channel; and 3) the outer bound part of the result of Maric, Yates, and Kramer on strong interference channels with a common message. [ABSTRACT FROM AUTHOR]

We study a two-transmitter two-receiver network where Receiver 1 can only hear the transmitted signal of Transmitter 1. Transmitter 1 has two messages, one of which is intended for Receiver 1 while both are intended for Receiver 2. Transmitter 2 has one message which is intended for Receiver 2. We call this channel model the Z channel with degraded message sets. For networks with the element of distributed encoding, it has been shown that when the multiple access link between the two encoders and the decoder satisfies the conditions proposed by Liu and Goldsmith, capacity results can be obtained for a variety of problems. In this paper, we generalize these conditions and show that for a larger class of multiple access links, the capacity region of the Z channel with degraded message sets can be characterized despite the presence of distributed encoding. [ABSTRACT FROM AUTHOR]

This paper addresses a two-user Gaussian multiple access channel (MAC) under peak power constraints at the transmitters. It is shown that generating the code-books of both users according to discrete distributions with a finite number of mass points achieves the largest weighted sum-rate in the network. This verifies that any point on the boundary of the capacity region of a two-user MAC under peak power constraints at both transmitters is achieved by discrete distributions with a finite number of mass points. Although the capacity-achieving distributions are not necessarily unique, it is verified that only discrete distributions with a finite number of mass points can achieve a point on the boundary of the capacity region. It is shown that there exist an infinite number of sum-rate-optimal points on the boundary of the capacity region. In contrast to the Gaussian MAC with average power constraints, we verify that time division (TD) cannot achieve any of the sum-rate-optimal points in the Gaussian MAC with peak power constraints. Using the so-called I-MMSE identity of Guo et al., the largest achievable sum-rate by orthogonal code division (OCD) is characterized where it is shown that Walsh–Hadamard spreading codes of length 2 are optimal. In the symmetric case where the peak power constraints at both transmitters are identical, we verify that OCD can achieve a sum-rate that is strictly larger than the highest sum-rate achieved by TD. Finally, it is demonstrated that there are values for the maximum peak power at the transmitters such that OCD can not achieve any of the sum-rate-optimal points on the boundary of the capacity region. [ABSTRACT FROM AUTHOR]

A computable expression for Heegard and Berger’s rate-distortion function has eluded information theory for nearly three decades. Heegard and Berger’s single-letter achievability bound is well known to be optimal for physically degraded side information; however, it is not known whether the bound is optimal for arbitrarily correlated side information (general discrete memoryless sources). In this paper, we consider a new setup where the side information at one receiver is conditionally less noisy than that at the other. The new setup includes degraded side information as a special case, and it is motivated by the literature on degraded and less noisy broadcast channels. Our key contribution is a converse proving the optimality of Heegard and Berger’s achievability bound in a new setting, where the side information is conditionally less noisy and one distortion function is deterministic. The less noisy setup is also generalized to two different successive-refinement problems. [ABSTRACT FROM AUTHOR]

In this paper, the discrete memoryless arbitrarily varying broadcast channel (AVBC) with receiver side information is studied and its random code and deterministic code capacity regions are derived for the average error criterion. In addition, it is analyzed for deterministic list codes and it is shown that the corresponding list capacity region displays a behavior, which is similar to Ahlswede’s famous dichotomy result for the single-user arbitrarily varying channel: it either equals the random code capacity region or otherwise has an empty interior. This is characterized in terms of list sizes at the receivers and an appropriate concept of symmetrizability for the AVBC with receiver side information. The scenario studied here is motivated by the broadcast phase of bidirectional relaying, where a half-duplex relay node establishes a bidirectional communication between two other nodes using a decode-and-forward protocol. The relay decodes the messages both nodes have sent in the initial multiple access phase and broadcasts a re-encoded composition of them in the succeeding broadcast phase. Then, the broadcast phase corresponds to the AVBC with receiver side information, which differs from the classical broadcast channel, since both receivers can exploit their own messages from the previous phase as side information for decoding. [ABSTRACT FROM PUBLISHER]

A class of cognitive interference channels with state are investigated, in which a primary transmitter sends a message to two receivers (receivers 1 and 2) with assistance of a cognitive transmitter (that knows the primary transmitter’s message), and the cognitive transmitter also sends a separate message to receiver 2. The channel is corrupted by an independent and identically distributed state sequence. The scenario, in which the state sequence is noncausally known at both the cognitive transmitter and receiver 2, is first studied. The capacity region is obtained for both the discrete memoryless and Gaussian channels. The second scenario, in which the state sequence is noncausally known only at the cognitive transmitter, is further studied. Inner and outer bounds on the capacity region are obtained for the discrete memoryless channel and its degraded version. The capacity region is characterized for the degraded semideterministic channel and for channels that satisfy a less noisy condition. The Gaussian channels are further studied, which are partitioned into two cases based on how the interference compares with the signal at receiver 1. For each case, inner and outer bounds on the capacity region are derived, and partial boundaries of the capacity region are characterized. The full capacity region is also characterized for channels that satisfy certain conditions. It is shown that certain Gaussian channels achieve the capacity of the same channels with state noncausally known at both the cognitive transmitter and receiver 2. [ABSTRACT FROM PUBLISHER]