УСТРОЙСТВО ДЛЯ КОРРЕКЦИИ ОШИБОК В ПОЛИНОМИАЛЬНОЙ СИСТЕМЕ КЛАССОВ ВЫЧЕТОВ С ИСПОЛЬЗОВАНИЕМ ПСЕВДООРТОГОНАЛЬНЫХ ПОЛИНОМОВ Российский патент 2007 года по МПК G01F11/08 G06N3/02 

Устройство относится к области вычислительной техники, в частности может быть использовано как для контроля и исправления ошибки при передаче информации, так и при проведении арифметических операций в расширенных полях Галуа GF(2^v).

Известно устройство для обнаружения и исправления ошибок (СССР №714399, 08.02.1980, G 06 F 11/08), содержащее регистр, два блока модульной свертки, предназначенных для вычисления остатков числа по контрольным основаниям, два модульных сумматора, предназначенных для вычисления синдрома ошибки по первому и второму контрольному основаниям, блок памяти, предназначенный для хранения констант, третий сумматор, предназначенный для получения исправленного числа путем суммирования ошибочного числа с константой ошибки.

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

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

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

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

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

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

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

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

В основу математической модели определения позиционной характеристики - нормированного следа полинома A(z) положена китайская теорема об остатках, согласно которой

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

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

Тогда на основании равенств (3) и (4) очевидно, что

Если положить условие, A(z)∈Р_раб(z), то справедливо

Согласно китайской теореме об остатках полином можно представить в виде

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

где - ортогональный базис безизбыточной системы оснований ПСКВ.

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

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

Для получения псевдоортогональных полиномов проведем расширение системы оснований p₁(z), ..., p_k(z) на r контрольных оснований p_k+1(z), ..., p_k+r(z) и представим ортогональные полиномы в виде

Выражение (8) определяет значения псевдоортогональных полиномов, у которых нарушена ортогональность по контрольным основаниям.

Подставив выражение (8) в равенство (6), и учитывая, что в процессе выполнения операции не бывает выход за пределы P_раб(z), получаем

Следовательно, справедливо

Таким образом, на основании выражения (9) и воспользовавшись значениями псевдоортогональных полиномов, определяемых равенством (8), можно вычислить значения остатков по контрольным основаниям согласно

Затем на основании полученных значений и значений α_k+1(z), ..., α_k+r(z), поступающих на вход устройства коррекции ошибок, можно определить синдром ошибки согласно выражению

Если синдром ошибки равен нулю, т.е.

то исходный полином A(z)∈P_раб(z) является разрешенным и не содержит ошибки. В противном случае модулярная комбинация является запрещенной. Тогда в зависимости от величины синдрома ошибки осуществляется коррекция ошибки, т.е.

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

Структура устройства представлена на фигуре 1. Устройство состоит из регистра 2, предназначенного для хранения остатков по рабочим и контрольным основанием ПСКВ в течение времени обнаружения ошибки, вход которого соединен со входом 1 устройства, блока вычисления синдрома ошибки 3, входы которого соединены с выходами регистра 2, блокам памяти 4, предназначенного для хранения констант - векторов ошибки, входы которого подключены к выходам блока вычисления синдрома ошибки 3, сумматора 5, осуществляющего исправления ошибки путем суммирования исправленной (ошибкой) комбинации кода ПСКВ с вектором ошибки, первый, второй и третий входы которого соединены соответственно с тремя первыми выходами регистра 2 по которым передаются остатки рабочих оснований, а четвертый вход соединен с выходом блока памяти 4, выход сумматора 5 является выходом 6 устройства.

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

где α_i(z) - остаток полинома A(z) по модулю p_i(z); p₁(z), p₂(z), ..., p_k(z) - рабочие основания системы ПСКВ; р_k+1(z), p_k+2(z) - контрольные основания. Данный код записывается в регистр 2. Затем с выхода регистра 2 код ПСКВ в двоичном виде поступает на вход блока вычисления синдрома ошибки 3, который представляет собой двухслойную нейронную сеть. Модулярный код ПСКВ A(z)=(α₁(z), α₂(z), ..., α_k(z), α_k+1(z), α_k+2(z)) записывается нейронами первого слоя блока вычисления синдрома ошибки 3. С выхода нейронов первого слоя сигналы в двоичном виде поступают на второй слой нейронной сети, который осуществляет вычисление синдрома ошибки согласно выражению (11). С выхода нейронов второго слоя значение синдрома ошибки в двоичном коде θ_k+1(z), ..., θ_k+r(z) подается на вход блока 4 памяти, где осуществляется выбор оттуда соответствующей константы ошибки. Эта константа ошибки поступает на четвертый вход сумматора 5, где суммируется со значением A(z)=(α₁(z), α₂(z), ..., α_k(z)), представленным по рабочим основаниям, поступившим с выходов регистра 3 на первые три входа сумматора 5. Исправленное значение A(z) согласно равенству (12) с выхода сумматора 5 подается на выход 6 устройства.

В качестве примера рассмотрим расширенное поле Галуа GF(2⁴), в котором определены следующие основания:

p₁(z)=z+1; р₂(z)=z²+z+l; p₃(z)=z⁴+z³+z²+z+1; p₄(z)=z⁴+z³+1; p₅(z)=z⁴+z+1, где p₁(z), p₂(z), р₃(z) - рабочие основания, p₄(z), p₅(z) - контрольные основания ПСКВ. Тогда согласно выражению (1) имеем P_раб(z)=z⁷+z⁶+z⁵+z²+z+1.

В полной системе оснований ПСКВ поля GF(2⁴) определены следующие ортогональные базисы:

Используя сравнимость ортогональных базисов безызбыточной и полной системы по рабочему диапазону, определим значения ортогональных базисов безызбыточной системы оснований p₁(z)=z+1; p₂(z)=z²+z+1; p₃(z)=z⁴+z³+z²+z+1. Тогда

На основании полученных значений определим все псевдоортогональные полиномы для ПСКВ GF(2⁴), учитывая невозможность выхода за пределы рабочего диапазона Р_раб(z)=z⁷+z⁶+z⁵+z²+z+1. Полученные значения представлены в таблице 1.

Таблица 1
Псевдоортогональные полиномы ПСКВ поля GF(2⁴)Основание ПСКВПседоортогональный полиномp₁(z)=z+1(1, 0, 0, z³+z+1, z)p₂(z)=z²+z+1(0, 1, 0, z²+z+1, z³+1)(0, z, 0, z³+z, z²+z+1)(0, z+1, 0, z³+z²+1, z³+z²+z)p₃(z)=z⁴+z²+z²+z+1(0, 0, 1, z³+z²+1, z³+z)(0, 0, z, z+1, z²+z+1)(0, 0, z+0, z³+z²+z, z³+z²+1)(0, 0, z², z, z³)(0, 0, z²+l, z³+z²+z+1, z)(0, 0, z²+z, 1, z³+z²+z+1)(0, 0, z²+z+1, z³+z², z²+1)(0, 0, z³, z², z+l)(0, 0, z³+1, z³+1, z³+1)(0, 0, z³+z, z²+z+1, z²)(0, 0, z³+z+1, z³+z, z³+z²+z)(0, 0, z²+z², z²+z, z³+z+1)(0, 0, z³+z²+1, z³+z+1, 1)(0, 0, z³+z²+z, z²+1, z³+z²)(0, 0, z³+z²+z+1, z³, z²+z)

Если полином A(z)∈P_раб, то справедливо

где левая часть равенства представлена по рабочим основаниям p₁(z), p₂(z), р₃(z), средняя часть равенства - получена на основании выражения (10), а правая - модулярная комбинация системы оснований p₁(z), р₂(z), p₃(z), p₄(z), p₅(z) расширенного поля Галуа GF(2⁴), поступившая на вход устройства для коррекции ошибок в полиномиальной системе классов вычетов с использованием псевдоортогональных полиномов. Тогда согласно (11) имеем

В противном случае

Полученный результат свидетельствует, что поступившая на вход устройства модульная комбинация A(z) содержит ошибку, которую необходимо подвергнуть коррекции. В таблице 2 представлены значения вектора ошибки (0, ..., Δα_i(z), ..., 0) - модулярного кода для различных значений синдрома ошибки для ПСКВ поля GF(2⁴).

Таблица 2
Значения вектора ошибки модулярного кода поля GF(2⁴)Основание ПСКВЗначение вектора ошибкиθ₄(z)θ₅(z)00(0, 0, 0)z³+z+1z(1, 0, 0)z²+z+1z³+1(0, 1, 0)z³+zz²+z+1(0, z, 0)z³+z²+1z³+z²+z(0, z+1, 0)z³+z²+1z³+z(0, 0, 1)z+1z²+z+1(0, 0, z,)z³+z²+zz³+z²+l(0, 0, z+1)zz³(0, 0, z²)z³+z²+z+lz(0, 0, z²+1)1z³+z²+z+1(0, 0, z²+z)z³+z²z²+1(0, 0, z²+z+1)z²z+1(0, 0, z³)z³+1z³+l(0, 0, z³+1)z²+z+1z²(0, 0, z³+z)z³+zz³+z²+z(0, 0, z³+z+1)z²+zz³+z+1(0, 0, z³+z²)z³+z+11(0, 0, z³+z²+1)z²+1z³+z²(0, 0, z³+z²+z)z³z²+z(0, 0, z³+z²+z+l)

Пусть на вход 1 устройства подается полином A(z)=z⁵+z⁴+z, значение которого в модулярном коде представляется A(z)=(1, z+1, z³+z², 0, z²+z⁴+1).

Тогда согласно выражению (8) и данных, представленных в таблице 1, получаем следующие псевдоортогональные полиномы А_i(z):

Согласно выражению (10) определяем значения остатков по контрольным основаниям:

Согласно выражению (11) определяем синдром ошибки:

Из блока памяти 5 в соответствии с θ₄(z)=0, θ₅(z)=0 выбирается величина (0, 0, 0), которая складывается с A(z)=(1, z+1, z³+z²), в сумматоре 6 с образованием на выходе

Допустим, что в принятой комбинации произошла ошибка по третьему основанию и ее глубина равна Δα₃(z)=z²+z. Тогда имеем

Тогда согласно выражению (8) и данных, представленных в таблице 1, получаем следующие псевдоортогональные полиномы A_i(z):

Согласно выражению (10) определяем значения остатков по контрольным основаниям:

Согласно выражению (11) определяем синдром ошибки:

Из блока памяти 5 в соответствии с θ₄(z)=1, θ₅(z)=z³+z²+z+1 выбирается величина (0, 0, z²+z), которая складывается с A(z)=(1, z+1, z³+z) в сумматоре 6 с образованием на выходе

Ошибка в модулярном коде исправлена.

Блок вычисления синдрома ошибки представлен на фиг.2. Блок вычисления синдрома ошибки имеет 5 входов, по первым трем из которых подаются остатки α₁(z), α₂(2), α₃(z) по рабочим основанием p₁(z), p₂(z), р₃(z), по четвертому и пятому поступают остатки α₄(z) и α₅(z) по контрольным основаниям p₄(z) и p₅(z). Блок вычисления синдрома представляет собой двухслойную нейронную сеть. Первый слой содержит 15 нейронов. Входы нейронов 7, 8-9, 10-13 подключены соответственно к первому, второму и третьему входу блока вычисления синдрома ошибки. Входы нейронов 14-17 и 18-21 подключены соответственно к четвертому и пятому входам блока вычисления синдрома ошибок. На входы нейронов 7, 8-9, 10-13 в двоичном виде поступают остатки α₁(z), α₂(z), α₃(z) по трем рабочим основаниям ПСКВ. На нейроны 14-17 поступает двоичный код α₄(z) по первому контрольному модулю p₄(z)=z⁴+z³+1. На нейроны 18-21 в двоичном коде поступает в двоичном коде α₅(z) по второму контрольному модулю p₅(z)=z⁴+z+1. Старшие разряды остатков полинома α₁(z), α₂(z), α₃(z), α₄(z), α₅(z) записываются соответственно в нейроны 7, 8, 10, 14, 18 первого слоя. Второй слой нейронной сети содержит 8 нейронов, выполняющих базовую операцию согласно выражению (11), причем первые четыре нейрона 22-25 определяют значение θ₄(z), остальные нейроны 26-29 определяют значение θ₅(z). Входы нейрона 22 второго слоя соединены с выходами нейронов 7, 8, 13, 14 первого слоя. Входы нейрона 23 второго слоя соединены с выходами нейронов 9, 10, 13, 15 первого слоя. Входы нейрона 24 второго слоя соединены с выходами 7, 8, 9, 11, 12, 16 нейронов первого слоя. Входы нейрона 25 второго слоя соединены с выходами 7, 9, 12, 13, 17 нейронов первого слоя. Входы нейрона 26 второго слоя соединены с выходами 9, 11, 13, 18 нейронов первого слоя. Входы нейрона 27 второго слоя соединены с выходами 8, 12, 19 нейронов первого слоя. Входы нейрона 28 второго слоя соединены с выходами 7, 8, 10, 12, 13, 20 нейронов первого слоя. Входы нейрона 29 второго слоя соединен с выходами нейронов 8, 9, 10, 12, 21 нейронов первого слоя. Старшие значения синдрома ошибки θ₄(z) и θ₅(z) соответственно вычисляются в нейронах 22 и 26. Выходы нейронов второго слоя являются выход блока вычисления синдрома ошибки.

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

Таблица 3
Сигналы на выходе нейронов первого слояНейроны789101112131415161718192021Сигнал на выходе111110000000111

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

Таблица 4
Сигналы на выходе нейронов второго слояНейроны789101112131415161718192021выход221-1---00-------023--11--0-0------024111-10---0-----0251-1--00---0----026--1-1-0----0---027-1---0------1--02811-1-00------1-029-111-0--------10

Допустим, что в принятой комбинации произошла ошибка по третьему основанию и ее глубина равна Δα₃(z)=z²+z. Тогда имеем

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

Таблица 5
Сигналы на выходе нейронов первого слояНейроны789101112131415161718192021Сигнал на выходе111101000000111

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

Таблица 6
Сигналы на выходе нейронов второго слояНейроны789101112131415161718192021выход221- ---00-------023-- 1--0-0------02411 -01---0-----0251- --10---0----126-- -0-0----0---127-1---1------1--12811-1-10------1-129-111-1--------11

Таким образом, на выходе блока вычисления синдрома ошибки определены значения θ₄(z)=1, θ₅(z)=z³+z²+z+1. Полученные данные совпадают с контрольными просчетами, представленными ранее.

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

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