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

(505 Н 03 М 7/1 ЕТ Я ТОР ДЕ СТВУ 24 ительычисл ользо устрой а,А, ф. Чипи)свидетельствл. НОЗМ 7/1видетельство18, 1988,нов йст а по ия остит входройстмент ССР 88. Р М 1580561,выИ я кра леме ы,де ИЯ(54) УСТР ОСТАТКА ОТ ЧИСЛА ОРМИ НОМУ ТВОРО ил ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР ИСАНИЕ И 21) 4640147/22) 19.01.8946) 23.06.91.(57) Изобретение относится к в ной технике и может быть исп цифровых вычислительных Цель изобретения- повышение б вия. Устройстводля формирован произвольному модулю содерж ла устройства, вход 2 модуля уст ход 3 остатка устройства, эле шифратор 5, узлы 6 определени матрицы. вычитатели 7 группы, э матрицы, элементы ИЛИ 9 групп тор 10, выход 11 окончания устро 12 констант группы устройства.т,е, а=А-Я),55 Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах.Целью изобретения является повышение быстродействия. 5На чертеже представлена функциональная схема устройства для формирования остатка по произвольному модулю от числа,Устройство содержит вход 1 числа устройства, вход 2 модуля устройства, выход 3 10 остатка устройства, элемент ИЛИ 4, шифратор 5, узлы 6 определения кратности матрицы, вычитатели 7 группы, элементы И 8 матрицы, элементы ИЛИ 9 группы, дешифратор 10, выход 11 окончания устройства, 15 входы 12 констант группы устройства.Сущность изобретения состоит в том, чтодля формирования остатка ак по модулю Р 1 от числа Ак одновременно вычитают коды чисел от единицы до уменьшенного на 20 единицу максимального значения модуля Рмакс, ОТ КОТороГО ВОЗМОЖНО фОРМИРОВдние остатка, полученные результаты 51= А 52 = Ак - 15 р = Ак (Рмакс 1) ОгРаничиваЮт значениями 25( Б 51 )51 51 = Р Е ( Р 1, Рмакс) из которых путем одновременной проверкина кратность модулю Р выбирают 30 Я 1 б ( Яь 51 Ц 51 - = О, гпод Р 1),При этом ак = Ак - Я.Поясним на примере структуру устройства,Например, если устройство формируетостатки по модулям Р 1 = 23, Р 2 = 17, Рз = 7,Р 4 = 5, Р 5 = 3, то матрицы узлов 6 определения кратности и элементов И 8 должны содержать пять столбцов, причем в первомдолжно быть двадцать три соответствующих элемента, во втором - семнадцать, втретьем - семь, в четвертом - пять, впятом - три, Группа элементов ИЛИ 9 состоит из семнадцати элементов. Группавычитателей 7 состоит из двадцати двухвычитателей. Узлы 6 определения кратности столбца матрицы реализуют функциюопределения кратности числа Ак своему заданному модулю Рь если, например, реализуется функция определения кратности помодулю семь, то алгоритм их функционирования будет описываться выражением: у 1 = х 1 х;хламах,Х 1 чх 1 Х 2 ХЗхлх лх 1 х хахлх 5.,х 1 "х 12 хзх 1 х .," ргде ц разрядность входа 1 копрял д пред е л Я е т с я 1а к г. 1 м а л ь н 0 Й н е и и ч и н и ии ч и л А ,Устройство работает следующим образом.МоДУль Р б ( Р 1,Рмас), по котоРомУ необходимо сформировать остаток заданного числа, задается параллельным двоичным кодом, подаваемым на вход 2. Этот параллельный двоичный код численно равен значению (номеру) задаваемого модуля, На вход 1 воздействует двоичный код числа Ак в параллельном коде. Код модуля Рь поступая на входы дешифратора 10, дешифрируется на нем, Поэтому на одном из выходов дешифратора, однозначно соответствующем коду модуля Рь появляется сигнал логической единицы, который поступает на вторые входы элементов И 8 столбца, в котором узлы 6 определения кратности реализуют функцию определения кратности модулю Рь чем обеспечивается реализация функции(5 Ь 51) 3 51 -= Р 6( Р 1, Рмакс ). Одновременно код числа А, поступает на входы вычитателей 7 и на объединенные входы узлов 6 определения кратности первой строки, На выходах вычитателей 7 образуются коды чисел Я 2 = Ак 15 р = Ак - -Рмакс - 1). которые поступают соответственно на объединенные входы узлов 6 определения кратности последующих строк, Поэтому в каждом столбце происходит проверка на кратность чисел ( 5 ь 51), ( =2,Р) своему заданному модулю Р. На выходах тех узлов 6, где Ч 51 Е( Яр, Я 1)51 - О, пос 1 РЕ( Р 1 Рмакс ),появятся единичные потенциалы, которые поступают на первые входы элементов И 8, При этом сработает только тот элемент И 8, на второй вход которого поступает разрешающий потенциал с выхода дешифратора 10, а на первый - сигнал с выхода узла 6, для которого оказалось выполненным условие. 51 Е( 5 ь 51) Д БрО, п 1 ос 1 Р, ,Сигнал с выхода элемента И 8 через элемент ИЛИ 9 поступает на вход шифратора 5, реализующий функцию кодирования числа а,. и на вход элемента ИЛИ 4. При этом на выходе шифратора появляется комбинация единиц и нулей двоичного кода ак =Ак - 51, а на выходе элемента ИЛИ 4 появляется сигнал окончания процесса формирования остатка1658389 Рассмотрим пример конкретного выполнения процесса формирования остатка по произвольному модулю от числа. Пусть устройство реализует, процесс формирования остатков но модулям Р 1 = 23, Р 2 = 17, Рз =7, Р 4 - 5, Р 5 = 3, Необходимо сформировать ак при А - 1238 и Р 1= 17,Тогда в столбец узлов 6, реализующих функцию определения кратности по Рг =17, эа счет вычитателей 7 поступят коды чисел от 1238 до 1222, Поэтому с выхода узла 6 пятнадцатой строки (1224 0, щоб 17) через соответствующие элементы И 8 и ИЛИ 9 сигнал логической единицы поступает на четырнадцатый вход шифратора 5, чем обеспечивает формирование на его выходе кода числа ак = А - 31 " 1238 - 1224 = 14,51015 Составитель А.Клюев Редактор Б,Бугренкова Техред М,Моргентал Корректор М,КучерчваяЗаказ 1722 Тираж 466 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКН СССР113035. Москва, Ж, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул Гдглрил 101 Формула изобретенияУстройство для формирования остатка 20 по произвольному модулю от числа, содержащее элемент ИЛИ, дешифратор, первый вычитатель группы, первый и второй элементы ИЛИ группы, узлы определения кратности первой и второй строк матрицы, 25 элементы И первой и второй строк матрицы, причем вход числа устройства соединен с входом уменьшаемого первого вычитателя группы, вход вычитаемого которого соединен с первым входом констант группы 30 устройства, выходы узлов определения кратности первой и второй строк матрицы соединены соответственно с первыми входами соответствующих элементов И первой и второй строк матрицы, выходы элементов 35 И первой строки матрицы соединены соответственно с входами первого элемента ИЛИ группы, выходы элементов И второй строки матрицы соединены соответственно с входами второго элемента ИЛИ группы,40 выходы первого и второго элементов ИЛИ группы соединены с соответствующими входами элемента ИЛИ, вход модуля устройства соединен с входом дешифратора, выходы которого соединены с вторыми вхо) дами соответствующих элементов И первой строки матрицы, выход первого вычитателя группы соединен с входами узлов определения кратности второй строки матрицы, о тл и ч а ю щ е е с я тем. что, с целью повышения быстродействия, оно содержит шифратор. с второго по (п 1 - 1)-й (п 1 максимальное значение модуля) вычитатели группы, с третьего по п 2-й (п 2-следующее по величине, после максимального, значение модуля) элементы ИЛИ группы, с третьего по п 1-й (п - 1-е значение модуля,= 1 - гп. т - количество значений модуля) узлы определения кратности 1-го столбца матрицы с третьего по п-й элементы И 1-го столбца матрицы, причем вход числа устройства соединен с входами узлов определения кратности первой строки матрицы и с входами уменьшаемых вычитателей с второго по (п 1-1)-й группы, входы вычитаемых которых соединены с соответствующими входами констант группы устройства, выход -го вычитателя группы ( =- 2 - (п 1-1) соединен с входами узлов определения кратности (к + 1)-й строки матрицы, выходы узлов определения кратности (1 + 1)й строки матрицы соединены с первыми входами соответствующих элементов И (М+ 1)-й строки матрицы, выходы дешифратора соединены с вторыми входами элементов И, кроме первых, соответствующих столбцов матрицы, выходы элементов И 1-й строки матрицы Ц = 3 - п 2) соединены соответственно с входами )-го элемента ИЛИ группы, выход )-го элемента ИЛИ группы соединен с )-м входом элемента ИЛИ, выход которого является выходом окончания устройства, выход остатка которого соединен с выходом шифратора, выход 1-го элемента И первогостолбца матрицы ( = п 2+ 1 - и 1) соединен с 1-м входом элемента ИЛИ, выходы элементов ИЛИ, кроме первого, группы и выходы с (п 2 + 1)-го по п 1-й элементов И первого столбца матрицы соединены соответственно с входами шифратора.