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

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

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

Недостатком данного устройства является низкое быстродействие.

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

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

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

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

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

Сущность изобретения заключается в получении остатков произведения целого числа А и рационального числа b, представленного в виде дроби где В - целое число.

При этом считается, что числа А и В представлены модулярными кодами: А=(α ₁, α ₂,... , α _N), В=(β ₁, β ₂,... , β _n); α _i=A mod m_i; β _i=В mod m_i; m_i - совокупность взаимно простых целых чисел; М - диапазон представления чисел в МСС

В основу функционирования предлагаемого устройства положены следующие принципы. На основании теоремы о делении на произведение взаимно простых целых чисел [1, с.145] произведение произвольного целого числа А на произвольное рациональное число может быть представлено в виде суммы

в которой целые числа d_j определяются как решение уравнения:

В МСС все переменные, а также результаты арифметических операций должны быть целочисленными [1, с.12]. Поэтому результат масштабирования (1) необходимо привести к целому числу путем округления частного. С этой целью представим сумму в (1) в следующей эквивалентной форме:

Отметим, что выражения под знаком первой суммы в правой части формулы (2) всегда приводят к целым числам. Тогда округленное значение частного (1) может быть вычислено с помощью приближенного соотношения:

где - символ округления до ближайшего целого числа.

Численный расчет (3) для 0≤ А<М и 0≤ В<М показывает, что в 67% случаев получается точный результат, а в 33% - отличается на ± 1. То есть это не хуже, чем в аналогичных арифметических устройствах, функционирующих в позиционной системе счисления.

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

где

R_nj определяется из решения сравнения (R_nj·_{mj)mod mn≡ 1.}

Для нахождения остатков γ _n,n и δ _n,n может быть применен подход, изложенный в [2, с.8-9].

Согласно этому подходу учтем, что для 0≤ А<М и 0≤ В<М всегда справедливы неравенства:

Так как единственным условием при выборе МСС является взаимная простота ее оснований [1, с.13], то нумерация этих оснований может быть произвольной. Соответственно при определении остатков частных и основания могут перенумеровываться таким образом, чтобы основанию m_n соответствовал номер N в новой системе: Тогда в полиадическом коде частных и старший разряд кода будет равен нулю, а остатки γ _n,n и δ _n,n могут быть вычислены по формулам [2, с.8]:

где a_r и b_r - r-ый разряд полиадического кода частных и определяемый в соответствии с [3, с.21-22] выражениями:

Здесь находится из решения сравнения

Таким образом, алгоритм расчета модулярного кода частного состоит в получении для всех n остатков по формуле (4).

Для расчета этих остатков вычисляются 3N значений q_n,j, γ _n,j и δ _n,jпо формулам (5), (6) и (8), которые затем суммируются по модулю m_n.

Значения γ _n,j и δ _n,j (n, n≠ j), а также q_n,jмогут быть определены в табличных вычислителях, подобных описанным в [3, с.16-17]. Такой табличный вычислитель, содержащий m_n·_{mj двухвходовых элементов "И", представляет собой матричный дешифратор, на вход которого поступают два операнда в унитарном коде. Элементы "И" находятся в местах пересечения шин данных операндов в унитарном коде, соответствующих результату двухместной операции (5) или (6), а выходы элементов "И" объединяются в соответствующих элементах "ИЛИ", число которых равно mn. Поскольку логический сигнал в таком табличном вычислителе распространяется через два логических элемента, время вычисления qn,j, γ n,j и δ n,j будет равно}

где τ _ЛЭ - время задержки в логическом элементе.

Для сложения 3N чисел по модулю m_n может быть применен сумматор, описанный в [патент РФ №2188448, МПК G 06 F 7/72, Б.И. №24, 2002 г.], который содержит управляемые фазовращатели, генератор гармонического сигнала, фазовращатели на фиксированное значение фазы и измеритель фазы гармонического сигнала. Время сложения 3N чисел в таком сумматоре будет равно

При выводе формулы (11) полагалось, что частота генератора гармонического сигнала равна 100 ГГц, а время принятия решения о значении модульной операции -10^-10 с.

Для получения разрядов полиадического кода a_r и b_r (9) может быть применено устройство для преобразования чисел из кода системы остаточных классов в полиадический код, описанное в [патент РФ №2187886, МПК Н 03 М 7/18, Б.И. №23, 2002 г.], которое содержит входные регистры, генератор гармонического сигнала, управляемые фазовращатели и измерители фазы гармонического сигнала. Время получения разрядов полиадического кода в таком преобразователе будет равно

При выводе формулы (12) полагалось, что частота генератора гармонического сигнала равна 100 ГГц, время принятия решения о значении модульной операции -10^-10 с, а время коммутации управляемых фазовращателей -10^-11 c.

Получение остатков γ _n,n и γ _n,n может быть осуществлено в вычислительном блоке, содержащем табличные вычислители значений γ _n,j и δ _n,j (n, n≠ j) (6), устройство для преобразования чисел из кода системы остаточных классов в полиадический код, устройства отображения, осуществляющие унарные преобразования и сумматор N-1 чисел по модулю m_n. Структурная схема такого вычислительного блока приведена в [2, с.8, рис.1]. Полученная в [2, с. 10] оценка времени расчета остатков γ _n,n и δ _n,n составляет 3· 10^-9 с.

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

В прототипе время получения результата масштабирования равно

где ][ - символ округления в большую сторону; t_МТ - длительность модульного такта устройства.

При оценке значения t_МТ учтем, что основные функциональные элементы прототипа (регистры, сумматоры, счетчики и т.п.) содержат от 10 до 50 и более логических элементов. Соответственно время задержки логического сигнала в этих функциональных элементах может достигать более 50τ _ЛЭ. Поскольку t_МТ не может быть меньше наибольшего времени задержки логического сигнала в функциональных элементах прототипа, то примем

t_мт≈ 50τ _ЛЭ.

Тогда

Будем считать, что минимальное время задержки в логическом элементе составляет τ _ЛЭ≈ 10^-10 с [4, с.173].

В предлагаемом устройстве время вычисления Т_ПУ остатка результата округления частного по основанию m_nскладывается из времени определения остатков γ _n,n(δ _n,n)-3· 10^-9 с, времени расчета остатков γ _n,j, δ _n,jи q_n,jс и времени суммирования 3N чисел - τ _3N={(3N+3)· 10^-11+10^-10}, с.

Например, при N=6 получаем

Т_ПР=50· 10^-10·^{(3+3)=30· 10-9 с=30 нс;}

T_ПУ=3· 10^-9+2· 10^-10+(18+3)· 10^-11+10^-10≈ 3,5 нс.

Структурная схема устройства для масштабирования числа в модулярной системе счисления представлена на фиг.1.

В данной схеме Вх 1.1-Вх 1.N и Вх 2.1-Вх 2.N (N - число оснований МСС) - входы первого (А) и второго (В) операндов, соответственно 1 - входной регистр, 2.1-2.N - блоки вычисления остатков, 3.1-3.N - выходы устройства.

Входы операндов А и В соединены с информационными входами Вх 1.1-Вх 1.N и Вх 2.1-Вх 2.N входного регистра 1 соответственно. Выходы Вых 1.1-Вых 1.N и Вых 2.1-Вых 2.N входного регистра 1 подключены ко входам Вх 1.1-Вх 1.N и Вх 2.1-Вх 2.N блоков вычисления остатков 2.1-2.N, выходы которых подключены к соответствующим выходам устройства 3.1-3.N.

Реализация основных узлов устройства для масштабирования числа в модулярной системе счисления приведена на фиг.2-5.

На фиг.2 представлена структурная схема n-ого блока вычисления остатка 2.n, где Вх 1.1-Вх 1.N и Вх 2.1-Вх 2.N - входы блока вычисления остатка, 4.1.n-4.N.n - устройства вычисления остатка по n-ому основанию, 5 - сумматор 3N чисел по модулю m_n, 3.n - выход n-го блока вычисления остатка.

На фиг.3 представлена структурная схема j-го устройства вычисления остатка по n-ому основанию где Вх 1.n, Вх 2.n, Вх 1.j и Вх 2.j - входы устройства, 8.1-8.5 - табличные вычислители, Вых 1-Вых 3 - выходы устройства вычисления остатка по n-ому основанию.

На фиг.4 представлена структурная схема n-го устройства вычисления остатка по n-ому основанию, где Вх 1.1-Вх 1.N и Вх 2.1-Вх 2.N -входы устройства, 6.1-6.3 - вычислительные блоки, 7.1-7.2 - блоки умножения, Вых 1-Вых 3 - выходы n-го устройства вычисления остатка по n-ому основанию.

На фиг.5 представлена структурная схема вычислительного блока 6.1 (6.2). В данной схеме Вх 1.1-Вх 1.N и Вх 2.1-Вх 2.N - входы вычислительного блока, 9.1-9.(N-1) - табличные вычислители, 10 - устройство для преобразования чисел из кода системы остаточных классов в полиадический код, 11.1-11.(N-1) - устройства отображения, 12 - сумматор (N-1) чисел по модулю m_n.

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

Остатки (α ₁, α ₂,... ,α _N) операнда А и остатки (β ₁, β ₂,... ,β _N) операнда В в МСС подаются на информационные входы Вх 1.1-Вх 1.N и Вх 2.1-Вх 2.N соответственно и записываются во входной регистр 1. С выходов Вых 1.1-Вых 1.N и Вых 2.1-Вых 2.N входного регистра остатки α _j и β _jв унитарном коде поступают на соответствующие входы блоков вычисления остатков 2.1.-2.N.

В j-ом устройстве вычисления остатка по n-ому основанию 4.j.n остаток α _j (со входа Вх 1.j) поступает на Вх 1 табличного вычислителя 8.5 и Вх 2 табличного вычислителя 8.1, остаток α _n (со входа Вх 1.n) - на Вх 1 табличных вычислителей 8.1 и 8.2, остаток β _j (со входа Вх 2.j) - на Вх 2 табличных вычислителей 8.2 и 8.3, а остаток β _n (со входа Вх 2.n) - на Вх 1 табличных вычислителей 8.3 и 8.4.

В табличных вычислителях 8.1 и 8.3 по формуле (6) соответственно рассчитываются остатки γ _n,j и δ _n,j, а в табличном вычислителе 8.2 по формуле (5) вычисляется остаток q_n,j, который поступает на Вых 2 устройства вычисления остатка 4.j.n.

Затем в табличных вычислителях 8.4 и 8.5 соответственно вычисляются слагаемые формулы (4): (d_j·_{γ n,j·β n)mod mn и (dj·δ n,j·α j)mod mn, которые поступают на Вых 1 и Вых 3 устройства вычисления остатка 4.j.n.}

В n-ом устройстве вычисления остатка по n-ому основанию 4.n.n остатки α _i(со входов Вх 1.i) поступают на Вх 1.i вычислительного блока 6.1, остатки β _i(со входов Вх 2.i) поступают на Вх 2.i вычислительного блока 6.2, а остатки α _n и β _n (со входов Вх 1.n и Вх 2.n) - на Вх 1.n и Вх 2.n вычислительного блока 6.3. В вычислительном блоке 6.3 по формуле (5) рассчитывается остаток q_n,n, который поступает на Вых 3 устройства вычисления остатка 4.n.n.

В вычислительном блоке 6.1 остатки α _i ( i≠ n) со входов Вх 1.i поступают на Вх 2 табличных вычислителей 9.1 (при i<n) и 9.(i-1) (при i>n), а на Вх 1 этих табличных вычислителей поступает остаток α _n со входа Вх 1.n вычислительного блока.

Учитывая то, что в вычислительном блоке 6.1 основания m_kперенумерованы следующим образом: в табличных вычислителях 9.1-9.(N-1) вычисляются остатки где остаток равен остатку α _i в исходной системе оснований, номер которого - i соответствует номеру z в новой системе оснований.

С выходов табличных вычислителей 9.1-9.(N-1) остатки поступают на вход устройства преобразования чисел из кода системы остаточных классов в полиадический код - 10, где по формуле (9) вычисляются разряды a_rполиадического кода. Данные разряды с Вых 1-Вых (N-1) устройства преобразования 10 поступают на входы устройств отображения 11.1-11.(N-1), где соответственно осуществляются унарные преобразования а в сумматоре (N-1) чисел по модулю m_n 12 в соответствии с формулой (8) получается остаток γ _n,n.

Аналогичным образом при замене α _iна β _i в вычислительном блоке 6.2 рассчитывается остаток δ _n,n.

С выходов сумматоров 12 вычислительных блоков 6.1 и 6.2 остатки γ _n,n и δ _n,n поступают на Вх 1 первого (7.7) и второго (7.2) блоков умножения, на Вх 2 которых поступают соответственно остатки β _n (со входа Вх 2.n) и α _n (со входа Вх 1.n). В блоках умножения 7.1 и 7.2 соответственно получаются слагаемые формулы (4): (d_n·_{γ n,n·β n)mod mn и (dn·δ n,n·α n)mod mn, которые поступают на Вых 1 и Вых 2 устройства вычисления остатка 4.n.n.}

Данные с Вых 1-Вых 3 j-ого устройства вычисления остатка по n-ому основанию 4.j.n поступают соответственно Вх 1.j-Вх 3.j сумматора 3N чисел по модулю m_n, где по формуле (4) вычисляется остаток результата масштабирования который поступает на выход 3.n устройства для масштабирования числа в МСС.

Пример: Пусть заданы основания модулярной системы счисления: m₁=3, m₂=5, m₃=7, m₄=11 (N=4), в которой числа А=100 и В=578 представлены кодами: А=(1, 0, 2, 1); В=(2, 3, 4, 6). Диапазон представления чисел в такой МСС: а коэффициенты в формуле (4) принимают следующие значения: d₁=1, d₂=-4, d₃=2, d₄=2. Требуется найти модулярный код результата масштабирования частного

Рассмотрим работу предлагаемого устройства для приведенных выше исходных данных.

Коды операнда А=(1, 0, 2, 1) и операнда В=(2, 3, 4, 6) поступают на соответствующие входы Вх 1.1-Вх 1.4 и Вх 2.1-Вх 2.4 входного регистра 1. С выходов Вых 1.1-Вых 1.4 и Вых 2.1-Вых 2.4 входного регистра 1 операнды А и В поступают на соответствующие входы Вх 1.1-Вх 1.4 и Вх 2.1-Вх 2.4 блоков вычисления остатков 2.1-2.4.

Проиллюстрируем порядок вычисления остатка результата масштабирования на примере расчета остатка по первому основанию (m₁=3) в блоке вычисления остатка 2.1.

Коды операндов А и В со входов Вх 1.1-Вх 1.4 и Вх 2.1-Вх 2.4 блока вычисления остатка 2.1 поступают соответственно на входы Вх 1.1-Вх 1.4 и Вх 2.1-Вх 2.4 устройства вычисления остатка 4.1.1. При этом остатки α ₁ (со входа Вх 1.1) и β ₁ (со входа Вх 2.1) подаются на Вх 1.1 и Вх 2.1 устройств вычисления остатка 4.2.1-4.4.1. На Вх 1.j и Вх 2.j устройств вычисления остатка 4.j.1 соответственно поступают остатки α _j и β _j. В табличных вычислителях 8.2 устройств вычисления остатка 4.2.1-4.4.1 по формуле (5) вычисляются остатки

Данные остатки поступают на Вых 2 устройств вычисления остатка 4.2.1-4.4.1.

Одновременно в табличных вычислителях 8.1 и 8.3 устройств вычисления остатка 4.2.1-4.4.1 по формуле (6) определяются остатки γ _1,j и δ _1,j

γ ₁₂=(R₁₂·_{(α 1-α 2))mod m1=(2· (1-0))mod 3=2;}

γ ₁₃=(R₁₃·_{(α 1-α 3))mod m1=(1· (1-2))mod 3=2;}

γ ₁₄=(R₁₄·_{(α 1-α 4))mod m1=(2· (1-1))mod 3=0;}

δ ₁₂=(R₁₂·_{(β 1-β 2))mod m1=(2· (2-3))mod 3=1;}

δ ₁₃=(R₁₃·_{(β 1-β 3))mod m1=(1· (2-4))mod 3=1;}

δ ₁₄=(r₁₄·_{(β 1-β 4))mod m1=(2· (2-6))mod 3=1,}

где R₁₂=R₁₄=2; R₁₃=1.

Затем в табличных вычислителях 8.4 и 8.5 устройств вычисления остатка 4.2.1-4.4.1 рассчитываются остатки слагаемых в формуле (4) (d_j·_{γ 1,j·β 1)mod m1 и (dj·δ 1,j·α j)mod m1}

(d₂·_{γ 1,2·β 1)mod m1=((-4)· 2· 2)mod 3=2;}

(d₃·_{γ 1,3·β 1)mod m1=(2· 2· 2)mod 3=2;}

(d₄·_{γ 1,4·β 1)mod m1=(2· 0· 2)mod 3=0;}

(d₂·_{δ 1,2·α 2)mod m1=((-4)· 1· 0)mod 3=0;}

(d₃·_{δ 1,3· α 3)mod m1=(2· 1· 2)mod 3=1;}

(d₄·_{δ 1,4·α 4)mod m1=(2· 1· 1)mod 3=2.}

Далее остаток (d_j·_{γ 1,j·β 1) mod m1 поступает на Вых 1, а остаток (dj·δ 1,j·α j)mod m1 - на Вых 3 устройства вычисления остатка 4.j.1.}

В устройстве вычисления остатка 4.1.1 остатки α _i(со входов Вх 1.i) поступают на Вх 1.i вычислительного блока 6.1, остатки β _i(со входов Вх 2.i) поступают на Вх 2.i вычислительного блока 6.2, а остатки α ₁ и β ₁ (со входов Вх 1.1 и Вх 2.1) - на Вх 1.1 и Вх 2.1 вычислительного блока 6.3. В вычислительном блоке 6.3 по формуле (5) рассчитывается остаток

который поступает на Вых 3 устройства вычисления остатка 4.1.1.

В вычислительном блоке 6.1 остатки α _iсо входов Вх 1.i поступают на Вх 2 табличных вычислителей 9.i, а на Вх 1 этих табличных вычислителей поступает остаток α ₁ со входа Вх 1.1 вычислительного блока.

В вычислительном блоке 6.1 основания m_kперенумерованы следующим образом: Соответственно в табличных вычислителях 9.1-9.3 вычисляются остатки где, как уже отмечалось выше, остаток равен остатку α _i в исходной системе оснований, номер которого - i соответствует номеру z в новой системе оснований, то есть а коэффициенты принимают следующие значения:

С выходов табличных вычислителей 9.1-9.3 остатки поступают на вход устройства преобразования чисел из кода системы остаточных классов в полиадический код - 10, где по формуле (9) вычисляются разряды а_rполиадического кода:

Данные разряды с Вых 1-Вых 3 устройства преобразования 10 поступают на входы устройств отображения 11.1-11.3, где соответственно осуществляются унарные преобразования

Преобразованные числа в соответствии с формулой (8) складываются в сумматоре 12 трех чисел по модулю 3, где получается остаток γ _1,1=0, который поступает на Вх 1 блока умножения 7.1, а на Вх 2 этого блока умножения подается остаток β ₁ (со входа Вх 2.1). В блоке умножения 7.1 рассчитывается слагаемое формулы (4): (d₁·_{γ 1,1·β 1)mod m1=(1· 0· 2)mod 3=0, которое поступает на Вых 1 устройства вычисления остатка 4.1.1.}

Аналогичным путем при замене α _iна β _i в вычислительном блоке 6.2 рассчитывается остаток δ _1,1:

b₁→_{2; b2→0; b3→1; δ 1,1=0;}

(d₁·_{δ 1,1·α 1)modm1=(1· 0· 1)mod3=0.}

Рассчитанное значение (d₁·_{δ 1,1·α 1)mod m1 подается на Вых 2 устройства вычисления остатка 4.1.1.}

И, наконец, полученные данные с Вых 1-Вых 3 устройств вычисления остатков 4.j.n поступают соответственно Вх 1.j-Вх 3.j сумматора двенадцати чисел по модулю 3, где по формуле (4) вычисляется остаток результата масштабирования

μ ₁=(0+2+2+0+0+0+1+2+1+0+2+1)mod 3=2,

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

Аналогичным путем в блоках вычисления остатка 2.2 - 2.4 рассчитываются значения μ ₂=0; μ ₃=1; μ ₄=6.

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

Проверка:

ИСТОЧНИКИ ИНФОРМАЦИИ

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

2. Овчаренко Л.А., Лопатин Д.С. Деление числа в модулярном коде на основание системы счисления.// Телекоммуникации, 2002, №6, с.7-10.

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

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

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

Устройство для масштабирования числа в модулярной системе счисления (МСС), содержащее входной регистр, N входов первого и N входов второго операндов которого являются входами устройства (N - число оснований МСС), отличающееся тем, что в него введены N блоков вычисления остатков, выходы которых являются выходами устройства, причем i-й выход k-го операнда () входного регистра соединен с i-ми входами k-х операндов блоков вычисления остатков, при этом n-й блок вычисления остатка содержит N устройств вычисления остатка по n-му основанию и сумматор 3N чисел по модулю m_n (m_n - n-е основание МСС, ), причем j-е устройство вычисления остатка по n-му основанию ( j≠ n) содержит пять табличных вычислителей, причем первый и третий табличные вычислители предназначены для расчета остатков γ _n,j и δ _n,j, причем γ _n,j = (R_nj·_{(α n-α j))mod mn, δ n,j=(Rnj·(β n-β j))mod mn, Rnj определяется из решения сравнения (Rnj·mj)mod mn≡ 1, α j=A mod mj, α n=A mod mn, β j=В mod mj, β n=B mod mn, А и В - соответственно первый и второй целочисленные операнды, при этом второй табличный вычислитель предназначен для вычисления остатка qn, j, причем}

где - символ округления до ближайшего целого числа,

а целые числа d_j определяют как решение уравнения

причем четвертый и пятый табличные вычислители предназначены для вычисления значений (d_j·_{γ n,j·β n)mod mn и (dj·δ n,j·α j)mod mn, при этом n-й вход первого операнда соединен с первым входом первого и второго табличных вычислителей, а n-й вход второго операнда - с первым входом третьего и четвертого табличного вычислителя, j-й вход первого операнда - со вторым входом первого табличного вычислителя и первым входом пятого табличного вычислителя, j-й вход второго операнда - со вторыми входами второго и третьего табличных вычислителей, выходы первого и третьего табличных вычислителей подключены соответственно ко вторым входам четвертого и пятого табличных вычислителей, выход четвертого табличного вычислителя является первым выходом j-го устройства вычисления остатка по n-му основанию, выход второго табличного вычислителя - вторым выходом j-го устройства вычисления остатка по n-му основанию, а выход пятого табличного вычислителя - третьим выходом j-го устройства вычисления остатка по n-му основанию, при этом n-е устройство вычисления остатка по n-му основанию содержит три вычислительных блока для вычисления остатков qn,n, γ n,n, δ n, n и два блока умножения, причем}

где - символ округления до ближайшего целого числа, целые числа d_n определяются как решение уравнения

α _n=Amod m_n,

β _n=Bmod m_n,

А и В - соответственно первый и второй целочисленные операнды,

причем i-е входы () первого и второго операндов подключены соответственно к i-м входам () первого и второго вычислительных блоков, выходы которых соединены соответственно с первыми входами первого и второго блоков умножения, ко вторым входам которых подключены n-е входы второго и первого операндов соответственно, а ко входам третьего вычислительного блока подсоединены n-е входы первого и второго операндов, причем выходы первого и второго блоков умножения и выход третьего вычислительного блока являются, соответственно, первым, вторым и третьим выходами n-го устройства вычисления остатка по n-му основанию, при этом выходы устройств вычисления остатков подключены ко входам сумматора 3N чисел по модулю m_n, выход которого является выходом n-го блока вычисления остатка.