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

Тип работы:
Реферат
Предмет:
Радиоэлектроника


Узнать стоимость

Детальная информация о работе

Выдержка из работы

_АЛГОРИТМИ ПРОЦЕДУРНОГО ТИПУ. ОПЕРАЦІЙНІ УСТРОЙСТВА
Алгоритми цього є наступним етапом обобщения
описів обчислювальних процесів. Тепер, проти ал-
горитмами автоматного типу, кожному кроці, крім модифика-
ции пам’яті, идентифицирующей крок алгоритму, дозволяється изме-
нять будь-яку іншу пам’ять устрою локально (частинами) или
глобально (всю сразу).
Устройство-исполнитель алгоритму цього будемо назы-
вать операційним пристроєм (ОУ).
ЗУ можна як один синхронний автомат со
складно структурованої пам’яттю — станом: частина памяти
використовується для ідентифікації кроку алгоритму, інша па-
м’яти використовується для запам’ятовування проміжних даних, вы-
числяемых у процесі послідовного, по кроків, выполнения
алгоритму. У такій моделі обчислювача особливо зручна для рас-
подружжя тривалості одного такту роботи устройства.
Інший зручною моделлю обчислювача є совокуп-
ность взаємодіючих синхронних автоматів, одне із которых
називається управляючим автоматом (УА), поєднання всіх ос-
тальных автоматів називається операційним автоматом (ОА).
УА виконавець алгоритму автоматного типу, ко-
торый входить складовою у будь-якій алгоритм процедурного
типу. З іншого боку, УА ініціює дії окремих кроків ал-
горитма і бере участь у їх выполнении.
ОА виконує все обчислення на окремих кроках алгоритма
під керівництвом УА; ще, до ОА зручно віднести все вы-
числения предикатных функцій, залишивши УА лише аналіз вычис-
ленних предикатных значений.
Перш ніж переходити до точним термінам, розглянемо сле-
дующи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 ???/З?? ?
??D?? ?
??? ?
???

Звісно, ця реалізація збігаються з реалізацією алгоритму ав-
томатного типу, якщо вже стан р1 кодується 1, а состояние
р0 — 0.
Цей приклад показывает, что на початок обчислень может
знадобитися початкова установка пам’яті. Насправді это
потрібно було вже у алгоритми автоматного типу, так как
код початкового стану потребує попереднього установ-
кі. Обмежимося тут позначенням цієї проблеми, а решение
її, пов’язане насамперед із коректною синхронізацією ус-
тройства у першому такті його роботи, розглянемо ниже.
Зблизька процедури побудови автомата Мура эк-
вивалентного автомату Мілі, не обговорювалася проста возмож-
ность його реалізації і структурному рівні. Наприклад, только
що розглянутий автомат Мілі то, можливо перетворений на эк-
вивалентный автомат Мура однієї зі наступних вариантов:
???t??? ??? ???
a ??#??T??#?HS?S??#b a ???#?HS?S??#??T???#b
?/???? ?? ?? ??/???
З? ?? З? ?? 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???>
???? ?
???>? З?? ?
???

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 ???>? 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>
m2{rO: =0; A: =I1; B: =I2}
m3{(p, S)=A-B}
>
g2>
m4{(x, B:)=-A+B}
>
m5{(x, A:)= A-B}
>
m6{rO: =1}
>

— 5 —

4) Розробка функціональної схеми операційного автомата.

У ОА мають бути реалізовані все перемінні з пам’яттю и
без, а також обчислювальні операции, используемые в алгоритме.

A ???> D
?/???? ???
C?? RG?? ? f1=(A-B) ?
?? ??? A? ?
I1???> ??>?? ??? ?>? f2=(-A+B)? ???
?? ??? ?P.S S?1?
?? ??? ?> ?>? o???> z
???? ?? ?
B? ? ???
?/???? ?
C?? RG?? ???> p
?? ??B B? ?
I2???> ?>?? ??> ?>?? ?/???
?? ??? ? З? ??> rO
?? ??? ? ?? ??
rI???> ??? ??? ???

З іншого боку, в ОА необхідно реалізувати все информацион-
ные зв’язку, відповідні микрооперации комутації, а также
микрооперации запам’ятовування (завантаження, записи) і обнуления.

???
? A ???> D
? ??? ?/???? ??? ??? ?
?? MUX? C?? RG?? ?M2*8? 1?> ?cr SM? ?
??> ?0? ?? ??? ?? ??? ?
I1???> ?1 ???> ?? ???>? ???> ?I1? ? ???
?? ? ?? ?? A? ?? ?? ?1?
? ?А? W? ?? ??? ? P. 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??? ???R W? ??
?? ? ?A?A???
uMB uB uiB urO uwO

5) Формулювання вимог до управляючому автомату.
При формуванні управляючих сигналів слід обратить
не лише для операцій, які потрібно выполнить
цьому кроці, а й у ті оперции, які можна выполнять
у цьому кроці, це — зазвичай, операції зміни памяти.
Вважатимемо, що операція із активна, якщо значення уп-
равляющего сигналу одно 1.

— 6 —
Для управління обчисленнями кожному кроці алгоритма
знадобляться такі управляючі сигналы:

?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? ?? ??? ? P. 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? R W? ??
???? ?? ??? ?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?
???

— 7 —

Структура вычислителя:
???
??> ?I1 ?
? ?
??> ?I2 ОА D???>
? ?
???/З 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 ?
?? ?
???/З ?
? УА ?
??> ?rI ?
???

УА має виконувати наступний алгоритм автоматного типа,
поданий у вигляді блок-текста:
m1{xxxx10}
g1>
m2{111×10}
m3{x000×0}
>
g2>
m4{0011×0}
>
m5{0100×0}
>
m6{x0xx01}
>

_МІКРОПРОГРАМУВАННЯ. ОПРЕДЕЛЕНИЯ.
МИКРООПЕРАЦИЯ — базисне (елементарне) дію, необ-
ходимое щоб одержати (обчислення) значення однієї або более
переменных.
Микрооперация присвоювання В=А означає, що переменные
лівої частини отримують значення висловлювання з правої части.
Завжди розрядність лівої частини дорівнює розрядності правої час-
ти. У цьому біти, розташовані в одній й тією самою позиції в
лівої і правої частинах, равны.
Невикористовувані розряди у частині і довільні зна-
чения у правій частині микрооперации присвоювання обозначаются
(x). Например:
(В[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) — выходами.
Микрооперация (:) — двокрапка — означає запоминание
(зміна значення) у пам’яті устрою. Змінна типу па-
м’яти зберігає свою значення між двома черговими присва-
иваниями.

— 8 —
Микрооперации завжди входять до складу микрооператоров.
МИКРООПЕРАТОР — набір взаємозалежних микроопераций (или
одна микрооперация), виконуваних це й необходимых
щоб одержати однієї чи більш значень. Например:
(e, D:) = R1 + R2 + c
Фрагмент апаратури, реалізує цей микрооператор, міг бы
бути, наприклад, таким:
???
з? MUX?
???? ? ???
??T ???> ?0? ??? ?MUX? D
??? ??> ?1? ? SM?? ? ???
??> ?А ???> ?cr? ???> ?0 ???> ??RG???>
???? S???> ?1? ???
R1? MUX?? ? ???> ?А ?
???? ?? ? ???
??RG???> ?0 ???> ?I1? ???
??? ??> ?1? ?? ?MUX?
??> ?А? ?? ? ???> e
???? p???> ?0 ?
R2? MUX???> ?I2? ???> ?1 ?
???? ? ??? ???> ?А ?
??RG???> ?0? ???
??? ??> ?1 ?
??> ?А ?
???

Імена всіх змінних, які у цьому микрооператоре,
означають виконання микроопераций комутації (транспортиров-
кі). Значення змінних коммутируются на входи суммматора,
а результат підсумовування — до місць розташування переменных.
МИКРОБЛОК — набір микрооператоров, виконуваних одновре-
менно (щодо одного такті) й одночасно. У першому микроблоке любо-
му з бітов присвоюється лише одна значение.
Синхронність означає, що у всіх микрооператорах одно-
го микроблока використовується лише «старе «значення памяти.
Например:
{ (p, A):= A + B
(C, r):= A + D }
— у тому, в іншому микрооператоре використовується те й то
ж старе значення А.
У той самий час у микроблоке:
{ (C, x):= A + D
(x, A)= З + B }
у першому микрооператоре використовується нового значення А, а во
другому — старе значення З. Зрозуміло, ці дві дії вы-
полняются одновременнo двома різних сумматорах.
При реалізації микроблока { A:= B; B:= 0 } обязательна
синхронна реалізація В: =0 (хоча зазвичай це проще
реалізувати асинхронно, але ці призводить до помилці). Другой
правильний варіант: можна виконати В: =0 асинхронно, але в
следющем такте.
Завжди передбачається, що предикат обчислюється вместе
(щодо одного такті) про те микроблоком, на яких непосредственно
слід його использование. Таким чином, тут, як і в
микроблоке, використовується старе значення пам’яті, существовав-
шиї перед входом в микроблок. Це з особенностями
взаємодії ОА і УА. Например:

— 9 —

? ?
? CT: =(?0)?? CT: =(?0)?
? ?
? ?
???V??? ???V???
m1? CT: =3? m1? CT: =3 ?
??? ???
???>? ???> ?
? ?V?? ?V?
? / =0? / =0
? ?>? ?>
? ___/? ___/
? ??0? ??0
? ???V???? ???V???
?m2??? ?m2… ?
?? ?? ? ?
? ?CT: =CT-1?? ?CT: =CT-1?
? ???? ???
???? ???V???
?m3… ?
? ???
???

У першому випадку цикл буде виконано 4 разу; у другому — если
в микроблоке m3 немає операцій, модифицирующих СП, — 3 ра-
за. (Зверніть увагу до початкова значення СТ!)
МІКРОКОМАНДА — набір сигналів, що надходить з УА в ОА и
интерпретируемый як управляющий, т. е. необхідний выпол-
нения всіх микроопераций одного микроблока. Сигнали, входящие
в микрокоманду, можуть брати участь в микрооперациях і в
ролі информационных.
Микрокомандой також інколи називають слово управляющей
пам’яті (зазвичай ПЗУ), що є частиною УА. Для различения
цих понять слово керуючої пам’яті називатимемо МИКРО-
ИНСТРУКЦИЕЙ.
МІКРОПРОГРАМА ЗМІСТОВНА — алгоритм, представленный
як микроблоков і предикатных блоків на одній із принятых
форм, наприклад, як блок-схемы чи блок-текста.
МІКРОПРОГРАМА КОДИРОВАННАЯ — апаратна форма содержа-
тельной мікропрограми як кодів, що заповнюють управляющую
память.

_КАНОНІЧНА СТРУКТУРА ОПЕРАЦІЙНОГО АВТОМАТА
У випадку канонічна структура операційного ав-
томату має вид:
???
? ?
? ??? ??? ??? ??? ?
??> ?комутація? ??пам'ять? ?комутація? ?функции???
? ???> ?? ???>? ???>? ?
??>?? ?? ??? ?? ???>
??A??? ?/???A??? ???A??? ???A???
? ???CC? ? ?
? SYN?> ?&??? ? ?
? ??? ?? ?
? yC???? ? ?
???
сигнали управления

Настільки чіткого розмежування операцій на зони (пам'ять, комму-
тація, функції) може і не. Наприклад, такі широко ис-
пользуемые функції як зрушення або добре поєднуються с
комутацією, або інтегруються з регістрами хранения. Также
часто інтегруються зі збереженням функції инкремента и

— 10 —
декремента (лічильники звичайні і реверсивные).
Особливо виділимо сигнал yС, управляючий доступом синхросиг-
налов в ОА. Такий варіант управління, званий условной
синхронізацією, дозволяє заборонити будь-які зміни пам’яті ОА
в якомусь такті. Причому, якщо робочим є зріз (зад-
ний фронт) сигналу синхронізації, то використовується елемент И,
як і показано на рисунке. Если ж робочим є фронт (пе-
редний фронт) сигналу, то використовується елемент АБО. (Первый
перепад сигналу синхронізації з нового такті ні быть
рабочим.)

_ОПТИМІЗАЦІЯ ОПЕРАЦІЙНОГО АВТОМАТА
Під час проектування обчислювального устрою основными
є обмеження на:
1) — час вычисления;
2) — обсяг апаратури, реалізує вычисления;
3) — тип застосовуваних базових функций.
ОПТИМІЗАЦІЯ АПППАРАТУРЫ ПРИ ЗБЕРЕЖЕННІ МІНІМАЛЬНОГО ВРЕМЕНИ
Алгоритм функціонального типу має максимальним по-
тенциальным паралелізмом (у межах даної алгоритмической
ідеї), и, следовательно, його реалізація як КС обладает
максимальним швидкодією проти будь-якими другими
обчислювачами. Неможливість реалізації обчислювача як КС
то, можливо зумовлена такими причинами:
— дуже великий обсяг апаратури КС;
— функціональне подання, і його реалізація являются
статичним відображенням вхідних об'єктів у вихідні: это
виключає можливості роботи з об'єктами, які «ведуть се-
бя «складніше у часі; неможливо також реализовать
принципово рекуррентные алгоритми (см., например, алгоритм
Евкліда перебування НОД).
Проте, якщо формально алгоритм функционального
типу то, можливо записано, то проектування устрою надо
розпочинати з записи саме такої алгоритма.
Мінімізація апаратури «складної «КС із переходом про-
цедурный варіант реалізації пов’язані з «економією «числа опера-
ционных елементів, тобто. зі злиттям декого з тих в один
функціональний модуль, виконує ці операції з очереди.
Таке усунення потребуватиме запам’ятовування всіх змінних (входных
і выходных), связанных з виконанням операцій. Требуется
також управління пам’яттю, що з цим функціональним мо-
дулем, і навіть — то, можливо — управління самим функциональным
модулем, коли він об'єднав суттєво відмінні функции.
Перехід до процедурної реалізації і, отже, к
дискретизації часу неминуче збільшить час обчислення од-
ного результату — навіть за реалізації структури як і КС.
У цьому, хоч як дивно, може зменшитися час следующих
друг за іншому обчислень саме за дискретизації време-
ні застосування про «конвеєрних «обчислень — но
про це піде у іншому курсе.
Розглянемо можливість скорочення апаратури без увели-
чения часу рішення, досягнутого в алгоритмі функциональ-
ного типу. Порівняємо схемою устрою, що реалізовуватиме алгоритм
функціонального типу, просту модель як направленного
графа. Вершини графа відповідатимуть операціям, а дуги
— змінним алгоритму. Назвемо такий граф сигнальним (графом
потоків даних). Зауважимо, що сигнальний граф завжди будет
ациклическим.
Мінімальність часу обчислень збережеться, якщо совме-
щать до одного функціональний модуль операції, які располо-
дружини однією й тому самому шляху до сигнальному графі, або на аль-
тернативных шляхах решения.

— 11 —

_МІНІМІЗАЦІЯ АППАРАТУРЫ
Може бути, що у заваді в сигнальному графе
розташовані операції, погано чи взагалі не совмещаемые друг с
іншому (тобто. суміщення це не дає економії в апаратурі функци-
онального модуля). Можливе також, що проведена минимиза-
ция, яка зберігає мінімальне час, Демшевського не дозволяє выполнить
обмеження на обсяг апаратури. У разі необходима
глибша минимизация, охватывающая паралельні ветви
сигнального графа. Мінімізація мусить бути взаємопов'язаної по
всім компонентами ОА: з пам’яті, функціональним модулями і ком-
мутации.
Нині процедури мінімізації не формализованы
і зводяться до перебору «правдоподібних «вариантов.
Можна запропонувати таку послідовність действий:
1) — все «схожі «функції (операції) реалізувати на одном
функціональному модулі, наприклад, все підсумовування выполнять
однією сумматоре;
2)-скорректировать алгоритм те щоб щодо одного микроблоке не
виконувалося більше операції у тому ж функци-
ональном модуле;
3) — мінімізувати пам’ять автомата, тобто. число запоминаемых
проміжних переменных;
Виконання цих етапів можуть призвести до ускладнення ком-
мутації, отже, і до підвищення цієї компоненти в аппарату-
ре ОА. Якщо обмеження за обсягом апаратури досі наруше-
але, то повторити етапи 1 — 3 з іншим варіантом объединения
функціональних модулів і памяти.
При реалізації ОА — щоб уникнути помилок -необхідно бук-
вально слідувати опису алгоритму, але водночас, при
проектуванні самого алгоритму треба уявляти собі реали-
зацию микроблоков. Реалізація одним і тієї ж обчислень может
бути значно різної за обсягом аппаратуры.
Наприклад, обчислення в циклі зажадають реализации:
???
?
???V??? A ???
? J: =0? ???? MUX? ???
??? ??RG?0???> ?0? ? f ?
???? ?? … ?. ?A[J]? ?
? ???V??V??? ?? … ?. ???>? ?
? …? ?? … ?.? ?? B
?? ? ??? ?? ?? ???>
?? B= f (…, A[J])? ?? ?K???> ?K? ? ?
?? ? ?? ?.? ?.? ??>? ?
?? J: =J+1? ?? ?.? ?.? ? ?
? ??? ?? ?.? ?.? ? ?
? ?V? ??? ??? ???
? ?А ?
???> ???
__/

(реалізація лічильника J не показанa).

— 12 —
Запишемо цього фрагмента алгоритму інакше те щоб нужный
біт витягався з допомогою зсуву в регістрі D. Тоді получим:

??? A D
? ??? ??? A[J] ???
???V??? ??RG? ??RG?0???>? f ?
? J: =0? ?? ?? ?? ?.?? ?
?? ?? ?? ??->?.?? ? B
? D: =A? ?? ???> ?? ?.?? ???>
??? ?? ?? ??? ?? ?
???? ?? ?? ?? ?K?? ?
? ???V??V??? ?? ?? x ??> ?Dn ?.?? ?
? …? ?? ?? ?? ?.? ??>? ?
?? ? ?? ?? P. S W? ?.?? ?
?? B= f (…, D[0])? ??? ?v?v??? ???
?? ?
?? (D, x): =(x, D) ?
?? ?
?? J: =J+1 ?
? ???
? ?V?
?
???>
__/

Проміжний регістр A запроваджено для спільності, якщо потребуется
зберегти слово, А (найчастіше і не нужен).
Інший приклад: фрагмент алгоритму, який реалізує регуляр-
ную запис окремих біт слова його реалізація мають вид:
??? ???B[0]
? a ???> ??T???>
???V???? W? ??
? J: =0? ???? ?A???
??? ?DC? ???| |
???? ? 0???? | |
? ???V??V??? …? ???B[K]
? …? … ???> ??T???>
?? ? … W? ??
?? a=f (…)? J ??>?? ?A???
?? ?? K???
?? B[J]: =a? ?. ?
?? ? ?. ?
?? J: =J+1? ?. ?
? ??? ???
? ?V?
?
???>
__/

Слово У не можна реалізовувати вигляді регістру, а в виде
окремих триггеров.
Можна формувати слово з допомогою операції сдви-
га, при обов’язковій умові D[K. 0], тоді алгоритм та її ре-
ализация мають вид:

— 13 —

???
? D B
???V??? ??? ???
? J: =0? ? ?RG? ??RG?
???? ?-> ?? ?? ??
???? a? ? ???> ?? ??
? ???V??V??? ??> ?Dk? ?? ?? ??
? …? P. S?? ?? W? ??
?? ? ?v??? ?v???
?? a=f (…) ?
?? ?
?? (D, x): =(a, D) ?
?? ?
?? J: =J+1 ?
? ???
? ?V?
?
???> ?B:=D?>
__/ ???

І тут, як і, як і попереднього, найчастіше не ну-
дружин проміжний регістр (В).

_УНІВЕРСАЛЬНИЙ ОА
Використання під час проектування універсальних ОА з за-
раніше фіксованою і мінімізовану структурою оправдано
тим, такі універсальні ОА виготовляються промышлен-
ностью як БІС великим накладом тому вони сравнительно
дешеві. Такі універсальні ОА входить у мікропроцесорні на-
бори 582, 583, 584, 588, 589, 1800, 1804 тощо., які на-
зываются микропрограммируемыми, секционными, разрядно-модуль-
ными.
У основі перелічених універсальних ОА лежить следующая
структура:
???
?? ?
?? SYN? ACC ?
? ???? ?/??? ??? ?
?? ? RGF ??? C?? RG?? ALU? ?
?? ? ??? ?? ??? ? ?
?? ? ?? ???> ?? ???>?? ?
?? ? ?? ?? ??? ???> DO
???> ?D? ?? ???? ?
?? ?? T? ?
?? ?? ???? ???> P
?? ?? ??RG?? ?
?? ???> ?? ???>? ?
?? ?? ?? ??? ?
З W? А? ?? З? ?? ??>? ?
?o?A?A??? ???? ???A???
SYN?? ? SYN?? ?
?? ? ?
yW YA DI??? YF

ALU — арифметико-логическое пристрій — комбинационная
схема з гаком, але універсальним набором арифметичних и
логічних операций.
RGF — регистровый файл — адресуемая пам’ять RAM зі стати-
ческой синхронізацією при записи.
RG «T «- регистр-фиксатор зі статичної синхронизацией.
RG «АCC «- регистр-аккумулятор з динамічної синхрониза-
цией.

DI, DO — вхідні і вихідна інформаційні шины.

— 14 —
Р — предикатні сигнали (флажки).
YF — сигнали управління вибором функции.
YA — адресу читання і/або записи RGF.
yW — дозвіл запис у RGF.
Пам’ять порівняно великого об'єму, якою є RGF,
дешевше реалізувати зі статичної синхронізацією. Для то-
го, чтобы така пам’ять могла працювати у замкнутому информацион-
ном кільці і навіть не виникали б гонки, додається еше
один проміжний регістр RG «T «зі статичної синхрониза-
цией. Якщо передній фронт є робочою для регістрів уп-
равляющего автомата і RG «ACC », то, на першої фазі синхрониза-
ции при SYN=1 інформація читається з RGF; у своїй RG «T «
прозорий. Під час наступної фазі синхронізації при SYN=0 информа-
ция фіксується в RG «T », тобто. він закритий для записи, а запись
(якщо вона дозволена) виробляється у RGF. Фіксується информа-
ция в RGF і RG «ACC «з початком наступного такту, тобто. на пе-
реднем фронті сигнала.

_ВЗАЄМОДІЯ ОА і УА
Щоб не допустити гонок при взаємодії ОА і УА будем
проектувати УА як автомат Мура. Схема їх взаимодействия
то, можливо представленій у виде:
???
??? ??? ??? ?
?? CS? ??RG? ?CS ?
? ?
??? b? ? ?? ??? з ?
? ???? ???A? ??? ?
? ???? ??? ?
? ?CS ?
??? a ?
ОА ?? ???? ? ?
----??----------------------------?-?-?--
УА?? РА??? ??? ???? ??
???>? CS? ??RG?? CS ??? ??
???>? ???> ?? ???>? ??? ??Y
РМ? ? ?? ??? ???
?>? p? ?? ??? y ??? ?
? ??? ??? ??? ?
???

Зазначимо, що РА (t)=f (Y (t)) залежить без зсуву від сигналов
управления,
PB (t+1)=F (Y (t)) залежить зі зсувом від сигналов
управления,
де РА і РМ — предикатні перемнные.
Тривалість такту роботи схеми визначається наибо-
лее довгими ланцюгами між регістрами. Для даної схеми, кото-
рую називатимемо послідовної схемою взаимодействия,
задамося (так найчастіше буває), що така критической
ланцюгом є ланцюг (CSy, CSa, CSp, RG). Тому длительность
такту определяется:
Т > ty + ta + tp + trg,
де tj- час встановлення відповідного компонента цепи.
Щоб скоротити довжину цьому ланцюзі, застосовують інший вари-
анте взаємодії автоматів — конвейерный:

— 15 —

???
??? ??? ??? ?
?? CS? ??RG? ?CS ?
? ?
??? b? ? ?? ??? з ?
? FF ???? ???A? ??? ?
? ??? ???? ??? ?
???RG?
?? ?? ??? a ?
?? ???A? ???? ? ?
ОА ?? ???? ? ?
---??----------------------------------?-?-?-?--
УА ?? MK? ?? ?
?? PA ??? ???? ? ??
???>? CS? CS? ??RG???? ? ??
? РМ? ?? ?? ???? ??Y
???>?? ???> ?? ??? ??
?? ? ?? ???
?>? p? y? ?? ??? ?
? ??? ??? ?
???

У цьому варіанті взаємодії такий довгому ланцюгу, как
у випадку, не возникает. Эта ланцюг розділена регис-
трами RG «FF «(регістр прапорців) і RG «MK «(регістр микрокоман-
ды) на дві ланцюга. Тривалість такту дедалі менше и
яку можна визначити наступним образом:
T > max (ta,(tp + ty))+ trg,
При конвеєрному варіанті взаимодействия
PA (t+1)=f (Y (t)), тобто. й інші значення стали зависить со
зрушенням від сигналів управління. Тоді фрагмент микропрограммы
mS{… ;pA=f (…)}
< GO (pA; mi, mj)>>,
що здійснюється у послідовній схемою за такт, в кон-
вейерном варіанті за такт виконано не може і дол-
дружин бути модифікований наступним образом:
mS{…, pA=f (…)}
mS «{немає операции}
< GO (pA; mi, mj)>>
Отже, час виконання цієї фрагмента як не
зменшилося, і навіть зросла попри зменшення продол-
жительности кожного з тактів. Зате в усіх інших случа-
ях (при безумовних переходах, при переходах за значенням РВ)
час виконання мікропрограми уменьшается.

_ПОЧАТКОВА ІНІЦІАЛІЗАЦІЯ СИНХРОННОЇ СХЕМЫ
Нехай пристрій, крім сигналу синхронізації SYN, имеет
іще одна сигнал М, що означає початок і поклала край синхронної ра-
боти устрою. При Н=0 — неробочий стан — можна выпол-
нять початкову установку значень пам’яті устрою. Измене-
ние значення М з 0 на 1 відбувається у випадковий момент времени
(асинхронно), та заодно початковий такт роботи устройства
має бути цілковитим. «Затягування «асинхронного сигналу М в
синхронний режим твориться з допомогою найпростішого синхронного
автомата з диаграммой:
??? ???
V 0H/CONST? V 1H/SYN?
??? ???
>? 0 ???>? 1 ???
??? 1H/CONST ??? 0H/X ?
л ?
???
Це автомата найпростішої є функція переходів, так
як діаграма автомата збігаються з діаграмою переходов

— 16 —
D-триггера.
Схема автомата разом із ланцюгами умовної синхронизации
виглядає так (для синхронізації по фронтам):
а)-по переднього фронту, б) — по задньому фронту:
??? ???
SYN ??? 1??? CC SYN ??? & ??? CC
? ??? ???? ? ??? ??? ?
??/C?T?? ??? ??C?T?? ???
?? ?? ?? ???
???D?? ? ???D? ?
? ??? o???? ??? o?
??oR?? ??oR? ?
H? ???вуст. поч. ДТ. H? ???вуст. поч. зн.
??? ???

Така в ланцюгах умовної синхронізації, як вже объяс-
нялось вище, залежить від того, перший перепад сигналу СС
ні бути рабочим.

ПоказатьСвернуть
Заполнить форму текущей работой