I am working on Bent functions that are of interest in cryptography. I developed an algorithm that construct such functions. However, I need some tools to calculate boolean expression from the truth table. Is there such a application or applet available? (Actually I am interested in expressions without any NOTs).
|show 3 more comments|
It depends on what you are interested in, when building your expression. If you want to optimize for speed and/or expression size, then the problem is hard, and no good solution is known. You can either try to enumerate all expressions, looking for a match with your table (this is exponential in the size of the expression, so it becomes prohibitive real fast); or you can start with a generic expression as a tree of multiplexers then try to find local shortcuts.
You can often work with the "fake multiplexer": for inputs $a$ and $b$, and control $c$, output $a \oplus (b \wedge c)$: in this way, the bit $c$ selects between values $a$ (if $c = 0$) and $a \oplus b$ (if $c = 1$). For a function $f : n \rightarrow 1$ ($n$ input bits, $1$ output bit), you work recursively:
(Note: if you have only bitwise AND, OR and XOR, and not access to constants, then you cannot build all functions; in particular, you won't be able to make a $1$ out of an all-$0$ input. If you really don't want a NOT or the equivalent "$\oplus 1$", and the output of your function for an all-zero input is $1$, then there is no solution. On the other hand, if the function output for an all-zero input is $0$, then you can make a serviceable $1$ by ORing all input bits together.)
(Note 2: if you want to optimize for speed on software platforms, be aware that not all processor architectures offer the same set of operations. On some processors you have elementary XORNOT or NOTXOR. This can change the achievable speed quite a lot.)