Способы описания работы дискретных устройств

3.1 Общие сведения об управляющем автомате

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

(рис 3.1)

Операционная часть в этом случае представляет собой набор функциональных узлов типа счётчик, регистр, сумматор, дешифратор и т.п., с соответствующими связями. На базе этих функциональных узлов выполняются все элементарные операции из множества, определяемого видом зависимости $$R=F(j)$$ (рис.3.1)

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

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

(рис 3.2)

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

Основным элементом программного управления на рассматриваемом уровне является микрокоманда.

$$Y=\{y_1, y_2, \dots, y_N\}$$ -множество микрокоманд $$\{МК\}$$ микропрограммных автоматов как составной части устройств управления.

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

(рис 3.3)

Микрооперация - наименование микрокоманды.

Микрокоманде, представленной на рис.3.3, соответствует микрооперация: "Передать число из Рг I в Рг2".

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

$$Yt=\{y_{t1}, y_{t2}, \dots, y_{tU} \}$$ -микрокоманда, состоящая из микроопераций (МО)

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

(рис 3.4)

Например, на рис.3.4) показана МП операции сложения. Если ввести формальное переобозначение микрокоманд ( $$A_i$$ или $$Y_i$$ ), то для МП на рис.3.4,б получим ГСА ГСА МП показанную на рис.3.5.

(рис 3.5)

Последовательность выполнения МК определяется функциями перехода

$$\alpha ij (i,j =1,2,…T)$$ от множества логических переменных $$X ={x_1,x_2,…,x_L}$$. Функции перехода обладают 2 свойствами: полноты и ортогональности.

- ортогональности $$\alpha ij * \alpha it =0$$

T

- полноты $$\vee \alpha ij =1$$

$$j=1 \dots$$

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

Способы формальной записи МП, удовлетворяющие перечисленным выше свойствам, это:

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

формулы перехода ;

матричные схемы алгоритмов ( МСА );

логические схемы алгоритмов (ЛСА).

3.2 Граф-схемы алгоритмов

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

Основными символами, используемыми при записи граф-схем алгоритмов (ГСА), будем считать:

операторы,

логические условия,

стрелки (рис.3.6).

(рис 3.6)

Из всего множества операторов выделяются:

начальный оператор $$А_0$$,

конечный оператор $$А_к$$,

произвольный оператор $$А_i (i=1,2,\dots,n)$$.

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

Особенность записи оператора $$А_0$$ в ГСА состоит в том, что в этот оператор не входит ни одной стрелки.

Конечный оператор будем рассматривать как оператор, символизирующий конец работы алгоритма.

Особенность записи оператора и $$А_к$$ в ГСА состоит в том, что из этого оператора не выходит ни одной стрелки.

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

Особенность записи операторов $$А_i$$ состоит в том, что в эти операторы могут входить несколько стрелок, но выходит всегда только одна стрелка.

Под логическим условием будем понимать логическую функцию вида $$\alpha_i(р_1,р_2,\dots р_к)$$, где $$р_1,р_2,\dots р_к$$ элементарные логические условия. Особенность записи логических условий состоит в том, что они могут иметь несколько входящих стрелок и только две выходящие, помеченные символами "О" и "I" в со-ответствии со значением логического условия. В дальнейшем будем допускать также ГСА замену левой части выражения вида $$\alpha_i= \alpha_i(р_1,\dots р_к)$$ его правой частью.

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

Выполнение алгоритма всегда начинается с оператора $$А_0$$ и заканчивается оператором $$А_к$$.

3.3Формулы переходов

В общем виде для каждой операторной вершины формула перехода записывается так:

$$Y_t \to \alpha_{ i1} Y_1 \vee \alpha_{ i2} Y_2 \vee \dots \vee \alpha_{ it} Y_t,$$

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

Для МП, представленной на рис.3.7, формулы перехода будут записаны так:

$$A_0 \to A_1$$ ;

$$A_1 \to p_{1A3} \vee p_1A_2$$ ;

$$A_2 \to A_k$$ ;

$$A_3 \to p_{2A1} \vee p_2A_k$$ ;

(рис 3.7)

3.4. Матричные схемы алгоритмов

Говорят, что задана матричная схема алгоритма (МСА), если задана матрица вида

$$\begin{array}{cccccc} A_1 A_2\ldots A_j\ldots A_n A_k\\ A_0 \alpha_{01} \alpha_{02} \ldots \alpha_{0j} \ldots \alpha_{0n} \alpha_{0k}\\ A_1 \alpha_{11} \alpha_{12} \ldots \alpha_{1j} \ldots \alpha_{1n} \alpha_{1k}\\ \vdots; \\ A_i \alpha_(i1} \alpha_{i2} \ldots \alpha_{ij} \ldots \alpha_in \alpha_{ik}\\ \vdots; \\ A_n \alpha_{n1} \alpha_{n2} \ldots \alpha_{nj} \ldots \alpha_{nn} \alpha_{nk} \end{array}$$

где $$А_i (i=1,n)\end{array}$$ -операторы,

$$A_0,A_k$$ - начальный и конечный операторы,

$$\alpha_ij$$ - логические условия, имеющие тот же смысл, что и в ГСА.

	А1	А2	А3	Аk
A0	1
A1		p1	p1
A2				1
A3	p2			p2

В MCA $$\alpha_{ij}$$ принято рассматривать как такую логическую функцию, что если выполнялся оператор $$A_i$$ и на образовавшемся наборе $$\Delta$$ значений элементарных логических условий функция $$?_ij$$ получила значение, равное единице, то непосредственно после оператора $$A_i$$ должен выполняться оператор $$A_j$$.

В рис.3.1,а приводится МСА МП, показанной на рис.3.7.

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

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

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

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

Логической схемой алгоритма называется строчка, составленная из символов операторов $$А_0,А_1,\dots,А_n,A_k$$, или $$Y_0, Y_1,\dots,Y_k$$ и логических условий $$\alpha_{ji}$$, а также верхних и нижних стрелок. Иногда верхние и нижние стрелки заменяют на правые и левые полускобки.

Итак, ЛСА- строчка, составленная из символов операторов $$Y_0, Y_1,\dots,Y_k$$, логических условий $$xi$$ и верхних $$\uparrow$$ и нижних $$\downarrow$$ стрелок, причем:

Сильная операторная вершина $$Y_0(Y_н)$$ и одна конечная $$Y_k$$ ;

Строка начинается с $$Y_0$$ и заканчивается $$Y_k$$ ;

Не должно быть двух нижних стрелок $$\downarrow$$ с одинаковыми номерами;

Для каждой нижней стрелки $$\downarrow$$ должна быть по крайней мере одна верхняя;

Переход по логическому условию $$X_i$$, стоящему в ЛСА

$$\dots Y_p X_i \uparrow Y_m \dots \downarrow Y_n$$

осуществляется так:

Если $$x_i=1$$, то после $$Y_p$$ выполнится $$Y_m$$,

Если $$x_i=0$$, то после $$Y_p$$ выполнится $$Y_n$$.

Безусловный переход для ясности может быть обозначен дополнительным символом, например $$\omega \uparrow$$.

ЛСА для МП, представленной на рис. 3.7 выглядит так:

$$A_0 \downarrow^3A_1p_1\uparrow^1A_3 p_2\uparrow^2 \omega \uparrow^3 \downarrow ^1A_2 \downarrow ^2A_k.$$

Правило чтения ЛСА состоит в следующем.

Вначале анализируется элемент ЛСА, следующий непосредственно за оператором $$А_0$$. Если рассматриваемым элементом является оператор, то он отмечается (выписывается) и на следующем шаге анализируется стоящий справа элемент (оператор или логическое условие).

Если рассматриваемым элементом является логическое условие $$\alpha_{ji},$$ производится проверка этого условия;

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

Пусть задана ЛСА.

$$Y_0 \downarrow^2Y_1 x_1 \uparrow^1Y_2 \downarrow^4Y_3 x_3 \uparrow^2Y_4 \omega \uparrow^3\downarrow^1\rightharpoondown x_2 \uparrow^4 Y_5 \downarrow^3Y_k$$

Построим соответствующую ей ГСА. За начальным оператором $$Y_0$$ следует оператор $$Y_1$$ и далее логическое условие $$x_1$$. Если логическое условие выполняется, то есть $$x_1=1$$, то следующим оператором выполняется $$Y_2$$. Если логическое условие не выполняется, то есть $$x_1=0$$, то следующим оператором выполняется $$х_2$$, то есть оператор, стоящий за нижней стрелкой с номером 1.

Далее в ЛСА за оператором $$Y_2$$ стоит оператор $$Y_3$$ и $$x_3$$. В такой последовательности и изображаем их на ГСА. Далее строим аналогичным образом.

Одной важной особенностью ЛСА является возможность неоднозначной записи одного и того же алгоритма.

(рис 3.8)

Так, ГСА на рис.3.8 может быть описана еще несколькими вариантами ЛСА:

$$Y_0 \downarrow^4Y_1 \rightharpoondown x_1 \uparrow^1 x_2 \uparrow^2Y_5 \omega \uparrow^3 \downarrow^1Y_2 \downarrow^2Y_3 x_3\uparrow^ 4Y_4 \downarrow ^3Y_k;$$ $$Y_0 \downarrow^5Y_1 x_1\uparrow^1 x_2\downarrow^2 \downarrow^4 Y_3 x_3\uparrow^5Y_4 \omega \uparrow^3 \downarrow^1Y_2 \omega \uparrow^4 \downarrow^2 Y_5 \downarrow^3Y_k;$$