Содержательные и закодированные ГСА

Граф-схемой алгоритма (ГСА) называют ориентированный связанный граф, содержащий одну начальную вершину (А₀), одну конечную (А_k) и произвольное конечное множество операторных (A = {a₁,..., a_k-1}) и условных (P = {p₁,..., p_f}) вершин. Данные вершины изображены на рисунке 5.4 под буквами а, б, в и гсоответственно.

Рисунок 5.4 – Типы вершин ГСА

Конечная, операторная и условная вершины имеют по одному входу, начальная вершина входов не имеет, как и показано на рисунке. Начальная и операторная вершины имеют только по одному выходу, а условная - два выхода, помеченных символами 1 и 0. Конечная вершина выходов не имеет.

При построении ГСА должна удовлетворять следующим условиям:

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

2. Каждый выход соединен точно с одним входом;

3. Любой вход соединяется, по крайней мере, с одним выходом;

4. Любая вершина графа лежит, по крайней мере, на одном пути из начальной вершины к конечной вершине;

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

6. В каждой условной вершине записывается один из элементов множества X = {x₁,..., x_L}, называемого множеством логических условий. Запись одинаковых элементов множества X в различных условных вершин разрешается;

7. В каждой операторной вершине записывается оператор (микрокоманда) Y_t - подмножество множества Y = {y₁,..., x_N}, называемого множеством микроопераций. Y = {y_t1,..., y_tu,..., y_tU}; y_tU Î Y, u = 1,..., U_t. При U_t = 0 Y_t = Æ, Разрешается также запись в различных операторных вершинах одинаковых подмножеств множества операций.

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

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

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

Для записи функциональных микропрограмм используется язык функционального микропрограммирования (Ф - язык).

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

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

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

1. Описание слов и массивов, устанавливающее типы и форматы слов, с которыми оперирует микропрограмма.

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

Основным элементом информации, с которым оперирует Ф – микропрограмма, является слово. Наименование и формат слова задаются в следующем виде C(П₁:П₂), где С – идентификатор; П₁ и П₂ – номера старшего и младшего двоичных разрядов слова. Разряды слова номеруются направо неотрицательными целыми числами n₁>0, n₂>0, n₁<n₂. Одноразрядное слово состоит только из идентификатора С.

Совокупность слов, имеющих одинаковую длину, может объединятся в массив. Массив описывается в следующем виде: M[m₁:m₂](n₁:n₂), где M – идентификатор массива; m₁,m₂ – границы номеров слов, составляющих массивов, причем m₁<m₂; n₁,n₂ – номера старшего и младшего разрядов слова.

В зависимости от способа использования значений выделяют следующие типы слов:

1. Входные слова – значения присваиваются вне микропрограммы и используются внутри микропрограммы.

2. Внутренние – значения присваиваются и используются только внутри микропрограммы.

3. Вспомогательные – значения присваиваются и используются только внутри микропрограммы, но существуют не постоянно, а только в течении такта автоматного времени (типа А).

4. Выходные – значения присваиваются в микропрограмме и используются вне ее (типа О).

Двоичное выражение определяет правило вычисления двоичного значения путем выполнения операций над первичными двоичными значениями. Константы записываются в следующем виде 1100₂, 14₈, 12₁₀, С₁₆.

Первичные двоичные значения, слова и поля – объединяются в двоичное выражение с помощью двоичных операций, к которым относятся обычно следующие операции: ù - инверсия, × конкатенация, Ù - конъюнкция, Ú-дизъюнкция, + - сложение, - - вычитание, Å - сложение по модулю 2.

Примерами двоичных выражений являются следующие конструкции:

А; В(0); ù А; С+1; С+А(1:15); С+11₂ù А(1:15)+1.

Последнее выражение вычисляется в следующем порядке – вначале инвертируются разряды 1-15 слова А ù А(1:15); затем формируется составляющее значение 11₀ù А(1:15); выполняется сложение с С составным значением С+11₂ù А(1:15); и последняя сумма складывается с 1.

В синтаксическом смысле микрооперация – это оператор присваивания, посредством которого слову присваивается значение двоичного выражения. Микрооперация состоит из левой части, знака присваивания (:=) и двоичного выражения в правой части.

Все микрооперации подразделяются на семь классов:

1. установки;

2. инвертирования;

3. предачи;

4. сдвига;

5. счета;

6. сложения;

7. бинарные логические;

8. комбинированные.

Микрооперация передачи – обеспечивает присваивание слову значение другого слова (А:=В). Микрооперация сдвига служит для изменения положения разрядов слова по отношению к начальному пути перемещения каждого разряда на k позиций влево или вправо. Операции сдвига обозначаются следующим образом:

Rh(A) – удаление из двоичного выражения А k младших правых разрядов, то есть сдвиг на k разрядов вправо.

Lk(A) – удаление из двоичного выражения A k старших левых разрядов, то есть сдвиг на k разрядов влево.

Бинарные логические микрооперации присваивают слову значение, получаемое поразрядным применением микроопераций Ù, Ú, Å к парам соответствующих разрядов слагаемых. Например, С:=АÚВ.

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

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

- шины, обеспечивающие передачу слов информации;

- регистры, обеспечивающие хранение слов;

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

Рассмотрим в качестве примера содержательную ГСА, описывающую устройство сложения двоичных чисел с использованием обратного кода. Sm=A+B (рис. 2.5).

После построения содержательной ГСА логические условия и микрооперации кодируются символами x₁,..., x_L и y₁,..., y_N соответственно.