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

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

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

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

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

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

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

где A(z)=(α₁(z), α₂(z), …, α_n(z)) - результат вычислений в модулярном коде, представленный в системе оснований p₁(z), p₂(z), …, p_n(z)

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

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

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

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

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

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

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

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

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

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

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

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

где $$P\left(z\right)={\prod }_{i=1}^n{p}_i\left(z\right)$$ - рабочий диапазон.

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

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

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

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

Пример. Пусть задана упорядоченная система оснований p₁(z)=z+1, p₂(z)=z²+z+1, p₃(z)=z⁴+z³+z²+z+1.

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

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

P₁(z)=p₂(z)*p₃(z)=(z²+z+1)*(z⁴+z³+z²+z+1)=z⁶+z⁴+z³+z²+1

P₂(z)=p₁(z)*p₃(z)=(z+1)*(z⁴+z³+z²+z+1)=z⁵+1

P₃(z)=p₁(z)*p₂(z)=(z+1)*(z²+z+1)=z³+1

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

Тогда имеем

m₁(z)=1;

m₂(z)=z+1;

m₃(z)=z²+z+1.

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

B₁(z)=m₁(z)*P₁(z)=z⁶+z⁴+z³+z²+1;

B₂(z)=m₂(z)*P₂(z)=z⁶+z⁵+z+1;

B₃(z)=m₃(z)*P₃(z)=z⁵+z⁴+z³+z²+z+1.

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

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

p_n+1(z)=p₄(z)=z⁴+z+1

Вычислим значения P_i(z)modp₄(z)

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

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

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

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

Устройство содержит вход устройства 1, первый блок умножителей 2, который содержит n умножителей по модулю p_i(z), где i=1, 2, …, n, первый блок памяти 3, для хранения ортогональных весов m_i(z); второй блок умножителей 4, который содержит n умножителей по модулю p_n+1(z), второй блок памяти 5 для хранения $${\left|P_i\left(z\right)\right|}_{p_{n+1\left(z\right)}}^{+}$$ , сумматор 6 по модулю два, выход устройства 7.

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

Устройство работает следующим образом. На вход устройства 1 поступает модулярный код (α₁(z), α₂(z), …, α_n(z)). Остаток α_i(z) подается на вход умножителя 2.i первого блока умножителей 2. На второй вход умножителя 2.i подается вес ортогонального базиса m_i(z) с выхода первого блока памяти 3. С выхода умножителя 2.i первого блока 2 умножителей снимаются значения $${\left|({\alpha }_i\left(z\right)\ast m_i\left(z\right)\right|}_{p_i\left(z\right)}^{+}$$ . Это значение подается на первый вход умножителя 4.i, выполняющего умножение по модулю p_n+1(z). На второй вход умножителя 4.i второго блока умножителей 4 подается значение $${\left|P_i\left(z\right)\right|}_{p_{n+1}\left(z\right)}^{+}$$ с выхода второго блока памяти 5. С выхода умножителя 4.i, второго блока умножителей 4 снимаем значение

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

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

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