Function decomposition and synthesis using linear sifting

In order to simplify a synthesis task for particularly hard functions it is sometimes inevitable to decompose the function in a preprocessing step. We propose a new algorithm for automatically decomposing a target function by extracting a linear filter within the synthesis process. The algorithm is an application of the Linear Sifting algorithm which has been proposed in Meinel et al. (1996). Using this method we were able to synthesize functions with standard tools which fail otherwise