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

СОЮЗ СОВЕТСНИХССЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 51) 5 Н О 3 И 7/18 ОПИСАНИЕ ИЗОБРЕТЕН А ВТОРСКОМУ С ЛЬСТВ 7 2 91. Б орбен енко 088. кое юл. В 9 ко, И,И тк 8)свидетельствоН 03 М 7/18,идетельство СЧ 03 М 718ЛЛЧ ФОРМ 1 РОБВОЛЬНОМУ Н 0,1 СССР981.ССР986.АН 1 ЯУЛО ОТ в кл в СТВО ПРОИ 12 сра суммат ментов со сня тенне относится к вычи ехнике и может быт: н 2 ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР(57) Изобрелительной т 901633495 польэонано г устройствах для формирования кодовых последовательносте й, построение которых основы вается на теории конечных полей. Целью изобретения является повышение быстродействия. Цель достигается тем, что устройство для формирования остатка, содержащее регистры 9 и 10, элементы ИЛИ 4 и 5, вычитатель 13, схему 11 сравнения и мультиплексор 18, содержит элементы 11 ЛИ 6, 7 и 8, схемувнения, элемен 1 14 задержки,ор 15, группу блоков 16 элеИ и блок 17 постоянной памятизями. 1 ил.основание системы счисления, и каждое число А представляется в видекомбинации его степеней с коэффициентами а;, =Э,11 принимающими значенияот О до л, т,е. в виде 35 а ш а 1 ш а, к + М(1) 40 где 1 с - разрядность представляемогочисла, Для случая двоичной системысчисления выражение (1) принимаетвид 45 к(2)11 П где а =О,1 принимают значения О11 11или 1Известно также, что сравнения можно почленно складывать, т,е, если А =В (шосР)1, 1 А=Б к(шо 11 Р), то1= 1справ тливо гыраженис(а 1, 2 ++а, 2+а)гаооР К Изобретение относится к вычислительной технике и может быть использовано в устройствах для формирования элементов конечных полей, а также в устройствах для формирования кодовых последовательностей, построение которых основывается на теории конечных полей.Целью изобретения является повыше- О ние быстродействия.На чертеже изображена схема устройства для формирования остатка по произвольному модулю от числа.11Устройство содержит вход 1 Начало вычисления" устройства, вход 2 модуля устройства, вход 3 числа устройства, с первого по пятый элементы ИЛИ 4-8, первый 9 и второй 10 регистры, первую 11 и вторую 12 схемы срав нения, вычитатель 13, элемент 14 задержки, сумматор 15, группу блоков 16 элементов И, блок 17 постоянной памяти,мультиплексор 18, выход 19 "Конец вычисления" устройства и выход 2 О результата устройства,Принцип работы устройства для формирования остатка по произвольному модулю от числа заключается в реализации следующего способа приведения по модулям чисел.Известно, что позиционные системы счисления строятся по следующему принципу, Быбирается некоторое число ш(4) Так как для двоичной системы счисления коэффициенты а 1 принимают только два значения "Ч" или "1", то, суммируя заранее вычисленные остаткипо модулю Р от чисел 2 для техдля которых коэффициент а =1, получаем остаток по модулю Р от числа А,Для модулей Р с которыми предполагается работа устройства, в постоянном запоминающем устройстве (ПЗУ) запоминаются заранее вычисленныеостатки от чисел 1,Устройство работает следующим образом,В исходном состоянии все регистрыобнулены, В блоке 17 памяти предварительно записаны заранее вычисленные остатки от чисел 2 по модулямР, с которыми предполагается работаустройства, Нодуль Р, по которомуосуществляется формирование остатков чисел, задается параллельным двоичным кодом, подаваемым на вход 2модуля устройства. На вход 3 числапоступает число А , в параллельномдвоичном коде, После подачи кодовчисла и модуля на входы устройствана вход 1 "Начало вычисления" подаютимпульс, который, проходя через элемент ИПИ 4, поступает на вход раз"решения считывания блока 17 памяти,на вход разрешения записи регистра10 и на вход элемента 14 задержки.При этом н регистр 1 О через мультиплексор 18 происходит запись числа,а на выходах блока 17 памяти появляются остатки от чисел 2 по модулю Р , Блок 17 гамяти имеет 1 выходов, каждый из которых состоит из1 разрядов, необходимых для представления остатков чисел 2 по модулю 1,В зависимости от того, на первый входкакого из блоков 16 элементов И поступает логическая "1", тот из блоков 16 элементов 11 оказывается открытым и коммутирует на свой выход значения с второго входа. В результатена соответствующие входы сумматора 15поступают остатки от чисел 2, длятех ., для которых коэффициент а; =1в представлении (2) числа, записанногов регистре 1 О. Сумматор 15 осуществляет суммирдвание чисел, поступающихна его входы, и эта сумма в двоичномпараллельном коде .оказывается на его5 63349 выходе, При этом на первый вход схемы 11 сравнения воздействует код модуля, а ца второй вход - код вычисленной суммы с выхода сумматора 15. К этому моменту времени на выходе элемента 145 задержки появляется импульс, который, поступая на управляющий вход схемы 11 сравнения, разрешает сравнение кодов чисел, воздействующих на ее входы, Если в результате сравнения окажется, что код числа, воздеиствующий на второй вход схе ы сравнения, меньше кода модуля, то на выходеМеньше сХемы 11 сравнения появляется импульс, который поступает ца второй управляющий вход мультиплексора 18 и через элемент 1 Г 1 И 7 на вход разрешения записи регистра 9. В результате мультиплексор коммутируетна выход 20 свой второй входи в регистр 9 при этом записывается с выхода сумматора 15 код остатка, а на выходе 19 "Конец вычисления устройства появляется импульс, свидетельствующий о том, что 25 формированиеостатка закончено и в .регистре 9 записан код остатка. Если же в результате сравнения импульс появится на выходе "Равно" схемы 11сравнения, это свидетельствует о том, 30 что остаток от числа равен модулю, что означает тождественное равенство нулю числа. При этом импульс с выхода цРавнои схемы 11 сравнения, пройдя через элемент ИЧИ Ч, обнуляет регистр35 9 и через элемент ИЛИ 5 поступает на выход "Конец вычисления" 9 устройства. Появление же импульса на выходе Больше" схемы 1 сравнения свидетельствует о том, что формирова ние остатка не закончено, Импульс с выхода "Больше" схемы 11 сравнения поступает на управляющий вход схемы 12 сравнения, разрешая сравнение кодов чисел, воздействующих на ее входы. 45 При этом на ее первый вход воздействует код модуля, а на второй вход воздействует код числа с выхода вычитателя 13, численно равного разности кода числа с выхода сумматора 15 и кода модуля. Если в результате работы схемы 12 сравнения импульс появится на ее выходе Равно , то это свидетельствует о том, что код числа тождественно равен нулю по модулю. При этом этот импульс, проходя через элемент ИЛИ 8, поступает на обнуляющий вход регистра 9 и на второй вход элемента ИЛИ 5, В результате на вы 5 6ходе 9 устройс-ва появляется импульс "Конец вычисления", а на выходе 2 Ч появляется код нуля, Если импульс появляется на выходе иМеньше" схемы 12сравнения, то это также свидетельствует о том, что Аормирование остатка закончено, Этот импульс через элемент 11 ЛИ 6 поступает ца первый управляющий вход мультиплексора 18 и через элемент ИЛИ 7 на вход разрешения записи регистра Ч. В результате выход мультиплексора 18 оказывается скоммутированным с его третьим входом и в регистр 9 записывается код числа с выхода вычитателя 13. При этом ца выходе 19 появляется импульс "Конец вычисления", а на выходах 20 - код остатка числа по модулю. Если же импульс появится ца выходе "Больше" схемы сравнения, то это свидетельствует о том, что формирование остатка еще це закончно, Этот импульс поступает через элемент 1 И 6 на первый управляющий вход мультиплексора 18, коммутируя его выход с его тре. тьим входом, а также поступает на второй вход элемента ИЛИ 4. При этом работа устройства повторяется, Однако в регистр О зецис вается не код числа А К. а код чис.-, с выхода вычитателя 13, воздействующий на информационный вход регистра О через мультиплексор 18. Процесс формированияостатка по модулю от числа продолжается до тех пор, пока на выходах сумматора 5 или вычитателя 13 не появится число, меньшее или равное модулю, которое и будет численно равно остатку от числа А к по модулю Рформула изобретенияУстройство для формирования остатка по произвольному модулю от числа, содержащее первый и второй регистры, первый и второй элементы ИЛИ, вычитатепь, первую схему сравнения и мультиплексор, причем вход модуля устройства соединен с входом вычцтаемого вычитателя и первым информационнымвходом первой схемы сравнения, вход "НаЧаЛО ВЫЧИСЛЕНИЯи УетРОйетВа СОЕ- дицен с первым входом первого элемента ИЛ 1 выход втОрого элемента ИЛИ соединен с выходом иКонец вычисленияустройства, выход первого регистра является выходом результата устройства, вход числа устройства соединен1633495 Составитель А, КлюевТехред Л.Олийнык Корректор С.йевкун Редактор Н, ЛазаренкоЗаказ 622 Тираж 455 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., д, 4/5Производственно-издательскии колФинат "Патент", г.ужгород, уп. Гагарина,101 с первым информационным входом мультиплексора, выход которого соединен с инФормационным входом первого регистра первый и второй входы второУ5 го элемента ИЛИ соединены соответственно с входами разрешения записи и сброса первого регистра, о т л и - ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены с третьего по пятый элементы ИЛИ, элемент задержки, сумматор, группу блоков элементов И, блок постоянной памяти и вторую схему сравнения, причем выход мультиплексора соединен с информационным входом второго регистра, выходы разрядов которого соединены с первыми входами соответствующих блоков элементов И группы, выходы которых соединены с входами соот-, ветствующих слагаемых сумматора, выход которого соединен с вторым информационным входом первой схемы сравнения, входом уменьшаемого вычитателя и вторым информационным входом муль типлексора, первый и второй управляющие входы которого соединены соответственно с выходом третьего элемента ИЛИ и с объединенными выходом "Меньше" первой схемы сравнения и первым входом четвертого элемента ИЛИ, вход модуля устройства соединен с. первым информационным входом второй схемы сравнения и адресным входом блока постоянной памяти, выходы группы которого соединены с вторыми входами соответствующих блоков элементов И группы, выход нычитателя соединен с вторыминормационным входом второй схемысравнения и третьим информационнымвходом мультиплексора, вход разрешения чтения блока постоянной памяти соединен с выходом первого элемента ИЛИ, входом разрешения записивторого регистра и входом элементазадержки, выход "Больше" второй схемы сравнения соединен с первым входом третьего элемента ИЛИ и вторымвходом первого элемента ИЛИ, выходиРавнон второй схемы сравнения соединен с первым входом пятого элемента ИЛИ, выход "Меньше" второй схемы сравнения соединен с вторым входом третьего элемента ИЛИ и вторымвходом четвертого элемента ИЛИ, выход которого соединен с первым входом второго элемента ИЛИ, второй входкоторого соединен с выходом пятогоэлемента ИПИ, второй вход которогосоединен с выходом "Равно" первой схемы сравнения, выход иБольше" которой соединен с входом разрешения второй схемы сравнения, вход разрешенияпервой схемы сравнения соединен свыходом элемента задержки.