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

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

Известно устройство (аналог) (авт. св. СССР №1716511, МКИ G06F 7/72, Б.И. №8, 1992 г.), содержащее группу блоков элементов И, группу блоков умножения на константу по модулю, два блока элементов ИЛИ, дешифратор, группу элементов ИЛИ, элемент ИЛИ, два блока элементов И, элемент НЕ и преобразователь кода. Недостаток устройства - низкие функциональные возможности.

Известно также устройство (аналог) (патент РФ №2143723, МКИ G06F 7/52, 7/72, Б.И. №36, 1999 г.), содержащее два преобразователя двоичного кода числа в унитарный код по первому внутреннему модулю устройства, два преобразователя двоичного кода числа в унитарный код по второму внутреннему модулю устройства, два преобразователя унитарного кода числа в двоичный позиционный код, шесть блоков элементов И, сумматор по модулю устройства. Недостаток устройства - низкие функциональные возможности.

Наиболее близким по технической сущности (прототипом предполагаемого изобретения) является устройство (авт. св. СССР №1667055, МКИ G06F 7/49, 7/72, Б.И. №28, 1991 г.), содержащее пять элементов И, два элемента ИЛИ, дешифратор, две группы элементов ИЛИ, две группы элементов И, коммутатор, регистр, шифратор, два триггера и сумматор по модулю два.

Недостаток прототипа - низкие функциональные возможности ввиду того, что реализуется только коммутативная операция.

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

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

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

На фиг. 1 представлена структурная схема предлагаемого устройства.

На фиг. 2 представлена схема коммутатора (для m=5, где m - модуль операции).

В таблице 1 приведены результаты операции .

В таблице 2 приведены результаты операции , где x - результат операции 0⁰, т.е. неопределенность.

Сущность изобретения состоит в следующем. Наложение унитарных кодов операндов А и В (назовем это представление унитарным кодом бинарной операции) можно однозначно отобразить в результат коммутативной операции, как это сделано в прототипе. Для некоммутативных операций пространственная зависимость результата операции от перестановки ее элементов в предлагаемом устройстве заменяется анализом временного порядка их следования. При этом появляется возможность одновременного проведения двух типов бинарной операции (коммутативной и некоммутативной) с использованием одних и тех же основных узлов устройства. Рассматривая таблицы 1 и 2, можно отметить, что таблица 1 для операции отличается симметрией относительно левой диагонали по сравнению с таблицей 2 для модулярной операции (некоммутативной операции), где А и В - операнды, а m=5 - модуль операции.

Рассмотрим простые примеры. Пусть необходимо провести операцию . Тогда для А=3 и В=2 наложение унитарных кодов имеет вид:

0-1-1-0-0.

Результат соответствующей операции имеет представление:

0-0-0-1-0.

Он не изменится, если А=2 и В=3. Для модульной операции для А=3 и В=2 (А=2 и В=3) наложение унитарных кодов имеет вид:

0-1-1-0-1,

а результат операции в первом случае:

1-0-0-0-0,

а во втором:

0-1-0-0-0.

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

Представленная на фиг. 1 структурная схема предлагаемого устройства содержит: 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 - второй выход устройства.

Представленная на фиг. 2 схема коммутатора 10 (для m=5) содержит: 27_i - выходы разрядов регистра, 28_i - первая группа выходов коммутатора, 29_j - элементы И, 30_j - вторая группа выходов коммутатора.

Входы первого 1 и второго 2 операндов соединены соответственно с первыми входами первого 3 и второго 4 элементов И, вторые входы которых соединены соответственно с первым 5 и вторым 6 управляющими входами устройства, а выходы - соответственно с первым и вторым входами первого 7 элемента ИЛИ, выход которого соединен с входом дешифратора 8, выход которого соединен со входом регистра 9, выходы которого соединены с соответствующими входами коммутатора 10, первая группа выходов которого соединена с первыми входами соответствующих элементов И первой 11 и третьей 12 группы, вторые входы которых соединены с выходом «Равно» цифрового компаратора 13, первый и второй входы которого соединены соответственно с первым 5 и вторым 6 управляющими входами устройства, при этом вторая группа выходов коммутатора 10 соединена с первыми входами соответствующих элементов И второй 14, четвертой 15 и пятой 16 групп, вторые входы которой соединены с выходом «Меньше» цифрового компаратора 13, выход «Больше» которого соединен со вторыми входами элементов И четвертой 15 группы, выходы элементов И первой 11, второй 14, третей 12, четвертой 15 и пятой 16 групп соединены с соответствующими входами первого 17, второго 18, третьего 19, четвертого 20 и пятого 21 шифраторов соответственно, выход «Равно» цифрового компаратора 13 через элемент НЕ 22 соединен с вторыми входами элементов И второй 14 группы, выходы первого 17 и второго 18 шифраторов соединены с первым и вторым входами второго 23 элемента ИЛИ, выход которого является первым 24 выходом устройства, выходы третьего 19, четвертого 20 и пятого 21 шифраторов соединены с первым, вторым и третьим входами третьего 25 элемента ИЛИ соответственно, выход которого является вторым 26 выходом устройства.

Рассмотрим работу устройства. Перед началом работы все разряды регистра 9 установлены в нулевое состояние. По входам 1 и 2 входные операнды в двоичном коде поступают на первые входы соответствующих элементов И 3 и И 4. На первый управляющий вход 5 устройства поступает сигнал, и с выхода элемента И 3 операнд А поступает через первый элемент ИЛИ 7 на вход дешифратора 8, с выхода которого поступает сигнал на один из входов регистра 9. Далее сигнал поступает на второй управляющий вход 6 устройства, и операнд В аналогичным образом проходит с выхода второго 4 элемента И через рассмотренные элементы на один из входов регистра 9. Операнды А и В также поступают на первый и второй входы соответственно цифрового компаратора 13, на одном из трех выходов (А>В, А=В и А<В) появляется сигнал. Выходы 27_i разрядов регистра 9 соединены с соответствующими входами коммутатора 10. В зависимости от соотношения операндов возможны три случая.

При А=В сигнал со второго выхода цифрового компаратора 13 поступает на вторые входы первой 11 и третьей 12 группы элементов И, на один из первых входов которых поступает сигнал с выхода первой группы выходов 28_i коммутатора 10 (эта группа реализует левые диагонали таблиц 1 и 2). Далее через первый 17 и третий 19 шифраторы, а затем второй 23 и третий 25 элементы ИЛИ соответственно результаты операций и поступают в двоичных кодах на первый 24 и второй 26 выходы устройства соответственно.

При А>В сигнал с первого выхода цифрового компаратора 13 поступает на вторые входы четвертой 15 группы элементов И, а через элемент НЕ 22 на вторые входы второй 14 группы элементов И. С выхода второй 30_j группы выходов коммутатора 10 (реализуются недиагональные элементы таблиц 1 и 2) поступает сигнал на один из первых входов второй 14 и четвертой 15 группы элементов И, с выходов которых поступает сигнал на входы второго 18 и четвертого 20 шифраторов. Результаты обоих модульных операций аналогичным образом поступают на выходы 24 и 26 устройства.

При А<В сигнал с третьего выхода цифрового компаратора 13 также через элемент НЕ 22 поступает на вторые входы второй 14 группы (симметрия таблицы 1 для коммутативной операции ) и на вторые входы пятой 16 группы элементов И (реализуется нижняя часть таблицы 2 относительно первой диагонали для некоммутативной операции ). Также с одного выхода второй 30j группы выходов коммутатора 10 поступает сигнал, и последующие процессы проходят подобно первым двум случаям за исключением того, что результат второй операции поступает на второй 26 выход устройства через пятый 21 шифратор.

Пример 1. Пусть А=В=3. При этом на разрядах регистра 9 образуется унитарный код 0-1-0-0-0. Сигнал с выхода 28₃ первой группы 28_i коммутатора 10 поступает на первый вход четвертого элемента И первой 11 группы, на втором входе которого сигнал со второго выхода (А=В) цифрового компаратора 13 присутствует. Далее сигнал поступает на вход первого 17 шифратора, с выхода которого двоичный код 100₂ результата коммутативной операции поступает через второй 23 элемент ИЛИ на первый 24 выход устройства. Также сигнал с выхода 28₃ поступает на первый вход второго элемента третьей 12 группы, а затем через третий 19 шифратор двоичный код 010₂ результата операции через третий 25 элемент ИЛИ на второй 26 выход устройства.

Пример 2. Пусть А=3, В=2. При этом на разрядах регистра 9 образуется унитарный код бинарной операции 0-1-1-0-0. Сигнал с выхода 30₂ второй группы выходов 30_j коммутатора 10 поступает на первый вход первого элемента второй группы 14 элементов И, на втором входе которого присутствует сигнал с выхода элемента НЕ 22. Далее сигнал поступает на вход второго 18 шифратора, с выхода которого результат операции через второй 23 элемент ИЛИ поступает на первый 24 выход устройства. Сигнал с выхода 30₂ второй группы выходов 30_j коммутатора 10 также поступает на первый вход четвертого элемента четвертой группы 15 элементов И, и далее через четвертый 20 шифратор и третий 25 элемент ИЛИ результат операции поступает на второй 26 выход устройства.

Пример 3. Пусть А=2, В=3. Для операции работа устройства происходит подобным образом, как в предыдущем примере, ввиду коммутативности операции. Для второй операции сигнал с выхода 30₂ второй группы выходов 30_j коммутатора 10 поступает на первый вход третьего элемента пятой группы 16 элементов И. На второй его вход поступает сигнал с третьего выхода (А<В) цифрового компаратора 13, и результат операции через соответствующие элементы поступает на второй 26 выход устройства.

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