Пристрій арифметичного ділення за методом квадратичної апроксимації

 

АНОТАЦІЯ

У дипломній роботі реалізовано  базові етапи процесу проектування на базі ПЛІС пристрою для виконання операції ділення двох чисел. Операція ділення виконується, як операція множення одного числа на обернену величину другого числа. Обернена величина числа визначається за методом квадратичної апроксимації. Розроблено структурну та функціональну схеми, програмний модуль для апроксимації характеристики.

 

 

 

ABSTRACT

In the thesis work implemented basic stages of the design process on FPGA device to perform the operation division of two numbers. Division operation is performed as an operation of multiplication of one number by the reciprocal of the second number. Reciprocal of the number determined by the method of quadratic approximation. Structural and functional circuits, software module for approximation properties.

 

ЗМІСТ

 

АНОТАЦІЯ 3

ABSTRACT 4

ВСТУП 7

1. АНАЛІТИЧНИЙ  ОГЛЯД 8

1.2.Поняття  про комбінаційну схему і цифровий  автомат 11

1.3. Алгоритми  ділення 16

1.3. Пристрій  ділення в парафазному коді 19

1.4. Наближене  обчислення функцій 23

1.4.1. Основні  теоретичні відомості 23

1.4.2. Інтерполяційний  поліном Лагранжа 26

1.4.3. Інтерполяційний поліном Ньютона 28

1.4.4. Обернене  інтерполювання 31

1.4.5. Сплайн-інтерполювання 31

1.4.6. Інтерполювання  в таблицях 33

1.4.7. Лінійна  та квадратична апроксимація 34

1.5. Чисельне  розв'язання трансцендентних рівнянь 36

1.5.1. Метод  половинного ділення 38

1.5.2. Метод  хорд 38

1.5.3. Метод  дотичних (Ньютона) 40

1.6. Чисельне  інтегрування функцій 41

1.6.1. Метод  прямокутників 42

1.6.2. Метод  парабол 42

1.6.3.Формула  трапецій 44

2.  ОБГРУНТУВАННЯ ВИБРАНОГО НАПРЯМКУ ПРОЕКТУВАННЯ 46

2.1. Структурна схема пристрою 46

2.2. Алгоритм роботи програми 47

2.3. Опис елементної бази та засобів проектування 50

2.3.1. Огляд  програмного пакету Visual C++ 2010 Express 50

2.3.2 Загальні  характеристики САПР Quartus II 51

2.3.3. Основні  етапи проектування НВІС ПЛ 53

3. РОЗДІЛ 56

3.1. Розробка  структурної схеми пристрою 56

3.2. Розрахунок  надійності роботи пристрою 58

3.3. Розрахунок  потужності споживання 62

4. ЕКОНОМІЧНИЙ РОЗДІЛ 64

4.1. Визначення комплексного показника якості 64

4.2. Розрахунок  лімітної ціни нового виробу 66

4.3. Визначення показників економічної ефективності проектних рішень 67

4.3.1. Умови  економічної ефективності 67

4.3.2. Визначення собівартості і ціни спроектованого пристрою 69

4.3.3. Розрахунок  терміну служби пристрою за  амортизаційним терміном 71

4.3.4. Визначення економічного ефекту в сфері експлуатації 71

4.4. Висновки 73

ВИСНОВКИ 74

СПИСОК ЛІТЕРАТУРИ 75

ДОДАТКИ 76

Додаток А. Лістинг  програми 76

 

ВСТУП

Практично всі сучасні  мікропроцесори апаратно реалізують основні  арифметичні операції: додавання, віднімання, множення і ділення. Найбільш складною в реалізації серед них є операція ділення. У багатьох напрямках, таких  як комп’ютерна графіка, наукові  обчислення, мультимедіа системи  та ін., операція ділення відіграє критично важливу роль. Саме ця операція часто  стає вузьким місцем цілої системи  при нераціонально вибраному  алгоритмічи неоптимальній реалізації. Суттєвим обмеженням є також той  факт, що існуючі блоки ділення  реалізовані для чисел з розрядністю  кратною ступеню двійки, хоча при  реалізації конкретних пристроїв виникає  необхідність оперувати числами  довільної розрядності. У більшості  випадків, результат операції ділення  є наближеним, недостатня точність обчислень може призвести до суттєвих похибок кінцевого результату обчислення і в той же час збільшити  час виконання алгоритму та розмір схеми, якщо алгоритм реалізований не оптимально. Тому актуальною стала  потреба автоматизації синтезу  блоку ділення чисел довільної  розрядності з метою зменшення  апаратної складності алгоритмічних  операційних пристроїв (АОП). 

1. АНАЛІТИЧНИЙ ОГЛЯД

1.1. Арифметичний  пристрій

Арифметичний пристрій (АП), один з основних пристроїв електронною цифрової обчислювальної машини (ЦОМ), в якому безпосередньо виконуються арифметичні і логічні операції над числами. Виконання будь-якої арифметичної або логічної операції в АП зводиться по суті до послідовного виконання ряду елементарних операцій або мікрооперацій: установка в «нуль» будь-яких розрядів блоків АП, прийом коди числа або окремого розряду, видача коди, здобуття інверсної (зворотною) величини коди числа, складання код, зрушення коди у бік молодших або старших розрядів числа і т.д.

До арифметичних операцій відносяться складання, віднімання, множення, ділення і витягання  кореня. Останні дві дії, а також  зведення в міра, визначення логарифмів, тригонометричних функцій і т.п. часто виконуються по стандартних підпрограмах. Основна операція ЦОМ(цифрова обчислювальна машина) – складання, до якого зводяться всі арифметичні операції. Наприклад, віднімання числа В з числа А замінюється складанням за допомогою співвідношення А - В = А + (- У ), у якому обидва числа можуть бути представлені прямим, зворотним або додатковим кодом множення зводиться до багатократного підсумовування множеного; ділення – до послідовного знаходження цифр приватного за допомогою складання і віднімання.

АП у складі ЦОМ(цифрова  обчислювальна машина) пов'язано  з пристроєм (ЗУ) і центральним пристроєм, що запам'ятовує управління (див. Пристрій, що управляє ). Із ЗУ поступають вихідні числа, по команді центрального пристрою управління («скласти», «відняти», «помножити» і т.д.) АП виробляє відповідні операції, результати операцій передаються знову в ЗУ, а сигнали закінчення операції, ознаки переповнювання розрядної сітки і ін., при необхідності, –в центр.(центральний) пристрій управління. 

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

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

Залежно від вживаного  способу підсумовування чисел розрізняють  АП послідовної, паралельної і послідовно-паралельної  дії. У АП послідовної дії підсумовування двох чисел виконується одно розрядним суматором, через який послідовно, починаючи від молодших, проходять всі розряди доданків. У АП паралельної дії всі розряди кожного з доданків передаються в суматор одночасно, кількість розрядів суматора відповідає кількості розрядів в доданках. АП послідовно-паралельної дії – проміжна форма. Регістри паралельного АП будуються з тригерів або аналогічних елементів і забезпечують одночасний доступ до всіх розрядів числа. У АП послідовної дії як регістри використовуються також лінії затримки, які, якщо необхідно, замикаються в кільце через підсилювачі і логічні ланцюги рециркуляції. У елементах і схемах АП використовуються електронні лампи (у ранніх зразках), транзистори, напівпровідникові діоди, ферріттранзісторні вічка і феррітдіодні вічка . У АП з мікропрограмним управлінням в складі місцевого пристрою управління застосовують також феритові матрицідля зберігання мікропрограм операцій. 

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

 Методи прискорення  виконання операцій застосовуються  або до елементарних операцій (частинам повних), або до повних  операцій АП. Особливо ефективне  прискорення елементарної операції  підсумовування, оскільки вона входить  істотною частиною в алгебру  складання-віднімання, множення, ділення  і ін. У послідовних АП прискорення  підсумовування досягається переходом  до послідовно-паралельних схем; у паралельних – вживанням схем, що використовують статистичний характер перенесень, схем «з миттєвим перенесенням» і т.д. Найбільш розроблені методи прискорення множення. У послідовних пристроях вони засновані переважно на введенні доповнить. суматорів, що дозволяють одночасно підсумовувати декілька часткових творів; у межі наявність n суматорів послідовного типу (або n /2 суматорів і логічних схем) дає можливість виконати множення за 2 n тактів. У паралельних АП застосовуються методи прискорення множення логічні і апаратні 1-го і 2-го порядку. Логічні методи ґрунтуються на перетворенні множника; збільшення апаратури при їх використанні стосується лише місцевого пристрою управління і не залежить від кількості розрядів в перемножуваних числах; теоретична і практична межа можливостей логічних методів – зменшення середньої кількості підсумовувань при виконанні одного множення до ¹ / ₃ на кожен двійковий розряд множника. Апаратні методи 1-го порядку ґрунтуються на введенні додаткових суматорів, додаткових ланцюгів запам'ятовування перенесень або заміні ланцюгів зрушення ланцюгами множення і ділення на особливі множники; кількість додаткового устаткування пропорційно кількості розрядів; кількість тактів підсумовування в процесі множення теоретично може бути зменшене до одного (незалежно від кількості розрядів множника), але практично ця межа не досягається. Апаратні методи 2-го порядку ґрунтуються на побудові пірамід суматорів; кількість устаткування пропорційна квадрату кількості розрядів, час множення – 2-3 такти підсумовування. Аналогічні методи розробляються для прискорення операції ділення.

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

1.2.Поняття про комбінаційну  схему і цифровий автомат

Пристрій, який перетворює дискретну інформацію, в загальному випадку має n входів для вхідних  сигналів і k виходів, з яких знімаються вихідні сигнали.

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

Перетворення  інформації в ЕОМ виконується  електронними пристроями (логічними  схемами) двох класів: комбінаційними схемами і цифровими автоматами.

В комбінаційних  схемах (КС) сукупність вихідних сигналів (вихідне слово Y) в дискретний момент часу t_i однозначно визначається вхідними сигналами (вхідним словом X), які поступили на входи в той самий дискретний момент часу.

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

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

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

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

Цифровий автомат  містить пам’ять, що додається з  запам’ятовуючих елементів (ЗЕ) - тригерів, елементів затримки та інших, що фіксують стан, в якому він знаходився. Комбінаційна схема не містить ЗЕ. Тому її називають автоматом без  пам’яті або примітивним автоматом.

Структурна схема  цифрового автомату містить ЗЕ₁ - ЗЕ_k та комбінаційні схеми КС₁ і КС₂.

 

Рис. 1.1. Комбінаційна схема (а) і цифровий автомат (б).

Стан ЗЕ, що визначає стан автомату, передається в формі  сигналів q_i по ланцюгах прямого зв’язку на входи КС₂ і по ланцюгах зворотнього звязку на входи КС₁. На входи комбінаційних схем поступають також сигнали x₁,...,x_n з входу автомату.

Вихідне слово  виробляється в КС₂, причому вхідними змінними для неї служать букви вхідного слова і стани ЗЕ - стани автомату. Вихідні сигнали КС1 переводять автомат в нові стани, при цьому вхідними змінними для цієї схеми служать букви вхідного слова і стани ЗЕ. Одночасність появи нових значень вхідних сигналів на всіх входах пристрою досягається за допомогою тактових сигналів (синхросигналів), що забезпечують передачу інформації з ЗЕ на входи комбінаційної схеми одночасно з сигналами, що поступають на її входи з інших пристроїв.

В ряді випадків  при аналізі автомата його заміняють  автоматом з одним еквівалентним  входом і з одним еквівалентним  виходом і рахують, що еквівалентні вхідний сигнал x(t) і вихідний сигнал y(t) приймають значення з відповідним  чином перетворених алфавітів P і S вхідних  і вихідних сигналів.

Для задання цифрового  автомата повинно бути вказано:

1) вхідний алфавіт 

2) вихідний алфавіт 

3) алфавіт стану 

4) початковий  стан автомату 

5) функція переходу 

6) функція виходів  - однозначно визначає залежність відповідно стану автомата в момент дискретного часу і вихідного сигналу y(t), від стану автомата Q(t) і вхідного сигналу x(t) в момент дискретного часу t.

Використовуючи  функції переходів і виходів, поведінку автомата можна описати  рівняннями

(1.1)

(1.2)

де t=0,1,2 ...; Q(0)=Q₀.

Рівнянням (1) і (2) відповідає автомат, вихідний сигнал якого  залежить від стану автомата і  від сигналу на його вході. Такий  автомат називається автоматом  Мілі.

В пристроях ЕОМ  широко використовуються так звані  автомати Мура, 
в яких вихідний сигнал y(t) в момент дискретного часу t залежить виключно від стану автомата Q(t) в цей момент часу і незалежить від вхідного сигналу x(t).

Функціонування  автомата Мура описується рівняннями

(1.3)

(1.4)

де t=0,1,2 ... ; Q(0)=Q₀.

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

В теорії автоматів  вводиться поняття повної системи  переходів і повної системи виходів  автомата. Якщо для двох любих станів Q_i і Q_j автомата є вхідний сигнал, який переводить автомат з стану Q_i в Q_j, то такий автомат називається автоматом з повною системою переходів. Автомат Мура має повну систему виходів, якщо вихідні сигнали різні для всіх його станів.

При побудові вузлів ЕОМ, які являються цифровими  автоматами, в якості запам’ятовуючих  елементів (елементів пам’яті) використовуються елементарні автомати. Елементарними  автоматами є автомати Мура з двома  станами,що володіють повними системами  переходів і виходів.

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