We develop a new upper bound on the capacity of the relay channel that is tighter than previously known upper bounds. This upper bound is proved using traditional weak converse techniques involving mutual information inequalities and Gallager-type explicit identification of auxiliary random variables. We show that the new upper bound is strictly tighter than all previous bounds for the Gaussian relay channel with non-zero channel gains. When specialized to the relay channel with orthogonal receiver components, the bound resolves a conjecture by Kim on a class of deterministic relay channels. When further specialized to the class of product-form relay channels with orthogonal receiver components, the bound resolves a generalized version of Cover’s relay channel problem, recovers the recent upper bound for the Gaussian case by Wuet al., and improves upon the recent bounds for the binary symmetric case by Wuet al.and Barneset al., which were obtained using non-traditional geometric proof techniques. For the special class of a relay channel with orthogonal receiver components, we develop another upper bound on the capacity which utilizes an auxiliary receiver and show that it is strictly tighter than the bound by Tandon and Ulukus. Finally, we show through the Gaussian relay channel with i.i.d. relay output sequence that the bound with the auxiliary receiver can be strictly tighter than our main bound.

We establish a new upper bound on the capacity of the relay channel which is tighter than all previous bounds. The upper bound uses traditional weak converse techniques involving mutual information inequalities and identification of auxiliary random variables via past and future channel random variable sequences. We show that the new bound is strictly tighter than all previous bounds for the Gaussian relay channel for every set of non-zero channel gains. When specialized to the class of relay channels with orthogonal receiver components, the bound resolves a conjecture by Kim on a class of deterministic relay channels. When further specialized to the class of product-form relay channels with orthogonal receiver components, the bound resolves a generalized version of Cover's relay channel problem, recovers the recent upper bound for the Gaussian case by Wu et al. and also improves upon the recent bounds for the binary symmetric case by Wu et al. and Barnes et al., which were all obtained using non-traditional geometric proof techniques.

This paper studies lower bounds on the capacity of the relay channel with orthogonal receiver components (also referred to as primitive relay channel). We show that the lower bound in Theorem 7 of Cover and El Gamal, which uses mixed decode-forward and compress-forward strategies, is identical to the lower bound of Chong, Motani and Garg, and is always larger than or equal to the recent lower bound of Mondelli, Hassani and Urbanke. We provide a simplified expression for the lower bound in Theorem 7 of Cover and El Gamal and interpret one of its auxiliary variables as implementing the randomized time-sharing strategy. Next, we compare the lower bound for the Gaussian relay channel with orthogonal receiver components to existing upper bounds. Finally, we disprove a conjecture by Ahlswede and Han on the capacity of the subclass of relay channels with orthogonal receiver components and i.i.d. output. A full version of this paper is accessible at: http://chandra.ie.cuhk.edu.hk/pub/papers/NIT/Prim-Rel-LB.pdf

Shannon showed that to achieve perfect secrecy in point-to-point communication, the message rate cannot exceed the shared secret key rate giving rise to the simple one-time pad encryption scheme. In this paper, we extend this work from point-to-point to networks. We consider a connected network with pairwise communication between the nodes and assume that each node is provided with a certain amount of secret bits before communication commences. An eavesdropper with unlimited computing power has access to all communication and can hack a subset of the nodes not known to the rest of the nodes. We investigate the limits on information-theoretic secure communication with end-to-end encryption for this network. We establish a tradeoff between the secure channel rate (for a node pair) and the secure network rate (sum over all node pair rates) and show that information-theoretic secrecy can be achieved asymptotically if and only if the sum rate of any subset of unhacked channels does not exceed the shared unhacked-secret-bit rate of these channels. We also propose a practical scheme that achieves a good balance of network and channel rates with information-theoretic secrecy guarantee. This work has a wide range of potential applications for which strong secrecy is desired, such as cyber-physical systems, distributed-control systems, and ad-hoc networks.

Shannon showed that to achieve perfect secrecy in point-to-point communication, the message rate cannot exceed the shared secret key rate giving rise to the simple one-time pad encryption scheme. In this paper, we extend this work from point-to-point to networks. We consider a connected network with pairwise communication between the nodes. We assume that each node is provided with a certain amount of secret bits before communication commences. An eavesdropper with unlimited computing power has access to all communication and can hack a subset of the nodes not known to the rest of the nodes. We investigate the limits on information-theoretic secure communication for this network. We establish a tradeoff between the secure channel rate (for a node pair) and the secure network rate (sum over all node pair rates) and show that perfect secrecy can be achieved if and only if the sum rate of any subset of unhacked channels does not exceed the shared unhacked-secret-bit rate of these channels. We also propose two practical and efficient schemes that achieve a good balance of network and channel rates with perfect secrecy guarantee. This work has a wide range of potential applications for which perfect secrecy is desired, such as cyber-physical systems, distributed-control systems, and ad-hoc networks.

The classical problem of supervised learning is to infer an accurate estimate of a target variable Y from a measured variable X using a set of labeled training samples. Motivated by the increasingly distributed nature of data and decision making, this paper considers a variation of this classical problem in which the inference is distributed between two nodes, e.g., a mobile device and a cloud, with a rate constraint on the communication between them. The mobile device observes X and sends a description M of X to the cloud, which computes an estimate Y̑ of Y. We follow the recent minimax learning approach to study this inference problem and show that it corresponds to a one-shot minimax noisy lossy source coding problem. We then establish information theoretic bounds on the risk-rate Lagrangian cost, leading to a general method for designing a near-optimal descriptor-estimator pair. A key ingredient in the proof of our result is a refined version of the strong functional representation lemma previously used to establish several one-shot source coding theorems. Our results show that a naive estimate-compress scheme for rate-constrained inference is not optimal in general. When the distribution of (X, Y) is known and the error is measured by the logarithmic loss, our bounds on the risk-rate Lagrangian cost provide a new one-shot operational interpretation of the information bottleneck. We also demonstrate a way to bound the excess risk of the descriptor-estimator pair obtained by our method.

The classical problem of supervised learning is to infer an accurate predictor of a target variable Y from a measured variable X by using a finite number of labeled training samples. Motivated by the increasingly distributed nature of data and decision making, in this paper we consider a variation of this classical problem in which the prediction is performed remotely based on a rate-constrained description M of X. Upon receiving M, the remote node computes an estimate Y of Y. We follow the recent minimax approach to study this learning problem and show that it corresponds to a one-shot minimax noisy source coding problem. We then establish information theoretic bounds on the risk-rate Lagrangian cost and a general method to design a near-optimal descriptor-estimator pair, which can be viewed as a rate-constrained analog to the maximum conditional entropy principle used in the classical minimax learning problem. Our results show that a naive estimate-compress scheme for rate-constrained prediction is not in general optimal.

We establish the rate region of an extended Gray-Wyner system (EGW) for 2-DMS (X, Y) with two additional decoders having complementary causal side information. We show that the 5-D rate region of the EGW system is equivalent to the 3-D mutual information region consisting of the set of all triples of the form (I(X; U), I(Y; U), I(X, Y; U)) for some pU|X,Y. This correspondence greatly simplifies the exploration of the the extreme points of the rate region. In addition to the operationally significant extreme points of the original Gray-Wyner rate region, which include Wyner's common information, Gács-Körner common information, and the information bottleneck, the extreme points of the rate region for the EGW system also include the Körner graph entropy, the privacy funnel and excess functional information, as well as three new quantities of potential interest. We further show that projections of the mutual information region yield the rate regions for many settings involving a two discrete memoryless source (2-DMS), including lossless source coding with causal side information, distributed channel synthesis, and lossless source coding with a helper. To further motivate the mutual information region itself, we draw analogies between set operations and its extreme points. This allows us to find random variables that can be considered as intersection, difference, and symmetric difference of two random variables. Finally, we establish the rate regions for two related setups to the EGW system, namely, the noncausal EGW system and the lossy EGW system.

This paper shows that for any random variables X and Y, it is possible to represent Y as a function of (X, Z) such that Z is independent of X and I(X; Z| Y) ≤ log(I(X; Y)+1)+4. We use this strong functional representation lemma (SFRL) to establish a tighter bound on the rate needed for one-shot exact channel simulation than was previously established by Harsha et. al., and to establish achievability results for one-shot variable-length lossy source coding and multiple description coding. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand-Pinsker theorem. Finally we present an example in which the SFRL inequality is tight to within 5 bits.

We establish the rate region of an extended Gray-Wyner system for 2-DMS (X, Y) with two additional decoders having complementary causal side information. This extension is interesting because in addition to the operationally significant extreme points of the Gray-Wyner rate region, which include Wyner's common information, Gåcs-Körner common information and information bottleneck, the rate region for the extended system also includes the Körner graph entropy, the privacy funnel and excess functional information, as well as three new quantities of potential interest, as extreme points. To simplify the investigation of the 5-dimensional rate region of the extended Gray-Wyner system, we establish an equivalence of this region to a 3-dimensional mutual information region that consists of the set of all triples of the form (I (X; U), I (Y; U), I (X, Y; U)) for some pu\x, y. We further show that projections of this mutual information region yield the rate regions for many settings involving a 2-DMS, including lossless source coding with causal side information, distributed channel synthesis, and lossless source coding with a helper.

We establish the first known upper bound on the exact and Wyner's common information of n continuous random variables in terms of the dual total correlation between them (which is a generalization of mutual information). In particular, we show that when the pdf of the random variables is log-concave, there is a constant gap of n2 loge + 9n log n between this upper bound and the dual total correlation lower bound that does not depend on the distribution. The upper bound is obtained using a computationally efficient dyadic decomposition scheme for constructing a discrete common randomness variable W from which the n random variables can be simulated in a distributed manner. We then bound the entropy of W using a new measure, which we refer to as the erosion entropy.

Alice selects an arbitrary pdf f and uses a stochastic encoder to generate a prefix-free codeword M, which is sent to Bob so that he can generate a single instance of the random variable X ~ f. We describe a universal coding scheme for this setup which works for any f , and establish an upper bound on its expected codeword length when the pdf f is bounded, orthogonally concave (which includes quasiconcave pdf), and has a finite first absolute moment. A dyadic decomposition scheme is used to express the pdf as a mixture of uniform pdfs over hypercubes. Alice randomly selects a hypercube according to its weight, encodes its position and size into M, and sends it to Bob who generates X uniformly over the hypercube. Compared to previous results on channel simulation, our coding scheme applies to any continuous distribution and does not require two-way communication or shared randomness. Applying our coding scheme to classical simulation of quantum entanglement, we obtain a tighter bound on the average codeword length than previously known.

This paper shows that the slope at each corner point of the capacity region of the general broadcast channel coincides with that of the randomized time division (hence the Marton) inner bound and the Nair-El Gamal (as well as the Körner-Marton) outer bound. We then show that the optimal superposition coding inner bound by Bandemer, El Gamal, and Kim can be simplified to the convex closure of the union of the Cover-Bergmans UX region and the Cover-van der Meulen UV region. Generalizing a result by Hajek and Pursely on the skewed binary symmetric broadcast channel, we show that for binary input broadcast channels, the UV region reduces to time division further simplifying the superposition coding inner bound. Finally we establish necessary and sufficient conditions for the optimality of the superposition inner bound for skewed binary broadcast channels.

We establish the capacity region of several classes of broadcast channels with random state in which the channel to each user is selected from two possible channel state components and the state is known only at the receivers. When the channel components are deterministic, we show that the capacity region is achieved via Marton coding. This channel model does not belong to any class of broadcast channels for which the capacity region was previously known and is useful in studying wireless communication channels when the fading state is known only at the receivers. We then establish the capacity region when the channel components are ordered, e.g., degraded. In particular, we show that the capacity region for the broadcast channel with degraded Gaussian vector channel components is attained via Gaussian input distribution. Finally, we extend the results on ordered channels to two broadcast channel examples with more than two channel components, but show that these extensions do not hold in general.

This paper shows that the capacity region of the continuous-time Poisson broadcast channel is achieved via superposition coding for most channel parameter values. Interestingly, the channel in some subset of these parameter values does not belong to any of the existing classes of broadcast channels for which superposition coding is optimal (e.g., degraded, less noisy, and more capable). In particular, we introduce the notion of effectively less noisy broadcast channel and show that it implies less noisy but is not in general implied by more capable. For the rest of the channel parameter values, we show that there is a gap between Marton’s inner bound and the UV outer bound.

This paper shows that the capacity region of the continuous-time Poisson broadcast channel is achieved via superposition coding for most channel parameter values. Interestingly, the channel in some subset of these parameter values does not belong to any of the existing classes of broadcast channels for which superposition coding is optimal (e.g., degraded, less noisy, more capable). For the rest of the channel parameter values, we show that there is a gap between Marton's inner bound and the UV outer bound.

This paper shows that the Hirschfeld-Gebelein- Rényi maximal correlation between the message and the ciphertext provides good secrecy guarantees for cryptosystems that use short keys. We first establish a bound on the eavesdropper's advantage in guessing functions of the message in terms of maximal correlation and the Rényi entropy of the message. This result implies that the maximal correlation is stronger than the notion of entropic security introduced by Russell and Wang. We then show that a small maximal correlation ρ can be achieved via a randomly generated cipher with key length ≈ 2 log(1/ρ), independent of the message length, and by a stream cipher with key length 2 log(1/ρ) + logn + 2 for a message of length n. We establish a converse showing that these ciphers are close to optimal. This is in contrast with the entropic security for which there is a gap between the lower and upper bounds. Finally, we show that a small maximal correlation implies secrecy with respect to several mutual information-based criteria but is not necessarily implied by them. Hence, maximal correlation is a stronger and more practically relevant measure of secrecy than the mutual information.

The optimal rate region for interference networks is characterized when encoding is restricted to random code ensembles with superposition coding and time sharing. A simple simultaneous nonunique decoding rule, under which each receiver decodes for the intended message as well as the interfering messages, is shown to achieve this optimal rate region regardless of the relative strengths of signal, interference, and noise. This result implies that the Han-Kobayashi bound, the best known inner bound on the capacity region of the two-user pair interference channel, cannot be improved merely by using the optimal maximum likelihood decoder.

This paper shows that the Maddah-Ali–Tse (MAT) scheme, which achieves the symmetric capacity of two example broadcast channels with strictly causal state information at the transmitter, is a simple special case of the Shayevitz–Wigger (SW) scheme for the broadcast channel with generalized feedback, which involves block Markov coding, Gray–Wyner compression, superposition coding, and Marton coding. Focusing on the class of symmetric broadcast channels with state, we derive an expression for the maximum achievable symmetric rate using the SW scheme. We show that the MAT results for the two-receiver case can be recovered by evaluating this expression for the special case in which superposition coding and Marton coding are not used. We then introduce a new broadcast channel example that shares many features of the MAT examples. We show that another special case of our maximum symmetric rate expression in which superposition coding is also used attains a higher symmetric rate than the MAT scheme. The symmetric capacity of this new example is not known, however.

Consider a Gaussian relay network where a source node communicates to a destination node with the help of several layers of relays. Recent work has shown that compress-and-forward-based strategies can achieve the capacity of this network within an additive gap. Here, the relays quantize their received signals at the noise level and map them to random Gaussian codebooks. The resultant gap to capacity is independent of the SNRs of the channels in the network and the topology, but is linear in the total number of nodes. In this paper, we provide an improved lower bound on the rate achieved by the compress-and-forward-based strategies (noisy network coding in particular) in arbitrary Gaussian relay networks, whose gap to capacity depends on the network not only through the total number of nodes but also through the degrees of freedom of the min cut of the network. We illustrate that for many networks, this refined lower bound can lead to a better approximation of the capacity. In particular, we demonstrate that it leads to a logarithmic rather than linear capacity gap in the total number of nodes for certain classes of layered networks. The improvement comes from quantizing the received signals of the relays at a resolution decreasing with the total number of nodes in the network. This suggests that the rule-of-thumb in the literature of quantizing the received signals at the noise level can be highly suboptimal.

Existing fixed-length feedback communication schemes are either specialized to particular channels (Schalkwijk-Kailath, Horstein), or apply to general channels but either have high coding complexity (block feedback schemes) or are difficult to analyze (posterior matching). This paper introduces a new fixed-length feedback coding scheme which achieves the capacity for all discrete memoryless channels, has an error exponent that approaches the sphere packing bound as the rate approaches the capacity, and has O(n log n) coding complexity. These benefits are achieved by judiciously combining features from previous schemes with new randomization technique and encoding/decoding rule. These new features make the analysis of the error probability for the new scheme easier than for posterior matching.

This paper establishes the capacity region of a class of broadcast channels with random state in which each channel component is selected from two possible functions and each receiver knows its state sequence. This channel model does not fit into any class of broadcast channels for which the capacity region was previously known and is useful in studying wireless communication channels when the fading state is known only at the receivers. The capacity region is shown to coincide with the UV outer bound and is achieved via Marton coding.

This paper introduces the notion of exact common information, which is the minimum description length of the common randomness needed for the exact distributed generation of two correlated random variables (X, Y). We introduce the quantity G(X; Y) = minX→W→YH(W) as a natural bound on the exact common information and study its properties and computation. We then introduce the exact common information rate, which is the minimum description rate of the common randomness for the exact generation of a 2-DMS (X, Y). We give a multiletter characterization for it as the limit Ḡ(X; Y) = limn→∞(1/n)G(Xn; Yn). While in general Ḡ(X; Y) is greater than or equal to the Wyner common information, we show that they are equal for the Symmetric Binary Erasure Source. We do not know, however, if the exact common information rate has a single letter characterization in general.

Existing feedback communication schemes are either specialized to particular channels (Schalkwijk-Kailath, Horstein), apply to general channels but have high coding complexity (block feedback schemes), or are difficult to analyze (posterior matching). This paper introduces a feedback coding scheme that achieves the capacity for all discrete memoryless channels with a bound on the error exponent that approaches the sphere packing bound as the rate approaches the capacity and coding complexity of only O(n log n). These benefits are attained by combining features from previous schemes with new randomization technique and decoding rule.

This paper describes GridSpice, a scalable open-source simulation framework for modeling, designing, and planning of the smart grid. GridSpice seamlessly integrates existing electric power simulation tools to enable modeling of large electric networks that blur the boundaries between generation, transmission, distribution, and markets. This is achieved via a cloud-based architecture that allows for parallelizing large simulation jobs across many virtual machines using a pay-as-you-go model. GridSpice simulations can be managed through a Representational State Transfer (REST) application programming interface (API), or through a Python library, allowing users to run simulations programmatically and interface with disparate data inputs, energy management systems (EMS), distribution management systems (DMS), and postprocessing tools. These capabilities make GridSpice an ideal tool for the development and testing of new grid control and optimization algorithms. GridSpice also provides an easy-to-use browser-based interface to allow novice users to begin without any setup or configuration on their local PC. A first implementation of the GridSpice framework integrates Gridlab-D and MATPOWER as simulation tools, and has been used for projects including optimizing the placement of distributed generation and developing optimal dispatch schedules for flexible loads. The GridSpice framework and Gridlab-D are freely available in open-source under the BSD license.

Motivated by the broadcast view of the interference channel, the new problem of communication with disturbance constraints is formulated. The rate-disturbance region is established for the single constraint case and the optimal encoding scheme turns out to be the same as the Han-Kobayashi scheme for the two user-pair interference channel. This result is extended to the Gaussian vector (multiple-input and multiple-output) case. For the case of communication with two disturbance constraints, inner and outer bounds on the rate-disturbance region for a deterministic model are established. The inner bound is achieved by an encoding scheme that involves rate splitting, Marton coding, and superposition coding, and is shown to be optimal in several nontrivial cases. This encoding scheme can be readily applied to discrete memoryless interference channels and motivates a natural extension of the Han-Kobayashi scheme to more than two user pairs.

We establish several new results on Marton's inner bound on the capacity region of the general broadcast channel. Inspired by the fact that Marton's coding scheme without superposition coding is optimal in the Gaussian case, we consider the class of binary input degraded broadcast channels with no common message that have the same property. We characterize this class. We also establish new properties of Marton's inner bound that help restrict the search space for computing the Marton sum rate. In particular, we establish an extension of the XOR case of the binary inequality of Nair, Wang, and Geng.

This paper considers the problem of communicating over a relay channel with state when noncausal state information is partially available at the nodes. We first establish a lower bound on the achievable rates based on noisy network coding and Gelfand-Pinsker coding, and show that it provides an alternative characterization of a previously known bound. We then introduce the class of state-decoupled relay channels and show that our lower bound is tight for a subclass of semideterministic channels. We also compute the capacity for two specific examples of this subclass - a channel with multiplicative binary fading and a channel with additive Gaussian interference. These examples are not special cases of previous classes of semideterministic relay channels with known capacity.

This article describes a sensor network approach to tracking a single object in the presence of static and moving occluders using a network of cameras. To conserve communication bandwidth and energy, we combine a task-driven approach with camera subset selection. In the task-driven approach, each camera first performs simple local processing to detect the horizontal position of the object in the image. This information is then sent to a cluster head to track the object. We assume the locations of the static occluders to be known, but only prior statistics on the positions of the moving occluders are available. A noisy perspective camera measurement model is introduced, where occlusions are captured through occlusion indicator functions. An auxiliary particle filter that incorporates the occluder information is used to track the object. The camera subset selection algorithm uses the minimum mean square error of the best linear estimate of the object position as a metric, and tracking is performed using only the selected subset of cameras. Using simulations and preselected subsets of cameras, we investigate (i) the dependency of the tracker performance on the accuracy of the moving occluder priors, (ii) the trade-off between the number of cameras and the occluder prior accuracy required to achieve a prescribed tracker performance, and (iii) the importance of having occluder priors to the tracker performance as the number of occluders increases. We find that computing moving occluder priors may not be worthwhile, unless it can be obtained cheaply and to high accuracy. We also investigate the effect of dynamically selecting the subset of camera nodes used in tracking on the tracking performance. We show through simulations that a greedy selection algorithm performs close to the brute-force method and outperforms other heuristics, and the performance achieved by greedily selecting a small fraction of the cameras is close to that of using all the cameras.

This paper establishes inner bounds on the secrecy capacity regions for the general three-receiver broadcast channel with one common and one confidential message sets. We consider two setups. The first is when the confidential message is to be sent to two receivers and kept secret from the third receiver. Achievability is established using indirect decoding, Wyner wiretap channel coding, and the new idea of generating secrecy from a publicly available superposition codebook. The inner bound is shown to be tight for a class of reversely degraded broadcast channels and when both legitimate receivers are less noisy than the third receiver. The second setup investigated in this paper is when the confidential message is to be sent to one receiver and kept secret from the other two receivers. Achievability in this case follows from Wyner wiretap channel coding and indirect decoding. This inner bound is also shown to be tight for several special cases.

A lower bound on the secrecy capacity of the wiretap channel with state information available causally at both the encoder and the decoder is established. The lower bound is shown to be strictly larger than that for the noncausal case by Liu and Chen. Achievability is proved using block Markov coding, Shannon strategy, and key generation from common state information. The state sequence available at the end of each block is used to generate a key to enhance the transmission rate of the confidential message in the following block. An upper bound on the secrecy capacity when the state is available noncausally at the encoder and the decoder is established and is shown to coincide with the aforementioned lower bound for several classes of wiretap channels with state.

The paper establishes the capacity region of the Gaussian interference channel with many transmitter-receiver pairs constrained to use point-to-point codes. The capacity region is shown to be strictly larger in general than the achievable rate regions when treating interference as noise, using successive interference cancellation decoding, and using joint decoding. In a spatial network where the nodes are distributed according to a Poisson point process and the channel path loss exponent is β >; 2, it is shown that the density of users that can be supported by treating interference as noise can scale no faster than B2/βas the bandwidth B grows, while the density of users can scale linearly with B under optimal decoding.

The problem of communication with disturbance constraints is introduced. The rate-disturbance region is established for the single constraint case. The optimal encoding scheme turns out to be the same as the Han-Kobayashi scheme for the two user-pair interference channel. For communication with two disturbance constraints, a coding scheme and a corresponding inner bound for the deterministic case are presented. The results suggest a natural way to obtain a new inner bound on the capacity region of the interference channel with more than two user pairs.

The paper establishes the capacity region of the Gaussian interference channel with many transmitter-receiver pairs constrained to use point-to-point codes. The capacity region is shown to be strictly larger in general than the achievable rate regions when treating interference as noise, using successive interference cancellation decoding, and using joint decoding. The gains in coverage and achievable rate using the optimal decoder are analyzed in terms of ensemble averages using stochastic geometry. In a spatial network where the nodes are distributed according to a Poisson point process and the channel path loss exponent is β >; 2, it is shown that the density of users that can be supported by treating interference as noise can scale no faster than B2/βas the bandwidthBgrows, while the density of users can scale linearly with B under optimal decoding.

An inner bound to the capacity region of a class of deterministic interference channels with three user pairs is presented. The key idea is to simultaneously decode the combined interference signal and the intended message at each receiver. It is shown that this interference-decoding inner bound is tight under certain strong interference conditions. The inner bound is also shown to strictly contain the inner bound obtained by treating interference as noise, which includes interference alignment for deterministic channels. The gain comes from judicious analysis of the number of combined interference sequences in different regimes of input distributions and message rates. Finally, the inner bound is generalized to the case where each channel output is observed through a noisy channel.

A noisy network coding scheme for communicating messages between multiple sources and destinations over a general noisy network is presented. For multi-message multicast networks, the scheme naturally generalizes network coding over noiseless networks by Ahlswede, Cai, Li, and Yeung, and compress-forward coding for the relay channel by Cover and El Gamal to discrete memoryless and Gaussian networks. The scheme also extends the results on coding for wireless relay networks and deterministic networks by Avestimehr, Diggavi, and Tse, and coding for wireless erasure networks by Dana, Gowaikar, Palanki, Hassibi, and Effros. The scheme involves lossy compression by the relay as in the compress-forward coding scheme for the relay channel. However, unlike previous compress-forward schemes in which independent messages are sent over multiple blocks, the same message is sent multiple times using independent codebooks as in the network coding scheme for cyclic networks. Furthermore, the relays do not use Wyner-Ziv binning as in previous compress-forward schemes, and each decoder performs simultaneous decoding of the received signals from all the blocks without uniquely decoding the compression indices. A consequence of this new scheme is that achievability is proved simply and more generally without resorting to time expansion to extend results for acyclic networks to networks with cycles. The noisy network coding scheme is then extended to general multi-message networks by combining it with decoding techniques for the interference channel. For the Gaussian multicast network, noisy network coding improves the previously established gap to the cutset bound. We also demonstrate through two popular Gaussian network examples that noisy network coding can outperform conventional compress-forward, amplify-forward, and hash-forward coding schemes.

An inner bound to the capacity region of a class of three user pair deterministic interference channels is presented. The key idea is to simultaneously decode the combined interference signal and the intended message at each receiver. It is shown that this interference-decoding inner bound strictly contains the inner bound obtained by treating interference as noise, which includes interference alignment for deterministic channels. The gain comes from judicious analysis of the number of combined interference sequences in different regimes of input distributions and message rates.

A lower bound on the secrecy capacity of the wiretap channel with state information available causally at both the encoder and decoder is established. The lower bound is shown to be strictly larger than that for the noncausal case by Liu and Chen. Achievability is proved using block Markov coding, Shannon strategy, and key generation from common state information. The state sequence available at the end of each block is used to generate a key, which is used to enhance the transmission rate of the confidential message in the following block. An upper bound on the secrecy capacity when the state is available noncausally at the encoder and decoder is established and is shown to coincide with the lower bound for several classes of wiretap channels with state.

In this paper, we study the Nair-El Gamal outer bound and Marton's inner bound for general two-receiver broadcast channels. We show that the Nair-El Gamal outer bound can be made fully computable. For the inner bound, we show that, unlike in the Gaussian case, for a degraded broadcast channel even without a common message, Marton's coding scheme without a superposition variable is in general insufficient for obtaining the capacity region. Further, we prove various results that help to restrict the search space for computing the sum-rate for Marton's inner bound. We establish the capacity region along certain directions and show that it coincides with Marton's inner bound. Lastly, we discuss an idea that may lead to a larger inner bound.

Noisy network coding unifies network coding by Ahlswede, Cai, Li, and Yeung for noiseless networks and compress-forward by Cover and El Gamal for noisy relay channels. In particular, it achieves the best known capacity inner bounds for multi-source multicast networks including deterministic networks by Avestimehr, Diggavi, and Tse and erasure networks by Dana, Gowaikar, Palanki, Hassibi, and Effros. This paper extends noisy network coding for multicast networks to networks with general message demand by combining the underlying noisy network coding scheme with decoding techniques for interference channels. At one extreme, noisy network coding is combined with simultaneous decoding, while at the other extreme interference is treated as noise. The potential of noisy network coding as a canonical building block for wireless networks is demonstrated via three examples of Gaussian networks that have drawn recent attentions.

A 3-node lossy source coding problem for a 2-DMS (X1, X2) is considered. Source nodes 1 and 2 observe X1and X2, respectively, and each wishes to reconstruct the other source with a prescribed distortion. To achieve these goals, nodes 1 and 2 send descriptions of their sources to relay node 3. The relay node then broadcasts a joint description to the source nodes. A cutset outer bound and a compress-linear code inner bound are established and shown to coincide in several special cases. A compute-compress inner bound is then presented and shown to outperform the compress-linear code in some cases. An outer bound based on Kaspi's converse for the two-way source coding problem is shown to be strictly tighter than the cutset outer bound.

This paper proposes a systematic strategy to efficiently explore the design space of field-programmable gate array (FPGA) routing architectures. The key idea is to use stochastic methods to quickly locate near-optimal solutions in designing FPGA routing architectures without exhaustively enumerating all design points. The main objective of this paper is not as much about the specific numerical results obtained, as it is to show the applicability and effectiveness of the proposed optimization approach. To demonstrate the utility of the proposed stochastic approach, we developed the tool for optimizing routing architecture (TORCH) software based on the versatile place and route tool. Given FPGA architecture parameters and a set of benchmark designs, TORCH simultaneously optimizes the routing channel segmentation and switch box patterns using the performance metric of average interconnect power-delay product estimated from placed and routed benchmark designs. Special techniques - such as incremental routing, infrequent placement, multi-modal move selection, and parallelized metric evaluation - are developed to reduce the overall run time and improve the quality of results. Our experimental results have shown that the stochastic design strategy is quite effective in co-optimizing both routing channel segmentation and switch patterns. With the optimized routing architecture, relative to the performance of our chosen architecture baseline, TORCH can achieve average improvements of 24% and 15% in delay and power consumption for the 20 largest Microelectronics Center of North Carolina benchmark designs, and 27% and 21% for the eight benchmark designs synthesized with the Altera Quartus II University Interface Program tool. Additionally, we found that the average segment length in an FPGA routing channel should decrease with technology scaling. Finally, we demonstrate the versatility of TORCH by illustrating how TORCH can be used to optimize other aspects of the routing architecture in an FPGA.

In this paper, an information theoretic formulation of the distributed averaging problem previously studied in computer science and control is presented. We assume a network with$m$nodes each observing a white Gaussian noise (WGN) source. The nodes communicate and perform local processing with the goal of computing the average of the sources to within a prescribed mean squared error distortion. The network rate distortion function$R^{\ast }(D)$for a two-node network with correlated Gaussian sources is established. A general cutset lower bound on$R^{\ast }(D)$is established and shown to be achievable to within a factor of$2$via a centralized protocol over a star network. A lower bound on the network rate distortion function for distributed weighted-sum protocols, which is larger in order than the cutset bound by a factor of$\log m$, is established. An upper bound on the network rate distortion function for gossip-base weighted-sum protocols, which is only$\log \log m$larger in order than the lower bound for a complete graph network, is established. The results suggest that using distributed protocols results in a factor of$\log m$increase in order relative to centralized protocols.

Certain deterministic interference channels have been shown to accurately model Gaussian interference channels in the asymptotic low-noise regime. Motivated by this correspondence, we investigate a K user-pair, cyclically symmetric, deterministic interference channel in which each receiver experiences interference only from its neighboring transmitters (Wyner model). We establish the sum capacity for a large set of channel parameters, thus generalizing previous results for the 2-pair case.

Achievable secrecy rate regions for the general 3-receiver broadcast channel with one common and one confidential message sets are established. We consider two setups: (i) when the confidential message is to be sent to two of the receivers and the third receiver is an eavesdropper; and (ii) when the confidential message is to be sent to one of the receivers and the other two receivers are eavesdroppers. We show that our secrecy rate regions are optimum for some special cases.

We investigate distributed source coding of two correlated sources X and Y where messages are passed to a decoder in a cascade fashion. The encoder of X sends a message at rate R1 to the encoder of Y. The encoder of Y then sends a message to the decoder at rate R2based both on Y and on the message it received about X. The decoder's task is to estimate a function of X and Y. For example, we consider the minimum mean squared-error distortion when encoding the sum of jointly Gaussian random variables under these constraints. We also characterize the rates needed to reconstruct a function of X and Y losslessly. Our general contribution toward understanding the limits of the cascade multiterminal source coding network is in the form of inner and outer bounds on the achievable rate region for satisfying a distortion constraint for an arbitrary distortion function d(x, y, z). The inner bound makes use of a balance between two encoding tactics—relaying the information about X and recompressing the information about X jointly with Y. In the Gaussian case, a threshold is discovered for identifying which of the two extreme strategies optimizes the inner bound. Relaying outperforms recompressing the sum at the relay for some rate pairs if the variance of X is greater than the variance of Y.

An information theoretic formulation of distributed averaging is presented. We assume a network with m nodes each observing an i.i.d. source; the nodes communicate and perform local processing with the goal of computing the average of the sources to within a prescribed mean squared error distortion. The network rate distortion function R* (D) for a 2-node network with correlated Gaussian sources is established. A general cutset lower bound on R* (D) with independent Gaussian sources is established and shown to be achievable to within a factor of 2 via a centralized protocol. A lower bound on the network rate distortion function for distributed weighted-sum protocols that is larger than the cutset bound by a factor of log m is established. An upper bound on the expected network rate distortion function for gossip-based weighted-sum protocols that is only a factor of log log m larger than this lower bound is established. The results suggest that using distributed protocols results in a factor of log m increase in communication relative to centralized protocols.

Korner and Marton established the capacity region for the two-receiver broadcast channel with degraded message sets. Recent results and conjectures suggest that a straightforward extension of the Korner-Marton region to more than two receivers is optimal. This paper shows that this is not the case. We establish the capacity region for a class of three-receiver broadcast channels with two-degraded message sets and show that it can be strictly larger than the straightforward extension of the Korner-Marton region. The idea is to split the private message into two parts, superimpose one part onto the ldquocloud centerrdquo representing the common message, and superimpose the second part onto the resulting ldquosatellite codeword.rdquo One of the receivers finds the common message directly by decoding the ldquocloud center,rdquo a second receiver finds itindirectlyby decoding a satellite codeword, and a third receiver finds it by jointly decoding the transmitted codeword. This idea is then used to establish new inner and outer bounds on the capacity region of the general three-receiver broadcast channel with two and three degraded message sets. We show that these bounds are tight for some nontrivial cases. The results suggest that finding the capacity region of the three-receiver broadcast channel with degraded message sets is at least as hard finding as the capacity region of the general two-receiver broadcast channel with common and private message.

This paper describes a new programmable routing fabric for field-programmable gate arrays (FPGAs). Our results show that an FPGA using this fabric can achieve 1.57 times lower dynamic power consumption and 1.35 times lower average net delays with only 9% reduction in logic density over a baseline island-style FPGA implemented in the same 65-nm CMOS technology. These improvements in power and delay are achieved by 1) using only short interconnect segments to reduce routed net lengths, and 2) reducing interconnect segment loading due to programming overhead relative to the baseline FPGA without compromising routability. The new routing fabric is also well-suited to monolithically stacked 3-D-IC implementation. It is shown that a 3-D-FPGA using this fabric can achieve a 3.3 times improvement in logic density, a 2.51 times improvement in delay, and a 2.93 times improvement in dynamic power consumption over the same baseline 2-D-FPGA.

A design tool for routing channel segmentation in island-style FPGAs is presented. Given the FPGA architecture parameters and a set of benchmark designs, the tool optimizes routing channel segmentation using the average interconnect power-delay product as a performance metric estimated from placed and routed designs. A simulated-annealing procedure is used, whereby segmentation is incrementally changed in each iteration, the benchmark designs are mapped using VPR, and the performance metric is computed to decide whether to accept or reject the new segmentation. Run time is significantly reduced by using incremental routing in each iteration and parallelizing the metric evaluation. Experimental results using the MCNC benchmark designs demonstrate an average of 22% and 15% reduction in delay and power relative to a baseline segmentation. The results also show that average segment length should decrease with technology scaling. Finally, we demonstrate how the tool can be used to optimize other aspects of programmable routing in an FPGA

Körner and Marton established the capacity region for the 2-receiver broadcast channel with degraded message sets. Recent results and conjectures suggest that a straightforward extension of the Körner-Marton region to more than 2 receivers is optimal. This paper shows that this is not the case. We establish the capacity region for a class of 3-receiver broadcast channels with 2 degraded message sets and show that it can be strictly larger than the straightforward extension of the Körner-Marton region. The key new idea is indirect decoding, whereby a receiver who cannot directly decode a cloud center, finds it indirectly by decoding satellite codewords. This idea is then used to establish new inner bounds on the capacity region of the general 3-receiver broadcast channel with 2 and 3 degraded message sets. These bounds are tight for some nontrivial cases.

A previous study on the benefits of monolithically stacked 3D-FPGA has estimated a 3.2x improvement in logic density, a 1.7x improvement in delay, and a 1.7x improvement in dynamic power consumption over a baseline 2D-FPGA with no change in architecture. This paper describes a new routing fabric and shows that a 3D-FPGA using this fabric can achieve a 3.3x improvement in logic density, a 2.35x improvement in delay, and a 2.82x improvement in dynamic power consumption over the same baseline 2D-FPGA. The additional improvements in delay and power consumption are achieved by reducing net loading in several ways: (i) Only Single and Double interconnect segments are used. This reduces the total interconnect length used to implement each net. (ii) The routing fabric is hierarchical. Each logic block's inputs and outputs connect first to local segments. These segments can be then programmably connected to local segments in neighboring routing blocks via programmable buffers and/or to interconnect segments in routing channels via muxes with buffered outputs. (iii) Interconnect segments can be directly connected to form longer segments using programmable buffers without going through routing blocks. (iv) The routing block provides switching capability beyond that of a conventional switch box. A 3D-FPGA using this new routing fabric can be realized by stacking two configuration memory layers and a switch layer on top of a standard CMOS layer with a total of 12 metal layers interspersed between them. A CAD flow based on VPR with appropriate modifications to the routing graph generation and routing algorithm is developed and used in the performance analysis.

This paper describes a sensor network approach to tracking a single object in the presence of static and moving occluders using a network of cameras. To conserve communication bandwidth and energy, each camera first performs simple local processing to reduce each frame to a scan line. This information is then sent to a cluster head to track a point object. We assume the locations of the static occluders to be known, but only prior statistics on the positions of the moving occluders are available. A noisy perspective camera measurement model is presented, where occlusions are captured through an occlusion indicator function. An auxiliary particle filter that incorporates the occluder information is used to track the object. Using simulations, we investigate (i) the dependency of the tracker performance on the accuracy of the moving occluder priors, (ii) the tradeoff between the number of cameras and the occluder prior accuracy required to achieve a prescribed tracker performance, and (iii) the importance of having occluder priors to the tracker performance as the number of occluders increases. We generally find that computing moving occluder priors may not be worthwhile, unless it can be obtained cheaply and to a reasonable accuracy. Preliminary experimental results are provided.

This paper considers a multiple-access channel with two state components, where the first sender knows only the first state component, the second sender knows only the second component, and the receiver knows both components. The notion of adaptive-rate capacity is introduced to characterize the set of achievable rates when the state is fixed in each transmission block but can vary between blocks. Single-letter characterizations of the adaptive-rate capacity region for the discrete-memoryless and the Gaussian models are established. The expected adaptive sum-rate capacity is compared to the ergodic sum-rate capacities when the senders have complete and partial state information, and to the sum-rate capacity of the compound MAC. This comparison shows that the adaptive sum-rate capacity can be close to the ergodic capacity and much higher than the sum-rate capacity of the compound MAC.

This paper establishes necessary and sufficient conditions for reliable transmission of a source over a relay channel when source side information is available non-causally (a) only at the receiver, (b) only at the relay, or (c) at both the relay and the receiver. For the cases of side information only at the receiver and at both the relay and the receiver, we establish tight necessary and sufficient conditions that apply to any relay channel and show that source-channel separation is optimal. When side information is available only at the relay, we establish a necessary condition for reliable transmission and show that it is tight for the class of degraded relay channels and that source-channel separation is optimal in this case.

The performance benefits of a monolithically stacked three-dimensional (3-D) field-programmable gate array (FPGA), whereby the programming overhead of an FPGA is stacked on top of a standard CMOS layer containing logic blocks (LBs) and interconnects, are investigated. A Virtex-II-style two-dimensional (2-D) FPGA fabric is used as a baseline architecture to quantify the relative improvements in logic density, delay, and power consumption achieved by such a 3-D FPGA. It is assumed that only the switch transistor and configuration memory cells can be moved to the top layers and that the 3-D FPGA employs the same LB and programmable interconnect architecture as the baseline 2-D FPGA. Assuming they are les 0.7, the area of a static random-access memory cell and switch transistors having the same characteristics as n-channel metal-oxide-semiconductor devices in the CMOS layer are used. It is shown that a monolithically stacked 3-D FPGA can achieve 3.2 times higher logic density, 1.7 times lower critical path delay, and 1.7 times lower total dynamic power consumption than the baseline 2-D FPGA fabricated in the same 65-nm technology node

The paper investigates the effect of link delays on the capacity of relay networks. The relay-with-delay is defined as a relay channel with relay encoding delay d isin Z of units, or equivalently, a delay of units on the link from the sender to the relay, zero delay on the links from the transmitter to the receiver and from the relay to the receiver, and zero relay encoding delay. Two special cases are studied. The first is the relay-with-unlimited look-ahead, where each relay transmission can depend on its entire received sequence, and the second is the relay-without-delay, where the relay transmission can depend only on current and past received symbols, i.e., d=0. Upper and lower bounds on capacity for these two channels that are tight in some cases are presented. It is shown that the cut-set bound for the classical relay channel, corresponding to the case where d=1, does not hold for the relay-without-delay. Further, it is shown that instantaneous relaying can be optimal and can achieve higher rates than the classical cut-set bound. Capacity for the classes of degraded and semi-deterministic relay-with-unlimited-look-ahead and relay-without-delay are established. These results are then extended to the additive white Gaussian noise (AWGN) relay-with-delay case, where it is shown that for any dles0, capacity is achieved using amplify-and-forward when the channel from the sender to the relay is sufficiently weaker than the other two channels. In addition, it is shown that a superposition of amplify-and-forward and decode-and-forward can achieve higher rates than the classical cut-set bound. The relay-with-delay model is then extended to feedforward relay networks. It is shown that capacity is determined only by the relative delays of paths from the sender to the receiver and not by their absolute delays. A new cut-set upper bound that generalizes both the classical cut-set bound for the classical relay and the upper bound for the relay-without-delay on capacity is established.

The thirty-four papers in this special issue are devoted to models, theories, and codes for relaying and cooperation in communication networks. The demand for large, more efficient, reliable, and cost effective communication networks is motivating new network architectures for cellular and wireless communications as well as cognitive radio and sensor networks.

An outer bound to the capacity region of the two-receiver discrete memoryless broadcast channel is given. The outer bound is tight for all cases where the capacity region is known. When specialized to the case of no common information, this outer bound is contained in the Koumlrner-Marton outer bound. This containment is shown to be strict for the binary skew-symmetric broadcast channel. Thus, this outer bound is in general tighter than all other known outer bounds.

The performance benefits of a monolithically stacked 3D-FPGA, whereby the programming overhead of an FPGA is stacked on top of a standard CMOS layer containing the logic blocks and interconnects, are investigated. A Virtex-II style 2D-FPGA fabric is used as a baseline for quantifying the relative improvements in logic density, delay, and power consumption achieved by such a 3D-FPGA. It is assumed that only the pass-transistor switches and configuration memory cells can be moved to the top layers and that the 3D-FPGA employs the same logic block and programmable interconnect architecture as the baseline 2D-FPGA. Assuming a configuration memory cell that is ≤ 0.7 the area of an SRAM cell and pass-transistor switches having the same characteristics as nMOS devices in the CMOS layer are used, it is shown that a monolithically stacked 3D-FPGA can achieve 3.2 times higher logic density, 1.7 times lower critical path delay, and 1.7 times lower total dynamic power consumption than the baseline 2D-FPGA fabricated in the same 65nm technology node.

The process of DNA sequencing-by-synthesis and its non-idealities are modeled as a noisy switched linear system parameterized by the unknown DNA sequence. The base-calling problem is then formulated as a parameter detection problem. As this system can have long memory, performing exact maximum-likelihood decoding is computationally prohibitive. An approximate ML method applied to experimental Pyrosequencing data demonstrates reliable read lengths exceeding 200 bases, which is significantly longer than that achieved by current methods

Abstract — Gupta and Kumar showed that throughput in a static random wireless network increases with the amount of hopping. In a subsequent paper (2004), it was shown that although throughput benefits from a large number of hops, this comes at the expense of higher delay. Separately, several studies have shown that in ad hoc networks, transmission energy decreases as hopping increases. However, when transceiver circuit energy is also taken into account, hopping as much as possible no longer maximizes energy efficiency and the optimal amount of hopping depends on the topology and size of the network. This paper attempts to unify these earlier results by establishing the optimal hopping for energy efficiency along with throughput and delay. A random network model with n nodes in area A(n) is considered. The effect of interference is captured by the Physical model and the signal is assumed to decay with distance r as r −δ, δ> 1. Both transmission and transceiver circuit energy are taken into account. Optimal trade-offs between throughput, delay and energy-per-bit scaling for this random network model are established. These results show that the amount of hopping still determines the optimal trade-off and yield the amount of hopping that should be used to achieve any point of the optimal trade-off. In a constant area network, where A(n) = 1, Θ(1) hops result in the best energy and delay scaling of Θ(1) at the cost of the worst throughput scaling of Θ(1/n). At the other “ extreme, pn/ in” a constant density network, where A(n) = n, Θ log n hops result in the best throughput scaling of Θ ` 1 / √ n log n ´ and the best energy scaling but at the cost of the worst delay scaling. For intermediate values of A(n), p “p ” B(n) = Θ min{A(n), n / log n} hops should be used “ to obtain the minimum energy-per-bit scaling, which is Θ A(n) δ B(n) 1 2 −δ

We characterize the rate distortion function for the source coding with decoder side information setting when the i-th reconstruction symbol is allowed to depend only on the first i + d side information symbols, for some finite lookahead d, in addition to the index from the encoder. For the case of causal side information, i.e., d = 0, we find that the penalty of causality is the omission of the subtracted mutual information term in the Wyner-Ziv rate distortion function. For d > 0, we derive a computable "infinite-letter" expression for the rate distortion function. When specialized to the near-lossless case, our results characterize the best achievable rate for the Slepian-Wolf source coding problem with limited side information lookahead, and have some surprising implications. We find that side information is useless for any fixed d when the joint PMF of the source and side information satisfies the positivity condition P(x,y) > 0 for all (x,y). More generally, the optimal rate depends on the distribution of the pair X, Y only through the distribution of X and the bipartite graph whose edges represent the pairs x,y for which P(x,y) > 0. On the other hand, if side information lookahead dnis allowed to grow faster than logarithmic in the block length n, then H(X|Y) is achievable. Finally, we apply our approach to derive a computable expression for channel capacity when state information is available at the encoder with limited lookahead

The paper considers the source description problem with average distortion and per-symbol reproduction cost constraints. The source description cost-distortion function is then defined as the minimum of a weighted sum of the rate and the expected per-symbol reproduction cost subject to average distortion constraint. This function is evaluated for (i) binary source, Hamming loss and reproduction cost of 0 for a 0 and 1 for 1, (ii) Gaussian source, squared error distortion, and average power constraint on reproduction, and (iii) Gaussian Wyner-Ziv source coding with side information setting and average power constraint on reproduction. The results are compared to the description cost in the classical case

An outer bound to the capacity region of the two-receiver discrete memoryless broadcast channel is given. The outer bound is tight for all cases where the capacity region is known. When specialized to the case of no common information, this outer bound is shown to be contained in the Korner-Marton outer bound. This containment is shown to be strict for the binary skew-symmetric broadcast channel. Thus, this outer bound is in general tighter than all other known outer bounds on the discrete memoryless broadcast channel

The stringent performance requirements of many infrared imaging applications warrant the development of precision high dynamic range, high speed focal plane arrays. In addition to achieving high dynamic range, the readout circuits for these image sensors must achieve high linearity and SNR at low power consumption. Two high dynamic range image sensor schemes that have been developed for visible range imaging were reviewed first and discuss why they cannot meet the stringent performance demands of infrared imaging. A new dynamic range extension scheme, folded multiple capture, was then described that can meet these performance requirements. Dynamic range is extended using synchronous self-reset while high SNR is maintained using few non-uniformly spaced captures and least-squares fit to estimate pixel photocurrent. The paper concludes with a description of a prototype of this architecture targeted for 3D-IC IR focal plane arrays

Gupta and Kumar (2000) introduced a random model to study throughput scaling in a wireless network with static nodes, and showed that the throughput per source-destination pair is Theta(1/radic(nlogn)). Grossglauser and Tse (2001) showed that when nodes are mobile it is possible to have a constant throughput scaling per source-destination pair. In most applications, delay is also a key metric of network performance. It is expected that high throughput is achieved at the cost of high delay and that one can be improved at the cost of the other. The focus of this paper is on studying this tradeoff for wireless networks in a general framework. Optimal throughput-delay scaling laws for static and mobile wireless networks are established. For static networks, it is shown that the optimal throughput-delay tradeoff is given by D(n)=Theta(nT(n)), where T(n) and D(n) are the throughput and delay scaling, respectively. For mobile networks, a simple proof of the throughput scaling of Theta(1) for the Grossglauser-Tse scheme is given and the associated delay scaling is shown to be Theta(nlogn). The optimal throughput-delay tradeoff for mobile networks is also established. To capture physical movement in the real world, a random-walk (RW) model for node mobility is assumed. It is shown that for throughput of Oscr(1/radic(nlogn)), which can also be achieved in static networks, the throughput-delay tradeoff is the same as in static networks, i.e., D(n)=Theta(nT(n)). Surprisingly, for almost any throughput of a higher order, the delay is shown to be Theta(nlogn), which is the delay for throughput of Theta(1). Our result, thus, suggests that the use of mobility to increase throughput, even slightly, in real-world networks would necessitate an abrupt and very large increase in delay.

In Part I of this paper, the optimal throughput-delay tradeoff for static wireless networks was shown to be D(n)=Theta(nT(n)), where D(n) and T(n) are the average packet delay and throughput in a network of n nodes, respectively. While this tradeoff captures the essential network dynamics, packets need to scale down with the network size. In this "fluid model, " no buffers are required. Due to this packet scaling, D(n) does not correspond to the average delay per bit. This leads to the question whether the tradeoff remains the same when the packet size is kept constant, which necessitates packet scheduling in the network. In this correspondence, this question is answered in the affirmative by showing that the optimal throughput-delay tradeoff is still D(n)=Theta(nT(n)), where now D(n) is the average delay per bit. Packets of constant size necessitate the use of buffers in the network, which in turn requires scheduling packet transmissions in a discrete-time queuing network and analyzing the corresponding delay. Our method consists of deriving packet schedules in the discrete-time network by devising a corresponding continuous-time network and then analyzing the delay induced in the actual discrete network using results from queuing theory for continuous-time networks.

Upper and lower bounds on the capacity and minimum energy-per-bit for general additive white Gaussian noise (AWGN) and frequency-division AWGN (FD-AWGN) relay channel models are established. First, the max-flow min-cut bound and the generalized block-Markov coding scheme are used to derive upper and lower bounds on capacity. These bounds are never tight for the general AWGN model and are tight only under certain conditions for the FD-AWGN model. Two coding schemes that do not require the relay to decode any part of the message are then investigated. First, it is shown that the "side-information coding scheme" can outperform the block-Markov coding scheme. It is also shown that the achievable rate of the side-information coding scheme can be improved via time sharing. In the second scheme, the relaying functions are restricted to be linear. The problem is reduced to a "single-letter" nonconvex optimization problem for the FD-AWGN model. The paper also establishes a relationship between the minimum energy-per-bit and capacity of the AWGN relay channel. This relationship together with the lower and upper bounds on capacity are used to establish corresponding lower and upper bounds on the minimum energy-per-bit that do not differ by more than a factor of 1.45 for the FD-AWGN relay channel model and 1.7 for the general AWGN model.

We characterize the rate distortion function for the source coding with decoder side information setting when the ith reconstruction symbol is allowed to depend only on the first i+lscr side information symbols, for some finite look-ahead lscr, in addition to the index from the encoder. For the case of causal side information, i.e., lscr=0, we find that the penalty of causality is the omission of the subtracted mutual information term in the Wyner-Ziv rate distortion function. For lscr>0, we derive a computable "infinite-letter" expression for the rate distortion function. When specialized to the near-lossless case, our results characterize the best achievable rate for the Slepian-Wolf source coding problem with finite side information looka-head, and have some surprising implications. We find that side information is useless for any fixed lscr when the joint probability mass function (PMF) of the source and side information satisfies the positivity condition P(x,y)>0 for all (x,y). More generally, the optimal rate depends on the distribution of the pair X,Y only through the distribution of X and the bipartite graph whose edges represent the pairs x,y for which P(x,y)>0. On the other hand, if side information look-ahead is allowed to grow faster than logarithmic in the block length, then H(X|Y) is achievable. Finally, we apply our approach to derive a computable expression for channel capacity when state information is available at the encoder with limited look-ahead.

A relay-without-delay channel in which each transmitted relay symbol can depend on all its past as well as present received symbols is investigated. A general upper bound on the capacity of the channel is established. A lower bound on the capacity for the additive white Gaussian noise relay-without-delay channel is introduced and is shown to coincide with the upper bound for a certain range of parameter values

In previous work (2004), we characterized the optimal throughput-delay trade-off in static wireless networks as D(n) = Theta(nT(n)), where D(n) and T(n) are the average packet delay and throughput in a network of n nodes, respectively. While this trade-off captured the essential network dynamics, packets needed to scale down with the network size. In this "fluid model", no buffers were required. Due to this packet scaling, D(n) did not correspond to the average delay per bit. That led to the question whether the trade-off remains the same when the packet size is kept constant, which necessitates buffers and packet scheduling in the network. In this paper, we answer this question in the affirmative by showing that the optimal throughput-delay trade-off is still D(n) = Theta(nT(n)), where now D(n) is the average delay per bit. Packets of constant size necessitate the use of buffers in the network, which in turn requires scheduling packet transmissions in a discrete-time queueing network and analyzing the corresponding delay. Our method consists of deriving packet schedules in the discrete-time network by looking at a corresponding continuous-time network and then analyzing the delay induced in the actual discrete network using results from queueing theory for continuous-time networks

Recent advances in imaging sensor technology make high frame-rate video capture practical. As demonstrated in previous work, this capability can be used to enhance the performance of many image and video processing applications. The idea is to use the high frame-rate capability to temporally oversample the scene and, thus, to obtain more accurate information about scene motion and illumination. This information is then used to improve the performance of image and standard frame-rate video applications. This paper investigates the use of temporal oversampling to improve the accuracy of optical flow estimation (OFE). A method for obtaining high accuracy optical flow estimates at a conventional standard frame rate, e.g., 30 frames/s, by first capturing and processing a high frame-rate version of the video is presented. The method uses the Lucas-Kanade algorithm to obtain optical flow estimates at a high frame rate, which are then accumulated and refined to estimate the optical flow at the desired standard frame rate. The method demonstrates significant improvements in OFE accuracy both on synthetically generated video sequences and on a real video sequence captured using an experimental high-speed imaging system. It is then shown that a key benefit of using temporal oversampling to estimate optical flow is the reduction in motion aliasing. Using sinusoidal input sequences, the reduction in motion aliasing is identified and the desired minimum sampling rate as a function of the velocity and spatial bandwidth of the scene is determined. Using both synthetic and real video sequences, it is shown that temporal oversampling improves OFE accuracy by reducing motion aliasing not only for areas with large displacements but also for areas with small displacements and high spatial frequencies. The use of other OFE algorithms with temporally oversampled video is then discussed. In particular, the Haussecker algorithm is extended to work with high frame-rate sequences. This extension demonstrates yet another important benefit of temporal oversampling, which is improving OFE accuracy when brightness varies with time.

The capacity of a class of discrete-memoryless relay channels with orthogonal channels from the sender to the relay receiver and from the sender and relay to the receiver is shown to be equal to the max-flow min-cut upper bound. The result is extended to additive white Gaussian noise (AWGN) relay channels where the channel from the sender to the relay uses a different frequency band from the channel from the sender and the relay to the receiver.

Recently it has been shown that optical flow estimation (OFE) accuracy can benefit from temporal oversampling especially for large displacements between frames. In this paper, we show that temporal oversampling also benefits OFE in the case of complex scenes with small displacements but high spatial bandwidth. Using synthetic test sequences and a high-speed real video sequence, it is shown that temporal oversampling improves the performance of OFE by reducing motion aliasing not only for areas with large displacements but also for areas with small displacements but with high spatial frequencies. We also demonstrate that the minimum frame rate necessary to achieve good OFE performance for the tested sequences is largely determined by the minimum frame rate necessary to prevent motion aliasing.

Gupta and Kumar (2000) introduced a random network model for studying the way throughput scales in a wireless network when the nodes are fixed, and showed that the throughput per source-destination pair is /spl otimes/(1//spl radic/nlogn). Grossglauser and Tse (2001) showed that when nodes are mobile it is possible to have a constant or /spl otimes/(1) throughput scaling per source-destination pair. The focus of this paper is on characterizing the delay and determining the throughput-delay trade-off in such fixed and mobile ad hoc networks. For the Gupta-Kumar fixed network model, we show that the optimal throughput-delay trade-off is given by D(n) = /spl otimes/(nT(n)), where T(n) and D(n) are the throughput and delay respectively. For the Grossglauser-Tse mobile network model, we show that the delay scales as /spl otimes/(n/sup 1/2//v(n)), where v(n) is the velocity of the mobile nodes. We then describe a scheme that achieves the optimal order of delay for any given throughput. The scheme varies (i) the number of hops, (ii) the transmission range and (iii) the degree of node mobility to achieve the optimal throughput-delay trade-off. The scheme produces a range of models that capture the Gupta-Kumar model at one extreme and the Grossglauser-Tse model at the other. In the course of our work, we recover previous results of Gupta and Kumar, and Grossglauser and Tse using simpler techniques, which might be of a separate interest.

The random network model assumed in this paper is a generalization of the model that incorporates transmission energy consumption. The throughput, delay and energy-per-bit for a communication scheme are related through the scheme's average transmission range, i.e., average hop distance is considered. For mobile networks, the same model with additional feature that each node moves with velocity according to an independent Brownian motion is considered.

This paper describes the capacity of frequency-division AWGN relay channels with linear relaying functions. A sequence of nonconvex optimization problems solving are also described in this paper

This paper investigates the problem of energy-efficient transmission of data packets in a wireless network by jointly adapting to backlog and channel condition. Specifically, we consider minimum-energy scheduling problems over multiple-access channels, broadcast channels, and channels with fading, when packets of all users need to be transmitted before a deadline T. Earlier work has considered a similar setup and demonstrated significant transmission energy saving by adapting to backlog for channels that are time invariant and when transmission is restricted to time-division. For concreteness, throughout the paper, rates and powers corresponding to optimal coding over discrete-time additive white Gaussian noise (AWGN) channels are assumed. The results, however, hold for more general channels and coding schemes where the total transmitted power is convex in the transmission rates. The offline scheduling problems for all the channels considered are shown to reduce to convex optimization problems with linear constraints. An iterative algorithm, referred to as FlowRight, that finds optimal offline schedules is presented. A heuristic online algorithm that we call look-ahead water-filling, which jointly adapts to both channel fading state and backlog is described. By the use of a small buffer which introduces an almost fixed delay, this algorithm achieves a considerable reduction in energy relative to water filling solely on channel states.

No abstract available.

The paper explores the adaptation of transmission rate and power jointly to the data generation rate and channel fading, for minimizing transmission energy. The optimal offline adaptation problem is solved, which provides a lower-bound on the transmission energy consumed by any practical, that is, online, scheme. A heuristic online algorithm, look-ahead water-filling, is developed for adapting to the queue state as well as the channel state, and is shown through simulations to achieve transmission energy per packet close to optimal. As the packet arrival rate is varied within known limits, the average energy per packet used by look-ahead water-filling is significantly lower than that achieved by optimal adaptation to the channel only (water-filling in time). The delay per packet is larger, but is almost constant for all data arrival rates. The results can be generalized to multi-access and broadcast fading channels.

The paper develops algorithms for minimizing the energy required to transmit packets in a wireless environment. It is motivated by the following observation: In many channel coding schemes it is possible to significantly lower the transmission energy by transmitting packets over a long period of time. Based on this observation, we show that for a variety of scenarios the offline energy-efficient transmission scheduling problem reduces to a convex optimization problem. Unlike for the special case of a single transmitter-receiver pair studied by (see Prabhakar, Uysal-Biyikoglu and El Gamal. Proc. IEEE Infocom 2001), the problem does not, in general, admit a closed-form solution when there are multiple users. By exploiting the special structure of the problem, however, we are able to devise energy-efficient transmission schedules. For the downlink channel, with a single transmitter and multiple receivers, we devise an iterative algorithm, called MoveRight, that yields the optimal offline schedule. The MoveRight algorithm also optimally solves the downlink problem with additional constraints imposed by packet deadlines and finite transmit buffers. For the uplink (or multiaccess) problem MoveRight optimally determines the offline time-sharing schedule. A very efficient online algorithm, called MoveRightExpress, that uses a surprisingly small look-ahead buffer is proposed and is shown to perform competitively with the optimal offline schedule in terms of energy efficiency and delay.

In this paper we argue that biological vision and electronic image acquisition share common principles despite their vastly different implementations. These shared principles are based on the need to acquire a common set of input stimuli as well as the need to generalize from the acquired images. Two related principles are discussed in detail, namely, multiple parallel image representations and the use of dedicated local memory in various stages of acquisition and processing. We review relevant literature in visual neuroscience and image systems engineering to support our argument. Particularly, the paper discusses multiple capture image acquisition, with applications such as dynamic range, field-of-view, or depth-of-field extension. Finally, as an example, a novel multiple-capture-single-image complementary metal-oxide-semiconductor sensor is presented. This sensor illustrates the principles that are shared among biological vision and image acquisition.

The paper considers the problem of minimizing the energy used to transmit packets over a wireless link via lazy schedules that judiciously vary packet transmission times. The problem is motivated by the following observation. With many channel coding schemes, the energy required to transmit a packet can be significantly reduced by lowering transmission power and code rate and therefore transmitting the packet over a longer period of time. However, information is often time-critical or delay-sensitive and transmission times cannot be made arbitrarily long. We therefore consider packet transmission schedules that minimize energy subject to a deadline or a delay constraint. Specifically, we obtain an optimal offline schedule for a node operating under a deadline constraint. An inspection of the form of this schedule naturally leads us to an online schedule which is shown, through simulations, to perform closely to the optimal offline schedule. Taking the deadline to infinity, we provide an exact probabilistic analysis of our offline scheduling algorithm. The results of this analysis enable us to devise a lazy online algorithm that varies transmission times according to backlog. We show that this lazy schedule is significantly more energy-efficient compared to a deterministic (fixed transmission time) schedule that guarantees queue stability for the same range of arrival rates.

Advances in CMOS image sensors enable fast image capture, which makes it possible to capture multiple images within a normal exposure time. An algorithm that takes advantage of this capability by simultaneously constructing a high dynamic range image and performing motion blur restoration from multiple image captures is described. The algorithm comprises two main procedures-photocurrent estimation and motion/saturation detection. It operates completely locally-each pixel's final value is computed using only its captured values-and recursively, requiring the storage of only a constant number of values per pixel independent of the number of images captured. These modest computational and storage requirements make it feasible to integrate all needed memory and processing with the image sensor on a single CMOS chip. Simulation results demonstrate the enhanced SNR, dynamic range, and the motion blur restoration obtained using our algorithm.

Gradient-based optical flow estimation methods such as the Lucas-Kanade (1981) method work well for scenes with small displacements but fail when objects move with large displacements. Hierarchical matching-based methods do not suffer from large displacements but are less accurate. By utilizing the high speed imaging capability of CMOS image sensors, the frame rate can be increased to obtain more accurate optical flow with wide range of scene velocities in real time. Further, by integrating the memory and processing with the sensor on the same chip, optical flow estimation using high frame rate sequences can be performed without unduly increasing the off-chip data rate. The paper describes a method for obtaining high accuracy optical flow at a standard frame rate using high frame rate sequences. The Lucas-Kanade method is used to obtain optical flow estimates at high frame rate, which are then accumulated and refined to obtain optical flow estimates at a standard frame rate. The method is tested on video sequences synthetically generated by perspective warping. The results demonstrate significant improvements in optical flow estimation accuracy with moderate memory and computational power requirements.

The paper considers the problem of minimizing the energy used to transmit packets over a wireless link via lazy schedules that judiciously vary packet transmission times. The problem is motivated by the following key observation: in many channel coding schemes, the energy required to transmit a packet can be significantly reduced by lowering the transmission power and transmitting the packet over a longer period of time. However, information is often time-critical or delay-sensitive and transmission times cannot be made arbitrarily long. We therefore consider packet transmission schedules that minimize energy subject to a deadline or a delay constraint. Specifically, we obtain an optimal offline schedule for a node operating under a deadline constraint. An inspection of the form of this schedule naturally leads us to an online schedule which is shown, through simulations, to be energy-efficient. Finally, we relax the deadline constraint and provide an exact probabilistic analysis of our offline scheduling algorithm. We then devise a lazy online algorithm that varies transmission times according to backlog and show that it is more energy efficient than a deterministic schedule that guarantees stability for the same range of arrival rates.

We consider the problem of determining optimal wire widths for a power or ground network, subject to limits on wire widths, voltage drops, total wire area, current density, and power dissipation. To account for the variation of the current demand, we model it as a random vector with known statistics, possibly including correlation between subsystem currents. Other researchers have shown that when the variation in the current is not taken into account, the optimal network topology is a tree. A tree topology is, however, almost never used in practice, because it is not robust with respect to variations in the lock currents. We show that when the current variation is taken into account, the optimal network is usually not a tree.

Conventional methods for optimal sizing of wires and transistors use linear resistor-capacitor (RC) circuit models and the Elmore delay as a measure of signal delay. If the RC circuit has a tree topology, the sizing problem reduces to a convex optimization problem that can be solved using geometric programming. The tree topology restriction precludes the use of these methods in several sizing problems of significant importance to high-performance deep submicron design, including for example, circuits with loops of resistors, e.g., clock distribution meshes and circuits with coupling capacitors, e.g., buses with crosstalk between the wires. In this paper, we propose a new optimization method that can be used to address these problems. The method is based on the dominant time constant as a measure of signal propagation delay in an RC circuit instead of Elmore delay. Using this measure, sizing of any RC circuit can be cast as a convex optimization problem and solved using recently developed efficient interior-point methods for semidefinite programming. The method is applied to three important sizing problems: clerk mesh sizing and topology design, sizing of tristate buses, and sizing of bus line widths and spacings taking crosstalk into account.

Conventional methods for optimal sizing of wires and transistors use linear RC circuit models and the Elmore delay as a measure of signal delay. If the RC circuit has a tree topology, the sizing problem reduces to a convex optimization problem which can be solved using geometric programming. The tree topology restriction precludes the use of these methods in several sizing problems of significant importance to high-performance deep submicron design including, for example, circuits with loops of resistors, e.g. clock distribution meshes, and circuits with coupling capacitors, e.g. buses with crosstalk between the lines. The paper proposes a new optimization method which can be used to address these problems. The method uses the dominant time constant as a measure of signal propagation delay in an RC circuit, instead of Elmore delay. Using this measure, sizing of any RC circuit can be cast as a convex optimization problem which can be solved using the recently-developed efficient interior-point methods for semidefinite programming. The method is applied to two important sizing problems-the sizing of clock meshes and the sizing of buses in the presence of crosstalk.

A JBIG compliant, quadtree based, lossless image compression algorithm is described. In terms of the number of arithmetic coding operations required to code an image, this algorithm is significantly faster than previous JBIG algorithm variations. Based on this criterion, our algorithm achieves an average speed increase of more than 9 times with only a 5% decrease in compression when tested on the eight CCITT bi-level test images and compared against the basic non-progressive JBIG algorithm. The fastest JBIG variation that we know of, using "PRES" resolution reduction and progressive buildup, achieved an average speed increase of less than 6 times with a 7% decrease in compression, under the same conditions.

Logic replication has been shown empirically to reduce pin count and partition size in partitioned networks. This paper presents the first theoretical treatment of the min-cut replication problem, which is to determine replicated logic that minimizes cut size. A polynomial time algorithm for determining min-cut replication sets for k-partitioned graphs is derived by reducing replication to the problem of finding a maximum flow. The algorithm is extended to hypergraphs and replication heuristics are proposed for the NP-hard problem with size constraints on partition components. These heuristics, which reduce the worst-case running time by a factor of O(k/sup 2/) over previous methods, are applied to designs that have been partitioned into multiple FPGA's. Experimental results demonstrate that min-cut replication provides substantial reductions in the numbers of FPGA's and pins required.>

Abstract | Placement and routing heuristics for a Field Programmable Multi-Chip Module (FPMCM) are presented. The placement is done in three phases; partitioning, chip assignment and iterative improvement. The routing is done in two phases; global routing followed by detailed routing. Detailed routing involves new channel routing problems denoted by Exact Segmented Channel Routing (ESCR) and K-ESCR. A very fast K-ESCR heuristic is described. Experimental results show that the placement heuristic achieves high gate utilization, and that the K-ESCR heuristic performs surprisingly well over wide range of channel sizes. I.

A survey of field-programmable gate array (FPGA) architectures and the programming technologies used to customize them is presented. Programming technologies are compared on the basis of their volatility, size parasitic capacitance, resistance, and process technology complexity. FPGA architectures are divided into two constituents: logic block architectures and routing architectures. A classification of logic blocks based on their granularity is proposed, and several logic blocks used in commercially available FPGAs are described. A brief review of recent results on the effect of logic block granularity on logic density and performance of an FPGA is then presented. Several commercial routing architectures are described in the context of a general routing architecture model. Finally, recent results on the tradeoff between the flexibility of an FPGA routing architecture, its routability, and its density are reviewed.>

Logic synthesis algorithms and methods for field-programmable gate arrays (FPGAs) are reviewed. The three most popular types of FPGA architectures are considered, namely, those using logic blocks based on lookup-tables, multiplexers, and wide AND/OR arrays, respectively. The emphasis is on tools that attempt to minimize the area of the combinational logic part of a design, since little work has been done on optimizing performance or routability, or on synthesis of the sequential part of a design. The different tools surveyed are compared using a suite of benchmark designs.>

Novel problems concerning routing in a segmented routing channel are introduced. These problems are fundamental to routing and design automation for field programmable gate arrays (FPGAs), a new type of electrically programmable VLSI. The first known theoretical results on the combinatorial complexity and algorithm design for segmented channel routing are presented. It is shown that the segmented channel routing problem is in general NP-complete. Efficient polynomial time algorithms for a number of important special cases are presented.>

Heuristics for replicating logic have been shown to reduce pin count and wiring density in partitioned logic networks. An efficient algorithm for determining an optimal min-cut replication set for a k-partitioned graph in O(knm log (n/sup 2//m)) time is presented. For the NP-hard case with limited size partition components, a replication heuristic which reduces the worst-case running time by a factor of O(k/sup 2/) over previous methods is proposed. Experimental results are presented.>

Summary form only given as follows. Recent advances in device architectures and programmable technology have resulted in a dramatic increase in the integration capacity of field-programmable integrated circuits (FPICs). FPICs with over 10000 usable gates are currently available and it is expected that FPICs with 200000 gates will become feasible before the end of the century. Such high integration FPICs are becoming viable alternatives to many gate array and standard cell implementations. Moreover, the ability to rapidly prototype large systems using FPICs is opening up new and exciting possibilities in product customization, emulation, and configurable hardware acceleration. The author presents an overview of existing FPICs and discusses future directions in device architectures and applications to system level programmability.>

Routing channels in a field-programmable gate array contain predefined wiring segments of various lengths. These may be connected to the pins of the gates or joined end-to-end to form longer segments by programmable switches. The segmented channel routing problem is formulated, and polynomial time algorithms are given for certain special cases. The general problem is NP-complete, but it can be adequately solved in practice. Experiments indicate that a segmented channel with judiciously chosen segment lengths may near the efficiency of a conventional channel.

The communication complexity of a two-variable function f(x,y) is the number of information bits two communicators need to exchange to compute f when, initially, each knows only one of the variables. There are several communication-complexity measures corresponding to whether (1) the worst case or average number of bits is considered, (2) computation errors are allowed and (3) randomization is allowed. Tight bounds are provided for the typical behavior of all bounded-error communication-complexity measures of Boolean functions. In the present work, the authors formally define the deterministic model. They describe randomized protocols and compare them to deterministic ones. They both survey previous work and describe original results.>

The capacity region of the discrete memoryless interference channel with strong interference is established.

Simulated annealing is a computational heuristic for obtaining approximate solutions to combinatorial optimization problems. It is used to construct good source codes, error-correcting codes, and spherical codes. For certain sets of parameters codes that are better than any other known in the literature are found.

Let ${\bf x},{\bf y} \in \{ 0,1\} ^n $. Persons A and B are given ${\bf x}$ and ${\bf y}$ respectively. They communicate in order that both find the Hamming Distance $d_H^n ({\bf x},{\bf y})$. Three communication models, viz, deterministic, $\varepsilon $-error and $\varepsilon $-randomized, are considered. Let $C(d_H^n )$, $C_\varepsilon (d_H^n )$ and $D_\varepsilon (d_H^n )$ be the respective minimum number of bits that must be communicated under the three models. It is shown that \[ n + \log (n + 1 - \sqrt n ) \leqq C\left( {d_H^n } \right) \leqq n + \lceil {\log (n + 1)} \rceil . \] It is also shown that both $C_\varepsilon (d_H^n )$ and $D_\varepsilon (d_H^n )$ are lower bounded by $\Omega (n)$, thus solving an open problem posed by Yao.

Let X and Y be two random variables with probability distribution p(x,y), joint entropy H(X,Y) and conditional entropies H(X \ Y) and H(Y \ X) . Person P/sub x/ knows X and person P/sub Y/ knows Y. They communicate over a noiseless two-way channel so that both know X and Y. It is proved that, on the average, at least H(X \ Y) + H(Y \ X) bits must be exchanged and that H(X,Y) + 2 bits are sufficient. If p(x.y) > 0 for all (x.y), then at least H(X,Y) bits must be communicated on the average. However, if p (x,y) is uniform over its support set, the average number of bits needed is close to H(X \ Y) + H (Y \ X). Randomized protocols can reduce the amount of communication considerably but only when some probability of error is acceptable.

Let x, y, z be finite sets, X,Y random variables uniformly distributed over x×y, f a function from x×y to Z and 0≤ε&le1. A person PX knows X and a person PY knows Y and they want to exchange X and Y. An eavesdropper who knows their protocol listens to their communication in order to obtain information about f(X, Y). PX and PY want to ensure that for every value (x,y) of (X,Y) the eavesdropper's a priori and a posteriori probabilities of {f(X,Y)=j} are ε-close for all j. Therefore, they encrypt some of the transmitted bits. The problem is to find a protocol that minimizes the number of bits encrypted in the worst case. Two kinds of protocols are considered: deterministic and randomized.

The penalties for configuring VLSI arrays for yield enhancement are assessed.Each dement of the fabricated array is assumed to be defective with independent probability p.A fixed fractmn R of the elements are to be connected into a prespecified defect-free configuration by means of switched interconnections.The probability that this can be done, known as the yield, must be bounded away from zero.The additional interconnections required increase the integrated circuit's area by the area overhead ratio AOR.Propagation delay is determined by the maximum connection length d.The following results are shown.Connection of RN fixed pins to distinct nondefective elements from an Nelement linear array requires d = O(log N), AOR = O(log N).Connection of RN pairs of elements from two N-element linear arrays requires only constant d and AOR.Connection of a chain ofRN 2 dements from an N x N array requires only constant d and AOR; this result is closely related to the percolation model of statistical physics.Connection of a V'-RN x d'-RN lattice from an N x N array requires d = [~( IV]-~ N).Algorithms are presented that connect any fraction R < I -p of the dements with yield approaching one as N increases.

Hadamard's inequality follows immediately from inspection of both sides of the entropy inequalityh(X_{1}, X_{2},, \cdots, X_{n})\leq \sum h(X_{i}), when(X_{l}, X_{2},\cdots, X_{n})is multivariate normal.

It is proved that if(X,Y)are two finite alphabet correlated sources withp(x,y)>0for all(x,y) \in ({\cal X} \times {\cal Y}), and if a functionF(X,Y)is\alpha-sensitive, then the rateRof transmission fromXtoYnecessary to computeF(X,Y)reliably must be greater thanH(X|Y). The same result holds if the function is highly sensitive and for everyx_{1} \neq x_{2} \in {\cal X}, then the number of elementsy \in {\cal Y}withp(x_{l},y) \cdot p(x_{2}, y)>0is different from one.

A computer memory with defects is modeled as a discrete memoryless channel with states that are statistically determined. The storage capacity is found when complete defect information is given to the encoder or to the decoder, and when the defect information is given completely to the decoder but only partially to the encoder. Achievable storage rates are established when partial defect information is provided at varying rates to both the encoder and the decoder. Arimoto-Blahut type algorithms are used to compute the storage capacity.

This paper presents a novel and effective strategy for routing custom integrated circuits as well as solutions to subproblems associated with this strategy. Given an initial placement of rectangular blocks, the routing strategy includes the following major steps: construction of a channel graph, estimation of channel widths (based on a statistical model for signal nets and topological routing of power and ground nets), placement modification to include the estimated channel widths, topological routing for signal nets, and finally track assignment.

The capacity of the class of relay channels with senderx_{1}, a relay senderx_{2}, a relay receivery_{1}=f(x_{1},x_{2}), and ultimate receiveryis proved to beC = \max\min_{p(x_{1},x_{2})} \{I(X_{1}, X_{2}; Y), H(Y_{1}|X_{2})+I(X_{1};Y|X_{2},Y_{1}})\}.

The capacity region of a class of deterministic discrete memoryless interference channels is established. In this class of channels the outputsY_{1}andY_{2}are (deterministic) functions of the inputsX_{1}andX_{2}such thatH(Y_{1}|X_{1})=H(V_{2})andH(Y_{2}|X_{2})=H(V_{l})for all product probabiliW distributions onX_{1}X_{2}, whereV_{1}is a function ofX_{1}andV_{2}a function ofX_{2}. The capacity, region for the case in whichV_{2} \equiv 0andY_{1}depends randomly onX_{1}is also obtained and illustrated with an example.

Consider a sequence of independent identically distributed (i.i.d.) random variablesX_{l},X_{2}, \cdots, X_{n}and a distortion measured(X_{i},X̂_{i})on the estimatesX̂_{i}ofX_{i}. Two descriptionsi(X)\in \{1,2, \cdots ,2^{nR_{1}\}andj(X)\in \{1,2, \cdots,2^{nR_{2}\}are given of the sequenceX=(X_{1}, X_{2}, \cdots ,X_{n}). From these two descriptions, three estimates(i(X)), X2(j(X)), and\hat{X}_{O}(i(X),j(X))are formed, with resulting expected distortionsE \frac{1/n} \sum^{n}_{k=1} d(X_{k}, \hat{X}_{mk})=D_{m}, m=0,1,2.We find that the distortion constraintsD_{0}, D_{1}, D_{2}are achievable if there exists a probability mass distributionp(x)p(\hat{x}_{1},\hat{x}_{2},\hat{x}_{0}|x)withEd(X,\hat{x}_{m})\leq D_{m}such thatR_{1}>I(X;\hat{X}_{1}),R_{2}>I(X;\hat{X}_{2}),whereI(\cdot)denotes Shannon mutual information. These rates are shown to be optimal for deterministic distortion measures.

Bounds on the output entropy of the additive white Gaussian noise (AWGN) channel with feedback are used to prove that the capacity of the degraded additive white Gaussian noise (DAWGN) broadcast channel is not increased by feedback.

A simple proof using random partitions and typicality is given for Marton's coding theorem for broadcast channels.

Let\{(U_{i},V_{i})\}_{i=1}^{n}be a source of independent identically distributed (i.i.d.) discrete random variables with joint probability mass functionp(u,v)and common partw=f(u)=g(v)in the sense of Witsenhausen, Gacs, and Körner. It is shown that such a source can be sent with arbitrarily small probability of error over a multiple access channel (MAC)\{\cal X_{1} \times \cal X_{2},\cal Y,p(y|x_{1},x_{2})\},with allowed codes\{x_{l}(u), x_{2}(v)\}if there exist probability mass functionsp(s), p(x_{1}|s,u),p(x_{2}|s,v), such thatH(U|V)<I(X_{1}; Y|X_{2},V,S),H(V|U )<I(X_{2};Y|X_{1},U,S),H(U,V|W)<I(X_{1},X_{2};Y|W,S),H(U,V)

A relay channel consists of an inputx_{l}, a relay outputy_{1}, a channel outputy, and a relay senderx_{2}(whose transmission is allowed to depend on the past symbolsy_{1}. The dependence of the received symbols upon the inputs is given byp(y,y_{1}|x_{1},x_{2}). The channel is assumed to be memoryless. In this paper the following capacity theorems are proved. 1)Ifyis a degraded form ofy_{1}, thenC \: = \: \max \!_{p(x_{1},x_{2})} \min \,{I(X_{1},X_{2};Y), I(X_{1}; Y_{1}|X_{2})}. 2)Ify_{1}is a degraded form ofy, thenC \: = \: \max \!_{p(x_{1})} \max_{x_{2}} I(X_{1};Y|x_{2}). 3)Ifp(y,y_{1}|x_{1},x_{2})is an arbitrary relay channel with feedback from(y,y_{1})to bothx_{1} \and x_{2}, thenC\: = \: \max_{p(x_{1},x_{2})} \min \,{I(X_{1},X_{2};Y),I \,(X_{1};Y,Y_{1}|X_{2})}. 4)For a general relay channel,C \: \leq \: \max_{p(x_{1},x_{2})} \min \,{I \,(X_{1}, X_{2};Y),I(X_{1};Y,Y_{1}|X_{2}). Superposition block Markov encoding is used to show achievability ofC, and converses are established. The capacities of the Gaussian relay channel and certain discrete relay channels are evaluated. Finally, an achievable lower bound to the capacity of the general relay channel is established.

The capacity region is established for those discrete memoryless broadcast channelsp(y,z \mid x)for whichI(X;Y) \geq I(X;Z)holds for all Input distributions. The capacity region for this class of channels resembles the capacity region for degraded message sets considered by Körner and Marton.

The fact that the capacity region of the discrete memoryless physically degraded broadcast channel is not increased by feedback is established.