авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 | 4 |   ...   | 5 |

«А.А. Мельников, А.В. Ушаков ДВОИЧНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ ДИСКРЕТНОЙ АВТОМАТИКИ x( k + 1) = [ x( k ), u ( k ) ], ...»

-- [ Страница 2 ] --

0 0 Решим поставленную задачу в форме z ( k ) = ( k ), k, для чего в силу (1.104) выберем матрицу T в форме T = I. Решение уравнения Сильвестра (1.98) относительно матрицы L и вычисление матрицы G дает L = [ 0 0 1], G = [ 0 0 1].

T T В силу (1.104) и того, что матрица имеет индекс нильпотентно сти, равный трем, то, очевидно, что начиная с момента k 3 вектор со стояния z ДНУ должен будет совпасть с вектором состояния исход ной ДДС. Покажем это, полагая, что входная последовательность u ( k ) ДДС на первых семи тактах имеет вид u ( k ): 1001010, а начальное со стояние ( 0 ) ДДС определяется вектором ( 0 ) = [0 1 1].

T Таблица 1. 0 1 2 3 4 5 6 k u(k) 0 1 0 0 1 0 1 T ( k) 011 110 100 001 011 111 111 zT ( k ) 000 000 000 001 011 111 111 ( k) 3 (k ) 2 (k ) 1 (k ) u ( k) 3 (k + 1) 2 (k + 1) 1 (k + 1) z1 (k ) z3 (k ) z 2 (k ) Рисунок 1.18. Структурное представление процесса двоичного динамического наблюдения Из таблицы 1.1 видно, что начиная с третьего такта, то есть с вы полнением условия k = 3, вектор состояния z синтезированного ДНУ повторяет в форме z ( k ) = ( k ) состояние ( 0 ) наблюдаемой ДДС.С использованием полученных результатов структурно-функциональная схема процесса двоичного динамического наблюдения вектора состоя ния заданной ДДС примет вид, как показано на рисунке 1.18.

Из таблицы 1.1 видно, что начиная с третьего такта, то есть с вы полнением условия k = 3, вектор состояния z синтезированного ДНУ повторяет в форме z ( k ) = ( k ) состояние ( 0 ) наблюдаемой ДДС.С использованием полученных результатов структурно-функциональная схема процесса двоичного динамического наблюдения вектора состоя ния заданной ДДС примет вид, как показано на рисунке 1.18.

1.5.2 Концепция подобия в задаче декодирования систематических помехозащищенных кодов Задачу декодирования систематических помехозащищенных кодов, подвергшихся воздействию на функциональном и модельном уровнях, зададим следующим образом. Кодирующее устройство (КУ) на выходе которого формируется ( n, k ) -помехозащищенный код y, выводимый в канал связи в виде двоичной кодовой последовательности y ( k ), стар шим разрядом вперед, представляется n -разрядным регистром сдвига, начальное состояние которого ( 0 ) представляет собой передаваемую помехозащищенную кодовую посылку. Векторно-матричное модель ное представление КУ имеет вид x ( k + 1) = F x ( k );

x ( 0 );

y ( k ) = P x ( k ), (1.116) где F – матрица размерности ( n n ) является нильпотентной с индек сом нильпотентности равным n так, что = n. Формирователь им пульсной помехи, которая в канале связи (КС) искажает передавае мую кодовую посылку y, также представим n -разрядным регистром сдвига, который будем именовать регистром канала связи (РКС). РКС характеризуется нулевой входной последовательностью и вектором начального состояния ( 0 ), который представляет собой n -разрядный вектор помехи, выводимый в КС в виде последовательности ( k ) старшим разрядом вперед. Векторно-матричное описание РКС имеет вид ( k + 1) = A ( k );

( 0 );

( k ) = C ( k ). (1.117) Матрица A совпадает с матрицей F и так же является нильпотентной с индексом нильпотентности = n.

Процесс искажения кодовой последовательности y ( k ), при переда че по КС представим суммированием в простом двоичном поле GF ( 2 ), в результате чего формируется искаженная кодовая комбинация f = y +, в виде кодовой последовательности f ( k ) = y( k ) + ( k ). (1.118) Процесс декодирования реализуем в форме построения ДНУ, фор мирующего к моменту k = n состояние z ( n ), которое с точностью до матрицы преобразования подобия представляло бы собой вектор ( 0 ) начального состояния РКС. Векторно-матричное описание ДНУ – де кодирующего устройства (ДКУ) принимает вид z ( k + 1) = z ( k ) + L f ( k );

z ( 0 ), (1.119) а структурное представление процесса декодирования – так, как пока зано на рисунке 1.19.

Рисунок 1.19. Структурное представление двоичного динамического наблюдения начального состояния регистра канала связи Поставленная задача опирается на следующее утверждение.

Утверждение 1.24 (У1.24). Вектор z ( k ) состояния ДКУ, постро енного по структуре двоичного наблюдающего устройства для наблю дения векторов x( 0 ) и ( 0 ), задается соотношением ( ) ( ) z ( k ) = k z ( 0 ) + T A k + k T ( 0 ) + Tx F k + k Tx x ( 0 ), (1.120) где матричные компоненты T и Tx вычисляются как решение мат ричных уравнений Сильвестра T A + T = L C, Tx F + Tx = L P. (1.121) Доказательство утверждения ведется по той же схеме, что и дока зательство У1.23. В рассмотрение вводится агрегированный вектор [ ] T z = z T, T, xT. (1.122) Вектор (1.122) подчиняется рекуррентному векторно-матричному уравнению [ ] z ( k + 1) = z ( k );

z ( 0 ) = z T ( 0 ), T ( 0 ), x T ( 0 ), T (1.123) явное решение которого в показательной форме имеет вид z ( k ) = k z ( 0). (1.124) В (1.123) и (1.124) матрицы и k имеют вид k T A k + k T Tx F k + k Tx LC L P = 0 A 0 ;

k = 0 Ak 0 (1.125) 0 0 F k 0 0 F Подстановка из (1.125) в (1.124) и выделение из z ( k ) компо k нента z ( k ) приводит к (1.120).

В стандартной постановке задачи декодирования [51] сформиро ванный ДКУ синдром ошибки представляет собой образ вектора на чального состояния ( 0 ) РКС, формируемого с помощью матрицы преобразования подобия T. В этой связи выясним при каких условиях и свойствах матричных компонентов соотношения (1.120) последнее вырождается в соотношение вида (1.107), записываемое в форме () z k = T ( 0 ). (1.126) Решение поставленной задачи получим с использованием положе ний следующего утверждения.

Утверждение 1.25 (У1.25). Если ДНУ начального состояния ( 0 ) функционирует так, что всегда z ( 0 ) = 0, то есть перед запуском его состояние обнуляется, матрица принадлежит показателю µ = n, матрицы A и F обладают индексом нильпотентности = n, мат рица преобразования подобия Tx обладает свойством Tx G T = O. (1.127) где G – образующая матрица систематического кода [51], то выпол няется соотношение векторно-матричного подобия z ( n ) = T ( 0 ). (1.128) Доказательство утверждения строится на определениях свойств нильпотентности матрицы и принадлежности матрицы показателю, а так же на использовании условия z ( 0 ) = 0, что приводит (1.120) к виду z ( n ) = T ( 0 ) + Tx x ( 0 ). (1.129) Напомним, что вектор x( 0 ) формируется из информационной части xи ( 0 ) систематического помехозащищенного кода с помощью обра зующей матрицы G кода в силу соотношения x ( 0 ) = G T xи ( 0 ). (1.130) Если (1.130) подставить в (1.129) и учесть (1.127), то получим (1.128).

Следует заметить, что в силу (1.127) матрица Tx как решение мат ричного уравнения Сильвестра (1.121) является проверочной матрицей [51] систематического кода.

Пример 1.6 (Пр1.6) В качестве примера рассмотрим аналитику решения в виде (1.130) задачи конструирования декодирующего устройства в форме ДНУ циклического кода с образующим многочленом g ( x ) = x 3 + x + 1.

Сконструируем ДКУ в форме ДНУ и кодирующее устройство в ви де модельных представлений «вход-состояние-выход» с матричными компонентами I [ ] A = F = O7 66, T C = P = 1 O T O соответственно.

Решение относительно матрицы T матричного уравнения (1.97) дает 1 1 1 0 1 0 T = 0 1 1 1 0 1 0.

1 1 0 1 0 0 Следует заметить тождественность результата для вычисленной матрицы T каноническому [51] представлению проверочной матрицы ~ H циклического кода, который в рассматриваемом примере соответ ствует образующему многочлену g ( x ) = x 3 + x + 1, которая имеет вид T 1 1 1 0 1 0 [ ] ~~ T H = GT I = 0 1 1 1 0 1 0.

1 1 0 1 0 0 Заметим также, что процесс декодирования состоит в вычислении вектора ошибки (применительно к данному примеру – вектору состоя ния регистра канала связи см. рисунок 1.19) посредством умножения матрицы T T на вектор начального состояния ( 0 ) РКС. Нетрудно ви ~ деть, что в силу равенств матриц T и H T, процесс декодирования циклических кодов полностью совпадает с классическим его представ лением. Структурная схема процесса декодирования циклического ко да с образующим многочленом g ( x ) = x 3 + x + 1 представлена на ри сунке 1.20.

7 (0 ) 6 (0 ) 5 (0 ) 4 (0 ) 2 (0 ) 1 (0 ) 3 (0) РКС 7 6 5 4 3 2 ( k) d d d d d d d КУ xи (0) ~ GT x7 (0) x6 (0 ) x5 (0 ) x4 (0 ) x2 (0 ) x1 (0) x3 (0) 7 6 5 4 3 2 y ( k) d d d d d d d z3 (k ) ДНУ z 2 (k ) 3 2 f ( k) z1 (k ) d d d Рисунок 1.20. Структурное представление процесса декодирования циклического кода 1.5.3 Концепция подобия в задаче синтеза двоичных динамических систем в логике произвольных линейных триггеров Решая поставленную задачу, следует отметить, что банк линейных триггеров состоит из D- и T- триггеров при этом так, как передаточная функция элемента памяти (ЭП), выполненного в виде D- триггера, ха рактеризуется передаточной функцией D ЭП ( d ) = d, (1.131) а в виде T- триггера – характеризуется передаточной функцией d T ЭП ( d ) =, (1.132) 1+ d то векторы состояний ДДС, имеющих D- и T- триггерную реализацию, оказываются связанными отношениями подобия xT ( k ) = M x D ( k ), k. (1.133) Пусть в результате синтеза ДДС, решающей задачу преобразования входной последовательности u ( k ) в выходную y ( k ), получена D триггерная реализация системы, имеющая векторно-матричное пред ставление x D ( k + 1) = AD x D ( k ) + B D u ( k ), y D ( k ) = C D x D ( k ) + H u ( k ). (1.134) Требуется, опираясь на условие векторно-матричного подобия (1.133), построить T- триггерную реализацию системы xT ( k + 1) = AT xT ( k ) + BT u ( k ), yT ( k ) = C T xT ( k ) + H u ( k ), (1.135) решающую ту же задачу кодопреобразования. Поставленную задачу решим, опираясь на следующие утверждения.

Утверждение 1.26 (У1.26). Матричные компоненты векторно матричных представлений (1.134) и (1.135) ДДС, решающих одну и ту же задачу кодопреобразования входной последовательности u ( k ) в выходную y ( k ), связаны соотношениями AT = M AD M -1, (1.136) C T = C D M -1.

BT = M B D, (1.137) Доказательство утверждения строится на использовании (1.133), которое должно выполняться для k, а потому оказывается справед ливой запись xT ( k + 1) = M x D ( k + 1), k. (1.138) Подстановка в (1.138) соотношений (1.134) и (1.135) приводит к справедливости (1.136) и первого соотношения в (1.137). Второе соот ношение в (1.137) получается после подстановки (1.133) в выражение для выходной последовательности y ( k ) в (1.135).

Утверждение 1.27 (У1.27). Матричное условие подобия (1.136), записанное в форме M AD = AT M, (1.139) представимо в виде неоднородного матричного уравнения Сильвестра M AD + AT M = BT LD, (1.140) где dim AD = dim AT, ( AD, LD ) – полностью наблюдаемая пара матриц [4], ( AT, BT ) – полностью управляемая пара матриц, алгеб раические спектры собственных значений матриц AD и AT не пересе каются, то есть { AD } { AT } =, размерности матриц BT, LD согласованы в силу соотношения dim BT = dim LD.

Доказательство утверждения строится на представлении матрицы AT в форме AT = AT + BT N T, (1.141) где матрица N T допускает представление N T = LD M - 1. (1.142) Выражение (1.142) допускает эквивалентное представление ~ LD = N T M. (1.143) Подстановка (1.143) в (1.140) с учетом (1.141) приводит к (1.139).

Утверждение (У1.27) является основой следующего алгоритма синтеза ДДС в логике T- триггеров.

Алгоритм 1.5 (А1.5) конструирования двоичных динамических систем в логике произвольных линейных триггеров 10. Выполнить А1.2, получив представление линейной ДДС в форме (1.138).

11. Назначить произвольные матрицы AT, BT и LD, удовлетворяю щие условиям У1.30.

12. Решить матричное уравнение Сильвестра (1.140) относительно матрицы подобия M и вычислить матрицу M 1.

13. Сконструировать матричные компоненты T-триггерной реали зации линейной ДДС (1.138) с помощью соотношений (1.136) и (1.137).

Следует отметить, что так как нелинейные ДДС, именуемые ко нечными автоматами, имеют линейные аналоги, то, как представляется авторам, концепция подобия может быть распространена и на этот класс ДДС.

Пример 1.7 (Пр1.7) Построить для декодирующего устройства циклического кода с образующим многочленом g ( x ) = x 3 + x + 1 модельное представление ДДС в логике линейных T-триггеров.

1. Выполнение п.1 А1.5 формирует модельное «вход состояние-выход» представление декодирующего устройства с матричными компонентами 0 1 0 C D = [ 1 0 0 ], H = [ 1].

AD = 1 0 1, B D = 1, 1 0 0 2. Назначение произвольных матриц AT, BT и LD, удовлетво ряющих условиям У1.27, дает 1 1 0 ~ ~ LD = [1 0 0 ].

BT = 0, AT = 0 1 1, 0 0 1 3. Выполнение п.3 алгоритма, состоящее в решении матричного уравнения Сильвестра (1.138) относительно матрицы подо бия M, приводит к матрице 0 1 1 1 0 M = 0 1 0 и M -1 = 0 1 0 соответственно.

1 1 1 1 1 4. С помощью соотношений (1.136) и (1.137) конструирование матричных компонентов T-триггерной реализации ДДС, описываемой матричными компонентами, полученными в п.1 алгоритма, дает матричные компоненты искомого век торно-матричного описания 1 1 0 C T = [1 0 1].

AT = 0 1 1 ;

BT = 1 ;

1 0 0 Структурное представление векторно-матричного описания иско мой ДДС с полученными компонентами AT, BT,C T имеет вид, как по казано на рисунке 1.21.

Рисунок 1. 1.6. Векторно-матричное представление линейного помехозащитного кодопреобразования, непараметризованное дискретным временем.

Методы формирования матриц помехозащищенных кодов Процесс линейного помехозащитного кодопреобразования как в фазе кодирования, так и в фазе декодирования [15, 42, 55, 51] как част ный случай линейного кодопреобразования имеет три модельных представления, приведенных в параграфе 1.1. В данном параграфе ис пользуется векторно-матричное представление линейного помехоза щитного кодопреобразования, непараметризованное дискретным вре менем, при этом особое внимание обращается на методы формирова ния образующей и проверочной матриц помехозащищенного кода (ПЗК).

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

f = y + y a E Рисунок 1. На рисунке 1.22: КУ – кодирующее устройство;

КС – канал связи, ис кажение в котором моделируется сумматором по модулю два помехо защищенного кода и кода ошибки;

ДКУ – декодирующее устройство, формирующее синдром ошибки;

a – вектор-строка исходного помехо незащищенного кода, dim a = k ;

y – вектор-строка помехозащищенно го ( n, k ) -кода, наблюдаемого на выходе КУ, dim y = n, n k, m = n k – число вводимых избыточных разрядов кода y ;

– вектор-строка помехи, воздействующей на КС, dim = n ;

f = y + – вектор-строка искаженного кода, принимаемого из КС;

E – вектор-строка синдрома ошибки (искажения) в принятой из КС кодовой комбинации, dim E = m.

Процесс формирования вектор-строки помехозащищенного кода y из вектор-строки помехонезащищенного кода a, осуществляемый в КУ, может быть описан линейным векторно-матричным соотношением y = aG, (1.144) где G – ( k n ) -матрица, именуемая образующей матрицей [42, 51] по мехозащищенного линейного кода y.

Процесс искажения передаваемой кодовой комбинации y в канале связи под действием помехи такой, что на выходе КС формируется вектор-строка искаженного кода f, может быть представлен операци ей суммирования f = y +, (1.145) соответствующих вектор-строк.

И, наконец, процесс декодирования, состоящий в формировании вектор-строки синдрома (опознавателя) E из вектор-строки принятого из КС искаженного кода f может быть описан векторно-матричным соотношением E= f H, (1.146) где H – ( k n ) -матрица, именуемая проверочной [42, 51] матрицей помехозащищенного кода y.

Заметим, что все операции умножения и суммирования в соотно шениях (1.144) – (1.146) и ниже осуществляются по правилам моду лярной арифметики с модулем два ( mod 2 ).

Выясним: какими свойствами должна обладать пара матриц ( G, H ) с тем, чтобы она порождала помехозащищенный код?

С этой целью сформулируем утверждение.

Утверждение 1.28 (У1.28). Матрица G, принятая за образующую матрицу, и матрица H, принятая за проверочную матрицу, порож дают помехозащищенный код, если они удовлетворяют матричному соотношению GH =O. (1.147) Доказательство утверждения строится [42] на использовании со отношений (1.146), (1.145) и (1.144). Если в (1.146) подставить (1.145), в котором учесть (1.144), то получим цепочку равенств E = f H = ( y + ) H = ( a G + ) H = a GH + H. (1.148) Напомним, что декодирующие устройства помехозащищенных ко дов, построенные в прямой логике, функционируют так, что при отсут ствии ошибки в принятой кодовой комбинации декодирующее устрой ство формирует нулевой синдром, а в случае наличия ошибок, для об наружения или исправления которых осуществлено помехозащитное кодирование, ДКУ формирует соответствующий ненулевой синдром.

Таким образом ДКУ реализует соотношение E = E ( ) =0 = O, E = E ( ) 0 O. (1.149) Если теперь в (1.148) положить = 0, то в силу первого из соот ношений (1.149) получим векторно-матричное равенство E = a GH = O, (1.150) выполняемое при любых вектор-строках исходного кода a, что дока зывает справедливость утверждения.

Примечание 1.1 (ПМ1.1). Следует заметить, что характеристи ческое свойство (1.147) матриц ПЗК не нарушается при перестановке строк образующей матрицы G и столбцов проверочной матрицы H.

При перестановке столбцов матрицы G для сохранения (1.147) необ ходима согласованная перестановка строк матрицы H.

Нетрудно видеть, что соотношения (1.147) – (1.149) содержат дока зательство следующего утверждения.

Утверждение 1.29 (У1.29). Процедура формирования синдрома E имеет два эквивалентных представления (1.145) и E = H. (1.151) Следует заметить, что векторно-матричные представления (1.146) и (1.149) имеют различную нагрузку и среду реализацию. Первое ис пользуется в аппаратурной среде, а второе – в аналитической при фор мировании проверочной матрицы H помехозащищенного кода.

Заметим так же, что доказательство У1.28 делает справедливым положения следующего утверждения.

Утверждение 1.30 (У1.30). Пара матриц ( G, H ) размерности dim G = k n и dim H = n m, удовлетворяющие матричному соотно шению (1.147), принятые соответственно за образующую и провероч ную матрицы кода, порождают помехозащищенный ( n, k ) -код, ха рактеризующийся корректирующей способностью, определяемой мощностью [ { E} ] множества { E} ненулевых синдромов, задаваемой в силу (1.149) соотношением [ { E} ] = 2 m 1. (1.152) Поставим теперь задачу конструирования алгоритмов формирова ния образующей G и проверочной H матриц помехозащищенного ко да. Эта задача не инвариантна относительно требований к блоковой систематике формируемого помехозащищенного кода. В связи с этим введем следующие определения.

Определение 1.8 (О1.8). Систематическим помехозащищенным кодом называется код, элементы которого представляют собой ком бинации элементов исходного помехонезащищенного кода. При этом ПЗК называется линейным, если эти комбинации строятся на основе линейных бинарных операций модулярной арифметики, и нелинейным, если комбинации строятся на основе нелинейных бинарных операций модулярной арифметики.

Нетрудно видеть, что ПЗК, сформированные в силу правила (1.144), являются систематическими и линейными, при этом вся систе матика помехозащищенного линейного кода y заложена в образующей матрице G.

Определение 1.9 (О1.9). Систематический ПЗК называется сис тематическим помехозащищенным кодом с полной блоковой систе матикой, если проверочные разряды кода, вводимые в структуру ПЗК процедурой кодирования, и информационные разряды, образованные исходным помехонезащищенным кодом (ПНЗК) a, представляют со бой отдельные монолитные блоки.

Следует заметить, что в современной телекоммуникационной тех нике, в которой преобладает передача кодов «старшим разрядом впе ред», в ПЗК с полной блоковой систематикой исходный ПНЗК образу ет старшие разряды кода, а блок проверочных разрядов – младшие его разряды.

Определение 1.10 (О1.10). Систематический ПЗК называется ко дом с неполной блоковой систематикой, если разряды исходного ПНЗК и проверочные разряды ПЗК перемежаются, не образуя монолитные блоки.

С целью конструирования алгоритмов формирования матриц G и H ПЗК сформулируем дополнительно следующее утверждение.

Утверждение 1.31 (У1.31). Если помехозащищенный код исправля ет ошибки кратности = 1, s, то синдром E j ошибки j в разря дах для j -ой их комбинации j = 1,C n равен сумме по модулю два строк H i, i = 1,n проверочной матрицы H однократных ошибок, сум ма которых образует данную ошибку j.

Доказательство утверждения строится на использовании соотно шения (1.149), в котором вектор-строку синдрома E, вектор-строку ошибки следует писать в поэлементной форме { } { } E = row E, = 1,m, = row i, i = 1,n, (1.153) а проверочную матрицу H записать в столбцовой форме { } H = col H i, i = 1,n, (1.154) где H i – i -я строка матрицы H. Подстановка компонентов соотноше ния (1.149), представленных в форме (1.153), (1.154), в соотношение (1.152) доказывает справедливость утверждения.

Примечание 1.2 (ПМ1.2). Нетрудно видеть, что если при коди ровке векторов ошибок векторами-синдромами E при построении ПЗК, исправляющего ошибки кратности s 1 или обнаруживающего ошибки кратности r 2, учтены условия У1.31, то достаточно иметь таблицу кодировок ошибок только первой кратности. Ниже при построении алгоритмов формирования матриц G и H кода пред полагается, что условия У1.31 выполняются.

Утверждение 1.32 (У1.32). Столбцы H, = 1,m матрицы H принадлежат ядру матрицы G так, что выполняются соотношения H ker G GH = O ;

(1.155) в свою очередь столбцы G T, j = 1,k транспонированной G T образую j щей матрицы принадлежат ядру транспонированной H T провероч ной матрицы кода так, что выполняются соотношения G T ker H T H T G T = O. (1.156) j j Доказательство утверждения строится на представлении матрич ного соотношения (1.147) в векторно-матричной форме с использова нием правых вектор-столбцов G[ H 1 H 2 H H m ] = O, (1.157) что позволяет записать GH = O, = 1,m H ker G.

в свою очередь матричное соотношение (1.147) в транспонированной форме по аналогии с (1.157) может быть записано в виде [ ] H T G T = H T G1 G2 G T Gk = O, T T T j что позволяет записать H T G T = O, j = 1,k G T ker H T.

j j Утверждение 1.33 (У1.33). Матрицы G и H, сформированные в виде ~ [ ] G.

~ G = Ik G, H = (1.158) Im где I k – k k -единичная матрица, I m – m m -единичная матрица, ~ G – k m -матрица синдромов однократных ошибок вида [ ] ~ = Om, (1.159) ~ где – k -мерный вектор-строка, содержащий одну единицу, Om – m -мерная нулевая вектор-строка, порождают помехозащищенный код, обладающий полной блоковой систематикой.

Доказательство утверждения в первой части состоит в непосред ственной подстановке матриц G и H вида (1.158) в (1.147), которая приводит к ~ [ ] ~ G ~ ~ GH = I k G = G + G = O.

Im Доказательство второй части утверждения строится на подстановке матрицы G вида (1.158) в (1.144) [ ][ ] ~ ~ y = aG = a I G = a aG, (1.160) что обнаруживает полную блоковую систематику ПЗК y.

Алгоритмы формирования матриц G и H ПЗК различаются по следовательностью этой процедуры. Сначала рассмотрим процедуры формирования матриц помехозащищенного кода, в которых сперва конструируется проверочная матрица H, а затем на основе сформули рованных утверждений вычисляется образующая матрица G ПЗК.

Вторую группу алгоритмов составляют процедуры, в которые на пер вом этапе формируется матрица G кода, а затем формируется прове рочная матрица H ПЗК.

1.6.1 Формирование матриц ПЗК с помощью проверочных равенств при декодировании и кодировании Процедура формирования матриц H и G ПЗК, основанная на ис пользовании проверочных равенств при декодировании и кодировании, инвариантна относительно требований к блоковой систематике кода.

По существу уровень блоковой систематики в структуре проверочной матрицы H кода закладывается в силу (1.146) и У1.31 на первом шаге процедуры, состоящем в кодировке векторов-строк ошибок j векто рами-строками синдромов E j. Следует заметить, что на этапе кодиро вок ошибок j синдромами E j может быть так же заложен [42, 51] способ технической реализации исправления ошибки(ок) в принятой кодовой комбинации. Так кодировкой ошибок j синдромами E j по схеме Р. Хэмминга [42, 51] закладывается возможность технической реализации исправления однократных ошибок с использованием стан дартных дешифраторов [27, 51].

Алгоритм 1.6 (А1.6) формирования матриц ПЗК с помощью проверочных равенств при кодировании и декодировании 14. Составить таблицу кодировок векторов-строк однократных ошибок j векторами-строками синдромов E j, начиная с ошиб ки в старшем разряде n = [ 1 On1 ] и заканчивая ошибкой в младшем разряде 1 = [ On1 1], где On1 – ( n 1) -мерная нуле вая вектор-строка, так, что E j удовлетворяют условиям У1.31 и принятым техническим соображениям относительно процедуры коррекции искаженного кода.

15. Сформировать проверочную матрицу H на основании состав ленной таблицы кодировок и соотношения (1.151), которая по строчно должна удовлетворять условию H j = E n+1 j ;

j = 1, n. (1.161) 16. На основании составленной проверочной матрицы H кода и со отношения (1.146), описывающего процесс формирования син дрома в аппаратурной среде ДКУ, составить аналитические вы ражения для каждого разряда E, = m, 1 синдрома как функции принятой из КС искаженной кодовой комбинации { } f = row f n+1 j ;

j = 1,n в силу соотношения E = f H m+1, = 1,m, (1.162) где H m+1 – ( m + 1 ) -ый столбец матрицы H.

17. Сформировать аналитические выражения для помехозащитного { } кодирования помехонезащищенного кода a = row ai, i = k,1, для чего записать соотношения (1.162) в предположении, что в КС отсутствует помеха ( = 0 ), положив, тем самым, справедли вость выполнения условий E = 0, f n+1 j = y n+1 j, j = 1,n, (1.163) порождающих систему равенств 0 = y H m+1 = y n+1 j, = 1,m, (1.164) допускающих явное разрешение относительно разрядов y j ПЗК как функций разрядов ai помехонезащищенного кода в форме ( ) y j = y j ai, i = 1,k, j = 1,n. (1.165) { } кода 18. Сформировать образующую матрицу G = row G j, j = 1,n на основании соотношения (1.144) в силу условия { ( ) } G j = arg y j = a G j = y j ai, i = 1,k ;

j = 1,n, (1.166) в котором известны вектор-строка помехонезащищенного кода a, а также линейная связь y j и ai в форме (1.165).

1.6.2 Формирование матриц ПЗК с использованием матричного уравнения Сильвестра На возможность использования матричного уравнения Сильвестра для формирования проверочной матрицы циклического помехозащи щенного кода (ЦПЗК) указано в параграфе 1.4. Эти возможности в сис тематизированном виде являются основой алгоритма 1.7 формирова ния указанной матрицы ЦПЗК.

Алгоритм 1.7 (А1.7) формирования проверочной матрицы ЦПЗК на основе использования матричного уравнения Сильвестра 1. Сформировать k -разрядный ПНЗК на основе мощности [ Q] = N и заданного массива Q передаваемой или хранимой ин формации так, что k = arg{2 k N и = [ Q ] } (1.167) 2. Сформировать число m проверочных разрядов, удовлетворяю щих требованием к достоверности передачи или хранения ин формации и к способу реализации корректирующей способности синтезируемого ПЗК.

3. Выбрать неприводимый модулярный многочлен g ( ) степени deg g ( ) = m, удовлетворяющий всем требованиям к корректи рующей способности кода [28, 42, 51].

4. Задать m m -матрицу в произвольном базисе = arg { det ( I + ) = g ( ) }, (1.168) так, чтобы она обладала характеристическим полиномом g ( ).

5. Выбрать матрицу L размерности m 1, образующую с матрицей полностью управляемую пару (, L).

6. Задать матрицу A размерности n n, где n = k + m, с индексом нильпотентности равным = n в канонической Жордановой [12, 13] форме A = J { = 0 }. (1.169) 7. Выбрать матрицу P размерности 1 n, образующую с матрицей A полностью наблюдаемую пару ( A, P ) матриц.

8. Найти решение матричного уравнения Сильвестра T A + T = L P (1.170) относительно матрицы T.

9. Сформировать проверочную матрицу H помехозащищенного ( n, k ) -кода в силу соотношения H =T. (1.171) Примечание 1.3 (ПМ.1.3). Множество формируемых матриц H с помощью приведенного алгоритма (А1.7) может быть существенно расширено, если в матрицах L и P допустить отличное от единицы соответственно число столбцов и строк, но при этом они всякий раз должны быть согласованы с тем, чтобы существовало их произведе ние L P.

1.6.3 Использование сингулярного разложения матриц в задаче формирования матриц ПЗК Рассмотрим теперь алгоритм конструирования образующей матри цы G ПЗК по известной проверочной матрице H, который основан на положениях У1.32 и использующий возможности сингулярного разло жения (SVD-процедуры) матриц [12, 16]. С этой целью сделаем неко торые пояснения.

Определение 1.11 (О1.11). Сингулярным разложением [12, 16] µ матрицы N над произвольным полем называется ее представ ление в форме N = UV T, (1.172) где U – -матрица левого сингулярного базиса, V – µ µ -матрица правого сингулярного базиса, обладающие свойством над этим полем UU T = U T U = I, VV T = V T V = I µ, (1.173) – µ -квазидиагональная матрица сингулярных чисел, размещае мых на главной диагонали, при этом их число равно min {, µ }.

Если с помощью (1.172) сконструировать матрицы NN T и N T N, то в силу (1.173 получим NN T = U T U T ;

N T N = V T V T, (1.174) при этом оказывается, что сингулярные числа совпадают с арифмети ческими значениями корней из собственных значений матриц NN T и N T N. Элементы левого сингулярного базиса U являются нормиро ванными собственными векторами матрицы NN T, а элементы правого сингулярного базиса V являются нормированными собственными век торами матрицы N T N.

Выделим случай реализации µ -матрицы N, которая характери зуется выполнением условия µ, (1.175) тогда [12, 16] µ последних столбцов матрицы V правого сингуляр ного базиса будут принадлежать ядру матрицы N, что записывается в форме Vi ker N, i = + 1, µ. (1.176) Для построения алгоритма формирования образующей матрицы G ПЗК по известной проверочной матрице H, необходимо положить N = HT.

Если с помощью (1.172) сконструировать матрицы NN T и N T N, то в силу (1.173 получим NN T = U T U T ;

N T N = V T V T, (1.174) при этом оказывается, что сингулярные числа совпадают с арифмети ческими значениями корней из собственных значений матриц NN T и N T N. Элементы левого сингулярного базиса U являются нормиро ванными собственными векторами матрицы NN T, а элементы правого сингулярного базиса V являются нормированными собственными век торами матрицы N T N.

Выделим случай реализации µ -матрицы N, которая характери зуется выполнением условия µ, (1.175) тогда [12, 16] µ последних столбцов матрицы V правого сингуляр ного базиса будут принадлежать ядру матрицы N, что записывается в форме Vi ker N, i = + 1, µ. (1.176) Для построения алгоритма формирования образующей матрицы G ПЗК по известной проверочной матрице H, необходимо положить N = HT.

Алгоритм 1.8 (А1.8) формирования образующей матрицы G ПЗК по известной проверочной матрице H с использованием SVD-процедуры 1. Сформировать проверочную n m -матрицу H помехозащищен ного ( n, k ) -кода с помощью приведенных А1.6 и А1.7.

2. Построить сингулярное разложение m n -матрицы H T в форме H T = U н н Vн, T (1.177) где dim U н = m m, dim н = m n, dim Vн = n n.

3. Сконструировать ядро матрицы H T в форме { ( ) } ker H T = row i ker H T, i = m + 1,n. (1.178) 4. В силу соотношений (1.156) сформировать образующую матри цу G помехозащищенного ( n, k ) -кода в форме ( ) T G = ker H T. (1.179) 1.6.4 Формирование матриц ПЗК с полной блоковой систематикой Рассмотрим проблемы формирования матриц G и H ПЗК с пол ной блоковой систематикой. Если формирование матриц кода осуще ствляется с помощью алгоритма 1.6, то блоковая систематика заклады вается на этапе кодировке вектор-строк однократных ошибок j в m младших разрядах помехозащищенного ( n, k ) -кода векторами строками синдромов E j так, чтобы последние m синдромов в таблице кодировок образовывали m m -единичную матрицу I m. При этом проверочная матрица H ( n, k ) -кода примет вид (1.158), который в си лу положений утверждения У.1.33 является основой для формирования образующей матрицы G ПЗК в форме (1.158).

Завершим рассмотрение поставленной проблемы формирования матриц ( G, H ) помехозащищенного ( n, k ) -кода случаем циклических ПЗК, матрицы которых обладают полной блоковой систематикой.

Приводимый ниже алгоритм строится на базе работ [42, 44].

Алгоритм 1.9 (А1.9) конструирования матриц циклического ПЗК с полной блоковой систематикой 1. Выполнить п.п. 1 – 3 алгоритма 1.7.

2. Вычислить остаток ri ( x ) от деления ММ, производимого на об разующий ММ g ( x ) в силу соотношения x n i ri ( x ) = rest ;

i = 1,k. (1.180) g( x ) 3. Сформировать кодовые аналоги остатков ri ( x ) в форме m разрядных вектор-строк x n i ~ G i = к ri ( x ) = rest ;

i = 1,k, (1.181) g( x ) где к{(• )} – код ММ (•).

~ 4. Сформировать k m -матрицу G кодов остатков в силу соотно шения { } ~ ~ G = col G i ;

i = 1,k. (1.182) 5. С использованием соотношения (1.158) сформировать образую щую G и проверочную H матрицы циклического ПЗК с полной блоковой систематикой.

Пример 1.8 (Пр1.8) Решается задача формирования матриц G и H ПЗК ( 15,7 ), ис правляющего ошибки кратности s = 2 и обладающего синдромами од нократных ошибок, удовлетворяющих условиям У1.31.

Формирование матриц требуется осуществлять с помощью прове рочных равенств при декодировании и кодировании. Тогда, следуя ал горитму 1.6:

1. Составим таблицу 1.2 однократных ошибок, используя синдро мы группового кода [50], исправляющие ошибки кратности s = 2.

2. Составим проверочную матрицу H, используя соотношение (1.158), в результате чего получим 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 { } j = 1,15 = 0 H = col H j = E n+1 j ;

0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 Таблица 1. Синдром Синдром Номер искаженного раз- Номер искаженного раз E = [E8 E7 E6 E5 E4 E3 E2 E1 ] E = [E8 E7 E6 E5 E4 E3 E2 E1 ] ряда ряда 15 11011011 7 14 10110101 6 13 10010110 5 12 10000000 4 11 01101010 3 10 01010101 2 9 8 3. Составим аналитические выражения для каждого разряда E, = m,1 синдрома в силу соотношения (1.162), которые при мут вид E8 = f 15 + f 14 + f 13 + f E7 = f 15 + f 11 + f 10 + f E6 = f 14 + f 11 + f 8 + f E5 = f 15 + f 14 + f 13 + f 9 + f 8 + f E4 = f 15 + f 11 + f 5 + f E3 = f 14 + f 13 + f 10 + f 5 + f E 2 = f 15 + f 13 + f 11 + f 8 + f 5 + f E1 = f 15 + f 14 + f 10 + f 8 + f 5 + f 4. Сформируем аналитические выражения для помехозащитного кодирования, используя соотношения (1.163), в результате чего получим y12 = y15 + y14 + y y 9 = y15 + y11 + y y7 = y14 + y11 + y y6 = y15 + y14 + y13 + y10 + y y 4 = y15 + y11 + y y 3 = y14 + y13 + y10 + y y 2 = y13 + y15 + y11 + y 8 + y y1 = y15 + y14 + y10 + y 8 + y 5. Сформируем образующую матрицу G ПЗК ( 15, 7 ), используя соотношение (1.166). Для этого заметим, что соотношения, по лученные в п.4 алгоритма, обнаруживают, что проверочными разрядами ПЗК являются 12, 9, 7, 6, 4, 3, 2, 1, а информацион ными – 15, 14, 13, 11, 10, 8, 5-й разряды. Если теперь процесс (1.144) формирования ПЗК записать в развернутой форме [ y15 y14 y13 y12 y11 y10 y9 y8 y7 y6 y5 y4 y3 y2 y1 ]=, = [ a7 a6 a5 a4 a3 a2 a1 ]G, где y15 = a y14 = a y13 = a y12 = a y11 = a y10 = a y 9 = a = a7 + a6 + a y = a7 + a4 + a y = a6 + a4 + a y = a7 + a6 + a5 + a 3 + a y = a7 + a4 + a y = a6 + a5 + a3 + a y = a7 + a5 + a4 + a 2 + a y = a7 + a6 + a3 + a 2 + a y то образующая матрица кода ( 15, 7 ) принимает вид 100 100 100 10 10 0 10 10000 1100 10 00 1100000 100 G = 0000 10 10 100 10 00000 1100 100 10 0000000 111000 0 0 0 0 0 0 0 0 0 0 1 1 1 1 Примечание 1.4 (ПМ1.4). Рассмотренный ПЗК ( 15, 7 ), исправ ляющий ошибки кратности s = 2 имеет избыточное число провероч ных разрядов. Действительно, число синдромов m N c = 2 1 = 2 1 = 255, а число ошибок первой и второй кратности N ош = С n + С n = n ( n + 1) / 2 = 120. Складывается впечатление, что со 1 отношение N c N ош сохранится, если число m проверочных разрядов сократить с 8 до 7. Действительно, в этом случае код ( 15,7 ) транс формировался бы в код ( 14,7 ), для которого было бы справедливо не равенство N c = 2 m 1 = 27 1 = 127 N ош = С n + С n = 105.

1 Но в этом случае необходимо было бы приведенные в таблице 1.1 син дромы укоротить на один старший разряд. Однако при этом наруша ется условие [42, 51] и корректирующая способность ПЗК, исправ ляющего ошибки кратности s = 2, что вызывается появлением нуле вого синдрома (для ошибки в двенадцатом разряде в рамках рассмот ренного примера) и сокращением кодового расстояния между синдро мами до d min = 3.

Пример 1.9 (Пр1.9) Иллюстрируется процедура формирования проверочной матрицы H ПЗК ( 7, 4 ), исправляющего ошибки кратности s = 1.

Читателю предлагается убедиться, что проверочная матрица H вида 1 0 ~ G ~ 1 1 H =, где G =, 1 1 I 0 1 получена решением уравнения Сильвестра (1.170) относительно мат рицы = H T с матричными компонентами 0 1 0 [ ] I 6 6 T = 1 0 1 ;

L = 0 ;

A = O7 T ;

P = 1 O6.

O 1 0 0 Матрица H обнаруживает полную блоковую систематику ПЗК [ ] ( 7,4 ), поэтому образующая матрица кода принимает вид G = I G. ~ Пример 1.9 (Пр1.9) Иллюстрируется процедура формирования проверочной матрицы H ПЗК ( 7, 4 ), исправляющего ошибки кратности s = 1.

Читателю предлагается убедиться, что проверочная матрица H вида 1 0 ~ G ~ 1 1 H =, где G =, 1 1 I 0 1 получена решением уравнения Сильвестра (1.170) относительно мат рицы = H T с матричными компонентами 0 1 0 [ ] I 6 6 T = 1 0 1 ;

L = 0 ;

A = O7 T ;

P = 1 O6.

O 1 0 0 Матрица H обнаруживает полную блоковую систематику ПЗК [ ] ( 7,4 ), поэтому образующая матрица кода принимает вид G = I G. ~ 1.7. Анализ структуры неподвижных состояний и замкнутых циклов линейных двоичных динамических систем В данном параграфе рассматриваются проблемы, связанные со спецификой структуры пространства состояния линейных двоичных динамических систем, характеризующихся наличием неподвижных состояний и замкнутых циклов при отсутствии ( u ( k ) = 0 ) и наличии ( u ( k ) 0 ) экзогенной задающей последовательности на входе ЛДДС.

Решаемая задача связана с особенностью структуры алгебраического спектра собственных значений { A }= { i : D( ) = det ( I + A) = 0 } матрицы A состояния линейной ДДС, особенностями структуры гео } метрического спектра собственных векторов { i : A i = i ;

i = 1,n той же матрицы, с фактом, когда этот спектр имеет своими элементами вектор начального x( 0 ) (в общем случае исходного x( k ) ) состояния системы и столбцы матрицы B входа ЛДДС. Для случая, когда u ( k ) 0 решаемая задача связана с проблемой управляемости пары матриц ( A, B ). И, наконец, решение задачи в значительной степени за висит от показателя µ, которому принадлежит матрица A.

Рассматриваемая проблема решается с использованием моделей «вход–состояние» линейных ДДС, задаваемых в рекуррентной x ( k + 1) = A x ( k ) + B u ( k ), x ( 0 ) ;

(1.183) и суммарной k x ( k ) = A x ( 0 ) + A k 1i B u ( i ) k (1.184) i = формах.

Анализ структуры пространства состояния ЛДДС, задаваемой мо делями (1.183), (1.184) проведем для случая, когда ( n r ) матрица B входа представляет собой n -мерный вектор-столбец так, что r = 1.

1.7.1 Неподвижные состояния линейной двоичной динамической системы Рассмотрение проблемы начнем с определения неподвижного со стояния.

Определение 1.12 (О1.12). Состояние x( k ) ЛДДС (1.182), (1.183) называется неподвижным, если оно удовлетворяет условию x ( k + 1) = x ( k ), k. (1.185) Анализ структуры неподвижных состояний начнем со случая, ко гда экзогенная последовательность u ( k ) на входе ЛДДС отсутствует.

Для этого случая u ( k ) = 0, поэтому модели (1.183), (1.184) принимают вид x ( k + 1) = A x ( k ), x ( 0 ) ;

(1.186) x ( k ) = Ak x ( 0 ). (1.187) Утверждение 1.34 (У1.34). ЛДДС (1.186), (1.187) при любой ( n n ) -реализации матрицы A состояния всегда имеет в качестве неподвижного состояния нулевое x( k) 0. (1.188) Доказательство утверждения использует рекуррентную модель (1.186), подстановка в которую (1.188) дает цепочку равенств x ( k + 1) = A x ( k ) = A O = O = x ( k ).

Утверждение 1.35 (У1.35). ЛДДС (1.186), (1.187) при реализации матрицы A состояния в форме единичной ( n n ) -матрицы так, что A = I, имеет неподвижными все 2 n состояния двоичной системы.

Доказательство утверждения, как и выше, использует рекуррент ную модель (1.186) ЛДДС, в которой следует положить A = I так, что (1.186) принимает вид x ( k + 1) = A x ( k ) = I x ( k ) = x ( k );

x ( k ).

Выделим теперь класс матриц состояния ЛДДС (1.186), (1.187), при которых двоичная система обладает неподвижным состоянием x ( k ) 0, отличным от нуля.

Утверждение 1.36 (У1.36). Если состояние x ( k ) является собст венным вектором матрицы A, соответствующим ее собственному значению равному единице ( = 1), то состояние x( k)= (1.189) является неподвижным.

Доказательство утверждения использует рекуррентную модель ЛДДС (1.186) и определение собственного вектора матрицы A =. (1.190) Для собственного значения = 1 соотношение (1.190) принимает вид A =. (1.191) Если x ( k ) выбран в форме (1.189), тогда используя (1.186) полу чим цепочку равенств x ( k + 1) = A x ( k ) = A = = x ( k ). (1.192) Выделим класс матриц состояния ЛДДС, которые не порождают ненулевые неподвижные состояния x ( k ) 0. Очевидно, что в этот класс входят все ( n n ) -матрицы A, обладающие индексом нильпо тентности, удовлетворяющим неравенствам 1 n. (1.193) Это вызвано тем, что нильпотентная ( n n ) -матрица A с индексом нильпотентности (1.193) имеет все n собственных значений, равных нулю ( = 0 ), что делает невозможным переход от (1.190) к (1.191).

В этот класс также входит ( n n ) -матрица A, принадлежащая максимальному показателю µ = 2 n 1, что имеет место, когда характе ристический полином матрицы A D( ) = det ( I + A) представляет со бой неприводимый полином степени n ( deg D( ) = n ). В этом случае матрица A не имеет собственных значений в простом двоичном поле Галуа GF ( 2 ) = {0,1}, как следствие матрица A не имеет собственных векторов, в силу чего не выполняется соотношение (1.191). Таким об разом неподвижным ненулевым состоянием обладает ЛДДС, ( n n ) матрица A состояния которая принадлежит показателю µ, удовлетво ряющему неравенствам n µ 2n 1. (1.194) Рассмотрим теперь структуру неподвижных состояний для случая отличной от нуля экзогенной последовательности на входе ЛДДС так, что выполняются соотношения u( k ) 0 ;

u( k ) = 1, k. (1.195) Утверждение 1.37 (У1.37). Нулевое состояние x ( k ) 0 не принад лежит множеству неподвижных состояний ЛДДС при ненулевой эк зогенной последовательности, удовлетворяющей условиям (1.195).

Доказательство утверждения строится на подстановке x ( k ) 0 и (1.195) в модель (1.183) ЛДДС, что приводит к соотношению x ( k + 1) = B u ( k ). (1.196) В случае если dim B = ( n 1 ) и B O соотношение x ( k + 1) = O = x ( k ) при u ( k ) = 1 не выполняется.

Утверждение 1.38 (У1.38). Ненулевое неподвижное состояние ЛДДС (1.183) вычисляется в силу соотношения x ( k ) = ( I + A) B.

(1.197) Доказательство утверждения строится на непосредственном вы числении неподвижного состояния, опирающегося на его определение (1.185), и соотношение (1.183) с учетом (1.195), из которых получаем x( k)= Ax( k)+ B, что записывается в форме ( I + A) x ( k ) = B, (1.198) приводящей к выражению (1.197), если матрица ( I + A ) обратима.

Выделим случай, когда матрица ( I + A ) не является обратимой.

С этой целью воспользуемся свойством спектра собственных значений матричной функции от матрицы. В соответствии с этим свойством { } ~ спектр { I + A}= i ;

i = 1,n состоит из элементов ~ i = 1 + i, i = 1,n, (1.199) где i – элемент алгебраического спектра { } { A} = i : det ( I + A) = 0 ;

i = 1,n собственных значений матрицы A. В силу соотношения (1.199) матри ца ( I + A ) является обратимой, а следовательно линейная ДДС (1.183), (1.184) имеет при u ( k ) = 1 неподвижное состояние, определяемое в си лу (1.198), если матрица A является нильпотентной с любым индексом нильпотентности или если матрица A имеет своим характеристиче ским полиномом любой неприводимый полином степени n, принадле жащий показателю µ, удовлетворяющему условию (1.194).

Необратимой матрица ( I + A ) является для ЛДДС, матрица A состоя ния которой имеет в своем алгебраическом спектре собственных зна { } ~ чений { A} = i : det ( I + A) = 0 ;

i = 1,n элемент j = 1 так, что j в ~ силу (1.200) обращается в ноль ( j = 0 ). В этом случае линейная ДДС (1.183), (1.184) не имеет неподвижных состояний отличных от нулево го. Следует, однако, заметить, что сказанное выше справедливо, если иметь в виду произвольную реализацию матрицы B. Если же матрица входа такова, что она принадлежит пространству столбцов матрицы B, то есть выполняется условие B Jm( I + A ), то вектор x ( k ) ищется из условия n x ( k ) = arg B = ( I + A )i xi ( k ).

i = 1.7.2 Замкнутые циклы линейных ДДС Вынесенную в название параграфа проблему как для случая иссле дования неподвижных состояний будем решать с использованием мо дельных представлений ЛДДС в форме (1.186), (1.187) при отсутствии на входе двоичной динамической системы экзогенной последователь ности ( u ( k ) = 0 ) и в форме (1.183), (1.184) при наличии на входе сис темы экзогенной последовательности ( u ( k ) 0 ).

Предварим исследование важным для решения проблемы утвер ждением.

Утверждение 1.39 (У1.39). Пусть ( n n ) -матричная функция f ( A) от ( n n ) -матрицы A задана над простым полем Галуа GF ( p ) при p = 2 в степенной форме f ( A) = A q (1.200) где q – целое положительное число. Пусть матрица A обладает ал гебраическим спектром { A } = { i : det ( I + A) = 0 ;

i GF ( 2 ) } соб ственных значений и геометрическим спектром } { i : A j = j ;

j = 1,rA собственных векторов. Пусть матричная функция f ( A) от матрицы A обладает алгебраическим спектром { f ( A) } = { f i = f ( i ) : det [ f I + f ( A) ] = 0 ;

i = 1,n } собственных значений и геометрическим спектром { { : f ( A) = f }. Тогда геометрический спектр f ;

= 1,r } соб ственных векторов f ( A) включает в себя геометрический спектр } собственных векторов матрицы { j ;

j = 1,n A A, при этом они мо гут не совпадать так, что выполняется соотношение { } f ;

= 1,r f } { j ;

j = 1,r (1.201) rf r. (1.202) Доказательство. Очевидно сформулированное утверждение спра ведливо для матрицы A, не являющейся нильпотентной матрицей лю бого значения индекса нильпотентности, которая обладает алгебраи ческим спектром собственных значений, составленным из нулей так, { } что { A } = i = 0 ;

i = 1,n, а также для матрицы A, имеющей своим характеристическим полиномом D( ) = det ( I + A) неприводимый по лином степени n, который не имеет корней в простом поле Галуа GF ( 2 ) так, что { A } = { i GF ( 2 ) }. Таким образом утверждение имеет дело со случаем, когда характеристический полином матрицы A разложим в произведение двучленов D( ) = det ( I + A) = ( + j ) n (1.203) j = и который характеризуется кратными единичными собственными зна ( ) чениями j = 1 j = 1,n. Известно [13], что число rA различных собст венных векторов j матрицы A, имеющей кратные корни, меньше n = dim x и определяется из соотношения rA = dim{ Ker ( I + A) } = n dim{ Jm ( j I + A)} = n rank ( I + A) (1.204) В свою очередь число r f собственных векторов f матричной функ ции f ( A) от матрицы A определяется из соотношения r f = dim{ Ker ( f I + f ( A))}= = n dim{ Jm ( f I + f ( A))} = n rank ( I + f ( A)) (1.205) Причем так как по свойству спектра собственных значений матричной функции f ( A) от матрицы A оказывается справедливым соотношение f = f ( j ) : j, = 1,n, (1.206) то с учетом степенного характера f ( A) = A q спектр кратных единич { } = 1: j = 1, n сохраняется и для матрич ных значений матрицы A j { } ной функции f ( A) f = 2 = 1: = 1,n. Если к этому добавить, что матричная функция f ( A) в общем случае не сохраняет базис пред ставления исходной матрицы A, то размерности ядер (нуль пространств) матриц ( j I + A) = ( I + A) и ( I + f ( A)) = ( I + f ( A)) могут быть различными так, что выполняется неравенство r f rA. (1.207) Пример 1.10 (Пр1.10) Для иллюстрации положений утверждения рассмотрим матрицу 0 1 A = 0 0 1 1 и матричную функцию от матрицы 0 1 0 0 1 0 0 0 f ( A) = A = A A = 0 0 1 0 0 1 = 1 1 1 1 1 1 1 1 1 0 1 det ( I + A) = det 0 1 = 3 + 2 + + 1 = ( + 1).


1 1 + { A} = { 1 = 2 = 3 = 1}.

f ( ) det ( f I + f ( A)) = det 1 1 = 3f + 2f + f + 1 = f + 1+ f f 1 { f ( A) = A 2 } = { f 1 = f 2 = f 3 = 1}.

Вычислим 1 rA = dim Ker ( I + A) = Ker 0 0 1 = n dim{ Jm ( I + A) }= 1 1 1 1 = n rank ( I + A) = 3 rank 0 1 1 = 3 2 = 1.

1 1 Размерность rA ядра Ker ( I + A), определяющая число собствен ных векторов j, составляет rA = 1. Таким образом, матрица A имеет единственный собственный вектор 1 0 1 0 1 = 1 такой, что A = : 0 0 1 1 = 1 выполняется.

1 1 1 1 1 Оценим теперь размерность r f ядра Ker ( f I + f ( A)), определяющую число собственных векторов f 1 0 dim Ker ( f I + f ( A)) = Ker 1 0 1 = 1 0 = n dim{ Jm ( f I + f ( A))} = n rank ( I + f ( A)) = 1 0 = 3 rank 1 0 1 = 3 1 = 1 0 Таким образом f ( A) = A 2 имеет следующие собственные вектора:

f 1 = по свойству матричной функции от матрицы сохра нять геометрический спектр собственных векторов в форме f ( A) = A 2 = A { = A = = f 1. Действительно A 0 0 1 1 f ( A) = 1 1 1 1 = 1 = f 1 ;

1 0 0 1 f 2 и f 3, вычисленные из соотношения f ( A) f = f так, что 1 0 0 1 1 f 2 = 0 : f ( A) f 2 = 1 1 1 0 = 0 = f 2 ;

1 1 0 0 1 0 0 0 1 0 f 3 = 1 : f ( A) f 3 = 1 1 1 1 = 1 = f 3.

0 1 0 0 0 Заметим, что собственные векторы f 1, f 2, f 3 матричной функ ции f ( A) = A 2 оказались линейно зависимыми. Действительно 1 0 f 1 = f 2 + f 3 = 0 + 1 = 1 ;

1 0 1 1 f 3 = f 1 + f 2 = 1 + 0 = 1 и т.д.

1 1 Этого результата и следовало ожидать, так как линейная оболочка, натянутая на эти векторы, имеет размерность r f = 2 n = 3.

Введем понятие замкнутый цикл в структуре пространства матри цы состояния линейной ДДС с помощью следующего определения.

Определение 1.13 (О1.13). Пусть множество ~ мощности x ~ [ ~ ] = N = 2 n 1 состояний линейной ДДС (1.186), (1.187), не вклю x чающее в себя нулевое неподвижное состояние, тогда подмножество множества ~, содержащее T состояний, на котором выполняется x соотношение x( k ) = x( k + T ), (1.208) называется замкнутым циклом длинной T, составленным из векторов состояния {x( k );

x( k + 1) = Ax( k );

x( k + 2) = Ax( k + 1) = A x( k ),, x( k + T 1) = AT 1 x( k )}. (1.209) Рассмотрим факторы, определяющие длину T замкнутых циклов на множестве состояний ЛДДС при отсутствии экзогенной последова тельности ( u ( k ) = 0 ) на ее входе. С этой целью соотношение (1.208) за пишем в форме (1.187) x( k ) = AT x( k ). (1.210) Сформулируем следующее утверждение.

Утверждение 1.40 (У1.40). При x( k ) 0 соотношение (1.210) вы полняется в случаях, когда:

– матрица A принадлежит показателю T ;

– x( k ) является собственным вектором матрицы AT.

Доказательство справедливости первой части утверждения стро ится на определении показателя µ, которому принадлежит матрица A, в соответствии с которым выполняется матричное равенство Aµ = I, (1.211) подстановка µ = T делает справедливым (1.210). Доказательство спра ведливости второй части утверждения строится на определении собст венного вектора с учетом специфики простого поля Галуа GF ( p ) при p = 2.

Нетрудно видеть, что длина T замкнутых циклов удовлетворяет неравенствам 1 T n 1. (1.212) Очевидно, что в структуре пространства ( n n ) -матрицы A состояния ЛДДС (1.186), (1.187) имеется цикл длины T = 1, когда x( k ) является собственным вектором матрицы A. Иначе говоря, ненулевое непод вижное состояние образует цикл длительностью T = 1. Максимальная длительность T = 2 n 1 имеет место, когда ( n n ) -матрица A и ее ха рактеристический полином D( ) = det ( I + A) принадлежат показате лю µ = 2 n 1.

Наложим на неравенства (1.212), определяющие возможные по длине T циклы на множестве ненулевых состояний ~ мощностиx ~ [x ~ ] = N = 2 n 1, неравенства, оценивающие возможные показатели µ, которым могут принадлежать ( n n ) -матрица состояния ЛДДС и ее характеристический полином D( ) n µ 2n 1. (1.213) В результате этого наложения, а также с использованием положений У1.39 и У1.40 можно предложить следующий алгоритм анализа струк туры замкнутых циклов линейных ДДС (1.186), (1.187), которому при дадим номер 1.10.

Алгоритм 1.10 (А1.10) 6. Построить векторно-матричное представление линейной двоич ной динамической системы в форме (1.183), (1.184).

7. Перейти от представления ЛДДС (1.183), (1.184) к ее представ лению в форме (1.186), (1.187), положив в (1.183), (1.184) u( k ) = 0.

8. Вычислить характеристический полином D( ) матрицы A со стояния ЛДДС в силу соотношения D( ) = det ( I + A).

9. Определить показатель µ которому принадлежит характеристи ческий полином D( ) и матрица A состояния ЛДДС с исполь зованием таблиц полиномов, принадлежащих конкретному µ или возведением матрицы A в степень над полем Галуа GF ( 2 ) до момента выполнения равенства A µ = I.

10. Проанализировать полученное значение µ : если µ = 2 n 1, то осуществить переход к п.11 алгоритма, в противном случае – к п.6 алгоритма.

11. Найти корни характеристического полинома D( ), после чего его записать в форме ( ) D( ) = g ( ) n j + 1, (1.214) j = где g ( ) – неприводимый модулярный многочлен, n1 = 1 n2 n j n j +1 n (1.215) deg D( ) = n = deg g ( ) + n j (1.216) j = 12. Вычислить величину r, определяющую сумму размерностей ядер матриц ( I + A n j ) в силу соотношений 2 n 1 = nµ µ + r, (1.217) где nµ – число циклов длины T = µ.

( ) 13. Вычислить размерности r j ядер Ker I + A n j матриц I + A n j, определяющих число собственных векторов матриц A n j, а, сле довательно, длину T j = r j соответствующих им замкнутых цик лов.

14. Вычислить собственные векторы f j матриц A n j.

15. Определить состав и очередность изменения состояний в замк нутых циклах длиной T j = r j, порожденных собственными век торами f j матриц A n j, используя для этого представление циклов в форме (1.209).

16. Определить состав и очередность изменения состояний в замк нутых циклах длиной Tµ = µ, порожденных фактом принадлеж ности матрицы A состояния ЛДДС показателю µ, используя представление циклов в форме (1.209), в котором за исходное состояние x( k ) цикла взять любое состояние множества ~, не x принадлежащее циклам, сформированным в п.10.

17. Сформировать структуру замкнутых циклов и неподвижных со стояний линейной ДДС (1.186), (1.187) (при u ( k ) 0 ) путем объ единения циклов в п.п. 10 и 11, дополнив их нулевым непод вижным состоянием.

Пример 1.10 (Пр1.10) (Продолжение) 1. Выполним п.п.1–3 А1.10, в результате чего ЛДДС будет иметь матрицу A состояния и характеристический полином D( ) = det ( I + A) 0 1 A = 0 0 1 ;

D( ) = 3 + 2 + + 1 ;

n = 1 1 4. Путем возведения матрицы A в степень получим 0 0 1 0 0 1 0 0 1 1 0 A 2 = A A = 1 1 1 ;

A4 = A 2 A 2 = 1 1 1 1 1 1 = 0 1 0, 1 0 0 1 0 0 1 0 0 0 0 что показатель µ, которому принадлежит матрица A, равен че тырем ( µ = 4 ) 5. Анализ значения µ обнаруживает, что µ = 4 2n 1 = 23 1 = 8 1 = 7 ;

в результате чего необходимо перейти к п.6 А1.10.

6. Выполнение п.6 алгоритма дает 1 = 2 = 3 = 1 и D( ) предста вим в форме ( )( D( ) = 3 + 2 + + 1 = 2 + 1 + 1), где g ( ) = 1 ;

n1 = 1 ;

n2 = 2.

7. Выполнение п.7 алгоритма дает 2 n 1 = 7 = 1 4 + 3 так, что в структуре пространства матрицы A состояния ЛДДС имеется один замкнутый цикл длиной T = µ = 4.

8. Вычисление размерности r j ядер матриц 1 1 0 1 0 ( I + A ) = ( I + A) = 0 ( )( ) n 1 1 и I + A n 2 = I + A 2 = 1 0 1 1 0 1 0 дает r1 = 1 и r2 = 2.

9. Вычисление собственных векторов матриц A n j приводит к ре зультату { } { f 1 }= arg An1 f 1 = f 1 = arg{ A = }= 0 1 0 = arg 0 0 1 = = 1 1 1 10. Определение состава циклов, порожденных собственными век торами матриц A n j дает два цикла, представляющих собой на бор векторов 1 1 { f 1 } = 1, { f 2 }= 0, 1 1 11. Определение состава и очередность смены состояния ЛДДС в замкнутом цикле длины Tµ = µ = 4, порожденным фактом при надлежности матрицы A показателю µ = 4, если за x( k ) при нять x( k ) = [0 0 1], не принадлежащий { f 1 } { f 2 }, и восполь T зоваться (1.208), дает замкнутый цикл 0 0 1 1 0, 1, 1, 0, 1 1 0 0 12. Полная структура замкнутых циклов и неподвижных состояний при u ( k ) 0 принимает вид (рисунок 1.23).

Рисунок 1.23. Структура замкнутых циклов и неподвижных состояний ЛДДС Рассмотрим теперь структуру замкнутых циклов линейной ДДС при u ( k ) = 1. Описание ЛДДС для этого случая задается представле ниями (1.183), (1.184), в которых следует положить u ( k ) = 1 так, что получим:

в рекуррентной форме x( k + 1) = Ax( k ) + B ;

x( 0 ) (1.218) и в суммарной форме x( k + 1) = A k x( 0 ) + A k 1 B + A k 2 B + + AB + B ;

x( 0 ). (1.219) Следует заметить, что введенное с помощью О1.13 определение замкнутого цикла длинной T сохраняется, однако структура этих цик лов не только зависит от показателя µ, которому принадлежит матри ца A, структуры собственных векторов { f } степенных матричных функций f ( A) = A q от ( n n ) -матрицы A состояния ЛДДС, но и от матрицы B. Последняя может принадлежать пространству столбцов матрицы A, то есть ее образу B Jm A, (1.220) тогда пара матриц ( A, B ) оказывается не полностью управляемой, про стейший случай такой ситуации является случай, когда матрица B яв ляется собственным вектором матрицы A.

В этой связи сформулируем утверждение.

Утверждение 1.41 (У1.41). Если матрица B векторно матричного описания ЛДДС является собственным вектором матри цы A, то ЛДДС с такой парой матриц ( A, B ) не является полностью управляемой, при этом размерность подпространства управляемости равна единице.

Доказательство. Тот факт, что матрица B суть собственный век тор матрицы A состояния ЛДДС над простым полем Галуа GF ( 2 ), по зволяет записать AB = B. (1.221) Составим матрицу управляемости пары ( A, B ) [ ] W у ( A, B ) = B A B A 2 B A n1 B. (1.222) Для элементов W у ( A, B ) можно записать ( ) A B = B ;


A 2 B = A B = B,, A n1 B = A A n2 B = = B.

Подстановка полученных матричных равенств в (1.222) дает для мат рицы управляемости rank W у ( A, B ) = rank [B B B B ] = rank B = 1 n.

Следует заметить, что рекуррентная форма (1.218) представления ЛДДС при u ( k ) = 1 содержит конструктивный алгоритм формирования структуры замкнутых циклов путем простого суммирования состояния перехода с матрицей B, так что в цикле происходит аддитивный сдвиг на векторный компонент B. Однако это впечатление обманчиво.

Структура замкнутых циклов может измениться так, что в них могут полностью исчезнуть неподвижные состояния. Напомним, что выше было доказано, что при u ( k ) = 1 нулевое состояние перестает быть не подвижным, а ненулевое неподвижное состояние существует, когда матрица ( I + A) обратима или когда матрица B принадлежит ее обра зу. Но возможны ситуации, когда ни одно из этих условий не выполня ется. Проиллюстрируем сказанное на примере.

Пример 1.11 (Пр1.11) Рассмотрим ЛДДС с матрицей A состояния из Пр1.9 в сочетании с двумя версиями матрицы входа B :

1 B1 = 1, B2 = 0.

1 Для поиска ненулевого неподвижного состояния x( k ) : x( k + 1) = x( k ) в силу (1.198) сконструируем матрицу 0 1 0 1 0 0 1 1 ( A + I ) = 0 0 1 + 0 1 0 = 0 1 1.

1 1 1 0 0 1 1 1 Ранг матрицы ( A + I ) меньше n = 3, действительно 1 1 rank ( A + I ) = rank 0 1 1 = 2.

1 1 Матрица ( A + I ) является необратимой, а потому использование соотношения (1.197) для поиска ненулевого неподвижного состояния оказывается некорректным. Однако проверим принадлежат ли матри цы B1 и B2 в силу (1.198) ( A + I ) x( k ) = B образу ( A + I ). Для первой версии матрицы B = B1 имеет место соот ношение 1 1 0 0 1 1 x( k ) = 1, 1 1 0 откуда следует B1 Jm ( A + I ), при этом неподвижных состояний два x( k ) = [0 1 0 ] и x( k ) = [1 0 1].

T T Для второй версии имеем 1 1 0 0 1 1 x( k ) = 0, 1 1 0 откуда следует B2 Jm ( A + I ), а следовательно ЛДДС с парой матриц ( A,B2 ) при u ( k ) = 1 не имеет ненулевых неподвижных состояний, как следствие следует ожидать объединения «коротких» замкнутых цик лов. На рисунке 1.24 приведена структура циклов ЛДДС с парой мат риц ( A,B1 ), построенная в силу (1.217).

( A,B1 ) Рисунок 1.24. Структура циклов ЛДДС с парой матриц ( A,B1 ) не является полностью управ Следует заметить, что пара ляемой, так как матрица B1 = [1 1 1] является собственным векто T ром матрицы A. В результате ранг W у ( A, B1 ) равен единице, а управ ляемое подпространство натянуто на вектор x = B1. Если ЛДДС нахо дится в нулевом начальном состоянии x( 0 ) = [0 0 0 ], то никакими T u ( k ) нельзя ЛДДС вывести из подпространства, натянутого на состоя ния x = [0 0 0 ] и x = [1 1 1].

T T На рисунке 1.25 приведена структура циклов ЛДДС с парой матриц ( A,B2 ) – полностью управляемой, так как 0 0 rank W у ( A, B2 ) = rank 0 1 1 = 3 = n 1 1 ( A,B2 ) Рисунок 1.25. Структура циклов ЛДДС с парой матриц Неподвижные состояния в случае u ( k ) = 1 в ЛДДС с парой матриц ( A,B2 ) «исчезли», структура пространства состояний распалась на два замкнутых цикла длиной T = µ = 4. В силу полной управляемости пары ( A,B2 ) существует последовательность u ( k ), которая позволяет обой ти все состояния ЛДДС. Примером такой последовательности является u ( k ) = 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1...

В заключение следует остановиться на проблеме вычисления со стояния, из которого ЛДДС переходит в нулевое состояние. Нетрудно видеть, если в левой части (1.218) положить для состояния перехода x( k + 1) 0, то x( k ), из которого происходит под действием u ( k ) пе реход в нулевое состояние, определится выражением x( k ) = A 1 B. (1.223) Оценка состояния (1.223) особенно важна в задачах помехозащитного декодирования.

Следует также заметить, что структура замкнутых циклов претер певает минимальную модификацию для случая, когда матрица A со стояния ЛДДС принадлежит показателю µ = 2 n 1. В этом случае ну левое состояние перестает быть неподвижным, существует единствен ное ненулевое неподвижное состояние x( k ) = ( A + I ) B и единствен ный замкнутый цикл длиной T = 2 n 1. Пара матриц ( A, B ) при любой реализации матрицы B является управляемой так как матрица A с не приводимым характеристическим полиномом D( ) = det ( I + A) не имеет над GF ( 2 ) собственных векторов.

В заключение приведем в форме таблицы 1.3 результаты исследо вания всех 28 возможных вариантов реализаций пар ( A, B ) матриц, за дающих соответствующие ЛДДС при размерности dim x вектора x их состояния равной трем, что является широко распространенным случа ем конструирования ДДС. Для компактности записи в таблицах ис пользованы представления матриц, циклов, последовательностей в ви де их десятичных эквивалентов, причем величина периодичности представлена скобочной записью с указанием длительности периода в виде нижнего индекса у правой скобки.

Таблица 1. Матрица B T Матрица Показатель Характеристика µ AT 1 2 3 4 5 6 [2, 1, 4] 3 3 2 3 2 2 1 Ранг матрицы [2, 1, 6] 3 3 3 3 2 3 3 управляемости [2, 1, 5] 3 3 3 3 3 3 3 [2, 1, 7] 3 2 3 3 2 3 1 [2, 1, 4] (175)8 (175)8 – (175)8 – – – Управляющая по- [2, 1, 6] (207)8 (207)8 (207)8 (207)8 – (207)8 (207)8 следовательность [2, 1, 5] (243)8 (243)8 (243)8 (243)8 (243)8 (243)8 (243)8 [2, 1, 7] (221)8 – (221)8 (221)8 – (221)8 – [2, 1, 4] (1, 2, 4)3, (3, 6, 5)3 [2, 1, 6] (1, 2, 5, 3, 7, 6, 4)7 Замкнутые циклы [2, 1, 5] (1, 3, 7, 6, 5, 2, 4)7 [2, 1, 7] (2, 5)2, (1, 3, 6, 4)4 [2, 1, 4] (0), (7) Неподвижные [2, 1, 6] (0) состояния [2, 1, 5] (0) [2, 1, 7] (0), (7) Таблица 1.3 (продолжение) Матрица B T Матрица Показатель Характеристика µ AT 1 2 3 4 5 6 (0,1,3,7, (0,2,6,7, (0,3,5)3, (0,4,5,7, (0,5,6)3, (0,6,3)3, (1,5,4,6, [2, 1, 4] 6,4)6, 5,0)6, (2,7,4)3, 3,2)6, (1,7,2)3, (1,4,7)3, 2,3)6, (2,5)2 (3,4)2 (1)1, (6)1 (1,6)2 (3)1, (4)1 (2)1, (5)1 (0,7) (0,1,3,6, (0,2,7,4, (0,3,4,2, (0,2,7,4, (0,5,6,1, (0,6,2,3, (0,7,1,5, Сепаратные управ- [2, 1, 6] 5,4,2)7, 3,5,1)7, 6,7,5)7, 3,5,0)7, 7,3,2)7, 1,4,7)7, 4,6,3)7, ляемые состояния (7)1 (6)1 (1)1 (6)1 (4)1 (5)1 (2) и циклы (0,1,2,5, (0,2,6,7, (0,3,4,2, (0,4,5,6, (0,5,7,3, (0,6,3,1, (0,7,1,4, (при u ( k ) = 1( k ) ) [2, 1, 5] 3,6,4)7, 4,3,5)7, 7,5,1)7, 1,7,2)7, 2,1,6)7, 5,4,7)7, 6,2,3)7, (7)1 (1)1 (6)1 (3)1 (4)1 (2)1 (5) (0,1,2,4)4, (1)1, (6)1, (0,3,5,1)4, (0,4,5,6)4, (3)1, (4)1, (0,6,2,3)4, (2)1, (5)1, [2, 1, 7] (3,7,6,5)4 (0,2,7,5)4 (2,6,7,4)4 (1,7,3,2)4 (1,6)2, (1,5,4,7)4 (0,7)2, (0,5,7,2)4 (1,4,6,3) Примечания.

1. Матрица AT представлена построчно: в таблице указаны десятичные эквиваленты строк матрицы.

2. Матрица B T представлена десятичным эквивалентом ее столбца.

3. Запись вида ( •) означает цикл длины ( ) с последовательностью кодов состояния ( •), каждый из которых задан в десятичном эквиваленте.

1.8. Линейные двоичные динамических системы в задачах дивидендного помехозащитного кодирования Дивидендное представление процессов помехозащитного кодопре образования в фазе кодирования и декодирования использует вектор но-матричное описание, параметризованное дискретным временем k этих процессов в форме линейных двоичных динамических систем, опирающиеся на модели «вход-состояние» (ВС) вида (1.23), (1.25) x ( k + 1) = A x ( k ) + B u ( k ), x ( 0 ) 0, (1.224) k 1 k x ( k ) = A k x ( 0 ) + A k 1i B u ( i ) = A k 1i B u ( i ). (1.225) x ( 0 )0 i = i = Форма модели ВС (1.224), как указано в параграфе 1.2, именуется ре куррентной формой, форма (1.225) – суммарной. В (1.224), (1.225) x ( k ) – вектор состояния ЛДДС, осуществляющей помехозащитное ко допреобразование;

u ( k ) – входная кодовая последовательность;

dim x = m, dim u = 1, dim A = ( m m ), dim B = ( m 1). В зависимости от задачи помехозащитного кодопреобразования u ( k ) принимает смысл помехонезащищенного информационного кода u ( k ) = a ( k ) при фор мировании помехозащищенного кода y ( k ) и смысл принятого из кана ла связи искаженного кода f ( k ) = y ( k ) + ( k ) так, что u ( k ) = f ( k ) в задаче декодирования. Характерной особенностью модельных пред ставлений (1.224) и (1.225) является то, что матрица Aку состояния ко дирующего устройства и матрица Aдку состояния декодирующего уст ройства совпадают так, что выполняется равенство Aку = Aдку = A. (1.226) Матрица A состояния КУ и ДКУ задается в одном базисе, при этом чаще всего в сопровождающей характеристический полином (ХП) форме, причем ХП D( ) = det ( I + A) совпадает с образующим ПЗК модулярным многочленом g ( x ) так, что выполняется соотношение D ( ) = g ( x ) x = (1.227) Матрицы входа для устройств кодирования и декодирования чаще все го не совпадают так что для КУ и ДКУ модель (1.224) соответственно получает представление x ( k + 1) = A x ( k ) + Bку u ( k );

x ( k + 1) = A x ( k ) + Bдку u ( k ). (1.228) Если при формировании ПЗК предполагается возможность перехо да от их матричного задания, не параметризованного дискретным вре менем k, с помощью образующей матрицы G и проверочной матрицы H, то следует иметь в виду следующее. Необходимое условие реали зуемости матричного представления ПЗК (1.144), (1.146) дивидендным способом, осуществляемым средствами ЛДДС (1.228), является одно значное соответствие строк проверочной матрицы H ПЗК с точностью до процедуры транспонирования с матрицей входа Bдку устройства де ~ кодирования и строк матрицы G при представлении образующей мат рицы ПЗК в форме (1.158) с матрицей входа Bку (1.228) устройства ко дирования.

Высказанные соображения подтвердим следующими утвержде ниями.

Утверждение 1.42 (У1.42). Матрица Bку ЛДДС дивидендного кодирующего устройства с точностью до операции транспонирова ~ ния совпадает с последней строкой ( k -ой) строкой G k образующей матрицы G так, что выполняется соотношение Bку = G k = { g ( x ) + x m }, ~ T (1.229) где { ( •) } – код модулярного многочлена ( •).

Доказательство. Рассмотрим процесс кодирования для случая u ( k ) = a ( x ) = 1, то есть для случая k -элементной входной последова тельности u ( k ) = [ u ( 0 ) = 0, u ( 1) = 0,, u ( k 2 ) = 0, u ( k 1) = 1 ]. (1.230) В течение первых ( k 1) -тактов ЛДДС КУ будет находится в нулевом неподвижном состоянии. При приеме элемента u ( k 1) = 1 ЛДДС КУ (1.228) перейдет в состояние x ( k ) = Bку u ( k 1) u ( k 1)=1 = Bку. (1.231) Состояние (1.231) определяет код остатка, выводимый из КУ, для ~ a( x ) = 1, задаваемый последней строкой матрицы G кодов остатков так, что выполняется цепочка равенств x T ( k ) = Bку = G k = { g ( x ) + x m }.

~ T (1.232) Утверждение 1.43 (У1.43). Матрица Bдку входа ЛДДС (1.228) ди видендного декодирующего устройства с точностью до процедуры транспонирования совпадает с последней строкой проверочной мат рицы H ПЗК так, что выполняется равенство Bдку = H n.

T (1.233) Доказательство. В силу идентичности результатов процедур фор мирования синдрома E при декодировании в форме (1.146), (1.151) с целью анализа процессов в ЛДДС (1.228) при декодировании рассмот рим последний при входной последовательности u ( k ) = ( k ). Как и выше, ограничимся ситуацией, когда последовательность ( k ) содер жит единицу только в младшем разряде u ( k ) = ( k ) = [ u ( 0 ) = 0, u ( 1) = 0,, u ( k 2 ) = 0, u ( k 1) = 1 ]. (1.234) При входной последовательности вида (1.234) ЛДДС (1.228) уст ройства декодирования в течение первых ( n 1) -тактов, характери зующихся u ( k ) = 0 остается в нулевом неподвижном состоянии, а на последнем n -м такте перейдет в состояние, совпадающее с матрицей Bдку. Однако в силу правил декодирования это состояние представляет собой синдром ошибки в младшем разряде, который в силу правил формирования проверочной матрицы H ПЗК является ее последней строкой, что приводит к цепочке равенств E = x T ( n ) = Bдку = H n.

T (1.235) Поставим задачу: матрица A ЛДДС устройств кодирования и декоди рования (1.228) фиксирована, матрица входа ЛДДС кодирующего уст ройства фиксирована в форме (1.232), модифицируема ли матрица вхо да ЛДДС устройства декодирования при сохранении матричного ха рактеристического свойства ПЗК (1.146) GH = O ?

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

Определение 1.14 (О1.14). Матрицей циклического сдвига на один шаг «вниз» строк произвольной ( n m ) -матрицы H называется ( n n ) -матрица Pc вида O I1 Pc = 1 ( n1). (1.236) I (n1) (n1) O( n1) Определение 1.15 (О1.15). Матрицей циклического сдвига на один шаг «вверх» произвольной ( n m ) -матрицы H называется ( n n ) матрица Pc1 вида O I (n1) (n1) Pc1 = ( n1) 1. (1.237) O1 ( n1) I1 Из (1.236) и (1.237) видно, что матрицы циклического сдвига «вниз» и «вверх» строк произвольной ( n m ) -матрицы H связаны соотноше ниями Pc1 = PcT, Pc PcT = PcT Pc = I. (1.238) Определение 1.16 (О1.16). Матрицей циклического сдвига на шагов «вниз» строк произвольной ( n m ) -матрицы H называется ( n n ) -матрица Pc вида O I Pc = ( n ). (1.239) I (n ) (n ) O( nv ) v Определение 1.17 (О1.17). Матрицей H ( ) размерности ( n m ), полученной из ( n m ) -матрицы H путем сдвига на шагов ее строк «вниз», называется матрица, вычисленная в силу матричного соотно шения H ( ) = Pc H. (1.240) Утверждение 1.44 (У1.44). Характеристическое свойство (1.147) матриц ( G, H ) помехозащищенного кода сохраняется для матриц ( G, H ( )) так, что GH ( ) = GPc H. (1.241) Доказательство утверждения строится на использовании матрицы G, записанной в каноническом виде (1.158) [ ] ~ G= I G, kk и матрицы H, записанной в форме [ ]T H = A n1 Bдку A n2 Bдку ABдку Bдку. (1.242) При этом используются свойства ( m m ) -матрицы A принадлежности показателю n = 2 m 1, в силу чего выполняется равенство An = I, (1.243) а также справедливости теоремы Гамильтона-Кэли позволяющей запи сать D( ) = A = D( A) = O. (1.244) Если записать (1.241) в транспонированной форме H T ( Pc ) G T, T (1.245) подставить в нее матрицу H в форме (1.242), Pc в форме (1.239) и матрицу G в форме (1.158), учесть (1.243) и (1.244), тогда получим матричное соотношение { } H T ( Pc ) G T = row A i D( A)Bдку ;

i = 1,k, i = 0,1,2,,m = O. (1.246) T Пример 1.12 (Пр1.12).

Проиллюстрируем положения У1.44 на примере циклического ПЗК с образующим ММ g ( x ) = x 3 + x + 1, который характеризуется матри цами G и H 1 0 0 0 1 0 1 1 1 1 0 1 0 G = 0 1 0 0 1 1 1 ;

H T = 0 1 1 1 0 1 0 (1.247) 0 0 1 0 1 1 0 1 1 0 1 0 0 0 0 0 1 0 1 Матрица Pc циклического сдвига «вниз» строк матрицы H на один шаг (1.236) имеет вид O Pc = 1 7. (1.248) I7 7 O7 Тогда для матриц (1.245) для = 0, = 3, = 6 получим 1 0 0 0 1 0 0 0 1 [ ]0 0 0 1 ;

H T G T = A6 Bдку A 5 Bдку A 4 Bдку A 3 Bдку A 2 Bдку ABдку Bдку 1 1 1 0 1 1 1 1 0 (1.249) H T ( Pc3 )G T = 1 0 0 0 1 0 0 0 1 [ ]0 0 0 1 ;

= A 2 Bдку ABдку Bдку A6 Bдку A 5 Bдку A 4 Bдку A 3 Bдку 1 1 1 0 1 1 1 1 0 (1.250) ( P )G = T 6 T H 1 0 0 c 0 1 0 0 0 1 [ ]0 0 0 1.

= A 5 Bдку A 4 Bдку A 3 Bдку A 2 Bдку ABдку Bдку A6 Bдку 1 1 1 0 1 1 1 1 0 (1.251) Раскрытие произведений матриц позволяет для (1.248) – (1.250) за писать [ H T G T = (A6 + A 2 + I ) Bдку (A 5 + A 2 + A + I ) Bдку ] (A + A 2 + A) Bдку (A 3 + A + I ) Bдку (1.252) [ H T ( Pc3 )G T = (A 5 + A 3 + A 2 ) Bдку (A 5 + A 4 + A 3 + A) Bдку ] (A + A 4 + I ) Bдку (A6 + A 4 + A 3 ) Bдку (1.253) [ H T ( Pc6 )G T = (A6 + A 5 + A) Bдку (A6 + A 4 + A + I ) Bдку ] (A + A + I ) Bдку (A6 + A 2 + I ) Bдку (1.254) Если в (1.252) – (1.254) учесть (1.243) и (1.244), записываемые для рассматриваемого примера в форме A7 = I, D( A) = A 3 + A + I = O, (1.255) то (1.252) – (1.254) примут вид [ H T G T = A 1 D( A) Bдку A 2 D( A) Bдку AD( A) Bдку D( A) Bдку ] = O (1.256) [ H T ( Pc3 )G T = A 2 D( A) Bдку AD( A) Bдку ] A 3 D( A) Bдку A 3 D( A) Bдку = O (1.257) [ H T ( Pc6 )G T = A 2 D( A) Bдку A 3 D( A) Bдку ] D( A) Bдку A 1 D( A) Bдку = O (1.258) Общее представление результатов (1.256) – (1.258) имеет вид (1.246).

Утверждение (У1.44) и Пр1.11 по существу содержат доказатель ство следующего утверждения.

Утверждение 1.45 (У1.45). В качестве матрицы Bдку входа уст ройства дивидендного декодирования, реализованного в форме линей ной ДДС (1.228), может быть принята любая строка проверочной матрицы H помехозащищенного кода в транспонированном виде так, что Bдку = H iT, i = n,1, (1.259) при этом образующая и проверочная матрицы ПЗК, сформированного средствами ЛДДС (1.228) с матрицей входа (1.259) устройства деко дирования сохраняют свое характеристическое свойство (1.147).

Таким образом пользователь аппаратуры дивидендного помехоза щитного кодирования – декодирования без изменения ее кодирующей части может модифицировать декодирующую часть путем изменения матрицы Bдку входа декодирующего устройства. Количество вариантов модификации матрицы Bдку составляет N в = n, где n – полное число разрядов помехозащищенного ( n, k ) -кода. При этом опасность получе ния неуправляемой пары матриц ( A,Bдку ) на указанном наборе отсут ствует, так как матрица Bдку при всех ее версиях не является собствен ным вектором матрицы A. Последнее объясняется тем, что матрица A состояния ЛДДС кодирующих и декодирующих устройств (1.228) име ет своим характеристическим полиномом неприводимый модулярный многочлен, который не имеет корней в простом поле Галуа GF ( 2 ), что гарантирует и отсутствие собственных векторов.

Полученные в параграфе результаты позволяют сформировать ал горитм синтеза линейных ДДС дивидендного помехозащитного коди рования и декодирования.

Алгоритм 1.11 (А1.11) синтеза ЛДДС дивидендного помехозащитного кодирования и декодирования 18. По заданному информационному массиву Q мощности [ Q ] = N и определить размерность k помехозащищенного кода в силу со отношения k = arg {2 k N и = [ Q ] }.

19. По заданной корректирующей способности помехозащищенного ( n, k )-кода определить степень m = n k его образующего мо дулярного многочлена g ( x ) в силу соотношения s m = arg N c = 2 1 N ош = C(ik + m ), m i = где N c – число синдромов, N ош – число ошибок, s – кратность исправляемой ошибки. Выбрать или сформировать реализацию образующего ММ g ( x ) степени m в классе неприводимых, га рантирующих минимальное кодовое расстояние d min на исполь зуемых кодовых комбинациях ПЗК d min 2 s + 1.

D-образ ММ g ( x ) в форме 20. Вычислить g ( d ) =D{ g ( x )} = g ( x 1 ) 1, ~ x =d ~ ( x 1 ) : g ( x ) = x m g ( x 1 ).

~ где g 21. Сконструировать передаточную функцию устройства деления модулярных многочленов в форме (d)=.

g( d ) 22. Пользуясь правилом Мейсона некасающихся контуров постро ить структурную реализацию ( d ) на элементах памяти (ЭП) с передаточной функцией ЭП ( d ) = d.

23. Произвести отметку входов и выходов ЭП переменными xi ( k + 1) на входе и xi ( k ) на выходе и сформировать векторно матричное описание автономной версии УДММ x( k + 1) = Ax( k ).

24. Сформировать матрицу входа Bку дивидендного кодирующего устройства (1.228) в силу соотношения (1.229).

25. Сформировать проверочную матрицу H ПЗК и матрицу Bдку входа дивидендного декодирующего устройства (1.228) в силу соотношения (1.259).

26. Проверить правильность функционирования устройств кодиро вания и декодирования (1.228) сформированными парами мат риц (A,Bку ) и (A,Bдку ).

27. Построить техническую реализацию устройств дивидендного кодирования и декодирования:

a. в схемотехнической форме на базе структурных представле ний;

b. в программной форме на базе рекуррентных процедур (1.228).



Pages:     | 1 || 3 | 4 |   ...   | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.