Преобразователь кода из системы остаточных классов в двоичный код Советский патент 1982 года по МПК G06F5/02 

(n - количество оснований системы, pj - основание системы), сумматор по модулю сумматор по модулю рп+2 содержит регистр интервального индекса, вход которого является индексным входом преобраэоватеяя, сдвиговый ретастр, выходы которого являются выходами двоичного кода преобразователя/ первый, второй и третий блоки хранения констант интервального индекса, первые входы первых n сумматоров группы объединены с первьада входами соответствующих n блоков хранения констант группы и подключены к соответствукицим выходам входного,регистра, первый вход (n+l) го сумматора группы объединен с первым входом первого блока хранения констант интервального индекса и под ключен к выходу регистра интервально го индекса, вторые входы п+1-го сумматоров группы объединены и подключе ны к выходу сумматора по модулю р,.2 и к входу сдвигового регистра, первы входы первых n сумматоров группы подключены к соответствующим входам входного регистра, а вторые - к вторым входам блоков хранения констант, первые выходы которых подключены к соответствующим n входам сумматора по модулю Pn., а вторые - к соответ ствующим n входам сумматора по модулю ,(п+1)-ый вход сумматора по модулю р„ подключен к первому выходу (п+1)-го сумматора группы, второй выход которого подключен к второму входу первого блока хранения констан интервального индекса, первый выход которого подключен к первому входу второго блока хранения констант интервального индекса, а второй - к Сп+2)-му входу сумматора по модулю р, первый выход которого подключен к второму входу второго блока хранения констант интервального индекса, а второй - к первому входу третьего блока хранения констант интервального индекса, второй вход которого под ключен к первому входу первого блока хранения констант интервального индекса, а выход подключен к (п+1)-му входу сумматора по модулю Упрощение преобразователя достигается за счет использо.вания кодов рангового расширения системы остаточ ных классов. В основу работы преобразователя положено следующее. Пусть требуется преобразовать в двоичную систему счисления целое числ А , пре;5ставленное в виде А Ol.aj«„, 1д , гдеос |АР; IP . i-ая цифра нормированного кода в остатках числа | А I р. , а 1д - интервальный индекс числа А ,определяемый так, чтобы ,|,.PnlAP. Здесь Р ;П Р; .Р;, , РЗ . . . ,РП -основные модули рангового расширения системы остаточных классов; через обозначается наименьший неотрицательный вычет по модулю р, сравнимн.1й с X. Индекс 1д числа А должен удовлетворять условию -q JlAlp-b Гд q, (2) где -5 |А1р- нормированный ранг числа |А|р , а q 2(К - фиксированное натуральное число). В соответствии с определением нормированного ранга числа можно записатьА |А1р + (91А1 р + 1д)р. Учитывая (2), заключаем, что диапазон рангового расширения системы остаточных классов, а следовательно, и множество чисел, которыемогут быть приведены из рассматриваемых систем в двоичный код с помощью предлагаемого устройства, представляет собой интервал -qP, q PJ На чертеже представлена блок-схема устройства. Схема включает входной регистр 1, группу 2 из n блоков хранения констант, группу 3 из п+1 сумматоров по модулю р , регистр 4 интервального индекса, первый блок 5 хранения констант интервального индекса, сумматоры 6 и 7 по модулю P„,, Pni2 второй и третий блоки 8 и 9 хранения констант интервального индекса, сдвиговый регистр 10. Входной регистр предназначен для хранения остатков числа по каждому из оснований системы и состоит из n подрегистров. Группа 2 блоков хранения констант представляет собой совокупность из n постоянных запоминающих блоков, адресом которых являются остатки по соответствующим основаниям системы, а выходом преобразованные остатки в соответствии с формулами I Pi otjlP jHJ-oiyP lP, Группа сумматоров 3 выполняет функции вычитателей по основаниям системы р и р с весом |Ь . Если i 1,2,...,п , то i-ый сумматор формирует величину|{(--с.р:)/р, | р. если i п+1, то (п+1)-ый сумматор формирует величину|(р,-а.)/Р/Рп 2|р„ Первый блок 5 хранения констант интервального индекса представляет собой таблицу дополнительного кода интервального индекса, на выходе которой формируется величина -1| Р с весом . Если i 1,2,...,п , то i-ый сумматор формирует величину Pi-обгРГ Р, если i п+1, то (п+1) ллй сумматор формирует величину

Р р . Второй и третий блоки nt-o.

хранения констант интервального индекса также представляют собой таблицы, которые по входной информации, определяемой величиной I, формируют на выходах величины|-1Р|Рп и|1Р| Рг,2.

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

Процесс перевода числа , qPj в двоичный код состоит из двух этапов, на первом из которых число А, поступающее в регистр 1, расширяется на дополнительные модули рангового расширения системы остаточных классов .р„,,и р„,2 Д Pn+j q 2 , а р 2q, причем модули р .Pj , попарно взаимно просты.

С точки зрения ЭКОНОР ШИ оборудования расчетные формулы для-вычисления остатков oif,+ ,ил:л,1 1А1р„ 2 записываются в виде

П . Q«iiLplr l-±i|p +LT IP IP

iPn..,i2)

С.Г.,

I 1-Гх1 p. I Al4n-ll n -i

рг

.2:|Р; ПРп,2М1лР1Р„..1Р.

oi.

п+2-Ь7 1Ч 1п.21 1 п+2п+1. ( ) Реализация устройством формул (3) и (4) осуществляется следующим образом.

Цифра Xi (i 1, 2, . . . ,n) числа А через выход i-ro подрегистра входного регистра 1 подается на вход i-ro блока группы 2, на выходах которого формируются вычеты |Р, 5,- 1 Рп + 2и|-а;-|Р 1Р„ которые с первого и второго выходов подаются на i-ые входы сумматоров 6 и 7 соответственно. В то же время индекс 1д числа А выхода регистра интервального индекса поступает на входы блоков 9 и 5. В результате из них считываются соответственно величины j и1-1д1Рп41 , которые поступают на соответствующие входы соответственно сумматоров 6 и 7.

Сумматоры 6 и 7 производят суммирование согласно формул (3.) и (4) . Для окончательного формирования вычета«п41 результат суммирования в блоке б с второго выхода поступает на вход блока 8 для умножения на -Р по модулю Р( + . Искомое значение oiifi с выхода блока 8 передается на вход регистра 4 интервального индекса.

Вычет ос f, 21 представляющий собой К младших двоичных разрядов позиционного кода числа А, с выхода блока 7 поступает в К старших разрядов сдвигового регистра 10, разрядность которого составляет тК бит, где

1 I +1 (4 Р)С Г г -л г

J (через xt:

m

обозначается не1именьшее целое число, не меньшее X).

Второй этап процедуры перевода числа А в двоичный код состоит из т-1 одинаковых шагов, на j-oM из которых (J 1,2,..., т-1) преобразователь выполняет следующее действие.

Содержимое сдвигового регистра 10 сдвигается на бит вправо, а содержимое входного регистра 1, представляютее собой вектор вычетов ) . . . ,об| о п+л) полученный на пре(О) --. If

СО)

( ос х..

ai-.

.(Х.

, . . . ,,

, SntJ. через

ВЫХОДЫ своих подрегистров подается на первые входы сумматоров группы 3, на вторые входы, которых с выхода блока 7 поступает остаток

(01

). В реCoi

nf 2

2

зультате i-ый сумматор группы 3 (i 1,2,...,п ) определяет величину

i ip-.)

(iV. - f 064

P, a (п+1)-ый сум ntl

4-1) (i-«) «n+i o n+i матор - величину

hti)

nt2

которая через первый вйход передается на (п+1)-ый вход блока 5.

Дополнительный код по модулю Р найденной величины с первого выхода блока 5 поступает на первый вход блока 8, где окончательно формируется величина , по формуле

-; ( ,,,li-)

J П4.-1 - Ob П42

11-PlP,

iPntzlP.

ti+ij

n+u

p p + 2

которая с выхода блока 8 передается в регистр 4 интервального индекса.

Вычет oi. через первый выход i-ro сумматора группы 3 Ci 1,2,...,п) пересылается в i-ый подрегистр регистра 1, а через второй выход подается на вход i-ro блока группы 2. В результате блоки 2,7 и 6 определяют величины

h

(i),

..

,(J)

U)

|(. ч

-|Pn.,lP,

11 о i

n-n

n+iin+i

F

Вычет Tj формируется на втором выходе блока б, откуда поступает на вход блока 9 для определения величины jfj/P|P j , которая с выхода блока 9 передается на (п+1)-ый вход сумматора 7. В результате на выходе сумматора 7 формируется вычет оС j |Pj-t-|fjP|Pn,5|Pn.j/ двоичное представление которого совпадает с очередныт м млгодшими двоичными разрядами дополнительного кода числа А по модулю 2q .

Таким образом, введение в состав устройства регистра интервального индекса, сдвигового регистра и трех блоков хранения констант интервального индекса позволяет при сохранении достаточно высокого быстродейстВИЯ сократить объем оборудования преобразователя.

Формула изобретения Преобразователь кода из систе ы остаточных классов в двоичный код,

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

вторые - к вторым входам блоков хранения констант, первые выходы которых подключены к- соответствующим п входам сумматора по модулю р, а вторые - к сс ответствующим п входам сумматора по модулю р,, (п+1)ый вход сумматора по модулю р„ подключен к первому выходу (п+1)-го сумматора группы, второй выход которого подключен к второму входу первого блока хранения констант интервального индекса, первый выход которого подключен к первому входу второго блока хранения констант интервального индекса, а второй - к (п+2) му входу сумматора по модулю Pn+i первый выход которого подключен к второму входу второго блока хранения констант интервального индекса, а второй - к первому входу третьего блока хранения констант интервального индекса, второй вход которого подключен к первому входу первого блока хранения констант интервального индекса, а выход подключен к (п-«-1)-му входу сумматора по модулю

Источники информации,

принятые во внимание при экспертизе

1.Авторское свидетельство СССР № 554536, кл.С 06 F 5/02, 1977.

2.Авторское свидетельство СССР № 328448, кл.С 06 F 5/02, 1970 (прототип),