Устройство для умножения чисел по модулю

 

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

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

Известно устройство (аналог) (авт. св. СССР N 1615714, МКИ G 06 F 7/72, Б. И. N 47, 1990 г.), содержащее два дешифратора, три труппы элементов ИЛИ, два блока элементов И, коммутатор, шифратор, блок инвертирования, вычитатель по модулю, две группы элементов И, сумматор по модулю два. Недостаток устройства - большое количество оборудования.

Известно также устройство (аналог) (авт. св. СССР N 1775721, МКИ G 06 F 7/49, 7/72, Б.И. N 42, 1992 г.), содержащее два дешифратора, группы элементов ИЛИ, элементы ИЛИ и И, элементы НЕ, блоки элементов И, элемент запрета, коммутатор, сумматор по модулю два, шифраторы. Недостаток устройства - большое количество оборудования.

Наиболее близким по технической сущности (прототипом к предполагаемому изобретению) является устройство (авт. св. СССР N1667055, МКИ G 06 F 7/49, 7/52, Б.И. N 28, 1991 г.), содержащее дешифратор, две группы элементов ИЛИ, два элемента ИЛИ, пять элементов И, две группы элементов И, шифратор, регистр и коммутатор. Общее количество логических элементов И коммутатора составляет m²/8, где m - модуль устройства, что обуславливает основной недостаток устройства.

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

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

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

Сущность изобретения состоит в совмещении операций по двум внутренним модулям устройства на одном табличном вычислителе за несколько тактов работы, ввиду чего происходит уменьшение числа логических элементов, необходимых для реализации устройства. Обозначим через m - модуль устройства, m₁ - первый внутренний модуль устройства, m₂ - второй внутренний модуль устройства (m₁ > m₂, m₁ · m₂ ≅ m). Для взаимно простых модулей m₁ и m₂ операцию модульного умножения с операндами А и В можно представить в виде A·B mod m = (α₁·β₁,α₂·β₂) = (t₁,t₂), где α₁(β₁) = A(B) mod m₁, α₂(β₂) = A(B) mod m₂. Исходя из минимизации количества используемого оборудования, целесообразно выбирать m₁ ≈ m₂, т.е. Рассмотрим реализацию основных узлов устройства при m = 12, m₁ = 4, m₂ = 3. Для выполнения операции модульного умножения по внутренним модулям m₁ = 4 и m₂ = 3 необходимо иметь соответствующие табл. 1 и 2.

Для восстановления результата операции умножения по модулю m устройства необходимо иметь табл.3.

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

Преобразователи 2, 11 двоичного кода числа реализуют табл. 4.

Преобразователи 3, 12 двоичного кода числа реализуют табл.5.

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

Следует отметить, что предварительный анализ операндов А и В на равенство нулю позволит упростить схемотехническое решение предлагаемого устройства за счет уменьшения количества оборудования при построении его отдельных узлов.

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

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

Первый 1 информационный вход устройства соединен с входами первых преобразователей 2, 3 двоичного кода числа в унитарный код соответственно по первому и второму внутренним модулям устройства, выходы которых соединены с первыми входами соответственно первого 4 и второго 5 блоков элементов И, выходы разрядов которых соединены с соответствующими информационными входами табличного 6 вычислителя, выходы которого соединены с соответствующими первыми входами разрядов пятого 7, шестого 8 и седьмого 9 блоков элементов И, второй 10 информационный вход устройства соединен с входами вторых 11, 12 преобразователей двоичного кода числа в унитарный код соответственно по первому и второму внутренним модулям устройства, выходы которых соединены с первыми входами соответственно третьего 13 и четвертого 14 блоков элементов И, выходы разрядов которых соединены с соответствующими управляющими входами табличного 6 вычислителя, выходы пятого 7 и шестого 8 блока элементов И соединены со входами соответственно первого 15 и второго 16 регисторов, выходы которых соединены с первыми входами соответственно восьмого 17 и девятого 18 блоков элементов И, выходы разрядов которых соединены соответственно с соответствующими информационными и управляющими входами табличного 6 вычислителя, первый 19 тактовый вход устройства соединен со вторыми входами первого 4, третьего 13 и пятого 7 блоков элементов И, второй 20 тактовый вход устройства соединен со вторыми входами второго 5, четвертого 14 и шестого 8 блоков элементов И, третий 21 тактовый вход устройства соединен со вторыми входами восьмого 17, седьмого 9 и девятого 18 блоков элементов И, выход седьмого 9 блока элементов И соединен с входом шифратора 22, выход которого является выходом 23 устройства.

Работа устройства происходит на три такта.

При первом такте работы поступает сигнал на первый 19 тактовый вход устройства. Одновременно этот сигнал поступает на вторые входы первого 4, третьего 13 и пятого 7 блоков элементов И. Операнд А в двоичном коде поступает с первого 1 информационного входа устройства на вход первого преобразователя 2 двоичного кода числа в унитарный код по первому внутреннему модулю устройства, с выхода которого A mod m₁ в унитарном коде поступает на первый вход α₁-го разряда первого 4 блока элементов И и далее на соответствующий информационный вход табличного 6 вычислителя. Операнд В в двоичном коде поступает со второго 10 информационного входа устройства на вход второго преобразователя 11 двоичного кода числа в унитарный код по первому внутреннему модулю устройства, с выхода которого В mod m₁ в унитарном коде поступает на первый вход β₁-го разряда третьего 13 блока элементов И и далее на соответствующий управляющий вход табличного 6 вычислителя. Результат операции α₁·β₁ mod m₁ поступает с t₁-го выхода табличного 6 вычислителя на первый вход соответствующего разряда пятого 7 блока элементов И, с выхода которого результат модульного умножения по первому внутреннему модулю устройства фиксируется записью единицы в t₁-м разряде первого 15 регистра.

На втором такте работы сигнал поступает на второй 20 тактовый вход устройства и процесс определения результата операции умножения по второму m₂ внутреннему модулю устройства α₂·β₂ mod m₂, с точностью до соответствующих элементов, происходит аналогичным образом. Это фиксируется записью единицы в t₂-м разряде второго 16 регистра.

На третьем такте работы сигнал поступает на третий 21 тактовый вход устройства. Одновременно этот сигнал поступает на вторые входы седьмого 9, восьмого 17 и девятого 18 блоков элементов И. С выхода первого 15 и второго 16 регистров поступают сигналы соответственно на t₁-й информационный и t₂-й управляющий входы табличного 6 вычислителя, с выхода которого результат операции модульного умножения поступает на А·В mod m-й первый вход седьмого 9 блока элементов И. Табличный 6 вычислитель на третьем такте работы производит восстановление результата операции по модулю устройства m. С выхода седьмого 9 блока элементов И результат операции модульного умножения в унитарном коде поступает на вход шифратора 22, с выхода которого в двоичном коде - на выход 23 устройства.

Рассмотрим пример выполнения операции A·B mod m при m=12, А = 5, В = 7, m₁ = 4, m₂ = 3. В этом случае операнд А = 0101₂ и В = 0111₂ поступают соответственно на первый 1 и второй 10 информационные входы устройства. По первому такту работы с выходов первого 2 и второго 11 преобразователей двоичного кода числа в унитарный код по первому внутреннему модулю на первый информационный и третий управляющий входы табличного 6 вычислителя через соответствующие разряды первого 4 и третьего 13 блоков элементов И поступают сигналы (см. табл. 4). С выходов табличного 6 вычислителя сигнал поступает через пятый 7 блок элементов И на запись единицы в третий разряд первого 15 регистра (см. табл. 1). При втором такте работы устройства с выхода первого 3 и второго 12 преобразователей двоичного кода числа в унитарный код по второму внутреннему модулю поступают сигналы на второй информационный и первый управляющий входы табличного 6 вычислителя через соответствующие разряды второго 5 и четвертого 14 блоков элементов И (см. табл. 5). С выходов табличного 6 вычислителя сигнал поступает через шестой 8 блок элементов И на запись единицы во второй разряд второго 16 регистра (см. табл. 2). На третьем такте работы с выходов первого 15 и второго 16 регистров поступают сигналы на третий информационный и второй управляющий входы табличного 6 вычислителя, с выхода которого сигнал поступает на одиннадцатый вход шифратора 22 (см. табл. 3) через соответствующий элемент седьмого 9 блока элементов И. На выходе шифратора 22 будет число 1011₂, которое поступит на выход 23 устройства. Проверка: 5 · 7 mod 12 = 11 mod 12.

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

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

РИСУНКИ

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