BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Michelle Effros

Michelle Effros appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITNetworking and Internet ArchitectureDiscrete Mathematicseess.SYMultiagent SystemsMultimediaSystems and Control

Catalog footprint

What is connected

35works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

35 published item(s)

preprint2022arXiv

Gaussian Multiple and Random Access in the Finite Blocklength Regime

This paper presents finite-blocklength achievability bounds for the Gaussian multiple access channel (MAC) and random access channel (RAC) under average-error and maximal-power constraints. Using random codewords uniformly distributed on a sphere and a maximum likelihood decoder, the derived MAC bound on each transmitter's rate matches the MolavianJazi-Laneman bound (2015) in its first- and second-order terms, improving the remaining terms to $\frac12\frac{\log n}{n}+O \left(\frac 1 n \right)$ bits per channel use. The result then extends to a RAC model in which neither the encoders nor the decoder knows which of $K$ possible transmitters are active. In the proposed rateless coding strategy, decoding occurs at a time $n_t$ that depends on the decoder's estimate $t$ of the number of active transmitters $k$. Single-bit feedback from the decoder to all encoders at each potential decoding time $n_i$, $i \leq t$, informs the encoders when to stop transmitting. For this RAC model, the proposed code achieves the same first-, second-, and third-order performance as the best known result for the Gaussian MAC in operation.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Network Coding Multicast Key-Capacity

For a multi-source multi-terminal noiseless network, the key-dissemination problem involves the task of multicasting a secret key K from the network sources to its terminals. As in secure multicast network-coding, in the key-dissemination problem the source nodes have access to independent randomness and, as the network is noiseless, the resulting key K is a function of the sources' information. However, different from traditional forms of multicast, in key-dissemination the key K need not consist of source messages, but rather may be any function of the information generated at the sources, as long as it is shared by all terminals. Allowing the shared key K to be a mixture of source information grants a flexibility to the communication process which gives rise to the potential of increased key-rates when compared to traditional secure multicast. The multicast key-capacity is the supremum of achievable key-rates, subject to the security requirement that the shared key is not revealed to an eavesdropper with predefined eavesdropping capabilities. The key-dissemination problem (termed also, secret key-agreement) has seen significant studies over the past decades in memoryless network structures. In this work, we initiate the study of key-dissemination in the context of noiseless networks, i.e., network coding. In this context, we study similarities and differences between traditional secure-multicast and the more lenient task of key-dissemination.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the Benefit of Cooperation in Relay Networks

This work addresses the cooperation facilitator (CF) model, in which network nodes coordinate through a rate limited communication device. For independent multiple-access channel (MAC) encoders, the CF model is known to show significant rate benefits, even when the rate of cooperation is negligible. Specifically, the benefit in MAC sum-rate, as a function of the cooperation rate $C_{CF}$, sometimes has an infinite slope at $C_{CF}=0$. This work studies the question of whether cooperation through a CF can yield similar infinite-slope benefits when applied to internal network encoders in which dependence among MAC transmitters can be established without the help of the CF. Towards this end, this work studies the CF model when applied to relay nodes of a single-source, single-terminal, diamond network consisting of a broadcast channel followed by a MAC. In the relay channel with orthogonal receiver components, careful generalization of the partial-decode-forward/compress-forward lower bound to the CF model yields sufficient conditions for an infinite-slope benefit. Additional results include derivation of a family of diamond networks for which the infinite-slope rate-benefit derives directly from the properties of the corresponding MAC component when studied in isolation.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

OUTformation: Distributed Data-Gathering with Feedback under Unknown Environment and Communication Delay Constraints

Towards the informed design of large-scale distributed data-gathering architectures under real-world assumptions such as nonzero communication delays and unknown environment dynamics, this paper considers the effects of allowing feedback communication from the central processor to external sensors. Using simple but representative state-estimation examples, we investigate fundamental tradeoffs between the mean-squared error (MSE) of the central processor's estimate of the environment state, and the total power expenditure per sensor under more conventional architectures without feedback (INformation) versus those with broadcast feedback (OUTformation). The primary advantage of enabling feedback is that each sensor's understanding of the central processor's estimate improves, which enables each sensor to determine when and what parts of its current observations to transmit. We use theory to demonstrate conditions in which OUTformation maintains the same MSE as INformation with less power expended on average, and conditions in which OUTformation obtains less MSE than INformation at additional power cost. These performance tradeoffs are also considered under settings where environments undergo less variation, and sensors implement random backoff times to prevent transmission collisions. Our results are supported via numerical studies, which show that the properties derived in theory still hold even when some of the simplifying assumptions are removed.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Beyond Capacity: The Joint Time-Rate Region

The traditional notion of capacity studied in the context of memoryless network communication builds on the concept of block-codes and requires that, for sufficiently large blocklength n, all receiver nodes simultaneously decode their required information after n channel uses. In this work, we generalize the traditional capacity region by exploring communication rates achievable when some receivers are required to decode their information before others, at different predetermined times; referred here as the "time-rate" region. Through a reduction to the standard notion of capacity, we present an inner-bound on the time-rate region. The time-rate region has been previously studied and characterized for the memoryless broadcast channel (with a sole common message) under the name "static broadcasting".

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Every Bit Counts: Second-Order Analysis of Cooperation in the Multiple-Access Channel

The work at hand presents a finite-blocklength analysis of the multiple access channel (MAC) sum-rate under the cooperation facilitator (CF) model. The CF model, in which independent encoders coordinate through an intermediary node, is known to show significant rate benefits, even when the rate of cooperation is limited. We continue this line of study for cooperation rates which are sub-linear in the blocklength $n$. Roughly speaking, our results show that if the facilitator transmits $\log{K}$ bits, there is a sum-rate benefit of order $\sqrt{\log{K}/n}$. This result extends across a wide range of $K$: even a single bit of cooperation is shown to provide a sum-rate benefit of order $1/\sqrt{n}$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Edge removal in undirected networks

The edge-removal problem asks whether the removal of a $λ$-capacity edge from a given network can decrease the communication rate between source-terminal pairs by more than $λ$. In this short manuscript, we prove that for undirected networks, removing a $λ$-capacity edge decreases the rate by $O(λ)$. Through previously known reductive arguments, here newly applied to undirected networks, our result implies that the zero-error capacity region of an undirected network equals its vanishing-error capacity region. Whether it is possible to prove similar results for directed networks remains an open question.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finite-Blocklength and Error-Exponent Analyses for LDPC Codes in Point-to-Point and Multiple Access Communication

This paper applies error-exponent and dispersion-style analyses to derive finite-blocklength achievability bounds for low-density parity-check (LDPC) codes over the point-to-point channel (PPC) and multiple access channel (MAC). The error-exponent analysis applies Gallager's error exponent to bound achievable symmetrical and asymmetrical rates in the MAC. The dispersion-style analysis begins with a generalization of the random coding union (RCU) bound from random code ensembles with i.i.d. codewords to random code ensembles in which codewords may be statistically dependent; this generalization is useful since the codewords of random linear codes such as random LDPC codes are dependent. Application of the RCU bound yields improved finite-blocklength error bounds and asymptotic achievability results for i.i.d. random codes and new finite-blocklength error bounds and achievability results for LDPC codes. For discrete, memoryless channels, these results show that LDPC codes achieve first- and second-order performance that is optimal for the PPC and identical to the best-prior results for the MAC.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Towards an Operational Definition of Group Network Codes

Group network codes are a generalization of linear codes that have seen several studies over the last decade. When studying network codes, operations performed at internal network nodes called local encoding functions, are of significant interest. While local encoding functions of linear codes are well understood (and of operational significance), no similar operational definition exists for group network codes. To bridge this gap, we study the connections between group network codes and a family of codes called Coordinate-Wise-Linear (CWL) codes. CWL codes generalize linear codes and, in addition, can be defined locally (i.e., operationally). In this work, we study the connection between CWL codes and group codes from both a local and global encoding perspective. We show that Abelian group codes can be expressed as CWL codes and, as a result, they inherit an operational definition.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Can Negligible Cooperation Increase Network Reliability?

In network cooperation strategies, nodes work together with the aim of increasing transmission rates or reliability. This paper demonstrates that enabling cooperation between the transmitters of a two-user multiple access channel, via a cooperation facilitator that has access to both messages, always results in a network whose maximal- and average-error sum-capacities are the same---even when those capacities differ in the absence of cooperation and the information shared with the encoders is negligible. From this result, it follows that if a multiple access channel with no transmitter cooperation has different maximal- and average-error sum-capacities, then the maximal-error sum-capacity of the network consisting of this channel and a cooperation facilitator is not continuous with respect to the output edge capacities of the facilitator. This shows that there exist networks where sharing even a negligible number of bits per channel use with the encoders yields a non-negligible benefit.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Impact of a Single Edge on the Network Coding Capacity

In this paper, we study the effect of a single link on the capacity of a network of error-free bit pipes. More precisely, we study the change in network capacity that results when we remove a single link of capacity $δ$. In a recent result, we proved that if all the sources are directly available to a single super-source node, then removing a link of capacity $δ$ cannot change the capacity region of the network by more than $δ$ in each dimension. In this paper, we extend this result to the case of multi-source, multi-sink networks for some special network topologies.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Multivariate Covering Lemma and its Converse

The multivariate covering lemma states that given a collection of $k$ codebooks, each of sufficiently large cardinality and independently generated according to one of the marginals of a joint distribution, one can always choose one codeword from each codebook such that the resulting $k$-tuple of codewords is jointly typical with respect to the joint distribution. We give a proof of this lemma for weakly typical sets. This allows achievability proofs that rely on the covering lemma to go through for continuous channels (e.g., Gaussian) without the need for quantization. The covering lemma and its converse are widely used in information theory, including in rate-distortion theory and in achievability results for multi-user channels.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Unbounded Benefit of Encoder Cooperation for the $k$-user MAC

Cooperation strategies allow communication devices to work together to improve network capacity. Consider a network consisting of a $k$-user multiple access channel (MAC) and a node that is connected to all $k$ encoders via rate-limited bidirectional links, referred to as the "cooperation facilitator" (CF). Define the cooperation benefit as the sum-capacity gain resulting from the communication between the encoders and the CF and the cooperation rate as the total rate the CF shares with the encoders. This work demonstrates the existence of a class of $k$-user MACs where the ratio of the cooperation benefit to cooperation rate tends to infinity as the cooperation rate tends to zero. Examples of channels in this class include the binary erasure MAC for $k=2$ and the $k$-user Gaussian MAC for any $k\geq 2$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Perspective on Future Research Directions in Information Theory

Information theory is rapidly approaching its 70th birthday. What are promising future directions for research in information theory? Where will information theory be having the most impact in 10-20 years? What new and emerging areas are ripe for the most impact, of the sort that information theory has had on the telecommunications industry over the last 60 years? How should the IEEE Information Theory Society promote high-risk new research directions and broaden the reach of information theory, while continuing to be true to its ideals and insisting on the intellectual rigor that makes its breakthroughs so powerful? These are some of the questions that an ad hoc committee (composed of the present authors) explored over the past two years. We have discussed and debated these questions, and solicited detailed inputs from experts in fields including genomics, biology, economics, and neuroscience. This report is the result of these discussions.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Cost and Benefit of Cooperation (Extended Version)

In a cooperative coding scheme, network nodes work together to achieve higher transmission rates. To obtain a better understanding of cooperation, we consider a model in which two transmitters send rate-limited descriptions of their messages to a "cooperation facilitator", a node that sends back rate-limited descriptions of the pair to each transmitter. This model includes the conferencing encoders model and a prior model from the current authors as special cases. We show that except for a special class of multiple access channels, the gain in sum-capacity resulting from cooperation under this model is quite large. Adding a cooperation facilitator to any such channel results in a network that does not satisfy the edge removal property. An important special case is the Gaussian multiple access channel, for which we explicitly characterize the sum-rate cooperation gain.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the Power of Cooperation: Can a Little Help a Lot? (Extended Version)

In this paper, we propose a new cooperation model for discrete memoryless multiple access channels. Unlike in prior cooperation models (e.g., conferencing encoders), where the transmitters cooperate directly, in this model the transmitters cooperate through a larger network. We show that under this indirect cooperation model, there exist channels for which the increase in sum-capacity resulting from cooperation is significantly larger than the rate shared by the transmitters to establish the cooperation. This result contrasts both with results on the benefit of cooperation under prior models and results in the network coding literature, where attempts to find examples in which similar small network modifications yield large capacity benefits have to date been unsuccessful.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Multi-Resolution Video Streaming in Peer-to-peer Networks

We consider multi-resolution streaming in fully-connected peer-to-peer networks, where transmission rates are constrained by arbitrarily specified upload capacities of the source and peers. We fully characterize the capacity region of rate vectors achievable with arbitrary coding, where an achievable rate vector describes a vector of throughputs of the different resolutions that can be supported by the network. We then prove that all rate vectors in the capacity region can be achieved using pure routing strategies. This shows that coding has no capacity advantage over routing in this scenario.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Network Equivalence in the Presence of an Eavesdropper

We consider networks of noisy degraded wiretap channels in the presence of an eavesdropper. For the case where the eavesdropper can wiretap at most one channel at a time, we show that the secrecy capacity region, for a broad class of channels and any given network topology and communication demands, is equivalent to that of a corresponding network where each noisy wiretap channel is replaced by a noiseless wiretap channel. Thus in this case there is a separation between wiretap channel coding on each channel and secure network coding on the resulting noiseless network. We show with an example that such separation does not hold when the eavesdropper can access multiple channels at the same time, for which case we provide upper and lower bounding noiseless networks.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the Delay Advantage of Coding in Packet Erasure Networks

We consider the delay of network coding compared to routing with retransmissions in packet erasure networks with probabilistic erasures. We investigate the sub-linear term in the block delay required for unicasting $n$ packets and show that there is an unbounded gap between network coding and routing. In particular, we show that delay benefit of network coding scales at least as $\sqrt{n}$. Our analysis of the delay function for the routing strategy involves a major technical challenge of computing the expectation of the maximum of two negative binomial random variables. This problem has been studied previously and we derive the first exact characterization which may be of independent interest. We also use a martingale bounded differences argument to show that the actual coding delay is tightly concentrated around its expectation.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Separation of source-network coding and channel coding in wireline networks

In this paper we prove the separation of source-network coding and channel coding in wireline networks. For the purposes of this work, a wireline network is any network of independent, memoryless, point-to-point, finite-alphabet channels used to transmit dependent sources either losslessly or subject to a distortion constraint. In deriving this result, we also prove that in a general memoryless network with dependent sources, lossless and zero-distortion reconstruction are equivalent provided that the conditional entropy of each source given the other sources is non-zero. Furthermore, we extend the separation result to the case of continuous-alphabet, point-to-point channels such as additive white Gaussian noise (AWGN) channels.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Network Coding: Is zero error always possible?

In this work we study zero vs. epsilon-error capacity in network coding instances. For multicast network coding it is well known that all rates that can be delivered with arbitrarily small error probability can also be delivered with zero error probability; that is, the epsilon-error multicast capacity region and zero-error multicast capacity region are identical. For general network coding instances in which all sources originate at the same source node, Chan and Grant recently showed [ISIT 2010] that, again, epsilon-error communication has no rate advantage over zero-error communication. We start by revisiting the setting of co-located sources, where we present an alternative proof to that given by Chan and Grant. While the new proof is based on similar core ideas, our constructive strategy complements the previous argument.We then extend our results to the setting of index coding, which is a special and representative form of network coding that encapsulates the "source coding with side information" problem. Finally, we consider the "edge removal" problem (recently studied by Jalali, Effros, and Ho in [Allerton 2010] and [ITA 2011]) that aims to quantify the loss in capacity associated with removing a single edge from a given network. Using our proof for co-located sources, we tie the "zero vs. epsilon-error" problem in general network coding instances with the "edge removal" problem. Loosely speaking, we show that the two problem are equivalent.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Theory of Network Equivalence, Parts I and II

A family of equivalence tools for bounding network capacities is introduced. Part I treats networks of point-to-point channels. The main result is roughly as follows. Given a network of noisy, independent, memoryless point-to-point channels, a collection of communication demands can be met on the given network if and only if it can be met on another network where each noisy channel is replaced by a noiseless bit pipe with throughput equal to the noisy channel capacity. This result was known previously for the case of a single-source multicast demand. The result given here treats general demands -- including, for example, multiple unicast demands -- and applies even when the achievable rate region for the corresponding demands is unknown in the noiseless network. In part II, definitions of upper and lower bounding channel models for general channels are introduced. By these definitions, a collection of communication demands can be met on a network of independent channels if it can be met on a network where each channel is replaced by its lower bounding model andonly if it can be met on a network where each channel is replaced by its upper bounding model. This work derives general conditions under which a network of noiseless bit pipes is an upper or lower bounding model for a multiterminal channel. Example upper and lower bounding models for broadcast, multiple access, and interference channels are given. It is then shown that bounding the difference between the upper and lower bounding models for a given channel yields bounds on the accuracy of network capacity bounds derived using those models. By bounding the capacity of a network of independent noisy channels by the network coding capacity of a network of noiseless bit pipes, this approach represents one step towards the goal of building computational tools for bounding network capacities.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Compressive Sensing Over Networks

In this paper, we demonstrate some applications of compressive sensing over networks. We make a connection between compressive sensing and traditional information theoretic techniques in source coding and channel coding. Our results provide an explicit trade-off between the rate and the decoding complexity. The key difference of compressive sensing and traditional information theoretic approaches is at their decoding side. Although optimal decoders to recover the original signal, compressed by source coding have high complexity, the compressive sensing decoder is a linear or convex optimization. First, we investigate applications of compressive sensing on distributed compression of correlated sources. Here, by using compressive sensing, we propose a compression scheme for a family of correlated sources with a modularized decoder, providing a trade-off between the compression rate and the decoding complexity. We call this scheme Sparse Distributed Compression. We use this compression scheme for a general multicast network with correlated sources. Here, we first decode some of the sources by a network decoding technique and then, we use a compressive sensing decoder to obtain the whole sources. Then, we investigate applications of compressive sensing on channel coding. We propose a coding scheme that combines compressive sensing and random channel coding for a high-SNR point-to-point Gaussian channel. We call this scheme Sparse Channel Coding. We propose a modularized decoder providing a trade-off between the capacity loss and the decoding complexity. At the receiver side, first, we use a compressive sensing decoder on a noisy signal to obtain a noisy estimate of the original signal and then, we apply a traditional channel coding decoder to find the original signal.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Concatenated Polar Codes

Polar codes have attracted much recent attention as the first codes with low computational complexity that provably achieve optimal rate-regions for a large class of information-theoretic problems. One significant drawback, however, is that for current constructions the probability of error decays sub-exponentially in the block-length (more detailed designs improve the probability of error at the cost of significantly increased computational complexity \cite{KorUS09}). In this work we show how the the classical idea of code concatenation -- using "short" polar codes as inner codes and a "high-rate" Reed-Solomon code as the outer code -- results in substantially improved performance. In particular, code concatenation with a careful choice of parameters boosts the rate of decay of the probability of error to almost exponential in the block-length with essentially no loss in computational complexity. We demonstrate such performance improvements for three sets of information-theoretic problems -- a classical point-to-point channel coding problem, a class of multiple-input multiple output channel coding problems, and some network source coding problems.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Multiple-access Network Information-flow and Correction Codes

This work considers the multiple-access multicast error-correction scenario over a packetized network with $z$ malicious edge adversaries. The network has min-cut $m$ and packets of length $\ell$, and each sink demands all information from the set of sources $\sources$. The capacity region is characterized for both a "side-channel" model (where sources and sinks share some random bits that are secret from the adversary) and an "omniscient" adversarial model (where no limitations on the adversary's knowledge are assumed). In the "side-channel" adversarial model, the use of a secret channel allows higher rates to be achieved compared to the "omniscient" adversarial model, and a polynomial-complexity capacity-achieving code is provided. For the "omniscient" adversarial model, two capacity-achieving constructions are given: the first is based on random subspace code design and has complexity exponential in $\ell m$, while the second uses a novel multiple-field-extension technique and has $O(\ell m^{|\sources|})$ complexity, which is polynomial in the network size. Our code constructions are "end-to-end" in that all nodes except the sources and sinks are oblivious to the adversaries and may simply implement predesigned linear network codes (random or otherwise). Also, the sources act independently without knowledge of the data from other sources.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Network error correction with unequal link capacities

This paper studies the capacity of single-source single-sink noiseless networks under adversarial or arbitrary errors on no more than z edges. Unlike prior papers, which assume equal capacities on all links, arbitrary link capacities are considered. Results include new upper bounds, network error correction coding strategies, and examples of network families where our bounds are tight. An example is provided of a network where the capacity is 50% greater than the best rate that can be achieved with linear coding. While coding at the source and sink suffices in networks with equal link capacities, in networks with unequal link capacities, it is shown that intermediate nodes may have to do coding, nonlinear error detection, or error correction in order to achieve the network error correction capacity.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On Equivalence Between Network Topologies

One major open problem in network coding is to characterize the capacity region of a general multi-source multi-demand network. There are some existing computational tools for bounding the capacity of general networks, but their computational complexity grows very quickly with the size of the network. This motivates us to propose a new hierarchical approach which finds upper and lower bounding networks of smaller size for a given network. This approach sequentially replaces components of the network with simpler structures, i.e., with fewer links or nodes, so that the resulting network is more amenable to computational analysis and its capacity provides an upper or lower bound on the capacity of the original network. The accuracy of the resulting bounds can be bounded as a function of the link capacities. Surprisingly, we are able to simplify some families of network structures without any loss in accuracy.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On the Separation of Lossy Source-Network Coding and Channel Coding in Wireline Networks

This paper proves the separation between source-network coding and channel coding in networks of noisy, discrete, memoryless channels. We show that the set of achievable distortion matrices in delivering a family of dependent sources across such a network equals the set of achievable distortion matrices for delivering the same sources across a distinct network which is built by replacing each channel by a noiseless, point-to-point bit-pipe of the corresponding capacity. Thus a code that applies source-network coding across links that are made almost lossless through the application of independent channel coding across each link asymptotically achieves the optimal performance across the network as a whole.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On Zero-Error Source Coding with Feedback

We consider the problem of zero error source coding with limited feedback when side information is present at the receiver. First, we derive an achievable rate region for arbitrary joint distributions on the source and the side information. When all source pairs of source and side information symbols are observable with non-zero probability, we show that this characterization gives the entire rate region. Next, we demonstrate a class of sources for which asymptotically zero feedback suffices to achieve zero-error coding at the rate promised by the Slepian-Wolf bound for asymptotically lossless coding. Finally, we illustrate these results with the aid of three simple examples.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Optimal Reverse Carpooling Over Wireless Networks - A Distributed Optimization Approach

We focus on a particular form of network coding, reverse carpooling, in a wireless network where the potentially coded transmitted messages are to be decoded immediately upon reception. The network is fixed and known, and the system performance is measured in terms of the number of wireless broadcasts required to meet multiple unicast demands. Motivated by the structure of the coding scheme, we formulate the problem as a linear program by introducing a flow variable for each triple of connected nodes. This allows us to have a formulation polynomial in the number of nodes. Using dual decomposition and projected subgradient method, we present a decentralized algorithm to obtain optimal routing schemes in presence of coding opportunities. We show that the primal sub-problem can be expressed as a shortest path problem on an \emph{edge-graph}, and the proposed algorithm requires each node to exchange information only with its neighbors.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Capacity Definitions for General Channels with Receiver Side Information

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 not necessarily stationary, ergodic, or information stable. The {\em Shannon capacity} is the highest rate asymptotically achievable with arbitrarily small error probability. The {\em capacity versus outage} is the highest rate asymptotically achievable with a given probability of decoder-recognized outage. The {\em expected capacity} is the highest average rate asymptotically achievable with a single encoder and multiple decoders, where the channel side information determines the decoder in use. As a special case of channel codes for expected rate, the code for capacity versus outage has two decoders: one operates in the non-outage states and decodes all transmitted information, and the other operates in the outage states and decodes nothing. Expected capacity equals Shannon capacity for channels governed by a stationary ergodic random process but is typically greater for general channels. These alternative capacity definitions essentially relax the constraint that all transmitted information must be decoded at the receiver. We derive capacity theorems for these capacity definitions through information density. Numerical examples are provided to demonstrate their connections and differences. We also discuss the implication of these alternative capacity definitions for end-to-end distortion, source-channel coding and separation.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Evolutionary Approaches to Minimizing Network Coding Resources

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 the computational complexity that makes the problem NP-hard. Our experiments show great improvements over the sub-optimal solutions of prior methods. Our new algorithms improve over our previously proposed algorithm in three ways. First, whereas the previous algorithm can be applied only to acyclic networks, our new method works also with networks with cycles. Second, we enrich the set of components used in the genetic algorithm, which improves the performance. Third, we develop a novel distributed framework. Combining distributed random network coding with our distributed optimization yields a network coding protocol where the resources used for coding are optimized in the setup phase by running our evolutionary algorithm at each node of the network. We demonstrate the effectiveness of our approach by carrying out simulations on a number of different sets of network topologies.

0 citations0 reviewsNo code linkedOpen access