# How to find minimum number of k-input LUTs needed to express a n variable boolean function?

An k-input LUT (look up table) takes in atmost k-inputs and gives 1 output (which is a function of the k inputs). I need to devise an algorithm to find the minimum number of k-input LUT's required to express a n variable boolean function.

For example : - n=8 and k=4 8 input variables are a0,a1...a7

1) f1(a0,a1,..a7)= a0*a1 +a3*a4 + a5*a7 + a6*a8 Requires 3 LUTs : LUT1 :a0*a1 + a3*a4 =x1 LUT2 :a5*a7 + a6*a8 =x2 LUT3 : x1+x2

2) f2(a0,a1,..a7)= a0*a1 +a3*a4 + a5*a7 + a6 Requires 2 LUTs : LUT1: a0*a1 +a3*a4 =x1 LUT2: x1+a5*a7+a6

NOTE: I want to solve this for the particular case of n=8 and k=4. Though, I would like to extend it to other cases like (n,k)= (8,2).

• This sounds quite difficult... Aug 27, 2017 at 12:31
• If you are looking for practical algorithms, perhaps you could look at the literature on logic synthesis; and it might help if you told us typical range of values of n,k.
– D.W.
Aug 27, 2017 at 17:34
• I am indeed looking for a practical algorithm to implement this for the case n=8 and k=4.
– QB13
Aug 28, 2017 at 0:58

Given a formula $f$, an integer $k$, and an integer $s$ (encoded in unary), determine whether $f$ can be represented using at most $s$ many $k$-input LUT's.
Indeed, you can easily solve SAT by asking whether the instance of SAT can be represented using at most one 0-input LUT. If you disallow $k=0$, you need to work a bit harder: a formula $\phi$ is satisfiable iff $\phi \oplus x$ (where $x$ is a fresh variable) can be represented using at most one 1-input LUT.