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

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

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

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

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

Сущность изобретения состоит в том, что для формирования остатка ак по модулю PI от числа Ак одновременно вычитают коды чисел от единицы до уменьшенного на единицу максимального значения модуля Рмакс, от которого возможно формирование остатка, полученные результаты Si Ак,

S. Ак-1Sp Ак-(Рмакс-1) ограничивают

значениями

}} S1-S| Pl €{ Pi. Рмакс} ,

из которых путем одновременной проверки на кратность модулю Pi выбирают

Sj 6 {Si, SiHfcj 0, mod Pi.

При этом ак Ак - Sj.

Поясним на примере структуру устрой- ства.

Например, если устройство формирует остатки по модулям PI 23, Р2 17, Рз 7, Р/1 5, РБ 3, то матрицы узлов 6 определения кратности и элементов И 8 должны со- держать пять столбцов, причем в первом должно быть двадцать три соответствующих элемента, во втором - семнадцать, в третьем - семь, в четвертом - пять, в пятом - три. Группа элементов ИЛИ 9 состо- ит из семнадцати элементов. Группа вычитателей 7 состоит из двадцати двух вычитэтелей. Узлы 6 определения кратности столбца матрицы реализуют функцию определения кратности числа Ак своему за- данному модулю PI, если, например, реализуется функция определения кратности по модулю семь, то алгоритм их функционирования будет описываться выражением:

У1 X WX.lX4Xfi...Xi;|VX 1Х2ХЗХ/1ХТ,. «q v V- Х1Х2ХЧХ.1ХГ). Xi| v/x lX2X3X 1Xt:i . X.|i .

где q разрядность входя 1. ко горяч ппре- деляетсч максимальной величиной мч пп дк.

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

Модуль PI 6 { Pi,Рмакс} , по которому необходимо сформировать остаток заданного числа, задается параллельным двоичным кодом, подаваемым на вход 2. Этот параллельный двоичный код численно равен значению (номеру) задаваемого модуля. На вход 1 воздействует двоичный код числа Ак в параллельном коде. Код модуля Pi, поступая на входы дешифратора 10, дешифрируется на нем. Поэтому на одном из выходов дешифратора, однозначно соответствующем коду модуля PI, появляется сигнал логической единицы, который поступает на вторые входы элементов И 8 столбца, в котором узлы 6 определения кратности реализуют функцию определения кратности модулю Pi, чем обеспечивается реализация функции

(Si. Si} 3 Si S,- Pi6{ Pi. Рмакс}.

Одновременно код числа Ак поступает на входы вычитателей 7 и на объединенные входы узлов 6 определения кратности первой строки. На выходах вычитателей 7 образуются чисел S2 Ак - 1Sp Ак -(Рмакс - 1). которые поступают соответственно на объединенные входы узлов б определения кратности последующих строк. Поэтому в каждом столбце происхо- дит дроверка на кратность чисел { Si.Sj}. (i 2,P) своему заданному модулю Р. На выходах тех узлов 6, где

VSjЈ{ Sp, Si}f , mod Pi(f{ Pi. Рмакс},

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

SjЈ{ Si. Si}g S,sO, mod P, , т.е. .

Сигнал с выхода элемента И 8 через элемент ИЛИ 9 поступает на вход шифратора 5, реализующий функцию кодирования числа ак и на вход элемента ИЛИ 4. При этом на выходе шифратора появляется комбинация единиц и нулей двоичного кода ак АК - Sj, а на выходе элемента ИЛИ 4 появляется сигнал окончания процесса формирования остатка.

Рассмотрим пример конкретного выполнения процесса формирования остатка по произвольному модулю от числа. Пусть устройство реализует, процесс формирования остатков по модулям PI 23, PZ 17, Рз 7, РА 5, PS 3. Необходимо сформировать ак при Ах - 1238 и Р| 17.Тогда в столбец узлов 6, реализующих функцию определения кратности по PI 17, за счет вычи- тателей 7 поступят коды чисел от 1238 до 1222. Поэтому с выхода узла 6 пятнадцатой строки (1224 sO, mod 17) через соответствующие элементы И 8 и ИЛИ 9 сигнал логической единицы поступает на четырнадцатый вход шифратора 5, чем обеспечивает фор- мирование на его выходе кода числа ак Ак -Sj 1238- 1224 14.

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

выходы которого соединены с вторыми вхо- i

дами соответствующих элементов И первой строки матрицы, выход первого вычитателя группы соединен с входами узлов определения кратности второй строки матрицы, о т - личающееся тем, что, с целью повышения быстродействия, оно содержит шифратор, с второго по (ni - 1)-й (ni - максимальное значение модуля) вычитате- ли группы, с третьего по П2-й (п2-следующее по величине, после максимального, значение модуля) элементы ИЛИ группы, с третьего по ni-й (щ - 1-е значение модуля, I 1 - т, т - количество значений модуля) узлы определения кратности 1-го столбца матрицы с третьего по щ-й элементы И 1-го столбца матрицы, причем вход числа устройства соединен с входами узлов определения кратности первой строки матрицы и с входами уменьшаемых вычитателей с второго по (щ-1)-й группы, входы вычитаемых которых соединены с соответствующими входами констант группы устройства, выход k-ro вычитателя группы (k - 2 - (щ-1) соединен с входами узлов определения кратности (k + 1)-й строки матрицы, выходы узлов определения кратности (k + 1)-й строки матрицы соединены с первыми входами соответствующих элементов И (k + 1)-й строки матрицы, выходы дешифратора соединены с вторыми входами элементов И, кроме первых, соответствующих столбцов матрицы, выходы элементов И J-й строки матрицы (J 3- П2) соединены соответственно с входами j-ro элемента ИЛИ группы, выход J-ro элемента ИЛИ группы Соединен с j-м входом элемента ИЛИ, выход которого является выходом окончания устройства, выход остатка которого соединен с выходом шифратора, выход 1-го элемента И первого столбца матрицы (I - П2 + 1 - ш) соединен с l-м входом элемента ИЛИ, выходы элементов ИЛИ, кроме первого, группы и выходы с (п2 + 1)-го по пгй элементов И первого столбца матрицы соединены соответственно с входами шифратора.

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