устройство для сложения и вычитания n чисел по модулю 2ⁿ- 1

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

УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ N ЧИСЕЛ ПО МОДУЛЮ 2ⁿ-1, содержащее сумматор по модулю выход которого соединен с i-м выходом устройства, отличающееся тем, что оно содержит m уровней многоходовых одноразрядных сумматоров (m находится из условия K₁ N, K_m 3, K_j log₂ K_j-1[, где K_j количество входов сумматоров j-го уровня, K_i и K_m количество входов сумматоров первого и m-го уровней соответственно), при этом вход i-го N-входового однозарядного сумматора первого уровня соединен с входом i-го разряда l-го входного операнда, входы i-го K_h-входового одноразрядного сумматора уровня соединены с выходами сумматоров (h 1)-го уровня, имеющими вес A (A находится из условия A mod (2ⁿ 1) 2^i-1), выход суммы i-го одноразрядного двоичного сумматора m-го уровня соединен с первым входом i-го разряда сумматора по модулю 2ⁿ-1, второй вход S-го разряда которого соединен с выходом переноса (S-1)-го одноразрядного двоичного сумматора m-го уровня, выход переноса n-го одноразрядного двоичного сумматора m-го уровня соединен с вторым входом первого разряда сумматора по модулю 2ⁿ-1, при этом i-е разряды входных операндов и сумматора по модулю 2ⁿ-1 имеют вес 2^i-1.

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

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

Известен сумматор по модулю три двух полных двухразрядных операндов, который содержит восемь элементов И, два элемента ИЛИ, два элемента ИЛИ-НЕ и два элемента сложения по модулю два [1]

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

Наиболее близким техническим решением к предлагаемому является сумматор по модулю 2ⁿ-1, содержащий n-элементов И, n-элементов ИЛИ, n-элементов ИЛИ-НЕ, n-элементов РАВНОЗНАЧНОСТЬ и n-элементов НЕРАВНОЗНАЧНОСТЬ [2]

Недостатком устройства также являются ограниченные функциональные возможности, так как оно не выполняет операций сложения и вычитания по модулю 2ⁿ-1 над N операндами.

На чертеже в качестве примера представлена схема устройства для сложения и вычитания N чисел по модулю 2ⁿ-1 при N-25 и n-4.

Устройство содержит n= 4 25-входовых одноразрядных сумматора первого уровня 1₁ 1₄, n=4 5-входовых одноразрядных сумматора второго уровня 2₁ 2₄, n= 4 одноразрядных двоичных сумматора третьего уровня 3₁ 3₄, сумматор по модулю 2⁴-1= 15 4, входы первых 5₁ 29₁, вторых 5₂-29₃, третьих 5₃ -29₃ и четвертых 5₄ 29₄ разрядов входных операндов, причем 5₄ 29₄ входы старших, а 5₁ 29₁ входы младших разрядов операндов, и выходы результата 32₁ 32₄, причем 32₄ выход старшего, а 32₁ выход младшего разряда результата.

В общем случае устройство для сложения и вычитания N чисел по модулю 2ⁿ-1 содержит сумматор по модулю 2ⁿ-1, i-й (i=), выход которого соединен с i-м выходом устройства, и m уровней многовходовых одноразрядных сумматоров (m находится из условия: k₁=N, k_m=3, k_j=log₂k_j-1[, где j=, k_j количество входов сумматоров j-го уровня, k₁ и k_m- количество входов сумматоров первого и m-го уровня соответственно). В i-м N-входовом одноразрядном сумматоре первого уровня l-й (l=) вход соединен с входом i-го разряда l-го операнда. Входы i-го k_h-входового одноразрядного сумматора h-го (h=) уровня соединены с выходами сумматоров (h-1)-го уровня, имеющими вес А (А определяется из условия: А mod(2ⁿ-1)=2i^-1). Выход суммы i-го одноразрядного двоичного сумматора m-го уровня соединен с первым входом i-го разряда сумматора по модулю 2ⁿ-1, второй вход s-го (s=) разряда которого соединен с выходом переноса (s-1)-го одноразрядного двоичного сумматора m-го уровня. Выход переноса n-го одноразрядного двоичного сумматора m-го уровня соединен с вторым входом первого разряда сумматора по модулю 2ⁿ-1. При этом i-е разряды входных операндов сумматора по модулю 2ⁿ-1 имеют вес 2^i-1.

При n=4 и N=25 входы первого 25-входового одноразрядного сумматора первого уровня l₁ cоединены соответственно со входами 5₁ 29₁устройства, входы второго 25-входового одноразрядного сумматора первого уровня l₂ соединены соответственно с входами 5₂ 29₂ устройства, входы третьего 25-входового одноразрядного сумматора первого уровня l₃соединены соответственно со входами 5₃ 29₃ устройства, входы четвертого 25-входового одноразрядного сумматора первого уровня l₄соединены соответственно со входами 5₄ -29₄ устройства. Входы первого 5-входового одноразрядного сумматора второго уровня 2₁ соединены с выходами сумматоров первого уровня, имеющими вес 1 или 16, входы второго 5-входового одноразрядного сумматора второго уровня 2₂ соединены с выходами сумматоров первого уровня, имеющими вес 2 или 32, входы третьего 5-входового одноразрядного сумматора второго уровня 2₃соединены с выходами сумматоров первого уровня, имеющими вес 4 или 64, входы четвертого 5-входового одноразрядного сумматора 2₄ соединены с выходами сумматоров первого уровня, имеющими вес 8 или 128. Входы первого одноразрядного двоичного сумматора третьего уровня 3₁ соединены с выходами сумматоров второго уровня, имеющими вес 1 или 16, входы второго одноразрядного двоичного сумматора третьего уровня 3₂ соединены с выходами сумматоров второго уровня, имеющими вес 2 или 32, входы третьего одноразрядного двоичного сумматора третьего уровня 3₃ соединены с выходами сумматоров второго уровня, имеющими вес 4, входы четвертого одноразрядного двоичного сумматора третьего уровня 3₄ соединены с выходами сумматоров второго уровня, имеющими вес 8. Выход переноса первого одноразрядного двоичного сумматора третьего уровня 3₁ соединен с вторым входом второго разряда 31₂ сумматора по модулю пятнадцать 4, первый вход второго разряда 30₂ которого соединен с выходом суммы второго одноразрядного двоичного сумматора третьего уровня 3₂, выход переноса которого соединен с вторым входом третьего разряда 31₃сумматора по модулю пятнадцать 4, первый вход третьего разряда 30₃которого соединен с выходом суммы третьего одноразрядного двоичного сумматора третьего уровня 3₃, выход переноса которого соединен с вторым входом четвертого разряда 31₄ сумматора по модулю пятнадцать 4, первый вход четвертого разряда 30₄ которого соединен с выходом суммы четвертого одноразрядного двоичного сумматора третьего уровня 3₄, выход переноса которого соединен с вторым входом первого разряда 31₁ сумматора по модулю пятнадцать 4, первый вход первого разряда 30₁ которого соединен с выходом суммы первого одноразрядного двоичного сумматора третьего уровня 3₁. Выходы первого, второго, третьего и четвертого разрядов сумматора по модулю пятнадцать 4 соединены соответственно с выходами 32₁, 32₂, 32₃ и 32₄ устройства, при этом выход 32₁ соответствует младшему разряду сумматора по модулю пятнадцать 4, а выход 32₄ его старшему разряду.

Устройство для сложения и вычитания N чисел по модулю 2ⁿ-1 при N=25 и n= 4 работает следующим образом. На входы 5₁ 5₄, 6₁ 6₄, 29₁ 29₄ устройства подаются соответственно четырехразрядные полные операнды

X₁= 2^i-1x_i1, X₂=2^i-1x_i2,..., X₂₅=2^i-1x_i25, где x_ij{0,1} j=1,25, X_j{0,15}

На выходах 33₁ 33₄ формируется четырехразрядный двоичный код результата R 2^i-1r_i, операций сложения и вычитания двадцати пяти чисел по модулю пятнадцать, r_i {0,1} R 0,14} Причем на выходе 33₄ реализуется старший разряд r₄, а на выходе 33₁ младший разряд r₁ результата R.

Предлагаемое устройство реализует 2^N операций сложения и вычитания вида R X mod(2ⁿ-1) (1)

Выполняемая операция определяется путем соответствующей коммутации прямых и обратных кодов операндов на входах устройства, а именно: если i-й операнд Х_i входит в уравнение (1) со знаком "плюс", то на вход устройства подается его прямой код, а если со знаком "минус" то обратный.

Укажем, что k-входовый одноразрядный сумматор работает следующим образом. На вход сумматора подаются k одноразрядных двоичных операндов. На выходе формируется позиционный двоичный код числа операндов, имеющих значение "1". Веса выходов сумматоров на чертеже обозначены цифрами 1, 2, 4, 8 и 16.

Устройство для сложения и вычитания N чисел по модулю 2ⁿ-1 построено с использованием следующего соотношения:

(-X) mod(2ⁿ-1) mod(2ⁿ-1), где X2^i-1x_i.

Отметим, что в качестве сумматора 4, входящего в состав заявляемого устройства, может быть использован сумматор, выполняющий сложение по модулю 2ⁿ-1 двух полных операндов. Работа такого сумматора при n=4 описывается табл. 1.

В табл. 2 приведены значения количества уровней одноразрядных многовходовых сумматоров m и количества входов сумматоров каждого уровня k_j(j=) в зависимости от числа входных операндов N. Как видно из таблицы, на практике количество уровней сумматоров m не превышает четырех, так как реально число входных операндов N<<2-1.

Достоинством заявляемого устройства являются широкие функциональные возможности. Так, предлагаемое устройство выполняет 2^N операций сложения/вычитания по модулю 2ⁿ-1 над N операндами. Известные же устройства такими возможностями не обладают.