Преобразование автомата для упрощения функционального контроля

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

Обычно функциональный контроль реализуется так, как это изображено на рис.9.1. На этом рисунке блок СВК представляет собой схему встроенного контроля. Как видно из рисунка, рабочие воздействия $$X$$ поступают как на ЦУ, так и на СВК. Помимо последовательности $$X$$ на входы СВК поступают также выходные реакции $$Y$$ ЦУ. На выход $$F$$ СВК выводится информация о техническом состоянии (исправности или неисправности) ЦУ.

Один из принципов построения СВК для комбинационных устройств (КУ), используемый на практике, базируется на восстановлении входов ЦУ (рис.9.2).

Известно, что для КУ блок $$L^{-1}$$ существует не всегда, а необходимым и достаточным условием его существования является наличие у булевых функций, реализуемых блоком $$L$$, свойства обратимости [80].

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

В лекции 4 был рассмотрен класс ОБПИК-автоматов, которые обладают следующим свойством: по наблюдаемой реакции такого автомата на неизвестную входную последовательность длины $$k$$ всегда возможно однозначное восстановление первого символа этой входной последовательности независимо от начального состояния автомата из заданного множества $$S_0$$ допустимых состояний. Отметим, что упомянутое восстановление осуществляется с помощью специальной схемы, описанной в лекции 4, которая фактически является СВК, изображенной на рис.9.2. Существенный недостаток использования упомянутой СВК при $$k \gt; 0$$ состоит в том, что сигнал на ее выходе $$F_0$$ возникшей неисправности в ЦУ появится не в момент ее первого проявления, а через $$k$$ тактов. Понятно, что такая задержка может привести к катастрофическому отказу ЦУ. Таким образом, чтобы исключить такую ситуацию, необходимо, чтобы порядок $$k$$ ОБПИК-автомата был равен 1.

В связи с изложенным возникает задача преобразования произвольного автомата в ОБПИК-автомат порядка 1, которая и будет исследована в этом разделе.

Указанное преобразование будем осуществлять за счет расширения выходного алфавита автомата, достигаемого путем выведения контрольных точек.

Рассмотрим слабоинициальный минимальный автомат Мили $$A=(S,X,Y,\beta, \gamma, S_0)$$, где $$S_0$$ - множество допустимых начальных состояний $$1 \le |S_0| \le |S|$$.

Как следует из теоремы 4.1, необходимое и достаточное условие принадлежности автомата классу ОБПИК порядка 1 состоит в следующем: в его проверочном графе, конструкция которого описана в лекции 4, должны отсутствовать выделенные дуги.

Легко показать, что выведение контрольных точек из автомата $$A$$, преобразующее его в ОБПИК-автомат порядка 1, эквивалентно нахождению такого разбиения $$П=\{K_1, \dots, K_{\gamma}$$ множества $$Q=S+X$$, чтобы проверочный граф автомата $$\tilde A=(S,X,Y \times П, \beta, \Lambda)$$ не имел выделенных дуг. Функция выходов в автомате $$\tilde A $$ такова, что $$\Lambda (s,x)=(\lambda(s,x), K(s,x))$$, где $$K(s,x)$$ - код класса разбиения $$\Pi$$, содержащего пару $$(s,x)$$ в некотором стандартном алфавите.

В формулировке рассматриваемой задачи отсутствует требование минимальности множества контрольных точек, поскольку при его наличии никакого другого метода ее решения, кроме перебора, не существует. Справедливость последнего утверждения вытекает из того, что задача поиска минимального множества контрольных точек может быть сведена к классической задаче о покрытии, относящейся к числу $$NP$$ -полных проблем.

Напомним, что дуга $$\{s_k, s_l\} \to \{s_i, s_j\}$$ с пометкой $$y$$ проверочного графа $$T(A)$$ автомата $$A$$ называется выделенной, если

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

Лемма 9.1. Пусть символ $$y \in Y$$ находится в $$m$$ клетках ТПВ автомата $$A$$, а $$p_1, p_2, \dots, p_y$$ - номера всех столбцов ТПВ, которые этот символ содержат. Если $$n_1, n_2, \dots, n_y$$ - количество символов $$y \in Y$$ в соответствующих столбцах, то число выделенных дуг в проверочном графе автомата $$A$$, помеченных символом $$y$$, равно величине

где $$\sum _{i=1}^{\gamma}C_{n_i}^2=m$$ и $$C^2_{n_i}=0$$, если $$n_i /lt; 2, i=1,2, \dots, r$$.

Доказательство приведенной формулы достаточно очевидно, поэтому мы не будем на нем останавливаться.

Вернемся теперь к рассматриваемой задаче отыскания множества выходных контрольных точек. По построению каждой выделенной дуге $$\{s_k,s_l\} \to |{s_i, s_j|}$$ с пометкой $$y$$ графа $$T(A)$$ соответствует две дуги: $$s_k \xrightarrow {x_1/y} s_i$$ и $$s_l \xrightarrow {x_2/y} S_j$$ графа автомата $$A$$, которые далее именуются ее составляющими. Очевидно, что если изменить выходной сигнал $$y$$ одной из этих дуг, то в проверочном графе для автомата с измененной функцией выхода эта выделенная дуга будет отсутствовать. Воспользуемся этим для удаления всех выделенных дуг в проверочном графе.

Опишем теперь способ получения разбиения $$П$$ множества $$Q=S*X$$. С этой целью сначала сформируем список $$D$$ всех выделенных дуг в проверочном графе $$T(A)$$ автомата $$A$$, упорядочив его произвольным образом. На основе списка $$D$$ составим множество $$L=\{l_1, \dots, l_v\}$$ всех попарно различных дуг графа автомата $$A$$, являющихся составляющими выделенных дуг этого списка. Далее сформируем множество $$M=\{(l_{i_1}, l_{i_2}), \dots, (l_{i_a}, l_{i_b})\}$$ всех таких пар дуг автомата, которые совместно не образуют выделенной дуги проверочного графа. Содержательно принадлежность пары $$(l_i, l_j)$$ множеству $$M$$ означает, что в автомате $$\tilde A$$, полученном из $$A$$ в результате расширения выходного алфавита, дуги $$l_i$$ и $$l_j$$ могут иметь одну и ту же пометку. Вместе с тем, если $$\tilde {l_i}$$ и $$\tilde {l_j}$$ принадлежат разным парам из $$M$$, то их пометки обязательно должны быть различными.

В принятых обозначениях алгоритм получения искомого разбиения $$П$$ можно сформулировать следующим образом:

Проиллюстрируем описанный способ на примере. Пусть автомат $$A$$, у которого $$S_0=S$$, задан своей ТПВ ( табл.9.1), в которой имеется $$m$$ клеток $$(m=6),$$ помеченных одним и тем же выходным символом $$a$$, причем в первом столбце имеется $$n_1=3$$ таких символов, во втором - $$n_2=1$$ и в третьем - $$n_3=2$$. В соответствии с леммой 9.1 общее число выделенных дуг этого автомата равно $$C^2_6-(C^2_3+C^2_2+C^2_1)=15-(3+1+0)=11$$.

Приведем список $$D$$ этих выделенных дуг, каждая из которых имеет одну и ту же пометку $$\underline a$$.

Множество всех попарно различных составляющих выделенных дуг этого списка есть $$L=\{l_1=(1,1), l_2=(1,3) l_3=(2,2), l_4=(2.3), l_5=(2.1) l_6=(3.3)\}$$. Сформируем теперь на основе $$L$$ множество пар дуг $$M=\{(l_1, l_3),(l_1, l_6),(l_2, l_5),(l_3, l_6)\}$$.

Применение предложенного алгоритма дает следующее разбиение $$\Pi$$: $$K_1=\{l_1, l_3, l_6\}; K_2=\{l_2, l_5\}; K_3=\{l_4\}$$.

Поскольку разбиение имеет три класса, для кодирования символов классов достаточно двух двоичных переменных. Пусть $$K_1=00, K_2=10, K_3=01$$, тогда автомат с контрольными точками представлен табл.9.2.

Предположим, что выходные сигналы $$a,b,c$$ закодированы двоичными числами 00, 01 и 10. При таком кодировании часть СВК для рассматриваемого автомата, восстанавливающая входные сигналы, должна, как легко сообразить, реализовывать две булевы функции $$f_1$$ и $$f_2$$, заданные табл.9.3.

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

Исходя из общего определения ОБПИК-автоматов, определение СВО-автоматов может быть сформулировано следующим образом: слабоинициальный автомат $$A=(S, X, Y, \beta, \lambda, S_0)$$ назовем СВО, если

где $$\Gamma \{S_0\}$$ - множество состояний автомата $$A$$, достижимых без состояний множества $$S_0$$.

Из этого определения непосредственно следует критерий принадлежности автомата классу СВО.

Лемма 9.2. Слабоинициальный автомат $$A$$ является СВО-автоматом тогда и только тогда, когда

Отметим существенное различие между (9.1) и (9.2): если в (9.1) используются слова из алфавита $$X$$, то в (9.2) фигурируют символы этого алфавита.

Пусть $$A_1=(S_1, X, Y_1, \beta_1, \lambda_1, S_0^{(1)})$$ и $$A_2=(S_2, Y_1, Y, \beta_2, \lambda_2, S_0^{(2)})$$ - два слабоинициальных автомата, тогда автомат $$A=(S_1 \times S_2, X, Y, \beta, \lambda, S_0)$$ с множеством начальных состояний $$S_0=S_0^{(1)} \times S_0^{(2)}$$ назовем суперпозицией автоматов $$A_1$$ и $$A_2$$, если $$\beta ((S_1, s_2),x)=(\beta_1 (s_1,x), \beta_2 (s_1,x)), \lambda ((s_1, s_2),x)=\lambda_2 (s_2, \lambda_1 (s_1, x))$$.

Нетрудно показать справедливость следующего утверждения.

Лемма 9.3. Суперпозиция СВО-автоматов $$A_1$$ и $$A_2$$ является СВО-автоматом.

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

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