Truth tables in code? How to structure state machine?

Question

I have a (somewhat) large truth table / state machine that I need to implement in my code (embedded C). I anticipate the behavior specification of this state machine to change in the future, and so I'd like to keep this easily modifiable in the future.

My truth table has 4 inputs and 4 outputs. I have it all in an Excel spreadsheet, and if I could just paste that into my code with a little formatting, that would be ideal.

I was thinking I would like to access my truth table like so:

u8 newState[] = decisionTable[input1][input2][input3][input4];

And then I could access the output values with:

setOutputPin( LINE_0, newState[0] );
setOutputPin( LINE_1, newState[1] );
setOutputPin( LINE_2, newState[2] );
setOutputPin( LINE_3, newState[3] );

But in order to get that, it looks like I would have to do a fairly confusing table like so:

static u8 decisionTable[][][][][] =
 {{{{ 0, 0, 0, 0 },
    { 0, 0, 0, 0 }},
   {{ 0, 0, 0, 0 },
    { 0, 0, 0, 0 }}},
  {{{ 0, 0, 1, 1 },
    { 0, 1, 1, 1 }},
   {{ 0, 1, 0, 1 },
    { 1, 1, 1, 1 }}}},
 {{{{ 0, 1, 0, 1 },
    { 1, 1, 1, 1 }},
   {{ 0, 1, 0, 1 },
    { 1, 1, 1, 1 }}},
  {{{ 0, 1, 1, 1 },
    { 0, 1, 1, 1 }},
   {{ 0, 1, 0, 1 },
    { 1, 1, 1, 1 }}}};

Those nested brackets can be somewhat confusing -- does anyone have a better idea for how I can keep a pretty looking table in my code?

Thanks!

Edit based on HUAGHAGUAH's answer:

Using an amalgamation of everyone's input (thanks -- I wish I could "accept" 3 or 4 of these answers), I think I'm going to try it as a two dimensional array. I'll index into my array using a small bit-shifting macro:

#define SM_INPUTS( in0, in1, in2, in3 ) ((in0 << 0) | (in1 << 1) | (in2 << 2) | (in3 << 3))

And that will let my truth table array look like this:

static u8 decisionTable[][] = {
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 1, 1 },
{ 0, 1, 1, 1 },
{ 0, 1, 0, 1 },
{ 1, 1, 1, 1 },
{ 0, 1, 0, 1 },
{ 1, 1, 1, 1 },
{ 0, 1, 0, 1 },
{ 1, 1, 1, 1 },
{ 0, 1, 1, 1 },
{ 0, 1, 1, 1 },
{ 0, 1, 0, 1 },
{ 1, 1, 1, 1 }};

And I can then access my truth table like so:

decisionTable[ SM_INPUTS( line1, line2, line3, line4 ) ]

I'll give that a shot and see how it works out. I'll also be replacing the 0's and 1's with more helpful #defines that express what each state means, along with /**/ comments that explain the inputs for each line of outputs. Thanks for the help, everyone!

Answer 1

No need for a multidimensional table. With a 4 bit => 4 bit mapping, you can have a single u8[16] array mapping inputs to outputs. State lookups will be much cheaper, and you can extract individual bits with some shift-and-mask ops.

If the algorithm to populate rows is easy to codify, you could #define a macro to populate each row by index number.

Answer 2

I'd suggest either (preferred approaches first):

• Use a macro to intialize each "row" - this will hide the braces within the macro call.
• Use comments to break up the rows.
• Use an init function to initialize the context explicitly - perhaps use functions to initialize each section. This is similar to the first option above but has a disadvantage that the init function must be invoked before the state machine can be used.

Answer 3

Personally, I'd read it from a configuration file. CSV, perhaps, which is easy to export to from Excel. Or you could just copy and paste from Excel into plain text, which gives you space-separated values, which is equally easy to import.

This also means, given that you are working with C, that you won't have to recompile your code each time the decision table changes.

Answer 4

if your truth-table is all booleans, you could just collapse it to a list of pairs, e.g.

1111,0000
1110,0110
...

for data compression, represent the values as bytes (two nybbles)...

where/how to store it for soft-coding in your particular embedded-system configuration, only you can say ;-)

Answer 5

If the truth table is really only 4x4x4x4 then I'd use macros. If it's ever going to grow past that, I'd use Ragel. Chances are it will make smaller, faster C code than you will.

Answer 6

I don't see any reference to the current state in order to get your output state. This means it is not a state machine, but only a truth table. There are four inputs, so there are only 16 possible input combinations. So, a table with 16 positions ought to do it.

Answer 7

Usually when you have a problem like this, one tries to reduce it to a simple boolean formula. I don't see why that wouldn't be the best approach here. It would be much more compact and more readable, plus it has the potential to be faster (I imagine a handful of ANDs and ORs would execute more quickly than the collection of multiplies/shifts + memory access needed for the lookup table approach). The easiest way to reduce this table to a boolean formula is with a K-Map.