Таблицы правды в коде? Как структурировать конечный автомат? - PullRequest
Новая
       7

Таблицы правды в коде? Как структурировать конечный автомат?

10 голосов
/ 02 марта 2009

У меня есть (несколько) большая таблица истинности / конечный автомат, которую мне нужно реализовать в моем коде (встроенный C). Я ожидаю, что спецификация поведения этого конечного автомата изменится в будущем, и поэтому я бы хотел, чтобы в будущем это было легко изменяемым.

Моя таблица истинности имеет 4 входа и 4 выхода. У меня все это есть в электронной таблице Excel, и если бы я мог просто вставить это в свой код с небольшим форматированием, это было бы идеально.

Я думал, что хотел бы получить доступ к моей таблице истинности так: 

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

И тогда я мог получить доступ к выходным значениям с помощью: 

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

Но чтобы получить это, похоже, мне нужно было бы сделать довольно запутанную таблицу, например: 

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 }}}};

Эти вложенные скобки могут несколько сбивать с толку - кто-нибудь может лучше понять, как мне сохранить красивую таблицу в моем коде?

Спасибо!

Редактировать на основе ответа ХУАХАГУА:

Используя объединение всех данных (спасибо - я хотел бы «принять» 3 или 4 из этих ответов), я думаю, что я собираюсь попробовать это как двумерный массив. Я внесу в свой массив индекс с помощью небольшого макроса, сдвигающего биты: 

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

И это позволит моему массиву таблицы истинности выглядеть так: 

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 }};

И тогда я могу получить доступ к своей таблице истинности так: 

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

Я попробую и посмотрю, как это работает. Я также заменю 0 и 1 на более полезные #defines, которые выражают, что означает каждое состояние, вместе с / ** / комментариями, которые объясняют входные данные для каждой строки выходных данных. Всем спасибо за помощь!

Ответы [ 7 ]

4 голосов
/ 02 марта 2009

Я бы предложил либо (предпочтительные подходы в первую очередь):

  • Используйте макрос для инициализации каждой "строки" - это скроет фигурные скобки в вызове макроса.
  • Используйте комментарии, чтобы разбить строки.
  • Используйте функцию init для явной инициализации контекста - возможно, используйте функции для инициализации каждого раздела. Это похоже на первый вариант, описанный выше, но имеет недостаток, заключающийся в том, что перед использованием конечного автомата должна быть вызвана функция init.
3 голосов
/ 02 марта 2009

Нет необходимости в многомерном столе. С 4-битным => 4-битным отображением вы можете иметь один массив u8 [16], отображающий входы на выходы. Поиск состояний будет намного дешевле, и вы можете извлекать отдельные биты с помощью операций сдвига и маски.

Если алгоритм заполнения строк легко кодифицировать, вы можете # определить макрос для заполнения каждой строки по порядковому номеру.

3 голосов
/ 02 марта 2009

Лично я бы прочитал это из файла конфигурации. CSV, возможно, который легко экспортировать из Excel. Или вы можете просто скопировать и вставить из Excel в простой текст, который дает вам разделенные пробелами значения, которые одинаково легко импортировать.

Это также означает, что, учитывая, что вы работаете с C, вам не придется перекомпилировать код каждый раз, когда изменяется таблица решений.

2 голосов
/ 02 марта 2009

если ваша таблица истинности булева, вы можете просто свернуть ее в список пар, например, 

1111,0000
1110,0110
...

для сжатия данных, представьте значения в байтах (два nybbles) ...

где / как хранить его для программного кодирования в вашей конкретной конфигурации встроенной системы, только вы можете сказать; -)

1 голос
/ 02 марта 2009

Обычно, когда у вас возникает такая проблема, вы пытаетесь свести ее к простой булевой формуле. Я не понимаю, почему это не лучший подход здесь. Это было бы намного более компактно и более читабельно, плюс у него есть потенциал, чтобы быть быстрее (я предполагаю, что несколько AND и OR будут выполняться быстрее, чем набор умножений / сдвигов + доступ к памяти, необходимый для подхода с использованием таблицы поиска). Самый простой способ уменьшить эту таблицу до логической формулы - это K-Map .

1 голос
/ 02 марта 2009

Я не вижу никакой ссылки на текущее состояние, чтобы получить ваше выходное состояние. Это означает, что это не конечный автомат, а только таблица истинности. Есть четыре входа, поэтому есть только 16 возможных комбинаций входов. Итак, таблица с 16 позициями должна это сделать.

1 голос
/ 02 марта 2009

Если таблица истинности действительно только 4x4x4x4, то я бы использовал макросы. Если это когда-нибудь пройдет, я бы использовал Ragel . Скорее всего, он сделает меньший, более быстрый C-код, чем вы.

...