Оптимизация цифрового автомата (FSM)

[@kovigor]

Для ознакомления с основами ЦА и вообще цифровой схемотехники я бы все-таки рекомендовал книжку Лобанова «Азбука разработчика цифровых устройств»…

[@teology]

Что получаем на выходе программы? В каком виде оптимальный ответ?

[@Efi-fi]

Описание графа файл вида:
Efifi 4 1 #Имя_графа размерность_памяти размерность_входного_сигнала
A1 A3 0 #Имя_узла1 имя_узла2 входной сигнал для перехода из узла1 в узел2
A1 A2 1
A10 A2 1
…
A9 A1 1
A9 A10 0

Выходной файл:
{'digauto':
['A5|(0, 0, 0, 0)', 'A8|(0, 0, 0, 1)', 'A6|(0, 0, 1, 0)', 'A9|(1, 0, 0, 1)', 'A3|(0, 1, 0, 1)', 'A4|(1, 0, 0, 0)', 'A1|(0, 1, 1, 1)', 'A2|(0, 1, 0, 0)', 'A7|(0, 1, 1, 0)', 'A10|(0, 0, 1, 1)'],
'exprs':
{'D0': {'form': 'D', 'expression': (v1 & ~v5) | (v2 & v5 & ~v4) | (v3 & ~v2 & ~v4), 'num_gates': 7},
'D1': {'form': 'C', 'expression': v4 & (v3 | ~v2 | ~v5), 'num_gates': 3},
'D2': {'form': 'D', 'expression': v4 & ~v3, 'num_gates': 1},
'D3': {'form': 'C', 'expression': (v3 | ~v2) & (~v3 | ~v4 | ~v5), 'num_gates': 4}},
'gates': 15}

Описание выходного файла:
'digauto': [имя_узла|(код)]
'exprs': {имя_триггера: {D-дизъюктивная или C-коньюктивная, уравнения входов тригеров, количество использемых элементов}}
'gates': общее число используемых элементов, по этому числу оценивается автомат.

[@teology]

Ок, вроде понятно: узлы и триггеры — это вроде как состояния и переходы.
Что на счёт КА, допускающего распараллеливание выполнения (несколько состояний одновременно)?

[@Efi-fi]

Неожиданный вопрос, никогда не думал об этом.

[@Brak0del]

Что на счёт КА, допускающего распараллеливание выполнения

Звучит не очень, по крайней мере в контексте упоминавшихся ПЛИС. Что вы подразумеваете под распараллеливанием в данном случае? Каждое состояние присваивает значение выходных сигналов явно или неявно, одному сигналу за один и тот же такт нельзя присвоить 2 разных состояния. Поэтому если вы можете выполнить несколько состояний одновременно, то они должны совпадать по выходным значениям, следовательно, они неразличимы.

[@teology]

Представьте себе два КА, работающие параллельно. Если они полностью независимые, то могут быть реализованы на двух ПЛИС. А если зависимые, то вот как раз об этом речь. КА параллельные бывают в природе и там решаются проблемы типа синхронизации и конфликта состояний… А про ПЛИС не знаю, но параллельные КА можно всегда заменить на один КА, только он будет как правило невменяемо сложный.

[@Brak0del]

А если зависимые, то вот как раз об этом речь

Если это вопрос компоновки, так в литературе есть ещё и иерархические КА, когда в ходе одного состояния родительского КА выполняются несколько состояний дочернего.

Но всё же не находите ли, что речь в итоге сводится к нескольким КА (т.е. когда у каждого КА будет выполняться снова-таки одно состояние в каждый момент времени)? Сама зависимость двух КА — это же как раз входной сигнал для одного КА и выходной для другого. Ну придется проге скормить вместо одного КА два или три. Имхо, параллельный КА противоречит определению КА.

[@teology]

Если это вопрос компоновки, так в литературе есть ещё и иерархические КА, когда в ходе одного состояния родительского КА выполняются несколько состояний дочернего.

А родительское КА, которое порождает два и более дочерних?

Уверяю в реальных задачах такие КА часто могут иметь место, и они удобнее, чем логика моно-КА (назовем его так). Может нужны примеры?
А пример такой: пусть у нас есть две лампочки и три кнопки. Мы должны включать кнопкой1 лампочку 1 и включать кнопкой2 лампочку 2, а отключать обе лампочки кнопкой 3. Все просто.
Можно придумать моно-КА и параллельные КА. Что проще?

[@Brak0del]

Можно придумать моно-КА и параллельные КА. Что проще?

У вас скачок в логике, изначально у вас был один параллельный КА, и к нему у меня претензии. Сейчас у вас уже 2 КА. Не имею ничего против нескольких КА — это вопрос удобства и компоновки, сам такими пользуюсь, но давайте называть вещи своими именами.
Справедливости ради, существуют ещё fuzzy fsm из области нечёткой логики и нечётких множеств, там есть какая-то тема с несколькими состояниями одновременно. Может вы о них?

[@teology]

Решите задачку двумя способами, может поймёте, о чем я.

[@Brak0del]

В литературе есть термин fsm-partitioning, оптимизация, когда из одного большого КА средство синтеза (тулза) делает несколько маленьких связанных КА, которые суммарно весят меньше по ресурсам и кушают меньше энергии. Вы о таком говорите?

[@teology]

Может быть!
Такие КА не только экономят ресурсы у процессора, но и в них часто легче разбираться и понимать человеку.