On a Lower Bound for the Redundancy of Reliable Networks with Noisy Gates

Authors

Nicholas Pippenger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1991

Abstract

A proof is provided that a logarithmic redundancy factor is necessary for the reliable computation of the parity function by means of a network with noisy gates. This result was first stated by R.L. Dobrushin and S.I. Ortyukov (1977). However, the authors believe that the analysis given by Dobrushin and Ortyukov is not entirely correct. The authors establish the result by following the same steps and by replacing the questionable part of their analysis with entirely new arguments.

Rights Information

© 1991 Institute of Electrical and Electronics Engineers

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1109/18.79921

Recommended Citation

Pippenger, N.; Stamoulis, G.D.; Tsitsiklis, J.N., "On a lower bound for the redundancy of reliable networks with noisy gates," Information Theory, IEEE Transactions on , vol.37, no.3, pp.639,643, May 1991. doi: 10.1109/18.79921