УСТРОЙСТВО СПЕКТРАЛЬНОГО ОБНАРУЖЕНИЯ И КОРРЕКЦИИ ОШИБОК В КОДАХ ПОЛИНОМИАЛЬНОЙ СИСТЕМЫ КЛАССОВ ВЫЧЕТОВ
DEVICE FOR SPECTRAL ERROR DETECTION AND CORRECTION IN CODES OF POLYNOMIAL SYSTEM OF RESIDUE CLASSES

Устройство относится к вычислительной технике и может быть использовано как для контроля и исправления ошибок при передаче информации, так и при проведении арифметических операций в ЭВМ.
Известно устройство спектрального обнаружения и коррекции ошибок в кодах полиномиальной системы классов вычетов (ПСКВ) (патент RU 2301441, кл. G06F 7/72), содержащее три информационных входа и два контрольных входа, регистр, блок вычисления интервального полинома, блок спектрального анализа, постоянное запоминающее устройство, корректирующий сумматор, выход.
Недостатками известного устройства являются его сложность и значительные схемные затраты.
Технический результат, достигаемый при осуществлении заявленного изобретения, заключается в снижении аппаратурных затрат на определение местоположения и глубины ошибки в модулярном коде ПСКВ и последующей ее коррекции.
кор
Указанный технический результат достигается за счет удаления из структуры постоянного запоминающего устройства, где хранятся корректирующие значения Δα(z), и введения в состав блока спектрального анализа, представляющего собой двухслойную нейронную сеть (НС) третьего и четвертого слоев нейронов.
Функциональная схема устройства представлена на фиг.1. Устройство содержит вход 1, на который подают код полинома
i
i
где α(z) - остатки по рабочим и контрольным основаниям ПСКВ p(z);
i=1÷n - количество оснований ПСКВ,
он подсоединен ко входу регистра 2, выход которого подключен ко входу блока вычисления интервального полинома 3, реализующего вычисление во временной области
i
i
где Q(z) - частное от деления ортогонального базиса B(z) на величину
k - количество рабочих оснований ПСКВ;
r=n-k - количество контрольных оснований;
m
*
B (z) - ортогональный базис безызбыточной ПСКВ.
Выход блока 3 подключен ко входу блока спектрального анализа 4, выход которого соединен со вторым входом корректирующего сумматора 5, первый вход которого подключен к выходу регистра 2, по которому осуществляется передача остатков модулярного кода ПСКВ по рабочим и контрольным основаниям. Выход корректирующего сумматора 5 является выходом 6 устройства.
1
2
3
4
5
2
4
3
2
4
3
4
Рассмотрим работу устройства. На вход 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), представленный в виде ПСКВ, принадлежит рабочему диапазону, то он не содержит ошибок.
1
2
3
4
5
В противном случае A(z)=(α(z), α(z), α(z), α(z), α(z)) содержит ошибку.
При этом если модулярный код A(z) не содержит ошибок, то определенные спектральные составляющие интервального полинома (2), определяемые выражением
j
где S(Z) - j-ая спектральная составляющая полинома s(z);
k+l
k+l
v
v-1
β - первообразный элемент расширенного поля GF(p), порожденный полиномом p(z); l=1, 2, …, r, j=0, …, p-1,
будут равны 0.
1
1
2
1
4
1
8
1
7
1
11
1
13
1
14
1
4
5
Такими спектральными составляющими будут S(Z), S(Z), S(Z), S(Z), а также S(Z), S(Z), S(Z), S(Z). Данные спектральные составляющие интервального полинома s(z) соответствуют корням контрольных оснований p(z) и p(z) соответственно.
i
Появление ошибки в n-мерной комбинации A(z) по i-тому основанию и глубиной Δα(z) приводит к смещению последнего во временной области на величину
т.е.
4
При этом наблюдается смещение спектра. В таблице 1 представлены смещения спектра при различных ошибках по всем основаниям ПСКВ расширенного поля Галуа GF(2).
Таблица 1
Смещение выравнивания в GF(2<sup>4</sup>) при возникновении ошибок в ПСКВ
Основание
Глубина ошибки Δα<sub>i</sub>
Полином s(z)
Смещение значения S<sub>1</sub> (Z)
p<sub>4</sub>(z)=z<sup>4</sup>+z<sup>3</sup>+1
p<sup>5</sup>(z)=z<sup>4</sup>+z+1
p<sub>1</sub>(z)=z+1
1
z<sup>7</sup>+z<sup>4</sup>+z<sup>2</sup>+z
β<sup>3</sup>
β<sup>11</sup>
p<sub>2</sub>(z)=z<sup>2</sup>+z+1
1
z<sup>7</sup>+z<sup>5</sup>+z<sup>2</sup>+z+1
β<sup>5</sup>
β<sup>9</sup>
z
z<sup>8</sup>+z<sup>6</sup>+z<sup>3</sup>+z<sup>2</sup>+z+1
β<sup>8</sup>
β<sup>5</sup>
p<sub>3</sub>(z)=z<sup>4</sup>+z<sup>3</sup>+z<sup>2</sup>+z+1
1
z<sup>7</sup>+z<sup>4</sup>+z<sup>3</sup>+z+1
β<sup>9</sup>
β<sup>4</sup>
z
z<sup>8</sup>+z<sup>5</sup>+z<sup>4</sup>+z<sup>2</sup>+z
β<sup>10</sup>
β<sup>5</sup>
z<sup>2</sup>
z<sup>9</sup>+z<sup>6</sup>+z<sup>5</sup>+z<sup>3</sup>+z<sup>2</sup>+1
β<sup>14</sup>
β<sup>13</sup>
z<sup>3</sup>
z<sup>10</sup>+z<sup>7</sup>+z<sup>6</sup>+z<sup>4</sup>+z<sup>3</sup>+z
1
β<sup>14</sup>
p<sub>4</sub>(z)=z<sup>4</sup>+z<sup>3</sup>+1
1
z<sup>7</sup>+z<sup>4</sup>+z<sup>3</sup>
β<sup>13</sup>
0
z
z<sup>8</sup>+z<sup>5</sup>+z<sup>4</sup>
β<sup>14</sup>
0
z<sup>2</sup>
z<sup>9</sup>+z<sup>6</sup>+z<sup>5</sup>
1
0
z<sup>3</sup>
z<sup>10</sup>+z<sup>7</sup>+z<sup>6</sup>
β
0
p<sub>5</sub>(z)=z<sup>4</sup>+z+1
1
z<sup>5</sup>+z<sup>4</sup>+z
0
β<sup>10</sup>
z
z<sup>6</sup>+z<sup>5</sup>+z<sup>2</sup>
0
β<sup>11</sup>
z<sup>2</sup>
z<sup>7</sup>+z<sup>6</sup>+z<sup>3</sup>
0
β<sup>12</sup>
z<sup>3</sup>
z<sup>8</sup>+z<sup>7</sup>+z<sup>4</sup>
0
β<sup>13</sup>
1
i
Анализируя смещения первой гармоники S (Z), сложно составить соответствие между ее величиной и местоположением ошибки Δα(z), которое приведено в таблице 2.
i
Анализ таблицы показывает, что определить значения Δα(z) можно с использованием третьего слоя нейронов блока спектрального анализа.
1
1
4
4
3
Структура блока спектрального анализа показана на фиг.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.
1
1
5
4
Входы нейрона 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 нейронов третьего слоя.
i
i
полн
Нейроны 38-52 четвертого слоя реализуют базовую операцию «логическое умножение». С выходов данных нейронов снимается значение Δα(z)B(z)modP(z), i=1, 2, 3, 4, 5, представленное в модулярном коде.
1
1
1
полн
кор
При этом корректирующее значение Δα (z)=Δα(z)В(z)modP(z), где
2
2
2
полн
3
3
3
полн
4
4
4
полн
5
5
5
полн
i
i
i
полн
кор
кор
кор
кор
кор
- полный диапазон; снимается с выхода нейрона 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 четвертого слоя. Данные значения Δα (z)=Δα(z)B(z)modP(z) представлены в двоичном коде, при этом снимаются с выходов 38, 40, 44, 48, 52 нейронов четвертого слоя. Выходы нейронов четвертого слоя являются выходом блока спектрального анализа.
1
2
3
4
5
1
2
3
2
4
3
2
Устройство работает следующим образом. На вход 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, которые образуют диапазон
4
5
4
3
4
6
3
2
3
2
и два контрольных основания 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. Для системы ПСКВ имеем ортогональные базисы
1
14
13
12
11
10
9
8
7
6
5
4
3
2
B(z)=z+z+z+z+z+z+z+z+z+z+z+z+z+z+1;
2
14
13
11
10
8
7
5
4
2
В(z)=z+z+z+z+z+z+z+z+z+z;
3
14
13
12
11
9
8
7
6
4
3
2
В(z)=z+z+z+z+z+z+z+z+z+z+z+z;
4
14
13
12
11
9
7
6
3
B(z)=z+z+z+z+z+z+z+z;
5
12
9
8
6
4
3
2
B(z)=z+z+z+z+z+z+z+z.
Тогда
1
1
раб
*
6
4
3
2
B (z)=B(z)modP(z)=z+z+z+z+1;
2
2
раб
*
6
5
B (z)=B(z)modP(z)=z+z+z+1;
3
3
раб
*
5
4
3
2
B (z)=B(z)modP(z)=z+z+z+z+1.
1
10
9
7
6
5
2
Согласно выражению (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 реализует операцию
испр
кор
3
2
3
2
A(z)=A(z)+Δα(z)=(1,z,1,z+z,z+z+z+1)+(0,0,0,0,0)=
3
2
3
2
=(1,z,1,z,+z,z+z+z+1).
Полученное значение подается на выход устройства 6.
2
2
2
Допустим, что ошибка произошла по второму основанию p(z)=z+z+1, а ее глубина Δα(z)=z. Тогда модулярная комбинация имеет вид
ош
3
2
3
2
A(z)=(1,0,1,z+z,z+z+z+1).
Данный модулярный код ПСКВ через вход 1 поступает на регистр 2, с выхода которого подается на блок вычисления интервального полинома 3.
С выхода блока вычисления интервального полинома 3 выдается двоичный код интервального полинома
10
9
8
7
5
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.
4
1
5
2
ош
4
3
3
2
4
2
Ненулевой результат спектральных составляющих по модулю p(z)=z+z+1-s(z)=1110=z+z+z, по модулю p(z)=z+z+1-s(z)=0110=z+z свидетельствует о том, что комбинация А(z) содержит ошибку. Данные сигналы поступают на входы нейронов третьего и четвертого слоев.
В таблице 9 представлены сигналы на выходе нейронов третьего слоя.
В таблице 10 представлены сигналы на выходе нейронов четвертого слоя.
Полученный результат на выходе нейронов четвертого слоя соответствует
2
кор
Δα (z)=(0,z,0,0,0).
Данный модулярный код с выхода блока спектрального анализа 4 поступает на второй вход корректирующего сумматора 5, на первый вход которого подается код ПСКВ из регистра 2. Корректирующий сумматор 5 реализует операцию
испр
кор
3
2
3
2
A(z)=A(z)+Δα(z)=(1,0,1,z+z,z+z+z+1)+(0,z,0,0,0)=
3
2
3
2
=(1,z,1,z+z,z+z+z+1).
Ошибка исправлена.