Signal propagation and noisy circuits
Signal propagation and noisy circuits
复制标题
信号传播和噪声电路
DOI：
--
复制
发表时间：
1999
影响因子：
2.5
通讯作者：
L. Schulman
中科院分区：
文献类型：
--
作者：
W. Evans;L. Schulman
当信号被随机噪声破坏时，信号所携带的信息会衰减。当消息在有噪声的信道上传输时，以及当有噪声的组件执行计算时，都会发生这种情况。我们首先研究了这种信号衰减的背景下的通信，并获得一个严格的约束的信息减少的速度作为一个信号穿过一个嘈杂的信道。然后，我们使用这个信息理论的结果，以获得深度下界的噪声电路模型的计算所定义的冯诺依曼。在这个模型中，每个组件都以固定的概率独立地失败（产生1而不是0，反之亦然），但电路的输出需要以高概率正确。冯·诺依曼展示了如何在这个模型中构建电路，可靠地计算函数，并且对于该函数来说，比无噪声电路深不超过一个常数因子。我们提供了一个可靠的计算所需的电路深度的乘法增加的下限，和可靠的计算是可能的噪声的最大水平上的上限。
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.