ЗАДАЧИ ТЕОРИИ КОНЕЧНЫХ АВТОМАТОВ

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

1. Абстрактный синтез.

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

На втором этапе абстрактного синтеза проводится минимизация числа внутренних состояний (минимизация таблицы переходов).

2. Абстрактный анализ.

При решении задачи анализа по таблице переходов требуется получить словесное описание алгоритма функционирования КА.

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

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

– хотя бы один ЭА с двумя разными состояниями, для которого соблюдается условие полноты системы переходов и выходов (то есть существует хотя бы один входной сигнал, переводящий автомат из состояния в и в каждом состоянии автомат выдаёт выходной сигнал, отличный от сигналов, выдаваемых в других состояниях);

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

4. Структурный анализ.

При решении задачи структурного анализа по схеме автомата необходимо получить таблицу переходов и сравнить с исходной таблицей с целью проверки правильности синтеза.

Дата добавления: 2020-06-09; просмотров: 324;