Метод ускоренного сложения двоичных чисел

С запоминанием переносов

Для минимизации времени сложения при выполнении операций, требующих ряда последовательных суммирований большого количества чисел, в ряде случаев используют параллельные сумматоры с запоминанием переноса. В подобных сумматорах сложение выполняется как разрядная операция с запоминанием поразрядного значения суммы S_iп . Возникающие при этом в процессе последовательных сложений единичные сигналы переноса не распространяются по сумматору, а запоминаются в отдельном регистре переносов РП.

Процесс ускоренного сложения с запоминанием переносов группы чисел состоит из ряда циклов по числу слагаемых. В каждом цикле, за исключением последнего -го, производится поразрядное сложение и формирование переносов трех чисел: очередного слагаемого, поразрядной суммы от предшествовавших сложений и значение переноса, сформированного в предшествующем цикле сложения. Образующиеся при этом новое поразрядное значение суммы и значение переноса запоминаются и в следующем цикле сложения суммируются с очередным слагаемым аналогичным образом. Для завершения выполнения сложения и получения окончательного результата (полной суммы) необходимо в последнем цикле выполнить операцию полного сложения с учетом распространения переноса, например, по цепи сквозного переноса.

Для иллюстрации описанного метода рассмотрим пример сложения четырех чисел с запоминанием переноса (табл. 2.1).

В последнем цикле вычисления суммы включается цепь переноса, по которой осуществляются межразрядные связи в сумматоре и формируется окончательный результат.

Таблица 2.1

	Регистр переносов РП	Сумматор
Слагаемые	Запоминаемый перенос	Формирование поразрядной суммы Siп	Примечание
0 0 1 0 1 0 1 0	0 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0	цикл 1 S0,П Х1 П0
0 0 0 1 1 0 1 0	0 0 0 0 0 0 0 0	0 0 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0	цикл 2 S1,П Х2 П1
0 0 1 1 0 0 1 1	0 0 0 1 0 1 0 0	0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0	цикл 3 S2,П Х3 П2
0 0 1 0 0 1 0 1	0 1 1 0 0 0 0 0	0 0 0 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0	цикл 4 S3,П Х4 П3
0 0 0 0 0 0 0 0	0 1 0 0 1 0 1 0	0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0	цикл 5 S4,П 0 сложение П4 с учетом переносов
		1 0 0 1 1 1 0 0	окончательный результат сложения

Из рассмотренного примера ясно, что использование принципа поразрядного сложения с запоминанием переносов при суммировании большого массива цифр, как это имеет место при выполнении экономических расчетов, операции умножения и деления, позволяет значительно сократить общее время суммирования за счет исключения времени на распространение переноса.

Умножение двоичных чисел с фиксированной запятой

Умножение двоичных чисел чаще всего осуществляется в прямом коде.

Знак произведения определяется путем сложения по модулю два знаков сомножителей, что полностью соответствует известным правилам алгебры.

Определение знака Правило знаков

произведения при умножении

0 0 = 0 + ∙ + = +

0 1 = 1 + ∙ – = –

1 0 = 1 – ∙ + = −

1 1 = 0 − ∙ − = +

Умножение сомножителей в прямом коде осуществляется по обычным правилам двоичной арифметики, изложенным выше. При этом умножение можно начинать как со старшего, так и с младшего разряда множителя. В первом случае каждое последующее частичное произведение сдвигается относительно предыдущего на один разряд вправо и суммируется с ним, а во втором случае очередное частичное произведение сдвигается влево на один разряд и также суммируется с предшествовавшей суммой частичных произведений. Частичные произведения, равные нулю, т.е. получающиеся умножением множимого на нулевое значение соответствующего разряда множителя, можно опускать, но сдвиг на один разряд равного нулю частичного произведения необходимо учитывать.

Из сказанного следует, что умножение сомножителей фактически сводится к сдвигам (вправо или влево) множимого и сложению сдвинутых частичных произведений с предшествующей суммой частичных произведений.

Известно, что количество разрядов произведения должно равняться сумме разрядов сомножителей. Поэтому при работе с фиксированной (постоянной) длиной разрядной сетки результат перемножения сомножителей должен ограничиваться по числу разрядов и округляться по известным в арифметике правилам.

Пример.

Множимое

Множитель .

Требуется найти т.е. найти .

Первый шаг.Определение знака произведения.

.

Второй шаг.Определение цифровой части (модуля) произведения

1011 1011

1101 1101

1101 1101

10001111 10001111

Третий шаг.Ограничение результата четырьмя разрядами и округление 1001.

Результат операции умножения

Не нашли, что искали? Воспользуйтесь поиском по сайту: