Кр. Задание_на_кр. Структурный синтез дискретных автоматов
![]()
|
Рисунок 2. Варианты представления карты Карно для функции ![]() а) для случая записи ![]() ![]() На рис. 2, а показана карта Карно для минимизации функции, представленной в СДНФ. В этом случае МДНФ может быть представлена в виде логической суммы минтермов, количество которых соответствует числу замкнутых областей. На рис. 2,б показана карта Карно для минимизации функции, представленной в СКНФ. В этом случае МКНФ может быть представлена в виде логического произведения макстермов, количество которых соответствует числу замкнутых областей. Для записи полученных в результате минимизации ФАЛ в базисах И-НЕ или ИЛИ-НЕ используют закон де Моргана (закон дуальности), согласно которому инверсия дизъюнкций ![]() ![]() В соответствии с законом де Моргана мы можем представить данную функцию в различных базисах. Для представления функции в базисе И-НЕ необходимо произвести двойную инверсию над всей функцией и, используя теорему де Моргана преобразовать инверсию дизъюнкций в конъюнкцию инверсий. Для представления функции в базисе ИЛИ-НЕ необходимо произвести двойную инверсию над каждой конъюнкцией, а также двойную инверсию над всей функцией и, используя закон де Моргана преобразовать инверсию конъюнкций в дизъюнкцию инверсий Двойное инвертирование ФАЛ не изменяет функцию, но позволяет исключить одну логическую операцию ИЛИ путем замены ее на две операции ИЛИ-НЕ. Для технической реализации ФАЛ используется количество логических элементов типа И-НЕ или ИЛИ-НЕ, равное числу инверсий в ее алгебраическом выражении. Так как любой из этих логических элементов должен иметь по определению число входов не менее двух, то при наличии инверсии только одной переменной, эта переменная подается на оба входа логического элемента И-НЕ или ИЛИ-НЕ в зависимости от выбранного базиса. ЗАДАЧА 2 Провести синтез автомата Мили, функционирование которого описывается заданными таблицами переходов и выходов. Изобразить граф синтезируемого автомата. Задавая произвольную двоичную последовательность (входное слово), определить соответствующую двоичную выходную последовательность (выходное слово) автомата. Построить структурную схему синтезированного автомата в базисе И, ИЛИ, НЕ. Варианты таблиц переходов определяются следующим образом: по последней цифре шифра из табл. 3 определяется последовательность восьми состояний (из четырех заданных А0, А1, А2, А3). Эта последовательность построчно слева направо и сверху вниз заносится в таблицу переходов, состоящую из двух строк, верхняя из которых определяет последующие состояния автомата под воздействием входного сигнала ![]() ![]() Таблица 3 Варианты таблиц переходов
Представить число из трех последних цифр шифра в двоичной системе счисления, добавив при необходимости слева нули до восьми разрядов или убрав (также слева) лишние, оставив восемь младших разрядов. Эта двоичная последовательность построчно слева направо и сверху вниз заносится в таблицу выходов, первая строка которой будет определять выходные сигналы автомата при воздействии входного сигнала ![]() ![]() Заполняем соответствующие таблицы, как это показано на рис. 5.
Рисунок 5. Пример заполнения таблиц переходов и выходов МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ ЗАДАЧИ 2 Синтез последовательностных устройств Известно, что для синтеза комбинационных схем требуется набор логических элементов, реализующих некоторую полную систему логических функций (базис). Особенность последовательностных схем состоит в том, что они обладают памятью, для реализации которой требуются дополнительные элементы. В качестве таких элементов используются триггеры. Опишем структуру синтезируемого автомата Мили, относящегося к одной из разновидностей последовательностных схем. Автомат состоит из набора ![]() ![]() ![]() ![]() ![]() ![]() Для формирования сигналов ![]() ![]() ![]() ![]() Функции переходов и выходов автомата могут быть заданы в форме таблиц переходов и выходов или с помощью графов. В столбцах таблиц (рис. 5) указаны состояния автомата, а в строках - входные сигналы. На пересечении столбца и строки в таблице переходов указано новое состояние, в которое переходит автомат, а в таблице выходов - выходной сигнал. Граф же состоит из узлов, отождествляемых с отдельными состояниями автомата. Связи между узлами показывают переходы автомата из одного состояния в другое под воздействием входных сигналов. На каждой связи сверху указывается входной сигнал, вызывающий данный переход, и сигнал, формируемый на выходе автомата до перехода его в новое состояние. Таким образом, для синтеза автомата необходимо выполнить следующее: определить какая комбинация состояний триггеров будет соответствовать каждому из внутренних состояний автомата, т.е. провести кодирование внутренних состояний автомата; синтезировать комбинационное устройство формирования сигналов управления триггерами ![]() синтезировать комбинационное устройство, формирующее выходные сигналы автомата ![]() Затем каждой комбинации состояний триггеров нужно поставить в соответствие определенное состояние автомата. Кодирование состояний автомата может производиться различными способами. кодирования состояний автомата приведен в табл. 4. Таблица 4 Кодирование состояний автомата
Далее заполняем табл. 5 функционирования автомата Таблица 5 Таблица функционирования автомата Мили
Рассмотрим подробнее заполнение таблицы функционирования автомата Мили. В первых трех ее столбцах записываются все возможные сочетания кодов входного сигнала и состояния автомата. Для заданного входного сигнала и состояния автомата по графу находится значение выходного сигнала, которое записывается в последнем столбце таблицы, и следующее состояние автомата, в которое он переходит. Код этого состояния заносится в четвертый и пятый столбцы таблицы. Столбцы с 6 по 9 отведены для записи сигналов управления триггерами. Управление триггерами осуществляется подачей сигналов на входы очистки (вход ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() В тех случаях, когда предыдущее ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() В подобных случаях, когда логический уровень сигнала управления безразличен («0» или «1»), соответствующие клетки табл.5 остаются пустыми или в них заносится символ *. Для построения комбинационного устройства, формирующего сигналы управления триггерами ( ![]() Для построения комбинационного устройства, формирующего выходной сигнал ![]() ![]() |