This paper presents an implant for electrical deep brain stimulation that can fit in the sphenoid sinus, a hollow space in the skull’s sphenoid bone that is accessible transnasally. The implant consists of flexible disk electrodes attached to a circuit capable of generating voltage pulses of up to 40 V through capacitive discharge from a 3 V DC power supply. The 10 mm × 4 mm × 3 mm circuit consumes <50 µA when idle and 50 µC/pulse. Different pulse widths and pulsing frequencies can be selected with hardware changes. When operated from a 1 mAh battery, the circuit can generate over 80000 pulses. The circuit was inserted into the sphenoid sinus of a human cadaver, and electric fields generated by the circuit in the brain were measured. Injecting a peak current of 10 mA, resulting fields of up to 15 V/m were measured in the ventral diencephalon, demonstrating sufficient amplitude to activate neurons. This work is the first demonstration of an implant for minimally invasive stimulation of deep brain structures through the skull base, which opens new horizons for clinical treatments of neural disorders.

Quantifying relevant interactions between neural populations is a prominent question in the analysis of high-dimensional neural recordings. However, existing dimension re-duction methods often discuss communication in the absence of a formal framework, while frameworks proposed to address this gap are impractical in data analysis. This work bridges the formal framework of$M$-Information Flow with practical analysis of real neural data. To this end, we propose Iterative Regression, a message-dependent linear dimension reduction technique that iteratively finds an orthonormal basis such that each basis vector maximizes correlation between the projected data and the message. We then define'$M$-forwarding' to formally capture the notion of a message being forwarded from one neural population to another. We apply our methodology to recordings we collected from two neural populations in a simplified model of whisker-based sensory detection in mice, and show that the low-dimensional$M$-forwarding structure we infer supports biological evidence of a similar structure between the two original, high-dimensional populations.

Motivated by rapid advances in neuroengineering, we recently proposed an interventional way of reverse engineering neural circuits that is oriented towards treating disorders. The emphasis is on finding efficient (i.e. sparse) interventions that change the input-output behavior of the circuit to a desirable one. In a subsequent work, we proposed algorithms for arriving at efficient interventions using just observations, and further, demonstrated the efficacy of our algorithms on artificial neural networks, using them as "model organisms". In this work, we examine this problem of arriving at efficient interventions using just observations from an information-theoretic perspective. We provide a simple 2-layer "worst-case" example showing that estimating minimal interventions using just observations is hard: in the worst case, this can require testing every solution in a list of exponentially many (in the size of the network) solutions. Guided by this example, we relax the problem to merely detecting the diseased layer. We focus our attention on cases where disease is induced by carefully choosing a single node intervention that causes immense disruption to the performance. We first use the cut-set bound to provide insights on the layer of the diseased node. Motivated by this bound, we propose a mutual-information-based algorithm to identify the layer of the diseased node, and quantify its performance. Strikingly, we observe that a surprisingly high fraction of networks preserve mutual information post-disease even until the very last layer. We propose an alternate decision rule for these cases which allows detection of diseased layers when mutual-information-based metrics fail due to this property.

Motivated by neuroscientific and clinical applications, we empirically examine whether observational measures of information flow can suggest interventions. We do so by performing experiments on artificial neural networks in the context of fairness in machine learning, where the goal is to induce fairness in the system through interventions. Using our recently developed M-information flow framework, we measure the flow of information about the true label (responsible for accuracy, and hence desirable), and separately, the flow of information about a protected attribute (responsible for bias, and hence undesirable) on the edges of a trained neural network. We then compare the flow magnitudes against the effect of intervening on those edges by pruning. We show that pruning edges that carry larger information flows about the protected attribute reduces bias at the output to a greater extent. This demonstrates that M-information flow can meaningfully suggest targets for interventions, answering the title's question in the affirmative. We also evaluate bias-accuracy tradeoffs for different intervention strategies, to analyze how one might use estimates of desirable and undesirable information flows (here, accuracy and bias flows) to inform interventions that preserve the former while reducing the latter.

With the growing use of machine learning algorithms in highly consequential domains, the quantification and removal of disparity in decision making with respect to protected attributes, such as gender, race, etc., is becoming increasingly important. While quantifying disparity is essential, sometimes the needs of a business (e.g., hiring) may require the use of certain features that are critical in a way that any disparity that can be explained by them might need to be exempted. For instance, in hiring a software engineer for a safety-critical application, a coding-test score may be a critical feature that is weighed strongly in the decision even if it introduces disparity, whereas other features, such as name, zip code, or reference letters may be used to improve decision-making, but only to the extent that they do not add disparity. In this work, we propose a novel information-theoretic decomposition of the total disparity (a quantification inspired from counterfactual fairness) into two components: a non-exempt component which quantifies the part of the disparity that cannot be accounted for by the critical features, and an exempt component which quantifies the remaining disparity. This decomposition is important: it allows one to check if the disparity arose purely due to the critical features (inspired from the business necessity defense of disparate impact law) and also enables selective removal of the non-exempt component of disparity if desired. We arrive at this decomposition through canonical examples that lead to a set of desirable properties (axioms) that any measure of non-exempt disparity should satisfy. We then demonstrate that our proposed counterfactual measure of non-exempt disparity satisfies all of them. Our quantification bridges ideas of causality, Simpson's paradox, and a body of work from information theory called Partial Information Decomposition (PID). We also obtain an impossibility result showing that no observational measure of non-exempt disparity can satisfy all of the desired properties, which leads us to relax our goals and examine alternative observational measures that satisfy only some of these properties. We perform case studies to show how one can audit existing models as well as train new models while reducing non-exempt disparity.

The needs of a business (e.g., hiring) may require the use of certain features that are critical in a way that any discrimination arising due to them should be exempted. In this work, we propose a novel information-theoretic decomposition of the total discrimination (in a counterfactual sense) into a non-exempt component, which quantifies the part of the discrimination that cannot be accounted for by the critical features, and an exempt component, which quantifies the remaining discrimination. Our decomposition enables selective removal of the non-exempt component if desired. We arrive at this decomposition through examples and counterexamples that enable us to first obtain a set of desirable properties that any measure of non-exempt discrimination should satisfy. We then demonstrate that our proposed quantification of non-exempt discrimination satisfies all of them. This decomposition leverages a body of work from information theory called Partial Information Decomposition (PID). We also obtain an impossibility result showing that no observational measure of non-exempt discrimination can satisfy all of the desired properties, which leads us to relax our goals and examine alternative observational measures that satisfy only some of these properties. We then perform a case study using one observational measure to show how one might train a model allowing for exemption of discrimination due to critical features.

QR decomposition of a matrix is one of the essential operations that is used for solving linear equations and finding least-squares solutions. We propose a coded computing strategy for parallel QR decomposition with applications to solving a full-rank square system of linear equations in a high-performance computing system. Our strategy is applied to the parallel Gram-Schmidt algorithm, which is one of the three commonly used algorithms for QR decomposition. Conventional coding strategies cannot preserve the orthogonality of Q. We prove a condition for a checksum-generator matrix to restore the degraded orthogonality of the decoded Q through low-cost post-processing, and construct a checksum-generator matrix for single-node failures. We obtain the minimal number of checksums required for singlenode failures under the "in-node checksum storage setting", where checksums are stored in original nodes, and further adapt the coded QR decomposition to this setting.

Recently, we developed a systematic framework for defining and inferring flows of information about a specific message in neural circuits [2], [3]. We defined a computational model of a neural circuit consisting of computational nodes and transmissions being sent between these nodes over time. We then gave a formal definition of information flow pertaining to a specific message, which was capable of identifying paths along which information flowed in such a system. However, this definition also had some non-intuitive properties, such as the existence of "orphans"-nodes from which information flowed out, even though no information flowed in. In part, these non-intuitive properties arose because we restricted our attention to measures that were functions of transmissions at a single time instant, and measures that were observational rather than counterfactual. In this paper, we consider alternative definitions, including one that is a function of transmissions at multiple time instants, one that is counterfactual, and a new observational definition. We show that a definition of information flow based on counterfactual causal influence (CCI) guarantees the existence of information paths while also having no orphans. We also prove that no observational definition of information flow that satisfies the information path property can match CCI in every instance. Furthermore, each of the definitions we examine (including CCI) is shown to have examples in which the information flow can take a non-intuitive path. Nevertheless, we believe our framework remains more amenable to drawing clear interpretations than classical tools used in neuroscience, such as Granger Causality.

Computing systems are evolving rapidly. At the device level, emerging devices are beginning to compete with traditional CMOS systems. At the architecture level, novel architectures are successfully avoiding the communication bottleneck that is a central feature, and a central limitation, of the von Neumann architecture. Furthermore, such systems are increasingly plagued by unreliability. This unreliability arises at device or gate-level in emerging devices, and can percolate up to processor or system-level if left unchecked. The goal of this article is to survey recent advances in reliable computing using unreliable elements, with an eye on nonsilicon and non-von Neumann architectures. We first observe that instead of aiming for generic computing problems, the community could use “dwarfs of modern computing,” first noted in the high-performance computing (HPC) community, as a starting point. These computing problems are the basic building blocks of almost all scientific computing, machine learning, and data analytics today. Next, we survey the state of the art in “coded computing,” which is an emerging area that advances on classical algorithm-based fault-tolerance (ABFT) and brings a fundamental information-theoretic perspective. By weaving error-correcting codes into a computing algorithm, coded computing provides dramatic improvements on solutions, as well as obtains novel fundamental limits, for problems that have been open for more than 30 years. We introduce existing and novel coded computing techniques in the context of “coded dwarfs,” where a specific dwarf's computation is made resilient by applying coding. We discuss how, for the same redundancy, “coded dwarfs” are significantly more resilient compared to classical techniques such as replication. Furthermore, by examining a widely popular computation task-training large neural networks-we demonstrate how coded dwarfs can be applied to address this fundamentally nonlinear problem. Finally, we discuss practical challenges and future directions in implementing coded computing techniques on emerging and existing nonsilicon and/or non-von Neumann architectures.

We provide novel coded computation strategies for distributed matrix-matrix products that outperform the recent “Polynomial code” constructions in recovery threshold, i.e., the required number of successful workers. When a fixed 1/m fraction of each matrix can be stored at each worker node, Polynomial codes require m2 successful workers, while our MatDot codes only require 2m - 1 successful workers. However, MatDot codes have higher computation cost per worker and higher communication cost from each worker to the fusion node. We also provide a systematic construction of MatDot codes. Furthermore, we propose “PolyDot” coding that interpolates between Polynomial codes and MatDot codes to trade off computation/communication costs and recovery thresholds. Finally, we demonstrate a novel coding technique for multiplying n matrices (n ≥ 3) using ideas from MatDot and PolyDot codes.

We develop a theoretical framework for defining and identifying flows of information in computational systems. Here, a computational system is assumed to be a directed graph, with “clocked” nodes that send transmissions to each other along the edges of the graph at discrete points in time. We are interested in a definition that captures the dynamic flow of information about a specific message, and which guarantees an unbroken “information path” between appropriately defined inputs and outputs in the directed graph. Prior measures, including those based on Granger Causality and Directed Information, fail to provide clear assumptions and guarantees about when they correctly reflect information flow about a message. We take a systematic approach-iterating through candidate definitions and counterexamples-to arrive at a definition for information flow that is based on conditional mutual information, and which satisfies desirable properties, including the existence of information paths. Finally, we describe how information flow might be detected in a noiseless setting, and provide an algorithm to identify information paths on the time-unrolled graph of a computational system.

As error/failure rates in supercomputers are projected to grow, computationally intensive scientific applications that lever-age large-scale parallelization will suffer from the increased error rate. In this work, we apply "coded computing" to protein folding simulations in an error-prone environment. We implemented the fast Fourier Poisson method for solving electrostatic equations at each time step of the simulation, and we utilize coded FFT algorithm to protect the compute-intensive FFT algorithm from soft errors. Through experiments on Amazon AWS, we showed that coded protein folding can be implemented with less than 10% overhead in total simulation time, and also showed that coded computing approach is faster than classical checkpointing method when the error rate is high.

The problem of computing distributed matrix multiplication reliably has been of immense interest for several decades. Recently, it was shown that Polynomial codes achieve the theoretically minimum recovery bandwidth. However, existing constructions for Polynomial codes are nonsystematic, which can impose substantial overhead in distributed computing. In this paper, we propose two different systematic code constructions that achieve the same recovery bandwidth as Polynomial codes. First uses a random coding argument, and the second is polynomial-based, but uses bivariate instead of originally used univariate polynomials. We show that the proposed constructions are communication optimal with high probability.

We develop a theoretical framework for defining information flow in neural circuits, within the context of "eventrelated" experimental paradigms in neuroscience. Here, a neural circuit is modeled as a directed graph, with "clocked" nodes that send transmissions to each other along the edges of the graph at discrete points in time. We are interested in a definition that captures the flow of "stimulus"-related information, and which guarantees a continuous information path between appropriately defined inputs and outputs in the directed graph. Prior measures, including those based on Granger Causality and Directed Information, fail to provide clear assumptions and guarantees about when they correctly reflect stimulus-related information flow, due to the absence of a theoretical foundation with a mathematical definition. We take a methodical approach- iterating through candidate definitions and counterexamples- to arrive at a definition for information flow that is based on conditional mutual information, and which satisfies desirable properties, including the existence of information paths.

Cloud providers have recently introduced new offerings whereby spare computing resources are accessible at discounts compared to on-demand computing. Exploiting such opportunity is challenging inasmuch as such resources are accessed with low-priority and therefore can elastically leave (through preemption) and join the computation at any time. In this paper, we design a new technique called coded elastic computing enabling distributed computations over elastic resources. The proposed technique allows machines to leave the computation without sacrificing the algorithm-level performance, and, at the same time, flexibly reduce the workload at existing machines when new ones join the computation. Leveraging coded redundancy, our approach is able to achieve similar computational cost as the original (uncoded) method when all machines are present; the cost gracefully increases when machines are preempted and reduces when machines join. The performance of the proposed technique is evaluated on matrix-vector multiplication and linear regression tasks, and shows improvements over existing techniques.

In an era of ever-increasing dynamicity and heterogeneity of wireless networks, energy is fast becoming the most constrained resource. First, we review recent studies that suggest that using one single error-correcting code (ECC) designed to meet the worst case requirement is inefficient in terms of energy consumption when there are many heterogeneous nodes in the network. These works extend the classical Shannon theory and incorporate circuit energy and signal transmit energy to optimize total energy/power consumption of today's communication systems. Then, we survey recent work on designing adaptive ECCs to operate energy efficiently even in the presence of extremely large heterogeneity in requirements and conditions. Two constructions of energy-adaptive codes are summarized: energy-adaptive low-density parity-check (LDPC) codes and energy-adaptive polar codes. These constructions have shown theoretically and empirically that having adaptivity in code design can save substantial energy, especially when the network has very diverse communication scenarios. Finally, we suggest a few possible applications where energy-adaptive codes can be employed and outline interesting future directions and challenges.

We consider the problem of computing a matrix-vector product Ax using a set of P parallel or distributed processing nodes prone to “straggling,” i.e., unpredictable delays. Every processing node can access only a fraction (s/N) of the N-length vector x, and all processing nodes compute an equal number of dot products. We propose a novel error correcting code-that we call “Short-Dot”-that introduces redundant, shorter dot products such that only a subset of the nodes' outputs are sufficient to compute Ax. To address the problem of straggling in computing matrix-vector products, prior work uses replication or erasure coding to encode parts of the matrix A, but the length of the dot products computed at each processing node is still N. The key novelty in our work is that instead of computing the long dot products as required in the original matrix-vector product, we construct a larger number of redundant and short dot products that only require a fraction of x to be accessed during the computation. Short-Dot is thus useful in a communication-constrained scenario as it allows for only a fraction of x to be accessed by each processing node. Further, we show that in the particular regime where the number of available processing nodes is greater than the total number of dot products, Short-Dot has lower expected computation time under straggling under an exponential model compared to existing strategies, e.g. replication, in a scaling sense. We also derive fundamental limits on the trade-off between the length of the dot products and the recovery threshold, i.e., the required number of processing nodes, showing that Short-Dot is near-optimal.

We propose a novel application of coded computing to the problem of the nearest neighbor estimation using MatDot Codes (Fahim et al., Allerton'17) that are known to be optimal for matrix multiplication in terms of recovery threshold under storage constraints. In approximate nearest neighbor algorithms, it is common to construct efficient in-memory indexes to improve query response time. One such strategy is Multiple Random Projection Trees (MRPT), which reduces the set of candidate points over which Euclidean distance calculations are performed. However, this may result in a high memory footprint and possibly paging penalties for large or high-dimensional data. Here we propose two techniques to parallelize MRPT that exploit data and model parallelism respectively by dividing both the data storage and the computation efforts among different nodes in a distributed computing cluster. This is especially critical when a single compute node cannot hold the complete dataset in memory. We also propose a novel coded computation strategy based on MatDot codes for the model-parallel architecture that, in a straggler-prone environment, achieves the storage-optimal recovery threshold, i.e., the number of nodes that are required to serve a query. We experimentally demonstrate that, in the absence of straggling, our distributed approaches require less query time than execution on a single processing node, providing near-linear speedups with respect to the number of worker nodes. Our experiments on real systems with simulated straggling, we also show that in a straggler-prone environment, our strategy achieves a faster query execution than the uncoded strategy.

This paper has two main contributions. First, we propose a novel coding technique - Generalized PolyDot - for matrix-vector products that advances on existing techniques for coded matrix operations under storage and communication constraints. Next, we use Generalized PolyDot for the problem of training large Deep Neural Networks (DNNs) using unreliable nodes that are prone to soft-errors, e.g., bit flips during computation that produce erroneous outputs. An additional difficulty imposed by the problem of DNN training is that the parameter values (weight matrices) are updated at every iteration, and thus require a prohibitively large encoding cost at every iteration if we naively extend existing coded computing techniques. Thus, we propose a “unified” coded DNN training strategy where we weave coding into the operations of DNN training itself, so that the weight matrices, once initially encoded, remain encoded during updates with negligible encoding/decoding overhead per iteration. Moreover, our strategy can also allow for errors even in the nonlinear step of training. Finally, our coded DNN training strategy is completely decentralized: no assumptions on the presence of a master node are made, which avoids any single point of failure under soft-errors. Our strategy can provide unboundedly better error tolerance than the competing replication strategy and an MDS-code-based strategy [1].

We propose a coded computing technique for making the power-iteration method of solving a single sparse linear inverse problem robust to erasure-type noise. We observe that for sparse inverse problems, codes with dense generator matrices can significantly increase storage costs. Thus, we propose coding the power-iteration computation using sparse generator matrices. Surprisingly, despite the poor error-correction ability of codes with sparse generator matrices, we show through both theoretical analysis and simulations that these codes are sufficient to achieve almost the same convergence rate as noiseless power iterations, provided that a new decoding algorithm that we call “substitute decoding” is used.

We consider a problem of localizing the destination of an activated path signal supported on a graph. An “activated path signal” is a graph signal that evolves over time that can be viewed as the trajectory of a moving agent. We show that by combining dynamic programming and graph partitioning, the computational complexity of destination localization can be significantly reduced. Then, we show that the destination localization error can be upper-bounded using methods based on large-deviation. Using simulation results, we show a tradeoff between the destination localization error and the computation time. We compare the dynamic programming algorithm with and without graph partitioning and show that the computation time can be significantly reduced by using graph partitioning. The proposed technique can scale to the problem of destination localization on a large graph with one million nodes and one thousand time slots.

We consider the problem of computing the convolution of two long vectors using parallel processors in the presence of “stragglers”. Stragglers refer to the small fraction of faulty or slow processors that delays the entire computation in time-critical distributed systems. We first show that splitting the vectors into smaller pieces and using a linear code to encode these pieces provides improved resilience against stragglers than replication-based schemes under a simple, worst-case straggler analysis. We then demonstrate that under commonly used models of computation time, coding can dramatically improve the probability of finishing the computation within a target “deadline” time. As opposed to the more commonly used technique of expected computation time analysis, we quantify the exponents of the probability of failure in the limit of large deadlines. Our exponent metric captures the probability of failing to finish before a specified deadline time, i.e., the behavior of the “tail”. Moreover, our technique also allows for simple closed form expressions for more general models of computation time, e.g. shifted Weibull models instead of only shifted exponentials. Thus, through this problem of coded convolution, we establish the utility of a novel asymptotic failure exponent analysis for distributed systems.

It is now well known that using a long and complicated error correcting code (ECC) designed for the worst-case error probability requirement wastes excessive total system energy (transmit + circuit energy) when the error probability requirement is much higher than the worst case. We propose a novel adaptive polar coding strategy that adjusts the decoder circuit to consume minimal decoding circuit energy at each given target error requirement. By combining Thompson's VLSI theory and scaling analysis of polar codes, we provide upper bounds on energy, area, and time complexity of polar decoding circuits in terms of target block error probability. The upper bounds are derived from an explicit construction of decoder circuit based on mesh-network structure. Our comparison shows that the proposed energy-adaptive coding strategy has a scaling-sense gain in decoding energy with little circuit area overhead when there is a large gap between the worst-case and typical target error rate requirements.

Temperature constraints arise naturally in communication scenarios where the act of data transmission causes heat dissipation. We address this problem in point to point communications over an additive white Gaussian noise channel in an information theoretic setting. In the specific scenario, transmitted code symbols cause heat dissipation as an input to a first order discrete time heat circuit and the output of this dynamical system, being the temperature, has to remain below a critical level Tc. Additionally, we allow the transmitter to use an energy harvesting device to power its transmission. We investigate channel capacity for various combinations of peak and average temperature, average power, and energy harvesting constraints on the transmitted code symbols.

The “source localization” problem is one in which we estimate the location of a point source observed through a diffusive medium using an array of sensors. We obtain lower bounds on the minimax risk (mean squared-error in location) in estimating the location of the source, which apply to all estimators, for certain classes of diffusive media, when using a uniformly distributed sensor array. We show that for sensors of a fixed size, the lower bound decays to zero with increasing numbers of sensors. We also analyze a more physical sensor model to understand the effect of shrinking the size of sensors as their number increases to infinity, wherein the bound saturates for large sensor numbers. In this scenario, it is seen that there is greater benefit to increasing the number of sensors as the signal-to-noise ratio increases. Our bounds are the first to give a scaling for the minimax risk in terms of the number of sensors used.

Computationally intensive distributed and parallel computing is often bottlenecked by a small set of slow workers known as stragglers. In this paper, we utilize the emerging idea of ``coded computation'' to design a novel error-correcting-code inspired technique for solving linear inverse problems under specific iterative methods in a parallelized implementation affected by stragglers. Example machine-learning applications include inverse problems such as personalized PageRank and sampling on graphs. We provably show that our coded-computation technique can reduce the mean-squared error under a computational deadline constraint. In fact, the ratio of mean-squared error of replication-based and coded techniques diverges to infinity as the deadline increases. Our experiments for personalized PageRank performed on real systems and real social networks show that this ratio can be as large as $10^4$. Further, unlike coded-computation techniques proposed thus far, our strategy combines outputs of all workers, including the stragglers, to produce more accurate estimates at the computational deadline. This also ensures that the accuracy degrades ``gracefully'' in the event that the number of stragglers is large.

This paper uses an information-theoretic lens to examine the use and implementation of electroencephalography (EEG) systems for neural imaging. There is a widespread belief in the clinical and neuroscientific community that ultra-high-density EEG imaging of the brain (beyond the typically used few hundred or fewer electrodes) will not yield higher spatial resolution. Theoretically, this belief rests on a spatial Nyquist rate analysis for human head models. This analysis in turn relies on the understanding that high spatial frequencies (that carry high-resolution information) decay as they travel from the brain to the scalp surface. Interestingly, the belief continues to be held despite being recently challenged experimentally, in part because of the spatial Nyquist results. In this work, we question the spatial Nyquist rate analysis, mathematically as well as conceptually. Mathematically, we correct and generalize the Nyquist rate analysis, and then use it to obtain improved estimates for spatial Nyquist rates. Conceptually, we observe that the Nyquist rate analysis provides a limit on the following problem: what is the minimum number of sensors required to reconstruct the scalp EEG to within a specified (small) mean-squared error? However, this problem is fundamentally different from the imaging problem of minimizing error in reconstructing the neural source inside the brain, which optimizes a different objective, and requires inclusion of noise in the analysis. To that end, we utilize the transfer function to obtain an information-theoretic fundamental limit on the achievable accuracy in localizing single-dipole sources. The technique relies on computing the distortion-rate function for a single dipole source and evaluating it at an upper bound on mutual information across the brain-to-scalp channel, and can be extended to more general sources as well. Finally, we observe that the main obstacle in understanding the required number of EEG sensors is the lack of ultra-high-density systems that can test these limits, and information theory can prove helpful in this context as well. One engineering difficulty is that the required circuit area and energy for sampling EEG signals can be too large to enable these systems to be safe, compact, and portable. Toward reducing this area and energy, we observe that the decay of high spatial frequencies in EEG, while being a detriment to reconstruction accuracy, also leads to large spatial correlations in the recorded EEG signals. Interestingly, these correlations can be harnessed using a novel information-theoretic "hierarchical referencing" technique that can reduce circuit energy and area to enable high-resolution high-density implementations.

We consider the problem of computing a binary linear transformation when all circuit components are unreliable. Two models of unreliable components are considered: probabilistic errors and permanent errors. We introduce the “ENCODED” technique that ensures that the error probability of the computation of the linear transformation is kept bounded below a small constant independent of the size of the linear transformation even when all logic gates in the computation are noisy. By deriving a lower bound, we show that in some cases, the computational complexity of the ENCODED technique achieves the optimal scaling in error probability. Further, we examine the gain in energy-efficiency from the use of a “voltage-scaling” scheme, where gate-energy is reduced by lowering the supply voltage. We use a gate energy-reliability model to show that tuning gate-energy appropriately at different stages of the computation (“dynamic” voltage scaling), in conjunction with ENCODED, can lead to orders of magnitude energy-savings over the classical “uncoded” approach. Finally, we also examine the problem of computing a linear transformation when noiseless decoders can be used, providing upper and lower bounds to the problem.

We consider the problem of distributed lossy linear function computation in a tree network. We examine two cases: 1) data aggregation (only one sink node computes) and 2) consensus (all nodes compute the same function). By quantifying the accumulation of information loss in distributed computing, we obtain fundamental limits on network computation rate as a function of incremental distortions (and hence incremental loss of information) along the edges of the network. The above characterization, based on quantifying distortion accumulation, offers an improvement over classical cut-set type techniques, which are based on overall distortions instead of incremental distortions. This quantification of information loss qualitatively resembles information dissipation in cascaded channels [2]. Surprisingly, this accumulation effect of distortion happens even at infinite blocklength. Combining this observation with an inequality on the dominance of mean-square quantities over relative-entropy quantities, we obtain outer bounds on the rate distortion function that are tighter than classical cut-set bounds by a difference, which can be arbitrarily large in both data aggregation and consensus. We also obtain inner bounds on the optimal rate using random Gaussian coding, which differ from the outer bounds by O(√D), where D is the overall distortion. The obtained inner and outer bounds can provide insights on rate (bit) allocations for both the data aggregation problem and the consensus problem. We show that for tree networks, the rate allocation results have a mathematical structure similar to classical reverse waterfilling for parallel Gaussian sources. Apart from data aggregation and distributed consensus, the distortion accumulation analysis framework is also applicable in large-scale data summarization through histograms and linear sketching, e.g., word counting tasks for document summarization.

We consider the problem of minimizing the number of broadcasts for collecting all sensor measurements at a sink node in a noisy broadcast sensor network. Focusing first on arbitrary network topologies, we provide: 1) fundamental limits on the required number of broadcasts of data gathering and 2) a general in-network computing strategy to achieve an upper bound within factor log N of the fundamental limits, where N is the number of agents in the network. Next, focusing on two example networks, namely, arbitrary geometric networks and random Erdös-Rényi networks, we provide improved in-network computing schemes that are optimal in that they attain the fundamental limits, i.e., the lower and upper bounds are tight in scaling sense. Our main techniques are three distributed encoding techniques, called graph codes, which are designed, respectively, for the above-mentioned three scenarios. Our work, thus, extends and unifies previous works such as those of Gallager and Karamchandani on the number of broadcasts for distributed function computation in special network topologies, while bringing in novel techniques, e.g., from error-control coding and noisy circuits, for both upper and lower bounds.

The advantages of adaptivity and feedback are of immense interest in signal processing and communication with many positive and negative results. Although it is established that adaptivity does not offer substantial reductions in minimax mean square error for a fixed number of measurements, existing results have shown several advantages of adaptivity in complexity of reconstruction, accuracy of support detection, and gain in signal-to-noise ratio, under constraints on sensing energy. Sensing energy has often been measured in terms of the Frobenius Norm of the sensing matrix. This paper uses a different metric that we call the l0cost of a sensing matrix- to quantify the complexity of sensing. Thus sparse sensing matrices have a lower cost. We derive information-theoretic lower bounds on the l0cost that hold for any non-adaptive sensing strategy. We establish that any non-adaptive sensing strategy must incur an l0cost of a Θ(N log2(N)) to reconstruct an N-dimensional, one-sparse signal when the number of measurements are limited to Θ(log2(N)). In comparison, bisection-type adaptive strategies only require an l0cost of at most O(N) for equal order of measurements. The problem has an interesting interpretation as a sphere packing problem in a multidimensional space, such that all the sphere centres have minimum non-zero co-ordinates. We also discuss the variation in l0cost as the number of measurements increase from Θ(log2(N)) to Θ(N).

In this paper, we obtain information-theoretic fundamental limits on attainable source-localization accuracy in Electroencephalography (EEG) recordings of the brain. To develop a systematic approach, we borrow idealized models of the human head from neuroscience literature and analyze the brain-activity to scalp “channel,” where brain activity is viewed as the input, and the recordings on the brain-surface as the output of the channel. An evaluation of the distortion-rate function at this channel's capacity is used to obtain outer (lower) bounds on attainable mean-squared reconstruction error for localizing a single dipole. These bounds can not be surpassed using any sensing algorithm and hold in the limit of infinite number of sensors. While these limits are obtained under simplistic assumptions, these are the first limits for the problem that hold for all estimation algorithms, and need to be extended to more sophisticated models for obtaining a better understanding of optimal neural interfaces and algorithms. Finally, we also provide an upper bound on the Shannon capacity of EEG-based brain-computer interfaces.

We consider the problem of lossy linear function computation for Gaussian sources in a tree network. The goal is to find the optimal tradeoff between the sum rate (the overall number of bits communicated in the network) and the achieved distortion (the overall mean-square error of estimating the function result) at a specified sink node. Using random Gaussian codebooks, an inner bound is obtained that is shown to match the information-theoretic outer bound (obtained in our earlier work [1]) in the limit of zero distortion. To compute the overall distortion for the random coding scheme, we applied the analysis of Distortion Accumulation which was quantified in [1] for MMSE estimates of intermediate computation variables instead of for the codewords of random Gaussian codebooks. The key in applying the analysis of Distortion Accumulation is showing that the random-coding based codeword on the receiver side is close in mean-square sense to the MMSE estimate of the source, even if the knowledge of the source distribution is not fully accurate.

We consider the problem of computing a binary linear transform when all circuit components are unreliable. We propose a novel “ENCODED” technique that uses LDPC (low-density parity-check) codes and embedded noisy decoders to keep the error probability of the computation below a small constant independent of the size of the linear transform, even when all logic gates in the computation are prone to probabilistic errors. Unlike existing works on applying coding to computing with unreliable components, the “ENCODED” technique explicitly considers the errors that happen during both the encoding and the decoding phases. Further, we show that ENCODED requires fewer operations (in order sense) than repetition techniques.

We consider the problem of data collection in a two-layer network consisting of (1) noisy links between N distributed agents and a remote sink node; (2) a noisy sparse network formed by these distributed agents. We jointly consider the design of the optimal graph topology for the inter-agent network and the in-network computing scheme under the sparsity constraint and the energy constraint, and study the effect of inter-agent communications on the overall energy consumption. Despite the sparse connections between agents, we provide an in-network coding scheme that reduces the overall energy consumption by a factor of Θ(logN) compared to a naive scheme based on direct agent-to-sink communications only. By providing lower bounds on both the energy consumption and the sparseness (number of links) of the network, we show that the proposed scheme is energy-optimal except for a factor of Θ(log logN). The proposed scheme extends a previous work of Gallager [2] on noisy broadcasting from a complete graph to a sparse graph, while bringing in new techniques from error control coding and noisy circuits.

Faced with saturation of Moore's law and increasing size and dimension of data, system designers have increasingly resorted to parallel and distributed computing to reduce computation time of machine-learning algorithms. However, distributed computing is often bottle necked by a small fraction of slow processors called "stragglers" that reduce the speed of computation because the fusion node has to wait for all processors to complete their processing. To combat the effect of stragglers, recent literature proposes introducing redundancy in computations across processors, e.g., using repetition-based strategies or erasure codes. The fusion node can exploit this redundancy by completing the computation using outputs from only a subset of the processors, ignoring the stragglers. In this paper, we propose a novel technique - that we call "Short-Dot" - to introduce redundant computations in a coding theory inspired fashion, for computing linear transforms of long vectors. Instead of computing long dot products as required in the original linear transform, we construct a larger number of redundant and short dot products that can be computed more efficiently at individual processors. Further, only a subset of these short dot products are required at the fusion node to finish the computation successfully. We demonstrate through probabilistic analysis as well as experiments on computing clusters that Short-Dot offers significant speed-up compared to existing techniques. We also derive trade-offs between the length of the dot-products and the resilience to stragglers (number of processors required to finish), for any such strategy and compare it to that achieved by our strategy.

Motivated by recently derived fundamental limits on total (transmit + decoding) power for coded communication with VLSI decoders, this paper investigates the scaling behavior of the minimum total power needed to communicate over AWGN channels as the target bit-error-probability tends to zero. We focus on regular-LDPC codes and iterative message-passing decoders. We analyze scaling behavior under two VLSI complexity models of decoding. One model abstracts power consumed in processing elements (node model), and another abstracts power consumed in wires which connect the processing elements (wire model). We prove that a coding strategy using regular-LDPC codes with Gallager-B decoding achieves order-optimal scaling of total power under the node model. However, we also prove that regular-LDPC codes and iterative message-passing decoders cannot meet existing fundamental limits on total power under the wire model. Furthermore, if the transmit energy-per-bit is bounded, total power grows at a rate that is worse than uncoded transmission. Complementing our theoretical results, we develop detailed physical models of decoding implementations using post-layout circuit simulations. Our theoretical and numerical results show that approaching fundamental limits on total power requires increasing the complexity of both the code design and the corresponding decoding algorithm as communication distance is increased or error-probability is lowered.

We consider the problem of communicating data from energy-constrained distributed sensors. To reduce energy requirements, we go beyond the source reconstruction problem classically addressed, and focus on the problem where the recipient wants to perform supervised learning and classification on the data received from the sensors. Restricting our attention to a noiseless communication setting under simplistic Gaussian source assumptions, we study supervised learning and classification under total energy limitations. The energy constraints are modeled in two ways: 1) a linear scaling and 2) an exponential scaling of energy with number of bits used for compression at sensors. We first assume that the underlying parameters for Gaussian distributions have already been learned, and obtain (with linear scaling, reverse-waterfilling-type) strategies for allocating energy, and thus, bits, across different sensors under these two models. Intuitively, these strategies allocate larger rates and energies to sensors that are more “relevant” for the classification goal. These strategies are used to obtain an achievable bound on the tradeoff between energy and error-probability (classification risk). We then provide an algorithm for learning the distribution-parameters of the sensor-data under energy constraints to arrive at high-reliability energy-allocation strategies, while enabling the energy-allocation algorithm to backtrack when the underlying distributions change, or when there is noise in sensed data that can push the algorithm toward a local minimum. Finally, we provide numerical results on energy-savings for classification of simulated data as well as neural data acquired from electrocorticography (ECoG) experiments.

Motivated by the damage due to heating in sensor operation, we consider the throughput optimal offline data scheduling problem in an energy harvesting transmitter, such that the resulting temperature remains below a critical level. We model the temperature dynamics of the transmitter as a linear system and determine the optimal transmit power policy under such temperature constraints as well as energy harvesting constraints over an additive white Gaussian noise channel. We first derive the structural properties of the solution for the general case with multiple energy arrivals. We show that the optimal power policy is piecewise monotone decreasing with possible jumps at the energy harvesting instants. We derive analytical expressions for the optimal solution in the single energy arrival case. We show that, in the single energy arrival case, the optimal power is monotone decreasing, the resulting temperature is monotone increasing, and both remain constant after the temperature hits the critical level. We then generalize the solution for the multiple energy arrival case.

Motivated by damage due to heating in sensor operation, we consider the throughput optimal offline data scheduling problem in an energy harvesting transmitter such that resulting temperature increase remains below a critical level. We model the temperature dynamics of the transmitter as a linear system and determine the optimal transmit power policy under such temperature constraints as well as energy harvesting constraints over an AWGN channel. We first derive the structural properties of the solution for the general case with multiple energy arrivals. We, then, obtain closed form solutions for the case of a single energy arrival. We observe that the optimal power policy is piecewise monotone decreasing with possible jumps at the energy harvesting instants, and remains constant after the temperature reaches the critical level.

The papers in this special issue presents cutting-edge research results in the emerging area of energy harvesting wireless communications and wireless energy transfer. This first issue starts with a review article coauthored by the guest editors that summarizes recent results in the broad area of energy harvesting communications, in particular, in information-theoretic, offline and online schedulingtheoretic, medium access, networking approaches to energy harvesting communications, as well as in energy cooperation and simultaneous wireless energy and information transfer.

This paper summarizes recent contributions in the broad area of energy harvesting wireless communications. In particular, we provide the current state of the art for wireless networks composed of energy harvesting nodes, starting from the information-theoretic performance limits to transmission scheduling policies and resource allocation, medium access, and networking issues. The emerging related area of energy transfer for self-sustaining energy harvesting wireless networks is considered in detail covering both energy cooperation aspects and simultaneous energy and information transfer. Various potential models with energy harvesting nodes at different network scales are reviewed, as well as models for energy consumption at the nodes.

Just as there are frictional losses associated with moving masses on a surface, what if there were frictional losses associated with moving information on a substrate? Indeed, many modes of communication suffer from such frictional losses. We propose to model these losses as proportional to “bit-meters,” i.e., the product of “mass” of information (i.e., the number of bits) and the distance of information transport. We use this information-friction model to understand the fundamental energy requirements on encoding and decoding in communication circuitry. First, for communication across a binary input additive white Gaussian noise channel, we arrive at fundamental limits on bit-meters (and thus energy consumption) for decoding implementations that have a predetermined input-independent length of messages. For encoding, we relax the fixed-length assumption and derive bounds for flexible-message-length implementations. Using these lower bounds, we show that the total (transmit + encoding + decoding) energy-per-bit must diverge to infinity as the target error probability is lowered to zero. Furthermore, the closer the communication rate is maintained to the channel capacity (as the target error probability is lowered to zero), the fast required decoding energy diverges to infinity.

We consider the problem of information embedding where the encoder modifies a white Gaussian host signal in a power-constrained manner to encode a message, and the decoder recovers both the embedded message and the modified host signal. This partially extends the recent work of Sumszyk and Steinberg to the continuous-alphabet Gaussian setting. Through a control-theoretic lens, we observe that the problem is a minimalist example of what is called the triple role of control actions. We show that a dirty-paper-coding strategy achieves the optimal rate for perfect recovery of the modified host and the message for any message rate. For imperfect recovery of the modified host, by deriving bounds on the minimum mean-square error (MMSE) in recovering the modified host signal, we show that Dirty-Paper Coding-based strategies are guaranteed to attain within a uniform constant factor of 16 of the optimal weighted sum of power required in host signal modification and the MMSE in the modified host signal reconstruction for all weights and all message rates. When specialized to the zero-rate case, our results provide the tightest known lower bounds on the asymptotic costs for the vector version of a famous open problem in decentralized control: the Witsenhausen counterexample. Numerically, this tighter bound helps us characterize the asymptotically optimal costs for the vector Witsenhausen problem to within a factor of 1.3 for all problem parameters, improving on the earlier best known bound of 2.

Towards understanding energy requirements for computation with noisy gates, we consider the computation of an arbitrary k-input, k-output binary invertible function. For broader applicability of our results, we allow using some noiseless gates in conjugation with noisy ones. However, we stipulate that the input gates on the computation graph must be separated from the output nodes by a “noisy cut.” We show that for the “information-friction” model proposed recently for energy consumed in circuits, and for binary-input AWGN noise in the computational nodes (with fixed communication schedule), the total (gate + info-friction) energy consumption for reliable computation must diverge to infinity as the target error probability is lowered to zero. Thus, in this model, the capacity of noisy computing is zero regardless of how “rate” of computation is defined: the required energy is unbounded for reliable computation regardless of how efficiently the available resources (e.g. gates, wires, etc.) are used.

Just as there are frictional losses associated with moving masses on a surface, what if there are frictional losses associated with moving information on a substrate? We propose to model these losses as proportional to “bit-meters” i.e., the product of mass of information (i.e., the number of bits) and the distance of information transport. For communication across a binary input AWGN channel decoded by decoders implemented using a simple circuit model, we derive unavoidable lower bounds on bit-meters for decoding computation. These bounds are translated into limits on energy consumption in decoding under the information-friction model. Using these lower bounds we show that the total (transmit + decoding) energy-per-bit must diverge to infinity as the target error probability is lowered.

How do we design an error correcting code and a corresponding decoding implementation to minimize not just the transmit power, but the sum of transmit and decoding power? Recent interest in this question has led to new fundamental results that show the traditional approach of designing the code and the decoder implementation in isolation can be suboptimal. However, joint design of codes and their corresponding decoder implementations can be hard simply because of the sheer number of possibilities for both, and the human effort often required in optimizing the decoder implementation for a given code. In this paper, we suggest taking a middle-path between analyzing theoretical models of decoding and building decoder implementations. Based on circuit simulations of power consumption of decoders for simple regular LDPC codes, we develop circuit models for the decoding power for larger and more complex (but still regular) LDPC codes. These models are then used to search for the best code and corresponding decoder (within a limited set) for a given communication distance and error probability.

We provide fundamental information-theoretic bounds on the required circuit wiring complexity and power consumption for encoding and decoding of error-correcting codes. These bounds hold for all codes and all encoding and decoding algorithms implemented within the paradigm of our VLSI model. This model essentially views computation on a 2-D VLSI circuit as a computation on a network of connected nodes. The bounds are derived based on analyzing information flow in the circuit. They are then used to show that there is a fundamental tradeoff between the transmit and encoding/decoding power, and that the total (transmit + encoding + decoding) power must diverge to infinity at least as fast as cube-root of log 1/pe, where Peis the average block-error probability. On the other hand, for bounded transmit-power schemes, the total power must diverge to infinity at least as fast as square-root of log 1/Pedue to the burden of encoding/decoding.

Does approaching fundamental limits on rates of information acquisitionor transmission fundamentally require increased power consumption in the processing circuitry? Our recent work shows that this is the case for channel coding for some simple circuit and channel models. In this paper, we first develop parallel results for source coding. Reinterpreting existing results on complexity of lossless source coding, we first observe that the sum power consumed in computational nodes in the circuitry of the encoder and the decoder diverges to infinity as the target error probability approaches zero and the coding rate approaches the source entropy. Next, focusing on on-chip wires, we show that the power consumed in circuit wiring also diverges to infinity as the error probability approaches zero. For the closely related problem of recovering a sparse signal, we first derive a fundamental bound on the required number of “finite-capacity” (e.g. quantized or noisy) measurements. By extending our bounds on wiring complexity and power consumption to sparse-signal recovery, we observe that there is a tradeoff between measurement power and power required to compute the recovered signal.

We investigate the behavior of aggregate interference generated by cognitive radios. We find that a phase change occurs in the behavior of aggregate interference as the density of the white-space devices is increased for a fixed protection radius. For a deterministic grid model, the mean of the interference behaves differently depending on whether the problem is one of ``near field'' or ``far field''. For a more realistic Poisson-placement model, we show that the shape of the distribution of interference changes from a heavy-tailed distribution to something that is approximately Gaussian. Investigating models with random fading of signal at each transmitter, we show that fading can alter the boundary of near and far fields. These phase-changes suggest that in designing rules for whitespace devices, the FCC rules may have to be sensitive to whether the situation is one of near or far field. For Poisson placement of nodes, our results also suggest that central limit theorem-style arguments might help in obtaining a conceptually and computationally improved understanding of interference aggregation.

In decentralized control, a control agent often has the possibility of `signaling,' i.e. the ability to affect the observations of other agents, enabling the agents to `talk.' Signaling has been noted to make many decentralized control problems, in particular the celebrated Witsenhausen counterexample, hard. In this paper, in order to refine the understanding of signaling, we identify two separate notions of signaling that relate to Witsenhausen's counterexample: source-simplification and the presence of an implicit communication channel. We isolate the two aspects aspect of signaling by constructing two variations on the counterexample. Studying these variations, we conclude that the source-simplification aspect plays the more significant role in the counterexample. As a demonstration of the utility of this refinement, we formulate and address finite-time-horizon versions of the counterexample and of our second variation on the counterexample. For these problems, we use the understanding developed for Witsenhausen's counterexample to obtain asymptotically-approximately- optimal strategies in some cases. Finally, we suggest a thermodynamic analogy to signaling in the counterexample paralleling a similar analogy for Kalman filtering proposed by Mitter and Newton.

Traditional communication theory focuses on minimizing transmit power. However, communication links are increasingly operating at shorter ranges where transmit power can be significantly smaller than the power consumed in decoding. This paper models the required decoding power and investigates the minimization of total system power from two complementary perspectives. First, an isolated point-to-point link is considered. Using new lower bounds on the complexity of message-passing decoding, lower bounds are derived on decoding power. These bounds show that 1) there is a fundamental tradeoff between transmit and decoding power; 2) unlike the implications of the traditional "waterfall" curve which focuses on transmit power, the total power must diverge to infinity as error probability goes to zero; 3) Regular LDPCs, and not their known capacity-achieving irregular counterparts, can be shown to be power order optimal in some cases; and 4) the optimizing transmit power is bounded away from the Shannon limit. Second, we consider a collection of links. When systems both generate and face interference, coding allows a system to support a higher density of transmitter-receiver pairs (assuming interference is treated as noise). However, at low densities, uncoded transmission may be more power-efficient in some cases.

The purpose of this paper is to develop an information-theoretic understanding of the tradeoffs between decoder power, probability of error and decoding throughput. We start by considering the power consumed in the decoder circuit's interconnects, modeled as a lumped capacitor and resistor. After making simplifying assumptions about the decoder circuit, we use a sphere-packing technique to lower bound the decoding error probability for a given number of clock-cycles (or iterations). The analysis can be used to give lower bounds on probability of error versus total decoding power at a fixed decoding throughput.

We consider the problem of two-stage signal cancelation based on noisy observations. This problem turns out to be an extension of the Witsenhausen counterexample - a famous open problem in distributed control. Cost is imposed on the power expended by the first controller, and the residual signal after the actions of the two controllers. Along the lines of a recent approximate solution to the Witsenhausen counterexample, we provide an approximate solution to this distributed signal cancelation problem to within a constant factor. This approximation holds uniformly over all problem parameters and for all vector lengths.

The problem considered here is that of wireless information and power transfer across a noisy coupled-inductor circuit, which is a frequency-selective channel with additive white Gaussian noise. The optimal tradeoff between the achievable rate and the power transferred is characterized given the total power available. The practical utility of such systems is also discussed.

The problem of minimizing the total (transmit and decoding) energy required for communicating over a two-receiver Gaussian broadcast channel is investigated. For achieving a specified rate-tuple, joint broadcast schemes (e.g. superposition coding) require smaller transmit energy per-bit than the conceptually simpler time-division multiplexing (TDM) based schemes. However, for short distance communication, the energy expended in the decoding can be comparable to that required in the transmission. Two technical advances are introduced to understand these energy costs: (a) an improvement on the best known outer bounds on the error exponents for the Gaussian broadcast problem, and (b) a finer analysis to have these bounds hold for neighborhood sizes instead of block-lengths. Using these results, it is then shown that in some typical short and moderate distance communication scenarios, time-division multiplexing saves on the decoding energy, thereby likely requiring smaller total energy than any joint broadcasting scheme for achieving the target rate and error probabilities. Further, we observe that TDM outperforms joint schemes by larger margins when the ratio of the distances of the receivers from the transmitter is closer to 1.

Recently, we considered a vector version of Witsenhausen's counterexample and used a new lower bound to show that in that limit of infinite vector length, certain quantization-based strategies are provably within a constant factor of the optimal cost for all possible problem parameters. In this paper, finite vector lengths are considered with the vector length being viewed as an additional problem parameter. By applying the ldquosphere-packingrdquo philosophy, a lower bound to the optimal cost for this finite-length problem is derived that uses appropriate shadows of the infinite-length bounds. We also introduce lattice-based quantization strategies for any finite length. Using the new finite-length lower bound, we show that the lattice-based strategies achieve within a constant factor of the optimal cost uniformly over all possible problem parameters, including the vector length. For Witsenhausen's original problem - which corresponds to the scalar case - lattice-based strategies attain within a factor of 8 of the optimal cost. Based on observations in the scalar case and the infinite-dimensional case, we also conjecture what the optimal strategies could be for any finite vector length.

A green code attempts to minimize the total energy per-bit required to communicate across a noisy channel. The classical information-theoretic approach neglects the energy expended in processing the data at the encoder and the decoder and only minimizes the energy required for transmissions. Since there is no cost associated with using more degrees of freedom, the traditionally optimal strategy is to communicate at rate zero. In this work, we use our recently proposed model for the power consumed by iterative message passing. Using generalized sphere-packing bounds on the decoding power, we find lower bounds on the total energy consumed in the transmissions and the decoding, allowing for freedom in the choice of the rate. We show that contrary to the classical intuition, the rate for green codes is bounded away from zero for any given error probability. In fact, as the desired bit-error probability goes to zero, the optimizing rate for our bounds converges to 1.

A transmitter may have non-causal knowledge of the interference signal being transmitted by another user. Recently, Tarokh and others have raised the possibility of exploiting this knowledge to increase the data rates of a cognitive radio. However, there is a difference between knowing the signal transmitted by the primary and the actual interference at our receiver since there is a wireless channel between these two points. This raises the interesting problem of finding the achievable rates for a compound Gel'fand-Pinsker channel. The problem was addressed recently in the work by Mitran et al, where the authors gave some upper and lower bounds to the achievable rates, with an emphasis on fading channels. But the upper bounds in that work are sometimes non-computable. In this work, we derive computable upper bounds on the outage capacity for a channel where the primary signal can be Rayleigh faded at our receiver.

In this correspondence, we consider the class of finite-state Markov channels (FSMCs) in which the channel behaves as a binary symmetric channel (BSC) in each state. Upper bounds on the rate of LDPC codes for reliable communication over this class of FSMCs are found. A simple upper bound for all noninverting FSMCs is first derived. Subsequently, tighter bounds are derived for the special case of Gilbert–Elliott (GE) channels. Tighter bounds are also derived over the class of FSMCs considered. The latter bounds holdalmost-surelyfor any sequence ofrandomly constructedLDPC codes of given degree distributions. Since the bounds are derived for optimal maximum-likelihood decoding, they also hold for belief propagation decoding. Using the derivations of the bounds on the rate, some lower bounds on the density of parity check matrices for given performance over FSMCs are derived.

Geolocation using received signal strength (RSS) has large errors due to multipath fading, since fading results in high variations in RSS. We show how and when spatial diversity combined with channel knowledge at the receiver can be used to combat fading effects to increase accuracy in location estimation. We then propose a simple scheme for distance estimation, characterize the channels for which improvement in distance estimates can be thus obtained and prove that the mean square error of the distance estimate converges to zero with increasing diversity order. It is observed that the improvement can always be obtained for the Rayleigh channel, and for the Nakagami-m channel if the parameter m remains the same regardless of the distance.

Recently, there has been work in use of LDPC codes over channels with memory, in particular, over Gilbert-Elliott (GE) channels. In this paper, we derive expressions for upper bounds on the rate of LDPC codes for reliable communication over a large class (non-oscillatory and non-inverting) of GE channels using the methods for memoryless channels.