CODEWITHSUNDEEP
calgorithmtruthtablekarnaugh-map
Satrapes
Satrapes

Reputation: 183

Optimal implementation of truth table

I have identified a truth table such as the one below

prev_state| input1         | input2 |next_state| Action
(def/new) |(Disable/Enable)|(Off/On)|          |
def       | D              | Off    | def      | Nothing
def       | D              | On     | def      | Nothing
def       | E              | Off    | def      | Nothing
def       | E              | On     | new      | call function1
new       | D              | Off    | def      | call function2
new       | D              | On     | def      | call function2
new       | E              | Off    | def      | call function2
new       | E              | On     | new      | Nothing

I was wondering what is the minimum number of checks that you need to achieve this.

Is my thought to use a Karnaugh map such as the following one:

    00| 01| 11| 10 
  -----------------
0 | A | A | B | A |  
  -----------------
1 | C | C | A | C |  
  -----------------

Where A corresponds to nothing, B to call function1 and C to call function2

According to what I see you have 2 combinations of 2 A's and a single A total of 3 for A 1 for B and 2 combinations of 2 C's

Does that mean that the minimum number of compares is 3+1+2=6? But because A's do nothing the minimum implementation would require only the 3 combinations for B and C?

Test implementation

if (prev_state == new && input1 == disable) {
    function2();
}
else if (prev_state == new && input2 == Off) {
    function2();
}
else if (input1 == enable && input2 == On) {
    function1();
}

Also now that I see it which is better the above or this one:

if ((prev_state == new && input1 == disable) || (prev_state == new && input2 == Off)) {
    function2();
}
else if (input1 == enable && input2 == On) {
    function1();
}

Thank you for those who proposed a look up table which is O(1) but takes up space in memory. I now realize that I would prefer to have a solution that doesn't use extra memory. Do you agree that using Karnaugh maps is a valid method to derive minimum amount of comparisons?

Upvotes: 1

Views: 170

Answers (4)

chux
chux

Reputation: 154169

I was wondering what is the minimum number of checks that you need to achieve ...

Zero. Use a look-up table

void f_Nothing(void) {
  ; // do nothing
}

void f_function1(void) {
  ;  // something interesting
}

void f_function2(void) {
  ;  // something interesting
}

int main(void) {

  typedef void (*fun_type)(void);

  fun_type f[2][2][2] = { //
      {{f_Nothing, f_Nothing}, {f_Nothing, f_function1}}, 
      {{f_function2, f_function2}, {f_function2, f_Nothing}}};
  bool prev_state, input1, input2;
  //...
  f[prev_state][input1][input2]();

OP later commented looking for a solution that ... doesn't use further extra memory.

if ( (input1 == E && input2 == ON) && (prev_state == def)) function1();
if (!(input1 == E && input2 == ON) && (prev_state == new)) function2();

// or

if (input1 == E && input2 == ON) {
  if (prev_state == def) function1();
} else {
  if (prev_state == new) function2();
}

Upvotes: 7

kiran Biradar
kiran Biradar

Reputation: 12742

I would do something like below.

int check = (int)((prev_state == new) << 2 | (input1 == E)<<1 | (input2 == on));

/*def       | E              | On     | new      | call function1 == 3
  new       | D              | Off    | def      | call function2 == 4
  new       | D              | On     | def      | call function2 == 5
  new       | E              | Off    | def      | call function2 == 6 */

if (check == 4 || check == 5 || check == 6)
  function2();
else if (check == 3)
  function1();

Upvotes: 0

Ian Abbott
Ian Abbott

Reputation: 17503

You can remove some repeated tests, but whether or not it makes much difference in practice depends on the compiler optimizations.

if (prev_state == new) {
    if (input1 == disable || input2 == Off) {
        function2();
    }
} else {
    if (input1 == enable && input2 == On) {
        function1();
    }
}

Or:

if (input1 == disable || input2 == Off) {
    if (prev_state == new) {
        function2();
    }
} else {
    if (prev_state == def) {
        function1();
    }
}

Upvotes: 1

bruno
bruno

Reputation: 32596

If the behavior is static it is useless to do tests, you can

  • use a 3 dimensional array where each value is the couple next-state and action, first dimension is prev_state 0/1, second input 1 D/E -> 0/1, third input2 off/on -> 0/1

  • but because your input are very limited you can also encode the 3 indexes in only one = prev_state * 4 + input1 * 2 + input2 and use a simple vector of size 8. As Schwern suggest in a remark you can also doing a switch/case on the result of prev_state * 4 + input1 * 2 + input2

Upvotes: 2

Related Questions