УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ЧИСЛА В МОДУЛЯРНОМ КОДЕ НА ОСНОВАНИЕ СИСТЕМЫ СЧИСЛЕНИЯ Российский патент 2004 года по МПК G06F7/72 H03M7/18 

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

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

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

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

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

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

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

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

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

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

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

где δ =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] такой фазовращатель наиболее просто реализовать на основе линий задержки (ЛЗ) на время

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

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

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

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

Выполнение операции деления числа А в модулярном коде на основание системы счисления p_N сводится к нахождению остатков частного по модулю p_k. Условием деления нацело числа А на p_N является выполнение сравнения [3, с.146 и 147], в противном случае можно рассматривать в качестве делимого число (A-α _N=A-Amodp_N), что эквивалентно округлению результата деления в меньшую сторону до ближайшего целого числа. Тогда [3, с.147] значения остатков модулярного кода частного ((A-α _N)/p_N) по основаниям р_n определяются формальным делением остатков (α _n-(α _N)modp_n) на число (p_Nmodp_n), то есть

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

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

где - вес k-гo разряда; p₁,p₂,... ,p_N - основания МCC; p₀=1.

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

Действительно, положим, что все разряды полиадического кода частного, за исключением последнего (N-го), равны максимальным значениям, то есть β _n=p_n-1, а β _N=0. Тогда в соответствии с (12) получим число, равное Следовательно, для представления в полиадическом коде частного ((A-α _N)/p_N) достаточно вычислить разряды β ₁,β ₂,... β _N-1, для получения которых необходимы только остатки γ ₁,γ ₂,... γ _N-1 модулярного кода [4, с.21 и 22].

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

β ₁=γ ₁,

где d_r=p_r-1; c_k,r - обратная мультипликативная величина [4, с.22], определяемая как решение сравнения (c_k,r· p)mod p_r≡_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), в которой р заменяется на p_n, а А_i - на величину соответствующего слагаемого из (14). Например, при расчете β ₂, первый управляемый фазовращатель сдвигает фазу на второй - на третий - на Так как μ ₂, d₂ и c_1,2 - константы, то сдвиг фазы зависит только от α ₂, α _N и β ₁.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Значения α ₁=1 и α ₂=1 через регистр 2 модулярного кода числа поступают на первые входы соответственно первого 3₁ и второго 3₂ табличных вычислителей, на второй вход которых поступает значение α ₃=5. В результате с выхода табличных вычислителей 3₁ и 3₂ на выходы 6₁ и 6₂ устройства поступают модулярные коды частного γ ₁ и γ ₂, значения которых соответственно определены в табличных вычислителях 3₁ и 3₂ по формуле (11):

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

Полиадический код с выхода устройства преобразования 4 модулярного кода в полиадический код поступает на вход сумматора 5 двух чисел по модулю p₃=7, где происходит вычисление остатка γ ₃ частного по формуле (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-1) табличный вычислитель (N - число оснований МСС), устройство преобразования модулярного кода в полиадический код, сумматор (N-1) чисел по модулю p_N (p_N - N-e основание МСС, на которое осуществляется деление). 1 ил.

Устройство для деления числа в модулярном коде на основание системы счисления, содержащее регистр модулярного кода числа, отличающееся тем, что в него введены N-l (N - число оснований модулярной системы счисления (МСС)) табличных вычислителей, предназначенных для вычисления остатков причем γ _n=(μ _n(α _n-(α _N)mod p_n))mod p_n, где α _n=A mod p_n; α _N=A mod p_N; А - целое число; р_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-м выходом устройства.}