Обобщенные линейные автоматы без потери информации

Разбить на страницы

Показывать лекцию целиком

Рассмотрим автоматы, у которых входы и выходы являются многоканальными, т. е. их входные и выходные алфавиты структурированы. Каждый из таких автоматов может не быть автоматом БПИ в классическом смысле, но вместе с тем он может допускать возможность восстановления некоторого подмножества компонент входного символа при наблюдении реакций на подмножестве его выходных каналов. Такого рода автоматы были исследованы в работах [48], [49] и названы обобщенными автоматами БПИ (ОБПИ).

В этой лекции будут исследованы обобщенные линейные автоматы БПИ. В частности, в терминах характеристических матриц ЛА будет получен критерий принадлежности автомата упомянутому классу.

Введем некоторые понятия, которые понадобятся далее.

Выходной канал $$y_i$$ ЛА $$A$$ назовем избыточным, если в любой момент времени $$t$$ значение сигнала $$y_i(t) $$ на нем есть линейная комбинация сигналов на остальных выходных каналах этого же автомата.

Линейный автомат назовем неизбыточным по выходам, если в нем отсутствуют избыточные выходные каналы.

Из сказанного выше следует, что множество $$\tilde Y=\{y_{j1}, \dots, y_{jk}\}$$ неизбыточных каналов представляет собой такое минимальное по мощности подмножество множества $$Y=\{y_1, \dots, y_m\}$$ всех выходных каналов ЛА, значений сигналов на которых достаточно для определения значений сигналов на каналах из множества $$\frac {Y}{\tilde Y}$$.

Теорема 16.1. Для того чтобы ЛА $$\tilde A$$ был неизбыточным по выходам, необходимо и достаточно, чтобы число его выходных каналов было равно рангу матрицы $$[C, D] $$ системы (1.2) уравнений выходов этого автомата.

Доказательство. Предположим, что ранг матрицы системы линейных уравнений (10.2) относительно неизвестных $$s_1(t), \dots, s_n(t), u_1(t), \dots, u_l(t) $$ равен $$\nu$$, где $$\nu < m$$. Известно [19], что это условие является необходимым и достаточным для того, чтобы $$m- \nu$$ уравнений упомянутой системы представляли собой линейные комбинации остальных уравнений. Применительно к линейному автомату этот факт означает, что $$m- \nu$$ его выходных каналов являются избыточными. Отсюда и вытекает справедливость теоремы.

Опишем общий метод, позволяющий определить избыточные выходные каналы в ЛА. Этот метод основан на применении известного метода Гаусса [33] для решения систем линейных алгебраических уравнений. Пусть Q - матрица системы (1.2). Методом Гаусса приведем матрицу $$Q$$ к ступенчатой форме. В процессе такого приведения некоторые строки могут вырождаться в нулевые, что свидетельствует о линейной зависимости соответствующих уравнений системы (10.2) от других уравнений. Очевидно, что выходные каналы ЛА, которым соответствуют нулевые строки в ступенчатой матрице, и являются избыточными.

Проиллюстрируем изложенное на примере ЛА над полем $$GF(2) $$ с характеристическими матрицами

$$C= \left [ \begin {matrix} 100\\ 010\\ 011\\ 001 \end {matrix} \right ], D= \left [ \begin {matrix} 010\\ 100\\ 000\\ 100 \end {matrix} \right ]$$

Преобразование методом Гаусса матрицы $$[C,D]$$ в данном случае осуществляется за два шага, и полученные при этом матрицы имеют вид

$$\left [ \begin {matrix} 100010\\ 010!00\\ 001100\\ 001100 \end {matrix} \right ] \begin {matrix} y_1\\ y_2\\ y_2\oplus y_3\\ y_4 \end {matrix} \left [ \begin {matrix} 100010\\ 010100\\ 001100\\ 000000 \end {matrix} \right ] \begin {matrix} y_1\\ y_2\\ y_2 \oplus y_3\\ y_2 \oplus y_3 \oplus y_4 \end {matrix} $$

Равенство нулю четвертой строки последней матрицы означает, что $$y_2 \oplus y_3 \oplus y_4=[0]$$. Последнее равенство равносильно трем следующим: $$y_2=y_3 \oplus y_4, y_3=y_2 \oplus y_4, y_4=y_2 \oplus y_3$$. Эти равенства говорят о том, что любой, но только один канал из множества $$\{y_2, y_3, y_4\}$$ в действительности можно считать избыточным. В самом деле, значение сигнала на одном из упомянутых каналов есть линейная комбинация сигналов на двух других каналах из этой тройки.

Теорема 16.2. Для того чтобы ЛА БПИ являлся неизбыточным по выходам, необходимо и достаточно, чтобы число его выходных каналов $$m$$ было не меньше числа $$l$$ его входных каналов.

Доказательство.

Необходимость. Пусть ЛА $$A$$ есть БПИ и не имеет избыточных выходов. Покажем, что тогда $$m \ge l$$. Поскольку ЛА есть автомат БПИ, то по теореме 3.1 $$\rank D = l$$. На основании теоремы 16.1 неизбыточность ЛА по выходам равносильна условию $$\rank [C,D]=m$$. Из определения ранга матрицы следует, что $$\rank [C,D] \ge \rank D$$, т. е. $$m \ge l$$.

Достаточность. Пусть ЛА есть автомат БПИ и $$m \ge l$$. Докажем, что ЛА будет неизбыточен по выходам. Доказательство проведем от противного. Пусть $$m<l$$. Нетрудно показать, что

$$\rank [C,D] \ge \max [\rank C, \rank D]$$

Поскольку ЛА есть БПИ, то $$\rank D = l$$. С учетом неравенств $$m<l$$ и $$\rank C \le m$$, получаем

$$\max [\rank C, \rank D]=l$$

Таким образом, из (16.1) следует, что $$\rank [C,D] \ge l$$. Поскольку $$l \ne m$$, то $$\rank [C,D] \ne m$$ и по теореме 16.1 рассматриваемый ЛА является избыточным по выходам. Полученное противоречие завершает доказательство теоремы.

Введем теперь понятие обобщенного линейного автомата БПИ (ОБПИ).

Пусть $$\bar g=(g_1, g_2, \dots, g_h)'$$ - вектор-столбец, представляющий собой входной символ ЛА; $$i_1, i_2, \dots, i_{\nu}$$ - некоторые натуральные числа, где $$i_a \ne i_b$$, если $$a \ne b$$ и $$1 \le I \le h$$. Назовем проекцией вектора $$\bar g$$ по входным каналам $$i_i, \dots, i_{\nu}$$ вектор-столбец $$(g_{i_1}, \dots, g_{i_{\nu}})'$$ и обозначим ее как $$pr_{i_1, \dots, i_{\nu}} =bar g$$. Пусть $$\hat g=(\bar g(1), \bar g(2), \dots, \bar g(k))$$ - упорядоченная последовательность вектор-столбцов, которую будем называть входным словом. Тогда проекцией слова $$\hat g$$ по каналам $$i_1, \dots, i_{\nu}$$ назовем упорядоченную последовательность вектор-столбцов $$(pr_{i_1, \dots, i_{\nu}}\bar g(1), \dots, pr_{i_1, \dots, ui_{\nu}} \bar g(k))$$.

Рассмотрим следующую задачу. На ЛА $$A$$, находящийся в известном начальном состоянии $$\bar s(0)$$, подается неизвестное входное слово $$\hat a=\bar u(0), \bar u(1), \dots, \bar u(k)$$ и по выходным каналам с номерами $$j_1<j_2<\dots <j_{\mu}$$, где $$1 \le j_i \le m$$ наблюдается выходная реакция. Требуется распознать проекцию слова $$\hat a$$ по каналам с номерами $$i_1, i_2, \dots, i_{\nu}$$, где $$1 \le i_j \le l$$

Условимся далее через $$A(I,J) $$, где $$I=\{i_1, \dots, i_{\nu}\}, J=\{j_1, \dots, j_{\mu}\}$$, обозначать такой подавтомат ЛА $$A$$, у которого:

множество состояний, входной и выходной алфавиты и функция переходов те же, что у ЛА $$A$$ ;

выходной символ подавтомата в момент времени $$t$$ есть $$pr_{j_1, \dots, j_{\mu}}\bar y(t)$$, где $$\bar y(t)$$ - выходной символ ЛА $$A$$ в тот же момент времени.

Понятно, что решение сформулированной выше задачи сводится к выяснению того, существует ли для заданного ЛА $$A$$ такой подавтомат $$A(I,J) $$, для которого восстановление $$pr_{i_1, \dots, i_{\nu}}\bar u(t)$$ по наблюдаемой реакции $$pr_{j_1, \dots, j_{\mu}} \bar y(t)$$ возможно независимо от входного слова $$\bar u(t)$$ и действительного начального состояния ЛА $$A$$.

Далее такой подавтомат $$A(I,J$$ ) будем называть обобщенным без потери информации (ОБПИ).

Существование у ЛА $$A$$ подавтомата ОБПИ $$A(I,J) $$ содержательно означает, что исходный ЛА, не являясь автоматом БПИ в классическом смысле, тем не менее позволяет восстановить фрагменты его неизвестных входных слов по наблюдаемым фрагментам выходных слов и известному начальному состоянию.

Перейдем теперь к описанию процедуры, с помощью которой для заданного ЛА и заданного подмножества его выходных каналов можно установить, существует ли в ЛА такое подмножество $$I$$ его входных каналов, что подавтомат $$A(I,J) $$ является ОБПИ.

Условимся далее выходные каналы с номерами из подмножества $$J$$ называть наблюдаемыми, а каналы с номерами из подмножества $$\bar J=\{1,2, \dots, m\}\J$$ - ненаблюдаемыми.

Пусть $$\bar J=\{z_1, \dots, z_k\}$$, т. е. выходные каналы с номерами $$z_1,z_2,\dots ,z_k$$ - ненаблюдаемые. Условимся, что строки всех характеристических матриц ЛА пронумерованы числами $$1, 2, \dots$$ сверху вниз, а столбцы - числами $$1, 2, \dots$$ слева направо. Напомним, что строкам $$1, 2, \dots , h$$ матриц $$A$$ и $$B$$ и столбцам $$1, 2, \dots$$,h матриц $$A$$ и $$C$$ соответствуют компоненты $$s_1, \dots , s_n$$ вектор-состояния, строкам $$1, 2, \dots,$$ m матриц $$C$$ и столбцам $$1, 2, \dots , l$$ матриц $$B$$ и $$D$$ - компоненты $$u_1, \dots , u_l$$ входного вектора $$\bar u$$.

Перейдем теперь к описанию упомянутой выше процедуры.

В матрице $$D$$ вычеркиваются строки, соответствующие ненаблюдаемым выходам $$y_{z_1}, \dots, y_{z_k}$$. Оставшуюся часть матрицы размерности $$(m-k) \times l$$ обозначим через $$D_j$$. Находим в ней подматрицу с максимальным рангом, который обозначим через $$q$$. Пусть $$\tilde {u_1}, \dots, \tilde {u)q}$$ - переменные, соответствующие столбцам подматрицы с максимальным рангом $$q$$, которые будем называть потенциально восстанавливаемыми. Вычеркнем из $$D_j$$ столбцы, соответствующие переменным $$\tilde {u_1}, \dots, \tilde {u_q}$$, и полученную матрицу обозначим $$[D_J] $$. Если $$[DJ] = [0] $$, то перейдем к пункту 2, иначе процедура завершается - при удалении выходов $$y_{z_1}, \dots, y_{z_k}$$ не существует такого подмножества выходов $$I$$, что подавтомат $$A(I,J) $$ является ОБПИ.

В матрице C вычеркиваются строки, соответствующие ненаблюдаемым выходам $$y_{z_1}, \dots, y_{z_k}$$. Оставшуюся часть матрицы обозначим через $$C_j$$. Пусть $$\tilde {s_1}, \dots, \tilde {s_h}$$ - переменные, которым соответствуют столбцы в матрице $$C_j$$, содержащие нулевые элементы. Очевидно, что $$\tilde {s_1}, \dots, \tilde {s_h}$$ - компоненты вектор-состояния, которые необходимо знать для вычисления по известной реакции неизвестных компонент $$\tilde {u_1}, \dots, \tilde {u_q}$$ выходного вектора. Переходим далее к пункту 3 процедуры.

В матрице $$A$$ выделим строки, соответствующие компонентам $$\tilde {s_1}, \dots, \tilde {s_h}$$ вектор-состояния, и полученную матрицу обозначим через $$A_j$$ Вычеркнем из нее столбцы, соответствующие переменным $$\tilde {s_1}, \dots, \tilde {s_h}$$, в результате чего получим матрицу $$[A_J] $$. Если $$[A_J] = [0] $$, то перейдем к пункту 4, иначе процедура завершается - при выходах $$y_{z_1}, \dots, y_{z_k}$$ не существует такого подмножества выходов $$I$$, что подавтомат $$A(I,J) $$ является ОБПИ.

В матрице $$B$$ выделим строки, соответствующие компонентам $$\tilde {s_1}, \dots, \tilde {s_h}$$, и полученную матрицу обозначим через $$B_j$$. Вычеркнем из нее столбцы, соответствующие переменным $$\tilde {u_1}, \dots, \tilde {u_q}$$, в результате чего получим матрицу $$[BJ$$ ]. Если $$[BJ] = [0] $$, то подавтомат $$A(I,J) $$, где $$I=\{\tilde {u_1}, \dots, \tilde {u_q}\}, J=\{z_1, \dots, z_k\}$$ является ОБПИ, иначе в ЛА при заданном J не существует подавтомата ОБПИ. На этом процедура свою работу завершает.

Описанная процедура позволяет не только определить, существует ли такое множество $$I$$, что подавтомат $$A(I,J) $$ является ОБПИ, но и установить состав множества $$I$$. Построенный подавтомат $$A(I,J) $$ имеет в качестве входного вектор $$[\tilde {u_1}, \dots, \tilde {u_q}]'$$, в качестве выходного вектор $$[y_{j_i}, \dots, y_{j_{\mu}}]'$$, в качестве вектор-состояния $$[\tilde {s_1}, \dots, \tilde {s_h}]'$$, а его характеристическими матрицами являются матрицы $$A, B, C, D$$, из которых удалены все строки и столбцы, за исключением тех, которые соответствуют множествам переменных $$\{\tilde {u_1}, \dots, \tilde {u_q}\}, \{\tilde {y_1}, \dots, \tilde {j_{\mu}}\}, \{\tilde {s_1}, \dots, \tilde {s_h}\}$$.

Прокомментируем описанную процедуру. Условие $${D_j}=[0]$$ в пункте 1 процедуры означает, что при вычислении реакций подавтомата $$A(I,J) $$ используются только потенциально восстанавливаемые переменные $$\tilde {u_1}, \dots, \tilde {u_q}$$ и никакие другие. Условия $$[A_j]=[0]$$ и $$[B_j]=[0]$$ в пунктах 3, 4 процедуры означают, что при вычислении компонент $$\tilde {s_1}, \dots, \tilde {s_h}$$ следующего состояния подавтомата $$A(I,J) $$ по формуле (1.1) в составляющей $$A \bar s(t)$$ задействуются только эти же компоненты, а в составляющей $$B\bar u(t)$$ - только потенциально восстанавливаемые компоненты $$\tilde {u_1}, \dots, \tilde {u_q}$$ входного вектора.

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

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

Теорема 16.3. Для того чтобы у ЛА $$A$$ существовал подавтомат ОБПИ $$A(I,J) $$, где $$I$$ и $$J$$ - непустые собственные подмножества множеств входных и выходных каналов ЛА соответственно, необходимо и достаточно, чтобы матрица $$D$$ содержала подматрицу ранга $$|I|$$, а матрицы $$[D_j], [B_j], [A_j]$$ были ненулевыми.

Выше уже отмечалось, что у заданного ЛА $$A$$ в общем случае может существовать несколько различных подавтоматов ОБПИ $$A(I,J) $$. Наибольший интерес среди них представляет такой подавтомат, у которого подмножество I максимально, а подмножество $$J$$ минимально по мощности. Далее такой подавтомат $$A(I,J) $$ будем называть оптимальным ОБПИ подавтоматом ЛА $$A$$.

Содержательно оптимальный подавтомат ОБПИ $$A(I,J) $$ дает возможность восстанавливать информацию максимального объема, поступающую на вход ЛА $$A$$, при минимальных затратах, определяемых числом наблюдаемых выходных каналов.

Восстановление фрагмента неизвестного входного слова $$\bar u(0), \bar u(1), \dots$$ оптимального подавтомата $$A(I,J) $$ осуществляется путем последовательного решения систем линейных алгебраических уравнений

$$D \bar u(t)=C\bar s(t)-\bar y(t)$$

для $$t = 0, 1, \dots$$ В силу теоремы 6.1 необходимым и достаточным условием разрешимости систем является условие $$rank D = l$$. Если $$m>l$$, то $$m-l$$ уравнений этих систем являются линейными комбинациями $$l$$ остальных уравнений. Последнее означает, что для упомянутого восстановления в действительности требуется наблюдать не все $$m$$ выходных каналов, а только $$l$$ из них. По существу оставшиеся $$-l$$ каналов являются при этом избыточными.

Из этих рассуждений вытекает справедливость следующего утверждения.

Теорема 16.4. Если $$A(I,J) $$ является оптимальным ОБПИ подавтоматом ЛА A, то $$|I|=|J|$$.

Опишем теперь способ, позволяющий для заданного ЛА найти его оптимальный подавтомат ОБПИ.

Предположим, что исходный ЛА является БПИ, причем $$m>l$$. Из теоремы 16.4 следует, что в нем $$m-l$$ каналов при восстановлении неизвестного входного слова являются избыточными. Приведя методом Гаусса матрицу $$D$$ ЛА к ступенчатой форме, найдем избыточные каналы и исключим их из дальнейшего рассмотрения. Очевидно, что полученный при этом подавтомат является оптимальным ОБПИ подавтоматом.

Если исходный ЛА не является автоматом БПИ, то оптимальный ОБПИ подавтомат, если таковой существует, можно найти методом перебора начиная с подавтомата $$A(H,H) $$, где $$|H|=l $$. Перебор будем осуществлять, например, следующим образом.

Начнем с попытки удаления у ЛА одного выходного канала $$y_i, i= \overline {1,m}$$. Если удаление одного очередного канала $$y_i$$ дает ОБПИ подавтомат, то он и является искомым. Если же ни один из получаемых при этом подавтоматов не является ОБПИ, необходимо перейти к удалению из ЛА всевозможных пар выходов $$\{y_i, y_j\}$$, где $$I \ne j$$ и $$1 \le I, j \le m$$. Среди полученных на втором этапе подавтоматов может найтись ОБПИ, который и будет являться искомым оптимальным подавтоматом. Продолжим этот процесс далее аналогичным образом до тех пор, пока на очередном этапе либо не будет найден подавтомат ОБПИ, который и является искомым оптимальным ОБПИ, либо при исключении $$m-1 $$ выходов (рассматриваются все возможные сочетания из $$m-1 $$ выходов) ни один подавтомат не является ОБПИ. Последнее означает отсутствие у исходного ЛА подавтоматов ОБПИ.

При реализации описанного способа придется обращаться к описанной ранее в этом разделе процедуре отыскания по заданному множеству $$J $$ выходных каналов такого множества $$I$$ входных каналов, что подавтомат $$A(I,J) $$ является ОБПИ. В худшем случае таких обращений будет $$\sum_{i=1}^{m-1}C_m^i$$.

Проиллюстрируем описанный способ на примере ЛА над полем $$CF(2)$$, заданного следующими характеристическими матрицами:

$$A= \left [ \begin {matrix} 100\\ 000\\ 000 \end {matrix} \right ], B= \left [ \begin {matrix} 100\\ 010\\ 001 \end {matrix} \right ], C= \left [ \begin {matrix} 100\\ 010\\ 011\\ 001 \end {matrix} \right ], D= \left [ \begin {matrix} 010\\ 100\\ 000\\ 100 \end {matrix} \right ] $$

Поскольку для рассматриваемого ЛА $$l=3$$, поиск оптимального подавтомата ОБПИ начнем с анализа подавтоматов с тремя выходами. В связи с этим среди четырех выходных каналов этого ЛА необходимо исключить один.

Заметим: в начале раздела для приведенных матриц $$C$$ и $$D$$ было установлено, что в качестве избыточного выхода может быть принят как $$y_4$$, так и $$y_3$$ и $$y_2$$. Для определенности остановимся на первом варианте. Тогда удаление выхода $$y_4$$ приведет к удалению из матриц $$C$$ и $$D$$ четвертой строки.

Поскольку $$|D|=0$$, то $$\rank D < 3$$, следовательно, подавтомат с тремя выходами не является БПИ. Поэтому для поиска оптимального подавтомата ОБПИ воспользуемся перебором, организация которого была описана выше.

Положим $$i=1$$ ; тогда удаление выхода $$y_1$$ (или, что все равно, первой строки из матрицы $$D$$ в соответствии с процедурой установления существования оптимального ОБПИ $$A(I,J)$$ при заданном множестве $$J$$ ) приводит к матрице

$$D_{y_2, y_3}= \left [ \begin {matrix} 100\\ 000 \end {matrix} \right ]$$

Поскольку любые ее подматрицы размерности $$2 \times 2$$ имеют ранг, меньший 2, то условия теоремы 16.3 не выполняются и поэтому исключение выхода $$y_1$$ не приведет к выделению подавтомата ОБПИ с двумя входными (выходными) каналами.

Положим $$i=2$$ ; тогда удаление выхода $$y_2$$ приводит к матрице

$$D_{y_1, y_2}= \left [ \begin {matrix} 010\\ 000 \end {matrix} \right ]$$

По той же причине, что и в предыдущем случае, исключение выхода $$y_2$$ также не приведет к выделению подавтомата ОБПИ.

Положим $$i=3$$ ; тогда удаление выхода $$y_3$$ приводит к матрице

$$\begin {matrix} u_1u_2u_3 \end {matrix}\\ D_{y_1, y_2}= \left [ \begin {matrix} \ldots\ldots\\ \vdots01\vdots 0\\ \vdots10\vdots 0\\ \ldots \ldots \end {matrix} \right ] $$

Ее подматрица, выделенная пунктиром, имеет ранг 2, следовательно, потенциально восстанавливаемыми являются компоненты $$u_1$$ и $$u_2$$ входного вектора. Поскольку удаление упомянутой подматрицы из $$D_{y_1, y_2}$$ приводит к нулевой матрице, перейдем к пункту 2 упомянутой выше процедуры.

Удалив из матрицы $$C$$ третью строку, соответствующую ненаблюдаемому выходу $$y_3$$, получим матрицу

$$\begin {matrix} s_1s_2s_3 \end {matrix}\\ C_{y_1, y_2}= \left [ \begin {matrix} 100\\ 010 \end {matrix} \right ]$$

в которой столбцы $$s_1$$ и $$s_2$$ содержат ненулевые элементы. Следовательно, $$s_1$$ и $$s_2$$ - компоненты, которые необходимы для вычисления неизвестных $$u_1$$ и $$u_2$$.

В соответствии с пунктом 3 процедуры построим матрицу $$[A_{y_1, y_2}]$$, удалив из $$A$$ строки и столбцы с номерами 1, 2, которым соответствуют переменные $$s_1$$ и $$s_2$$

$$[A_{y_1, y_2}]=[0 0]'$$

Поскольку эта матрица нулевая, то в соответствии с процедурой переходим к пункту 4. Выделим в матрице $$B$$ две первые строки, соответствующие компонентам $$s_1$$ и $$s_2$$, и из полученной матрицы удалим два первых столбца, соответствующих переменным $$u_1$$ и $$u_2$$. Оставшаяся матрица

$$[B_{y_1, y_2}]=[0 0]'$$

является нулевой. Построенные в процессе выполнения процедуры матрицы $$[D_{y_1, y_2}], [B_{y_1. y_2}], [A_{y_1, y_2}]$$, а также матрица $$D$$ заданного ЛА удовлетворяют условиям теоремы 16.3. Таким образом, подавтомат, полученный за счет удаления выхода $$y_3$$, является ОБПИ.

В соответствии с процедурой найденный оптимальный ОБПИ имеет следующие характеристические матрицы:

$$A= \left [ \begin {matrix} 10\\ 00 \end {matrix} \right ], B= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ] , C= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ], D= \left [ \begin {matrix} 01\\ 10 \end {matrix} \right ] $$

Пусть, например, начальным состоянием рассматриваемого автомата является $$s(0)=[1,0,1]',$$ а на выходе наблюдается вектор $$[y_1(0), y_2(0)]'=[0,1]'$$. Тогда по формуле (1.2) получаем

$$\left [ \begin {matrix} 0\\ 1 \end {matrix} \right ]= \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ] \left [ \begin {matrix} 1\\ 0 \end {matrix} \right ] \oplus \left [ \begin {matrix} 01\\ 10 \end {matrix} \right ] \left [ \begin {matrix} u_1(0)\\ u_2(0) \end {matrix} \right ]$$

что в координатной форме дает систему

$$0=1 \oplus u_2(0), 1=0 \oplus u_1(0)$$

Отсюда получаем $$U-1(0)=1, u_2(0)=1$$. Вычислим теперь следующее состояние подавтомата по формуле (1.1):

$$\left [ \begin {matrix} s_1(1)\\ s_2(1) \end {matrix} \right ]= \left [ \begin {matrix} 10\\ 00 \end {matrix} \right ] \left [ \begin {matrix} s_1(0)\\ s_2(0) \end {matrix} \right ] \oplus \left [ \begin {matrix} 10\\ 01 \end {matrix} \right ] \left [ \begin {matrix} u_1(0)\\ u_2(0) \end {matrix} \right ]$$

Тогда в координатной форме получаем

$$s_1(1)=s_1(0)+u_1(0)=1 \oplus 1=0, s_2(1)+u_2(0)=1$$

Далее по аналогии с изложенным выше для $$t = 1$$ получаем систему

$$y_1(1)=s_1(1) \oplus u_2(1), y_2(1)=s_2(1) \oplus u_1(1)$$

которая при наблюдаемом, например, векторе [0,1]' становится такой:

$$1=0 \oplus u_2(1), 1=1 \oplus u_1(1)$$

Отсюда $$u_1(1) = 0, u_2(1) = 1$$. Процесс восстановления последующих входных векторов может быть продолжен и далее аналогичным образом.

Заметим, что если у ЛА, для которого ищется оптимальный подавтомат , ОБПИ таков, что $$m > l$$, то этот подавтомат не единственен. В самом деле, пусть у ЛА имеются дублирующие друг друга выходы, т. е. по крайней мере один его выход является избыточным. В этом случае при исключении избыточных выходов множество неизбыточных выходов может быть разным по составу в зависимости от того, какие из дублирующих выходов оставлены и какие исключены. Отсюда следует, что такому ЛА соответствуют различные неизбыточные по выходам автоматы, отличающиеся друг от друга множествами выходных каналов. Очевидно, что построенные для них оптимальные подавтоматы ОБПИ также будут отличаться друг от друга составом выходных каналов.

Если заданный ЛА является неизбыточным по выходам, имеет место следующее утверждение.

Теорема 16.5. Если у неизбыточных по выходам ЛА $$A$$ оптимальный подавтомат ОБПИ существует, то он единственен.

Доказательство. Проведем его методом от противного. Пусть для ЛА $$A$$, у которого $$m=l$$, существует два различных оптимальных подавтомата ОБПИ $$A_1(I_1,J_1)$$ и $$A_2(I_2,J_2) $$. Рассмотрим все возможные соотношения между подмножествами $$I_1, I_2, J_1, J_2$$:

$$I_1 \ne I_2, J_1 \bigcap J_2 = \varnothing$$ или $$J_1 \bigcap J_2 \ne \varnothing $$.

В этом случае в силу оптимальности подавтоматов $$A_1(I_1,J_1) $$ и $$A_2(I_2,J_2) $$ соответствующие им системы уравнений $$D \bar u(t)=C \bar s(t)-\bar y(t)$$, из которых определяются неизвестные, сопоставляемые входным каналам подмножеств $$I_1$$ и $$I_2$$, имеют единственное решение. Объединим эти системы в одну и будем рассматривать ее как систему относительно неизвестных, сопоставляемых входным каналам множества $$I_1 \bigcup I_2$$. Понятно, что последняя система также имеет единственное решение. Это означает, что у исходного ЛА существует такой подавтомат ОБПИ, который при наблюдении сигналов на каналах из множества $$J_1 \bigcap J_2$$ позволяет восстановить сигналы на входных каналах из множества $$I_1 \bigcup I_2$$. Поскольку $$I_1 \ne I_2$$, то $$|I_1 \bigcup I_2|>|I_1|$$ и $$|I_1 \bigcup I_2|>|I_2|$$, следовательно, подавтоматы $$A_1$$ и $$A_2$$ не являются оптимальными ОБПИ подавтоматами, что противоречит исходному предположению.

$$I_1=I_2$$ и $$J_1 \ne J_2$$.

Как и в предыдущем случае, объединим две упоминавшихся системы в одну и будем рассматривать ее как систему относительно неизвестных, соответствующих входным каналам множества $$I_1(I_2)$$. Поскольку $$A_1(I_1,J_1) $$ и $$A_2(I_2,J_2) $$ - оптимальные подавтоматы ОБПИ, ранг объединенной системы равен $$|I_1|$$. Из теоремы 16.4 следует, что для $$A_1(I_1,J_1) $$ и $$A_2(I_2,J_2) $$ выполняются равенства $$|I_1|=|J_1|$$ и $$|I_2|=|J_2|$$. Тогда из неравенства $$J_1 \ne J_2$$ вытекает, что $$|J_1 \bigcup J_2|>|I_1|$$ (или, что все равно, $$|I_2|$$ ).

Ввиду того что ранг матрицы $$D$$ исходного ЛА равен $$|I_1|=|I_2|$$, а $$|J_1 \bigcup J-2|>|I_1|$$, в упомянутой объединенной системе имеется $$|J_1 \bigcup J_2|-|I_1|$$ уравнений, являющихся линейными комбинациями других уравнений той же системы. Последнее означает, что исходный ЛА $$A$$, у которого существует два различных оптимальных ОБПИ подавтомата, имеет избыточные выходы, что противоречит условию теоремы.

Из изложенного следует, что в действительности возможен лишь случай $$I_1=I_2$$ и $$J_1=J_2$$, что и доказывает теорему.

Вопросы и упражнения

Дайте определение избыточного выходного канала линейного автомата.

Сформулируйте ранговый критерий отсутствия у линейного автомата избыточных выходных каналов.

Сформулируйте тот же критерий в терминах отношений между числом входных и выходных каналов линейного автомата БПИ.

Опишите общий метод нахождения избыточных выходных каналов ЛА.

Сформулируйте определение обобщенного линейного автомата БПИ.

Дайте определение обобщенного линейного подавтомата $$A(I,J)$$ линейного автомата $$A$$, где $$I$$ и $$J$$ - заданные подмножества входных и выходных каналов автомата $$A$$.

Опишите процедуру построения обобщенного линейного подавтомата $$A(I,J)$$.

Сформулируйте необходимые и достаточные условия существования обобщенного линейного подавтомата $$A(I,J)$$.

Дайте определение оптимального обобщенного линейного подавтомата $$A(I,J)$$ линейного автомата $$A$$.

В случае существования у ЛА оптимального обобщенного линейного подавтомата $$A(I,J)$$ является ли такой подавтомат единственным?

Страницы: