ГСА, ЛСА и МСА

Получение математической модели микропрограммных устройств в виде

Для целей синтеза МПУ необходимо уметь строить модели микропрограммных устройств в виде ГСА, ЛСА, МСА. Методику их построения рассмотрим на примере.

Пример 5.1 Для МПУ, изображенного на рисунке 5.3, найти его описание в виде ГСА, ЛСА и МСА.

z 3

z 4

z 2

z 1

x 1 x 2 x 3 x 4

Пуск

Рисунок 5.3

Автомат имеет входы "Пуск", x ₁, x ₂, x ₃и x ₄, выходы z ₁, z ₂, z ₃, z ₄ и состоит из регистра Р, дешифратора D, блока формирования команд управления ФКУ, блока проверки логических условий ПЛУ и формирователя микрокоманд ФМК, соединенного со входами регистра.

Работа автомата состоит в следующем.

По команде "Пуск" в регистр Р записывается команда начала работы, по которой ФКУ формирует команду z ₁. После этого МПУ проверяет наличие сигнала на входе x ₁ (логическое условие x ₁). Если x ₁=1, то автомат формирует управляющую команду z ₂, затем z ₃, а если x ₁=0, то сразу формирует команду z ₃. После этого МПУ проверяет, выполнено ли логическое условие x ₂ (наличие сигнала на входе x ₂). Если x ₂=0, то автомат заканчивает работу, а если x ₂=1, то МПУ формирует управляющую команду z ₄ и проверяет выполнение логического условия x ₃. При x ₃=0 цикл работы автомат повторяет, начиная с формирования команды z ₁. Если логическое условие x ₃ выполняется (x ₃=1), то проверяется состояние входа автомата x ₄ (логическое условие x ₄). Если на входе x ₄ имеется сигнал (x ₄=1), то МПУ возвращается к формированию команды управления z ₄, если на этом входе отсутствует сигнал (x ₄=0), то работа автомата заканчивается.

Отметим, что, как правило, словесное описание работы МПУ получают по условиям, задаваемым заказчиком на разработку устройства (автомата).

Порядок построения ГСА состоит в следующем.

1) Составляется полный перечень команд (микрокоманд управления и логических условий). Для примера 5.1 это будут команды "Пуск", z ₁, z ₂, z ₃, z ₄, "Конец", x ₁, x ₂, x ₃, x ₄.

Заметим, что в реальных примерах эти команды имеют реальный смысл.

2) Вводится содержательное обозначение микрокоманд и ЛУ. Для примера 5.1 это будут: "Пуск", ФКУ= z ₁, ФКУ= z ₂, ФКУ= z ₃, ФКУ= z ₄, "Конец", Sign x ₁, Sign x ₂, Sign x ₃, Sign x ₄.

3) Определяется и вычерчивается начальная вершина "Пуск".

4) В соответствии со словесной формулировкой строится содержательная ГСА до конечной вершины.

При этом необходимо с особым вниманием относиться к случаям, когда якобы следует осуществить возврат к уже имеющимся вершинам, что может привести к противоречию в ГСА, а также к случаям, когда после некоторого значения ЛУ нет дальнейшего действия, а необходимо ждать противоположного значения ЛУ, т.е. возникает ждущая вершина.

По словесному описанию условий работы МПУ построим содержательную граф-схему алгоритма. Для примера 5.1 построение начинаем с вычерчивания начальной вершины "Пуск" (Рисунок 5.4). Так как после пуска автомат формирует команду управления z ₁, то ниже необходимо вычертить операторную вершину ФКУ= z ₁, которая соответствует формированию команды z ₁. Выход вершины "Пуск" следует соединить со входом вершины ФКУ= z ₁. По условию работы МПУ после формирования команды z ₁ проверяется логическое условие x ₁ поэтому ниже вершины ФКУ= z ₁ следует вычертить вершину Sign x ₁. Вход этой вершины соединяется с выходом вершины ФКУ= z ₁. Вершина Sign x ₁ имеет два выхода: "да" и "нет". Из условий работы МПУ следует, что если x ₁=1, то автомат формирует управляющую команду z ₂, а затем z ₃. Поэтому ниже вершины Sign x ₁ необходимо нарисовать последовательно соединенные вершины ФКУ= z ₂ и ФКУ= z ₃. Вход вершины ФКУ= z ₂ соединяется с выходом "да" вершины Sign x ₁. Если логическое условие x ₁ не выполнено, то сразу формируется команда z₃, поэтому выход "нет" вершины Sign x ₁ следует соединить со вторым входом вершины ФКУ= z ₃. Аналогично анализируя заданную схему автомата (его словесное описание), начертим содержательную граф-схему алгоритма (Рисунок 5.4) до конечной вершины.

5. После построения содержательной ГСА ее вершины кодируются, т.е. выбирается система операторов. Выберем для примера 1 следующую кодировку вершин:

А ₀ - "Пуск";

А ₁ - ФКУ= z ₁;

А ₂ - ФКУ= z ₂;

А ₃ - ФКУ= z ₃;

А ₄ - ФКУ= z ₄;

А_к - "Конец";

x ₁ - Sign x ₁;

x ₂ - Sign x ₂;

x ₃ - Sign x ₃;

x ₄ - Sign x ₄.

Получаем при таком кодировании вершин граф-схему алгоритма (Рисунок 5.5), наглядно представляющую условия функционирования заданного МПУ.

Ak

A 4

A 3

A 2

x 2

x 3

x 4

x 4

x 3

z 4

x 2

z 3

z 2

A 0

A 1

z 1

x 1

x 1

Рисунок 5.4

Рисунок 5.5

Порядок получения модели МПУ в виде логической схемы алгоритма следующий:

1) На основании анализа словесного описания условий функционирования МПУ определяется список формируемых МПУ команд (микрокоманд управления) и проверяемых логических условий.

2) Производится кодирование микрокоманд и ЛУ: вводятся условные обозначения формируемых микрокоманд (А ₀, А ₁, А ₂,... А_к) и проверяемых ЛУ (x ₁, x ₂,..., x_n), т.е. выбирается система операторов.

3) Выписывается начальный оператор, обозначающий начало алгоритма.

4) По словесной формулировке последовательно строится ЛСА - член за членом до А_к включительно. Эта процедура производится вначале при равенстве всех логических условий единице (ЛУ=1), а затем при равенстве ЛУ нулю (ЛУ=0), либо проставляются в необходимых местах концы стрелок, либо вводятся новые члены ЛСА. При этом каждое ЛУ снабжается началом стрелки.

Найдем описание в виде ЛСА микропрограммного устройства, описанного в примере 5.1. Перечень команд и логических условий был выписан при составлении ГСА.

Введем систему операторов, т.е. закодируем команды и условия, формируемые и проверяемые автоматом, следующим образом:

Команду "Пуск" - А ₀;

Команду z ₁- А ₁;

Команду z ₂ - А ₂;

Команду z ₃ - А ₃;

Команду z ₄ - А ₄;

Команду "Конец" - А_к;

Проверку выполнения логического условия x ₁ - x ₁;

Проверку выполнения логического условия x ₂ - x ₂;

Проверку выполнения логического условия x ₃ - x ₃;

Проверку выполнения логического условия x ₄ - x ₄;

Так как работа автомата начинается по команде "Пуск", обозначенной оператором А ₀, то и выражение ЛСА начинается с этого оператора (оператора начала), т.е. А ₀.

По команде "Пуск" автомат формирует команду управления z ₁, обозначенную символом А ₁, поэтому в ЛСА после оператора А ₀ необходимо записать оператор А ₁. Получим: А ₀ А ₁.

После формирования команды z ₁ МПА проверяет выполнено ли логическое условие х₁. Поэтому после оператора А ₁ следует записать логическое условие х ₁ с началом стрелки ­¹:

Из анализа работы автомата следует, что если х ₁=1, то автомат формирует команду управления z ₂, а затем z ₃, обозначенные соответственно А ₂ и А ₃. Следовательно, в ЛСА после символа ­¹ записываем последовательно операторы А ₂ и А ₃: А ₀ А ₁ x ₁­¹ А ₂ А ₃.

Если же х ₁=0, то МПА сразу формирует команду управления z ₃. Отсюда следует, что конец стрелки ¯₁ необходимо расположить перед оператором А ₃: А ₀ А ₁ x ₁ ­¹ А ₂¯₁ А ₃.

После формирования команды z ₃ автомат проверяет, выполнено ли логическое условие х ₂. Поэтому после оператора А ₃ нужно записать логическое условие х ₂ с началом стрелки ­²: А ₀ А ₁ x ₁­¹ А ₂¯₁ А ₃ х ₂­².

Если х ₂=1, то автомат формирует команду управления z ₄, обозначенную символом А ₄, а после формирования команды z ₄ автомат проверяет, выполнено ли логическое условие х ₃.

Таким образом, после символа ­² записываем А ₄, затем х ₃ с началом стрелки ­³:

А ₀ А ₁ x ₁­¹ А ₂¯₁ А ₃ х ₂­²¯₄ А ₄ х ₃­³.

Из анализа работы автомата следует, что если х ₃=1, то автомат проверяет состояние входа x ₄. Значит, после начала стрелки ­³ записывается символ х ₄­⁴. Если же х ₃=0, то цикл автомата повторяется, начиная с формирования команды z ₁, обозначенной через А ₁. Поэтому конец стрелки ¯₃ необходимо поставить перед оператором А ₁:

А ₀¯₃ А ₁ x ₁­¹ А ₂¯₁ А ₃ х ₂­² А ₄ х ₃­³ х ₄­⁴.

Из условий работы автомата следует, что если на входе х₄ имеется сигнал х ₄= 1, то МПА возвращается к формированию команды управления z ₄, обозначенной А ₄. Оператор А ₄ в уже построенной части ЛСА присутствует. Чтобы перейти к нему нужно в ЛСА вместо х₄ поставить символ, тогда конец стрелки ¯₄ необходимо записать перед оператором А ₄. Если же х ₂=0, или на входе х ₄ отсутствует сигнал (), то по условию автомат заканчивает работу. Так как конец работы мы обозначили оператором А_к, его следует записать после начала стрелки­⁴, а перед ним поставить конец стрелки ¯₂. Итак, окончательно получаем:

А ₀¯₃ А ₁ x ₁­¹ А ₂¯₁ А ₃ х ₂­²¯₄ А ₄ х ₃­³­⁴¯₂ А _к.

Полученное выражение и является искомой ЛСА, описывающей условия работы МПУ, изображенного на рисунке 5.1.

Входы автомата в ЛСА отождествляются с логическими условиями (переменными), выходы - с операторами, кроме операторов “Начало” (“Пуск”) и “Конец”. Начальное состояние автомата отождествляется с оператором “Начало” (“Пуск”).

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

Над моделями автоматов в виде ЛСА можно проводить эквивалентные преобразования.

Порядок получения модели МПУ в виде матричной схемы алгоритма (МСА) следующий.

1) Определяется полные список микрокоманд - операторов и логических условий.

2) Производится кодирование микрокоманд и ЛУ условными обозначениями, т.е. выбирается система операторов.

3) Строится квадратная матрица, строки которой обозначаются операторами А ₀, А ₁,..., А_i,..., А_{к -1}, а столбцы - операторами А ₁,..., А_i,...,А_к.

4) На основании словесной формулировки определяются совокупности значений ЛУ, при которых после А ₀ выполняется А ₁ и определяется функция переходов от А ₀ к А ₁ - а ₀₁, которая и проставляется в матрицу. Аналогичная процедура выполняется для всех строк и столбцов матрицы.

5) Проводится проверка правильности построения матрицы по соотношениям

Найдем для МПУ, приведенного в примере 1, его описание в виде МСА.

Закодируем команды “Пуск”, z ₁, z ₂, z ₃, z ₄ и “Конец” соответственно операторами А ₀, А ₁, A ₂, A ₃, A ₄, A_k. Проверки выполнения логических условий х ₁, х ₂, х ₃, х₄ закодируем соответственно х ₁, х ₂, х ₃, х_{4 .}

После кодирования устанавливаем размерность квадратной матрицы, равную 5, так как всего операторов 6, но оператором А ₀ не обозначается столбец, а оператором А_к не обозначается строка. Строки квадратной матрицы обозначим сверху вниз А ₀, А ₁, A ₂, A ₃, A ₄, а столбцы слева направо А ₁, А ₂, A ₃, A ₄, A _к. Затем необходимо определить функции переходов а_ij для каждой клетки матрицы. Из анализа схемы и условий ее работы следует, что по команде “Пуск”, обозначенной нами через А ₀, автомат формирует команду z ₁, обозначенную через А ₁.

Это означает, что в клетке < А ₀ А ₁> необходимо записать 1, а в остальных клетках - нули (так как а ₀₂= а ₀₃= а ₀₄= а _{0 к} =0). После заполнения строки А ₀ матрица примет вид, представленный на рисунке 5.6.

		Рисунок 5.6		Рисунок 5.7

Для сокращения записи нулевые значения а_ij в матрицу записывать не будем. Переходим к заполнению второй строки А ₁. Из условий работы МПУ вытекает, что после формирования команды z ₁ автомат проверяет, выполнено ли логическое условие х ₁. Если х ₁=1, то автомат формирует управляющую команду z ₂, отсюда следует, что функция переходов а ₁₂= х ₁, Если же логическое условие х ₁ не выполнено, т.е. х ₁=0, то автомат формирует команду z ₃. Значит, а ₁₃ = x 1. Другие переходы автомата в данном случае по условиям его работы невозможны, или а ₁₁= а ₁₄= а _{1 к} =0. После заполнения строки А ₁ матрица имеет вид, представленный на рисунке 5.7.

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

Остановимся более подробно на заполнении строки А ₄. Из условий работы автомата следует, что после формирования команды z ₄, обозначенной оператором А ₄, проверяется логическое условие х ₃. Если х ₃ = 0, то цикл работы автомата повторяется, начиная с формирования команды z ₁, обозначенной А ₁. Отсюда видно, что функция перехода от оператора А ₄ к оператору А ₁ равна , т.е. . Это необходимо записать в первую клетку строки А ₄ матрицы.

Если х ₃ = 1, то проверяется выполнение логического условия х ₄. Если х ₄ = 1, автомат снова формирует команду управления z ₄. Отсюда следует, что функция перехода от оператора А _{4 к} оператору А ₄ равна х ₃ х ₄, т.е. а ₄₄= х ₃ х ₄.

Если же на входе х ₄ сигнал отсутствует, то автомат заканчивает работу: . Другие переходы автомата после функционирования команды z ₄ невозможны. Следовательно, а ₄₂= а ₄₃=0.

Запишем значения полученных функций переходов в матрицу и получим ее окончательный вид, представленный на рисунке 5.9.

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

Между МСА, ГСА и ЛСА имеется однозначное соответствие. Входам автомата на ГСА соответствуют условные вершины, в ЛСА - логические условия или переменные логических условий, в МСА - переменные функций переходов а_ij. Выходным состоянием автомата в ГСА соответствуют операторные вершины, в ЛСА и МСА - операторы. Состояние автомата определяется количеством вершин в ГСА, операторов и логических условий - в ЛСА и МСА. Начальное состояние определяется на ГСА вершиной “Начало”, в ЛСА - самым левым оператором выражения, в МСА - самым верхним оператором строки. Функции переходов и выходов на ГСА определяются дугами графа и его вершинами, в МСА - функциями переходов а_ij, в ЛСА - порядком расположения операторов, логических условий и нумерованных стрелок.