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



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

 


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

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

Изобретение относится к вычислительной технике и, в частности, к непозиционным компьютерным системам, и предназначено для обеспечения требуемой точности при вычислении с использованием модулярного кода. Техническим результатом является снижение аппаратных затрат на выполнение операции расширения оснований в полиномиальном модулярном коде. Устройство расширения оснований модулярного кода характеризуется тем, что вход устройства, на который подается модулярный полиномиальный код 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 ил.

 

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

Одним из основных достоинств полиномиального модулярного кода (ПМК) является параллельная обработка данных по основаниям ПМК p1(z), p2(z), …, pn(z), где pi(z) - неприводимый полином поля GF(2). Данное свойство полиномиального модулярного кода позволяет не только повысить скорость обработки данных за счет использования малоразрядных остатков, но и обеспечить построение отказоустойчивых вычислительных систем.

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

При расширении набора оснований полиномиального модулярного кода на основании pn+1(z) диапазон представления чисел

Расширяется до значения

Задача расширения системы оснований заключается в нахождении остатка αn+1(z) по модулю pn+1(z), удовлетворяющего

где A(z)=(α1(z), α2(z), …, αn(z)) - результат вычислений в модулярном коде, представленный в системе оснований p1(z), p2(z), …, pn(z)

В работе [1] (Червяков Н.И., Сахнюк П.А., Шапошников А.В., Макоха А.Н. Нейрокомпьютеры в остаточных классах. Кн.11. - М.: Радиотехника, 2003, 272 с. - С.138-139) представлен алгоритм реализации процедуры расширения системы оснований.

В основу данного алгоритма положена китайская теорема об остатках (КТО), с помощью которой осуществляется перевод из модулярного кода в позиционный код

где Bi - ортогональный базис i-го основания; rA(z) - ранг A(z) в модулярном коде.

Тогда для вычисления остатка αn+1(z) справедливо выражение ([1 с.138])

Таким образом, для расширения системы оснований необходимо:

1. Вычислить значение ранга rA(z)

где ; mi(z) - вес ортогонального базиса;

2. Найти остаток αn+1(z) по формуле (5).

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

Целью изобретения является уменьшение аппаратных затрат на вычисление остатка αn+1(z). Цель достигается за счет применения нового алгоритма расширения системы оснований.

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

Рассмотрим алгоритм перевода из полиномиального модулярного кода в позиционный код согласно китайской теореме об остатках (КТО), имеем

где P ( z ) = i = 1 n p i ( z ) - рабочий диапазон.

Воспользуемся определением ортогональных базисов Bi(z), тогда выражение (7) можно представить в виде

где ; mi(z) - вес ортогонального базиса.

Умножение остатка αi(z) на вес ортогонального базиса mi(z) по модулю pi(z) с учетом, что суммирование в ПКМ выполняется по модулю два, позволяют отказаться от вычисления ранга rA(z) при использовании китайской теоремы об остатках при переводе к позиционному коду.

Тогда для вычисления нового остатка αn+1(z) по основанию pn+1(z) воспользуемся следующим выражением:

Пример. Пусть задана упорядоченная система оснований p1(z)=z+1, p2(z)=z2+z+1, p3(z)=z4+z3+z2+z+1.

В этом случае диапазон составляет

Вычислим значения Pi(z) и mi(z). Имеем

P1(z)=p2(z)*p3(z)=(z2+z+1)*(z4+z3+z2+z+1)=z6+z4+z3+z2+1

P2(z)=p1(z)*p3(z)=(z+1)*(z4+z3+z2+z+1)=z5+1

P3(z)=p1(z)*p2(z)=(z+1)*(z2+z+1)=z3+1

Вычислим значение веса ортогонального базиса mi(z) из условия

Тогда имеем

m1(z)=1;

m2(z)=z+1;

m3(z)=z2+z+1.

Следовательно, ортогональные базисы такой системы оснований равны

B1(z)=m1(z)*P1(z)=z6+z4+z3+z2+1;

B2(z)=m2(z)*P2(z)=z6+z5+z+1;

B3(z)=m3(z)*P3(z)=z5+z4+z3+z2+z+1.

Пусть задан полином A(z)=z6. Данный полином в модулярном коде представляется A(z)=(1, 1, z).

В качестве основания расширения выбираем

pn+1(z)=p4(z)=z4+z+1

Вычислим значения Pi(z)modp4(z)

Определим произведение

Подставим полученные значения в выражение (9)

Определим остаток

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

Устройство содержит вход устройства 1, первый блок умножителей 2, который содержит n умножителей по модулю pi(z), где i=1, 2, …, n, первый блок памяти 3, для хранения ортогональных весов mi(z); второй блок умножителей 4, который содержит n умножителей по модулю pn+1(z), второй блок памяти 5 для хранения | P i ( z ) | p n + 1 ( z ) + , сумматор 6 по модулю два, выход устройства 7.

Причем вход устройства 1 подключен к первому входу каждого из умножителей pi(z), i=1, …, n, (обозначение диапазона) первого блока умножителей 2, вторые входы умножителей этого блока подключены к выходу первого блока памяти 3. Выход умножителя 2.i, выполняющего операцию умножения по модулю pi(z) первого блока умножителей 2, подключен к первому входу умножителя 4.i, выполняющего операцию умножения по модулю pn+1(z), второго блока умножителей 4. Второй вход умножителя 4.i второго блока умножителей 4 подключен к входу второго блока памяти 5. Выход умножителя 4.i подается на вход сумматора 6 по модулю 2, выход которого является выходом устройства 7.

Устройство работает следующим образом. На вход устройства 1 поступает модулярный код (α1(z), α2(z), …, αn(z)). Остаток αi(z) подается на вход умножителя 2.i первого блока умножителей 2. На второй вход умножителя 2.i подается вес ортогонального базиса mi(z) с выхода первого блока памяти 3. С выхода умножителя 2.i первого блока 2 умножителей снимаются значения | ( α i ( z ) m i ( z ) | p i ( z ) + . Это значение подается на первый вход умножителя 4.i, выполняющего умножение по модулю pn+1(z). На второй вход умножителя 4.i второго блока умножителей 4 подается значение | P i ( z ) | p n + 1 ( z ) + с выхода второго блока памяти 5. С выхода умножителя 4.i, второго блока умножителей 4 снимаем значение

Вычисленные значения произведения подаются на входы сумматора 6 по модулю 2. На входе сумматора 6 по модулю два появляется значение остатка αn+1(z) в расширенной системе оснований. Вычисленное значение остатка αn+1(z)поступает на выход устройства 7.

Устройство расширения оснований модулярного кода отличается тем, что вход устройства, на который подается модулярный полиномиальный код 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) подключен к выходу второго блока памяти, выходы умножителей второго блока умножителей подсоединены к входам сумматора по модулю два, выход которого является выходом устройства.



 

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к области шифрования сообщений на основе использования точек на эллиптической кривой. Технический результат - повышение надежности криптографического шифрования за счет выполнения аутентификации и идентификации за одно и то же время. Способ выполнения аутентификации пароля или идентификации идентификатора с использованием криптографического преобразования включает этапы, на которых выполняют криптографическое преобразование в электронном компоненте для получения точки Р (Х, 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 ил.

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