Examples



mdbootstrap.com



 
Статья
2017

About complexity of implementing threshold functions


O. N. MuzychenkoO. N. Muzychenko
Русская математика
https://doi.org/10.3103/S1066369X17070052
Abstract / Full Text

We study properties and ways of classification of threshold functions as well as known estimates of complexity of implementing in the functional elements type of circuits. We determine a dependence of the maximum values of variables weights on their number. Using the intermediate conversion method we obtain a precise upper bound of complexity of implementing arbitrary threshold functions in the functional elements type of circuits.

Author information
  • Baltic State Technical University “Voenmekh” named after D. F. Ustinov, ul. Pervaya Krasnoarmeiskaya 1, St.-Petersburg, 190005, RussiaO. N. Muzychenko
References
  1. Lupanov, O. V. “Über einen Zugang zur Synthese von Regelungssystemen—das Prinzip der lokalen Kodierung”, Probl. Kibern., No. 14, 31–110 (1965) [in Russian].
  2. Korshunov, A. D. “Monotone Boolean Functions”, Russ. Math. Surv. 58, No. 5, 929–1001 (2003).
  3. Ugol’nikov, A. B. “Über die Realisierung monotoner Funktionen durch Schemata funktionaler Elemente”, Probl. Kibern., No. 31, 167–185 (1976) [in Russian].
  4. Pippenger, N. “The Complexity of Monotone Boolean Functions”, Math. Syst. Theory 11, 289–316 (1977/78).
  5. Muzychenko, O. N. Specialized Methods for Synthesizing Logic Circuits. Part 1. Methods for Synthesizing Logic Circuits of Symmetric and Threshold Functions (Baltiisk State Technical University, St. Petersburg, 2004) [in Russian].
  6. Muzychenko, O. N. “Simplification of Threshold Circuits Designed by the Intermediate Transformation Method”, Avtomat. i Telemekh., No. 12, 164–170 (1990).
  7. Muzychenko, O. N. “The Synthesis of Symmetric-Function Logic Systems by a Combined Method”, Automation and Remote Control 56, No. 5, 727–737 (1995).
  8. Zuev, Yu. A. “Threshold functions and threshold representations of Boolean functions”, Mat.VoprosyKibern., No. 5, 5–61 (1994) [in Russian].
  9. Shabanin, O. V. “About the Complexity of Representations of the Threshold Functions in the Traditional Basis”, Vestn.Mosk. Univ. of Forest, No. 1, 152–155 (2006) [in Russian].
  10. Dertouzos, M. L. Threshold Logic: A Synthesis Approach (MIT. Press, 1965; Mir, Moscow, 1967).
  11. Butakov, E. A. Methods for the Synthesis of Relay Devices From Threshold Elements (Energiya, Moscow, 1970) [in Russian].