Реферат: Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)
Реферат: Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)
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 в одной
из двух форм:
GO m - безусловный переход,
GO (P; m0,m1,m2,...) - условный переход.
здесь m0,m1,... - метки блоков,
P - предикатное значение,интерпретируемое оператором GO
- 3 -
как неотрицательное целое число, являющееся порядковым номе-
ром метки в списке меток оператора GO. С этой метки должно
быть продолжено выполнение алгоритма. Блоки условных перехо-
дов эквивалентны предикатным вершинам блок-схемы алгоритма.
На следующем более сложном примере демонстрируется пос-
ледовательность синтеза операционного устройства.
Пример. Вычислитель наибольшего общего делителя (НОД)
двух натуральных чисел (8-разрядных).
1) Разработаем интерфейс вычислителя:
8 ┌──┬─────┬──┐
═══╪═>╡I1│ НОД │ │
│ │ │ │ 8
8 │ │ │D ╞══╪══>
═══╪═>╡I2│ │ │
├──┤ ├──┤
─────>┤rI│ │rO├─────>
├──┤ │ │
─────>┤ C│ │ │
└──┴─────┴──┘
I1[7..0], I2[7..0] -входные информационные шины.
rI -входной сигнал готовности: если rI=1, то на входах I1,
I2 готовы операнды.
D[7..0] -выходная информационная шина .
rO -выходной сигнал готовности: если rO=1, то готов резуль-
тат на шине D, который сохраняется до появления новых операн-
дов.
2) Математическое обоснование алгоритма вычислений:
Идея алгоритма, следуя Евклиду (IIIв. до р.Х.), заключа-
ется в том, что НОД двух натуральных чисел А и В в случае ра-
венства этих чисел совпадает с любым из них, а в случае их
неравенства совпадает с НОД двух других чисел: меньшего и
разности между большим и меньшим. Последовательно, уменьшая
числа, получим два равных числа -значение одного из них и бу-
дет НОД исходных чисел.
3) Блок-схема алгоритма (микропрограмма в содержательном
виде):
- 4 -
█
│
┌──────V──────┐
m1│ rO: = 0 │
└──────┬──────┘
│┌──────────────────┐
││┌─────┐ │
─VVV─ │ │
/ \ 0 │ │
< rI>─────┘ │
\_/ │
│1 │
┌──────V──────┐ │
│ rO: = 0 │ │
│ │ │
m2│ А: = I1 │ │
│ │ │
│ B: = I2 │ │
└──────┬──────┘ │
┌───────────────────┐│ │
│ ┌─────VV──────┐ │
│ m3│ (p,S)=A - B │ │
│ └──────┬──────┘ │
│ ─V─ m6 │
│ / \ =0 ┌──────────┐│
│ z <S==0>───>┤ rO:=1;D=A├┘
│ \__/ └──────────┘
│ │╪0
│ V
│ 0 / \ 1
│ ┌───────< p >────────┐
│ ┌───────V──────┐ \_/ ┌───────V──────┐
│m4│ (x,B:)=-A+B │ m5│ (x,A:)=A - B │
│ └───────┬──────┘ └───────┬──────┘
└──────────┴────────────────────┘
Или в виде блок-текста:
I1[7..0], I2[7..0] --входные шины
D[7..0] --выходная шина
