- •Основы компьютерной арифметики и логики
- •Предисловие
- •Глава 4, подготовленная доцентом о.П. Шафеевой, посвящена вопросам разработки алгоритмических моделей выполнения арифметических операций и моделирования на пэвм спроектированных алгоритмов.
- •Основы двоичной компьютерной арифметики
- •1.1. Позиционные системы счисления
- •Десятичная позиционная система счисления
- •Двоичная позиционная система счисления
- •1.1.3. Восьмеричная позиционная система счисления
- •1.1.4. Шестнадцатеричная позиционная система счисления
- •Сложение Вычитание
- •Перевод чисел из одной позиционной системы счисления в другую
- •1.2.1. Перевод целых чисел
- •1.2.2. Перевод правильных дробей
- •1.2.3. Перевод неправильных дробей из одной системы счисления в другую
- •1.2.4. Частный случай перевода чисел из одной системы счисления в другую
- •1.2.5. Перевод чисел из одной системы счисления в другую с использованием промежуточной двоично-десятичной системы
- •1.3. Представление чисел с фиксированной запятой (точкой)
- •1.4. Представление чисел с плавающей запятой (точкой)
- •1.5. Коды двоичных чисел
- •1.5.1. Прямой код
- •1.5.2. Обратный код
- •1.5.3. Модифицированный обратный код
- •1.5.4. Дополнительный код
- •2.1.1. Алгебраическое сложение чисел в дополнительном коде
- •2.1.2. Алгебраическое сложение чисел в обратном коде
- •2.1.3. Переполнение разрядной сетки при сложении чисел
- •2.2. Сложение (вычитание) двоичных чисел с плавающей запятой
- •2.2.1. Метод ускоренного сложения двоичных чисел с запоминанием переносов
- •2.3. Умножение двоичных чисел с фиксированной запятой
- •2.4. Машинные технологии выполнения операции умножения двоичных чисел с фиксированной запятой
- •2.5. Умножение двоичных чисел с плавающей запятой
- •2.6. Методы ускоренного выполнения операции умножения двоичных чисел
- •2.6.1. Метод пропуска такта суммирования
- •2.6.2. Метод анализа сомножителей
- •2.6.3. Метод расшифровки и одновременного умножения на два разряда множителя
- •2.6.4. Метод ускоренного умножения Мак-Сорли
- •2.6.5. Метод ускоренного умножения Лемана
- •2.6.6. Метод умножения с расшифровкой пар разрядов множителя и запоминанием переносов
- •2.7. Деление двоичных чисел с фиксированной запятой
- •2.8. Деление двоичных чисел с плавающей запятой
- •3. Основы десятичной компьютерной арифметики
- •3.1. Машинное кодирование десятичных чисел
- •3.2. Выполнение арифметических операций с десятичными числами
- •3.2.1. Сложение десятичных чисел в эвм
- •3.2.2. Умножение десятичных чисел в эвм
- •3.2.3. Ускорение умножения в -кодах
- •Деление десятичных чисел в эвм
- •4.2. Моделирование алгоритма сложения двоичных чисел
- •Различные случаи ненормализованных мантисс
- •4.3. Проектирование алгоритма умножения чисел
- •4.5. Проектирование алгоритма деления чисел
- •4.7. Разработка алгоритма вычисления квадратного корня
- •Определение 1. Пусть и произвольные множества. Соответствием называется тройка множеств
- •Свойства отношений
- •Эквивалентность
- •Толерантность
- •Отношения порядка
- •Самодвойственные функции
- •Монотонные функции
- •Линейные функции
- •Функции, сохраняющие константу
- •5.2.7. Минимизация булевых функций
- •Метод Блейка
- •Метод Квайна-Мак-Класки
- •Минимизация с использованием карт Карно
- •Дана функция четырех переменных (рис. 5.13):
- •Минимизация не полностью определенных булевых функций
- •Минимизация систем булевых функций
- •5.3. Методика синтеза комбинационных схем на логических элементах
- •5.3.1. Логические элементы
- •5.3.2. Общий алгоритм построения комбинационных схем
- •5.3.3. Синтез кс в классическом базисе
- •5.3.4. Синтез кс в базисах «и-не», «или-не»
- •5.3.5. Реализация кс в базисе Жегалкина
- •5.3.6. Синтез составных кс
- •Заключение
- •Библиографический список к главам 1, 2, 3, 4
- •Библиографический список к главе 5
2.6.4. Метод ускоренного умножения Мак-Сорли
Логический метод ускорения выполнения операции умножения с одновременным анализом и обработкой нескольких разрядов множителя, начиная со старших его разрядов, который также может быть использован и при умножении, начиная с младших разрядов множителя, был предложен Мак-Сорли.
Рассмотрим этот метод на примере умножения, начиная со старших разрядов множителя, с обработкой за один цикл двух разрядов множителя. В этом случае разряды множителя анализируются слева направо.
При анализе первой пары разрядов множителя предусматриваются следующие действия. Если анализируемая пара 00 или 10, то есть правый (младший) разряд пары имеет значение 0, то производятся те же действия, что и в предыдущем методе: к сумме частичных произведений или ничего не прибавляется, или прибавляется удвоенное множимое . Если анализируемая пара разрядов множителя 01 или 11, то производится прибавление к сумме частичных произведений множимого, умноженного на число, которое на единицу больше, чем данная пара. Иными словами, к сумме частичных произведений прибавляется либо удвоенное , либо учетверенное множимое.
Из сказанного следует, что при обработке пар разрядов множителя 00 и 10 вновь сформированная сумма частичных произведений будет правильная, а при обработке пар 01 и 11 сформированная сумма частичных произведений будет неправильная и ее необходимо скорректировать в следующем цикле.
После обработки очередной пары разрядов множителя сумма частичных произведений сдвигается на два разряда влево, то есть увеличивается в четыре раза. Следовательно, в случае обработки пары разрядов множителя 01 и 11 сумма частичных произведений перед обработкой следующей пары будет больше истинной на учетверенное множимое. Поэтому, если правый (младший) разряд предыдущей пары разрядов множителя был равен 1, то для коррекции суммы частичных произведений действие при обработке данной пары должно учитывать необходимость вычитания учетверенного множимого.
При обработке пары 00 из суммы частичных произведений должно быть вычтено учетверенное множимое. При обработке пары 10 из суммы частичных произведений должно быть вычтено удвоенное множимое. При обработке пары 01 также должно быть вычтено удвоенное множимое, а при паре 11 сумма частичных произведений не изменяется.
Правила для обработки по методу Мак-Сорли пар разрядов множителя с учетом младшего разряда предыдущей пары удобно представить в виде табл. 2.2.
Таблица 2.2
Пара разрядов множителя |
Младший разряд предыдущей пары |
Операция в сумматоре |
Кратность множимому |
0 0 |
0 |
Отсутствие действия |
0 |
0 1 |
0 |
+ |
2Х |
1 0 |
0 |
+ |
2Х |
1 1 |
0 |
+ |
4Х |
0 0 |
1 |
- |
4Х |
0 1 |
1 |
- |
2Х |
1 0 |
1 |
- |
2Х |
1 1 |
1 |
- |
0 |
Из приведенной таблицы видно, что для выполнения умножения используется удвоенное и учетверенное множимое. Поэтому перед началом умножения в регистр множимого засылается удвоенное, то есть сдвинутое на один разряд влево, множимое. При обработке пар разрядов множителя, требующих прибавления или вычитания учетверенного множимого, логическими схемами вырабатывается сигнал, подключающий к сумматору содержимое регистра множимого, то есть 2Х, сдвинутое еще на один разряд влево.
Логические схемы, формирующие сигнал вычитания (-); формирующие сигнал сложения (+); формирующие сигнал подключения учетверенного множимого, управляются старшими разрядами и дополнительным разрядом регистра множителя. После обработки в очередном цикле каждой пары разрядов регистра множителя его содержимое и содержимое сумматора частичных произведений сдвигается на два разряда влево.
Следует отметить, что если младший разряд множителя равен «1», то необходимо после получения результата вычесть из него множимое.