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

(51) МПК (2006) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ В СТЕПЕНЬ ПО МОДУЛЮ ПЯТЬ(71) Заявитель Государственное научное учреждение Объединенный институт проблем информатики Национальной академии наук Беларуси(72) Авторы Бибило Петр Николаевич Городецкий Данила Андреевич(73) Патентообладатель Государственное научное учреждение Объединенный институт проблем информатики Национальной академии наук Беларуси(57) Вычислительное устройство для возведения в степень по модулю пять, характеризующееся тем, что содержит три элемента И, три элемента ЗАПРЕТ и два элемента ИЛИ, выход первого из которых соединен с выходом старшего разряда устройства, выход младшего разряда которого соединен с выходом первого элемента ЗАПРЕТ, а выход среднего разряда 12561 1 2009.10.30 которого соединен с выходом первого элемента И, первый вход которого соединен со входом среднего разряда основания степени устройства, с первым прямым входом второго элемента ЗАПРЕТ и первым входом второго элемента И, второй вход которого соединен со входом младшего разряда основания степени устройства и с первым входом запрета третьего элемента ЗАПРЕТ, прямой вход которого соединен со входом младшего разряда показателя степени устройства, со вторым входом первого элемента И, с первым входом третьего элемента И и со входом запрета второго элемента ЗАПРЕТ, второй прямой вход которого соединен со входом среднего разряда показателя степени устройства, со вторым входом запрета третьего элемента ЗАПРЕТ и с третьим входом второго элемента И, а вход старшего разряда основания степени устройства соединен со вторым входом третьего элемента И, входы второго элемента ИЛИ с первого по третий соединены соответственно с входами младшего, среднего и старшего разрядов основания степени устройства, а выход соединен с прямым входом первого элемента ЗАПРЕТ, первый и второй входы запрета которого соответственно соединены с выходом второго элемента И и с выходом третьего элемента ЗАПРЕТ, третий вход запрета первого элемента ЗАПРЕТ соединен с выходом второго элемента ЗАПРЕТ и с первым входом первого элемента ИЛИ второй вход которого соединен с выходом третьего элемента И и с четвертым входом запрета первого элемента ЗАПРЕТ. Изобретение относится к области вычислительной техники и автоматики и может быть использовано для построения систем передачи и переработки дискретной информации. Известно устройство для умножения по модулю пять, содержащее восемь элементов И, два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, три мажоритарных элемента с порогом три, элемент ИЛИ, шесть входов и три выхода 1. Недостатком устройства для умножения по модулю пять является большая конструктивная сложность по числу входов логических элементов, большое число внешних выводов и низкие функциональные возможности, так как он не выполняет операцию А( 5). Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для возведения чисел в степень по модулю Р 2, содержащее регистр входа, регистр выхода, дешифратор, группу элементов ИЛИ, шифратор, устройство для умножения чисел по модулю Р, параллельно-последовательный регистр, группа элементов ЗАПРЕТ. Недостатком устройства для возведения чисел в степень по модулю Р является большая конструктивная сложность (по числу входов логических элементов и по числу логических элементов) и низкое быстродействие. Изобретение направлено на решение технической задачи уменьшения конструктивной сложности и увеличения быстродействия устройства для возведения чисел в степень по модулю Р. Вычислительное устройство для возведения в степень по модулю пять характеризуется тем, что содержит три элемента И, три элемента ЗАПРЕТ и два элемента ИЛИ. Выход первого элемента ИЛИ соединен с выходом старшего разряда устройства. Выход младшего разряда устройства соединен с выходом первого элемента ЗАПРЕТ. Выход среднего разряда устройства соединен с выходом первого элемента И. Первый вход первого элемента И соединен с входом среднего разряда основания степени устройства, с первым прямым входом второго элемента ЗАПРЕТ и первым входом второго элемента И. Второй вход второго элемента И соединен с входом младшего разряда основания степени устройства и с первым входом запрета третьего элемента ЗАПРЕТ. Прямой вход третьего элемента ЗАПРЕТ соединен с входом младшего разряда показателя степени устройства, со 2 12561 1 2009.10.30 вторым входом первого элемента И, с первым входом третьего элемента И и со входом запрета второго элемента ЗАПРЕТ. Второй прямой вход второго элемента ЗАПРЕТ соединен с входом среднего разряда показателя степени устройства, со вторым входом третьего элемента ЗАПРЕТ и с третьим входом второго элемента И. Вход старшего разряда основания степени устройства соединен с вторым входом третьего элемента И. Входы второго элемента ИЛИ с первого по третий соединены соответственно с входами младшего, среднего и старшего разрядов основания степени устройства. Выход второго элемента ИЛИ соединен с прямым входом первого элемента ЗАПРЕТ. Первый и второй входы запрета первого элемента ЗАПРЕТ соединены с выходом второго элемента И и с выходом третьего элемента ЗАПРЕТ соответственно. Третий вход запрета первого элемента ЗАПРЕТ соединен с выходом второго элемента ЗАПРЕТ и с первым входом первого элемента ИЛИ. Второй вход первого элемента ИЛИ соединен с выходом третьего элемента И и с четвертым входом запрета первого элемента ЗАПРЕТ. Основной технический результат изобретения заключается в уменьшении конструктивной сложности и повышении быстродействия. Названный эффект достигается путем введения новых логических элементов в схему устройства для возведения чисел в степень по модулю Р. На чертеже (фиг. 1) представлена схема вычислительного устройства для возведения в степень по модулю пять. Вычислительное устройство для возведения в степень по модулю пять содержит три элемента И 1, 2 и 3, три элемента ЗАПРЕТ 4, 5 и 6, два элемента ИЛИ 7 и 8, пять входов 9 13 и три выхода 14, 15 и 16. Основание А и показатель степени В задаются трехразрядными двоичными кодами А(1, ,а 2, 3), В(1, 2, 3), где 1, 1 - первые (младшие) разряды основания и показателя степени а 2, 2 - вторые (средние) разряды основания и показателя степени а 3, 3 - третьи (старшие) разряды основания и показателя степени, т.е. А 12 а 24 а 3 и В 12243. В соответствии с выбранным модулем Р 5 показатель и основание степени могут принимать значения 0 (000), 1 (001), 2 (010), 3 (011) и 4 (100). Результат возведения в степень , задается трехразрядным двоичным кодом(, 2, 3), где 12243. На входы 9 и 11 подаются значения младших разрядов а 1, 1 основания и показателя степени соответственно на входы 10 и 13 - значения средних разрядов а 2, 2 основания и показателя степени соответственно на вход 11 - значение старшего разряда а 3 показателя степени, на выходе 14 реализуется младший разряд 1, на выходе 15 - средний разряд 2, а на выходе 16 - старший разряд 3 результата выполнения операции возведения в степень ,где А( 5). Логическая схема вычислительного устройства для возведения в степень по модулю пять синтезирована по следующим аналитическим представлениям функций 1 2 и 3 1312 1 21121 22(123 ), 22 1, 3312 1 2 . Таблица истинности логических функций 1, 2 и 3 описывает работу вычислительного устройства для возведения в степень по модулю пять (фиг. 2). Отметим, что при реализации операции возведения в степень возникает неопределенность вида 00. Так как в модулярной арифметике 0( ), то 00 рр 0( р. Следовательно, здесь 000( 5). Основными достоинствами вычислительного устройства являются, во-первых, небольшая конструктивная сложность (по числу входов логических элементов), равная 23,во-вторых, высокое быстродействие, которое составляет 2, где- задержка на логический элемент. 1. Патент РБ 3299, МПК 06 7/49, 2000. 2. Заявка на патент 2000101103 А, МПК 06 7/38, 2001 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.