n=top>
C 6
C 5
C 4
Рисунок 1 - Схема пристрою для реалізації матричного методу
Елементи, складові кожен і-й стовпець матриці, підсумуємо за допомогою звичайних трехвходових двійкових суматорів. 3наченіе переносів з цих суматорів повинні бути доданками для (i +1)-гo стовпця. Це призведе до того, що в кожному (i +1)-м стовпці поява доданків відбуватиметься з запізненням за часом щодо i-гo стовпця. p> Схема пристрою для реалізації цього дерева спуску, яке являє собою одну з різновидів матричного алгоритму множення, представлена ​​на рис. 1. p> Для однорозрядних суматорів час утворення суми більше, ніж час освіти перенесення П„ п , тому найбільшу час спуску по дереву даного виду є Т уск = (n-1) (П„ смГ¬ + П„ n ); якщо тільки всі кон'юнкції виду a i b j надходять на дерево спуску одночасно. Цей час складається з спуску по найдовшій вертикалі, а потім послідовного розповсюдження переносу через суматори нижнього ряду аж до самого лівого. Розглянута структура дерева спуску не єдина Час спуску можна ще зменшити, перетворивши дерево узвозу. <В
5. Виконання операції ділення в ЕОМ
Операція поділу зустрічається порівняно рідко (Р = 0,02), однак, реалізація її по підпрограмі займає досить великий час. Тому в більшості сучасних ЕОМ поділ реалізується спеціальними операційними блоками. p> Ділення в ЕОМ, також як і множення, найпростіше виконується в прямому коді. Але на відміну від множення дробових чисел, де не може виникнути переповнення розрядної сітки, при діленні правильних дробів таке переповнення можливо у випадку, коли ділене більше дільника. Ознакою переповнення є поява цілої частини в приватному, що грубо спотворює результат.
Знак приватного при діленні визначається складанням за модулем 2 знакових розрядів діленого і дільника і присвоюється приватному наприкінці операції ділення.
Приватна визначається шляхом ділення модулів вихідних чисел. При цьому, щоб уникнути переповнення розрядної сітки має дотримуватися умова:
| А | <| В |
де А - ділене, В - дільник. Крім того: У В№ 0. p> Відомі два основних алгоритму виконання операції ділення:
- поділ з відновленням залишків;
- розподіл без відновлення залишків.
5.1 Ділення чисел з відновленням залишків
Нехай необхідно розділити А на В. Тоді частка від ділення
Y i = А/В = 0, у 1 у 2 у 3 ... у и -1 у и = у 1 2 -1 + у < sub> 2 2 -2 + у 3 2 -3 ... у и -1 2 -і -1 + у и 2 -і (1.1.)
При будь-якому значенні и повинно виконуватися нерівність:
0 ≤ А - ВY i ≤ В2 -і
тобто залишок від ділення повинен бути менше дільника, помноженого на 2 -і , або:
0 ≤ (А - В Y i ) 2 и ≤ В, позначимо (А - В Y i ) 2 и = R и і отримаємо:
0 ≤ R и ≤ В. (1.2)
При розподілі цифри приватного визначаються послідовно, починаючи зі старшого розряду. Припустимо, що в результаті виконання и циклів отримані старші І розряду приватного, тобто наближене значення приватного Y i . У наступному (і +1)-циклі буде отримано значення (і +1)-го розряду приватного. Вихідними даними для цього циклу є Y i і R и .
Цифра у и +1 може мати одне з двох значень:
1 або 0. Якщо у и +1 = 0, то
Y і + 1 = Y и + у и +1 х 2 - ( і +1) = Y и ; (1.3.)
R і +1 = (А-В Y і + 1 ) х 2 і +1 = 2 R и , (1.4.)
тобто в приватному записується 0 за ...
