РЕКУРРЕНТНОЕ СИСТЕМАТИЧЕСКОЕ ПОМЕХОЗАЩИТНОЕ ПРЕОБРАЗОВАНИЕ КОДОВ: ВОЗМОЖНОСТИ АППАРАТА ЛИНЕЙНЫХ ДВОИЧНЫХ ДИНАМИЧЕСКИХ СИСТЕМ
17
УДК [517.938 + 519.713/718]: 621.398
А. В. УШАКОВ, Е. С. ЯИЦКАЯ
РЕКУРРЕНТНОЕ СИСТЕМАТИЧЕСКОЕ ПОМЕХОЗАЩИТНОЕ ПРЕОБРАЗОВАНИЕ КОДОВ: ВОЗМОЖНОСТИ АППАРАТА ЛИНЕЙНЫХ ДВОИЧНЫХ ДИНАМИЧЕСКИХ СИСТЕМ
Рассматривается проблема формирования матричных компонентов векторноматричного описания двоичных динамических систем помехозащитного преобразования кодов. Показано, что базис представления матричных компонентов зависит от проверочной и образующей матриц помехозащищенного кода, а также от его образующего модулярного многочлена. Ключевые слова: двоичная динамическая система, систематический помехозащищенный код, проверочная и образующая матрицы, образующий модулярный многочлен, помехозащитное преобразование кодов.
В работах [1, 2], посвященных преобразованию кодов (ПК), представленных в виде кодовых последовательностей, получен конструктивный инструментарий модельного представления процедур ПК в виде линейных последовательностных машин (ЛПМ). Так как термин ЛПМ выпадает из общей теории систем, то со временем он был заменен понятием „линейная двоичная динамическая система “ (ЛДДС). Таким образом, ЛДДС, использующая в основном векторно-матричные модельные представления (ВММП) аппарата пространства состояний (АПС), со временем стала инструментом ПК, в том числе и помехозащитного преобразования систематических кодов в задачах кодирования и декодирования [3—5]. Из теории АПС [6] известно, что одной из проблем формирования векторно-матричного модельного представления динамических процессов над бесконечными и конечными полями является поиск базиса представления, в котором матричные компоненты ВММП обладают желаемыми исследователю свойствами. Причем возможность выбора базиса представления при построении ВММП процессов общего вида практически не ограничена. К сожалению, этого нельзя сказать о ВММП ЛДДС, использованных в задачах помехозащитного преобразования кодов.
Известно [7, 8], что систематическое помехозащитное преобразование кодов (ППК) в задачах кодирования и декодирования может быть осуществлено несколькими способами, основанными на различном описании процесса ППК. Тем не менее эти способы имеют единое
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
18 А. В. Ушаков, Е. С. Яицкая
функциональное представление, структурная реализация которого приведена на рис. 1, здесь КУ — помехозащитное кодирующее устройство, формирующее на своем выходе помехозащищенный код (ПЗК); КС — канал связи, выполняющий функцию среды искажения в задаче ППК; ДКУ — помехозащитное декодирующее устройство, формирующее на своем выходе синдром ошибки (факта или места искажения); ФСК — формирователь сигнала коррекции;
⊕ — сумматор по модулю два; a (∗) — помехонезащищенный информационный код
(ПНЗИК); y (∗) — помехозащищенный код передачи; ξ(∗) — код помехи, воздействующей
на код y (∗) при его передаче по КС; f (∗) — искаженный в КС ПЗК; E (∗) — код синдрома
ошибки (факта или места искажения); η(∗) — код коррекции; y (∗) — откорректированный
принятый из КС код, удовлетворяющий условию
y (∗) = {arg min y (∗) − y (∗) } . η(∗)
G
ξ(*) H
УКК H+
a(*) КУ y(*)
f(*)
ДКУ E(*)
η(*) ФСК
y(*)
КС
Рис. 1
Символ „ ∗ “ опускается, если все коды, использованные в процедуре помехозащитного преобразования, рассматриваются как векторы-строки, преобразование которых осуществляется в соответствии с векторно-матричными соотношениями:
y = aG, f = y + ξ, E = fH, η = EH+ , y = f + η .
(1)
Операцию сложения следует понимать как процедуру суммирования по модулю два; a : dim a = k; y : dim y = n; f : dim f = n; ξ :dim ξ = n; E :dim E = m = n − k; η :dim η = n;
y :dim y = n; G — образующая (k × n) -матрица ПЗК; H — проверочная (n × m) -матрица
ПЗК, которая удовлетворяет условию {G,H} = arg{GH = 0} .
Если коды, используемые в процедуре помехозащитного преобразования кодов, рас-
сматриваются как модулярные многочлены (ММ) над полем Галуа GF( p) p = 2 , то символ
„ ∗ “ принимает значение переменной x . При этом преобразование кодов-ММ осуществляется в соответствии с модулярными полиномиальными соотношениями:
y(
x)
=
a(
x)
xm
+
r
(
x)
:rest
y g
(x) (x)
=
0,
r
(
x)
=
rest
a
(x) xm g ( x)
⎫ ,⎪ ⎪
f (x) = y(x) + ξ(x),
E
(x)
=
rest
f g
(x) (x)
=
rest
ξ(x) g ( x)
,
⎪⎪ ⎬ ⎪ ⎪ ⎪
η(x) = ξ(x), y(x) = f (x) + η(x),
⎭⎪
(2)
в которых a ( x) : deg a ( x) = k −1; y ( x) : deg y ( x) = n −1; f ( x) : deg f ( x) = n −1; ξ( x) :deg ξ( x) = n −1; E ( x) : deg E ( x) = m −1; η( x) :deg η( x) = n −1; y ( x) :deg y ( x) = n −1;
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
Рекуррентное систематическое помехозащитное преобразование кодов
19
g ( x) — образующий модулярный многочлен ПЗК, представляющий собой неприводимый
многочлен степени m , имеющий не менее dmin = 2s +1 ненулевых элементов. Символ „ ∗ “ принимает смысл дискретного времени q , выраженного в числе тактов
длительности ∆t , при этом все коды, используемые в процедуре помехозащитного преобразования, рассматриваются как кодовые последовательности, преобразование которых осуществляется рекуррентным образом в соответствии с векторно-матричными соотношениями, параметризованными дискретным временем q :
xк ( q + 1) = Aк xк (q) + Bк uк (q); y (q) = Nuк (q),
(3)
xк (q +1) = Axк (q); y (q) = Cк xк (q),
(4)
f (q) = y(q)+ ξ(q),
(5)
xд (q + 1) = Aд xд (q) + Bдuд (q) ,
(6)
в которых uк (q) = a (q) — входная двоичная последовательность, представляющая собой
вводимый в КУ ПНЗИК; xк — вектор состояния КУ, размерности dim xк = m ; y (q) — фор-
мируемая ПЗК-последовательность; Aк — (m × m) -матрица состояния КУ; Bк — (m ×1) -
матрица входа КУ;
Cк
=
⎣⎡1
O1×( n−1)
⎤ ⎦
— матрица выхода КУ;
N = [1]
— матрица вход—выход
КУ; A — нильпотентная матрица с индексом ν = m ; uд (q) = f (q) — входная двоичная последовательность, представляющая собой принятый из канала связи искаженный системати-
ческий ПЗК; xд — вектор состояния ДКУ размерности dim xд = m ; Aд — (m × m) -матрица
состояния ДКУ; Bд — (m ×1) -матрица входа ДКУ.
Постановка задачи. Ставится задача синтеза ЛДДС помехозащитного преобразования
кодов с матрицами Aк , Bк , Aд , Bд , A, Cк , N как функциями образующего модулярного
многочлена ПЗК g ( x) , его проверочной H и образующей G матриц:
{Aк , Bк , Aд , Bд , A,Cк , N} = Ψ ( g ( x), H,G ) .
Приведенные выше методы помехозащитного преобразования кодов характеризуются различным уровнем связи их аналитического описания с возможной аппаратной реализацией. Действительно, первый метод, представленный системой выражений (1), использующий векторно-матричное описание ППК, не параметризованное временем, приводит к системе скалярных аналитических выражений (САВ), которые позволяют строить устройства помехозащитного кодирования и декодирования [8].
Второй метод, представленный системой выражений (2), приводит к двум видам аппаратной реализации ППК: схемотехнической и программной, описываемой рекуррентными процедурами параметризованной дискретным временем q , задаваемыми соотношениями
(3)—(6). Схемотехническая реализация ППК имеет две версии: первая строится по схеме
„ g ( x) → (G, H ) → САВ “; вторая — по схеме „ g ( x) → УДММ :Φ (d ) = g−1 (d ) → СР Φ (d ) “,
УДММ — устройство деления ММ, СР Φ (d ) — структурная реализация передаточной функ-
ции Φ(d ) .
Для формирования программной реализации устройств ППК в форме (3)—(6) сформулируем необходимые определение и утверждение.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
20 А. В. Ушаков, Е. С. Яицкая
Определение 1. Помехозащищенный (n, k ) -код, множество кодовых комбинаций кото-
рого yi мощностью [ yi ] = 2k , описываемых модулярными многочленами yi ( x) , обладаю-
щими рекуррентным свойством
rest
yi ( x) g ( x)
=
0
,
(7)
называется циклическим помехозащищенным кодом.
□
Утверждение 1. Код, множество кодовых комбинаций которого формируется в соот-
ветствии с первым соотношением системы (2), обладает рекуррентным свойством (7), т.е. яв-
ляется циклическим ПЗК.
□
Д о к а з а т е л ь с т в о утверждения сводится к доказательству наличия у кода с ММ (2)
рекуррентного свойства (7). Для этой цели полиномиальный компонент a ( x) xm представим
в форме a ( x) xm = Q ( x) g ( x) + r ( x) . Если полученное выражение подставить в первое соот-
ношение системы (2) и осуществить приведение по модулю два, то получим
y ( x) = {Q ( x) g ( x) + r ( x) + r ( x)}mod 2 = Q ( x) g ( x) .
(8)
Нетрудно видеть, что представление (8) определяет наличие у y ( x) рекуррентного
свойства (7).
■
По существу, первое выражение представления (2) ММ y ( x) циклического ПЗК содер-
жит алгоритм его формирования в среде рекуррентного кодирующего устройства. При этом КУ функционирует посредством коммутации структуры. Это вызвано тем, что при формиро-
вании (n, k ) -кода в течение первых k тактов k-разрядная информационная часть в виде кодо-
вой последовательности одновременно подается в КС и на вход УДММ для вычисления остатка в форме
xT
(Q)
=
K
⎨⎪⎧rest ⎪⎩
⎛ ⎝⎜⎜
a(x) xm g ( x)
⎠⎟⎞⎟⎭⎪⎪⎬⎫
.
По принятии информационной части из источника дискретной информации (ИДИ) вход
КС переключается с выхода ИДИ на выход УДММ, в котором сформировался остаток. Все
обратные связи в УДММ в этот момент разрываются, процесс деления останавливается, а
УДММ без связей становится т-разрядным регистром сдвига. Все перечисленные коммута-
ции цепей и связей осуществляются специально вводимым в состав КУ устройством комму-
тации (УК). Таким образом, помехозащитное КУ представляет собой объединение УДММ и
УК, функционирующее в два этапа. На первом оно описывается ЛДДС вида (3), а на вто-
ром — вида (4).
Третье выражение представления (2) ММ E ( x) синдрома ошибки по существу описы-
вает алгоритм функционирования рекуррентного декодирующего устройства, который предназначен для проверки сохранности рекуррентного свойства (7) применительно к принятому
из КС искаженному коду с ММ f ( x) = y ( x) + ξ ( x) путем деления этого многочлена на обра-
зующий g ( x) . Если E ( x) = 0 , то принимается решение, что f ( x) = y ( x) . Если E ( x) ≠ 0 , то
синдром используется как адрес искажений кода. Помехозащитное ДКУ есть функциональное объединение УДММ и устройства съема синдрома, отражающее состояние УДММ в момент q = n так, что код
K {E ( x)} = xдT (q) q=n .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
Рекуррентное систематическое помехозащитное преобразование кодов
21
Таким образом, УДММ в фазе вычисления остатка описывается ЛДДС вида (6). Утверждение 2. Матрица Bк ЛДДС УДММ кодирующего устройства (3) с точностью
до операции транспонирования совпадает с последней (k-й) строкой Gk матрицы G , входя-
щей в состав образующей матрицы G = ⎣⎡I(k×k) G⎦⎤ так, что выполняется соотношение
{ }BTк = Gk = K g ( x) + xm ,
(9)
где K{ ( •) } — код ММ ( •) .
□
Д о к а з а т е л ь с т в о . Рассмотрим процесс кодирования для случая помехонезащищенного кода a , имеющего единицу только в младшем разряде, а в остальных — нули
{ММ : a ( x) = 1} . Это значит, что входная последовательность uк (q) с учетом передачи кодов
и ММ старшим разрядом вперед будет иметь вид
uк (q) = ⎣⎡ uк ( 0) = 0, uк ( 1) = 0,…, uк ( k − 2) = 0, uк (k −1) = 1,uк (k ) = 0…⎦⎤ .
В течение первых (k −1) тактов ЛДДС УДММ кодирующее устройство будет находить-
ся в нулевом состоянии. При приеме элемента uк (q) q=k−1= 1 ЛДДС устройство деления мо-
дулярного многочлена КУ в силу (3) перейдет в состояние
( ) ( ) ( )xк q + 1 q+1=k = Aк xк q xк(q) q=0,k−1 = 0 + Bк uк q uк (q) q=k−1 = 1 = Bк .
Данное соотношение в транспонированном виде {xк (k ) = Βк }T определяет код
⎧ K ⎨⎪rest
⎩⎪
a(x) xm g ( x)
a( x)=1
=
rest
xm
g ( x)
=g(
x) +
⎫
x
m
⎪ ⎬
⎪⎭
остатка от деления, выводимый из КУ и задаваемый последней k-й строкой Gk матрицы G
кодов остатков так, что выполняется цепочка равенств
{ }xкT (k ) = BTк = Gk = K g ( x) + xm .
■
Соотношение (9) совместно с представлением функционирования рекуррентного КУ позволяет сконструировать его векторно-матричное описание в форме ЛДДС вида (3)—(4).
Алгоритм 1 (А1) формирования матриц {Aк , Bк , A,Cк , N } = Ψ ( g ( x),G )
ЛДДС рекуррентного помехозащитного кодирования
1. По заданному информационному массиву W мощности [W ] = Vи определить размер-
ность k помехонезащищенного информационного кода в силу соотношения
{ }k = min arg 2k ≥ Vи = [W ] .
2. По заданным категории системы, характеризующейся величиной Pдоп — допустимой
вероятностью приема ложной команды, и параметру модели двоичного канала связи в форме
p — вероятностью искажения разряда (бита) кода, заданному выражением p = max{ p01, p10} ,
определить кратность исправляемой ошибки s
∑ ∑s
=
min
arg
⎧⎪ ⎨
Nc
=
2m
−1≥
Nош
=
s
Cni &
n
Cni pi
(1 −
p )n−i
≤
Pдоп
⎫⎪ ⎬
,
⎪⎩ i=1 i=s+1 ⎭⎪
где Nc — число синдромов, Nош — число исправляемых ошибок.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
22 А. В. Ушаков, Е. С. Яицкая
3. В зависимости от величины s-кратности исправляемой ошибки — выбрать из таблиц неприводимых многочленов или сформировать с помощью БЧХ-технологии [9] реализацию
образующего ММ g ( x) степени m и сформировать (n, k ) -формат помехозащищенного ко-
да, где n удовлетворяет условию n = k + m .
4. Вычислить D -образ ММ g ( x) в форме
( ) ( )g ( d ) = D{ g ( x)} = g
x−1
, где g
x −1 =d
x−1
= x−mg ( x) .
5. Сконструировать передаточную функцию Фк (d ) УДММ КУ на образующий ММ
g ( x)
в
форме
Фк
(d)
=
1 g (d )
.
6. Пользуясь правилом Мейсона не касающихся контуров, построить две предваритель-
ные структурные реализации передаточной функции Фк (d ) на элементах памяти (ЭП) с пе-
редаточной функцией ΦЭП ( d ) = d в двух канонических базисах.
7. Произвести разметку входов и выходов ЭП каждой структурной реализации перемен-
ными xкi ( q + 1) на входе и xкi (q) на выходе, присвоив выходу самого правого ЭП перемен-
ную xк1 (q) , а его входу — xк1 ( q + 1) , и сформировать векторно-матричное описание (ВМО)
автономной версии УДММ xк ( q + 1) = Aк xк (q) , „списав“ реализации матриц Aк с отмечен-
ных структурных реализаций Фк (d ) .
8. Сформировать матрицу входа Bк УДММ КУ (3) в форме (9). 9. Структурно с использованием правила Мейсона или аналитически определить пере-
даточные функции УДММ КУ (3) для двух базисных реализаций матрицы Aк состояния
( )УДММ для процесса кодирования как Фк (d ) = Cк d −1I + Aк −1 Bк .
10. Выбрать для дальнейшего использования структурную реализацию передаточной
функции УДММ КУ, отмеченная версия которой характеризуется матрицей Aк ее состояния,
( )удовлетворяющей
условию
Aк
=
arg
⎧ ⎩⎨
g−1 (d )
=
Cк
d −1I + Aк
−1 Bк ⎭⎫⎬.
11. Сформировать матрицу A УДММ КУ, переведенного в режим регистра сдвига, по
отмеченной версии, выбранной в п. 10 структурной реализации Φ (d ) с разорванными обрат-
ными связями. 12. Дополнить УДММ УК устройством коммутации структуры УДММ и точки подклю-
чения входа канала связи с выхода ИДИ на выход устройства деления модулярных многочленов.
13. На конкретном примере проверить правильность функционирования устройства рекуррентного кодирования, задаваемого парой ВМО (3) и (4) со сформированными матрицами
(Aк , Bк , N) и (A,Cк ) .
■
Утверждение 3. Матрица Bд входа декодирующего рекуррентного устройства (6) удовлетворяет соотношению
( )Bд =
Hn
T
.
(10)
Д о к а з а т е л ь с т в о этого утверждения использует тот факт, что синдром E , вычисляемый в соответствии с соотношением E = fH , удовлетворяет цепочке
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
Рекуррентное систематическое помехозащитное преобразование кодов
23
E = fH = ( y + ξ) H = (aG + ξ) H = aGH + ξH GH=0 = ξH равенств. Это соотношение показыва-
ет, что в ВМО (6) процесса декодирования можно положить uд (q) = ξ (q) так, что оно с уче-
том (5) принимает вид
xд (q + 1) = Aд xд (q) + Bдξ(q), xд (0) =0.
(11)
Выражение (11) используем при формировании синдромов ошибок, которые образуют
строки проверочной матрицы H в силу соотношения Hn+1−i = Ei , где Ei — синдром ошибки
в i -м разряде принятого из КС искаженного ПЗК, Hn+1−i — (n +1− i) -я строка матрицы H .
Тогда в соответствии с (6) и при условии ξ(q) : 000…001 входная последовательность uд (q)
будет иметь вид uд (q) = ⎣⎡ uд ( 0) = 0, uд ( 1) = 0,…, uд ( n − 2) = 0, uд (n −1) = 1,uд (n) = 0…⎦⎤ . В течение первых ( n −1) тактов ЛДДС устройство деления модулярных многочленов
ДКУ будет находиться в нулевом состоянии. При приеме элемента uд (q) q=n−1= 1 ЛДДС
УДММ КУ в соответствии с (6) перейдет в состояние
xд (q + 1) q+1=n
=
( )Aд xд
q
xд
(
q
)
=0
q=0,n−1
+ Bд uд (q) uд (q)
q=n−1= 1
= Bд .
Данное соотношение в транспонированном виде {xд (n) = }Βд T определяет код
K
⎨⎪⎧rest ⎩⎪
ξ(x) g ( x)
ξ( x)=1
=
rest
g
1
(x)
=1⎬⎪⎫ ⎪⎭
остатка от деления, вводимого из КС в ДКУ кода ошибки с ММ ξ( x) = 1, задающей синдром
E ошибки в младшем разряде и задаваемой последней (п-й) строкой Hn проверочной мат-
рицы H так, что выполняется цепочка равенств
( )Ei = xдT i=1
n
uд (n−1)=1
= BдT
uд (q)=0;q=0,n−2
= Hn+1−i = Hn .
i=1
■
Соотношение (10) совместно с описанием функционирования рекуррентного ДКУ по-
зволяет сконструировать его векторно-матричное описание в форме ЛДДС вида (6).
Алгоритм 2 (А2) формирования матриц {Aд , Bд } = Ψ ( g ( x), H)
ЛДДС рекуррентного помехозащитного декодирования 1. Выполнить пп. 1—4 алгоритма А1 синтеза рекуррентного КУ.
2. Сконструировать передаточную матрицу-столбец Φд (d ) = arg{xд (d ) = Φд (d )uд (d )}
( )УДММ ДКУ на образующий ММ
g( x)
в форме
Φд ( d ) =
g
1
(d
)
col
Φ j ( d ); j = 1,m
, где пе-
( )редаточные функции Φ j ( d ); j = 1,m подлежат вычислению.
3. В качестве матрицы Aд состояния векторно-матричного описания УДММ ДКУ (6)
принять матрицу Aк , удовлетворяющую условиям п. 9 алгоритма А1 так, что становится справедливым матричное соотношение Aд = Aк = A .
4. Сформировать матрицу Bд входа ВМО (6) УДММ ДКУ с помощью соотношения (10).
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
24 А. В. Ушаков, Е. С. Яицкая
5. Структурно, реализовав ВМО (6) УДММ ДКУ с матрицами ( Aд ,Bд ) , сформирован-
ными в п. 3, 4, графически, с помощью правила Мейсона, или аналитически, с помощью со-
( )отношения Φд (d ) = d −1I + Aд −1 Bд , сформировать передаточную матрицу-столбец
( ) ( )Φд ( d ) = g−1 ( d ) col Φ j ( d ); j = 1, m , с последующим вычислением col Φ j ( d ); j = 1, m =
( )= g ( d ) d −1I + Aд −1 Bд .
6. На конкретном примере проверить правильность функционирования устройства ре-
куррентного декодирования (6) со сформированной парой матриц ( Aд ,Bд ) .
■
Пример. На основе использования алгоритмов синтеза рекуррентных кодирующих и декодирующих устройств осуществлено их проектирование по следующим исходным дан-
ным. Пусть массив сообщений W характеризуется мощностью [W ] = Vи = 120 и кратностью
исправляемой ошибки s = 2. Схемы кодирующего и декодирующего устройств приведены на рис. 2 и 3 соответственно.
xк8(q+1) xк7(q+1) xк6(q+1) xк5(q+1)
xк4(q+1) xк3(q+1) xк2(q+1)
xк1(q+1)
dd d
d
dd
d
d
xк8(q) xк7(q) из
ИДИ uк(q)
xк6(q)
xк5(q)
xк4(q)
xк3(q)
xк2(q)
xк1(q)
УК КЗ
К2 в КС 1
К1
Рис. 2
из КС
xд8(q+1) d
ид(q)= f(q)
xд7(q+1) xд6(q+1) dd
xд5(q+1) d
xд8(q) xд7(q) xд6(q)
xд4(q+1) xд3(q+1) dd
xд2(q+1) d
xд1(q+1) d
xд5(q)
xд4(q) xд3(q)
xд2(q)
xд1(q)
xдT(q)|q=n=E Рис. 3
Заключение. Поставленная задача решена. Показано, что представление процессов преобразования кодов в задаче помехозащитного кодирования и декодирования средствами линейных двоичных динамических систем на основе связи матриц входа с образующей и проверочной матрицами имеет элегантную алгоритмическую поддержку.
СПИСОК ЛИТЕРАТУРЫ
1. Гилл А. Линейные последовательностные машины. М.: Наука, 1974. 2. Фараджев Р. Г. Линейные последовательностные машины. М.: Сов. радио, 1975.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
Рекуррентное систематическое помехозащитное преобразование кодов
25
3. Кирюшин А. А., Рассветалова Л. А., Ушаков А. В. Модальное управление в задаче синтеза двоичных динамических систем в логике линейных триггеров // Автоматика и телемеханика. 1993. № 7.
4. Рассветалова Л. А., Ушаков А. В. Двоичное динамическое наблюдение в задаче помехоустойчивого кодирования // Автоматика и телемеханика. 1993. № 6.
5. Ушаков А. В. Синтез циклических кодирующих и декодирующих устройств в логике произвольных триггеров // Автоматика и телемеханика. 1997. № 11.
6. Заде Л., Дезоер Ч. Теория линейных систем. М.: Наука, 1970.
7. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976.
8. Тутевивич В. Н. Телемеханика. М.: Высш. школа, 1985.
9. Мельников А. А., Ушаков А. В. Двоичные динамические системы дискретной автоматики. СПб: СПбГУ ИТМО, 2005.
10. Rosenthal J. Some interesting problems in systems theory which are of fundamental importance in coding theory // Proc. 36th Conf. Decision Control. San Diego, CA, 1997. Vol. 5. P. 4574—4579.
Анатолий Владимирович Ушаков Елена Сергеевна Яицкая
Сведения об авторах — д-р техн. наук, профессор; Санкт-Петербургский государственный
университет информационных технологий, механики и оптики, кафедра систем управления и информатики; E-mail: ushakov-AVG@yandex.ru — аспирант; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра систем управления и информатики; E-mail: yaitskayaes@mail.ru
Рекомендована кафедрой систем управления и информатики
Поступила в редакцию 27.09.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
УДК [517.938 + 519.713/718]: 621.398
А. В. УШАКОВ, Е. С. ЯИЦКАЯ
РЕКУРРЕНТНОЕ СИСТЕМАТИЧЕСКОЕ ПОМЕХОЗАЩИТНОЕ ПРЕОБРАЗОВАНИЕ КОДОВ: ВОЗМОЖНОСТИ АППАРАТА ЛИНЕЙНЫХ ДВОИЧНЫХ ДИНАМИЧЕСКИХ СИСТЕМ
Рассматривается проблема формирования матричных компонентов векторноматричного описания двоичных динамических систем помехозащитного преобразования кодов. Показано, что базис представления матричных компонентов зависит от проверочной и образующей матриц помехозащищенного кода, а также от его образующего модулярного многочлена. Ключевые слова: двоичная динамическая система, систематический помехозащищенный код, проверочная и образующая матрицы, образующий модулярный многочлен, помехозащитное преобразование кодов.
В работах [1, 2], посвященных преобразованию кодов (ПК), представленных в виде кодовых последовательностей, получен конструктивный инструментарий модельного представления процедур ПК в виде линейных последовательностных машин (ЛПМ). Так как термин ЛПМ выпадает из общей теории систем, то со временем он был заменен понятием „линейная двоичная динамическая система “ (ЛДДС). Таким образом, ЛДДС, использующая в основном векторно-матричные модельные представления (ВММП) аппарата пространства состояний (АПС), со временем стала инструментом ПК, в том числе и помехозащитного преобразования систематических кодов в задачах кодирования и декодирования [3—5]. Из теории АПС [6] известно, что одной из проблем формирования векторно-матричного модельного представления динамических процессов над бесконечными и конечными полями является поиск базиса представления, в котором матричные компоненты ВММП обладают желаемыми исследователю свойствами. Причем возможность выбора базиса представления при построении ВММП процессов общего вида практически не ограничена. К сожалению, этого нельзя сказать о ВММП ЛДДС, использованных в задачах помехозащитного преобразования кодов.
Известно [7, 8], что систематическое помехозащитное преобразование кодов (ППК) в задачах кодирования и декодирования может быть осуществлено несколькими способами, основанными на различном описании процесса ППК. Тем не менее эти способы имеют единое
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
18 А. В. Ушаков, Е. С. Яицкая
функциональное представление, структурная реализация которого приведена на рис. 1, здесь КУ — помехозащитное кодирующее устройство, формирующее на своем выходе помехозащищенный код (ПЗК); КС — канал связи, выполняющий функцию среды искажения в задаче ППК; ДКУ — помехозащитное декодирующее устройство, формирующее на своем выходе синдром ошибки (факта или места искажения); ФСК — формирователь сигнала коррекции;
⊕ — сумматор по модулю два; a (∗) — помехонезащищенный информационный код
(ПНЗИК); y (∗) — помехозащищенный код передачи; ξ(∗) — код помехи, воздействующей
на код y (∗) при его передаче по КС; f (∗) — искаженный в КС ПЗК; E (∗) — код синдрома
ошибки (факта или места искажения); η(∗) — код коррекции; y (∗) — откорректированный
принятый из КС код, удовлетворяющий условию
y (∗) = {arg min y (∗) − y (∗) } . η(∗)
G
ξ(*) H
УКК H+
a(*) КУ y(*)
f(*)
ДКУ E(*)
η(*) ФСК
y(*)
КС
Рис. 1
Символ „ ∗ “ опускается, если все коды, использованные в процедуре помехозащитного преобразования, рассматриваются как векторы-строки, преобразование которых осуществляется в соответствии с векторно-матричными соотношениями:
y = aG, f = y + ξ, E = fH, η = EH+ , y = f + η .
(1)
Операцию сложения следует понимать как процедуру суммирования по модулю два; a : dim a = k; y : dim y = n; f : dim f = n; ξ :dim ξ = n; E :dim E = m = n − k; η :dim η = n;
y :dim y = n; G — образующая (k × n) -матрица ПЗК; H — проверочная (n × m) -матрица
ПЗК, которая удовлетворяет условию {G,H} = arg{GH = 0} .
Если коды, используемые в процедуре помехозащитного преобразования кодов, рас-
сматриваются как модулярные многочлены (ММ) над полем Галуа GF( p) p = 2 , то символ
„ ∗ “ принимает значение переменной x . При этом преобразование кодов-ММ осуществляется в соответствии с модулярными полиномиальными соотношениями:
y(
x)
=
a(
x)
xm
+
r
(
x)
:rest
y g
(x) (x)
=
0,
r
(
x)
=
rest
a
(x) xm g ( x)
⎫ ,⎪ ⎪
f (x) = y(x) + ξ(x),
E
(x)
=
rest
f g
(x) (x)
=
rest
ξ(x) g ( x)
,
⎪⎪ ⎬ ⎪ ⎪ ⎪
η(x) = ξ(x), y(x) = f (x) + η(x),
⎭⎪
(2)
в которых a ( x) : deg a ( x) = k −1; y ( x) : deg y ( x) = n −1; f ( x) : deg f ( x) = n −1; ξ( x) :deg ξ( x) = n −1; E ( x) : deg E ( x) = m −1; η( x) :deg η( x) = n −1; y ( x) :deg y ( x) = n −1;
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
Рекуррентное систематическое помехозащитное преобразование кодов
19
g ( x) — образующий модулярный многочлен ПЗК, представляющий собой неприводимый
многочлен степени m , имеющий не менее dmin = 2s +1 ненулевых элементов. Символ „ ∗ “ принимает смысл дискретного времени q , выраженного в числе тактов
длительности ∆t , при этом все коды, используемые в процедуре помехозащитного преобразования, рассматриваются как кодовые последовательности, преобразование которых осуществляется рекуррентным образом в соответствии с векторно-матричными соотношениями, параметризованными дискретным временем q :
xк ( q + 1) = Aк xк (q) + Bк uк (q); y (q) = Nuк (q),
(3)
xк (q +1) = Axк (q); y (q) = Cк xк (q),
(4)
f (q) = y(q)+ ξ(q),
(5)
xд (q + 1) = Aд xд (q) + Bдuд (q) ,
(6)
в которых uк (q) = a (q) — входная двоичная последовательность, представляющая собой
вводимый в КУ ПНЗИК; xк — вектор состояния КУ, размерности dim xк = m ; y (q) — фор-
мируемая ПЗК-последовательность; Aк — (m × m) -матрица состояния КУ; Bк — (m ×1) -
матрица входа КУ;
Cк
=
⎣⎡1
O1×( n−1)
⎤ ⎦
— матрица выхода КУ;
N = [1]
— матрица вход—выход
КУ; A — нильпотентная матрица с индексом ν = m ; uд (q) = f (q) — входная двоичная последовательность, представляющая собой принятый из канала связи искаженный системати-
ческий ПЗК; xд — вектор состояния ДКУ размерности dim xд = m ; Aд — (m × m) -матрица
состояния ДКУ; Bд — (m ×1) -матрица входа ДКУ.
Постановка задачи. Ставится задача синтеза ЛДДС помехозащитного преобразования
кодов с матрицами Aк , Bк , Aд , Bд , A, Cк , N как функциями образующего модулярного
многочлена ПЗК g ( x) , его проверочной H и образующей G матриц:
{Aк , Bк , Aд , Bд , A,Cк , N} = Ψ ( g ( x), H,G ) .
Приведенные выше методы помехозащитного преобразования кодов характеризуются различным уровнем связи их аналитического описания с возможной аппаратной реализацией. Действительно, первый метод, представленный системой выражений (1), использующий векторно-матричное описание ППК, не параметризованное временем, приводит к системе скалярных аналитических выражений (САВ), которые позволяют строить устройства помехозащитного кодирования и декодирования [8].
Второй метод, представленный системой выражений (2), приводит к двум видам аппаратной реализации ППК: схемотехнической и программной, описываемой рекуррентными процедурами параметризованной дискретным временем q , задаваемыми соотношениями
(3)—(6). Схемотехническая реализация ППК имеет две версии: первая строится по схеме
„ g ( x) → (G, H ) → САВ “; вторая — по схеме „ g ( x) → УДММ :Φ (d ) = g−1 (d ) → СР Φ (d ) “,
УДММ — устройство деления ММ, СР Φ (d ) — структурная реализация передаточной функ-
ции Φ(d ) .
Для формирования программной реализации устройств ППК в форме (3)—(6) сформулируем необходимые определение и утверждение.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
20 А. В. Ушаков, Е. С. Яицкая
Определение 1. Помехозащищенный (n, k ) -код, множество кодовых комбинаций кото-
рого yi мощностью [ yi ] = 2k , описываемых модулярными многочленами yi ( x) , обладаю-
щими рекуррентным свойством
rest
yi ( x) g ( x)
=
0
,
(7)
называется циклическим помехозащищенным кодом.
□
Утверждение 1. Код, множество кодовых комбинаций которого формируется в соот-
ветствии с первым соотношением системы (2), обладает рекуррентным свойством (7), т.е. яв-
ляется циклическим ПЗК.
□
Д о к а з а т е л ь с т в о утверждения сводится к доказательству наличия у кода с ММ (2)
рекуррентного свойства (7). Для этой цели полиномиальный компонент a ( x) xm представим
в форме a ( x) xm = Q ( x) g ( x) + r ( x) . Если полученное выражение подставить в первое соот-
ношение системы (2) и осуществить приведение по модулю два, то получим
y ( x) = {Q ( x) g ( x) + r ( x) + r ( x)}mod 2 = Q ( x) g ( x) .
(8)
Нетрудно видеть, что представление (8) определяет наличие у y ( x) рекуррентного
свойства (7).
■
По существу, первое выражение представления (2) ММ y ( x) циклического ПЗК содер-
жит алгоритм его формирования в среде рекуррентного кодирующего устройства. При этом КУ функционирует посредством коммутации структуры. Это вызвано тем, что при формиро-
вании (n, k ) -кода в течение первых k тактов k-разрядная информационная часть в виде кодо-
вой последовательности одновременно подается в КС и на вход УДММ для вычисления остатка в форме
xT
(Q)
=
K
⎨⎪⎧rest ⎪⎩
⎛ ⎝⎜⎜
a(x) xm g ( x)
⎠⎟⎞⎟⎭⎪⎪⎬⎫
.
По принятии информационной части из источника дискретной информации (ИДИ) вход
КС переключается с выхода ИДИ на выход УДММ, в котором сформировался остаток. Все
обратные связи в УДММ в этот момент разрываются, процесс деления останавливается, а
УДММ без связей становится т-разрядным регистром сдвига. Все перечисленные коммута-
ции цепей и связей осуществляются специально вводимым в состав КУ устройством комму-
тации (УК). Таким образом, помехозащитное КУ представляет собой объединение УДММ и
УК, функционирующее в два этапа. На первом оно описывается ЛДДС вида (3), а на вто-
ром — вида (4).
Третье выражение представления (2) ММ E ( x) синдрома ошибки по существу описы-
вает алгоритм функционирования рекуррентного декодирующего устройства, который предназначен для проверки сохранности рекуррентного свойства (7) применительно к принятому
из КС искаженному коду с ММ f ( x) = y ( x) + ξ ( x) путем деления этого многочлена на обра-
зующий g ( x) . Если E ( x) = 0 , то принимается решение, что f ( x) = y ( x) . Если E ( x) ≠ 0 , то
синдром используется как адрес искажений кода. Помехозащитное ДКУ есть функциональное объединение УДММ и устройства съема синдрома, отражающее состояние УДММ в момент q = n так, что код
K {E ( x)} = xдT (q) q=n .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
Рекуррентное систематическое помехозащитное преобразование кодов
21
Таким образом, УДММ в фазе вычисления остатка описывается ЛДДС вида (6). Утверждение 2. Матрица Bк ЛДДС УДММ кодирующего устройства (3) с точностью
до операции транспонирования совпадает с последней (k-й) строкой Gk матрицы G , входя-
щей в состав образующей матрицы G = ⎣⎡I(k×k) G⎦⎤ так, что выполняется соотношение
{ }BTк = Gk = K g ( x) + xm ,
(9)
где K{ ( •) } — код ММ ( •) .
□
Д о к а з а т е л ь с т в о . Рассмотрим процесс кодирования для случая помехонезащищенного кода a , имеющего единицу только в младшем разряде, а в остальных — нули
{ММ : a ( x) = 1} . Это значит, что входная последовательность uк (q) с учетом передачи кодов
и ММ старшим разрядом вперед будет иметь вид
uк (q) = ⎣⎡ uк ( 0) = 0, uк ( 1) = 0,…, uк ( k − 2) = 0, uк (k −1) = 1,uк (k ) = 0…⎦⎤ .
В течение первых (k −1) тактов ЛДДС УДММ кодирующее устройство будет находить-
ся в нулевом состоянии. При приеме элемента uк (q) q=k−1= 1 ЛДДС устройство деления мо-
дулярного многочлена КУ в силу (3) перейдет в состояние
( ) ( ) ( )xк q + 1 q+1=k = Aк xк q xк(q) q=0,k−1 = 0 + Bк uк q uк (q) q=k−1 = 1 = Bк .
Данное соотношение в транспонированном виде {xк (k ) = Βк }T определяет код
⎧ K ⎨⎪rest
⎩⎪
a(x) xm g ( x)
a( x)=1
=
rest
xm
g ( x)
=g(
x) +
⎫
x
m
⎪ ⎬
⎪⎭
остатка от деления, выводимый из КУ и задаваемый последней k-й строкой Gk матрицы G
кодов остатков так, что выполняется цепочка равенств
{ }xкT (k ) = BTк = Gk = K g ( x) + xm .
■
Соотношение (9) совместно с представлением функционирования рекуррентного КУ позволяет сконструировать его векторно-матричное описание в форме ЛДДС вида (3)—(4).
Алгоритм 1 (А1) формирования матриц {Aк , Bк , A,Cк , N } = Ψ ( g ( x),G )
ЛДДС рекуррентного помехозащитного кодирования
1. По заданному информационному массиву W мощности [W ] = Vи определить размер-
ность k помехонезащищенного информационного кода в силу соотношения
{ }k = min arg 2k ≥ Vи = [W ] .
2. По заданным категории системы, характеризующейся величиной Pдоп — допустимой
вероятностью приема ложной команды, и параметру модели двоичного канала связи в форме
p — вероятностью искажения разряда (бита) кода, заданному выражением p = max{ p01, p10} ,
определить кратность исправляемой ошибки s
∑ ∑s
=
min
arg
⎧⎪ ⎨
Nc
=
2m
−1≥
Nош
=
s
Cni &
n
Cni pi
(1 −
p )n−i
≤
Pдоп
⎫⎪ ⎬
,
⎪⎩ i=1 i=s+1 ⎭⎪
где Nc — число синдромов, Nош — число исправляемых ошибок.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
22 А. В. Ушаков, Е. С. Яицкая
3. В зависимости от величины s-кратности исправляемой ошибки — выбрать из таблиц неприводимых многочленов или сформировать с помощью БЧХ-технологии [9] реализацию
образующего ММ g ( x) степени m и сформировать (n, k ) -формат помехозащищенного ко-
да, где n удовлетворяет условию n = k + m .
4. Вычислить D -образ ММ g ( x) в форме
( ) ( )g ( d ) = D{ g ( x)} = g
x−1
, где g
x −1 =d
x−1
= x−mg ( x) .
5. Сконструировать передаточную функцию Фк (d ) УДММ КУ на образующий ММ
g ( x)
в
форме
Фк
(d)
=
1 g (d )
.
6. Пользуясь правилом Мейсона не касающихся контуров, построить две предваритель-
ные структурные реализации передаточной функции Фк (d ) на элементах памяти (ЭП) с пе-
редаточной функцией ΦЭП ( d ) = d в двух канонических базисах.
7. Произвести разметку входов и выходов ЭП каждой структурной реализации перемен-
ными xкi ( q + 1) на входе и xкi (q) на выходе, присвоив выходу самого правого ЭП перемен-
ную xк1 (q) , а его входу — xк1 ( q + 1) , и сформировать векторно-матричное описание (ВМО)
автономной версии УДММ xк ( q + 1) = Aк xк (q) , „списав“ реализации матриц Aк с отмечен-
ных структурных реализаций Фк (d ) .
8. Сформировать матрицу входа Bк УДММ КУ (3) в форме (9). 9. Структурно с использованием правила Мейсона или аналитически определить пере-
даточные функции УДММ КУ (3) для двух базисных реализаций матрицы Aк состояния
( )УДММ для процесса кодирования как Фк (d ) = Cк d −1I + Aк −1 Bк .
10. Выбрать для дальнейшего использования структурную реализацию передаточной
функции УДММ КУ, отмеченная версия которой характеризуется матрицей Aк ее состояния,
( )удовлетворяющей
условию
Aк
=
arg
⎧ ⎩⎨
g−1 (d )
=
Cк
d −1I + Aк
−1 Bк ⎭⎫⎬.
11. Сформировать матрицу A УДММ КУ, переведенного в режим регистра сдвига, по
отмеченной версии, выбранной в п. 10 структурной реализации Φ (d ) с разорванными обрат-
ными связями. 12. Дополнить УДММ УК устройством коммутации структуры УДММ и точки подклю-
чения входа канала связи с выхода ИДИ на выход устройства деления модулярных многочленов.
13. На конкретном примере проверить правильность функционирования устройства рекуррентного кодирования, задаваемого парой ВМО (3) и (4) со сформированными матрицами
(Aк , Bк , N) и (A,Cк ) .
■
Утверждение 3. Матрица Bд входа декодирующего рекуррентного устройства (6) удовлетворяет соотношению
( )Bд =
Hn
T
.
(10)
Д о к а з а т е л ь с т в о этого утверждения использует тот факт, что синдром E , вычисляемый в соответствии с соотношением E = fH , удовлетворяет цепочке
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
Рекуррентное систематическое помехозащитное преобразование кодов
23
E = fH = ( y + ξ) H = (aG + ξ) H = aGH + ξH GH=0 = ξH равенств. Это соотношение показыва-
ет, что в ВМО (6) процесса декодирования можно положить uд (q) = ξ (q) так, что оно с уче-
том (5) принимает вид
xд (q + 1) = Aд xд (q) + Bдξ(q), xд (0) =0.
(11)
Выражение (11) используем при формировании синдромов ошибок, которые образуют
строки проверочной матрицы H в силу соотношения Hn+1−i = Ei , где Ei — синдром ошибки
в i -м разряде принятого из КС искаженного ПЗК, Hn+1−i — (n +1− i) -я строка матрицы H .
Тогда в соответствии с (6) и при условии ξ(q) : 000…001 входная последовательность uд (q)
будет иметь вид uд (q) = ⎣⎡ uд ( 0) = 0, uд ( 1) = 0,…, uд ( n − 2) = 0, uд (n −1) = 1,uд (n) = 0…⎦⎤ . В течение первых ( n −1) тактов ЛДДС устройство деления модулярных многочленов
ДКУ будет находиться в нулевом состоянии. При приеме элемента uд (q) q=n−1= 1 ЛДДС
УДММ КУ в соответствии с (6) перейдет в состояние
xд (q + 1) q+1=n
=
( )Aд xд
q
xд
(
q
)
=0
q=0,n−1
+ Bд uд (q) uд (q)
q=n−1= 1
= Bд .
Данное соотношение в транспонированном виде {xд (n) = }Βд T определяет код
K
⎨⎪⎧rest ⎩⎪
ξ(x) g ( x)
ξ( x)=1
=
rest
g
1
(x)
=1⎬⎪⎫ ⎪⎭
остатка от деления, вводимого из КС в ДКУ кода ошибки с ММ ξ( x) = 1, задающей синдром
E ошибки в младшем разряде и задаваемой последней (п-й) строкой Hn проверочной мат-
рицы H так, что выполняется цепочка равенств
( )Ei = xдT i=1
n
uд (n−1)=1
= BдT
uд (q)=0;q=0,n−2
= Hn+1−i = Hn .
i=1
■
Соотношение (10) совместно с описанием функционирования рекуррентного ДКУ по-
зволяет сконструировать его векторно-матричное описание в форме ЛДДС вида (6).
Алгоритм 2 (А2) формирования матриц {Aд , Bд } = Ψ ( g ( x), H)
ЛДДС рекуррентного помехозащитного декодирования 1. Выполнить пп. 1—4 алгоритма А1 синтеза рекуррентного КУ.
2. Сконструировать передаточную матрицу-столбец Φд (d ) = arg{xд (d ) = Φд (d )uд (d )}
( )УДММ ДКУ на образующий ММ
g( x)
в форме
Φд ( d ) =
g
1
(d
)
col
Φ j ( d ); j = 1,m
, где пе-
( )редаточные функции Φ j ( d ); j = 1,m подлежат вычислению.
3. В качестве матрицы Aд состояния векторно-матричного описания УДММ ДКУ (6)
принять матрицу Aк , удовлетворяющую условиям п. 9 алгоритма А1 так, что становится справедливым матричное соотношение Aд = Aк = A .
4. Сформировать матрицу Bд входа ВМО (6) УДММ ДКУ с помощью соотношения (10).
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
24 А. В. Ушаков, Е. С. Яицкая
5. Структурно, реализовав ВМО (6) УДММ ДКУ с матрицами ( Aд ,Bд ) , сформирован-
ными в п. 3, 4, графически, с помощью правила Мейсона, или аналитически, с помощью со-
( )отношения Φд (d ) = d −1I + Aд −1 Bд , сформировать передаточную матрицу-столбец
( ) ( )Φд ( d ) = g−1 ( d ) col Φ j ( d ); j = 1, m , с последующим вычислением col Φ j ( d ); j = 1, m =
( )= g ( d ) d −1I + Aд −1 Bд .
6. На конкретном примере проверить правильность функционирования устройства ре-
куррентного декодирования (6) со сформированной парой матриц ( Aд ,Bд ) .
■
Пример. На основе использования алгоритмов синтеза рекуррентных кодирующих и декодирующих устройств осуществлено их проектирование по следующим исходным дан-
ным. Пусть массив сообщений W характеризуется мощностью [W ] = Vи = 120 и кратностью
исправляемой ошибки s = 2. Схемы кодирующего и декодирующего устройств приведены на рис. 2 и 3 соответственно.
xк8(q+1) xк7(q+1) xк6(q+1) xк5(q+1)
xк4(q+1) xк3(q+1) xк2(q+1)
xк1(q+1)
dd d
d
dd
d
d
xк8(q) xк7(q) из
ИДИ uк(q)
xк6(q)
xк5(q)
xк4(q)
xк3(q)
xк2(q)
xк1(q)
УК КЗ
К2 в КС 1
К1
Рис. 2
из КС
xд8(q+1) d
ид(q)= f(q)
xд7(q+1) xд6(q+1) dd
xд5(q+1) d
xд8(q) xд7(q) xд6(q)
xд4(q+1) xд3(q+1) dd
xд2(q+1) d
xд1(q+1) d
xд5(q)
xд4(q) xд3(q)
xд2(q)
xд1(q)
xдT(q)|q=n=E Рис. 3
Заключение. Поставленная задача решена. Показано, что представление процессов преобразования кодов в задаче помехозащитного кодирования и декодирования средствами линейных двоичных динамических систем на основе связи матриц входа с образующей и проверочной матрицами имеет элегантную алгоритмическую поддержку.
СПИСОК ЛИТЕРАТУРЫ
1. Гилл А. Линейные последовательностные машины. М.: Наука, 1974. 2. Фараджев Р. Г. Линейные последовательностные машины. М.: Сов. радио, 1975.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3
Рекуррентное систематическое помехозащитное преобразование кодов
25
3. Кирюшин А. А., Рассветалова Л. А., Ушаков А. В. Модальное управление в задаче синтеза двоичных динамических систем в логике линейных триггеров // Автоматика и телемеханика. 1993. № 7.
4. Рассветалова Л. А., Ушаков А. В. Двоичное динамическое наблюдение в задаче помехоустойчивого кодирования // Автоматика и телемеханика. 1993. № 6.
5. Ушаков А. В. Синтез циклических кодирующих и декодирующих устройств в логике произвольных триггеров // Автоматика и телемеханика. 1997. № 11.
6. Заде Л., Дезоер Ч. Теория линейных систем. М.: Наука, 1970.
7. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976.
8. Тутевивич В. Н. Телемеханика. М.: Высш. школа, 1985.
9. Мельников А. А., Ушаков А. В. Двоичные динамические системы дискретной автоматики. СПб: СПбГУ ИТМО, 2005.
10. Rosenthal J. Some interesting problems in systems theory which are of fundamental importance in coding theory // Proc. 36th Conf. Decision Control. San Diego, CA, 1997. Vol. 5. P. 4574—4579.
Анатолий Владимирович Ушаков Елена Сергеевна Яицкая
Сведения об авторах — д-р техн. наук, профессор; Санкт-Петербургский государственный
университет информационных технологий, механики и оптики, кафедра систем управления и информатики; E-mail: ushakov-AVG@yandex.ru — аспирант; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра систем управления и информатики; E-mail: yaitskayaes@mail.ru
Рекомендована кафедрой систем управления и информатики
Поступила в редакцию 27.09.10 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 3