Устройство для деления числа в модулярном коде на основание системы счисления

 

Устройство относится к вычислительной технике, предназначено для деления числа в модулярной системе счисления (МСС) на одно из ее оснований и может быть использовано в цифровых вычислительных устройствах. Техническим результатом является повышение быстродействия выполнения операции деления числа в модулярном коде на основание системы счисления. Технический результат достигается за счет того, что устройство содержит регистр модулярного кода числа, (N-1) табличный вычислитель (N - число оснований МСС), устройство преобразования модулярного кода в полиадический код, сумматор (N-1) чисел по модулю pN (pN - N-e основание МСС, на которое осуществляется деление). 1 ил.

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

Известно устройство (аналог) (Авторское свидетельство СССР №1683013, МКИ G 06 F 7/72, БИ №37, 1991 г.), содержащее регистры делимого и делителя, регистр сдвига, вспомогательный регистр, блок вычитания, блок умножения, блок сложения, параллельно-конвейерный формирователь, счетчик, элемент ИЛИ-НЕ, элементы И, элемент задержки, регистр частного и элемент ИЛИ.

Недостаток устройства - низкая скорость выполнения операции деления в МСС.

Наиболее близким по технической сущности (прототипом к предлагаемому изобретению) является устройство (Авторское свидетельство СССР №1667066, МКИ G 06 F 7/72, БИ №28, 1991 г.), содержащее блок элементов задержки, блок вычисления интервального индекса числа, элемент задержки, два регистра сдвига, регистр модулярного кода числа, регистр интервального индекса, два блока мультиплексоров, два блока хранения констант, блок управления и два блока элементов ИЛИ.

Недостаток прототипа - низкая скорость выполнения операции деления в МСС вследствие большого количества тактов, в ходе которых реализуется данная операция, и конечного времени переключения полупроводниковых логических вентилей, составляющих основу прототипа.

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

Технический результат выражается в повышении быстродействия (уменьшении временных затрат) выполнения операции деления числа в модулярном коде на основание системы счисления.

Технический результат достигается тем, что в устройство, содержащее регистр модулярного кода числа, введены (N-1) (N - число оснований МСС) табличных вычислителей, устройство преобразования модулярного кода в полиадический код и сумматор (N-1) чисел по модулю pN (pN - N-е основание МСС, на которое осуществляется деление), причем N входов регистра модулярного кода числа являются входами устройства, N выходов регистра модулярного кода числа соединены с соответствующими входами устройства преобразования модулярного кода в полиадический код, при этом n-й выход регистра модулярного кода числа подключен к первому входу n-го табличного вычислителя, а N-й выход регистра модулярного кода числа - ко вторым входам табличных вычислителей, выход n-го табличного вычислителя является n-м выходом устройства, n-й выход устройства преобразования модулярного кода в полиадический код соединен с соответствующим входом сумматора (N-1) чисел по модулю pN, выход которого является N-м выходом устройства.

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

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

Известно, что

где =1, 2, 3,...

Если гармонический сигнал с амплитудой U и частотой

проходит через m (m - число слагаемых) последовательно соединенных фазовращателей, то на выходе последнего (m-го) фазовращателя гармонический сигнал будет описываться выражением

где i - сдвиг фазы в i-м фазовращателе,

Положим, что в i-м фазовращателе сдвиг фазы i прямо пропорционален значению i-го слагаемого Аi

где р - величина модуля.

Тогда (3) с учетом (4) можно представить в виде

Так как

а в свою очередь

то на основании (3)-(6) получим

где [•] - символ округления в меньшую сторону до ближайшего целого.

Таким образом, после прохождения гармонического сигнала через m фазовращателей, сдвиги фазы в которых прямо пропорциональны значению слагаемых Аi фаза гармонического сигнала (7) на выходе m-го фазовращателя будет прямо пропорциональна значению модуля суммы m чисел:

Для определения (8) необходимо измерить разность фаз на выходе генератора гармонического сигнала и сигнала на выходе линейки фазовращателей:

Измеритель сдвига фазы можно построить на основе оптимального измерителя параметра сигнала известной формы [1, с.488, рис. 12.1], в котором опорные сигналы формируются из гармонического сигнала (2) путем сдвигов фазы на 0,

Необходимые для реализации устройства сложения m чисел по модулю p m фазовращателей должны быть управляемыми и могут быть реализованы на основе различных схемных решений. Например, в СВЧ-диапазоне [2, с.102] такой фазовращатель наиболее просто реализовать на основе линий задержки (ЛЗ) на время

где - несущая частота гармонического сигнала.

Если на входе ЛЗ на время ts действует гармонический сигнал (2), то на выходе ЛЗ с учетом (11) будет сигнал

то есть фаза сигнала uЛЗ(t) будет соответствовать (4) при s=Ai.

Следовательно, подключая линию задержки в соответствии с унитарным кодом слагаемого можно получить значение фазового сдвига в i-м управляемом фазовращателе, прямо пропорциональное величине этого слагаемого.

Выполнение операции деления числа А в модулярном коде на основание системы счисления pN сводится к нахождению остатков частного по модулю pk. Условием деления нацело числа А на pN является выполнение сравнения [3, с.146 и 147], в противном случае можно рассматривать в качестве делимого число (A- N=A-AmodpN), что эквивалентно округлению результата деления в меньшую сторону до ближайшего целого числа. Тогда [3, с.147] значения остатков модулярного кода частного ((A- N)/pN) по основаниям рn определяются формальным делением остатков ( n-( N)modpn) на число (pNmodpn), то есть

где находится из решения сравнения ( n pN)modpn 1. Неопределенность вида при вычислении остатка частного N по основанию рN раскрывается путем представления N, в полиадической позиционной системе счисления (ППСС) [4, с.21].

Произвольное число В в полиадической системе счисления представляется в виде последовательности разрядов 1, 2,... , N, при этом связь числа с значениями его разрядов характеризуется соотношением

где - вес k-гo разряда; p1,p2,... ,pN - основания МCC; p0=1.

При нахождении частного ((A- N)/pN) учтем, что 0 A<M, [3, с.12 и 13]. Тогда 0 ((A- N)/pN)<(M/p). В этом случае из выражения (12) следует, что в полиадическом коде числа ((A- N)/pN) старший разряд ( N) всегда будет равен нулю.

Действительно, положим, что все разряды полиадического кода частного, за исключением последнего (N-го), равны максимальным значениям, то есть n=pn-1, а N=0. Тогда в соответствии с (12) получим число, равное Следовательно, для представления в полиадическом коде частного ((A- N)/pN) достаточно вычислить разряды 1, 2,... N-1, для получения которых необходимы только остатки 1, 2,... N-1 модулярного кода [4, с.21 и 22].

Алгоритм [5, с.41] перевода числа ((A- N)/pN) из модулярного кода 1, 2,... N-1 в полиадический код заключается в последовательном вычислении значений начиная с младшего разряда (k=1), по формулам

1= 1,

где dr=pr-1; ck,r - обратная мультипликативная величина [4, с.22], определяемая как решение сравнения (ck,r p)mod pr 1;

Таким образом, остаток частного N по основанию рN можно определить по формуле

где разряды с учетом взаимосвязи k с k и N (11) определяются по формуле

где

Из (14) видно, что для получения n-го, , разряда n полиадического кода необходимо сложить (n+1) чисел по модулю рn. В соответствии с (1)-(9) устройство преобразования модулярного кода в полиадический код будет содержать сумматор (n+1) чисел, который может быть выполнен на основе устройства, включающего генератор гармонического сигнала (2), (n+1) управляемых фазовращателей и измеритель сдвига фазы. При этом выход генератора гармонического сигнала соединен с первым входом первого управляемого фазовращателя, выход i-го управляемого фазовращателя - с первым входом (n+1)-го управляемого фазовращателя, выход (n+1)-го управляемого фазовращателя подключен к первому входу измерителя сдвига фазы, на второй вход которого поступает сигнал с выхода генератора гармонического сигнала. При этом выход измерителя сдвига фазы является выходом сумматора, а на вторые входы управляемых фазовращателей поступают соответствующие слагаемые из выражения (14). Управляемые фазовращатели обеспечивают поворот фазы на величину, определяемую формулой (4), в которой р заменяется на pn, а Аi - на величину соответствующего слагаемого из (14). Например, при расчете 2, первый управляемый фазовращатель сдвигает фазу на второй - на третий - на Так как 2, d2 и c1,2 - константы, то сдвиг фазы зависит только от 2, N и 1.

Соответственно на второй вход первого управляемого фазовращателя поступают данные со второго выхода регистра модулярного кода числа, на второй вход второго управляемого фазовращателя - с N-го выхода регистра модулярного кода числа, на второй вход третьего управляемого фазовращателя - значение первого разряда 1 полиадического кода, снимаемое с выхода сумматора, в котором осуществляется расчет этого разряда. Примеры устройств, осуществляющих сложение (n+1) чисел по модулю pN, приведены в [5, с.41-44] и [6, с.10].

Аналогично вышеизложенному может быть построен сумматор (N-1) чисел по модулю рN. В этом сумматоре, в соответствии с выражением (13), в первом управляемом фазовращателе осуществляется сдвиг фазы на во втором - на в третьем - на и т.д.

Сравним быстродействие прототипа и предлагаемого устройства. Вычисление остатка от деления числа в МСС в прототипе происходит за (]log2N[+2) тактов. Следовательно, время выполнения операции деления в прототипе составляет

где - суммарное время переключения цифровых логических схем в блоке хранения констант прототипа, ]•[ - символ округления в большую сторону.

Основу узла, обеспечивающего операцию деления по модулю р в блоке хранения констант прототипа, составляет матричный дешифратор [4, с.16 и 17], построенный на двухвходовых элементах И, расположенных в местах пересечений р горизонтальных и р вертикальных входных шин. Выходы элементов И подключены к входу соответствующих элементов ИЛИ, число которых равно p. Таким образом, сигнал от входа к выходу в этом дешифраторе проходит через 2 логических элемента - И и ИЛИ. Поэтому

Как показано в [7, с.173], время ЛЭ 10-10 с является практическим пределом для логических элементов на транзисторах, которое достигается только при жидкостном охлаждении до криогенных температур.

Поэтому минимальное время выполнения операции деления по модулю в прототипе на основании (15) и (16) составляет

Время выполнения модульной операции в предлагаемом устройстве (ТПУ) будет равно:

где ТТВ - временной сдвиг в табличном вычислителе, ТПК - временной сдвиг в устройстве преобразования модулярного кода в полиадический код, Т - временной сдвиг в сумматоре (N-1) чисел по модулю pN.

Временной сдвиг ТТВ в табличном вычислителе, построенном по схеме матричного дешифратора, как было указано ранее в (16), составляет

В [5, с.43] и [6, с.11] показано, что при реализации входящего в состав сумматоров (n+1) чисел по модулю pn и сумматора (N-1) чисел по модулю pN генератора гармонического сигнала на частоте 400 ГГц, время ТПК может быть не более:

Поэтому максимальное время выполнения модульной операции в предлагаемом устройстве на основании (18)-(20) составляет (при N<62)

Из (17) и (21) видно, что предлагаемое устройство предпочтительнее прототипа, так как операция формирования остатка от деления числа в модулярном коде на основание системы счисления в предлагаемом устройстве происходит быстрее примерно в (]log2N[+2) раз.

На чертеже представлена структурная схема предлагаемого устройства, где 11-1N - информационные входы устройства, 2 - регистр модулярного кода числа, 31-3N-1 - табличные вычислители, 4 - устройство преобразования модулярного кода в полиадический код, 5 - сумматор (N-1) чисел по модулю pN, 61-6N - выходы устройства.

Вход регистра 2 модулярного кода числа соединен с входом 1k устройства, а n-й выход регистра 2 модулярного кода числа соединен с первым входом табличного вычислителя 3n, выход которого соединен с выходом 6n устройства, k-й выход регистра 2 модулярного кода числа соединен с k-м входом устройства преобразования 4 модулярного кода в полиадический код, а N-й выход регистра модулярного кода числа соединен со вторыми входами табличных вычислителей 31-3N-1, n-й выход устройства преобразования 4 модулярного кода в полиадический код соединен с n-м входом сумматора 5 (N-1) чисел по модулю рN, выход которого является выходом 6N устройства.

Рассмотрим работу устройства. Остаток делимого по модулю рk поступает на информационный вход 1k устройства и далее на вход Вхk регистра 2 модулярного кода числа, с выхода Выхk которого остаток k поступает на вход Вхk устройства преобразования 4 модулярного кода в полиадический код, где происходит преобразование по формуле (14). Полиадический код ( 1, 2,... n) остатка N от деления ((А- N)/рN) с выхода устройства преобразования 4 модулярного кода в полиадический код поступает на вход Вхn сумматора 5 (N-1) чисел по модулю рN, где, согласно выражению (13), происходит суммирование по модулю рN. С выхода сумматора 5 (N-1) чисел по модулю рN модулярный код остатка N поступает на выход 6N устройства. С выхода Выхn регистра 2 модулярного кода числа остаток n поступает на вход Вх1 табличного вычислителя 3n, на вход Вх2, которого поступает остаток N с выхода ВыхN регистра 2 модулярного кода числа. С выхода табличного вычислителя 3n, осуществляющего вычисление остатка n согласно выражению (11), модулярный код этого остатка поступает на выход 6n устройства.

Пример: Пусть основания МСС равны р1=3, р2=5, р3=7 (N=3). При этом заранее известны величины: с1,2,=2, d1=2, d2=4, 1=4, 2=3. Найдем результат деления числа А=61 ( 1=1, 2=1, 3=5) на основание МСС р3=7.

Значения 1=1 и 2=1 через регистр 2 модулярного кода числа поступают на первые входы соответственно первого 31 и второго 32 табличных вычислителей, на второй вход которых поступает значение 3=5. В результате с выхода табличных вычислителей 31 и 32 на выходы 61 и 62 устройства поступают модулярные коды частного 1 и 2, значения которых соответственно определены в табличных вычислителях 31 и 32 по формуле (11):

В то же время значения 1=1, 2=1 и 3=5 через регистр 2 модулярного кода числа поступают на соответствующие входы устройства преобразования 4 модулярного кода в полиадический код, в котором происходит вычисление разрядов полиадического кода числа ((А- 3)/р3) по формуле (14):

Полиадический код с выхода устройства преобразования 4 модулярного кода в полиадический код поступает на вход сумматора 5 двух чисел по модулю p3=7, где происходит вычисление остатка 3 частного по формуле (13):

Проверка:

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

1. Тихонов В.И. Статистическая радиотехника. - М.: Сов. радио, 1966, 678 с.

2. Радиоприемные устройства: Учеб. пособие для радиотехнич. спец. ВУЗов./ Ю.Т. Давыдов, Ю.С. Данилич. - М.: Высш. шк., 1989, 342 с.

3. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. - М.: Сов. радио, 1968. - 440 с.

4. Долгов А.И. Диагностика устройств, функционирующих в системе остаточных классов. - М.: Радио и связь, 1982, 64 с.

5. Овчаренко Л.А. Когерентный преобразователь модулярного кода. -Телекоммуникации, 2001, №6.

6. Овчаренко Л.А. Вариант реализации основных операций в модулярном арифметическом устройстве.// Телекоммуникации, №3, 2001, с.8-11.

7. Акаев А.А., Майоров С.А. Оптические методы обработки информации. - М.: Высш. шк., 1988, 237 с.

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

Устройство для деления числа в модулярном коде на основание системы счисления, содержащее регистр модулярного кода числа, отличающееся тем, что в него введены N-l (N - число оснований модулярной системы счисления (МСС)) табличных вычислителей, предназначенных для вычисления остатков причем n=( n( n-( N)mod pn))mod pn, где n=A mod pn; N=A mod pN; А - целое число; рn - n-е основание МСС; рN - N-e основание МСС, на которое осуществляется деление, а n находится из решения сравнения ( n pN)mod pn 1, устройство преобразования модулярного кода в полиадический код и сумматор N-1 чисел по модулю рN, причем N входов регистра модулярного кода числа являются входами устройства, N выходов регистра модулярного кода числа соединены с соответствующими входами устройства преобразования модулярного кода в полиадический код, при этом n-й выход регистра модулярного кода числа подключен к первому входу n-го табличного вычислителя, а N-й выход регистра модулярного кода числа - ко вторым входам табличных вычислителей, выход n-го табличного вычислителя является n-м выходом устройства, n-й выход устройства преобразования модулярного кода в полиадический код соединен с соответствующим входом сумматора N-1 чисел по модулю рN, выход которого является N-м выходом устройства.

РИСУНКИРисунок 1



 

Похожие патенты:

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

Изобретение относится к автоматике и вычислительной технике и может быть использовано при проектировании устройств преобразования цифрового кода числа А в системе остаточных классов (СОК) в напряжение в блоках сопряжения разнотипных элементов вычислительных и информационно-измерительных систем

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

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

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах для перевода чисел из кода системы остаточных классов (СОК) в код полиадической системы счисления (ПСС)

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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано в устройствах для формирования элементов конечных полей, в устройствах, функционирующих в СОК, а также в устройствах для формирования кодовых последовательностей, построение которых основывается на теории конечных полей

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

Изобретение относится к области автоматики и вычислительной техники и может быть использовано в вычислительных структурах, функционирующих в модулярной системе счисления (МСС)

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

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

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

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

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

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

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

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

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