1 Постановка задачи

1.1Общие сведения о работе сумматора. Принцип построения сумматоров

Сумматор осуществляет арифметическое суммирование n-разрядных кодов X=(x(n-1),..,x0) и Y=(y(n-1),..,y0). Правила сложения двух одноразрядных двоичных чисел:

0 (+) 0 = 0

0 (+) 1 = 1 (+) 0 = 1

1 (+) 1 = 0 и перенос 1 в старший разряд.

Операция (+) называется - сумма по модулю два. Устройство реализующее эти правила называется одноразрядным полусумматором и имеет два входа и два выхода. Сложение трех одноразрядных чисел производится следующим образом:

0 (+) 0 (+) 0 = 0

0 (+) 0 (+) 1 = 1

0 (+) 1 (+) 1 = 0 и перенос 1 в старший разряд

1 (+) 1 (+) 1 = 1 и перенос 1 в старший разряд.

Устройство реализующее эти правила называется одноразрядным полным сумматором (ОПС) и имеет три входа и два выхода. Таблица истинности ОПС приведена на рис.1, слева.

Рисунок 1

xi,yi - одноименные двоичные разряды чисел X и Y, ci - перенос из предыдущего разряда, si - частичная сумма по модулю два и c(i+1) - перенос в следующий разряд. Значения c(i+1) совпадают со значениями функции мажоритарности, поэтому воспользуемся готовым решением:

c(i+1) = xi*yi + xi*ci + yi*ci.                                                                                        (1)

Таблица Карно для si приведена на рис.1 справа. Из таблицы находим: si = xi*~yi*~ci + ~xi*~yi*ci + xi*yi*ci+ ~xi*yi*~ci = ~yi(xi*~ci + ~xi*ci) + yi(xi*ci + ~xi*~ci) = ~yi(xi (+) ci) + yi(xi*ci + ~xi*~ci). Выражение в последней скобке необходимо преобразовать, используя соотношение двойственности.

xi*ci + ~xi*~ci = ~(xi*ci) * ~(~xi*~ci) = (~xi+~ci) *(xi+ci)= ~xi*xi + ~xi*ci + ~ci*xi + ~ci*ci = ~xi*ci + xi*~ci = ~(xi (+) ci) = ~F6 = F9,

где  F6=x1 (+) x0 - исключающее ИЛИ,

F9= ~(x1 (+) x0) исключающее - ИЛИ-НЕ

С учетом последнего выражения

si = ~yi(xi (+) ci) + yi~(xi (+) ci) =

yi (+) (xi (+) ci) = yi (+) xi (+) ci.                                                                                  (2)

Схема полного одноразрядного сумматора соответствующая уравнениям (1) и (2) и её условное обозначение приведены на рисунке 2.

Рисунок 2

Сумматор с последовательным переносом для сложения n- разрядных двоичных чисел показан на схеме (рис.3.). К его недостатку относится большое время задержки, в наихудшем случае, когда от сложения x0,y0 возникает сквозной перенос через все разряды до выхода s(n-1). При двухъярусной схеме одноразрядного сумматора, задержка сигнала от входов до выходов составит 2tзд.р., если считать задержку в каждом ярусе одинаковой. Суммарная величина задержки будет равна:

tзд.р.посл.сумматора = n*2tзд.р.                                                                                (3)

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

Рисунок 3

В ЭВМ сумматор является центральным узлом арифметико-логического устройства (АЛУ) и от его быстродействия зависит производительность компьютера. Поэтому применяются сумматоры с параллельной схемой переноса. Выражение (1) для младшего разряда можно преобразовать, используя тождество для функции ИЛИ: x + y = ~x*y + x*~y + xy. В правой части равенства совершенной дизъюнктивной нормальной формой (СДНФ) выражения (4) функции ИЛИ. Тогда

c1 = x0*y0 + x0*c0 + y0*c0 = x0*y0 + c0(x0 + y0) =

x0*y0 + c0(~x0*y0 + x0*~y0 + x0*y0) =

x0*y0(с0 +1) + c0(~x0*y0 + x0*~y0) =

x0*y0 + с0(x0 (+) y0).                                                                                            (5)

Уравнениям (2) и (5) соответствует схема на рис.4

Рисунок 4

Если в каждом разряде сумматора использовать такой одноразрядный сумматор, то никакого выигрыша в скорости не будет. Узел, обведенный точками, называется узлом переноса (УП), а функции gi и pi называются функциями генерации переноса и распространения переноса. С учетом этого можно записать:

c1 = g0 + p0*c0, с2 = g1 + p1*c1 =                                                                      (6)

     = g1 + p1*g0 + p1*p0*c0,                                                                                (7)

с3 = g2 + p2*c2 =                                                                                                   (8)

     = g2 + p2*g1 + p2*p1*g0 + p2*p1*p0*c0,                                                      (9)

......, и так далее. Выражения (6, 8) - это еще последовательный сумматор, т.к. c3 зависит от c2, c2 зависит от c1, а c1 зависит от c0. Выражения (7, 9) соответствуют уже параллельному, т.к. величина ci снимается с выхода предыдущего разряда, в котором она формируется параллельно из всех первичных переменных. Схемы узлов переноса УП1 и УП2 приведены на рис.5.

Рисунок 5

Из рис.4 и 5 видно, что узел сложения в каждом разряде остается неизменным, а изменяется только узел переноса, причем задержка сигнала от входов xi, yi до c(i+1) остается неизменной и для 3-ярусной схемы равна 3tзд.р.. Суммарная задержка в каждом разряде увеличится на время прохождения сигнала от входа ci до si, т.е. на величину tзд.р., и составит: tзд.р.паралл.сумматора = 4tзд.р. независимо от количества разрядов. За это приходится платить усложнением узла переноса от разряда к разряду.

1.2 Запись десятичных чисел

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

Таблица 1.

Остальные комбинации двоичного кода в тетраде являются запрещенными. Запишем пример двоично-десятичного кода:

1258 = 0001 0010 0101 1000

589 = 0000 0101 1000 1001

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

1.3Суммирование двоично-десятичных чисел

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

Каждое целое число занимает два байта (две ячейки) в памяти компьютера, т.е. 16 разрядов. При этом старший разряд отводится под знак числа. У положительных чисел в старшем разряде находится 0, а у отрицательных — 1. Таким образом, можно закодировать числа в диапазоне от —32 768 до 32 767. Отрицательные числа кодируются в дополнительном коде.

Правила создания дополнительного кода:

1)     

2)     

Примеры:

3-           0000000000000011

- 3 -        11111111 11111101

9-           0000000000001001

-9-          11111111 11110111

32 767-  0111111111111111

—32 767-   10000000 00000001

—32 768-   10000000 00000000 2 Построение АЛУ