Устройство для формирования остатка по произвольному модулю от числа

)5 ОБРЕТ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) УСТРОИСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА(57) Изобретение относится к вычислительной технике и может быть использовано в устройствах для формирования сигнально- кодовых конструкций в конечных полях. Цель изобретения - расширение функцио 501 б 8 б 702 А нальных возможностеи за счет обеспечения формирования индексов мультипликативных групп полей Галуа ОГ(Р). Устройство содержит блок умножения 1, блоки сравнения 2,3, вычитатель 4, регистры 5,6, счетчик 7, группы 8 и 9 элементов ИЛИ, группу 10 элементов И, элементы ИЛИ 11 - 13, формирователи импульсов 14,15, элемент задержки 16, вход "Начало вычислений" 17, вход модуля 18, входы 19 записи первообразного элемента поля, входы 20 элемента поля, выход "Конец вычислений" 21, выходы индекса 22. Если 0-первообразный элемент поля ОГ(Р), то для любого элемента а С Г(Р) существует единственное целое число гс- СГ (Р) такое, что а = О ", которое и называется индексом элемента а по основанию О. 1 ил,Изобретение относится к вычислительной ение и оже быть сползоао В устройствах для формирования сигнально- кОдОВых кОнструкций в конечных полях.Цель изобретения - расширение функциональных возможностей за счет обеспечения формирования индексов элементов мультипликативных групп полей Галуа СГ(Р).На чертеже приведена схема устройстВа,Устройство содержит блок 1 умножения, блоки 2 и 3 сравнения, вычитатель 4, регистры 5 и 6, счетчик 7, руппы 8 и 9 элементов ИЛИ, группу 10 элементов И, элементы ИЛИ 11-13, формирователи 14 и 15 импульсов, элемент 16 задержки, вход "Начало вычислений" 17, входы 18 разрядов модуля, входы 19 записи первообразного элемента поля, входы 20 элемента поля, выход "Конец вычислений" 21, выходы 22 индекса,Устройство работает следующим обра- ЗОМ.Если О-первообразный элемент поля С Г(Р), то для любого элемента з 6 Г(Р) существует единственное целое число г е СРР) такое, что а =- 0 , которое и называется индексом элемента а по основанию О.В исходном состоянии все регистры обнулены (не показано). Импульс "Начало вычислений" поступает на вход 17 и обнуляет счетчик 7 и осушествляет запись единицы в регистр множимого блока 1 умножения.4 одуль, по которому осуществляется формирование Остатков, задается пзрал" лельным двоичным кодом, подаваемыкг на вход 18, Импульс "Начало Вычислений", пройДЯ через элемеит 16 задержки, через элемент ИЛИ 13 запускает блок 1 умножения. В регистр множителя блока 1 умножения по Входу 19 записывается первообрззный элемен поля, После пер 8- мнОжеиия импульс конца умножения подсчитывается счетчиком 7 и, пройдя через элемент ИЛИ 12, посгупает нз вход рззр- шения сравнения блока 2 сравнения. 1(од произведения проходит через группу 8 элементов ИЛИ на информационный вход блока 2 сраВнения, из Другой информзЦиониый Вход Коороо с хода 18 поступает код модуля, В результате сравнения могут возникнуть следующие ситуации.Произвед 8 ние по сВОему знач 8 нию меньше мОдуля. В этОм случз 8 блок 2 сравнения выдает импульс по выходу "Меньше", который поступает на вход элемента ИЛИ 11 и из ВМОД разреш 8 ния записи регистра 5, Нз информаЦиониый ВХОД регистра 5 в этот момент подается код произведения с выходов группы 8 элементов ИЛИ. В результаекод произведения оазывается записаннымв регистре 5.Если произведение по своему значениючисленно равно модулю, блок 2 сравнениявыдает импульс по выходу "Равно", который обнуляет регистр 5 и через элемент ИЛИ 11поступает на разрешающий вход блока 3сравнения,Если произведение по своему значениюбольше модуля, блок 2 сравнения выдаетимпульс по выходу "Больше", который поступает на вход формирователя 14 импульсов и на вход разрешения вычитателя 4. Навход вычитаемого вычитателя 4 поступает значение модуля с входа 18 устройства, а на вход уменьшаемого - значение произведения через группу 9 элементов ИЛИ, Значение разности с выхода вычитателя 4 под воздействием импульса, сформированного формирователем 14 импульсов, по фронтувходного импульса записывается в регистр 6,По срезу импульса, сформированного формирователем 14 импульсов, формирователь 15 импульсов сформирует импульс, который открывает группу 10 элементов И ипоступает через элемент ИЛИ 12 на входразрешения блока 2 сравнения, Код числа, записанного в регистр 6, через группу 10 элементов И и группу 8 элементов ИЛИ поступает на вход блока 2 сравнения, на другой вход которого поступает с входа 18 код модуля. Под действием импульса с выхода элемента ИЛИ 12 блок 2 сравнивает кодычисел, поступающие на его входы. В результате сравнения вновь могут возникнуть описанные выше три ситуации. Процесс Вычисления остатка по модулю от произведения будет продолжаться до тех пор, покаполученное в результате Вычитания число окажется меньше или равно величине модуля. В результате с выхода регистра 5 остатокот произведения по модулю поступает на ВМОД блока 3 срзвн 8 ниЯ, а импульс кОИЦз формирования остака поступает на разрешающий вход блока 3 сравнения, разрешая сравнение остатка от произведения по модулю и элемента поля, подаваемого на вход20 устройства, Если остаток от проиэведения не равен элементу поля, то с выхода "Не равно" блока 3 сравнения импульс поступает на вход элемента ИЛИ 13 и с его выходана запускающий вход блока 1 умножения.Процесс формирования повторяется сначала, а количество перемножений подсчитыВзется сч 8 тчиком 7.Если остаток от произведения по модулю численно равен элементу поля, то с вы1686702 хода "Равно" блока 3 сравнения поступает импульс, который обнуляет регистр множимого блока 1 умножения, и поступает на выход 21 "Конец вычисления", свидетельствуя о том, что вычисление законно, а на выходах счетчика 7 сформирован индекс от заданного на входах 20 устройства элемента поля по первообраэному элементу, заданному на входах 19 устройства. ходом "Конец вычислений" устройства и соединен с входом разрешения выдачи результата счетчика и входом установки в нулевое состояние блока умножения, выход "Конец умножения" которого соединен с вторым входом второго элемента ИЛИ и счетным входом счетчика, выходы разрядов которого являются выходами индекса устройства. 45 50 Составитель В. ГороховТехред М.Моргентал Корректор О, Кравцова Редактор М. Янкович Заказ 3611 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101 Формула изобретения Устройство для формирования остатка по произвольному модулю от числа, содержащее вычитатель, первый блок сравнения, два регистра, две группы элементов ИЛИ, группу элементов И, первый и втооой элементы ИЛИ и два формирователя импульсов, причем входы разрядов модуля устройства соединены с входами соответствующих разрядов вычитаемого вычитателя и соответствующими информационными входами первой группы первого блока сравнения, выходы "Меньше" и "Равно" которого соединены соответственно с первыми и вторыми входами первого элемента ИЛИ и соответственно с входами разрешения записи и установки в нулевое состояние первого регистра, информационные входы которого объединены с соответствующими входами второй группы первого блока сравнения и подключены к выходам соответствующих элементов ИЛИ первой группы, первые и вторые входы которых попарно объединены с первыми и вторыми входами соответствующих элементов ИЛИ второй группы, выходы которых соединены с входами соответствующих разрядов уменьшаемого вычитателя, выходы разрядов которого соединены с соответствующими информационными входами первого регистра, выходы разрядов которого соединены с первыми входами соответствующих элементов И группы, выходы которых соединены с первыми входами соответствующих элементов ИЛИ первой группы, выход второго элемента ИЛИ соединен с входом разрешения сравнения первого блока сравнения, выход "Меньше" которого соединен с входом разрешения вычитания вычитателя и входом 5 10 15 20 25 30 35 40 первого формирователя импульсов, выход которого соединен с входом разрешения записи второго регистра и входом второго формирователя импульсов, выход которого соединен с вторыми входами всех элементов И групп и с первым входом второго элемента ИЛИ, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возмож остей за счет обеспечения формирования индексов элементов мультипликативных групп полей Галуа ОЕ(Р), в него введены блок умножения, счетчик, второй блок сравнения, третий элемент ИЛИ и элемент задержки, причем вход "Начало вычислений" устройства соединен свходом установки в нулевое состояние счетчика, входом записи единичного значения блока умножения и через элемент задержки - с первым входом третьего элемента ИЛИ, выход которого соединен с входом разрешения умножения блока умножения, выходы разрядов произведения которого соединены с вторыми входами соответствующих элементов ИЛИ первой группы, выходы разрядов первого регистра соединены с соответствующими информационными входами первой группы второго блока сравнения и входами соответствующих разрядов множителя блока умножения, входы разрядов множимого которого являются входами записи первообразного элемента поля устройства, входы разрядов элемента поля усгройства соединены с соответствующими информационными входами второй группы второго блока сравнения, выход "Не равно" которого соединен с вторым входом третьего элемента ИЛИ, выход первого элемента ИЛИ соединен с входом разрешения сравнения второго блока сравнения, выход "Равно" которого является.вы