Комментарии 13
Для ознакомления с основами ЦА и вообще цифровой схемотехники я бы все-таки рекомендовал книжку Лобанова «Азбука разработчика цифровых устройств»…
Что получаем на выходе программы? В каком виде оптимальный ответ?
Описание графа файл вида:
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': общее число используемых элементов, по этому числу оценивается автомат.
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': общее число используемых элементов, по этому числу оценивается автомат.
Ок, вроде понятно: узлы и триггеры — это вроде как состояния и переходы.
Что на счёт КА, допускающего распараллеливание выполнения (несколько состояний одновременно)?
Что на счёт КА, допускающего распараллеливание выполнения (несколько состояний одновременно)?
Неожиданный вопрос, никогда не думал об этом.
Что на счёт КА, допускающего распараллеливание выполнения
Звучит не очень, по крайней мере в контексте упоминавшихся ПЛИС. Что вы подразумеваете под распараллеливанием в данном случае? Каждое состояние присваивает значение выходных сигналов явно или неявно, одному сигналу за один и тот же такт нельзя присвоить 2 разных состояния. Поэтому если вы можете выполнить несколько состояний одновременно, то они должны совпадать по выходным значениям, следовательно, они неразличимы.
Представьте себе два КА, работающие параллельно. Если они полностью независимые, то могут быть реализованы на двух ПЛИС. А если зависимые, то вот как раз об этом речь. КА параллельные бывают в природе и там решаются проблемы типа синхронизации и конфликта состояний… А про ПЛИС не знаю, но параллельные КА можно всегда заменить на один КА, только он будет как правило невменяемо сложный.
А если зависимые, то вот как раз об этом речь
Если это вопрос компоновки, так в литературе есть ещё и иерархические КА, когда в ходе одного состояния родительского КА выполняются несколько состояний дочернего.
Но всё же не находите ли, что речь в итоге сводится к нескольким КА (т.е. когда у каждого КА будет выполняться снова-таки одно состояние в каждый момент времени)? Сама зависимость двух КА — это же как раз входной сигнал для одного КА и выходной для другого. Ну придется проге скормить вместо одного КА два или три. Имхо, параллельный КА противоречит определению КА.
Если это вопрос компоновки, так в литературе есть ещё и иерархические КА, когда в ходе одного состояния родительского КА выполняются несколько состояний дочернего.
А родительское КА, которое порождает два и более дочерних?
Уверяю в реальных задачах такие КА часто могут иметь место, и они удобнее, чем логика моно-КА (назовем его так). Может нужны примеры?
А пример такой: пусть у нас есть две лампочки и три кнопки. Мы должны включать кнопкой1 лампочку 1 и включать кнопкой2 лампочку 2, а отключать обе лампочки кнопкой 3. Все просто.
Можно придумать моно-КА и параллельные КА. Что проще?
Можно придумать моно-КА и параллельные КА. Что проще?
У вас скачок в логике, изначально у вас был один параллельный КА, и к нему у меня претензии. Сейчас у вас уже 2 КА. Не имею ничего против нескольких КА — это вопрос удобства и компоновки, сам такими пользуюсь, но давайте называть вещи своими именами.
Справедливости ради, существуют ещё fuzzy fsm из области нечёткой логики и нечётких множеств, там есть какая-то тема с несколькими состояниями одновременно. Может вы о них?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Оптимизация цифрового автомата (FSM)