КОМБИНАЦИОННЫЙ СУММАТОР СТРУКТУРНЫХ КОДОВ Российский патент 1994 года по МПК G06F7/49 

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

Известно устройство для сложения чисел, представленных в двоичной избыточной системе счисления, содержащее последовательно соединенные логические узлы и трехвходовые одноразрядные двоичные сумматоры (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-разрядного кода.

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

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

3i≅>i5^≅5
Следовательно, правило сложения имеет вид
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.

Изобретение относится к автоматике и вычислительной технике и может быть использовано для параллельного суммирования многоразрядных двоичных чисел. Цель изобретения - увеличение быстродействия устройства для счет одновременного суммирования трех чисел, представленных в двоичной избыточной минимальной системе счисления. Сумматор содержит разряды, каждый из которых состоит из трехвходового одноразрядного двоичного сумматора, мажоритарного элемента, четырех элементов ИЛИ, четырех элементов И, двух элементов ИМПЛИКАЦИЯ, элемента ЗАПРЕТ. Второй и четвертый разряды содержат дополнительно по одному элементу ИЛИ. 3 ил., 1 табл.

КОМБИНАЦИОННЫЙ СУММАТОР СТРУКТУРНЫХ КОДОВ, содержащий в каждом 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)-го разряда.