Реферат: Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)
Антик М.И. 11_03_91МИРЭА
АЛГОРИТМЫПРОЦЕДУРНОГО ТИПА. ОПЕРАЦИОННЫЕ УСТРОЙСТВА
Алгоритмыэтого типа являются следующим этапом обобщения
описаний вычислительных процессов. Теперь, по сравнению сал-
горитмами автоматного типа, на каждом шаге, помимо модифика-
ции памяти, идентифицирующей шаг алгоритма, разрешаетсяизме-
нять любую другую память устройства локально (почастям) или
глобально (всю сразу).
Устройство-исполнитель алгоритма этого типа будем назы-
вать операционным устройством (ОУ).
ОУ можнорассматривать как один синхронный автомат со
сложно структурированной памятью — состоянием: часть памяти
используется для идентификации шага алгоритма,остальная па-
мять используется для запоминания промежуточных данных, вы-
числяемых в процессе последовательного, по шагам, выполнения
алгоритма. Такая модель вычислителя особенно удобнадля рас-
чета продолжительности одного такта работы устройства.
Другойудобной моделью вычислителя является совокуп-
ность взаимодействующих синхронных автоматов, один изкоторых
называется управляющим автоматом (УА), а объединение всехос-
тальных автоматов называется операционным автоматом (ОА).
УА являетсяисполнителем алгоритма автоматного типа, ко-
торый входит составной частью в любой алгоритм процедурного
типа. Кроме того, УА инициирует действия отдельныхшагов ал-
горитма и участвует в их выполнении.
ОА выполняетвсе вычисления на отдельных шагах алгоритма
под управлением УА; кроме того, к ОА удобно отнести все вы-
числения предикатных функций, оставив УА только анализвычис-
ленных предикатных значений.
Прежде чемпереходить к точным терминам, рассмотрим сле-
дующиe примеры алгоритмов процедурного типа.
Например,каноническое описание синхронного конечного
автомата может быть интерпретировано (истолковано)как одно-
шаговый алгоритм процедурного типа.
█
┌──────┐ │
│ ┌──V──V─────┐
│ │ B=FO(S,A)│
│ │ │
│ │ S:=FS(S,A)│
│ └─────┬─────┘
└─────────┘
Исполнительэтого алгоритма состоит только из ОА. На
каждом шаге этого алгоритма изменяется вся памятьустройства,
поэтому управление памятью не требуется, идентифицироватьша-
ги этого алгоритма не надо.
Например,инкрементор с одноразрядным входом и однораз-
рядным выходом может быть реализацией следующих преобразова-
ний:
█
█ p:=1 █
█
┌────────┐│
│ ┌─────V─V───────┐
│ │ (p:, b) = a+p│
│ └───────┬───────┘
└──────────┘
<span Courier New";mso-fareast-font-family: Batang;mso-ansi-language:RU;mso-fareast-language:KO;mso-bidi-language:AR-SA">ОА, реализующий инкрементор в целом, будет следующим:
┌──┬─┐
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 в одной
<span Courier New";mso-fareast-font-family: Batang;mso-ansi-language:RU;mso-fareast-language:KO;mso-bidi-language:AR-SA">из двух форм:
GO m — безусловный переход,
GO (P;m0,m1,m2,...) — условный переход.
здесь m0,m1,… — метки блоков,
P — предикатное значение, интерпретируемое оператором GO
как неотрицательное целое число, являющеесяпорядковым номе-
ром метки в списке меток оператора 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) Блок-схемаалгоритма (микропрограмма в содержательном
виде):
<span Courier New";mso-fareast-font-family: Batang;mso-ansi-language:RU;mso-fareast-language:KO;mso-bidi-language:AR-SA">█
│
┌──────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] --выходная шина
rI, rO --сигналы готовности
A[7..0]:, B[7..0]: --память текущих значений
S[7..0] --разность
z, p --предикатные переменные
z=┐(!/S) --сжатие(свертка) S[7..0] по ИЛИ-НЕ
--можнозаписать иначе z=(S==0)
D=A
-------------------------------------------
m1{rO:=0}
g1<<GO(rI;g1,m2)>>
m2{rO:=0; A:=I1; B:=I2}
m3{(p,S)=A-B}
<<GO(z;g2,m6)>>
g2<<GO(p;m4,m5)>>
m4{(x,B:)=-A+B}
<>
m5{(x,A:)= A-B}
<>
m6{rO:=1}
<<GOg1>>
4) Разработкафункциональной схемы операционного автома-
та.
<span Courier New";mso-fareast-font-family: Batang;mso-ansi-language:RU;mso-fareast-language:KO;mso-bidi-language:AR-SA">В ОА должныбыть реализованы все переменные с памятью и
без, а также вычислительные операции, используемые валгоритме.
A ╔══════════════════════════════>D
─/┬┬──┬┐ ║ ┌────────────┐
C││RG││ ║ │ f1=(A-B) │
││ ││ ║ A│ │
I1═════> ══>╡│ │╞══╝ ═>╡ f2=(-A+B)│ ┌─┐
││ ││ │ │S S│1│
││ ││ │ ╞> ═>┤o───>z
┴┴──┴┘ │ │ │ │
B │ │ └─┘
─/┬┬──┬┐ │ │
C││RG││ │ ├────────────>p
││ ││B B│ │
I2═════> ═>╡│ │╞> ═>╡ │ ─/┬┬─┬┐
││ ││ │ │ C││ │├>rO
││ ││ │ │ ││ ││
rI─────> ┴┴──┴┘ └────────────┘ └┴─┴┘
Кроме того, вОА необходимо реализовать все информацион-
ные связи, соответствующие микрооперации коммутации,а также
микрооперации запоминания (загрузки, записи) и обнуления.
╔══════════════════════════════════════════════╗
║ A ╔══════════════════════║═══════>D
║ ┌────┐ ─/┬┬──┬┐ ║ ┌────┐ ┌──────┐ ║
║ │ MUX│ C││RG││ ║ │M2*8│ 1─>┤cr SM│ ║
╠═>┤0 │ ││ ││ ║ │ │ ├─ │ ║
I1══║═>┤1 ╞══════>╡│ │╞══╩══>╡ ╞═══>╡I1 │ ║ ┌─┐
║ ├ │ ││ ││ A │ │ │ │ ║ │1│
║ │А │ W││ ││ ├─ │ │ S╞═╩>╡ o───>z
║ └A───┘ ─A┴┴──┴┘ └A───┘ │ │ │ │
║ │ │ │ │ │ └─┘
║ umA uA uiA │ │
║ B │ │
║ ┌────┐ ─/┬┬──┬┐ ┌────┐ │ │
║ │ MUX│ C││RG││ │M2*8│ │ p├─────────>p
╚═>╡0 │ ││ ││ B │ │ │ │
I2════>╡1 ╞══════>╡│ │╞═════>╡ ╞═══>╡I2 │ C
├ │ ││ ││ │ │ │ │─/┬┬─┬┐
│А │ W││ ││ ├─ │ │ │1─>┤│T│├>rO
└A───┘ ─A┴┴──┴┘ └A───┘ └──────┘RW││ ││
│ │ │ ─A─A┴┴─┴┘
uMB uB uiB urO uwO
5)Формулировка требований к управляющему автомату.
При формировании управляющих сигналов следует обратить
внимание не только на операции, которые необходимо выполнить
на данном шаге, но и на те оперции, которые нельзя выполнять
на этом шаге, это — как правило, операции измененияпамяти.
Будем считать,что операция активна, если значение уп-
равляющего сигнала равно 1.
Для управлениявычислениями на каждом шаге алгоритма
<span Courier New";mso-fareast-font-family: Batang;mso-ansi-language:RU;mso-fareast-language:KO;mso-bidi-language:AR-SA">потребуются следующие управляющие сигналы:
║umA│umB│uwA│uwB│uiA│uiB│urO│uwO│
══╬═══╪═══╪═══╪═══╪═══╪═══╪═══╪═══╡
m1║ │ │ │ │ │ │ 1 │ 0 │
──╫───┼───┼───┼───┼───┼───┼───┼───┤
m2║ 1 │ 1 │ 1 │ 1 │ │ │ 1 │ 0 │
──╫───┼───┼───┼───┼───┼───┼───┼───┤
m3║ │ │ 0 │ 0 │ 0 │ 1│ │ 0 │
──╫───┼───┼───┼───┼───┼───┼───┼───┤
m4║ │ 0 │ 0│ 1 │ 1 │ 0 │ │ 0 │
──╫───┼───┼───┼───┼───┼───┼───┼───┤
m5║ 0 │ │ 1│ 0 │ 0 │ 1 │ │ 0 │
──╫───┼───┼───┼───┼───┼───┼───┼───┤
m6║ │ │ 0 │ │ │ │ 0 │ 1│
──╨───┴───┴───┴───┴───┴───┴───┴───┘
Внезаполненных клетках сигналы безразличны.
Заметив, чтоumA = umB, uiB = ┐uiA, окончательно полу-
чаем:
╔══════════════════════════════════════════════╗
║ A ╔══════════════════════║═══════>D
║ ┌────┐ ─/┬┬──┬┐ ║ ┌────┐ ┌──────┐ ║
║ │ MUX│ C││RG││ ║ │M2*8│ 1─>┤cr SM│ ║
╠═>╡0 │ ││ ││ ║ │ │ ├─ │ ║
I1══║═>╡1 ╞══════>╡│ │╞══╩══>╡ ╞═══>╡I1 │ ║ ┌─┐
║ ├ │ ││ ││ │ │ │ │ ║ │1│
║ │А │ W││ ││ ├─ │ │ S╞═╩>╡ o───>z
║ └A───┘ ─A┴┴──┴┘ └A───┘ │ │ │ │
║ └────┐ ┌─┘ B ┌────┘ ├─ │ └─┘
║ ┌────┐│ │─/┬┬──┬┐ │ ┌────┐ │ │
║ │ MUX││ │ C││RG││ │ │M2*8│ │ p├─────────>p
╚═>╡0 ││ │ ││ ││ │ │ │ │ │
I2════>╡1 ╞│═══│═>┤│ │╞══│══>┤ ╞═══>╡I2 │
├ ││ │ ││ ││ │ │ │ │ │
│А ││ │ W││ ││ │ ├─ │ │ │ C
└A───┘│ │─A┴┴──┴┘ │ └A───┘ └──────┘ ─/┬┬─┬┐
│ │ │ └─┐ │ ┌─┐│ 1─>┤│T│├>rO
│ │ │ │ ├>┤o┘ RW││ ││
├────┘ │ │ │└─┘ ─A─A┴┴─┴┘
umB uwA uwB uiA urO uwO
---│--------│----│-----│----------------------│-│-----
y1 y2 y3 y4 y5 y6
║y1│y2│y3│y4│y5│y6│
══╬══╪══╪══╪══╪══╪══╡
m1║ │ │ │ │ 1│ 0│
──╫──┼──┼──┼──┼──┼──┤
m2║ 1│ 1│ 1│ │ 1│ 0│
──╫──┼──┼──┼──┼──┼──┤
m3║ │ 0│0│ 0│ │ 0│
──╫──┼──┼──┼──┼──┼──┤
m4║ 0│ 0│ 1│ 1│ │ 0│
──╫──┼──┼──┼──┼──┼──┤
m5║ 0│ 1│ 0│ 0│ │ 0│
──╫──┼──┼──┼──┼──┼──┤
m6║ │ 0│ │ │ 0│ 1│
──╨──┴──┴──┴──┴──┴──┘
<span Courier New";mso-fareast-font-family: Batang;mso-ansi-language:RU;mso-fareast-language:KO;mso-bidi-language:AR-SA">Структуравычислителя:
┌────────────────────────────────┐
══>╡I1 │
│ │
══>╡I2 ОА D╞══>
│ │
┌──/C rO├──>
│ │ │
│ │z p umB uwA uwB uiA urO uwO │
│ └┬──┬──A───A───A───A───A───A─────┘
│ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ │ │
│ ┌V──V──┴───┴───┴───┴───┴───┴─────┐
│ │z p y1 y2 y3 y4 y5 y6 │
│ │ │
┴──/C │
│ УА │
──>┤rI │
└────────────────────────────────┘
УА долженвыполнять следующий алгоритм автоматного типа,
представленный в виде блок-текста:
m1{xxxx10}
g1<<GO(rI;g1,m2)>>
m2{111x10}
m3{x000x0}
<<GO(z;g2,m6)>>
g2<<GO(p;m4,m5>>
m4{0011x0}
<>
m5{0100x0}
<>
m6{x0xx01}
<>
МИКРОПРОГРАММИРОВАНИЕ.ОПРЕДЕЛЕНИЯ.
МИКРООПЕРАЦИЯ- базисное (элементарное) действие, необ-
ходимое для получения (вычисления) значения одной или более
переменных.
Микрооперацияприсваивания В=А означает, что переменные
левой части получают значения выражения из правой части.
Всегда разрядность левой части равна разрядностиправой час-
ти. При этом биты, расположенные на одной и той жепозиции в
левой и правой частях, равны.
Неиспользуемыеразряды в левой части и произвольные зна-
чения в правой части микрооперации присваивания обозначаются
(х). Например:
(В[7],x,B[6..0]) = (A[7..0],x)
означает арифметический сдвиг влево на один разряд 8-разряд-
ного числа с присваиванием произвольного значения младшему
разряду и с потерей старшего после знака разряда. А, напри-
мер, микрооперация
(B[7..0],d) =(A[7],A[7..0])
означает арифметический сдвиг вправо на один разряд.
Микрооперация
(p,S[3..0]) =A[3..0] + B[3..0] + q
описывает действие, выполняемое стандартным4-разрядным сум-
матором, если ( А, В,q ) являются его непосредственнымивхода-
ми, а ( р,S ) — выходами.
Микрооперация(: ) — двоеточие - означает запоминание
(изменение значения) в памяти устройства. Переменная типапа-
мять сохраняет свое значение между двумя очередными присва-
<span Courier New";mso-fareast-font-family: Batang;mso-ansi-language:RU;mso-fareast-language:KO;mso-bidi-language:AR-SA">иваниями.
Микрооперациивсегда входят в состав микрооператоров.
МИКРООПЕРАТОР- набор взаимосвязанных микроопераций (или
одна микрооперация ), выполняемых одновременно и необходимых
для получения одного или более значений. Например:
( e,D:) = R1 +R2 + c
Фрагмент аппаратуры, реализующей этот микрооператор, мог бы
быть, например, таким:
┌───┐
c │MUX│
┌┬──┬┐ │ │ ┌───┐
││T│├───>┤0 │ ┌────┐ │MUX│ D
└┴──┴┘──>┤1 │ │ SM│ │ │ ┌┬──┬┐
──>┤А ├───>┤cr │ ═══>╡0 ╞═══>╡│RG│╞══>
├───┤ │ S╞═════>╡1 │ └┴──┴┘
R1 │MUX│ │ │ ═══>╡А │
┌┬──┬┐ │ │ │ │ └─