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

/>Зміст
ВСТУП
1. РОЗРОБКА АЛГОРИТМУ ТА ОПЕРАЦІЙНОГОАВТОМАТУ
1.1 Опис операції множення
1.1.1 Основні методи множення
1.1.2 Множення чисел зфіксованою комою
1.1.3 Прискорені методивиконання операції множення
1.2 Розробка операційногоавтомату
1.2.1 Формалізований описопераційного автомату
1.2.2 Структурна схемаопераційного автомату
1.3 Розробка машинногоалгоритму
1.3.1 Побудова граф-схемиалгоритму
1.3.2 Приклад реалізаціїалгоритму
2. СИНТЕЗ КЕРУЮЧОГО АВТОМАТУ
2.1 Основи теорії керуючихавтоматів
2.2 Опис керуючого автоматуМілі
2.3 Кодування граф-схемиавтомату
2.4 Побудова таблиціпереходів
2.5 Синтез керуючого автомату
3. МЕТОДИКА КОНТРОЛЮ
3.1 Теоретичні відомості
3.2 Приклад контролювиконання операції множення за допомогою 11N-коду
ВИСНОВКИ
ПЕРЕЛІК ПОСИЛАНЬ
/>ВСТУП
 
В основупроектування операційних пристроїв різного призначення покладено принципфункціонального мікропрограмування і концепцію операційних і керуючихавтоматів. При цьому мікропрограмування — це спосіб опису функцій операційнихпристроїв безвідносно до технічних засобів, які використовуються для їхреалізації. Таке тлумачення мікропрограмування дозволяє формалізувати синтезструктур будь-яких операційних пристроїв незалежно від способу керуванняроботою пристрою. Необхідно відзначити, що принципи побудови і методипроектування операційних і керуючих автоматів є тою основою, на якій базуєтьсятеорія і практика проектування більшої частини пристроїв ЕОМ.
Складність івідповідальність задач, що вирішуються сучасними ЕОМ та системами, потребуютьвід них високої надійності та продуктивності. Тому, однією з основних проблем,які стоять перед розробниками сучасної обчислювальної техніки, є підвищенняпродуктивності, відказостійкості та життєздатності.
В наш час основним напрямкомвирішення цих проблем є створення обчислювальних машин, які побудовані звеликої кількості однорідних модулів, що утворюють єдину систему шляхомвстановлення логічних зв`язків між ними. В цьому суть концепціїмультипроцесорних ЕОМ, частинними випадками яких є матричні, конвеєрні, зпрограмованою архітектурою і т.д. При цьому висовуються вимоги простоти контрольногообладнання і високої достовірності обробки інформації.
В даній курсовійроботі здійснюється розробка алгоритму операційного автомату виконання операціїмноження чисел в прямому коді, синтез керуючого автомату з жорсткою логікоютипу Мілі. А також приведено приклад контролю виконання операції множення задопомогою 11N контролю.
/>1.РОЗРОБКА АЛГОРИТМУ ТА ОПЕРАЦІЙНОГО АВТОМАТУ
 1.1 Опис операціїмноження
Множення можепроводитись в прямому, оберненому та доповняльному кодах. Знак результатуоперації множення можна визначати окремо. Для цього використовується операціяXOR над знаковими розрядами співмножників відповідно.
При виконаннімноження двох операндів однакової розрядності розрядність результатузбільшується вдвічі, порівняно з розрядністю множників. При виконанні множенняоперандів, представлених в прямому коді, їх модулі множаться як цілі двійковічисла без знаків, або як дробові числа без знаків, оскільки процедура множенняв обох випадках та ж сама. При виконанні множення операндів, представлених воберненому коді, всі розряди від'ємних чисел потрібно інвертувати, а даліпроводити множення так само, як над даними, представленими в прямому коді.Разом з тим, потрібно зауважити, що існують методи прямого множення операндів,представлених в обернених кодах.1.1.1 Основні методи множення
Методи множеннячисел у двійковій системі числення можна класифікувати таким чином:
За формою поданнячисел
методи множеннячисел з фіксованою комою;
методи множеннячисел з плаваючою комою.
За швидкодією
методи простогомноження
методиприскореного множення
За видомвикористаного суматора:
методи множенняна суматорі прямого коду;
методи множенняна суматорі доповняльного коду;
методи множенняна суматорі оберненого коду (рідко використовується ).
За аналізомрозрядів множника:
множення змолодших розрядів;
множення зістарших розрядів;
Усі перерахованіметоди можуть накладатися один на одного, що дає змогу вибрати потрібний методмноження двійкових чисел з урахуванням вимог до швидкості виконання операції тадо використання апаратних затрат на реалізацію алгоритму.
Виходячи звищевикладеного можна виділити чотири варіанти схем машинного множення:
Метод 1.Припустимо В-множене (В>0), A-множник (А>0) С-добуток. Тодіу випадку зображення чисел у формі з фіксованою комою отримуємо
А = а1а2…аn ;
B = b1b2…bn = b12-1+ b22-2 + … + bn2-n;
Звідси:
С = АВ =(0а1а2…аn)(b12-1 + … + bn2-n) = = (2-10,a1a2…an)b1(1.1) + (2-10,a1a2…an)b2 + … + (2-n0,a1a2…an)bn.
Множник 2-nозначає зсув на n розрядів вправо числа яке заключене в дужкитобто в даному випадку зсувається вправо множене і множення починається зстарших розрядів.
Структурна схемапристрою що реалізує цей метод наведена на рис. 1а.
Метод 2. МножникB = 0b1b2…bn перетворюється по схемі Горнера
B = (…((bn2-1+ bn-1)2-1 + bn-2)2-1 + … + b2)2-1 + b1)2-1
Тоді:
C = AB =(…((bn0,a1a2…an)2-1 + bn-10,a1a2…an)2-1 … (1.2)…+b10,a1a2…an)2-1

Тут множенняпочинається з молодших розрядів та зсувається вправо суми часткових добутків.Структурна схема пристрою що реалізує цей метод наведена нарис. 1б.
Метод 3. Множникзаписується таким чином
B = 2-n(bn+ bn-121 + bn-222 + … +b12n-1).
С = AB =2-n[bn0,a1a2…an + bn-1(210,a1a2…an) +  (1.3)+bn(220,a1a2…an) + … + b1(2n-10,a1a2…an)] .
Це означаєщо множення починається з молодших розрядів і множене зсувається вліво на одинрозряд в кожному такті.
Структурна схемапристрою що реалізує цей метод наведена на рис. 1в.
Метод 4. Якщомножник записати по схемі Горнера
B = 2-n(…((b121+ b2)21 + … + bn-1)21 + bn
C = AB =2-n(…((b10,a1a2…an)21 + b20,a1a2…an)21+ … + (1.4)+ bn-10,a1a2…an)21 + bn0,a1a2…an).
У цьому випадкумноження починається з старшого розряду і в кожному такті зсувається вліво сумачасткових добутків.
Структурна схемапристрою що реалізує цей метод наведена на рис. 1
Другий варіантмає найменші апаратурні витрати перший та третій – найменший часмноження.
Таким чиномдля реалізації звичайної операції множення необхідно мати суматоррегістри для зберігання множеного та схему аналізу розрядів множника. Суматорта регістри повинні мати ланцюги зсуву вмісту в ту чи іншу сторону увідповідності з прийнятим методом множення.
При множеннічисел на суматорі прямого коду знак добутку визначається окремо від цифровоїчастини як сума по модулю 2 знаків обох співмножників. У оберненому тадоповняльному кодах знак добутку визначається автоматично за рахунок внесенняпоправок в звичайний добуток операндів.
Якщо множниквід’ємний то добуток чисел на суматорі оберненого коду отримуютьдодаванням поправок [A]об та [A]об2-n до добутку обернених кодівспівмножників.[А.Я. Савельєв «Прикладная теория цифровых автоматов» М.: Высш.шк.1987]
При множеннічисел на суматорах оберненого та доповняльного кодів одночасно отримуютьзнакову та цифрову частини.1.1.2 Множення чисел з фіксованоюкомою
В ЕОМ операціямноження чисел з фіксованою комою за допомогою відповідних алгоритмів зводитьсядо операції додавання і зсуву.
Множення двох (n- 1) розрядних чисел може мати 2(n — 1) значущих розрядів.
Тому при операціїмноження цілих чисел необхідно побачити можливість формування в АЛП добутку,котрий має двохкратну в порівнянні із співмножниками довжину. В ЕОМ, в якихчисла з фіксованою комою є дробами, молодші (n — 1) розрядів множення частовідкидаються (при відкиданні може виконуватись операція округлення добутку).Для виконання множення АЛП повинен мати регістри множеного, множника та схемиформування суми часткових добутків — суматор часткових добутків, в якому шляхомвідповідної організації передач виконується послідовне додавання частковихдобутків.
Операціямноження складається з (n — 1) циклів. В кожному циклі аналізується слідуючацифра множника, якщо це 1, то до суми часткових добутків додається множене, віншому випадку додавання не виконується. Цикл закінчується з зсувом множеноговідносно суми часткових добутків або з зсувом суми часткових добутків відноснонерухомого множеного.
1.1.3 Прискорені методи виконанняоперації множення
Прискоренняоперації множення дозволяє істотно підвищити продуктивність ЦОМ, оскількиприблизно 70% свого часу вони витрачають на виконання цієї операції. Аналізуючи(3.2) — (3.5), можна намітити такі шляхи скорочення часу множення: зменшеннячасу додавання і зсуву кодів; зменшення кількості додавань і кількості зсувівкодів.
Оскільки простіметоди множення передбачають виконання в кожному циклі зсув кодів тільки наодин розряд, то зменшити час зсуву неможливо тому, що кола для зсувуреалізують, як правило, з найменшою затримкою сигналів.
Зменшення часудодавання двох кодів досягається за рахунок ускладнення кіл формуваннярозрядних сум і перенесень у суматорі. Але це ні яким чином не впливає наорганізацію процесу множення. Тому основні підходи щодо прискорення операціїмноження базуються на зменшенні кількості додавань і кількості зсувів кодів.
Відомі на цей часметоди прискорення множення розподілені на дві великі групи: логічні йапаратні.
Логічнимиметодами прискорення множення називають такі методи, реалізація яких не вимагаєзмін основної структури арифметичних кіл пристрою для множення (див. рис. 3.1 — 3.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.
/>
Рисунок 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. Керуючийавтомат з збереженою в пам’яті логікою (програмованою логікою). Кожній операціїщо виконується в операційному пристрої ставиться у відповідністьсукупність збережених в пам’яті слів-мікрокоманд кожна з яких міститьінформацію про мікрооперації що підлягають виконанню на протязі одногомашинного такту та вказівку (яка в загальному випадку залежить відзначень вхідних сигналів) яке повинно бути вибране з пам’яті наступнеслово (наступна мікрокоманда). Таким чином в цьому випадку функціїпереходів та виходів А та В керуючого автомату реалізуються збереженою впам’яті сукупністю мікрокоманд.
Послідовністьмікрокоманд що виконують одну машинну команду чи окрему процедурустворює мікропрограму. Звичайно мікропрограми зберігаються в спеціальнійпам’яті мікропрограм (керуючій пам’яті).
В керуючихавтоматах з збереженоюю в пам’яті програмою мікропрограми використовуються вявній формі вони програмуються в кодах мікрокоманд і в такому виглядізаносяться в пам’ять. Тому такий метод управління цифровим пристроємназивається мікропрограмуванням а керуючі блоки щовикористовують цей метод — мікропрограмними керуючими пристроями.
В залежності відприйнятого способу кодування мікрооперацій розрізняють три варіанти організаціїмікропрограмного керування горизонтальне вертикальне та комбінованемікропрограмування. При горизонтальному мікропрограмуванні для кожноїмікрооперації виділяється один розряд у мікрокоманді. При такому кодуванні всіоперації що виконуються одночасно визначаються одиницями увідповідних розрядах однієї мікрокоманди. Код операції задає адресу першоїмікрокоманди в мікропрограмі. Адреси наступних мікрокоманд визначаються запринципом примусової адресації згідно цього мікрокоманда складається здвох частин-мікроопераційної та адресної. Основною перевагою горизонтальногомікропрограмування є висока швидкодія як за рахунок простоти та можливостіодночасної генерації довільного числа сигналів мікрооперацій так і зарахунок швидкого формування адреси наступної мікрокоманди. Однак пригоризонтальному мікропрограмуванні довжина поля мікрооперації повинна бути неменша за максимальну кількість несумісних мікрооперацій тобтовимагаються довгі формати мікрокоманд та комірки запам’ятовуючого пристроющо призводить до значних витрат обладнання. Крім того лише невеликечисло розрядів в полі мікрооперації буде містити одиниці тобтозапам’ятовуючий пристрій буде використовуватись неефективно.
Скоротити довжинумікрокоманд дозволяє застосування вертикального мікропрограмування приякому кожна мікрооперація кодується ]log2 n[ — розрядним кодом де n –загальна кількість мікрооперацій. Таке кодування накладає обмеження на методивиконання операцій а саме не повинно бути операцій щопотребують одночасного виконання ряда мікрооперацій. В тих випадкахколи це обмеження виконати неможливо треба використовувати складнімікрооперації що складаються з сукупності простих.2.2 Опис керуючогоавтомату Мілі
За способомформування функції виходів виділяють три типи абстрактних автоматів: автоматМілі, автомат Мура та С-автомат.
В абстрактномуавтоматі Мілі значення функції виходу в момент t залежить не лише від стануавтомата, але і від набору значень вхідних сигналів.
Довільнийабстрактний автомат Мілі має один вхідний і один вихідний канали.
Автомат Міліхарактеризується системою рівнянь:
/>(2.1)
де /> – множина вхідних сигналівавтомата (вхідний алфавіт);
/>– множина станів автомата(алфавіт станів);
/>– множина вихідних сигналів(вихідний алфавіт).
λ – функція виходівавтомата;
φ – функціяпереходів автомата.
Іншими словами,функція виходів λ задає відображення (X/>S)→Y,тобто ставить у відповідність будь-якій парі елементів декартового добуткумножин (X/>S) елемент множини S.2.3 Кодування граф-схемиавтомату
В автоматі Міліпочаток і кінець мікропрограми представляються початковим станом автомата а0.Кожна дуга, яка виходить із операторної вершини позначається символом аі.Якщо декілька дуг, позначені певними станами ак, входять до одногоблоку графа мікропрограми, то всі вони помічаються однаковим символом стану ак.
Позначенняоперацій та логічних умов наведено у таблиці 3. 2.4 Побудова таблиціпереходів
Умови переходу помікропрограмі від одного стану до іншого задають функцію переходів автомата.
Таблиця переходів(виходів) являє собою таблицю з подвійним входом, рядки якого пронумерованівхідними буквами, а стовпці – станами. На перетині вказується стан, у якийпереходить автомат (в таблиці переходів) або вихідний сигнал, що видається ним(у таблиці виходів).
Іноді призавданні автоматів Мілі використовують одну суміщену таблицю переходів івиходів, в якій на перетині стовпця аm і рядка хjзаписуються у вигляді аs/yg наступний стан і вихіднийсигнал, що видається.
У таблиці 4 длязаданого автомата маємо суміщену таблицю переходів і виходів.

Таблиця 2 –Таблиця переходів і виходівt t+1 Тригери JK2 JK1 JK0
ai
код ai
xi
ai+1
код ai+1
yi J2 K2 J1 K1 J0 K0
a0 000
/>
a1 001 y1,y2,y3,y4 1
/>
a2 010 1
/>
a3 011 1 1
a1 001
/>
a2 010 y5 1 1
/>
a3 011 1
a2 010 ___
a3 011 y6 1
a3 011 ___
a4 100 y7,y8 1 1 1
a4 100
/>
a5 101 y9,y10 1
/>
a2 010 1 1
/>
a3 011 1 1 1
a5 101 ____
a6 110 y11 1 1
a6 110 ____
a0 000 y12 1 1  2.5 Синтез керуючогоавтомату
Керуючі пристроїскладаються із окремих логічних схем елементів, які виробляють керуючі сигналив заданій послідовності. Такий керуючий пристрій можна розглядати як керуючийавтомат типу Мура чи Мілі.
Для автомату Мілівихідний сигнал залежить не лише від внутрішнього стану, а й від зовнішньогостану схеми. Можна побудувати граф переходів автомата Мура, де вершинамиявляються стани автомата, а дугами — умови переходу з одного стану в інший.
В залежності відспособу визначення вихідного сигналу в синхронних автоматах існує два способи:
вихідний сигналy(t) однозначно визначається вхідним сигналом x(t) і станом а(t-1) автомата вслідуючий момент часу;
вихідний сигналy(t) однозначно визначається вхідним сигналом x(t) і станом а в даний моментчасу.
Автомати можназадати також у вигляді графів, таблиць виходів та переходів, суміщеної таблиціпереходів і виходів. Управляючий пристрій складається із окремих логічних схем,що виробляють управляючі сигнали в заданій послідовності. Такий управляючийпристрій можна розглядати як керуючий автомат типу Мура чи Мілі.
Після побудовиавтомата Мілі функціонування керуючого автомата представляють у вигляді таблицьпереходів і виходів. Для цього спочатку виробляють кодування станів автоматадвійковими кодами, визначають тип та кількість тригерів. Потім по таблиціпереходів встановлюють значення сигналів на входах тригерів, при якихвідбуваються переходи; визначають функції збудження тригерів і виконують їхмінімізацію (спрощення). По знайдених виразах будується схема управляючогоавтомата на вибраних елементах.
В нашому випадкубуде використовуватись три логічні умови Х = {х1,x2, х3} і дванадцятьмікрооперацій Y = {y1, …, y10}
Отже, длякодування станів автомата необхідно 3 JK-тригера: JK0, JK1, JK2,. Закодуємостани автомата так, як це показано у таблиці 5.
Для побудовифункцій збудження тригерів і виходів використовується структурна таблицяавтомата (таблиця 5).
На основі таблиці 5 будуєтьсяканонічна система функцій виходів і функції збудження тригерів.
Функції виходів:
/>;
/>;
/>;
/>;
/>;
/>;
/>;
/>;
/>
/>;
/>;
/>.
Функції збудженнятригерів:
/>;
/>;
/>
/>;
/>
/>.
/>3.МЕТОДИКА КОНТРОЛЮ3.1 Теоретичні відомості
Різноманітні задачі можна вирішувати за допомогою методуконтролю, який оснований на властивостях порівнянь. Розвинуті на цій основіметоди контролю арифметичних і логічних операцій називають контролем по модулю.
Арифметичніоперації виконуються на суматорах прямого, оберненого і доповняльного коду.Допустимо, що зображення чисел зберігаються в машині деякого коду, тобтооперація перетворення в заданий код на виході чи вході машини. Методика реалізаціїоперацій контролю представляється наступним чином.
По-першерозглянемо зображення числа в відповідному коді, як єдину кодову комбінацію.
Розглянемопослідовність дій на прикладі суматора прямого коду додаються тільки цифровічастини зображення чисел, а знак зберігається, то контроль можна здійснитидвома способами:
1)   роздільний контроль знаковоїі цифрової чистин зображень результату;
2)   загальний контроль всьогозображення.
Прироздільному способі для контролю знакових розрядів можна використовувати засібдля визначення переповнення, так як у випадку модифікованого коду поява помилокв знакових розрядах приведе до неспівпаданню інформації в них. При перевірціправильності обробки цифрових частин зображень також не виникає особахускладнень.
При загальномуспособі контролю потребує корекцію контрольного коду результату із-за того, щознак результату при додаванні повторює знак доданків.
Контроль помодулю дозволяє ефективно визначити одиничні помилки. Однак одинична помилка водному розряді може привести до ряду помилок, в декількох розрядах. Тому кращезнайти засоби, які дозволять знайти не тільки одиничні помилки, але ряд їхпакетів, які можуть зустрічатись. Для цього використовуються арифметичні коди.
Одним з такихкодів є AN-код, де А-контролюєме число, N-модуль. Для таких кодів змінюютьсяпоняття відстані і ваги.
Вагоюарифметичного коду прийнято вважати кількість нульових символів в кодовійкомбінації, а відстань визначається як вага різниці кодових комбінацій,називають арифметичною відстанню.
А = 2і– 1, і=2,3,…
АN1 АN2 = A(N1  N2)
Якщоділення виконується без остачі, помилок немає, якщо з остачею – помилки є.
АN1АN2 = A2N1 N2
АN –використовуються для контролю лише в тих пристроях, де реалізується операціяділення.3.2 Приклад контролювиконання операції множення за допомогою 11N-коду
Виконаємочисловий контроль за допомогою 11N-коду для заданих чисел:
N1= 57
N2= -923
A=11
11*57*(-923)*11= 121*(-52 611) = -6 365 931
Теперотримане число ділимо на 121:
-6 365 931/121= -52611
Отримаємо-52611 – це означає що націло ділиться отже не існує помилки. Остача в цьомуприкладі дорівнює нулю.
Внесемопохибку в обчислення:
-6 365 933/121= -52611 і остачу 2, отже результат не збігається.
/>ВИСНОВКИ
 
В ході виконаннякурсової роботи проведено аналіз проблеми логiчної реалізації операції множеннячисел у формі з фіксованою комою, зокрема, алгоритму множення на суматоріпрямого коду, починаючи зі старших розрядів множника. Вищевказана операціяперевірена на прикладі чисел А= 57 та В= — 923, а також для заданої операції побудованоалгоритм виконання множення чисел у формі з фіксованою комою. Потім за данималгоритмом розроблено операційний та керуючий автомати. А також описанаметодика 11N контролю даної операції.
/>ПЕРЕЛІК ПОСИЛАНЬ
 
1.   Методичні вказівки дооформлення курсових проектів (робіт) у Вінницькому національному технічномууніверситеті / Г.Л. Лисенко, А.Г. Буда, Р.Р. Обертюх. – Вінниця: ВНТУ, 2006. –60 с.
2.   Прикладная теория цифровыхавтоматов: Учеб. для вузов по спец. ЭВМ / А.Я. Савельев. – М.: Высшая школа,1987. – 272 с.
3.   Прикладная теория цифровыхавтоматов / К.Г. Самофалов, А.М. Романкевич, В.Н. Валуйский,Ю.С Каневский, М.М. Пиневич. – К.: Вища школа. Головное изд-во, 1987.– 375 с.
4.   Структура электронныхвычислительных машин / С.А. Майоров, Г.И. Новиков. – Л.:Машиностроение. Ленинградское отделение, 1979. – 384 с.
5.   Электронные вычислительныемашины и системы: Учеб. пособие для вузов. – 3-е изд., перераб. и доп. /Б.М. Каган. – М.: Энергоатомиздат, 1991. – 592 с.
6.   Цифровые ЭВМ: Теория ипроектирование / К.Г. Самофалов, В.И. Корнейчук, В.П. Тарасенко. – К.:Выща школа. Головное изд-во, 1989. – 424 с.
7.   Справочник по цифровойсхемотехнике / В.И. Зубчук, В.П. Сигорский, А.Н. Шкуро. – К.: Тэхника,1990. – 448 с.