On the minimization of complexity and automation of efficient representation of boolean functions in classes of formulas and circuits

A method for synthesizing Boolean formulas intended for the efficient construction of circuit composed on functional elements, which is also suitable for minimal complexity circuits, is developed. Upper bounds on the implementation complexity of arbitrary Boolean functions in terms of the Zhegalkin...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer & systems sciences international 2013-07, Vol.52 (4), p.618-627
Main Authors: Egorova, E. K., Cheburakhin, I. F.
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Artificial Intelligence
Automation
Boolean
Boolean algebra
Boolean functions
Circuits
Complexity
Construction
Control
Decomposition
Engineering
Integrated circuits
Mechatronics
Optimization
Production methods
Representations
Robotics
Studies
Systems science
Upper bounds
Variables
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A method for synthesizing Boolean formulas intended for the efficient construction of circuit composed on functional elements, which is also suitable for minimal complexity circuits, is developed. Upper bounds on the implementation complexity of arbitrary Boolean functions in terms of the Zhegalkin basis are determined. A computational method for improving these bounds is proposed. A method for deriving certain countable classes of Boolean functions of minimal complexity is also recommended.
ISSN:1064-2307
1555-6530
DOI:10.1134/S1064230713030064