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

Раздел 2. Синтез последовательностных логических устройств

Последовательностные логические схемы. Типы триггеров. Способы изображения различных типов входов логических схем. Синтез триггеров с использованием таблицы состояний триггера и карт Карно.

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

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

Общий вид автомата с памятью. Использование ПЗУ и ПЛМ для реализации автомата с памятью. Сокращение емкости ПЗУ. Использование мультиплексора для уменьшения емкости ПЗУ.

Импульсные цепи в дискретных системах. Реализация формирователей временных интервалов.

Последовательностные логические схемы. Типы триггеров. Способы изображения различных типов входов логических схем. Синтез триггеров с использованием таблицы состояний триггера и карт Карно.

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

Таблица истинности, описывающая работу различных триггеров

Состояния входов и выхода до срабатывания триггера	Состояния выходов после срабатывания триггеров

Существует несколько типов триггеров: RSS, RSR, JK, D, T.

RSS, RSR – разновидности RS триггера; символы S,R в конце названия триггера определяют преобладающие входы при запрещённом состоянии.

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

RSS триггер:

RSR триггер:

Способы изображения различных типов входов логических схем:

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

На рисунке ниже изображены синхронный D триггер с асинхронными RS входами и временные диаграммы при изменении сигналов на D и C входах при сигналах на R и S входах равных единице.

Временные диаграммы показывают, что в триггере происходит повтор состояния на D входе в момент времени окончания импульса (по заднему фронту) на С входе.

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

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

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

Несомненное преимущество графов – это их наглядность. Переходя по дугам из одной из одного состояния в другое, можно разобраться в работе исследуемого устройства.

Например, RSS-триггер можно представить следующим графом:

Работа двухразрядного двоичного суммирующего счетчика, имеющего входы +1 – сложение и R- сброс, может быть иллюстрирована следующим графом

Использование теории графов для синтеза логического устройства поясним на следующем примере.

Пусть задание на разработку звучит так: «необходимо спроектировать устройство управления, выдающее сигнал на выходе – , если на двух его входах появились единичные сигналы, причем на входе сигнал появится раньше, чем на входе ».

Из задания ясно, сто следует фиксировать по следующим входным сигналам .Другими словами нужно помнить, что пришло первым.

Составляется таблица, в которой в левой части перечислены все входные наборы (комбинации), а в правой части – соответствующий им выходной сигнал. Если устройство управления имело входов, то таблица будет содержать строк.

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

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

Формально память в системе управления может быть введена за счет рассмотрения множества внутренних состояний, в которых может находится система. Это множество мы будем обозначать как Среди этих состояний выделим одно, которое будем называть начальным. Начальное состояние будет обозначаться .

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

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

Таблица переходов

Состояние	Входные комбинации

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

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

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

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

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

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

Для полноты описания работы устройства по графу, укажем на ребрах, под соответствующими входными комбинациями, в прямоугольнике состояние выхода.

Таблица переходов		Таблица выходов
Состояние						Состояние

Для последнего графа необходима таблица выходов, так как в может существовать, а может и нет.

По таблице выходов составим логическое выражение для y: а из таблицы переходов найдем необходимое в выражении для y значение z₁

Функциональная схема, построенная по полученным выражениям примет вид: