US 2011/0214095 A1 · DECOMPOSITION BASED APPROACH FOR THE SYNTHESIS OF THRESHOLD LOGIC CIRCUITS

Abstract

Systems and methods for identifying a Boolean function as either a threshold function or a non-threshold function are disclosed. In one embodiment, in order to identify a Boolean function as either a threshold function or a non-threshold function, a determination is first made as to whether the Boolean function satisfies one or more predefined conditions for being a threshold function, where the one or more predefined conditions include a condition that both a positive cofactor and a negative cofactor of the Boolean function are threshold functions. If the one or more predefined conditions are satisfied, a determination is made as to whether weights for the positive and negative cofactors are equal. If the weights for the cofactors are equal, then the Boolean function is determined to be a threshold function. Further, in one embodiment, this threshold function identification process is utilized in a threshold circuit synthesis process.

Claims23

Dependent claims

A computerized method for identifying a Boolean function as either a threshold function or a non-threshold function comprising:

determining whether the Boolean function satisfies one or more predefined conditions for being a threshold function, the one or more predefined threshold conditions comprising a condition that both a positive cofactor and a negative cofactor of the Boolean function are threshold functions;
if the one or more predefined conditions for being a threshold function are satisfied, determining whether weights for the positive cofactor are equal to weights for the negative cofactor, the weights for the positive cofactor being weights that together with a threshold value for the positive cofactor define a threshold function that corresponds to the positive cofactor and the weights for the negative cofactor being weights that together with a threshold value for the negative cofactor define a threshold function that corresponds to the negative cofactor;
and
if the weights for the positive cofactor and the weights for the negative cofactor are equal, identifying the Boolean function as a threshold function.

1 more element

A computerized method for synthesizing a threshold logic circuit comprising:

representing a Boolean function as a cofactor tree comprising a plurality of nodes;
identifying functions corresponding to the plurality of nodes in the cofactor tree as either threshold functions or non-threshold functions beginning with leaf nodes of the cofactor tree and proceeding up the cofactor tree;
if the function corresponding to one of the plurality of nodes in the cofactor tree is a non-threshold function, substituting a literal that represents an output of a threshold gate for one of a positive cofactor and a negative cofactor of the function corresponding to the one of the plurality of nodes in the cofactor tree such that the function corresponding to the one of the plurality of nodes in the cofactor tree is transformed to a threshold function.

Dependencies are inferred from the claim text.

Decomposition based approach for the synthesis of threshold logic circuits

Life of this patent

Decomposition based approach for the synthesis of threshold logic circuits

Life of this patent

Abstract

Claims23