Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.

§ 4.3. Алгоритмический этап проектирования

271

На абстрактном этапе решается задача минимизации объема

памяти автомата. На этапе кодирования (размещения) внутрен

них состояний автомата каждому внутреннему состоянию авто-

— Ч~ I—--Ь -

—А - Ч Pi k f- Л -

-» А —Г~рГ~1

-K ^ H Z Z lD - k S*)"

- * А - И Рг I— ► А»

Рз 1— »*(^>* I i - k S * 1

Рис. 4.7

мата сопоставляется код, т. е. определенная совокупность состоя

ний (значений) элементов памяти.

В результате выполнения двух рассмотренных этапов состав

ляют системы выходных функций и функций возбуждения авто

мата — строят автоматный оператор. После построения автомат

ного оператора переходят к структурному синтезу.

II. Этап структурного синтеза автомата. Этап

структурного синтеза автомата заключается в построении из за

данных элементов логической (функциональной) схемы автомата,

реализующей полученный автоматный оператор. Более подробно

структурный синтез рассмотрим ниже.

§ 4.3. Алгоритмический этап проектирования

Проектирование автоматного оператора заключается в построе

нии автоматного отображения по заданному словесному описанию,

включающему цель проектирования, назначение синтезируемого

автомата и свойства поведения (функционирования) управляемого

272

_______

Гл. 4. Теория формальных грамматик и автоматов

объекта, в контуре, с которым проектируемый автомат реализует

поставленную цель.

Автоматное отображение, как правило, задают в виде графа

переходов. Граф переходов — это граф G = {V, (X, У)), каждая

вершина которого взаимно однозначно соответствует внутреннему

состоянию автомата, и если из состояния 5,- автомат переходит

в состояние Sj, то соответствующие им вершины и,-, Vj соединя

ются дугой (и,-, vj) € U, взвешенной парой векторов (X , У), при

которых этот переход осуществляется.

На алгоритмическом этапе неформально заданная информация

преобразуется в формальную систему в виде автоматного опера

тора. При этом используется принцип аналогий. Формально этот

переход может быть основан на применении грамматик, в которых

правила подстановки формализуют данные свойства управляемого

объекта. В результате применения грамматик порождаются ком

позиции графов переходов, удовлетворяющие заданному словес

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

уровневую иерархию. Первый уровень представляет собой графы

переходов, реакцией которых является непосредственно управляю

щее воздействие на управляемый объект. Второй уровень предста

вляет собой граф переходов, реакция которого соответствует воз

буждению инициальных вершин графов первого уровня.

Рассмотрим построение графов переходов автоматов, реализую

щих устройства вычислительной техники и промышленной авто

матики.

Пусть задан операционный автомат в виде арифметического устройства по

следовательного действия, изображенного на рис. 4.8. Это устройство содержит

РА

СдР4„

Лсд РЗ Лсд РЪ

Рис. 4.8

§4.3. Алгоритмический этап проектирования

273

четыре регистра: Pi, Р2, РЗ, Р4, и одноразрядный сумматор комбинацион

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

ляемыми веитилями. Четырехразрядные числа представляются в устройстве в

двоичном коде 8421.

Синтезируем автомат, управляющий вычислением мантиссы частного. До

выполнения операции делимое а находится в регистре Р1, делитель Ъ — в реги

стре Р2, числа а и Ь нормализованы, а частное формируется в регистре РЗ. При

выполнении операции деления вычитание заменяем сложением в дополнитель

ном коде и используем следующий алгоритм.

1. Вычитаем в дополнительном коде содержимое регистра Р2(Ъ) из содер

жимого регистра Р1{а), одновременно переписывая содержимое регистра Pi в

регистр Р4■

2. Если о — Ь > 0, то выполняем п. 3, в противном случае — п. 4.

3. Разность а — b записываем в регистр Р1, регистр PJ устанавливаем в

“нуль”, а в регистр РЗ записываем 1, сдвигаем на один разряд вправо делитель,

регистр результата — влево и переходим к п. 5.

4. Записываем содержимое регистра Р4 в регистр Р1, в регистр РЗ записы

ваем 0, сдвигаем на один разряд делитель вправо, регистр результата — влево и

переходим к п. 5.

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

случае — к п. 6.

6. Конец (в общем случае здесь осуществляется передача управления в блок

нормализации частного).

Для простоты считаем, что в регистр РЗ предварительно записан код нуля.

Зная операционный автомат и реализуемый алгоритм, соста

вляем временную диаграмму функционирования управляющего

автомата, которая представляет собой алгоритм выполнения дан

ной операции в терминах управляющих точек — микроопераций.

Каждой микрооперации соответствует выходной канал управляю

щего автомата. Отсюда число выходных каналов синтезируемого

автомата равно числу всех микроопераций.

Множество микроопераций рассматриваемого устройства таково: СЭР1 —

сдвиг регистра Р1\ СЭР2 — сдвиг регистра Р2; ПСдПЗ— правый сдвиг реги

стра РЗ; ЛСдРЗ — левый сдвиг регистра Р3\ СЭР4 — сдвиг регистра Р4 (на

личие регистра Р4 позволяет ие производить восстановления остатка); ПК1 —

прямой код содержимого регистра Р1; ПК2 — прямой код содержимого реги

стра Р2\ OKI — обратный код содержимого регистра PI; ОК2 — обратный код

содержимого регистра Р2\ ВхР1 — вход регистра Р1; ВхР2 — вход регистра

Р2\ У"0"Р1 — установка регистра Р1 в “нуль”; ВхЛРЗ — вход регистра РЗ

слева; ВхПРЗ — вход регистра РЗ справа; ЦР1 — цикл регистра Р1; ЦР2 —

цикл регистра Р2; -f 1 ) . — подача единицы в цепь переноса сумматора; Д4 —

работа с векторами длины 4; Д5 — работа с векторами длины 5; Дб — работа

с векторами длины 6; Д7 — работа с векторами длины 7; Р4~*Р1 — передача

содержимого регистра Р4 в регистр Р1.

Строка временной диаграммы взаимно однозначно соответст

вует микрооперации.

Множество микроопераций, выполняемых одновременно, на

зывается микрокомандой, а множество последовательностей ми

крокоманд, соответствующее выполняемой операции — микропро

граммой. Каждая микропрограмма взаимно однозначно соответ

ствует значению входного вектора X. Следовательно, число раз

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

274

Гл. 4. Теория формальных грамматик и автоматов

операций, а число входных каналов равно [log2 |{X,}|], где [ ] —

знак ближайшего целого числа.

При синтезе управляющего автомата, реализующего заданный алгоритм,

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

пункт алгоритма. Временная диаграмма, соответствующая вычислению нуле

вого разряда частного иа операционном автомате (рис. 4.8) по приведенному алго

ритму деления, приведена на рис. 4.9. Временные диаграммы, соответствующие

ТТкТ

ШГ

Ок2

ШРГ

ЩРГ

штт

ж ш

\ л с ш

ТТкГ

WFI

y r a i

w m

w im

ПГ-

ра~0

Г0, если п. 1 выполняется

о=< менее пяти раз,

(. 1 в противном случае

Блок

нормализации

Рд- перенос в нулевой

(знаковый) разряд

при суммировании чисел

Рис. 4.9

вычислениям последующих разрядов частного, отличаются от диаграмм, изо

браженных иа рис. 4.9, только в первом блоке, а именно: при вычислении i-ro

разряда частного вместо четырехкратного выполнения микрооперации Д4 имеет

место соответственно (4 — |)-кратное выполнение микрооперации Д(4 — i), т. е.

прн вычислении первого разряда выполняется пятикратное возбуждение Д5 и

т. д. Следовательно, чтобы использовать первый временной блок, надо перед

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

Настройка первого временного блока заключается в следующем: Д} рассма

тривают как входной параметр этого блока и перед вычислением нулевого раз

ряда j присваивают значение 4, а после вычисления каждого разряда частного

значение j увеличивают иа 1. Осуществим настройку первого временного блока

введением дополнительного четырехразрядного регистра Р5, в который перед

началом выполнения операции деления записывается 1, а после вычисления ка

ждого разряда частного производится сдвиг, регистра PS иа один разряд. Выход

i-ro разряда регистра Р5 подается на клапан Д(|»| ± 3).

Для нахождения числа вычисленных разрядов частного введем трехразряд

ный счетчик ( СчЦ), состояние 101 которого укажет на то, что вычислено пять

разрядов частного и надо передавать управление в блок нормализации.

§4.3. Алгоритмический этап проектирован ил

__________

275

Основываясь иа проведенном анализе, целесообразно изменить множество

микроопераций, а именно: вместо микроопераций Д4, Д5, Дб, Д7 ввести ми

крооперации СЭР5 (сдвиг регистра Р5) и 1вР5 (запись единицы в регистр Р5) и

иЭ'РГ

Cd Р2

JlCdP3

СдР4

7Гк\

Ок2

Ш'РГ~

У"0"Р1

ШТШ

тщ—

ЦР2

П Т-

СдР$

1 1>1 1 1

1вР5

Р4-Р1

+1 СчЦ

СчЩХГ

Л.

/S /S

/ N /S / S /S /S

/S / N /S / S /S /S

л л /S

/ N

/S л

/S /S

/ \

/S / S /S /S

/S /S

л л

/ S

л / ч

2{Р5\=

3 IPS]-

[СчЦ] ф 101

[СчЦ] — содержимое Блок

счетчика циклов нормализации

i [Я5]—содержимое i-го разряда

регистра PS, »«1,4

■

р0

СдР\

СёР2

Лсд РЪ

СдР4

Ш '

Ок2

6 х Р \

У“0">1

ВхП РЪ г-*

1—•

L—*

ЦР1

.....

+■ 1х

Сд PS

UPS

Pt-Pt

+1 СчЦ

СнЩ ХГ

Рис. 4.10

дополнительно ввести микрооперацию +1 СчЦ (прибавление единицы в счетчик

циклов СчЦ) и СчЦв “О” (установление счетчика циклов в “нуль”).

В результате рассмотренных преобразований временная диаграмма, приве

денная на рис. 4.9, преобразуется во временную диаграмму, изображенную на

рис. 4.10.

276

Гл. 4. Теория формальных грамматик и автоматов

Временная диаграмма еще не дает автоматного отображения.

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

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

выходного вектора (микрокоманд), т. е. временная диаграмма за

дает неоднозначное преобразование входного вектора в выходной.

Следовательно, это преобразование не является автоматным ото

бражением. Для получения автоматного отображения необходимо

ввести в синтезируемый автомат память. При этом заведомо до

статочен объем памяти, равный числу всех микрокоманд. Сово

купность входного вектора и состояния памяти однозначно опре

деляет микрокоманду.

В соответствии с временной диаграммой построим граф перехо

дов автомата. Внутреннее состояние автомата взаимно однозначно

сопоставляется столбцу во временной диаграмме.

Граф переходов автомата, реализующий временную диаграмму (рис. 4.10),

изображение рис. 4.11. Микрокоманды на этом рисунке обозначены латинскими

буквами и имеют следующий вид:

а = {1вР5, СчЦв “О”};

Ь = {СдР1, СЭР2, ПК1, ОК2, ЦР1, ЦР2, + 1 £ , +1СиЦ)-

§4.3. Алгоритмический этап проектирования

277

с = {BxPl}- d = {СдР1, СдР2, ПК1, 0К2, ЦР2}\

е = { + 1 £ }; / = {ВхПРЗу, g = { СдР2, ЛСдРЗ, CdPfr,

h = {У“0"еР1}-, к = { СдР2, ЛСдРЗ, СдР4, P4~>Pl}; т = {СЭР5}.

Считаем, что если иа вход автомата управления поступила единица (х = 1),

то автомат выполняет управление делением.

Логические переменные (признаки), определяющие ход управления, обозна

чим как: аг; — содержимое »-го разряда регистра Р5\ /3 — условное состояние

счетчика СчЦ,

д _ f 1 , еслн состояние счетчика есть 101,

” — i 0 в противном случае;

Ро — перенос в нулевой разряд при суммировании чисел.

Рассмотрим большую систему промышленной автоматики — систему сжи

гания твердого топлива в плотном слое. Система содержит четыре полугазовые

толкн, установки подачи топлива, воздуха и установку удаления шлака. Схема

полугазовой топки изображена иа рис. 4.12, где: 1 — конвейер; 2 — плужок;

15'

Рис. 4.12

S — входной бункер; 4 — топливо; 5 — питатель; 6 — забрасыватель; 7 —

полугаз; 8 — подача воздуха; 9 — рабочая камера; 10 — шлак; 11 — слой све

278

Гл. 4. Теория формальных грамматик и автоматов

жезаброшенного топлива; 12— зона восстановления; 13— зона горения; 14 —

зона шлака; 15 — колосниковая решетка.

Полугазовые топки, являющиеся одним из видов промышленных печей, вхо

дят в состав газового хозяйства завода, и автоматизация управления процессами

сжигания в топках — одна из задач автоматизации всего технологического про

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

двуоксида углерода. С его повышением падает теплота сгорания полугаза и уве

личивается температура в' толке. Полугаз перед выходом из толки смешиввется

с вторичным воздухом и подается в рабочую камеру. Топка снабжается топли

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

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

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

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

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

деленной толщины слоя сгораемого топлива (200-400 мм для антрацита, 400-

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

топлива, первичного воздуха н удаления шлака из зоны горения.

Система управления сжиганием имеет следующие каналы (рис. 4.13), пред

ставляющие собой микрооперации при проектировании управляющего автомата:

XI8

пК

Х43 Х44

*45 Х46

К1

К2

КЗ

К4

Хб

Х51

К52

-| Х39 |

К7

jED 7 111*8!

К40

К9

XI о

ка

\ I

хп

Х31

Х32

АЗЗ

КЗ 4

K3S

Х36

КЗ!

К38

К19

К20

К2\ К22

Х47

Х48

*49 Х50

"" Г

К23

Х24

K2S К26

ATI 2

К19

£Е]

I ка I

K5S

кзо

К53

Рис. 4.13. Система газификации: 1 — конвейер, 2— л лужок, 3— входной бункер,

4 — система подачи топлива, 5 — топка, 6 — клапан подачи воздуха, 7— общий

клапан

§4.4. Абстрактное проектирование автоматов 279

К1 — пуск и останов промесса газификации; К2 — индикация работы процесса

гааификацин; КЗ — пуск и останов заполнения входных бункеров; К4 — ин

дикация заполнения входных бункеров; К5 — пуск и останов подачи топлива в

топки; Кб — индикация подачи топлива в топки; К7 — лриостанов газифика

ции в первой топке; К8 — индикация состояния канала К7; К9 — лриостанов

газификации во второй толке; К10 — индикация состояния канала К9; К11 —

приостанов газификации в третьей топке; К12 — индикация состояния канала

Kll\ К13 — приостанов газификации в четвертой топке; КЦ — индикация со

стояния канала К13\ К15— плужок первой топки; К16— плужок второй топки;

К17— плужок третьей топки; К18 — плужок четвертой топки; К19 — конвейер;

К20-К23 — питатели первой— четвертой толки соответственно; К24-К2 7 —

забрасыватели; K28-KS1 — клапаны подачи вторичного воздуха; К32-К35 —

датчики верхнего уровня во входных бункерах; К4 О-К4З— датчики подачи топ

лива; К44-К4 7 — индикация аварии установки заполнения входных бункеров;

К48-К51 — индикация аварии установки подачи топлива в печи; К52 — пуск и

останов процесса управления; K5S — индикация управления; К54 — начальные

установки исполнительных элементов.

Перечисленное множество каналов включается в носитель мо

дели Фа, формализующей функционирование управляемого объ

екта. Кроме этого множества носитель модели Фа может включать

множество дополнительных элементов, являющихся идентифика

торами входных, внутренних и выходных клапанов, которые вве

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

ходя из информации, полученной от технолога, в носителе устана

вливаются причинно-следственные связи вида А —► В, которые

определяют сигнатуру модели Ф0. Очевидно, что модель обла

дает свойством симметричности и ее можно задать в виде мографа

GM (Фа). Причинно-следственные связи могут быть заданы и в

виде временных диаграмм. Переход от мографа или временных

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

диаграмм (которые могут быть заданы в виде мографа) к графу

переходов устройств микропрограммного управления.

Таким образом, на этом этапе проектирования автоматов осу

ществляется переход от отображения А -* В к автоматному отоб

ражению X S + —У S~Y, где: X — входной вектор; У — выходной

вектор, или реакция автомата; S+ — идентификатор внутрен

него состояния, в котором автомат находится в рассматриваемый

момент; 5~ — идентификатор внутреннего состояния, в которое

автомат переходит из состояния S+ под действием входного век

тора X.

§ 4.4. Абстрактное проектирование автоматов

Введенный на этапе алгоритмического проектирования объем

памяти {Si} автомата может быть избыточным. Эта избыточность

устраняется склеиванием эквивалентных состояний. Данное пре

образование относится к этапу абстрактного проектирования.

Эквивалентными называются состояния, при первоначальной

установке в которые автомат вырабатывает для любой входной по

следовательности одну и ту же выходную последовательность.

280

Гл. 4. Теория формальных грамматик и автоматов

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

каждый класс эквивалентных состояний заменить одним состоя

нием, склеивая соответствующие вершины, то полученный граф

переходов будет задавать то же отображение X -* У, что и перво

начальный.

Метод абстрактной минимизации автомата, основанный на

склеивании эквивалентных состояний, был предложен Хафменом

и состоит в последовательном выделении классов эквивалентных

состояний с помощью таблиц выходов и переходов. Рассмотрим

метод Хафмена на примере.

Пример 4.1. Пусть в результате проведения алгоритмического этапа син

теза был получен граф переходов, изображенный на рис. 4.14, а.

Строим таблицу выходов, представляющую собой двумерную таблицу

(табл. 4.3), каждой строке которой взаимно однозначно соответствует значение

входного вектора X, столбцу — внутреннее состояние автомата и иа пересечении

i-й строки с j-м столбцом находится значение выходного вектора Y, который вы

рабатывается на выходе, когда автомат находится в j-м внутреннем состоянии

и иа входе подай i-й вектор.

Таблица 4.3

Si s<

0 1

0 0 ' 1

1 1

Если двум внутренним состояниям автомата соответствуют различные зна

чения столбцов в таблице выходов, то состояния ие эквивалентны, так как в

этих состояниях отображения X —¥ Y различные. Предварительно разобьем

все множество состояний на классы условно эквивалентных состояний, а

именно в один и тот же класс попадают те состояния, которым соответствуют

одинаковые значения столбцов в таблице выходов: К\ — {Si, S2, 5s}, К2 =

= {S3, St, St, S7}.

Если таблицу выходов рассматривать как матрицу инцидент

ности некоторой модели, то внутренние состояния попадают в

один и тот же класс, если в соответствующей ей частотной ма

трице отношений собственные и взаимные частоты внутренних