Устройство для расширения диапазона в системе остаточных классов

 

Изобретение относится к вычислительной технике, а точнее к устройствам процессоров специализированной вычислительной техники с непозиционным представлением информации. Изобретение предназначено для выполнения одной из основных операций модулярной арифметики - операции расширения диапазона. Целью изобретения является сокращение аппаратурных затрат . Поставленная цель достигается тем, что устройство для расширения диапазона в системе остаточных классов , содержащее модульные вычитатели 3, л группу преобразователей 6 прямого кода в дополнительный код, содержит модульные вычитатели 3|,г , и блок 5 памяти с соответствую- 1 ил., 1 табл. - пщими связями. i (Л

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

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

РЕСПУБЛИК (19) ()1) А1 (51) 4 С 06 F 7/72 Н 03 М 7/18

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

° р »ч <

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

C е

:В»

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4152719/24-24 (22) 28.11.86 (46) 15.04.88. Бюл. ¹ 14 (71) Институт математики и механики

АН КазССР (72) И.||.Акушский, С.А.Инютин и А.Н.Казангапов (53) 681.33(088.8) (56) Авторское свидетельство СССР № 1259495, кл. С 06 F 7/72, Н 03 M 7/18, 1984.

Авторское свидетельство СССР № 1282134, кл. G 06 F 7/72, Н 03 N 7/18, 1985. (54) УСТРОЙСТВО ДЛЯ РАСШИРЕНИЧ ДИАПАЗОНА В СИСТЕМЕ ОСТАТОЧНЪ|Х КЛАССОВ (57) Изобретение относится к вычислительной технике, а точнее к устройствам процессоров специализированной вычислительной техники с непозиционным представлением информации.

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

3<-3 „ и группу преобразователей

6 прямого кода в дополнительный код, содержит модульные вычитатели 3„, 3 „, и блок 5 памяти с соответствующими связями. 1 ил., 1 табл.

1388861 (1)

Р<» Р»» ° ° ° » Р« основания системы остаточных классов (СОК). Тогда целое число А однозначно представляется совокупностью неотрицательных вычетов (2) »< » ° ° ° » < « где А = «<;(mod А, ), i„=- 1, 2, п, AE (0,9 =,П Р;).

Под расширением диапазона понимается получение числа А в расширенной системе (3)

Р<, „° ., Р„,<< в виде записи

А (К,» ° ° ° »<П»6ÄÄ »

С< n <.к

55 и нужно определить вычеты <С „+, » < <<»<<

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

5 в коде системы остаточных классов.

Целью изобретения является сокращение аппаратурных затрат.

На чертеже представлена схема устройства для расширения диапазона в . системе остаточных классов.

Устройство содержит группу информационных входов 1 устройства, группу выходов 2 устройства, модульные вычитатели 3,-3„,, группу тактовых входов 4 устройства, блок 5 памяти, группу преобразователей 6 прямого ко; да в дополнительный код.

Модульные вычитатели 3< -3„, выполнены накапливающими. 20

Блок 5 памяти для первоначальных оснований 3, 5, 7 и 11 и дополнительных оснований 13 и 17 имеет следующую .кодировку (см. таблицу).

На тактовые входы 4 группы устрой- 25 .ства подается последовательность из n импульсов со сдвигом между ними, :определяемым временем срабатывания модульного вычитателя 3 и блока 5 памяти. 30

В основу работы устройства положен следующий алгоритм.

Пусть взаимно простые числа

Число А можно представить следующим образом:

А=, М ; (5) где М;, ) — минимальные числа, которые являются наименьшими из чисел вида М;»

, = (О, О, ..., ; °, 0<<

В дальнейшем предполагаем, что минимальные числа представлены в системе (3):

М;,, = (О, О, ..., О, У, (6) ° ° 2| n У, ° F n,ê

Для получения из числа (2) число вида (4) в представлении (2) дополним нулями последние к разрядов

А = (oc,, ...,«<„, О, ...,0), (7) Минимальные числа в заданной системе оснований всегда постоянны, поэтому всегда заранее можно составить таблицу. Теперь, последовательно вычитая числа (6) из (7), получим

M,,«<,, = (О, о

А =А<

<. ° .,oC,„, );

n-<

«-< — Ми, .,», n

«

О,.- „„„„...,,»к ), (0, 0, А„=

° ° ° »

Образуя формальную разность, получим А = А — А«.

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

Первый вычет с входов 1 устройства поступает на первый адресный вход блока 5 памяти, остальные вычеты поступают с входов 1 устройства на входы уменьшаемых вычитателей 3<-3„, где запоминаются. Из блока 5 памяти по значению первого вычета (см. таблицу) происходит выбор соответствующего минимального числа М<» с<,< значение которого с второй группы выходов блока 5 памяти поступает на входы вычитаемых модульных вычитателей 3,-3„< . Одновременно вычеты минимального числа по основаниям, на которые производится расширение, с первой группы выходов блока 5 памяти

1388861

Выходы (M;, ; ) Выходы (М;. 2I ) Входы

Входы

¹ Значе2 группа

2 группа группа

1 группа № Значение ние

12, 5) (О, О, 6, 2, (О, О, О, 6, 3 6

4 6

4 1

4 7

4 2

1, 1) (1, 1, 1, 1, 1 1 (2, 2, 2, 2, 2, 2) (о, з, з, з, 3, 3) (О, 1, 6, 6, 6, 6) 1, 3) 1. 2 (О, О, О, 1, 2, 6)

3, 9)

4, 12)

5, 15)

6, 1)

7, 4)

8, 7) 2 3 (О, О, О, 7, (О, О. О, 2, (О, О, О, 8, (О, О, О, 3, (О, О, О, 9, (О, О, О. 4, 2 1

2 4

2 2

9, 9) (О, 4, 2, 9, (0, 2, 5, 1, 12, 12) 4 8 (0, О, 1, 4, 2, 15) 4 3

4 9 ,4 4

3. 1

3 2

3 3 поступают в соответствующие преобразователи 6. С входов 1 устройства снимаются значения первоначальных вычетов. В модульных вычитателях вычисляется значение Л,. На первый тактовый вход 4 группы устройства подается импульс, по которому значение с выхода модульного вычитателя 3, поступает на второй адресный вход блока 5 памяти. Из блока 5 памяти

< выбирается значение М, о<., поступающее на входы вычитаемых модульных вычитателей 3, -3„ <, где образуется значение А, и на информационные входы преобразователей 6. Описанный процесс продолжается по получения значения A Затем по импульсу с последнего тактового входа 4 групгы устройства сформированные значения oC „,, выдаются с выходов преобразователей 6 на выходы 2 группы устройства..

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

Устройство для расширения диапазона в системе остаточных классов, содержащее п-3 (и — количество первоначальных оснований) модульных вычитателя и группу преобразователей прямого кода в дополнительный код, (О, О, 2, 8, 4, 13) (О, О, 3, 1, 6, 11) причем выходы преобразователей прямого кода в дополнительный код группы являются группой выходов устройства, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, оно содержит блок памяти, (n-2)-й и (и-1)-й модульные вычитатели, причем информационные входы группы с второго по и-й устройства соединены соответственно с входами уменьшаемых модульных вычитателей с nepaoro no (n-1)-й, первый информационный вход группы устройства и выходы модульных вычитателей с первого по (и-1)-й сое-!

5 динены соответственно с адресными входами группы блока памяти, выходы первой группы которого соединены с информационными входами соответствующих преобразователей прямого кода в дополнительный код группы, выходы второй группы блока памяти соединены с входами вычитаемых соответствующих модульных вычитателей с первого по (п-1)-й, входы разрешения выдачи разности которых соединены соответственно с тактовыми входами группы, кроме последнего, устройства, последний тактовый вход группы которого соединен с входами разрешения выдачи результата преобразователей прямого кода в дополнительный код группы.

1388861

Продолжение таблицы

3цкоды (И1 е ) Вьиоды (И;, ; ) 2 группа

2 группа (О, О, 4,, 5, 8, 9) 10 (О. О, О, 10, 9, 10) Редактор Е.Копча

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

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4,3 4 3 5 (О, О, 5 °, 9, 10, 7) 4 5 (О, О, О, 5, 10, 13) Составитель А.Клюев

Техред А.Кравчук Корректор А. Обручар