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



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

 


Владельцы патента RU 2503995:

Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Северо-Кавказский федеральный университет" (RU)

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

 

Изобретение относится к вычислительной технике и может быть использовано для определения знаков модулярных чисел, входящих в вычислительные устройства, функционирующие в системе остаточных классов. Известно устройство, для определения знаков числа, представленное в системе остаточных классов (А.С. № 1552181, БИ №11, 1990), состоящее из блока 1 определения номера интервала, схем 3 и 4 сравнения, элементов «или» 5 и 6. Однако данное устройство обладает следующими недостатками: низкое быстродействие и большие аппаратные затраты. Наиболее близким по технической сущности к заявленному устройству является устройство для определения знака числа, представленного в системе остаточных классов (А.С. № 1674121, БИ №32, 1991), содержащее блок определения номера интервала, схемы сравнения, группы шифрования и дешифрования, сумматор и логические элементы «или».

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

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

Поставленная цель достигается тем, что в известном устройстве введены просмотровые таблицы (LUT) и параллельный сумматор.

Рассмотрим метод определения знака числа, обладающий высоким быстродействием и низкими затратами оборудования. Суть метода быстрого определения знака модулярного числа основан на использовании китайской теореме об остатках числа, которая связывает позиционное число А с его представлениями в остатках (α1, α2, …, αn), где αi наименьшие неотрицательные остатки числа по модулям p1, p2, …, pn.

Цифры αi данного представления по выбранным модулям образуются следующим образом

где - целочисленное частное, pi - основания (модули) - взаимно-простые числа. В теории чисел доказано, что если ∀i≠j(pi, pj)=1, то представление (1) является единственным, при условии 0≤A<P, где - диапазон представления чисел, то есть существует число A, для которого:

Известна Китайская теорема об остатках, которая связывает позиционное число А с его представлением в остатках (α1, α2,…,αn), где αi - наименьшие неотрицательные вычеты числа, относительно модулей системы остаточных классов p1, p2, …, pn следующим выражением

где , pi - модули СОК, - мультипликативная инверсия Pi относительно pi, и .

Если (3) разделить на константу P, то получим приближенное значение

где - константы выбранной системы, а αi - разряды числа, представленного в СОК, при этом значение каждой суммы будет в интервале [0, 1). Конечный результат суммы определяется после суммирования и отбрасывания целой части числа с сохранением дробной части суммы. Дробная часть может быть записана также как Amod1, потому что . Количество разрядов дробной части числа определяется максимально возможной разностью между соседними числами. При необходимости точного сравнения необходимо вычислить значение (4), которое является эквивалентом преобразования из СОК в позиционную систему счисления. Для решения задач основных процедур принятия решения достаточно знать приблизительно значения чисел A и B по отношению к динамическому диапазону P, которое выполняется достаточно просто, но при этом правильно определяет соотношение A=B, A>B или A<B.

Рассмотрим случай, когда рабочий диапазон разбит на два интервала - положительные числа, и - отрицательные числа.

Известно, что при кодировании дополнительным кодом, отрицательная часть динамического диапазона находится у верхнего предела полного диапазона. Положительные числа из дополнительного диапазона отображаются на область при нечетных P и на область при четных P. Отображение динамического диапазона на соответствующую область для избыточного кода СОК показано на рисунке 1.

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

Для преодоления этой трудности необходимо произвести сдвиг отрицательной области путем вращения остаточного кольца в положение, указанное на рисунке 2. Пунктиром показана область, которая перенесена в начало диапазона.

В результате отрицательные числа будут отображены в начальной части динамического диапазона.

Показанное на рисунке 2 вращение, называется сдвигом полярности и его можно осуществить путем прибавления перед сравнением модулярных чисел константы при нечетном P или при четных P к каждому .

Если , то сдвиг полярности в пределах СОК оказывается простым остатком, определяемом по формуле , в которой αic обозначает остаточные цифры после сдвига полярности.

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

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

Определение знака модулярных чисел

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

В качестве второго машинного нуля выбирается точка числового диапазона . Числа, расположенные в поддиапазонах и считаются числами разных знаков.

Если дано представление (α1, α2,…,αn), то для того чтобы установить знак числа, которое оно представляет, достаточно решить задачу о принадлежности этого числа к определенному интервалу. В случае если pi=2 достаточно решить задачу о принадлежности этого числа к первой или второй половине диапазона . Эта задача решается сравнением данного представления с представлением , при условии, что p1=2. Все известные методы реализуют данный алгоритм на основе использования абсолютных величин, здесь же мы предлагаем использовать относительные величины, что существенно упрощает преобразование, сохраняя при этом основные функциональные возможности.

На рисунке 3 приведена схема устройства для определения знака модулярного числа по модулям p1, p2, …, pn.

Устройство состоит из входных регистров 3 по модулям p1, p2, …, pn, для временного хранения разрядов СОК (каждый разряд СОК представлен двоичным кодом), просмотровых таблиц (LUT) для хранения произведения констант разрядов СОК. , где мультипликативная инверсия, pi - модуль СОК, , , параллельного сумматора для суммирования входных шин 1 для подачи исходного числа, выходной шины для фиксирования знака числа и входа .

Работа устройства для определения знака модулярного числа определяется следующим образом.

На входные регистры (RGi) 3 по входам 1 устройства для определения знака числа подается исходное число, представленное в системе остаточных классов A=(α1, α2,…,αn). На выходе 2 формируется знак модулярного числа. Выходы регистров являются адресными входами просмотровых таблиц (LUT) (память), в элементах которых хранятся значения . С выходов 5 просмотровых таблиц 4 выбранные значения поступают на первые входы сумматора, а на второй вход 7 поступает значение . Результатом операции является знак числа 0 - положительное, 1 - отрицательное.

Код числа A, для которого необходимо определить интервал, что равносильно определению знака числа, поступает на входные регистры RGi в двоичном коде (каждый разряд СОК кодируется двоичным кодом). Сигналы с выходов регистров поступают на входы просмотровых таблиц LUT. В просмотровых таблицах хранятся произведения констант ki и остатков αi, то есть , представленных в естественной форме двоичной дроби в дополнительном коде. Количество элементов памяти (N) просмотровых таблиц определяется выражением .

Выходные сигналы просмотровых таблиц в дополнительном двоичном коде поступают на вход сумматора, в котором уже записана константа 0,5 во время начальной установки. (Дополнительный код используется для того, чтобы операцию вычитания заменить операцией сложения). Знак результата сложения определяет интервал: первый или второй, что соответственно определяет знак числа.

Пример 4. Пусть дана система оснований p1=2, p2=3, p3=5, p4=7. Тогда P=210. Константы ki соответственно равны k1=0,5, k2≈0,3333, k3=0,6, k4≈0,5714.

Дано число A=(1, 1, 2, 0). Требуется определить знак числа A.

Решение. В регистры RG1=1, RG2=1, RG3=2, RG4=0. В соответствии с этими значениями регистров (адресные входы LUT) на выходах которых формируются значения LUT1=0,5, LUT2=0,3333·1=0,3333, , LUT4=0.

Таким образом, при суммировании в знаковом разряде сумматора будет 0, что говорит о том, что число находится в первом интервале, поэтому , то есть число A - положительное.

Определение знака осуществляется за n суммировании, где n - число оснований (модулей) СОК. Время суммирования определяется логической глубиной устройства (количество последовательно соединенных элементов) и временем суммирования сумматора. Для уменьшения времени суммирования, схему сумматора можно реализовать по принципу дерева (рекурсивного сдваивания). Кроме того реализация сумматора может быть выполнена на искусственных нейронных сетях.

Устройство для определения знака модулярного числа, отличающееся тем, что в него введены входные регистры по модулям p1, p2, …, pn, для временного хранения разрядов СОК, параллельный сумматор для суммирования , входные шины для подачи исходного числа, просмотровые таблицы для хранения произведений констант разрядов СОК , представленных в двоичном коде, на входы которых поступают с выхода регистров двоичные коды разрядов СОК αi, выходы которых соединены с входами сумматора, на вторые входы которого поступает константа , выход которого является выходом устройства.



 

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

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

Изобретение относится к вычислительной технике и предназначено для построения быстродействующих параллельно-конвейерных умножителей. Техническим результатом является повышение скорости вычисления.

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

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

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

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

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

Изобретение относится к вычислительной технике. .

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

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

Изобретение относится к вычислительной технике и может быть использовано для выполнения операции умножения чисел, представленных в модулярно-позиционном формате с плавающей точкой на универсальных многоядерных процессорах. Техническим результатом является повышение скорости вычисления за счет замены операции умножения t-разрядных позиционных мантисс сомножителей n параллельно выполняемыми операциями умножения q-разрядных знакопозиций чисел в системе счисления в остаточных классах. Способ реализуется на универсальном многоядерном вычислителе, содержащем g k-разрядных вычислительных ядер, каждое из которых обеспечивает выполнение системы из f операций, в состав которых входят операции алгебраического умножения и алгебраического сложения над числами, представленными в позиционных целочисленных форматах данных. При организации выполнения операций умножения каждое число, множитель и множимое, представляется в модулярно-позиционном формате с плавающей точкой в виде (1+k+q·n) - элементного вектора.

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

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

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

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

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

Изобретение относится к вычислительной технике и, в частности, к непозиционным компьютерным системам, и предназначено для обеспечения требуемой точности при вычислении с использованием модулярного кода. Техническим результатом является снижение аппаратных затрат на выполнение операции расширения оснований в полиномиальном модулярном коде. Устройство расширения оснований модулярного кода характеризуется тем, что вход устройства, на который подается модулярный полиномиальный код A(z)=(α1(z), α2(z), …, αn(z)), где αi(z) - остатки по основанию pi(z), i=1, …, n, используемому в полиномиальном модулярном коде, подключается к первым входам умножителей по модулю pi(z) первого блока умножителей соответственно, а вторые входы этих умножителей соединены с выходами первого блока памяти, выход 2.i-го умножителя по модулю pi(z), первого блока умножителей подсоединен к первому входу 4.i-го умножителя по модулю pn+1(z) второго блока умножителей, при этом второй вход умножителя по модулю pn+1(z) подключен к выходу второго блока памяти, выходы умножителей второго блока умножителей подсоединены к входам сумматора по модулю два, выход которого является выходом устройства. 1 ил.

Изобретение относится к области шифрования сообщений на основе использования точек на эллиптической кривой. Технический результат - повышение надежности криптографического шифрования за счет выполнения аутентификации и идентификации за одно и то же время. Способ выполнения аутентификации пароля или идентификации идентификатора с использованием криптографического преобразования включает этапы, на которых выполняют криптографическое преобразование в электронном компоненте для получения точки Р (Х, Y) на эллиптической кривой исходя из по меньшей мере одного параметра t, связанного с указанным паролем или идентификатором; выполняют аутентификацию пароля или идентификацию идентификатора с использованием значений абсциссы (X) и ординаты (Y) полученной точки Р. 2 н. и 5 з.п. ф-лы, 3 ил.

Изобретение относится к вычислительной технике, в частности к модулярным нейрокомпьютерным средствам, и предназначено для вычисления коэффициентов обобщенной полиадической системы (ОПС), представленных в полях Галуа GF(2v). Техническим результатом является обеспечение возможности исправления ошибок в коэффициентах ОПС, которые были получены из кодовой комбинации, представленной в полиномиальной системе классов вычетов (ПСКВ). Устройство содержит двухслойную нейронную сеть, каждый слой которой содержит 15 нейронов, блок памяти и 7 корректирующих сумматоров по модулю два. 1 ил., 4 табл.

Изобретение относится к вычислительной технике и может быть использовано как специализированный вычислитель - универсальный в классе логических вычислений. Техническим результатом является уменьшение объемов оборудования. Устройство содержит коммутатор, 2k блоков памяти хранения значений коэффициентов полиномов разложения, 2n-k блоков памяти хранения значений вычетов возведения переменной в i-тую степень (i=0, 1, …, 2n-k-1) по модулю Р, многоканальный мультиплексор выделения группы коэффициентов, многоканальный мультиплексор выделения группы вычетов, 2n-k умножителей по модулю Ρ, сумматор по модулю Ρ, n входов подачи булевых переменных устройства, управляющий вход устройства подачи значения количества переменных разложения, управляющий вход устройства подачи значений коэффициентов, управляющий вход устройства подачи значений вычетов возведения переменной в i-тую степень по модулю Р, d выходов устройства выдачи значений булевых функций. 1 ил.
Наверх