Умножение двоичных чисел
Алгоритмы умножения, их отличительные особенности, этапы и функции. Умножение беззнаковых чисел, младшими разрядами вперед, со сдвигом суммы ЧП вправо, а также старшими со сдвигом влево. Пути умножения знаковых чисел в прямых и дополнительных кодах.
| Рубрика | Математика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 12.11.2011 |
| Размер файла | 185,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Умножение двоичных чисел
1. Алгоритмы умножения
1.1 Умножение беззнаковых чисел
умножение беззнаковый число код
Пусть сомножителями X и Y являются s-битные целые числа без знака:
,
.
Здесь X - множимое, Y - множитель.
Представим множитель Y в развернутой форме:
. (1)
Тогда:
(2)
Произведение множимого на один бит множителя называется частичным произведением. Полное произведение числа представляет собой сумму s частичных произведений (ЧП).
В отличие от ручного умножения, операционное устройство компьютера не может просуммировать сразу s частичных произведений, как это делает человек. Обычный сумматор, как правило, рассчитан на одновременное сложение только двух операндов. Если нужно получить сумму нескольких слагаемых, то происходит накопление суммы: сначала в сумматор записывается первое слагаемое, к нему прибавляется второе, затем к полученной сумме прибавляется третье слагаемое и так до получения полной суммы.
Длина произведения s-битных сомножителей равна 2s бит:
(3)
Поскольку умножение на эквивалентно сдвигу влево, то вычисление произведения Z сводится к формированию частичных произведений , их сдвигу и суммированию с учетом весов, определяемых величинами .
(4)
Умножение реализуется циклическим процессом, на каждом шаге которого:
1) анализируется очередной бит множителя;
2) в зависимости от его значения происходит (yi=1) или нет (yi=0) прибавление множимого к предыдущей сумме частичных произведений;
3) производится изменение взаимного положения множимого X и суммы частичных произведений с учетом веса 2i.
Таким образом, умножение в 2СС естественным образом сводится к двум операциям - сложению и сдвигу чисел. При этом достаточно иметь сумматор и сдвигатель, а специальный умножитель не требуется.
1.2 Методы умножения беззнаковых чисел
В соответствии со способом формирования суммы ЧП, возможны четыре варианта умножения. Они различаются тем, с каких разрядов множителя Y (младших или старших) начинается умножение, и что сдвигается (множимое или сумма ЧП).
Варианты умножения начиная с младших или старших разрядов множителя называются еще умножением младшими и старшими разрядами вперед соответственно.
Рисунок 1 - Схемы выполнения операции умножения двоичных чисел
При умножении младшими разрядами вперед производятся последовательные сдвиги множителя вправо, вследствие чего в младшем разряде регистра множителя последовательно появляются все его цифры, начиная с младшей. Т.о., в специальной схеме анализа значения текущей цифры множителя нужно анализировать только состояние младшего разряда соответствующего регистра. Соответственно, при умножении старшими разрядами вперед должен анализироваться старший разряд множителя.
Схема 1
Время выполнения операции умножения:
,
где tс - время, затрачиваемое на выполнение операции сдвига на один разряд;
t+ - время, затрачиваемое на выполнение операции сложения.
Схема 2
Схема 3
Схема 4
Характерные особенности приведенных выше схем умножения:
1. Везде нужен счетчик тактов (СчТ), но можно обойтись без него, если в схеме 4 использовать терминальную 1 в Y, а в схемах 1 и 3 - проверку ;
2. Схема 2 используется при делении;
3. Схема 4 имеет малый пробег переноса. Возможно временное переполнение сумматора.
4. Процесс умножения по схеме 4 заканчивается операцией сдвига, по схемам 1-3 - операцией суммирования;
5. В схеме 1 первое ЧП представляет собой множимое, сдвинутое на 1 разряд вправо;
6. В схеме 2 первый сдвиг является фиктивным, т.к. он приложен к нулевой накапливаемой сумме. Этим обеспечивается регулярность процесса умножения.
1.3 Алгоритм умножения младшими разрядами вперед, со сдвигом суммы ЧП вправо
1. Исходное значение суммы ЧП принимается равным 0, СчТ присваивается значение, равное числу разрядов множителя.
2. Анализируется младшая разрядная цифра множителя. Если она равна 1, то к сумме ЧП прибавляется множимое, совмещенное по старшим разрядам; если 0 - прибавление не призводится.
3. Производится сдвиг множителя и суммы ЧП вправо на 1 разряд. Содержимое СчТ уменьшается на 1.
4. Анализируется содержимое СчТ. Если оно не равно 0, то переход к п. 2, иначе - п. 5.
5. Умножение закончено, младшая часть произведения находится на месте множителя, а старшая - на месте суммы ЧП.
1.4 Алгоритм умножения старшими разрядами вперед, со сдвигом суммы ЧП влево
1. Исходное значение суммы ЧП принимается равным 0, СчТ присваивается значение, равное числу разрядов множителя.
2. Производится сдвиг суммы ЧП влево на 1 разряд.
3. Анализируется старшая разрядная цифра множителя. Если она равна 1, то к сумме ЧП прибавляется множимое, совмещенное по младшим разрядам; если 0 - прибавление не призводится.
4. Производится сдвиг множителя влево на 1 разряд. Содержимое СчТ уменьшается на 1.
5. Анализируется содержимое СчТ. Если оно не равно 0, то переход к п. 2, иначе - п. 6.
5. Умножение закончено, произведения находится на месте суммы ЧП, которая имеет удвоенную разрядность.
2. Умножение знаковых чисел
При выполнении операции умножения знаковых чисел исходные сомножители могут быть представлены в ПК, ОК или ДК.
2.1 Умножение знаковых чисел в прямых кодах
При данном способе умножения знаковые и числовые разряды обрабатываются отдельно. Для определения знака произведения осуществляют суммирование по модулю 2 цифр, записанных в знаковых разрядах операндов.
Модуль произведения получают, перемножая модули сомножителей в соответствии с одним из рассмотренных ранее алгоритмов:
Однако в современных компьютерах операнды в памяти обычно хранятся в ДК, что продиктовано, в частности, удобством выполнения операции сложения (учитывая автоматическое формирование знака суммы). Для того, чтобы умножить два числа, представленных в ДК можно использовать следующий прием: перед выполнением операции умножения исходные числа преобразуют в ПК, затем их перемножают, а результат далее переводят в ДК.
Такой прием не является эффективным. Поэтому на практике чаще всего используют специальные алгоритмы умножения чисел в дополнительных кодах.
2.2 Умножение знаковых чисел в дополнительных кодах
Алгоритмы корректного умножения операндов в ДК можно разделить на две группы:
1) алгоритмы с обработкой знаковых разрядов отдельно от числовых;
2) алгоритмы с обработкой знаковых разрядов вместе с числовыми. Т.е., на сумматоре дополнительных кодов в процессе перемножения машинных изображений операндов получают одновременно знаковую и числовую части произведения.
Теорема
Произведение дополнительных кодов сомножителей равно дополнительному коду результата только в случае положительных сомножителей. Если хотя бы один сомножитель отрицателен, то произведение чисел на сумматоре дополнительных кодов получается прибавлением поправки к произведению дополнительных кодов сомножителей.
2.3 Умножение знаковых чисел в дополнительных кодах отдельно от формирования знака произведения
Рассмотрим арифметическое обоснование алгоритмов первой группы при различных вариантах комбинаций знаков операндов. С этой целью у операндов отбрасывается знаковая цифра и выполняется умножение полученных псевдомодулей по одному из известных алгоритмов. Результат такого умножения назовем псевдопроизведением .
Обозначим вес знакового разряда сомножителей . Тогда, в соответствии с рассмотренным ранее правилом формирования дополнительного кода, отрицательные сомножители будут представлены в ДК следующим образом:
При удалении знакового разряда получаем псевдомодули:
Всего возможны четыре варианта сочетания знаков сомножителей.
1. .
.
В этом случае сразу получено истинное значение положительного произведения в ДК, которое не требует корректирования:
2. .
.
Результат значительно отличается от модуля кода истинного произведения
;
Сомножитель представляет собой (s-1) - разрядный псевдомодуль числа (-X), представленного в ДК. Сомножитель эквивалентен сдвигу на (s-1) разряд влево.
Сравнение Z и Z' показывает, что результат умножения должен быть скорректирован посредством сложения Z' с поправкой .
3. .
.
4. .
На практике используют упрощенную поправку , поскольку нескорректированный член C проявит себя в виде 1 в знаковом разряде. Это не имеет значения, поскольку знак Z был сформирован отдельно на начальном этапе.
2.4 Умножение знаковых чисел в дополнительных кодах совместно с формированием знака произведения
Подход к формированию алгоритма умножения состоит в следующем.
1. Получим псевдомодули операндов, отбросив старшие (знаковые) цифры: 0 - в положительном числе, 1 - в отрицательном.
2. Считая разрядную сетку наращиваемой, видим, что операнд в старших разрядах содержит незначащие цифры, тождественно равные знаковой.
3. В таком случае истинные операнды можем считать «удлиненными псевдомодулями», у которых самые левые цифры играют роль знаковых разрядов.
4. Выполняя их умножение по правилам, рассмотренным выше, получаем уже не модуль Z', а само псевдопроизведение с некоторыми псевдознаковыми цифрами в двух самых старших разрядах. Указанные цифры относятся к знаковым по расположению, но не имеют смысла таковых.
5. Возникает задача найти истинное значение знаковой цифры числа Z.
Рассмотрим варианты умножения чисел в ДК с обработкой знаковых разрядов вместе с числовыми в зависимости от сочетания знаков сомножителей. При этом используем предпосылки, приведенные в предыдущем доказательстве.
Считаем, что вес знакового разряда равен A. Тогда вес разряда, следующего за знаковым, .
1. .
Перемножая машинные представления сомножителей в ДК, получим:
.
2. .
Учитывая, что разрядность произведения (и псевдопроизведения) составит 2s бит, вес разряда, следующего за знаковым разрядом произведения,
.
Тогда:
Перемножая ДК сомножителей, получим:
Истинное значение произведения
.
3. .
Аналогично предыдущему можно показать, что данному варианту требуется коррекция
.
4. .
На практике используют упрощенную поправку
.
При умножении в ДК по любому из вариантов данной группы в процессе прибавления к Z' важно соблюдать соответствие весов разрядов псевдопроизведения и корректирующей поправки (с учетом наличия псевдознака). Старший разряд корректирующей поправки сформирует знаковую цифру.
2.5 Методы внесения поправок
Из рассмотренных ранее вариантов умножения в соответствии с алгоритмами обеих групп, следует, что для коррекции результата умножения ДК операндов необходимо в каждом случае по комбинации знаков определять величину коррекции, а затем выполнять 1-2 шага суммирования. Однако этого можно избежать, если коррекцию совмещать с процессом суммирования частичных произведений.
Рассмотренные алгоритмы являются базовыми и реализуют непосредственный способ введения поправок. Более широкое применение на практике получили алгоритмы с косвенным способом введения поправок.
1. .
По примеру п. 1 результат является истинным произведением и корректировка не требуется. Т.е. сформированы истинные модуль и знак.
2. .
При умножении младшими разрядами вперед получится известный для этого случая модуль псевдопроизведения. Если при умножении на знаковую цифру множителя не прибавлять последнее ЧП к их сумме, а вычесть его, тем самым, Z' будет уменьшено на .
Кроме того, если для представления последнего ЧП воспользоваться ДК, то при его прибавлении не только будет откорректирована числовая часть произведения, но и сформируется правильный его знак. При этом, последний сдвиг ЧП должен быть арифметическим с учетом отрицательного знака ЧП.
3. .
Если сдвиг суммы ЧП вправо на i разрядов выполнять по правилам сдвига модифицированного ДК, а затем выполнять суммирование ЧП по правилам суммирования модифицированных ДК (с потерей переноса из знакового разряда), то будет получено правильное произведение исходных чисел в ДК, т.е. . Т.о., коррекция не требуется.
4. .
Коррекция результата выполняется объединением двух предыдущих вариантов, т.е. при умножении на знаковый разряд множителя выполняют вычитание, а суммирование и сдвиг частичных произведений производят с использованием МДК.
Т.о., при положительном множителе умножение в ДК можно выполнять по алгоритмам умножения в ПК, если только суммировать ЧП и сдвиг выполнять по правилам сложения и сдвига модифицированного ДК (перенос из ЗР будет игнорироваться).
Существует еще один способ умножения знаковых чисел в ДК. Он заключается в том, что отрицательный множитель необходимо преобразовать в положительный. Это выполняется умножением на «-1» множимого и множителя. В итоге, в соответствии с теоремой 1, умножение выполняется по обычным правилам, а результат не нуждается в корректировке.
2.6 Общий алгоритм умножения целых двоичных знаковых чисел, представленных в ДК
1. Исходное значение суммы ЧП принимается равным 0, СчТ присваивается значение, равное числу разрядов множителя.
2. Анализируется младшая разрядная цифра множителя. Если она равна 1, то к сумме ЧП прибавляется множимое; если 0 - прибавление не производится. Множимое при этом совмещается с суммой ЧП по старшим разрядам и представлено в исходном коде.
3. Производится арифметический сдвиг суммы ЧП вправо на 1 разряд с учетом флагов переноса (CY) и переполнения (OV). Содержимое СчТ уменьшается на 1.
4. пп. 2-3 последовательно выполняются для всех цифровых разрядов множителя.
5. Если множитель - положительное число, то полученный результат является истинным произведением Z. Если множитель - отрицательное число, то к полученному результату Z' прибавляется множимое с обратным знаком (дополнение), совмещенное по старшим разрядам. Полученная сумма представляет собой истинное произведение Z.
умножение знаковый разряд код
.
Размещено на Allbest.ru
Подобные документы
Новый способ умножения чисел. Схожесть образующейся при вычислении матрицы из цифр, с треугольником относительна, но все же есть, особенно при умножении трехзначных чисел и выше. Треугольная матрица.
статья [7,6 K], добавлен 06.02.2005Как люди научились считать, возникновение цифр, чисел и систем счисления. Таблица умножения на "пальцах": методика умножения для чисел 9 и 8. Примеры быстрого счета. Способы умножения двузначного числа на 11, 111, 1111 и т.д. и трехзначного числа на 999.
курсовая работа [66,8 K], добавлен 22.10.2011Сложение и умножение целых p-адических чисел, определяемое как почленное сложение и умножение последовательностей. Кольцо целых p-адических чисел, исследование свойств их деления. Объяснение данных чисел с помощью ввода новых математических объектов.
курсовая работа [345,5 K], добавлен 22.06.2015Назначение, состав и структура арифметическо-логических устройств, их классификация, средства представления. Принципы построения и функционирования АЛУ ЭВМ. Создание блок-схемы алгоритма умножения, определение набора управляющих сигналов, схемное решение.
курсовая работа [134,0 K], добавлен 25.10.2014Ознакомление с действиями умножения и деления. Рассмотрение случаев замены суммы произведением. Решения примеров с одинаковыми и разными слагаемыми. Вычислительный прием деления, деление на равные части. Преподавание таблицы умножения в игровой форме.
презентация [3,4 M], добавлен 15.04.2015Свойства чисел натурального ряда. Периодическая зависимость от порядковых номеров чисел. Шестеричная периодизация чисел. Область отрицательных чисел. Расположение простых чисел в соответствии с шестеричной периодизацией.
научная работа [20,2 K], добавлен 29.12.2006Учебное пособие по математике для младших классов. Таблицы умножения и деления. Решение задач на сравнение. Работа с большими числами. Разбор чисел по разрядным слагаемым. Умножение и деление в столбик. Справочник величин. Нахождение доли от числа.
учебное пособие [400,5 K], добавлен 20.02.2010Закон сохранения количества чисел Джойнт ряда в натуральном ряду чисел как принцип обратной связи чисел в математике. Структура натурального ряда чисел. Изоморфные свойства рядов четных и нечетных чисел. Фрактальная природа распределения простых чисел.
монография [575,3 K], добавлен 28.03.2012Сумма n первых чисел натурального ряда. Вычисление площади параболического сегмента. Доказательство формулы Штерна. Выражение суммы k-х степеней натуральных чисел через детерминант и с помощью бернуллиевых чисел. Сумма степеней и нечетных чисел.
курсовая работа [8,2 M], добавлен 14.09.2015Идея элементарного доказательства великой теоремы Ферма исключительно проста: разложение чисел a, b, c на пары слагаемых, группировка из них двух сумм U' и U'' и умножение равенства a^n + b^n – c^n = 0 на 11^n (т.е. на 11 в степени n, а чисел a, b, c на 1
статья [12,9 K], добавлен 07.07.2005
