Каталог Рефератов - Розробка алгоритму операційного автомату, синтез керуючого автомату з жорсткою логікою типу Міл

	Информационно-образоательный портал
	Рефераты, курсовые, дипломы, научные работы,



МЕНЮ\|

поиск

Розробка алгоритму операційного автомату, синтез керуючого автомату з жорсткою логікою типу Міл

аким чином, будь-який операцiйний пристрiй - процессор, канал вводу-виводу, пристрiй управлiння зовнiшнiм пристроєм - є композицiєю операцiйного та керуючого автоматiв. Операцiйний автомат, реалiзовуючи дiї над словами iнформацiї, є виконавчою частиною пристрою, роботою якого управляє керуючий автомат, генеруючий необхiднi послiдовностi управляючих сигналiв.

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

Функцiя операцiйного автомату визначається слiдуючою єднiстю вiдомостей:

Множиною вхiдних слiв d={d(1),...,d(H)}, що вводиться в автомат в якостi операндiв.

Множиною вихiдних слiв R={r(1),...,r(Q)}, що представляє результати операцiй.

Множиною мiкрооперацiй Y={y(m)}, m=1,...,M, реалiзуючих перетворення S={f(m)}(S) над словами iнформацiї, де f(m) - шукана функцiя.

Таким чином, функцiя операцiйного автомату задана, якщо визначенi множини D,R,S,Y,X. Час не є аргументом функцiї операцiйного автомату. Функцiя встановлює список дiй - мiкрооперацiй i логiчних умов,- якi може виконувати автомат, але нiяк не визначає порядок слiдування цих дiй у часi. Iнакше кажучи, функцiя операцiйного автомату характеризує засоби, якi можуть бути використанi для обчислень, але не сам обчислювальний процес. Порядок виконання дiй у часi визначається у формi функцiй управляючого автомату.

1.2.2 Структурна схема операційного автомату

В загальному випадку операційний пристрій будується по схемі.

Операційний автомат ОА розділяється на три частини: пам'ять S; комбінаційну схему Ф, яка реалізує мікрооперації; комбінаційну схему ?, яка обчислює значення логічних умов. Пам'ять S забезпечує збереження слів s1,…sN, які представляють значення операндів D, проміжкові значення і кінцеві результати R. Для виконання мікрооперацій Y={ ym} служить комбінаційна схема Ф. Керуючі сигнали Y, що формуються управляючим автоматом УА, ініціюють виконання необхідних мікрооперацій. Так, якщо надходять сигнали ym1 і ym2, то схема Ф виконує дві мікрооперації що зводиться до обчислення значень і присвоєння їх словам . Для обчислення значень логічних умов служить комбінаційна схема ?, що реалізує систему булевих функцій , значення яких представляються інформаційними сигналами X={xl}.

1.3 Розробка машинного алгоритму

1.3.1 Побудова граф-схеми алгоритму
Побудова словесного алгоритму:
1) У регістр А записується прямий код множеного А, який передається із вхідної шини:
РгА:=Швх1

2) У регістр В записується прямий код множника В, який передається із вхідної шини:

РгВ:=Швх2

3) Встановлюємо в нуль накопичувальний суматор:

НСМ:=0

4) У лічильник записуємо кількість разів повторення циклу:

ЛІЧ:=29

5) Перевіряємо чи рівні знакові розряди співмножників:

РгА[31]=РгВ[31] ?

Якщо так,то переходимо до пункту 7.

Якщо ні, то переходимо до пункту 6.

6) Знаковий розряд НСМ виставляється в 1:

НСМ[63]:=1

7) Аналізуємо старший розряд регістра В:

РгВ[30]=1?

Якщо так, тоді переходимо до пункту 8.

Якщо ні, тоді переходимо до пункту 9.

8) Додаємо до вмісту накопичувального суматора значення коду регістра А:

НСМ:=НСМ+РгА

9) Відновлюємо попередній вміст регістра В, циклічно зсуваючи його вліво на один розряд:

L1.РгB[0:30]

10) Вміст накопичувального суматора циклічно зсуваємо на один розряд вліво:

L1.НСМ[0:62]

11) Декрементуємо значення лічильника:

ЛІЧ:=ЛІЧ-1

12) Молодший розряд накопичувального суматора приймає значення нуль:

НСМ[0]=0

13) Перевіряємо, чи лічильник рівний нулеві:

ЛІЧ=0?

Якщо так, то переходимо до пункту 14

Якщо ні, то переходимо до пункту 7.

14) Значення накопичувального суматора циклічно зсуваємо на один розряд вправо:

R1.НСМ[0:62]

15) Закінчення операції множення. Значення результату, яке записане у накопичувальному суматорі, передається на шину даних:

Швих:=НСМ[0:63]

Для наочного зображення алгоритму виконання операцій використовують граф-схеми алгоритмів.

Граф-схема алгоритма (ГСА) - орієнтований зв'язаний граф, який містить одну початкову вершину (Початок), одну кінцеву вершину (Кінець) і довільну кількість умовних і операторних вершин. Вершина "Початок" входів не має.

Кінцева, операторна і умовна вершини мають по одному входу, початкова вершина входів не має. Вершина "Початок" і будь-яка операторна мають по одному виходу, умовна вершина має два виходи, позначених символами «1» та «0». Вершина "Кінець" виходів не має.

ГСА має задовольняти наступні умови:

входи і виходи вершин з'єднуються один з одним за допомогою дуг, направлених завжди від виходу до входу;

кожен вихід з'єднано лише з одним входом;

кожен вихід з'єднується лише з одним входом;

будь-який вхід з'єднується принаймні з одним виходом;

будь-яка вершина ГСА лежить принаймні на одному шляху від початкової вершини до кінцевої;

один із виходів умовної вершини може з'єднуватись з її входом, що є недопустимим для операторної вершини. Такі умовні вершини іноді називаються зворотними;

в кожній умовній вершині записується логічна умова із множини логічних умов;

в кожній операторній вершині записується оператор, який являє собою вихідний сигнал або сукупність вихідних сигналів управляючого автомата.

При проектуванні різноманітних пристроїв ЕОМ зазвичай використовуються змістовні граф-схеми алгоритмів, які описують не лише формальні елементи, а також логічні умови і мікрооперації у змістовних термінах.

Структурна схема операційного автомата - на рисунку 1.

Рисунок 1 - Структурна схема операційного автомата

1.3.2 Приклад реалізації алгоритму
Приклад: Перемножити на суматорі прямого коду починаючи з старших розрядів множника А=57, В=-923 з використанням описаного у пункті 1.3.1 алгоритму.
Розв'язання.

Спочатку запишемо машинні зображення чисел А та В в прямих кодах з заданою розрядністю:

А = 0,[0] 30...[0] 6111001; В = 1,[0] 30…[0] 111110011011

Послідовність дій, що виконуються над числами, наведена у таблиці 1.

Відповідь: 1,[0] 62…[0] 1701100110011011000.

Таблиця 1 - Приклад реалізації алгоритму множення, починаючи зі старших розрядів множника

Суматор НСМ	Регістр РгА	Регістр РгВ	Примітки
0,[0]62…[0]1700000000000000000	0,[0]30...[0]6111001	1,[0]30…[0]111110011011	НСМ:=0; РгА:=Швх1; РгВ:=Швх2; ЛІЧ:=29;
1,[0]62…[0]18000000000000000000	0,[0]30...[0]6111001	1,[0]30…[0]121110011011_	НСМ[63]:=1; РгВ[30]=0; L1.РгВ[0:30]; ЛІЧ:=28; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1700000000000000000	0,[0]30...[0]6111001	1,01110011011[ _ ] 19…[ _ ] 0	РгВ[30]=0; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=10;
1,[0]62…[0]1700000000000000000 1,[0]62…[0]1700000000000111001 1,[0]62…[0]1700000000001110010	0,[0]30...[0]6111001	1,1110011011[_] 20…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=9;
1,[0]62…[0]1700000000001110010 1,[0]62…[0]1700000000010101011 1,[0]62…[0]1700000000101010110	0,[0]30...[0]6111001	1,110011011[_] 21…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=8;
1,[0]62…[0]1700000000101010110 1,[0]62…[0]1700000000110001111 1,[0]62…[0]1700000001100011110	0,[0]30...[0]6111001	1,10011011[_] 22…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=7;
1,[0]62…[0]1700000001100011110 1,[0]62…[0]1700000011000111100	0,[0]30...[0]6111001	1,0011011[_] 23…[_] 0	РгВ[30]=0; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=6;
1,[0]62…[0]1700000011000111100 1,[0]62…[0]1700000110001111000	0,[0]30...[0]6111001	1,011011[_] 24…[_] 0	РгВ[30]=0; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=5;
1,[0]62…[0]1700000110001111000 1,[0]62…[0]1700000110010110001 1,[0]62…[0]1700001100101100010	0,[0]30...[0]6111001	1,11011[_] 25…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; ЛІЧ:=4; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1700001100101100010 1,[0]62…[0]1700001100110011011 1,[0]62…[0]1700011001100110110	0,[0]30...[0]6111001	1,1011[_] 26…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; ЛІЧ:=3; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1700011001100110110 1,[0]62…[0]1700110011001101100	0,[0]30...[0]6111001	1,011[_] 27…[_] 0	РгВ[30]=0; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=2;
1,[0]62…[0]1700110011001101100 1,[0]62…[0]1700110011010100101 1,[0]62…[0]1701100110011011000	0,[0]30...[0]6111001	1,11[_] 28…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; ЛІЧ:=1; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1701100110011011000 1,[0]62…[0]1701100110110000011 1,[0]62…[0]1711001100110110000	0,[0]30...[0]6111001	1,1[_] 29…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; ЛІЧ:=0; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1711001100110110000 1,[0]62…[0]1701100110011011000	0,[0]30...[0]6111001	1,1[_] 29…[_] 0	R1.НСМ[0:62]; Швих:=НСМ[0:63]

2. СИНТЕЗ КЕРУЮЧОГО АВТОМАТУ

2.1 Основи теорії керуючих автоматів

Керуючий автомат (КА) генерує послідовність керуючих сигналів, яка передбачена мікропрограмою і відповідає значенням логічних умов. Інакше кажучи, керуючий автомат задає порядок виконання дій в операційному автоматі, який виходить з алгоритму виконання операцій. Найменування операції, яку необхідно виконувати у пристрої, визначається кодом операції. По відношенню до керуючого автомату сигнали коду операції, за допомогою яких кодується найменування операції, і повідомлювальні сигнали х1,...,хi, які формуються в операційному автоматі, грають однакову роль: вони впливають на порядок генерування керуючих сигналів y. Тому сигнали коду операції і умовні сигнали відносяться до одного класу - до класу повідомлювальних сигналів, які поступають на вхід керуючого автомату.

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

Існують два основні типи керуючих автоматів?

1. Керуючий автомат з жорсткою? чи схемною? логікою. Для кожної операції будується набір комбінаційних схем? які в потрібних тактах збуджують відповідні керуючі сигнали. Іншими словами? будується скінчений автомат? в якому необхідна множина станів представляється станами k запам'ятовуючих елементів

q = {q1? q2, …, qk}

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

Послідовність мікрокоманд? що виконують одну машинну команду чи окрему процедуру? створює мікропрограму. Звичайно мікропрограми зберігаються в спеціальній пам'яті мікропрограм (керуючій пам'яті).

В керуючих автоматах з збереженоюю в пам'яті програмою мікропрограми використовуються в явній формі? вони програмуються в кодах мікрокоманд і в такому вигляді заносяться в пам'ять. Тому такий метод управління цифровим пристроєм називається мікропрограмуванням? а керуючі блоки? що використовують цей метод - мікропрограмними керуючими пристроями.

В залежності від прийнятого способу кодування мікрооперацій розрізняють три варіанти організації мікропрограмного керування горизонтальне? вертикальне та комбіноване мікропрограмування. При горизонтальному мікропрограмуванні для кожної мікрооперації виділяється один розряд у мікрокоманді. При такому кодуванні всі операції? що виконуються одночасно? визначаються одиницями у відповідних розрядах однієї мікрокоманди. Код операції задає адресу першої мікрокоманди в мікропрограмі. Адреси наступних мікрокоманд визначаються за принципом примусової адресації? згідно цього мікрокоманда складається з двох частин-мікроопераційної та адресної. Основною перевагою горизонтального мікропрограмування є висока швидкодія як за рахунок простоти та можливості одночасної генерації довільного числа сигналів мікрооперацій? так і за рахунок швидкого формування адреси наступної мікрокоманди. Однак при горизонтальному мікропрограмуванні довжина поля мікрооперації повинна бути не менша за максимальну кількість несумісних мікрооперацій? тобто вимагаються довгі формати мікрокоманд та комірки запам'ятовуючого пристрою? що призводить до значних витрат обладнання. Крім того? лише невелике число розрядів в полі мікрооперації буде містити одиниці? тобто запам'ятовуючий пристрій буде використовуватись неефективно.

Страницы: 1, 2, 3

© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.