Патент на изобретение №2246753

(54) УСТРОЙСТВО ДЛЯ МАСШТАБИРОВАНИЯ ЧИСЛА В МОДУЛЯРНОЙ СИСТЕМЕ СЧИСЛЕНИЯ

(57) Реферат:

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

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

Известно устройство (аналог) (авт. св. СССР №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· m_j)mod m_n 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· m_j двухвходовых элементов “И”, представляет собой матричный дешифратор, на вход которого поступают два операнда в унитарном коде. Элементы “И” находятся в местах пересечения шин данных операндов в унитарном коде, соответствующих результату двухместной операции (5) или (6), а выходы элементов “И” объединяются в соответствующих элементах “ИЛИ”, число которых равно m_n. Поскольку логический сигнал в таком табличном вычислителе распространяется через два логических элемента, время вычисления q_n,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 m_n и (d_j· _n,j· _j)mod m_n, которые поступают на Вых 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 (при in), а на Вх 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 m_n и (d_n· _n,n· _n)mod m_n, которые поступают на Вых 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₁₂· ( ₁– ₂))mod m₁=(2· (1-0))mod 3=2;

₁₃=(R₁₃· ( ₁– ₃))mod m₁=(1· (1-2))mod 3=2;

₁₄=(R₁₄· ( ₁– ₄))mod m₁=(2· (1-1))mod 3=0;

₁₂=(R₁₂· ( ₁– ₂))mod m₁=(2· (2-3))mod 3=1;

₁₃=(R₁₃· ( ₁– ₃))mod m₁=(1· (2-4))mod 3=1;

₁₄=(r₁₄· ( ₁– ₄))mod m₁=(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· ₁)mod m₁ и (d_j· _1,j· _j)mod m₁

(d₂· _1,2· ₁)mod m₁=((-4)· 2· 2)mod 3=2;

(d₃· _1,3· ₁)mod m₁=(2· 2· 2)mod 3=2;

(d₄· _1,4· ₁)mod m₁=(2· 0· 2)mod 3=0;

(d₂· _1,2· ₂)mod m₁=((-4)· 1· 0)mod 3=0;

(d₃· _1,3· ₃)mod m₁=(2· 1· 2)mod 3=1;

(d₄· _1,4· ₄)mod m₁=(2· 1· 1)mod 3=2.

Далее остаток (d_j· _1,j· ₁) mod m₁ поступает на Вых 1, а остаток (d_j· _1,j· _j)mod m₁ – на Вых 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· ₁)mod m₁=(1· 0· 2)mod 3=0, которое поступает на Вых 1 устройства вычисления остатка 4.1.1.

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

b₁ 2; b₂ 0; b₃ 1; _1,1=0;

(d₁· _1,1· ₁)modm₁=(1· 0· 1)mod3=0.

Рассчитанное значение (d₁· _1,1· ₁)mod m₁ подается на Вых 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 с.

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

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

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

Устройство для масштабирования числа в модулярной системе счисления (МСС), содержащее входной регистр, 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 m_n, _n,j=(R_nj· ( _n– _j))mod m_n, R_nj определяется из решения сравнения (R_nj· m_j)mod m_n 1, _j=A mod m_j, _n=A mod m_n, _j=В mod m_j, _n=B mod m_n, А и В – соответственно первый и второй целочисленные операнды, при этом второй табличный вычислитель предназначен для вычисления остатка q_{n, j}, причем

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

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

причем четвертый и пятый табличные вычислители предназначены для вычисления значений (d_j· _n,j· _n)mod m_n и (d_j· _n,j· _j)mod m_n, при этом n-й вход первого операнда соединен с первым входом первого и второго табличных вычислителей, а n-й вход второго операнда – с первым входом третьего и четвертого табличного вычислителя, j-й вход первого операнда – со вторым входом первого табличного вычислителя и первым входом пятого табличного вычислителя, j-й вход второго операнда – со вторыми входами второго и третьего табличных вычислителей, выходы первого и третьего табличных вычислителей подключены соответственно ко вторым входам четвертого и пятого табличных вычислителей, выход четвертого табличного вычислителя является первым выходом j-го устройства вычисления остатка по n-му основанию, выход второго табличного вычислителя – вторым выходом j-го устройства вычисления остатка по n-му основанию, а выход пятого табличного вычислителя – третьим выходом j-го устройства вычисления остатка по n-му основанию, при этом n-е устройство вычисления остатка по n-му основанию содержит три вычислительных блока для вычисления остатков q_n,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-го блока вычисления остатка.

РИСУНКИ

MM4A Досрочное прекращение действия патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе

Дата прекращения действия патента: 31.12.2005

Извещение опубликовано: 27.01.2007 БИ: 03/2007