Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Вінницький державний технічний університет

Кафедра захисту інформації

КУРСОВА РОБОТА

з дисципліни

Прикладна теорія цифрових автоматів

Виконав: ст. гр. 2-КС-2002

Бойчук А. А.

Перевірив: професор

Лужецький В.А.

Вінниця 2004

ЗМІСТ

Вступ

1. Розробка операційного автомату і машинного алгоритму

1.1 Основні методи виконання операції множення

1.2 Методи прискорення операції множення

1.3 Формалізований опис операційного автомату

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

1.5 Машинний алгоритм виконання операції

1.6 Приклад реалізації алгоритму

1.7 Обчислення абсолютної і відносної похибок виконання операції

2. Розробка керуючого автомату

2.1 Керуючі автомати з програмованою логікою із вертикальним кодуванням

2.2 Порядок синтезу керуючого автомату програмованою логікою

2.3 Синтез керуючого автомату з програмованою логікою

ВСТУП

ЕОМ відкрили нову сторінку в історії людських знань і можливостей, звільнили тисячі обчислювачів, значно полегшили працю вчених, дали можливість вивчати найскладніші процеси. З моменту використання обчислювальної техніки стало можливим вирішення низки проблем, пов'язаних з автоматизацією виробничих процесів, підвищенням якості наукових досліджень, продуктивності праці, економією матеріалів та енергії. У теперішній час важко назвати сфери науки або виробництва, де б не застосовувались обчислювальні пристрої та, зокрема, що одержали особливий розвиток мiкропроцесорнi пристрої. Вид інформації, яка обробляється ЕОМ, впливає на структуру обчислювальних машин, які в залежності від цього поділяються на два основних класи: аналогові і цифрові.

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

Формулювання постулату Поста підводить до поняття алгоритму. По Колмогорову це є всіляка система обчислень, що виконується по суворо визначеним правилам, яка після любого числа приводить до вирішення поставленої задачі. Алгоритм має забезпечити отримання результату через конечну кількість кроків.

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

1. РОЗРОБКА ОПЕРАЦІЙНОГО АВТОМАТУ ТА МАШИННОГО АЛГОРИТМУ

1.1 Основні методи виконання операції множення

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

Множення двох (n - 1) розрядних чисел може мати 2(n - 1) значущих розрядів. Тому при операції множення цілих чисел необхідно передбачити можливість формування в АЛП добутку, котрий має двохкратну в порівнянні із співмножниками довжину. В ЕОМ, в яких числа з фіксованою комою є дробами, молодші ( n - 1) розрядів множення часто відкидаються (при відкиданні може виконуватись операція округлення добутку). Для виконання множення АЛП повинен мати регістри множеного, множника та схеми формування суми часткових добутків - суматор часткових добутків, в якому шляхом відповідної організації передач виконується послідовне додавання часткових добутків.

Операція множення складається з (n - 1) циклів. В кожному циклі аналізується слідуюча цифра множника, якщо це 1, то до суми часткових добутків додається множене, в іншому випадку додавання не виконується. Цикл закінчується зсувом множеного відносно суми часткових добутків або зсувом суми часткових добутків відносно нерухомого множеного. В залежності від способу формування суми часткових добутків розрізняють чотири основних методи виконання множення та відповідно чотири структури АЛП для цієї операції. Для визначеності спочатку будемо вважати, що обидва співмножника - додатні числа.

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

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

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

Метод3. Множення, починаючи з старших розрядів множника, при зсуві суми часткових добутків вліво та нерухомому множеному. Регістр множника та суматор часткових добутків повинні мати кола зсуву вліво. Регістр множеного не має кіл зсуву. Послідовність дій виконання множення визначається старшим розрядом регістра множника. При цьому методі суматор часткових добутків повинен мати подвійну довжину. Даний метод потребує додаткового в порівнянні з першим методом устаткування. Не дивлячись на це, він застосовується в деяких АЛП, так дозволяє без додаткових кіл зсуву виконувати і ділення. Для виконання операції ділення в АЛП, котрий реалізує перший метод множення, необхідні додаткові кола зсуву вліво в регістрі множеного та в суматорі часткових добутків.

Метод4. Множення, починаючи з старших розрядів множника, при зсуві вправо множеного та нерухомій сумі часткових добутків. Регістр множника повинен мати кола зсуву вліво, регістр множеного - кола зсуву вправо. Суматор часткових добутків не має кіл зсуву. Послідовність дій на кожному кроці множення визначається старшим розрядом регістра множника. При цьому методі множення і регістр множеного, і суматор часткових добутків повинні мати подвійну довжину. Проте, як і третій метод, він не потребує додаткових кіл зсуву при виконанні ділення. При четвертому методі, в якому сума часткових добутків нерухома, можливо суміщати в часі операції зсуву та додавання і за цей рахунок збільшити швидкодію АЛП при виконанні множення. Якщо необхідне створення добутку подвійної довжини, наприклад, при операціях з цілими числами, найбільш економним є перший із розглянутих вище методів множення, оскільки він дозволяє використовувати всі регістри одинарної довжини. Якщо в результаті множення досить мати добуток одинарної довжини, то доцільно буде використання або першого, або четвертого методів множення. При використанні першого метода потрібно ввести додаткові кола зсуву для реалізації ділення, а при використанні четвертого необхідне збільшення довжини суматора. Вибір одного з цих методів множення визначається співвідношенням витрат обладнання на реалізацію кіл зсуву та додаткових розрядів суматора.

При виникненні добутків одинарної довжини просте відкидання молодших розрядів вносить похибку, котра буде накопичуватись, так як добутки будуть завжди вираховуватись з недостачею. Тому для підвищення точності обчислень часто виконують округлення результату множення, внаслідок чого похибка стає знакозмінною. Для округлення добутків довжина суматора часткових добутків звичайно збільшується на один розряд. Після визначення добутку до цього додаткового розряду додається 1. Якщо додатковий розряд добутку дорівнював 0, то добуток в основних розрядах суматора отримується з недостачею. Якщо додатковий розряд дорівнював 1, то в результаті переносу 1 з додаткового розряду до основних розрядів суматора добавляється 1 та добуток отримується з надлишком, при цьому максимальне значення похибки добутку дорівнює половині першого молодшого розряду.

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

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

Sg _A Sg _B = Sg _C,

де - знак додавання за модулем 2.

1.2 Методи прискорення операції множення

Операція множення зустрічається в програмах так же часто як і операція додавання. Однак час виконання множення в декілька разів більший часу додавання. Тому продуктивність арифметико-логічного пристрою (АЛП) практично визначається часом множення а при проектуванні АЛП велика увага приділяється прискоренню множення. Це прискорення як правило супроводжується збільшенням апаратурних витрат. Оскільки блок множення (БМ) складається з підсумовуючого блоку (ПБ) та блоку місцевого керування (БМК) то в залежності від того яка частина БМ ускладнюється розрізняють логічні апаратні та комбіновані способи прискорення. Логічним будемо називати такі способи в яких прискорення множення досягається за рахунок ускладнення схеми БМК при незмінній структурі ПБ. При цьому в залежності від того якій величині (n або n²) пропорційні витрати додаткового обладнання розрізняють апаратні способи прискорення першого та другого порядків. При комбінованих способах використовуються як апаратні так і логічні методи прискорення.

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

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

Представлення двійкових чисел за допомогою трьох цифр є неоднозначним тому з усіх можливих варіантів вибирають той що містить найменшу кількість значущих цифр тобто 1 і -1. Для цього групу з m>2 одиниць 011…10 перетворюють в групу 100…-10. У правомірності таких перетворень легко переконатися на такому прикладі.

30₍₁₀₎ = 011110₍₂₎ = 02⁵ + 12⁴ + 12³ + 12² + 12¹ +02⁰ = 12⁵ + 02⁴ + 02³ + 02² + (-1)2¹ + 02⁰ = 32₍₁₀₎ - 2₍₁₀₎ = 1000(-1)0₍₂₎ .

При виконанні множення множене додають до суми часткових добутків якщо чергова цифра множника дорівнює 1 та віднімають якщо чергова цифра множнику -1. Перетворення множнику відбувається одночасно з виконанням множення. Алгоритм перетворення залежить від того з старших чи з молодших розрядів виконується множення. Метод множення з послідовним перетворенням цифр множника передбачає послідовний аналіз цифр множника без розбиття на групи. При цьому використовується такі правила перетворення:

- якщо дана цифра неперетвореного множника не збігається із сусідньою праворуч цифрою, сусідня ліворуч цифра є 0 і попередня цифра перетвореного множника є 0, то даний розряд у перетвореному множнику є 1;

- якщо дана цифра неперетвореного множника не збігається із сусідньою праворуч цифрою, сусідня ліворуч цифра є 1 і попередня цифра перетвореного множника є 0, то даний розряд перетвореного множника повинний містити ;

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

Застосовуючи ці правила необхідно враховувати, що старша значуща цифра перетвореного множника може знаходитися в розряді цілих; праворуч і ліворуч від значущих розрядів перетвореного множника завжди передбачаються нулі. Коли в приведеному правилі говориться про "попередні" цифри перетвореного множника, то стосовно до множення від молодших розрядів це відноситься до попередньої молодшої цифри перетвореного множника, а стосовно до множення від старших - до старшої попередньої цифри.

Описане послідовне перетворення розрядів множнику забезпечує під час множення в середньому 0,333п додавань-віднімань. Це найкращий результат, що може бути отриманий для логічних методів прискорення множення. У здійсненні метод послідовних перетворень ненабагато складніше, ніж метод групування розрядів множника, ефективність же його вище. При цьому виникають визначеної довжини послідовності чи нулів одиниць, що приводить до необхідності одночасного аналізу декількох розрядів множника і зрушенню на довільне число розрядів.

1.3 Формалізований опис операційного автомату

операційний автомат алгоритм прошивка програмований

В функц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домостей:

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

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

3. Множиною м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й керуючого автомату.

Згідно з канонізованим методом синтезу поставимо у відповідність кожному математичному елементу структурний елемент.

Вхідні дані (множене та множник) надходять в пристрій через шину вхідних даних Ш_вх.

Результат (добуток) видається з пристрою через шину вихідних даних Ш_вих.

Для зберігання операндів потрібні регістри Рг А - для множеного Рг В - для множника.

Для зберігання операндів потрібні тригери Тзн А і Тзн В у яких буде зберігатись значення знакового розряду множників.

Для накопичення часткових добутків необхідно використати нагромаджувальний суматор який складається з комбінаційного суматора (КСМ) та регістра результату - Рг С.

Для аналізу і перетворення розрядів множника буде використовуватись схема перетворення коду (СхПК).

Для формування оберненого коду, який потрібен у випадках, коли потрібно віднімання, буде використовуватись схема формування оберненого коду (СхФОК).

Для підрахування кількості кроків множення використовується лічильник (Ліч).

Для визначення знаку добутку потрібна схема знаходження суми за модулем 2, та тригер (Тзн С де буде зберігатись значення знакового розряду).

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

На основі формалізованого опису побудуємо структурну схему операційного автомату (рис. 1):

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

1.5 Машиний алгорим виконання операції множення

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

Алгоритм множення:

1. Надати операнди з вхідної шини - Ш вх, у відповідні регістри.

2. Регістр Рг С результату занулити, лічильнику присвоїти 8 .

4. Виконати перевірку молодшого розряду згрупованого множника: якщо В=01 - до вмісту Рг С добавляємо вміст Рг А; якщо В=10 - до вмісту Рг С добавимо Рг А зсунутий на одну позицію вліво; якщо В=0 - до вмісту Рг С добавимо доповняльний код Рг А.

5. Лічильник (Ліч) зменшити на 1.

6. Превірити якщо Ліч=0 то перейти до наступного кроку, якщо Ліч 0 виконати зсув регістрів С і В в право на два розряди.

7. Виконати поправку, якщо В<0.

8. Видати результат на Ш вих.

1.6 Приклад реалізації алгоритму

Отже маємо:

Виконаємо приклад множення над заданими числами: 0,5555 і -0,6666.

А(0,5555)₁₀=(0,10001110)₂;В(-0,6666)₁₀=(-0,10101010)₂;

Для виконання множення зробимо перетворення та групування множника: В(-0,10101010)₂=(1,01010110)_доп=(0,1|0|0|0)_пер;

Послідовність дій операції множення наведемо у таб.1

Рг С	Рг А	Рг В	Примітки
0,00000000000000 1,01110010000000	0,10001110000000 1,01110010000000	0,1|0|0|0	В:=11 РгС=РгС+(РгА)об+1 РгС:=R2РгВ
1,01110010000000 1,11011100100000 1,01110010000000	1,01110010000000	0,1|0|0	РгС:=R2РгС В:=11 РгС=РгС+(РгА)об+1 РгС:=R2РгВ
1,01001110100000 1,11010011101000 1,01110010000000	1,01110010000000	0,1|0	РгС:=R2РгС В:=11 РгС=РгС+(РгА)об+1 РгС:=R2РгВ
1,01000101101000 1,11010001011010 0,10001110000000	0,10001110000000	0,1	РгС:=R2РгС В:=01 РгС=РгС+РгА
0,01011111011010 1,00101111101101 1,01110010000000			Поправка
0,10100001101101 1,01011110010011			Перетворення у прямий код

Отже ми отримали такий результат:

С1=(1,01011110010011)₂=(-0,368347167)₁₀;

перемножимо задані числа

С2=0,5555*(-0,6666)=-0,3702963;

1.7 Обчислення абсолютної і відносної похибок виконання операції

Для знаходження похибки потрібно поділити дані числа в десятковій формі. Потім похибки вираховується за формулами:

Абсолютна похибка становить =|C1-C2|= 0,001949133;

Відносна похибка становить у=(100%)/С2=0,526%.



2. РОЗРОБКА КЕРУЮЧОГО АВТОМАТУ

2.1 Керуючі автомати з програмованою логікою із вертикальним кодуванням

Будь-яка мікрокоманда складається:

у	х	А

у - поле логічних операцій; х - поле логічних умов, що реалізуються; А - поле адрес. х разом з А називаються скороченою частиною.

При х=0, то А_і=А; при х=1, то А_і=А_і-1+1.

1	у	- робоча мікро-команда
0	х	А	- умовна мікро-команда

1 - розряд ознаки мікро-команди.

Відрізняють такі способи кодування:

Вертикальне кодування мікрооперацій: кожному у відповідає свій двійковий код

у1	0	0	1
у2	0	1	0
у3	0	1	1
у4	1	0	0

Горизонтальне кодування мікрооперацій:

	у*1	у*2	у*3	у*4	у*5
у1	1	0	0	0	0
у2	0	1	0	0	0
у3	0	0	1	0	0
у4	0	0	0	1	0
у5	0	0	0	0	1

Приклад:у3,у4,у5=00111.

Вертикально-горизонтальне або горизонтально-вертикальне кодування:

Поле логічних умов можна корегувати або двійковим кодом (вертикального кодування) або унарним кодом (горизонтального кодування).

Порівняння керуючих автоматів з програмованою і жорсткою логікою:

Програмована логіка	Жорстка логіка
Переваги
Простота зміни алгоритму (достатньо записати нові коди у пам'ять)	Висока швидкодія. Відносно невеликі апаратні витрати.
Недоліки
Низька швидкодія	Складність зміни алгоритму (проектування і виготовлення автоматів)

Рекомендація:

Автомати з програмованою логікою рекомендується використовувати на етапі створення нової техніки. Для масового виробництва рекомендується використовувати автомати з жорсткою логікою.

2.2 Порядок синтезу керуючого автомату програмованою логікою

Для синтезу керуючого автомату з програмованою логікою необхідно

Побудувати розмічену граф схему-алгоритму.

Визначити кількість вхідних сигналів х, визначити кількість вихідних сигналів у, визначити кількість станів автомату.

Побудувати таблицю переходів та виходів.

Побудова схеми.

2.3 Синтез керуючого автомату з програмованою логікою

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

y1 РгА := Швх ;	у7 РгА := L1(РгА);
y2 РгВ := Швх ;	у8 Ліч := Ліч - 1;
у3Рг С =0;	у9 РгВ := R2(РгВ);
у4 Ліч := 15;	у10 РгС := R2(РгС);
у5 Рг С=Рг С+Рг А;	у11 Рг С=Рг С+;
у6 Рг С=Рг С+;	у12 Швих =Рг С.

Позначимо відповідні отримані керуючі сигнали та умови переходів на кресленні операційного автомату.

Размещено на Allbest.ru

...