Устройство для перевода числа, представленного в системе остаточных классов, в полиадическую систему счисления

Устройство для перевода числа, представленного в системе остаточных классов, в полиадическую систему счисления

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК (191 011 (g1)g Н 03 М 7/18

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

H ABTGPCH0MY СВИДЕТЕЛЬСТВУ

V yg

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

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

ПРИ ГКНТ СССР (61) 652556 (21) 4678091/24 (22) 11.04.89 (46) 07.01.91. Бюл. ¹ 1 (72) О.Н.: Фоменко, В.А. Краснобаев, В.П. Ирхин, В.М. Панков, А.А. Журавлев, С.И. Куцый и С.О. Гладченко (53) 681.3{088,8) (56) Авторское свидетельство СССР № 652556, кл. Н 03 М 7/18, 1976 °

2 (54) УСТРОЙСТВО ДЛЯ ПЕРЕВОДА ЧИСЛА, ПРЕДСТАВЛЕННОГО В СИСТЕМЕ ОСТАТОЧНЫХ

КЛАССОВ, В ПОЛИАДИЧЕСКУ .О CHCTENy СЧИСЛЕНИЯ (57) Изобретение является усовершенствованием устройства по авт. св. № 652556, относится K автоматике н вычислительной технике и может быть использовано B вычислительных машиI

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

Устройство содержит входные регистры

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

Изобретение относится к автоматике и вычислительной технике, в част.ности, к вычислительным машинам и устройствам, функционирующим в систе- 25 ме остаточных классов (СОК), и является усовершенствованием устройства по авт.св, 9 652556.

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

На фиг. 1 представлена схема устройства для перевода числа, представ-. 35 ленного в системе остаточных классов, в полиадическую систему счисления; на фиг,2 — пример реализации устройства для перевода числа, представленного в системе остаточных классов, 40 в полиадическую систему счисления дпя п=4. . Устройство содержит входные регистры 1-1 — 1-(3n+2) ° первую ступень матриц элементов И 2-1 — 2-п, первую группу элементов ИЛИ 3-1 — 3-и вторую ступень матриц элементов И 4-1

4-(и-1) ° вторую группу элементов ИЛИ

5-1 - 5(n-1), (n-1)-ю ступень матриц элементов И 6-1 и 6-2, (n-1)-ю группу элементов ИЛИ 7 -1 и 7-2, и-ю ступень матриц элементов И 8, и-ю группу элементов ИЛИ 9, элемент И,10, элемент ИЛИ 11, преобразователь 12-1 ,полиадического кода в двоичный, допол-.. э5 нительный преобразователь 12-2 полиадического кода в двоичный код, второй элемент ИЛИ-НЕ 13, первый дополнительный элемент И 14, второй дополватель 12-2 полиадического кода в двоичный код, второй 13 и первый 18 элементы ИЛИ-НЕ, первый 14 и второй

15 дополнительные элементы И, элемент НЕ 19, матрицу элементов И 20, блок 21 элементов ИЛИ, группу блоков

22 элементов ИЛИ и группу матриц элементов И 23 со связями. Устройство унифицировано для немодульных операций преобразования в двоичный код и расширения диапазона представления чисел, формирует признаки числа, 2 ил. нительный элемент И 15, выходы 16 и 17 признака минимального числа и признака максимального числа устройства соответственно, первый элемент ИЛИ-НЕ

18, элемент НЕ 19, матрицу элементов

И .20, блок 21 элементов ИЛИ группу блоков 22 элементов ИЛИ и группу матриц элементов И 23 °

Известное устройство позволяет осуществить расширение диапазона представления числа А в СОК, т.е ° по известным остаткам числа A=(g,,h ,...ф„), .соответствующим некоторым модулям Р,Р,...р,;.определяет знаь чение остатка p(n < этого же числа для другого основания Р „, (дополнительного). Если в качестве дополни" тельного основания р + выбрать число

Р,+, =Р Р,...,р„ =Р-!, где р, " основания. (i=1, и+1), Р -диапазон представления чисел в СОК, а .р, — вэаимопростые числа, то остаток по основанию р„„ равен двоичному коду числа, для которого получаем расширение диапазона.

Пусть остаток в СОК, основаниями которой выбраны числа P),Р,...,р„, задано числа А=(М, Ф,...,Фд), лежащее в интервале О,Р ). Необходимо найти вычетА„ по дополнительно введенному модулю. Для этого согласно алгоритму в разряде по модулю р„, остаток по которому необходимо получить, записывается 0; в разрядах по модулю

Р > и Рд+ параллельно вычисляются величины an i u Q (А n-q " коэффициент полиадической системы счисления), 1619403

Фв 0 1 — (modPn)- О(I s )

Р( (modP ) (n-z)

° ° ° ° ° n I (modP ) а

n-i (шос1Р ) Ы

? ( (и-2)

-а -, (modPn+1 )у

° ° ° В ° ° ° ° ° ° ° Ф ° ° ° ° ° ° ° ° ° (i-2) (i H) 01; — 0 -1 где 0 ; = - цля i=2,3...,n-l, 1-1 (о) приф, = IX",-, 20 ()(nyq = |(a Q) (шос)д nial ) ° Где ф 11 остаток числа А по основанию Г и+1 ф при = П р (mod p ), Таким образом можно получить двоич-25 ный позиционный код числа А, заданного в СОК из интервала (О, P-l), При ОСп =О возможны два случая.

Если остатки по каждому основанию равны нулю, то A=Î, но еслr tx 0, 30 а.остаток, например, по первому основанию не равен нулю, то А=Р-I, так как О(,+, =(Р-l)(mod(P-I))=0, Исходя из рассмотренного алгоритма, можно предположить, что при его технической

35 реализации возможно проведение ряда этапов двух различных немодульных операций на однотипных узлах устройства.

На фиг.1 в качестве основной сис- 4р темы взяты п оснований, соответствующие входным регистрам 1-i (i=1,п), в качестве дополнительных — соответ. ствует регистрам 1-(n+1), 1-(и+2).

Во входных регистрах по каждому осно- 45 ванию представлены остатки числа А.

Код числа А принимается на входные регистры 1-i. На входном регистре

1-(и+1) получаем расширение представ.ления числа А, на входном регист- 50 ре 1-(и+2) — двоичный позиционный код. числа. Функционирование устройства по передаче остатка в дополнительные регистры 1-(и+1), 1-(n+2) происходит по одному алгоритму поэто 55 му при рассмотрении работы устройства достаточно разобрать действия, кото.рые происходят при получении остатка по модулю Р„+ . Этот случай является предельным случаем расширения диапазона с некоторыми ограничениями, но позволяет с небольшими нарушениями однородности структуры устройства получить результат ещс одной немодульной операции. Сигналы на выходах элементов ИЛИ-НЕ 18 и 13 будут в том случае, когда остатки в соответствующих регистрах 1 — 1 и 1 †(и+2) будут равны нулю. Каждой матрицей элементов И 23 выполняется действие (Ы Ex )mod p,причем gn» М „,z=0 °

Каждый элемент ИЛИ 3 групп и блок 22 элементов ИЛИ выполняет действие: (О(, -g) mod p х(— -) а < и тд. Эле(i) мент И 1 0 определяет результат (а < -Q ) mo d p, а матрица элементов

hi(И 20 определяет результат (а z -Q)x

mod Р„ . Блок 21 элементов ИЛИ определяет P„XP . ° . Р„х(а,,-Q) я

Рассмотрим работу устройства (фиг.l) для двух случаев. Первый случай — при A=(I,Р-2), а второй при

A=0 и А=Р-I, В .первом случае устройство работает следующим образом. Код числа А, для которого нужно получить двоичный позиционный код (расширение по модулю р„+ =Р-1) поступает на регистры 1-i (i=l,n). С выхода этих ре-. гистров остатки по основаниям Р,Р

В Ф ...,p> поступают на соответствующие входы элементов И матриц первой ступени 2-j(j=l,n+1). Пройдя через усеченную матрицу элементов И, код исходного числа, преобразованный в полиадическую систему счисления по основаниям Р,Р ...,,Р„ и р„+,поступает на матрицу элементов И 20, с вы" хода которой через блок 21 элементов

ИЛИ поступает на вход преобразователя

1619403

7, 11, 209

А =

2, 3, l 2, -1, 1, О, 10, 208

О, 1, 3, 2, 4, О, 5, 104

О, 2, 5, 3, 102

1 1

Х

3 Р

4, 4, 1, 34

О, О, 8, 30

1 1 — — 1

5 Р

О, 6, 6

I 1 — Х

7 Р4

0 (mod 11)

0 (mod 209) 4, 180

12-2, преобразующего полиадический код числа А в остаток по основанию

Р,„ . С выхода преобразователя 12-2 остаток передается на входной регистр

1-(n+2). Это и будет двоичный позиционный код числа А. Одновременно с этим на входном регистре 1-(n+I) получаем вычет К д+,по другому дополнительному основанию аналогичным об- Ip разом.

При А=О, M = 0(„, = 3 с выходов элементов ИЛИ-НЕ 18 и 13 поступают сигна" лы на входы элемента И 14 и на выходе 16 признака минимального числа 6у- 15 дет сигнал. Если А=Р-I, то С1 $0> а

0(q g=0, тогда сигнал .будет на выходе

17 признака максимального числа.

Рассмотрим пример конкретного выполнения операциипреобразования кодов щ из системы остаточных классов в двоичный позиционный код, В качестве основной систе возьмем оснонания Р1=2, Р2=3, P =5, Р4=7, а в качестве дополнительных Pg=ll и P =2 3 5 7=209. В этом 25 случае P=210 — диапазон представления в данной СОК, Выбор (P-1)=Р =209 не случаен, ибо он объясняется требованием того, чтобы Рб и р (i=1,5) взаимно просты, а также тем, что в данном 3р случае легко определяются и соответственно технически реализуются следующие мультипликативные величины:

Остаток числа А по основанию P

1 — (mod 209)=3 5 7=105= —;

1 P

2 Р„

1 (mod 209)=2 3 7=42= — -;

Р

Р, 1

y (mod 209)=2 5 7=70= — ;

Р

Х (mod 209)=2.3 5=30=— .1 P

4

В этом случае о (mod 209)=l

Пример. Пусть необходимо определить двоичный позиционный код числа А=29, если А=(1,2,4,1), 1

На вход регистра 1-1 (фиг.2) поступает число 1, на вход регистра

1-2 — число 2, на вход регистра 1-3— число 4 и на вход регистра 1-4 — число l,разряды регистров 1-5 и 1 — 6 будут в нулевом состоянии. Дальнейшая записьпо определению вычитов.числа А по основаниям P =11 и Р =209 является в не6 которой степени формальной по отношению к фиг.2, но в достаточной степени отражает функционирование устройства при прохождении кода исходного числа

А через усеченную матрицу элементов И, не требуя более детальных схем устройства.

8 = П Р; (шосl Р„ ), тогда

1г!

g (mod 11) 210(mod 11)=1(mod 11);

1619403

Д (шой 209)=210(шой 209)=1(mod 209);

=1 (0-4) mod 11=7; ф 1 (0-18 ) mod 209=29.

6 5

Таким образом в шестом регистре 1-6 получают двоичный позиционный код числа А=29..

При А=(0,0,0,0)=0 на выходе 16 при16 знака минимального числа будет сигнал, а при А=(1,2,4,6)=210-1=209 будет сигнал на выходе 17. Использование устройства позволяет унифицировать немодульные операции СОК вЂ” расшире15

: ние диапазона представления чисел и преобразование в двоичный код.

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

Устройство для перевода числа, представленного в системе остаточных классов, в полиадическую систему счисления по авт. св. 9 652556, о тличающееся тем, что,сце- 25 лью расширения функциональных возможностей за счет преобразования числа, представленного в системе остаточных классов, в двоичный код, оно содержит (n+2)-й регистр, матрицу элемен- 30 тов И, блок элементов ИЛИ, первый и второй дополнительные элементы И, до.полнительный преобразователь полиадического кода в двоичный код, первый и второй элементы ИЛИ-НЕ и элемент

НЕ, группу матриц элементов И и группу блоков элементов ИЛИ, причем выходы разрядов первого входного регистра соединены с соответствующими входами первого элемента ИЛИ-НЕ, выход которого соединен с первым входом первого дополнительного элемента И и через элемент HE — с первым входом второго дополнительного элемента И, выход которого является выходом признака максимального числа устройства, выходы разрядов (и+2)-го входного регистра соединены с соответствующими входами второго элемента ИЛИ-НЕ, выход которого соединен с вторым входом второго ,дополнительного элемента И и с вторым

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

ИЛИ групп соединены соответственно с первыми группами входов матриц элементов И группы, выходы группы которых соединены с соответствующими входами блоков элементов ИЛИ группы, соответственно, выходы разрядов выхода k-го блока элементов ИЛИ (k=1...n-1) соединены с второй группой входов (1+1)-й матрицы элементов И группы, выход первого элемента ИЛИ (n-1)-й группы и выхода разрядов выхода последнего блока элементов ИЛИ группы соединены соответственно с первой и второй груп пами входов матрицы элементов И.

1619403

Число А РУ2. 2

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

Редактор H. Яцола Техред М.яндык

Корректор Т. Малец

Заказ 55 Тираж, Подписное

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

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

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