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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

 

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

 

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

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

 

 

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