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

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

Известно устройство спектрального обнаружения и коррекции ошибок в кодах полиномиальной системы классов вычетов (ПСКВ) (патент RU 2301441, кл. G06F 7/72), содержащее три информационных входа и два контрольных входа, регистр, блок вычисления интервального полинома, блок спектрального анализа, постоянное запоминающее устройство, корректирующий сумматор, выход.

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

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

Указанный технический результат достигается за счет удаления из структуры постоянного запоминающего устройства, где хранятся корректирующие значения Δα^кор(z), и введения в состав блока спектрального анализа, представляющего собой двухслойную нейронную сеть (НС) третьего и четвертого слоев нейронов.

Функциональная схема устройства представлена на фиг.1. Устройство содержит вход 1, на который подают код полинома

где α_i(z) - остатки по рабочим и контрольным основаниям ПСКВ p_i(z);

i=1÷n - количество оснований ПСКВ,

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

где Q_i(z) - частное от деления ортогонального базиса B_i(z) на величину

k - количество рабочих оснований ПСКВ;

r=n-k - количество контрольных оснований;

B_m ^*(z) - ортогональный базис безызбыточной ПСКВ.

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

Рассмотрим работу устройства. На вход 1 устройства подается три остатка по рабочим основаниям p₁(z)=z+1; р₂(z)=z²+z+1; р₃(z)=z⁴+z³+z²+z+1 и двум контрольным основаниям p₄(z)=z⁴+z³+1 и p₅(z)=z⁴+z+1. В этом случае рабочий диапазон будет равен

Известно, что если полином A(z), представленный в виде ПСКВ, принадлежит рабочему диапазону, то он не содержит ошибок.

В противном случае A(z)=(α₁(z), α₂(z), α₃(z), α₄(z), α₅(z)) содержит ошибку.

При этом если модулярный код A(z) не содержит ошибок, то определенные спектральные составляющие интервального полинома (2), определяемые выражением

где S_j(Z) - j-ая спектральная составляющая полинома s(z);

β_k+l - первообразный элемент расширенного поля GF(p^v), порожденный полиномом p_k+l(z); l=1, 2, …, r, j=0, …, p^v-1-1,

будут равны 0.

Такими спектральными составляющими будут S₁(Z₁), S₂(Z₁), S₄(Z₁), S₈(Z₁), а также S₇(Z₁), S₁₁(Z₁), S₁₃(Z₁), S₁₄(Z₁). Данные спектральные составляющие интервального полинома s(z) соответствуют корням контрольных оснований p₄(z) и p₅(z) соответственно.

Появление ошибки в n-мерной комбинации A(z) по i-тому основанию и глубиной Δα_i(z) приводит к смещению последнего во временной области на величину

т.е.

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

Таблица 1 Смещение выравнивания в GF(2⁴) при возникновении ошибок в ПСКВ Основание Глубина ошибки Δα_i Полином s(z) Смещение значения S₁ (Z) p₄(z)=z⁴+z³+1 p⁵(z)=z⁴+z+1 p₁(z)=z+1 1 z⁷+z⁴+z²+z β³ β¹¹ p₂(z)=z²+z+1 1 z⁷+z⁵+z²+z+1 β⁵ β⁹ z z⁸+z⁶+z³+z²+z+1 β⁸ β⁵ p₃(z)=z⁴+z³+z²+z+1 1 z⁷+z⁴+z³+z+1 β⁹ β⁴ z z⁸+z⁵+z⁴+z²+z β¹⁰ β⁵ z² z⁹+z⁶+z⁵+z³+z²+1 β¹⁴ β¹³ z³ z¹⁰+z⁷+z⁶+z⁴+z³+z 1 β¹⁴ p₄(z)=z⁴+z³+1 1 z⁷+z⁴+z³ β¹³ 0 z z⁸+z⁵+z⁴ β¹⁴ 0 z² z⁹+z⁶+z⁵ 1 0 z³ z¹⁰+z⁷+z⁶ β 0 p₅(z)=z⁴+z+1 1 z⁵+z⁴+z 0 β¹⁰ z z⁶+z⁵+z² 0 β¹¹ z² z⁷+z⁶+z³ 0 β¹² z³ z⁸+z⁷+z⁴ 0 β¹³

Анализируя смещения первой гармоники S₁ (Z), сложно составить соответствие между ее величиной и местоположением ошибки Δα_i(z), которое приведено в таблице 2.

Анализ таблицы показывает, что определить значения Δα_i(z) можно с использованием третьего слоя нейронов блока спектрального анализа.

Структура блока спектрального анализа показана на фиг.2. Он представляет собой четырехслойную нейронную сеть, первый слой которой содержит пятнадцать нейронов 7-21, второй слой - восемь нейронов 22-29, третий слой - восемь нейронов 30-37, а четвертый слой - пятнадцать нейронов 38-52. Нейроны первого слоя осуществляют распределение значений, поступивших на их входы, нейроны второго слоя реализуют базовую операцию суммирования по модулю два, нейроны третьего слоя реализуют базовую операцию «НЕ», а нейроны четвертого слоя - операцию «логическое И». Причем входы нейрона 22 второго слоя соединены с выходами 7, 11, 12, 13, 14, 16, 18, 19 нейронов первого слоя. Входы нейрона 23 второго слоя соединены с выходами 8, 12, 13, 14, 15, 17, 19, 20 нейронов первого слоя. Входы нейрона 24 второго слоя соединены с выходами 9, 13, 14, 15, 16, 18, 20, 21 нейронов первого слоя. Входы нейрона 25 второго слоя соединены с выходами 10, 11, 12, 13, 15, 17, 18, 21 нейронов первого слоя. Выходы нейронов 22, 23, 24, 25 представляют собой соответственно нулевой, первый, второй и третий разряды первой спектральной составляющей S₁ (Z₁) по модулю p₄(z)=z⁴+z³+1.

Входы нейрона 26 второго слоя соединены с выходами 7, 11, 14, 15, 16, 18, 19, 20 нейронов первого слоя. Входы нейрона 27 второго слоя соединены с выходами 8, 11, 12, 14, 16, 17, 18, 19 нейронов первого слоя. Входы нейрона 28 второго слоя соединены с выходами 9, 12, 13, 15, 17, 18, 19, 20 нейронов первого слоя. Входы нейрона 29 второго слоя соединены с выходами 10, 13, 14, 16, 18, 19, 20, 21 нейронов первого слоя. Выходы нейронов 26, 27, 28, 29 представляют собой соответственно нулевой, первый, второй и третий разряды первой составляющей S₁ (Z₁) по модулю p₅(z)=z⁴+z+1.

Вход нейрона 30 третьего слоя соединен с выходом нейрона 22 второго слоя. Вход нейрона 31 третьего слоя соединен с выходом нейрона 23 второго слоя. Вход нейрона 32 третьего слоя соединен с выходом нейрона 24 второго слоя. Вход нейрона 33 третьего слоя соединен с выходом нейрона 25 второго слоя. Вход нейрона 34 третьего слоя соединен с выходом нейрона 26 второго слоя. Вход нейрона 35 третьего слоя соединен с выходом нейрона 27 второго слоя. Вход нейрона 36 третьего слоя соединен с выходом нейрона 28 второго слоя. Вход нейрона 37 третьего слоя соединен с выходом нейрона 29 второго слоя. Нейроны 30-37 третьего слоя реализуют операцию «логическое НЕ».

Входы нейрона 38 четвертого слоя соединены с выходами 25, 27, 28, 29 нейронов второго слоя и выходами 30, 31, 32, 34 нейронов третьего слоя. Входы нейрона 39 четвертого слоя соединены с выходами 22, 23, 25, 27, 29 нейронов второго слоя и выходами 32, 34, 36 нейронов третьего слоя. Входы нейрона 40 четвертого слоя соединены с выходами 23, 24, 25, 27, 28 нейронов второго слоя и выходами 30, 34, 37 нейронов третьего слоя. Входы нейрона 41 четвертого слоя соединены с выходами 22, 24, 26, 27 нейронов второго слоя и выходами 31, 33, 36, 37 нейронов третьего слоя. Входы нейрона 42 четвертого слоя соединены с выходами 23, 25, 27, 28 нейронов второго слоя и выходами 30, 32, 34, 37 нейронов третьего слоя. Входы нейрона 43 четвертого слоя соединены с выходами 24, 25, 26, 28, 29 нейронов второго слоя и выходами 30, 31, 35 нейронов третьего слоя. Входы нейрона 44 четвертого слоя соединены с выходами 22, 26, 29 нейронов второго слоя и выходами 31, 32, 33, 35, 36 нейронов третьего слоя. Входы нейрона 45 четвертого слоя соединены с выходами 23, 24 нейронов второго слоя и выходами 30, 33, 34, 35, 36, 37 нейронов третьего слоя. Входы нейрона 46 четвертого слоя соединены с выходами 24, 25 нейронов второго слоя и выходами 30, 31, 34, 35, 36, 37 нейронов третьего слоя. Входы нейрона 47 четвертого слоя соединены с выходами 22 нейронов второго слоя и выходами 31, 32, 33, 34, 35, 36, 37 нейронов третьего слоя. Входы нейрона 48 четвертого слоя соединены с выходами 23 нейронов второго слоя и выходами 30, 32, 33, 34, 35, 36, 37 нейронов третьего слоя. Входы нейрона 49 четвертого слоя соединены с выходами 26, 27, 28 нейронов второго слоя и выходами 30, 31, 32, 33, 37 нейронов третьего слоя. Входы нейрона 50 четвертого слоя соединены с выходами 27, 28, 29 нейронов второго слоя и выходами 30, 31, 32, 33, 34 нейронов третьего слоя. Входы нейрона 51 четвертого слоя соединены с выходами 26, 27, 28, 29 нейронов второго слоя и выходами 30, 31, 32, 33 нейронов третьего слоя. Входы нейрона 52 четвертого слоя соединены с выходами 26, 28, 29 нейронов второго слоя и выходами 30, 31, 32, 33, 35 нейронов третьего слоя.

Нейроны 38-52 четвертого слоя реализуют базовую операцию «логическое умножение». С выходов данных нейронов снимается значение Δα_i(z)B_i(z)modP_полн(z), i=1, 2, 3, 4, 5, представленное в модулярном коде.

При этом корректирующее значение Δα₁ ^кор(z)=Δα₁(z)В₁(z)modP_полн(z), где

- полный диапазон; снимается с выхода нейрона 38 четвертого слоя. Корректирующее значение Δα₂ ^кор(z)=Δα₂(z)B₂(z)modP_полн(z) снимается с выходов нейронов 39 и 40 четвертого слоя. Корректирующее значение Δα₃ ^кор(z)=Δα₃(z)В₃(z)modР_полн(z) снимается с выходов нейронов 41-44 четвертого слоя. Корректирующее значение Δα₄ ^кор(z)=Δα₄(z)В₄(z)modР_полн(z) снимается с выходов нейронов 45-48 четвертого слоя. Корректирующее значение Δα₅ ^кор(z)=Δα₅(z)В₅(z)modР_полн(z) снимается с выходов нейронов 49-52 четвертого слоя. Данные значения Δα_i ^кор(z)=Δα_i(z)B_i(z)modP_полн(z) представлены в двоичном коде, при этом снимаются с выходов 38, 40, 44, 48, 52 нейронов четвертого слоя. Выходы нейронов четвертого слоя являются выходом блока спектрального анализа.

Устройство работает следующим образом. На вход 1 устройства подается модулярный код полинома A(z)=(α₁(z), α₂(z), α₃(z), α₄(z), α₅(z)), который поступает на вход регистра 2, предназначенного для хранения принятой комбинации, данный модулярный код имеет 3 рабочих основания p₁(z)=z+1, p₂(z)=z²+z+1, р₃(z)=z⁴+z³+z²+z+1, которые образуют диапазон

и два контрольных основания p₄(z)=z⁴+z³+1 и p₅(z)=z⁴+z+1. Пусть в качестве исходного полинома выбираем A(z)=z⁶+z+1, принадлежащий рабочему диапазону. Тогда данный полином представляется в виде кода ПСКВ A(z)=(1,z,1,z³+z²,z³+z²+z+1).

С выхода регистра 2 модулярный код поступает на вход блока вычисления интервального полинома 3. Для системы ПСКВ имеем ортогональные базисы

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

В₂(z)=z¹⁴+z¹³+z¹¹+z¹⁰+z⁸+z⁷+z⁵+z⁴+z²+z;

В₃(z)=z¹⁴+z¹³+z¹²+z¹¹+z⁹+z⁸+z⁷+z⁶+z⁴+z³+z²+z;

B₄(z)=z¹⁴+z¹³+z¹²+z¹¹+z⁹+z⁷+z⁶+z³;

B₅(z)=z¹²+z⁹+z⁸+z⁶+z⁴+z³+z²+z.

Тогда

B₁ ^*(z)=B₁(z)modP_раб(z)=z⁶+z⁴+z³+z²+1;

B₂ ^*(z)=B₂(z)modP_раб(z)=z⁶+z⁵+z+1;

B₃ ^*(z)=B₃(z)modP_раб(z)=z⁵+z⁴+z³+z²+1.

Согласно выражению (2) имеем s₁(z)=z¹⁰+z⁹+z⁷+z⁶+z⁵+z²+z.

Данное значение интервального полинома подается на входы нейронов первого слоя блока спектрального анализа 4. В таблице 3 представлено распределение сигналов на выходе нейронов первого слоя.

Таблица 3 Сигналы на выходе нейронов первого слоя нейроны 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 сигнал 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0

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

Полученный нулевой результат на выходе нейронов второго слоя поступает на соответствующие входы нейронов третьего и четвертого слоев. Так как данные нейроны реализуют базовую операцию «НЕ» и операцию логического умножения, то на выходах нейронов четвертого слоя будет нулевой результат. Этот сигнал с выхода блока спектрального анализа 4 поступает на второй вход корректирующего сумматора 5, на первый вход которого подается с регистра 2 модулярный код А(z). Корректирующий сумматор 5 реализует операцию

A_испр(z)=A(z)+Δα^кор(z)=(1,z,1,z³+z²,z³+z²+z+1)+(0,0,0,0,0)=

=(1,z,1,z³,+z²,z³+z²+z+1).

Полученное значение подается на выход устройства 6.

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

A_ош(z)=(1,0,1,z³+z²,z³+z²+z+1).

Данный модулярный код ПСКВ через вход 1 поступает на регистр 2, с выхода которого подается на блок вычисления интервального полинома 3.

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

s(z)=z¹⁰+z⁹+z⁸+z⁷+z⁵+z+1.

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

Таблица 6 Сигналы на выходе нейронов первого слоя нейроны 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 сигнал 1 1 0 0 0 1 0 1 1 1 1 0 0 0 0

Данные значения подаются на входы нейронов второго слоя, на выходе которых появляются сигналы в соответствии с таблицами 7 и 8.

Ненулевой результат спектральных составляющих по модулю p₄(z)=z⁴+z³+1-s₁(z)=1110=z³+z²+z, по модулю p₅(z)=z⁴+z+1-s₂(z)=0110=z²+z свидетельствует о том, что комбинация А_ош(z) содержит ошибку. Данные сигналы поступают на входы нейронов третьего и четвертого слоев.

В таблице 9 представлены сигналы на выходе нейронов третьего слоя.

В таблице 10 представлены сигналы на выходе нейронов четвертого слоя.

Полученный результат на выходе нейронов четвертого слоя соответствует

Δα₂ ^кор(z)=(0,z,0,0,0).

Данный модулярный код с выхода блока спектрального анализа 4 поступает на второй вход корректирующего сумматора 5, на первый вход которого подается код ПСКВ из регистра 2. Корректирующий сумматор 5 реализует операцию

A_испр(z)=A(z)+Δα^кор(z)=(1,0,1,z³+z²,z³+z²+z+1)+(0,z,0,0,0)=

=(1,z,1,z³+z²,z³+z²+z+1).

Ошибка исправлена.

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

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