УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МОДУЛЮ ПЯТЬ Российский патент 2002 года по МПК G06F7/52 

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

Известно устройство для умножения чисел по а.с. СССР 1160398, МПК G 06 F 7/49, 1985, содержащее блок формирования частичных произведений, соединенный входами с входами устройства, и матрицу из n х n элементов, а выходами - с входами блока суммирования частичных произведений, содержащего матрицу из n х (n-2) сумматоров, выходы которого соединены с входами сумматора двоичных чисел, выходы которого соединены с входами блока коррекции.

Недостатками устройства являются большая сложность, низкое быстродействие и невозможность умножения чисел по модулю К, отличному от 2ⁿ-1.

Известно матричное устройство умножения по а.с. СССР 259479 МПК G 06 F 7/38, 1969, содержащее матрицу из К х К элементов И, соединенных выходами с входами К элементов ИЛИ, где К - модуль.

В случае К= 5 сложность устройства составляет 45 элементов И, ИЛИ, НЕ. Кроме того на его входы необходимо подавать параллельный унитарный позиционный код, а выходной сигнал вырабатывается в этом же коде. Это требует при работе в натуральном двоичном коде установки на входах устройства двух дешифраторов, а на выходе шифратора из элементов ИЛИ. В результате суммарная сложность устройства составит 56 элементов И, ИЛИ, НЕ.

Таким образом, недостатком устройства является его сложность.

Наиболее близким по технической сущности и функциональным возможностям к заявляемому является устройство для умножения по модулю пять по а.с. СССР 1644131 МПК G 06 F 7/49, 1991, содержащее тринадцать элементов И, восемь элементов ИЛИ и три элемента ЗАПРЕТ, причем вход первого разряда первого сомножителя устройства соединен с первыми входами первого, второго, третьего и четвертого элементов И и первым входом первого элемента ИЛИ, второй вход которого соединен с вторым входом четвертого элемента И, первыми входами пятого, шестого и седьмого элементов И и входом первого разряда второго сомножителя устройства, вход второго разряда которого соединен с вторыми входами третьего и шестого элементов И и первыми входами восьмого и девятого элементов И, вход второго разряда первого сомножителя устройства соединен с вторыми входами второго, седьмого и восьмого элементов И и первым входом десятого элемента И, второй вход которого соединен с вторым входом первого элемента И, первым входом одиннадцатого элемента И и входом третьего разряда второго сомножителя устройства, вход третьего разряда первого сомножителя которого соединен с вторыми входами пятого, девятого и одиннадцатого элементов И, выходы первого, восьмого и пятого элементов И соединены с первым, вторым и третьим входами второго элемента ИЛИ, выход которого соединен с прямым входом первого элемента ЗАПРЕТ, выход которого соединен с первым входом третьего элемента ИЛИ, выход которого соединен с выходом третьего разряда результата устройства, а второй вход - с первым входом четвертого элемента ИЛИ и выходом двенадцатого элемента И, первый вход которого соединен с выходом шестого элемента И и первым входом пятого элемента ИЛИ, второй вход которого соединен с выходом второго элемента И и вторым входом двенадцатого элемента И, а выход - с инверсным входом первого элемента ЗАПРЕТ, выходы первого и пятого элементов И соединены с вторым и третьим входами четвертого элемента ИЛИ, выход которого соединен с инверсным входом второго элемента ЗАПРЕТ, выход которого соединен с выходом первого разряда результата устройства, а прямой вход - с выходом шестого элемента ИЛИ, первый вход которого соединен с выходом тринадцатого элемента И, первый вход которого соединен с выходом первого элемента ИЛИ, а второй вход - с выходом восьмого элемента И и с инверсным входом третьего элемента ЗАПРЕТ, выход которого соединен с выходом второго разряда результата устройства, а прямой вход - с выходом седьмого элемента ИЛИ, первый и второй входы которого соединены с выходами третьего и седьмого элементов И, а третий вход - с выходом восьмого элемента ИЛИ и вторым входом шестого элемента ИЛИ, третий и четвертый входы которого соединены с выходами четвертого и одиннадцатого элементов И, выходы девятого и десятого элементов И соединены с первым и вторым входами восьмого элемента ИЛИ.

Данное устройство имеет меньшую сложность, чем устройство по а.с. 259479. Однако и его недостатком является сложность, поскольку оно содержит 24 элемента И, ИЛИ и ЗАПРЕТ, в том числе 4 трехвходовых элемента ИЛИ. В пересчете на двухвходовые элементы его сложность составит 28 элементов. Последний из показателей более точно отражает сложность известного устройства, поскольку учитывает сложность используемых в нем логических элементов.

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

Указанная задача решается за счет того, что в устройство для умножения по модулю пять, содержащее восемь элементов И, восемь элементов ИЛИ и элементы ЗАПРЕТ, выход первого элемента И соединен с первым входом первого элемента ИЛИ, выход второго элемента И соединен с первым входом второго элемента ИЛИ, третий элемент ИЛИ соединен первым входом с выходом первого элемента ЗАПРЕТ, а вторым входом - с выходом третьего элемента И, введен сумматор по модулю два, причем первый элемент И соединен первым входом с входом первого разряда первого сомножителя устройства, а вторым входом - с входом второго разряда первого сомножителя, второй элемент ЗАПРЕТ соединен прямым входом с входом первого разряда первого сомножителя устройства, инверсным входом - с входом второго разряда первого сомножителя устройства, а выходом - с первым входом четвертого элемента ИЛИ, второй вход которого соединен с вторым входом первого элемента ИЛИ и входом третьего разряда первого сомножителя устройства, второй элемент И соединен первым входом с входом первого разряда второго сомножителя устройства, а вторым входом - с входом второго разряда второго сомножителя устройства, третий элемент ЗАПРЕТ соединен прямым входом с входом первого разряда второго сомножителя устройства, инверсным входом - с входом второго разряда второго сомножителя устройства, а выходом - с первым входом пятого элемента ИЛИ, второй вход которого соединен со вторым входом второго элемента ИЛИ и входом третьего разряда второго сомножителя устройства, четвертый элемент И соединен входами с выходами четвертого и пятого элементов ИЛИ, а выходом - с прямым входом первого элемента ЗАПРЕТ и первым входом пятого элемента И, шестой элемент И соединен входами с входом второго разряда первого сомножителя и выходом пятого элемента ИЛИ, а выходом - с первым входом шестого элемента ИЛИ, соединенного выходом - с выходом второго разряда устройства, а вторым входом - с выходом седьмого элемента И, входы которого соединены с входом второго разряда второго сомножителя устройства и выходом четвертого элемента ИЛИ, восьмой элемент И соединен входами с входами вторых разрядов первого и второго сомножителей устройства, а выходом - с прямым входом четвертого элемента ЗАПРЕТ, соединенного выходом с первым входом седьмого элемента ИЛИ, второй вход которого соединен с выходом пятого элемента И, а выход - с выходом третьего разряда устройства, сумматор по модулю два соединен входами с выходами первого и второго элементов ИЛИ, а выходом - с вторыми входами третьего и пятого элементов И и инверсными входами первого и четвертого элементов ЗАПРЕТ, восьмой элемент ИЛИ соединен входами с выходом шестого элемента ИЛИ и восьмого элемента И, а выходом - с первым входом третьего элемента И, выход третьего элемента ИЛИ соединен с выходом первого разряда устройства.

Введение сумматора по модулю два и элемента ЗАПРЕТ, а также новых связей между элементами обеспечивает получение устройства умножения по модулю пять, имеющего сложность в пересчете на двухвходовые элементы, равную 21 двухвходовому элементу, что на 12,5% меньше, чем у известного устройства по а.с. СССР 1644131, выбранного в качестве прототипа. В пересчете на двухвходовые элементы предложенное устройство проще известного на 25%, тем самым получен технический результат, а именно упрощение устройства умножения по модулю пять как за счет сокращения числа использованных логических элементов, так и за счет сокращения числа их входов. Кроме того, предложенное устройство имеет более высокую надежность за счет меньшего объема оборудования.

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

Устройство умножения по модулю пять содержит элемент И 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 и третьего разряда 30 устройства.

Вход первого разряда 22 первого сомножителя соединен с первым входом элемента И 1 и прямым входом элемента ЗАПРЕТ 2, вход второго разряда 23 первого сомножителя соединен с вторым входом элемента И 1, инверсным входом элемента ЗАПРЕТ 2 и первыми входами элементов И 10 и 12, вход 24 третьего разряда первого сомножителя соединен с первыми входами элементов ИЛИ 5 и 6, вторые входы которых соединены с выходами элемента И 1 и элемента ЗАПРЕТ 2 соответственно, вход первого разряда 25 второго сомножителя соединен с первым входом элемента И 4 и прямым входом элемента ЗАПРЕТ 3, вход второго разряда 26 второго сомножителя соединен с вторым входом элемента И 4, инверсным входом элемента ЗАПРЕТ 3, первым входом элемента И 11 и вторым входом элемента И 12, вход 27 третьего разряда второго сомножителя соединен с первыми входами элементов ИЛИ 7 и 8, вторые входы которых соединены с выходами элемента ЗАПРЕТ 3 и элемента И 4 соответственно, элемент ИЛИ 6 соединен выходом с первым входом элемента И 9 и вторым входом элемента И 11, элемент ИЛИ 7 соединен выходом с вторыми входами элементов И 9 и 10, сумматор по модулю два 13 соединен входами с выходами элементов ИЛИ 5 и 8, а выходом - с первыми входами элементов И 17 и 18 и инверсными входами элементов ЗАПРЕТ 16 и 19, элемент ИЛИ 14 соединен входами с выходами элементов И 10 и 11, а выходом - с первым входом элемента ИЛИ 15 и выходом 29 второго разряда устройства, элемент ИЛИ 15 соединен вторым входом с выходом элемента И 12, а выходом - с вторым входом элемента И 18, элемент И 9 соединен выходом с прямым входом элемента ЗАПРЕТ 16 и вторым входом элемента И 17, элемент И 12 соединен выходом с прямым входом элемента ЗАПРЕТ 19, элемент ИЛИ 20 соединен входами с выходом элемента ЗАПРЕТ 16 и элемента И 18, а выходом - с выходом 28 первого разряда устройства, элемент ИЛИ 21 соединен входами с выходом элемента И 17 и элемента ЗАПРЕТ 19, а выходом - с выходом третьего разряда устройства 30.

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

Из таблицы видно, что при подаче на входы устройства любых разрешенных комбинаций значений сомножителей устройство формирует на выходах двоичный код числа (X х Y)mod5.

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

Примечание
1. Элементы И с первого по восьмой в формуле изобретения на чертеже и в описании имеют нумерацию 1, 4, 18, 9, 17, 10, 11 и 12 соответственно.

2. Элементы ИЛИ с первого по восьмой в формуле изобретения на чертеже и в описании имеют нумерацию 5, 8, 20, 6, 7, 14, 21 и 15 соответственно.

3. Элементы ЗАПРЕТ с первого по четвертый в формуле изобретения на чертеже и в описании имеют нумерацию 16, 2, 3, 19 соответственно.

Изобретение относится к области вычислительной техники и может быть использовано для построения систем передачи и переработки дискретной информации. Техническим результатом является упрощение устройства умножения по модулю пять за счет уменьшения числа используемых логических элементов и сокращения числа их входов. Для этого устройство содержит элементы И, элементы ИЛИ, сумматор по модулю два, элементы ЗАПРЕТ. 1 ил., 2 табл.

Устройство для умножения по модулю пять, содержащее восемь элементов И, восемь элементов ИЛИ и элементы ЗАПРЕТ, при этом выход первого элемента И соединен с первым входом первого элемента ИЛИ, выход второго элемента И соединен с первым входом второго элемента ИЛИ, третий элемент ИЛИ соединен первым входом с выходом первого элемента ЗАПРЕТ, а вторым входом - с выходом третьего элемента И, отличающееся тем, что в него введен сумматор по модулю два, причем первый элемент И соединен первым входом с входом первого разряда первого сомножителя устройства, а вторым входом - с входом второго разряда первого сомножителя, второй элемент ЗАПРЕТ соединен прямым входом с входом первого разряда первого сомножителя устройства, инверсным входом - с входом второго разряда первого сомножителя устройства, а выходом - с первым входом четвертого элемента ИЛИ, второй вход которого соединен с вторым входом первого элемента ИЛИ и входом третьего разряда первого сомножителя устройства, второй элемент И соединен первым входом с входом первого разряда второго сомножителя устройства, а вторым входом - с входом второго разряда второго сомножителя устройства, третий элемент ЗАПРЕТ соединен прямым входом с входом первого разряда второго сомножителя устройства, инверсным входом - с входом второго разряда второго сомножителя устройства, а выходом - с первым входом пятого элемента ИЛИ, второй вход которого соединен с вторым входом второго элемента ИЛИ и входом третьего разряда второго сомножителя устройства, четвертый элемент И соединен входами с выходами четвертого и пятого элементов ИЛИ, а выходом - с прямым входом первого элемента ЗАПРЕТ и первым входом пятого элемента И, шестой элемент И соединен входами с входом второго разряда первого сомножителя и выходом пятого элемента ИЛИ, а выходом - с первым входом шестого элемента ИЛИ, соединенного выходом с выходом второго разряда устройства, а вторым входом - с выходом седьмого элемента И, вход которого соединен с входом второго разряда второго сомножителя устройства и выходом четвертого элемента ИЛИ, восьмой элемент И соединен входами с входами вторых разрядов первого и второго сомножителей устройства, а выходом - с прямым входом четвертого элемента ЗАПРЕТ, соединенного выходом с первым входом седьмого элемента ИЛИ, второй вход которого соединен с выходом пятого элемента И, а выход - с выходом третьего разряда устройства, сумматор по модулю два соединен входами с выходами первого и второго элементов ИЛИ, а выходом - с вторыми входами третьего и пятого элементов И и инверсными входами первого и четвертого элементов ЗАПРЕТ, восьмой элемент ИЛИ соединен входами с выходом шестого элемента ИЛИ и восьмого элемента И, а выходом - с первым входом третьего элемента И, выход третьего элемента ИЛИ соединен с выходом первого разряда устройства.