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

 

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

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

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

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

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

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

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

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

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

В основу функционирования предлагаемого устройства положены следующие принципы.

Признаком деления нацело числа А, представленного в модулярном коде A=(α ₁, α ₂,... , α _N) m_i - i-oe основание МСС), на основание m_N является равенство нулю сравнения α _N=Amodm_N ≡ 0 [1, с.146-147]. Если α _N ≠ 0, то можно рассматривать деление числа А-α _N=А-Amodm_N, что эквивалентно округлению результата деления до целого значения в меньшую сторону. Значения остатков γ _i модулярного кода частного (А-α _N)/m_N по основаниям определяются [1, с.147] делением их на число (m_N)modm_i, т.е.

где ρ _iN - заранее определяемая константа, которая находится из решения сравнения (ρ _iNm_N)modm_i ≡ 1. Данная операция легко реализуется в табличных вычислителях.

Основная проблема состоит в раскрытии неопределенности вида 0/0 при делении остатка по N-ому основанию на m_N. Данная неопределенность раскрывается следующим образом. Известно [1, с.12-13], что число А находится в диапазоне 0≤ A≤ M, где Тогда число (A-α _N)/m_N находится в диапазоне

С другой стороны, число (А-α _N)/m_N может быть представлено в полиадическом позиционном коде [2, с.21-22]

где - разряды полиадического кода

Разряды полиадического кода определяются по остаткам модулярного кода γ _i в соответствии с выражениями [2, с.21-22]

где ρ _k,r - обратная мультипликативная величина, определяемая из решения сравнения (ρ _r,k·m_k)modm_r ≡ 1; d_r=m_r-1;

Из анализа выражения (3) следует, что если β _N=0, а то максимальное значение числа в этом случае будет равно М/m_N-1. Таким образом, из (2), (3) и (4) следует, что в полиадическом коде числа (A-α _N)/m_N старший разряд β _N=0, а для определения разрядов необходимо знать только остатки результата деления числа (А-α _N)/m_N по основаниям m₁, m₂,... , m_N-1, которые могут быть вычислены в табличных вычислителях.

На основании изложенного выше получаем

Следовательно, расчет γ _N состоит в определении разрядов полиадического кода числа, код которого в МСС равен (γ ₁, γ ₂,... , γ _N-1), и суммировании по модулю m_N этих разрядов, умноженных на соответствующие весовые коэффициенты, по формуле (5).

Таким образом, сущность изобретения заключается в определении в (N-1) табличных вычислителях по основаниям остатков γ _j результата деления на основание m_N числа А, расчете остатка γ _N путем получения из остатков γ _j разрядов полиадического кода β _j, в преобразователе модулярного кода и сложении этих разрядов с учетом весовых коэффициентов в сумматоре (N-1) чисел по модулю m_N.

Для получения γ _N представим значения остатков (γ ₁, γ ₂,... , γ _N-1) числа (А-α _N)/m_N фазой гармонического сигнала. Суммируя фазы этого сигнала в соответствии с алгоритмом преобразования чисел из модулярного кода в полиадический (4), определяем разряды полиадического кода путем измерения суммарного набега фазы и затем, повторно кодируя фазы гармонического сигнала в соответствии со значениями разрядов полученного полиадического кода, определяем остаток γ _N, который будет прямо пропорционален суммарному набегу фазы.

Структурная схема устройства, реализующего изложенный алгоритм, представлена на фиг.1.

В данной схеме 1.1-1.N - входы устройства (N - число оснований МСС), 2 - регистр модулярного кода числа, 3.1-3.(N-1) - табличные вычислители, 4 - преобразователь модулярного кода в полиадический код, 5.1-5.(N-1) - устройства отображения, 6 - сумматор (N-1) чисел по модулю _N, 7.1-7.N - выходы устройства.

Входы устройства 1.1-1.N соединены с информационными входами Bx1-BxN регистра модулярного кода числа 2. Выходы 1-(N-1) регистра модулярного кода числа подключены ко входам 1 табличных вычислителей 3.1-3.(N-1) соответственно, а выход N регистра модулярного кода числа 2 соединен со входами 2 табличных вычислителей 3.1-3.(N-1), выходы которых подключены ко входам 1-(N-1) преобразователя модулярного кода в полиадический код 4, выходы 1-(N-1) которого через устройства отображения 5.1-5.(N-1) подключены ко входам 1-(N-1) сумматора по модулю m_N 6, выход которого является выходом устройства 7.N, а выходы табличных вычислителей 3.1-3.(N-1), соответственно, являются выходами 7.1-7.(N-1) устройства.

Реализация основных узлов устройства представлена на фиг.2 и 3.

На фиг.2 представлена структурная схема преобразователя модулярного кода в полиадический код 4, где – входы преобразователя, 8 - генератор гармонического сигнала, 9.1.1-9.(N-1).N - устройства отображения, 10.1.1-10.(N-1).N - управляемые фазовращатели, 11.1-11.(N-1) - измерители сдвига фазы, Вых к - выходы преобразователя.

На фиг.3 представлена структурная схема сумматора по модулю _N 6, где - входы устройства, 12 - генератор гармонического сигнала, 11.1-11.N - управляемые фазовращатели, 14.1-14.(m_N-1) – линии задержки на время (где - частота генератора гармонического сигнала), 15.1-15.m_N - аналоговые перемножители, 16.1-16.m_N - интеграторы, 17 - схема выбора максимума.

Рассмотрим работу устройства.

Остатки (α ₁, α ₂,... , α _N) числа А в МСС подаются на информационные входы 1.1-1.N и записываются в регистр модулярного кода числа 2. С выходов 1-(N-1) регистра модулярного кода числа остатки в унитарном коде поступают на первые входы табличных вычислителей 3.1-3.(N-1), на вторые входы которых поступает сигнал с выхода N регистра модулярного кода числа 2. В j-ых табличных вычислителях определяются остатки γ _j модулярного кода частного (А-α _N)/m_N по основаниям Полученные остатки поступают на выходы устройства 7.j и на соответствующие входы преобразователя модулярного кода числа в полиадический код 4, где сигнал со входа 1 следует непосредственно на выход 1 преобразователя и на входы устройств отображения 9.1.2-9.(N-1).2, а со входов 2-(N-1) на устройства отображения 9.1.1-9.(N-1).1. В устройствах отображения 9.j.1 в соответствии с формулой (4) осуществляется унарное преобразование а в устройствах отображения 9.j.2 - унарное преобразование Сигналы с выходов устройств отображения 9.j.1 и 9.j.2 поступают на Вх2 управляемых фазовращателей 10.1.j и 10.2.j соответственно, где устанавливаются набеги фазы, пропорциональные и Гармонический сигнал с выхода генератора 8 будет иметь на выходе УФ 10.1.2 суммарный набег фазы, прямо пропорциональный значению разряда полиадического кода β ₂. В измерителе сдвига фазы 11.1 эта фаза сравнивается с фазой опорного сигнала с выхода ГГС 8, и на выходе формируется унитарный код разряда

β ₂=((γ ₂ρ _2,1)modm₂+(d₂β ₁ρ _2,1)modm₂)modm₂,

который поступает на Вых2 преобразователя 4 и на устройства отображения 9.2.3-9.(N-1).3. Аналогично формируются разряды унитарного кода β ₃-β _(N-1), которые поступают на Bых3-(N-1) преобразователя 4 соответственно.

Сформированный полиадический код, через устройства отображения 5.j осуществляющих соответственно унарные преобразования

β ₁ → (β ₁)modm_N,

β ₂ → (β ₂·m₁)modm_N,...

β _N-1 → (β _N-1·m₁m₂...m_N-2)modm_N,

поступает на Bx1-Bx(N-1) сумматора (N-1) чисел по модулю m_N 6. В сумматоре 6 в управляемых фазовращателях 13.j устанавливаются соответствующие сдвиги фазы Δ ϕ _j:

После прохождения гармонического сигнала с выхода генератора 12 на выходе управляемого фазовращателя 13.(N-1) будет суммарный набег фазы

На выходах линий задержки 14.1 сдвиг фазы гармонического сигнала, соответственно, будет равен В результате перемножения в перемножителях 15.1-15.m_N гармонических сигналов с выхода управляемого фазовращателя 13.(N-1) и с выходов линий задержки 14.l и последующего интегрирования результатов произведения в интеграторах 16.1-16m_N образуются постоянные напряжения разного уровня. При этом максимальное напряжение будет на выходе интегратора 75.Z, где Z=γ _N+1. В схеме выбора максимума 17 определяется интегратор с наибольшим откликом и результат γ _N в унитарном коде поступает на выход сумматора 6, и, соответственно, на выход 7.N устройства.

Сравним быстродействие прототипа и предлагаемого устройства.

В прототипе время получения остатка равно

Т_ПР=(]log₂N[+2)·t_MT,

где ]• [ - символ округления в большую сторону; t_МТ - длительность модульного такта устройства, которая не может быть меньше длительности переключения логического элемента t_ЛЭ ≈ 10^-10С [3, с. 173]. Реально t_МТ на порядок больше t_ЛЭ, то есть t_МТ ≈ 10^-9С.

Таким образом, Т_ПР ≈ 10^-9·(]log₂N[+2), C.

В предлагаемом устройстве время вычисления модулярного кода частного Т_ПУ равно сумме времени расчета γ _j в табличных вычислителях - t_ТВ, времени получения разрядов полиадического кода в преобразователе 4 - t_МП и времени суммирования (N-1) чисел в сумматоре 6 - tΣ . Время получения γ _j в табличных вычислителях примерно равно времени переключения логического элемента: t_TB ≈ 10^-10C. Оценки времени t_МП и tΣ , полученные в [4, с.8-11, 5, с.40-44], описываются формулами

tΣ ≈ (N+3)T+10^-11, C;

t_МП=TN+(N-1)·3T+2N·τ _K, C,

где Т - период частоты генератора гармонического сигнала; τ _К - время коммутации управляемых фазовращателей.

Например, при N=6 и Т=τ _К=10^-11C получаем

Т_ПР=10^-9(3+2)=5·10^-9С.

Т_ПУ=t_ТВ+τ _МВ+tΣ =5,3·10^-10C.

Пример: Пусть N=3; m₁=5; m₂=7; m₃=3. Тогда ρ _1,3=2; ρ _l,2=3; ρ _2,3=5; d₂=6.

Найдем результат деления числа А=47=(2,5,2) на m₃=3.

В табличных вычислителях 3.1 и 3.2 по формуле (1) определяются

γ ₁=(ρ _1,3(α ₁-(α ₂)modm₁))modm₁=(2·(2-2))mod5=0;

γ ₂=(ρ _2,3(α ₂-(α ₃)modm₂))modm₂=(5·(5-2))mod7=1.

Данные числа поступают соответственно на выходы 7.1 и 7.2 устройства и на входы 1 и 2 преобразователя 4. В этом преобразователе β ₁=γ ₁=0, а β ₂ рассчитывается по формуле (4)

В устройствах отображения 5.1 и 5.2 осуществляется преобразование β ₁ → (β ₁)mod3=0 и β ₂ → (β ₂·5)mod3=0. Данные числа складываются в сумматоре 6:

γ ₃=(0+0)mod3=0.

Результат сложения поступает на выход 7.3 устройства.

Таким образом, модулярный код частного (А-α _N)/m_N=(0,1,0).

Проверка. (47-2)/3=15=(0,1,0).

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

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

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

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

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

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

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3