Устройство сложения (вычитания) n чисел с настраиваемым модулем - RU2637988C1

Чертежи

Описание

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

Известно устройство для сложения и вычитания чисел по модулю [1], содержащее две группы элементов ИЛИ, три кольцевых регистра сдвига, шесть блоков элементов И, дифференцирующую цепочку, семь элементов И, четыре элемента запрета, шифратор, дешифратор, блок элементов ИЛИ, два элемента НЕ, два счетчика, два элемента ИЛИ-НЕ, элемент ИЛИ, преобразователь числа в код Х/k, преобразователь кода числа Х в код X mod k, преобразователь кода числа в дополнительный код по модулю.

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

Также известно устройство для сложения n чисел по модулю Р [2], содержащее N дешифраторов, входы которых являются входами устройства, и шифратор, выход которого является выходом устройства, N управляемых фазовращателей, генератор гармонического сигнала, (р-1) фазовращателей на фиксированные значения фазы и измеритель фазы гармонического сигнала, причем выход генератора гармонического сигнала соединен с первым входом первого управляемого фазовращателя, выход i-го управляемого фазовращателя - с первым входом (i+1)-го управляемого фазовращателя, выход N-го управляемого фазовращателя с входом 1-го измерителя фазы гармонического сигнала, 2-й вход которого соединен с выходом генератора гармонического сигнала, вход q-го измерителя фазы гармонического сигнала соединен с выходом генератора гармонического сигнала через фазовращатель на фиксированное значение фазы, при этом вход (р+2) измерителя фазы гармонического сигнала является тактовым входом устройства, выход измерителя фазы гармонического сигнала соединен с входом шифратора, а выходы дешифраторов подключены к вторым входам соответствующих управляемых фазовращателей.

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

Также известен сумматор с переменным модулем сложения [3], предназначенный для сложения двоичных чисел с возможностью электронной перестройки модуля сложения и может использоваться в управляемых генераторах импульсов с селекцией опорной фазы. Для получения переменного модуля сложения устройство, содержащее пару обычных сумматоров, один из которых складывает слагаемые, а другой корректирует при необходимости результат сложения, дополнено элементом ИЛИ, блоком управляемых инверторов и компаратором. В устройстве предусмотрена также шина управления модулем, на которую подается двоичное число, равное заданному модулю сложения. Компаратор сравнивает образованную основным сумматором сумму с модулем сложения и в случае, когда указанная сумма равна или больше модуля, вырабатывает сигнал, обеспечивающий вычитание из нее корректирующим сумматором значения модуля и выработку сигнала переноса.

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

Также известно устройство для сложения и вычитания чисел по модулю [4], сущность которого состоит в проведении операции модульного сложения (вычитания) по частным модулям m₁ и m₂ (m₁⋅m₂≥m, где m - модуль операции) с последующим преобразованием в результате операции по модулю. Устройство содержит дешифратор, два блока элементов И, две группы элементов ИЛИ, пять элементов И, два элемента запрета, два преобразователя кода, два счетчика, два элемента ИЛИ-НЕ, коммутатор, шифратор, два кольцевых регистра сдвига.

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

Наиболее близким по сущности технического решения является накапливающий сумматор по модулю [5], содержащий n-разрядный сумматор и n-разрядный регистр, причем вторые информационные входы сумматора являются информационными входами устройства, а информационные выходы регистра являются информационными выходами устройства и соединены с первыми информационными входами n-разрядного сумматора, тактовый вход регистра является тактовым входом устройства, вход обнуления регистра является входом обнуления устройства, а вход переноса n-разрядного сумматора является входом переноса устройства, (n+1)-разрядный сумматор и n-разрядный мультиплексор, причем 1…n информационные выходы n-разрядного сумматора соединены с первыми информационными входами (n+1)-разрядного сумматора и вторыми 1…n информационными входами мультиплексора, выход переноса n-разрядного сумматора соединен с первым (n+1) информационным входом (n+1)-разрядного сумматора, вторые 1...n+1 информационные входы которого являются входами кода модуля в инверсном виде, на вход переноса (n+1)-разрядного сумматора подается логическая единица, выход переноса (n+1)-разрядного сумматора соединен с управляющим входом мультиплексора, а 1…n информационные выходы соединены с первыми 1…n информационными входами мультиплексора, информационные выходы которого соединены со входами записи регистра.

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

Цель изобретения - повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство сложения (вычитания) N чисел с настраиваемым модулем, включающее регистр памяти, мультиплексор, введены n блоков памяти хранения значений слагаемых, многоканальный вход каждого из которых подключен к соответствующему многоканальному входу подачи значения слагаемого, при этом n многоканальных входов подачи значений слагаемых являются входами устройства n блоков памяти хранения значений знаков слагаемых, вход каждого из которых подключен к соответствующему входу подачи знака слагаемых, при этом n входов подачи знака слагаемых являются входами устройства; многоканальный мультиплексор, n многоканальных информационных входов которого подключены к соответствующим многоканальным выходам блоков памяти хранения значений слагаемых; мультиплексор, n информационных входов которого подключены к соответствующим выходам блоков памяти хранения значений знаков слагаемых; первый вычитающий счетчик, первый многоканальный вход параллельной записи значений ячеек памяти которого подключен к многоканальному выходу многоканального мультиплексора, третий вход подключен ко входу подачи тактовых импульсов, а второй многоканальный выход подключен ко входам первого многовходового логического элемента ИЛИ-НЕ, второй выход последовательной выдачи тактовых импульсов подключен ко второму входу реверсного счетчика по настраиваемому модулю; первый многоканальный вход реверсного счетчика по настраиваемому модулю подключен к многоканальному входу подачи значения модуля k, который является входом устройства, а третий вход настройки прямого и обратного счета подключен к выходу мультиплексора; второй вычитающий счетчик, первый многоканальный вход параллельной записи значений ячеек памяти которого подключен к многоканальному выходу подачи значения количества слагаемых, являющемуся входом устройства, а многоканальный выход подключен к адресным входам мультиплексора и многоканального мультиплексора, входам второго многовходового логического элемента ИЛИ-НЕ; третий вычитающий счетчик, первый многоканальный вход параллельной записи значений ячеек памяти которого подключен к многоканальному выходу реверсного счетчика по настраиваемому модулю, второй вход подключен ко входу подачи тактовых импульсов, третий вход подачи сигнала записи подключен к выходу первого многовходового логического элемента ИЛИ-НЕ, а второй многоканальный выход подключен к третьему многовходовому логическому элементу ИЛИ-НЕ, выход которого подключен к четвертому входу сброса реверсного счетчика по настраиваемому модулю, входу подачи тактовых импульсов второго вычитающего счетчика и входу элемента задержки сигнала, выход которого подключен к входу подачи сигнала записи первого вычитающего счетчика; счетчик по настраиваемому модулю, первый многоканальный вход которого подключен к многоканальному входу подачи значения модуля k, второй вход подачи тактовых импульсов подключен к первому выходу последовательной выдачи тактовых импульсов третьего вычитающего счетчика, третий вход сброса подключен к выходу элемента задержки, вход которого подключен к выходу второго многовходового логического элемента ИЛИ-НЕ; выходной регистр, первый многоканальный вход которого подключен к многоканальному выходу счетчика по настраиваемому модулю, второй вход подачи сигнала записи подключен к выходу второго многовходового логического элемента ИЛИ-НЕ, а многоканальный выход подключен к многоканальному выходу выдачи значения суммы (разности) по модулю, являющемуся выходом устройства.

Структурная схема предлагаемого устройства представлена на Фиг. 1 и включает блоки памяти хранения значений слагаемых 1.1-1.n, блок памяти хранения значений знаков слагаемых 2.1-2.n, многоканальный мультиплексор 3, мультиплексор 4, первый вычитающий счетчик 5, первый многовходовый логический элемент ИЛИ-НЕ 6, второй вычитающий счетчик 7, второй многовходовый логический элемент ИЛИ-НЕ 8, реверсный счетчик по настраиваемому модулю 9, третий вычитающий счетчик 10, третий многовходовый логический элемент ИЛИ-НЕ 11, счетчик по настраиваемому модулю 12, элемент задержки сигнала 13, выходной регистр 14, многоканальный вход подачи значения модуля k 15, многоканальные входы подачи значений слагаемых 16.1-16.n, входы подачи знака слагаемых 17.1-17.n, многоканальный вход подачи значения количества слагаемых 18, вход подачи тактовых импульсов 19, многоканальный выход выдачи значения суммы (разности) по модулю 20.

При этом реверсный счетчик по настраиваемому модулю 9, счетчик по настраиваемому модулю 12 могут быть выполнены на основе устройств [6, 7].

В статическом виде элементы предлагаемого устройства взаимосвязаны следующим образом (фиг. 1): многоканальные входы подачи значений слагаемых 16.1-16.n, являющиеся входами устройства, подключены к соответствующим многоканальным входам блоков памяти хранения значений слагаемых 1.1-1.n; входы подачи знака слагаемых 17.1-17.n, являющиеся входами устройства, подключены к соответствующим входам блоков памяти хранения значений знаков слагаемых 2.1-2.n; n многоканальных информационных входов многоканального мультиплексора 3 подключены к соответствующим многоканальным выходам блоков памяти хранения значений слагаемых 1.1-1.n; n информационных входов мультиплексора 4 подключены к соответствующим выходам блоков памяти хранения значений знаков слагаемых 2.1-2.n; первый многоканальный вход параллельной записи значений ячеек памяти первого вычитающего счетчика 5 подключен к многоканальному выходу многоканального мультиплексора 3, третий вход первого вычитающего счетчика 5 подключен ко входу подачи тактовых импульсов 19, а второй многоканальный выход подключен ко входам первого многовходового логического элемента ИЛИ-НЕ 6, второй выход последовательной выдачи тактовых импульсов первого вычитающего счетчика 5 подключен ко второму входу реверсного счетчика по настраиваемому модулю 9; первый многоканальный вход реверсного счетчика по настраиваемому модулю 9 подключен к многоканальному входу подачи значения модуля k 15, который является входом устройства, а третий вход настройки прямого и обратного счета реверсного счетчика по настраиваемому модулю 9 подключен к выходу мультиплексора 4; первый многоканальный вход параллельной записи значений ячеек памяти второго вычитающего счетчика 7 подключен к многоканальному выходу подачи значения количества слагаемых 18, являющемуся входом устройства, а многоканальный выход второго вычитающего счетчика 7 подключен к адресным входам мультиплексора 4 и многоканального мультиплексора 3, а также входам второго многовходового логического элемента ИЛИ-НЕ 8; первый многоканальный вход параллельной записи значений ячеек памяти третьего вычитающего счетчика 10 подключен к многоканальному выходу реверсного счетчика по настраиваемому модулю 9, второй вход третьего вычитающего счетчика 10 подключен ко входу подачи тактовых импульсов 19, третий вход подачи сигнала записи третьего вычитающего счетчика 10 подключен к выходу первого многовходового логического элемента ИЛИ-НЕ 6, а второй многоканальный выход третьего вычитающего счетчика 10 подключен к третьему многовходовому логическому элементу ИЛИ-НЕ 11, выход которого подключен к четвертому входу сброса реверсного счетчика по настраиваемому модулю 9, входу подачи тактовых импульсов второго вычитающего счетчика 7 и входу элемента задержки сигнала 13, выход которого подключен к второму входу подачи сигнала записи первого вычитающего счетчика 5; первый многоканальный вход счетчика по настраиваемому модулю 12 подключен к многоканальному входу подачи значения модуля k 15, второй вход подачи тактовых импульсов счетчика по настраиваемому модулю 12 подключен к первому выходу последовательной выдачи тактовых импульсов третьего вычитающего счетчика 10, третий вход сброса счетчика по настраиваемому модулю 12 подключен к выходу элемента задержки 13, вход которого подключен к выходу второго многовходового логического элемента ИЛИ-НЕ 8; первый многоканальный вход выходного регистра 14 подключен к многоканальному выходу счетчика по настраиваемому модулю 12, второй вход подачи сигнала записи выходного регистра 14 подключен к выходу второго многовходового логического элемента ИЛИ-НЕ 8, а многоканальный выход выходного регистра 14 подключен к многоканальному выходу выдачи значения суммы (разности) по модулю 20, являющемуся выходом устройства.

Функционирование устройства осуществляется следующим образом. В момент времени, соответствующий началу работы устройства, с многоканальных входов подачи значений слагаемых 16.1-16.n, являющихся входами устройства, выполняется запись в соответствующие блоки памяти хранения значений слагаемых 1.1-1.n N слагаемых; со входов подачи знака слагаемых 17.1-17.n, являющихся входами устройства, выполняется запись в соответствующие блоки памяти хранения значений знаков слагаемых 2.1-2.n знаков N слагаемых (логический 0 соответствует знаку -, логическая 1 соответствует знаку +); с многоканального входа подачи значения количества слагаемых 18 во второй вычитающий счетчик 7 выполняется запись значения количества слагаемых N; с многоканального входа подачи значения модуля k подается значение модуля счета на реверсный счетчик по настраиваемому модулю 9 и счетчик по настраиваемому модулю 12; далее со второго вычитающего счетчика 7 на адресные входы многоканального мультиплексора 3 и мультиплексора 4 поступает комбинация, соответствующая выбору N-го слагаемого, и соответственно знака N-го слагаемого; далее значение N-го слагаемого записывается в первый вычитающий счетчик 5, а значение знака N-го слагаемого подается на третий вход реверсного счетчика по настраиваемому модулю 9 (логическая 1 соответствует прямому счету, логический 0 соответствует обратному счету); далее первый вычитающий счетчик 5 выполняет последовательный счет импульсов до обнуления, при этом передавая импульсы на второй вход подачи импульсов реверсного счетчика по настраиваемому модулю 9, который также выполняет счет импульсов; при обнулении первого вычитающего счетчика 5 с первого многовходового логического элемента ИЛИ-НЕ 6 поступает сигнал логической 1 на третий вход третьего вычитающего счетчика 10, в соответствии с которым выполняется запись содержимого реверсного счетчика по настраиваемому модулю 9 в третий вычитающий счетчик 10; далее третий вычитающий счетчик 10 выполняет последовательный счет импульсов до обнуления, при этом передавая импульсы на второй вход подачи импульсов счетчика по настраиваемому модулю 12, который также выполняет счет импульсов; при обнулении третьего вычитающего счетчика 10 с третьего многовходового логического элемента ИЛИ-НЕ 11 поступает сигнал логической 1 на четвертый вход сброса реверсного счетчика по настраиваемому модулю 9, соответствующий его обнулению, на вход подачи тактовых импульсов второго вычитающего счетчика 7, что соответствует одному отсчету, на вход элемента задержки сигнала 13 (выполняется задержка сигнала на время, необходимое для выбора N-1-го слагаемого, в соответствии с комбинацией выдаваемой после нового отсчета вторым вычитающим счетчиком 7 на адресные входы многоканального мультиплексора 3 и мультиплексора 4); далее значение сигнала логической 1 подается на вход записи первого вычитающего счетчика 5, который записывает значение N-1-го слагаемого, и значение знака N-1-го слагаемого подается на реверсный счетчик по настраиваемому модулю 9… таким образом, циклически осуществляется счет всех оставшихся слагаемых до обнуления второго вычитающего счетчика 7; при обнулении второго вычитающего счетчика 7 с выхода второго многовходового логического элемента ИЛИ-НЕ 8 подается сигнал логической 1 на вход записи выходного регистра 14, соответствующий записи содержимого счетчика по настраиваемому модулю 12, при этом значение суммы N слагаемых по модулю с многоканального выхода выходного регистра 14 подается на многоканальный выход выдачи значения суммы (разности) по модулю 20, также сигнал логической 1 с выхода второго многовходового элемента ИЛИ-НЕ 8 подается на вход элемента задержки сигнала 13 (выполняется задержка сигнала на время, необходимое для записи содержимого счетчика по настраиваемому модулю 12 в выходной регистр 14); далее с выхода элемента задержки сигнал 13 сигнал логической 1 подается на третий вход сброса счетчика по настраиваемому модулю 12.

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

Предложенное устройство может быть реализовано с использованием современной элементной базы программируемых логических интегральных схем фирм Altera и Xilinx.

Литература

1. RU 2156998, 02.02.1999 г.

2. RU 2188448, 15.11.2000 г.

3. RU 2183347, 24.03.2000 г.

4. RU 2018935, 30.08.1994 г.

5. RU 2500017, 05.06.2012 г.

6. RU 2179784, 07.04.2000 г.

7. RU 2273951, 10.12.2004 г.

Реферат

Изобретение относится к вычислительным устройствам, функционирующим в системе остаточных классов, и может быть использовано при аппаратной реализации криптографических алгоритмов. Технический результат - повышение быстродействия устройства. Для этого устройство содержит блоки памяти хранения значений слагаемых, блоки памяти хранения значений знаков слагаемых, многоканальный мультиплексор, мультиплексор, первый вычитающий счетчик, первый многовходовый логический элемент ИЛИ-НЕ, второй вычитающий счетчик, второй многовходовый логический элемент ИЛИ-НЕ, реверсный счетчик по настраиваемому модулю, третий вычитающий счетчик, третий многовходовый логический элемент ИЛИ-НЕ, счетчик по настраиваемому модулю, элементы задержки сигнала, выходной регистр. 1 ил.

Формула