2
$\begingroup$

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).

Improve this question
$\endgroup$
3
  • $\begingroup$ This sounds quite difficult... $\endgroup$
    – Yuval Filmus
    Aug 27, 2017 at 12:31
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Aug 27, 2017 at 17:34
  • $\begingroup$ I am indeed looking for a practical algorithm to implement this for the case n=8 and k=4. $\endgroup$
    – QB13
    Aug 28, 2017 at 0:58

1 Answer 1

Reset to default
3
$\begingroup$

The following decision version of your problem is NP-complete:

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.