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

 

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

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

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

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

Наиболее близким по технической сущности (прототипом к предлагаемому изобретению) является устройство (патент РФ N 2023289, МКИ G 06 F 7/49, Б.И. N 21, 1994 г.), содержащее четыре счетчика, четыре элемента ИЛИ - НЕ, два элемента запрета, восемь преобразователей кода, четыре блока элементов ИЛИ, два элемента ИЛИ, элемента И и дешифратора. Устройство позволяет проводить операции сложения и вычитания только по модулю m = m₁m₂ (m₁, m₂ - подмодули устройства), что обуславливает его основной недостаток.

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

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

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

Технический результат достигается тем, что в устройство, содержащее два блока определения кода остатка по первому подмодулю, два блока определения кода остатка по второму подмодулю, шесть блоков элементов И, три блока элементов ИЛИ и первый шифратор, причем информационные входы разрядов первого операнда соединены с отсутствующими входами соответственно первого блока определения кода остатка по второму модулю, информационные входы разрядов второго операнда соединены с соответствующими входами соответственно второго блока определения кода остатка по первому подмодулю и второго блока определения кода остатка по второму подмодулю, выходы которого соединены с соответствующими первыми входами разрядов четвертого блока элементов И, выход которого соединен с первым входом второго блока элементов ИЛИ, а вторые входы разрядов - с входом задания вычитания устройства и с вторыми входами разрядов второго блока элементов И, первые входы разрядов которого соединены с соответствующими выходами второго блока определения кода остатка по первому подмодулю, а выход - с первым входом первого блока элементов ИЛИ, введены три табличных вычислителя, два сумматора по модулю два, элемент НЕ, два элемента И, элемент ИЛИ и второй шифратор, причем i₁-е выходы второго блока определения кода остатка по первому подмодулю соединены с первыми входами j₁-ых разрядов первого блока элементов И j₁ = (m - i₁) mod m₁; m - модуль устройства, m₁ - первый подмодуль устройства, i₂-e - выходы второго блока определения кода остатка по второму подмодулю соединены с первыми входами j₂-ых разрядов первого блока элементов И j₂ = (m-i₂) mod m₂; m₂ - второй подмодуль устройства), вход задания сложения устройства соединен со вторыми входами разрядов первого и третьего блоков элементов И, выходы которых соединены со вторыми входами соответственно первого и второго блоков элементов ИЛИ, выходы которых соединены с соответствующими управляющими входами соответственно первого и второго табличных вычислителей, информационные входы которых соединены с соответствующими выходами соответственно первого блока определения кода остатка по первому подмодулю и первого блока определения кода остатка по второму подмодулю, выходы первого табличного вычислителя, управляющие входы которого соединены с соответствующими выходами второго табличного вычислителя, а выходы - со входами первого и второго шифраторов, выходы которых соединены с соответствующими первыми входами разрядов соответственно пятого и шестого блоков элементов И, информационный вход нулевого разряда первого операнда соединен с первым входом первого сумматора по модулю два, информационный вход нулевого разряда второго операнда соединен с первым входом второго элемента И и входом элемента HЕ, выходы которых соединены соответственно с первым входом элемента ИЛИ и первым входом первого элемента И, выход которого соединен со вторым входом элемента ИЛИ, вторые входы первого и второго элементов И соединены с входами задания соответственно вычитания и сложения устройства, выход элемента ИЛИ соединен со вторым входом первого сумматора по модулю два, прямой выход которого соединен с первым входом второго сумматора по модулю два, второй вход которого соединен с выходом нулевого разряда первого шифратора, а прямой и инверсный выходы - со вторыми входами разрядов соответственно шестого и пятого входа элементов И, выходы которых соединены соответственно со вторым и первым входами третьего блока элементов ИЛИ, выход которого является выходом устройства.

Сущность изобретения состоит в сравнении показателей четности входных операндов с последующим анализом показателя четности результата аддитивной модульной операции. Наиболее просто реализуются модульные арифметические устройства, если m₁m₂. ..m_n=m (m-модуль верхней ступени системы остаточных классов, m₁ - подмодули нижней ступени Однако при многоступенчатом построении подобных узлов актуальным является вопрос о том, что при переходе к первой ступени необходимо обеспечить условие m₁m₂...m_n < m. Одним из способов реализации данного условия является применение немодульной операции - расширения системы оснований. Однако в этом случае с полученным результатом нижней ступени необходимо провести довольно громоздкую (как в алгоритмическом, так и в аппаратном варианте) операцию, сравнимую с переводом числа из системы остаточных классов (СОК) в позиционную систему счисления. Рассмотрим реализацию основных узлов предлагаемого устройства, позволяющего получить непосредственно результат модульной операции при m=13, m₁=3, m₂=5. В этом случае блоки, 2, 5 определения кода остатка по первому подмодулю m₁ и блоки 3, 6 определения кода остатка по второму подмодулю m₂ реализуют операции, отображенные на табл. 1 и 2 соответственно (для операндов A и B).

Табл. 3 и 4 отображают функции, выполненные соответственно первым и вторым 16 табличными вычислителями.

Табл. 5 отображает работу третьего 17 табличного вычислителя. где: X₁ = (A+B)mod m₁, X₂=(A+B)mod m₂. В верхней части клетки таблицы отражен результат модульной операции на выходе первого 18 шифратора, в нижней - второго 19 шифратора.

Основным условием правильного функционирования устройства является (2, m) = 1, т. е. модуль m должен быть нечетным, что обычно выполняется, т.к. единственным четным простым числом является число два. В случае четного модуля устройства необходимо обеспечить, чтобы (m₀, m) = 1. При этом m₀-2 и анализ входных операндов и результата операции несколько усложнится при сохранении применяемого подхода, который в определенном смысле осуществляет контроль переполнения путем расширения в два раза рабочего диапазона устройства, что вполне достаточно, т.к. (A+B)mod m ≅ 2_m - 2.

Операция модульного вычитания сводится к модульному сложению путем использования соотношения (A - B) mod m = [A + (m-B) mod m, (1) и в данном случае выглядит как [(a₁, a₂) - (b₁,b₂)]modm = {(a₁,a₂) + [(m-b₁)modm₁, (m-b₂)modm₂]}modm, (2) где a₁(b₁) = A(B)mod m₁, a₂(b₂) = A(B) mod m₂.

Операции инверсии второго операнда, представленного в виде (b₁,b₂) относительно соответствующих подмодулей m₁ и m₂ реализуется путем соответствующей коммутации унитарных кодов на входах второго 10 и четвертого 7 блоков элементов. Следует отметить, что при использовании соотношения (1) в случае нечетного модуля m устройства показатель четности второго операнда B меняется на противоположный, что реализуется соответствующим схемным узлом устройства.

Алгоритм работы устройства следующий: 1) складываются по модулю два показатели четности операндов A и B; 2) производится сложение по модулю два полученного результата с показателем четности результата модульной операции (значение сложения, равное 0, означает, что переполнение при модульной операции не происходило, значение 1 - в противном случае).

3) в первом случае результат операции (A+B)mod m получаем на выходе первого шифратора 18 (верхние части клеток табл. 5), во втором случае - на выходе второго шифратора 19 (нижние части клеток табл. 5).

В некотором роде в данном случае при анализе переполнения используется контроль вычислений по модулю два.

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

На чертеже представлена структурная схема, где 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 - выход устройства.

Информационные входы 1 разрядов первого операнда соединены с соответствующими входами соответственно первого блока 2 определения кода остатка по первому подмодулю и первого блока 3 определения кода остатка по второму подмодулю, информационные входы 4 разрядов второго операнда соединены с соответствующими входами соответственно второго блока 5 определения кода остатка по первому подмодулю и второго блока 6 определения кода остатка по второму подмодулю, выходы которого соединены с соответствующими первыми входами разрядов четвертого блока 7 элементов И, выход которого соединен с первым входом второго блока 8 элементов ИЛИ, а вторые входы разрядов - с входом 9 задания вычитания устройства и с вторыми входами разрядов второго блока 10 элементов И, первые входы разрядов которого соединены с соответствующими выходами блока 5 определения кода остатка по первому подмодулю, а выход - с первым входом первого блока 11 элементов ИЛИ, i₁-e выходы второго блока 5 определения кода остатка по первому подмодулю соединены с первыми входами j₁-ых разрядов первого блока 12 элементов И j₁ = (m-i₁) mod m₁; m-модуль устройства; m₁ - первый подмодуль устройствах, i₂-e выходы второго блока 6 определения кода остатка по второму подмодулю соединены с первыми входами j₂-ых разрядов третьего блока 13 элементов И j₂= (m-i₂) mod m₂; m₂ - второй подмодуль устройства), вход 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 устройства.

Работу устройства удобно рассматривать в двух режимах: 1) режим определения результата операции модульного сложения;
2) режим определения результата операции модульного вычитания.

В первом режиме работы операнд A поступает в двоичном коде на первый информационный вход 1 устройства и далее на входы первых блоков определения кодов остатков по первому 2 и второму 3 подмодулям. Числа a₁=Amod m₁ и a₂= Amod m₂ в унитарном коде поступают затем на информационные входы соответственно первого 15 и второго 16 табличных вычислителей. Операнд B в двоичном коде поступает на второй 4 информационный вход устройства и далее на входы вторых блоков определения кодов остатков по первому 5 и второму 6 подмодулям. Числа b₁=Bmod m₁ и b₃=Bmod m₂ в унитарном коде поступают затем соответственно через открытые первый 12 и третий 13 блоки элементов (сигнал на входе 14 задания сложения присутствует) на первые входы первого 11 и второго 8 блоков элементов ИЛИ. Далее b₁ и b₂ поступают на управляющие входы соответственно первого 15 и второго 16 табличных вычислителей. С их выходов результаты сложения по подмодулям X₁ = (a₁ + b₁) mod m₁ и X₂ = (a₂ + b₂)mod m₂ mod m₂ в унитарном коде поступают соответственно на информационные и управляющие входы третьего табличного вычислителя 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 устройства.

Работа устройства в режиме модульного вычитания отличается от первого режима тем, что второй операнд B инвертируется по подмодулям согласно соотношению (2), а показатель четности его изменяется на обратный (сигнал на входе 9 присутствует).

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

Пусть A=9, B=8. Необходимо определить результат операции (A+B)mod 13. В этом случае операнд A=10012 поступает на входы первых блоков определения кодов остатков по первому 2 и второму 3 подмодулям. Числа a₁=Amod 3 = 002 и a₂= 1002 поступают в унитарном коде на нулевой и четвертый информационные входы соответственно первого 15 и второго 16 табличных вычислителей. Операнд B=10002 поступает на входы вторых блоков определения кодов остатков по первому 5 и второму 6 подмодулям. Числа b₁=B mod 3=102 и b₂=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.

Пусть A=9, B=10. Необходимо определить результат операции (A-B)mod 13. В этом случае путь прохождения операнда A аналогичен первому примеру. Операнд В= 10102 поступает на входы вторых блоков-определений кодов остатков по первому 5 и второму 6 подмодулям. Числа b₁=Bmod 3=012 и b₂=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.

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

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

РИСУНКИ

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