комбинационный сумматор структурных кодов

Формула изобретения

КОМБИНАЦИОННЫЙ СУММАТОР СТРУКТУРНЫХ КОДОВ, содержащий в каждом i-м разряде ((i = ), где n - разрядность операндов) трехвходовой одноразрядный двоичный сумматор, четыре элемента И и четыре элемента ИЛИ, причем выход первого элемента И i-го разряда соединен с первым входом первого элемента ИЛИ данного разряда, второй вход которого соединен с выходом второго элемента И данного разряда, первые входы второго элемента ИЛИ и третьего элемента И данного разряда соединены с выходом переноса из (K + 5)-го разряда (k i, k = , выход второго элемента ИЛИ i-го разряда подключен к первому входу четвертого элемента И данного разряда, выход которого соединен с первым входом третьего элемента ИЛИ данного разряда, выход переноса из данного разряда подключен к входам переносов (j - 2)-го и (j - 3)-го, (j i, j = ) разрядов, отличающийся тем, что в каждый разряд комбинационного сумматора для трех слагаемых введены элементы ИЛИ, мажоритарный элемент, два элемента ИМПЛИКАЦИЯ, элемент ЗАПРЕТ и два элемента ИЛИ соответственно в второй и четвертый разряды сумматора, причем входные шины первого, второго и третьего операндов данного разряда подключены соответственно к первому, второму и третьему входам трехвходового одноразрядного двоичного сумматора i-го разряда, выход суммы которого подключен к вторым входам третьего и четвертого элементов И данного разряда, к первому входу второго элемента И данного разряда и к инверсному входу первого элемента ИМПЛИКАЦИЯ данного разряда, выход которого подключен к первому входу первого элемента И данного разряда, второй вход которого соединен с выходом элемента ЗАПРЕТ и инверсным входом второго элемента ИМПЛИКАЦИЯ данного разряда, выход которого подключен к второму входу второго элемента И i-го разряда, а прямой вход соединен с вторым входом третьего элемента ИЛИ данного разряда, инверсным входом элемента ЗАПРЕТ данного разряда и выходом мажоритарного элемента i-го разряда, первый вход которого соединен с выходом четвертого элемента ИЛИ данного разряда и вторым входом второго элемента ИЛИ данного разряда, выход которого подключен к прямому входу элемента ЗАПРЕТ i-го разряда, выход переноса трехвходового одноразрядного двоичного сумматора данного разряда подключен к прямому входу первого элемента ИМПЛИКАЦИЯ данного разряда и к третьим входам третьих элементов И и ИЛИ данного разряда, выход первого элемента ИЛИ данного разряда является выходом суммы i-го разряда, выход третьего элемента И каждого j-го разряда соединен с первым входом четвертого элемента ИЛИ (j - 2)-го разряда и вторым входом четвертого элемента ИЛИ (j - 3)-го разряда, выход третьего элемента И второго разряда подключен к первому входу четвертого элемента ИЛИ первого разряда, выход третьего элемента ИЛИ каждого l-го разряда (l i, l = ) подключен к второму входу мажоритарного элемента (l + 2)-го разряда и к третьему входу второго элемента ИЛИ (l + 2)-го разряда, первый, второй и третий входы пятого элемента ИЛИ второго разряда подключены соответственно к выходам третьих элементов ИЛИ пятого, шестого и седьмого разрядов, первый и второй входы пятого элемента ИЛИ четвертого разряда подключены соответственно к выходам третьих элементов ИЛИ восьмого и девятого разрядов, входы пятых элементов ИЛИ второго и четвертого разрядов подключены к третьим входам мажоритарных элементов соответственно второго и четвертого разрядов и к первым входам второго элемента ИЛИ и третьего элемента И второго и четвертого разрядов, третий элемент ИЛИ каждого k-разряда соединен с третьим входом мажоритарного элемента (k - 5)-го разряда.

Описание изобретения к патенту

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

Известно устройство для сложения чисел, представленных в двоичной избыточной системе счисления, содержащее последовательно соединенные логические узлы и трехвходовые одноразрядные двоичные сумматоры (1). Недостаток данного устройства - низкое быстродействие.

Наиболее близким к изобретению является комбинационный сумматор (2), содержащий в каждом разряде трехвходовой одноразрядный двоичный сумматор, четыре элемента И, пять элементов ИЛИ, причем входные шины первого и второго операндов каждого i-го разряда (i = (i = , где n - разрядность операндов) подключены, соответственно, к первому и второму входам первого элемента ИЛИ и первого элемента И i-го разряда, выход первого элемента И данного разряда соединен с первым входом второго элемента ИЛИ i-го разряда, второй вход которого соединен с выходом второго элемента И i-го разряда, первый вход которого соединен с первыми входами третьего элемента ИЛИ, третьего элемента И, пятого элемента ИЛИ данного разряда и выходом переноса трехвходового одноразрядного двоичного сумматора (i+1)-го разряда, второй вход второго элемента И i-го разряда соединен со вторым входом третьего элемента ИЛИ i-го разряда и выходом переноса трехвходового одноразрядного двоичного сумматора (i-2)-го разряда, выход третьего элемента ИЛИ i-го разряда подключен к первому входу четвертого элемента ИЛИ данного разряда, выходы первого и четвертого элементов ИЛИ i-го разряда соединены соответственно с первым и вторым информационными входами трехвходового одноразрядного двоичного сумматора данного разряда, вход переноса которого подключен к выходу второго элемента ИЛИ i-го разряда, третий вход которого подключен к выходу третьего элемента И i-го разряда, второй вход которого соединен со вторым входом пятого элемента ИЛИ i-го разряда и выходом переноса трехвходового одноразрядного двоичного сумматора (i-3)-го разряда, третий вход пятого элемента ИЛИ i-го разряда соединен с выходом переноса трехвходового одноразрядного двоичного сумматора (i-5)-го разряда и третьим входом третьего элемента И данного разряда, четвертый вход которого соединен с входом разрешения суммирования в минимальной и оптимальной системах счисления и первым входом четвертого элемента И i-го разряда, второй вход которого соединен с выходом пятого элемента ИЛИ i-го разряда, а выход - со вторым входом четвертого элемента ИЛИ данного разряда, третий вход второго элемента И i-го разряда соединен со входом разрешения суммирования в "Фибоначчиевой" системе счисления.

Недостаток этого устройства - низкое быстродействие.

Цель изобретения - повышение быстродействия сумматора за счет способности суммировать одновременно три числа, представленных в двоичной избыточной минимальной системе счисления.

Любое натуральное число А в двоичной минимальной системе счисления представляется в виде многочлена

A =(i) ,, где _i {0,1}

(i) = ,1

Значение (n+2) определяет мощность минимального n-разрядного кода.

Минимальная система счисления предполагает наличие не менее четырех нулей после каждой единицы.

Метод сложения основан на выражениях, вытекающих из рекуррентного соотношения

+((- ^при_при ³_{i >} ⁱ₅ ⁵

Следовательно, правило сложения имеет вид

0 + 0 + 0 = 0

0 + 0 + 1 = 1

0 + 1 + 0 = 1

1 + 0 + 0 = 1

0 + 1 + 1 = 100001 при 3 i 5

0 + 1 + 1 = 10000001 при i > 5

1 + 1 + 1 = 101001 при 3 i 5

1 + 1 + 1 = 10100001 при i > 5

Анализ выражения позволяет предположить, что операция сложения будет протекать с появлением в ряде случаев промежуточных сумм. Это обусловлено приходом сигналов переноса в разряды, в которых есть единица. Однако, учитывая, что минимальная форма представления числе предполагает наличие не менее чем четырех нулей после каждой единицы, видно, что при наличии единицы в двух или трех слагаемых данного разряда возможен приход сигнала переноса только из (i+5)-го разряда, при одном слагаемом - из (i+5)-го и (i-2)-го разрядов.

Такой анализ показывает, что в сложении участвуют не более четырех сигналов. При этом правило сложения принимает следующий вид:

1 + 1 + 1 + 1 = 1 0 1 0 11 0 1

Перенос в (i-2)-ой разряд осуществляется беспрепятственно, при переносе в (i-3)-й разряд в него же может прийти сигнал переноса из (j+2)-го разряда (j = i-5).

В таблице представлены значения сигналов, поясняющие работу i-го одноразрядного сумматора

При составлении таблицы полагалось, что на входы трехвходового одноразрядного двоичного сумматора подаются сигналы суммируемых слагаемых в данном разряде а; b; c;

В таблице обозначено : S - сигнал суммы трехвходового одноразрядного двоичного сумматора, P - сигнал переноса трехвходового одноразрядного двоичного сумматора, Р_i-2,i, P_i+5,i, P_i+2,i, P_i+3,i - сигналы переноса в i-й разряд сумматора соответственно из (i-2)-го, (i+5)-го, (i+2)-го, (i+3)-го разрядов, S_i - сигнал суммы одноразрядного сумматора, P_i,i+2, P_i,i-5, P_i,i-2, P_i,i-3 - сигналы переноса из i-го разряда сумматора соответственно в (i+2)-й, (i-5)-й, (i-2)-й, (i-3)-й разряды.

На основе данной логики строится комбинационный сумматор для трех слагаемых.

Рассмотрим пример сложения чисел A, B и C.

B и C A = B = 00001000010000100001000

С = 00100000010000000100000

Для сложения чисел A, B и C и минимизации кода суммы потребовалось 11 тактов.

Сущность изобретения состоит в реализации выражений (2), (3) в соответствии с таблицей.

На фиг. 1 приведена структурная схема комбинационного сумматора для трех слагаемых; на фиг. 2 - функциональная схема p-го разряда сумматора (p = 1,3,5-n); на фиг. 3 - функциональная схема q-го разряда сумматора (q = 2,4).

Комбинационный сумматор для трех слагаемых содержит n (где n - разрядность операндов) разрядов 1, имеющих выходы 2, 3 переносов, входные шины первого 4, второго 5 и третьего 6 слагаемых, шину суммы 7.

Каждый p-n разряд 1, имеющий входы 8-11 переносов, содержит трехвходовый одноразрядный двоичный сумматор 12 с выходами 13, 14 суммы и переноса, мажоритарный элемент 15, четыре элемента или 16-19, четыре элемента И 20-23, два элемента ИМПЛИКАЦИЯ 24, 25, элемент ЗАПРЕТ 26.

Каждый q-й разряд содержит, кроме того, элемент ИЛИ 27 и входы 28, 29, 30 переносов.

Разряд 1 предназначен для суммирования разрядов слагаемых и сигналов переноса, поступающих в данный разряд и выдачи значения суммы данного разряда на выходную шину 7 и сигналов переноса из данного разряда в соседние.

Элемент ИЛИ 27 предназначен для формирования сигнала переноса соответственно из пятого, шестого и седьмого разрядов во второй и из восьмого и девятого разрядов в четвертый.

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

Элементы ИЛИ 16, ИЛИ 17 предназначены для выдачи сигнала о наличии переноса в данный разряд.

Мажоритарный элемент 15 предназначен для выдачи сигнала при наличии двух сигналов переноса в данный разряд.

Элементы ИМПЛИКАЦИЯ 24, 25, ЗАПРЕТ 26, элементы И 21, И 22 и элемент ИЛИ 18 предназначены для суммирования сигналов, поступающих с трехвходового одноразрядного двоичного сумматора 14 и сигналов переноса в данный разряд и выдачи значения суммы данного разряда на шину суммы Г.

Элементы И 20 и ИЛИ 19 предназначены для формирования сигналов переноса из данного разряда в (i+2)-ой и (i-5)-й разряды.

Элемент И 23 предназначен для формирования сигналов переноса из данного разряда в (i-2)-й и (i-3)-й разряды.

Устройство работает следующим образом:

Сигналы разрядов слагаемых поступают на входы трехвходового одноразрядного двоичного сумматора 12. В зависимости от значений разрядов формируются сигналы для дальнейшего суммирования с сигналами переноса или выдачи сигнала через элементы ИМПЛИКАЦИЯ 24, И 21, 22, ИЛИ 18 на шину суммы 7.

При наличии в данном разряде "1" в одном из слагаемых на выходе 13 трехвходового одноразрядного двоичного сумматора 12 формируется единичный сигнал, поступающий на входы элемента И 20 и элемента И 22, на второй вход которого поступает сигнал с элемента ИМПЛИКАЦИЯ 24, свидетельствующий об отсутствии сигналов переноса в данный разряд. С выхода элемента И 22 сигнал через элемент ИЛИ 18 проходит на шину суммы 7. Если сигнал переноса в данный разряд есть, он через элемент ИЛИ 17 и ЗАПРЕТ 26 поступает на инверсный вход элемента ИМПЛИКАЦИЯ 25 и запирает его - сигнал суммы данного разряда не формируется. Одновременно сигнал переноса в данный разряд через элементы И 20 и ИЛИ 19 проходит на выход переноса 13 в (i+2)-ой и (i-5)-й разряды. При помощи "1" в одном из слагаемых и двух сигналов переноса в данный разряд элемент ЗАПРЕТ 26 запирается, открывается элемент ИМПЛИКАЦИЯ 25, формируется сигнал суммы данного разряда и сигнал переноса в (i+2)-ой и (i-5)-й разряды.

При наличии "1" в двух слагаемых в данном разряде сигнал с выхода 14 трехвходового одноразрядного двоичного сумматора 12 через элемент ИЛИ 19 проходит на выход переноса 3 в (i+2)-й и (i-5)-й разряды.

При одном сигнале переноса в данный разряд он через элементы ИЛИ 17 и ЗАПРЕТ 26 проходит на вход элемента И 21, на втором входе которого "1" с выхода элемента ИМПЛИКАЦИЯ 24.

При двух сигналах переноса в данный разряд они через мажоритарный элемент и элемент ИЛИ 19 поступают на выход переноса 3 в (i+2)-й, (i-5)-й разряды.

Наличие "1" в трех слагаемых приводит к формированию сигнала суммы данного разряда и сигналов переноса в (i+2)-ой, (i-5)-й разряды. Приход в это время в данный разряд сигнала переноса из (i+5)-го разряда вызывает формирование в элементе И 23 сигналов переноса в (i-2)-й и (i-3)-й разряды с выхода переноса 2.