Розробка алгоритму операційного автомату, синтез керуючого автомату з жорсткою логікою типу Мілі (стр. 2 из 5)
Апаратні методи, прискорення множення вимагають для свого здійснення введення додаткової апаратури в основні арифметичні кола пристрою для множення.
Розрізняють апаратні методи першого порядку і другого порядку. Для апаратних методів першого порядку характерна лінійна залежність кількості додаткової апаратури від кількості розрядів у співмножниках п. Тоді як реалізація методів другого порядку вимагає введення додаткової апаратури, кількість якої пропорційна
.До логічних методiв прискорення операції множення належать: метод множення з пропусканням додавань у тих випадках, коли чергова цифра множнику є нуль; метод множення з перетворенням цифр множнику шляхом групування розрядiв i метод множення з послідовним перетворенням цифр множника.
В основi двох останніх логічних методiв лежить перехід до надлишкової двійкової системи числення з алфавітом {1, 0,
}, який дозволяє зменшити кількість одиниць у коді множника, але при цьому в процесi множення будуть виконуватись операції додавання та віднімання.Метод множення з пропусканням додавань є найпростішим з логічних методів прискорення множення. Схему керування взагалі простіше побудувати так, щоб за тактом зсуву щораз приділявся час на додавання, але додавання виконувалося б у залежності від цифри множника. Невелике ускладнення схеми керування, що дозволяє відводити час на додавання тільки тоді, коли воно дійсно необхідно, скорочує число тактів додавання в середньому вдвічі.
Цей метод прискорення рівною мірою підходить для тих випадків, коли множення починається зі старших розрядів множника, і для випадків, коли множення починається з молодших розрядів.
1.2 Розробка операційного автомату
1.2.1 Формалізований опис операційного автомату
В функц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в Y=[y(1),...,y(m)], з кожним iз них ототожнюється визначена мiкрооперацiя. Значення логiчних умов, якi обчислюються в операцiйному автоматi, вiдображаються множиною освiдомлюючих сигналiв X=[x(1),...,x(l)], кожний з яких ототожнюється з визначеною логiчною умовою. Керуючий автомат КА генерує послiдовнiсть керуючих сигналiв, визначену мiкропрограмою, яка вiдповiдає значенням логiчних умов. Іншими словами, керуючий автомат задає порядок виконання дiй в операцiйному автоматi, що зрозумiло з алгоритму виконання операцiй. Найменування операцiї, яку необхiдно виконати в пристрої, визначається кодом g операцiї. По вiдношенню до керуючого автомату сигнали g(1),...,g(h), за допомогою яких кодується найменування операцiї, i освiдомлюючi сигнали x(1),...,x(l), що формуються в операцiйному автоматi, грають однакову роль: вони впливають на порядок утворення робочих сигналiвY. Тому сигнали g(1),...,g(h) i x(1),...,x(l) в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йного автомату визначається сл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.
