Синтез дискретных автоматов без памяти. Синтез дискретных автоматов с памятью (Глава 2 учебного пособия "Основы электронной вычислительной техники и программирования"), страница 4

Синтез состоит из следующих этапов:

-  разбиения сложного автомата на подавтоматы, если это необходимо;

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

-  минимизации числа внутренних состояний по первоначальным графу или таблице переходов-выходов;

-  определения необходимого объема памяти и координирования внутренних состояний;

-  построения кодированных таблиц переходов-выходов;

-  построения карт Карно функций выходов и определения их МДНФ.

На этом заканчивается абстрактный синтез. Следующие этапы составляют структурный синтез:

-  выбор элементной базы, если она не задана, и определение типа элементов памяти;

-  построение таблиц функций возбуждения элементов памяти;

-  задание этих функций картами Карно и определение их МДНФ;

-  переход от МДНФ функций возбуждения и выходов к виду, удобному для реализации в избранной системе элементов;

-  разработка логических, функциональных или принципиальных электрических схем автомата.

Особенности синтеза обуславливаются характером входов автомата.

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

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

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

В-третьих, в качестве элементов памяти автомата с импульсными входами можно использовать элементарные автоматы любого из рассмотренных ранее триггеров. Для автоматов с потенциальными входами будем применять элементы памяти типа задержек или RS-триггеров. При наличии в составе элементной базы JK-триггеров с потенциальными входами синтез автомата целесообразно выполнять следующим образом: вначале синтезировать прототип с импульсными входами на JK-триггерах и получить функции возбуждения  каждого элемента памяти и функции выходов автомата. Затем при построении схемы использовать JK-триггеры с потенциальными входами, реализовав функции возбуждения и выходов по полученным ранее формулам.

Минимизация числа внутренних состояний выполняется для упорядочения переходов автомата и может привести к уменьшению объема памяти и упрощению структуры. Для этого применяется метод Хаффмана, который заключается в поиске групп эквивалентных, псевдоэквивалентных и совместимых внутренних состояний и объединении состояний группы в одно внутреннее состояние, Таким образом производится сжатие графа или таблицы переходов-выходов. Эквивалентные внутренние состояния таковы:

-  они устойчивы при действии одних и тех же состояний входов;

-  им соответствуют одинаковые комбинации выходных сигналов;

-  при одних и тех же последовательностях состояний входов формируются одинаковые последовательности состояний выходов, независимо от того, какое из эквивалентных принято за исходное внутреннее состояние.

Псевдоэквивалентные внутренние состояния таковы:

-  они устойчивы при действии одних и тех же состояний входов;

-  им соответствуют непротиворечивые состояния выходов;