{'fraction_non_alphanumeric': 0.04184700646157996, 'fraction_numerical': 0.007675425152343702, 'mean_word_length': 4.268393514630838, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 38, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimality and Approximate Optimality of Source-Channel Separation in Networks

We consider the source-channel separation architecture for lossy source coding in communication networks. It is shown that the separation approach is optimal in two general scenarios, and is approximately optimal in a third scenario. The two scenarios for which separation is optimal complement each other: the first is when the memoryless sources at source nodes are arbitrarily correlated, each of which is to be reconstructed at possibly multiple destinations within certain distortions, but the channels in this network are synchronized, orthogonal and memoryless point-to-point channels; the second is when the memoryless sources are mutually independent, each of which is to be reconstructed only at one destination within a certain distortion, but the channels are general, including multi-user channels such as multiple access, broadcast, interference and relay channels, possibly with feedback. The third scenario, for which we demonstrate approximate optimality of source-channel separation, generalizes the second scenario by allowing each source to be reconstructed at multiple destinations with different distortions. For this case, the loss from optimality by using the separation approach can be upper-bounded when a"difference"distortion measure is taken, and in the special case of quadratic distortion measure, this leads to universal constant bounds.

The difficulty in answering these questions lies in the fact that in most multiuser communication scenarios, we do not have explicit characterizations of the rate-distortion regions, the channel capacity regions, or the joint coding achievable distortion regions; however, in order to determine whether the separation approach is optimal, it is natural to first couple the rate-distortion region and the channel capacity region, then compare it with the joint coding achievable distortion region. With at least one region unknown in most cases, it seems utterly impossible to answer the above questions even in some of the simplest settings (e.g., communicating sources on an interference channel), let alone in more complex networks. In this work, we show that this difficulty in determining the optimality of source-channel separation can in fact be circumvented completely in several important settings, and the answers to the sequence of questions posed earlier are indeed positive.
More precisely, we show that for lossy coding of memoryless sources in a network, the source-channel separation approach is optimal for the following two general scenarios: the first scenario, referred to as distributed network joint source-channel coding (DNJSCC), is when the sources are arbitrarily correlated, each of which is to be reconstructed at possibly multiple destinations within certain distortions, but the channels between any pair of nodes 1 in this network are synchronized, orthogonal, and memoryless; the second scenario, referred to as joint source-channel multiple unicast with distortion (JSCMUD), is when the sources are mutually independent, each of which is to be reconstructed only at one destination within a certain distortion, but the channels can be general, including multi-user channels such as multiple access, broadcast, interference and relay channels, possibly with feedback.
The third scenario is a natural extension of the second one by allowing a source to be reconstructed at multiple destinations; this case is referred to as joint source-channel multiple multicast with distortion (JSCMMD). For this scenario, the classical example of sending a Gaussian source over a Gaussian broadcast channel [3] reveals that the source-channel separation approach is not optimal in general. Thus we turn our attention to whether the separation approach is approximately optimal, and show that under the "difference" distortion measure, it is indeed so in the sense that the loss from the optimum can be upper-bounded 2 . In the important special case of quadratic distortion measure, the upper bound is at most 0.5 bit per (additional) user which reconstructs the same source.
Though our results demonstrate the effectiveness of source-channel separation, a large portion of the difficulty in designing efficient codes remains in the extracted pure source coding problem or the extracted pure channel coding problem. Particularly for the DNJSCC problem, the network induces a pure sourcecoding problem with rather complex multiple-session user interactions where each session has the same rate, which suggests a distinct and perhaps under-studied line of research in network source coding. Some simple interactive settings have indeed been considered in the literature: Kaspi considered the lossy two-way source coding problem [4] (see more recent results in [5], [6]), and in a series of papers, Orlitsky considered the lossless two-way problem from the perspective of worst-case vs. average-case communication complexity [7]- [9]. Our work suggests that it is important to consider the interactive coding problems for the case of a large (or infinite) number of sessions, and the interactive communication rates do not need to change from session to session. This class of source-coding problems naturally occur in practice, and their solutions in fact solve a large class of joint source channel coding problems.
When discussing source-channel separation, it is natural to assume that the sources are independent of the channels, which is often the default assumption in the information theory literature, and it is also assumed in this work. More precisely, the assumption is that the channel output is conditionally independent of the sources given the channel input. This is because otherwise, even if the encoding and decoding functions are designed according to the separation architecture, the inherent dependence between source and channel will render such a separation rather meaningless even in a point-to-point setting, and joint source-channel coding is expected to be more effective in these scenarios.
In the rest of this section, we give a brief overview of our proof approach, and discuss the relation between this work and existing work in the literature.

A. Overview of the Indirect Approach
As mentioned earlier, the direct proof approach of first characterizing all the relevant regions in their single letter forms, and then making comparison is rather difficult, thus instead, our approach is an indirect one.
For the distributed network joint source-channel coding problem, the key observation is in fact extremely simple, which is to abstract the block channel input into a super source which can be compressed with certain rate. Roughly speaking, for a fixed joint source-channel code, the block channel input of this code can be viewed as a super source, and thus we can simulate the channel output by compressing this super source with some lossy source code, whose compression rate is upper-bounded by the channel capacity of the original channel. Thus any joint source-channel code can be converted into a separation-based code with asymptotically the same performance, which implies the optimality of source-channel separation. The first example in Section II illustrates this idea for a simple DNJSCC problem. For more complex networks with relay and feedback, there is an additional difficulty introduced by the interaction of the users, and this can be resolved by properly interleaving many copies of the original joint source-channel code (see also the discussion in the next subsection regarding the relation with [10]).
The technique we rely on to tackle the second scenario, i.e., joint source-channel multiple unicast with distortion, is complementary to the previous case. Here the overall communication system is abstracted into an interference channel with certain individual mutual information guarantees that are implied by the achievable end-to-end distortions. Roughly speaking, for a fixed joint source-channel code, the deterministic encoding-decoding operations together with the probabilistic channel operations can be viewed as an induced (memoryless) super block channel, where these mutual information guarantees can be utilized to provide a lower bound to the capacity of this super block channel. Thus the sources can be sent over this new super block channels, and it follows again that any joint source-channel code can be converted into a separationbased scheme with asymptotically the same performance. The second example in Section II illustrates this case with a small interference network.
For the third scenario of joint source-channel multiple multicast with distortion, a similar abstraction yields a more complex interference channel. However, for this case, the mutual information guarantees are less straightforward, and they have to be derived in conjunction with the separation-based coding scheme. The separation architecture we use here is based on successive refinement codes for each source [11], [12], concatenated with delivery of messages within degraded message sets [13]. By strategically comparing the rate expressions of this separation scheme and utilizing the rate loss technique [14], we are able to upperbound the performance gap between the joint source-channel scheme and the separation-based scheme (see also discussion in the next subsection). As in earlier scenarios, this result does not rely on an explicit solution of either the degraded message set problem or the joint source-channel coding problem.

B. Relation to Existing Works
Closely related to source-channel separation in the DNJSCC problem is the problem of separation between network coding and channel coding, which has received considerable attention in recent years [10], [15]- [17]. In general, the approach based on separating network coding and channel coding is also not optimal [17]. However, a surprising result by Koetter, Effros and Medard [10] essentially states that for general multicast on networks with orthogonal, synchronized and memoryless point-to-point channels (i.e., "noisy" graphs), there is no loss of optimality by employing such a separation. The DNJSCC problem we consider can be thought of as a generalization of the problem studied in [10] to correlated sources with distortions, and in fact the interleaving technique in our proof is directly borrowed from [10]. The super source view and the channel simulation idea are also inherent in the proof in [10], however, they are encapsulated in the "stacked network" technique, and thus less transparent. In contrast, we explicitly apply the super source view and the channel simulation idea on the original network instead of the "stacked network", which results in a conceptually more straightforward proof, despite the more general setting of lossy source coding and correlated sources 3 . It is worth noting that [10] does not directly focus on the issue of sourcechannel separation, and the result is given from the perspective of an equivalence model. For this reason, the induced pure block source coding problem is not defined formally in their work. In contrast, we directly consider the separation issue on the original network, and the induced pure source coding problem shall be defined explicitly in the traditional block coding framework.
Another approach of treating source-channel separation for various special cases in DNJSCC is to utilize the infinite letter expressions, instead of the single letter characterizations, of the source coding rate regions and the joint coding achievable distortion regions. This is also an indirect approach, since the infinite letter expressions are not computable, and thus do not qualify as characterizations; see [19] for discussions on the computability issue. In [20], Yeung applied this indirect approach to several classical multiuser source coding problems on orthogonal communication channels, including the (two-user) distributed source coding problem [21], the multiple description problem [22] and the cascade communication problem [23]. Xiao and Luo [24] applied this approach to the problem of distributed source coding (with any number of users) on orthogonal multiple access channels. Though this approach is successful in these simple settings, it becomes rather unwieldy in more complex networks. In contrast, our proof approach can be naturally applied to more general networks, and consequently the result for the DNJSCC problem in this work subsumes those in [20] and [24].
A more recent work related to the DNJSCC problem is by Han [25], where the problem of lossless coding of correlated sources on acyclic networks (i.e., no feedback) with orthogonal channels is considered; see also [26], [27] for earlier results on such networks with a single sink node. Han provided a necessary and sufficient condition for transmissibility in terms of source entropies and channel cut-set capacity. The approach took in [25] is to first give a necessary condition for transmissibility using conventional information inequalities, and then show that a separation-based approach can transmit the sources as long as this condition is satisfied. This proof approach appears difficult to apply on networks with feedback and lossy reconstructions. Interestingly, the result in [25] establishes a source-channel separation different from the one we consider in this work, and this intriguing point will be revisited in the last section.
Similar to the approach we take in the JSCMUD problem, the super-channel view was also used in [28], [29] where non-ergodic point-to-point communications were considered. The focus of [28], [29] is mainly on non-ergodic point-to-point channels, whereas our focus is on ergodic channels but in a more general network setting. The network scenario is quite different from the point-to-point case since it induces a coupling of the transmitted signals through the abstracted interference channel.
The difficulty encountered in the JSCMMD problem is similar to that in [30], where a simpler version of the problem, i.e., broadcasting a single Gaussian source with bandwidth mismatch, was considered. The proof approach in [30] is to introduce many additional auxiliary random variables not in the original problem (originally applied on the multiple description problem; see [31]), then derive explicit outer bound by leveraging the Markov relation among them. Our approach for the JSCMMD problem is a generalization of this technique, however, the introduced auxiliary random variables serve another role in addition to providing an outer bound: their probability distribution is also used to generate codewords in the successive refinement source codes. By strategically utilizing the rate loss technique [14] together with these auxiliary random variables, we are able to upper-bound the performance loss by the separation-based scheme.
The DNJSCC problem and JSCMUD problem, for which source-channel separation is optimal, include many cases previously considered in the literature. For example, the joint source-channel coding problem of successive refinement coding with degraded decoder side information in [32], [33], and the two-way successively refined joint source-channel coding problem considered in [34] are special cases of the DNJSCC problem; when the sources are independent, the problem of sending a pair of Gaussian sources over Gaussian broadcast channels [35] and sending a pair of Gaussian sources over interference channels [36], are special cases of the JSCMUD problem.
Shannon's source-channel separation in the classical sense has several immediate implications, some of which may be taken individually as weaker notions of source-channel separation. For example, Tuncel [37] discovered an "operational separation" where the source codebook and the channel codebook are largely designed independently, between which only certain codeword indices serve as their connection. This notion of operational separation is weaker than the classical source-channel separation, which was referred to as "information separation" in [37]. To see this, observe that in the classical source-channel separation architecture, the digital codeword indices are the only information interface between the source coding component and the channel coding component, and particularly the source decoder takes the decoded digital codeword indices from the channel decoder as the sole information provider originating from the channel output, and ignores any other information from the channel. The decoder in the coding strategy in [37] is in fact a joint decoder which is impossible to be separated into two components. In our work, we shall use the notion of source-channel separation in the classical (informational separation) sense; this point regarding the meaning of source-channel separation will be revisited in later sections.

C. Paper Organization
The rest of this paper is organized as follows. In Section II we discuss a few examples to provide some intuitions for the solutions. Necessary notation and definitions are given in Section III. The main results and the proofs on DNJSCC, JSCMUD and JSCMMD are given in Sections IV, V and VI, respectively. Section VII concludes the paper.

II. THREE EXAMPLES
In this section we discuss three examples in the context of sending sources on interference channels to provide some intuitions for the optimality (or approximate optimality) of source-channel separation in DNJSCC, JSCMUD and JSCMMD. The main results of this work are built on these intuitions, and Sections IV, V and VI essentially make them more precise and rigorous. For simplicity, the channel bandwidth and source bandwidth are assumed to match.

A. An Example for Distributed Network Joint Source-Channel Coding
Consider the example depicted in Fig. 1, where the discrete memoryless sources S 1 , S 2 are correlated. Each discrete memoryless channel between a transmitter and a receiver is orthogonal to the other channels. More precisely, the channel from node i to node j has transition probability P (Y i,j |X i,j ), and the overall transition probability is given by (i,j) P (Y i,j |X i,j ). Both node 3 and node 4 require a lossy reconstruction of source S 1 , denoted asŜ 1,3 andŜ 1,4 , respectively. Node 4 also requires a lossy reconstruction of source S 2 , denoted asŜ 2,4 .
Though the capacity region of this special case of the interference channel is not difficult to establish, the rate-distortion region of the source coding problem is not known, and this problem is at least as difficult as the well known distributed source coding problem [21]. Thus the conventional proof approach of characterizing separately the rate-distortion region, channel capacity region and the joint source-channel coding achievable distortion region, and then making comparison, does not yield the desired separation result. Next, we illustrate through this example the methodology that enables us to prove the optimality of source-channel separation for the DNJSCC problem.
Suppose there exists a length-n joint source-channel code that achieves the distortion triple (D 1,3 , D 1,4 , D 2,4 ). The key observation is the following simple fact. If we fix this joint source-channel code, then the channel input for any given channel, for example X n 1,3 , can be viewed as a super (block) source, independent and identically distributed across blocks; see Fig. 2. Therefore, we can encode a lengthn ′ sequence of such blocks using a "rate-distortion" code of rate per block slightly greater than I(X n 1,3 ; Y n 1,3 ), the codewords of which are generated using the distribution Y n 1,3 . It follows that with probability approaching one (as n ′ goes to infinity) we can find a Y nn ′ 1,3 codeword in the codebook that is jointly typical with a channel input sequence X nn ′ 1,3 , (i.e., a length-n ′ vector of the super source samples), for sufficiently large n ′ . This lossy source code essentially simulates the channel output over n ′ length-n blocks, and only the codeword index needs to be known at node 3 to reconstruct Y nn ′ 1,3 . As such, this digital codeword index can be simply sent across this channel using any good channel code, and the original joint source-channel decoding function can be performed on this simulated channel output, which eventually (asymptotically) achieves the same distortion as the original code. It is easy to see that since I(X n 1,3 ; Y n 1,3 ) ≤ nC 1,3 , where C 1,3 is the channel capacity of the channel between node 1 and node 3, this rate-distortion codeword index is expected to be reliably transmitted on this channel. Replacing all the channel outputs with such simulated outputs in this problem results in a new scheme. In this "new" coding scheme, the codeword indices of these "rate-distortion" codes are the only informational interface between the source coding component and the channel coding component, and this is a separation-based scheme which asymptotically achieves the same distortions (D 1,3 , D 1,4 , D 2,4 ) originally achieved by the joint coding scheme. In other words, any distortions that are achievable by joint coding scheme can be achieved by a separation-based scheme.
The above observation largely reflects the intuition behind the optimality proof of source-channel separation for the general DNJSCC problem, however, some technical details (besides the asymptotically diminishing quantities omitted in the above discussion) need to be addressed: the main difficulty is that when the network has relays or cycles, the super source argument given above does not apply since channel usage constraints prevent coding over long super-channel blocks directly. The proof given Section IV will resolve this difficulty through an intricate arrangement of channel simulation.

B. Examples for Joint Source-Channel Multiple Unicast with Distortions
Consider the problem depicted in Fig. 3, where the sources S 1 , S 2 and S 3 are mutually independent; here the interference channel is more generally given by the transition probability P (Y 3 , Y 4 |X 1 , X 2 ), where X 1 , X 2 are the channel inputs by node 1 and node 2, respectively, and Y 3 , Y 4 are the channel outputs at Fig. 3. Transmitting mutually independent S1, S2, S3 on an interference channel. 6 4. Transmitting mutually independent S1, S2, S3 on an interference channel to multiple destinations, i.e., source S1 is required at both destination node 3 and node 4. node 3 and node 4, respectively.
Since the capacity region of interference channel is unknown, it is impossible to explicitly characterize (in a single-letter manner) the achievable distortion region of the separation approach. However, suppose for the problem in Fig. 3, a distortion triple (D 1 , D 2 , D 3 ) is achievable using some joint source-channel code of length-n. The conventional rate-distortion theorem [38] dictates that we must have is the rate-distortion function of source S i . The key is now the following simple fact, which is different from that discussed for the DNJSCC problem: if we fix this particular source-channel code, then the transition probability of P (Ŝ n 1 ,Ŝ n 2 ,Ŝ n 3 |S n 1 , S n 2 , S n 3 ) can be viewed as that of an alternative super interference channel with three users. On this channel, the individual mutual information guarantee I(S n i ;Ŝ n i ) ≥ nR i (D i ) holds for i = 1, 2, 3, due to the conventional rate-distortion theorem. Thus intuitively, this super interference channel should be able to support a rate triple of (nR 1 (D 1 ), nR 2 (D 2 ), nR 3 (D 3 )) per super-block channel use (or per n original channel uses) by a digital code. Now a good digital channel code on this super interference channel can be used to transmit a digital rate-distortion source code for the source S 1 , S 2 and S 3 , respectively. This is indeed a separation-based scheme, and it can achieve the distortion pair (D 1 , D 2 , D 3 ) asymptotically. In other words, any achievable distortion triple (D 1 , D 2 , D 3 ) can be achieved by the separation approach.
In order to show that the super-interference channel can indeed asymptotically support the rate triple (nR 1 (D 1 ), nR 2 (D 2 ), nR 3 (D 3 )), we essentially need to construct (random) codes over large super-channel blocks, and prove that the error probability can be made small, just as in conventional channels. The proof in Section V follows this approach and makes the above intuitive argument more rigorous.

C. Examples for Joint Source-Channel Multiple Multicast with Distortions
Consider the problem depicted in Fig. 4, which is only slightly different from that in Fig. 3 in that source S 1 is to be reconstructed at both node 3 and node 4, denoted asŜ 1,3 andŜ 1,4 , respectively; the reconstruction of source S 3 at node 3 is denoted 4 as S 3,3 and the reconstruction of source S 2 at node 4 is denoted as S 2,4 . Taking a similar view as in the previous example, the abstracted channel now has transition probability P (Ŝ n 1,3 ,Ŝ n 1,4 ,Ŝ n 2,4 ,Ŝ n 3,3 |S n 1 , S n 2 , S n 3 ). However, the mutual information bounds by the conventional rate-distortion theorem cannot be directly used as in the previous case. A moment of thought should convince the readers that the broadcast nature of the marginal transition probability P (Ŝ n 1,3 ,Ŝ n 1,4 |S n 1 ) is the culprit, and some additional coding component is needed.
A natural separation architecture is to use a successive refinement [11] source code to produce descriptions satisfying the distortion requirements for each source and couple it to a superposition broadcast code [38] to deliver reliably these messages in the degraded message set [13]. More precisely, in the example of Fig.  4, assume without loss of generality that the distortion for source S 1 at node 3 is greater than that at node 4. We shall use a successive refinement code for S 1 to produce messages (W 1,1 , W 1,2 ) such that W 1,1 is to be delivered to node 3 and both (W 1,1 , W 1,2 ) are to be delivered to node 4. Node 1 also produces a message W 3,1 to encode source S 3 , and node 2 produces a message W 2,1 to encode source S 2 . The messages (W 1,1 , W 3,1 ) need to be reliably transmitted to node 3, and the messages (W 1,1 , W 1,2 , W 2,1 ) to node 4.
Let us for the moment isolate source S 1 and focus on the super block broadcast channel P (Ŝ n 1,3 ,Ŝ n 1,4 |S n 1 ) with the messages (W 1,1 , W 1,2 ), since it is the main difficulty in generalizing the proof approach for JSCMUD. We will introduce an auxiliary random variable (in general more than one auxiliary random variable is needed), and show that this broadcast channel can support a certain rate pair for the degraded message set broadcast [13], parametrized by this newly-introduced random variable. The same probability distribution of this auxiliary random variable is also used to construct successive refinement source code for S 1 . However, the afore-mentioned channel coding rates for degraded message set broadcast are in fact insufficient to support this successive refinement source code; nevertheless, the shortfall in the rates can be upper-bounded by comparing the broadcast channel coding rates and the successive refinement source coding rates, both of which are parametrized by this afore-introduced auxiliary random variable. This upper bound implies the approximate optimality of source-channel separation in JSCMMD.

D. Remarks on the Separation Schemes
One may argue that the schemes described above for the given examples are not really based on source-channel separation, because in the example for DNJSCC, the source codes embed in themselves the original joint source-channel codes, and thus these source codes are designed with the knowledge of the channel statistics. Similarly, in the examples for JSCMUD and JSCMMD, the channel codes also embed in themselves the original joint source-channel codes, and thus they are designed with the knowledge of the source statistics. Following this argument, it cannot be claimed that in these scenarios source-channel separation is optimal (or approximately optimal). This is, however, a rather subtle misconception.
Indeed in a scheme based on source-channel separation, the source code should not rely on the channel statistics, and the channel code should not rely on the source statistics. In fact, the separated source coding problem (i.e., charactering the rate-distortion region) is defined to be the original joint coding problem without the channel statistics, and the separated channel coding problem (i.e., characterizing the capacity region) is defined to be the original joint source channel coding problem without the source statistics; moreover, the optimality of source-channel separation can be defined (in a manner similar to Shannon's original work [1]) as when the source coding rate-distortion region coupled with the channel coding capacity region is the same as the joint coding achievable distortion region 5 , and this is precisely the kind of results we shall establish in this work.
Without more precise mathematical definitions, it may be difficult to convince the readers that the arguments given in the previous sub-sections indeed show the optimality of source-channel separation. Nevertheless, here we shall provide an informal explanation in the context of the example in Fig. 3. Note that when each source in Fig. 3 is replaced by a message, we are left with an interference channel (with a common message between node 1 and node 2). The capacity region of this channel is unknown, and the question whether the capacity-achieving codes for this interference channel depends on any source statistics is not even relevant, because there exists no source in this new channel coding problem. In the previous discussion we have essentially shown that if for a set of sources is achievable in the joint coding setting, then the rate triple (r 1 , r 2 , is also achievable on this interference channel in the pure channel coding setting. Though the channel code constructed in the previous sub-section relies on the source statistics, the statement that "the rate triple (r 1 , r 2 , r 3 ) is achievable on this interference channel" does not depend on any source, and the newly constructed channel code can be understood as merely a tool to show this statement is true. If the rate triple (r 1 , r 2 , r 3 ) is achievable on this interference channel, then in the joint coding setting, we can also use other capacity achieving channel codes (not related to the original source statistics) to send the individual rate-distortion codeword index for each source S i , which results in a separation scheme. Conversely, the channel code constructed in the previous section can also be used to send rate-distortion codes for any other sources, not necessarily the original sources, and this is also an apparent separation scheme. At this point, it is clear that we can indeed conclude source-channel separation is optimal in this setting. In Sections IV, V and VI, the formal proofs follow a similar line of argument in a more rigorous manner.

III. NOTATION AND DEFINITIONS
In this section, we provide the notation and define the codes in consideration. The notation would become rather unwieldy if a unified framework were used for all the problems treated in this work. We therefore forgo this ambitious goal and define the problems separately; however, when convenient, the notation will be kept consistent among them. We focus on the problems with finite-alphabet discrete sources, finite-alphabet discrete channels and bounded distortion measures, unless noted otherwise explicitly.

A. Definitions for the Distributed Network Joint Source-Channel Coding Problem
For this case, the network with a total of N nodes can be conveniently written as a directed graph G = (V, E), where V = {1, 2, . . . , N} I N is the set of nodes, and E is the set of edges between any two nodes; from here on, for any integer M, we use I M to denote the set {1, 2, . . . , M}. Each edge e = (i, j) ∈ E is associated with a discrete memoryless channel, whose transition probability is given as P (Y i,j |X i,j ) with input alphabet X i,j and output alphabet Y i,j ; these channels are assumed to be synchronized. Each node i has a discrete memoryless source S i , distributed in the alphabet S i , and the collection of the sources are distributed according to the joint distribution P (S 1 , S 2 , . . . , S N ) at each time instance. For simplicity, we are inherently assuming these sources are synchronized, and thus the notation P (S 1 , S 2 , . . . , S N ) is meaningful. A length-n vector of a source S i is written as S n i , and the t-th symbol in this vector is written as S i (t); i.e., (2), . . . , S i (n)). Similar notation is also used for other random variables. We use upper case for random variables, and lower case for their realizations. For any set S, we write the r-th order product set as S r .
For each source, a distortion measure is defined in a general manner as d : notationally, we may write the set of sources that node j is interested in as T j . Next we define the class of codes being considered for the distributed network source coding problem, which are conventional block codes.
Definition 1: An (m, n, {d k,j , k ∈ T j }) distributed network joint source-channel code on a joint sourcechannel network (V, E, {T j , j ∈ I N }, P (S 1 , S 2 , . . . , S N ), (i,j)∈E P (Y i,j |X i,j )) consists of the following components: • At each transmitter node i, for each j such that (i, j) ∈ E, an encoding function for time instance t • At each receiver node j, for each source k ∈ T j , a decoding function ψ k,j : The encoding and decoding functions induce the distortions whereŜ k,j is the reconstruction of source S k at node j.
Here m is the source block length and n is the channel block length, which imply that there is a sourcechannel bandwidth mismatch factor of κ = n/m (channel uses per source sample). Note that if a node is not interested in a certain source, the distortion of the reconstruction at this node can simply be assumed to be large. Thus we can write a distortion matrix without loss of generality, whose element d k,j is the distortion associated with the reconstruction of source S k at node j. Clearly, without loss of generality 6 , we can let the element d i,i = 0 and simply define d i,j = d max is the distortion achievable at rate zero for source S i . With this in mind, the region of achievable distortion matrix can be defined as follows.
Definition 2: A distortion matrix D is achievable for distributed network joint source-channel coding with bandwidth mismatch factor κ on a joint source-channel network , if for any ǫ > 0 and sufficiently large m, there exist an integer n ≤ κm and an (m, n, {d k,j , k ∈ T j }) distributed network joint source-channel code, such that The collection of all such distortion matrices is the distributed network joint source-channel coding achievable distortion region, denoted as D dis .
To discuss source-channel separation, it is important to clarify the individual source code and channel code used in the separation-based approach. To this end, we essentially need to define the pure source coding problem and the pure channel coding problem. The channel coding problem in the DNJSCC problem is simply the point-to-point channel capacity problem, and the codes used are naturally block channel codes. The source coding problem is more complex: intuitively speaking, it is the original problem when the noisy channels are replaced by noise-free bit-pipes. However, this statement needs to be made more precise because although the "bit-pipe" channels lead to a more intuitive understanding, in a network setting, we also need to specify the timing, and the causality relation of all the channel inputs and outputs; moreover, when the rates of the channels are not integers, the concept of "bit-pipe" channel is not easily defined, and this may cause further confusion. Our definition of the pure source coding problem given below naturally eliminates such confusions. It is important to note that the definition of the block source codes on this network needs to incorporate the interactive communication aspect carefully.
network source code with a total of l sessions on a source communication network (V, E, {T j , j ∈ I N }, P (S 1 , S 2 , . . . , S N )) consists of the following components: • At each (transmitter) node i, for each j such that (i, j) ∈ E, an encoding function for transmission session t = 1, 2, . . . , l,φ where L i,j and L k,i 's are positive integers.
• At each receiver node j, for each source k ∈ T j , a decoding functioñ ψ k,j : The encoding and decoding functions induce the distortions where againŜ k,j is the reconstruction of source S k at node j.
, if for any ǫ > 0, there exists an integer l, such that for any sufficiently large m, there exists an (m, l, The collection of distortion matrix D for which the rate-distortion-matrix tuple Roughly speaking, 1 m log L i,j is the rate of "noise-free bit-pipe channel" on edge e = (i, j) per source symbol in each session. Each session has the same rate in this source coding problem, and the separation result we present will show that this additional requirement does not cause any loss of optimality. The above definition is given in the traditional block source coding framework, and there is no need to introduce the concept of "noise-free bit-pipe channels", which eliminates any possible confusions accompanied with it. In the above source code, there are a total of l sessions of coding which generate code indices at node j ∈ I N ; at the end of each session, the index w j,k ∈ I L j,k in this session becomes available at destination node k, and thus can be used by node k in the next coding session. In other words, the encoding functions need to observe the causality constraints on the session level on this network, by allowing the coding operation at a node to utilize only the source at this node and all previous session information from its incoming edges.
With the above definitions, it is clear that we can combine the source codes together with the capacityachieving channel codes for each channel on the original communication network. More precisely, we can define the achievable distortion region using such a separation approach as where C i,j is the channel capacity between node i and node j, and we sometimes also write it as C e with any e = (i, j) ∈ E. It is straightforward to see that The separation approach we take is indeed in the classical sense, since not only the source codes and the channel codes are defined separately, the digital codeword indices are the only information interface between them during encoding and decoding.

B. Definitions for Joint Source-Channel Multiple Unicast and Multiple Multicast with Distortions
For this case, there are a total of M mutually independent discrete memoryless sources, denoted as S i , distributed in the alphabet S i according to some distribution P (S i ), i = 1, 2, . . . , M; note that the index i here is not related to the index of the node, which is the case for the distributed network source coding problem given in the last section. For notational simplicity, we shall assume all the sources are synchronized. The distortion measures are defined similarly as in the last subsection; here we do not allow the existence of multiple distortion measures for the same source, or distortion measures defined on the functions of more than one source.
Let the number of nodes be N. For the JSCMUD and JSCMMD problem, the graph theoretical notation is not suitable, since multiuser communication channels with broadcast and multiple access signal interactions are involved. For notational simplicity, we treat the overall communication network as a single channel, with inputs (X 1 , X 2 , . . . , X N ) over the alphabets X 1 × X 2 × . . . × X N and outputs (Y 1 , Y 2 , . . . , Y N ) over the alphabets Y 1 ×Y 2 ×. . .×Y N , and transition probability given by P (Y N 1 |X N 1 ); here X i and Y i are the channel input and output at node i, respectively. This model naturally includes feedback, and we have inherently assumed the channels are synchronized by using this notation. Note that this general channel model includes the case that the overall network consists of many independent individual multiuser channels, and moreover, some of inputs and outputs can simply be set as constant if the particular node does not send or receive over the channel. For simplicity we shall also assume the channel is memoryless.
Each source S i can be present at several nodes, and for each node j ∈ I N , we denote the sources present at node j as S j . The receiver demands are defined as follows: • Joint source-channel multiple unicast with distortion: each source is to be reconstructed (with or without distortion) at a single destination. Again denote for receiver node j the set of the sources it is interested in as T j , then we have T j ∩ T k = ∅ for any j = k.
• Joint source-channel multiple multicast with distortion: each source is to be reconstructed (with or without distortions) at multiple destinations, i.e., it is possible that T j ∩ T k = ∅.
Next we define the class of codes being considered in this work, which are again block codes.
consists of the following components: • At each transmitter node j, an encoding function for (time) index t • At each receiver node j, for each source k ∈ T j , a decoding function The encoding and decoding function induces the distortion whereŜ k (t) is the reconstruction of source S k at a node j such that k ∈ T j . Next we need to define the source codes and the channel codes extracted for the separation-based approach. For the JSCMUD problem, the source codes are conventional lossy source codes. In the channel coding problem we consider, each source S i is replaced with a message W i of cardinality L i with a uniform distribution; moreover, these messages are mutually independent. The precise channel code definition is as follows.
Definition 7: An (n, L 1 , L 2 , . . . , L M , P err ) multiple unicast channel code on a communication network consists of the following components: • At each transmitter node j, an encoding function for (time) index t φ (t) j : • At each receiver node j, for each message W k where k ∈ T j , a decoding functioñ Denote the decoded message asŴ i at node j where i ∈ T j , the encoding and decoding functions induce the average decoding error probability Definition 8: A rate vector (R 1 , R 2 , . . . , R M ) is achievable for multiple unicast channel coding on a communication network ({S j , j ∈ I N }, {T j , j ∈ I N }, P (Y N 1 |X N 1 )), if for any ǫ > 0 and sufficiently large n, there exists an (n, L 1 , L 2 , . . . , L M , ǫ) multiple unicast channel code, such that R i ≤ 1 n log L i + ǫ, i = 1, 2, . . . , M. The collection of such achievable rate vectors is the achievable capacity region of the network, denoted as C uni .
Using conventional rate-distortion codes on each source and then combining it with the above defined multiple unicast channel codes as the coding scheme, an achievable distortion region is immediate, which will be denoted as D * uni . More precisely, we can write where D i (·) is the distortion-rate function of the source S i . In the case of JSCMMD, a source is to be reconstructed with possibly different distortions at multiple destinations. The JSCMMD codes are defined in the same manner as in the case of JSCMUD, and thus the detailed definitions are omitted here. The achievable distortion matrix and the achievable distortion region D mul can also be defined accordingly.
The source-channel separation scheme for JSCMMD is slightly more involved. Consider first source S i , and assume it is to be reconstructed in a lossy manner at nodes in the set Q i = {j : i ∈ T j }. The source codes we shall consider are successive refinement codes [11], and source S i is encoded in |Q i | stages, where the operator | · | denotes the cardinality of a set. For the channel codes in the separation approach, we shall consider a generalized version of the two-user degraded message set problem [13]. More precisely, in the given source communication network, let us fix an order O i for the elements in the set Q i for each i = 1, 2, . . . , M. The source S i is replaced with a total of |Q i | messages, denoted as W i,j , whose rate is The k-th node in this given order O i is required to reconstruct the first k messages, W i,j , j = 1, 2, . . . , k. We can now define the achievable  (3, 4).
Clearly, the degraded message set scenario naturally sets the stage for the successive refinement source codes, and by combining these two components, we arrive at an achievable distortion region using the separation appraoch for a given set of orders O. We shall denote this achievable region as D * mul ( O).

IV. OPTIMALITY OF SEPARATION FOR DISTRIBUTED NETWORK JOINT SOURCE-CHANNEL CODING
Our first main result is the following theorem, which formally states that the joint coding achievable distortion region is the same as separation coding achievable distortion region in the distributed network joint source-channel coding problem.
Theorem 1: For any discrete and memoryless distributed network joint source-channel coding problem (with orthogonal communication channels), we have D dis = D * dis . The following uniform Markov lemma is needed in the proof of this theorem, which can be found in [41]- [43]. This lemma is alternative version of the well known Markov lemma [21], and it has been used more recently in [44]. We rewrite it below using notation more convenient to us 8 .
Lemma 1: Let X ↔ Y ↔ Z be a Markov string in finite alphabets. For any fixed strongly jointly typical sequence pair (x n , y n ), let Z n be chosen uniformly at random from the set which consists of all sequences that are strongly typical with y n . Let Q(·) be the probability measure induced by this random choice. Then lim n→∞ Q((x n , y n , Z n ) are not strongly jointly typical) = 0, and the convergence is uniform over the set of strongly jointly typical (x n , y n ) sequence pairs.

Proof of Theorem 1:
We first show that D dis ⊇ D * dis . Consider an l-session length-m distributed network source code with rates {R i,j , (i, j) ∈ E}. With the bandwidth mismatch factor κ, we have a total of κm channel uses, and we shall partition them into l channel sessions, each with κm l channel uses; for simplicity, we shall assume κm l is an integer. Thus the channel on edge (i, j) in each session can support a message of cardinality up to exp( κm l C i,j ) , with vanishing error probability, where we assume natural logarithm for mutual information definition. Each session of the source code has a message output of cardinality L i,j = exp( m l R i,j ) . Thus omitting the rounding issue, as long as exp( m l R i,j ) < exp( κm l C i,j ), i.e., R i,j < κC i,j , we can use the digital channel codes to transmit the source codes reliably (with vanishing error probability). Since the sources are discrete and thus finite, it follows that indeed, Because the achievable distortion region D dis is a closed set and the distortion-matrix-rate function D(R i,j ) is continuous, the condition R i,j < κC i,j can be replaced by R i,j ≤ κC i,j and the rounding issues can be safely ignored, resulting in the achievable region D * dis . Thus we have D dis ⊇ D * dis . Next we focus on the direction D dis ⊆ D * dis . For an achievable distortion matrix D, there exists a sequence of distributed network joint source-channel codes approaching it. In other words, for any ǫ > 0, there exists an (m, n, {D k,j + ǫ, k ∈ T j }) distributed network joint source-channel code (see Definition 1 and Definition 2), where n ≤ κm. It is instructive to first examine the joint probability distribution induced by this particular code. Let X E (t) and Y E (t) denote the collection of channel inputs and outputs at time t; similarly we use S m V to denote the collection of all the source vectors in the network. At t = 1, X E (1) is a function of S m V , i.e., . We next show that if a distortion matrix D is achievable in the joint coding problem given by Definition 1 and Definition 2, which is denoted as È j , then the rate distortion matrix pair ({κC e }, D) is also achievable in the pure source coding problem given by Definition 3 and Definition 4, which is denoted as È s . For this purpose, we shall construct an n-session distributed network source code for È s that operates on a source sequence of length mn ′ . Definition 3 and Definition 4 are rather crucial in the discussion below, and the readers are encouraged to familiarize with them before proceeding.
We first partition the source sequence S mn ′ i , i = 1, 2, . . . , N, into n ′ disjoint block components, each of length m. The v-th block component of S mn ′ i is written as S m i v , i.e., To make this partition explicit, S mn ′ i is written in the sequel as S m, n ′ i .
For each (i, j) ∈ E and each session t = 1, 2, . . . , n, a source coding codebook C (i,j),l of size exp(n ′ (I(X i,j (t); Y i,j (t)) + δ)) is generated by choosing from the strongly typical set of the random variable Y i,j (t) uniformly at random with replacement. This codebook is revealed to both the encoder and decoder on edge (i, j) in the problem È s . Now consider encoding for session t = 1 at any given edge (i, j) ∈ E. We first apply the original joint source channel encoding function φ The outputs are then concatenated to produce a length-n ′ vector X For is strongly typical, we then find a codeword y n ′ i,j (1) in C (i,j),1 such that x n ′ i,j (1) and y n ′ i,j (1) are strongly jointly typical with respect to P (X i,j (1), Y i,j (1)); if there does not exist such a codeword, an error is declared. Denote the index of this chosen y n ′ i,j (1) codeword in C (i,j),1 as w i,j (1); the v-th location in the vector y n ′ i,j (1) is written as y i,j (1, v ). For notational simplicity, we shall also write The new encoding functionsφ (1) i,j for the distributed network source coding problem (i.e., È s ) are given bỹ We continue to construct the new code for the source coding problem È s . In the t-th session, for any given edge (i, j) ∈ E, the original joint source-channel encoding function φ (t) i,j is applied, and the outputs are concatenated (see Fig. 5), i.e., Then for any (i, j) ∈ E, if x n ′ i,j (t) is strongly typical, find a codeword y n ′ i,j (t) in C (i,j),t such that x n ′ i,j (t) and y n ′ i,j (t) are strongly jointly typical with respect to P (X i,j (t), Y i,j (t)); if there does not exist such a codeword, an error is declared. The index of the chosen codeword y n ′ i,j (t) in C (i,j),t is denoted as w i,j (t), and thus the new encoding functionsφ (t) i,j for the distributed network source coding problem (i.e., È s ) are given byφ After n sessions of encoding, at node j ∈ V, we apply the originally joint source-channel decoding function ψ k,j to reconstruct the v-th block component of source s which are then concatenated to formŝ m, n ′ k,j , i.e. the length-mn ′ reconstruction of source k at node j. Thus the new decoding functionsψ k,j for the distributed network source coding problem (i.e., È s ) are given bỹ There are three kinds of error events in session-t: does not occur, then for all (i, j) ∈ E, the sequence x n ′ i,j (t) is strongly typical.
• For an edge (i, j) ∈ E, given x n ′ i,j (t) is strongly typical, there does not exist any codeword in C (i,j),t such that it is strongly jointly typical with x n ′ i,j (t), with respect to P (X i,j (t), Y i,j (t)); this event is denoted as E The overall error event is given as where we used S to denote the complement of set S, and E By the union bound, we have Next we show that Pr(E n ′ ) → 0 as n ′ → ∞. Pr E

It is clear that Pr(E
Since E t,(i,j) ) → 0 for any t and (i, j) ∈ E, by the properties of the strongly typical sequences ( [38], Lemma 13.6.2), and the fact that the number of codewords in C (i,j),t is exp(n ′ (I(X i,j (t); Y i,j (t)) + δ)).
To bound the third summation in (23), let us fix an arbitrary order for the edges in the set E, and write it as e 1 , e 2 , . . . , e |E| . Define E are not strongly jointly typical. We can then rewrite where E is a Markov string. Invoking Lemma 1 gives that Pr(E (3) * t,k ) → 0, for any t and k, as n ′ → ∞. There are a total of n terms in the first summation of (23), a total of n|E| terms in the second summation, and a total of n|E| terms in the third summation. Since n and |E| are fixed in the above construction, and each term can be made arbitrarily small by making n ′ sufficiently large, it is seen that Pr(E n ′ ) → 0 as n ′ → ∞. This implies that the sequences (s m, n ′ V , x n, n ′ E , y n, n ′ E ) are strongly jointly typical with respect to the original distribution P (S m V , X n E , Y n E ) with probability approaching one as n ′ → ∞. This further implies that s m, n ′ k andŝ m, n ′ k,j are strongly jointly typical with respect to P (S m k ,Ŝ m k,j ), and the new code induces a distortion D k,j + ǫ + δ ′ , where δ ′ → 0 as n ′ → ∞.
It remains to analyze the rates of this digital scheme, i.e., the cardinalities of indices delivered during each session for the problem È s . It is clear that for each link e = (i, j) ∈ E, for each session t, we have I(X e (t); Y e (t)) ≤ C e , t = 1, 2, . . . , n, where C e is the capacity of the channel on edge e, due to the conventional channel coding theorem. Thus it is seen that the cardinality of above digital codes for each session associated with any given link e is bounded as exp(n ′ (I(X e (t); Y e (t)) + δ)) ≤ exp(n ′ (C e + δ)), t = 1, 2, . . . , n. It follows that the following rate is achievable in the problem È s R e = n mn ′ log exp(n ′ (C e + δ)) ≤ κ(C e + δ), according to Definition 4. Thus we have shown that this newly constructed code can operate at the ratedistortion-matrix tuple ({R e = κ(C e + δ)}, D + ǫ + δ ′ ) for the problem È s , where δ and δ ′ can be made arbitrarily small by letting n ′ → ∞. Since the achievable rate-distortion-matrix region for È s is a closed set, the asymptotically small terms δ and δ ′ can be safely ignored, and it follows that the rate-distortion-matrix tuple ({R e = κC e }, D + ǫ) is achievable in the problem È s . Now since the distortion matrix D is achievable in the joint coding problem È j , for any ǫ > 0, there exists an (m, n, {D k,j +ǫ, k ∈ T j }) joint source-channel code, where n ≤ κm. It follows that ({R e = κC e }, D + ǫ) is an achievable rate-distortion-matrix tuple in the source coding problem È s for any ǫ > 0, and again since the achievable rate-distortion-matrix region for È s is a closed set, it is clear that ({R e = κC e }, D) is indeed achievable for È s . The proof can be completed for D dis ⊆ D * dis by applying (6).
Remark: In the proof, the original joint source-channel code length (m, n) and the number of super blocks n ′ need to be controlled carefully. To arrive at the conclusion, we essentially need to drive both of them to infinity, but at different rates. This consideration also applies in the proof for the JSCMUD problem in the next section.

V. OPTIMALITY OF SEPARATION FOR JOINT SOURCE-CHANNEL MULTIPLE UNICAST WITH DISTORTION
The main result of this section is the following theorem, which formally states that the joint coding achievable distortion region is the same as separation coding achievable distortion region in the JSCMUD problem.
Theorem 2: For discrete and memoryless joint source-channel multiple unicast with distortion, we have D uni = D * uni . Proof of Theorem 2: The direction D uni ⊇ D * uni is rather obvious, and thus we focus on the other direction D uni ⊆ D * uni . For any achievable distortion vector (D 1 , D 2 , . . . , D M ), there exists a sequence of JSCMUD codes to approach it. In other words, for any ǫ > 0, there exists an (m, n, D 1 +ǫ, D 2 +ǫ, . . . , D M + ǫ) JSCMUD code, where n ≤ κm (see Definition 5 and 6).
The sources and the above given block code induce a joint distribution and we view the second term as the transition probability of a block-level interference channel, which has input alphabets S m 1 × S m 2 × . . . × S m M , and output alphabetsŜ m 1 ×Ŝ m 2 × . . . ×Ŝ m M . Moreover, by the conventional rate-distortion theorem [38], it is clear that where R i (·) is the rate-distortion function for source S i . This super interference channel operates in the same manner as a memoryless interference channel, however it operates on a block level (S m 1 , S m 2 , . . . , S m M ) → (Ŝ m 1 ,Ŝ m 2 , . . . ,Ŝ m M ), instead of on a single time instance level on the original channel (X 1 , X 2 , · · · , X N ) → (Y 1 , Y 2 , · · · , Y N ).
Next we show that if a distortion vector (D 1 , D 2 , . . . , D M ) is achievable on the joint coding problem defined in Definition 5 and Definition 6, which we denoted again as È j , then the rate vector is achievable on the pure channel coding problem defined in Definition 7 and Definition 8, which we denoted as È c . For this purpose, we shall construct a multiple unicast channel code for È c using the afore-mentioned (m, n, D 1 + ǫ, D 2 + ǫ, . . . , D M + ǫ) JSCMUD code for È j .
The coding scheme for È c can be formally described as follows. For each source S i , exp(mn ′ (R i (D i +ǫ)− δ)) codewords of length-(mn ′ ) are generated independently, accordingly to the mn ′ -th product distribution of P (S i ); denote this codebook as C i . The codebooks are revealed to all the nodes.
To encode for È c , given a message w i , we shall choose the w i -th codeword s mn ′ i (w i ) in the C i codebook generated above. Each codeword is partitioned into n ′ blocks of equal length, and let us denote the vth block as s m i (w i , v ); to emphasize this partition, we also write s mn ′  This results in a set of reconstruction sequences (ŝ m 1 v ,ŝ m 2 v , . . . ,ŝ m M v ). At the end of n ′ blocks, we concatenate the reconstruction for each source block asŝ mn ′ i =ŝ m, n ′ i = (ŝ m i 1 ,Ŝ m i 2 , . . . ,Ŝ m i n ′ ). Mathematically, let the original joint source-channel encoding and decoding function at node j be φ (t) j , and ψ k,j , respectively. Similarly as the notation of s m i (w i , v ), the v-th length-n block of y nn ′ i is written as y n i v , and the first t symbols of the block y n i v is written as y t i v . Then the new channel code encoding functionφ The reconstructions are simplŷ We proceed to construct the multiple unicast channel code decoder (for problem È c ). At node j, for which k ∈ S j , find a unique codeword in the codebook C k such that it is (weakly) jointly typical [38] witĥ s mn ′ k according to the distribution P (S m k ,Ŝ m k ), i.e., the marginal from (30). If there is a unique codeword, then the corresponding message w * k is declared; otherwise an error is declared. There are three kinds of errors in this new scheme: ) are not jointly typical with respect to (30); denote this event as E (2) .
• For a given message w i , there is more than one codeword in C i that is jointly typical withŝ m, n ′ i (w i ), with respect to the marginal of (30); denote this event as E (3) i . The overall error probability can be bounded as where the inequality is by the union bound. Since all the codewords are generated according to P (S i )'s independently, by the basic properties of the jointly typical sequences ( 2), and the fact that the number of codewords in C i is exp(mn ′ (R i (D i + ǫ) − δ)). Since there are a total of M + 2 terms in (34), it is clear that Pr(E n ′ ) → 0 as n ′ → ∞.
By making n ′ large and thus δ small, it is clear that the rate tuple (R 1 (D 1 +ǫ), R 2 (D 2 +ǫ), . . . , R M (D M + ǫ)) ∈ C uni for any fixed ǫ > 0. Since the rate-distortion functions R i (·)'s are continuous, and the capacity region C uni is a closed set, it follows that (R 1 (D 1 ), R 2 (D 2 ), . . . , R M (D M )) ∈ C uni . Therefore we can conclude that (D 1 , D 2 , . . . , D M ) ∈ D * uni , by the definition of D * uni given in (13), and thus D uni ⊆ D * uni . This completes the proof.
Remark: When a source S i is present at multiple nodes, these nodes in fact cooperate to communicate to the destination. A source S i present at multiple nodes in the joint coding problem implies a common message W i available also at these nodes in the pure channel coding problem, and thus these nodes can cooperate to transmit this common message. This cooperation is implicit in the original JSCMUD code, but in the induced channel code it does not appear explicitly. Note that since our proof given above only relies on weak typicality, it can be extended straightforwardly to problems with more general (continuous) alphabets.

VI. APPROXIMATE OPTIMALITY OF SEPARATION FOR JOINT SOURCE-CHANNEL MULTIPLE MULTICAST WITH DISTORTION
In this section we examine the third scenario considered in this paper, i.e., the case where there could be multiple receivers interested in the same source, but at different distortion levels. We limit ourselves to a set of distortion measures often referred to as the "difference" distortion measures, since its properties play an important role in the proof. More precisely, the distortion measure d(·, ·) is given in the form of X = X , where X is an Abelian group with a proper addition operation; furthermore, i.e., the distortion mapping only depends on the difference between the two variables. In order to present our results, some additional definitions are quoted directly from [14]. For a random variable N in the alphabet X , the capacity of the additive noise channel X → X + N where X is also in the alphabet X , under a d(·) constraint is defined as The addition + is defined on the Abelian group of X , and it can be real addition, modulo addition or finite field addition where appropriate; ⊥ here stands for independence. The minimax (or worst noise) capacity is defined as C X (D) can be interpreted as the capacity at equilibrium in a mutual information jammer game, played over an additive-noise channel, in which both the expected noise and expected input are limited to within D in terms of d(·). Though for general difference distortion measures, the quantity C X (D) is a function of D, for some specific cases, considerable simplification is possible. For example, when the distortion is mean squared error, C X (D) is always 1/2 bit [14].
Our approximation result is in a genie-aided form, where additional communication links with bounded capacities are provided by a genie. We will show that a separation-based approach using the original communication network together with the additional genie-provided communication network can achieve any distortion matrix D that is achievable in the original communication network with arbitrary joint coding schemes. To quantify this genie-provided communication network, recall that the i-th row of an achievable distortion matrix D ∈ D mul corresponds to the distortions achieved for source S i at the destinations in the set Q i . It will become clear in the proof that if the reconstructions of a source S i at multiple destinations in the set Q i are required to be at the same distortion level a priori, then these destinations can be viewed as a single super-destination, and the problem can be reduced to a simpler one. Therefore, without loss of generality we shall assume the reconstructions of a source at multiple destinations are at different distortion levels.
The decreasing sequence of distortions for the elements on the i-th row thus specifies an order O i of the set Q i ; let O i (j) be the j-th element in the set of Q i according to the order O i . We require this genie-provided network to support degraded message set broadcast from source S i to the nodes in the set Q i for each i where |Q i | > 1. In other words, for each source S i such that |Q i | > 1, for each j ∈ I |Q i | , there is a common link of capacity R i,O i (j) per source sample 9 from S i to all the nodes O i (j), O i (j + 1), . . . , O i (|Q i |). These rate entries are collected and written together as the rate matrix R. Consider adding this genie-provided communication network on top of the original source communication network, and denote the achievable distortion using a separation approach of successive refinement coupled with superposition channel code on this joint communication network as D * * mul ( O, R). Example: Consider the example given in Fig. 4. The sets Q i 's are The orders when the distortion ofŜ 1,3 is larger thanŜ 1,4 are The rate matrix of the genie-provided communication network has the form where 3 at row-i and column-j means that the genie does not need to provide an additional communication capability from source S i to node j, thus R i,j is not defined. The new network consisting of the additional Fig. 6. The Example in Fig. 4 with the additional genie links, which are in drawn in dashed lines. The region D * * mul ( O, R) is the achievable distortion region using separation-based scheme on this joint network. genie communication network on top of the original source communication network is given in Fig. 6.
The following theorem is our first result on general network multicast.
Theorem 3: Let D be an achievable distortion matrix, for which O is the corresponding orders induced by D. For any random variable U i,j in the alphabet X i , j = 1, 2, . . . , |Q i |, such that where O i (j) is the j-th node index in the set of Q i according to the order O i , and V i,j 's are mutually independent such that d( , let the genie communication network support the rate matrix R O whose elements are Then we have D ∈ D * * mul ( O, R * ).

Remark: It is clear that
in the above theorem. This theorem in fact provides more than one approximation, one for each set of V i,j random variables, resulting in a rather powerful bounding tool. To find the tightest bound, we can optimize over these random variables under certain constraints depending on the achievable distortion matrix D.
Under certain distortion measures, significant simplifications can be made. The quadratic distortion measure is an important special case of difference distortion measures since it is used in many practical systems 10 . The main result of this section is given for this case, which shows that a separation-based scheme is approximately optimal, universally across all distortion values, for the quadratic distortion measure. Note that the sources need not be Gaussian.
Theorem 4: Let D be an achievable distortion matrix, for which O is the corresponding orders induced by D. Let the sources S i 's satisfy the condition that for all lettersŝ i ∈Ŝ i , (S i −ŝ i ) 2 < ∞. Let the genie communication network support the rate matrix R O whose elements are We have D ∈ D * * mul ( O, R * ) under the mean squared error distortion measure. In the simplest case where a single node broadcasts a Gaussian source to a set of receivers, this result essentially reduces to Corollary 1 given in [30] for the Gaussian source. The intuitive translation of the above result is that when a genie helps the separation-based scheme by providing half a bit information for each receiver, and at the same time, all the receivers with better quality reconstructions receive this information for free, then the genie-aided separation-based scheme is as good as the optimal ones. Theorem 4 implies that the total aggregate throughput 11 provided by the genie is 1 This depends on the demand structure and grows large in networks with many sources and when most sources are required to be reconstructed at many destinations. However, for any fixed network, the approximation in Theorem 4 holds regardless of the quality of the channel. As such, this result is more useful in the high resolution regime for large networks, when the genie-network becomes negligible compared to the original communication network. In networks with only a few sources, or when most sources are to be reconstructed at only a few destinations, the genie network aggregated throughput is not large, and the approximation is usually sufficiently accurate.
Next, we focus on the proof of Theorem 3, since Theorem 4 can be directly obtained by using Gaussian auxiliary random variables V 's in Theorem 3.
Proof of Theorem 3: To simplify the notation, let us first consider a single source S i ; we can assume for the time-being that the joint source-channel encoding procedure is still performed on other sources, and we shall return to this point at the end of the proof. Without loss of generality, we can assume the destination nodes of source S i are 1, 2, . . . , K, and moreover the distortions, which are achieved by this given source-channel joint code, are ordered as D i,1 ≥ D i,2 ≥ . . . ≥ D i,K . To simplify notation, we shall omit the index i in S i for the time-being. This will also imply that instead of the cumbersome notation for the distortions as Next we choose a set of auxiliary random variables as specified in the theorem. More precisely, we define the auxiliary random variables in the alphabet S such that, where V k 's are random variables in the alphabet S, which are independent of everything else. Furthermore the auxiliary random variables are chosen such that d(U k ) ≤ D k . For the moment this choice seems arbitrary, but we will link these auxiliary variables to the achievable distortions.
Consider a JSCMMD code which induces the distortion vector (D 1 , D 2 , . . . , D K ) for source S, whose reconstructions are denoted asŜ m 1 ,Ŝ m 2 , . . . ,Ŝ m K . We shall view the transition probability P (Ŝ m 1 ,Ŝ m 2 , . . . ,Ŝ m K |S m ), as a broadcast channel and denote it as P bc . We need the following lemma to proceed, whose proof will be given shortly. For simplicity, we shall ignore the asymptotically small quantities such as δ, ǫ in the previous section, which are inconsequential.
Lemma 2: On the broadcast channel P bc , the following degraded message set broadcast rates can be (asymptotically) supported Moreover, these rates can be achieved by a random superposition code [38] based on the joint distribution . Though this lemma is regarding the broadcast channel P bc , in a manner similar to the proof for general network unicast, we can in fact conclude that on the original network, when all the other encoders still perform the original joint source-channel encoding, the communication channel from source S to its destinations can support degraded message set broadcast rates (R c 1 , R c 2 , . . . , R c K ) per m source samples. This is because the broadcast channel P bc is simply the communication channel in the original network with certain additional operations on the block level.
Using this lemma, it is clear that together with the genie-provided communication network, we can send messages within the degraded message set from source S i to its destinations at rates per m-samples In other words, these degraded message set broadcast channel rates can be supported for pure channel coding purpose. Note that, however, if we use the distribution (S m +U m 1 , S m +U m 2 , . . . , S m +U m K ) to construct a successive refinement code [12], the rates (R is achievable using the separation approach in this genie-aided network, because we can simply use the codewords generated by distribution S m + U m k as the construction to achieve distortion d(U k ) ≤ D k . It remains to argue that if all the users simultaneously replace the original joint source-channel codes with the newly constructed channel codes, the rates that can be supported are still the same as above. This is indeed true, because in the superposition code in Lemma 2, we rely on the joint typicality on the block level when the channel input is of distribution S n . This however does not change if the other users replace the original joint source-channel codes also with their newly constructed channel codes, since the superposition channel codes constructed this way for all the broadcast channels indeed preserve joint typicality according to the distribution P (S m 1 , S m 2 , . . . , S m K ). This completes the proof with exception of Lemma 2.
To prove Lemma 2, we first give an auxiliary lemma.

Proof of Lemma 3:
We can write I(S m + U m 1 ;Ŝ m i , S m ) in two ways and where I(S m + U m 1 ;Ŝ m i |S m ) = I(U m 1 ;Ŝ m i |S m ) = 0, because of the construction of the auxiliary random variable U 1 ensures that U m 1 is independent of (Ŝ m i , S m ), as seen in (45). Thus we have where (a) follows again since U m 1 is independent of (Ŝ m i , S m ), and the last step follows the concavity of I(X; Y ) as a function of the marginal distribution. This proves (48) in Lemma 3.
Note further that for k = 2, 3, . . . , K, we have as well as It follows that Note that where (b) follows because of the Markov string S m + U m k−1 ↔ S m + U m k ↔ S m ↔Ŝ m i . This proves (49) in Lemma 3.

Furthermore, because of the Markov stringŜ
and it follows that This proves (50) in Lemma 3, and thus the proof is complete. Now we are ready to prove Lemma 2.

Proof of Lemma 2:
We shall use the distribution (S m +U m 1 , S m +U m 2 , . . . .S m +U m K−1 , S m ) to construct superposition broadcast channel code on the broadcast channel P bc for the degraded message set 12 . The rates (per length-m block) for these messages within the degraded message set are (asymptotically) We need to show that the chosen rates can indeed be supported on this broadcast channel with a degraded message set. Since this channel itself is not degraded, we have to show that the superposition coding scheme succeeds for all the receivers. To see this, observe that for the i-th receiver, we have by Lemma 3. It follows that where the last inequality is straightforward by noticing and thus we conclude the i-th receiver can decode the messages 1, 2, . . . , i. The K-th receiver does not pose any additional difficulty. Thus indeed the rates specified in (66)-(67) can be supported on this superbroadcast channel, and the proof is complete.

VII. CONCLUDING REMARKS
We considered the optimality of source-channel separation architecture in networks, and showed that the separation approach is optimal for the problems of distributed network joint source-channel coding and joint source-channel multiple unicast with distortion. Moreover, the separation approach is also approximately optimal for the problem of joint source-channel multiple multicast with distortion under certain distortion measures. The results in this work are obtained without explicit characterizations of the underlying regions. Such an approach of identifying properties without explicit individual component solutions is a valuable tool which may lead to further insights into network information theory problems. The source coding problem extracted from the distributed network source coding scenario implies that the interactive coding aspect needs to be carefully incorporated into this source coding problem, which suggests a distinct line of research direction into network source coding.
The requirement on the sources being independent in the general network unicast and multicast problem may seem rather stringent. However, in many practical situations the sources are indeed either independent or identical. Furthermore, the dependence structure among the sources can sometimes be approximated reasonably well by a model only allowing multiple independent or identical sources; one such example is in [45], where an approximate characterization for the rate-distortion region of the three source Gaussian distributed source coding problem was given. Thus our results on general network unicast and multicast may have implications in even broader settings.
For notational and conceptual simplicity, we made many assumptions which are not strictly necessary. The results can be straightforwardly extended to more general cases with some minimal efforts, the proofs of which are left to interested readers.
• Distributed network joint source-channel coding: The synchronization requirement among sources can be removed, i.e., the source bandwidths do not have to be the same throughout the whole network.
The multiple reconstructions of a source S i can be under different distortion measures; in fact the distortion measures defined can be defined on multiple sources, such as to reconstruct (S 1 − S 2 ). The optimality result can be also extended to lossless reconstruction under vanishing block error probability requirement, instead of zero distortion requirement 13 .
• Joint source-channel multiple unicast with distortion: The synchronization requirement among sources and channels can be removed and the memoryless requirement on the channel can be relaxed to channels with finite memory (see [40] for an outline). As mentioned, the restriction on the discrete alphabets can be relaxed to sources and channels with continuous alphabets, where the sources satisfy the "bounded expected distortion" condition. The condition that each source is to be reconstructed at one destination can be relaxed to some extent. More precisely, when each source is to be reconstructed at multiple destinations but at the exact same distortion under the same distortion measure, then the source-channel separation architecture is still optimal.
• Joint source-channel multiple multicast with distortion: Similar to the JSCMUD case, the synchronization, the memoryless channel, and the discrete alphabet requirement can be relaxed. The condition that each source is to be reconstructed under the same distortion measure can be relaxed to different distortion measures. In this case, the orders O among the reconstructions are not straightforward, however as we take all the possible order O, there is always one order that yield a valid approximation. If some of the reconstructions of a source S i are specified to have the same distortion a priori, then the approximation upper bound can be improved; particularly, when the reconstructions of each source are specified to all have the same distortion, then source-channel separation is optimal, which is essentially the generalization discussed above for the JSCMUD problem.
For DNJSCC in a communication network without any relay or feedback, the orthogonal channels do not need to be synchronized with each other, and the source-channel separation architecture is still optimal. We believe the optimality result holds in more general networks without the synchronization requirement, however the interleaving argument becomes exceedingly complex.
Our proof for DNJSCC relies on the (uniform) Markov lemma and thus applies only to discrete alphabets, however given the recent effort on extending the Markov lemma to abstract alphabets [46] (see also the generalized Markov Lemma to Gaussian sources in [47]), we believe it should be possible to extend our result on DNJSCC to the sources and channels in more general alphabets.
The result on JSCMMD is given in a genie-aided-communication-network form, and this may be less pleasing. In some cases, such a bound can be translated to multiplicative bounds on the difference between the separation scheme distortion region and joint coding scheme distortion region. In [30], we provide such multiplicative bounds for the Gaussian source broadcast problem; in fact, two kinds of multiplicative bounds were provided in [30], one is a direct translation of Theorem 4, and the other is a single constant bound which holds uniformly for all the components of the distortion tuples. The result in this work is presented in the current genie-aided form partly due to the abstract setting. For a more specific model in which bandwidths, power, and other resources are given, the genie-aided form can often be converted to other more explicit forms, such as the multiplicative distortion bound or a genie-aided-resource form; this is an interesting future research direction.
One fascinating aspect of our results is the difference between the separation in the DNJSCC problem and that in the JSCMUD problem. From a philosophical point of view, in the point-to-point setting, the source and channel are specified by their statistical behaviors alone; however in the network setting, the new network components of the connectivity structure among nodes and the source-demand coding requirements are introduced. Our result in DNJSCC treats the source statistics and these network components as a whole, and treats the channel statistics as the other, resulting in the separation between a complex network source coding problem and multiple conventional point-to-point channel coding problems. In contrast, the result in JSCMUD treats the channel statistics and the network components as a whole, and the source statistics as the other, resulting in the separation between a complex network channel coding problem and multiple conventional point-to-point source coding problems. These separations are not the only possibility, and one can choose to separate in a different manner. Indeed, the work of Han [25] suggests for lossless coding over network with orthogonal links without feedback, the joint coding problem can be separated without loss of optimality into a moderately complex network source coding problem (Slepian-Wolf coding) and a complex network channel coding problem. Thus the problem of source-channel separation is by no means solved, and it calls for further investigation.