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

 

Изобретение относится к вычислительной технике и может быть использовано в устройствах для формирования кодовых последовательностей, построение которых основывается на теории конечных полей. Целью изобретения является повышение быстродействия . Цель достигается тем, что устройство для формирования остатка, содержащее регистры 9 и 10, элементы ИЛИ 4 и 5, вычитатель 13, схему II сравнения и мультиплексор 18, содержит элементы ИЛИ 6, 7 и 8, схему 12 сравнения, элемент 14 задержки, сумматор 15, группу блоков 16 элементов И и блок 17 постоянной памяти со связями. 1 ил.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

„„SU„„1633495

А1 (51) 5 Н 03 H 7/18

ГСЕСВВЗИАЯ

И МТК- 1ЫВЧВ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ HOMHTET

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

К А STOPCHOMY СВИДЕТЕЛЬСТВУ (21) 4698127/24 (22) 31.05.89 (46) 07.О3,91. Бюл, Р 9

{72) И.Б. Горбенко, И,H Сныткин и В.И. Петренко (53) 681.3{088.8) (56) Авторское свидетельство СССР

М 1008729, кл. Н ОЗ M 7/18, 1981.

Авторское свидетельство СССР

9 1396281, кл. Н 03 М 7!18, 1986. (54) УСТРОЙСТВО ДЛ1 ФОР1ШРОБАН1И

ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МО,1YJ70 ОТ

ЧИСЛА (57) Изобретение относится к вычислительной технике и может быт . ис2 пользонано н устройствах для формирования кодовых последовательносте й, построение которых основывается на теории конечных полей. Целью изобретения является повышение быстродействия. Дель достигается тем, что устройство для формирования остатка, содержащее регистры 9 и 10, элементы ИЛИ 4 и 5, вычитатель 13, схему 11 сравнения и мультиплексор 18, содержит элементы 11ЛИ 6, 7 и 8, схему

12 сравнения, элеменз 14 задержки, сумматор 15, группу блоков 16 элементов И и блок 17 постоянной памяти со связями. 1 ил.

3 1633495 4 основание системы счисления, и каждое число А представляется в виде комбинации его степеней с коэффициентами а;, i=0,k, принимающими значения от О до л-1, т.е. в виде

+ ° +а!ш aît

k к (1) 40 где k — разрядность представляемого числа, Для случая двоичной системы счисления выражение (1) принимает вид 45

k (2)

It u где ai, i=0,k при»»мают значения О

It 11 или 1

Известно также, что сравнения мож»о почле»но складывать, т,е, если

А В1 (modP) <,...., А„=Б <(mot1P), то

1 справедливо гыраженис.АкыВ +....4В„(тподР). (3) (2 )» (3), - -ж»о запи—

А +..., Учитывая сать (ак 2 +.... ° +а, 2+а„)гпойР

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

Целью изобретения является повыше- !О ние быстродействия.

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

ll

Устройство содержит вход 1 Начало вычисления" устройства, вход 2 модуля устройства, вход 3 числа устройства, с первого по пятый элементы

ИЛИ 4-8, первый 9 и второй 10 регистры, первую 11 12 схемы срав- 20 нения, вычитатель 13, элемент 14 задержки, сумматор 15, группу блоков 16 элементов И, блок 17 постоянной памяти,мультиплексор 18, выход 19 "Конец вычисления" устройства и выход 2О результата устройства.

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

Известно, что позиционные системы счисления строятся по следующему принципу. Быбирается некоторое число m

=ак 2 (modP)+.....+а, 2(modP)+

+ао (шопР) (4) Так как для двоичной системы счисления коэффициенты а, принимают только два значения »Ч" или "1", то, суммируя заранее вычисленные остатки по модулю Р от чисел 2 для тех для которых коэффициент а =1, получаем остаток по модулю P от числа А.

Для модулей P с которыми предполаУ гается работа устройства, в постоянном запоминающем устройстве (ПЗУ) запоми»аются заранее вычисленные остатки от чисел ?, Устройство работает следующим образом, В исходном состоянии все регистры обнулены. В блоке 17 памяти предварительно записа»ы заранее вычисленные остатки от чисел ? по модулям

P с которыми предполагается работа устройства, !!одуль Р, по которому осуществляется Формирование остатков чисел, задается параллельным двоичным кодом, подаваемым на вход 2 модуля устройства. На вход 3 числа поступает число А в параллельном двоичном коде. После подачи кодов числа и модуля на входы устройства на вход 1 "Начало вычисления" подают импульс, который, проходя через элемент ИПИ 4, поступает на вход разрешения считывания блока 17 памяти, »а вход разрешения записи регистра

10 и на вход элемента 14 задержки.

При этом н регистр 10 через мультиплексор 18 происходит запись числа, а на выходах блока 17 памяти появляются остатки от чисел 2 по модулю Р, Блок 17, k выхо,! дов, каждый из которых состоит из

1 разрядов, необходимых для представле»ия остатков чисел 2 по модулю Р .

В зависимости от того, на первый вход какого из блоков 16 элементов И поступает логическая "1", тот из блоков 16 элементов !1 оказывается открытым и коммутирует на свой выход значения с второго входа. В результате на соответствующие входы сумматора 15 поступают остатки от чисел 2, для тех i для которых коэффициента; =1 в представлении (2) числа, записанного в регистре It). Сумматор 15 осуществляет суммирдвание чисел, поступающих на его входы, и эта сумма в двоичном параллельном коде .оказывается на его

5 !63349 выходе, При этом на первый вход схемы ll сравнения воздействует код модуля, а на второй вход — код вычисленной суммы с выхода сумматора 15. К этому моменту времени на выходе элемента 14

5 задержки появляется импульс, который, поступая на управляющий вход схемы 11 сравнения, разрешает сравнение кодов чисел, воздействующих на ее входы. Если в результате сравнения окажется, что код числа, воздействующий на второй вход схе.ы сравнения, меньше кода модуля, то на выходе

Меньше схемы 11 сравнения появляет-!5 ся импульс, который поступает на второй управляющий вход мультиплексора 18 и через элемент ИЛИ 7 на вход разрешения записи регистра 9. В результате мультиплексор коммутирует на выход 20 свой второй входи в регистр 9 при этом записывается с выхода сумматора

15 код остатка, а на выходе 19 "Конец вычисления устройства появляется импульс, свидетельствующий о том, что 25 формирование остатка закончено и в .регистре 9 записан код остатка. Если же в результате сравнения импульс появится на выходе "Равно" схемы 11 сравнения, это свидетельствует О том, что остаток от числа равен модулю, что означает тождественное равенство нулю числа. При этом импульс с выхода иРавно" схемы ll сравнения,, ройдя через элемент ИЛИ Ч, обнуляет регистр

9 и через элемент ИЛИ 5 поступает на выход "Конец вычисления" 19 устройства. Появление же импульса на выходе Больше" схемы ll сравнения свидетельствует о ТоМ что формирова- 4п ние остатка не закончено. Импульс с выхода "Больше" схемы ll сравнения поступает на управляющий вход схемы 12 сравнения, разрешая сравнение кодов чисел, воздействующих на ее входы. 4

При этом на ее первый вход воздействует код модуля, а на второй вход воздействует код числа с выхода вычитателя 13, численно равного разности кода числа с выхода сумматора 15 и кода модуля. Если в результате работы схемы 12 сравнения импульс появится на ее выходе Равно", то это свидетельствует о том, что код числа тождественно равен нулю по модулю.

При этом этот импульс, проходя через элемент ИЛИ 8, поступает на обнуляющий вход регистра 9 и на второй вход элемента ИЛИ " В результате на вы5 6 ходе !9 устройс-ва появляется импульс

"Конец вычисления", а на выходе 2Ч появляется код нуля. Если импульс появляется на выходе "Меньше" схемы 12 сравнения, то это также свидетельствует о том, что формирование остатка закончено, Этот импульс через элемент ПЛИ 6 поступает на первый управляющий вход мультиплексора 18 и через элемент 1ПИ 7 на вход разрешения записи регистра 9. В результате выход мультиплексора 18 оказывается скоммутированным с его третьим входом и в регистр 9 записывается код числа с выхода вычигателя 13. При этом на выходе 19 появляется импульс "Конец вь,числения", а на выходах 20 — код остатка числа по модулю. Если же импульс появится па выходе "Больше" схемы сравнения, то это свидетельствует о том, что формирование остатка еще не закончено, Этот импульс поступает через элемент 1ПИ 6 íà первый управляющий вход мультиплексора 18, коммутируя его выход с его тре. тьим входом, а также поступает на второй вход элемента ИЛИ 4. При этом работа устройства повторяется. Однако в регистр I О .эепис вается не код числа А К. а код чис . -, с выхода вычитателя 13, воздействующий на информационный вход регистра !О через мультиплексор 18. Процесс формирования остатка по модулю от числа продо..жается до тех пор, пока на выходах сумматора 15 или вычитателя 13 не появится число, меньшее или равное модулю, которое и будет численно равно остатку от числа А < по модулю P

Фор мул а из обретения

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

"Начало вычисления устройства соединен с первым входом первого элемента ИЛ!1 выход втОрОГО элемеHTB ИЛИ соединен с выходом Конец вычисления устройства, выход первого регистра является выходом результата устройства, вход числа устройства соединен

1633495

Составитель А, Клюев

Техред Л.Олийнык Корректор С.йевкун

Редактор Н, Лазаренко

Заказ 622

Тираж 455

Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

1131!35, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательскии ком инат "Патент", г.ужгород, уп. Гагарина,101 с первым информационным входом мультиплексора, выход которого соединен с информационным входом первого регистра первый и второй входы второУ

5 го элемента ИЛИ соединены соответственно с входами разрешения записи и сброса первого регистра, о т л и— ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него вве- О дены с третьего по пятый элементы

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

ИЛИ и с объединенными выходом "Меньше" первой схемы сравнения и первым входом четвертого элемента ИЛИ, вход модуля устройства соединен с. первым информационным входом второй схемы сравнения и адресным входом блока постоянной памяти, выходы группы которого соединены с вторыми входами соответствующих блоков элементов И группы, выход нычитателя соединен с вторым информационным входом второй схемы сравнения и третьим информационным входом мультиплексора, вход разрешения чтения блока постоянной памяти соединен с выходом первого элемента ИЛИ, входом разрешения записи второго регистра и входом элемента задержки, выход "Больше" второй схемы сравнения соединен с первым входом третьего элемента ИЛИ и вторым входом первого элемента ИЛИ, выход иРавно" второй схемы сравнения соединен с первым входом пятого элемента ИЛИ, выход "Меньше" второй схемы сравнения соединен с вторым входом третьего элемента ИЛИ и вторым входом четвертого элемента ИЛИ, выход которого соединен с первым входом второго элемента ИЛИ, второй вход которого соединен с выходом пятого элемента ИПИ, второй вход которого соединен с выходом "Равно" первой схемы сравнения, выход иБольше" которой соединен с входом разрешения второй схемы сравнения, вход разрешения первой схемы сравнения соединен с выходом элемента задержки.