Decomposition based approach for the synthesis of threshold logic circuits
View Patent ↗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.
1. A method implemented in a computer system comprising a processor, comprising:
determining, by the processor, that a Boolean function satisfies one or more predefined conditions for being a threshold function, the one or more predefined conditions comprising a condition that both a positive cofactor and a negative cofactor of the Boolean function are threshold functions;
determining, by the processor, that 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;
identifying, by the processor, the Boolean function as a threshold function in response to determining that the Boolean function satisfies the one or more predefined conditions for being a threshold function and determining that the weights for the positive cofactor are equal to the weights for the negative cofactor; and
determining, by the processor, weights and a threshold value that characterize a threshold logic gate that implements the threshold function corresponding to the Boolean function based on the weights and the threshold values for the positive cofactor and the negative cofactor.
2. The method of claim 1 wherein the one or more predefined conditions for being a threshold function further comprise a condition that a support set for one of the positive and negative cofactors contain a support set of the other one of the positive and negative cofactors.
3. The method of claim 1 wherein the one or more predefined conditions for being a threshold function further comprise a condition that one of the positive and negative cofactors be contained by the other one of the positive and negative cofactors.
4. The method of claim 1 wherein the one or more predefined conditions for being a threshold function further comprise a condition that the weights for the positive and negative cofactors have the same wavy ordering.
5. The method of claim 1 wherein the Boolean function is a sub-function of another Boolean function.
6. A method implemented in a computer system comprising a processor, comprising:
determining, by the processor, that a Boolean function satisfies one or more predefined conditions for being a threshold function, the one or more predefined conditions comprising a condition that both a positive cofactor and a negative cofactor of the Boolean function are threshold functions;
determining, by the processor, that weights for the positive cofactor and weights for the negative cofactor are not equal, 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;
equalizing, by the processor, the weights for the positive and negative cofactors in response to determining that the weights for the positive cofactor and the weights for the negative cofactor are not equal;
identifying, by the processor, the Boolean function as a threshold function in response to determining that the Boolean function satisfies the one or more predefined conditions and equalizing the weights for the positive and negative cofactors; and
determining, by the processor, weights and a threshold value that characterize a threshold logic gate that implements the threshold function corresponding to the Boolean function based on the weights and the threshold values for the positive cofactor and the negative cofactor.
7. The method of claim 6 further comprising, prior to equalizing the weights for the positive and negative cofactors:
determining that a wavy ordering of the weights for the positive and negative cofactors are not different; and
in response to determining that the wavy ordering of the weights for the positive and negative cofactors are not different, proceeding to the step of equalizing the weights for the positive and negative cofactors.
8. The method of claim 6 wherein equalizing the weights for the positive and negative cofactors comprises:
determining that support sets of the positive and negative cofactors are not equal; and
in response to determining that the support sets of the positive and negative cofactors are not equal, resynthesizing the weights for one of the positive and negative cofactors using don't care variables to equalize the weights for the positive and negative cofactors.
9. The computerized method of claim 6 wherein equalizing the weights for the positive and negative cofactors comprises:
determining that support sets of the positive and negative cofactors are equal;
in response to determining that the support sets of the positive and negative cofactors are equal, determining that the weights for one of the positive and negative cofactors are valid for the other one of the positive and negative cofactors; and
in response to determining that the weights for one of the positive and negative cofactors are valid for the other one of the positive and negative cofactors, setting the weights for the other one of the positive and negative cofactors equal to the weights for the one of the positive and negative cofactors.
10. The method of claim 6 wherein equalizing the weights for the positive and negative cofactors comprises:
determining that support sets of the positive and negative cofactors are equal;
in response to determining that the support sets of the positive and negative cofactors are equal, determining that a sum of the weights for the positive and negative cofactors is a valid set of weights for both the positive and negative cofactors; and
in response to determining that the sum of the weights for the positive and negative cofactors is a valid set of weights for both the positive and negative cofactors, setting the weights for both the positive and negative cofactors equal to the sum of the weights for the positive and negative cofactors.
11. A non-transitory computer readable medium storing software for instructing a controller of a computing device to:
determine that a Boolean function satisfies one or more predefined conditions for being a threshold function, the one or more predefined conditions comprising a condition that both a positive cofactor and a negative cofactor of the Boolean function are threshold functions;
determine that 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;
identify the Boolean function as a threshold function in response to determining that the Boolean function satisfies the one or more predefined conditions for being a threshold function and determining that the weights for the positive cofactor are equal to the weights for the negative cofactor; and
determine weights and a threshold value that characterize a threshold logic gate that implements the threshold function corresponding to the Boolean function based on the weights and the threshold values for the positive cofactor and the negative cofactor.