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

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТИЧЕСКИХ ОСТАТКОВ ПО МОДУЛЮ n+1

Патент Российской Федерации
Суть изобретения: Изобретение относится к вычислительной технике и может быть использовано в специализированных системах для сопряжения вычислительных устройств, функционирующих в квадратической системе остаточных классов. Целью изобретения является повышение быстродействия устройства. Преимущество устройства достигается за счет введения преобразователей 3, 4 прямого кода в дополнительный и регистров 7, 8 хранения промежуточного результата, что позволяет увеличить быстродействие почти в 2 раза устройства, содержащего входные регистры 1, 2, сумматоры 5, 6, 10 по модулю 2n+1, умножитель 9 по модулю 2n+1 и вычитатель 11 по модулю 2n+1 . 1 ил.
Поиск по сайту

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

   С помощью Google:    

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


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

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

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

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2012136
Класс(ы) патента: H03M7/18
Номер заявки: 4924318/24
Дата подачи заявки: 02.04.1991
Дата публикации: 30.04.1994
Заявитель(и): Оленев Александр Анатольевич
Автор(ы): Оленев Александр Анатольевич
Патентообладатель(и): Оленев Александр Анатольевич
Описание изобретения: Изобретение относится к вычислительной технике и может быть использовано для сопряжения вычислительных устройств, функционирующих в квадратичной системе остаточных классов (СОК).
Целью изобретения является повышение быстродействия вычислительного процесса.
В основу работы устройства положено следующее.
Двоичное k-разрядное число Х может быть разделено на l групп по n разрядов, где n - четное и равно степени Pk = 2n + 1. Тогда число Х по модулю может быть представлено
x= ao+a+a2+ . . . + a (1) где ao, a1, . . . , al - группы по n разрядов;
ao-n-младших разрядов числа Х и т. д.
Кодопреобразователь преобразует n разрядов так, чтобы на его выходе была реализована функция дополнения числа до нужного модуля, т. е.
a= Pk-ai-1 (2)
где i = 2, 4, 6, 8, . . . l± 1, ai-1 - n-разрядов числа Х
Квадратически СОК представляется в виде
wi= xi+riyPk;
w*i= xi-riyPk, (3) где ri2 = -1 mod Pk, что выполнимо только при P = 4n + 1, Pk = 2n + 1, если n четное, то Pk = 22 (2n-2) + 1 = 4 (2n-2) + 1 (4) условие выполняется.
Таким образом, с помощью выражений (1), (2) возможна реализация выражений (3), (4), т. е. преобразование комплексного числа в квадратическую СОК.
На чертеже приведена схема устройства для вычисления квадратических остатков.
Устройство содержит входные регистры 1, 2, преобразователи 3, 4 прямого кода в дополнительный, сумматоры 5, 6, 10 по модулю 2n+1, регистры 7, 8 хранения промежуточных результатов, умножитель 9 по модулю 2n+1, вычитатель 11 по модулю 2n+1, выходы 12, 13 устройства, первый и второй тактовые входы 14.1 и 14.2 устройства.
Устройство работает следующим образом.
В исходном состоянии в регистре 1 находится код преобразуемого числа Х, в регистре 2 - код преобразуемого числа Y, регистра 7, 8 обнулены.
На первом такте преобразователя число ао, определяемое n младшими разрядами преобразуемых чисел Х, Y, поступает на сумматоры 6, 5 по модулю 2n+1, число а1, определяемое n вторыми разрядами чисел Х, Y, подается на преобразователи 3, 4 прямого кода в дополнительный. С выхода преобразователей 3, 4 прямого кода в дополнительный подается на вторые входы сумматоров 5, 6 по модулю 2n+1 код дополнения числа до модуля Pk. По окончании переходных процессов на выходе сумматора 5
x= ao+a, на входе сумматора 6
y= ao+a.
Результат суммирования записывается в момент поступления импульса по входу 14.2 в регистры 7, 8.
На втором такте преобразования в момент поступления импульса по входу 14.1 содержимое регистров 1, 2 сдвигается на 2n разрядов вверх и цикл повторяется с добавлением результата предыдущего суммирования, подаваемого с регистров 7, 8.
Когда преобразование произведено, то производится умножение | Y| Pk+на ri в умножителе 9, и сумматор 10 выполняет операцию
xi+r iy, а вычитатель 11 - операцию
xi-r iy.
Окончательные результаты снимают с выходов сумматора 10 и вычитателя 11.
Формула изобретения: УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТИЧЕСКИХ ОСТАТКОВ ПО МОДУЛЮ 2n+1, содержащее два входных регистра, три сумматора по модулю 2n + 1, умножитель по модулю 2n + 1, вычитатель по модулю 2n + 1 причем входы разрешения сдвига первого и второго входных регистров соединены с первым тактовым входом устройства, выходы n младших разрядов первого и второго входных регистров соединены с входами первого слагаемого первого и второго сумматоров по модулю 2n + 1 соответственно, выходы умножителя по модулю 2n + 1 соединены с входами первого слагаемого третьего сумматора по модулю 2n + 1 и вычитаемого вычитателя по модулю 2n + 1, выходы которых являются выходами устройства, отличающееся тем, что, с целью повышения быстродействия, устройство содержит два преобразователя прямого кода в дополнительный и два регистра хранения промежуточных результатов, причем выходы разрядов с (n + 1)-го по 2n первого и второго входных регистров соединены с входами первого и второго преобразователей прямого кода в дополнительный, выходы которых соединены с входами второго слагаемого первого и второго сумматоров по модулю 2n + 1 соответственно, выходы которых соединены с информационными входами первого и второго регистров хранения промежуточных результатов соответственно, выходы которых соединены с входами третьего слагаемого первого и второго сумматоров по модулю 2n + 1 соответственно, выход первого регистра хранения промежуточных результатов соединен с входом второго слагаемого третьего сумматора по модулю 2n + 1 и входом уменьшаемого вычитателя по модулю 2n + 1, выход второго регистра промежуточных результатов соединен с входом умножителя по модулю 2n + 1, второй тактовый вход устройства соединен с входами разрешения записи первого и второго регистров хранения промежуточных результатов.