Search

This paper develops a methodology for finding minimum energy per bit in networks with correlated information, without at need for finding bounds on capacity. This is used to derive the exact minimum energy per bit for some broadcast and interference channels with common and correlated messages, and bounds on the minimum energy per bit for some other channels. [ABSTRACT FROM PUBLISHER]

Index coding studies multiterminal source-coding problems where a set of receivers are required to decode multiple (possibly different) messages from a common broadcast, and they each know some messages a priori. In this paper, at the receiver end, we consider a special setting where each receiver knows only one message a priori, and each message is known to only one receiver. At the broadcasting end, we consider a generalized setting where there could be multiple senders, and each sender knows a subset of the messages. The senders collaborate to transmit an index code. This paper looks at minimizing the number of total coded bits the senders are required to transmit. When there is only one sender, we propose a pruning algorithm to find a lower bound on the optimal (i.e., the shortest) index codelength, and show that it is achievable by linear index codes. When there are two or more senders, we propose an appending technique to be used in conjunction with the pruning technique to give a lower bound on the optimal index codelength; we also derive an upper bound based on cyclic codes. While the two bounds do not match in general, for the special case where no two distinct senders know any message in common, the bounds match, giving the optimal index codelength. The results are expressed in terms of strongly connected components in directed graphs that represent the index-coding problems. [ABSTRACT FROM AUTHOR]

In this paper, we study linear encoding for a pair of correlated Gaussian sources transmitted over a two-user Gaussian broadcast channel in the presence of unit-delay noiseless feedback, abbreviated as the GBCF. Each pair of source samples is transmitted using a linear transmission scheme in a finite number of channel uses. We investigate three linear transmission schemes: A scheme based on the Ozarow–Leung (OL) code, a scheme based on the linear quadratic Gaussian (LQG) code of Ardestanizadeh et al., and a novel scheme derived in this paper using a dynamic programming (DP) approach. For the OL and LQG schemes we present lower and upper bounds on the minimal number of channel uses needed to achieve a target mean-square error (MSE) pair. For the LQG scheme in the symmetric setting, we identify the optimal scaling of the sources, which results in a significant improvement of its finite horizon performance, and, in addition, characterize the (exact) minimal number of channel uses required to achieve a target MSE. Finally, for the symmetric setting, we show that for any fixed and finite number of channel uses, the DP scheme achieves an MSE lower than the MSE achieved by either the LQG or the OL schemes. [ABSTRACT FROM AUTHOR]

This paper studies incremental relay strategies for a two-user Gaussian relay-interference channel with an in-band-reception and out-of-band-transmission relay, where the link between the relay and the two receivers is modelled as a degraded broadcast channel. It is shown that generalized hash-and-forward (GHF) can achieve the capacity region of this channel to within a constant number of bits in a certain weak-relay regime, where the transmitter-to-relay link gains are not unboundedly stronger than the interference links between the transmitters and the receivers. The GHF relaying strategy is ideally suited for the broadcasting relay because it can be implemented in an incremental fashion, i.e., the relay message to one receiver is a degraded version of the message to the other receiver. A generalized-degree-of-freedom (GDoF) analysis in the high signal-to-noise ratio (SNR) regime reveals that in the symmetric channel setting, each common relay bit can improve the sum rate roughly by either one bit or two bits asymptotically depending on the operating regime, and the rate gain can be interpreted as coming solely from the improvement of the common messages rate, or alternatively in the very weak interference regime as solely coming from the rate improvement of the private messages. Further, this paper studies an asymmetric case in which the relay has only a single link to one of the destinations. It is shown that with only one relay-destination link, the approximate capacity region can be established for a larger regime of channel parameters. Further, from a GDoF point of view, the sum-capacity gain due to the relay can now be thought as coming from either signal relaying only or interference forwarding only. [ABSTRACT FROM PUBLISHER]

A (layered) broadcast approach is studied for the fading wiretap channel without the channel state information (CSI) at the transmitter. Two broadcast schemes, based on superposition coding and embedded coding, respectively, are developed to encode information into a number of layers and use stochastic encoding to keep the corresponding information secret from an eavesdropper. The layers that can be successfully and securely transmitted are determined by the channel states to the legitimate receiver and the eavesdropper. The advantage of these broadcast approaches is that the transmitter does not need to know the CSI to the legitimate receiver and the eavesdropper, but the scheme still adapts to the channel states of the legitimate receiver and the eavesdropper. Three scenarios of block fading wiretap channels with stringent delay constraints are studied, in which either the legitimate receiver's channel, the eavesdropper's channel, or both channels are fading. For each scenario, the secrecy rate that can be achieved via the broadcast approach developed in this paper is derived, and the optimal power allocation over the layers (or the conditions on the optimal power allocation) is also characterized. A notion of probabilistic secrecy, which characterizes the probability that a certain secrecy rate of decoded messages is achieved during one block, is also introduced and studied for scenarios when the eavesdropper's channel is fading. Numerical examples are provided to demonstrate the impact of the CSI at the transmitter and the channel fluctuations of the eavesdropper on the average secrecy rate. These examples also demonstrate the advantage of the proposed broadcast approach over the compound channel approach. [ABSTRACT FROM AUTHOR]

This paper considers a Gaussian broadcast channel with two unmatched degraded components, three individual messages, and a common message that is intended for all three receivers. It is shown that for this channel, superposition coding with Gaussian signalling is sufficient to achieve every point in the capacity region. [ABSTRACT FROM AUTHOR]

We consider a graphical approach to index coding. As cycles have been shown to provide coding gain, cycles and cliques (a specific type of overlapping cycles) have been exploited in an existing literature. In this paper, we define a more general form of overlapping cycles, called the interlinked-cycle ( \mathsf IC ) structure, that generalizes cycles and cliques. We propose a scheme, called the interlinked-cycle-cover ( \mathsf ICC ) scheme, that leverages \mathsf IC structures in digraphs to construct scalar linear index codes. We characterize a class of infinitely many digraphs where our proposed scheme is optimal over all linear and non-linear index codes. Consequently, for this class of digraphs, we indirectly prove that scalar linear index codes are optimal. Furthermore, we show that the \mathsf ICC scheme can outperform all the existing graph-based schemes (including partial-clique-cover and fractional-local-chromatic number schemes), and a random-coding scheme (namely, composite coding) for certain graphs. [ABSTRACT FROM AUTHOR]

The problem of transmitting a pair of correlated Gaussian sources over degraded broadcast channels using optimal separate source and channel codes is studied. Upper bounds are derived for the rate penalty (in terms of channel uses per source symbol) and the power loss endured by separate coding compared to joint coding. Although source–channel separation is suboptimal in general, it is demonstrated that the performance of separate coding comes close to that of optimal joint coding, especially for low distortion pairs. In fact, in some cases, separate coding performs better than the best known joint schemes so far. It is also shown analytically that separate coding is optimal when either of the sources is to be reconstructed in a near-lossless fashion. [ABSTRACT FROM PUBLISHER]

We consider the time correlated multiple-input single-output (MISO) broadcast channel where the transmitter has imperfect knowledge of the current channel state, in addition to delayed channel state information. By representing the quality of the current channel state information as P^-\alpha for the signal-to-noise ratio P and some constant \alpha \geq 0, we characterize the optimal degrees of freedom region for this more general two-user MISO broadcast correlated channel. The essential ingredients of the proposed scheme lie in the quantization and multicast of the overheard interferences, while broadcasting new private messages. Our proposed scheme smoothly bridges between the scheme recently proposed by Maddah-Ali and Tse with no current state information and a simple zero-forcing beamforming with perfect current state information. [ABSTRACT FROM AUTHOR]

For a multicast network, in which a common source is transmitted to N users, the problem of maximizing the average rate subject to a coverage constraint (minimum quality of service) is studied. Considering such a network with single-antenna nodes and assuming that the channel state information is available only at the receiver side, the highest expected rate achievable by a random user in the network, called the expected typical rate, is derived in two scenarios: hard coverage constraint and soft coverage constraint. In the first case, the coverage is expressed in terms of the outage probability, while in the second case, the expected rate should satisfy a certain minimum requirement. It is shown that the optimum solution (achieving the highest expected typical rate for given coverage requirements) in both cases is achieved by an infinite layer superposition code for which the optimal power allocation among different layers is derived. The analysis is extended to a scenario with multiple transmit antennas. For the MISO case, a suboptimal coding scheme is proposed, which is shown to be asymptotically optimal, when the number of transmit antennas grows at least logarithmically with the number of users in the network. [ABSTRACT FROM PUBLISHER]

We provide a complete characterization of the achievable distortion region for the problem of sending a bivariate Gaussian source over bandwidth-matched Gaussian broadcast channels, where each receiver is interested in only one component of the source. This setting naturally generalizes the simple single Gaussian source bandwidth-matched broadcast problem for which the uncoded scheme is known to be optimal. We show that a hybrid scheme can achieve the optimum for the bivariate case, but neither an uncoded scheme alone nor a separation-based scheme alone is sufficient. We further show that in this joint source channel coding setting, the Gaussian scenario is the worst scenario among the sources and channel noises with the same covariances. [ABSTRACT FROM AUTHOR]

We determine the capacity region of a 3-receiver less noisy broadcast channel. The difficulty in extending the two-receiver result to three-receivers involves extending the Csiszar-sum lemma to three or more sequences, a standard difficulty in this area. In this work we bypass the difficulty by using a new information inequality, for less noisy receivers, that is employed in the converse. We also generalize our result to obtain the capacity region for a class of less noisy receivers. [ABSTRACT FROM AUTHOR]

A recent inner bound on the capacity region of the two-receiver discrete memoryless broadcast channel is shown to be equivalent to the Marton-Gelfand-Pinsker region. The proof method is based on a result of Gelfand and Pinsker concerning channel input distributions. [ABSTRACT FROM AUTHOR]

We characterize the capacity region of the two-user broadcast packet erasure channel (PEC) with single-user delayed channel state information (CSI). More precisely, we assume one receiver does not provide its channel state to the other two nodes (the other receiver and the transmitter), while the other receiver reveals its state globally with unit delay. This is a hybrid CSI at the transmitter (CSIT) setting where the transmitter has the delayed CSI of one user but not the other. Previous results developed opportunistic network coding schemes for this setting, which strictly enlarge the achievable rate region compared to the no-CSIT baseline. Characterization of the capacity region with single-user delayed CSI, however, remained open. In this work, we develop an improved achievability strategy and show that the capacity region, surprisingly, matches that of the broadcast PEC with global delayed CSI of both users. The key to such improvement over previous results is a new precoding strategy for the retransmission phase of the opportunistic network coding scheme. It harnesses the single-user delayed CSI in the retransmission phase, so that interference from the feedback receiver can be aligned at the other receiver. Besides the broadcast PEC with two private messages, an extension to a model with an additional common message is also provided and the corresponding capacity region with single-user CSI also matches that with global delayed CSI. Finally, further extensions to three-user cases are also provided. [ABSTRACT FROM AUTHOR]

Motivated by error correction coding in multimedia applications, we study the problem of broadcasting a single common source to multiple receivers over heterogeneous erasure channels. Each receiver is required to partially reconstruct the source sequence by decoding a certain fraction of the source symbols. We propose a coding scheme that requires only off-the-shelf erasure codes and can be easily adapted as users join and leave the network. Our scheme involves splitting the source sequence into multiple segments and applying a systematic erasure code to each such segment. We formulate the problem of minimizing the transmission latency at the server as a linear programming problem and explicitly characterize an optimal choice for the code rates and segment sizes. Through numerical comparisons, we demonstrate that our proposed scheme outperforms both separation-based coding schemes and degree-optimized rateless codes and performs close to a natural outer (lower) bound in certain cases. We further study individual user decoding delays for various orderings of segments in our scheme. We provide closed-form expressions for each individual user’s excess latency when parity checks are successively transmitted in both increasing order and decreasing order of their segment’s coded rate and also qualitatively discuss the merits of each order. [ABSTRACT FROM AUTHOR]

Index coding has received considerable attention recently motivated in part by applications such as fast video-on-demand and efficient communication in wireless networks and in part by its connection to network coding. Optimal encoding schemes and efficient heuristics were studied in various settings, while also leading to new results for network coding such as improved gaps between linear and non-linear capacity as well as hardness of approximation. The problem of broadcasting with side information, a generalization of the index coding problem, begins with a sender and sets of users and messages. Each user possesses a subset of the messages and desires an additional message from the set. The sender wishes to broadcast a message so that on receipt of the broadcast each user can compute her desired message. The fundamental parameter of interest is the broadcast rate, \beta , the average communication cost for sufficiently long broadcasts. Though there have been many new nontrivial bounds on \beta by Bar-Yossef (2006), Lubetzky and Stav (2007), Alon (2008), and Blasiak (2011) there was no known polynomial-time algorithm for approximating \beta within a nontrivial factor, and the exact value of \beta remained unknown for all nontrivial instances. Using the information theoretic linear program introduced in Blasiak (2011), we give a polynomial-time algorithm for recognizing instances with \beta = 2 and pinpoint \beta precisely for various classes of graphs (e.g., various Cayley graphs of cyclic groups). Further, extending ideas from Ramsey theory, we give a polynomial-time algorithm with a nontrivial approximation ratio for computing \beta . Finally, we provide insight into the quality of previous bounds by giving constructions showing separations between \beta and the respective bounds. In particular, we construct graphs where \beta is uniformly bounded while its upper bound derived from the naïve encoding scheme is polynomially worse. [ABSTRACT FROM AUTHOR]

A pair of strings (\bf X,\bf Y) put out by a memoryless source needs to be reliably communicated over a memoryless broadcast channel. Receiver 1 has \bf Y as side information and must reconstruct \bf X to within some distortion. Receiver 2 has \bf X and must reconstruct \bf Y to within some distortion. The problem is motivated by the broadcast phase (downlink) of the two-way relay channel. We characterize reliable communication for Gaussian sources with quadratic distortion functions; conditionally independent sources; deterministic distortion functions; and small distortions with Hamming distortion functions. The last result is obtained by solving a new version of the broadcast problem with Steinberg's common-reconstruction decoding constraint. [ABSTRACT FROM AUTHOR]

In this work, coding for a discrete memoryless broadcast channel with random states and two receivers is studied. Each receiver knows one of the two information messages at the sender and wants to know the other one. Assuming the channel state sequence is noncausally known at the sender, an achievable rate region based on the Gel'fand–Pinsker coding strategy is derived and an outer bound to the capacity region is presented. Further, the capacity region for the special case where in addition one receiver knows the channel state is established. An equivalent characterization of an achievable rate region characterizing convex set is derived using Shannon's concept of transmit strategies. This characterization is used to derive an Arimoto–Blahut-like algorithm including a stopping criterion to compute the weighted rate-sum maxima, which can be used to characterize the whole achievable rate region. The tradeoff between the input distribution and the impact of the channel state, the necessity of the time-sharing operation, and the additive Gaussian channel case assuming Costa's choice of auxiliary random variables are discussed by examples. [ABSTRACT FROM AUTHOR]

We study a wireless broadcast network, where a single source reliably communicates independent messages to multiple destinations, with the potential aid of relays and cooperation between destinations. The wireless nature of the medium is captured by the broadcast nature of transmissions as well as the superposition of transmitted signals plus independent Gaussian noise at the received signal at any radio. We propose a scheme that can achieve rate tuples within a constant gap away from the cut-set bound, where the constant is independent of channel coefficients and power constraints. First, for a deterministic broadcast network, we propose a new coding scheme, constructed by adopting a “receiver-centric” viewpoint, that uses quantize-and-forward relaying as an inner code concatenated with an outer Marton code for the induced deterministic broadcast channel. This scheme is shown to achieve the cut-set bound evaluated with product form distributions. This result is then lifted to the Gaussian network by using a deterministic network called the discrete superposition network as a formal quantization interface. This two-stage construction circumvents the difficulty involved in working with a vector nonlinear non-Gaussian broadcast channel that arises if we construct a similar scheme directly for the Gaussian network. [ABSTRACT FROM AUTHOR]

We study the two-user Gaussian multiple-input multiple-output (MIMO) broadcast channel with common and confidential messages. In this channel, the transmitter sends a common message to both users, and a confidential message to each user which needs to be kept perfectly secret from the other user. We obtain the entire capacity region of this channel. We also explore the connections between the capacity region we obtain for the Gaussian MIMO broadcast channel with common and confidential messages and the capacity region of its nonconfidential counterpart, i.e., the Gaussian MIMO broadcast channel with common and private messages, which is not known completely. [ABSTRACT FROM AUTHOR]

We study the secret-key capacity in a joint source-channel coding setup—the terminals are connected over a discrete memoryless channel and have access to side information, modelled as a pair of discrete memoryless source sequences. As our main result, we establish the upper and lower bounds on the secret-key capacity. In the lower bound expression, the equivocation terms of the source and channel components are functionally additive even though the coding scheme generates a single secret-key by jointly taking into account the source and channel equivocations. Our bounds coincide, thus establishing the capacity, when the underlying wiretap channel can be decomposed into a set of independent, parallel, and reversely degraded channels. For the case of parallel Gaussian channels and jointly Gaussian sources we show that Gaussian codebooks achieve the secret-key capacity. In addition, when the eavesdropper also observes a correlated side information sequence, we establish the secret-key capacity when both the source and channel of the eavesdropper are a degraded version of the legitimate receiver. We finally also treat the case when a public discussion channel is available, propose a separation based coding scheme, and establish its optimality when the channel output symbols of the legitimate receiver and eavesdropper are conditionally independent given the input. [ABSTRACT FROM AUTHOR]

We consider a broadcast channel with a degraded message set, in which a single transmitter sends a common message to two receivers and a private message to one of the receivers only. The main goal of this work is to find new lower bounds to the error exponents of the strong user, the one that should decode both messages, and of the weak user, that should decode only the common message. Unlike previous works, where suboptimal decoders were used, the exponents we derive in this work pertain to optimal decoding and depend on both rates. We take two different approaches. The first approach is based, in part, on variations of Gallager-type bounding techniques that were presented in a much earlier work on error exponents for erasure/list decoding. The resulting lower bounds are quite simple to understand and to compute. The second approach is based on a technique that is rooted in statistical physics, and it is exponentially tight from the initial step and onward. This technique is based on analyzing the statistics of certain enumerators. Numerical results show that the bounds obtained by this technique are tighter than those obtained by the first approach and previous results. The derivation, however, is more complex than the first approach and the retrieved exponents are harder to compute. [ABSTRACT FROM AUTHOR]

We present inner bounds to the broadcast capacity region of two classes of information networks: Networks of Multiple Access Channels (MACs) and Networks of Deterministic Broadcast Channels (DBCs). Our achievability scheme is a separation based scheme consisting of a physical layer that involves “cleaning up” the constituent channels in the network to create a point-to-point wired overlay, and a network layer that involves routing over this wired overlay. It is shown that finding the optimal way to “clean-up” is equivalent to the problem of finding maximal flows in “polymatroidal” flow networks, an already solved problem. The resulting inner bounds are cut-set bounds evaluated over product input distributions and are tight for Networks of DBCs. [ABSTRACT FROM AUTHOR]

We investigate the effects of user cooperation on the secrecy of broadcast channels by considering a cooperative relay broadcast channel. We show that user cooperation can increase the achievable secrecy region. We propose an achievable scheme that combines Marton's coding scheme for broadcast channels and Cover and El Gamal's compress-and-forward scheme for relay channels. We derive outer bounds for the rate-equivocation region using auxiliary random variables for single-letterization. Finally, we consider a Gaussian channel and show that both users can have positive secrecy rates, which is not possible for scalar Gaussian broadcast channels without cooperation. [ABSTRACT FROM AUTHOR]