Виконання операції множення

Виконання операції множення

Вступ

Перші ЕОМ з програмованим керуванням із програмою, яка зберігається в пам’яті з’явились практично одночасно в Англії, США та ін.

Фундаментальний внесок в розвиток вітчизняної обчислювальної техніки вніс академік С.А. Лєбєдєв. Під його керівництвом в 1949-1951 роках в АНУРСР в Києві була побудована перша в нашій країні ЕОМ - мала електронна лічильна машина (МЕЛМ), а в 1952-1954 рр. - швидкодіюча електронна лічильна машина (ШЕЛМ), яка виконувала 8000 операцій/сек. і була на той час однією із самих швидкодіючих ЕОМ в світі.

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

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

В останній час визначились контури нового, п’ятого покоління ЕОМ. В значній мірі цьому допомогли публікації відомостей про проект ЕОМ п’ятого покоління, який розробляється провідними японськими фірмами та науковими організаціями.

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

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

.1 Основні способи виконання операції множення

Ми використовуємо двійкову систему числення, в якій є декілька основних способів виконання операції множення:

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

Множник B = 0,b₁b₂…b_n перетворюється за схемою Горнера:

= (… ((b_n×2^-1 + b_n-1)×2^-1 + b_n-2)×2^-1 + … + b₂)×2^-1 + b₁)×2^-1

Тоді

= A×B = (… ((b_n×0, a₁a₂…a_n)×2^-1 + b_n-1×0, a₁a₂…a_n)×2^-1+ … + b₁×0, a₁a₂…a_n)×2^-1

Тут множення починається з молодших розрядів та зсувається вправо сума часткових добутків. Структурну схему пристрою наведено на рис. 1.1. Час виконання операції можна визначити за формулою

Т_мн2 = n ×t_дод (1.1)

Рисунок 1.1 - Структурна схема пристрою множення (метод 1).

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

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

Припустимо В-множене (В>0), A-множник (А>0), С-добуток. Тоді, у випадку зображення чисел у формі з фіксованою комою, отримуємо:

А = а₁а₂…а_n;= b₁b₂…b_n = b₁×2^-1 + b₂×2^-2 + … + b_n×2^-n;

Випливає що,

С = А×В = (0,а₁а₂…а_n)×(b₁×2^-1 + … + b_n×2^-n) =

= (2^-1×0, a₁a₂…a_n)×b₁ + (2^-1×0, a₁a₂…a_n)×b₂ + … + (2^-n×0, a₁a₂…a_n)×b_n.

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

Структурну схему пристрою для множення, реалізуючого цей метод, наведено на рис 1.2. Час виконання операції можна визначити за формолою

Т_мн1 = n ×(t_дод + t_зс) (1.2)

Регістр множника і суматор часткових добутків повинні мати кола зсуву вправо. Регістр множеного не має кіл зсуву.

Рисунок 1.2 - Структурна схема пристрою множення (метод 2)

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

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

Множник записується таким чином:

= 2^-n×(b_n + b_n-1×2¹ + b_n-2×2² + … +b₁×2^n-1).

В цьому випадку

С = A×B = 2^-n×[b_n×0, a₁a₂…a_n + b_n-1×(2¹×0, a₁a₂…a_n) + b_n×(2²×0, a₁a₂…a_n) + … + b₁×(2^n-1×0, a₁a₂…a_n)].

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

Структурну схему пристрою наведено на рис. 1.3. Час виконання операції визначається за формулою.

Т_мн3 = n ×(t_дод + t_зс) (1.3)

Рисунок 1.2 - Структурна схема пристрою множення (метод 3)

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

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

Метод 4. Множення, починаючи із старших розрядів множника з зсувом вправо множеного.

Якщо множник записати за формулою Горнера:

= 2^-n×(… ((b₁×2¹ + b₂)×2¹ + … + b_n-1)×2¹ + b_n ,

C = A×B = 2^-n×(… ((b₁×0, a₁a₂…a_n)×2¹ + b₂×0, a₁a₂…a_n)×2¹ + … +

+ b_n-1×0, a₁a₂…a_n)×2¹ + b_n×0, a₁a₂…a_n).

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

Структурну схему наведено на рис. 1.4. Час виконання операції можна визначити за формулою

Т_мн4 = n ×t_дод (1.4)

Регістр множника повинен мати кола зсуву вліво, регістр множеного - кола зсуву вправо. Суматор часткових добутків не має кіл зсуву.

Рисунок 1.4 - Структурна схема пристрою множення (метод 4).

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

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

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

До логічних методів прискорення множення відносяться: пропускання тактів сумування, групування розрядів множника, розподілення множника на частини; множення з запам’ятовуванням перенесення та інші.

Розглянемо докладніше метод групування розрядів множника. Розбивання множника на групи з довжиною 2 з цього слідує що ми переходимо до нової системи числення з основою 2². комбінації вигляду 01, 10 не змінюються, перетворюється 11 в наступну комбінацію 101. Для більш детального зображення побудуємо таблицю правила перетворення множника для системи (0,1,).

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

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

,

де

DI - множина вхідних даних,

S - множина проміжних результатів,

DO - множина вихідних даних,

X - множина логічних умов,

Y - множина мікрооперацій, що виконується,

Множиною вхідних даних є значення числа А, значення числа В, кількість розрядів n:

.

Множина проміжних результатів має вигляд:

.

Множиною вихідних даних є значення числа С:

.

Множина логічних умов має вигляд:

, де

х₁, х₂, х₃ - чергові цифри множника;

х₄ - логічна умова: якщо усі кроки множення виконані, то , інакше .

Множина мікрооперацій, що виконується:

.

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

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

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

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

.        Для зберігання знаку операнда А потрібний регістр (Тзн А).

.        Для зберігання знаку операнда В потрібний регістр (Тзн В).

.        Для регістру А потрібна схема формування оберненого коду (СхЗс).

.        Для зберігання операнду В потрібний регістр (РгВ).

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

.        Для збереження результату потрібен регістр (РгС).

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

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

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

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

1. Число А зі знаком записується в регістр Рг А і Тзн А, відповідно.

2. Число В зі знаком записується в регістр РгВ і Тзн В, відповідно.

3. Регістру С присвоюється значення 0.

4. Лічильнику присвоюється значення 8.

5. Розраховується знаковий розряд.

6. Перевіряється два розряди в регістрі В, після чого робиться наступні кроки, якщо:

7. В=00 переходиться до пункту 11.

8. В=01 до регістру С додається значення регістр А.

9. В=10 до регістру С додається значення регістр А в доповняльному коді.

10.В=11 до регістру С додається зсунений на один розряд значення регістру А.

11. Зсувається регістр С вліво на 2 розряди.

. Зсувається регістр В вліво на 2 розряди.

. Вміст лічильника зменшується на 1.

. Аналізується лічильник якщо він дорівнює 1, то потрібно перейти до пункту 15, інакше в п. 6.

. Видається результат знак РгС на шину даних.

. Кінець алгоритму

Граф-схема алгоритму

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

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

Двійкові коди чисел А і В

Двійковий код чисел

А = -0,4581= -0,0111011₂

В = -0,7891= -0,1100100₂

Запишемо машинне зображення операндів в прямому коді.

РгА= 0,0111011

РгВ= 1,000100

Виконаємо множення (вміст регістрів і виконані операції приведені в таб 2:

Приклад виконання множення за розробленим алгоритмом

A + Sgn B= Sgn C

Знак дорівнє 1, тобто мінус

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

,7891*0,4581=0,36148 в десятковій.

,011101

,110010

,010110101010 множення в двійковій в стовпчик

,3437- в десятковій

Абсолютна похибка ∆=0,3614-0,3437=0,0177

Відносна похибка σ=∆/0,3437*100%=5,1%

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

2.1 Керуючі автомати з жорсткою логікою

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

Функція керуючого автомату - це операторна схема алгоритму (мікропрограми), функціональними операторами якої є символи у₁,…, у_m, які ототожнюються з мікроопераціями, в якості логічних умов (предікатів) використовуються булеві змінні х₁,…, х_l. Кожна з цих формул визначає обчислювальний процес в послідовному аспекті - встановлює порядок перевірки логічних умов х₁,…, х_l і порядок виконання мікрооперацій у₁,…, у_m.

В залежності від способу визначення вихідного сигналу в керуючих автоматах розрізняють три типи абстрактних автоматів: автомат Мілі, автомат Мура, С-автомат. В абстрактному автоматі Мілі функція виходів l задає відображення (XxS)®Y. В абстрактному автоматі Мура функція виходів l задає відображення S®Y. В абстрактному С-автоматі вводяться дві функції виходів l₁ і l₂, що задають відображення (XxS)®Y₁ і S®Y₂ відповідно. При цьому алфавіт виходів С-автомата, Y=Y₁=Y₂ або Y=Y₁ÈY₂.

Довільний абстрактний атомат Мілі або Мура має один вхідний і один вихідний канали. Довільний абстрактний С-автомат має один вхідний і два вихідних канали.

Розмічена граф-схема алгоритму

2. Закодуємо вхідні та вихідні сигнали та стани автомату

. Складаємо кодовану таблицю переходів та виходів.

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

чотири D-тригерів для формування коду внутрішнього стану;

дишифратор DC для визначення стану за його двійковим кодом;

логічні схеми на елементах «І», «АБО», «НІ».

3. Методика контролю арифметичної операції

.1 Загальні теоретичні відомості

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

По-перше розглянемо зображення числа в відповідному коді, як єдину кодову комбінацію.

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

1)   розділений контроль знакової і цифрової чистин зображень результату;

2)   загальний контроль всього зображення.

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

При загальному способі контролю потребує корекцію контрольного коду результату із-за того, що знак результату при додаванні повторює знак доданків.

При числовому методі контролю код заданого числа визначається як найменший додатній залишок від ділення числа на вибраний модуль p:

_A=A - {A/p} p,

де у фігурних дужках - ціла частина від ділення; А - число, яке контролюється.

Величина модуля р істотно впливає на якість контролю; якщо р=q (q - основа системи числення, в якій виражене число) і має місце числовий контроль, то контролюється тільки молодший розряд числа і контроль як такий не має змісту; для р = q^m вірні аналогічні міркування, так як, якщо m<n, знову ж не всі розряди числа приймають участь у контролі і помилки в розрядах старших m взагалі не сприймаються.

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

А º r_A (mod p); B º r_B (mod p)

де 0 £ r_A £ p-1, то А + В º r_A + r_B(mod p).

Звідси

_{A +В} º r_A + r_B(modp).

Аналогічним чином доводиться вірність і наступних відношень:

_{A -В} º r_A - r_B(modp)._{A В} º r_A r_B(modp).

.2 Приклад реалізації методики контролю

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

А = 47 та В =-16, якщо модуль p = 3.

Контрольні коди чисел:_A= 47 mod 3 = 2, r_B = 16 mod 3 = 1

Контрольні коди для суми:- B = 47-16 = 31, (А+ В) mod 3=(31) mod 9= 0;_A+r_B =2+1 = 3, (r_A-r_B)mod 3= (3) mod 3= 0;

Так як (А - В) mod 3 = (r_A+r_B)mod 3=0, то це означає, що операцію віднімання виконано вірно.

Тепер внесемо помилку. Нехай А - В=30, (А - В) mod 3= (30) mod 3=1;

(r_A-r_B)mod 3= (3) mod 3= 0;

Оскільки, (А - В) mod 3¹(r_A-r_B)mod 3, то існує помилка - операцію додавання виконано невірно.

Таким чином, числовий контроль дозволяє визначити, чи вірний результат було отримано

Висновок

цифровий автомат множення мілі

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