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

(54) УСТРОЙСТВО ОБНАРУЖЕНИЯ И КОРРЕКЦИИ ОШИБОК В КОДАХ ПОЛИНОМИАЛЬНОЙ СИСТЕМЫ КЛАССОВ ВЫЧЕТОВ НА ОСНОВЕ НУЛЕВИЗАЦИИ

(57) Реферат:

Изобретение относится к вычислительной технике, в частности к модулярным нейрокомпьютерным средствам, и предназначено для выполнения операции поиска и коррекции ошибок в модулярных кодах полиномиальной системы классов вычетов (ПСКВ). Техническим результатом является повышение скорости обнаружения и коррекции ошибок в модулярных кодах ПСКВ. Указанный технический результат достигается за счет применения ПСКВ, в которой в качестве основания системы используется минимальные многочлены p_i(z), i=1, 2, …, 7, определенные в расширенных полях Галуа GF(2⁵) и нейросетевых технологий, а также параллельного применения модифицированных констант нулевизации, определяемых в данной ПСКВ. 2 ил., 7 табл.

Изобретение относится к вычислительной технике, в частности к модулярным нейрокомпьютерным средствам, и предназначено для выполнения операции поиска и коррекции ошибок в модулярных кодах полиноминальной системы классов вычетов (ПСКВ).

Целью изобретения является повышение, скорости определения местоположения и глубины ошибок в модулярном коде ПСКВ для коррекции результата на основе способа нулевизации. Цель достигается за счет перехода от последовательного характера выполнения операции нулевизации к параллельному вычитанию констант нулевизации, а также применению нейросетевого базиса и выполнению операций в полиномиальной системе классов вычетов расширенного поля Галуа GF(2).

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

Указанный технический результат достигается за счет применения полиномиальной системы классов вычетов (ПСКВ), в которой в качестве основания системы используются минимальные многочлены p_i(z), i=1, 2, …, k+r, определенные в расширенных полях Галуа GF(2), и нейросетевых технологий, а также параллельного применения модифицированных констант нулевизации, определяемых в данной ПСКВ.

Если в качестве оснований новой алгебраической системы выбрать минимальные многочлены p_i(z) поля GF(p), то любой полином A(z), удовлетворяющий условию

A(z)P_пол,

где

можно представить в виде n-мерного вектора

где , i=1, 2, …, k+r.

Так как сравнения по одному и тому же модулю можно почленно складывать, вычитать и умножать, то для суммы, разности и произведения двух полиномов A(z) и B(z), имеющих соответственно модулярные коды (₁(z),₂(z),…,_k+r(z)) и (₁(z),₂(z),…,_k+r(z)) справедливы соотношения:

Таким образом, выполнение операций над операндами в расширенном поле Галуа GF(р) производятся независимо по каждому из модулей p_i(z), что указывает на параллелизм данной алгебраической системы.

Кроме того, особенность ПСКВ состоит еще и в том, что независимость обработки информации по основаниям ПСКВ позволяет не только повысить скорость и точность обработки, но также и обеспечить обнаружение и коррекцию ошибок в процессе функционирования вычислительного устройства класса вычетов. Если на диапазон возможного изменения кодируемого множества полиномов наложить ограничения, то есть выбрать k из n оснований ПСКВ (kполн(z) расширенного поля Галуа GF(p) на два непересекающихся подмножества.),>

Первое подмножество называется рабочим диапазоном и определяется выражением

Многочлен A(z) с коэффициентами из поля GF(р) будет считаться разрешенным в том и только том случае, если он является элементом нулевого интервала полного диапазона P_полн(z), то есть принадлежит рабочему диапазону A(z)P_раб(z).

Второе подмножество GF(р), определяемое произведением r=n-k контрольных оснований

задает совокупность запрещенных комбинаций. Если A(z) является элементом второго подмножества, то считается, что данная комбинация содержит ошибку. Таким образом, местоположение полинома A(z) относительно двух данных подмножеств позволяет однозначно определить, является ли кодовая комбинация A(z)=(₁(z),₂(z),…,_k+r(z)) разрешенной, или содержит ошибочные символы.

Для определения местоположения A(z)=(₁(z), ₂(z),…, _k+r(z)) в работе (Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. – М.: Советское радио, 1968. – 439 с. (стр.193-194)) предложено использовать способ нулевизации, заключающийся в переходе от исходного полинома к полиному вида

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

Согласно этому способу нулевизация заключается в последовательном вычитании из исходного полинома, представленного в модулярном коде, некоторых минимальных полиномов – констант нулевизации таких, что полином A(z) последовательно преобразуется в полином вида

где – константа нулевизации по первому основанию p₁(z).

Затем из полученного результата вычитается следующая константа нулевизации для получения полинома

где по второму основанию p₂(z), и так далее. Продолжая данный процесс в течение k итераций, получается

Применение способа нулевизации позволяет последовательно получать наименьший полином, кратный сначала p₁(z), затем полином – кратный p₁(z)p₂(z), и в конечном итоге – кратный рабочему диапазону .

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

x_k+1(z)=0, x_k+2(z)=0,…,x_k+r(z)=0,

то это свидетельствует, что исходная комбинация A(z), представленная в модулярном коде, не содержит ошибок. В противном случае – модулярный код A(z) – содержит ошибки.

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

где

Повысить скорость выполнения-процедуры нулевизации можно за счет модификации констант нулевизации M_i(z). Оставляя неизменным условие невыхода константы нулевизации M_i(z) за пределы рабочего диапазона , возьмем в качестве последних значения произведение остатков рабочих оснований на величину ортогональных базисов безызбыточной системы оснований

где – ортогональный базис, безызбыточной системы оснований; i=1, 2, …, k.

Тогда если положить условие, что A(z)P_раб(z), где , то полином A(z)=(₁(z),₂(z)…,_k(z)) согласно китайской теореме об остатках (КТО) можно представить в виде

Каждое слагаемое выражения (9) представляет собой

Подставим выражения (8) в равенство (10). Получаем

Следовательно, значения остатков по контрольным основаниям будут определяться

Значит, разность полинома A(z) и модифицированных констант нулевизации M_i(z), i=1, 2, …, k, псевдоортогональных форм, полученных согласно (4.5), задает величину нормированного следа полинома

Исходя из условия, что модифицированные константы нулевизации M_i(z) представляют собой ортогональные базисы безызбыточной системы оснований ПСКВ, то операция нулевизации (13) может быть реализована параллельно.

Для уменьшения объема хранимых значений констант нулевизации M_i(z), i=1, 2, …, k, представим остатком числа _i(z) в виде

где элементы поля GF(2); j=0, 1, …, ordp_i(z)-1.

Тогда справедливо

Таким образом, вместо хранения констант нулевизации M_i(z) достаточно определить ordp_i(z) констант.

Рассмотрим ПСКВ, определяемую в поле GF(2⁵). В таблице 1 помещены значения рабочих и контрольных оснований ПСКВ, а также динамический диапазон для расширенного поля Галуа.

Ортогональные базисы безызбыточной системы оснований ПСКВ p₁(z), p₂(z), р₃(z), p₄(z), p₅(z) принимают следующие значения

B₁ ^*(z)=z²⁰+z¹⁹+z¹⁵+z¹⁴+z¹³+z¹⁰+z⁹+z⁷+z⁶+z²+1;

B₂ ^*(z)=z¹⁶+z⁸+z⁴+z²+z+1;

B₃ ^*(z)=z²⁰+z¹⁸+z¹⁶+z¹⁵+z¹⁴+z¹³+z¹²+z¹¹+z¹⁰+z⁶+z³+z;

B₄ ^*(z)=z¹⁹+z¹⁸+z¹⁶+z¹⁵+z¹⁴+z¹³+z⁸+z⁷+z⁶+z⁵+z⁴+z;

B_l ^*(z)=z¹⁶+z¹⁵+z¹⁴+z¹³+z¹²+z¹¹+z⁹+z⁶+z⁵+z³+z+1.

Определим все значения произведений степеней z^j на ортогональные базисы B_i ^*(z), учитывая невозможность выхода за пределы рабочего диапазона P_раб(z)=z²¹+z¹⁹+z¹⁶+z¹³+z¹¹+z⁹+z⁸+z⁶+z³+z²+z+1. Полученные значения модифицированных констант нулевизации представлены в таблице 2.

Таблица 2
Константы нулевизации для поля GF(25)
	1(z)	2(z)	3(z)	4(z)	5(z)	6(z)	7(z)
z0B1 *(z)	1	0	0	0	0	z2	z
z0B2 *(z)	0	1	0	0	0	1	1
z1B2 *(z)	0	z	0	0	0	z	z
z2B2 *(z)	0	z2	0	0	0	z2	z2
z3B2 *(z)	0	z3	0	0	0	z3	z3
z4B2 *(z)	0	z4	0	0	0	z4	z4
z0B3 *(z)	0	0	1	0	0	z4+z	z4+1
z1B3 *(z}	0	0	z	0	0	z3+z2+1	z3+z+1
z2B3 *(z)	0	0	z2	0	0	z4+z3+z	z4+z2+z
z3B3 *(z)	0	0	z3	0	0	z4+1	z+1
z4B3 *(z)	0	0	z4	0	0	z2+z+1	z2+z
z0B4 *(z)	0	0	0	1	0	z2	z+1
z1B4 *(z)	0	0	0	z	0	z3	z2+z
z2B4 *(z)	0	0	0	z2	0	z4+z3+z2	z3+z
z3B4 *(z)	0	0	0	z3	0	z4+z	z4+z2
z4B4 *(z)	0	0	0	z4	0	z3+z+1	z3+z2+1
z0B5 *(z)	0	0	0	0	1	z4+z	z4
z1B5 *(z)	0	0	0	0	z	1	z3+z2+z+1
z2B5 *(z)	0	0	0	0	z2	z	z4+z3+z2+z
z3B5 *(z)	0	0	0	0	z3	z2	z4+z+1
z4B5 *(z)	0	0	0	0	z4	z3	z3+1

Если в упорядоченной избыточной ПСКВ расширенного поля Галуа GF(p) для которой справедливо ord_p1(z)ordp₂(z)…ordp_k(z) для двух контрольных оснований p_k+1(z) и p_k+2(z) имеет место соотношение

то они определяют местоположение и величину ошибки по любому основанию.

Рассмотрим пример. Пусть в поле GF(2⁵), в котором определены рабочие и контрольные основания согласно таблице 1, задан – полином A(z)=z⁶+z⁵+z⁴+1, Данный полином принадлежит P_раб(z). Представим его в модулярном коде

A(z)=z⁶+z⁵+z⁴+1=(0,z³+z,z⁴+z³+z²+z+1,z²+z+1,z³+z+1,z⁴+z³+z²+z,0).

Проведем последовательно процедуру нулевизации. На первом этапе путем вычитания по модулю 2 получаем

Значение М₂(z) получено согласно выражению (15) путем суммирования значений

M₂(z)=z³B₂ ^*(z)+zB₂ ^*(z)=(0, z³, 0, 0, 0, z³, z³)+(0, z, 0, 0, 0, z, z)=(0, z³+z, 0, 0, 0, z³+z, z³+z).

На втором этапе нулевизации имеем

На третьем этапе нулевизации получаем

На четвертом этапе нулевизации имеем

Таким образом, полином A(z) не содержит ошибки.

Допустим ошибка произошла по первому основанию. Тогда имеем

A*(z)=(1, z³+z, z⁴+z³+z²+z+1, z²+z+1, z³+z+1,z⁴+z³+z²+z, 0).

Проведем последовательно процедуру нулевизации. На первом этапе путем вычитания по модулю 2 получаем

На втором этапе нулевизации имеем

На третьем этапе нулевизации получаем

На четвертом этапе нулевизации имеем

На четвертом этапе нулевизации имеем

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

В зависимости от величины синдрома ошибки осуществляется коррекция

где (0,…,_i(z),…,0) – вектор ошибки модулярного кода; _i(z) – глубина ошибки по i-му модулю; .

Согласно таблице 3, где приведена зависимость местоположения и глубины ошибки от результатов выполнения процедуры нулевизации, для полученного результата x₆(z)=z², x₇(z)=z имеем, что ошибка произошла по первому основанию и глубина равна 1. Тогда исходный полином имеет вид

A*(z)+(1, 0, 0, 0, 0, 0, 0)=(0, z³+z, z⁴+z³+z²+z+1, z²+z+1, z³+z+1, z⁴+z³+z²+z, 0).

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

Она включает: вход устройства 1, блок нулевизации 2, блок памяти 3, сумматоры 4, 5, 6, 7, 8, 9, 10, выход устройства 11.

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

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

A(z)=(₁(z), ₂(z), ₃(z), ₄(z), ₅(z), ₆(z), ₇(z)).

где _i(z) – остаток полинома A(z) по модулю p_i(z); p₁(z), р₂(z), p₃(z), p₄(z), p₅(z) – рабочие основания системы ПСКВ поля GF(2⁵); p₆(z), p₇(z) – контрольные основания. Вход устройства соединен с входами блока нулевизации 2. С выхода блока нулевизации вычисленные значения x₆(z), x₇(z) подаются на входы блока памяти 3 и выбирают оттуда соответствующую константу ошибки (0,…,_i(z),…,0), i=1, 2, 3, 4, 5, 6, 7. Эта константа ошибки поступает на вторые входы корректирующих сумматоров 4, 5, 6, 7, 8, 9, 10 соответственно по основаниям p₁(z), р₂(z), р₃(z), p₄(z), p₅(z), p₆(z), p₇(z), где суммируется с поступившими на первые входы значениями ₁(z), ₂(z), ₃(z), ₄(z), ₅(z), ₆(z), ₇(z), подаваемые со входа устройства 1. Исправленное значение A(z) согласно равенству (17) с выхода корректирующих сумматоров 4-10 подается на выход 11 устройства.

Блок нулевизации представлен на фиг.2.

Она состоит из: первый слой нейронов 12-42, второй слой нейронов 43-52.

Блок нулевизации представляет собой двухслойную нейронную сеть. Первый слой содержит 31 нейрон. На вход нейронов 12 в двоичном коде поступает остаток ₁(z) по основанию p₁(z)=z+1. На вход нейронов 13-17 поступает остаток ₂(z) по основанию p₂(z)=z⁵+z³+1, причем старший разряд подается на 13 нейрон, а младший – 17 нейрон. На вход нейронов 18-22 поступает остаток ₃(z) по основанию p₃(z)=z⁵+z⁴+z²+z+1, причем старший разряд подается на 18 нейрон, а младший – 22 нейрон. На вход нейронов 23-27 поступает остаток ₄(z) по основанию p₄(z)=z⁵+z⁴+z³+z+1, причем старший разряд подается на 23 нейрон, а младший – 27 нейрон. На вход нейронов 28-32 поступает остаток ₅(z) по основанию p₅(z)=z⁵+z⁴+z³+z²+1, причем старший разряд подается на 28 нейрон, а младший – 32 нейрон. На нейроны 33-37 поступает двоичный код ₆(z) по первому контрольному модулю p₆(z)=z⁵+z²+1, причем старший разряд подается на 33 нейрон, а младший – на 37 нейрон. На нейроны 38-42 в двоичном коде поступает в двоичном коде ₇(z) по второму контрольному модулю p₇(z)=z⁵+z³+z²+z+1, причем старший разряд подается на 38 нейрон, а младший – на 42 нейрон. Второй слой нейронной сети содержит 10 нейронов, выполняющих базовую операцию суммирования по модулю два согласно выражению (13), причем первые пять нейронов 43-47 определяют значение x₆(z), остальные нейроны 48-52 определяют значение x₇(z). Входы нейрона 43 второго слоя соединены с выходами нейронов 13, 19, 20, 22, 24, 25, 32, 33 нейронов первого слоя. Входы нейрона 44 второго слоя соединены с выходами нейронов 14, 20, 21, 23, 25, 26, 28, 34 нейронов первого слоя. Входы нейрона 45 второго слоя соединены с выходами нейронов 12, 15, 18, 21, 25, 27, 29, 35 нейронов первого слоя. Входы нейрона 46 второго слоя соединены с выходами нейронов 16, 18, 20, 22, 23, 30, 32, 36 нейронов первого слоя. Входы нейрона 47 второго слоя соединены с выходами нейронов 17, 18, 19, 21, 23, 24, 31, 37 нейронов первого слоя. Входы нейрона 48 второго слоя соединены с выходами нейронов 13, 20, 22, 24, 29, 30, 31, 38 нейронов первого слоя. Входы нейрона 49 второго слоя соединены с выходами нейронов 14, 21, 23, 25, 28, 30, 31, 39 нейронов первого слоя. Входы нейрона 50 второго слоя соединен с выходами нейронов 15, 18, 20, 23, 26, 30, 31, 40 нейронов первого слоя. Входы нейрона 51 второго слоя соединен с выходами нейронов 12, 16, 18, 19, 20, 21, 24, 25, 26, 27, 29, 30, 31, 41 нейронов первого слоя. Входы нейрона 52 второго слоя соединен с выходами нейронов 17, 19, 21, 22, 23, 27, 28, 29, 31, 42 нейронов первого слоя. Старшие значения результатов нулевизации по контрольным основаниям x₆(z) и x₇(z) соответственно вычисляются в нейронах 43 и 48.

Рассмотрим процесс работы блока нулевизации на примерах. Пусть на вход устройство обнаружения и коррекции ошибок в кодах полиномиальной системы классов вычетов на основе нулевизации был подан модулярный код A(z)=(0, z³+z, z⁴+z³+z²+z+1, z²+z-1, z⁴+z³+z²+1, 0). Данный код поступает на входы нейронов первого слоя блока нулевизации. Сигналы на выходе нейронов первого слоя представлены в таблице 4.

Сигналы с выходов нейронов первого слоя поступают на соответствующие входы нейронов второго слоя. В таблице 5 представлены значения сигналов на входе и на выходе нейронов второго слоя. Символ «-» соответствует отсутствию связи между нейронами второго и первого слоя. Полученный нулевой результат свидетельствует о том, что данная комбинация не содержит ошибки.

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

A*(z)=(1, z³+z, z⁴+z³+z²+z+1, z²+z+1, z³+z+1, z⁴+z³+z²+z, 0)

Данный код поступает на входы нейронов первого слоя блока нулевизации. Сигналы на выходе нейронов первого слоя представлены в таблице 6.

Сигналы с выходов нейронов первого слоя поступают на соответствующие входы нейронов второго слоя. В таблице 7 представлены значения сигналов на входе и на выходе нейронов второго слоя.

В результате выполнения процедуры, параллельной нулевизации, был получен результат, отличный от нулевого, т.е. x₆(z)=z², x₇(z)=z. Следовательно, модульная комбинация, поданная на вход устройства, содержит ошибку.

Согласно таблице 3, где приведена зависимость местоположения и глубины ошибки от результатов выполнения процедуры нулевизации, для полученного результата x₆(z)=z², x₇(z)=z имеем, что ошибка произошла по первому основанию и глубина равна 1.

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

Устройство обнаружения и коррекции ошибок на основе нулевизации в кодах полиномиальной системы классов вычетов (ПСКВ) в исходном полиноме A(z)=(₁(z),…,_i(z)), где _i(Z) – остаток полинома A(z) по модулю p_i(z), i=(1,…, 7), a p₁(z), р₂(z), р₃(z), p₄(z), p₅(z) – рабочие основания системы ПСКВ поля GF(2⁵), р₆(z), p₇(z) – контрольные основания, отличающееся тем, что устройство содержит вход, который соединен с входами блока нулевизации, представляющего собой двухслойную нейронную сеть, первый слой которой содержит 31 нейрон, а второй слой – десять нейронов, выполняющих базовую операцию суммирования по модулю, входы первого нейрона второго слоя соединены с выходами 2, 8, 9, 11, 13, 14, 21, 22 нейронов первого слоя, входы второго нейрона второго слоя соединены с выходами 2, 9, 10, 12, 14, 15, 17, 23 нейронов первого слоя, входы третьего нейрона второго слоя соединены с выходами 1, 4, 7, 10, 14, 16, 18, 24 нейронов первого слоя, входы четвертого нейрона второго слоя соединены с выходами 5, 7, 9, 11, 12, 19, 21, 25 нейронов первого слоя, входы пятого нейрона второго слоя соединены с выходами 6, 7, 8, 10, 12, 13, 20, 26 нейронов первого слоя, входы шестого нейрона второго слоя соединены с выходами 2, 9, 11, 13, 18, 19, 20, 27 нейронов первого слоя, входы седьмого нейрона второго слоя соединены с выходами 3, 10, 12, 14, 17, 19, 20, 28 нейронов первого слоя, входы восьмого нейрона второго слоя соединены с выходами 4, 7, 9, 12, 15, 19, 20, 29 нейронов первого слоя, входы девятого нейрона второго слоя соединен с выходами 1, 5, 7, 8, 9, 10, 13, 14, 15, 16, 18, 19, 20, 30 нейронов первого слоя, входы десятого нейрона второго слоя соединен с выходами 6, 8, 10, 11, 12, 16, 17, 18, 20, 31 нейронов первого слоя, на входы блока нулевизации подают значения остатков _i(z) соответственно, выходы блока нулевизации подключены соответственно ко входам блока памяти, содержащего константы ошибки, выходы которого подключены ко вторым входам семи корректирующих сумматоров соответственно, первые входы упомянутых сумматоров соединены со входом устройства, причем корректирующие сумматоры осуществляют суммирование поступающих на их первые входы значений _i(z) с соответствующими константами ошибки по основаниям p_i(z), поступающими на вторые входы упомянутых сумматоров соответственно, выходы корректирующих сумматоров являются выходом устройства.

РИСУНКИ

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

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

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