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

15

И

п

(Я

Изобретение относится к вычислительной технике и является усовершенствованием устройства по авт. св. N 902013. Его использование в вычислительных устройствах, работающих в системе остаточных классов, позволяет расширить область применения за счет преобразования целых комплексных чисел в вычет по целому комплексному модулю. Преобразователь содержит входной регистр 1, шифраторы 2 двоичного кода в код по модулю и сумматор 3 по модулю. Благодаря введению блоков 4, 5 коммутации, блоков 6, 7 умножения действительной и мнимой частей, накапливающего модульного сумматора 8 и блоков 9, 10 преобразования кодов действительной и мнимой частей в преобразователе реализуется новый алгоритм вычисления остатка целого комплексного числа по целому комплексному модулю. 3 ил.

4

О) 00

с со

N)

Физ.1

Изобретение относится к вычислительной технике, является усовершенствованием устройства по авт. св. № 902013 и может быть использовано в вычислительных устройствах, работающих в системе остаточных классов. (СОК).

Цель изобретения - расширение области применения за счет преобразо- ю вания целых комплексных чисел в вычет по целому комплексному модулю.

На фиг. 1 приведена блок-схема преобразователя; на фиг. 2 и 3 - таблицы, поясняющие алгоритм работы пре- 15 образователя.

Преобразователь Двоичного кода в код по модулю содержит входной регистр 1, шифраторы 2 двоичного кода в код по модулю, сумматор 3 по моду- 20 лю, первый и второй блоки 4 и 5 коммутации, блок 6 умножения действительней части,- бло к 7 умножения мнимой части, накапливающий модульный

Пусть

ap+bq Zmod(p2 +q2) bp-aq Vmod(p2 +q2) Тогда

xp+yq

урУмножив первое уравнение системы (5) на q, а второе на р, сложив их и выразив у, получим

(6)

э+ycpZ }

(4)

(5)

Zq+Vp

/ --- -

(7)

Аналогично определяем Zp-Vq

y -- - --

X P2+q2

Геометрической интерпретацией решения системы (5) является пересечение двух отрезков, длина которых ограничена величиной модуля комплексного числа, следовательно, достаточно получить только одно из значений Z или V, а затем, составив таблицу соответствия, получить другое значение, а далее искомые величины у и х. Колисумматор 8, блок 9 преобразования ко- 25 чество возможных пар х и у для дакно- да действительной части, блок 10 преобразования кода мнимой части, входы 11 и 12 действительной и мнимой частей, управляющий вход 13, выходы 14 и 15 действительной и мнимой час- 30 тей.

го основания СОК постоянно и равно (p2+q 2).

Пример. Пусть комплексный модуль , где qf2, тогда p2+q2 13. Следовательно, ,12 и ,1 2. Таблица значений у, рассчитанных в зависимости от комбинаций V и Z по формуле (6), представлена на фиг. 2, где пустым клеткам соответствуют дробные значения величины у, что выходит за пределы решаемой задачи.

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

Пусть - целое комплексное число, подлежащее преобразованию, - целый комплексный модуль, В x+yi - наименьший вычет, равный наименьшему целому положительному остатку от деления числа А на число т.

Деление А на т дает следующий результат :

L21bi aЈ+bq ,

m p4-qi p2+q2 pz+qz1 Ч

)1

М

(2)

на т,

Если т - целое число, то можно Зписать

ap+bq 0mod(p2 +q2

bp-aq 0raod(p2 +q2

Если А не делится нацело существует такое В, что А-В делится нацело на т. Тогда получив разность А.-В, разделив ее на in по правилу (1 и приведя к виду (2), получим

ap+bq(xp+yq)mod(p2 +q2

bp-aq(yp-xq)mod(p2 +qs где .

Для определения х и у необходимо решить два уравнения с двумя неизвестными.

.ШУЧ

I2)

1)|

(3)

ть

ap+bq Zmod(p2 +q2) bp-aq Vmod(p2 +q2)

xp+yq

урв первое уравнение системы (5) а второе на р, сложив их и выу, получим

(6)

э+ycpZ }

(4)

(5)

Zq+Vp

/ --- -

(7)

Аналогично определяем Zp-Vq

y -- - --

X P2+q2

Геометрической интерпретацией решения системы (5) является пересечение двух отрезков, длина которых ограничена величиной модуля комплексного числа, следовательно, достаточно получить только одно из значений Z или V, а затем, составив таблицу соответствия, получить другое значение, а далее искомые величины у и х. Количество возможных пар х и у для дакно-

го основания СОК постоянно и равно (p2+q 2).

Пример. Пусть комплексный модуль , где qf2, тогда p2+q2 13. Следовательно, ,12 и ,1 2. Таблица значений у, рассчитанных в зависимости от комбинаций V и Z по формуле (6), представлена на фиг. 2, где пустым клеткам соответствуют дробные значения величины у, что выходит за пределы решаемой задачи.

Аналогичная таблица составляется

для расчета значения х. На фиг. 3

представлена сводная таблица соответ- ствия значений Z, у, х. Пусть необходимо найти В от числа А 29+81, где . Но формуле (4) определим Z:

Z ap+bq(29mod13x3+8mod13x2)mod13 12mod13. Но таблице на фиг. 3 определим величины х и у, соответствующие . Получим . Таким образом, .

Если полученный результат является верным, то должны выполняться два условия: разность А-В должна нацело делиться на p2+q2; модуль комплексного числа В не должен превышать в еличины р2 +q2 .

Используя формулу (1), разделим разность на га: А-В 29+81-2-31

пГ 3+21

7-31.

7-3i - целое комплексное число, т.е. первое условие выполняется.

2г- +3г 13 Ј р2 +q2 1 3 - второе условие выполняется. Следовательно, полу- ченный результат является верным.

Блок 6 умножения реализует операцию умножения величины amod(p2+q2) на константу р по модулю (p2+q2). Блок 7 реализует операцию умножения величины bmod(p2+q2) на константу q по модулю (p2+q2). Нлок 9 преобразует значение величины Z в величину х согласно сводной таблицы соответствия (подобная таблица для модуля показана на фиг. 3). Блок 10 преобразует значение величины Z в величину у согласно сводной таблице. Сумматор 8 производит суммирование по модулю

(p2+q2).

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

В исходном состоянии блоки 4 и 5 коммутируют входы 11 и блок 6, сумматор 8 обнулен. На выходах 14 и 15 нули. На входы 11 и 12 подаются соответственно величины а и Ь. Шифраторы 2 и сумматор 3 преобразуют величину а (целую часть комплексного числа)

в величину a amod(p2+q2), которая

35

подается на входы блока 6.

По окончании переходного процесса на выходе блока 6 устанавливается величина a1- pmod(p2 +q2) , которая складывается с нулем накапливающего сумматора 8.

Затем блоки 4 и 5 переключаются в иное положение, при этом величина b преобразуется в вычет по модулю Ъ1 bmod(p2+q2) .40

На выходе блока 7 устанавливается величина b « qmod(p2+q2), которая складывается с содержимым сумматора 8, на выходах которого появляется результат. 45

a .p+b1 (p2+q2) .

Блоки 9 и 10 преобразуют величину Z в величины х и у по вышеизложенному алгоритму.

Таким образом, предлагаемый преоб- разователь позволяет преобразовать

комплексные числа в вычет по целому комплексному модулю.

Так как целые действительные числа являются подмножеством цеяых комплексных чисел вида при , рассматриваемый преобразователь преобразует и действительные числа в вычет по комплексному модулю, а на выходах сумматора 3 формируется вычет по целому действительному модулю, равному (p2+q2).

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

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

О

U

о

Л

nt-iXtsf. a&xatffis

Редактор И.Рыбченко

Составитель 00Ревинский

Техред Л.Олийнык Корректор М.Васильева

Заказ 2852/56

Тираж 884

ВНИИПИ Государственно о комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва,, Ж-35, Раушская нзб., д. 4/5

11

11

ч

3

II

о

Подписное