Алгоритм операції множення

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Завдання

Розробити машинний алгоритм операції множення в доповняльному коді з пропуском тактів додавання в двійковій системі числення з старших розрядів чисел, представлених у формі з плаваючою комою (розрядність мантиси — 16, порядків -8) та операційний автомат. На прикладі чисел 41,32 і -14,52 показати роботу алгоритму.

Синтезувати керуючий автомат з програмованою логікою (вертикальне кодування, одно-адресне поле).

Виконати контроль операції віднімання по модулю 11 (кодовий).

Вступ

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

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

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

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

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

Розробка алгоритму

Стосовно двійкової системи числення найбільше відомі такі основні способи виконання операції множення:

I) множення починаючи з молодших розрядів множника:

2) множення починаючи зі старших розрядів множника:

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

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

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

А=0, B=0,.

Звідси

(1).

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

Метод 2. Нехай - множене і , — множник.

Множник можна легко перетворити, використовуючи метод Горнера:

. Тоді

(2)

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

Метод 3. Нехай — множене і - множник.

Множник, використовуючи метод Горнера, можна записати так:

.

В такому випадку

,

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

Метод 4 Нехай — множене і - множник

Якщо множник В записати за методом Горнера

,

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

Таким чином, для реалізації операції множення необхідно мати суматор, регістри для зберігання множеного і множника і схему аналізу розрядів множника. Суматор і регістри повинні мати кола зсуву вмісту в ту чи іншу сторону відповідно до ухваленого методу множення.

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

Для множення чисел у прямому коді з молодших розрядів з пропуском тактів додавання знак результату і числове значення отримуються окремо. Для визначення знаку результату знакові розряди множників складаються по модулю 2 і результат записується в знаковий розряд регістра результату.

Множення виконується з молодших розрядів, тому будем аналізувати молодший розряд множника РгВ[15] - якщо він дорівнює 1, то додаємо до вмісту суматора регістр множеного РгА; якщо РгВ[0] дорівнює 0, то пропускаємо такт додавання (звідки і назва методу). В обох випадках виконуємо:

зсув регістра РгВ на 1 розряд вправо, щоб проаналізувати наступний розряд множника;

зсув суматора СМ на 1 розряд вправо.

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

Опишемо покроково наш алгоритм.

1.2 Розробка алгоритму

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

Отримуємо з шини даних значення мантиси і порядку чиса А: РгАм: =Швх, РгАп: =Швх.

Отримуємо з шини даних значення мантиси і порядку чиса В: РгВм: =Швх, РгВп: =Швх.

Додаємо порядки СМп: =РгВм+РгАп

Присвоюємо суматору СМ значення 0 і в лічильник заносимо число кількості тактів множення Ліч: =16.

Якщо множник РгА від'ємний, то додаємо поправку СМ: =СМ+(не) РгА.

Аналізуємо старший розряд числа В (РгВ[1]), якщо він дорівнює 0, то переходимо до пункту 8, інакше до суматора СМ додаємо число А.

Виконуємо зсув на один розряд вліво суматора СМ і регістру РгВ, вміст лічильника зменшуємо на 1 і переходимо в пункт. 9 нашого алгоритму.

Аналізуємо розряд РгВ[2] - якщо він дорівнює 1, то переходимо до пункту 7, інакше виконуємо зсув на два розряди вправо суматора СМ і регістру РгВ. Вміст лічильника зменшуємо на 2.

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

Якщо знакові розряди СМм не рівні між собою, то виконуємо нормалізацію СМм: =L (1, СМм), СМп: =СМп+[-1] доп

Видаємо результат СМм і СМп на шину даних.

1.2 Розробка операційного автомату

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

Вхідні дані - множене і множник, які надходять в пристрій через шину вхідних даних ШДвх; результат — добуток видається з пристрою через шину вихідних даних ШДвих.

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

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

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

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

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

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

Для операційного автомату визначимо:

Функції входів:

Y1: РгАм: =Шд вх

Y2: РгАп: =Шд вх

Y3: РгВм: =Шд вх

Y4: РгВп: =Шд вх

Y5: СМм: =0

Y6: СМп: =0

Y7: Ліч: =8

Y8: СМп: =СМп+РгАп

Y9: СМп: =СМп+РгВп

Y10: СМм: =СМм+(не) РгАм

Y11: СМм:=СМм+РгАм

Y12: РгВм: =L1РгВм

Y13: СМм: =L1СМм

Y14: Ліч: = Ліч — 1

Y15: РгВм: =L2РгВм

Y16: СМм:=L2СМм

Y17: Ліч: = Ліч — 2

Y18: СМп:=СМп+[-1]доп

Y19: Шд вих: =СМм

Y20: Шд вих: =СМп

Функції виходів:

X1: РгВ [15]=1

X2: РгВ [14]=1

X3: Ліч: =Ліч-1

X4: РгВ > 0

X5: СМм[0]= СМм[1].

1.3 Приклад виконання операції множення

Виконаємо множення за розробленим алгоритмом для заданих чисел.

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

А = 41,3210 = 101 001. 101 000 1112 = 0,1 010 010 101 000 1112 26

В = -14,5310 = -1110. 100 001 010 0012 = -0,1 110 100 001 010 0012 24

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

РгА=00,1 010 010 101 000 111

РгВ=11,1 011 110 101 111

Також при введенні поправки будемо використовувати код

(не) А=11,101 101 010 111 000

Додамо порядки:

110

100

1 0102 = 1010

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

Таблиця 1

СМм

РгВм

Виконувані операції

0

1 011 110 101 111

РгВм[1]=0; РгВм[12]=0;

РгВм: =L2РгВм; CMм: =L2СМм

0

1 011 110 101 111

РгВм[1]=0; РгВм[12]=1;

РгВ: =R1РгВм; CM: =R1СМм

0

1 010 010 101 000 111

1 010 010 101 000 111

1 011 110 101 111

РгВм[15]=1;

CMм: =CMм+РгАм

РгВ: =L1РгВм; CM: =L1СМм

10 100 101 010 001 110

11 110 101 111

РгВм[1]=0; РгВм[12]=1;

РгВ: =R1РгВм; CM: =R1СМм

10 100 101 010 001 110

1 010 010 101 000 111

110 011 101 001 100 016

11 110 101 111

РгВм[15]=1;

CMм: =CMм+РгАм

РгВ: =L1РгВм; CM: =L1СМм

1 100 111 010 011 000 064

1 010 010 101 000 111

1 110 001 101 000 001 152

1 110 101 111

РгВм[15]=1;

CMм: =CMм+РгАм

РгВ: =L1РгВм; CM: =L1СМм

11 100 011 010 000 011 264

1 010 010 101 000 111

11 101 101 100 101 099 520

110 101 111

РгВм[15]=1;

CMм: =CMм+РгАм

РгВ: =L1РгВм; CM: =L1СМм

111 011 011 001 010 995 200

1 010 010 101 000 111

111 100 101 100 000 002 048

10 101 111

РгВм[15]=1;

CMм: =CMм+РгАм

РгВ: =L1РгВм; CM: =L1СМм

1 111 001 010 999 999 987 712

101 111

РгВм[1]=0; РгВм[12]=1;

РгВ: =R1РгВм; CM: =R1СМм

11 110 010 109 999 999 614 976

1 010 010 101 000 111

11 110 100 000 010 101 850 112

101 111

РгВм[15]=1;

CMм: =CMм+РгАм

РгВ: =L1РгВм; CM: =L1СМм

111 101 000 000 101 018 501 120

1 111

РгВм[1]=0; РгВм[12]=1;

РгВ: =R1РгВм; CM: =R1СМм

1 111 010 000 001 010 084 347 904

1 010 010 101 000 111

1 111 010 001 011 101 029 892 096

1111

РгВм[15]=1;

CMм: =CMм+РгАм

РгВ: =L1РгВм; CM: =L1СМм

11 110 100 010 111 010 298 920 960

1 010 010 101 000 111

11 110 100 100 001 100 243 927 040

111

РгВм[15]=1;

CMм: =CMм+РгАм

РгВ: =L1РгВм; CM: =L1СМм

111 101 001 000 011 006 734 237 696

1 010 010 101 000 111

111 101 001 001 101 103 793 700 864

11

РгВм[15]=1;

CMм: =CMм+РгАм

РгВ: =L1РгВм; CM: =L1СМм

1 111 010 010 011 011 037 937 008 640

1 010 010 101 000 111

1 111 010 010 100 101 166 600 814 592

1

РгВм[15]=1;

CMм: =CMм+РгАм

РгВ: =L1РгВм; CM: =L1СМм

Оскільки В-число від'ємне, то до отриманого результату слід додати поправку: СМ: =СМ+(не) РгА,

00,1 111 010 010 100 101 166 600 814 592

11,1 011 010 101 110 001 123 618 136 784 896

11,1 101 010 000 000 110 048 769 902 379 008

Отримано результат в доповняльному коді. Переведемо його в прямий код і в десяткову систему числення:

Спр=-0,11 010 100 000 001 100 206 224 047 079 42410

С= -1 001 010 111,111001010001101111111

С10= -599,894 958

Перевірка результату на калькуляторі показує вірний результат:

АВ = 41,32(-14,52)= -599,9664

Похибка обчислення: = | 599,894 958 — 599,9664| = 0,71 442

=(/ 599,9664) 100% =0,0119%

Отже, похибка незначна.

2. Синтез керуючого автомату

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

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

В залежності від способу визначення вихідного сигналу в керуючих автоматах розрізняють три типи абстрактних автоматів: автомат Мілі, автомат Мура, С-автомат. В абстрактному автоматі Мілі функція виходів задає відображення (XxS) Y. В абстрактному автоматі Мура функція виходів задає відображення SY. В абстрактному С-автоматі вводяться дві функції виходів 1 і 2, що задають відображення (XxS) Y1 і SY2 відповідно. При цьому алфавіт виходів С-автомата, Y=Y1=Y2 або Y=Y1Y2.

Адресація мікрокоманд

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

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

Після виконання мікрокоманди з адресою, А може виникнути необхідність в переході до мікрокоманди з адреси В = А + 1. Перехід може бути безумовним або залежати від поточного значення х. Умовні переходи реалізуються слідуючим чином: якщо х = 0, то виконується наступна мікрооперація з адресою (А + 1); якщо х = 1, то наступною виконується мікрокоманда з адресою В. Для реалізації умовних переходів в мікрокоманду вводиться адресна часна частина, яка складається з полів Х та В.

Скоротити довжину мікрокоманд дозволяє застосування вертикального мікропрограмування при якому кожна мікрооперація кодується] log2 n [- розрядним кодом де n — загальна кількість мікрооперацій. Таке кодування накладає обмеження на методи виконання операцій, а саме не повинно бути операцій що потребують одночасного виконання ряда мікрооперацій. В тих випадках коли це обмеження виконати неможливо треба використовувати складні мікрооперації що складаються з сукупності простих.

В цьому випадку мікрооперація матиме вигляд:

Де Y-поле мікрооперацій, Х-поле умови переходу А-адресна частина.

Позначивши мікрооперацію — у логічну умову — х адресу — А проведемо розмітку алгоритму. Символом «* «позначимо фіктивні логічні умови що забезпечують відповідні безумовні переходи. Тому об'єднаємо мікрооперації які можна виконувати одночасно.

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

Таблиця 2. Кодування мікрооперацій

Y

Код Y

Y1, Y2

0001

Y3, Y4

0010

Y5, Y6, Y7

0011

Y8

0100

Y9

0101

Y10

0110

Y11

0111

Y12, Y14

1000

Y13

1001

Y15, Y16, Y17

1010

Y18

1011

Y19, Y20

1100

Закодуємо умови переходу Х:

Таблиця 3. Кодування умов переходу

Х

Код

Х0

000

Х1

001

Х2

010

Х3

011

Х4

100

Х5

101

Безумовний

перехід

111

Розмітку алгоритма показано на рисунку в додатку В. Автомат працює за мікропрограмою яка записана в постійному запам’ятовуючому пристрої і наведена в таблиці 4.

Таблиця 4. Карта програмування ПЗП

Адреса

Y

Х

А0

0

0001

000

*

1

0010

000

*

10

0011

000

*

11

0100

000

*

100

0101

001

110

101

0110

000

*

110

0000

010

111

0111

000

*

1 000

1000

000

*

1 001

1001

000

1 111

1 010

0000

100

110

1 011

0000

101

1 101

1 100

1001

000

*

1 101

1011

000

*

1 110

1100

111

0

1 111

0000

011

1 000

10 000

1010

111

1 010

3. Розробка методики контролю операції множення

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

Контрольний код r заданого числа утворюється додаванням цифр числа по обраному модулю р:

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

При використанні операції віднімання контрольний код результату С=А-В визначається так:

де S — кількість зайомів з попередньої групи, q — основа системи числення, в якій виконуються згортки (в нашому випадку q=16).

Ми виконаємо операцію віднімання на суматорі доповняльного коду, тому замінимо операцію віднімання операцією додаванням в цьому випадку:

де L — кількість переносів в наступну групу,

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

А=00,1 010 010 101 000 111

B=00,1 110 100 001 010 001

Вдоп=11,1 011 110 101 111

rA = 1 010 010 101 000 111 = 4 (mod 11)

rB = 1 011 110 101 111=0 (mod 11)

Виконаємо віднімання, А і В (додамо, А і Вдоп):

00,1 010 010 101 000 111

11,1 011 110 101 111

11,1 011 110 011 110 110

При цьому L = 1.

Отже, АВ = 11,1 011 110 011 110 110

rА-В = 1 011 110 011 110 110 = 0 (mod 11)

Контрольний код

Так як, то віднімання виконано вірно.

Припустимо, що А-В = 1 011 110 011 110 111.

Тоді rА-В = 1 011 110 011 110 111 = 1 (mod 3);

; Отримали, що свідчить про невірно виконану операцію віднімання.

Висновки

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

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

Список літератури

Каган Б.М. «Электронные вычислительные машины и системы». Москва Энергоатомиздат 1991, 592 с.

Лужецький В.А. «Конспект лекцій по прикладній теорії цифрових автоматів».

Лужецький В.А., Білан С.М., Квітка М.А. «Прикладна теорія цифрових автоматів». Методичні вказівки. — Вінниця, ВДТУ, 1997 — 56 с. Укр. мовою.

Лысиков Б.Г. «Арифметические и логические основы цифровых автоматов». — Мн. :Высшая школа, 1980 г.

Савельев А.Я. «Прикладная теория цифровых автоматов». Москва Высшая школа, 269 с.

Самофалов К.Г., Корнейчук В. И., Тарасенко В. П. «Цифровые ЭВМ». — Киев: Высшая школа, 1989 г.

алгоритм множення автомат плаваючий

ПоказатьСвернуть
Заполнить форму текущей работой