We typically synthesize combinational Boolean logic functions into structures based on two-level or multi-level implementations. For complex logic functions, a two-level implementation has less delay but takes a larger silicon area than a multi-level implementation.

The authors of this paper present a method that uses a three-level logic implementation. The method initially searches for regular features of the function that reduce the dimension of the Boolean space of the given function. They present an algorithm for identifying the dimension-reducible (D-reducible) function based on exclusive-OR functions; exclusive-OR gates form the first level of logic implementation. If we then project the function onto the resulting D-reducible space, there is a reduced Hamming distance between individual ON-set terms, which thereby increases the probability of finding adjacent ON-set terms that can be combined, resulting in simpler sum-of-product (SOP) functions. SOP functions form the second and third levels of logic implementation.

When applied to a number of standard benchmark circuits, the proposed method results in a good tradeoff in area and delay, as compared to two-level and multi-level implementations.