Логические схемы алгоритмов

Способы описания (задания) микропрограммных устройств

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

Условия функционирования автомата считаются заданными, если известны следующие множества и функциональные соответствия:

= множество входных сигналов;

= множество выходных сигналов;

= множество состояний памяти;

= начальное состояние памяти автомата;

= функция переходов автомата;

= функция выходов автомата.

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

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

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

Микропрограммный автомат является дискретным автоматом с памятью специального вида. Наибольшее распространение для описания МПУ получили логические схемы алгоритмов (ЛСА), граф-схемы алгоритмов (ГСА) и матричные схемы алгоритмов (МСА). Указанные модели МПА имеют наиболее простое и наглядное представление, а также легко преобразуются из одной формы в другую.

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

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

Рассмотрим кратко способы задания МПУ с помощью ЛСА, ГСА, и МСА.

МПУ реализует некоторый алгоритм. Что такое алгоритм?

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

Алгоритмы могут быть выражены в виде логических схем алгоритмов, граф-схем алгоритмов и матричных схем алгоритмов. Все три выражения алгоритмов эквивалентны между собой.

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

Алгоритм обладает следующими основными свойствами:

= определенностью, т.е. он облечен в формальное общепонятное предписание, не оставляющее место произволу;

= результативностью, т.е. он направлен на достижение некоторого результата и всегда приводит к какому-либо результату: положительному или отрицательному;

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

= дискретностью.

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

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

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

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

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

Операторы обычно обозначаются большими буквами латинского алфавита A, B, C,... Проверяемые логические условия обозначаются малыми буквами a, b, g. Часто для обозначения операторов выбирают одну большую букву А с разными индексами (А ₁, А ₂, А ₃,..., А_n), а для обозначения логических условий - малую букву p тоже с разными индексами (p ₁, p ₂,..., p_m).

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

Логические условия могут принимать 2 значения - 0 и 1. Единица обозначает, что логическое условие выполнено, а нуль - не выполнено.

Например, логическое условие ЛУ р (х=у): p =1, если х=у; p =0, если х <> у.

ЛУ р (х > у): p =1, если х > у; p =0, если х < =у.

Логические условия могут быть и сложными (а=а (p ₁ ,p ₂,..., p_n)), включающими в себя несколько простых. Например, ЛУ а=p ₁Ú p ₂. Очевидно, что а =1, если p ₁=1 или p ₂=1, или p ₁ =p ₂=1; а =0, если p ₁ =p ₂=0.

Для описания строения алгоритмов служит специальный математический аппарат - логические схемы алгоритмов.

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

Операторы и логические условия называются членами данной ЛСА, стрелки членами ЛСА не являются.

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

A®B®C®D.

Если алгоритм не является строго последовательным, то в ЛСА включаются логические условия, определяющие порядок выполнения операторов. От каждого логического условия начинается нумерованная стрелка (­ⁱ), которая оканчивается у какого-либо члена ЛСА (¯_i).

Знак ­ⁱ означает начало стрелки, знак ¯_i - ее конец. Это как бы одна стрелка `é``¯ у которой опущена средняя часть, чтобы не затемнять ЛСА. Начало и конец одной и той же стрелки обозначаются одинаковыми номерами: ­¹ и ¯₁ или ­² и ¯₂ и т.д.

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

Рассмотрим порядок работы ЛСА.

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

Если проверяемое логическое условие выполнено, (равно 1), должен работать член, соседний справа. Если же логическое условие не выполнено (равно 0), должен работать тот член, к которому ведет стрелка, начинающаяся после данного логического условия, т.е. член схемы, стоящий справа от конца стрелки. Аналогичным образом работают и другие члены ЛСА. Работа ЛСА прекращается тогда, когда последний из сработавших операторов содержит указание о прекращении работы либо тогда, когда на некотором этапе не оказывается такого члена схемы, который должен был бы работать.

Рассмотрим примеры.

Пример 4.1 Пусть задана ЛСА ¯₂ Ар ­¹ В ¯₁ q ­² C. Порядок работы ее при всех возможных комбинациях значений логических условий указан в таблице 4.1 Отметим, что часто вместо ЛСА говорят просто алгоритм.

Таблица 4.1

p	q	Порядок работы
		AAA...A...
		AC
		ABABAB...AB...
		ABC

Пример 4.2 Дана ЛСА ¯₂ Ар ­¹ В ¯₁ Cq ­² D. Порядок работы определяется таблицей 4.2.

Таблица 4.2

p	q	Порядок работы
		AСAС...AС...
		AСD
		ABCABC...ABC...
		ABCD

Пример 4.3 Дана ЛСА ¯₂ Aa ₁­¹ Bа ₂­²¯₁ C; , Порядок работы определяется таблицей 4.3.

Таблица 4.3

p1	p2			Порядок работы
				ABС
				AC
				ABAB...AB...
				ABAB...AB...

Среди логических условий выделяются такие, которые всегда принимают нулевое значение. Такие члены ЛСА называют тождественно-ложными логическими условиями. Эти условия не требуют проверки и обозначаются ω.

Например, ЛСА A ₀¯₁ A ₁ x ₁­²¯₃ A ₂ ω ­¹¯₂ A ₃ x ₂­ ³A ₄ A_k содержит одно тождественно-ложное логическое условие ω. Оно означает, что после выполнения оператора А ₂ действие всегда переносится по стрелке 1 к оператору А ₁.

Тождественно-ложные логические условия являются вспомогательными, а операторы и логические условия - основными членами ЛСА. Вспомогательный член ЛСА ω нужен для того, чтобы при записи ЛСА избежать многократного повторения ее основных членов.

В ЛСА выделение начального и конечного оператора не обязательно, ибо в их отсутствие начальным считают крайний левый, а конечным - крайний правый операторы.

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

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

При описании с помощью ЛСА функционирования МПУ всем элементарным актам - командам (микрокомандам) и проверяемым условиям ставятся в соответствие некоторые операторы и логические условия ЛСА. Составленная таким образом ЛСА отражает закон функционирования микропрограммного автомата.

Граф-схема алгоритмов (ГСА)

Как известно, при задании ДУ ориентированными графами, состояния памяти изображаются вершинами графа, а переходы автомата из одного состояния в другое - стрелками (дугами) графа, соединяющими соответствующие вершины.

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

Чтобы можно было установить начало и конец этой последовательности, выделяется специальная начальная вершина, которая соответствует первой команде (микрокоманде) МПУ, и конечная вершина, соответствующая конечной микрокоманде МПУ.

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

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

Начальная и конечная вершины обозначаются по ГОСТ 19.701-90 овалами с обозначениями А ₀ и А_к (Рисунок 4.5 а).

Операторные вершины будем обозначать прямоугольниками с буквами А ₁, A ₂,..., А_n, или А,В,С,..., или А ₁, А ₂,..., В ₁, В ₂,... (Рисунок 4.5 б). Вершины другого типа, соответствующе микрокомандам, по которым проверяются логические условия, называют условными вершинами. Условные вершины будем изображать ромбами с буквой x_i или p_i, или f (x) (Рисунок 4.5 в).

Операторная вершина может иметь один или несколько входов (входных дуг) и один выход (выходную дугу). Это соответствует в МПУ тому, что после выполнения микрокоманды (операции) за ней выполняется всегда только одна микрокоманда (операция).

а

Аi

б

в г

Рисунок 4.5

Условная вершина может иметь один или несколько входов и точно два выхода, отмеченные символами "да" и "нет". Это соответствует тому, что после проверки МПУ некоторого логического условия (x_i) возможны два исхода: x_i =1 или x_i =0.

Граф-схема алгоритма (ГСА) удовлетворяет следующим условиям:

= содержит конечное число вершин, каждая из которых является либо начальной, либо конечной, либо операторной, либо условной;

= имеет одну начальную и одну конечную вершины;

= входы и выходы вершин соединяются друг с другом с помощью дуг, направленных всегда от выхода ко входу;

= каждый выход соединен только с одним входом;

= любой вход соединяется хотя бы с одним выходом;

= для любой вершины графа существует хотя бы один путь из этой вершины к конечной вершине;

= один из выходов условной вершины может соединяться с ее входом (рисунок 4.5 г), что недопустимо для операторной вершины (так называемая ждущая вершина);

= в каждой вершине ГСА записывается оператор, присвоенный вершине.

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

Формализация условий работы МПА в виде ГСА начинается с содержательной граф-схемы алгоритма.