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

Антик М.И. 11_03_91МИРЭА

АЛГОРИТМЫПРОЦЕДУРНОГО ТИПА. ОПЕРАЦИОННЫЕ УСТРОЙСТВА

Алгоритмыэтого типа являются следующим этапом обобщения

описаний вычислительных процессов. Теперь, по сравнению сал-

горитмами автоматного типа, на каждом шаге, помимо модифика-

ции памяти, идентифицирующей шаг алгоритма, разрешаетсяизме-

нять любую другую память устройства локально (почастям) или

глобально (всю сразу).

Устройство-исполнитель алгоритма этого типа будем назы-

вать операционным устройством (ОУ).

ОУ можнорассматривать как один синхронный автомат со

сложно структурированной памятью — состоянием: часть памяти

используется для идентификации шага алгоритма,остальная па-

мять используется для запоминания промежуточных данных, вы-

числяемых в процессе последовательного, по шагам, выполнения

алгоритма. Такая модель вычислителя особенно удобнадля рас-

чета продолжительности одного такта работы устройства.

Другойудобной моделью вычислителя является совокуп-

ность взаимодействующих синхронных автоматов, один изкоторых

называется управляющим автоматом (УА), а объединение всехос-

тальных автоматов называется операционным автоматом (ОА).

УА являетсяисполнителем алгоритма автоматного типа, ко-

торый входит составной частью в любой алгоритм процедурного

типа. Кроме того, УА инициирует действия отдельныхшагов ал-

горитма и участвует в их выполнении.

ОА выполняетвсе вычисления на отдельных шагах алгоритма

под управлением УА; кроме того, к ОА удобно отнести все вы-

числения предикатных функций, оставив УА только анализвычис-

ленных предикатных значений.

Прежде чемпереходить к точным терминам, рассмотрим сле-

дующиe примеры алгоритмов процедурного типа.

Например,каноническое описание синхронного конечного

автомата может быть интерпретировано (истолковано)как одно-

шаговый алгоритм процедурного типа.

█

┌──────┐ │

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

│ │ B=FO(S,A)│

│ │ │

│ │ S:=FS(S,A)│

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

└─────────┘

Исполнительэтого алгоритма состоит только из ОА. На

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

поэтому управление памятью не требуется, идентифицироватьша-

ги этого алгоритма не надо.

Например,инкрементор с одноразрядным входом и однораз-

рядным выходом может быть реализацией следующих преобразова-

ний:

█

█ p:=1 █

█

┌────────┐│

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

│ │ (p:, b) = a+p│

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

└──────────┘

ОА, реализующий инкрементор в целом, будет следующим:

┌──┬─┐

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

как неотрицательное целое число, являющеесяпорядковым номе-

ром метки в списке меток оператора 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) Блок-схемаалгоритма (микропрограмма в содержательном

виде):

█

│

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

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

│ ┌───────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) Разработкафункциональной схемы операционного автома-

та.

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

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

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.

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

потребуются следующие управляющие сигналы:

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

──╨──┴──┴──┴──┴──┴──┘

Структуравычислителя:

┌────────────────────────────────┐

══>╡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 ) — выходами.

Микрооперация(: ) — двоеточие - означает запоминание

(изменение значения) в памяти устройства. Переменная типапа-

мять сохраняет свое значение между двумя очередными присва-

иваниями.

Микрооперациивсегда входят в состав микрооператоров.

МИКРООПЕРАТОР- набор взаимосвязанных микроопераций (или

одна микрооперация ), выполняемых одновременно и необходимых

для получения одного или более значений. Например:

( e,D:) = R1 +R2 + c

Фрагмент аппаратуры, реализующей этот микрооператор, мог бы

быть, например, таким:

┌───┐

c │MUX│

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

││T│├───>┤0 │ ┌────┐ │MUX│ D

└┴──┴┘──>┤1 │ │ SM│ │ │ ┌┬──┬┐

──>┤А ├───>┤cr │ ═══>╡0 ╞═══>╡│RG│╞══>

├───┤ │ S╞═════>╡1 │ └┴──┴┘

R1 │MUX│ │ │ ═══>╡А │

┌┬──┬┐ │ │ │ │ └─

еще рефераты

Еще работы по радиоэлектронике

Реферат по радиоэлектронике

Разработка методики программного тестирования цифровых устройств с помощью программного пакета Design Center

29 Августа 2013

Реферат по радиоэлектронике

Проектирование лог. ключа в n-МОП базисе с квазилинейной нагрузкой (МСХТ)

29 Августа 2013

Реферат по радиоэлектронике

Расчет характеристик канала вывода СИ (синхротронного излучения)

29 Августа 2013

Реферат по радиоэлектронике

Устройства защиты громкоговорителей

29 Августа 2013