FSM Mealy, Moore, практическое применение Опции

[dxp]

Всем привет!

Несомненно все, кто не прогуливал занятия по цифровой электронике, изучали конечные автоматы (КА), и в том числе их базовые разновидности - автоматы Мили и Мура. Я тоже прилежно учился и когда постигал премудрости профессии на практике, пытался накладывать полученные теоретические знания на разрабатываемые решения. В большинстве случаев это прекрасно работает. Но вот в случае с упомянутыми в заголовке темы вещами оно как-то не получилось. Поясню.

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

Плюсы и минусы обоих вариантов очевидны:

• у Мили решение может обойтись меньшим количеством внутренних регистров за счёт использования логики с входами, и при этом ещё получается меньше задержка - выходы могут меняться в том же такте, что и изменение входов. Недостатки: возможны глитчи и бОльшая задержка распространения по выходам из-за использования комбинационной логики;
• у Мура больше регистров и всегда задержка на такт относительно Мили, но зато можно сделать без глитчей и задержку тоже можно сделать меньше, т.к. нет обязательной логики по выходам.

Когда мне приходилось (и приходится) проектировать КА, я честно пытался применить эту теорию к этому процессу, но почему-то именно тут она уходила в фон: при описании КА смотришь на целевую задачу и решаешь её, исходя из доступных средств. Собственно, описываешь автомат так, чтобы его работа удовлетворяла целевой задаче, и почему-то тут [мне] ни разу совсем не потребовалось погружаться в эту классификацию и анализ свойств - просто кодишь логику, конечно имея в виду, что комбинационная задержка может подзатянуть слаки и/или дополнительный регистр сдвигает результат на такт, это надо тоже учитывать...

А вопрос, собственно, такой: какое практическое преимущество даёт знание этой классификации нашему брату - ПЛИСоводу? Подозреваю, что для разработчиков компиляторов, синтезаторов эта классификация может быть полезна - например, в этой теории могут быть доказаны теоремы, что если, де, автомат Мили, то можно провести такую-то или такую-то оптимизацию, а если Мура, то вот такие-то или такие-то ограничения. Как сказал один мудрый человек: "Нет ничего практичнее хорошей теории". Но нам-то - простым пользователям компиляторов, синтезаторов, есть практическая польза? Например, вот описал я логику КА, вижу, что он Мили. Или Мура. И что? Что даёт это понимание? Ведь логику-то я описал, исходя из требований целевой задачи, а не ставя цель, сделать Мили или Мура.

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

[Shivers]

Несколько комментариев
1. Строго говоря, автоматы Мура и Мили, это алгоритмы, состоящие из шагов, т.е. по сути - программы. К электронике имели отношение весьма отдаленное. То, о чем вы пишете, это реализации алгоритмов Мура и Мили в виде автомата Хаффмана. Автомат Хаффмана - это логика, на выходе которой включена память, + необязательная обратная связь с выхода памяти на вход логики. Хаффман это придумал лет за 15 до появления алгоритмов Мура и Мили. Бывают еще не-Хаффмановские автоматы - проектируются с использованием графов, и не имеют четкого разделения элементов на память и логику.
2. Автомат Мили может быть сведен к автомату Мура, поэтому автоматы Мили упоминают лишь вскользь, для галочки.
3. Все синхронные схемы - уже автоматы Мура. Просто потому, что триггер - это элемент памяти, добавим перед ним логику - получаем Хаффмановскую модель автомата, т.е. фактически - реализацию алгоритма Мура/ автомат Мура.
4. Все же топикстартер спрашивает о более сложных автоматах, чем просто Мура/Мили. Как уже было верно написано, если воспользоваться теорией автоматов, то можно минимизировать число состояний у проектируемого FSM. На практике никто этого не делают - ваяют на верилоге как получится. Надо только понимать, что если минимизацию не делаете вы, то это придется делать тулу. А уж как он это сделает .. поэтому надо очень хорошо покрывать тестами автоматы в коде - их реализация вполне может оказаться некорректной. Синтез автоматов - одно из наиболее слабых мест современных тулов.
5. О применении теории графов. Если делать по науке, то можно вручную сократить число флопов в вашей FSM, не отдавая это на откуп синтезатору. Вот и все преимущество. Но на мой взгляд, гораздо полезнее просто научиться правильно описывать FSM на верилоге, тогда и тул будет корректно работать.

[x736C]

5. О применении теории графов. Если делать по науке, то можно вручную сократить число флопов в вашей FSM, не отдавая это на откуп синтезатору.

На мой скромный взгляд, сегодня мировая тенденция такова, что скорость разработки, читаемость кода преобладают над аппаратурной эффективностью. Со всеми вытекающими.
Можно замутить автомат по науке, но он будет не так прозрачен и понятен для программиста.

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

Позволю замечание. То, что в книгах не давались ответы на практические вопросы совсем не доказывает, что математический аппарат, который давали авторы, бестолковый и не применим на практике. Тут я не имею в виду именно те книги, которые вы прочитали. Сомнительным мне кажется сам подход игнорировать теоретическую науку, оставляя её 'академикам'.
Думаю, что практики (инженеры-программисты) с хорошей теоретической подготовкой (математика, физика, мат. статистика) дают фору простым кодерам по востребованности в высокооплачиваемых должностях. Но это неточно

По теме. Мне думается, что с триггерами происходит та же история. Когда-то люди придумывали разные бистабильные элементы, используя ламповые, а потом транзисторные структуры. Эти триггеры получали разные названия. D-, JK-, RS-, T-триггер и прочие. Сегодня, не смотря на то, что ключевой логический элемент физически может быть реализован в виде триггера какого-то конкретного типа, программист же может не задумываться, какой именно триггер по типу он использует, ориентируясь только на его конкретную функциональность. То есть, перефразируя ув. dxp, просто кодишь логику, не погружаясь в классификацию и анализ свойств.

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