CaltechAUTHORS
  A Caltech Library Service

Signal propagation and noisy circuits

Evans, William S. and Schulman, Leonard J. (1999) Signal propagation and noisy circuits. IEEE Transactions on Information Theory, 45 (7). pp. 2367-2373. ISSN 0018-9448 http://resolver.caltech.edu/CaltechAUTHORS:EVAieeetit99

[img]
Preview
PDF
See Usage Policy.

161Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:EVAieeetit99

Abstract

The information carried by a signal decays when the signal is corrupted by random noise. This occurs when a message is transmitted over a noisy channel, as well as when a noisy component performs computation. We first study this signal decay in the context of communication and obtain a tight bound on the rate at which information decreases as a signal crosses a noisy channel. We then use this information theoretic result to obtain depth lower bounds in the noisy circuit model of computation defined by von Neumann. In this model, each component fails (produces 1 instead of 0 or vice-versa) independently with a fixed probability, and yet the output of the circuit is required to be correct with high probability. Von Neumann showed how to construct circuits in this model that reliably compute a function and are no more than a constant factor deeper than noiseless circuits for the function. We provide a lower bound on the multiplicative increase in circuit depth necessary for reliable computation, and an upper bound on the maximum level of noise at which reliable computation is possible.


Item Type:Article
Additional Information:© Copyright 1999 IEEE. Reprinted with permission. Manuscript received October 1, 1997; revised May 17, 1999. The work of W.S. Evans was supported in part by NSF under Grant CCR 92-01092. The work of L.J. Schulman was supported by an NSF Post-Doctoral Fellowship. The material in this paper was presented in part at the 34th Symposium on Foundations of Computer Science, Palo Alto, CA, 1993 and at the IEEE International Symposium on Information Theory, Whistler, BC, Canada, 1995. Communicated by R. L. Cruz, Associate Edotpr for Communication Networks. The authors wish to thank N. Pippenger for helpful consultations.
Subject Keywords:Data processing inequality, mutual information, noisy circuit complexity
Record Number:CaltechAUTHORS:EVAieeetit99
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:EVAieeetit99
Alternative URL:http://dx.doi.org/10.1109/18.796377
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:5241
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:05 Oct 2006
Last Modified:26 Dec 2012 09:04

Repository Staff Only: item control page