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

Метод 3. Множник записується таким чином

B = 2-n(bn + bn-121 + bn-222 + … +b12n-1).

С = AB = 2-n[bn0,a1a2…an + bn-1(210,a1a2…an) + (1.3)+ bn(220,a1a2…an) + … + b1(2n-10,a1a2…an)] .

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

Структурна схема пристрою що реалізує цей метод наведена на рис. 1в.

Метод 4. Якщо множник записати по схемі Горнера

B = 2-n(…((b121 + b2)21 + … + bn-1)21 + bn

C = AB = 2-n(…((b10,a1a2…an)21 + b20,a1a2…an)21 + … + (1.4)+ bn-10,a1a2…an)21 + bn0,a1a2…an).

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

Структурна схема пристрою що реалізує цей метод наведена на рис. 1

Другий варіант має найменші апаратурні витрати перший та третій – найменший час множення.

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

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

Якщо множник від’ємний то добуток чисел на суматорі оберненого коду отримують додаванням поправок [A]об та [A]об2-n до добутку обернених кодів співмножників.[А.Я. Савельєв «Прикладная теория цифровых автоматов» М.: Высш. шк.1987]

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

1.1.2 Множення чисел з фіксованою комою

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

Множення двох (n - 1) розрядних чисел може мати 2(n - 1) значущих розрядів.

Тому при операції множення цілих чисел необхідно побачити можливість формування в АЛП добутку, котрий має двохкратну в порівнянні із співмножниками довжину. В ЕОМ, в яких числа з фіксованою комою є дробами, молодші (n - 1) розрядів множення часто відкидаються (при відкиданні може виконуватись операція округлення добутку). Для виконання множення АЛП повинен мати регістри множеного, множника та схеми формування суми часткових добутків - суматор часткових добутків, в якому шляхом відповідної організації передач виконується послідовне додавання часткових добутків.

Операція множення складається з (n - 1) циклів. В кожному циклі аналізується слідуюча цифра множника, якщо це 1, то до суми часткових добутків додається множене, в іншому випадку додавання не виконується. Цикл закінчується з зсувом множеного відносно суми часткових добутків або з зсувом суми часткових добутків відносно нерухомого множеного.

1.1.3 Прискорені методи виконання операції множення

Прискорення операції множення дозволяє істотно підвищити продуктивність ЦОМ, оскільки приблизно 70% свого часу вони витрачають на виконання цієї операції. Аналізуючи (3.2) - (3.5), можна намітити такі шляхи скорочення часу множення: зменшення часу додавання і зсуву кодів; зменшення кількості додавань і кількості зсувів кодів.

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

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

Відомі на цей час методи прискорення множення розподілені на дві великі групи: логічні й апаратні.

Логічними методами прискорення множення називають такі методи, реалізація яких не вимагає змін основної структури арифметичних кіл пристрою для множення (див. рис. 3.1 - 3.5), а прискорення досягається тільки за рахунок ускладнення схеми керування цим пристроєм. Стосовно пристроїв для множення паралельних кодів ознакою того, що ми маємо справу з логічним методом прискорення множення, є незалежність кількості додаткової апаратури (у порівнянні з вихідною схемою) від кількості розрядів співмножників.

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

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

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

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

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