УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТИЧЕСКИХ ОСТАТКОВ ПО МОДУЛЮ 2+1 Российский патент 1994 года по МПК H03M7/18 

Описание патента на изобретение RU2012136C1

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

Целью изобретения является повышение быстродействия вычислительного процесса.

В основу работы устройства положено следующее.

Двоичное 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.

Похожие патенты RU2012136C1

название год авторы номер документа
УСТРОЙСТВО ДЛЯ ПРЕОБРАЗОВАНИЯ ЧИСЛА В КВАДРАТИЧЕСКИЕ ОСТАТКИ 1992
  • Оленев Александр Анатольевич
  • Червяков Николай Иванович
  • Горлачев Игорь Викторович
  • Федорцов Сергей Владимирович
RU2029436C1
СИСТОЛИЧЕСКИЙ ПРОЦЕССОР ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ С КОРРЕКЦИЕЙ ОШИБКИ 1992
  • Калмыков Игорь Анатольевич
  • Оленев Александр Анатольевич
  • Бережной Виктор Васильевич
RU2018950C1
УСТРОЙСТВО ДЛЯ КОНТРОЛЯ И ИСПРАВЛЕНИЯ ОШИБОК В ИЗБЫТОЧНОМ МОДУЛЯРНОМ КОДЕ 1991
  • Бережной Виктор Васильевич
  • Оленев Александр Анатольевич
  • Микула Николай Павлович
  • Николаев Юрий Иванович
RU2015620C1
УСТРОЙСТВО ДЛЯ КОНТРОЛЯ И ИСПРАВЛЕНИЯ ОШИБОК В ИЗБЫТОЧНОМ МОДУЛЯТОРНОМ КОДЕ 1991
  • Бережной Виктор Васильевич
  • Червяков Николай Иванович
  • Оленев Александр Анатольевич
  • Николаев Юрий Иванович
RU2022472C1
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТИЧЕСКИХ ОСТАТКОВ ПО МОДУЛЮ 1991
  • Оленев А.А.
  • Червяков Н.И.
RU2020757C1
СИСТОЛИЧЕСКИЙ ОТКАЗОУСТОЙЧИВЫЙ ПРОЦЕССОР ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ 1992
  • Калмыков Игорь Анатольевич
  • Оленев Александр Анатольевич
RU2029437C1
Устройство для вычисления остатка по модулю 2 @ +1 1990
  • Червяков Николай Иванович
  • Оленев Александр Анатольевич
SU1734212A1
СИСТОЛИЧЕСКИЙ ПРОЦЕССОР ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ ФУНКЦИЙ 1991
  • Оленев Александр Анатольевич
RU2015549C1
Устройство для обработки информации, представленной в системе остаточных классов 1990
  • Червяков Николай Иванович
  • Оленев Александр Анатольевич
SU1743002A1
Преобразователь кода из системы остаточных классов в позиционный код 1986
  • Червяков Николай Иванович
  • Коршунов Олег Евгеньевич
  • Финько Олег Анатольевич
SU1388996A1

Реферат патента 1994 года УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТИЧЕСКИХ ОСТАТКОВ ПО МОДУЛЮ 2+1

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

Формула изобретения RU 2 012 136 C1

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТИЧЕСКИХ ОСТАТКОВ ПО МОДУЛЮ 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, второй тактовый вход устройства соединен с входами разрешения записи первого и второго регистров хранения промежуточных результатов.

RU 2 012 136 C1

Авторы

Оленев Александр Анатольевич

Даты

1994-04-30Публикация

1991-04-02Подача