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

StackOverflow https://stackoverflow.com/questions/603035

  •  03-07-2019
  •  | 
  •  

Вопрос

У меня есть (несколько) большая таблица истинности / конечный автомат, который мне нужно реализовать в моем коде (встроенный 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, которые выражают значение каждого состояния, наряду с /**/ комментариями, объясняющими входные данные для каждой строки выходных данных.Всем спасибо за помощь!

Это было полезно?

Решение

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

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

Другие советы

Я бы предложил либо то, либо другое (сначала предпочтительные подходы).:

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

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

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

если ваша таблица истинности состоит исключительно из логических значений, вы могли бы просто свернуть ее в список пар, например

1111,0000
1110,0110
...

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top