Устройство для преобразования числа в квадратические остатки

 

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

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

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

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

В основу предлагаемого устройства положено следующее. Известно, что для предоставления чисел в виде квадратических остатков необходимо произвести следующие операции: Z = x_i + jy_i; (1) Z = (W, W*), (1.1) где W = (x_i + σ _iy_i) mod p_i; (2) W* = (x_i - σ _i y_i) mod p_i, (3) где σ _i² = -1mod p_i и p_i = 4n + 1, так как p_i = 2ⁿ+1, где n - четное, и σ p_i = 2p_i, отсюда σ _i = 2^n/2 (4) Выше приведенные формулы позволяют воспользоваться следующим алгоритмом нахождения квадратических остатков.

Двоичное k-разрядное число х может быть разделено на l групп по n разрядов, где n - четное и равно степени p_k = 2ⁿ+1. Тогда число х по модулю может быть представлено как X = a_o+a₁+a₂+ ... +a где а₀, а₁, а₂,...,а_l - группы по n разрядов младших разрядов числа Х и т.д.

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

а_i-1¹ = p_k - a_i, где i = 2,4,6,8,...,l ±1, (6) где a_i-1 - n разрядов числа х.

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

Умножение на 2^n/2 или σ i легко организовать, произведя сдвижку мнимой части Y_i в многофункциональном регистре.

Таким образом, для получения квадратических остатков необходимо ввести дополнительный блок для получения остатка по модулю 2ⁿ+1, обеспечивающий получение комплексной части остатка, а также сумматор и вычитатель по модулю 2ⁿ+1, что обеспечивает получение "действительной" и "мнимой" частей по данному модулю.

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

На фиг.1 приведена схема устройства для преобразования числа в квадратические остатки; на фиг. 2 - схема преобразователя по модулю 2ⁿ+1.

Устройство содержит два преобразователя 1 и 2 по модулю 2ⁿ+1, сумматор 5, вычитатель 6 и группу тактовых входов. Вход 3 является соответственно входом действительной части числа, а вход 4 - мнимой части числа, которые подключены соответственно к входам преобразователей 1 и 2. Сумматор 5 и вычитатель 6 являются известными функциональными элементами, к которым подключены соответственно выходы 7 и 8 устройства.

На фиг. 2 входные регистры 11.1 и 11.2 функционально известные элементы. Выводы младших n разрядов входного регистра подключены к сумматору 13.1 (13.2) по модулю 2ⁿ+1, выводы младших разрядов с n-1-го по 2n-й входного регистра подключены к функционально известному преобразователю 12.1 (12.2) прямого кода в дополнительный, выходы n+1 которого подключены к сумматору 13.1 (13.2) по модулю 2ⁿ+1. Последний является функционально известным элементом комбинационного типа. Выходы сумматора по модулю 2ⁿ+1 подключены к входам выходного регистра 14.1 (14.2), а его выходы подключены к входам сумматора и подаются на входы сумматора и вычитателя.

Тактовые входы 9.1 являются входами разрешения сдвига регистров 11.1 и 11.2 , тактовый вход 9.2 соединен с выходным регистром 14.1 (14.2), а тактовый вход 9.3 является входом разрешения сдвига регистра 11.2.

Устройство работает следующим образом.

В исходном состоянии в регистре 11.1 находится код действительной части преобразуемого числа х, поступающего по входу 3, регистр 14.1 обнулен. В регистре 11.2 находится код мнимой части преобразуемого числа х, поступающего по входу 4, регистр 14.2 обнулен. На первом такте по входу 9.3 подается тактовый импульс, осуществляющий сдвиг кода мнимой части числа х влево, что соответствует умножению числа на 2^n/2. Затем по входу 9.1 поступает тактовый импульс, который сдвигает действительную и мнимую части числа А₀, определяемого n младшими разрядами преобразуемого числа х, и поступает соответственно на сумматоры 13.1 (13.2) по модулю 2ⁿ+1. Затем число А₁, определяемое n вторыми разрядами числа х подается на преобразователь прямого кода в дополнительный, а с его выходов на вторые входы сумматоров 13.1 (13.2) по модулю 2ⁿ+1 поступает код дополнения числа до модуля p_k. Таким образом, по окончании переходных процессов на выходе сумматоров имеют Результат суммирования записывается в момент поступления импульса по входу 9.2 в регистры 14.1 (14.2). С выходов сумматоров 13.1 (13.2) преобразуемое число поступает на выходные регистры 14.1 (14.2). На втором такте преобразования в момент поступления импульса по входу 9.1 содержимое регистров 11.1 (11.2) сдвигается на 2ⁿ разрядов влево, и цикл повторяется с добавлением результата предыдущего суммирования, подаваемого с выходных регистров 14.1 (14.2). Их выходы 10.1 (10.2) являются выходами преобразователей по модулю 2ⁿ+1. Окончательный результат преобразования l Х l⁺ _р поступает с выходов 10.1 (10.2) регистров 14.1 (14.2) на входы сумматора 5 и вычитателя 6, выходы 7 и 8 которых являются выходами устройства.

Преимущества предлагаемого устройства по сравнению с базовым объектом. Вводя второй блок по вычислению остатка по модулю 2ⁿ+1, имеют возможность получать действительную и мнимую части числа в квадратической форме путем ввода мнимой части комплексного числа во второе устройство по вычислению остатка по модулю 2ⁿ+1. Это достигнуто тем, что тактовый импульс, идущий с входа 9.3, осуществляют дополнительный сдвиг мнимой части, находящейся во входном регистре 11.2, что соответствует умножению на 2^n/2 и позволяет производить операции с комплексными числами.

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

УСТРОЙСТВО ДЛЯ ПРЕОБРАЗОВАНИЯ ЧИСЛА В КВАДРАТИЧЕСКИЕ ОСТАТКИ, содержащее первый блок преобразования числа по модулю, в состав которого входят входной и выходной регистры и накапливающий сумматор по модулю, выход которого соединен с информационным входом выходного регистра, а первый вход разрешения сдвига информации входного регистра и вход разрешения записи выходного регистра первого блока преобразования числа по модулю являются соответственно первым и вторым тактовыми входами устройства, отличающееся тем, что в него введены второй блок преобразования числа по модулю, сумматор по модулю и вычитатель по модулю, причем в каждый блок преобразования числа по модулю введен преобразователь прямого кода в дополнительный, с первого по n-й выходные разряды входного регистра блока преобразования числа по модулю соединены с первым входом накапливающего сумматора по модулю, второй вход которого соединен с выходом преобразователя прямого кода в дополнительный, вход которого соединен с (n+1)-го по 2 n-й выходными разрядами входного регистра, второй вход разрешения сдвига информации которого является третьим тактовым входом устройства, четвертый и пятый тактовые входы которого соединены соответственно с входом разрешения записи выходного регистра и первым входом разрешения сдвига информации входного регистра второго блока преобразования числа по модулю, выходы выходных регистров первого и второго блоков преобразования числа по модулю соединены с третьими входами соответствующих накапливающих сумматоров по модулю и являются выходами первого и второго блоков преобразования числа по модулю, выход первого преобразователя числа по модулю соединен с первыми входами сумматора по модулю и вычитателя по модулю, выход второго преобразователя числа по модулю соединен с вторыми входами сумматора по модулю и вычитателя по модулю , выходы которых являются выходами устройства.

РИСУНКИ

Рисунок 1, Рисунок 2