Линейные автоматы существенно без потери информации

В работах Хаффмена [76] и Ивена [74] были впервые введены автоматы без потери информации (БПИ) и автоматы БПИ конечного порядка (БПИК). Эти автоматы позволяют восстановить неизвестную входную последовательность по наблюдаемой реакции и известному начальному состоянию. В работах [43], [46] были введены и исследованы так называемые автоматы существенно без потери информации (СБПИ) и автоматы СБПИ конечного порядка (СБПИК), являющиеся неинициальными, т. е. такими, у которых начальное состояние неизвестно. В упомянутых работах в терминах графов переходов автомата были получены критерии принадлежности конкретных автоматов перечисленным классам. Заметим, что проверка этих критериев является достаточно трудоемким делом. Ниже будет показано, что для линейных автоматов аналогичные критерии могут быть сформулированы в терминах характеристических матриц и проверяются они достаточно просто.

Отметим, что дискретные устройства, описываемые моделями ЛА СБПИ, обладают одной важной особенностью - для них могут быть построены сравнительно простые и эффективные схемы встроенного контроля (СВК). Такие СВК основаны на сравнении сигналов, поступающих на входы устройств, с сигналами, восстанавливаемыми по выходам. Рассогласование этих сигналов свидетельствует о неправильном функционировании автомата и дает возможность зафиксировать этот факт в момент первого его проявления, не допуская распространения появившейся ошибки.

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

Для преодоления указанных выше недостатков естественно стремление разумным образом сочетать для дискретных устройств как средства тестового, так и функционального контроля. Для устройств, описываемых моделями ЛА, это можно осуществить, выделив из них такие максимальные по размерам подсхемы, которые представляют собой либо автоматы БПИ, либо некоторую их модификацию, с тем, чтобы организовать для них функциональный контроль с применением СВК. Оставшуюся часть исходного устройства можно контролировать с помощью тестов, затраты на построение которых уменьшаются по сравнению с затратами на построение тестов для устройства в целом. В качестве одной из модификаций ЛА БПИ являются обобщенные автоматы БПИ, исследованные в лекции 7.

Напомним определение автомата БПИ, данное Хаффменом [76] в связи с рассмотрением следующей задачи. На автомат, находящийся в известном начальном состоянии $$\bar {s_0}$$, подается неизвестная входная последовательность (слово) $$p$$ и наблюдается реакция w автомата на это слово. Требуется построить эксперимент, проводимый с автоматом после подачи слова $$p$$, позволяющий распознать его. Автоматы, для которых сформулированная задача может быть решена независимо от входной последовательности и начального состояния, называются автоматами БПИ.

В монографии А. Гилла [19] применительно к линейным автоматам также введено иное определение автомата БПИ: линейный автомат называется автоматом БПИ, если по его начальному состоянию и наблюдаемой выходной реакции можно однозначно восстановить неизвестное входное слово. Таким образом, в этом определении, в отличие от определения Хаффмена, проведения дополнительного эксперимента не требуется.

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

Лемма 15.1. Если ранг матрицы $$D$$ ЛА А равен $$l$$, то из любой вершины графа переходов этого автомата не может выходить более одной дуги, помеченной одним и тем же выходным сигналом.

Доказательство. Проведем его методом от противного. Пусть из некоторого состояния $$\bar s \in S_n$$ выходят две дуги, соответствующие двум различным входным сигналам $$\bar {u_1}$$ и $$\bar {u_2}$$, помеченные одним и тем же выходным символом $$\bar y$$. Это означает, что $$\bar u=C \bar s+D \bar {u_1}$$ и $$\bar y=C\bar s+D\bar {u_2}$$. Вычитая одно равенство из другого, получим $$D(\bar {u_1}-\bar {u_2})=[0]$$, или, что то же самое, $$D \bar u=[0]$$. Последнее равенство можно рассматривать как линейную однородную систему уравнений относительно неизвестных $$u=(u_1, u_2, \dots, u_l)'$$, записанную в матричной форме и имеющую ненулевое решение. Известно, что нетривиальное решение однородная система имеет тогда и только тогда, когда ранг матрицы $$D$$ меньше $$l$$, что противоречит условиям леммы.

Вернемся теперь к вопросу об эквивалентности двух приведенных выше определений автомата БПИ.

Пусть автомат Мили $$A$$, находящийся в состоянии $$\bar {s_0}$$, после подачи на него неизвестного входного слова $$p$$ выдал слово $$w$$ и перешел в состояние $$\bar s$$, неизвестное экспериментатору. Подадим на вход установочное слово $$p_1$$ (оно всегда существует, если автомат Мили минимален) и по реакции $$w_1$$ определим его конечное состояние $$\bar {s_1}$$. В [18] доказано, что по состоянию $$\bar {s_1}$$ однозначно устанавливается состояние $$\bar s$$. Наконец, знание состояний $$\bar {s_0}$$ и $$\bar {s_1}$$ и реакции $$w$$ дает возможность распознать входное слово $$p$$. Таким образом, установочный эксперимент играет роль лишь промежуточного звена для определения состояния $$\bar s$$.

В случае линейного автомата БПИ, учитывая лемму 15.1, справедлив следующий факт: при наблюдаемой реакции $$w$$ ЛА, стартующего в состоянии $$\bar {s_0}$$, на неизвестное входное слово $$p$$ в графе ЛА существует единственный путь из $$\bar {s_0}$$ в $$\bar s$$, но не несколько путей, как это может быть в случае автомата Мили БПИ. Отсюда следует, что для ЛА дополнительный установочный эксперимент будет давать избыточную информацию для распознавания слова $$p$$, поскольку отказ от такого эксперимента не повлияет на возможность восстановления упомянутого слова. Итак, знания начального состояния и выходной реакции ЛА достаточно для распознавания неизвестного входного слова и потому применительно к ЛА оба приведенных определения автомата БПИ эквивалентны.

Приведем критерий принадлежности автомата классу автоматов БПИ, доказанный в [19].

Теорема 15.1. Для того чтобы ЛА $$A$$ являлся ЛА БПИ, необходимо и достаточно, чтобы ранг матрицы $$D$$ равнялся $$l$$.

Доказательство. Из уравнения переходов ЛА (10.1) следует, что

$$\bar y(0)-C\bar s(0)=D \baru(0)$$

Последнее равенство можно интерпретировать как систему линейных алгебраических уравнений относительно неизвестных $$u_1(0), u_2(0), \dots, u_l(0)$$, являющихся координатами входного вектора $$\bar u(0)$$. Из алгебры известно, что эта система имеет решение тогда и только тогда, когда ранг $$D$$ равен $$l$$. Зная вектор $$\bar u(0)$$, по формуле (1.1) вычисляем состояние $$\bar s(1)$$, а затем и вектор $$\bar u(1)$$ из системы

$$\bar y(1)-C\bar s(1)=Du(1)$$

Ясно, что справедливость теоремы легко теперь доказать методом математической индукции.

Введем еще одну разновидность автоматов БПИ.

Пусть неизвестная входная последовательность $$p$$ подается на ЛА $$A$$, начальное состояние которого неизвестно и может быть любым состоянием из пространства $$S_n$$, и наблюдается реакция $$w$$ на эту последовательность. Если для заданного ЛА $$A$$ существует такое натуральное число $$N(А) $$, что знания начального отрезка длины $$N(А) $$ слова w достаточно для однозначного определения первого символа слова $$p$$ независимо от входной последовательности $$p$$ и начального состояния ЛА, то $$A$$ называют ЛА существенно БПИ конечного порядка (СБПИК).

Для однозначного определения числа $$N(A)$$ будем считать, что оно является минимальным из всех возможных чисел такого рода и называть порядком ЛА $$A$$. Условимся далее ЛА СБПИК порядка $$k$$ обозначать как ЛА СБПИК- $$k$$.

Перейдем теперь к нахождению критерия принадлежности ЛА классу автоматов СБПИК- $$k$$.

Введем в рассмотрение следующие матрицы:

$$G(0)=[D, C],\\ G(1)= \left [ \begin {matrix} D0C\\ CBDCA \end {matrix} \right ],\\ G(k)= \left [ \begin {matrix} D[0] \dots [0][0]C\\ CBD \dots [0][0]CA\\ \dots \dots \dots \dots \dots \dots \dots \\ CA^{k-1}BCA^{k-2}B \dots CBDCA^k\end {matrix} \right ]$$

Принципы построения этих матриц легко получить из формулы (1.4).

Условимся через $$\bar a(k)$$ и $$\bar y(k)$$ обозначать векторы

$$\bar a (k)=(u_1(0), \dots , u_l(0), \dots , u_1(k-1), \dots , u_l(k-1), s_1(0), \dots , s_k(0))',\\ \bar y(k)=(y_1(0), \dots , y_m(0), \dots , y_1(k-1), \dots , y_m(k-1))'$$

Используя эти обозначения, запишем в матричной форме следующую СЛАУ:

$$G(k)\bar a(k)= \bar y(k)$$

где неизвестными являются координаты вектора $$\bar s(k)$$.

Используя метод Гаусса решения СЛАУ [33], матрицу $$G(k)$$, к которой добавлен столбец $$\bar y(k)$$, всегда можно привести к виду

$$\bar G(k)= \left [ \begin {matrix} 10 \dots g_{1, r+1} \dots g_{1, kl}b_1\\ 01 \dots g_{2, r+1} \dots g_{2, kl}b_2\\ \dots \dots \dots \dots \dots \dots \dots \dots \\ 00 \dots 1 g_{r, r+1} \dots g_{r,kl} b_r\\ \dots \dots \dots \dots \dots \dots \dots \dots \\ 00 \dots 0 g_{d, r+1} \dots g_{d, kl} b_d \end {matrix} \right ] $$

Здесь $$d \le m(k-1), \bar b=(b_1, \dots, b_d)'$$ - вектор, компоненты которого получены из компонент вектора $$\bar y(k)$$ в процессе преобразования по методу Гаусса матрицы $$G(k)$$ с добавленным к ней столбцом $$\bar y(k),$$ в матрицу $$\bar G(k)$$. Выделим из $$\bar G(k)$$ подматрицу, состоящую из первых $$l$$ строк $$\bar G(k)$$ с отброшенным последним столбцом $$\bar b$$, а также столбцами c 1-го по $$r$$ -й:

$$\bar {G_1}(k)= \left [ \begin {matrix} g_{1, r+1} \dots g_{1,kl}\\ g_{2,r+1} \dots g_{2,kl}\\ \dots \dots \dots \\ g_{l,r+1} \dots g_{l,kl} \end {matrix} \right ]$$

Теорема 15.2. Для того чтобы ЛА был автоматом СБПИК- $$k$$, необходимо и достаточно, чтобы $$\bar {G_1}(k)$$ была нулевой матрицей.

Доказательство.Восстановление первого символа $$\bar u(0)=(u_1(0), \dots, u_l(0))'$$ неизвестного слова $$\tilde u(k)= \bar u(0), \bar u(1), \dots, \bar u(k-1)$$ по известной реакции $$\bar y(k)$$, как нетрудно понять, эквивалентно нахождению решения СЛАУ

$$[E_1 \bar {G_1}(k)] \tilde u(k)=\bar {b_1}$$

где $$E_l$$ - единичная матрица размерности $$l\times l, \bar {b_1} $$ - вектор, состоящий из первых $$l$$ координат вектора $$\bar b$$. Если $$\bar {G_1}(k)=[0]$$, то система (15.3) в координатной форме записи примет вид

$$u_1(0)=b_1, u_2(0)=b_2, \dots, u_1(0)=b_l$$

Таким образом, $$u_1(0), \dots, u_l(0)$$, составляющие первый символ неизвестного входного слова ЛА, находятся однозначно. Отсюда следует достаточность условий теоремы.

Понятно, что если $$\bar {G_1}(k) \ne [0]$$, то система (15.3) имеет не единственное решение и, следовательно, однозначное восстановление неизвестного первого входного символа невозможно. Таким образом, условие теоремы является и необходимым.

Пользуясь теоремой 15.2, порядок СБПИК можно определить, проверяя равенство $$\bar {G_1}(k)=[0]$$ последовательно для $$k=0,1, \dots$$ Наименьшее значение $$k$$, для которого это равенство будет выполняться, и будет давать искомый порядок.

Проиллюстрируем изложенное на примере ЛА, заданного над полем GF(2) следующими характеристическими матрицами ( $$n=m=4, l=2$$ ):

$$A= \left [ \begin {matrix} 1000\\ 0100\\ 0010\\ 0001 \end {matrix} \right ],\\ B= \left [ \begin {matrix} 10\\ 00\\ 11\\ 01 \end {matrix} \right ],\\ C= \left [ \begin {matrix} 0100\\ 0001\\ 0000\\ 0100 \end {matrix} \right ],\\ D= \left [ \begin {matrix} 10\\ 00\\ 00\\ 00 \end {matrix} \right ] $$

Пусть на этот ЛА подан неизвестный входной символ $$\bar u(0)=(u_1(0), u_2(0))'$$ и на его выходе наблюдается символ $$\bar y(0)=(1,0,0,0)'$$.

Построим матрицу

$$G(0)= \left [ \begin {matrix} 100100\\ 000001\\ 000000\\ 000100 \end {matrix} \right ] \begin {matrix} y_1(0)\\ y_2(0)\\ y_3(0)\\ y_4(0) \end {matrix} $$

Преобразование ее по методу Гаусса (с отбрасыванием нулевых строк) дает матрицу

$$G(0)= \left [ \begin {matrix} 100000\\ 000100\\ 000001 \end {matrix} \right ] \begin {matrix} y_1(0)\\ y_4(0)\\ y_2 \end {matrix}$$

Поскольку в $$G(0)$$ отсутствует строка вида (0 1 0 …), то символ $$u_2(0)$$ заведомо не восстанавливается по одному наблюдаемому выходному символу. Отсюда следует, что порядок рассматриваемого ЛА больше единицы.

Пусть на исследуемый ЛА подан еще один неизвестный входной символ и на него получена реакция $$\bar y(1)=(0,0,0,0)'$$. Сформируем матрицу

$$G(1)= \left [ \begin {matrix} 10000100\\ 00000001\\ 00000000\\ 00000100\\ \\ 00100100\\ 01000001\\ 00000000\\ 00000100 \end {matrix} \right ] \begin {matrix} y_1(0)\\ y_2(0)\\ y_3(0)\\ y_4(0)\\ \\ y_1(1)\\ y_2(1)\\ y_3(1)\\ y_4(1) \end {matrix}$$

Преобразование ее по методу Гаусса с отбрасыванием нулевых строк дает матрицу

$$\bar G(1)= \left [ \begin {matrix} 10000000\\ 01000000\\ 00100100\\ 00000100\\ 00000001 \end {matrix} \right ] \begin {matrix} y_1(0)+y_4(1)\\ y_2(0)+y_2(1)\\ y_1(1)\\ y_4(1)\\ y_2(0) \end {matrix} $$

В последней матрице подматрица $$\bar {G_1}(1)=[0]$$. Из первых двух строк матрицы $$\bar G(1)$$ получаем искомый результат:

$$u_1(0) = y_1(0)+y_4(1) = 1+0 = 1,\\ u_2(0) = y_2(0)+y_2(1) = 0+0 = 0.$$

Таким образом, порядок исследуемого ЛА равен 2, а при заданных реакциях на входное слово длины 2 первый символ этого слова есть (1, 0)'.

Остановимся теперь на вопросе о том, какой схемой можно восстановить неизвестный входной символ входного слова. Общий вид схемы, решающей эту задачу для ЛА СБПИК- $$k$$, изображен на рис.15.1, где $$D$$ - элемент единичной задержки. Она содержит m сдвиговых регистров, каждый из которых состоит не более чем из $$k-1$$ элементов задержки. Выходы элементов задержки представляют собой значения $$y_1(0), \dots, y_m(0), \dots, y_1(k-1), \dots, y_m(k-1) $$, которые подаются на комбинационную схему с $$l$$ выходами. Эта схема выполняет над перечисленными сигналами операции в соответствии с выражениями, полученными в первых $$l$$ позициях последнего столбца матрицы $$\bar G(k-1)$$.

(рис 15.1)

Понятно, что для ЛА над полем GF(2) соответствующая комбинационная схема содержит только сумматоры по модулю 2, а ее выходами являются компоненты первого символа неизвестного входного слова.

Для рассмотренного примера описанная схема восстановления сигналов $$u_1(0)$$ и $$u_2(0)$$ представлена на рис.15.2.

Подводя итоги изложенному, отметим, что по сравнению с автоматами Мили и Мура, являющимися в общем случае нелинейными, ЛА за счет их специфики позволяют ослабить требования, обеспечивающие восстановление неизвестного входного слова по наблюдаемой реакции. Отметим также, что сама процедура упомянутого восстановления для ЛА значительно менее трудоемка, чем для автоматов Мили. В самом деле, для ЛА она сводится к решению СЛАУ, для чего разработан целый ряд эффективных и простых в реализации методов, и не требует проведения никаких дополнительных экспериментов, необходимых для автоматов Мили.

(рис 15.2)

Кроме того, если для автоматов Мили критерии принадлежности их различным разновидностям автоматов БПИ сформулированы в [19] в терминах довольно громоздких конструкций так называемых проверочных графов, то для ЛА соответствующие критерии удалось сформулировать в терминах их характеристических матриц, довольно просто проверяемых.

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

Приведите определение автомата без потери информации.

Сформулируйте критерий принадлежности автомата этому классу.

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

Сформулируйте критерий принадлежности автомата этому классу.

Опишите метод синтеза комбинационной схемы для восстановления первого символа неизвестного слова, поданного на вход автомата БПИК.