Patent ID: 6868536
Filing Date: 2005-03-15
Classification: G06F

Abstract:
1. A method to construct a symmetry tree of a Boolean function, comprising: (a) setting an initial set of the trees T={D (b) applying a procedure to construct a 1-symmetric part for the set T and the function ƒ, wherein T′={D′ (c) determining whether |T′|=1, wherein |T′| is the cardinality of the set T′, and if |T′|=1, then the tree D′ (d) determining whether |T′|>1, if |T′|>1, then m is set equal to 2, where m corresponds to m-symmetric part of the set T′, and proceeding to step (e); (e) determining whether m>|T′|/2, and if so, constructing tree N(T′) utilizing an N-union operation and returning the tree as the result of the operation, otherwise proceeding to step (f); (f) determining whether m≦|T|′/2, and if so, applying a procedure to construct an m-symmetric part to the set T′ and the function ƒ, wherein T″ is the result of the procedure, and proceeding to step (g); and (g) determining whether T′=T″, and if so, m is set equal to m+1 and the method returns to step (f), if T′≠T″, then T is set equal to T″ and the method returns to step (b). wherein the method is utilized to minimize path delays and eliminate ramptime violations in internal synthesis tools for intergrated circuits.