Особливості арифметико-логічних пристроїв АЛП з двійково-десятковими кодами ДДК при обчисленні

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

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

Приклад:

37 =

АЛП, збудоване для обробки ДДК базується на традиційному двійковому суматорі з виконанням додаткових коригувальних дій. Основна ідея коригувальних механізмів полягає в тому, що при обробці десяткових розрядів переноси в суміжні розряди виникають при значеннях, що перевищують число 10, а при додаванні ДДК перенесення в суміжний розряд виникає при перевищенні в розряді 16. Одиницею даних при обробці ДДК є т. зв. тетрада, що представляє собою 4 послідовних біта. Для компенсації спотворень, що виникають при додаванні ДДК, формують операнд, кожна цифра якого має надлишок, рівний 6. У такому разі:

z [i] = x [i] + y [i] + P [i]

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

z [i] = x [i] + y [i] + P [i] -10

P [i +1] = 1

Формується сигнал переносу в наступний розряд. Тому при додаванні операндів з надлишком в (х6) отримуємо:

zt = x6 + Y

У такому випадку в i-тому розряді zt буде таке значення:

тоді zt $ 16. У такому випадку в i-тому розряді zr буде:

z r [i] = 6 + x [i] + y [i] + P [i] -16 = x [i] + y [i] + P [i] -10 = z [i]

P [i +1] = 1-перенесення в наступний розряд

При отриманні псевдосумми zt виявляється ситуація, коли розряди (тетради), з яких було перенесення в старший розряд, містять правильне значення цифри цього розряду. Розряди, з яких не було переносів в старший розряд, містять цифру з надлишком, рівним 6. Тому отримане значення вимагає коректування. Вона може бути проведена шляхом вирахування з розрядів, з яких не було переносів, значення 6. На практиці, замість вирахування до цих розрядів додають значення дорівнює 10 і блокують міжтетрадного перенесення:

Спрощена схема АЛП

Алгоритм складання ДДК

РГВ приймає перший операнд, потім у РДА формують чіслосо значенням 6 у кожному тетраде.

У РгСм формується код першого операнда з надлишком 6, який приймається в РГВ.

У РДА приймається другий операнд. Суматор формує значення zr = x6 + y. При цьому тетради, з яких не виникли сигнали перенесення, фіксуються.

У РДА формується операнд, в тетрадах якого розміщено число 10, якщо у відповідних тетрадах zr не виникало сигнал переносу. zr з РгСм передається в РГВ.

Коригування zr шляхом додавання операнда з 10 в РДА з блокуванням міжтетрадного переносів. Отриманий результат передається на вихідну шину даних.

Для вирахування ДДК виробляються такі дії:

Другий операнд Y перетворять у зворотний код інвертуванням кожного біта, при цьому виходить зворотний код з надлишком 6, тому що кожна тетрада є доповненням до 15.

Виконується підсумовування . Якщо зі старшої тетради zr при формуванні було перенесення, то отримано позитивне значення результату. Якщо перенесення не було зі старшої тетради, то результат є негативним у додатковому коді. При цьому додатковий код інвертується і додається 1 до молодшого розряду. Отримане значення вимагає коректування. Якщо при отриманні zr з тетради був перенесення, то в наслідку до цієї тетраде треба додати 10 з блокуванням міжтетрадного переносів.

Опції з ДДК зі знаками зводяться до визначення реальних опцій, які потім виконуються за наведеними схемами.

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

Розподіл ДДК. Виробляється шляхом багаторазового вирахування дільника з поточного значення часткових різниць, які спочатку рівні значенням діленого, послідовним зсувом часткових різниць вліво по розрядній сітці. Багаторазове віднімання виконує до отримання негативного результату. Кількість вирахувань до отримання негативного результату відповідає черговому цифрі приватного. У цілому, опція схожа на традиційний поділ «куточком».

Методи прискорення операції множення. Апаратурні методи прискорення вимагають додаткових витрат, пропорційних кількості зворотних розрядів. Як приклад до апартний методам операції (*) - включення додаткових ланцюгів зсуву можливо за 1 такт алгоритму синхронізувати виконання зсуву на декількох розрядах. Іншим методом є роботи суматорів, а також суміщення в часі зсувних операцій та операцій підсумовування

Логічні методи прискорення операції множення вимагають зміни центрального управління. Основним джерелом підвищення ефективності є зменшення кол-ва складань виконуються в процесі отримання S приватних творів. До логічним так само можна віднести методи дозволяють аналізувати кілька розрядів множників одночасно і виконати відповідні зміни суми приватних творів.

Приклад лот. методу

0151413121100 = 26 -21;

k +1 k k-1 0

| | | |

0 1 1 1 0 1 1 1 ... ....

Замість 2-Х вирахувань виконується одне. Якщо ... 0 1к 0 в (к) виконується тільки одне додавання

Формалізація цього підходу може бути зроблена так:

di = (bi + bi-1) * di-1

Si = di * bi +1

bi-логічна змінна визначає необхідність виконання арифметичної операції для i-того розряду множника

Si-визначає знак здійсненним операції. Якщо Si = 0, то виконується складання поточної суми приватного твори і множимо. Якщо Si = 1 то виконується "-" віднімання множимо із суми приват. Творів

Це правило - правило Лемана. Воно при самих несприятливих комбінаціях розрядів множників вдвічі скорочує кількість операцій підсумовування. Середнє значення прискорення * 3.

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

При аналізі 2-х розрядів множника можна запропонувати слід послідовність дій:

Якщо два розряди 00. то виконується тільки зрушення S приватного твори (далі S ч.п.) вправо на 2 розряди

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

Якщо 10 то до S ч.п добовляют подвоєний множимое і S ч.п зсувається вправо на два розряди, якщо 11 то віднімаємо множимое і на спеціальному тригері запам'ятовується ситуація про необхідність корекції при аналіз слід 2-х розрядів. Далі S ч.п зсувається вправо на два розряди, слід пара розряду множника вже розглядається як повів на 1.

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

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

АЛП для реалізації операції ділення. Операція / є зворотним по отн до операції *, тому загальна структура операції полягає в послідовності віднімання значення дільника з діленого і зрушення.

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

Розглянути. осн. вимоги: Приватне Z як рез-т поділу діленого X на дільник Y, Z = X / Y. Х представляється у форматі подвійного слова, тобто займає (2n-1) розрядів, Z і Y представлені у форматі одинарного слова, тобто займають (n-1) розрядів. Тому | Z | <2n-1. Для того, щоб приватне розміщувалося у форматі подвійного слова необхідно | X '| - | Y | <0, де | X' | = | X | -2 - (n +1). В іншому випадку приватне не може бути розміщено в форматі одного слова. Тому операція ділення нездійсненна. Для повірки цієї умови виконаємо пробне віднімання. Для цього вирівнюють ділене і дільник так, щоб молодший розряд дільника був під (n-1)-м розрядом делімого.еслі віднімання дасть негативний результат, то операція триває. По суті справи ми реалізували традиційний поділ «у стовпчик». Т.ч. для виконання операції ділення необхідно або зрушувати вправо дільник по розрядній сітці, починаючи зі старших розрядів в процесі отримання часткових різниць. При цьому ділене залишається нерухомим. Або можна зрушувати вліво значення діленого при нерухомому дільнику. У процесі отримання часткових різниць чергова цифра приватного визначається знаком поточного значення часткових різниць. Виходячи з цього може бути побудовано 2 варіанти АЛП. (СХЕМА)

Дана схема припускає використання подвійний розрядності всіх елементів. При цьому ділене і послід. значення часткових різниць нерухомі, а зсуваються вправо компоненти дільника. Початкове положення дільника старші розряди регістра РГУ, а потім дільник à з результаті кожної ітерації. Часткові різниці виходять за допомогою суматора, на один вхід якого подається ділене, а на іншій-зворотний код дільника. Доп. код виходить подсуммірованіем 1 до молодшого розряду суматора. Цифри приватного формують за знаком отриманих часткових різниць, тобто за нульовим розряду суматора. Цифри заносяться в молодший розряд регістра РгZ, які передаються із зсувом вліво в регістр Z ', а далі прямо в регістр Z. Основним недоліком цієї схеми є використання подвійний розрядності всіх компонентів. На практиці набула поширення схема з нерухомим дільником і зсувається вліво значенням часткових різниць. (СХЕМА).

У Рг1 розміщується дільник, а в РГВ і Рг2-ділене. В тригерах знака зберігаються знаки операндів. Регістр 3 використовується для розміщення цифр приватного. Загальна схема алгоритму:

1.Берутся модулі від операндів, які розміщуються в регістрах.

2.Делімое ß на 1 розряд, для цього регістр А обнуляється і вміст передається в регістр суматора зі зрушенням ß на один разряд.В звільнився молодший розряд суматора записується молодший розряд з регістра 2. Після цього вміст регістра суматора записується в регістр В. одночасно розряди регістра 2, крім старшого, передаються в Рг2 'зі зрушенням ß на 1 розряд і потім в регістр 2.

3.виполняется отримання значення часткових різниць шляхом складання вмісту регістра В і зворотного коду дільника з регістра А. Виконується додавання 1 до молодшого розряду суматора для отримання додаткового коду дільника.

4.Якщо 0-й розряд регістра суматора> 0, то цифра Zi, що заносяться в молодший розряд регістра 3 '= 1. Вміст регістра 3 'передається в регістр 3. При черговому одержанні часткових (поточних?) Різниць вміст регістра 3 передається в 3 'зі зрушенням ß на 1 розряд.

Лічильник циклів містить кількість цифрових розрядів приватного. Після отримання чергової цифри приватного значення лічильника зменшується на 1. При досягненні 0 операція закінчується. Якщо в процесі отримання часткових різниць поточне значення в регістрі суматора <0, то як цифри Zi заноситься 0, а попереднє значення часткових різниць відновлюється (воно зберігалось у регістрі В) і зсувається ß на 1 розряд; з занесенням з регістра 2 черговий цифри діленого в молодший розряд регістра суматора при обнулення регістра А. Потім здійснюється передача отриманого значення поточної різниці в регістр В.

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

Розглянутий алгоритм передбачає при отриманні значення <0 часткового залишку його відновлення до попереднього значення. Це вимагає додаткового проміжку часу. Тому на практиці використовується алгоритм ділення без відновлення залишку зі зсувним значенням часткової різниці і нерухомим дільником. Алгоритм:

1.Берутся модулі від діленого і дільника.

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

3.Значеніе часткового залишку подвоюється шляхом зсуву ß на 1 розряд.

4.Із значення часткових залишків віднімається дільник; якщо частковий залишок> 0!! то додається дільник якщо <0!!

5.Ціфра приватного покладається = 1, якщо після виконання попереднього кроку часткові залишки> = 0 і 0 у противному випадку.

6.Пункти 3,4,5 виконуються до отримання всіх цифр приватного.

7.Якщо в кінці циклу частковий залишок <0 то він відновлюється шляхом додавання дільника.

Знак приватного = 0, якщо знаки діленого і дільника збігаються, і 1 якщо вони різні.

Зміст ділення без відновлення залишків полягає в тому, що при зсуві ß значення часткового залишку а подвоюється 2а, тому віднімання дільника еквівалентно 2а-в = 2 (а-в) + в його додаванню на наступному кроці.

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

Якщо x> 0, ay <0 то приватне слід збільшити на 1

Якщо x <0, ay> 0 то приватне слід збільшити на 1 у разі якщо залишок = 0

Якщо x <0, ay <0 то приватне слід збільшити на 1еслі залишок = 0.

Побудова АЛП для виконання операції множення чисел з плаваючою точкою

Правила множення:

X = ± qx * SPx

Y = ± qy * SPy

Z = X * Y = ± qx * qy * SPx + Py = ± qz * SPz

To qz = qx * qy; Pz = Px + Py;

Відповідно до даних виразами мантиса твори дорівнює добутку мантис співмножників.

Результат нормалізується. Знаку результату відповідає:

+ Якщо мантиси співмножників мають однакові знаки;

- Якщо мантиси співмножників мають різні знаки.

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

Р [0] = 0; P [1] = 0 в якості результату операції приймається 0

Р [0] = 0; P [1] = 1

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

Р [0] = 1; P [1] = 0

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

Р [0] = 1; P [1] = 1

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

Загальна схема АЛП для операції множення

У Рг1 розміщується множимое, в Рг2-множник. На початку для складання зміщених порядків в РДА і РГВ передаються тільки біти зміщених порядків. Біти мантис в РДА і РГВ обнуляються. Відповідно обнуляються і регістри знаків. Самі знаки пишуться в ТрЗн. Після розміщення порядків в РДА і РГВ суматор формує код суми зміщених порядків. Він розміщується у відповідному полі РгСм.

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

Після цього йде твір мантис. Для цього:

У РДА йде код мантиси Х (8-31 розр.). РГВ використовується для зберігання поточного значення суми часткових творів. Йде аналіз молодших розрядів мантиси Y в Рг2 і додавання або не додавання до поточного значення суми часткових творів мантиси Х.

Результат у вигляді суми часткових творів передається в РгСм із зсувом управо і наступною передачею у РГВ.

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

Відмінність даного множення мантис від множення мантис цілих чисел в тому, що мантиса твору має той самий розмір, що і мантиси співмножників. Після закінчення множення мантис результат нормалізується (можливо змінюється значення Сч1). Результат Сч1 йде в поле для зміщеного порядку.