 |
Center for Nonlinear Studies |
We show how models of random formulae can be mapped onto a physical framework and employ methods of statistical physics, developed specifically to analyze the typical behavior of random disordered systems, to gain insight into the behavior of noisy Boolean random formulae. The stability of the circuit towards input-layer perturbations and its dependence on the input magnetization have been studied to establish the main characteristics of the generated formulae. To investigate the properties of noisy circuits we consider two copies of the same topology with different temperatures representing the noisy and noiseless versions of the same circuit. We show that the typical-case macroscopic behavior observed corresponds straightforwardly to the bounds obtained in the information theory literature for specific cases. Being very general, the framework is extended to consider further properties of random Boolean formulae for different gates, the level of error and function-bias expected at any depth, the sensitivity to input perturbations and expected convergence rate depending on the input bias, gate properties and gate-noise level. This framework enables one to discover typical properties of noisy computation that are inaccessible via traditional methods of information theory and complements the analysis carried out in the theoretical computer science and information theory communities.
Host: IS&T