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

Завдання

Розробити машинний алгоритм операції множення в доповняльному коді з пропуском тактів додавання в двійковій системі числення з старших розрядів чисел, представлених у формі з плаваючою комою (розрядність мантиси — 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,32₁₀ = 101 001.0101000111₂ = 0,1 010 010 101 000 111₂ 2⁶

В = -14,53₁₀ = -1110.100 001 010 001₂ = -0,1 110 100 001 010 001₂ 2⁴

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

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

РгВ=11,1 011 110 101 111

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

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

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

100

1 010₂ = 10₁₀

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

Таблиця 1

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

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 424¹⁰

С= -1 001 010 111,111001010001101111111

С₁₀= -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, то наступною виконується мікрокоманда з адресою В. Для реалізації умовних переходів в мікрокоманду вводиться адресна часна частина, яка складається з полів Х та В.

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

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

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

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

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

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

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

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

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

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

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

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

r_B = 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 г.

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