Смекни!
smekni.com

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

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─ │ │

/ &bsol; 0 │ │

< rI>─────┘ │

&bsol;_/ │

│1 │

┌──────V──────┐ │

│ rO: = 0 │ │

│ │ │

m2│ А: = I1 │ │

│ │ │

│ B: = I2 │ │

└──────┬──────┘ │

┌───────────────────┐│ │

│ ┌─────VV──────┐ │

│ m3│ (p,S)=A - B │ │

│ └──────┬──────┘ │

│ ─V─ m6 │

│ / &bsol; =0 ┌──────────┐│

│ z <S==0>───>┤ rO:=1;D=A├┘

│ &bsol;__/ └──────────┘

│ │╪0

│ V

│ 0 / &bsol; 1

│ ┌───────< p >────────┐

│ ┌───────V──────┐ &bsol;_/ ┌───────V──────┐

│m4│ (x,B:)=-A+B │ m5│ (x,A:)=A - B │

│ └───────┬──────┘ └───────┬──────┘