Noisy random Boolean formulae: A statistical physics perspective

Alexander Mozeika, David Saad, and Jack Raymond
Phys. Rev. E 82, 041112 – Published 14 October 2010

Abstract

Properties of computing Boolean circuits composed of noisy logical gates are studied using the statistical physics methodology. A formula-growth model that gives rise to random Boolean functions is mapped onto a spin system, which facilitates the study of their typical behavior in the presence of noise. Bounds on their performance, derived in the information theory literature for specific gates, are straightforwardly retrieved, generalized and identified as the corresponding macroscopic phase transitions. The framework is employed for deriving results on error-rates at various function-depths and function sensitivity, and their dependence on the gate-type and noise model used. These are difficult to obtain via the traditional methods used in this field.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
1 More
  • Received 16 March 2010

DOI:https://doi.org/10.1103/PhysRevE.82.041112

©2010 American Physical Society

Authors & Affiliations

Alexander Mozeika1,*, David Saad1, and Jack Raymond2

  • 1The Non-linearity and Complexity Research Group, Aston University, Birmingham B4 7ET, United Kingdom
  • 2Department of Physics, The Hong Kong University of Science and Technology, Clear Water Bay, Hong Kong, China

  • *a.s.mozeika@aston.ac.uk

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 82, Iss. 4 — October 2010

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×