212

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

6.4.2. Додавання двійкових чисел із знаками

Як ми вже бачили в попередньому розділі, існує чотири методи представлення п-роз-рядних чисел із знаками: в прямому, оберненому та доповняльному кодах, а також із зміщенням. В прямому коді старший розряд представляє знак числа, а наступні n-1 роз­ряди представляють модуль числа. В оберненому та доповняльному кодах додатні числа мають те ж саме представлення, що і в прямому. Представлення ж від'ємних чисел тут є іншим. В оберненому коді від'ємні числа представляються шляхом інверсії їх розря­дів, а в доповняльному коді крім того до молодшого розряду оберненого коду додається одиниця. В представленні із зміщенням всі числа, як додатні так і від'ємні, додаються до зміщення і отримані суми представляються як звичайні числа без знаків. Так від'ємне число k буде представлене як k + b > = 0, де b - зміщення. Типовим значенням зміщення вибирається число 2ⁿ- 1.

Приклад: використовуючії чотирирозрядну сітку (n = 4), представимо в описаних вище кодах число k = - 3 (або в двійковій системі k = - 011₂). В прямому коді k = 1011₂, причому старший розряд є знаковий. В оберненому коді k =1100₂ , а в доповняльному коді k = 1101₂. Для системи із зміщенням, коли зміщення Ь=2ⁿ - 1=8, маємо k = 0101₂.

Додавання чисел, представлених в прямому коді, вимагає проведення початкового аналізу знаків чисел. Якщо знаки однакові, то модулі чисел додаються, а результату при­своюється їх знак до проведення додавання. Якщо ж їх знаки різні, то модулі чисел відні­маються, а результату присвоюється знак більшого за модулем числа, або знак "+", якщо модулі чисел є рівними.

Додавання чисел, представлених в оберненому та прямому кодах, не залежить від 'їх знаків і проводиться так само як додавання додатних чисел в прямому коді з тією різ­ницею, що при додаванні чисел, представлених в оберненому коді, необхідно перенос з старшого розряду подавати на вхід переносу молодшого розряду. Представлення в до­повняльному коді використовується значно ширше, ніж в оберненому, оскільки при до­даванні чисел тут перенос із старшого розряду просто ігнорується. Наприклад, додавши 5+(-2) в доповняльному коді маємо 0101₂ + 1110₂ = 0011₂. Тобто отриманий правильний результат 3 при ігноруванні переносом із старшого розряду. Якщо ж додати ті ж самі числа в оберненому коді отримаємо 0101₂ + 1101₂ + 1 = 0011₂. Тобто також отриманий правильний результат 3 при врахуванні переносу із старшого розряду. Цей перенос називається циклічним. Додавання до отриманої суми одиниці циклічного переносу не викликає повторного циклічного переносу Наведений приклад наглядно ілюструє рис. 6.10.

---

213

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

При виконанні додавання двійкових чисел можливе переповнення, коли отримана сума перевищує діапазон представлення чисел, тобто коли вона виходить за межі роз­рядної сітки. Для інформування програміста про отримання неправильного результа­ту переповнення повинно бути зафіксованим. Для фіксації переповнення аналізуються знакові розряди чисел. Переповнення виникає тільки при додаванні чисел з однаковими знаками і виявити його можна порівнюючи знаки суми і доданків. При переповненні знак суми S не дорівнює знакам доданків х та у, тобто Signx = Signy =/ SignS.

Для спрощення фіксування наявності переповнення використовуються так звані модифіковані коди з двома знаковими розрядами (тобто 0 представляється як 00, а 1 представляється як 11). Неоднаковість цих розрядів після виконання операції означає наявність переповнення, як це показано на прикладах на рис. 6.11.

В першому прикладі відбулося переповнення, оскільки два перші розряди, які пред­ставляють знак, не є однаковими.

6.4.3. Віднімання двійкових чисел

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

S_i= х_i XOR у_i XOR b_i

b_i+1=(x_i AND у_i) OR (x_i-AND b_i) OR (у_i AND b_i)

b₀=0

Ці формули отримані з наступної таблиці істинності (табл. 6.6).

---

214

Таблиця 6.6

bi	Xi	уi	Si	сі+1
0	0	0	0	0
0	0	1	1	1
0	1	0	1	0
0	1	1	0	0
1	0	0	1	1
1	0	1	0	1
1	1	0	0	0
1	1	1	1	1

Де: Si. - і-й розряд різниці, хi, уi - і-ті розряди зменшуваного та від'ємника відповідно, bi. - розряд запозичення.

Приклади виконання операції віднімання двійкових чисел без знаків приведено на рис. 6.12.

Коли числа представлені в оберненому або доповняльному кодах, то можна використа­ти інший метод: потрібно змінити знак від'ємника, всі його розряди потрібно інверту­вати, а для доповняльного коду, крім того, збільшити від'ємник на одиницю молодшого розряду, і тоді просто додати до зменшуваного отримане число S = х + (NOT(y) + 1 м.р.).

6,4.4. Множення двійкових чисел

Множення може проводитись в прямому, оберненому та доповняльному кодах. Знак результату операції множення можна визначати окремо. Для цього використовується операція XOR над знаковими розрядами співмножників відповідно до табл. 6.7.

Таблиця 6.7

■ знак Х	знак Y	Знак результату
0	0	0
0	1	1
1	0	1
_ 1	1	0

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

При виконанні множення операндів, представлених в прямому коді, їх модулі мно­жаться як цілі двійкові числа без знаків, або як дробові числа без знаків, оскільки про-

---

215

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

6.4.4.7. Множення цілих двійкових чисел без знаків

Якщо позначити множене буквою X, а множник буквою Y, причому представити Y у вигляді суми його двійкових розрядів

то результат Z множення двох цілих двійкових чисел без знаків визначається з ви­разу:

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

Лінійка операторів AND формує п n-розрядних результатів логічного множення множеного на розряди множника, які зсуваються праворуч на R. (і = 1, 2, ..., п-1) роз­рядів. Ці результати називаються частковими добутками. Оператор із знаком додавання тут означає багатомісну операцію додавання часткових добутків.

---

216

6.4.4.2. Багатомісна операція додавання часткових добутків

Алгоритм виконання багатомісної операції додавання часткових добутків залежить від типу використовуваних операторів додавання. Це можуть бути зокрема оператори попарного n-розрядного додавання двох чисел, оператори попарного однорозрядного додавання двох чисел, оператори багатомісного паралельного додавання чисел і т. д. Якщо використовувати оператори попарного n-розрядного додавання двох чисел, тобто двох часткових добутків, то можуть бути запропоновані наступні алгоритми:

" алгоритм послідовного попарного додавання часткових добутків, отриманих по­чинаючи з аналізу молодших розрядів множника;

• алгоритм послідовного попарного додавання часткових добутків, отриманих по­чинаючи з аналізу старших розрядів множника;

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

Граф алгоритму послідовного попарного додавання часткових добутків, отриманих починаючи з аналізу молодших розрядів множника, показаний на рис. 6.14.

Тут послідовно з'єднані оператори двомісного (попарного) додавання (ОДД), причо­му часткові добутки подаються для додавання із зміщенням на і (L1,L2, ..,Li, L_n-1) розря­дів ліворуч. Молодший розряд результату кожного і-го ОДД (ОДД,, ОДД₂,..., ОДД_n-1) є відповідним розрядом добутку Zi, а нульовий розряд добутку є рівним молодшому роз­ряду першого часткового добутку. Розряди добутку від Z_2n-1-го до Z_n-1-го отримуються з виходів (nІ)-го оператора ОДД, починаючи з другого виходу.

Подібним до розглянутого є алгоритм послідовного попарного додавання часткових добутків, отриманих починаючи з аналізу старших розрядів множника, граф якого по­казано на ис. 6.15.

---

Смотрите также файлы

• Екологія посібник.doc

• LR3_[5405].doc

• Питання до модуля 1 з АК.doc

• Питання до 1 модуля з КЕ.doc

• ДБН В.3.2-2-2009_Жил_здания_реконст_кап_ремонт.doc