Многовходовой сумматор

Многовходовой сумматор

Реферат

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

Известен сумматор с переменным модулем сложения (RU №2183347 С2, МПК G06F 7/50, заявлен 24.03.2000, опубликован 10.06.2002), содержащий два n-разрядных сумматора, компаратор, элемент ИЛИ, блок управляемых инверторов, шину n-разрядного модуля, причем первая группа входов компаратора подсоединена к выходам первого сумматора, а вторая группа входов компаратора подсоединена к входной шине модуля, входы элемента ИЛИ соединены соответственно с выходом переноса первого сумматора и выходом компаратора. Компаратор сравнивает образованную сумму с модулем сложения и в случае, когда полученная сумма равна или больше модуля, вычитает из суммы значение модуля и вырабатывает сигнал переноса.

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

Известен многовходовой сумматор (SU №1679483 А1, МПК G06F 7/50, заявлен 23.03.1989, опубликовано 23.09.1991, Бюл. №35), имеющий информационные входы, тактовый вход, вход обнуления, вход режима работы, блоки четырехвходового одноразрядного суммирования, блок суммирования, накапливающий сумматор. В основу работы положен алгоритм быстрого вычисления разрядных сумм и их вычисление с учетом весовых коэффициентов.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятый за прототип счетчик числа единиц в слове данных (Дж. Ф. Уэйкерли. Проектирование цифровых устройств. В 2-х томах. - М.: Постмаркет, 2002. - 1088 с., рис.6.15, с.606-609), содержащий древовидную структуру сумматоров - на первом уровне одноразрядные сумматоры, на втором - трехразрядные сумматоры, на третьем - четырехразрядные сумматоры и т.д.

Недостаком данного устройства является то, что проводится суммирование одноразрядных чисел.

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

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

Указанный технический результат при осуществлении изобретения достигается тем, что в многовходовой сумматор, содержащий древовидную структуру сумматоров, введены элемент ИЛИ и компаратор, причем информационные входы многовходового сумматора объединены в М групп n-разрядных внешних входов данных устройства, (М-1) n-разрядных сумматоров древовидной структуры объединены в к каскадов (k=]log₂M[большее целое), причем первый каскад содержит [М/2] (целая часть) сумматоров, второй каскад содержит [М/4] сумматоров,…, i-й каскад содержит [М/2ⁱ] сумматоров (i=3, 4,…, k-1),…, k-й каскад содержит один сумматор, внешние нечетные входы данных устройства соединены с первыми группами входов соответствующих сумматоров первого каскада сумматоров, вторые группы входов которых соединены с внешними четными группами входов данных устройства, информационные выходы нечетных сумматоров i-го каскада (i=2, 2,…, k-1) соединены с первыми группами входов соответствующих сумматоров (i+1)-го каскада, вторые группы входов которых соединены с информационными выходами четных сумматоров i-го каскада, информационные выходы сумматора k-го каскада являются первыми выходами устройства и соединены со второй группой входов компаратора, первая группа входов которого соединена с внешней группой входов S устройства максимума суммы данных, выход компаратора соединен с первым входом элемента ИЛИ, другие входы которого соединены с выходами переносов всех (М-1) сумматоров, а выход элемента ИЛИ является вторым выходом устройства.

На фиг. 1 приведена схема предлагаемого многовходового сумматора для М=16 групп n-разрядных входов устройства.

На фиг. 1 приняты следующие обозначения: сумматоры первого каскада 1₁, 1₂, …, 1₈ (индекс указывает номер сумматора в каскаде), сумматоры второго каскада 2₁, 2₂, 2₃, 2₄. сумматоры третьего каскада 3₁ 3₂, сумматор четвертого каскада 4₁, компаратор 5, элемент ИЛИ 6, вход 7 порога максимальной суммы S, первые выходы 8 суммы, второй выход 9 превышения заданного порога.

Многовходовой сумматор содержит М групп n-разрядных внешних входов данных устройства D1-D16 (на фиг. 1 М=16). В состав многовходового сумматора включены (М-1) n-разрядных сумматоров, образующих древовидную структуру, при этом сумматоры объединены в k каскадов (k=]log₂M[большее целое). На фиг.1 количество каскадов k=4 (]log₂l6[). Первый каскад содержит восемь сумматоров 1₁, 1₂, …, 1₈, второй каскад содержит четыре сумматора 2₁, 2₂, 2₃, 2₄, третий каскад содержит два сумматора 3₁, 3₂, четвертый каскад содержит один сумматор 4₁. Внешние входы устройства D1-D16 подсоединены к соответствующим входам сумматоров первого каскада 1₁, 1₂, …, 1₈. Выходы сумматоров первого каскада 1₁, 1₂, …, 1₈ соединены с соответствующими входами сумматоров второго каскада 2₁, 2₂, 2₃, 2₄, выходы которых соединены с входами сумматоров третьего каскада 3₁, 3₂, выходы которых соединены с входами сумматора четвертого каскада 4₁.

Выходы сумматора четвертого каскада 4₁ являются первыми выходами устройства 8. Первая группа входов компаратора 5 соединена с внешней группой входов 7 устройства максимума суммы данных S, а вторая группа входов соединена с выходами сумматора четвертого каскада 4₁.

Выход компаратора 5 соединен с первым входом элемента ИЛИ 6, другие входы которого соединены с выходами переносов СО всех (M-1) сумматоров. Выход элемента ИЛИ 6 является вторым выходом 9 устройства превышения заданного порога S.

Предлагаемый многовходовой сумматор работает следующим образом.

На М групп n-разрядных внешних входов устройства D1-D16 подается массив входных данных. Входные данные попарно складываются на сумматорах первого каскада 1₁, 1₂, …, 1₈, на выходах которых формируются значения суммы и единичные сигналы переноса CO=1, при превышении n-разрядной суммы. Далее значения сумм первого каскада складываются на сумматорах второго каскада 2₁, 2₂, 2₃, 2₄ на выходах которых формируются значения суммы и сигналы переноса CO=1, при превышении n-разрядной суммы. Далее аналогично вычисляются суммы и формируются сигналы переноса CO=1 для третьего и четвертого каскадов.

В результате суммирования на выходе сумматора 4₁ четвертого каскада будет получена сумма массива входных данных, которая передается на группу первых выходов 8. Кроме того, данная сумма на компараторе 5 сравнивается с заданным на входе 7 порогом максимальной суммы S. Если сумма массива превышает порог S, то на выходе компаратора 5 формируется единичный сигнал.

Единичные сигналы переносов CO=1 сумматоров всех и сигнал превышения порога S с компаратора 5 поступают на элемент ИЛИ 6 и с его выхода передаются на второй выход устройства 9.

В предлагаемом устройстве каждый из элементов массива входных данных D1-D16 имеет разрядность n. При этом порог суммы S также имеет разрядность n. Введение проверки сигналов переносов сумматоров позволило ввести у всех сумматоров единую разрядность n.

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

Многовходовой сумматор, содержащий древовидную структуру сумматоров, отличающийся тем, что в него дополнительно введены элемент ИЛИ и компаратор, причем информационные входы многовходового сумматора объединены в М групп n-разрядных внешних входов данных устройства, (М-1) n-разрядных сумматоров древовидной структуры объединены в к каскадов (k=]log₂M[большее целое), причем первый каскад содержит [М/2] (целая часть) сумматоров, второй каскад содержит [М/4] сумматоров,…, i-й каскад содержит [М/2ⁱ] сумматоров (i=3, 4,…, k-1),…, k-й каскад содержит один сумматор, внешние нечетные входы данных устройства соединены с первыми группами входов соответствующих сумматоров первого каскада сумматоров, вторые группы входов которых соединены с внешними четными группами входов данных устройства, информационные выходы нечетных сумматоров i-го каскада (i=l, 2,…, k-1) соединены с первыми группами входов соответствующих сумматоров (i+1)-го каскада, вторые группы входов которых соединены с информационными выходами четных сумматоров i-го каскада, информационные выходы сумматора k-го каскада являются первыми выходами устройства и соединены со второй группой входов компаратора, первая группа входов которого соединена с внешней группой входов S устройства максимума суммы данных, выход компаратора соединен с первым входом элемента ИЛИ, другие входы которого соединены с выходами переносов всех (М-1) сумматоров, а выход элемента ИЛИ является вторым выходом устройства.