УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ Российский патент 1994 года по МПК G06F7/72 

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

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

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

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

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

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

Коммутатор устройства содержит большое количество элементов (пропорциональное m², где m - модуль операции), что и обуславливает основной недостаток устройства. Недостаток прототипа - большое количество используемых элементов И для построения наиболее громоздкой в аппаратурном отношении части устройства - коммутатора.

Цель изобретения - упрощение устройства за счет сокращения аппаратурных затрат.

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

Сущность изобретения состоит в определении результата операции модульного умножения по частным модулям m₁ и m₂ (m₁ m₂ ≥m) с последующим преобразованием результата операции в двоичный код по модулю m. Предположим, что m₁ ≈ m₂ = m_x. Тогда m₁ ˙ m₂ = m_x² = m. В условиях применения коммутатора, реализующего диагональную симметрию таблицы модульного умножения (авт. св. СССР N 1571583, 1990), находят зависимость для определения общего количества элементов И в трех коммутаторах:
N = 2 · + = ;;
N = + + 1 ≈ ,.

Получают линейную зависимость количества логических элементов коммутаторов от модуля операции. Рассмотрим реализацию операции модульного умножения при m = m₁ ˙m₂ = 3 ˙ 5 = 15. В этом случае операнды α и β представляются в виде α = (α₁ , α₂) и β = (β₁ , β₂), где α₁, β₁ - остатки исходных операндов по модулю m₁= 3; , α₂, β₂ - остатки исходных операндов по модулю m₂ = 5. Построение первого и второго коммутаторов представлено в табл. 1 и 2.

Следует отметить, что при подобном построении коммутаторов реализуется в отличие от прототипа и тот случай, когда один из операндов либо оба равны нулю. Данные таблиц приведены для случая, когда γ_α1 = γ_β1 и γ_α2 = γ_β2 . В других случаях проводится соответствующая коррекция результата операции при помощи третьего коммутатора, представленного на табл. 3 - 6.

Первая и вторая группы элементов ИЛИ состоят из двух элементов. Первый элемент ИЛИ объединяет выходы дешифраторов - 0, 3, 6, 9, 12-й, а второй - 1, 2, 4, 5, 7, 8, 10, 11, 13, 14-й. Первый и второй элементы ИЛИ объединяют выходы 2, 5, 8, 11, 14-й соответствующих дешифраторов. Третья и четвертая группы элементов ИЛИ состоят из трех элементов. Первый элемент ИЛИ этих групп объединяет выходы дешифраторов - 0, 5, 10-й, второй - 1, 4, 6, 9, 11, 14-й, третий - 2, 3, 7, 8, 12, 13-й. Третий и четвертый элементы ИЛИ объединяют выходы 4, 9, 14, 3, 8, 13-й соответствующих дешифраторов.

Первый элемент И при помощи первого шифратора реализует табл. 6, второй элемент И (второй шифратор) - табл. 4, третий элемент И (третий шифратор) - табл. 5 и четвертый элемент И (четвертый шифратор) - табл. 3.

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

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

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

На чертеже представлена структурная схема устройства, где 1 - вход первого сомножителя устройства, 2 - вход второго сомножителя устройства, 3 - первый дешифратор, 4 - второй дешифратор, 5 - первая группа элементов ИЛИ, 6 - вторая группа элементов ИЛИ, 7 - первый элемент ИЛИ, 8 - второй элемент ИЛИ, 9 - первый сумматор по модулю два, 10 - вход запуска устройства, 11 - первый блок элементов И, 12 - третья группа элементов ИЛИ, 13 - четвертая группа элементов ИЛИ, 14 - третий элемент ИЛИ, 15 - четвертый элемент ИЛИ, 16 - второй сумматор по модулю два, 17 - первый коммутатор, 18 - второй коммутатор, 19 - третий коммутатор, 20 - первый шифратор, 21 - второй шифратор, 22 - третий шифратор, 23 - четвертый шифратор, 24 - второй блок элементов И, 25 - третий блок элементов И, 26 - четвертый блок элементов И, 27 - пятый блок элементов И, 28 - блок элементов ИЛИ, 29 - выход устройства, 30 - первый элемент И, 31 - второй элемент И, 32 - третий элемент И, 33 - четвертый элемент И.

Входы первого 1 и второго 2 сомножителей устройства соединены с входами первого 3 и второго 4 дешифраторов, соответствующие группы выходов которых соединены с соответствующими входами элементов ИЛИ соответственно первой 5 и второй 6 групп. Первые группы старших выходов первого 3 и второго 4 дешифраторов соединены с соответствующими входами соответственно первого 7 и второго 8 элементов ИЛИ, выходы которых соединены соответственно с первым и вторым входами первого сумматора 9 по модулю два. Вход 10 запуска устройства соединен с первым входом первого блока 11 элементов И, соответствующие группы входов первого 3 и второго 4 дешифраторов соединены с соответствующими входами элементов ИЛИ соответственно третьей 12 и четвертой 13 групп, вторые группы старших выходов первого 3 и второго 4 дешифраторов соединены с соответствующими входами соответственно третьего 14 и четвертого 15 элементов ИЛИ, выходы которых соединены соответственно с первым и вторым входами второго сумматора 16 по модулю два. Выходы первой 5 и третьей 12 групп элементов ИЛИ соединены с группами информационных входов, а выходы второй 6 и четвертой 13 групп элементов ИЛИ - с группами управляющих входов соответственно первого 17 и второго 18 коммутаторов, выходы которых соединены соответственно с группами информационных и управляющих входов третьего коммутатора 19. Группа выходов последнего соединена с соответствующими входами с первого по четвертый шифраторов 20 - 23, выходы которых соединены с первыми входами соответственно с второго по пятый блоков 24 - 27 элементов И. Выходы блоков 24 - 27 элементов И соединены с соответствующими входами блока 28 элементов ИЛИ, выход которого соединен с вторым входом первого блока 11 элементов И, выход которого является выходом 29 устройства. Прямой выход первого сумматора 9 по модулю два соединен с первыми входами первого 30 и второго 31 элементов И, а инверсный - с первыми входами третьего 32 и четвертого 33 элементов И. Прямой выход второго сумматора 16 по модулю два соединен с вторыми входами первого 30 и третьего 32 элементов И, а инверсный - с вторыми входами второго 31 и четвертого 33 элементов И. Выходы с первого по четвертый элементов И 30 - 33 соединены с вторыми входами соответственно с второго по пятый блоков 24 - 27 элементов И.

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

Первый и второй сомножители поступают на соответствующие дешифраторы 3 и 4, с выходов которых операнды в унитарном коде поступают на соответствующие элементы ИЛИ 5 и 6 первой и второй групп, а также на соответствующие элементы ИЛИ 12 и 13 третьей и четвертой групп. Элементы ИЛИ 5 (6) реализуют определение остатка операнда α (β) по модулю m₁, а также симметрию таблицы модульного умножения по модулю m₁ относительно горизонтали (вертикали). Элементы ИЛИ 12 (13) проводят аналогичную операцию относительно модуля m₂. Сумматор 9 по модулю два производит сравнение величин γ_α1 и γ_β1 , а сумматор 16 по модулю два - γ_α2 и γ_β2 . С выходов элементов ИЛИ 5 и 6 сигналы поступают соответственно на информационные и управляющие входы первого коммутатора 17, с выходов которого результат операции модульного умножения ( α₁ * β₁ ) mod m₁ поступает на информационные входы третьего коммутатора 19, на управляющие входы которого с выходов второго коммутатора 18 поступает результат операции модульного умножения ( α₂ * β₂ ) mod m₂. На выходе третьего коммутатора 19 формируется в унитарном коде результат операции ( α * β ) mod m. Окончательный результат операции модульного умножения формируется шифраторами 20 - 23 в зависимости от соотношения величин γ_α1 и γ_β1 (γ_α2 и γ_β2 ). Возможны четыре случая:
= , = ;;
, = ;;
= , ;;
, ..

В первом случае по сигналам с инверсных выходов первого 9 и второго 16 сумматоров по модулю два сигнал с выхода четвертого элемента И поступает на второй вход пятого блока 27 элементов И. Результат операции модульного умножения в двоичном коде с выхода четвертого шифратора 23 поступает через блок 28 элементов ИЛИ, с выхода которого он поступает на второй вход первого блока 11 элементов И. По сигналу с входа 10 запуска устройства результат операции поступает на выход 29 устройства. В других случаях результат операции реализуется при помощи элементов И 30 - 32 и соответствующими шифраторами 20 - 22.

Рассмотрим примеры конкретного выполнения модульной операции умножения при m = 15, m₁ = 3, m₂ = 5.

П р и м е р 1. Пусть необходимо определить результат операции модульного умножения для α = (α₁, α₂) = 4 = (1, 4) и β = (β₁, β₂) = 7 = (1, 2). При α₁ = 1 сигнал поступает на выход второго элемента ИЛИ 6 группы. В виду того, что α₂ = 4, а β₂ = =2, сигналы поступают на выходы соответственно второго элемента ИЛИ третьей группы 12 и третьего элемента ИЛИ четвертой группы 13. В соответствии с табл. 1 и 2 сигналы поступают на первый информационный и второй управляющий входы третьего коммутатора 19. В данном случае γ_α1 = γ_β1, γ_α2 ≠ γ_β2 и, следовательно, сигналы имеются на инверсном выходе первого сумматора 9 по модулю два и прямом выходе второго сумматора 16 по модулю два. На выходе третьего элемента И 32 имеется сигнал, который поступает на вход четвертого блока 26 элементов И (производится выбор табл. 5). Значение результата, равное 13, поступает через блок 28 элементов ИЛИ и далее через первый блок 11 элементов И по сигналу с входа 10 запуска устройства на выход 29 устройства. Проверка: 4 х 7 mod 15 = 13 mod 15.

П р и м е р 2. Пусть необходимо определить результат операции модульного умножения для α = 6 = (0, 1) и β = 7 = (1, 2). При α₁= 0 сигнал поступает на выход первого элемента ИЛИ первой группы 5, а при α₂ = 1 - на выход второго элемента ИЛИ третьей группы 12. Прохождение второго операнда аналогично примеру 1. В соответствии с табл. 1 и 2 сигналы поступают на нулевой информационный и второй управляющий входы третьего коммутатора 19. В данном случае γ_α1 = γ_β1, γ_α2 = γ_β2 , поэтому на выходе четвертого элемента И 33 имеется сигнал (выбирается табл. 3). Результат операции модульного умножения, равный 12, в двоичном коде через соответствующие цепи поступает на выход 29 устройства. Проверка: 6 х 7 mod 15 = 12 mod 15.

Техническое преимущество изобретения по сравнению с прототипом состоит в существенном упрощении устройства. В частности, для m = 15 требуется всего 15 элементов И для построения всех трех коммутаторов, для прототипа необходимо иметь 42 элемента И. В общем случае выигрыш происходит примерно в m/2 раз, что существенно упрощает построение устройства модульного умножения как за счет уменьшения логических элементов, так и связей между ними.

Достоверность достижения цели подтверждается примерами выполнения операции модульного умножения для m = 15.

Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Устройство содержит дешифраторы 3, 4, четыре группы элементов ИЛИ 5, 6, 12, 13, четыре элемента ИЛИ 7, 8, 14, 15, два сумматора 9, 16 по модулю два, с первого по четвертый элементы И 30-33, три коммутатора 17-19, четыре шифратора 20-23, пять блоков 11, 24-27 элементов И, блок 28 элементов ИЛИ. Сущность изобретения состоит в определении результата операции модульного умножения по частным модулям m₁ и m₂ (m₁·m₂ ≥ m, , m - модуль операции) с последующим преобразованием результата операции в двоичный код по модулю m. 6 табл., 1 ил.

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ, содержащее первый и второй дешифраторы, элементы ИЛИ первой и второй групп, первый и второй элементы ИЛИ, первый коммутатор, первый шифратор, первый блок элементов И, первый сумматор по модулю два, причем входы первого и второго сомножителей устройства соединены с входами первого и второго дешифраторов соответственно, первые выходы соответствующих групп которых соединены с соответствующими входами элементов ИЛИ первой и второй групп соответственно, выходы первых старших групп первого и второго дешифраторов соединены с соответствующими входами первого и второго элементов ИЛИ соответственно, выходы которых соединены соответственно с первым и вторым входами первого сумматора по модулю два, вход запуска устройства соединен с первыми входами элементов И первого блока, отличающееся тем, что устройство содержит элементы ИЛИ третьей и четвертой групп, третий и четвертый элементы ИЛИ, второй сумматор по модулю два, с первого по четвертый элементы И, второй и третий коммутаторы, с второго по четвертый шифраторы, с второго по пятый блоки элементов И, блок элементов ИЛИ, вторые выходы соответствующих групп первого и второго дешифраторов соединены с соответствующими входами элементов ИЛИ третьей и четвертой групп, выходы вторых старших групп первого и второго дешифраторов соединены с соответствующими входами третьего и четвертого элементов ИЛИ, выходы которых соединены с первым и вторым входами соответственно второго сумматора по модулю два, выходы элементов ИЛИ первой и третьей групп соединены с информационными входами первого и второго коммутаторов соответственно, управляющие входы которых соединены с выходами элементов ИЛИ второй и четвертой групп соответственно, выходы первого и второго коммутаторов соединены с информационными и управляющми входами соответственно третьего коммутатора, выходы которого соединены с соответствующими входами с первого по четвертый шифраторы, выходы которых соединены с первыми входами элементов И с второго по пятый блоки, выходы которых соединены с соответствующими входами элементов ИЛИ блока, выходы которого соединены с вторыми входами элементов И первого блока, выходы которых являются выходами устройства, прямой выход первого сумматора по модулю два соединен с первыми входами первого и второго элементов И, инверсный выход первого сумматора по модулю два соединен с первыми входами третьего и четвертого элементов И, прямой выход второго сумматора по модулю два соединен с вторыми входами первого и третьего элементов И, инверсный выход второго сумматора по модулю два соединен с вторыми входами второго и четвертого элементов И, выходы элементов И с первого по четвертый соединены с вторыми входами элементов И с второго по пятый блоки соответственно.