Вычислительный элемент модулярной арифметики

Заявленная полезная модель относится к устройствам для выполнения вычислений с использованием машинных чисел и числовых полей, т.е. представление числа без оснований с помощью совокупности арифметических остатков. Техническим результатом, который может быть получен в заявленной полезной модели, является повышение быстродействия вычислительного элемента модулярной арифметики. Технический результат достигается тем, что вычислительный элемент модулярной арифметики, содержит устройство управления, оперативное запоминающее устройство (ОЗУ), постоянное запоминающее устройство (ПЗУ), мультиплексор, первый и второй входы элемента, сумматор по модулю р, умножитель, выполненный в виде сумматора по модулю р-1, первый и второй входы которого соединены соответственно с первым постоянным запоминающим устройством (ПЗУ) умножителя и вторым постоянным запоминающим устройством (ПЗУ) умножителя, а выход которого соединен с третьим запоминающим устройством (ПЗУ) умножителя, при этом устройство управления соединено с ОЗУ, ПЗУ и управляющим входом мультиплексора, а первый вход элемента соединен с ОЗУ, ПЗУ, первым входом сумматора по модулю р и первым ПЗУ умножителя, а второй вход элемента соединен с ОЗУ, вторым входом сумматора по модулю р и вторым ПЗУ умножителя, кроме того, первый вход мультиплексора соединен с выходом сумматора по модулю р, второй вход мультиплексора соединен третьим ПЗУ умножителя, третий вход мультиплексора соединен с ПЗУ, а выход мультиплексора соединен с ОЗУ.

Область применения

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

Предшествующий уровень техники

Известно, выбранное в качестве ближайшего аналога, устройство цифровой обработки сигналов, включающее преобразователь входных сигналов в двоичный код соединенный с блоком постоянных запоминающих устройств, каждое из которых преобразует поступающий на них кодированный сигнал в индексы на основании таблиц введенных в них, а каждое постоянное запоминающее устройство соединено с устройством выполняющим арифметическое действие по заданному модулю (публикация US 5117383 A, кл. МПК G06F 7/72, опубл. 26.05.1992 г.)

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

Раскрытие полезной модели

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

Технический результат достигается тем, что вычислительный элемент модулярной арифметики, содержит устройство управления, оперативное запоминающее устройство (ОЗУ), постоянное запоминающее устройство (ПЗУ), мультиплексор, первый и второй входы элемента, сумматор по модулю р, умножитель, выполненный в виде сумматора по модулю р-1, первый и второй входы которого соединены соответственно с первым постоянным запоминающим устройством (ПЗУ) умножителя и вторым постоянным запоминающим устройством (ПЗУ) умножителя, а выход которого соединен с третьим запоминающим устройством (ПЗУ) умножителя, при этом устройство управления соединено с ОЗУ, ПЗУ и управляющим входом мультиплексора, а первый вход элемента соединен с ОЗУ, ПЗУ, первым входом сумматора по модулю р и первым ПЗУ умножителя, а второй вход элемента соединен с ОЗУ, вторым входом сумматора по модулю р и вторым ПЗУ умножителя, кроме того, первый вход мультиплексора соединен с выходом сумматора по модулю р, второй вход мультиплексора соединен третьим ПЗУ умножителя, третий вход мультиплексора соединен с ПЗУ, а выход мультиплексора соединен с ОЗУ.

Увеличение быстродействия повышается за счет введения в вычислительный элемент модулярной арифметики устройства управления, ОЗУ и ПЗУ. По командам устройства управления результаты промежуточных вычислений направляются в ОЗУ и из него снова в сумматор по модулю р и в умножитель, а постоянные величины (константы) из ПЗУ также по командам устройства управления направляются в сумматор по модулю р и в умножитель.

Описание чертежа

На прилагаемом чертеже представлена схема вычислительного элемента модулярной арифметики.

Осуществление полезной модели

Вычислительный элемент (устройство) модулярной арифметики, содержит устройство 1 управления, оперативное запоминающее устройство 2 (ОЗУ), постоянное запоминающее устройство 3 (ПЗУ), мультиплексор 4, сумматор 5 по модулю р, умножитель 6 первый вход 11 элемента и второй вход 12 элемента.

Умножитель 6 основан на перекодировании вычетов по модулю р в их индексы и выполнен в виде сумматора 7 по модулю р-1, входы которого соединены с первым постоянным запоминающим устройством 8 (ПЗУ) умножителя и вторым постоянным запоминающим устройством 9 (ПЗУ) умножителя, а его (сумматора 7 по модулю р-1) выход соединен с третьим постоянным запоминающим устройством 10 (ПЗУ) умножителя.

Подобное выполнение умножителя 6 известно (например, см. «Машинная арифметика в остаточных классах», М. 1968, Акушский И.Я., Юдицкий Д.Н.) и позволяет заменить затратную операцию умножения по модулю р, на операцию сложения по модулю р-1. Первое ПЗУ 8 умножителя содержит таблицу индексов IND1, второе ПЗУ 9 умножителя содержит таблицу индексов IND2, а третье ПЗУ 10 умножителя содержит таблицу обратных индексов IND INV.

Устройство 1 управления соединено с ОЗУ 2, ПЗУ 3 и управляющим входом мультиплексора 4.

ОЗУ 2 предназначено для хранения результатов промежуточных вычислений сумматора 5 по модулю р и умножителя 6, а в ПЗУ 3 хранятся постоянные величины необходимые для выполнения вычислений (константы).

Первый вход 11 элемента соединен с ОЗУ 2, ПЗУ 3, первым входом сумматора 5 по модулю р и первым ПЗУ 8 умножителя, а второй вход 12 элемента соединен с ОЗУ 2, вторым входом сумматора 5 по модулю р и вторым ПЗУ 9 умножителя. Первый вход 11 элемента и второй вход 12 элемента могут быть выполнены, например, в виде входных буферных регистров операндов. Первый вход 11 элемента и второй вход 12 элемента могут быть соединены с внешним источником данных, таким как, например, глобальная память компьютера, или процессор, или любое иное аналогичное устройство.

Первый вход мультиплексора 4 соединен с выходом сумматора 5 по модулю р, второй вход мультиплексора 4 соединен третьим ПЗУ 10 умножителя, третий вход мультиплексора 4 соединен с ПЗУ 3, а выход мультиплексора 4 соединен с ОЗУ 2.

Заявленный вычислительный элемент модулярной арифметики работает следующим образом.

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

Сигналы, содержащие данные, поступают на первый вход 11 элемента и второй вход 12 элемента от внешнего источника данных.

Операнд (в виде двоичного кода), поступивший на первый вход 11 элемента, поступает на первый вход сумматора 5 по модулю р, а операнд (в виде двоичного кода), поступивший на второй вход 12 элемента, поступает на второй вход сумматора 5 по модулю р. Сумматор 5 по модулю р выполняет операцию сложения по модулю р данных поступивших с первого входа 11 элемента и со второго входа 12 элемента, а полученный результат через выход сумматора 5 по модулю через первый вход мультиплексора 4 поступает в упомянутый мультиплексор 4.

Одновременно операнд, поступивший на первый вход 11 элемента, поступает на первое ПЗУ 8 умножителя, а операнд, поступивший на второй вход 12 элемента, поступает на второе ПЗУ 9 умножителя. Первое ПЗУ 8 умножителя и второе ПЗУ 9 умножителя по заданному значению входного сигнала определяют по таблицам IND1 и IND2 соответственно и выдают на своих выходах сигналы содержащие значение индекса по заданному основанию. Затем упомянутые сигналы из первого ПЗУ 8 умножителя и второго ПЗУ 9 умножителя поступают на вход сумматора 7 по модулю р-1, который выполняет операцию сложения значении упомянутых индексов по модулю р-1. Далее сигнал, содержащий сумму значений индексов, с выхода сумматора 7 по модулю р-1 поступает на третье ПЗУ 10 умножителя. В третьем ПЗУ 10 умножителя выполняется обратное преобразование индексов по таблице IND INV в значения вычетов, которое является результатом умножения по модулю р. Указанный результат из третьего ПЗУ 10 умножителя поступает через второй вход мультиплексора 4 в упомянутый мультиплексор 4.

Устройство 1 управления в зависимости от программы обработки данных определяет, какой из результатов, поступивший от сумматора 5 по модулю р или поступивший от умножителя 6, должен быть принят как результат одного цикла, при этом второй результат может быть удален мультиплексором 4.

Затем устройство 1 управления в зависимости от программы обработки данных формирует и передает мультиплексору 4 команду на выполнение какого-либо действия с результатом, например, команду выдать полученный результат па выход мультиплексора 4 или команду на передачу полученного результата в ОЗУ 2.

В качестве данных, передаваемых на первый вход 11 элемента и на второй вход 12 элемента, для выполнения промежуточных вычислений в заявленном элементе модулярной арифметики могут быть использованы данные промежуточных вычислений, выполняемых сумматором 5 по модулю р или умножителем 6, поступающие по команде устройства 1 управления в ОЗУ 2. Для этого устройство 1 управления выдает ОЗУ 2 команду на передачу хранящегося в нем (ОЗУ 2) данного на первый вход 11 элемента и/или па второй вход 12 элемента. Из ОЗУ 2 могут поступать данные сразу на первый вход 11 элемента и па второй вход 12 элемента, или только на один из указанных входов 11 или 12, а второй операнд может поступать от внешнего источника данных или ПЗУ 3, которое содержит значения констант. При этом из ПЗУ 3 данные могут передаваться только на один вход элемента, в данном случае - на первый вход 11 элемента.

При любой комбинации данных, поступающих от внешнего источника данных, или от ОЗУ 2, или от ПЗУ 3, сумматор 5 по модулю р выполняет операцию сложения по модулю р данных, а умножитель 6 выполняет операцию умножения по тому же модулю. Результаты вычислений передаются в мультиплексор 4, а устройство 1 управления в зависимости от программы обработки данных определяет, какой из результатов должен быть принят как результат одного цикла.

В некоторых случаях, в зависимости от программы обработки, данные могут не поступать на первый вход 11 элемента и на второй вход 12 элемента, а устройство 1 управления выдает ПЗУ 3 команду на передачу в мультиплексор 4 какой-либо константы, предусмотренной программой обработки. При этом мультиплексор 4 в данном случае выдает указанную константу на выход мультиплексора как окончательный результат.

Процесс обработки данных завершается после того, как мультиплексор 4 по команде устройства 1 управления передаст на выход мультиплексора 4 окончательный результат обработки данных.

Таким образом, за счет введения в вычислительный элемент модулярной арифметики устройства управления, ОЗУ и ПЗУ достигается технический результат, то есть повышается быстродействие вычислительный элемент модулярной арифметики.

Вычислительный элемент модулярной арифметики, содержащий устройство управления, оперативное запоминающее устройство (ОЗУ), постоянное запоминающее устройство (ПЗУ), мультиплексор, первый и второй входы элемента, сумматор по модулю р, умножитель, выполненный в виде сумматора по модулю р-1, первый и второй входы которого соединены соответственно с первым постоянным запоминающим устройством (ПЗУ) умножителя и вторым постоянным запоминающим устройством (ПЗУ) умножителя, а выход которого соединен с третьим запоминающим устройством (ПЗУ) умножителя, при этом

устройство управления соединено с ОЗУ, ПЗУ и управляющим входом мультиплексора, а

первый вход элемента соединен с ОЗУ, ПЗУ, первым входом сумматора по модулю р и первым ПЗУ умножителя, а

второй вход элемента соединен с ОЗУ, вторым входом сумматора по модулю р и вторым ПЗУ умножителя, кроме того,

первый вход мультиплексора соединен с выходом сумматора по модулю р, второй вход мультиплексора соединен с третьим ПЗУ умножителя, третий вход мультиплексора соединен с ПЗУ, а выход мультиплексора соединен с ОЗУ.