Depth Optimized Synthesis of Symmetric Boolean Functions

Symmetric Boolean functions are characterized by the fact that their output can be determined by the Hamming weight of their inputs. Symmetric Boolean functions are essential for many complex systems and possess significant cryptographic properties.Due to their popularity and significance, research has been focusing on optimization of synthesis strategies for symmetric Boolean functions. However, none of them has targeted optimizing the depth of the final synthesis, yet.In this paper, we propose a synthesis scheme for symmetric Boolean functions which generates circuits with a worst-case depth of O(log
²
n). To the best of our knowledge we are the first to propose a synthesis scheme that aims at reducing the depth of the generated circuits for symmetric Boolean functions. In the experiments we show that our approach allows to reduce the depth of the final implementation by up to 25.93% compared to the state-of-the-art.