On the Delay of Network Coding over Line Networks (2009)
Dikaliotis, Theodoros K., Dimakis, Alexandros G., Ho, Tracey, Effros, Michelle
We analyze a simple network where a source and a receiver are connected by a line of erasure channels of different reliabilities. Recent prior work has shown that random linear network coding can...
Generalized Capacity and Source-Channel Coding for Packet Erasure Channels (2009)
Yifan Liang, Andrea Goldsmith, Michelle Effros
Abstract — We study the transmission of a stationary ergodic Gaussian source over a packet erasure channel, which is a composite channel with degraded states. A broadcast channel code can be...
Distortion Metrics of Composite Channels with Receiver Side Information (2009)
Yifan Liang, Andrea Goldsmith, Michelle Effros
Abstract — We consider transmission of stationary ergodic sources over non-ergodic composite channels with channel state information at the receiver (CSIR). Previously we introduced alternative...
On the Capacity of a Binary MIMO Channel with Random Interference (2009)
Răzvan Cristescu, Michelle Effros, Muriel Médard
We study the capacity of a binary multiple input multiple output (MIMO) channel with interference. Interference is modelled as a non-linear relation between the input and the output words of the...
On Lossless Coding With Coded Side Information (2009)
Marco, Daniel, Effros, Michelle
This paper considers the problem, first introduced by Ahlswede and Korner in 1975, of lossless source coding with coded side information. Specifically, let X and Y be two random variables such that X...
Source-Channel Coding and Separation for Generalized Communication Systems (2009)
Liang, Yifan, Goldsmith, Andrea, Effros, Michelle
We consider transmission of stationary and ergodic sources over non-ergodic composite channels with channel state information at the receiver (CSIR). Previously we introduced alternate capacity...
OPTIMAL STRATEGIES FOR EFFICIENT PEER-TO-PEER FILE SHARING (2009)
Mortada Mehyar, Weihsin Gu, Steven H. Low, Michelle Effros, Tracey Ho
We study a model for peer-to-peer �le sharing. The goal is to distribute a �le from a server to multiple peers. We assume the upload capacity of each peer is the only bottleneck. We examine the...
Optimal multiple description and multiresolution scalar quantizer design (2008)
The author presents new algorithms for fixed-rate multiple description and multiresolution scalar quantizer design. The algorithms both run in time polynomial in the size of the source alphabet and...
On achievable rates for multicast in the presence of side information (2008)
Bakshi, Mayank, Effros, Michelle
We investigate the network source coding rate region for networks with multiple sources and multicast demands in the presence of side information, generalizing earlier results on multicast rate...
On Network Coding of Independent and Dependent Sources in Line Networks (2008)
Bakshi, Mayank, Effros, Michelle, Gu, WeiHsin, Koetter, Ralf
We investigate the network coding capacity for line networks. For independent sources and a special class of dependent sources, we fully characterize the capacity region of line networks for all...
On Source Coding with Coded Side Information for a Binary Source with Binary Side Information (2008)
Gu, WeiHsin, Koetter, Ralf, Effros, Michelle, Ho, Tracey
The lossless rate region for the coded side information problem is "solved," but its solution is expressed in terms of an auxiliary random variable. As a result, finding the rate region for any fixed...
Capacity Definitions of General Channels with Receiver Side Information (2008)
Effros, Michelle, Goldsmith, Andrea, Liang, Yifan
We consider three capacity definitions for general channels with channel side information at the receiver, where the channel is modeled as a sequence of finite dimensional conditional distributions...
Resilient Network Coding in the Presence of Byzantine Adversaries (2008)
Jaggi, Sidharth, Langberg, Michael, Katti, Sachin, Ho, Tracey, Katabi, Dina, Médard, Muriel, ...
Network coding substantially increases network throughput. But since it involves mixing of information inside the network, a single corrupted packet generated by a malicious node can end up...
Byzantine Modification Detection in Multicast Networks With Random Network Coding (2008)
Ho, Tracey, Leong, Ben, Koetter, Ralf, Médard, Muriel, Effros, Michelle, Karger, David R.
An information-theoretic approach for detecting Byzantine or adversarial modifications in networks employing random linear network coding is described. Each exogenous source packet is augmented with...
Capacity Definitions for General Channels with Receiver Side Information (2008)
Effros, Michelle, Goldsmith, Andrea, Liang, Yifan
We consider three capacity definitions for general channels with channel side information at the receiver, where the channel is modeled as a sequence of finite dimensional conditional distributions...
Tracey Ho, Muriel Médard, Ralf Koetter, David R. Karger, Michelle Effros, Jun Shi, ...
random linear network coding approach to multicast
Aditya Ramamoorthy, Kamal Jain, Michelle Effros, Philip A. Chou
This work considers the problem of distributed source coding of multiple sources over a network with multiple receivers. Work by Ho et. al [1] demonstrates that random network coding can solve this...
Quantization as Histogram Segmentation: Optimal Scalar Quantizer Design in Network Systems (2008)
Muresan, Dan, Effros, Michelle
An algorithm for scalar quantizer design on discrete-alphabet sources is proposed. The proposed algorithm can be used to design fixed-rate and entropy-constrained conventional scalar quantizers,...
1 Byzantine Modification Detection in Multicast Networks using Randomized Network Coding (2007)
Tracey Ho, Ben Leong, Ralf Koetter, Muriel M Edard, Michelle Effros, David R. Karger
Abstract--- Distributed randomized network coding is a flexible and robust approach to transmitting and compressing information in multi-source multicast networks. In this paper, we show how the path...
Joint Design of Fixed-Rate Source Codes and UEP Channel Codes for Fading Channels Hai-Xin Tie (2007)
Andrea Goldsmith, Michelle Effros
We study an iterative design algorithm that jointly optimizes source and channel codes for image transmission over Rayleigh fading channels. The joint design combines channel-optimized vector...
John Doyle, Michelle Effros, Jason Hickey, Steven Low
We plan to build a testbed consisting of 8-10 mobile vehicles with embedded computing and communications capability for use in testing new approaches for command and control across dynamic networks....
SEPARABLE KARHUNEN LOEVE TRANSFORMS FOR THE WEIGHTED UNIVERSAL TRANSFORM CODING ALGORITHM (2007)
The weighted universal transform code (WUTC) is a twostage transform code that replaces JPEG's single, non-optimal transform code with a jointly designed collection of transform codes to achieve...
On Approximating the Rate Region for Source Coding with Coded Side Information (2007)
The achievable rate region for the problem of lossless source coding with coded side information was derived by Ahlswede and Körner in 1975. While the Ahlswede-Körner bound completely characterizes...
On the Continuity of Achievable Rate Regions for Source Coding over Networks (2007)
The continuity property of achievable rate regions for source coding over networks is considered. We show rate- distortion regions are continuous with respect to distortion vectors. Then we focus on...
Distortion Metrics of Composite Channels with Receiver Side Information (2007)
Liang, Yifan, Goldsmith, Andrea, Effros, Michelle
We consider transmission of stationary ergodic sources over non-ergodic composite channels with channel state information at the receiver (CSIR). Previously we introduced alternative capacity...
Optimal Strategies for Efficient Peer-to-Peer File Sharing (2007)
Mehyar, Mortada, Gu, WeiHsin, Low, Steven H., Effros, Michelle, Ho, Tracey
We study a model for peer-to-peer file sharing. The goal is to distribute a file from a server to multiple peers. We assume the upload capacity of each peer is the only bottleneck. We examine the...
Evolutionary Approaches To Minimizing Network Coding Resources (2007)
Kim, Minkyu, Médard, Muriel, Aggarwal, Varun, O'Reilly, Una-May, Kim, Wonsik, Ahn, Chang Wook, ...
We wish to minimize the resources used for network coding while achieving the desired throughput in a multicast scenario. We employ evolutionary approaches, based on a genetic algorithm, that avoid...
On Separation for Multiple Access Channels (2007)
Ray, Siddarth, Médard, Muriel, Effros, Michelle, Koetter, Ralf
We examine the issue of separation for multiple access channels. We demonstrate that source-channel separation holds for noisy multiple access channels, when the channel operates over a common finite...
A Practical Scheme for Wireless Network Operation (2007)
Gowaikar, Radhika, Dana, Amir F., Hassibi, Babak, Effros, Michelle
In many problems in wireline networks, it is known that achieving capacity on each link or subnetwork is optimal for the entire network operation. In this paper, we present examples of wireless...
Evolutionary Approaches to Minimizing Network Coding Resources (2007)
Kim, Minkyu, Medard, Muriel, Aggarwal, Varun, O'Reilly, Una-May, Kim, Wonsik, Ahn, Chang Wook, ...
We wish to minimize the resources used for network coding while achieving the desired throughput in a multicast scenario. We employ evolutionary approaches, based on a genetic algorithm, that avoid...
Capacity definitions of general channels with receiver side information (2007)
Abstract — We consider three capacity definitions for general channels with channel side information at the receiver, where the channel is modeled as a sequence of finite dimensional conditional...
Evolutionary approaches to minimizing network coding resources (2007)
Minkyu Kim, Muriel Médard, Varun Aggarwal, Wonsik Kim, Chang Wook Ahn, Michelle Effros
Abstract — We consider the problem of minimizing the resources used for network coding while achieving the desired throughput in a multicast scenario. Since this problem is NPhard, we seek a method...
Low Complexity Encoding for Network Codes (2006)
Jaggi, Siddarth, Cassuto, Yuval, Effros, Michelle
In this paper we consider the per-node run-time complexity of network multicast codes. We show that the randomized algebraic network code design algorithms described extensively in the literature...
On the Concavity of Rate Regions for Lossless Source Coding in Networks (2006)
Gu, Wei-Hsin, Effros, Michelle
For a family of network source coding problems, we prove that the lossless rate region is concave in the distribution of sources. While the proof of concavity is straightforward for the few examples...
A Random Linear Network Coding Approach to Multicast (2006)
Ho, Tracey, Médard, Muriel, Koetter, Ralf, Karger, David R., Effros, Michelle, Shi, Jun, ...
We present a distributed random linear network coding approach for transmission and compression of information in general multisource multicast networks. Network nodes independently and randomly...
Low-Complexity Approaches to Slepian–Wolf Near-Lossless Distributed Data Compression (2006)
Coleman, Todd P., Lee, Anna H., Médard, Muriel, Effros, Michelle
This paper discusses the Slepian–Wolf problem of distributed near-lossless compression of correlated sources. We introduce practical new tools for communicating at all rates in the achievable...
A tiling approach to network code design for wireless networks (2006)
Effros, Michelle, Ho, Tracey, Kim, Sukwon
We describe a new tiling approach for network code design. The proposed method applies dynamic programming to find the best strategy among a restricted collection of network codes. We demonstrate the...
A partial solution for lossless source coding with coded side information (2006)
Marco, Daniel, Effros, Michelle
This paper considers the problem, first introduced by Ahlswede and Körner in 1975, of lossless source coding with coded side information. Specifically, let X and Y be two random variables such that...
Interference management via capacity-achieving codes for the deterministic broadcast channel (2006)
Coleman, Todd P., Martinian, Emin, Effros, Michelle, Médard, Muriel
This paper considers the problem, first introduced by Ahlswede and Körner in 1975, of lossless source coding with coded side information. Specifically, let X and Y be two random variables such that...
On some new approaches to practical Slepian-Wolf compression inspired by channel coding (2006)
Coleman, Todd P., Lee, Anna H., Médard, Muriel, Effros, Michelle
This paper considers the problem, first introduced by Ahlswede and Körner in 1975, of lossless source coding with coded side information. Specifically, let X and Y be two random variables such that...
Separating distributed source coding from network coding (2006)
Ramamoorthy, Aditya, Jain, Kamal, Chou, Philip A., Effros, Michelle
This correspondence considers the problem of distributed source coding of multiple sources over a network with multiple receivers. Each receiver seeks to reconstruct all of the original sources. The...
On Multi-Resolution Coding and a Two-Hop Network (2006)
Gu, Wei-Hsin, Effros, Michelle
We study the source coding problem on a simple two-hop network with side information on the middle and end nodes. For the degraded case, where the side information at the end node is weaker than the...
Time-sharing vs. source-splitting in the Slepian-Wolf problem: error exponents analysis (2006)
Todd P. Coleman, Todd P., Médard, Muriel, Effros, Michelle
We discuss two approaches for decoding at arbitrary rates in the Slepian-Wolf problem - time sharing and source splitting - both of which rely on constituent vertex decoders. We consider the error...
On rate-distortion with mixed types of side information (2006)
Fleming, Michael, Effros, Michelle
In this correspondence, we consider rate-distortion examples in the presence of side information. For a system with some side information known at both the encoder and decoder, and some known only at...
On Separation, Randomness and Linearity for Network Codes over Finite Fields (2006)
Ray, Siddharth, Effros, Michelle, Medard, Muriel, Koetter, Ralf, Ho, Tracey, Karger, David, ...
We examine the issue of separation and code design for networks that operate over finite fields. We demonstrate that source-channel (or source-network) separation holds for several canonical network...
Capacity of wireless erasure networks (2006)
Dana, Amir F., Gowaikar, Radhika, Palanki, Ravi, Hassibi, Babak, Effros, Michelle
In this paper, a special class of wireless networks, called wireless erasure networks, is considered. In these networks, each node is connected to a set of nodes by possibly correlated erasure...
On minimizing network coding resources: An evolutionary approach (2006)
Minkyu Kim, Chang Wook Ahn, Muriel Médard, Michelle Effros
Abstract — We consider the problem of minimizing the resources used for network coding while achieving the desired throughput in a multicast scenario. Since this problem is NPhard, we seek a method...
A random linear network coding approach to multicast (2006)
Tracey Ho, Muriel Médard, Ralf Koetter, David R. Karger, Associate Member, Michelle Effros, ...
Abstract—We present a distributed random linear network coding approach for transmission and compression of information in general multisource multicast networks. Network nodes independently and...
Low-complexity approaches to Slepian-Wolf near-lossless distributed data compression (2006)
Todd P. Coleman, Anna H. Lee, Student Member, Muriel Médard, Michelle Effros, Senior Member, ...
Abstract — This paper discusses the Slepian-Wolf problem of distributed near-lossless compression of correlated sources. We introduce practical new tools for communicating at all rates in the...
Linear complexity universal decoding with exponential error probability decay (2005)
Coleman, Todd P., Médard, Muriel, Effros, Michelle
In this manuscript we consider linear complexity binary linear block encoders and decoders that operate universally with exponential error probability decay. Such scenarios may be relevant in...
Source coding for a simple multi-hop network (2005)
Gu, Wei-Hsin, Effros, Michelle
We derive the rate-distortion region for source coding on a simple multihop network with side information. The result represents the first complete solution to a multihop source coding problem. The...
Rate-splitting for the deterministic broadcast channel (2005)
Coleman, Todd P., Effros, Michelle, Martinian, Emin, Médard, Muriel
We show that the deterministic broadcast channel, where a single source transmits to M receivers across a deterministic mechanism, may be reduced, via a rate-splitting transformation, to another...
Further results on coding for reliable communication over packet networks (2005)
Lun, Desmond S., Médard, Muriel, Koetter, Ralf, Effros, Michelle
In “On Coding for Reliable Communication over Packet Networks” (Lun, Médard, and Effros, Proc. 42nd Annu. Allerton Conf. Communication, Control, and Computing, 2004), a capacity-achieving coding...
Correction of adversarial errors in networks (2005)
Jaggi, Siddarth, Langberg, Michael, Ho, Tracey, Effros, Michelle
We design codes to transmit information over a network, some subset of which is controlled by a malicious adversary. The computationally unbounded, hidden adversary knows the message to be...
On the rate loss and construction of source codes for broadcast channels (2005)
Feng, Hanying, Effros, Michelle
In this paper, we first define and bound the rate loss of source codes for broadcast channels. Our broadcast channel model comprises one transmitter and two receivers; the transmitter is connected to...
On the utility of network coding in dynamic environments (2005)
Ho, Tracey, Leong, Ben, Médard, Muriel, Koetter, Ralf, Chang, Yu-Han, Effros, Michelle
Many wireless applications, such as ad-hoc networks and sensor networks, require decentralized operation in dynamically varying environments. We consider a distributed randomized network coding...
On Coding for Reliable Communication over Packet Networks (2005)
Lun, Desmond S., Medard, Muriel, Koetter, Ralf, Effros, Michelle
We present a capacity-achieving coding scheme for unicast or multicast over lossy packet networks. In the scheme, intermediate nodes perform additional coding yet do not decode nor even wait for a...
Further Results on Coding for Reliable Communication over Packet Networks (2005)
Lun, Desmond S., Medard, Muriel, Koetter, Ralf, Effros, Michelle
In "On Coding for Reliable Communication over Packet Networks" (Lun, Medard, and Effros, Proc. 42nd Annu. Allerton Conf. Communication, Control, and Computing, 2004), a capacity-achieving coding...
Polynomial time algorithms for multicast network code construction (2005)
Jaggi, Sidharth, Sanders, Peter, Chou, Philip A., Effros, Michelle, Egner, Sebastian, Jain, Kamal, ...
The famous max-flow min-cut theorem states that a source node s can send information through a network (V, E) to a sink node t at a rate determined by the min-cut separating s and t. Recently, it has...
Source Coding for a Multihop Network (2005)
Gu, Wei-Hsin, Effros, Michelle
Summary form only given. In this paper, we bound the rate-distortion region for a four-node network. The results are the first known expansion of rate-distortion theory from single-hop networks...
Towards practical minimum-entropy universal decoding (2005)
Coleman, Todd P., Médard, Muriel, Effros, Michelle
Minimum-entropy decoding is a universal decoding algorithm used in decoding block compression of discrete memoryless sources as well as block transmission of information across discrete memoryless...
Effros, Michelle, Koetter, Ralf, Goldsmith, Andrea J., Médard, Muriel
We compare two strategies for lossy source description across a pair of unreliable channels. In the first strategy, we use a broadcast channel code to achieve a different rate for each possible...
On the rate loss of multiple description source codes (2005)
Feng, Hanying, Effros, Michelle
The rate loss of a multiresolution source code (MRSC) describes the difference between the rate needed to achieve distortion D/sub i/ in resolution i and the rate-distortion function R(D/sub i/)....
Uniquely decodable multiple access source codes (2005)
The Slepian-Wolf bound raises interest in lossless code design for multiple access networks. Previous work treats instantaneous codes. We generalize the Sardinas and Patterson test and bound the...
Rapid near-optimal VQ design with a deterministic data net (2005)
Effros, Michelle, Schulman, Leonard J.
We present a new algorithm for fixed-rate vector quantizer (VQ) design with deterministic data net. The algorithm also performs efficient VQ design for simply characterized continuous distributions....
A new source-splitting approach to the Slepian-Wolf problem (2005)
Coleman, Todd, Lee, Anna, Médard, Muriel, Effros, Michelle
It is shown that achieving an arbitrary rate-point in the achievable region of the M-source Slepian-Wolf [1] problem may be reduced via a practical source-splitting transformation to achieving a...
Byzantine modification detection in multicast networks using randomized network coding (2005)
Ho, Tracey, Leong, Ben, Koetter, Ralf, Médard, Muriel, Effros, Michelle, Karger, David R.
Distributed randomized network coding, a robust approach to multicasting in distributed network settings, can be extended to provide Byzantine modification detection without the use of cryptographic...
Network coding for wireless applications: A brief tutorial (2005)
Supratim Deb, Michelle Effros, Tracey Ho, David R. Karger, Ralf Koetter, Desmond S. Lun, ...
Abstract — The advent of network coding promises to change many aspects of networking. Network coding moves away from the classical approach of networking, which treats networks as akin to physical...
Correction of adversarial errors in networks (2005)
Sidharth Jaggi, Michael Langberg, Tracey Ho, Michelle Effros
Abstract — We design codes to transmit information over a network, some subset of which is controlled by a malicious adversary. The computationally unbounded, hidden adversary knows the message to...
Multiresolution vector quantization (2004)
Effros, Michelle, Dugatkin, Diego
Multiresolution source codes are data compression algorithms yielding embedded source descriptions. The decoder of a multiresolution code can build a source reproduction by decoding the embedded bit...
Multiresolution source coding using entropy constrained dithered scalar quantization (2004)
Zhao, Qian, Feng, Hanying, Effros, Michelle
In this paper, we build multiresolution source codes using entropy constrained dithered scalar quantizers. We demonstrate that for n-dimensional random vectors, dithering followed by uniform scalar...
Suboptimality of the Karhunen-Loève transform for transform coding (2004)
Effros, Michelle, Feng, Hanying, Zeger, Kenneth
We examine the performance of the Karhunen-Loeve transform (KLT) for transform coding applications. The KLT has long been viewed as the best available block transform for a system that orthogonally...
Network vector quantization (2004)
Fleming, Michael, Zhao, Qian, Effros, Michelle
We present an algorithm for designing locally optimal vector quantizers for general networks. We discuss the algorithm's implementation and compare the performance of the resulting "network vector...
Is broadcast plus multiaccess optimal for Gaussian wireless networks? (2004)
Dana, Amir F., Sharif, Masoud, Gowaikar, Radhika, Hassibi, Babak, Effros, Michelle
In this paper we show that "separation"-based approaches in wireless networks do not necessarily give good performance in terms of the capacity of the network. Therefore in optimal design of a...
Feng, Hanying, Effros, Michelle
The rate loss of a multi-resolution source code (MRSC) describes the difference between the rate needed to achieve distortion D/sub i/ in resolution i and the rate-distortion function R(D/sub i/). We...
On the capacity of wireless erasure networks (2004)
Gowaikar, Radhika, Dana, Amir F., Palanki, Ravi, Hassibi, Babak, Effros, Michelle
We determine the capacity of a certain class of wireless erasure relay networks. We first find a suitable definition for the "cut-capacity" of erasure networks with broadcast at transmission and no...
Communication and distributional complexity of joint probability mass functions (2004)
Jaggi, Sidharth, Effros, Michelle
The problem of truly-lossless (Pe = 0) distributed source coding [1] requires knowledge of the joint statistics of the sources. In particular the locations of the zeroes of the probability mass...
On the utility of network coding in dynamic environments (2004)
Tracey Ho, Ben Leong, Muriel Médard, Ralf Koetter, Yu-han Chang, Michelle Effros
Abstract — Many wireless applications, such as ad-hoc networks and sensor networks, require decentralized operation in dynamically varying environments. We consider a distributed randomized network...
Byzantine modification detection in multicast networks using randomized network coding (2004)
Tracey Ho, Ben Leong, Ralf Koetter, Muriel Médard, Michelle Effros, David R. Karger
Abstract — We show how distributed randomized network coding, a robust approach to multicasting in distributed network settings, can be extended to provide Byzantine modification detection without...
Michael Fleming, Qian Zhao, Michelle Effros
We present an algorithm for designing locally optimal vector quantizers for general networks. We discuss the algorithm’s implementation and compare the performance of the resulting “network...
Byzantine modification detection in multicast networks using randomized network coding (2004)
Tracey Ho, Ben Leong, Ralf Koetter, Muriel Médard, Michelle Effros, David R. Karger
This paper gives an information theoretic approach for detecting Byzantine modifications in networks employing random linear network coding. Each exogenous source packet is augmented with a flexible...
Network Coding for Correlated Sources (2004)
Tracey Ho, Muriel Médard, Michelle Effros, Ralf Koetter
Abstract — We consider the ability of a distributed randomized network coding approach to multicast, to one or more receivers, correlated sources over a network where compression may be required....
A New Source-Splitting Approach to the Slepian-Wolf Problem (2004)
Todd Coleman Anna, Anna Lee, Muriel Médard, Michelle Effros
It is shown that achieving an arbitrary rate-point in the achievable region of the M-source Slepian-Wolf [1] problem may be reduced via a practical source-splitting transformation to achieving a...
Byzantine Modification Detection in Multicast Networks using Randomized Network Coding (2004)
Tracey Ho, Ben Leong, Ralf Koetter, Muriel Medard, Michelle Effros, David R. Karger
We show how distributed randomized network coding, a robust approach to multicasting in distributed network settings, can be extended to provide Byzantine modification detection without the use of...
On Source and Channel Codes for Multiple Inputs and Outputs (2004)
Michelle Effros, Ralf Koetter, Andrea J. Goldsmith, Muriel Médard
Abstract — We compare two strategies for lossy source description across a pair of unreliable channels. In the first strategy, we use a broadcast channel code to achieve a different rate for each...
On Source and Channel Codes for Multiple Inputs and Outputs (2004)
Michelle Effros, Ralf Koetter, Andrea J. Goldsmith, Muriel Médard
Abstract — We compare two strategies for lossy source description across a pair of unreliable channels. In the first strategy, we use a broadcast channel code to achieve a different rate for each...
Suboptimality of the Karhunen-Lo eve Transform (2004)
For Transform Coding, Michelle Effros, Hanying Feng, Kenneth Zeger
We examine the performance of the KLT for transform coding applications. The KLT has long been viewed as the best available block transform for transform coding.
On coding for reliable communication over packet networks (2004)
Desmond S. Lun, Muriel Médard, Michelle Effros
We present a capacity-approaching coding scheme for unicast or multicast over lossy packet networks. In the scheme, all nodes perform coding, but do not wait for a full block of packets to be...
Practical schemes for wireless networks operation (2004)
Radhika Gowaikar, Amir F. Dana, Babak Hassibi, Michelle Effros
In many problems in wireline networks, it is known that achieving capacity on each link or sub-network is optimal for the entire network operation. In this paper we show that achieving capacity on...
Toward a random operation of networks (2004)
Tracey Ho, Muriel Médard, Ralf Koetter, David R. Karger, Michelle Effros, Jun Shi, ...
We present a distributed randomized network coding approach for transmission and compression of information in general multi-source multicast networks. Network nodes independently and randomly select...
Practical schemes for wireless networks operation,” submitted to (2004)
Radhika Gowaikar, Amir F. Dana, Student Member, Student Member, Babak Hassibi, Michelle Effros, ...
Abstract—In many problems in wireline networks, it is known that achieving capacity on each link or subnetwork is optimal for the entire network operation. In this paper, we present examples of...
Functional source coding for networks with receiver side information (2004)
Hanying Feng, Michelle Effros, Serap Savari
We study the rate-distortion region for a functional source coding problem. In the given source coding scenario, an encoder receives a noisy observation ˜ X of source X and describes that source to...
On coding for reliable communication over packet networks (2004)
D. Medard, R Effros, Subaward No. S, Office Of, Desmond S. Lun, Muriel Médard, ...
We present a capacity-achieving coding scheme for unicast or multicast over lossy packet networks. In the scheme, intermediate nodes perform additional coding yet do not decode nor even wait for a...
On some new approaches to practical Slepian-Wolf compression inspired by channel coding (2004)
Todd P. Coleman, Anna H. Lee, Muriel Médard, Michelle Effros
We introduce three new innovations for compression using LDPCs for the Slepian-Wolf problem. The first is a general iterative Slepian-Wolf decoding algorithm that incorporates the graphical structure...
Separating Distributed Source Coding from Network Coding (2004)
Aditya Ramamoorthy, Kamal Jain, Philip A. Chou, Michelle Effros, Senior Member
Abstract—This correspondence considers the problem of distributed source coding of multiple sources over a network with multiple receivers. Each receiver seeks to reconstruct all of the original...
Rate-distortion with mixed types of side information (2003)
Fleming, Michael, Effros, Michelle
We present the rate-distortion function and bound the rate loss for a system with some side information (s.i.) known at both the encoder and decoder, and some known only at the decoder. We extend the...
The benefits of coding over routing in a randomized setting (2003)
Ho, Tracey, Koetter, Ralf, Médard, Muriel, Karger, David R., Effros, Michelle
A novel randomized network coding approach for robust, distributed transmission and compression of information in networks is presented, and its advantages over routing-based approaches is...
On the achievable region for multiple description source codes on Gaussian sources (2003)
Feng, Hanying, Effros, Michelle
We demonstrate inconsistencies in prior results on the achievable region for multiple description (MD) source codes on i.i.d. Gaussian sources with the squared error distortion measure. We then...
Suboptimality of the Karhunen-Loève transform for transform coding (2003)
Effros, Michelle, Feng, Hanying, Zeger, Kenneth
We examine the performance of the KLT for transform coding applications. The KLT has long been viewed as the best available block transform for transform coding. This paper treats fixed-rate and...
Low complexity code design for lossless and near-lossless side information source codes (2003)
The instantaneous side of information source code (SISC) design is considered. In the SISC configuration, the encoder describes source X to the decoder; the decoder uses this description and side...
Network source coding using entropy constrained dithered quantization (2003)
Feng, Hanying, Zhao, Qian, Effros, Michelle
Assuming the squared error distortion measure, we bound the performance achieved by using scalar entropy constrained dithered quantization (SECDQ) [1] to build multi-resolution (MR), multiple access...
Improved bounds for the rate loss of multiresolution source codes (2003)
Feng, Hanying, Effros, Michelle
We present new bounds for the rate loss of multiresolution source codes (MRSCs). Considering an M-resolution code, the rate loss at the ith resolution with distortion D/sub i/ is defined as L/sub...
Lossless and near-lossless source coding for multiple access networks (2003)
A multiple access source code (MASC) is a source code designed for the following network configuration: a pair of correlated information sequences {X-i}(i=1)(infinity), and {Y-i}(i=1)(infinity) is...
The benefits of coding over routing in a randomized setting (2003)
Tracey Ho, Ralf Koetter, Muriel Médard, David R. Karger, Michelle Effros
Abstract — We present a novel randomized coding approach for robust, distributed transmission and compression of information in networks. We give a lower bound on the success probability of a...
The benefits of coding over routing in a randomized setting (2003)
Tracey Ho, Ralf Koetter, Muriel Médard, David R. Karger, Michelle Effros
Abstract — We present a novel randomized coding approach for robust, distributed transmission and compression of information in networks. We give a lower bound on the success probability of a...
Polynomial Time Algorithms for Multicast Network Code Construction (2003)
Sidharth Jaggi, Peter Sanders, Philip A. Chou, Michelle Effros, Sebastian Egner, Kamal Jain, ...
The famous max-ow min-cut theorem states that a source node s can send information through a network (V; E) to a sink node t at a rate determined by the min-cut separating s and t. Recently it has...
Linear Network Codes: A Unified Framework for Source, Channel, and Network Coding (2003)
Michelle Effros, Muriel Medard, Tracey Ho, Siddharth Ray, David Karger, Ralf Koetter, ...
We examine the issue of separation and code design for network data transmission environments. We demonstrate that source-channel separation holds for several canonical network channel models when...
On Randomized Network Coding (2003)
Tracey Ho, Muriel Medard, Jun Shi, Michelle Effros, David R. Karger
We consider a randomized network coding approach for multicasting from several sources over a network, in which nodes independently and randomly select linear mappings from inputs onto output links...
On Coding for Non-Multicast Networks (2003)
Muriel Medard, Michelle Effros, David Karger, Tracey Ho
We consider the issue of coding for non-multicast networks. For multicast networks, it is known that linear operations over a field no larger than the number of receivers are su#cient to achieve all...
On randomized network coding (2003)
Tracey Ho, Muriel Médard, Jun Shi, Michelle Effros, David R. Karger
We consider a randomized network coding approach for multicasting from several sources over a network, in which nodes independently and randomly select linear mappings from inputs onto output links...
The Benefits of Coding over Routing in a Randomized Setting (2003)
Tracey Ho, Ralf Koetter, Muriel Medard, David R. Karger, Michelle Effros
We present a novel randomized network coding approach for robust, distributed transmission and compression of information in networks, and demonstrate its advantages over routing-based approaches.
Codecell contiguity in optimal fixed-rate and entropy-constrained network scalar quantizers (2002)
Effros, Michelle, Muresan, Dan
We consider the properties of optimal fixed-rate and entropy-constrained scalar quantizers for finite alphabet sources. In particular, we consider conditions under which the optimal scalar quantizer...
Multi-resolution adaptation of the SPIHT algorithm for multiple description (2002)
Varnica, Nedeljko, Fleming, Michael, Effros, Michelle
Multiple description codes are data compression algorithms designed with the goal of minimizing the distortion caused by data loss in packet-based or diversity communications systems. Recently,...
Multi-resolution VQ: parameter meaning and choice (2002)
Dugatkin, Diego, Effros, Michelle
In multi-resolution source coding, a single code is used to give an embedded data description that may be decoded at a variety of rates. Recent work in practical multi-resolution coding treats the...
Robustness to channel variation in source coding for transmission across noisy channels (2002)
We consider the problem of lossy source coding for transmission across an unknown or time-varying noisy channel. The objective is to design an optimal compression system for applications where the...
Effros, Michelle, Chou, Philip A.
We introduce a two-stage universal transform code for image compression. The code combines Karhunen-Loève transform coding with weighted universal bit allocation (WUBA) in a two-stage algorithm...
Universal lossless source coding with the Burrows Wheeler transform (2002)
Effros, Michelle, Visweswariah, Karthik, Kulkarni, Sanjeev R., Verdú, Sergio
The Burrows Wheeler transform (1994) is a reversible sequence transformation used in a variety of practical lossless source-coding algorithms. In each, the BWT is followed by a lossless source code...
Feng, Hanying, Effros, Michelle
We examine the rate-distortion performance and computational complexity of linear transforms for lossy data compression. The goal is to better understand the performance/complexity tradeoffs...
Side information source coding: low complexity design and source independence (2002)
Zhao, Qian, Jaggi, Sidharth, Effros, Michelle
Correlated sources X and Y are drawn i.i.d. according to probability mass function (pmf) p(x,y). In the side information source code (SISC) configuration: p(x,y) is known a priori to both the encoder...
Muresan, Dan, Effros, Michelle
We propose a polynomial-time algorithm for optimal scalar quantizer design on discrete-alphabet sources. Special cases of the proposed approach yield optimal design algorithms for fixed-rate and...
Universal linked multiple access source codes (2002)
Jaggi, Sidharth, Effros, Michelle
We consider the multiple access source coding (MASC) problem (also known as the Slepian-Wolf problem) for situations where the joint source statistics are unknown a priori. Since neither encoder...
Universal multiresolution source codes (2001)
A multiresolution source code is a single code giving an embedded source description that can be read at a variety of rates and thereby yields reproductions at a variety of resolutions. The...
Goldsmith, Andrea J., Effros, Michelle
We derive the capacity region for a broadcast channel with intersymbol interference (ISI) and colored Gaussian noise under an input power constraint. The region is obtained by first defining a...
Optimal code design for lossless and near lossless source coding in multiple access networks (2001)
A multiple access source code (MASC) is a source code designed for the following network configuration: a pair of correlated information sequences {Xi}i=1∞ and {Yi }i=1∞ is drawn i.i.d. according...
Lossless source coding for multiple access networks (2001)
A multiple access source code (MASC) is a source code designed for the following network configuration: a pair of jointly distributed information sequences {Xi}i=1∞ and {Yi}i=1∞ is drawn i.i.d....
Improved bounds for the rate loss of multi-resolution source codes (2001)
Feng, Hanying, Effros, Michelle
In this paper, we present new bounds for the rate loss of multi-resolution source codes. Consider an M-resolution code with ith-resolution rate and distortion Ri and Di. The ith-resolution rate loss,...
Network Vector Quantization (2001)
Fleming, Michael, Effros, Michelle
A network source code is an optimal source code for a network. To design network source codes, we require each node to have a single encoder, which jointly encodes all messages transmitted by that...
Andrea J. Goldsmith, Senior Member, Michelle Effros
Abstract—We derive the capacity region for a broadcast channel with intersymbol interference (ISI) and colored Gaussian noise under an input power constraint. The region is obtained by first...
Andrea J. Goldsmith, Senior Member, Michelle Effros
Abstract—We derive the capacity region for a broadcast channel with intersymbol interference (ISI) and colored Gaussian noise under an input power constraint. The region is obtained by first...
The Capacity Region of Gaussian Broadcast Channels with Intersymbol Interference (2001)
Andrea Goldsmith, Michelle Effros
We derive the two-user capacity region with and without common information for a Gaussian broadcast channel with intersymbol interference, assuming colored Gaussian noise and an input power...
PPM performance with BWT complexity: a fast and effective data compression algorithm (2000)
This paper introduces a new data compression algorithm. The goal underlying this new code design is to achieve a single lossless compression algorithm with the excellent compression ratios of the...
Broadcast systems are a class of networks where one system node (transmitter) simultaneously sends both common and independent, information to multiple nodes (receivers) in the system. Compressing...
Multi-resolution channel codes (2000)
Feng, Hanying, Effros, Michelle
In this paper, we present a new approach for channel coding on unknown or time-varying channels. Given a family of possible channel characteristics, we define a multi-resolution channel code as a...
PPM performance with BWT complexity: a new method for lossless data compression (2000)
This work combines a new fast context-search algorithm with the lossless source coding models of PPM to achieve a lossless data compression algorithm with the linear context-search complexity and...
The rate distortion region for the multiple description problem (2000)
Fleming, Michael, Effros, Michelle
We derive the rate-distortion region for the two-channel multiple description problem on stationary discrete ergodic and nonergodic sources with alphabets admitting an ergodic decomposition. The...
Joint design of vector quantizers and RCPC channel codes for Rayleigh fading channels (2000)
Shen, Yirong, Goldsmith, Andrea J., Effros, Michelle
We study the performance of joint source and channel codes designed to minimize end-to-end distortion over a Rayleigh fading channel. We consider two joint code designs. The first joint code uses a...
Weighted universal image compression (1999)
Effros, Michelle, Chou, Philip A., Gray, Robert M.
We describe a general coding strategy leading to a family of universal image compression systems designed to give good performance in applications where the statistics of the source to be compressed...
Distortion-rate bounds for fixed- and variable-rate multiresolution source codes (1999)
The source coding theorem for stationary sources describes the optimal performance theoretically achievable by fixed- and variable-rate block quantizers. The source coding theorem may be generalized...
Universal lossless source coding with the Burrows Wheeler transform (1999)
We here consider a theoretical evaluation of data compression algorithms based on the Burrows Wheeler transform (BWT). The main contributions include a variety of very simple new techniques for...
Broadcast system source codes: a new paradigm for data compression (1999)
Broadcast systems play a central role in an enormous variety of network technologies in which one system node must simultaneously send either the same or different information to multiple nodes in...
Separable Karhunen Loeve transforms for the weighted universal transform coding algorithm (1999)
Feng, Hanying, Effros, Michelle
The weighted universal transform code (WUTC) is a two-stage transform code that replaces JPEG's single, non-optimal transform code with a jointly designed collection of transform codes to achieve...
Generalized multiple description vector quantization (1999)
Fleming, Michael, Effros, Michelle
Packet-based data communication systems suffer from packet loss under high network traffic conditions. As a result, the receiver is often left with an incomplete description of the requested data....
Universal lossless source coding with the burrows wheeler transform (1999)
Michelle Effros, Karthik Visweswariah, Sanjeev R. Kulkarni, Senior Member, Sergio Verdú
reversible sequence transformation used in a variety of practical lossless source-coding algorithms. In each, the BWT is followed by a lossless source code that attempts to exploit the natural...
Optimal modeling for complex system design (1998)
The article begins with a brief introduction to the theory describing optimal data compression systems and their performance. A brief outline is then given of a representative algorithm that employs...
A Multi-Vehicles, Wireless Testbed for Networked Control, Communications and Computing (1998)
Murray, Richard, Doyle, John, Effros, Michelle, Hickey, Jason, Low, Steven
We have constructed a testbed consisting of 4 mobile vehicles (with 4 additional vehicles being completed), each with embedded computing and communications capability for use in testing new...
Joint design of fixed-rate source codes and multiresolution channel codes (1998)
Goldsmith, Andrea J., Effros, Michelle
We propose three new design algorithms for jointly optimizing source and channel codes. Our optimality criterion is to minimize the average end-to-end distortion. For a given channel SNR and...
Multi-resolution source coding theorems (1998)
For stationary sources on Polish alphabets, we describe the family of achievable rate and distortion vectors (R1,…,RL) and (D1,…,DL) for an L-resolution source code, where the description at the...
Effros, Michelle, Goldsmith, Andrea
We consider three capacity definitions for a channel with channel side information at the receiver. The capacity is the highest rate asymptotically achievable. The outage capacity is the highest rate...
Practical multi-resolution source coding: TSVQ revisited (1998)
Consider a multi-resolution source code for describing a stationary source at L resolutions. The description at the first resolution is given at rate R1 and achieves an expected distortion no greater...
Joint design of fixed-rate source codes and UEP channel codes for fading channels (1998)
Tie, Hai-Xin, Goldsmith, Andrea, Effros, Michelle
We study an iterative design algorithm that jointly optimizes source and channel codes for image transmission over Rayleigh fading channels. The joint design combines channel-optimized vector...
Joint design of fixed-rate source codes and multiresolution channel codes (1998)
Andrea J. Goldsmith, Michelle Effros
Abstract—We propose three new design algorithms for jointly optimizing source and channel codes. Our optimality criterion is to minimize the average end-to-end distortion. For a given channel SNR...
Practical Multi-Resolution Source Coding: TSVQ Revisited (1998)
Consider a multi-resolution source code for describing a stationary source at L resolutions. The description at the first resolution is given at rate R 1 and achieves an expected distortion no...
Iterative Joint Design of Source Codes and Multiresolution Channel Codes (1998)
Andrea Goldsmith, Michelle Effros
We propose an iterative design algorithm for jointly optimizing source and channel codes. The joint design combines channel-optimized vector quantization (COVQ) for the source code with...
Joint Design of Fixed-Rate Source Codes and Multiresolution Channel Codes (1998)
Andrea Goldsmith, Michelle Effros
We propose three new design algorithms for jointly optimizing source and channel codes. The joint designs combine channel-optimized vector quantization (COVQ) for the source code with rate-compatible...
The Capacity Region of Gaussian Broadcast Channels with Intersymbol Interference (1998)
Andrea J. Goldsmith, Michelle Effros
We derive the two-user capacity region with and without common information for a Gaussian broadcast channel with intersymbol interference, assuming colored Gaussian noise and an input power...
Effros and Chou (see Proceedings of the IEEE International Conference on Image Processing, Washington, DC, 1995) introduce a two-stage universal transform code called the weighted universal transform...
Conditional weighted universal source codes: second order statistics in universal coding (1997)
We consider the use of second order statistics in two-stage universal source coding. Examples of two-stage universal codes include the weighted universal vector quantization (WUVQ), weighted...
Zerotree design for image compression: toward weighted universal zerotree coding (1997)
We consider the problem of optimal, data-dependent zerotree design for use in weighted universal zerotree codes for image compression. A weighted universal zerotree code (WUZC) is a data compression...
Iterative joint design of source codes and multiresolution channel codes (1997)
Goldsmith, Andrea, Effros, Michelle
We propose an iterative design algorithm for jointly optimizing source and channel codes. The joint design combines channel-optimized vector quantization (COVQ) for the source code with...
The capacity region of broadcast channels with memory (1997)
Goldsmith, Andrea, Effros, Michelle
We derive the two-user capacity region of a broadcast channel with memory (ISI), assuming additive white Gaussian noise (AWGN) and an input power constraint. The results can be extended to any finite...
Rate-Distortion Bounds for Fixed- and Variable-Rate Multi-Resolution Source Codes (1997)
The source coding theorem for stationary sources describes the optimal performance theoretically achievable by fixed- and variable-rate block quantizers. We here generalize the source coding theorem...
In [1], Effros and Chou introduce a two-stage universal transform code called the weighted universal transform code (WUTC). By replacing JPEG's single, non-optimal transform code with a...
Zerotree Design for Image Compression: Toward Weighted Universal Zerotree Coding (1997)
We consider the problem of optimal, datadependent zerotree design for use in weighted universal zerotree codes for image compression. A weighted universal zerotree code (WUZC) is a data compression...
Iterative Joint Design of Fixed-Rate Source Codes and Multiresolution Channel Codes (1997)
Andrea Goldsmith, Michelle Effros
We propose an iterative design algorithm for jointly optimizing source and channel codes. The joint design combines channel-optimized vector quantization (COVQ) for the source code with...
A vector quantization approach to universal noiseless coding and quantization (1996)
Chou, Philip A., Effros, Michelle, Gray, Robert M.
A two-stage code is a block code in which each block of data is coded in two stages: the first stage codes the identity of a block code among a collection of codes, and the second stage codes the...
A Vector Quantization Approach to Universal Noiseless Coding and Quantization (1996)
Philip A. Chou, Michelle Effros, Roben M. Gray, Fellow Ieee
Abstract-A two-stage code is a block code in which each block of data is coded in two stages: the first stage codes the identity of a block code among a collection of codes, and the second stage...
Weighted Universal Image Compression (1996)
Michelle Effros, Philip A. Chou, Robert M. Gray
We describe a family of universal image compression systems designed to give good performance in applications where the statistics of the source to be compressed are not available at design time or...
Weighted Universal Image Compression (1996)
Michelle Effros, Philip A. Chou, Robert M. Gray
: We describe a general coding strategy leading to a family of universal image compression systems designed to give good performance in applications where the statistics of the source to be...
Data expansion with Huffman codes (1995)
Cheng, Jung-Fu, Dolinar, Sam, Effros, Michelle, McEliece, Robert
The following topics were dealt with: Shannon theory; universal lossless source coding; CDMA; turbo codes; broadband networks and protocols; signal processing and coding; coded modulation;...
Michelle Effros, Philip A. Chou
We introduce a two-stage universal transform code for image compression. The code combines KarhunenLo `eve transform coding with weighted universal bit allocation (WUBA) [1] in a two-stage algorithm...
A progressive universal noiseless coder (1994)
Effros, Michelle, Chou, Philip A., Riskin, Eve A., Gray, Robert M.
The authors combine pruned tree-structured vector quantization (pruned TSVQ) with Itoh's (1987) universal noiseless coder. By combining pruned TSVQ with universal noiseless coding, they benefit from...
Universal and adaptive source coding:--theory and practice /--by Michelle Effros. (1994)
Submitted to the Department of Electrical Engineering.
Perlmutter, Keren O., Perlmutter, Sharon M., Effros, Michelle, Gray, Robert M.
A finite-state vector quantizer (FSVQ) is a multicodebook system in, which the current state (or codebook) is chosen as a function of the previously quantized vectors. The authors introduce a novel...
A mean-removed variation of weighted universal vector quantization for image coding (1993)
Andrews, Barry D., Effros, Michelle, Chou, Philip A., Gray, Robert M.
Weighted universal vector quantization uses traditional codeword design techniques to design locally optimal multi-codebook systems. Application of this technique to a sequence of medical images...
Chou, Philip A., Effros, Michelle
Rissanen has shown that there exist universal noiseless codes for {Xi} with per-letter rate redundancy as low as (K log N)/2N, where N is the blocklength and K is the number of source parameters. we...
A Progressive Universal Noiseless Coder (1991)
Effros, Michelle, Chou, Philip A., Riskin, Eve A., Gray, Robert M.
We describe an adaptation of Itoh and Kawabata's universal noiseless coder that allows for progressive transmission of images. The system is based on a tree structure, and codewords stored at...