[go: up one dir, main page]

RU2145112C1 - Device for modulo addition and subtraction of numbers - Google Patents

Device for modulo addition and subtraction of numbers Download PDF

Info

Publication number
RU2145112C1
RU2145112C1 RU98109758A RU98109758A RU2145112C1 RU 2145112 C1 RU2145112 C1 RU 2145112C1 RU 98109758 A RU98109758 A RU 98109758A RU 98109758 A RU98109758 A RU 98109758A RU 2145112 C1 RU2145112 C1 RU 2145112C1
Authority
RU
Russia
Prior art keywords
elements
inputs
input
block
outputs
Prior art date
Application number
RU98109758A
Other languages
Russian (ru)
Inventor
В.П. Ирхин
А.Н. Обухов
С.С. Гульбин
Original Assignee
Воронежский государственный университет
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Воронежский государственный университет filed Critical Воронежский государственный университет
Priority to RU98109758A priority Critical patent/RU2145112C1/en
Application granted granted Critical
Publication of RU2145112C1 publication Critical patent/RU2145112C1/en

Links

Images

Landscapes

  • Error Detection And Correction (AREA)

Abstract

FIELD: automation and computer engineering, in particular, for computers operating in multiple-stage residual classes. SUBSTANCE: goal of invention is achieved by introduced first tabular automaton, second tabular automaton, third tabular automaton, first binary adder, first AND gate, second AND gate, OR gate, NOT gate, second binary adder and second decoder. Device provides comparison of parity of input operands and subsequent analysis of parity of additive modulo operation result. EFFECT: increased functional capabilities due to possibility to implement modulo taking operations for m<m1m2, where m is device modulo, m1 and m2 are two modulo factors of device. 1 dwg, 5 tbl

Description

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

Известно устройство (аналог) (патент РФ N 2018936, МКИ G 06 P 7/72, Б.И. N 16, 1994 г. ), содержащее два дешифратора, четыре группы элементов ИЛИ, четыре элемента ИЛИ, два сумматора по модулю два, пять блоков элементов И, четыре элемента И, три коммутатора, четыре шифратора и блок элементов ИЛИ. Недостаток устройства - низкие функциональные возможности. A device (analog) is known (RF patent N 2018936, MKI G 06 P 7/72, B.I. N 16, 1994), containing two decoders, four groups of OR elements, four OR elements, two adders modulo two, five blocks of AND elements, four AND elements, three switches, four encoders and an OR element block. The disadvantage of this device is its low functionality.

Известно также устройство (аналог) (патент РФ N 2018935, МКИ G 06 F 7/72, БИ N 16, 1994 г.), содержащее дешифратор, два блока элементов И, две группы элементов ИЛИ, пять элементов И, два элемента запрета, два преобразователя кода, два счетчика, два элемента ИЛИ - НЕ, коммутатор, шифратор и два кольцевых регистра сдвига. Недостаток устройства - низкие функциональные возможности. A device (analogue) is also known (RF patent N 2018935, MKI G 06 F 7/72, BI N 16, 1994) containing a decoder, two blocks of AND elements, two groups of OR elements, five AND elements, two prohibition elements, two code converters, two counters, two OR elements - NOT, a switch, an encoder and two ring shift registers. The disadvantage of this device is its low functionality.

Наиболее близким по технической сущности (прототипом к предлагаемому изобретению) является устройство (патент РФ N 2023289, МКИ G 06 F 7/49, Б.И. N 21, 1994 г.), содержащее четыре счетчика, четыре элемента ИЛИ - НЕ, два элемента запрета, восемь преобразователей кода, четыре блока элементов ИЛИ, два элемента ИЛИ, элемента И и дешифратора. Устройство позволяет проводить операции сложения и вычитания только по модулю m = m1m2 (m1, m2 - подмодули устройства), что обуславливает его основной недостаток.The closest in technical essence (the prototype of the present invention) is a device (RF patent N 2023289, MKI G 06 F 7/49, B.I. N 21, 1994), containing four counters, four elements OR - NOT, two a ban element, eight code converters, four blocks of OR elements, two OR elements, an AND element, and a decoder. The device allows addition and subtraction operations only modulo m = m 1 m 2 (m 1 , m 2 are submodules of the device), which causes its main drawback.

Недостаток прототипа заключается в отсутствии возможности проведения операций сложения и вычитания по модулю m < m1m2, что особенно актуально для вычислительных структур, функционирующих в многоступенчатой системе остаточных классов.The disadvantage of the prototype is the lack of the ability to perform addition and subtraction operations modulo m <m 1 m 2 , which is especially true for computing structures that operate in a multi-stage system of residual classes.

Задача, на решение которой направлено изобретение, состоит в расширении области применения арифметических устройств, использующих непозиционные системы счисления. The problem to which the invention is directed, is to expand the scope of arithmetic devices using non-positional number systems.

Технический результат выражается в расширении функциональных возможностей при проведении модульных операций сложения и вычитания за счет увеличения диапазона допустимых модулей. The technical result is expressed in the expansion of functionality during modular operations of addition and subtraction by increasing the range of valid modules.

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

Figure 00000002
j1 = (m - i1) mod m1; m - модуль устройства, m1 - первый подмодуль устройства, i2-e - выходы второго блока определения кода остатка по второму подмодулю соединены с первыми входами j2-ых разрядов первого блока элементов И
Figure 00000003
j2 = (m-i2) mod m2; m2 - второй подмодуль устройства), вход задания сложения устройства соединен со вторыми входами разрядов первого и третьего блоков элементов И, выходы которых соединены со вторыми входами соответственно первого и второго блоков элементов ИЛИ, выходы которых соединены с соответствующими управляющими входами соответственно первого и второго табличных вычислителей, информационные входы которых соединены с соответствующими выходами соответственно первого блока определения кода остатка по первому подмодулю и первого блока определения кода остатка по второму подмодулю, выходы первого табличного вычислителя, управляющие входы которого соединены с соответствующими выходами второго табличного вычислителя, а выходы - со входами первого и второго шифраторов, выходы которых соединены с соответствующими первыми входами разрядов соответственно пятого и шестого блоков элементов И, информационный вход нулевого разряда первого операнда соединен с первым входом первого сумматора по модулю два, информационный вход нулевого разряда второго операнда соединен с первым входом второго элемента И и входом элемента HЕ, выходы которых соединены соответственно с первым входом элемента ИЛИ и первым входом первого элемента И, выход которого соединен со вторым входом элемента ИЛИ, вторые входы первого и второго элементов И соединены с входами задания соответственно вычитания и сложения устройства, выход элемента ИЛИ соединен со вторым входом первого сумматора по модулю два, прямой выход которого соединен с первым входом второго сумматора по модулю два, второй вход которого соединен с выходом нулевого разряда первого шифратора, а прямой и инверсный выходы - со вторыми входами разрядов соответственно шестого и пятого входа элементов И, выходы которых соединены соответственно со вторым и первым входами третьего блока элементов ИЛИ, выход которого является выходом устройства.The technical result is achieved by the fact that in a device containing two blocks for determining the remainder code for the first submodule, two blocks for determining the remainder code for the second submodule, six blocks of AND elements, three blocks of OR elements and the first encoder, and the information inputs of the bits of the first operand are connected to the missing the inputs, respectively, of the first block determining the code of the remainder of the second module, the information inputs of the bits of the second operand are connected to the corresponding inputs, respectively, of the second block of determination the remainder code for the first submodule and the second unit for determining the remainder code for the second submodule, the outputs of which are connected to the corresponding first inputs of the bits of the fourth block of AND elements, the output of which is connected to the first input of the second block of OR elements, and the second inputs of the bits to the input of the device subtraction task and with the second inputs of the bits of the second block of AND elements, the first inputs of the bits of which are connected with the corresponding outputs of the second block determining the remainder code for the first submodule, and the output with the first input OR of the first block elements,
three tabular calculators were introduced, two adders modulo two, an element NOT, two AND elements, an OR element, and a second encoder, and the i first outputs of the second remainder code determination unit for the first submodule are connected to the first inputs j of the 1st bits of the first block of elements AND
Figure 00000002
j 1 = (m - i 1 ) mod m 1 ; m is the device module, m 1 is the first submodule of the device, i 2 -e are the outputs of the second unit for determining the remainder code for the second submodule connected to the first inputs j of the 2nd bits of the first block of AND elements
Figure 00000003
j 2 = (mi 2 ) mod m 2 ; m 2 is the second submodule of the device), the input of the job of adding the device is connected to the second inputs of the bits of the first and third blocks of AND elements, the outputs of which are connected to the second inputs of the first and second blocks of OR elements, the outputs of which are connected to the corresponding control inputs of the first and second tabular calculators, the information inputs of which are connected to the corresponding outputs, respectively, of the first block determining the remainder code for the first submodule and the first block determining yes, the remainder of the second submodule, the outputs of the first tabular calculator, the control inputs of which are connected to the corresponding outputs of the second tabular calculator, and the outputs are connected to the inputs of the first and second encoders, the outputs of which are connected to the corresponding first inputs of the digits of the fifth and sixth blocks of AND elements, respectively, information input the zero discharge of the first operand is connected to the first input of the first adder modulo two, the information input of the zero discharge of the second operand is connected to the first input of the second of the second AND element and the input of the HE element, the outputs of which are connected respectively to the first input of the OR element and the first input of the first AND element, the output of which is connected to the second input of the OR element, the second inputs of the first and second elements AND are connected to the job inputs, respectively, subtracting and adding the device, the output of the OR element is connected to the second input of the first adder modulo two, the direct output of which is connected to the first input of the second adder modulo two, the second input of which is connected to the zero discharge output of the first cipher ator, and direct and inverse outputs with the second inputs of the digits of the sixth and fifth inputs of the AND elements, respectively, the outputs of which are connected respectively with the second and first inputs of the third block of OR elements, the output of which is the output of the device.

Сущность изобретения состоит в сравнении показателей четности входных операндов с последующим анализом показателя четности результата аддитивной модульной операции. Наиболее просто реализуются модульные арифметические устройства, если m1m2. ..mn=m (m-модуль верхней ступени системы остаточных классов, m1 - подмодули нижней ступени

Figure 00000004
Однако при многоступенчатом построении подобных узлов актуальным является вопрос о том, что при переходе к первой ступени необходимо обеспечить условие m1m2...mn < m. Одним из способов реализации данного условия является применение немодульной операции - расширения системы оснований. Однако в этом случае с полученным результатом нижней ступени необходимо провести довольно громоздкую (как в алгоритмическом, так и в аппаратном варианте) операцию, сравнимую с переводом числа из системы остаточных классов (СОК) в позиционную систему счисления. Рассмотрим реализацию основных узлов предлагаемого устройства, позволяющего получить непосредственно результат модульной операции при m=13, m1=3, m2=5. В этом случае блоки, 2, 5 определения кода остатка по первому подмодулю m1 и блоки 3, 6 определения кода остатка по второму подмодулю m2 реализуют операции, отображенные на табл. 1 и 2 соответственно (для операндов A и B).The invention consists in comparing the parity of the input operands with the subsequent analysis of the parity of the result of the additive modular operation. The most simple are modular arithmetic devices if m 1 m 2 . ..m n = m (m-module of the upper stage of the system of residual classes, m 1 - submodules of the lower stage
Figure 00000004
However, in the multi-stage construction of such nodes, the urgent question is that when passing to the first stage, it is necessary to ensure the condition m 1 m 2 ... m n <m. One way to implement this condition is to use a non-modular operation - expanding the base system. However, in this case, with the result of the lower stage, it is necessary to carry out a rather cumbersome (both in the algorithmic and in the hardware version) operation, comparable with the conversion of a number from the system of residual classes (RNS) into a positional number system. Consider the implementation of the main nodes of the proposed device, which allows you to directly obtain the result of a modular operation with m = 13, m 1 = 3, m 2 = 5. In this case, the blocks, 2, 5 for determining the remainder code for the first submodule m 1 and the blocks 3, 6 for determining the remainder code for the second submodule m 2 implement the operations shown in Table. 1 and 2, respectively (for operands A and B).

Табл. 3 и 4 отображают функции, выполненные соответственно первым и вторым 16 табличными вычислителями. Tab. 3 and 4 show the functions performed by the first and second 16 tabular calculators, respectively.

Табл. 5 отображает работу третьего 17 табличного вычислителя. где: X1 = (A+B)mod m1, X2=(A+B)mod m2. В верхней части клетки таблицы отражен результат модульной операции на выходе первого 18 шифратора, в нижней - второго 19 шифратора.Tab. 5 displays the operation of the third 17 tabular calculator. where: X 1 = (A + B) mod m 1 , X 2 = (A + B) mod m 2 . The result of the modular operation at the output of the first 18 encoder is reflected in the upper part of the table cell, and the second 19 encoder in the lower part.

Основным условием правильного функционирования устройства является (2, m) = 1, т. е. модуль m должен быть нечетным, что обычно выполняется, т.к. единственным четным простым числом является число два. В случае четного модуля устройства необходимо обеспечить, чтобы (m0, m) = 1. При этом m0-2 и анализ входных операндов и результата операции несколько усложнится при сохранении применяемого подхода, который в определенном смысле осуществляет контроль переполнения путем расширения в два раза рабочего диапазона устройства, что вполне достаточно, т.к. (A+B)mod m ≤ 2m - 2.The main condition for the correct functioning of the device is (2, m) = 1, i.e., the module m must be odd, which is usually done, because the only even prime number is two. In the case of an even device module, it is necessary to ensure that (m 0 , m) = 1. At the same time, m 0 -2 and the analysis of input operands and the result of the operation will be somewhat more complicated while maintaining the applied approach, which in a sense carries out double overflow control the operating range of the device, which is quite enough, because (A + B) mod m ≤ 2 m - 2.

Операция модульного вычитания сводится к модульному сложению путем использования соотношения
(A - B) mod m = [A + (m-B) mod m, (1)
и в данном случае выглядит как
[(a1, a2) - (b1,b2)]modm = {(a1,a2) + [(m-b1)modm1, (m-b2)modm2]}modm, (2)
где a1(b1) = A(B)mod m1, a2(b2) = A(B) mod m2.The operation of modular subtraction reduces to modular addition by using the relation
(A - B) mod m = [A + (mB) mod m, (1)
and in this case it looks like
[(a 1 , a 2 ) - (b 1 , b 2 )] modm = {(a 1 , a 2 ) + [(mb 1 ) modm 1 , (mb 2 ) modm 2 ]} modm, (2)
where a 1 (b 1 ) = A (B) mod m 1 , a 2 (b 2 ) = A (B) mod m 2 .

Операции инверсии второго операнда, представленного в виде (b1,b2) относительно соответствующих подмодулей m1 и m2 реализуется путем соответствующей коммутации унитарных кодов на входах второго 10 и четвертого 7 блоков элементов. Следует отметить, что при использовании соотношения (1) в случае нечетного модуля m устройства показатель четности второго операнда B меняется на противоположный, что реализуется соответствующим схемным узлом устройства.Inversion operations of the second operand, presented in the form of (b 1 , b 2 ) with respect to the corresponding submodules m 1 and m 2, are realized by the corresponding switching of unitary codes at the inputs of the second 10 and fourth 7 blocks of elements. It should be noted that when using relation (1) in the case of an odd device module m, the parity of the second operand B is reversed, which is implemented by the corresponding circuit node of the device.

Алгоритм работы устройства следующий:
1) складываются по модулю два показатели четности операндов A и B;
2) производится сложение по модулю два полученного результата с показателем четности результата модульной операции (значение сложения, равное 0, означает, что переполнение при модульной операции не происходило, значение 1 - в противном случае).The algorithm of the device is as follows:
1) modulo two parity indices of operands A and B;
2) the modulo-two results are added together with the parity indicator of the result of the modular operation (the addition value of 0 means that the overflow did not occur during the modular operation, the value 1 otherwise).

3) в первом случае результат операции (A+B)mod m получаем на выходе первого шифратора 18 (верхние части клеток табл. 5), во втором случае - на выходе второго шифратора 19 (нижние части клеток табл. 5). 3) in the first case, the result of the operation (A + B) mod m is obtained at the output of the first encoder 18 (upper parts of the cells of Table 5), in the second case - at the output of the second encoder 19 (lower parts of the cells of Table 5).

В некотором роде в данном случае при анализе переполнения используется контроль вычислений по модулю два. In a way, in this case, the analysis of overflow uses the control of computations modulo two.

Возможность достижения положительного эффекта от использования данного изобретения состоит в расширении функциональных возможностей за счет использования различных модулей операционного устройства аддитивных модульных операций, функционирующего в многоступенчатой системе остаточных классов. Предлагаемый алгоритм позволяет использовать его для числа подмодулей, больших, чем два. The ability to achieve a positive effect from the use of this invention is to expand the functionality through the use of various modules of the operating unit of additive modular operations operating in a multi-stage system of residual classes. The proposed algorithm allows you to use it for the number of submodules greater than two.

На чертеже представлена структурная схема,
где 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 - выход устройства.The drawing shows a structural diagram
where 1 are the inputs of the bits of the first operand, 2 is the first block of determining the remainder code of the first submodule, 3 is the first block of determining the code of the remainder of the second submodule, 4 are the inputs of the bits of the second operand, 5 is the second block of determining the code of the balance of the first submodule, 6 - the second block of determining the remainder code for the second submodule, 7 - the fourth block of elements, AND, 8 - the second block of OR elements, 9 - the input of the subtraction task, 10 - the second block of AND elements, 11 - the first block of OR elements, 12 - the first block of AND elements , 13 - the third block of elements And, 14 - input task addition, 15 - the first tabular calculator, 16 - the second tabular calculator, 17 - the third tabular calculator, 18 - the first encoder, 19 - the second encoder, 20 - the fifth block of I elements, 21 - the sixth block of I elements, 22 - the first adder modulo two, 23 - the second element AND, 24 - the element NOT, 25 - the element OR, 26 - the first element AND, the 27-second adder modulo two, 28 - the third block of OR elements, 29 - the output of the device.

Информационные входы 1 разрядов первого операнда соединены с соответствующими входами соответственно первого блока 2 определения кода остатка по первому подмодулю и первого блока 3 определения кода остатка по второму подмодулю, информационные входы 4 разрядов второго операнда соединены с соответствующими входами соответственно второго блока 5 определения кода остатка по первому подмодулю и второго блока 6 определения кода остатка по второму подмодулю, выходы которого соединены с соответствующими первыми входами разрядов четвертого блока 7 элементов И, выход которого соединен с первым входом второго блока 8 элементов ИЛИ, а вторые входы разрядов - с входом 9 задания вычитания устройства и с вторыми входами разрядов второго блока 10 элементов И, первые входы разрядов которого соединены с соответствующими выходами блока 5 определения кода остатка по первому подмодулю, а выход - с первым входом первого блока 11 элементов ИЛИ, i1-e выходы второго блока 5 определения кода остатка по первому подмодулю соединены с первыми входами j1-ых разрядов первого блока 12 элементов И

Figure 00000005
j1 = (m-i1) mod m1; m-модуль устройства; m1 - первый подмодуль устройствах, i2-e выходы второго блока 6 определения кода остатка по второму подмодулю соединены с первыми входами j2-ых разрядов третьего блока 13 элементов И
Figure 00000006
j2= (m-i2) mod m2; m2 - второй подмодуль устройства), вход 14 задания сложения первого 11 и второго 8 блоков элементов ИЛИ, выходы которых соединены с соответствующими управляющими входами соответственно первого 15 и второго 16 табличных вычислителей, информационные входы которых соединены с соответствующими входами соответственно первого блока 2 определения кода остатка по первому подмодулю и первого блока 3 определения кода остатка по второму подмодулю, выходы первого табличного вычислителя 15 соединены с соответствующими информационными входами третьего табличного вычислителя 17, управляющие входы которого соединены с соответствующими выходами второго табличного вычислителя 16, а выходы - с входами первого 18 и второго 19 шифраторов, выходы которых соединены с соответствующими первыми входами разрядов соответственно пятого 20 и шестого 21 блоков элементов И, информационный вход 1 нулевого разряда первого операнда соединен с первым входом первого сумматора 22 по модулю два, информационный вход 4 нулевого разряда второго операнда соединен с первым входом второго элемента И 23 и входом элемента НЕ 24, выходы которых соединены соответственно с первым входом элемента ИЛИ 25 и первым входом первого элемента И 26, выход которого соединен со вторым входом элемента ИЛИ 25, вторые входы первого 26 и второго 23 элементов И соединены с входами задания соответственно вычитания 9 и сложения 14 устройства, выход элемента ИЛИ 25 соединен со вторым входом первого сумматора 22 по модулю два, прямой выход которого соединен с первым входом второго сумматора 27 по модулю два, второй вход которого соединен с выходом нулевого разряда первого шифратора 18, а прямой и инверсный выходы - со вторыми входами разрядов соответственно шестого 21 и пятого 20 блоков элементов И, выходы которых соединены соответственно со вторым и первым входами третьего блока 28 элементов И, выход которого является выходом 29 устройства.The information inputs of 1 bits of the first operand are connected to the corresponding inputs of the first block 2 of determining the remainder code for the first submodule and the first block 3 of determining the remainder code for the second submodule, the information inputs of 4 bits of the second operand are connected to the corresponding inputs of the second block 5 of determining the remainder code for the first the submodule and the second block 6 determine the remainder code for the second submodule, the outputs of which are connected to the corresponding first inputs of the bits of the fourth there are 7 AND elements, the output of which is connected to the first input of the second block of 8 OR elements, and the second bits inputs to the input 9 of the job of subtracting the device and to the second inputs of the bits of the second block of 10 AND elements, the first inputs of which bits are connected to the corresponding outputs of the determination unit 5 the remainder code for the first submodule, and the output with the first input of the first block of 11 OR elements, i the 1st outputs of the second block 5 for determining the remainder code for the first submodule are connected to the first inputs j of the 1st bits of the first block of 12 AND elements
Figure 00000005
j 1 = (mi 1 ) mod m 1 ; m-module of the device; m 1 - the first submodule of devices, i 2 -th outputs of the second block 6 determine the remainder code for the second submodule connected to the first inputs j of the 2nd bits of the third block of 13 elements And
Figure 00000006
j 2 = (mi 2 ) mod m 2 ; m 2 is the second submodule of the device), input 14 of the job of adding the first 11 and second 8 blocks of OR elements, the outputs of which are connected to the corresponding control inputs of the first 15 and second 16 table computers, the information inputs of which are connected to the corresponding inputs of the first block 2 of the code definition the remainder of the first submodule and the first block 3 determine the remainder code of the second submodule, the outputs of the first tabular calculator 15 are connected to the corresponding information inputs of the third a personal computer 17, the control inputs of which are connected to the corresponding outputs of the second tabular computer 16, and the outputs are connected to the inputs of the first 18 and second 19 encoders, the outputs of which are connected to the corresponding first inputs of the digits of the fifth 20 and sixth 21 blocks of AND elements, information input 1 is zero the discharge of the first operand is connected to the first input of the first adder 22 modulo two, the information input 4 of the zero discharge of the second operand is connected to the first input of the second AND element 23 and the input of the element NOT 24, the outputs of which are connected respectively to the first input of the OR element 25 and the first input of the first element AND 26, the output of which is connected to the second input of the OR element 25, the second inputs of the first 26 and second 23 elements AND are connected to the inputs of the job, respectively, subtracting 9 and addition 14 of the device , the output of the OR element 25 is connected to the second input of the first adder 22 modulo two, the direct output of which is connected to the first input of the second adder 27 modulo two, the second input of which is connected to the zero output of the first encoder 18, and the direct inverse outputs - to the second inputs of digits 21, respectively sixth and fifth blocks 20 and the elements, the outputs of which are connected respectively to the second and first inputs of the third unit element 28 and whose output 29 is an output device.

Работу устройства удобно рассматривать в двух режимах:
1) режим определения результата операции модульного сложения;
2) режим определения результата операции модульного вычитания.It is convenient to consider the operation of the device in two modes:
1) the mode of determining the result of the operation of modular addition;
2) a mode for determining the result of a modular subtraction operation.

В первом режиме работы операнд A поступает в двоичном коде на первый информационный вход 1 устройства и далее на входы первых блоков определения кодов остатков по первому 2 и второму 3 подмодулям. Числа a1=Amod m1 и a2= Amod m2 в унитарном коде поступают затем на информационные входы соответственно первого 15 и второго 16 табличных вычислителей. Операнд B в двоичном коде поступает на второй 4 информационный вход устройства и далее на входы вторых блоков определения кодов остатков по первому 5 и второму 6 подмодулям. Числа b1=Bmod m1 и b3=Bmod m2 в унитарном коде поступают затем соответственно через открытые первый 12 и третий 13 блоки элементов (сигнал на входе 14 задания сложения присутствует) на первые входы первого 11 и второго 8 блоков элементов ИЛИ. Далее b1 и b2 поступают на управляющие входы соответственно первого 15 и второго 16 табличных вычислителей. С их выходов результаты сложения по подмодулям X1 = (a1 + b1) mod m1 и X2 = (a2 + b2)mod m2 mod m2 в унитарном коде поступают соответственно на информационные и управляющие входы третьего табличного вычислителя 17, с выходов которого - на входы первого 18 и второго 19 шифраторов. С нулевого разряда первого информационного входа 1 показатель четности операнда A (0 или 1, определяемый младшим разрядом) поступает на первый вход первого сумматора 22 по модулю два, на второй вход которого поступает показатель четности операнда B через открытый второй элемент 23 и элемент ИЛИ 25. Значение показателя четности результата модульной операции сложения поступает на первый вход второго сумматора 27 по модулю два, на второй вход которого с нулевого выхода первого шифратора 18 поступает показатель четности результата операции. Если показатель четности результата операции соответствует сигналу, поступающему с прямого выхода первого сумматора 22 по модулю два, то сигнал с инверсного выхода второго сумматора 27 по модулю два открывает пятый блок 20 элементов И. Результат операции (A+B)mod m с выхода первого шифратора 18 через третий блок 28 элементов ИЛИ поступает на выход 29 устройства. При наличии переполнения при сложении операндов, сигнал поступает с прямого выхода второго сумматора 27 по модулю два и открывает шестой блок 21 элементов И. Результат операции модульного сложения в двоичном коде с выхода второго шифратора 19 через соответствующие элементы поступает на выход 29 устройства.In the first mode of operation, the operand A enters in binary code to the first information input 1 of the device and then to the inputs of the first blocks for determining residual codes from the first 2 and second 3 submodules. The numbers a 1 = Amod m 1 and a 2 = Amod m 2 in the unitary code then go to the information inputs of the first 15 and second 16 table computers, respectively. Operand B in binary code is fed to the second 4 information input of the device and then to the inputs of the second blocks for determining the remainder codes for the first 5 and second 6 submodules. The numbers b 1 = Bmod m 1 and b 3 = Bmod m 2 in the unitary code then arrive respectively through the open first 12 and third 13 blocks of elements (a signal at input 14 of the addition job is present) at the first inputs of the first 11 and second 8 blocks of OR elements. Next, b 1 and b 2 go to the control inputs of the first 15 and second 16 table computers, respectively. From their outputs, the results of addition by submodules X 1 = (a 1 + b 1 ) mod m 1 and X 2 = (a 2 + b 2 ) mod m 2 mod m 2 in the unitary code are respectively sent to the information and control inputs of the third tabular computer 17, from the outputs of which - to the inputs of the first 18 and second 19 encoders. From the zero bit of the first information input 1, the parity indicator of operand A (0 or 1, determined by the least significant bit) is supplied to the first input of the first adder 22 modulo two, the second input of which receives the parity of operand B through the open second element 23 and the OR element 25. The value of the parity indicator of the result of the modular operation of addition is supplied to the first input of the second adder 27 modulo two, the second input of which from the zero output of the first encoder 18 receives the parity of the result of the operation. If the parity result of the operation corresponds to the signal from the direct output of the first adder 22 modulo two, then the signal from the inverse output of the second adder 27 modulo two opens the fifth block of 20 elements I. The result of the operation (A + B) mod m from the output of the first encoder 18 through the third block 28 of the elements OR is supplied to the output 29 of the device. If there is an overflow during the addition of the operands, the signal comes from the direct output of the second adder 27 modulo two and opens the sixth block of 21 elements I. The result of the operation of modular addition in binary code from the output of the second encoder 19 through the corresponding elements goes to the output 29 of the device.

Работа устройства в режиме модульного вычитания отличается от первого режима тем, что второй операнд B инвертируется по подмодулям согласно соотношению (2), а показатель четности его изменяется на обратный (сигнал на входе 9 присутствует). The operation of the device in modular subtraction mode differs from the first mode in that the second operand B is inverted by submodules according to relation (2), and its parity is reversed (a signal at input 9 is present).

Рассмотрим примеры конкретного выполнения модульных операций сложения и вычитания при m=13, m1=3, m2=5.Consider examples of the specific implementation of modular operations of addition and subtraction for m = 13, m 1 = 3, m 2 = 5.

Пусть A=9, B=8. Необходимо определить результат операции (A+B)mod 13. В этом случае операнд A=10012 поступает на входы первых блоков определения кодов остатков по первому 2 и второму 3 подмодулям. Числа a1=Amod 3 = 002 и a2= 1002 поступают в унитарном коде на нулевой и четвертый информационные входы соответственно первого 15 и второго 16 табличных вычислителей. Операнд B=10002 поступает на входы вторых блоков определения кодов остатков по первому 5 и второму 6 подмодулям. Числа b1=B mod 3=102 и b2=0112 поступают в унитарном коде на второй и третий управляющие входы соответственно первого 15 и второго 16 табличных вычислителей через открытые первый 12 и третий 13 блоки элементов И (сигнал на входе 14 присутствует), а также первый 11 и второй 8 блоки элементов ИЛИ. Результаты операций по подмодулям поступают на второй информационный и второй управляющий входы третьего табличного вычислителя 17 (см. табл.3, 4). На первый вход первого сумматора 22 по модулю два поступает сигнал, на второй вход которого сигнал не поступит. С выхода первого сумматора 22 по модулю два сигнал поступит на первый вход второго сумматора 27 по модулю два, на второй вход которого сигнал не поступит (см. табл. 5). Следовательно, с прямого выхода второго сумматора 27 по модулю два сигнал поступит на вторые входы шестого блока 21 элементов И, который обеспечит прохождение результата операции сложения (A+B)mod m=01002 (см. табл. 5) с выходов второго 19 шифратора через третий 28 блок элементов ИЛИ на выход 29 устройства. Проверка: (9+8) mod 13 = 4.Let A = 9, B = 8. It is necessary to determine the result of operation (A + B) mod 13. In this case, the operand A = 10012 arrives at the inputs of the first blocks for determining the remainder codes from the first 2 and second 3 submodules. The numbers a 1 = Amod 3 = 002 and a 2 = 1002 are received in the unitary code at the zero and fourth information inputs of the first 15 and second 16 table computers, respectively. The operand B = 10002 arrives at the inputs of the second blocks of determination of residual codes from the first 5 and second 6 submodules. The numbers b 1 = B mod 3 = 102 and b 2 = 0112 are received in a unitary code at the second and third control inputs of the first 15 and second 16 table computers, respectively, through the open first 12 and third 13 blocks of AND elements (a signal at input 14 is present), as well as the first 11 and second 8 blocks of OR elements. The results of operations by submodules are fed to the second information and second control inputs of the third tabular calculator 17 (see tables 3, 4). The first input of the first adder 22 modulo two receives a signal, the second input of which the signal does not arrive. From the output of the first adder 22 modulo two, the signal will go to the first input of the second adder 27 modulo two, the second input of which the signal will not arrive (see table. 5). Therefore, from the direct output of the second adder 27 modulo two, the signal will go to the second inputs of the sixth block of 21 And elements, which will ensure the passage of the result of the addition operation (A + B) mod m = 01002 (see table 5) from the outputs of the second 19 encoder through the third 28 block of OR elements to the output 29 of the device. Check: (9 + 8) mod 13 = 4.

Пусть A=9, B=10. Необходимо определить результат операции (A-B)mod 13. В этом случае путь прохождения операнда A аналогичен первому примеру. Операнд В= 10102 поступает на входы вторых блоков-определений кодов остатков по первому 5 и второму 6 подмодулям. Числа b1=Bmod 3=012 и b2=Bmod 5=0002 на первые входы разрядов соответственно второго 10 и четвертого 7 блоков элементов И, с выходов которых числа b'2=(m-B)mod 3=002 и b'2=(m-B)mod 5=0112 (см. соотношение (2)) поступают в унитарном коде на нулевой и третий управляющие входы соответственно первого 15 и второго 16 табличных вычислителей через первый 11 и второй 8 блоки элементов ИЛИ. Результаты операций по подмодулям поступают на нулевой информационный и второй управляющие входы третьего табличного вычислителя 17 (см. табл. 3, 4). На первый вход первого сумматора 22 по модулю поступает сигнал. С выхода элемента НЕ 24 через открытый первый элемент И 26 и элемент ИЛИ 25 сигнал поступит на второй вход первого 23 сумматора по модулю два, следовательно, на первом входе третьего сумматора 27 по модулю два сигнала не будет, на второй вход которого сигнал также не поступит (см. табл. 5). Сигнал с инверсного выхода третьего сумматора 27 по модулю два откроет пятый блок 20 элементов И, результат операции модульного вычитания 11002 поступит на выход 29 устройства. Проверка: (9-10)mod 13=12mod 13.Let A = 9, B = 10. It is necessary to determine the result of operation (AB) mod 13. In this case, the path of operand A is similar to the first example. The operand B = 10102 arrives at the inputs of the second blocks-definitions of residual codes for the first 5 and second 6 submodules. The numbers b 1 = Bmod 3 = 012 and b 2 = Bmod 5 = 0002 to the first inputs of the digits of the second 10 and fourth 7 blocks of AND elements, respectively, from the outputs of which the numbers b'2 = (mB) mod 3 = 002 and b'2 = (mB) mod 5 = 0112 (see relation (2)) are received in the unitary code at the zero and third control inputs of the first 15 and second 16 table computers, respectively, through the first 11 and second 8 blocks of OR elements. The results of the operations on the submodules are fed to the zero information and second control inputs of the third tabular computer 17 (see tab. 3, 4). The first input of the first adder 22 modulo receives a signal. From the output of the element NOT 24 through the open first element And 26 and the element OR 25, the signal will go to the second input of the first 23 adder modulo two, therefore, at the first input of the third adder 27 modulo there will be no two signals, the second input of which the signal also will not arrive (see table. 5). The signal from the inverse output of the third adder 27 modulo two will open the fifth block of 20 elements And, the result of the operation of modular subtraction 11002 will go to the output 29 of the device. Check: (9-10) mod 13 = 12mod 13.

Claims (1)

Устройство для сложения и вычитания чисел по модулю, содержащее два блока определения кода остатка по первому подмодулю, два блока определения кода остатка по второму подмодулю, шесть блоков элементов И, три блока элементов ИЛИ и первый шифратор, причем информационные входы разрядов первого операнда соединены с соответствующими входами соответственно первого блока определения кода остатка по первому подмодулю и первого блока определения кода остатка по второму подмодулю, информационные входы разрядов второго операнда соединены с соответствующими входами соответственно второго блока определения кода остатка по первому подмодулю и второго блока определения кода остатка по второму подмодулю, выходы которого соединены с соответствующими первыми входами элементов четвертого блока элементов И, выход которого соединен с первым входом второго блока элементов ИЛИ, а вторые входы элементов четвертого блока элементов И - с входом задания вычитания устройства и с вторыми входами элементов второго блока элементов И, первые входы элементов которого соединены с соответствующими выходами второго блока определения кода остатка по первому подмодулю, а выход - с первым входом первого блока элементов ИЛИ, отличающееся тем, что оно содержит три табличных вычислителя, два сумматора по модулю два, элемент НЕ, два элемента И, элемент ИЛИ и второй шифратор, причем i1-е выходы второго блока определения кода остатка по первому подмодулю соединены с первыми входами j1-ых элементов первого блока элементов И
Figure 00000007
j1 = (m - i1) mod m1; m - модуль устройства; m1 - первый подмодуль устройства; i2-е выходы второго блока определения кода остатка по второму подмодулю соединены с первыми входами j2-ых элементов третьего блока элементов И
Figure 00000008
j2 = (m - i2) mod m2; - m2 - второй подмодуль устройства), вход задания сложения устройства соединен со вторыми входами элементов первого и третьего блоков элементов И, выходы которых соединены со вторыми входами соответственно первого и второго элементов ИЛИ, выходы которых соединены с соответствующими управляющими входами соответственно первого и второго табличных вычислителей, информационные входы которых соединены с соответствующими выходами соответственно первого блока определения кода остатка по первому подмодулю и первого блока определения кода остатка по второму подмодулю, выходы первого табличного вычислителя соединены с соответствующими информационными входами третьего табличного вычислителя, управляющие входы которого соединены с соответствующими выходами второго табличного вычислителя, а выходы - со входами первого и второго шифраторов, выходы которых соединены с соответствующими первыми входами элементов соответственно пятого и шестого блоков элементов И, информационный вход нулевого разряда первого операнда соединен с первым входом первого сумматора по модулю два, информационный вход нулевого разряда второго операнда соединен с первым входом второго элемента И и входом элемента НЕ, выходы которых соединены соответственно с первым входом элемента ИЛИ и первым входом первого элемента И, выход которого соединен со вторым входом элемента ИЛИ, вторые входы первого и второго элементов И соединены с входами задания соответственно вычитания и сложения устройства, выход элемента ИЛИ соединен со вторым входом первого сумматора по модулю два, прямой выход которого соединен с первым входом второго сумматора по модулю два, второй вход которого соединен с выходом нулевого разряда первого шифратора, а прямой и инверсный выходы - со вторыми входами элементов соответственно шестого и пятого элементов И, выходы которых соединены соответственно со вторым и первым входами третьего блока элементов ИЛИ, выход которого является выходом устройства.A device for adding and subtracting numbers modulo containing two blocks for determining the remainder code for the first submodule, two blocks for determining the remainder code for the second submodule, six blocks of AND elements, three blocks of OR elements and the first encoder, and the information inputs of the bits of the first operand are connected to the corresponding the inputs, respectively, of the first unit for determining the remainder code for the first submodule and the first unit for determining the remainder code for the second submodule, the information inputs of the bits of the second operand are connected to the corresponding inputs of the second unit of determining the remainder code by the first submodule and the second unit of determining the code of the remainder by the second submodule, the outputs of which are connected to the corresponding first inputs of the elements of the fourth block of AND elements, the output of which is connected to the first input of the second block of OR elements, and the second inputs of the fourth elements block of elements And - with the input of the task of subtracting the device and with the second inputs of the elements of the second block of elements And, the first inputs of the elements of which are connected to the corresponding the outputs of the second unit for determining the remainder code for the first submodule, and the output with the first input of the first block of OR elements, characterized in that it contains three tabular calculators, two adders modulo two, the element NOT, two AND elements, the OR element, and the second encoder moreover, the i 1st outputs of the second block of determining the remainder code for the first submodule are connected to the first inputs j of the 1st elements of the first block of AND elements
Figure 00000007
j 1 = (m - i 1 ) mod m 1 ; m is the device module; m 1 is the first submodule of the device; i the 2nd outputs of the second unit of determining the remainder code for the second submodule are connected to the first inputs j of the 2nd elements of the third block of AND elements
Figure 00000008
j 2 = (m - i 2 ) mod m 2 ; - m 2 is the second submodule of the device), the input of the job of adding the device is connected to the second inputs of the elements of the first and third blocks of AND elements, the outputs of which are connected to the second inputs of the first and second OR elements, the outputs of which are connected to the corresponding control inputs of the first and second tabular calculators, the information inputs of which are connected to the corresponding outputs, respectively, of the first block of determining the remainder code for the first submodule and the first block of determining the code about a tattoos according to the second submodule, the outputs of the first tabular calculator are connected to the corresponding information inputs of the third tabular calculator, the control inputs of which are connected to the corresponding outputs of the second tabular calculator, and the outputs to the inputs of the first and second encoders, the outputs of which are connected to the corresponding first inputs of the fifth and the sixth block of elements And, the information input of the zero discharge of the first operand is connected to the first input of the first adder modulo two, the zero-information information input of the second operand is connected to the first input of the second AND element and the input of the NOT element, the outputs of which are connected respectively to the first input of the OR element and the first input of the first AND element, the output of which is connected to the second input of the OR element, the second inputs of the first and second elements AND connected to the inputs of the job, respectively, subtracting and adding the device, the output of the OR element is connected to the second input of the first adder modulo two, the direct output of which is connected to the first input of the second adder modulo two, the second input of which is connected to the zero-discharge output of the first encoder, and the direct and inverse outputs are connected to the second inputs of the elements of the sixth and fifth AND elements, respectively, whose outputs are connected respectively to the second and first inputs of the third block of OR elements, the output of which is the output devices.
RU98109758A 1998-05-26 1998-05-26 Device for modulo addition and subtraction of numbers RU2145112C1 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
RU98109758A RU2145112C1 (en) 1998-05-26 1998-05-26 Device for modulo addition and subtraction of numbers

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
RU98109758A RU2145112C1 (en) 1998-05-26 1998-05-26 Device for modulo addition and subtraction of numbers

Publications (1)

Publication Number Publication Date
RU2145112C1 true RU2145112C1 (en) 2000-01-27

Family

ID=20206337

Family Applications (1)

Application Number Title Priority Date Filing Date
RU98109758A RU2145112C1 (en) 1998-05-26 1998-05-26 Device for modulo addition and subtraction of numbers

Country Status (1)

Country Link
RU (1) RU2145112C1 (en)

Similar Documents

Publication Publication Date Title
RU2145112C1 (en) Device for modulo addition and subtraction of numbers
JPH09222991A (en) Adding method and adder
RU2137181C1 (en) Device for modulo multiplication of numbers
RU2157560C1 (en) Modulo calculation unit
RU2018936C1 (en) Modulo multiplying device
RU2110087C1 (en) Modulo adder
RU2338241C1 (en) Device for number module multiplication
RU2143723C1 (en) Device for modulo multiplication of numbers
SU1633400A1 (en) Arithmetic moduli processing device
RU2023289C1 (en) Device for summing and subtracting values in modulo
RU2109326C1 (en) Modulo n adding and subtracting device
RU2829093C1 (en) Arbitrary modulus accumulator
SU1689949A1 (en) The modulo subtracter
RU2020556C1 (en) Device for forming overflow signal
RU1775721C (en) Arithmetic modulo device
SU1755275A1 (en) Device for adding and subtracting modulo two numbers
SU1647563A2 (en) Device for numbers modulo multiplication
RU2018935C1 (en) Device for modulo addition and subtraction
RU2018931C1 (en) Modulo 5 adder
SU1115056A1 (en) Device for checking dividing unit
SU1451690A1 (en) Modulo-m adding and subtracting device
UA130809U (en) DEVICES FOR ADDITION AND SUBMISSION OF SURPLUS ai and bi by the modulo m and the numbers represented in the system of residual classes
RU1820379C (en) Modulo n subtracting and summing device
SU1107122A1 (en) Arithmetic unit operating in residual class system
SU1756881A1 (en) Modulo arithmetic unit