Устройство для формирования остатка по произвольному модулю от числа Советский патент 1991 года по МПК H03M7/18 

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

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

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

Устройство содержит вход 1 Начало вычисления устройства, вход 2 модуля устройства, вход 3 числа устройства, с первого по пятый элементы ИЛИ 4-8, первый 9 и второй 10 регистВ исходном состоя

ры, первую 1 и вторую 12 схемы срав- 2Q обнулены. В блоке 17

нения, вычитатель 13, элемент 14 задержки, сумматор 15, группу блоков 16 элементов И, блок 17 постоянной памяти, мультиплексор 18, выход 19 Конец вычисления устройства и выход 20 25 результата устройства.

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

Известно, что позиционные системы счисления строятся по следующему принципу. Выбирается некоторое число m основание системы счисления, и каждое число А представляется в виде комбинации его гтепеней с коэффициентами a1, ,k, принимающими значения от 0 до п-1, т.е. в виде

30

35

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

akrn

++a,m+a0,

(О

afc- 2(modP) ++а, 2(modP) +

счистоль-сум+a0(modP).(4)

Так как для двоичной системы ления коэффициенты а| принимают ко два значения О или 1, то, мируя заранее вычисленные остатки по модулю Р от чисел 21 для тех i, 0 для которых коэффициент , получаем остаток по модулю Р от числа А.

с которыми предпола- в постоянном запоминающем устройстве (ПЗУ/ за- 5 поминаются заранее вычисленные остатки от чисел 2.

Устройство работает следующим образом,

В исходном состоянии все регистры

Для модулей Р.

гается работа устройства,

Q обнулены. В блоке 17

памяти предва5

0

5

0

рительно записаны заранее вычисленные остатки от чисел 2 по модулям Р.1, с которыми предполагается работа устройства. Модуль Pj, по которому осуществляется Формирование остатков чисел, задается параллельным двоичным кодом, подаваемым на вход 2 модуля устройства. На вход 3 числа поступает число А в параллельном двоичном коде. После подачи кодов числа и модуля на входы устройства на вход 1 Начало вычисления подают импульс, который, проходя через элемент ИПИ 4, поступает на вход разрешения считывания блока 17 памяти, на вход разрешения записи регистра 10 и на вход элемента 14 задержки. При этом н регистр 10 через мультиплексор 18 происходит запись числа, а на выходах блока 17 памяти появляются остатки от чисел 21 по моду

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

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

Известно также, что сравнения можно почленно складывать, т.е. если А,В (modP),, (modP), то

справедливо рыраженис

А, +AfcsB ,+ . . .. BK(raodP).

Учитывая (2) и (3), можно запи(3)

сать

(ak, 2

, -t-а, 2+aOmodP

45

50

3)

55

лю Р

J.

Г

вход

Блок 17 памяти имеет k выходов, каждый из которых состоит из „ 1 разрядов, необходимых для представления остатков чисел 2 по модулю Р; В зависимости от того, на первый какого из блоков 16 элементов И поступает логическая 1, тот из блоков 16 элементов Н оказывается открытым и коммутирует на свой выход значения с второго входа. В результате на соответствующие входы сумматора 15 поступают остатки от чисел 2 , для тех L, для которых коэффициент в представлении (2) числа, записанного в регистре 10, Сумматор 15 осуществляет суммирование чисел, поступающих на его входы, и эта сумма в двоичном параллельном коде оказывается на его

выходе. При этом на первый вход схемы I1 сравнения воздействует код моду пя, а на второй вход - код вычисленно суммы с выхода сумматора 15. К этому моменту времени на выходе элемента 14 задержки появляется импульс, который, поступая на управляющий вход схемы И сравнения, разрешает сравнение кодов чисел, воздействующих на ее входы. Если в результате сравнения окажется, что код числа, воздействующий на второй вход схечы сравнения, меньше кода модуля, то на выходе Меньше схемы II сравнения появляется импульс, который поступает на второй управляющий вход мультиплексора 1 и через элемент ИЛИ 7 на вход разрешения записи регистра 9. В результате мультиплексор коммутирует на выход свой второй вход и в регистр 9 при этом записывается с выхода сумматора 15 код остатка, а на выходе 19 Конец вычисления устройства появляется импульс, свидетельствующий о том, что Нормирование остатка закончено и в .регистре 9 записан код остатка. Если же в результате сравнения импульс появится на выходе Равно схемы 11 сравнения, это свидетельствует о том, что остаток от числа равен модулю, что означает тождественное равенство нулю числа. При этом импульс с выхода Равно схемы 11 сравнения, пройдя через элемент ИЧИ 8, обнуляет регистр 9 и через элемент ИЛИ 5 поступает на выход Конец вычисления 19 устройства. Появление же импульса на выходе Больше схемы I1 сравнения свидетельствует о том, что формирование остатка не закончено. Импульс с выхода Больше схемы 11 сравнения поступает на управляющий вход схемы 12 сравнения, разрешая сравнение кодов чисел, воздействующих на ее входы. При этом на ее первый вход воздействует код модуля, а на второй вход воздействует код числа с выхода вы- читателя 13, численно равного разности кода числа с выхода сумматора 15 и кода модуля. Если в результате работы схемы 12 сравнения импульс появится на ее выходе Равно, то это свидетельствует о том, что код числа тождественно равен нулю по модулю. При этом этот импульс, проходя через элемент ИЛИ 8, поступает на обнуляющий вход регистра 9 и на второй вход элемента ИЛИ 5. В результате на вы

5

20

25

д

30

35

40

45

50

5

ходе 19 устронс ва появляется импульс Конец вычисления, а на выходе 20 появляется код нуля. Если импульс появляется на выходе Меньше схемы 12 сравнения, то это также свидетельствует о том, что Лормирование остатка закончено. Этот импульс через элемент ИЛИ 6 поступает на первый управляющий вход мультиплексора I8 и через элемент ИЛИ 7 на вход разрешения записи регистра 9. В результате выход мультиплексора 18 оказывается скомму- тированным г его третьим входом и в регистр 9 описывается код числа с выхода вычнтателя 13. При этом на выхода 19 появляется импульс Конец рычисления, а на выходах 20 - код остатка числа по модупю. Если же импульс появится па выходе Больше схемы сравнения, то это свидетельствует о том, что Формирование остатка еще не закончено. Этот импульс поступает через элемент ИЛИ 6 на первый управляющий вход мультиплексора 18, коммутируя его выход с его третьим входом, а также поступает на второй вход элемента ИЛИ 4. При этом работа устройства повторяется. Однако в регистр 10 записывается не код числа Ак, а код MHCJV, с выхода вычи- тателя 13, воздействующий на информационный вход регистра 10 через мультиплексор 18. Процесс формирования остатка по модулю от числа продолжается до тех пор, пока на выходах сумматора I5 или вычитателя 13 не появится число, меньшее или равное модулю, которое и будет численно равно остатку от числа А по модулю Р:.

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

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

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

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

----- --- ---Составитель А. Клюев Техред Л.Олийнык

Заказ 622

Тираж 455

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 111035, Москва, Ж-35, Раушская наб., д. 4/5

Q с 5

0

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

Корректор С.Шевкун

Подписное