Автоматы Мили и Мура: Математические модели цифровых схем
В теории автоматов базовый конечный автомат (FSM) лишь распознает языки: он читает строку и в конце выдает вердикт "Допущено" или "Отвергнуто". Но для проектирования реальных микропроцессоров, контроллеров памяти и сетевых протоколов требуются автоматы-преобразователи, которые не просто меняют внутренние состояния, но и генерируют полезные выходные сигналы в процессе работы. Двумя фундаментальными математическими моделями таких устройств являются автоматы Мили и автоматы Мура.
Обе модели представляют собой детерминированные конечные автоматы с выходами, но их архитектурный подход к генерации ответа кардинально отличается, что напрямую влияет на скорость и схемотехнику проектируемого оборудования.
Автомат Мура (Moore machine), предложенный Эдвардом Муром в 1956 году, устроен так, что его выходной сигнал зависит исключительно от текущего состояния автомата. Входные сигналы влияют только на то, в какое состояние автомат перейдет на следующем такте генератора частоты.
Плюсы: Выход автомата Мура строго синхронизирован с тактовым сигналом и абсолютно не подвержен кратковременным помехам или дребезгу на входных линиях во время такта. Схемы на автоматах Мура стабильнее и проще в отладке.
Минусы: Система реагирует на изменение входа с опозданием ровно на один такт (пока не произойдет переход в новое состояние). Кроме того, для описания сложной логики автомату Мура обычно требуется больше состояний (а значит, больше физических триггеров в микросхеме), чем автомату Мили.
Автомат Мили (Mealy machine), созданный Джорджем Мили в 1955 году, устроен иначе: его выходной сигнал формируется комбинацией текущего состояния И текущих значений на входах.
Плюсы: Автомат Мили реагирует на входные воздействия мгновенно (в пределах задержки логических вентилей), не дожидаясь следующего тактового импульса. Как правило, графы переходов для автоматов Мили получаются более компактными и требуют меньшего числа внутренних состояний.
Минусы: Если на входе появится кратковременная помеха (глитч), она может мгновенно проскочить на выход автомата, что потребует дополнительных цепей фильтрации в асинхронных дизайнах.
Математически доказано, что автоматы Мили и Мура эквивалентны: любой автомат Мура можно преобразовать в автомат Мили, и наоборот (хотя при переводе в Мура число состояний может возрасти). На практике, при проектировании аппаратуры на языках описания логики VHDL или Verilog, инженеры часто используют гибридные автоматы, чтобы объединить преимущества обеих моделей для достижения максимальной тактовой частоты процессора.
