The Unison algorithm
Rok Sosič, Jun Hua Gu, Robert R. Johnson · ACM Transactions on Design Automation of Electronic Systems · 1996
We present a Unison algorithm to evaluate arbitrarily complex Boolean expressions. This novel algorithm, based on the total differential of a Boolean function, enables fast evaluation of Boolean expressions in software. Any combination of Boolean operations can be packed into the bits of one computer word and evaluated in parallel by bitwise logical operations. Sample runs of the Unison algorithm show that many Boolean operations can evaluated in one clock cycle. The Unison algorithm is able to evaluate Boolean expressions at an execution speed that is comparable to compiled evaluation while retaining the flexibility of interpreted approaches. The algorithm lends itself well to many practical applications.