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

 

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах. Цель изобретения - повышение быстродействия . Устройство для формирования остатка по произвольному модулю содержит вход 1 числа устройства, вход 2 модуля устройства, выход 3 остатка устройства, элемент ИЛИ 4, шифратор 5, узлы 6 определения кратности матрицы, вычитатели 7 группы, элементы И 8 матрицы, элементы ИЛИ 9 группы, дешифратор 10, выход 11 окончания устройства, входы 12 констант группы устройства 1 ил fe О ел 00 СО 00 о

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

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

РЕСПУБЛИК (я>5 Н 03 M 7/18

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ! в (21) 4640147/24 (22) 19.01.89 (46) 23.06.91. Бюл, N. 23 (72)Л. С. Сорока, А, Ф. Чипига и В, М. Тиунов (53) 681.3(088. 8) (56) Авторское свидетельство СССР

N. 15200667, кл. Н 03 М 7/18, 1988.

Авторское свидетельство СССР N. 1580561, кл. M 03 М 7/18, 1988. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ

ОТ ЧИСЛА

„„Я3 „„1658389 А1

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

Цель изобретения- повышение быстродействия. Устройство для формирования остатка по произвольному модулю содержит вход 1 числа устройства, вход 2 модуля устройства, выход 3 остатка устройства, элемент ИЛИ 4, шифратор 5, узлы 6 определения кратности матрицы. вычитатели 7 группы, элементы И 8 матрицы, элементы ИЛИ 9 группы, дешифратор 10, выход 11 окончания устройства, входы

12 констант группы устройства. 1 ил.

1658389

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

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

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

Устройство содержит вход 1 числа устройства, вход 2 модуля устройства, выход 3 10 остатка устройства, элемент ИЛИ 4, шифратор 5, узлы 6 определения кратности матрицы, вычитатели 7 группы, элементы И 8 матрицы, элементы ИЛИ 9 группы, дешифратор 10, выход 11 окончания устройства, 15 входы 12 констант группы устройства.

Сущность изобретения состоит в том, чтодля формирования остатка ак по модулю

PI от числа Ак одновременно вычитают коды чисел от единицы до уменьшенного на 20 единицу максимального значения модуля

Рмакс, QT KQToPQI возможно фоРмиРование остатка, полученные результаты Sl = А,, Sz. = Ак 1,....Sp = Ак (Рмакс — 1) ограничивают значениями 25 (Si, S1 ) g (S1 Sl = Pl E (P1, P BKc)) из которых путем одновременной проверки на кратность модулю Р> выбирают 30

Si E. (SI, S I) 3 (SI = О, mod Р ).

При этом ак = А» — Si.

Поясним на примере структуру устрой- 35 ства, Например, если устройство формирует остатки по модулям P1 = 23, Pz = 17, Рз = 7, Р4 =- 5, Р5 = 3, то матрицы узлов 6 определения кратности и элементов И 8 должны со- 40 держать пять столбцов, причем в первом должно быть двадцать три соответствующих элемента, во втором — семнадцать, в третьем — семь, в четвертом — пя-,ь, в пятом — три. Группа элементов ИЛИ 9 состо- 45 ит из семнадцати элементов. Группа вычитателей 7 состоит из двадцати двух вычитателей. Узлы 6 определения кратности столбца матрицы реализуют функцию определения кратности числа А» своему за- 50 данному модулю Pi, если, например, реализуется функция определения кратности по модулю семь, то алгоритм их функционирования будет описываться выражением:

Х 1XZX 1»аXгс ..X>1ЧХ 1ХZХ .Х>I Х>>»rl с X 1 X > X > X. Х >> Х > .> Х 1 Х Z Х 3Х.1 Х >1 где о p;)3j)Pliность входа 1. ко ор3ч пред е л Я е т с .3 а к с. h l м а л ь н о и B P f1 и > < I 111 > > Й I ч >> л А

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

Модуль Pi E (P1,Рмакс), по которому необходимо сформировать остаток заданного числа, задается параллельным двоичным кодом, подаваемым на вход 2. Этот параллельный двоичный код численно равен значению (номеру) задаваемого модуля, На вход 1 воздействует двоичный код числа Ак в параллельном коде. Код модуля

Pi, поступая на входы дешифратора 10, дешифрируется на нем. Поэтому на одном из выходов дешифратора, однозначно соответствующем коду модуля Pi, появляется сигнал логической единицы, который поступает на вторые входы элементов И 8 столбца, в котором узлы 6 определения кратности реализуют функцию определения кратности модулю Рь чем обеспечивается реализация функции (Si S1) 3 (S1 S> = PIE(Р1, Рмакс )).

Одновременно код числа А, поступает на входы вычитателей 7 и на объединенные входы узлов б определения кратности первой строки. На выходах вычитателей 7 образуются коды чисел Sz = А» 1,...,Sp = А»вЂ”

-(Рмакс — 1). которые поступают соответственно на объединенные входы узлов б определения кратности последующих строк. Поэтому в каждом столбце происходит проверка на кратность чисел(5>,SI), (i =2,Р) своему заданному модулю P. Ha выходах тех узлов 6, где

i> Si Е(Sp S1) g (Si=— - О, mod Р>Я Pl, Рмакс ), появятся единичные потенциалы, которые поступают на первые входы элементов И 8.

При этом сработает только тот элемент И 8, на второй вход которого поступает разрешающий потенциал с выхода дешифратора

10, а на первый — сигнал с выхода узла б, для которого оказалось выполненным условие:

SIЕ(S>, S1) g (БрО, mod Р, ), т.е. а»=А„S), Сигнал с выхода элемента И 8 через элемент ИЛИ 9 поступает на вход шифратора 5, реализующий функцию кодирования числа а,. и на вход элемента ИЛИ 4. При этом на выходе шифратора появляется комбинация единиц и нулей двоичного кода а» =А» — Sl, а на выходе элемента ИЛИ 4 появляется сигнал окончания процесса формирования остатка.

1658389

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

Редактор Б.Бугренкова Техред М.Моргентал Корректор M.Ку<ер«»

Заказ 1722 Тираж 466 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагар««л 101

Рассмотрим пример конкретного выполнения процесса формирования остатка по произвольному модулю от числа. Пусть устройство реализует, процесс формирования остатков по модулям P1 = 23, Pz = 17, 5

Рз = 7, Р4 - 5, Рь = 3, Необходимо сформировать ак при А» - 1238 и Р1= 17.Тогда в столбец узлов 6, реализующих функцию определения кратности по Рг =17, эа счет вычитателей 7 поступят коды чисел от 1238 до 10

1222, Поэтому с выхода узла 6 пятнадцатой строки (1224 =0, mod 17) через соответствующие элементы И 8 и ИЛИ 9 сигнал логической единицы поступает на четырнадцатый вход шифратора 5, чем обеспечивает фор- 15 мирование на его выходе кода числа ак = А» — SI - 1238 — 1224 = 14.

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

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

И первой строки матрицы соединены соответственно с входами первого элемента

ИЛИ группы, выходы элементов И второй строки матрицы соединены соответственно с входами второго элемента ИЛИ группы, 40 выходы первого и второго элементов ИЛИ группы соединены с соответствующими входами элемента ИЛИ, вход модуля устройства соединен с входом дешифратора, выходы которого соединены с вторыми вхо- 45

) дами соответствующих элементов И первой строки матрицы, выход первого вычитателя группы соединен с входами узлов определения кратности второй строки матрицы, о тл и ч а ю щ е е с я тем. что, с целью повышения быстродействия, оно содержит шифратор. с второго по (п1 — 1)-й (n1 максимальное значение модуля) вычитатели группы, с третьего по nz-й (nz-следующее по величине, после максимального, значение модуля) элементы ИЛИ группы, с третьего по nI-й (nI — I-e значение модуля, 1 = 1 — m. m — количество значений модуля) узлы определения кратности I-го столбца матрицы с третьего по ni-й элементы И I-го столбца матрицы, причем вход числа устройства соединен с входами узлов определения кратности первой строки матрицы и с входами уменьшаемых вычитателей с второго по (п1 1)-й группы, входы вычитаемых которых соединены с соответствующими входами констант группы устройства, выход

k-го вычитателя группы (k =- 2 — (п1-1) соединен с входами узлов определения кратности (k + 1)-й строки матрицы, выходы узлов определения кратности (k + 1)-й строки матрицы соединены с первыми входами соответствующих элементов И (k+ 1)-й строки матрицы, выходы дешифратора соединены с вторыми входами элементов И, кроме первых, соответствующих столбцов матрицы, выходы элементов И J-й строки матрицы (J = 3 — nz) соединены соответственно с входами J-го элемента ИЛИ группы, выход J-го элемента ИЛИ группы соединен с j-м входом элемента ИЛИ, выход которого является выходом окончания устройства, выход остатка которого соединен с выходом шифратора, выход I-го элемента

И первого столбца матрицы (! = nz + 1 — п1) соединен с -м входом элемента ИЛИ, выходы элементов ИЛИ, кроме первого, группы и выходы с (nZ + 1)-ro no п1-й элементов И первого столбца матрицы соединены соответственно с входами шифратора.