Source-channel separation in networks


One of the important architectural insights from information theory is the Shannon source-channel separation theorem. For point-to-point channels, the separation theorem shows that one can compress a source separately and have a digital interface with the noisy channel coding; and that such an architecture is (asypmtotically in block size) optimal. Therefore the importance of this is that one can 'layer' the architecture by separating the data compression into bits and the 'physical layer' of coding for noise. The optimality of this attractive architecture is known to break down in networks, for example for broadcast channels or multiple access channels. Nonetheless, this architecture is the basis for network layering in many of the current network architectures. Therefore, we have been studying the 'cost' of separation, that is, how much do we lose through separation. We have also studied special situations where one can demonstrate explicit optimal (hybrid) source-channel coding strategies.

For lossy source coding in general communication networks we have shown that the separation approach is optimal in two general scenarios, and is approximately optimal in a third scenario. These results are shown without explicitly characterizing the achievable distortions, or characterizing the rate-distortion regions of a separation approach. Such implicit characterizations of properties (first demonstrated in a related problem by Koetter, Effros and Medard, 2009) could provide a new tool to gain insight into network information theory problems.

The first general scenario, where we demonstrate optimality of separation, is when 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. For discrete networks, this result is a generalization of the result of Koetter, Effros and Medard (2009) for message transmission over noisy graphs, where they demonstrated a separation of network coding and channel coding. In our problem, the extracted pure network source-coding problem, due to the network connectivity, reveals the importance of interaction in such network data compression problems. We believe that this motivates a distinct research direction into interactive network source coding, which has not received a great deal of attention in literature.

The second general scenario, where we demonstrate optimality of separation, 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 finite-memory multi-user channels such as multiple access, broadcast, interference and relay channels.

The third general scenario, where we demonstrate approximate optimality of separation, is a relaxed version of the second scenario. Here we allow each independent source to be reconstructed at multiple destinations, with different distortion requirements. The network is still assumed to be general, i.e., including broadcast, multiple access interference and finite memory, but we restrict our attention to distortion metrics which are difference measures. For this restricted class of distortion measures we demonstrate that the loss of separation is bounded by a constant number of bits. For the important special case of quadratic distortion measures, this constant is shown to be universal across all required distortions, and is upper bounded by 0.5 bits per user requiring the same source.

The above work has been a generalization of previous work on separation over Gaussian broadcast channels, where approximate optimality of separation was established. For a special case of bi-variate Gaussian sources over Gaussian broadcast channels, we have established optimality of a hybrid analog-digital source-channel coding scheme, which we believe is the first such example.

Papers

  1. Download: tian_matched.pdf 
  2. Download: on Arxiv 
    Abstract:
    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 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.
  3. Abstract:
    We show that source-channel separation is approximately optimal for transmitting a Gaussian source over a bandwidth mismatched Gaussian channel, for quadratic distortion measures. Furthermore, we show that the results can be extended to general broadcast channels, and the performance of the source-channel separation based approach is also within the same constant multiplicative factors of the optimum.
  4. Abstract:
    We consider the problem of transmitting a Gaussian source on a slowly fading Gaussian channel, subject to the mean squared error distortion measure. We propose an efficient algorithm to compute the optimal expected distortion at the receiver in linear time O(M), when the total number of possible discrete fading states is M. We also provide a derivation of the optimal power allocation when the fading state is a continuum, using the classical variational method.
  5. Download: tcdsspcom10.pdf 
    Abstract:
    We consider the source-channel separation architecture for lossy source coding in communication networks. It is shown that the separation approach is optimal when the memoryless sources at source nodes are arbitrarily correlated, each of which is to be reconstructed at possibly multiple destinations within certain distortions, and the channels in this network are synchronized, orthogonal and memoryless (i.e., noisy graphs).
  6. C. Tian, S. N. Diggavi, and S. Shamai, "The achievable distortion region of bivariate Gaussian source on Gaussian broadcast channel," in Proc. Proc. of IEEE ISIT 2010, Austin, Texas, 2010, pp. 146-150.
  7. C. Tian, J. Chen, S. N. Diggavi, and S. Shamai, "Optimality and approximate optimality of source-channel separation in networks," in Proc. Proc. of IEEE ISIT 2010, Austin, Texas, 2010, pp. 495-499.
  8. Abstract:
    Lossless transmission of a set of correlated sources over a deterministic relay network is considered for two traffic requirements. In distributed multicast, the set of sources are to be delivered to a set of destinations. The source exchange requires all the nodes with access to sources to be able to reconstruct all other sources observed at other nodes. We develop achievable regions and outer bounds for both these situations. For linear deterministic networks, these bounds coincide, yielding a characterization.
  9. C. Tian, S. N. Diggavi, and S. Shamai, "An Approximate Characterization For the Gaussian Broadcasting Distortion Region," in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, 2009, pp. 2477-2481.
  10. C. Tian, A. Steiner, S. Shamai, and S. N. Diggavi, "Expected distortion for Gaussian source with broadcast transmission strategy over a fading channel," in Proc. IEEE Information Theory Workshop (ITW) Bergen, Norway, 2007, pp. 42-46.
  11. S. Dusad, S. N. Diggavi, and A. R. Calderbank, "Cross Layer Utility of Diversity Embedded Codes," in Proc. IEEE Conference on Information Sciences and Systems, Princeton, 2006.
    Note: invited paper