ПОМЕХОЗАЩИТНОЕ ДЕКОДИРОВАНИЕ СИСТЕМАТИЧЕСКИХ КОДОВ
77
УДК 621.398.1
А. В. УШАКОВ, Е. С. ЯИЦКАЯ
ПОМЕХОЗАЩИТНОЕ ДЕКОДИРОВАНИЕ СИСТЕМАТИЧЕСКИХ КОДОВ
Определяется зависимость скорости сходимости процесса наблюдения от индекса нильпотентности матрицы состояния динамического наблюдающего устройства (ДНУ). Рассматривается задача помехозащитного декодирования в форме построения ДНУ вектора начального состояния системы.
Ключевые слова: динамическое наблюдающее устройство, вектор невязки наблюдения, помехозащитное декодирование.
Введение. Базовые концепции двоичного динамического наблюдения. Для рассмотрения задачи двоичного динамического наблюдения представим линейную двоичную динамическую систему (ЛДДС) [1, 2], состояние которой подлежит наблюдению, имеющую векторно-матричное описание
χ ( k +1) = A χ ( k )+ B u ( k ), χ ( 0) = χ0 , ξ ( k ) = C χ ( k )+ H u(k) ,
(1)
где χ, u, ξ — соответственно п-мерный вектор состояния, r-мерный вектор входной последо-
вательности, l-мерный вектор выходной последовательности; матрицы A, B, C, Н согласованы по размерности с векторами χ, u и ξ . Элементы векторов и матриц принадлежат двоичному
простому полю Галуа GF ( 2) .
Двоичное динамическое наблюдающее устройство (ДНУ), использующее всю доступную для непосредственного измерения информацию об ЛДДС (1) в виде входной последова-
тельности u ( k ) и выходной — y ( k ), реализуется в форме следующей зависимости:
z ( k +1) = Γ z ( k )+ L ξ ( k )+G u ( k ), z ( 0) = z0 ,
(2)
где z — т-мерный вектор состояния ДНУ, матрица Γ определяет динамику процесса наблюдения, а пара матриц ( L,G ) обладает следующими свойствами:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 11
78 А. В. Ушаков, Е. С. Яицкая
L = arg { contr ( Γ, L) },G = arg { contr ( Γ,G) } ,
где contr{ } — предикат наличия полной управляемости пары матриц [3].
Рассмотрим задачу определения вектора χ состояния системы (1) в среде ДНУ (2) в виде
z( k)=T χ( k)+θ( k), ∀k ,
(3)
где Т — матрица преобразования подобия (в общем случае — особого); θ(k) — вектор невязки наблюдения (ВНН).
Сформулируем следующее утверждение. Утверждение 1. Если матрицы T , L,G удовлетворяют матричным соотношениям
ΓT +T A=LC, G=T B,
(4)
то процесс по ВНН θ( k ) описывается рекуррентным векторно-матричным уравнением
θ( k +1) = Γ θ( k ), θ( 0) =T χ ( 0)+ z ( 0) .
(5)
Доказательство утверждения проведем путем подстановки в (5) векторно-матричных соотношений (1), (2) и (4), в результате чего снова приходим к (5).
Для решения задачи определения вектора χ ( k ) текущего состояния ЛДДС (1) восполь-
зуемся явным (показательным) решением (5) и условием обнуления состояния ДНУ при за-
пуске ( z ( 0) = 0 ). С учетом этих обстоятельств имеем
θ( k)=Γk T χ( 0) .
(6)
В свою очередь, подстановка (6) в (3) дает
z( k)=T χ( k)+Γk θ( 0).
(7)
Пусть матрица Γ состояния ДНУ обладает свойством нильпотентности с индексом ν , тогда при k ≥ ν устанавливается равенство
z( k)=T χ( k), k ≥ν.
(8)
Таким образом, вектор z ( k ) состояния ДНУ с точностью до матрицы преобразования
подобия Т задает текущее состояние вектора χ ( k ) наблюдаемой ЛДДС (1). Причем скорость
сходимости процесса по ВНН тем выше, чем меньше индекс нильпотентности матрицы Γ состояния ДНУ. Подтвердим данное утверждение примерами.
Примеры построения двоичных наблюдающих устройств. Рассмотрим задачу синтеза ДНУ для определения вектора текущего состояния ЛДДС, ( A, B,C, H )-описание которой характеризуется матрицами
⎡0 1 1⎤ ⎡1⎤
A = ⎢⎢1 0 0⎥⎥ , B = ⎢⎢0⎥⎥ , C =[ 0 1 0] , H =[ 0] .
⎢⎣0 1 0⎦⎥ ⎢⎣1⎥⎦
С целью решения поставленной задачи в соответствии с выражениями (7) и (8) выберем в качестве модели ДНУ регистр сдвига третьего порядка. Для определения вектора текущего состояния представленной ЛДДС рассмотрим матрицы состояния ДНУ с различными индексами нильпотентности:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 11
Помехозащитное декодирование систематических кодов
79
⎡0 1 0⎤
⎡0 0 1⎤
⎡0 0 0⎤
а) ν = 3 Γ3 = ⎢⎢0 0 1⎥⎥ ; б) ν = 2 Γ2 = ⎢⎢0 0 0⎥⎥ ; в) ν =1 Γ1 = ⎢⎢0 0 0⎥⎥ .
⎢⎣0 0 0⎥⎦
⎣⎢0 0 0⎦⎥
⎢⎣0 0 0⎦⎥
Решим поставленную задачу в форме (8). Решение уравнения Сильвестра (4) относительно матриц Т и L и вычисление матрицы G дает:
⎡1 1 1⎤
а) Т3 = ⎢⎢1 0 1⎥⎥ , L3 =[ 0 0 1]T , G3 =[ 0 0 1]T ;
⎢⎣0 0 1⎥⎦
⎡1 0 1⎤
б) Т2 = ⎢⎢0 0 1⎥⎥ , L2 =[ 0 1 1]T , G2 =[ 0 1 1]T ;
⎢⎣0 0 1⎥⎦
⎡0 0 1⎤
в) Т1 = ⎢⎢0 0 1⎥⎥ , L1 =[ 1 1 1]T , G1 =[ 1 1 1]T .
⎢⎣0 0 1⎦⎥
В соответствии с (8) и поскольку матрица Γ имеет индекс нильпотентности, равный ν, очевидно, что начиная с момента k ≥ ν вектор состояния z ДНУ должен будет с точностью до матрицы преобразования подобия Т совпасть с вектором состояния χ исходной ЛДДС.
Покажем это, полагая, что входная последовательность u ( k ) ЛДДС на первых семи тактах
имеет вид u ( k ):1100110 , а начальное состояние χ( 0) ЛДДС определяется вектором χ( 0) =[0 0 1]T .
k 01 2 3 4 5 67
ν u(k) 0 1 1 0 0 1 1 0
χT ( k ) 001 100 111 110 111 011 100 111
zT ( k )
000 000 001 010 101 011 110 101
3
(Т3χ)T ( k )
111
110
101
010
101
011
110
101
zT ( k )
000 000 011 100 011 111 100 011
2
(Т2χ)T ( k )
111
100
011
100
011
111
100
011
zT ( k )
000 000 111 000 111 111 000 111
1
(Т1χ)T ( k )
111
000
111
000
111
111
000
111
Из таблицы видно, что начиная с k-го такта, т.е. с выполнением условия k = ν , вектор
состояния z синтезированного ДНУ повторяет в форме z ( k ) =Т χ ( k ) состояние наблюдае-
мой ЛДДС. Таким образом, иллюстрируется утверждение: чем меньше индекс нильпотентности матрицы Γ состояния ДНУ, тем выше скорость сходимости процесса по ВНН.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 11
80 А. В. Ушаков, Е. С. Яицкая
С использованием полученных результатов структурно-функциональная схема процесса
двоичного динамического наблюдения вектора текущего состояния заданной ЛДДС примет
вид, представленный на рис. 1.
u(k)
1 χ1(k)
χ1(k+1) d
χ2(k+1)
2 d
χ2(k) χ3(k+1)
d
3
ξ(k) d
3
z3(k)
χ3(k)
3 d
z3(k)
2 d
z2(k)
2 d
z2(k)
1 d
z1(k)
ДНУ ν=3
3 d
1 d
z1(k)
ДНУ ν=2
z3(k)
2 d
z2(k)
1 z1(k) d
ДНУ ν=1
Рис. 1
Основной результат. Поставим задачу помехозащитного декодирования систематиче-
ских кодов [4] как задачу определения вектора χ ( 0) начального состояния регистра канала
связи (РКС).
Кодирующее устройство (КУ), на выходе которого формируется ( n, k ) -помехозащи-
щенный код y , выводимый в канал связи в виде двоичной кодовой последовательности
y ( k ) старшим разрядом вперед, представляется п-разрядным регистром сдвига, начальное состояние которого x( 0) представляет собой передаваемую помехозащищенную кодовую по-
сылку. Векторно-матричное модельное представление КУ имеет вид
x ( k +1) = F x ( k ); x ( 0); y ( k ) = P x ( k ) ,
где F — матрица размерностью n×n является нильпотентной с индексом ν = n [5].
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 11
Помехозащитное декодирование систематических кодов
81
Формирователь импульсной помехи ξ , которая в канале связи (КС) искажает передаваемую кодовую посылку y , также представим п-разрядным регистром сдвига. РКС характе-
ризуется нулевой входной последовательностью и вектором начального состояния χ ( 0) , ко-
торый представляет собой п-разрядный вектор помехи ξ , выводимый в КС в виде последова-
тельности ξ ( k ) старшим разрядом вперед. Векторно-матричное описание РКС имеет вид
χ ( k +1) = Aχ ( k ); χ ( 0); ξ ( k ) = C χ ( k ) .
Матрица А совпадает с матрицей F и также является нильпотентной с индексом нильпотентности ν = n .
Процесс искажения кодовой последовательности y ( k ) при передаче по КС представим
суммированием в простом двоичном поле GF ( 2) , в результате чего формируется искажен-
ная кодовая комбинация f = y +ξ в виде кодовой последовательности f ( k ) = y ( k )+ξ ( k ) .
Процесс декодирования реализуем, построив ДНУ, формирующее к моменту k = n со-
стояние z ( n) , которое с точностью до матрицы преобразования подобия Tχ представляло бы
собой вектор χ ( 0) начального состояния РКС. Векторно-матричное описание ДНУ — деко-
дирующего устройства (ДКУ) — принимает вид
z ( k +1) = Γ z ( k )+ L f ( k ); z ( 0) .
Поставленная задача помехозащитного декодирования опирается на следующее утверждение.
Утверждение 2. Если ДНУ начального состояния χ ( 0) функционирует так, что всегда
z ( 0) = 0 , т.е. перед запуском его состояние обнуляется, матрица Γ принадлежит показателю
µ = n , матрицы А и F обладают индексом нильпотентности ν = n [5], матрица преобразова-
ния подобия Tx обладает свойством
Tx GT = O ,
(9)
где G — образующая матрица систематического кода, то выполняется соотношение вектор-
но-матричного подобия z ( n) =Tχ χ ( 0) , О — нулевая матрица.
Доказательство утверждения строится на определениях свойств нильпотентности мат-
рицы и принадлежности матрицы показателю, а также на использовании условия z ( 0) = 0 .
Следует заметить, что в силу (9) матрица Tx как решение матричного уравнения Силь-
вестра
Tχ A+ΓTχ = L C , Tx F +Γ Tx = L P
(10)
является проверочной матрицей [6] систематического кода.
Вектор x ( 0) формируется из информационной части xи ( 0) систематического помехо-
защищенного кода с помощью образующей матрицы G кода в силу соотношения
x ( 0) = GT xи ( 0) .
В качестве примера рассмотрим аналитическое решение задачи конструирования деко-
дирующего устройства в форме ДНУ циклического кода с образующим многочленом
g( x) = x 2 + x + 1 . Сконструируем ДКУ в форме ДНУ и кодирующее устройство в виде мо-
дельных представлений „вход—состояние—выход“ с матричными компонентами
⎡0 1 0⎤
A = F = ⎢⎢0 0 1⎥⎥ , C = P =[1 0 0] соответственно.
⎢⎣0 0 0⎥⎦
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 11
82 А. В. Ушаков, Е. С. Яицкая
Выберем в качестве модели ДНУ регистр сдвига второго порядка, матрица Γ векторноматричного описания которого будет иметь следующий вид:
Γ
=
⎡1 ⎣⎢1
1⎤ 0⎦⎥
.
Решение относительно матрицы Т матричного уравнения (10) дает
T
=
⎡1 ⎣⎢1
1 0
0⎤ 1⎦⎥
.
Следует отметить тождественность результата для вычисленной матрицы Т канониче-
скому [6] представлению проверочной матрицы
H
⎛ ⎜⎝⎜
H
=
⎡⎣G T
I
⎤T ⎦
=
⎡1 ⎢⎣1
1 0
0⎤T 1⎦⎥
⎞ ⎟⎠⎟
циклическо-
го кода, который в рассматриваемом примере соответствует образующему многочлену
g ( x) = x2 + x+1.
Заметим также, что процесс декодирования состоит в вычислении вектора ошибки по-
средством умножения матрицы TT на вектор начального состояния χ ( 0) РКС. Структурная
схема процесса декодирования циклического
g ( x) = x2 + x+1 представлена на рис. 2.
χ3(0)
χ2(0)
кода с образующим
χ1(0)
многочленом
РКС 3 21 d d d ξ(k)
xи(0)
3 d
x3(0)
2 d
x2(0) 1
d
КУ x1(0)
ДНУ f(k)
2 d
z2(k)
1 z1(k)
d
Рис. 2
Заключение. Теория и практика динамического наблюдения за двоичными полями Галуа обнаруживают новые возможности использования последних в задачах помехозащитного
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 11
Помехозащитное декодирование систематических кодов
83
декодирования систематических помехозащищенных кодов. Авторы полагают, что формализм матричного уравнения Сильвестра, на котором базируется алгоритмистика конструирования матричных компонентов ДНУ, позволит создать банк реализаций декодирующих устройств систематических кодов.
СПИСОК ЛИТЕРАТУРЫ
1. Мельников А. А., Ушаков А. В. Двоичные динамические системы дискретной автоматики. СПб: СПбГУ ИТМО, 2005.
2. Кузовков Н. Т. Модальное управление и наблюдающие устройства. М.: Машиностроение, 1976.
3. Мирошник И. В. Теория автоматического управления. Линейные системы. СПб: Питер, 2005.
4. Емельянов Г. А., Шварцман В. О. Теория передачи дискретной информации. М.: Связь, 1979.
5. Мельников А. А., Рукуйжа Е. В., Ушаков А. В. Использование свойств матриц для обнаружения неустойчивых циклов и неподвижных состояний двоичных динамических систем // Науч.-технич. вестн. СПбГИТМО(ТУ). 2002. Вып. 6. С. 243—249.
6. Тутевивич В. Н. Телемеханика. М.: Высш. школа, 1985.
Анатолий Владимирович Ушаков Елена Сергеевна Яицкая
Сведения об авторах — д-р техн. наук, профессор; Санкт-Петербургский государственный
университет информационных технологий, механики и оптики, кафедра систем управления и информатики; E-mail: Ushakov-AVG@yandex.ru — аспирант; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра систем управления и информатики; E-mail: yaitskayaes@mail.ru
Рекомендована кафедрой систем управления и информатики
Поступила в редакцию 01.07.09 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 11
УДК 621.398.1
А. В. УШАКОВ, Е. С. ЯИЦКАЯ
ПОМЕХОЗАЩИТНОЕ ДЕКОДИРОВАНИЕ СИСТЕМАТИЧЕСКИХ КОДОВ
Определяется зависимость скорости сходимости процесса наблюдения от индекса нильпотентности матрицы состояния динамического наблюдающего устройства (ДНУ). Рассматривается задача помехозащитного декодирования в форме построения ДНУ вектора начального состояния системы.
Ключевые слова: динамическое наблюдающее устройство, вектор невязки наблюдения, помехозащитное декодирование.
Введение. Базовые концепции двоичного динамического наблюдения. Для рассмотрения задачи двоичного динамического наблюдения представим линейную двоичную динамическую систему (ЛДДС) [1, 2], состояние которой подлежит наблюдению, имеющую векторно-матричное описание
χ ( k +1) = A χ ( k )+ B u ( k ), χ ( 0) = χ0 , ξ ( k ) = C χ ( k )+ H u(k) ,
(1)
где χ, u, ξ — соответственно п-мерный вектор состояния, r-мерный вектор входной последо-
вательности, l-мерный вектор выходной последовательности; матрицы A, B, C, Н согласованы по размерности с векторами χ, u и ξ . Элементы векторов и матриц принадлежат двоичному
простому полю Галуа GF ( 2) .
Двоичное динамическое наблюдающее устройство (ДНУ), использующее всю доступную для непосредственного измерения информацию об ЛДДС (1) в виде входной последова-
тельности u ( k ) и выходной — y ( k ), реализуется в форме следующей зависимости:
z ( k +1) = Γ z ( k )+ L ξ ( k )+G u ( k ), z ( 0) = z0 ,
(2)
где z — т-мерный вектор состояния ДНУ, матрица Γ определяет динамику процесса наблюдения, а пара матриц ( L,G ) обладает следующими свойствами:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 11
78 А. В. Ушаков, Е. С. Яицкая
L = arg { contr ( Γ, L) },G = arg { contr ( Γ,G) } ,
где contr{ } — предикат наличия полной управляемости пары матриц [3].
Рассмотрим задачу определения вектора χ состояния системы (1) в среде ДНУ (2) в виде
z( k)=T χ( k)+θ( k), ∀k ,
(3)
где Т — матрица преобразования подобия (в общем случае — особого); θ(k) — вектор невязки наблюдения (ВНН).
Сформулируем следующее утверждение. Утверждение 1. Если матрицы T , L,G удовлетворяют матричным соотношениям
ΓT +T A=LC, G=T B,
(4)
то процесс по ВНН θ( k ) описывается рекуррентным векторно-матричным уравнением
θ( k +1) = Γ θ( k ), θ( 0) =T χ ( 0)+ z ( 0) .
(5)
Доказательство утверждения проведем путем подстановки в (5) векторно-матричных соотношений (1), (2) и (4), в результате чего снова приходим к (5).
Для решения задачи определения вектора χ ( k ) текущего состояния ЛДДС (1) восполь-
зуемся явным (показательным) решением (5) и условием обнуления состояния ДНУ при за-
пуске ( z ( 0) = 0 ). С учетом этих обстоятельств имеем
θ( k)=Γk T χ( 0) .
(6)
В свою очередь, подстановка (6) в (3) дает
z( k)=T χ( k)+Γk θ( 0).
(7)
Пусть матрица Γ состояния ДНУ обладает свойством нильпотентности с индексом ν , тогда при k ≥ ν устанавливается равенство
z( k)=T χ( k), k ≥ν.
(8)
Таким образом, вектор z ( k ) состояния ДНУ с точностью до матрицы преобразования
подобия Т задает текущее состояние вектора χ ( k ) наблюдаемой ЛДДС (1). Причем скорость
сходимости процесса по ВНН тем выше, чем меньше индекс нильпотентности матрицы Γ состояния ДНУ. Подтвердим данное утверждение примерами.
Примеры построения двоичных наблюдающих устройств. Рассмотрим задачу синтеза ДНУ для определения вектора текущего состояния ЛДДС, ( A, B,C, H )-описание которой характеризуется матрицами
⎡0 1 1⎤ ⎡1⎤
A = ⎢⎢1 0 0⎥⎥ , B = ⎢⎢0⎥⎥ , C =[ 0 1 0] , H =[ 0] .
⎢⎣0 1 0⎦⎥ ⎢⎣1⎥⎦
С целью решения поставленной задачи в соответствии с выражениями (7) и (8) выберем в качестве модели ДНУ регистр сдвига третьего порядка. Для определения вектора текущего состояния представленной ЛДДС рассмотрим матрицы состояния ДНУ с различными индексами нильпотентности:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 11
Помехозащитное декодирование систематических кодов
79
⎡0 1 0⎤
⎡0 0 1⎤
⎡0 0 0⎤
а) ν = 3 Γ3 = ⎢⎢0 0 1⎥⎥ ; б) ν = 2 Γ2 = ⎢⎢0 0 0⎥⎥ ; в) ν =1 Γ1 = ⎢⎢0 0 0⎥⎥ .
⎢⎣0 0 0⎥⎦
⎣⎢0 0 0⎦⎥
⎢⎣0 0 0⎦⎥
Решим поставленную задачу в форме (8). Решение уравнения Сильвестра (4) относительно матриц Т и L и вычисление матрицы G дает:
⎡1 1 1⎤
а) Т3 = ⎢⎢1 0 1⎥⎥ , L3 =[ 0 0 1]T , G3 =[ 0 0 1]T ;
⎢⎣0 0 1⎥⎦
⎡1 0 1⎤
б) Т2 = ⎢⎢0 0 1⎥⎥ , L2 =[ 0 1 1]T , G2 =[ 0 1 1]T ;
⎢⎣0 0 1⎥⎦
⎡0 0 1⎤
в) Т1 = ⎢⎢0 0 1⎥⎥ , L1 =[ 1 1 1]T , G1 =[ 1 1 1]T .
⎢⎣0 0 1⎦⎥
В соответствии с (8) и поскольку матрица Γ имеет индекс нильпотентности, равный ν, очевидно, что начиная с момента k ≥ ν вектор состояния z ДНУ должен будет с точностью до матрицы преобразования подобия Т совпасть с вектором состояния χ исходной ЛДДС.
Покажем это, полагая, что входная последовательность u ( k ) ЛДДС на первых семи тактах
имеет вид u ( k ):1100110 , а начальное состояние χ( 0) ЛДДС определяется вектором χ( 0) =[0 0 1]T .
k 01 2 3 4 5 67
ν u(k) 0 1 1 0 0 1 1 0
χT ( k ) 001 100 111 110 111 011 100 111
zT ( k )
000 000 001 010 101 011 110 101
3
(Т3χ)T ( k )
111
110
101
010
101
011
110
101
zT ( k )
000 000 011 100 011 111 100 011
2
(Т2χ)T ( k )
111
100
011
100
011
111
100
011
zT ( k )
000 000 111 000 111 111 000 111
1
(Т1χ)T ( k )
111
000
111
000
111
111
000
111
Из таблицы видно, что начиная с k-го такта, т.е. с выполнением условия k = ν , вектор
состояния z синтезированного ДНУ повторяет в форме z ( k ) =Т χ ( k ) состояние наблюдае-
мой ЛДДС. Таким образом, иллюстрируется утверждение: чем меньше индекс нильпотентности матрицы Γ состояния ДНУ, тем выше скорость сходимости процесса по ВНН.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 11
80 А. В. Ушаков, Е. С. Яицкая
С использованием полученных результатов структурно-функциональная схема процесса
двоичного динамического наблюдения вектора текущего состояния заданной ЛДДС примет
вид, представленный на рис. 1.
u(k)
1 χ1(k)
χ1(k+1) d
χ2(k+1)
2 d
χ2(k) χ3(k+1)
d
3
ξ(k) d
3
z3(k)
χ3(k)
3 d
z3(k)
2 d
z2(k)
2 d
z2(k)
1 d
z1(k)
ДНУ ν=3
3 d
1 d
z1(k)
ДНУ ν=2
z3(k)
2 d
z2(k)
1 z1(k) d
ДНУ ν=1
Рис. 1
Основной результат. Поставим задачу помехозащитного декодирования систематиче-
ских кодов [4] как задачу определения вектора χ ( 0) начального состояния регистра канала
связи (РКС).
Кодирующее устройство (КУ), на выходе которого формируется ( n, k ) -помехозащи-
щенный код y , выводимый в канал связи в виде двоичной кодовой последовательности
y ( k ) старшим разрядом вперед, представляется п-разрядным регистром сдвига, начальное состояние которого x( 0) представляет собой передаваемую помехозащищенную кодовую по-
сылку. Векторно-матричное модельное представление КУ имеет вид
x ( k +1) = F x ( k ); x ( 0); y ( k ) = P x ( k ) ,
где F — матрица размерностью n×n является нильпотентной с индексом ν = n [5].
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 11
Помехозащитное декодирование систематических кодов
81
Формирователь импульсной помехи ξ , которая в канале связи (КС) искажает передаваемую кодовую посылку y , также представим п-разрядным регистром сдвига. РКС характе-
ризуется нулевой входной последовательностью и вектором начального состояния χ ( 0) , ко-
торый представляет собой п-разрядный вектор помехи ξ , выводимый в КС в виде последова-
тельности ξ ( k ) старшим разрядом вперед. Векторно-матричное описание РКС имеет вид
χ ( k +1) = Aχ ( k ); χ ( 0); ξ ( k ) = C χ ( k ) .
Матрица А совпадает с матрицей F и также является нильпотентной с индексом нильпотентности ν = n .
Процесс искажения кодовой последовательности y ( k ) при передаче по КС представим
суммированием в простом двоичном поле GF ( 2) , в результате чего формируется искажен-
ная кодовая комбинация f = y +ξ в виде кодовой последовательности f ( k ) = y ( k )+ξ ( k ) .
Процесс декодирования реализуем, построив ДНУ, формирующее к моменту k = n со-
стояние z ( n) , которое с точностью до матрицы преобразования подобия Tχ представляло бы
собой вектор χ ( 0) начального состояния РКС. Векторно-матричное описание ДНУ — деко-
дирующего устройства (ДКУ) — принимает вид
z ( k +1) = Γ z ( k )+ L f ( k ); z ( 0) .
Поставленная задача помехозащитного декодирования опирается на следующее утверждение.
Утверждение 2. Если ДНУ начального состояния χ ( 0) функционирует так, что всегда
z ( 0) = 0 , т.е. перед запуском его состояние обнуляется, матрица Γ принадлежит показателю
µ = n , матрицы А и F обладают индексом нильпотентности ν = n [5], матрица преобразова-
ния подобия Tx обладает свойством
Tx GT = O ,
(9)
где G — образующая матрица систематического кода, то выполняется соотношение вектор-
но-матричного подобия z ( n) =Tχ χ ( 0) , О — нулевая матрица.
Доказательство утверждения строится на определениях свойств нильпотентности мат-
рицы и принадлежности матрицы показателю, а также на использовании условия z ( 0) = 0 .
Следует заметить, что в силу (9) матрица Tx как решение матричного уравнения Силь-
вестра
Tχ A+ΓTχ = L C , Tx F +Γ Tx = L P
(10)
является проверочной матрицей [6] систематического кода.
Вектор x ( 0) формируется из информационной части xи ( 0) систематического помехо-
защищенного кода с помощью образующей матрицы G кода в силу соотношения
x ( 0) = GT xи ( 0) .
В качестве примера рассмотрим аналитическое решение задачи конструирования деко-
дирующего устройства в форме ДНУ циклического кода с образующим многочленом
g( x) = x 2 + x + 1 . Сконструируем ДКУ в форме ДНУ и кодирующее устройство в виде мо-
дельных представлений „вход—состояние—выход“ с матричными компонентами
⎡0 1 0⎤
A = F = ⎢⎢0 0 1⎥⎥ , C = P =[1 0 0] соответственно.
⎢⎣0 0 0⎥⎦
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 11
82 А. В. Ушаков, Е. С. Яицкая
Выберем в качестве модели ДНУ регистр сдвига второго порядка, матрица Γ векторноматричного описания которого будет иметь следующий вид:
Γ
=
⎡1 ⎣⎢1
1⎤ 0⎦⎥
.
Решение относительно матрицы Т матричного уравнения (10) дает
T
=
⎡1 ⎣⎢1
1 0
0⎤ 1⎦⎥
.
Следует отметить тождественность результата для вычисленной матрицы Т канониче-
скому [6] представлению проверочной матрицы
H
⎛ ⎜⎝⎜
H
=
⎡⎣G T
I
⎤T ⎦
=
⎡1 ⎢⎣1
1 0
0⎤T 1⎦⎥
⎞ ⎟⎠⎟
циклическо-
го кода, который в рассматриваемом примере соответствует образующему многочлену
g ( x) = x2 + x+1.
Заметим также, что процесс декодирования состоит в вычислении вектора ошибки по-
средством умножения матрицы TT на вектор начального состояния χ ( 0) РКС. Структурная
схема процесса декодирования циклического
g ( x) = x2 + x+1 представлена на рис. 2.
χ3(0)
χ2(0)
кода с образующим
χ1(0)
многочленом
РКС 3 21 d d d ξ(k)
xи(0)
3 d
x3(0)
2 d
x2(0) 1
d
КУ x1(0)
ДНУ f(k)
2 d
z2(k)
1 z1(k)
d
Рис. 2
Заключение. Теория и практика динамического наблюдения за двоичными полями Галуа обнаруживают новые возможности использования последних в задачах помехозащитного
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 11
Помехозащитное декодирование систематических кодов
83
декодирования систематических помехозащищенных кодов. Авторы полагают, что формализм матричного уравнения Сильвестра, на котором базируется алгоритмистика конструирования матричных компонентов ДНУ, позволит создать банк реализаций декодирующих устройств систематических кодов.
СПИСОК ЛИТЕРАТУРЫ
1. Мельников А. А., Ушаков А. В. Двоичные динамические системы дискретной автоматики. СПб: СПбГУ ИТМО, 2005.
2. Кузовков Н. Т. Модальное управление и наблюдающие устройства. М.: Машиностроение, 1976.
3. Мирошник И. В. Теория автоматического управления. Линейные системы. СПб: Питер, 2005.
4. Емельянов Г. А., Шварцман В. О. Теория передачи дискретной информации. М.: Связь, 1979.
5. Мельников А. А., Рукуйжа Е. В., Ушаков А. В. Использование свойств матриц для обнаружения неустойчивых циклов и неподвижных состояний двоичных динамических систем // Науч.-технич. вестн. СПбГИТМО(ТУ). 2002. Вып. 6. С. 243—249.
6. Тутевивич В. Н. Телемеханика. М.: Высш. школа, 1985.
Анатолий Владимирович Ушаков Елена Сергеевна Яицкая
Сведения об авторах — д-р техн. наук, профессор; Санкт-Петербургский государственный
университет информационных технологий, механики и оптики, кафедра систем управления и информатики; E-mail: Ushakov-AVG@yandex.ru — аспирант; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра систем управления и информатики; E-mail: yaitskayaes@mail.ru
Рекомендована кафедрой систем управления и информатики
Поступила в редакцию 01.07.09 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 11