We study cooperation problems in broadcast and relay networks, where the receivers do not satisfy the classical physical degradedness assumptions. New notions of degradedness,strongly less noisy and strongly more capableare introduced. We show that under these conditions, decode and forward (D&F) is optimal for classes of cooperative systems with limited conference rates, thus yielding new capacity results for these systems. In particular, we derive bounds on the capacity region of a class of broadcast channels with cooperation, that are tight on part of the capacity region. It is shown that the cut-set bound is tight for classes of primitive relay and diamond channels, beyond the physically or stochastically degraded models.

We study cooperation problems in broadcast and relay networks, where the receivers do not satisfy the classical physical degradedness assumptions. New notions of degradedness, strongly less noisy and strongly more capable are introduced. We show that under these conditions, decode and forward (D&F) is optimal for classes of cooperative systems with limited conference rates, thus yielding new capacity results for these systems. In particular, we derive bounds on the capacity region of a class of broadcast channels with cooperation, that are tight on part of the capacity region. It is shown that the cut-set bound is tight for classes of primitive relay and diamond channels, beyond the physically or stochastically degraded models.

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

The relay channel with unreliable helper is introduced and studied. The model is that of a classical relay channel where the input from the relay to the channel has an extra primitive link whose presence is not assured a priori. The extra link represents a helper who may decide not to cooperate in transmission. The goal is to devise robust coding schemes that exploit all the relay links when they are present, but can also operate, possibly at reduced rates, when the extra primitive link (helper) is absent. The capacity region of this class of problems is defined, and fully characterized for degraded relay channels. The degraded Gaussian relay channel with unreliable relay link is solved.

The relay channel with unreliable helper is introduced an studied. The model is that of a classical relay channel where the input from the relay to the channel has an extra primitive link whose presence is not assured a priori. The extra link represents a helper who may decide not to cooperate in transmission. The goal is to devise robust coding schemes that exploit all the relay links when they are present, but can also operate, possibly at reduced rates, when the extra primitive link (helper) is absent. The capacity region of this class of problems is defined, and fully characterized for degraded relay channels.

It has long been observed that cooperation between users in a communication network can improve its performance. Unfortunately, in practical ad-hoc networks, cooperation links can be unreliable, and in many cases part of the users in the system cannot be updated about their availability. In such a case we need robust coding schemes that exploit the cooperation links if they are present, but can still operate if cooperation is not possible. In this work we study the general broadcast channel with degraded message sets and cooperation link that may be absent, and derive its capacity region under such uncertainty conditions. A generalization of this model is studied, where the cooperation link capacity is one of k possible values, and its capacity region is derived. We examine the situation where the cooperation link capacity is random and suggest the following performance criterion: maximize the average rate of one user, subject to a constraint on the rate of the other user and the requirement that the system will operate in any realization of the (random) cooperation link. As examples to illustrate our results, the Gaussian broadcast channel is extensively examined, and its capacity is derived for the various cooperation models and assumptions suggested throughout.

We address the AVC with colored Gaussian noise. The paper consists of three parts. First, we study the AVC with fixed parameters, a model that combines the AVC and the time-varying channel. We determine both the deterministic and random code capacities and demonstrate super-additivity. In the second part, we consider the arbitrarily varying Gaussian product channel. The random code capacity was previously characterized by "double" water filling. We establish the deterministic code capacity and show that using independent scalar codes is suboptimal. Finally, we establish the capacity of the AVC with colored Gaussian noise, where double water filling is performed in the frequency domain. The analysis relies on our preceding results.

In this paper, we study the arbitrarily varying broadcast channel (AVBC) when the state information is available at the transmitter in a causal manner. We establish the inner and outer bounds on both the random code capacity region and the deterministic code capacity region with degraded message sets. The capacity region is then determined for a class of channels satisfying a condition on the mutual information between the strategy variables and the channel outputs. As an example, we consider the arbitrarily varying binary symmetric broadcast channel. We show the cases where the condition holds and, hence, the capacity region is determined and other cases where there is a gap between the bounds. This gap shows that the minimax theorem does not hold for rate regions.

We determine both the random code capacity region and the deterministic code capacity region of the arbitrarily varying multiple access channel (AVMAC) under input and state constraints. For the AVMAC without constraints, the characterization due to Ahlswede and Cai is complete except for two cases, pointed out in the literature as an open problem. The missing piece is obtained as a special case of our results.

We study the arbitrarily varying channel (AVC) with input and state constraints, when the encoder has state information in a causal or noncausal manner. For the causal state information setting, we develop lower and upper bounds on the random code capacity. A lower bound on the deterministic code capacity is established in the case of a message-averaged input constraint. In the setting where a state constraint is imposed on the jammer, while the user is under no constraints, the random code bounds coincide, and the random code capacity is determined. Furthermore, for this scenario, a generalized non-symmetrizability condition is stated, under which the deterministic code capacity coincides with the random code capacity. For the noncausal state information setting, we determine the random code capacity of the AVC under input and state constraints. In addition, a condition on the channel is stated, under which the deterministic code capacity coincides with the random code capacity.

We study the arbitrarily varying relay channel, and establish the cutset bound, decode-forward bound and partial decode-forward bound on the random code capacity. We further determine the random code capacity for special cases. Then, we consider deterministic coding schemes, and derive the deterministic code capacity, under certain conditions.

As demonstrated in many recent studies, cooperation between users can greatly improve the performance of communication systems. Most of the works in the literature present models where all the users are aware of the resources available for cooperation. However, the scenario where cooperation links are sometimes unavailable or that some users cannot be updated whether the cooperation links are present or not, is more realistic in today's dynamic ad-hoc communication systems. In such a case we need coding schemes that exploit the cooperation links if they are present, and can still operate if cooperation is not possible. In this work we study the general broadcast channel model with degraded message sets and cooperation links that may be absent, and derive it's capacity region under such uncertainty conditions.

In this work, we study the arbitrarily varying degraded broadcast channel (AVDBC), when state information is available at the transmitter in a causal manner. We establish inner and outer bounds on both the random code capacity region and the deterministic code capacity region. The capacity region is then determined for a class of channels satisfying a condition on the mutual informations between the strategy variables and the channel outputs. As an example, we show that the condition holds for the arbitrarily varying binary symmetric broadcast channel, and we find the corresponding capacity region.

We study the arbitrarily varying channel (AVC) with input and state constraints, when the encoder has state information in a causal manner. Lower and upper bounds on the random code capacity are developed. A lower bound on the deterministic code capacity is established in the case of a message-averaged input constraint. In the setting where a state constraint is imposed on the jammer, while the user is under no constraints, the random code bounds coincide, and the random code capacity is determined. Furthermore, for this scenario, a generalized non-symmetrizability condition is stated, under which the deterministic code capacity coincides with the random code capacity.

It is well known that cooperation between users in a communication network can lead to significant performance gains. A common assumption in past works is that all the users are aware of the resources available for cooperation, and know exactly to what extent these resources can be used. Unfortunately, in many modern communication networks, the availability of cooperation links cannot be guaranteed a priori, due to the dynamic nature of the network. In this paper, a family of models is suggested where the cooperation links may or may not be present. Coding schemes are devised that exploit the cooperation links if they are present, and can still operate (although at reduced rates) if cooperation is not possible.

It is by now well-known that cooperation between users can lead to significant performance gains. A common assumption in past works is that all the users are aware of the resources available for cooperation, and know exactly to what extent these resources can be used. In this work, we consider the multiple access channel (MAC) with (strictly causal, causal, and non-causal) cribbing that may be absent. The derived achievable regions are based on universal coding scheme which exploit the cribbing link if it is present, and can still operate (although at reduced rates) if cribbing is absent. We derive also an outer bound, which for some special case is tight.

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.

It is well known that cooperation between users in a communication network can lead to significant performance gains relative to the same network without cooperation. One common model which has been studied recently is the two users degraded broadcast channel (BC) with cooperating decoders. It can be viewed as a special case of the relay-broadcast channel (RBC), where the link from the relay to the other user is a noiseless channel (bit-pipe), that does not interact with the main channel. In this work two extensions of this basic model are suggested and studied: the BC with conferencing and degraded message sets, and the degraded BC with parallel conferencing, where there are parallel relays whose data streams are received by all the users in the channel. Since the data stream of each relay is also received by the other, one relay can allocate part of its rate to help the other relay to distribute its data stream. The capacity region is characterized for the two models.

We show that the rate regions achieved by linear-feedback coding schemes over dual multi-antenna Gaussian multi-access channels (MACs) and broadcast channels (BCs) with independent noises coincide. By dual here we mean: (1) the channel matrices of the MAC and the BC are transposes of each other and (2) the same total input-power constraint P is imposed on both the channels. We also present multi-letter expressions for the linear-feedback capacity regions of the two channels, i.e., for the set of all rates that are achievable with the linear-feedback coding schemes. We identify a sub-class of MAC and BC linear-feedback coding schemes that achieve the respective linear-feedback capacity regions, and within these subclasses, we identify pairs of MAC and BC coding schemes that achieve the same rate regions. In the two-user case, when the transmitters or the receiver are single-antenna, the capacity region for the Gaussian MAC is known [20], [15] and the capacity-achieving scheme is a linear-feedback coding scheme. With our results, we can thus determine the linear-feedback capacity region of the two-user Gaussian BC when either transmitter or receivers are single-antenna and we can identify the corresponding linear-feedback capacity-achieving coding schemes. Our results show that the control-theory inspired linear-feedback coding scheme by Elia [11], Wu et al. [30], and Ardestanizadeh et al. [1] is sumrate optimal among all the linear-feedback coding schemes for the symmetric single-antenna Gaussian BC with equal channel gains. More generally, we show that the linear-feedback sum-capacity of the scalar Gaussian BC with independent noises is achieved using a simple rearrangement of Ozarow's MAC encodings and decodings. In the K 3-user case, Kramer [16] and Ardestanizadeh et al. [2] determined the linear-feedback sum-capacity for the symmetric single-antenna Gaussian MAC with equal channel gains. Using our duality result, in this paper, we identify the linear-feedback sum-capacity for the K 3-user single-antenna Gaussian BC with equal channel gains. It is equal to the sum-rate achieved by Ardestanizadeh et al.'s linear-feedback coding scheme [1].

We show that for the multi-antenna Gaussian MAC and BC with perfect feedback, the largest achievable regions with linear-feedback schemes (called linear-feedback capacity regions) coincide when the same total input-power constraint is imposed on both channels and when the MAC channel matrices are the transposes of the BC channel matrices.

It is well known that cooperation between users in a communication network can lead to significant performance gains. A common assumption in past works is that all the users are aware of the resources available for cooperation, and know exactly to what extent these resources can be used. In this work a family of models is suggested where the cooperation links may or may not be present. Coding schemes are devised that exploit the cooperation links if they are present, and can still operate (although at reduced rates) if cooperation is not possible.

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

In this paper we study the degraded broadcast channel (DBC) with non-causal side information that depends on encoder's actions. This is a continuation of previous works, by Steinberg and Weissman and by Ahmadi and Simeone, that dealt with the causal case. We first focus on the model where the actions depend only on the messages. Inner and outer bounds on the capacity region of the DBC with non-causal knowledge of action-dependent states are developed. For the special case where the stronger user is informed about the states, the bounds coincide and the capacity region is characterised.

We study the interference channel with one-sided generalized feedback and secrecy requirements. In our model, Message 1 that is known just to Encoder 1 should be decoded by both receivers. Message 2—known only to Encoder 2—should be decoded by Decoder 2 and kept as secret as possible from Decoder 1. The uncertainty of Decoder 1 about Message 2 is measured by means of the equivocation rate. In addition, a noisy feedback is provided to Encoder 2. We derive an achievable rate-equivocation region for this model and an outer bound for the “noisy cribbing” regime without secrecy, the gap being the Markov conditions satisfied by one of the auxiliary random variables. Furthermore, we consider a simplified causal cognitive interference model: the interference channel with a cribbing encoder. We derive an inner bound on the rate region for this model and prove that when the interference channel is degraded conditionally on the input of Encoder 1, our inner bound is tight.

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

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

This paper studies the multiple-access channel (MAC) with rate-limited feedback. The channel output is encoded into one stream of bits, which is provided causally to the two users at the channel input. An achievable rate region for this setup is derived, based on superposition of information, block Markov coding, and coding with various degrees of side information for the feedback link. The suggested region coincides with the Cover-Leung inner bound for large feedback rates. The result is then extended for cases where there is only a feedback link to one of the transmitters, and for a more general case where there are two separate feedback links to both transmitters. We compute achievable regions for the Gaussian MAC and for the binary erasure MAC. The Gaussian region is computed for the case of common rate-limited feedback, whereas the region for the binary erasure MAC is computed for one-sided feedback. It is known that for the latter, the Cover-Leung region is tight, and we obtain results that coincide with the feedback capacity region for high feedback rates.

In this work we study problems of joint source-channel coding for the multiple access channel with cribbing encoders. These problems are motivated by modern communication scenarios such as an uplink channel for cellular users. Provided that the users are close enough to each other, they can causally crib to the output signals of their neighbours, thus obtaining some measure of cooperation. Three scenarios are considered in this work: (i) the symmetric model, where both encoders crib strictly causally at each other's output, (ii) the model where encoder 1 cribs strictly causally at the output of encoder 2, and encoder 2 cribs causally at the output of encoder 1, and (iii) the model where only one encoder cribs, in a causal or non-causal manner. For the symmetric case, model (i), sufficient conditions are derived for lossless transmission of a correlated pair source (U, V) via the multiple access channel (MAC). For the non-symmetric scenarios (ii) and (iii), necessary and sufficient conditions are derived, for transmissibility of the pair source via the MAC. The main focus of this work is on lossless transmission, however, for case (iii) we allow distortion in one of the source components.

In this paper we study the degraded broadcast channel with action dependent states and causal side information at the encoder. Two main models are studied: the case where the actions depend only on the messages, and the case where the actions can depend also on past values of the state. The latter model is referred to as actions with feedback. When the actions depend only on the messages, the full capacity region is derived. We then show that if the channel is physically degraded, then dependence of the actions on past values of the state does not increase its capacity region. We further demonstrate by an example that if the channel is stochastically degraded, action feedback can increase its capacity region. This situation resembles previous results on feedback in regular (state-independent) broadcast channels.

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

The two-user discrete memoryless state-dependent interference channel models a scenario in which two encoders transmit a pair of independent messages to two receivers where the signal intended for one receiver causes interference at the other receiver. Message 1 sent by Encoder 1 should be decoded by both receivers while Message 2 sent by Encoder 2 should be decoded by Decoder 2. The channel law is governed by an i.i.d. state process and the state sequence is available non-causally to both Encoder 2 and Decoder 2. It is further assumed that Encoder 2 cribs causally from Encoder 1. We derive an achievable rate-region for this model and show that it is tight when the output at Decoder 1 is degraded w.r.t. the output at Decoder 2 conditionally on the state and the input of Encoder 1.

The (non-causal) cognitive interference channel, studied recently by Liang et. al., is a model for a classical two-user discrete memoryless interference channel, over which two transmitters send a pair of independent messages. It is assumed that the first message is shared by both encoders, whereas the second message is known only to Encoder 2-the cognitive transmitter. Receiver 2 needs to decode both messages, and Receiver 1 should decode only the first message while Message 2 should be kept as secret as possible from Receiver 1. The level of secrecy is measured by the equivocation rate. For this model the capacity-equivocation region has been derived by Liang et. al. In this work we dispense of the assumption that Message 1 is shared a-priori by both encoders. Instead, we study the case in which Encoder 2 observes causally a feedback output of the channel and derive an achievable rate-equivocation region for this model. For a simplified model in which Encoder 2 cribs causally from Encoder 1 we establish the capacity-equivocation region for a degraded interference channel.

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

Consider the two-way rate-distortion problem in which a helper sends a common limited-rate message to both users based on side information at its disposal. We characterize the region of achievable rates and distortions when the Markov relation (Helper)-(User 1)-(User 2) holds. The main insight of the result is that in order to achieve the optimal rate, the helper may use a binning scheme, as in Wyner-Ziv, where the side information at the decoder is the ¿further¿ user, namely, User 2. We derive these regions explicitly for the Gaussian sources with square error distortion, analyze a tradeoff between the rate from the helper and the rate from the source, and examine a special case where the helper has the freedom to send different messages, at different rates, to the encoder and the decoder. The converse proofs use a technique for verifying Markov relations via undirected graphs.

Information embedding is the transmission of an independent data embedded into a host signal via a noisy channel. Reversible information embedding (RIE) extends this model by adding the requirement of decoding the host signal. In some applications however, this requirement is too strong. For example, if the user is interested in decoding the data and further transmitting the stegotext, i.e. the result of the embedding of independent data into the host, then full decoding of the host is not needed, only re-production of the stegotext. This work expands the study of information embedding channels by adding the requirement of retrieving the stegotext at the destination. A single-letter characterization of the achievable rate-distortion region is developed. In particular, it is shown that a rate higher than the RIE rate can be achieved, under the (more relaxed) requirement of stegotext decoding. Two examples are solved, and an iterative algorithm that computes numerically the capacity is provided.

Consider the two-way rate-distortion problem in which a helper sends a common limited-rate message to both users based on side information at its disposal. We characterize the region of achievable rates and distortions where a Markov form (Helper)-(User 1)-(User 2) holds. The main insight of the result is that in order to achieve the optimal rate, the helper may use a binning scheme, as in Wyner-Ziv, where the side information at the decoder is the ¿further¿ user, namely, User 2. The converse proofs use a new technique for verifying Markov relations via undirected graphs.

In this work we study source coding problems where a helper provides rate-limited side information to the involved parties. We first consider the Wyner-Ziv problem, where in addition to the memoryless side information available to the decoder, a helper sends common, rate-limited side information to the encoder and decoder. A single letter characterization of the achievable rates is derived, under certain Markov conditions on the source and side information. We then examine the problem of cascade rate distortion with a helper. Partial results are derived also for the case where the side information is not necessarily common, i.e., when the helper can send different streams of coded side information to the involved parties.

A multiple-input multiple-output (MIMO) system with a distributed receiver is considered. The system consists of a nomadic transmitter with several antennas, whose signal is received by multiple agents, exhibiting independent channel gains and an additive circular-symmetric Gaussian noise. In the nomadic regime, we assume that the agents do not have any decoding ability. These agents process their channel observations and forward them to the final destination through unidirectional lossless links with a fixed capacity. We propose new achievable rates based on elementary compression and on Wyner–Ziv (WZ)or chief executive officer (CEO) processing, for both fast-fading and block-fading channels, as well as for general discrete channels. The simpler two agents scheme is solved, up to an implicit equation with a single variable. Limiting the nomadic transmitter to circular-symmetric Gaussian signaling, new upper bounds are derived, based on the vector version of the entropy power inequality. Several asymptotic settings are analyzed. In addition, the upper bounds are analytically shown to be tight for several examples, while numerical calculations reveal a rather small gap in a finite$2\,\times\,2$setting. The advantage of the WZ approach over elementary compression is shown, where only the former can achieve the optimal diversity–multiplexing tradeoff (DMT).

This work studies problems of source and joint source-channel coding under the requirement that the encoder can produce an exact copy of the compressed source constructed by the decoder. This requirement, termed here as thecommon reconstruction constraint (CR), is satisfied automatically in rate-distortion theory for single sources. However, in the common formulation of problems of lossy source coding with side information at the decoder (the Wyner-Ziv problem), distributed source coding, and joint source-channel coding for networks, the destination can exploit the information it receives in a manner that cannot be exactly reproduced at the sender side. Some applications, like the transmission of sensitive medical information, may require that both sides-the sender and the receiver-will share a common version of the compressed data, for the purpose of future discussions or consulting. The purpose of this work is to study the implications of CR constraints on the achievable rates in scenarios of lossy source coding and lossy transmission of sources. Three problems are examined: source coding with side information at the decoder, simultaneous transmission of data and state over state-dependent channels, and joint source-channel coding for the degraded broadcast channel. Single-letter characterizations of the optimal performance are developed for these problems, under corresponding CR constraints. Implications of this constraint on problems of joint source-channel coding in networks are discussed.

The capacity region of a compound multiple-antenna broadcast channel is characterized when the users exhibit a certain degradedness order. The channel under consideration has two users, each user has a finite set of possible realizations. The transmitter transmits two messages, one for each user, in such a manner that regardless of the actual realizations, both users will be able to decode their messages correctly. An alternative view of this channel is that of a broadcast channel with two common messages, each common message is intended to a different set of users. The degradedness order between the two sets of realizations/users is defined through an additional, fictitious, user whose channel is degraded with respect to all realizations/users from one set while all realizations/users from the other set are degraded with respect to him.

This work studies the problem of simultaneous transmission of independent data and state via a state controlled channel, under the requirement that the encoder can produce locally an exact copy of the state estimation constructed by the decoder. The common formulation of problems of lossy source coding and source-channel coding, does not require that the sender be acquainted with the reconstructed source at the decoder. Some applications, like the transmission of medical images, may require that both sides - the sender and the receiver - will share a common version of the distorted data, for the purpose of future discussions or consultation. This requirement, termed here as the common knowledge (CK) constraint, is satisfied automatically in rate-distortion theory for single sources. However, in problems involving joint source-channel coding, the receiver can exploit the signals it receives in a manner that cannot be exactly reproduced at the sender site. In this work a single letter characterization of the achievable rate and distortion pairs is developed, for the problem of simultaneous transmission of data and state under the CK constraint. In particular, it is shown that even under the CK constraint separation strategy is not optimal in general, and joint state-channel coding is necessary to achieve optimal rate-distortion pairs.

The problem of a nomadic terminal sending information to a remote destination via agents with lossless connections to the destination is investigated. Such a setting suits, e.g., access points of a wireless network where each access point is connected by a wire to a wireline-based network. The Gaussian codebook capacity for the case where the agents do not have any decoding ability is characterized for the Gaussian channel. This restriction is demonstrated to be severe, and allowing the nomadic transmitter to use other signaling improves the rate. For both general and degraded discrete memoryless channels, lower and upper bounds on the capacity are derived. An achievable rate with unrestricted agents, which are capable of decoding, is also given and then used to characterize the capacity for the deterministic channel.

In this work, coding for channel with partial state information at the decoder is studied. Specifically, the model under consideration assumes that the encoder is provided with full channel state information (CSI) in a noncausal manner, and the decoder is provided with partial state knowledge, quantified by a rate limit. Coding of side information intended for the channel decoder is a Wyner-Ziv like problem, since the channel output depends statistically on the state, thus serving as side information in retrieving the encoded state. Therefore, coding for such a channel involves the simultaneous solution of a Wyner-Ziv problem and a related Gel'fand-Pinsker problem. A single-letter characterization of the capacity of this channel is developed, that involves two rate constraints, in the form of Wyner-Ziv and Gel'fand-Pinsker formulas. Applications are suggested to watermarking problems, where a compressed version of the host signal is present at the decoder. Two main models are examined: the standard watermarking problem, where the decoder is interested only in the embedded information, and the reversible information embedding problem, where the decoder is interested also in exact reproduction of the host. For both problems, single-letter characterizations of the region of all achievable rate-distortion triples (R, Rd, D) are given, where R is the embedding rate, Rdis the rate limit of the compressed host at the decoder, and D is the average distortion between the host and the composite data set (stegotext). For reversible information embedding, two stages of attack are considered, modeled by a degraded broadcast channel, where the weaker (degraded) channel represents the second attack, and both decoders are required to fully reproduce the host.

In this paper we investigate the achievable rate of a system that includes a nomadic transmitter with a Gaussian codebook and several antennas, which is received by multiple agents, each with a single antenna, suffering independent channel gains and additive Gaussian noise. In the nomadic regime, we assume that the agents do not have any decoding ability. These agents process their channel observations and forward it to the final destination through lossless links with fixed capacities. This paper extends a previous work [1] by providing new upper bounds on the achievable rates, and demonstrates optimality of the suggested coding scheme in several asymptotic situations. For a finite 2 × 2 setting and Rayleigh fading, the upper-bounds for both fast and block fading are demonstrated.

The capacity region of a compound multi-antenna broadcast channel is characterized when the users exhibit a certain degradedness order. For this purpose, we bring to bear a new extremal inequality for information theory and utilize a channel enhancement technique.

Channel coding for single-user channels with rate- limited, coded, partial channel state information at the transmitter and full side information (SI) at the receiver is studied. In the first part of the current work, we consider joint source-channel state channel coding. In particular, we deal with lossy transmission of a source, over a cost-constrained state controlled channel where the receiver gets full SI and the transmitter receive coded partial SI. We derive a single-letter characterization of the achievable distortion-cost triples. From this characterization, a separation principle follows for both, coding of the main source and the transmitter SI. In the second part, we consider channel coding when the transmitter receives multiple partial, rate-limited descriptions of the state, and the receiver gets full SI. Two rate-limited descriptions of the state sequence are generated and conveyed to the transmitter, where each description can be lost independently during this transmission. For three different possible partial SI at the transmitter, we explore a channel coding strategy with three different forward channel rates. Inner and outer bounds are derived on the set of achievable partial description and forward channel rates. Furthermore, special cases where the inner bound is tight are studied. Similarities between coding of SI as multiple partial descriptions and the multiple description problem of source coding theory are pointed out.

In this paper we investigate the achievable rate of a system that includes a nomadic transmitter with several antennas, which is received by multiple agents, each with a single antenna, suffering independent channel coefficients and additive Gaussian noises. Since the transmitter is nomadic, the agents do not have any decoding ability. These agents process their channel observations and forward it to the final destination through lossless links with a fixed given capacity. Assuming Gaussian signalling, we get lower and upper bounds on the achievable rates, and demonstrate the achievability of the full multiplexing gain. We also extend the model to address multi-user systems. The asymptotic setting with numbers of agents and transmitter's antennas taken to infinity is examined, and the incompetence of the simple compression when compared to a Wyner-Ziv scheme is demonstrated. For finite setting, an upper-bound is derived, which turns out to be quite tight when compared to the Wyner-Ziv achievable rate, even for a rather small 4 × 4 system.

This work studies reversible information embedding, where a compressed host data is available, before transmission, at the decoder. The problem is solved for a (fixed) degraded broadcast attack channel, which corresponds to the scenario where the stegotext is subject to several stages of attack. A single letter characterization of the region of all achievable rate-distortion quadruples (Ry, Rz, Rd, D) is given, where Ry, Rzare the embedding rates, Rdis the rate limit of the compressed host at the decoders, and D is the average distortion between the host and the data set (stegotext)

In this paper we discuss a two user Multi-Antenna Gaussian broadcast channel with common messages and explore the achievable region suggested by Jindal and Goldsmith. We present simple outer-bounds which are shown to be tight at certain regions. We investigate the aligned channel with common messages and show that beyond a certain threshold on the common rate, the achievable region coincides with the capacity region and we also give a full characterization of the capacity region of the degraded message sets case.

In this work we characterize the capacity region of the arbitrarily varying degraded memoryless broadcast channel, with noncausal channel state information at the transmitter (CSIT), and full channel state information at the receiver of the stronger user (CSIR). The analysis follows ideas of Ahlswede. The techniques used in this work can be used to derive an inner bound on the capacity region of an arbitrarily varying degraded broadcast channel without CSIR

In this work coding for channel with partial state information at the decoder is studied. Specifically, the model under consideration assumes that the encoder is provided with full channel state information in a non causal manner, and the decoder is provided with partial state knowledge, quantified by a rate-limit. Coding of side information intended for the channel decoder is a Wyner-Ziv like problem, since the channel output depends statistically on the state, thus serving as side information in retrieving the encoded state. Therefore, coding for such a channel involves the simultaneous solution of a Wyner-Ziv problem and a related Gel'fand-Pinsker problem. A single letter characterization of the capacity of this channel is developed, that involves two rate constraints, in the form of Wyner-Ziv and Gel'fand-Pinsker formulas. Applications to watermarking problems are suggested.

We extend the setting of two-stage lossy source coding with successive refinement structures into a joint source-channel coding setting. In particular, we consider a problem where two descriptions of a memoryless source are to be transmitted across two independent memoryless channels and where the output of the channel corresponding to the first (coarse) description is also available to the decoder of the second (refinement) decoder. Side information (SI), correlated to the source, may also be available to the decoders. In such a case, we confine attention to degraded SI, in the sense that the source, the SI available at the refinement decoder, and the SI available at the coarse decoder form a Markov chain in this order. Our first result is a separation theorem asserting that in the limit of long blocks, no optimality is lost by first applying lossy successive-refinement source coding, regardless of the channels, and then applying good channel codes to each one of the resulting bitstreams, regardless of the source and the SI. It is also shown that (even noiseless) feedback from the output of the first channel to the input of the second encoder cannot improve performance, but may sometimes significantly facilitate the implementation of optimum codes. We provide two examples where single-letter codes (of unit block length) achieve optimum performance, if feedback from the channel output of the first stage is provided to the encoder of the refinement stage. In one of these examples, it is evident that if feedback is not provided, optimality cannot be achieved with unit length code. Motivated by these examples, we then investigate single-letter codes for this system. Necessary and sufficient conditions are furnished for the optimality of single-letter codes with and without feedback. A corollary of these conditions is that for the quadratic distortion measure, feedback is necessary to achieve optimality in single-letter codes, regardless of the source distribution and the channel statistics

The Gaussian multiple-input multiple-output (MIMO) broadcast channel (BC) is considered. The dirty-paper coding (DPC) rate region is shown to coincide with the capacity region. To that end, a new notion of an enhanced broadcast channel is introduced and is used jointly with the entropy power inequality, to show that a superposition of Gaussian codes is optimal for the degraded vector broadcast channel and that DPC is optimal for the nondegraded case. Furthermore, the capacity region is characterized under a wide range of input constraints, accounting, as special cases, for the total power and the per-antenna power constraints

This paper considers joint state-source-channel coding and multiple descriptions coding of channel state information (CSI), for state dependent channels. Specifically, we examine coded, non-causal CSI at the transmitter (CSIT) and full CSI at the receiver (CSIR)

The common problem of a nomadic terminal sending information to a remote destination via agents with lossless connections is investigated. Such a setting suits, e.g. access points of a wireless network, where each access point is equipped with a different connection bandwidth. The case where these agents do not have any decoding ability is fully characterized for the Gaussian channel, when the transmitter uses "typical" codewords. For general discrete memoryless channels, lower and upper bounds are derived. An achievable rate with unrestricted agents, which are capable of decoding, is also given and then demonstrated by a numerical example for the Gaussian channel

In this paper we study coding for the general broadcast channel, controlled by random parameters, where the parameters are provided to the encoder only, in a non-causal manner. We give an achievable region which is an extension of the Marion region to the current model. The region we derive is shown to be tight for the Gaussian broadcast channel with additive interference at the two channels

This work studies the multiple-access channel (MAC) controlled by random parameters, with full side information at the decoder, and partial, rate limited, side information (SI) at the encoders. A single-letter characterization of the capacity region is derived, for the special case where the SI is degraded. Here degraded SI refers to the case where the SI available at one of the encoders is a subset of the SI available at the other encoder. Inner and outer bounds are derived on the capacity region of that channel for the general case where there are no restrictions on the structure of the SI at the two encoders. The techniques employed for coding the rate-limited SI, and the achievable regions so obtained, are closely related to the problems of hierarchical source coding, and multiple descriptions.

We consider an independent and identically distributed (i.i.d.) state-dependent channel with partial (rate-limited) channel state information (CSI) at the transmitter (CSIT) and full CSI at the receiver (CSIR). The CSIT comprises two parts, both subject to a rate constraint, and communicated over noiseless way-side channels. The first part is coded CSI, provided by a third party (a genie), and the second part is the output of a deterministic scalar quantizer of the state. A single-letter expression for the capacity of the channel is given. In case the CSIT comprises only the coded part, we show that the capacity previously suggested in the literature is too optimistic, and suggest a correction as part of our expression for the information capacity. For the general setting, an optimal coding scheme based upon multiplexing of several codebooks is presented. It is proved that the capacity of the channel is the same whether the quantizer's output is observed causally or noncausally by the encoder. In the rest of the correspondence, we focus on the special case where the system employs a stationary quantizer. Using a rate distortion approach we bound the alphabet's size of the auxiliary random variable (RV) of the information capacity. Next, we turn to the additive white Gaussian noise (AWGN) channel with fading, and show that the determination of the capacity region reduces to finding the optimal genie strategies and the optimal power allocation distribution along the product alphabet of the auxiliary RV and the quantizer's output alphabets. The suggested model can be applied, for example, to an orthogonal frequency-division multiplexing (OFDM) communication system. Here the fading across frequencies comprises the channel state sequence. Coded fading information is provided to the channel encoder via a way-side, rate-limited channel. In addition, since coding operation is expensive, a simpler scheme provides the channel encoder with quantized fading information, e.g., whether each coefficient is above/below a threshold.

In this work, coding for the degraded broadcast channel controlled by random parameters is studied. Two main paradigms are considered: where side information on the random parameters is provided to the transmitter in a noncausal manner (termed here noncausal coding), and where side information is provided in a causal manner (termed causal coding). Inner and outer bounds are derived on the capacity region with noncausal coding. For the special case where the nondegraded user is informed about the channel parameters, it is shown that the inner bound is tight, thus deriving the capacity region for that case. For causal coding, a single-letter characterization of the capacity region is derived. This characterization is expressed via auxiliary random variables (RVs), and can also be interpreted by means of Shannon strategies, as the formula for the capacity of the single-user channel with causal coding derived by Shannon. The capacity region of a class of binary broadcast channels with causal coding is computed, as an example. Applications to watermarking are suggested. In particular, the results on noncausal coding can be used to derive the capacity region of a watermarking system where the channel (attacker) is fixed, and the watermark is subject to several stages of attack, or a watermarking system where the encoder is required to encode watermarks for both private and public users

The capacity region of an i.i.d. state controlled memoryless multiple-access channel (MAC) with degraded, noncausal, rate-limited channel state information (CSI) at the transmitters (CSIT), and full CSI at the receiver (CSIR) is derived in this paper.

In this paper, We extend the notion of successive refinement (SR) of information to the Wyner-Ziv setting, where the decoders of the different stages have access to (possibly different) side informations, Y and Z, both correlated to the source to be encoded, X. We also give necessary and sufficient conditions for successive refineability

In this paper, we extend the setting of source coding with successive refinement into a joint source-channel coding setting: two descriptions of a memoryless source are to be transmitted across two independent memoryless channels. The output of the channel corresponding to the first (coarse) description is also available to the decoder of the second (refinement) channel. Side information (SI) is available to the decoders. Feedback from the output of the first (coarse) channel to the encoder of the second (refinement) channel is also available

The dirty paper coding rate region is shown to be the capacity region of the Gaussian MIMO broadcast channel. To that end, a new notion of an enhanced broadcast channel is introduced.

Achievable rates are characterized for successive refinement (SR) in the Wyner-Ziv scenario, namely, in the presence of correlated side information (SI) at the receivers. In this setting, the encoder is assumed to operate in two stages, where the first corresponds to relatively low rate and high distortion, and the second, comprising a refinement code on top of the first code, is aimed at reproduction at reduced distortion. Both decoders (for low rate/high distortion and for high rate/low distortion) are equipped with SI streams, correlated to the source, but unavailable to the encoder. Furthermore, it is assumed that the decoder that receives the higher rate bitstream, i.e., the additional refinement bits, accesses also SI of "better quality" than that of the lower resolution decoder. By "better quality," we mean that the source and the SI are modeled together as a stochastically degraded joint source, where the encoded symbols, the SI at the refinement stage, and the SI at the initial (coarse) stage, form a Markov chain in this order. For a memoryless joint process (that includes the source to be encoded and its instantaneously correlated SI streams), necessary and sufficient conditions are furnished, in terms of single-letter formulas, for the achievability of a pair of rates, corresponding to two given distortion levels. Special attention is devoted to the degenerate, but important, case where the two SI streams, at the two decoders, are identical. For this case, conditions are provided for successive refinability in the sense of the existence of codes that asymptotically achieve the Wyner-Ziv rate-distortion function, simultaneously at both distortion levels. In this context, the doubly symmetric binary source (with the Hamming distortion measure) and the jointly Gaussian source (with the squared error distortion measure) are successively refinable in the Wyner-Ziv setting. It is demonstrated that a source that is not successively refinable in the ordinary sense (i.e., without SI) may become successively refinable in the presence of SI at the decoders.

We investigate the fading multiple-antenna channel. The decoder is assumed to possess imperfect channel fading information. A modified nearest neighbor decoder with an innovative weighting factor is introduced and an expression for the generalized mutual information (GMI), the achievable rate, is obtained. We show that under certain conditions the achievable rate is equivalent to that of a fading multiple-antenna Gaussian channel where fading is known to the receiver and is equal to the channel estimation, and where noise is due to both the channel noise and the channel estimation error. We show that for our communication scheme, the minimum mean square error (MMSE) channel estimator is optimal in the sense that it achieves the highest value of GMI, and hence the highest communication rate. Additionally, a training based multiple-input multiple-output (MIMO) scheme in a block-fading channel is investigated and it is shown that the number of degrees of freedom depends on the signal-to-noise ratio (SNR).

In this work we study the problem of identification via the degraded broadcast channel with random parameters. Inner and outer bounds are derived on the identification capacity region when the random parameters are known non-causally to the encoder and to the non-degraded decoder. Applications to watermarking are suggested. In particular, this model describes the situation when watermarks are supposed to be identified by both private and public users.

Watermarking codes are analyzed from an information-theoretic viewpoint as identification codes with side information that is available at the transmitter only or at both ends. While the information hider embeds a secret message (watermark) in a covertext message (typically, text, image, sound, or video stream) within a certain distortion level, the attacker, modeled here as a memoryless channel, processes the resulting watermarked message (within limited additional distortion) in attempt to invalidate the watermark. In most applications of watermarking codes, the decoder need not carry out full decoding, as in ordinary coded communication systems, but only to test whether a watermark at all exists and if so, whether it matches a particular hypothesized pattern. This fact motivates us to view the watermarking problem as an identification problem, where the original covertext source serves as side information. In most applications, this side information is available to the encoder only, but sometimes it can be available to the decoder as well. For the case where the side information is available at both encoder and decoder, we derive a formula for the identification capacity and also provide a characterization of achievable error exponents. For the case where side information is available at the encoder only, we derive upper and lower bounds on the identification capacity. All characterizations are obtained as single-letter expressions.

We study the randomness needed for approximating the output distribution of a multiple-access channel, where the original input processes are independent of each other. The approximation is achieved by simulating (possibly alternative) input processes at each of the entries, where the sources of randomness available for the simulators are independent of each other, and the simulators do not cooperate. The resolvability region of a multiple-access channel is defined as the set of all random-bit rate pairs at which accurate output approximation is possible, where the simulation accuracy is measured by the variational distance between finite-dimensional output distributions. Inner and outer bounds on the resolvability region are derived, and close relations between the concepts of resolvability region and capacity region are demonstrated.

New converses for identification via arbitrary single-user and multiple-access channels, with finite first- and second-type probabilities of error, are developed. For the arbitrary single-user channel, it is shown that (/spl lambda//sub 1/, /spl lambda//sub 2/)-identification capacity is upper-bounded by /spl lambda/-capacity, and optimistic (/spl lambda//sub 1/,/spl lambda//sub 2/)-identification capacity is upper-bounded by optimistic /spl lambda/-capacity, for any /spl lambda/>/spl lambda//sub 1/+/spl lambda//sub 2/. The bounds become tight at the limit of the vanishing probabilities of error, thus generalizing previous results by Han and Verdu (1992), who showed that the identification capacity is equal to transmission capacity for channels satisfying the strong converse of the channel coding theorem. A by-product of the new identification converses is a general formula for optimistic /spl lambda/-capacity. An outer bound on the (/spl lambda//sub 1/, /spl lambda//sub 2/)-identification capacity region of an arbitrary multiple-access channel is developed. A consequence of this bound is that the identification capacity region is equal to the transmission capacity region for any stationary, finite-memory multiple-access channel. The key tool in proving these bounds is the partial resolvability of a channel, a new notion in resolvability theory, which deals with approximation of the output statistics on a suitably chosen part of the output alphabet. This notion of approximation enables us to get sharp bounds on identification for arbitrary channels, and to extend these bounds to the multiple-access channel.

The Bayesian Ziv-Zakai bound on the mean square error (MSE) in estimating a uniformly distributed continuous random variable is extended for arbitrarily distributed continuous random vectors and for distortion functions other than MSE. The extended bound is evaluated for some representative problems in time-delay and bearing estimation. The resulting bounds have simple closed-form expressions, and closely predict the simulated performance of the maximum-likelihood estimator in all regions of operation.

We study the randomness necessary for the simulation of a random process with given distributions, on terms of the finite-precision resolvability of the process. Finite-precision resolvability is defined as the minimal random-bit rate required by the simulator as a function of the accuracy with which the distributions are replicated. The accuracy is quantified by means of various measures: variational distance, divergence, Orstein (1973), Prohorov (1956) and related measures of distance between the distributions of random process. In the case of Ornstein, Prohorov and other distances of the Kantorovich-Vasershtein type, we show that the finite-precision resolvability is equal to the rate-distortion function with a fidelity criterion derived from the accuracy measure. This connection leads to new results on nonstationary rate-distortion theory. In the case of variational distance, the resolvability of stationary ergodic processes is shown to equal entropy rate regardless of the allowed accuracy. In the case of normalized divergence, explicit expressions for finite-precision resolvability are obtained in many cases of interest; and connections with data compression with minimum probability of block error are shown.

The single-user separation theorem of joint source-channel coding has been proved previously for wide classes of sources and channels. We find an information-stable source/channel pair which does not satisfy the separation theorem. New necessary and sufficient conditions for the transmissibility of a source through a channel are found, and we characterize the class of channels for which the separation theorem holds regardless of the source statistics.>

Considers the problem of multiuser amplitude estimation, i.e., the problem of estimating the amplitudes of several digital communications signals superimposed in the same channel. This problem is of importance in communications environments such as spread-spectrum radio networks, in which nonorthogonal multiplexing is used. Multiuser amplitude estimation is a critical prerequisite to the optimum demodulation of such signals using, for example, Verdu's algorithm. In the present paper, a sequential detection-estimation approach is applied to this problem, and several estimation paradigms, including the method of moments and likelihood-based estimators, are considered. The consistency, asymptotic variance, and complexity of these estimators are examined. A new method of constructing a recursive consistent and asymptotically efficient estimation algorithm out of a consistent estimator sequence is also suggested and is applied to the current setup. It is seen that detector-estimators that use these estimators in Verdu's algorithm result, asymptotically, in (known-amplitude) optimum error probabilities with little relative increase in complexity per demodulated bit.>

The problem of estimating the symbol timing in wideband data communication signals is considered. Conventional approaches to this problem suffer from several drawbacks, including possible lack of consistency due to multiple extrema in the error surface, and very slow convergence due to exceedingly sharp waveform correlation functions. In the paper sequential detection-estimation algorithms that alleviate these problems are constructed and analyzed. These algorithms are based on two techniques: the use of regularization (i.e., prefiltering) to produce a consistent initial estimate at the expense of higher mean-square error, and the coupling of recursive maximum-likelihood with this consistent estimator to produce the desired goal-a recursive consistent and efficient estimator.>

Studies the minimum random bit rate required to simulate a random system (channel), where the simulator operates with a given external input. As measures of simulation accuracy the authors use both the variational distance and the d~ distance between joint input-output distributions. They find the asymptotic number of random bits per input sample required for accurate simulation, as a function of the distribution of the input process. These results hold for arbitrary channels and input processes, including nonstationary and nonergodic processes and do not hinge on a specific simulation scheme. A by-product of the analysis is a general formula for the minimal achievable source coding rate with side information.>

A practical suboptimal universal block source coding scheme, subject to a fidelity criterion, is proposed. The algorithm is an extension of the Lempel-Ziv algorithm and is based on string matching with distortion. It is shown that given average distortion D>0, the algorithm achieves a rate of exceeding R(D/2) for a large class of sources and distortion measures. Tighter bounds on the rate are derived for discrete memoryless sources and for memoryless Gaussian sources.>

The problem of deciding whether a sample of a random field was generated by a Gaussian distribution is considered. Based on extensions of large deviation estimates due to M.D. Donsker and S.R.S. Varadhan (1985), a test that is optimal in a generalized Neyman-Pearson sense is proposed. This test turns out to depend on properties of the entropy of Gaussian processes and does not depend on cumulant computations.>