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

 

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах. Целью изобретения является повышение достоверности формирования . Устройство содержит пять эле- , ментов ИЛИ, семь формирователей импульсов , шесть счетчиков, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, блок умножения, элемент И, группу сумматоров по модулю два, блок умножения. Задается код числа Сд и выбранный модуль М. Код числа С в течение времени фор вфования постоянно подается на информациионные входы счетчика. Код модуля задается на группу сумматоров. Устрой- - ство реализует известное вьфазкение aj(- j + Сд(пю4М), где 9, Со - О, К - 1; j 1, М - Т, Блок умножения служит для вычисления символов кодовой последовательности. 2 ил. W ю ро 00 о

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

СОЦИАЛИСТИЧЕСКИХ . PECflVEiJlHH (1% (и) (5р 4 С 06 F 11/08. ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ СССР

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

: (21) 3808735/24-24 (22) 31 ° 10.84 (46) 15.06.86. Бюл. Я . 22 (72) В.И. Петренко и И.И. Сныткин (53) 681.3(088.8) (56) Авторское свидетельство СССР

«з 407313, кл. G 06 F 11/08, 1971.

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

Ф 1105895, кл. С 06 Г 11/08, .1983. (54) УСТРОЙСТВО ДЛЯ ФОРИИРОВМИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОИУ МОДУЛЮ ОТ ЧИСЛА (57) Изобретение относится к вычис.лительной технике и может бить использовано в цифровых вычислительных устройствах. Целью изобретения является повьипение достоверности формирования. Устройство содержит пять эле-, ментов ИЛИ, семь формирователей импульсов, шесть счетчиков, элемент

ИСКЛВЧАИЦЕК ИЛИ, блок умножения, элемент И, группу сумматоров но модулю два, блок умножения. Задается код числа C и. выбранный модуль И. Код . числа С в течение времени формирования постоянно подается на ин4ормаци-. онные входы счетчика. Код модуля задается на группу сумматоров. Устрой ство реализует известное:выражение а (4) j9 + С (шо4И), где 9, Со

О, м - ); j 1, и -Ч, Блок умножения служит для вычисления символов g кодовой последовательности. 2 ил.

Ф 12

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

На фиг. 1. показана блок-схема устройства; на фиг, 2 — то же, блока умножения.

Устройство содержит (фиг. 1) шину

1 задания кода модуля, элемент ИЛИ 2, формирователи импульсов 3 и 4, счетчики 5 и 6, элементы ИЛИ 7 и 8, элемент 9,. ИСКЛЮЧАЮЩЕЕ ИЛИ, элементы

ИЛИ 10 :и 11, счетчик 12, формирователь 13 импульсов, элемент ИЛИ 14„ счетчик 15, блок 16 умножения, счет" чики 17 и 18,.элемент И 19, генератор 20 тактовых импульсов, элемент

ИЛИ 21, формирователи 22-24.импульса, элемент ИЛИ-HE 25, группу 26 сумматоров па модулю два,счетчик 27, шину

28 задания кода числа, вход 29 пуска, выход 30 конца формирования устройства, выходы 31 устройства, элемент

ИЛИ 32.

Блок умножения (фиг. 2) содержит формирователь 33 импульсов, элемент

ИЛИ-HE 34, элемент ИЛИ 35, группу 36 сумматоров по модулю два, формирователь 37 импульса, элемент И 38, счетчики 39 и 40.

В исходном состоянии счетчики 5,6, 12, 15, 17, 18, 27 (фиг. 1) и счетчики

40 и 39 (фиг. 2) обнулены, причем счетчики 5,6,18 40 являются вычитающими, а счетчики 12,15, 17,27 . и 39 —, суммирующими. Генератор 20 тактовых импульсов выдает на свой выход последовательность тактовых импульсов.

Перед началом работы на шине 28 задания кода числа задается код С, который в течение времени формирования воздействует на входы предварительной записи счетчика 17, Также задается код модуля H .на шине 1, который воздействует на входы сумматоров группы 26 и на входы предварительной записи счетчиков 5 и 6.

Устройства реализует выражение а; (9)+j 4 + С (mod М), где Э С = О, И1, j = 1; М вЂ” 1. (1)

Импульс с входа 29 пуска устройства запускает устройство в работу.

Этот импульс, проходя через элемент

ИЛИ 2, воздействует на вход разрешения счетчика 5, в результате чего в, .мп@+;ф-. :, 38077 2 счетчик 5 запишется код модуля М, воздействующий на информационные входы; воздействуя на входы разрешения счетчика 6 и через элемент ИЛИ 32 на вход разрешения счетчика 27, запи-шет в эти счетчики код модуля М и код числа Ср соответственно; воздействуя на первый вход элемента ИЛИ ii и проходя на его выход, поступит на счет10 ный вход счетчика 15.

По срезу импульса пуска, подавае- . мого на вход формирователя 4 импульсов, на выходе последнего сформируется импульс, который проходя на входы

1 элементов ИЛИ 7 и 8 поступит на их выходы, а далее на вычитающие входы счетчиков 5 и 6 соответственно, вычитая из кода модуля И, записанного в этих счетчиках единицу; проходя на

2п первый вход элемента ИЛИ 10, поступит на вход разрешения счетчика,18, предварительно записывая в него код числа. С, записанный в счетчике 17.

Блок 16 умножения в вычислении перво25 ro символа кодовой последовательности не участвует, так как величина элемента см. (1), определяемая состоянием счетчика 12, численно равна нулю.

После того, как в счетчике 18 будет записана кодовая последовательность числа Сп, на выходе элемента

ИЛИ 21 появится единичный потенциал, который будет поддерживаться до тех

35 пор, пока счетчик 18 не обнулится. По фронту этого потенциала формирователь

22 импульсов сформирует импульс, ко горый обнулит счетчик 27.-Этим же . ,единичным потенциалом с выхода элемен га ИЛИ 21 откроется элемент И 19. и тактовые импульсы, воздействующие на другой его вход, поступают на. вычитающий вход счетчика 18 и на суммирующий вход счетчика 27. Последний осуществляет суммирование поступившего на

45 вход количества тактовых импульсов.

Суммиуование осуществляется до тех пор, пока на выходах счетчика 27 не образуется число в двоичном коде, численно равное выбранному модулю М и воздействующее на первые входы группы 26 сумматоров по модулю два, выполняющих операцию равнозначности.

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

26 окажутся нулевые потенциалы, которые воздействуют на входы элеменз 1238077, 4 та ИЛИ-НЕ 25 Н

25. На выходе последнего входами элемента ИЛИ 35, то на выходе об аз ется е чн

Р у единичный потенциал, кото- последнего возникает единичный потенрый через формирователь 24 импульсов циал, который будет поддерживаться обнулит счетчик 27 счетчик 27, а подсчет такто- до тех пор, пока счетчик 40 не окавых импульсов начне у сов начнется заново, т.е. g жется в нулевом состоянии. Единичный на первые входы сумматоров по модулю потенциал с выхода элемента ИЛИ 35 два группы 26 будут воздействовать открывает элемент И 38, на второй в параллельном ко коде двоичные коды чи- вход которого поступают тактовые имсел от 1 о M. В е д . В течение этого време- пульсы. В результате тактовые импульни хотя бы на о н дном из выходбв сумма- 10 сы поступают на счетный вход счетчиторов группы 26 будет единичный по- ка 39 и подсчитываются им. Как тольтенциал. Сле овательно . Сл до ательно, на выходе ко количество тактовых импульсов, элемента ИЛИ-НЕ 25 б

5 будет нулевой по- подсчитанное счетчиком 39, окажется тенциал. Как только ько счетчик 27 сосчи- равным коду числа, воздействующему тает количество тактовых импульсов, 15 на первые входы группы 36 сумматоров равных выбранному модулю М, опять по модулю два (множителю), на выходе произойдет его обнуление. Такая опе- элемента ИЛИ-НЕ 34 образуется едирация будет происходить до тех пор, ничный потенциал, по фронту которого .пока не обнулится счетчик 18. A об- формирователь 33 импульсов сформирунуление после него п д произойдет в том 20 ет импульс, который поступит на вычислучае, когда количество поступивших тающий вход счетчика 40 а также обS на его второй вход тактовых импульсов нулит счетчик 39. Как только на выбудет численно равно числу, записан- читающий вход счетчика 40 поступит ному в счетчике 18. В результате че- количество импульсов, численно равное го на выходе элемента ИЛИ 21 возника-25 коду записанного в нем числа, он обет нулевой потенциал, элемент И 19 нулится, на выходе элемента ИЛИ 35 закроется и тактовые им импульсы пере- образуется нулевой потенциал и такстанут поступать на входы счетчиков товые импульсы не будут проходить на

18 и 27. Поэтом на вых у одах счетчи- выход элемента И 38. Количество так. ка 27 останется остаток числа числа, запи- ЗО товых импульсов, поступившее с выхода санного в счетчике 1 8 попо-модулю М, элемента И 38 на счетный вход счетПо срезу имп льса об у, . Разующегося на, чика 39, а равно и на выход блока, выходе элемента ИЛИ 21 фо ми ова1, формирова- численно будет равно произведению читель 23 импульсов сфо ми у ф рмирует импульс, сел, воздействующих на первые и втокоторый поступит на вхо э д элемента рые входы блока 16 умножения. По среИЛИ. 32 и далее прохо я на вхо р д на вход счет- зу единичного импульса на выходе эле35 чика 17 запишет в посл . следний код Сд, мента ИЛИ 35 формирователь 37 импульна .счетный вход счетчика 12 ика 12 и через сов выдает импульс Конец умножения". !

Г элемент ИЛИ 7 на вычитающий вход счетчика 5, добавляя и вычитая из . Количество импУльсов поступившее

40.

У содержимого этих счетчиков единицу, на выход блока 16 умножения, подсчисоответственно, проходя через эле- тывается.счетчиком 17, в котором мент ИЛИ ИСКЛЮЧАЮЩЕЕ 9, поступит на предварительно записан код числа Со . вход формирователя 13 импульсов, ко" ИмпУльс "Конец УмножениЯ с выхода торый по срезу этого импульса сформи- формирователя 37 импульсов блока 16 рует импульс, поступающий через эле- умножения, проходя через элемент

45 мент ИЛИ 14 на вход разряжения блока ИЛИ 10, поступит на вход Разрешения

16 умножения, включая тем самым пос- счетчика 18, записывая в него код ледний в работу. числа счетчика 17, и далее начинаетВлок 16 умножения работает следу- ся процесс. вычисления остатка по моющим образом (фиг. 2). дулю М от этого числа, который опи-. сывался выше. После того, как будет

Поступивший на его управляю и сформирован следующий символ кодовой вход импульс проходит на и авля у р ляющии последовательности, формирователь 23 вход счетчика 40, записывая в нег го выдаст следующий импульс. На выходах тем самьм код числа множимого. В е- 55 .

В Ре- счетчика 12 под воздействием импульзультате на выходе этого счетчика обтчика об- сов с выходов формирователя 23 будут разуется код этого же числа а так

Э формироваться последовательно коды как выходы счетчика 40 соединены с от 0 M-1 от до -1. После того, как сформи1238077 руется М-1 код, под воздействием следующего импульса с выхода формирователя 23, счетчик 5 обнулится, в результате чего на его выходе переноса появится импульс, который обнулит счетчик 12, запретит прохождение импульса со входа элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 9 на его выход, проходя че,рез элемент ИЛИ 11, сосчитается счет- 10 чиком 15,. а проходя через элемент

ИЛИ 8, вычтется из счетчика 6, поступит на вход формирователя 3 импуль сов.

Формирователь 3 сформирует по сре- 15 зу поступившего íà eFo вход импуль са импульс, который, проходя через элемент ИЛИ 14, поступит на вход разрешения блока 16 умножения, включая его тем самым .в работу, а также, про- 20 ходя на вход элемента ИЛИ 2, поступит на вход разрешения счетчика,, устанавливая его в предварительное состояние, численно равное коду числа

М, воздействующего на входы с шины 1. 25

Этот же импульс, проходя через элемент ИЛИ 7 вычтет из счетчика 5 "1", в результате чего в счетчике 5 окажется записан код числа M-1. .30

При этом счетчик 15 с приходом на его счетный вход очередного импульса будет выцавать-на свои выходы код 1 до М-1, После того, как счетчик 15 установится в M-1 состояние а счет35 чик 6 в нулевое. состояние, то под воздействием следующего, поступающего на соответствующие входы этих счетчиков импульса с выхода переноса счетчика 5 через элементы ИЛИ 8 и 11 на

40 выходе переноса счетчика 6 образуется импульс, который обнуляет счетчики 15 и 1,7, а также является сигналом конца формирования, .свидетельст :вуя о том, что закончился процесс

45 формирования сигналов по выбранному модулю М и коду числа С„.

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

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

ИЛИ и с входом первого формирователя импульсов, выход которого соединен с входом сброса второго счетчика, выход второго формирователя импульсов соединен с входом сброса второго счетчика, вход второго формирователя импульсов соединен с выходом элемента ИЛИ-НЕ, входы которого соединены с выходом сумматоров по модулю два группы, первые входы которых соединены с соответствующими выходами второго счетчика, являющимися выходами устройства, входы первого элемента.

ИЛИ соединены с выходами первого счетчика, о т л и ч а ю щ е е с я тем, что, с целью повышения достоверности формирования, оно содержит второй,третий, четвертый, пятый, шестой, седьмой и восьмой элементы ИЛИ, третий, четвертый, пятый и шестой формирователи импульсов, третий, четвертый, пятый, шестой и седьмой счетчики, элемент HCKJIIO×ÀÞÙÅÅ ИЛИ и блок умножения, причем информационные входы третьего счетчика подключены к шине задания кода модуля, соединены с информационными входами четвертого счетчика и с вторыми входами соответствующих сумматоров по модулю два группы, вход пуска устройства соединен с первыми входами второго, третьего и четвертого элементов ИЛИ, через третий формирователь импульсов— с первыми входами пятого, шестого и седьмого элементов ИЛИ, с входом разрешения четвертого счетчика, информационные входы пятого счетчика подключены к шине задания кода числа, выход первого элемента ИЛИ соединен с входами первого и третьего формирователей импульсов, выход. третьего формирователя импульсов соединен с вторыми входами четвертого и пятого элементов ИЛИ, с первым входом элемента

ИСКЛЮЧАЮЩЕЕ ИЛИ и входом синхронизации шестого счетчика, выход переноса третьего счетчика соединен с вторыми входами третьего, шестого и седьмого элементов ИЛИ, с вторым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и через четвертый формирователь импульса — с вторым входом второго элемента ИЛИ, первым входом восьмого элемента ИЛИ

i238077 и входом сброса шестого счетчика, группа. выходов которого соединена с первой группой информационных входов блока умножения, вторая группа информационных входов которого соединена с группой выходов .седьмого счетчика, счетный вход которого соединен с выходом третьего элемента ИЛИ, выход четвертого элемента ИЛИ соединен с 10 входом разрешения пятого счетчика, выходы которого соединены с информационными входами первого счетчика, вход разрешения которого соединен с выходом седьмого элемента ИЛИ, выход пятого элемента ИЛИ соединен с вычитающим входом третьего счетчика, вход разрешения которого соединен с выходом второго элемента ИЛИ и третьим входом пятого элемента ИЛИ, выход пе- рц реноса четвертого счетчика соединен с входами сброса пятого и седьмого счетчиков и является выходом конца формирования устройства, выход шестого элемента ИЛИ соединен с вычитающим входом четвертого счетчика, выход генератора тактовых импульсов соединен с синхронизирующим входом блока умножения, вход разрешения которого соединен с выходом восьмого элемента ИЛИ, второй вход которого соеди-. нен с выходом пятого формирователя импульсов, вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, информационный выход блока умножения соединен с суммирующим входом пятого счетчика, выход конца умножения блока умножения соединен с третьим входом седьмого элемента ИЛИ.

1238077

Фоа2

Составитель А. Сиротская .

Техред Л.Сердюкова, .Корректор Е. Рошко

Редактор М. Товтии

Тираж 671 Подписное . ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Заказ 3293/50

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4