- •Арифметические и логические основы вычислительной техники учебное пособие
- •Введение
- •Арифметические основы вычислительной техники Системы счисления
- •Двоичная система счисления
- •Восьмеричная система счисления
- •Шестнадцатеричная система счисления
- •Критерии выбора системы счисления
- •Перевод чисел из одной системы счисления в другую
- •Перевод целых чисел.
- •Перевод правильных дробей.
- •Перевод чисел из системы счисления в систему счисления основания которых кратны степени 2
- •Кодирование чисел
- •Переполнение разрядной сетки
- •Модифицированные коды
- •Машинные формы представления чисел.
- •Погрешность выполнения арифметических операций
- •Округление
- •Нормализация чисел
- •Последовательное и параллельное сложение чисел
- •Сложение чисел с плавающей запятой
- •Машинные методы умножения чисел в прямых кодах
- •Ускорение операции умножения
- •Умножение с хранением переносов
- •Умножение на два разряда множителя одновременно.
- •Умножение на четыре разряда одновременно.
- •Умножение в дополнительных кодах.
- •Умножение на 2 разряда Мт в дополнительных кодах.
- •Матричные методы умножения.
- •Машинные методы деления
- •Деление чисел в прямых кодах.
- •Деление чисел в дополнительных кодах.
- •Методы ускорения деления.
- •Двоично-десятичные коды
- •Суммирование чисел с одинаковыми знаками в коде 8421.
- •Сложение чисел с разными знаками.
- •Двоично-десятичные коды с избытком 3
- •Код с избытком 6 для одного из слагаемых
- •Система счисления в остаточных классах (сок)
- •Представление отрицательных чисел в сок
- •Контроль работы цифрового автомата
- •Некоторые понятия теории кодирования
- •Обнаружение и исправление одиночных ошибок путем использования дополнительных разрядов
- •Коды Хемминга
- •Логические основы вычислительной техники Двоичные переменные и булевы функции
- •Способы задания булевых функций
- •Основные понятия алгебры логики
- •Основные законы алгебры логики
- •Формы представления функций алгебры логики
- •Системы функций алгебры логики
- •Минимизация фал
- •Метод Квайна
- •Метод Блейка - Порецкого
- •Метод минимизирующих карт Карно (Вейча)
- •Минимизация коньюнктивных нормальных форм.
- •Минимизация не полностью определенных фал
- •Кубическое задание функций алгебры логики.
- •Метод Квайна-Мак Класки
- •Алгоритм извлечения (Рота)
- •Минимизация фал методом преобразования логических выражений
- •Применение правил и законов алгебры логики к синтезу некоторых цифровых устройств Синтез одноразрядного полного комбинационного сумматора
- •Синтез одноразрядного комбинационного полусумматора
- •Синтез одноразрядного полного комбинационного сумматора на двух полусумматорах
- •Синтез одноразрядного комбинационного вычитателя
- •Объединенная схема одноразрядного комбинационного сумматора-вычитателя
- •Триггер со счетным входом как полный одноразрядный сумматор
- •Введение в теорию конечных автоматов Основные понятия теории автоматов
- •Способы задания автоматов
- •Структурный автомат
- •Память автомата
- •Канонический метод синтеза
- •Пример синтеза мпа Мили по гса
- •Синхронизация автоматов
- •Литература
- •220013, Минск, п.Бровки, 6.
Машинные методы умножения чисел в прямых кодах
Операция умножения состоит из ряда последовательных сложений. Сложением управляют разряды множителя: если в очередном разряде множителя содержится единица, то к сумме добавляется множимое. При этом, в зависимости от метода умножения, выполняется сдвиг либо множимого, либо частичной суммы. Наряду с этим умножение можно начинать как с младших, так и со старших разрядов множителя.
Введем некоторые обозначения, используемые ниже: - частичное произведение, - частичная сумма.
Ниже приводится схема четырех алгоритмов умножения .
Остановимся более подробно на реализации умножении согласно алгоритму А.
Представим Мн= А = 0,а1а2…аn
Мт= B = 0,b1b2….bn = b12-1+b22-2+…+bn2-n+bn2-n.
Мн∙Мт = С=А∙В= 0,а1а2…аn ( b12-1+b22-2+…+bn2-n)=
=0+(b1∙0,а1а2…аn)2-1+…+(bn-1∙0,а1а2…аn)2-(n-1)+(bn∙0,а1а2…аn)2-n=
=0+b1∙A2-1+…+bn-1∙A2-(n-1)+…+bn∙A2-n=0+bn∙A2-n+bn-1∙A2-(n-1)+…+b1∙A2-1=
=(…((0+bn∙A)2-1+bn-1∙A)2-1+…+b1∙A)2-1
Ниже приведены (без вывода) остальные три реализации алгоритмов (Б, В и Г) умножения.
Мн∙Мт = С=А∙В = (0+bn∙A+bn-1∙A∙22+…+b1∙A∙2n-1)2-n (алгоритм Б)
Мн∙Мт = С=А∙В = (…(0+b1∙A) ∙21+b2∙A)∙21+…+bn∙A)∙2-n (алгоритм В)
Мн∙Мт = С=А∙В = 0+b1∙A∙2-1+b2∙A∙2-2+…+bn∙A∙2-n (алгоритм Г)
Структурные схемы операционных устройств, выполняющих умножение по алгоритмам А,Б,В и Г приведены на рис 7.
Рассмотрим пример умножения чисел согласно алгоритму А.
Пример: МH = 0,1011
b1
… b4 4
0,0000 начальное содержимое сумматора
0,1011 = Мн ∙ b4 первое частичное произведение
0,1011 первая частичная сумма
0,0101 1 ∙ 2-1 сдвиг первой частичной суммы
0,0000 = Мн ∙ b3 второе частичное произведение
0,0101 1 вторая частичная сумма
0,0010 11 ∙ 2-1 сдвиг второй частичной суммы
0,1011 = Мн ∙ b2 третье частичное произведение
0,1101 11 третья частичная сумма
0,0110 111 ∙ 2-1 сдвиг третьей частичной суммы
0,1011 = Мн ∙ b1 четвертое частичное произведение
1,0001 111 (возникло переполнение)
0,1000 1111 ∙ 2-1 сдвиг для получения верного результата Мн∙Мт
Заметим, что при умножении чисел по алгоритму А на отдельных этапах операции возможно переполнение (попадание значащей единицы в знаковый разряд). Однако при последующем сдвиге переполнение устраняется. При использовании других алгоритмов (Б, В, Г) переполнения не возникает.
Время умножения чисел по алгоритму А tумн = ( tсл + tсдв ) n, где n - число разрядов Мт. Следовательно, сдвиг и сложение нельзя выполнять в одном автоматном такте. Это наглядно показано на рис 6.
Ускорение операции умножения
Арифметические операции, к числу которых относится умножение, часто встречаются при решении задач на ЭВМ. Умножение является длинной операцией. Временные затраты на умножение чисел в прямых кодах можно оценить по формуле:
(3)
где pi вероятность появления единицы в разрядах множителя, tсл – время формирования очередной частичной суммы, tсдв – время выполнения сдвига числа на один разряд. Анализируя выражение (3), можно предложить различные пути сокращения величины Тумн.: уменьшение времени на сдвиг, на формирование очередной суммы, уменьшение числа разрядов множителя. Этого можно достигнуть логическими или аппаратными методами. Рассмотрим логические методы ускорения умножения.
Один из наиболее простых способов состоит в том, чтобы при встрече нулевого разряда в множителе не выполнять формирование очередного (нулевого) частичного произведения, не изменяющего содержимое сумматора. В зависимости от используемого алгоритма умножения выполняется сдвиг либо частичной суммы, либо частичного произведения без выполнения суммирования.