Представление схемы алгоритма эквивалентным автоматом

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

Автомат, реализующий граф-схему алгоритма, впервые был предложен М.В. Уилксом [33] (принцип микропрограммного управления).

Рассмотрим получение по граф-схеме алгоритма других схем и получение соответствующего автомата.

Пусть задана некоторая ГСА (рис. 94).

Рис. 94. ГСА работы некоторого технологического агрегата

Допустим, ГСА построена по словесной формулировке работы некоторого агрегата.

Оптимизируем ГСА. Можно исключить блок 9 за счет подключения выхода блока 8 ко входу блока 7.

Получим соответствующую логическую схему алгоритма:

, где w – безусловный переход.

Построим матричную схему алгоритма (табл. 70) с учетом того, что в вершине 4 (рис. 94) выполняется «пустой» оператор А_Æ:

Таблица 70

Матричная схема алгоритма

	А1	А2	А3	А4	А5	АÆ	А6	Аk
А0
А1		х1
А2
А3
А4					х2х3
А5
АÆ					х2х3
Аk

Проверим корректность МСА: дизъюнкция логических условий исходящих дуг º1, конъюнкция условий, помечающих две любые исходящие из вершины дуги º0.

В нашем случае МСА корректна, например, для строки А₄:

Для получения эквивалентного автомата необходимо выделить состояния этого автомата по ГСА. Это выполняется путем так называемой отметки ГСА и получения отмеченной ГСА (ОГСА) [17].

Порядок получения отмеченной ГСА для автомата Мили:

· начальным символом отмечается выход начальной вершины и вход конечной;

· отмечаются входы вершин непосредственно следующих за операторными;

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

· при наличии «ждущих» вершин метка ставится ниже дуги от «ждущей» вершины.

Таким образом, при переходе от метки к метке выполняется не более одного оператора.

Для автомата Мура начальной меткой отмечаются начальная и конечная вершина, а метками обозначаются операторные вершины.

Далее строится граф соответствующего автомата.

Вершинам графа соответствуют метки ОГСА (состояния автомата). Дугам графа переходов соответствуют всевозможные условия перехода от одной метки к другой соответствующей метке ОГСА. Построим граф автомата (рис. 95).

Рис. 95. Граф переходов автомата по ГСА рис. 94

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

При этом строится обобщенная таблица возбуждения элементов памяти и выходов автомата (ОТВЭПВ).

ОТВЭПВ состоит из двух частей, первая из которых содержит информацию о коде состояния элементов памяти и обобщенном коде логических условий, помечающих дуги графа переходов. Во второй части содержится информация о состоянии входов элементов памяти, необходимых для осуществления данного перехода и о состоянии выходов z, называемых микрооперациями автомата. В частном случае – указывается последующее состояние автомата (табл. 71).

Таблица 71

Обобщенная таблица возбуждения элементов памяти и выходов автомата

y2 (t)

y1 (t)

х1

х2

х3

y2 (t+1)

y1 (t+1)

z1

z2

z3

z4

z5

z6

z7

z8

z9

z10

Y0

~

~

~

Y1

~

~

~

~

Y2

~

~

~

~

Y3

~

~

~

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

Из ОТВЭПВ выписывают информацию из первой ее части – коды дуг, соответствующие единичным наборам рассматриваемой функции, а также коды дуг, соответствующие нулевым наборам функции. Получают соответственно рабочие и запрещенные обобщенные коды.

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

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

Схема может быть построена на основе постоянного запоминающего устройства (ПЗУ).

В этом случае нет необходимости в минимизации переключательных функций, так как они представляются в СДНФ. Поэтому после получения ОГСА, сразу строится таблица программирования ПЗУ: сначала обобщенная (с «тильдами»), затем полная. Построим таблицу программирования ПЗУ (табл. 71) для ГСА, изображенной на рис. 96.

Рис. 96. Некоторая ГСА

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

Таблица 72

Таблица программирования ПЗУ

Адрес

Данные

y2

y1

x3

x2

x1

z1

z2

z3

z4

z5

D2

D1

Y0

~

~

Y0®Y0

~

Y0®Y0

~

Y0®Y1

Y1

~

~

~

Y1®Y2

Y2

~

~

Y2®Y2

~

~

Y2®Y0

Для получения полной таблицы программирования, в которой будет 2⁵=32 строки, необходимо составить развернутую таблицу (табл. 73) и затем доопределить адреса ПЗУ. Для компактности целесообразно записывать адреса и данные в восьмеричной системе счисления.

Таблица 73

Развернутая таблица программирования ПЗУ

в восьмеричной системе счисления

Адрес:	Данные
01,03,05,07	010 (1-я строка табл. 72)
00,04	010 (2-я строка)
02,06	101 (3-я строка)
10,11,12,13,14,15,16,17	063 (4-я строка)
30,31,32,33	003 (5-я строка)
34,35,36,37	004 (6-я строка)

Функциональная электрическая схема автомата на ПЗУ, реализующего заданную (рис.96) ГСА, изображена на рис. 97.

Рис. 97. Автомат на основе ПЗУ

На рис. 97 код состояния автомата фиксируется регистром RG, который тактируется генератором тактовых импульсов (изменение состояния автомата происходит по тактовым импульсам).

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

Рассмотрим получение автомата на ПЗУ и мультиплексоре для той же ГСА (рис. 96), но с другой разметкой (рис. 98).

Рис. 98. ОГСА для автомата на ПЗУ и мультиплексоре

Видно, что переход от метки к метке осуществляется с проверкой не более одного логического условия. Далее обычным образом строится граф автомата (рис. 99).

Рис. 99. Граф переходов автомата на ПЗУ и мультиплексоре

Теперь кодируем вершины графа. Число элементов памяти не изменилось (y₂y₁). Построим таблицу программирования ПЗУ. В отличие от табл. 72 сразу строится полная таблица программирования. Мультиплексор адресуется элементами памяти, поэтому на его выходе присутствуют некоторые переменные или заранее оговоренная константа. Сигнал на выходе мультиплексора назовем псевдопеременной (х), причем договоримся сопоставлять с безусловным переходом константу нуля (на соответствующий вход мультиплексора подаем константу нуля).

Количество строк таблицы программирования ПЗУ равно количеству дуг графа переходов, количество адресных разрядов для одновыходного мультиплексора равно s+1, где s – число элементов памяти. Количество разрядов микроопераций не изменяется, получаем табл. 74.

Таблица 74

Полная таблица программирования ПЗУ

для автомата с мультиплексором

Получим таблицу в 16-ричном коде (табл. 75).

Таблица 75

Полная таблица программирования ПЗУ

для автомата с мультиплексором в 16-ричном коде:

Адрес:	Данные
016	0116
116	0816
216	0816
316	4316
616	3216
516	0416
416	0216

Получим таблицу подключения информационных входов мультиплексора. Ее можно составить по графу автомата. В состоянии y₀(00) проверяется логическое условие х₁, в состоянии y₁(01) проверяется логическое условие х₂, в состоянии y₂(11) не проверяются логические условия – к соответствующему входу мультиплексора подключим генератор «0», в состоянии y₃(10) проверяется логическое условие х₃.

Таблица распределения входов мультиплексора имеет вид табл. 76.

Таблица 76

Таблица распределения входов мультиплексора

Номер информационного входа	Переменная (константа)
010	х1
110	х2
210	«0»	~
310	х3

Получим функциональную электрическую схему автомата на ПЗУ и мультиплексоре (рис. 100), реализующего заданную ГСА (рис. 98).

Мультиплексор – коммутатор каналов, реализующий следующую ПФ:

, где x₄ – псевдопеременная (~).

Рис. 100. Функциональная электрическая схема автомата

на ПЗУ и мультиплексоре

Объем памяти у такого автомата сокращается – необходимо 7*7=49 бит (против 168 бит для автомата на основе ПЗУ, см. рис. 97). Здесь мультиплексор в зависимости от состояния автомата, которое адресует не только ПЗУ, но и подключаемый к мультиплексору канал, передает на вход ПЗУ одну из переменных, или константу, в случае безусловного перехода.

Дата добавления: 2015-07-11