Forbidden

You don't have permission to access /zzz_siteguard.php on this server.

УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ N ЧИСЕЛ ПО МОДУЛЮ 2n- 1 - Патент РФ 2047897
Главная страница  |  Описание сайта  |  Контакты
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ N ЧИСЕЛ ПО МОДУЛЮ 2n- 1
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ N ЧИСЕЛ ПО МОДУЛЮ 2n- 1

УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ N ЧИСЕЛ ПО МОДУЛЮ 2n- 1

Патент Российской Федерации
Суть изобретения: Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения средств аппаратурного контроля и цифровых устройств, работающих в системе остаточных классов. Устройство содержит сумматор по модулю 2n-1 и m уровней многовходовых одноразрядных сумматоров по n-сумматоров в каждом уровне (m находится из условия: k1= N, km= 3, kj= ]log2kj-1[, где количество входов сумматоров j-го уровня, k1 и km количество входов сумматоров первого и m- го уровней соответственно). Устройство для сложения и вычитания N-чисел по модулю 2n-1 работает следующим образом. На входы устройства подаются n-разрядные операнды X1...XN. На выходах формируется n-разрядный двоичный код результата R: Выполняемая операция определяется путем соответствующей коммутации прямых и обратных кодов операндов на входах устройства. 1 ил. 2 табл.
Поиск по сайту

1. С помощью поисковых систем

   С помощью Google:    

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2047897
Класс(ы) патента: G06F7/49
Номер заявки: 5065259/24
Дата подачи заявки: 12.10.1992
Дата публикации: 10.11.1995
Заявитель(и): Авгуль Леонид Болеславович[BY]; Курносенко Сергей Васильевич[BY]
Автор(ы): Авгуль Леонид Болеславович[BY]; Курносенко Сергей Васильевич[BY]
Патентообладатель(и): Авгуль Леонид Болеславович (BY)
Описание изобретения: Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения средств аппаратурного контроля и цифровых устройств, работающих в системе остаточных классов.
Известен сумматор по модулю три двух полных двухразрядных операндов, который содержит восемь элементов И, два элемента ИЛИ, два элемента ИЛИ-НЕ и два элемента сложения по модулю два [1]
Недостатком сумматора являются ограниченные функциональные возможности, так как он реализует только операцию сложения по фиксированному модулю, равному трем.
Наиболее близким техническим решением к предлагаемому является сумматор по модулю 2n-1, содержащий n-элементов И, n-элементов ИЛИ, n-элементов ИЛИ-НЕ, n-элементов РАВНОЗНАЧНОСТЬ и n-элементов НЕРАВНОЗНАЧНОСТЬ [2]
Недостатком устройства также являются ограниченные функциональные возможности, так как оно не выполняет операций сложения и вычитания по модулю 2n-1 над N операндами.
На чертеже в качестве примера представлена схема устройства для сложения и вычитания N чисел по модулю 2n-1 при N-25 и n-4.
Устройство содержит n= 4 25-входовых одноразрядных сумматора первого уровня 11 14, n=4 5-входовых одноразрядных сумматора второго уровня 21 24, n= 4 одноразрядных двоичных сумматора третьего уровня 31 34, сумматор по модулю 24-1= 15 4, входы первых 51 291, вторых 52-293, третьих 53 -293 и четвертых 54 294 разрядов входных операндов, причем 54 294 входы старших, а 51 291 входы младших разрядов операндов, и выходы результата 321 324, причем 324 выход старшего, а 321 выход младшего разряда результата.
В общем случае устройство для сложения и вычитания N чисел по модулю 2n-1 содержит сумматор по модулю 2n-1, i-й (i=), выход которого соединен с i-м выходом устройства, и m уровней многовходовых одноразрядных сумматоров (m находится из условия: k1=N, km=3, kj=log2kj-1[, где j=, kj количество входов сумматоров j-го уровня, k1 и km- количество входов сумматоров первого и m-го уровня соответственно). В i-м N-входовом одноразрядном сумматоре первого уровня l-й (l=) вход соединен с входом i-го разряда l-го операнда. Входы i-го kh-входового одноразрядного сумматора h-го (h=) уровня соединены с выходами сумматоров (h-1)-го уровня, имеющими вес А (А определяется из условия: А mod(2n-1)=2i-1). Выход суммы i-го одноразрядного двоичного сумматора m-го уровня соединен с первым входом i-го разряда сумматора по модулю 2n-1, второй вход s-го (s=) разряда которого соединен с выходом переноса (s-1)-го одноразрядного двоичного сумматора m-го уровня. Выход переноса n-го одноразрядного двоичного сумматора m-го уровня соединен с вторым входом первого разряда сумматора по модулю 2n-1. При этом i-е разряды входных операндов сумматора по модулю 2n-1 имеют вес 2i-1.
При n=4 и N=25 входы первого 25-входового одноразрядного сумматора первого уровня l1 cоединены соответственно со входами 51 291устройства, входы второго 25-входового одноразрядного сумматора первого уровня l2 соединены соответственно с входами 52 292 устройства, входы третьего 25-входового одноразрядного сумматора первого уровня l3соединены соответственно со входами 53 293 устройства, входы четвертого 25-входового одноразрядного сумматора первого уровня l4соединены соответственно со входами 54 -294 устройства. Входы первого 5-входового одноразрядного сумматора второго уровня 21 соединены с выходами сумматоров первого уровня, имеющими вес 1 или 16, входы второго 5-входового одноразрядного сумматора второго уровня 22 соединены с выходами сумматоров первого уровня, имеющими вес 2 или 32, входы третьего 5-входового одноразрядного сумматора второго уровня 23соединены с выходами сумматоров первого уровня, имеющими вес 4 или 64, входы четвертого 5-входового одноразрядного сумматора 24 соединены с выходами сумматоров первого уровня, имеющими вес 8 или 128. Входы первого одноразрядного двоичного сумматора третьего уровня 31 соединены с выходами сумматоров второго уровня, имеющими вес 1 или 16, входы второго одноразрядного двоичного сумматора третьего уровня 32 соединены с выходами сумматоров второго уровня, имеющими вес 2 или 32, входы третьего одноразрядного двоичного сумматора третьего уровня 33 соединены с выходами сумматоров второго уровня, имеющими вес 4, входы четвертого одноразрядного двоичного сумматора третьего уровня 34 соединены с выходами сумматоров второго уровня, имеющими вес 8. Выход переноса первого одноразрядного двоичного сумматора третьего уровня 31 соединен с вторым входом второго разряда 312 сумматора по модулю пятнадцать 4, первый вход второго разряда 302 которого соединен с выходом суммы второго одноразрядного двоичного сумматора третьего уровня 32, выход переноса которого соединен с вторым входом третьего разряда 313сумматора по модулю пятнадцать 4, первый вход третьего разряда 303которого соединен с выходом суммы третьего одноразрядного двоичного сумматора третьего уровня 33, выход переноса которого соединен с вторым входом четвертого разряда 314 сумматора по модулю пятнадцать 4, первый вход четвертого разряда 304 которого соединен с выходом суммы четвертого одноразрядного двоичного сумматора третьего уровня 34, выход переноса которого соединен с вторым входом первого разряда 311 сумматора по модулю пятнадцать 4, первый вход первого разряда 301 которого соединен с выходом суммы первого одноразрядного двоичного сумматора третьего уровня 31. Выходы первого, второго, третьего и четвертого разрядов сумматора по модулю пятнадцать 4 соединены соответственно с выходами 321, 322, 323 и 324 устройства, при этом выход 321 соответствует младшему разряду сумматора по модулю пятнадцать 4, а выход 324 его старшему разряду.
Устройство для сложения и вычитания N чисел по модулю 2n-1 при N=25 и n= 4 работает следующим образом. На входы 51 54, 61 64, 291 294 устройства подаются соответственно четырехразрядные полные операнды
X1= 2i-1xi1, X2=2i-1xi2,..., X25=2i-1xi25, где xij{0,1} j=1,25, Xj{0,15}
На выходах 331 334 формируется четырехразрядный двоичный код результата R 2i-1ri, операций сложения и вычитания двадцати пяти чисел по модулю пятнадцать, ri ≡{0,1} R ∈0,14} Причем на выходе 334 реализуется старший разряд r4, а на выходе 331 младший разряд r1 результата R.
Предлагаемое устройство реализует 2N операций сложения и вычитания вида R X mod(2n-1) (1)
Выполняемая операция определяется путем соответствующей коммутации прямых и обратных кодов операндов на входах устройства, а именно: если i-й операнд Хi входит в уравнение (1) со знаком "плюс", то на вход устройства подается его прямой код, а если со знаком "минус" то обратный.
Укажем, что k-входовый одноразрядный сумматор работает следующим образом. На вход сумматора подаются k одноразрядных двоичных операндов. На выходе формируется позиционный двоичный код числа операндов, имеющих значение "1". Веса выходов сумматоров на чертеже обозначены цифрами 1, 2, 4, 8 и 16.
Устройство для сложения и вычитания N чисел по модулю 2n-1 построено с использованием следующего соотношения:
(-X) mod(2n-1) mod(2n-1), где X2i-1xi.
Отметим, что в качестве сумматора 4, входящего в состав заявляемого устройства, может быть использован сумматор, выполняющий сложение по модулю 2n-1 двух полных операндов. Работа такого сумматора при n=4 описывается табл. 1.
В табл. 2 приведены значения количества уровней одноразрядных многовходовых сумматоров m и количества входов сумматоров каждого уровня kj(j=) в зависимости от числа входных операндов N. Как видно из таблицы, на практике количество уровней сумматоров m не превышает четырех, так как реально число входных операндов N<<2>127-1.
Достоинством заявляемого устройства являются широкие функциональные возможности. Так, предлагаемое устройство выполняет 2N операций сложения/вычитания по модулю 2n-1 над N операндами. Известные же устройства такими возможностями не обладают.
Формула изобретения: УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ N ЧИСЕЛ ПО МОДУЛЮ 2n-1, содержащее сумматор по модулю выход которого соединен с i-м выходом устройства, отличающееся тем, что оно содержит m уровней многоходовых одноразрядных сумматоров (m находится из условия K1 N, Km 3, Kj log2 Kj-1[, где Kj количество входов сумматоров j-го уровня, Ki и Km количество входов сумматоров первого и m-го уровней соответственно), при этом вход i-го N-входового однозарядного сумматора первого уровня соединен с входом i-го разряда l-го входного операнда, входы i-го Kh-входового одноразрядного сумматора уровня соединены с выходами сумматоров (h 1)-го уровня, имеющими вес A (A находится из условия A mod (2n 1) 2i-1), выход суммы i-го одноразрядного двоичного сумматора m-го уровня соединен с первым входом i-го разряда сумматора по модулю 2n-1, второй вход S-го разряда которого соединен с выходом переноса (S-1)-го одноразрядного двоичного сумматора m-го уровня, выход переноса n-го одноразрядного двоичного сумматора m-го уровня соединен с вторым входом первого разряда сумматора по модулю 2n-1, при этом i-е разряды входных операндов и сумматора по модулю 2n-1 имеют вес 2i-1.