Умножение двоичных беззнаковых чисел в компьютерных системах - Компьютерная арифметика
Пусть сомножителями X и Y являются s-битные целые числа без знака:
Где - (Х) - множимое, (Y) - множитель, (Z) - произведение. Тогда:
Z = X - Y. (4.2)
Где:
;
.
Представим множитель Y в развернутой форме:
. (4.3)
Тогда:
(4.4)
Произведение множимого на один бит множителя называется частичным произведением. Полное произведение числа представляет собой сумму (s) частичных произведений (ЧП). При умножении вручную существует два способа:
- - Способ № 1, начиная с младшей цифры множителя и сдвиг частичных произведений влево; - Способ № 2, начиная со старшей цифры множителя и сдвиг частичных произведений вправо. Например. Необходимо перемножить два беззнаковых числа (7-3=21). Для удобства возьмем длину разрядной сетки равную четырем битам. Правило умножения вручную заключается в следующем: - шаг 1. Анализируется младший (правый) бит множителя, если младшая цифра множителя равна (1), то в сумму частичных произведений записываются все биты множимого, если младшая цифра множителя равна (0), то в сумму частичных произведений записываются все (0); - шаг 2. Анализируется следующий после младшего бит множителя, если цифра множителя равна (1), то в сумму частичных произведений записываются все биты множимого сдвинутые на один разряд влево, если цифра множителя равна (0), то в сумму частичных произведений записываются все (0), сдвинутые на один разряд влево; - шаг 3. Шаги (1) и (2) повторяются до тех пор, пока не будут проанализированы все цифры множителя; - шаг4. Производится сложение всех сумм частичных произведений. Полученная сумма и будет равна произведению множимого на множитель.
Итак: необходимо перемножить два беззнаковых числа (7-3=21)
Где: (7) - множимое;
- (3) - множитель; (21) - произведение.
Необходимо вычислить сумму частичных произведений - (ЧП), а следовательно и произведение.
Способ №1
Десятичное Число |
Двоичное Число |
Комментарии |
7(10) |
0111(2) |
Множимое |
3(10) |
0011(2) |
Множитель |
4321 |
Номера цифр множителя | |
0111 |
1Ое - ЧП | |
0111 |
2Ое - ЧП | |
0000 |
3Ое - ЧП | |
0000 |
4Ое - ЧП | |
21(10) 0010101(2) |
Сумма ЧП - произведение |
Способ №2
Десятичное Число |
Двоичное Число |
Комментарии |
7(10) |
0111(2) |
Множимое |
3(10) |
0011(2) |
Множитель |
1234 |
Номера цифр множителя | |
0000 |
1Ое - ЧП | |
0000 |
2Ое - ЧП | |
0111 |
3Ое - ЧП | |
0111 |
4Ое - ЧП | |
21(10) 0010101(2) |
Сумма ЧП - произведение |
В отличие от ручного умножения, операционное устройство компьютера не может просуммировать сразу (s) частичных произведений, как это делает человек. Обычный сумматор, как правило, рассчитан на одновременное сложение только двух операндов. Если нужно получить сумму нескольких слагаемых, то происходит накопление суммы: сначала в сумматор записывается первое слагаемое, к нему прибавляется второе, затем к полученной сумме прибавляется третье слагаемое и так до получения полной суммы.
Длина произведения s-битных сомножителей равна 2s бит:
(4.5)
Поскольку умножение на () эквивалентно сдвигу влево, то вычисление произведения (Z) сводится к формированию частичных произведений (), их сдвигу и суммированию с учетом весов, определяемых величинами ().
(4.6)
Умножение реализуется циклическим процессом, на каждом шаге которого:
- - анализируется очередной бит множителя; - в зависимости от его значения происходит (yI=1) или нет (yI=0) прибавление множимого к предыдущей сумме частичных произведений; - производится изменение взаимного положения множимого (X) и суммы частичных произведений с учетом веса (2I).
Таким образом, умножение в двоичной системе счисления естественным образом сводится к двум операциям -- сложению и сдвигу чисел.
В соответствии со способом формирования суммы частичных произведений - (ЧП), возможны четыре варианта умножения. Они различаются тем, с каких разрядов множителя (Y) (младших или старших) начинается умножение, и что сдвигается (множимое или сумма ЧП).
Варианты умножения, начиная с младших или старших разрядов множителя, называются еще умножением младшими и старшими разрядами вперед соответственно. Схемы выполнения операции умножения двоичных беззнаковых чисел представлены на рис. 4.8. При умножении младшими разрядами вперед производятся последовательные сдвиги множителя вправо, вследствие чего в младшем разряде регистра множителя последовательно появляются все его цифры, начиная с младшей. Т. о., в специальной схеме анализа значения текущей цифры множителя нужно анализировать только состояние младшего разряда соответствующего регистра.
Рисунок 4.8 -- Схемы выполнения операции умножения двоичных беззнаковых чисел
Соответственно, при умножении старшими разрядами вперед должен анализироваться старший разряд множителя.
Схема 1
. (4.7)
. (4.8)
Время выполнения операции умножения:
(4.9)
Где (tС) -- время, затрачиваемое на выполнение операции сдвига на один разряд;
(t+) -- время, затрачиваемое на выполнение операции сложения.
Схема 2
. (4.10)
(4.11)
. (4.12)
Схема 3
. (4.13)
. (4.14)
. (4.15)
Схема 4
. (4.16)
. (4.17)
. (4.18)
Рассмотрим на примере два базовых алгоритма умножения в компьютерных системах двоичных беззнаковых чисел:
Алгоритм №1. Алгоритм умножения младшими разрядами вперед, со сдвигом суммы ЧП вправо.
- 1. Исходное значение суммы (ЧП) принимается равным (0), счетчику тактов - (Сч. Т) присваивается значение, равное числу разрядов множителя. 2. Анализируется младшая разрядная цифра множителя. Если она равна (1), то к сумме (ЧП) прибавляется множимое, совмещенное по старшим разрядам; если (0) -- прибавление не производится. 3. Производится сдвиг множителя и суммы ЧП вправо на (1) разряд. Содержимое (Сч. Т) уменьшается на (1). 4. Анализируется содержимое (Сч. Т). Если оно не равно (0), то переход к (п.2), иначе -- (п.5). 5. Умножение закончено, младшая часть произведения находится на месте множителя, а старшая -- на месте суммы (ЧП). Например: необходимо перемножить два беззнаковых числа (7-3=21). Для удобства возьмем длину разрядной сетки равную четырем битам, а именно: Х = 7 - множимое, Y = 3 - множитель, Z = 21 - произведение. Если (X) и (Y) равняется четырем битам, то как было отмечено выше (Z) должно быть восьмиразрядным значением, т. е длина разрядной сетки произведения в два раза больше множимого и множителя. Алгоритм умножения приведен в табл. 4.1.
Таблица 4.1 - Алгоритм умножения со сдвигом вправо двоичных беззнаковых чисел
Регистр (В) Множимое X |
Регистр (С) Множитель Y |
Регистр (А) Произведение Z |
Счетчик тактов (Сч. Т) |
Комментарии | |||||
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
00000000 |
4 |
0111 |
Множимое | ||||||||
01110000 |
1Я СЧП | ||||||||
0 |
0 |
1 |
00111000 |
3 |
1ЫЙСдвиг СЧП | ||||
0111 |
Множимое | ||||||||
10101000 |
2Я СЧП | ||||||||
0 |
0 |
01010100 |
2 |
2 ОЙСдвиг СЧП | |||||
0 |
00101010 |
1 |
3 ИЙСдвиг СЧП | ||||||
00010101 |
0 |
4ЫЙСдвиг СЧП | |||||||
СТОП |
Алгоритм №2. Алгоритм умножения старшими разрядами вперед, со сдвигом суммы ЧП влево.
- 1. Исходное значение суммы (ЧП) принимается равным (0), (Сч. Т) присваивается значение, равное числу разрядов множителя. 2. Производится сдвиг суммы (ЧП) влево на (1) разряд. 3. Анализируется старшая разрядная цифра множителя. Если она равна (1), то к сумме (ЧП) прибавляется множимое, совмещенное по младшим разрядам; если (0) -- прибавление не производится. 4. Производится сдвиг множителя влево на (1) разряд. Содержимое (Сч. Т) уменьшается на (1). 5. Анализируется содержимое (Сч. Т). Если оно не равно (0), то переход к (п.2), иначе -- (п.6). 6. Умножение закончено, произведения находится на месте суммы (ЧП), которая имеет удвоенную разрядность. Например: необходимо перемножить два беззнаковых числа (7-3=21). Для удобства возьмем длину разрядной сетки равную четырем битам, а именно: Х = 7 - множимое, Y = 3 - множитель, Z = 21 - произведение. Если (X) и (Y) равняется четырем битам, то как было отмечено выше (Z) должно быть восьмиразрядным значением, т. е длина разрядной сетки произведения в два раза больше множимого и множителя. Алгоритм умножения приведен в табл. 4.2.
Таблица 4.2 - Алгоритм умножения со сдвигом влево двоичных беззнаковых чисел
Регистр (В) Множимое X |
Регистр (С) Множитель Y |
Регистр (А) Произведение Z |
Счетчик тактов (Сч. Т) |
Комментарии | |||||
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
00000000 |
4 |
00000000 |
1ЫЙСдвиг СЧП | ||||||||
0 |
1 |
1 |
00000000 |
3 |
2 ОЙСдвиг СЧП | ||||
00000000 |
3 ИЙСдвиг СЧП | ||||||||
1 |
1 |
00000000 |
2 |
4ЫЙСдвиг СЧП | |||||
00000000 |
5ЫЙСдвиг СЧП | ||||||||
0111 |
Множимое | ||||||||
00000111 |
1Я СЧП | ||||||||
1 |
1 | ||||||||
00001110 |
6ОЙ сдвиг СЧП | ||||||||
0111 |
Множимое | ||||||||
00010101 |
0 |
2Я СЧП | |||||||
СТОП |
Похожие статьи
-
Операции сдвига в компьютерных системах - Компьютерная арифметика
Является одной из самых распространенных в компьютерной арифметике. В частности, она используется при выполнении умножения или деления двоичных чисел....
-
Операция сложения и вычитания, двоичных беззнаковых чисел в компьютерных системах Компьютерная система выполняет сложение и вычитание операндов по...
-
При сложении и вычитании знаковых двоичных чисел операция вычитания заменяется операцией сложения в дополнительном коде. Докажем, что результат...
-
Он позволяет заменить операцию вычитания на операцию сложения, чем упрощает архитектуру компьютерной системы. Дополнительный код является дополнением...
-
Представление числовых данных в компьютерных системах - Компьютерная арифметика
Компьютерный арифметика счисление двоичный Система вещественных чисел, используемая в ручных расчетах, предполагается бесконечной и непрерывной, т. е....
-
Перевод чисел из одной позиционной системы счисления в другую - Компьютерная арифметика
Задача перевода чисел из одной позиционной системы счисления в другую является одной из главных в компьютерной арифметике. Ее можно сформулировать...
-
Контроль переполнения в компьютерных системах - Компьютерная арифметика
Возможно только при сложении чисел с одинаковыми знаками, когда для представления результата недостаточно отведенного количество разрядов (требуется...
-
Классификация систем счисления - Компьютерная арифметика
В настоящее время различают Позиционные И Непозиционные системы счисления. Классификация систем счисления приведена на рис. 2.1. Рисунок 2.1 --...
-
10 2 4 8 16 0 0 0 0 0 1 1 1 1 1 2 10 2 2 2 3 11 3 3 3 4 100 10 4 4 5 101 11 5 5 6 110 12 6 6 7 111 13 7 7 8 1000 20 10 8 9 1001 21 11 9 10 1010 22 12 A...
-
ДД-код Константа16 ДД-код Константа16 1111 1111 FF 0000 0000 00 0011 0101 35 1111 0100 F4 0101 0111 57 1001 1010 9A 1000 1101 8D 0000 0111 07 1000 0000...
-
Системы счисления - Компьютерная арифметика
Как было отмечено в первой главе Система счисления - совокупность приемов и правил для установления однозначного соответствия между любым числом и его...
-
Арифметические флажки - Компьютерная арифметика
Флажки являются признаками, представляющими общую характеристику результата выполнения операции. Наиболее широко применяются следующие флажки: - Флажок...
-
Собственные числа и собственные векторы матрицы Предположим, что среди бесконечного множества одномерных пространств R1 найдутся такие, которые будут...
-
Базовые понятия и определения компьютерной арифметики - Компьютерная арифметика
Компьютерная арифметика - совокупность принципов и форм представления числовой информации, методов и алгоритмов выполнения арифметических операций и...
-
Системы счисления. Представление данных в ЭВМ - Основы программирования
В современном мире для записи числовой информации используют позиционные системы счисления, в которых числа записываются с помощью ограниченного...
-
Действия над матрицами - Матричный формализм в теории систем
Суммой двух матриц A и B одной и той же размерности mn называется матрица C размерности mn, элементы которой находятся из условия cij=aij+bij....
-
Показатели обслуживания пассажиров в справочном бюро автовокзала - число окон, обеспечивающих предоставление необходимого числа справок, длина очереди и...
-
Нормализация Базы Данных - Разработка информационной системы "Магазин компьютерных товаров"
Результатом работы с АИС магазина компьютерных товаров является чек, который оформляет продавец. В этом чеке должна содержаться информация о количестве...
-
Типы данных и команды SQL - Разработка информационной системы "Магазин компьютерных товаров"
Microsoft SQL Server поддерживает большинство типов данных SQL 2003. Также SQL Server поддерживает дополнительные типы данных, используемые для...
-
Блок OVRDSEL принимает до четырех входов (от первичных блоков) и выбирает один с наибольшим или наименьшим значением. Графически это выглядит следующим...
-
При обслуживании пассажиров в кассах предварительной продажи билетов в качестве показателей, характеризующих систему обслуживания, используют максимально...
-
Рассмотрим замкнутую сеть массового обслуживания с разнотипными заявками, которая является вероятностной моделью обслуживания заявок в УП "Проектный...
-
Расчет потребного числа отдельных устройств автовокзала Расчет числа билетных касс Число билетных касс должно обеспечивать полное и своевременное...
-
Машинная арифметика с плавающей точкой - Представление и хранение информациии в ЭВМ
Число с плавающей точкой: X=±Mx-S±px Здесь: M - мантисса; S - порядок. 0.314 101 0.0314 102 Машинные числа. Машинными называются числа, допускающие...
-
Системы счисления - Основы информатики
1.1 Переведите число 154,23510 из десятичной системы счисления в двоичную, восьмеричную, шестнадцатеричную системы счисления Решение: При переводе из...
-
Арифметические операции в двоичной системе счисления Умножение в двоичной системе счисления = поразрядные сдвиги + суммирование Основные форматы хранения...
-
Компромиссная система, для удобства восприятия данных человеком и корректной работы компьютера, двоично-десятичная запись чисел. Принцип построения этой...
-
Введение - Разработка программ преобразования форматов двоичных данных и сортировок
Программа юникод кодирование Основной задачей работы является разработать программу, преобразующую массив чисел в соответствующий формат. Перед тем, как...
-
Степени матриц Произведение матриц AAA...A, где A - квадратная матрица порядка n, можно записать в виде Ak, где k означает число сомножителей, входящих в...
-
Вся информация, которую обрабатывает компьютер, должна быть представлена двоичным кодом с помощью двух цифр -- 0 и 1. Эти два символа принято называть...
-
Понятие матрицы Матрицей А размером mn или просто (mn)-матрицей называют прямоугольную таблицу, содержащую m строк и n столбцов, элементами которой...
-
Операционная система Windows - Программное обеспечение информационных компьютерных систем
Само название Windows, на русском языке означает "Окна" и имеет в нашем языке синонимы Виндовс, Вундоуз и другие производные полученные после перевода....
-
Проблема представления знаний в компьютерных системах - одна из основных проблем в области искусственного интеллекта. Решение этой проблемы позволит...
-
Операционная система - Программное обеспечение информационных компьютерных систем
Операционная система - это комплекс взаимосвязанных системных программ, назначение которого - организовать взаимодействие пользователя с компьютером и...
-
Основные термины теории баз данных - БД (База данных) - совокупность специальным образом организованных данных, хранимых в памяти вычислительной системы...
-
В вычислительной технике понятие безопасности является весьма широким. Оно подразумевает и надежность работы компьютера, и сохранность ценных данных, и...
-
Классификация компьютерных сетей - Теоретические основы информационных процессов и систем
Для классификации компьютерных сетей используются разные признаки, выбор которых заключается в том, чтобы выделить из существующего многообразия такие,...
-
Доставочные агенты., Адресация в системе электронной почты - Использование компьютерных сетей
Программы, которые принимают почту от транспортного агента и доставляют ее соответствующим пользователям. Почта может доставляться конкретному лицу, в...
-
Основным, с точки зрения пользователя, является прикладной уровень. Этот уровень обеспечивает выполнение прикладных процессов пользователей. Наряду с...
-
Электронная почта обеспечивает доставку писем (а часто и пpоизвольных файлов, а также голосовых и факсимильных сообщений) от одних пользователей к...
Умножение двоичных беззнаковых чисел в компьютерных системах - Компьютерная арифметика