RU2143723C1

RU2143723C1 - Device for modulo multiplication of numbers

Info

Publication number: RU2143723C1
Application number: RU98114897A
Authority: RU
Inventors: В.П. Ирхин; Е.Б. Глазков; И.М. Лукьянов; С.С. Гульбин
Original assignee: Воронежский государственный университет
Priority date: 1998-07-29
Filing date: 1998-07-29
Publication date: 1999-12-27

Abstract

FIELD: automation and computer engineering, in particular, devices which operate in residual class system. SUBSTANCE: Goal of invention is achieved by introduced tabular calculation unit, first and second converters of binary number code into unitary code by first internal device modulo, first and second converters of binary number code into unitary code by second internal device modulo, third to sixth units of AND gates, converter of unitary code by first internal device modulo into binary position code, converter of unitary code by second internal device modulo into binary position code, and device modulo adder. EFFECT: simplified design of equipment, which implements modulo multiplication. 1 dwg, 6 tbl

Description

Изобретение относится к области автоматики и вычислительной техники и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. The invention relates to the field of automation and computer engineering and can be used in computers and devices operating in a system of residual classes.

Известно устройство (аналог) (авт. св. СССР N 1615714, МКИ G 06 F 7/49, 7/72, Б.И. N 47, 1990 г.), содержащее два дешифратора, три группы элементов ИЛИ, два блока элементов И, коммутатор, шифратор, блок инвестирования, вычитатель по модулю, две группы элементов И, сумматор по модулю два. Недостаток устройства - большое количество оборудования. A device (analog) is known (ed. St. USSR N 1615714, MKI G 06 F 7/49, 7/72, B.I. N 47, 1990), containing two decoders, three groups of OR elements, two blocks of elements And, a switch, an encoder, an investment unit, a modifier subtractor, two groups of AND elements, an adder modulo two. The disadvantage of this device is a large amount of equipment.

Известно также устройство (аналог) (авт. св. СССР N 1775721, МКИ G 06 F 7/49, 7/72, Б.И. N 42, 1992 г.), содержащее два дешифратора, группы элементов ИЛИ, элементы ИЛИ и И, элементы НЕ, блоки элементов И, элемент запрета, коммутатор, сумматор по модулю два, шифраторы. Недостаток устройства - большое количество оборудования. A device (analogue) is also known (ed. St. USSR N 1775721, MKI G 06 F 7/49, 7/72, B.I. N 42, 1992), containing two decoders, groups of OR elements, OR elements and And, elements NOT, blocks of elements AND, prohibition element, switch, adder modulo two, encoders. The disadvantage of this device is a large amount of equipment.

Наиболее близким по технической сущности (прототипом к предлагаемому изобретению) является устройство (авт. св. СССР N 1667055, МКИ G 06 F 7/49, 7/72, Б.И. N 28, 1991 г.), содержащее дешифратор, две группы элементов ИЛИ, два элемента ИЛИ, пять элементов И, две группы элементов И, шифратор, регистр и коммутатор. Общее количество логических элементов И коммутатора составляет m²/8, где m - модуль устройства, что обуславливает основной недостаток устройства.The closest in technical essence (prototype to the proposed invention) is a device (ed. St. USSR N 1667055, MKI G 06 F 7/49, 7/72, B.I. N 28, 1991), containing a decoder, two groups of OR elements, two OR elements, five AND elements, two groups of AND elements, an encoder, a register, and a switch. The total number of AND gates switch is m ^2/8 where m - module device, which causes the main drawback of the device.

Недостаток прототипа - большое количество используемого оборудования, ввиду того, что количество логических элементов коммутатора пропорционально квадрату модуля. The disadvantage of the prototype is the large amount of equipment used, due to the fact that the number of logical elements of the switch is proportional to the square of the module.

Задача, на решение которой направлено заявляемое устройство, состоит в повышении надежности перспективных образцов вычислительной техники. The problem, which is aimed by the claimed device, is to increase the reliability of promising samples of computer technology.

Технический результат выражается в уменьшении количества оборудования для выполнения модульной операции умножения. The technical result is expressed in reducing the amount of equipment to perform a modular operation of multiplication.

Технический результат достигается тем, что в устройство, содержащее первый и второй блоки элементов И и регистр, отличающееся тем, что в него введены табличный вычислитель, первый и второй преобразователи двоичного кода числа в унитарный код по первому внутреннему модулю устройства, первый и второй преобразователи двоичного кода числа в унитарный код по второму внутреннему модулю устройства, с третьего по шестой блоки элементов И, преобразователь унитарного кода числа по первому внутреннему модулю устройства в двоичный позиционный код, преобразователь унитарного кода числа по второму внутреннему модулю устройства в двоичный позиционный код и сумматор по модулю устройства, причем первый информационный вход устройства соединен с входами первых преобразователей двоичного кода числа в унитарный код соответственно по первому и второму внутренним модулям устройства, выходы которых соединены с первыми входами соответственно первого и второго блоков элементов И, выходы которых соединены с соответствующими информационными входами табличного вычислителя, выходы которого соединены с соответствующими первыми входами пятого и шестого блоков элементов И, второй информационный вход устройства соединен с входами вторых преобразователей двоичного кода числа в унитарный код соответственно по первому и второму внутренним модулям устройства, выходы которых соединены с первыми входами соответственно третьего и четвертого блоков элементов И, выходы которых соединены с соответствующими управляющими входами табличного вычислителя, выход шестого блока элементов И соединен со входом преобразователя унитарного кода числа по второму внутреннему модулю устройства в двоичный позиционный код, выход которого соединен с вторым входом сумматора по модулю устройства, выход которого является выходом устройства, выход пятого блока элементов И соединен со входом регистра, выход которого соединен со входом преобразователя унитарного кода числа по первому внутреннему модулю устройства в двоичный позиционный код, выход которого соединен с первым входом сумматора по модулю устройства, первый тактовый вход устройства соединен со вторыми входами первого, третьего и пятого блоков элементов И, второй тактовый вход устройства соединен со вторыми входами второго, четвертого и шестого блоков элементов И. The technical result is achieved in that in a device containing the first and second blocks of AND elements and a register, characterized in that a table computer, first and second converters of the binary code of the number to unitary code according to the first internal module of the device, the first and second converters of binary are entered into it the code of the number into a unitary code according to the second internal module of the device, from the third to the sixth blocks of AND elements, the converter of the unitary code of the number according to the first internal module of the device into a binary positional code, a unitary number code converter according to the second internal module of the device into a binary positional code and an adder modulo the device, the first information input of the device being connected to the inputs of the first converters of the binary code of the number to the unitary code, respectively, through the first and second internal modules of the device, the outputs of which are connected to the first inputs respectively, the first and second blocks of AND elements, the outputs of which are connected to the corresponding information inputs of a table computer, the outputs of which connected to the corresponding first inputs of the fifth and sixth blocks of AND elements, the second information input of the device is connected to the inputs of the second converters of the binary code of the number into a unitary code, respectively, by the first and second internal modules of the device, the outputs of which are connected to the first inputs of the third and fourth blocks of AND elements, respectively the outputs of which are connected to the corresponding control inputs of the table computer, the output of the sixth block of elements And is connected to the input of the unitary converter ode of the number of the second internal module of the device into a binary positional code, the output of which is connected to the second input of the adder modulo the device, the output of which is the output of the device, the output of the fifth block of elements AND is connected to the input of the register, the output of which is connected to the input of the unitary code converter of the number of the first the internal module of the device in a binary positional code, the output of which is connected to the first input of the adder modulo the device, the first clock input of the device is connected to the second inputs of the first of the fifth and fifth blocks of AND elements, the second clock input of the device is connected to the second inputs of the second, fourth and sixth blocks of AND elements.

Сущность изобретения состоит в совмещении операций по двум внутренним модулям устройства на одном табличном вычислителе за несколько тактов работы, ввиду чего происходит уменьшение числа логических элементов, необходимых для реализации устройства. Обозначим через m - модуль устройства, m₁ - первый внутренний модуль устройства, m₂ - второй внутренний модуль устройства (m₁ > m₂). Для взаимно простых модулей m₁ и m₂ операцию модульного умножения с операндами A и B можно представить в виде
A•B mod m = (α₁•β₁,α₂•β₂) = (t₁,t₂),
где α₁(β₁) = A(B)mod m₁, α₂(β₂) = A(B)mod m₂.The essence of the invention consists in combining operations on two internal modules of the device on one tabular computer for several clock cycles, which means that there is a decrease in the number of logical elements needed to implement the device. Denote by m the device module, m _{1 the} first internal device module, m _{2 the} second internal device module (m ₁ > m ₂ ). For coprime modules m ₁ and m _{2, the} operation of modular multiplication with operands A and B can be represented as
A • B mod m = (α ₁ • β ₁ , α ₂ • β ₂ ) = (t ₁ , t ₂ ),
where α ₁ (β ₁ ) = A (B) mod m ₁ , α ₂ (β ₂ ) = A (B) mod m ₂ .

Исходя из минимизации количества используемого табличного оборудования, целесообразно выбирать m₁ ≈ m₂, т. е.

Рассмотрим реализацию основных узлов устройства при m = 12, m₁ = 4, m₂ = 3. Для выполнения операции модульного умножения по внутренним модулям m₁ = 4, m₂ = 3 необходимо иметь соответствующие таблицы 1 и 2.Based on minimizing the amount of tabular equipment used, it is advisable to choose m ₁ ≈ m ₂ , i.e.

Consider the implementation of the main nodes of the device with m = 12, m ₁ = 4, m ₂ = 3. To perform the operation of modular multiplication by internal modules m ₁ = 4, m ₂ = 3, it is necessary to have the corresponding tables 1 and 2.

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

т.е. пропорционально модулю устройства.Table 6 calculator is an overlay of tables 1 and 2, the total number of logical elements N of which will be

those. in proportion to the device module.

Преобразователи 2, 10 двоичного кода числа реализуют таблицу 3. Converters 2, 10 of the binary code of the number implement table 3.

Преобразователь 3, 11 двоичного кода числа реализуют таблицу 4. The binary number code converter 3, 11 implements table 4.

Блоки, реализующие таблицы 3 и 4, могут быть выполнены, например, на программируемых логических матрицах. Регистр 17 содержит четыре разряда (с нулевого по третий). Blocks implementing tables 3 and 4 can be performed, for example, on programmable logic matrices. Register 17 contains four bits (from zero to third).

Результат операции модульного умножения по первому m₁ и второму m₂ внутренним модулям устройства можно представить в виде
A•B mod m = (t₂, t₂) mod m = [(t₁, 0) + (0, t₂)] mod m,
где t₁ = α₁β₁mod m₁, t₂ = α₂β₂mod m₂, а α₁(β₁) и α₂(β₂) - остатки, которыми представлены операнды A и B по соответствующим внутренним модулям m₁ и m₂.The result of the operation of modular multiplication by the first m ₁ and second m ₂ internal modules of the device can be represented as
A • B mod m = (t ₂ , t ₂ ) mod m = [(t ₁ , 0) + (0, t ₂ )] mod m,
where t ₁ = α ₁ β ₁ mod m ₁ , t ₂ = α ₂ β ₂ mod m ₂ , and α ₁ (β ₁ ) and α ₂ (β ₂ ) are the residues that represent the operands A and B in the corresponding internal modules m ₁ and m ₂ .

Преобразователь 18 унитарного кода числа по первому внутреннему модулю устройства в двоичный позиционный код реализует таблицу 5, а преобразователь 14 унитарного кода числа по второму внутреннему модулю устройства в двоичный позиционный код реализует таблицу 6. The converter 18 of the unitary number code for the first internal module of the device into a binary positional code implements table 5, and the converter 14 of the unitary code of the number for the second internal module of the device to binary positional code implements table 6.

A•B mod m=[f(t₁)+f(t₂)] mod m,
где f(t₁) и f(t₂) - позиционные представления соответственно кодов (t₁, 0) и (0, t₂) в диапазоне чисел

.A • B mod m = [f (t ₁ ) + f (t ₂ )] mod m,
where f (t ₁ ) and f (t ₂ ) are positional representations of codes (t ₁ , 0) and (0, t ₂ ), respectively, in the range of numbers

.

Подобный прием можно использовать для перевода чисел из системы остаточных классов (СОК) в позиционную систему счисления по нескольким модулям. Если число C изображается набором остатков по всем модулям

C = (C₁,C₂...,C_n) =(C₁, 0,...,0)+(0,C₂,...,0)+...+(0,0,...,C_n), то (C)₁₀ = [f(c₁) + f(c₂) +...+f(c_n)] mod M,
где

Такое представление числа в СОК аналогично разложению по соответствующим модулям m₁ в позиционном коде и является однозначным. В отличие от ряда известных алгоритмов перевода числа из СОК в позиционную (десятичную) систему, этот алгоритм не требует для его выполнения операций умножения и деления. Преобразование C₁--->f(C₁) соответствует переводу числа (C₁, 0,..., 0) из СОК в позиционный код. В частности, согласно табл. 5 число 6 = (2, 0) по внутренним модулям m₁ = 4, m₂ = 3; а число 4 = (0, 1) по соответствующим внутренним модулям согласно табл. 6. Сумматор 15 по модулю устройства является арифметико-логическим устройством комбинационного типа. Следует отметить, что предварительный анализ операндов A и B на равенство нулю позволит упростить схематическое решение предлагаемого устройства за счет дополнительного уменьшения количества оборудования при построении его отделочных узлов.A similar technique can be used to translate numbers from the system of residual classes (RNS) into a positional number system for several modules. If the number C is represented by a set of residuals for all modules

C = (C ₁ , C ₂ ..., C _n ) = (C ₁ , 0, ..., 0) + (0, C ₂ , ..., 0) + ... + (0,0 , ..., C _n ), then (C) ₁₀ = [f (c ₁ ) + f (c ₂ ) + ... + f (c _n )] mod M,
Where

Such a representation of the number in the RNS is similar to the expansion in the corresponding modules m ₁ in the positional code and is unambiguous. Unlike a number of well-known algorithms for converting a number from a RNS to a positional (decimal) system, this algorithm does not require multiplication and division operations to perform it. The conversion C ₁ ---> f (C ₁ ) corresponds to the translation of the number (C ₁ , 0, ..., 0) from the RNS into a positional code. In particular, according to table. 5 number 6 = (2, 0) for the internal modules m ₁ = 4, m ₂ = 3; and the number 4 = (0, 1) for the corresponding internal modules according to the table. 6. The adder 15 modulo the device is an arithmetic logic device of a combination type. It should be noted that a preliminary analysis of operands A and B for equality to zero will simplify the schematic solution of the proposed device due to an additional reduction in the number of equipment when constructing its finishing units.

Возможность достижения положительного эффекта от использования данного изобретения состоит в уменьшении количества оборудования, применяемого при построении табличных устройств модульной арифметики. Этот эффект существенно возрастает с ростом модуля устройства. The ability to achieve a positive effect from the use of this invention is to reduce the amount of equipment used in the construction of tabular devices of modular arithmetic. This effect increases significantly with the growth of the device module.

На чертеже представлена структурная схема, где: 1 - первый информационный вход устройства, 2 - первый преобразователь двоичного кода числа в унитарный код по первому внутреннему модулю устройства, 3 - первый преобразователь двоичного кода числа в унитарный код по второму внутреннему модулю устройства, 4 - первый блок элементов И, 5 - второй блок элементов И, 6 - табличный вычислитель, 7 - пятый блок элементов И, 8 - шестой блок элементов И, 9 - второй информационный вход устройства, 10 - второй преобразователь двоичного кода числа в унитарный код по первому внутреннему модулю устройства, 11 - второй преобразователь двоичного кода числа в унитарный код по второму внутреннему модулю устройства, 12 - третий блок элементов И, 13 - четвертый блок элементов И, 14 - преобразователь унитарного кода числа по второму внутреннему модулю в двоичный позиционный код, 15 - сумматор по модулю устройства, 16 - выход устройства, 17 - регистр, 18 - преобразователь унитарного кода числа по первому внутреннему модулю устройства в двоичный позиционный код, 19 - первый тактовый вход устройства, 20 - второй тактовый вход устройства. The drawing shows a structural diagram, where: 1 - the first information input of the device, 2 - the first converter of the binary code of the number into a unitary code by the first internal module of the device, 3 - the first converter of the binary code of the number by the unitary code by the second internal module of the device, 4 - the first block of elements And, 5 - the second block of elements And, 6 - a table computer, 7 - the fifth block of elements And, 8 - the sixth block of elements And, 9 - the second information input of the device, 10 - the second converter of the binary code of the number into a unitary code per the second internal module of the device, 11 is the second converter of the binary code of the number to the unitary code according to the second internal module of the device, 12 is the third block of the elements And, 13 is the fourth block of the elements of And, 14 is the converter of the unitary code of the number of the second internal module to the binary positional code, 15 - adder modulo device, 16 - device output, 17 - register, 18 - unitary number code converter for the first internal device module to a binary position code, 19 - first device clock, 20 - second device clock Twa.

Первый 1 информационный вход устройства соединен с входами первых 2, 3 преобразователей двоичного числа в унитарный код соответственно по первому и второму внутренним модулям устройства, выходы которых соединены с первыми входами соответственно первого 4 и второго 5 блоков элементов И, выходы разрядов которых соединены с соответствующими информационными входами табличного 6 вычислителя, выходы которого соединены с соответствующими первыми входами разрядов пятого 7 и шестого 8 блоков элементов И, второй 9 информационный вход устройства соединен с входами вторых 10, 11 преобразователей двоичного числа в унитарный код соответственно по первому и второму внутренним модулям устройства, выходы которых соединены с первыми входами третьего 12 и четвертого 13 блоков элементов И, выходы разрядов которых соединены с соответствующими управляющими входами табличного 6 вычислителя, выход 8 блока элементов И соединен со входом преобразователя 14 унитарного кода числа по второму внутреннему модулю устройства в двоичный позиционный код, выход которого соединен со вторым входом сумматора 15 по модулю устройства, выход которого является выходом 16 устройства, выход пятого 7 блока элементов И соединен со входом регистра 17, выход которого соединен со входом преобразователя 18 унитарного кода числа по первому внутреннему модулю устройства в двоичный позиционный код, выход которого соединен с первым входом сумматора 15 по модулю устройства, первый 19 тактовый вход устройства соединен со вторыми входами первого 4, третьего 12 и пятого 7 блоков элементов И, второй 20 тактовый вход устройства соединен со вторыми входами второго 5, четвертого 13 и шестого 8 блоков элементов И. The first 1 information input of the device is connected to the inputs of the first 2, 3 converters of binary number into unitary code, respectively, according to the first and second internal modules of the device, the outputs of which are connected to the first inputs of the first 4 and second 5 blocks of AND elements, the outputs of which bits are connected to the corresponding information the inputs of the tabular 6 calculator, the outputs of which are connected to the corresponding first inputs of the digits of the fifth 7 and sixth 8 blocks of elements And, the second 9 information input of the device with it is single with the inputs of the second 10, 11 converters of the binary number into unitary code, respectively, according to the first and second internal modules of the device, the outputs of which are connected to the first inputs of the third 12 and fourth 13 blocks of AND elements, the outputs of the bits of which are connected to the corresponding control inputs of the table 6 calculator, the output 8 block of elements And is connected to the input of the converter 14 of the unitary code of the number of the second internal module of the device into a binary positional code, the output of which is connected to the second input of the adder 15 modulo the device, the output of which is the output 16 of the device, the output of the fifth 7 block of elements And is connected to the input of the register 17, the output of which is connected to the input of the converter 18 of the unitary code of the number according to the first internal module of the device into a binary position code, the output of which is connected to the first input of the adder 15 modulo the device, the first 19 clock input of the device is connected to the second inputs of the first 4, third 12 and fifth 7 blocks of elements And, the second 20 clock input of the device is connected to the second inputs of the second 5, fourth about 13 and sixth 8 blocks of elements I.

Работа устройства происходит на два такта. The device operates in two cycles.

При первом такте работы поступает сигнал на первый 19 тактовый вход устройства. Одновременно этот сигнал поступает на вторые входы первого 4, третьего 12 и пятого 7 блоков элементов И. Операнд A в двоичном коде поступает с первого 1 информационного входа устройства на вход первого преобразователя 2 двоичного кода в унитарный код по первому внутреннему модулю устройства, с выхода которого A mod m₁ в унитарном коде поступает на первый вход α₁-го разряда первого 4 блока элементов И и далее на соответствующий информационный вход табличного 6 вычислителя. Операнд В в двоичном коде поступает со второго 9 информационного входа устройства на вход второго преобразователя 10 двоичного кода числа в унитарный код по первому внутреннему модулю устройства, с выхода которого B mod m₁ в унитарном коде поступает на первый вход β₁-го разряда третьего 12 блока элементов И и далее на соответствующий управляющий вход табличного 6 вычислителя. Результат операции α₁•β₁ mod m₁ поступает с t₁-го выхода табличного 6 вычислителя на первый вход соответствующего разряда пятого 7 блока элементов И, с выхода которого результат модульного умножения по первому внутреннему модулю устройства фиксируется записью единицы в t₁-м разряде регистра 17. С выхода регистра 17 унитарный код операции α₁•β₁ mod m₁ поступает на вход преобразователя 18 унитарного кода числа по первому внутреннему модулю устройства в двоичный позиционный код, с выхода которого результат преобразования в двоичном коде поступает на первый вход сумматора 15 по модулю.At the first clock cycle, a signal is supplied to the first 19 clock input of the device. At the same time, this signal is supplied to the second inputs of the first 4, third 12, and fifth 7 blocks of elements I. Operand A in binary code is supplied from the first 1 information input of the device to the input of the first converter 2 of the binary code into a unitary code by the first internal module of the device, from the output of which A mod m ₁ in the unitary code is fed to the first input of the α _1-st category of the first 4 block of elements AND and then to the corresponding information input of the table 6 calculator. Operand B in binary code is supplied from the second 9 information input of the device to the input of the second converter 10 of the binary code of the number into a unitary code by the first internal module of the device, from the output of which B mod m ₁ in the unitary code goes to the first input β of the _1st discharge of the third 12 block of elements And on to the corresponding control input of the table 6 calculator. The result of the operation α ₁ • β ₁ mod m ₁ comes from the t _1- th output of the tabular 6 calculator to the first input of the corresponding discharge of the fifth 7 block of elements AND, from the output of which the result of modular multiplication by the first internal module of the device is fixed by writing the unit in t _1- th a discharge register 17. The output of unitary register 17 opcode ₁ α • β ₁ mod m ₁ is input to the inverter 18 unitary code number of the first indoor unit devices into a binary position code which is output from the conversion result in the binary code Postup It is the first input of the adder 15 to the module.

На втором такте работы сигнал поступает на второй 20 тактовый вход устройства и процесс определения результата операции умножения по второму m₂ внутреннему модулю устройства α₂•β₂ mod m₂, с точностью до соответствующих элементов, происходит аналогичным образом. Отличие заключается в том, что с выхода шестого 8 блока элементов И единичный код результата операции модульного умножения по второму внутреннему модулю устройства поступает на вход преобразователя 14 унитарного кода числа по второму внутреннему модулю устройства в двоичный позиционный код, с выхода которого результат преобразования в двоичном коде поступает на второй вход сумматора 15 по модулю. С выхода сумматора 15 по модулю результат операции A•B mod m поступает на выход 16 устройства.At the second clock cycle, the signal enters the second 20 clock input of the device and the process of determining the result of the multiplication operation by the second m ₂ internal module of the device α ₂ • β ₂ mod m ₂ , up to the corresponding elements, occurs in a similar way. The difference is that from the output of the sixth 8 block of elements AND, the unit code of the result of the operation of modular multiplication by the second internal module of the device is fed to the input of the converter 14 of the unitary code of the number by the second internal module of the device into a binary positional code, from the output of which the result of conversion in binary code arrives at the second input of the adder 15 modulo. From the output of the adder 15 modulo the result of the operation A • B mod m goes to the output 16 of the device.

Рассмотрим пример выполнения операции A•B mod m при m = 12, A=5, B=7, m₁ = 4, m₂ = 3. В этом случае операнд A= 0101₂ и B = 0111₂ поступают соответственно на первый 1 и второй 10 информационные входы устройства. По первому такту работы с выходов первого 2 и второго 10 преобразователей двоичного кода в унитарный код по первому внутреннему модулю поступают сигналы на первый информационный и третий управляющий входы табличного 6 вычислителя через соответствующие разряды первого 4 и третьего 12 блоков элементов И (см. табл. 3). С выходов табличного 6 вычислителя сигнал поступает через пятый 7 блок элементов И на запись единицы в третий разряд регистра 17 (см. табл. 1). Единичный код результата операции умножения по первому внутреннему модулю поступает с выхода регистра 17 на вход преобразователя 18 унитарного кода числа по первому внутреннему модулю устройства в двоичный позиционный код. Результат преобразования 0011₂ (см. табл. 5) поступает далее на первый вход сумматора 15 по модулю.Consider an example of the operation A • B mod m with m = 12, A = 5, B = 7, m ₁ = 4, m ₂ = 3. In this case, the operand A = 0101 ₂ and B = 0111 ₂ are respectively sent to the first 1 and the second 10 information inputs of the device. According to the first clock cycle, from the outputs of the first 2 and second 10 binary code converters into a unitary code, the first internal module receives signals to the first information and third control inputs of the table 6 calculator through the corresponding bits of the first 4 and third 12 blocks of AND elements (see table 3 ) From the outputs of table 6 of the calculator, the signal enters through the fifth 7 block of elements And to write units in the third category of register 17 (see table. 1). The unit code of the result of the operation of multiplication by the first internal module is supplied from the output of the register 17 to the input of the converter 18 of the unitary code of the number by the first internal module of the device into a binary positional code. The result of the conversion 0011 ₂ (see table. 5) then goes to the first input of the adder 15 modulo.

При втором такте работы устройства с выходов первого 3 и второго 11 преобразователей двоичного кода числа в унитарный код по второму внутреннему модулю поступают сигналы на второй информационный и первый управляющий входы табличного 6 вычислителя через соответствующие разряды второго 5 и четвертого 13 блоков элементов И (см. табл. 4). С выходов табличного 6 вычислителя сигнал поступает на первый вход второго разряда пятого 8 блока элементов И, с выхода которого унитарный код результата операции умножения по второму внутреннему модулю поступает на вход преобразователя 14 унитарного кода числа по второму внутреннему модулю устройства в двоичный позиционный код. Результат преобразования 1000₂ (см. табл. 6) поступает далее на второй вход сумматора 15 по модулю, с выхода которого результат операции модульного умножения 1011₂ = 11₁₀ поступает на выход 16 устройства. Проверка: 5•7 mod 12 = 11 mod 12.At the second clock cycle of the device, from the outputs of the first 3 and second 11 converters of the binary code of the number to the unitary code, the second internal module receives signals to the second information and first control inputs of the table 6 calculator through the corresponding bits of the second 5 and fourth 13 blocks of AND elements (see table . 4). From the outputs of table 6 of the calculator, the signal is fed to the first input of the second digit of the fifth 8 block of AND elements, from which the unitary code of the result of the multiplication operation by the second internal module is fed to the input of the unitary code converter 14 of the second internal module of the device into a binary positional code. The result of the conversion 1000 ₂ (see table. 6) then goes to the second input of the adder 15 modulo, from the output of which the result of the operation of modular multiplication 1011 ₂ = 11 ₁₀ goes to the output 16 of the device. Check: 5 • 7 mod 12 = 11 mod 12.

Claims

A device for multiplying numbers modulo containing the first and second blocks of AND elements and a register, characterized in that a table computer, first and second converters of the binary code of the number into unitary code, are introduced into the unit according to the first internal module of the device, the first and second converters of the binary code of the number into the unitary code according to the second internal module of the device, from the third to sixth blocks of AND elements, the converter of the unitary code of the number according to the first internal module of the device into a binary positional code, convert l the unitary code of the number in the second internal module of the device into a binary positional code and the adder in the module of the device, the first information input of the device connected to the inputs of the first converters of the binary code of the number into the unitary code, respectively, according to the first and second internal modules of the device, the outputs of which are connected to the first inputs accordingly, the first and second blocks of AND elements, the outputs of which are connected to the corresponding information inputs of a table computer, the outputs of which are connected to corresponding first inputs of the fifth and sixth blocks of AND elements, the second information input of the device is connected to the inputs of the second converters of the binary code of the number into a unitary code, respectively, by the first and second internal modules of the device, the outputs of which are connected to the first inputs of the third and fourth blocks of AND elements, the outputs of which connected to the corresponding control inputs of the table computer, the output of the sixth block of elements AND is connected to the input of the unitary code converter of the number of watts to the other internal module of the device in a binary positional code, the output of which is connected to the second input of the adder modulo the device, the output of which is the output of the device, the output of the fifth block of elements AND is connected to the input of the register, the output of which is connected to the input of the unitary code converter of the number according to the first internal module of the device into a binary positional code, the output of which is connected to the first input of the adder modulo the device, the first clock input of the device is connected to the second inputs of the first, third and fifth blocks of elements And, the second clock input of the device is connected to the second inputs of the second, fourth and sixth blocks of elements I.