Реферат: Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)
Реферат: Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)
2Антик М.И. 11_03_91 МИРЭА
_АЛГОРИТМЫ ПРОЦЕДУРНОГО ТИПА. ОПЕРАЦИОННЫЕ УСТРОЙСТВА
Алгоритмы этого типа являются следующим этапом обобщения
описаний вычислительных процессов. Теперь, по сравнению с ал-
горитмами автоматного типа, на каждом шаге, помимо модифика-
ции памяти, идентифицирующей шаг алгоритма, разрешается изме-
нять любую другую память устройства локально (по частям) или
глобально (всю сразу).
Устройство-исполнитель алгоритма этого типа будем назы-
вать операционным устройством (ОУ).
ОУ можно рассматривать как один синхронный автомат со
сложно структурированной памятью - состоянием: часть памяти
используется для идентификации шага алгоритма, остальная па-
мять используется для запоминания промежуточных данных, вы-
числяемых в процессе последовательного, по шагам, выполнения
алгоритма. Такая модель вычислителя особенно удобна для рас-
чета продолжительности одного такта работы устройства.
Другой удобной моделью вычислителя является совокуп-
ность взаимодействующих синхронных автоматов, один из которых
называется управляющим автоматом (УА), а объединение всех ос-
тальных автоматов называется операционным автоматом (ОА).
УА является исполнителем алгоритма автоматного типа, ко-
торый входит составной частью в любой алгоритм процедурного
типа. Кроме того, УА инициирует действия отдельных шагов ал-
горитма и участвует в их выполнении.
ОА выполняет все вычисления на отдельных шагах алгоритма
под управлением УА; кроме того, к ОА удобно отнести все вы-
числения предикатных функций, оставив УА только анализ вычис-
ленных предикатных значений.
Прежде чем переходить к точным терминам, рассмотрим сле-
дующиe примеры алгоритмов процедурного типа.
Например, каноническое описание синхронного конечного
автомата может быть интерпретировано (истолковано) как одно-
шаговый алгоритм процедурного типа.
█
┌──────┐ │
│ ┌──V──V─────┐
│ │ B=FO(S,A) │
│ │ │
│ │ S:=FS(S,A)│
│ └─────┬─────┘
└─────────┘
Исполнитель этого алгоритма состоит только из ОА. На
каждом шаге этого алгоритма изменяется вся память устройства,
поэтому управление памятью не требуется, идентифицировать ша-
ги этого алгоритма не надо.
Например, инкрементор с одноразрядным входом и однораз-
рядным выходом может быть реализацией следующих преобразова-
ний:
█
█ p:=1 █
█
┌────────┐ │
│ ┌─────V─V───────┐
│ │ (p:, b) = a+p │
│ └───────┬───────┘
└──────────┘
- 2 -
ОА, реализующий инкрементор в целом, будет следующим:
┌──┬─┐
a ──────────────────┤HS│S├────_b
┌─┬─┐p │ │ │
начальное значен.─┤S│T├──┤ │P├──┐
├─┤ │ └──┴─┘ │
SYN ─────────/C│ │ │
┌┤D│ │ │
│└─┴─┘ │
└───────────────┘
Конечно, эта реализация совпадает с реализацией алгоритма ав-
томатного типа, если состояние р1 кодируется 1, а состояние
р0 - 0.
Этот пример показывает,что до начала вычислений может
потребоваться начальная установка памяти. На самом деле это
необходимо было уже в алгоритмах автоматного типа, так как
код начального состояния требует предварительной установ-
ки. Ограничимся здесь обозначением этой проблемы, а решение
ее, связанное прежде всего с корректной синхронизацией ус-
тройства в первом такте его работы, рассмотрим ниже.
При рассмотрении процедуры построения автомата Мура эк-
вивалентного автомату Мили , не обсуждалась простая возмож-
ность ее реализации и на структурном уровне. Например, только
что рассмотренный автомат Мили может быть преобразован в эк-
вивалентный автомат Мура по одному из следующих вариантов:
┌┬─┬┐t┌──┬─┐ ┌──┬─┐ ┌┬─┬┐
a ──_┤│T│├_┤HS│S├─_b a ─────_┤HS│S├─_┤│T│├─_b
─/┴┴─┴┘ │ │ │ │ │ │─/┴┴─┴┘
C │ │ │ C │ │ │ C
─/┬┬─┬┐p│ │ │ ─/┬┬─┬┐p│ │ │
┌_┤│T│├_┤ │P├┐ ┌_┤│T│├_┤ │P├┐
│ └┴─┴┘ └──┴─┘│ │ └┴─┴┘ └──┴─┘│
└─────────────┘ └─────────────┘
При таких структурных преобразованиях проще истолковы-
вать алгоритмы как процедурные.
█ █
█ p:=1; t:=0 █ █ p:=1 █
█ █
┌────────┐ │ ┌────────┐ │
│ ┌─────V─V───────┐ │ ┌─────V─V───────┐
│ │t:=a;(p:,b)=t+p│ │ │ (p , b):= a+p │
│ └───────┬───────┘ │ └───────┬───────┘
└──────────┘ └──────────┘
БЛОК-ТЕКСТ. Способ описания автоматного алгоритма после
некоторых дополнений может быть использован и для описания
алгоритмов в процедурной форме:
Блок-текст состоит из трех частей:
1)- Описание переменных и начальных значений памяти.
2)- Описания функций и связей. Записываются любые функции и
функциональные связи (в том числе предикатные), не использу-
ющие запоминания. Переменные из левой части операции присва-
ивания таких функциональных описаний используются в блоках
процедуры.
3)- Процедура, состоящая из блоков (микроблоков) операторных
и блоков переходов:
- операторные - в скобках вида {.....},
- перехода - в скобках вида <<...>>;
и те, и другие блоки могут снабжаться метками, стоящими перед
блоком. В блоках перехода используется оператор GO в одной
из двух форм:
Страницы: 1, 2, 3, 4, 5, 6, 7, 8
