Aditya Ramamoorthy · IEEE Transactions on Information Theory · 2010
This paper considers the problem of transmitting multiple compressible sources over a network at minimum cost. The aim is to find the optimal rates at which the sources should be compressed and the network flows using which they should be transmitted so that the cost of the transmission is minimal. We consider networks with capacity constraints and linear cost functions. The problem is complicated by the fact that the description of the feasible rate region of distributed source coding problems typically has a number of constraints that is exponential in the number of sources. This renders general purpose solvers inefficient. We present a framework in which these problems can be solved efficiently by exploiting the structure of the feasible rate regions coupled with dual decomposition and optimization techniques such as the subgradient method and the proximal bundle method.
Cited by 26
Guillemot, C., Roumy, Aline, Toto-Zarasoa, Velotiaray · Zenodo (CERN European Organization for Nuclear Research) · 2010
Publication in the conference proceedings of EUSIPCO, Aalborg, Denmark, 2010
Cited by 0Open access
Farhad Shirani, Aria G. Sahebi, S. Sandeep Pradhan · 2013
We introduce a scheme for the binary one-help-one distributed source coding problem using two layers of codes. The primary code is of constant finite block-length and the secondary code has a block-length approaching infinity. The achievable rate-distortion region for this scheme is derived for the binary one-help-one problem. It is shown that the scheme achieves the common component rate-distortion region in the case when the sources have a common component, while if a common component is not present (i.e. replaced with highly correlated functions of the two inputs) it improves upon existing achievable bounds. We show that as the block-length of the primary code is increased, the transmission rate required in the scheme decreases, reaches its minimum at some finite value and then increases. This phenomenon is not typically seen in traditional schemes used in multi-terminal source coding.
Cited by 16
Yasutada Oohama · 2009
We consider the distributed source coding system for L correlated Gaussian remote sources X <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> , i = 1, 2,···, L, where X <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> , i = 1, 2, ·, L are L correlated Gaussian random variables. We deal with the case where each of L distributed encoders can not directly observe X <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> but its noisy version Y <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> = X <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> +N <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> . Here N <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> , i = 1,2,···, L are independent additive L Gaussian noises also independent of X <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> , i = 1, 2,···, L. On this coding system the determination problem of the rate distortion region remains open. In our previous works, we derived explicit outer and inner bounds of the rate distortion region and explicit sufficient condition for those two to match. In this paper we derive a stronger sufficient condition for the inner and outer bound to match. We further study the sum rate part of the rate distortion region when the correlation has some symmetrical property and derive a new lower bound of the sum rate part. We further derive a sufficient condition for this lower bound to be tight. The derived sufficient condition depends only on the correlation property of the sources and their observations.
Cited by 0
Hung-Tsai Wu, Wei-Ying Tsai, Wen‐Whei Chang · 2012
This paper describes the design and implementation of an ECG signal monitoring system that is compatible with existing mobile telecommunications networks. First, a two-dimensional ECG signal compression scheme is presented using the distributed source coding (DSC). Also proposed is a modified BCJR algorithm which further enhances the DSC decoding by exploiting the symbol-level a priori information. Finally, we implement a novel integrated system comprising a mobile telephone, with sensors for patient monitoring, and a remote receiver linked by cellular networks. The system, when fully developed, will become powerful aids to monitoring a patient for mobile telemedicine and for emergency situations.
Cited by 0
Jithin K. Sreedharan, Vinod Sharma · 2013
We consider nonparametric or universal sequential hypothesis testing when the distribution under the null hypothesis is fully known but the alternate hypothesis corresponds to some other unknown distribution. These algorithms are primarily motivated from spectrum sensing in Cognitive Radios and intruder detection in wireless sensor networks. We use easily implementable universal lossless source codes to propose simple algorithms for such a setup. The algorithms are first proposed for discrete alphabet. Their performance and asymptotic properties are studied theoretically. Later these are extended to continuous alphabets. Their performance with two well known universal source codes, Lempel-Ziv code and KT-estimator with Arithmetic Encoder are compared. These algorithms are also compared with the tests using various other nonparametric estimators. Finally a decentralized version utilizing spatial diversity is also proposed and analysed.
Cited by 5
David Varodayan, Anne Aaron, Bernd Girod · 2008
Source coding with correlated decoder side information is considered. We impose the practical constraint that the encoder be unaware of even the statistical dependencies between source and side information. Two classes of rate-adaptive distributed source codes, both based on Low-Density Parity-Check (LDPC) codes, are developed and their design is studied. Specific realizations are shown to be better than alternatives of linear encoding and decoding complexity. The proposed rate-adaptive LDPC Accumulate (LDPCA) codes and Sum LDPC Accumulate (SLDPCA) codes (of length 6336 bits) perform within 10 % and 5 % of the Slepian-Wolf bound in the moderate and high rate regimes, respectively. Keywords: distributed source coding, Slepian-Wolf theorem, side information, LDPC codes, iterative decoding algorithms 1.
Cited by 0
Alfonso Cano, Tairan Wang, Ro Ribeiro et al. · 2015
Abstract — Combining multi-source cooperation and link-adaptive regenerative techniques, we develop a novel protocol capable of achieving diversity up to the number of cooperating users and larger coding gains without incurring the overhead of cyclic redundancy check (CRC) codes. The resulting protocol can be further optimized to take advantage of the information provided by CRC when available. Simulations confirm our theoretical assessments. I.
Cited by 0
Jun Muramatsu · 2024
This paper investigates the general distributed loss-less/lossy source coding formulated by Jana and Blahut. Their multi-letter rate-distortion region, an alternative to the region derived by Yang and Qin, is characterized by entropy functions for arbitrary general correlated sources. Achievability is shown by constructing a code based on constrained-random number generators.
Cited by 2
Jun Muramatsu · arXiv (Cornell University) · 2024
This paper investigates the general distributed lossless/lossy source coding formulated by Jana and Blahut. Their multi-letter rate-distortion region, an alternative to the region derived by Yang and Qin, is characterized by entropy functions for arbitrary general correlated sources. Achievability is shown by constructing a code based on constrained-random number generators.
Cited by 0Open access
I. Manic · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2004
In this project, we investigate the possibility of using the Matching Pursuit algorithm to generate image representations of a pair of correlated images for distributed source coding. We propose to use constrained dictionaries by appropriately selecting neighbouring atoms to increase the correlation between parameters, and with this, enable the application of the distributed framework. Chapter 1
Cited by 0Open access
Sravan Kumar Ankireddy, Sandeep Chinchali, Hyeji Kim et al. · 2023
Cited by 1
Guang, Xuan, Sun, Xiufang, Zhang, Ruze · arXiv (Cornell University) · 2025
Inspired by mobile satellite communication systems and the important and prevalent applications of computational tasks, we consider a distributed source coding model for compressing vector-linear functions, which consists of multiple sources, multiple encoders and a decoder linked to all the encoders. Each encoder has access to a certain subset of the sources and the decoder is required to compute with zero error a vector-linear function of the source information, which corresponds to a matrix $T$. The connectivity state between the sources and the encoders and the vector-linear function are all arbitrary. In the paper, we are interested in the function-compression capacity to measure the efficiency of using the system. We first present a general lower bound on the function-compression capacity applicable to arbitrary connectivity states and vector-linear functions. Next, we confine to the nontrivial models with only three sources and no more than three encoders, and prove that all the $3\times2$ column-full-rank matrices $T$ can be divided into two types $T_1$ and $T_2$, for which the function-compression capacities are identical if the matrices $T$ have the same type. We explicitly characterize the function-compression capacities for two most nontrivial models associated with $T_2$ by a novel approach of both upper bounding and lower bounding the size of image sets of encoding functions. This shows that the lower bound thus obtained is not always tight. Rather, by completely characterizing their capacities, the lower bound is tight for all the models associated with $T_1$ and all the models associated with $T_2$ except for the two most nontrivial models. We finally apply the obtained results to network function computation and answer the open problem whether the best known upper bound proved by Guang et. al. (2019) on computing capacity is in general asymptotically tight.
Cited by 0Open access
David Rebollo‐Monedero, Rui Zhang, Bernd Girod · 2003
The problem of designing optimal quantizers for distributed source coding is addressed. The generality of this formulation includes both the symmetric and asymmetric scenarios, together with a number of coding schemes, such as ideal coding achieving a rate equal to the joint conditional entropy of the quantized sources given the side information. The paper shows the optimality conditions that quantizers must satisfy, and generalizes the Lloyd algorithm for their design. Experimental results are shown for the Gaussian scalar asymmetric case.
Cited by 103
T. Murayama · 2004
The Slepian-Wolf system is analyzed using statistical physics. In our framework, two correlated sequences are separately compressed into shorter codewords employing linear codes, which will be jointly decoded by a practical algorithm. Our analysis shows that the achievable rate region is described as phase transitions, assuming any kind of correlation.
Cited by 0
Mehrdad Panahpour Tehrani, Michael Droese, Toshiaki Fujii et al. · The Journal of The Institute of Image Information and Television Engineers · 2004
This paper discusses new methods for coding of multi-view images. Three distributed solutions are proposed based on a parent node and child node framework. A parent node encodes the whole image whereas a child node only partially. The proposed scheme allows independent encoding of each view. Experimental results show good performance of the proposed architectures at low bit-rates.
Cited by 1Open access
Ma, Nan, Ramchandran, Kannan, Tse, David · arXiv (Cornell University) · 2011
The problem of reconstructing a source sequence with the presence of decoder side-information that is mis-synchronized to the source due to deletions is studied in a distributed source coding framework. Motivated by practical applications, the deletion process is assumed to be bursty and is modeled by a Markov chain. The minimum rate needed to reconstruct the source sequence with high probability is characterized in terms of an information theoretic expression, which is interpreted as the amount of information of the deleted content and the locations of deletions, subtracting "nature's secret", that is, the uncertainty of the locations given the source and side-information. For small bursty deletion probability, the asymptotic expansion of the minimum rate is computed.
Cited by 0Open access
Vladimir Stanković · 2006
Real-time multimedia multicast overwireless networks isanexciting application that hasgenerated alotofinterest recently. Itsmainchallenge lies inthestringent bandwidth andtime-delay requirements of real-time multimedia andsevere impairments ofthewireless channels. We develop asystem formultimedia multicast overwirelesswireline networks, that leverages theknowledge onnetwork information theory, multimedia processing, error control, andnetworking. Inparticular, theencoded multimedia data arebroadcast tomultiple Internet servers overawireless channel. Eachserver merely compresses thesignal ithasreceived using distributed source coding. Thereceiver collects bitstreams fromtheservers before performing joint decoding. Duetospatial diversity gainanddistributed source coding, oursystem significantly outperforms conventional solutions. Inde.T. Terrls-MIutimedia communication, videosignal processing, aiversity metnoas
Cited by 0
Deepak Sridhara · 2003
In a communication network, suppose there are a collection of (correlated) source nodes that want to communicate to a common sink node, then the distributed source coding problem is one of designing a
Cited by 1
Chen, Feng · SHAREOK (University of Oklahoma) · 2015
Distributed Source Coding (DSC) is an important topic for both in information theory and communication. DSC utilizes the correlations among the sources to compress data, and it has the advantages of being simple and easy to carry out. In DSC, Slepian-Wolf (S-W) and Wyner-Ziv (W-Z) are two important problems, which can be classified as lossless compression and loss compression, respectively. Although the lower bounds of the S-W and W-Z problems have been known to researchers for many decades, the code design to achieve the lower bounds is still an open problem. \n \nThis dissertation focuses on three DSC problems: the adaptive Slepian-Wolf decoding for two binary sources (ASWDTBS) problem, the compression of correlated temperature data of sensor network (CCTDSN) problem and the streamlined genome sequence compression using distributed source coding (SGSCUDSC) problem. For the CCTDSN and SGSCUDSC problems, sources will be converted into the binary expression as the sources in ASWDTBS problem for encoding. The Bayesian inference will be applied to all of these three problems. To efficiently solve these Bayesian inferences, message passing algorithm will be applied. For a discrete variable that takes a small number of values, the belief propagation (BP) algorithm is able to implement the message passing algorithm efficiently. However, the complexity of the BP algorithm increases exponentially with the number of values of the variable. Therefore, the BP algorithm can only deal with discrete variable that takes a small number of values and limited continuous variables. For the more complex variables, deterministic approximation methods are used. These methods, such as the variational Bayes (VB) method and expectation propagation (EP) method, can efficiently incorporated into the message passing algorithm. \n \nA virtual binary asymmetric channel (BAC) channel was introduced to model the correlation between the source data and the side information (SI) in ASWDTBS problem, in which two parameters are required to be learned. The two parameters correspond to the crossover probabilities that are 0->1 and 1->0. Based on this model, a factor graph was established that includes LDPC code, source data, SI and both of the crossover probabilities. Since the crossover probabilities are continuous variables, the deterministic approximate inference methods will be incorporated into the message passing algorithm. The proposed algorithm was applied to the synthetic data, and the results showed that the VB-based algorithm achieved much better performance than the performances of the EP-based algorithm and the standard BP algorithm. The poor performance of the EP-based algorithm was also analyzed. \n \nFor the CCTDSN problem, the temperature data were collected by crossbow sensors. Four sensors were established in different locations of the laboratory and their readings were sent to the common destination. The data from one sensor were used as the SI, and the data from the other 3 sensors were compressed. The decoding algorithm considers both spatial and temporal correlations, which are in the form of Kalman filter in the factor graph. To deal with the mixtures of the discrete messages and the continuous messages (Gaussians) in the Kalman filter region of the factor graph, the EP algorithm was implemented so that all of the messages were approximated by the Gaussian distribution. The testing results on the wireless network have indicated that the proposed algorithm outperforms the prior algorithm. \n \nThe SGSCUDSC consists of developing a streamlined genome sequence compression algorithm to support alternative miniaturized sequencing devices, which have limited communication, storage, and computation power. Existing techniques that require a heavy-client (encoder side) cannot be applied. To tackle this challenge, the DSC theory was carefully examined, and a customized reference-based genome compression protocol was developed to meet the low-complexity need at the client side. Based on the variation between the source and the SI, this protocol will adaptively select either syndrome coding or hash coding to compress variable lengths of code subsequences. The experimental results of the proposed method showed promising performance when compared with the state of the art algorithm (GRS).
Cited by 0Open access