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

Для реализации этих формул можно взять различные микросхемы. Например, на рис.2.8,а показано совмещенное изображение элемента ЗИ-2 ИЛИ-НЕ с расширением по ИЛИ и расширителя 4И, выполняющих совместно функцию 3-3-2И-3ИЛИ-НЕ, так как два выхода расширителя не используются (оборваны). Для формирования  применен элемент 2И-НЕ, второй вход которого оборван. На этом же рисунке показано разнесенное изображение схемы, реализующей функцию . В ней к элементу 3И-НЕ присоединены  два  входа  расширителя  4И, так  что  получается  функция

4-3-3И-ИЛИ-НЕ. Окончательно сигнал формируется элементом 2И-НЕ, используемым как инвертор.

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

Если функции  привести к виду

то их реализовать можно, применяя лишь микросхемы типа ЛБ, без расширителей пол ИЛИ (рисунок 2.8,б). Предлагаем читателю самостоятельно подобрать микросхемы, которые наиболее целесообразно использовать.

Рис.2.8.

г) Поскольку в микросхемы входят элементы ИЛИ-НЕ / ИЛИ, функции выходов нужно выразить следующим образом:

;

Эти формулы можно реализовать с помощью микросхем К1ЛБ721 (рис.2.8, в) в виде:

Так как каждая микросхема состоит из двух элементов 4ИЛИ-НЕ / 4ИЛИ, требуется четыре К1ЛБ721.

2.8   Способы задания дискретных автоматов с памятью

Дискретный автомат полностью задан, если известны:

-  множество состояний входов

где  – число входов;

-  множество состояний выходов

где  – число выходов;

-  множество внутренних состояний

если автомат имеет K элементов памяти, то , причем часть внутренних состояний может не использоваться;

-  функции переходов, определяющие внутреннее состояние автомата в момент времени  в зависимости от внутреннего состояния автомата в момент  (от предыдущего внутреннего состояния) и состояния входов в момент

-  функции выходов

   (автомат Мили);

   (автомат Мура);

-  исходное (начальное) внутреннее состояние .

Автоматы без памяти – частный случай, когда  и

Заданием на синтез служит словесное описание, определяющее существенные черты работы автомата. По словесному описанию могут быть перечислены состояния входов и выходов и составлены временные диаграммы изменения входных и выходных сигналов. По ним можно определить циклы работы и выявить внутренние состояния автомата.

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

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

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

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

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

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