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

25

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

Цель изобретения - повышение дос- 5 товерности формирбвания.

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

Устройство содержит (фиг. 1) шину to 1 задания кода модуля, элемент ИЛИ 2, формирователи импульсов 3 и А, счетчики 5 и 6, элементы ИЛИ 7 и 8, эле- мент 9.. ИСКЛЮЧАЮЩЕЕ ИЛИ, элементы ИЛИ 10-и 11, цчетчик 12, формирова- is тель 12 импульсов, элемент ИЛИ 14, счетчик 15, блок Т6 умножения, счетчики 17 и 18,.элемент И 19, генератор 20 тактовых импульсов, элемент ИЛИ 21, формирователи 22-24 импульса, 20 элемент ИЛИ-ИЕ 25, группу 26 суммато--. ров по модулю два счетчик 27, шину 28 задания кода числа, вход 29 пуска, выход 30 конца формирования устройства, выходы 31 устройства, элемент

ИЛИ 32,

Блок умножения (фиг. 2) содержит формирователь 33 импульсов, элем1ент ИЛИ-НЕ 34, элемент ИЛИ 35, группу, 36 сумматоров по модулю два, формирователь 37 импульса, элемент И 38, счет-i чики 39 и 40,

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

Перед началом работы на шине 28 задания кода числа задается код С, который в течение времени формирования воздействует на входы предварительной записи счетчика 17. Также задается код модуля М .на шине 1, который воздействует на входы cy яIaтopoв

группы 26 и на входы предварительной записи счетчиков 5 и 6,

.Устройство реализует выражение

3 (9)j + Cg (mod М) , ,

30

35

40

45

50

где Сд О, М-1, j 1; М-1, (1)

Импульс с входа 29 пуска устройства запускает устройство в работу. Этот импульс, проходя через элемент ИЛИ 2, воздействует на вход разрешения счетчика 5, в результате чего в

5

1238077

счетчик 5 запишется код Модуля М, воздействующий на информационные входы; воздействуя на входы разрешения счетчика 6 и через элемент ИЛИ 32 на вход разрешения счетчику 27, запи- шет в эти счетчики код модуля М и код

5

o s 0

0

5

0

5

50

55

числа Ср соо.тветственно; воздействуя на первый вход элемента ИЛИ 11 и проходя на его выход, поступит на счетный вход счетчика 15.

По срезу импульса пуска, подавае- . мого на вход формирователя 4 импульсов, на выходе последнего сформируется импульс, который проходя на входы элементо13 ШШ 7 и 8 поступит на их выходы, а далее на вычитающие входы счетчиков 5 и 6 соответственно, вычитая из кода модуля М, записанного в этих счетчиках единицу; проходя на первь й вход элемента ИЛИ 10, посту- пит на вход разрешения счетчика .18, предварительно записывая в него код числа GO, записанный в счетчике 17. Блок 16 умножения в вычислении первого символа кодовой последовательности не участвует, так как величина элемента - см, (1), определяемая состоянием счетчика 12, численно рав- на. нулю, .

После того, как в счетчике 18 будет зацисана кодовая последовательность числа CQ , на выходе элемент.а ИЛИ 21 появится единичный потенциал, который будет поддерживаться до тех пор, пока счетчик 18 не обнулится. По фронту этого потенциала формирователь 22 импульсов сформирует Ш 1пульс, ко- горый обнулит счетчик 27.-Этим же . единичным потенциалом с выхода элемен- га ИЛИ 21 откроется элемент И 19. и тактовые импульсы, воздействующие на другой его В.ХОД, поступают на вычитаю- щш вход счетчика 18 и на су1.1мирующнй вход счетчика 27. Последний осуществляет суммирование поступившего на вход количества тактовых импульсов. Суммирование осуществляется до тех пор, пока на выходах счетчика 27 не образуется число в двоичном коде, числе.нно равное выбранному модулю М и воздействующее на первые входы группы 26 сумматоров по модулю два, выполняющих операцию равнозначности. На в.торые входы этих сумматоров воздействует двоичный код выбранного модуля М,В результате на выходе каждого сумматора по модулю два группы 26 окажутся нулевые потенциалы, которые воздействуют на входы элемента ИЛИ-НЕ 25. На выходе последнего образуется единичный потенциал, который через формирователь 24 импульсов обнулит счетчик 27, а подсчет такто- вь1х импульсов начнется заново, т.е. на пэрвые входы сумматоров по модулю два группы 26 будут воздействовать в параллельном коде двоичнь е коды чисел от 1 до М. В течение этого времени хотя бы на одном из выходов сумма торов группы 26 будет единичный потенциал. Следовательно, на выходе элемента ИЛИ-НЕ 25 будет нулевой потенциал. Как только счетчик 27 сосчитает количество тактовых импульсов, равньгх выбранному модулю М, опять произойдет его обнуление. Такая операция будет происходить до тех пор, пока не обнулится счетчик 18. А обнуление последнего произойдет В.ТОМ. случае, когда количество поступивших на его второй вход тактовых импульсо будет численно равно числу, записанному в счетчике .18.. В результате чего на выходе элемента ИЛИ 21 возника ет нулевой потенциал, элемент И 19 закроется и тактовые импульсы перестанут поступать на входы счетчиков 18 и 27, Поэтому на выходах счетчика 27 останется остаток числа, запи- санного в счёт чике 1-8 по- модулю М. По срезу импульса, образующегося на выходе элемента ИЛИ 21, формирователь 23 импульсов сформирует импульс который поступит на вход элемента ИЛИ 32 и далее, проходя на вход счет чика 17, запишет в последний код С, на счетный вход счетчика 12 и через элемент ИЛИ 7 на вычитающий вход счетчика 5, добавляя и вычитая из содержимого, этих счетчиков единицу, соответственно, проходя через элемент ИЛИ ИСКЛЮЧАЮЩЕЕ 9, поступит на вход формирователя 13 импульсов, ко

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

Блок 16 умножения работает следу- ющим образом (фиг. 2).

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

s to f5 20 25 зо

5

0.

5

0

5

входами элемента ИЛИ 35, то на выходе последнего возникает единичный потен- 1Шал, который будет поддерживаться до тех пор, пока счетчик 40 не окажется в нулевом состоянии. Единичный потенциал с выхода элемента ИЛИ 35 открывает элемент И 38, на второй вход которого поступают тактовые импульсы. В результате тактовые импульсы поступают на счетный вход счетчика 39 и подсчитываются им. Как только количество тактовых импульсов, подсчитанное счетчиком 39, окажется равным коду числа, воздействующему на первые входы группы 36 cyMtiaropoB по модулю два (множителю) на выходе элемента ИЛИ-НЕ 34 образуется единичный потенциал, по фронту которого формирователь 33 импульсов сформирует импульс, который поступит на вычитающий вход счетчика 40, а также обнулит счетчик 39. Как только на вычитающий вход счетчика 40 поступит количество импульсов, численно равное коду записанного в нем числа, он об- нулится, на: выходе элемента ИЛИ 35 образуется нулевой потенциал и тактовые импульсы не будут проходить на выход элемента И 38. Количество тактовых импульсов, поступившее с выхода элемента И 38 на счетный вход счетчика 39, а равно и на выход блока, численно будет равно произведению чисел, воздействующих на первые и вторые входы блока 16 умножения. По срезу единичного импульса на вьгкоде элемента ИЛИ 35 формирователь 37 импульсов вьщает импульс Конец умножения.

Количество импульсов, поступившее на выход блока 16 умножения, подсчитывается счетчиком 17, в Котором предварительно записан код числа Со. Импульс Конец умножения с выхода формирователя 37 импульсов блока 16 умножения, проходя через элемент ИЛИ 10, поступит на вход разрешения счетчика 18, записывая в него код числа счетчика 17, и далее начинает- . ся процесс вычисления остатка по модулю М от этого числа, который опи-, сывался выше. После того, как будет сформирован следующий символ кодовой последовательности, формирователь 23 вьщает следующий импульс. На выходах счетчика 12 под воздействием импульсов с выходов формирователя 23 будут формироваться последовательно коды от О до М-1. После того, как сформируется М-1 код, под воздействием следующего импульса с выхода формирователя 23, счетчик 5 обнулится, в результате чего на его выходе переноса появится импульс, который обнулит счетчик 12, запретит прохождение импульса со входа элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 9 на его выход, проходя че- рез элемент ИЛИ 11, сосчитается счетчиком 15, а проходя через элемент ИЛИ 8, вычтется из счетчика 6, поступит на вход формирователя 3 импуль- Сов.

Формирователь 3 сформирует по срезу поступившего на его вход импуль- са импульс, который, проходя через элемент ИЛИ 14, поступит на вход разрешения блока 16 умножения, включая его тем самым .в работу, а также, проходя на вход элемента ИЛИ 2, поступит на вход разрешения счетчика , устанавливая его в предварительное сос- тояние, численно равное коду числа М, воздействующего на входы с шины 1. Этот же импульс, проходя через элемент ИЛИ 7 вычтет из счетчика 5 1, в результате чего в счетчике 5 окажется записан код числа М-1,

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

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

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

o

5

0

5

0

5

0

5

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

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

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

Фиг.1

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

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

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

Заказ 3293/50Тираж 671Подписное

, ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

Ф14Ъ.2.

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